密码学
RSA攻击方法
深入了解RSA密码体制常见漏洞与攻击技术，掌握CTF比赛中的RSA破解方法
学习时间: 70分钟
挑战数量: 5个
难度级别: 高级
RSA攻击概述
RSA是现代密码学中最广泛使用的非对称加密算法之一，虽然其数学基础十分牢固，但在实际应用中由于不当的参数选择、实现缺陷或操作错误，可能导致密码系统遭受各种攻击。本课程将介绍针对RSA密码体制的常见攻击方法及其原理，帮助安全从业者更好地理解RSA的安全边界。
RSA算法回顾
在详细探讨RSA攻击前，我们先简要回顾RSA加密的基本流程：
- 密钥生成：
- 选择两个大素数p和q
- 计算n = p × q
- 计算欧拉函数φ(n) = (p-1) × (q-1)
- 选择整数e，满足1 < e < φ(n)且gcd(e, φ(n)) = 1
- 计算d，满足e × d ≡ 1 (mod φ(n))
- 公钥：(n, e)，私钥：(n, d)
- 加密：对明文m，计算密文c = m^e mod n
- 解密：对密文c，计算明文m = c^d mod n
RSA加密和解密的基本流程
RSA的安全边界
RSA的安全性主要基于大整数分解的计算难度。理论上，如果能够分解n得到p和q，就可以计算φ(n)，从而求出私钥d。然而，RSA的安全边界远不仅限于此，多种攻击方法可以在不分解n的情况下破解RSA：
- 数学攻击：利用RSA数学原理中的弱点
- 参数弱点：针对不当选择的RSA参数
- 实现攻击：利用RSA实现过程中的漏洞
- 侧信道攻击：通过旁路信息推导私钥
常见攻击方法
1. 小指数攻击
当公钥指数e较小（通常为3）且明文m很小时，可能出现m^e < n的情况，此时加密结果c = m^e，无需模运算。攻击者可直接对c开e次方根获得m。
Python - 小指数攻击示例
import gmpy2
def small_exponent_attack(c, e):
"""
当e很小且m^e < n时，可以直接开e次方根
:param c: 密文
:param e: 公钥指数
:return: 明文m（若攻击成功）
"""
# 尝试直接开e次方根
root, is_perfect = gmpy2.iroot(c, e)
if is_perfect:
return int(root)
else:
return None
# 示例
if __name__ == "__main__":
# 假设e=3，明文m很小，导致m^3 < n
c = 27 # 假设密文为27（即3^3）
e = 3
m = small_exponent_attack(c, e)
if m:
print(f"攻击成功! 明文为: {m}")
else:
print("攻击失败，可能m^e >= n")针对较为复杂的情况，如果多个接收者使用相同的小指数e和不同的模数n接收相同的消息，可以使用中国剩余定理（CRT）实施Håstad广播攻击。
2. 共模攻击
当多个用户使用相同的模数n但不同的公钥指数e时，如果一条消息使用两个不同的公钥加密，且两个公钥指数互质，攻击者可利用扩展欧几里得算法恢复原消息。
Python - 共模攻击示例
def extended_gcd(a, b):
"""扩展欧几里得算法计算ax + by = gcd(a,b)中的x,y"""
if a == 0:
return b, 0, 1
else:
gcd, x, y = extended_gcd(b % a, a)
return gcd, y - (b // a) * x, x
def common_modulus_attack(c1, c2, e1, e2, n):
"""
共模攻击，当两个公钥使用相同的n但不同的e时
:param c1: 使用第一个公钥加密的密文
:param c2: 使用第二个公钥加密的密文
:param e1: 第一个公钥指数
:param e2: 第二个公钥指数
:param n: 共同的模数
:return: 明文m
"""
# 计算gcd(e1,e2)和扩展欧几里得算法中的系数s和t
# 满足s*e1 + t*e2 = gcd(e1,e2)
gcd, s, t = extended_gcd(e1, e2)
# 确保e1和e2互质
if gcd != 1:
return None
# 如果t为负数，需要调整
if t < 0:
t = t + e1
s = s - e2
# 计算c1^s * c2^t mod n
c1_s = pow(c1, s, n)
c2_t = pow(c2, t, n)
m = (c1_s * c2_t) % n
return m
# 示例
if __name__ == "__main__":
# 示例参数
n = 143 # 公共模数
e1 = 7
e2 = 17
m = 42 # 原始消息
# 加密
c1 = pow(m, e1, n)
c2 = pow(m, e2, n)
# 攻击
recovered_m = common_modulus_attack(c1, c2, e1, e2, n)
print(f"原始消息: {m}")
print(f"恢复的消息: {recovered_m}")3. 因数分解攻击
RSA的根本安全性基于大数分解的难度。当模数n较小或p、q选择不当时，可能导致n被成功分解。常见的因数分解方法包括：
- 试除法：对于较小的n，尝试用小素数进行除法
- Fermat因数分解：适用于p和q相近的情况
- Pollard's rho算法：更适合找出中等大小的因子
- 二次筛法：适用于分解100位左右的大数
- 一般数域筛法：目前最快的因数分解算法
Python - Fermat因数分解示例
import gmpy2
def fermat_factorization(n, max_iterations=10000):
"""
使用Fermat因数分解方法，适合p和q相近的情况
:param n: 需要分解的模数
:param max_iterations: 最大迭代次数
:return: 因子p和q，若失败则返回None
"""
if n % 2 == 0:
return 2, n // 2
a = gmpy2.isqrt(n)
if a * a == n:
return a, a
a = a + 1
for i in range(max_iterations):
b2 = a * a - n
b = gmpy2.isqrt(b2)
if b * b == b2:
p = a + b
q = a - b
return p, q
a += 1
return None
# 示例
if __name__ == "__main__":
# 选择两个相近的素数
p = 10007
q = 10009
n = p * q
factors = fermat_factorization(n)
if factors:
p_found, q_found = factors
print(f"原始p: {p}, q: {q}")
print(f"分解结果: p: {p_found}, q: {q_found}")4. 低解密指数攻击（Wiener攻击）
当私钥指数d过小（通常d < n^(1/4)）时，可以使用连分数方法恢复私钥。这种攻击方法由Michael J. Wiener提出，利用了连分数逼近可以有效找出e/φ(n)的良好近似值。
Python - Wiener攻击示例
def continued_fraction(num, den):
"""计算分数num/den的连分数展开"""
expansion = []
while den:
q = num // den
expansion.append(q)
num, den = den, num - q * den
return expansion
def convergents(expansion):
"""计算连分数展开的渐进分数"""
n = len(expansion)
numerators = [0, 1]
denominators = [1, 0]
for i in range(2, n + 2):
if i <= n:
term = expansion[i - 2]
else:
term = 0
numerators.append(term * numerators[i - 1] + numerators[i - 2])
denominators.append(term * denominators[i - 1] + denominators[i - 2])
yield (numerators[i], denominators[i])
def wiener_attack(e, n):
"""
实现Wiener攻击恢复小私钥d
:param e: 公钥指数
:param n: 模数
:return: 私钥d（若攻击成功）
"""
# 计算e/n的连分数展开
expansion = continued_fraction(e, n)
# 生成渐进分数
for k, d in convergents(expansion):
if k == 0:
continue
# 检查k/d是否是e/φ(n)的良好近似
phi_approx = (e * d - 1) // k
# 利用φ(n) = (p-1)(q-1) = n - (p+q) + 1
# 有p+q = n - φ(n) + 1
sum_pq = n - phi_approx + 1
# 利用(p+q)^2 - 4n = (p-q)^2，检查是否为完全平方数
discriminant = sum_pq * sum_pq - 4 * n
discriminant_sqrt = gmpy2.isqrt(discriminant)
if discriminant_sqrt * discriminant_sqrt == discriminant:
# 找到可能的p和q
p = (sum_pq + discriminant_sqrt) // 2
q = (sum_pq - discriminant_sqrt) // 2
# 验证p*q是否等于n
if p * q == n:
return d
return None
# 示例
if __name__ == "__main__":
# 生成一个适合Wiener攻击的RSA密钥对
import random
# 选择大素数p和q
p = next_prime(random.randint(10**30, 10**31))
q = next_prime(random.randint(10**30, 10**31))
n = p * q
phi = (p - 1) * (q - 1)
# 选择小的d
d = random.randint(1, int(n**0.25) - 1)
while gcd(d, phi) != 1:
d = random.randint(1, int(n**0.25) - 1)
# 计算e
e = pow(d, -1, phi)
print(f"生成的RSA参数:")
print(f"n = {n}")
print(f"e = {e}")
print(f"d = {d} (私钥)")
# 尝试攻击
recovered_d = wiener_attack(e, n)
if recovered_d:
print(f"攻击成功! 恢复的d = {recovered_d}")
else:
print("攻击失败")5. 模数分解攻击
除了基本的因数分解方法，还有一些特殊情况可以更高效地分解RSA模数：
5.1 共因子攻击
如果有多个RSA公钥，且其中有公钥的模数共享某个素因子，可以通过计算最大公约数（GCD）轻松分解这些模数。
Python - 共因子攻击示例
import math
def gcd_attack(moduli):
"""
检查多个RSA模数是否共享素因子
:param moduli: RSA模数列表
:return: 字典，键为共享因子，值为拥有该因子的模数列表
"""
results = {}
# 比较每对模数
for i in range(len(moduli)):
for j in range(i+1, len(moduli)):
n1 = moduli[i]
n2 = moduli[j]
# 计算最大公约数
g = math.gcd(n1, n2)
# 如果g不是1，则找到共享因子
if g != 1:
if g not in results:
results[g] = []
if n1 not in results[g]:
results[g].append(n1)
if n2 not in results[g]:
results[g].append(n2)
return results
# 示例
if __name__ == "__main__":
# 创建共享素因子的模数
p1 = 13
p2 = 17
p3 = 19
n1 = p1 * p2 # 221
n2 = p1 * p3 # 247
n3 = p2 * p3 # 323
moduli = [n1, n2, n3]
results = gcd_attack(moduli)
print("发现共享因子:")
for factor, affected_moduli in results.items():
print(f"因子 {factor} 被以下模数共享:")
for mod in affected_moduli:
print(f" - {mod} = {factor} × {mod // factor}")5.2 相邻素数攻击
如果选择的p和q太过接近，可以使用类似于Fermat因数分解的方法有效分解模数。如果|p-q|很小，则可以快速找到p和q。
6. 侧信道攻击
侧信道攻击是通过分析密码系统的物理实现（而非数学结构）来破解密码的方法。对RSA的侧信道攻击包括：
- 时间攻击：分析解密操作的时间差异
- 能量分析：测量设备在加解密过程中的能耗
- 故障注入：通过引入计算错误提取私钥信息
- 电磁辐射分析：捕获设备运行时的电磁泄漏
7. 填充攻击（Padding Oracle）
许多RSA实现使用填充方案（如PKCS#1）来增强安全性。如果实现不当，可能导致填充预言机攻击，最著名的是Bleichenbacher的攻击。
伪代码 - PKCS#1 v1.5填充预言机攻击
function bleichenbacher_attack(c, oracle, e, n):
# c: 目标密文
# oracle: 一个预言机，如果解密后填充正确返回true，否则返回false
# e, n: RSA公钥
# 步骤1: 寻找能使oracle返回true的s0
s0 = 1
while not oracle(c * pow(s0, e, n) % n):
s0 += 1
# 步骤2: 缩小m的可能范围
B = 2^(8*(k-2)) # k是密文字节长度
M = [(2*B, 3*B-1)] # 初始范围[2B, 3B-1]
while len(M) > 1 or M[0][1] - M[0][0] > 0:
# 计算新的s值
s = find_next_s(M, n, s0, B)
# 使用预言机测试
if oracle(c * pow(s, e, n) % n):
# 更新区间M
M = update_intervals(M, s, B, n)
# 返回唯一可能的明文值
return M[0][0]CTF中的RSA挑战
RSA相关的CTF挑战是密码学分类中的常见题型，通常需要利用上述攻击方法来破解RSA加密。
常见RSA题型
- 已知部分私钥信息：例如已知p、q的部分位
- 多组相关RSA参数：例如共模攻击场景
- 特殊参数构造：例如使用小指数e或小私钥d
- Oracle利用：提供解密服务，但有特定限制
- 密文格式分析：利用密文或明文的特定格式
CTF解题工具箱
在解决RSA相关CTF题目时，可以使用以下工具和技术：
Python - RSA CTF工具箱
import gmpy2
from Crypto.Util.number import long_to_bytes, bytes_to_long
class RSACTFSolver:
@staticmethod
def factordb_check(n):
"""检查factordb等在线服务查找是否已知分解"""
print(f"请在浏览器中访问: http://factordb.com/index.php?query={n}")
p = int(input("找到的因子p:"))
q = n // p
return p, q
@staticmethod
def decrypt_message(c, d, n):
"""使用私钥(d,n)解密消息c"""
m = pow(c, d, n)
try:
return long_to_bytes(m).decode()
except:
return f"无法解码为ASCII: {m}"
@staticmethod
def check_special_cases(n, e, c):
"""检查常见的特殊情况"""
# 检查小指数
if e <= 3:
# 尝试直接开方
for i in range(3):
root, is_perfect = gmpy2.iroot(c + i*n, e)
if is_perfect:
m = int(root)
return f"小指数攻击成功: {m} ({long_to_bytes(m)})"
# 检查是否为Wiener攻击情况
if e > n:
d = wiener_attack(e, n)
if d:
m = pow(c, d, n)
return f"Wiener攻击成功: {m} ({long_to_bytes(m)})"
return "未找到特殊情况"
@staticmethod
def chinese_remainder_theorem(remainders, moduli):
"""中国剩余定理实现"""
total = 0
N = 1
for modulus in moduli:
N *= modulus
for a_i, n_i in zip(remainders, moduli):
m_i = N // n_i
inv = gmpy2.invert(m_i, n_i)
total += a_i * m_i * inv
return total % N
@staticmethod
def hastad_broadcast_attack(ciphertexts, moduli, e):
"""Håstad广播攻击实现"""
if len(ciphertexts) < e:
return "需要至少e个密文"
c_values = ciphertexts[:e]
n_values = moduli[:e]
# 使用中国剩余定理
x = RSACTFSolver.chinese_remainder_theorem(c_values, n_values)
# 开e次方根
root, is_perfect = gmpy2.iroot(x, e)
if is_perfect:
m = int(root)
return f"广播攻击成功: {m} ({long_to_bytes(m)})"
else:
return "广播攻击失败"实际CTF例题
以下是一个简化的CTF RSA题目示例及其解题过程：
CTF RSA挑战示例
# 示例CTF题目描述
"""
我们截获了一个RSA加密的消息，以及公钥文件。此外，有情报显示私钥指数d非常小。
你能恢复原始消息吗？
已知信息:
n = 9151782661793139884579645941916976975056052281401081907155649491519958947238345327
e = 6859308512356718535239535860897099017599192904087114544138903247230389037547835176061333514331115378405464554059960484771772788598043115001242459572944009
c = 5829358879869349738448348287829860562989951329773923012719611025368724718747857
"""
# 解题思路
import gmpy2
# 1. 注意到e非常大，这可能是一个小d的情况，尝试Wiener攻击
def continued_fraction(num, den):
"""计算分数num/den的连分数展开"""
expansion = []
while den:
q = num // den
expansion.append(q)
num, den = den, num - q * den
return expansion
def convergents(expansion):
"""计算连分数展开的渐进分数"""
n = len(expansion)
numerators = [0, 1]
denominators = [1, 0]
for i in range(2, n + 2):
if i <= n:
term = expansion[i - 2]
else:
term = 0
numerators.append(term * numerators[i - 1] + numerators[i - 2])
denominators.append(term * denominators[i - 1] + denominators[i - 2])
yield (numerators[i], denominators[i])
def wiener_attack(e, n):
"""
实现Wiener攻击恢复小私钥d
:param e: 公钥指数
:param n: 模数
:return: 私钥d（若攻击成功）
"""
# 计算e/n的连分数展开
expansion = continued_fraction(e, n)
# 生成渐进分数
for k, d in convergents(expansion):
if k == 0:
continue
# 检查k/d是否是e/φ(n)的良好近似
phi_approx = (e * d - 1) // k
# 利用φ(n) = (p-1)(q-1) = n - (p+q) + 1
# 有p+q = n - φ(n) + 1
sum_pq = n - phi_approx + 1
# 利用(p+q)^2 - 4n = (p-q)^2，检查是否为完全平方数
discriminant = sum_pq * sum_pq - 4 * n
discriminant_sqrt = gmpy2.isqrt(discriminant)
if discriminant_sqrt * discriminant_sqrt == discriminant:
# 找到可能的p和q
p = (sum_pq + discriminant_sqrt) // 2
q = (sum_pq - discriminant_sqrt) // 2
# 验证p*q是否等于n
if p * q == n:
return d
return None
# 2. 应用Wiener攻击
n = 9151782661793139884579645941916976975056052281401081907155649491519958947238345327
e = 6859308512356718535239535860897099017599192904087114544138903247230389037547835176061333514331115378405464554059960484771772788598043115001242459572944009
c = 5829358879869349738448348287829860562989951329773923012719611025368724718747857
d = wiener_attack(e, n)
if d:
print(f"找到可能的私钥d: {d}")
# 3. 使用私钥解密
from Crypto.Util.number import long_to_bytes
m = pow(c, d, n)
message = long_to_bytes(m)
print(f"解密后的消息: {message.decode()}") # 假设是可读的ASCII
else:
print("攻击失败，私钥d可能不够小")防御措施与最佳实践
为了抵御上述RSA攻击，应遵循以下安全实践：
- 合理选择参数：
- 使用足够大的模数n（当前建议至少2048位）
- 选择合适的公钥指数e（通常为65537）
- 选择足够大的私钥指数d
- 确保p和q的大小相近但不太接近
- 使用安全的填充方案：
- OAEP（最优非对称加密填充）
- PSS（概率签名方案）
- 避免直接使用"原始"RSA
- 防御侧信道攻击：
- 使用恒定时间实现
- 实施随机延迟或混淆
- 使用硬件安全模块（HSM）
- 其他安全措施：
- 使用安全的随机数生成器
- 定期更新密钥
- 实施适当的密钥管理
Python - 安全的RSA参数生成
from Crypto.PublicKey import RSA
from Crypto.Cipher import PKCS1_OAEP
from Crypto.Signature import pss
from Crypto.Hash import SHA256
def generate_secure_rsa_key(bits=2048):
"""生成安全的RSA密钥对"""
# 使用强随机数生成器创建RSA密钥
key = RSA.generate(bits)
# 打印密钥信息
print(f"RSA-{bits}密钥已生成")
print(f"公钥指数 e: {key.e}")
print(f"模数 n 位数: {key.n.bit_length()}")
return key
def secure_rsa_encrypt(message, public_key):
"""使用OAEP填充进行安全的RSA加密"""
# 创建OAEP密码对象
cipher = PKCS1_OAEP.new(public_key, hashAlgo=SHA256)
# 加密消息
ciphertext = cipher.encrypt(message)
return ciphertext
def secure_rsa_decrypt(ciphertext, private_key):
"""使用OAEP填充进行安全的RSA解密"""
# 创建OAEP密码对象
cipher = PKCS1_OAEP.new(private_key, hashAlgo=SHA256)
# 解密消息
try:
message = cipher.decrypt(ciphertext)
return message
except Exception as e:
print(f"解密失败: {e}")
return None
def secure_rsa_sign(message, private_key):
"""使用PSS填充进行安全的RSA签名"""
# 计算消息哈希
h = SHA256.new(message)
# 使用PSS填充方案创建签名
signature = pss.new(private_key).sign(h)
return signature
def secure_rsa_verify(message, signature, public_key):
"""验证RSA-PSS签名"""
# 计算消息哈希
h = SHA256.new(message)
# 验证签名
try:
pss.new(public_key).verify(h, signature)
return True
except Exception as e:
print(f"签名验证失败: {e}")
return False
# 示例使用
if __name__ == "__main__":
# 生成安全的RSA密钥
key = generate_secure_rsa_key(bits=2048)
# 测试消息
message = b"这是一条安全的RSA消息，使用了OAEP填充。"
# 加密
ciphertext = secure_rsa_encrypt(message, key.publickey())
print(f"加密成功，密文长度: {len(ciphertext)} 字节")
# 解密
decrypted = secure_rsa_decrypt(ciphertext, key)
print(f"解密结果: {decrypted.decode() if decrypted else '失败'}")
# 签名
signature = secure_rsa_sign(message, key)
print(f"签名成功，签名长度: {len(signature)} 字节")
# 验证
is_valid = secure_rsa_verify(message, signature, key.publickey())
print(f"签名验证: {'成功' if is_valid else '失败'}")