RSA算法详解与CTF应用总结

1. RSA算法基础

RSA是一种非对称加密算法，由Ron Rivest、Adi Shamir和Leonard Adleman于1977年提出。

1.1 关键参数

• n：模数，是两个大素数p和q的乘积（n = p * q）
• e：公钥指数，通常为65537（0x10001）
• d：私钥指数，满足 e*d ≡ 1 mod φ(n)
• φ(n)：欧拉函数，φ(n) = (p-1)*(q-1)
• m：明文消息
• c：密文消息

1.2 加密与解密过程

加密过程：

c ≡ m^e mod n

解密过程：

m ≡ c^d mod n

2. RSA在CTF中的常见攻击方式

2.1 模数分解攻击

当n较小时（通常小于512位），可以直接分解n得到p和q。

工具：

• factordb.com
• yafu
• msieve

2.2 共模攻击

当相同的明文m用相同的n但不同的e加密时：

已知：

c1 ≡ m^e1 mod n
c2 ≡ m^e2 mod n

如果gcd(e1,e2)=1，可以使用扩展欧几里得算法找到x和y使得：

e1*x + e2*y = 1

则：

m ≡ c1^x * c2^y mod n

2.3 小公钥指数攻击

当e很小（如3）且明文m较小时，可能满足 m^e < n，此时：

c = m^e (未取模)

可直接对c开e次方得到m。

2.4 Wiener攻击

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

2.5 Boneh-Durfee攻击

比Wiener攻击更强的攻击，当d < n^0.292时可能有效。

2.6 已知高位攻击

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

2.7 选择密文攻击

攻击者可以构造特定的密文并获取解密结果，从而推断出私钥信息。

3. 特殊情况的RSA

3.1 p和q相近

当p和q相近时，可以使用费马分解法：

n = p*q
a = ceil(sqrt(n))
while a^2 - n不是完全平方数:
    a += 1
b = sqrt(a^2 - n)
p = a + b
q = a - b

3.2 p-1光滑

当p-1的所有素因子都很小时，可以使用Pollard's p-1算法分解n。

3.3 多素数RSA

n = pqr*...，此时φ(n) = (p-1)(q-1)(r-1)*...

3.4 重复使用p

当两个不同的n共享一个素因子p时：

p = gcd(n1, n2)

4. 实际CTF例题解析

4.1 基础RSA解密

给定：

• n = 920139713
• e = 19
• c = [704796792,...]

步骤：

1. 分解n得到p=18443, q=49891
2. 计算φ(n) = (p-1)(q-1) = 1844249890
3. 计算d ≡ e^-1 mod φ(n)
4. 对每个c计算m ≡ c^d mod n
5. 将m转换为ASCII字符

4.2 共模攻击实例

给定：

• n相同
• e1=17, e2=65537
• c1, c2

步骤：

1. 使用扩展欧几里得算法找到x,y使得17x + 65537y = 1
2. 计算m ≡ c1^x * c2^y mod n
3. 注意x或y可能为负，此时需要计算模逆元

4.3 Wiener攻击实例

给定：

• n = 4606578138840656999
• e = 354611102441307700

步骤：

1. 将e/n展开为连分数
2. 检查每个收敛子是否满足ed ≡ 1 mod φ(n)
3. 找到正确的d后解密

5. 实用工具和脚本

5.1 Python库

from Crypto.Util.number import *
from gmpy2 import *
import sympy

# 基础RSA解密
def rsa_decrypt(n, e, c):
    p, q = factor(n)  # 需要实现或使用外部工具分解
    phi = (p-1)*(q-1)
    d = invert(e, phi)
    m = pow(c, d, n)
    return long_to_bytes(m)

5.2 SageMath脚本

# Wiener攻击实现
def wiener_attack(e, n):
    # 连分数展开和收敛子计算
    # ...
    return d

# Coppersmith方法
n = ...
pbar = ... # p的高位
kbits = ... # 未知低位比特数
PR.<x> = PolynomialRing(Zmod(n))
f = x + pbar
x0 = f.small_roots(X=2^kbits, beta=0.3)[0]
p = pbar + x0

6. 防御措施和安全实践

1. 使用足够大的n（至少2048位）
2. 选择适当的e值（通常为65537）
3. 确保p和q随机且长度相近
4. 避免重复使用模数n
5. 使用OAEP等填充方案而非裸RSA

7. 扩展知识

7.1 RSA签名

签名生成：

s ≡ m^d mod n

签名验证：

m ≡ s^e mod n

7.2 RSA-OAEP

最优非对称加密填充，提供更强的安全性。

7.3 RSA与PSS

概率签名方案，提供更强的安全性。

8. 总结

RSA在CTF中是一个常见考点，理解其数学原理和各种攻击场景对于解决相关问题至关重要。掌握模运算、欧拉定理、中国剩余定理等数学知识，并熟练使用相关工具和脚本，是成功解决RSA挑战的关键。