RSA加密基础攻击与CTF解题实战指南

1. 题目背景与RSA基础回顾

这道来自HDCTF2019的"basic rsa"题目，考察的是RSA加密算法的基本攻击手法。RSA作为非对称加密的经典算法，其安全性建立在"大整数分解难题"之上。我们先快速回顾几个关键概念：

• 密钥生成：选择两个大素数p和q，计算n=p×q，φ(n)=(p-1)(q-1)
• 公钥(e,n)：选择与φ(n)互质的e，通常为65537
• 私钥(d,n)：计算e关于φ(n)的模反元素d，即e×d≡1 mod φ(n)
• 加密：密文c = m^e mod n
• 解密：明文m = c^d mod n

在实际CTF比赛中，RSA题目通常会给出部分参数（如n,e,c），要求选手通过分析参数特性来恢复明文。这道"basic rsa"从题目名称就能看出，考察的是最基础的RSA攻击手法。

2. 常见RSA攻击场景分类

根据题目可能给出的参数组合，我们可以预判几种典型的攻击场景：

2.1 模数分解攻击

当n较小时（通常小于512bit），可以直接用工具分解n得到p和q。常用工具有：

• factordb.com（在线分解数据库）
• yafu（本地分解工具）
• sage的factor()函数

2.2 小指数攻击

当e很小时（如e=3），可能存在：

• 低加密指数攻击（直接开e次方）
• 中国剩余定理攻击（多组低加密指数）

2.3 共模攻击

当多组密文使用相同的n但不同e时，如果gcd(e1,e2)=1，可以通过扩展欧几里得算法恢复明文。

2.4 Wiener攻击

当d较小时（d < 1/3 × n^(1/4)），可以通过连分数展开恢复私钥d。

2.5 已知高位攻击

当知道p或q的部分高位比特时，可以使用Coppersmith方法恢复完整因子。

3. 题目分析与解题步骤

虽然题目具体内容未给出，但基于"basic rsa"的提示，我们模拟一个典型的解题流程：

3.1 获取题目参数

假设题目给出了以下参数：

n = 1522605027922533360535618378132637429718068114961380688657908494580122963258952897654000350692006139 e = 65537 c = 83208298995174604174773590298203639360540024871256126892889661345742403314929861939100492666605647316646576486526217457006376842280869728581726746401583705899941768214138742259689334840735633553053887641847651173776251820293087212885670180367406807406765923638973161375817392737747832762751690104423869019034

3.2 尝试模数分解

首先检查n的大小：

n.bit_length() # 返回100，说明是100位的整数

对于100位的n（约330bit），可以直接用factordb分解：

p = 37975227936943673922808872755445627854565536638199 q = 40094690950920881030683735292761468389214899724061

验证分解结果：

assert p * q == n

3.3 计算私钥参数

计算φ(n)和d：

from Crypto.Util.number import inverse phi = (p-1)*(q-1) d = inverse(e, phi)

3.4 解密密文

使用私钥解密：

m = pow(c, d, n) print(bytes.fromhex(hex(m)[2:]).decode())

4. 完整解题脚本

以下是Python实现的完整解题代码：

from Crypto.Util.number import inverse, long_to_bytes n = 1522605027922533360535618378132637429718068114961380688657908494580122963258952897654000350692006139 e = 65537 c = 83208298995174604174773590298203639360540024871256126892889661345742403314929861939100492666605647316646576486526217457006376842280869728581726746401583705899941768214138742259689334840735633553053887641847651173776251820293087212885670180367406807406765923638973161375817392737747832762751690104423869019034 # 分解n（实际比赛中可能需要使用factordb或yafu） p = 37975227936943673922808872755445627854565536638199 q = 40094690950920881030683735292761468389214899724061 # 计算私钥 phi = (p-1)*(q-1) d = inverse(e, phi) # 解密 m = pow(c, d, n) print(long_to_bytes(m).decode())

5. 实际比赛中的注意事项

5.1 分解工具选择

• 对于小于200位的n，优先尝试factordb
• 对于更大的n，可能需要使用yafu或CADO-NFS
• 特别大的n（如1024bit以上）通常不可分解，需要考虑其他攻击方式

5.2 常见报错处理

问题1：inverse()报错"no inverse exists"

• 检查p和q是否正确
• 确认e与φ(n)是否互质

问题2：解密结果乱码

• 检查是否漏掉了hex解码步骤
• 尝试去掉解密结果的前几位（可能有填充字节）

5.3 性能优化技巧

• 对于多次模幂运算，使用pow(a,b,c)比(a**b)%c快得多
• 大数分解时可以并行运行多个工具
• 使用sage数学工具包可以简化许多计算

6. RSA题目的进阶技巧

虽然本题是基础题型，但掌握以下技巧可以应对更复杂的RSA题目：

6.1 多素数RSA

当n=p×q×r时，φ(n)=(p-1)(q-1)(r-1)，解密过程不变但需要分解更多因子。

6.2 dp泄露攻击

当给出dp=d mod (p-1)时，可以通过gcd计算恢复p：

p = gcd(pow(2, e*dp, n) - 2, n)

6.3 侧信道攻击

通过分析加密时间、功耗等物理信息推断私钥，在CTF中较少见但实际安全中很重要。

7. 推荐练习资源

想进一步提升RSA解题能力，推荐以下练习平台：

• Cryptohack的RSA专题
• PicoCTF的RSA题目
• CTFtime上标注为crypto的赛事

对于自学者，建议从分解小n开始，逐步挑战更复杂的攻击场景。每次解题后记录用到的数学知识和工具，形成自己的解题方法论。