CTF BUUOJ [WUSTCTF2020]babyrsa【RSA解密实战】完整解题流程（附Python脚本）

一、题目背景

本题是经典的BabyRSA入门解密题，核心考察RSA算法的基本解密流程，重点在于大数分解、欧拉函数计算、模逆元求解及明文还原。题目给出的模数n仅77位十进制数（约256比特），在现有计算能力下可轻松分解，适合RSA初学者上手练习。

题目参数

密文 c = 28767758880940662779934612526152562406674613203406706867456395986985664083182
模数 n = 73069886771625642807435783661014062604264768481735145873508846925735521695159
公钥指数 e = 65537

题目要求：解密密文c，将明文按flag{明文}格式提交。

二、RSA解密核心原理回顾

RSA算法解密的核心流程为：

1. 分解模数n得到两个质因数p和q（RSA的核心前提：n = p × q）；
2. 计算欧拉函数φ(n) = (p-1) × (q-1)；
3. 求公钥指数e在模φ(n)下的模逆元，即私钥d（满足e × d ≡ 1 mod φ(n)）；
4. 解密密文：m = c^d mod n（m为明文整数）；
5. 将整数m转换为可读字符串，得到最终flag。

三、分步解题过程

步骤1：分解模数n（关键！）

RSA解密的核心难点是分解大数n，本题n仅77位，可通过在线工具factordb.com快速分解（也可使用yafu、sympy等本地工具）。

操作步骤：

1. 打开factordb.com；
2. 在搜索框输入模数n：73069886771625642807435783661014062604264768481735145873508846925735521695159；
3. 点击Factorize!按钮，得到分解结果（状态显示FF表示完全分解）：

   p = 189239861511125143212536989589123569301
   q = 386123125371923651191219869811293586459
   

4. 验证：p × q = n（必须保证等式成立，否则后续解密全错）。
   

步骤2：计算欧拉函数φ(n)

根据欧拉函数性质，若n = p × q（p、q为质数），则：
$$\varphi (n)=(p-1)\times (q-1)$$
代入正确的p、q计算即可。

步骤3：求解私钥d（模逆元）

私钥d是e在模φ(n)下的模逆元素，需满足：
$$d\equiv e^{-1}(\mathrm{mod}\varphi (n))$$
Python中可通过libnum.invmod(e, phi_n)或pow(e, -1, phi_n)（Python3.8+支持）快速求解。

步骤4：解密密文得到明文整数

通过RSA解密公式计算明文整数m：
$$m\equiv c^d(\mathrm{mod}n)$$
Python中用pow(c, d, n)高效计算（避免大数幂运算溢出）。

步骤5：整数转可读字符串

将明文整数m转换为字节串，再解码为UTF-8字符串，即可得到flag内容。

四、完整Python解题脚本

import libnum

# ====================== 题目参数 ======================
c = 28767758880940662779934612526152562406674613203406706867456395986985664083182
n = 73069886771625642807435783661014062604264768481735145873508846925735521695159
e = 65537

# ====================== 分解n得到的正确p、q ======================
p = 189239861511125143212536989589123569301
q = 386123125371923651191219869811293586459

# 验证p*q是否等于n（排查分解错误）
print(f"p × q == n: {p * q == n}")

# ====================== 计算欧拉函数φ(n) ======================
phi_n = (p - 1) * (q - 1)

# ====================== 计算私钥d（模逆元） ======================
# 方案1：使用libnum库（需提前安装：pip install libnum）
d = libnum.invmod(e, phi_n)
# 方案2：Python3.8+内置方法（无需第三方库）
# d = pow(e, -1, phi_n)

# ====================== 解密密文 ======================
m_int = pow(c, d, n)

# ====================== 整数转可读字符串 ======================
try:
    # 优先UTF-8解码
    flag_content = libnum.n2s(m_int).decode('utf-8')
except UnicodeDecodeError:
    # 容错：Latin-1解码（兼容所有字节）
    flag_content = libnum.n2s(m_int).decode('latin-1')

# ====================== 输出结果 ======================
print(f"解密得到的明文: {flag_content}")
print(f"flag: flag{{{flag_content}}}")

五、运行结果与验证

脚本运行输出：

p × q == n: True
解密得到的明文: wctf2020{just_@_piece_0f_cak3}
flag: flag{wctf2020{just_@_piece_0f_cak3}}

验证：输出的flag符合题目要求的格式，且明文为有意义的字符串，解密成功。

flag{just_@_piece_0f_cak3}

。

六、常见问题与避坑指南

1. 分解n得到错误的p/q

• 现象：解密出的字符串是乱码（如@¯MŽ¬9&‚}ºWw4£ÇF㶭‡˜*ÙékÇš€）；
• 原因：p × q ≠ n，导致欧拉函数和私钥计算错误；
• 解决：通过factordb分解后务必验证p × q = n。

2. 解码时出现UnicodeDecodeError

• 现象：'utf-8' codec can't decode byte 0x81 in position 1: invalid start byte；
• 原因：明文字节串非UTF-8编码；
• 解决：增加多编码尝试（UTF-8→GBK→Latin-1）或errors='ignore'容错。

3. 未安装libnum库

• 报错：ModuleNotFoundError: No module named 'libnum'；
• 解决：执行pip install libnum安装，或使用Python内置方法替代（脚本中已标注）。

七、总结

本题是典型的RSA入门题，核心考点为：

1. 大数分解工具的使用（factordb是RSA解题必备）；
2. RSA解密流程的完整实现；
3. 编码容错处理（避免因编码问题导致结果异常）。

对于RSA解密类题目，只要能正确分解模数n得到p和q，后续步骤均为固定流程，掌握后可应对绝大多数入门级RSA题目。

附：环境配置

• Python版本：3.8+（推荐3.10+）；
• 依赖安装：pip install libnum（如需使用sympy分解n，可安装pip install sympy）。