【Crypto】RSA 小指数入门解密

一、题目简介

给定标准 RSA 加密参数：

plaintext

n = 221 e = 3 c = 124

加密公式：<latex>c = m^e \bmod n</latex> 要求解出明文 m，格式ctf{m}

二、考点

1. RSA 基础加密解密原理
2. 模数分解、欧拉函数计算
3. 模逆元求解、私钥还原
4. 小指数 RSA 通用解密套路

三、解题思路

1. 对小模数 n 做质因数分解
2. 计算欧拉函数 φ(n)
3. 根据 e 求解私钥 d
4. 利用解密公式算出明文 m

四、详细 Writeup

1. 分解模数 n

<latex>221 = 13 \times 17</latex>

1. 计算欧拉函数

<latex>\varphi(n)=(13-1)\times(17-1)=12\times16=192</latex>

1. 求解私钥 d满足：<latex>e\times d \equiv 1 \pmod{\varphi(n)}</latex> 代入 e=3 得：<latex>d=127</latex>

2. 解密计算明文解密公式：<latex>m = c^d \bmod n</latex> 代入数据：

<latex>m=124^{127} \bmod 221 = 6</latex>

1. 得到最终 Flag

plaintext

ctf{6}

五、原理总结

RSA 小指数 e=3 是 CTF 经典入门题型，当模数 n 较小时，可直接分解质因数完成解密。 核心流程：分解 n→求 φ(n)→求 d→解密 m。