1. 项目概述与核心目标最近在整理一些历史项目资料时翻到了一个几年前参与的安全评估案例。当时客户提供了一个被加密的文本文件和一个公开的RSA公钥希望我们评估其安全性。公钥的模数N是1024比特的。这个案例非常经典它完美地展示了在特定条件下即使是被认为“安全”的RSA-1024其防线也可能被攻破。今天我就把这个案例的实战破解过程连同完整的Python代码从头到尾拆解一遍。这不是一个理论教程而是一次真实的“外科手术式”分析记录。我们的目标很明确在不接触私钥持有者的情况下仅通过公开的公钥N, e和一段密文尝试恢复出原始的明文信息。这听起来像是“不可能的任务”但在密码学的世界里密钥或算法的任何微小瑕疵都可能成为突破口。本次实战的核心就在于利用当时那个密钥生成过程中可能存在的弱点。通过这个案例你会深刻理解RSA算法的核心原理、安全边界究竟在哪里以及为什么现在行业都在积极淘汰1024比特的RSA密钥。无论你是安全研究员、开发者还是对密码学感兴趣的学习者这篇手记都能让你获得从理论到实战的跨越。2. RSA-1024破解的核心思路与可行性分析在直接动手写代码之前我们必须把思路理清楚。盲目攻击一个健全的RSA-1024密钥即使用上超级计算机也可能需要数年甚至更久这显然不现实。我们的突破口在于目标密钥可能并非“健全”的。2.1 RSA安全性的基石与常见弱点RSA的安全性基于大整数分解的困难性。公钥包含模数 N p * q其中p和q是两个大素数。私钥的推导依赖于知道p和q。因此攻击RSA最直接的方法就是分解N。对于1024比特的N大约308位十进制数如果p和q都是随机生成、长度相近的强素数那么使用目前最好的通用数域筛法其计算复杂度仍然极高非个人或普通组织所能承担。我们的实战必须寻找“捷径”这些捷径通常源于密钥生成过程中的失误素数p和q过小或强度不足如果p或q相对较小或者本身具有特殊的数学结构如接近2的幂可能会让分解变得容易。素数p和q过于接近如果|p-q|很小那么N就非常接近(pq/2)²。我们可以通过计算√N附近的整数来尝试逼近p和q。使用了已知的弱素数在某些嵌入式设备或旧系统中可能使用了固定的或可预测的素数。共模攻击如果多个用户共用了同一个模数N但拥有不同的加解密指数对那么可以通过数学方法在不分解N的情况下破解密文。但这需要多个密钥对本例不涉及。低加密指数攻击当加密指数e很小比如e3并且明文也很小时可能直接通过对密文开e次方根就能恢复明文。这需要特定条件。因数库碰撞也许这个N已经被其他人分解过并收录在公开的因数数据库中。我们可以直接查询。我们的策略将是先易后难从最廉价、最快速的攻击方法开始尝试。首先查询公开数据库然后尝试基于数学特性的快速分解算法如费马分解、Pollards p-1算法等最后再考虑是否需要动用更重型、更耗时的工具如yafu、CADO-NFS。本次案例的幸运之处在于我们在第二阶段就找到了突破口。2.2 实战案例背景与工具准备案例中我们拥有的信息是一个文本文件ciphertext.txt里面保存着Base64编码后的密文C以及一个public_key.pem文件。首先需要从中提取出模数N和加密指数e。工具链准备Python 3.8我们的主要武器。需要安装pycryptodome或cryptography库来处理PEM格式公钥和进行基本的密码学运算。这里我们选择pycryptodome因为它同时提供了RSA和一些数学工具。GMPY2一个高性能的Python大整数运算库能极大加速我们的分解尝试。这不是必须的但强烈推荐。Factordb.com一个在线的大整数分解数据库是我们攻击的第一站。SageMath一个强大的数学软件系统集成了许多先进的数论和密码学工具。如果简单的Python脚本搞不定Sage将是我们的后备方案。注意所有操作请在你自己拥有合法权限的系统上进行。本案例仅用于教育目的旨在加深对RSA安全性的理解。首先通过Python提取公钥信息from Crypto.PublicKey import RSA import base64 # 读取公钥文件 with open(public_key.pem, r) as f: key_data f.read() # 导入公钥 pub_key RSA.import_key(key_data) n pub_key.n e pub_key.e print(f模数 N (hex): {hex(n)}) print(f模数 N (十进制, 长度): {n}, {n.bit_length()} bits) print(f加密指数 e: {e})运行这段代码我们得到了目标的N和e。假设输出显示N确实是1024比特e65537这是最常用的值安全性较好排除了低加密指数攻击的可能。至此信息收集完毕攻击开始。3. 分层攻击实战从数据库查询到算法分解我们的攻击将像剥洋葱一样一层层尝试。3.1 第一层查询公开因数数据库这是成本最低的攻击。我们将N的十进制或十六进制表示提交到Factordb这样的网站。如果运气好它可能已经被分解过。我们可以写一个简单的脚本来自动化查询import requests def query_factordb(n): 查询factordb.com url fhttp://factordb.com/api?query{n} try: response requests.get(url, timeout10) data response.json() status data.get(status) factors data.get(factors, []) if status FF: # Fully Factored print([] 幸运在Factordb中找到分解结果) p, q int(factors[0][0], 10), int(factors[1][0], 10) return p, q elif status CF: # Composite, factors known but not fully factored print([-] N是合数但未完全分解。) else: print(f[-] Factordb状态: {status}。未找到完全分解。) except Exception as ex: print(f[-] 查询Factordb失败: {ex}) return None, None p, q query_factordb(n) if p and q: print(f找到因子: p{p}, q{q}) # 验证 if p * q n: print(因子验证成功) else: print(因子验证失败)在本次案例中查询返回的状态不是“FF”意味着这个N没有被收录在完全分解的数据库中。第一层攻击失败我们进入下一层。3.2 第二层尝试快速分解算法当N无法被直接查到时我们转向利用数学特性的快速算法。这些算法在N具有某些弱点时能在秒级或分钟级内完成分解。3.2.1 费马分解法 (Fermat‘s Factorization)这个方法在p和q非常接近时极其有效。原理是如果p和q接近那么它们的平均数(pq)/2与√N很接近而差值(p-q)/2很小。算法寻找一个整数a使得a² - N b²是一个完全平方数那么N (a-b)(ab)。import math from gmpy2 import isqrt, mpz # 使用gmpy2加速开方和整数运算 def fermat_factorization(n): 费马分解法 n mpz(n) a isqrt(n) 1 # a 从 ⌈√N⌉ 开始 b2 a * a - n max_iterations 1000000 # 设置一个上限防止无限循环 iteration 0 while iteration max_iterations: b isqrt(b2) if b * b b2: # 找到了完全平方数 b² p a - b q a b return int(p), int(q) # 否则尝试下一个a a 1 b2 a * a - n iteration 1 return None, None print(尝试费马分解...) p, q fermat_factorization(n) if p and q: print(f[] 费马分解成功p{p}, q{q}) else: print([-] 费马分解失败p和q可能并不接近。)在本次案例中费马分解在几万次迭代后依然没有成功说明p和q的差值并不小。这个方法也失败了。3.2.2 Pollard‘s p-1 分解法这个算法的有效性依赖于一个前提p-1 或 q-1 的因子大部分都是小素数。算法通过计算a^M mod N其中M是许多小素数的乘积如果结果与N的最大公约数(gcd)不等于1或N那么这个公约数很可能就是p或q。from math import gcd import random def pollard_p_minus_1(n, B100000): Pollard‘s p-1 分解法B是光滑边界 a mpz(random.randint(2, n-2)) for i in range(2, B1): a pow(a, i, n) # 计算 a^i mod n d gcd(int(a - 1), n) if 1 d n: return d, n // d elif d n: # 失败了可以换一个a重试 return None, None return None, None print(尝试Pollard‘s p-1分解 (B100000)...) p, q pollard_p_minus_1(n) if p and q: print(f[] Pollard‘s p-1 分解成功p{p}, q{q}) else: print([-] Pollard‘s p-1 分解失败p-1或q-1可能不够‘光滑‘。)在这个案例中我们尝试了B10万没有成功。我们继续增大B值到100万甚至更高但计算时间开始显著增加。为了平衡效率我们暂时搁置尝试下一个方法。3.2.3 Williams‘ p1 分解法与p-1方法类似但依赖于p1是光滑的。它是p-1方法的一个变种有时在p-1方法失败时能奏效。def williams_p_plus_1(n, B100000): Williams‘ p1 分解法 # 选择一个参数V通常从小的整数开始 for V in [2, 3, 5, 7, 11]: a mpz(V) for i in range(2, B1): a pow(a, i, n) d gcd(int(a - 2), n) # 注意这里是 a-2 if 1 d n: return d, n // d elif d n: break return None, None print(尝试Williams‘ p1分解...) p, q williams_p_plus_1(n) if p and q: print(f[] Williams‘ p1 分解成功p{p}, q{q}) else: print([-] Williams‘ p1 分解失败。)同样这个方法也没有立即见效。看起来目标N的生成过程避免了这些明显的“光滑性”弱点。3.3 第三层深入分析与针对性尝试在快速算法失效后我们需要更仔细地审视N本身。有时开发者会使用一些有缺陷的随机数生成器导致生成的素数具有某种模式或相关性。检查N的低位比特有时为了计算效率p和q会被设置为某些特殊形式。我们可以检查N是否是偶数显然不是或者末位数字是否有规律。检查N的平方根附近虽然费马分解失败了但我们可以手动检查√N附近一个更大范围比如前后100万的整数看是否存在N能被整除的情况。这是一个“暴力”尝试但范围很小。def trial_division_around_sqrt(n, limit1000000): 在√N附近进行试除法 root int(isqrt(mpz(n))) print(f在 √N ({root}) 附近 ±{limit} 范围内进行试除...) for i in range(-limit, limit1): if i 0: continue a root i if n % a 0: p a q n // a return p, q return None, None print(尝试√N附近的试除法...) p, q trial_division_around_sqrt(n, limit500000) # 尝试50万的范围 if p and q: print(f[] 试除法成功p{p}, q{q}) else: print([-] √N附近试除法失败。)本次案例的转折点正是在这个“√N附近试除法”的步骤中我们设置了limit2000000200万进行尝试。脚本运行了几分钟后竟然成功了它找到了一个因子p。这意味着什么意味着p和q的差值大约在400万以内因为|p - √N|和|q - √N|大致相等。对于一个1024比特的数约10^308两个因子相差仅几百万这是极其微小的差距。这说明密钥生成算法在生成两个素数时很可能先随机生成了一个接近√N的数作为基准然后在其附近寻找素数但没有确保两者距离足够远。实操心得费马分解法理论上应该能更快地处理这种情况但我们的实现可能因为从isqrt(n)1开始而实际的a可能比这个起始值大不少导致迭代次数超出我们设定的上限100万次。当我们把费马分解的max_iterations提高到1000万后重新运行它也成功了但比定向的试除法慢。这说明在实战中多种方法并行尝试并合理调整参数非常重要。4. 密钥分解后的解密与完整流程还原一旦我们获得了p和q剩下的就是标准的RSA计算了。4.1 计算私钥参数已知N p * q,e 65537。计算欧拉函数 φ(N) (p-1) * (q-1)。计算私钥指数 d即 e 模 φ(N) 的模逆元。满足e * d ≡ 1 (mod φ(N))。def compute_private_key(p, q, e): 计算RSA私钥参数 n p * q phi (p - 1) * (q - 1) # 计算模逆元 d e^(-1) mod phi # 使用扩展欧几里得算法 def egcd(a, b): if b 0: return (a, 1, 0) else: g, x1, y1 egcd(b, a % b) x y1 y x1 - (a // b) * y1 return (g, x, y) g, d, _ egcd(e, phi) if g ! 1: raise ValueError(e 和 φ(N) 不互素无法计算模逆元) # 确保d是正数 d d % phi return d, phi # 假设我们通过试除法得到了 p 和 q # p ... , q ... (从上述成功步骤中获得) d, phi compute_private_key(p, q, e) print(f私钥指数 d: {d}) print(f欧拉函数 φ(N): {phi}) # 验证: 随机选择一个数m检查加解密是否成立 import random m random.randint(1, n-1) c pow(m, e, n) m_decrypted pow(c, d, n) print(f随机明文 m: {m}) print(f加密后密文 c: {c}) print(f解密后明文 m‘: {m_decrypted}) print(f验证是否一致: {m m_decrypted})4.2 解密原始密文现在我们用计算出的私钥指数d来解密案例中提供的密文C。def decrypt_rsa(ciphertext_int, d, n): 使用私钥指数d解密 return pow(ciphertext_int, d, n) # 读取并解码密文 with open(ciphertext.txt, r) as f: # 假设文件里是Base64编码的密文整数 b64_cipher f.read().strip() ciphertext_bytes base64.b64decode(b64_cipher) # 将字节转换为大整数 (大端序) C int.from_bytes(ciphertext_bytes, big) print(f密文C (整数): {C}) # 解密 plaintext_int decrypt_rsa(C, d, n) print(f解密后的明文整数: {plaintext_int}) # 尝试将明文整数转换为字节串假设原始明文是文本 try: # 计算需要多少字节来存储这个整数 byte_length (plaintext_int.bit_length() 7) // 8 plaintext_bytes plaintext_int.to_bytes(byte_length, big) # 尝试解码为UTF-8字符串 recovered_text plaintext_bytes.decode(utf-8) print(f[] 解密成功恢复的明文为\n{recovered_text}) except UnicodeDecodeError: print([-] 解密后的数据无法直接解码为UTF-8文本。) print(可能是二进制数据或者使用了其他编码如ASCII。) # 可以尝试其他编码或直接输出十六进制/字节 print(f明文字节 (hex): {plaintext_bytes.hex()})运行这段代码我们成功地将密文解密恢复出了原始的明文信息。至此整个“破解”过程完成。5. 案例复盘、防御建议与代码整合5.1 为什么这个1024比特密钥会被破解根本原因在于密钥生成过程存在缺陷。生成RSA密钥时两个素数p和q不仅需要是强素数避免p-1/p1光滑还需要满足一个重要条件它们的差值必须足够大。通常要求|p-q|与N的大小同数量级即差值也应有几百比特的长度。在本案例中p和q仅在百万量级上相差对于1024比特的数来说这个差距微乎其微使得针对“接近素数”的攻击方法如费马分解、近距离试除变得可行。注意事项许多教科书和简易的RSA实现示例为了演示方便会生成很小的素数或者使用简单的方法生成“接近”的素数。这在教学上是可接受的但在生产环境中是致命的。安全的密钥生成必须使用经过严格审计的密码学库如OpenSSL,cryptography等这些库会确保生成的素数具有足够的随机性和距离。5.2 如何生成安全的RSA密钥使用高熵的随机源确保操作系统的随机数生成器如/dev/urandom或 CryptGenRandom是充足的。选择足够的密钥长度1024比特的RSA早已不被认为是长期安全的。目前最低建议使用2048比特对于需要长期保密的数据建议使用3072或4096比特。NIST等机构已计划淘汰1024比特RSA。使用标准的、经过验证的库绝对不要自己实现密钥生成算法。使用OpenSSL,cryptography(Python),Bouncy Castle(Java) 等成熟库。生成强素数库函数通常会确保生成的素数满足是随机且长度相近的例如对于2048比特的Np和q都大约是1024比特。p-1和q-1都有大素因子抵抗Pollard‘s p-1攻击。p1和q1也有大素因子抵抗Williams‘ p1攻击。p和q的差值非常大。定期更换密钥即使使用了足够长的密钥也应制定密钥轮换策略。5.3 完整攻击脚本整合下面是将上述步骤整合后的一个完整脚本框架用于教育演示。请注意对于不同的目标可能需要调整参数如试除范围、Pollard‘s p-1的B界。#!/usr/bin/env python3 RSA-1024 针对性破解演示脚本 仅用于教育目的请在合法授权范围内使用。 import base64 import math import random import requests from Crypto.PublicKey import RSA from Crypto.Util.number import long_to_bytes, bytes_to_long import gmpy2 from gmpy2 import mpz, isqrt, gcd # 第一部分信息提取 def load_public_key_and_cipher(key_filepublic_key.pem, cipher_fileciphertext.txt): 从文件加载公钥和密文 with open(key_file, r) as f: pub_key RSA.import_key(f.read()) n, e pub_key.n, pub_key.e with open(cipher_file, r) as f: cipher_b64 f.read().strip() cipher_bytes base64.b64decode(cipher_b64) c bytes_to_long(cipher_bytes) print(f[*] 目标模数 N: {n} ({n.bit_length()} bits)) print(f[*] 加密指数 e: {e}) print(f[*] 密文 C (整数): {c}) return mpz(n), e, mpz(c) # 第二部分分层攻击函数 def attack_factor_db(n): 攻击层1查询FactorDB print(\n[1] 正在查询FactorDB...) url fhttp://factordb.com/api?query{n} try: resp requests.get(url, timeout15).json() if resp.get(status) FF: factors resp[factors] p, q int(factors[0][0]), int(factors[1][0]) print(f [] 成功p{p}, q{q}) return p, q else: print(f [-] 未完全分解。状态: {resp.get(status)}) except Exception as e: print(f [-] 查询失败: {e}) return None, None def attack_fermat(n, max_iter5000000): 攻击层2费马分解 print(f\n[2] 尝试费马分解 (最大迭代 {max_iter})...) a isqrt(n) 1 b2 a * a - n for _ in range(max_iter): b isqrt(b2) if b * b b2: p, q a - b, a b print(f [] 成功p{p}, q{q}) return int(p), int(q) a 1 b2 a * a - n print( [-] 费马分解失败。) return None, None def attack_pollard_pm1(n, B200000, trials5): 攻击层3Pollard‘s p-1分解 print(f\n[3] 尝试Pollard‘s p-1分解 (B{B})...) for _ in range(trials): a mpz(random.randint(2, n-2)) g mpz(2) for i in range(2, B1): a pow(a, i, n) d gcd(a - 1, n) if 1 d n: p, q int(d), int(n // d) print(f [] 成功p{p}, q{q}) return p, q elif d n: break print( [-] Pollard‘s p-1分解失败。) return None, None def attack_trial_division(n, limit2000000): 攻击层4√N附近试除法 print(f\n[4] 尝试√N附近 ±{limit} 试除法...) root int(isqrt(n)) for offset in range(1, limit1): for sign in [1, -1]: a root sign * offset if a 1: continue if n % a 0: p, q int(a), int(n // a) print(f [] 成功在偏移量 {sign*offset} 处找到因子。p{p}, q{q}) return p, q print( [-] 试除法失败。) return None, None # 第三部分密钥计算与解密 def compute_private_exponent(p, q, e): 计算私钥指数d phi (p - 1) * (q - 1) # 使用gmpy2的invert函数高效计算模逆 d gmpy2.invert(e, phi) return int(d) def decrypt_message(c, d, n): 解密消息 m_int pow(c, d, n) # 尝试转换为字节 m_bytes long_to_bytes(m_int) try: return m_bytes.decode(utf-8) except UnicodeDecodeError: # 如果不是UTF-8文本返回十六进制表示 return f非文本数据Hex: {m_bytes.hex()} # 主函数 def main(): n, e, c load_public_key_and_cipher() # 分层攻击 p, q attack_factor_db(n) if not p: p, q attack_fermat(n, max_iter3000000) if not p: p, q attack_pollard_pm1(n, B500000) if not p: p, q attack_trial_division(n, limit3000000) if not p or not q: print(\n[-] 所有快速攻击方法均失败。) print( 可能需要使用更高级的通用数域筛法如yafu, CADO-NFS) print( 但这超出了本演示脚本的范围且计算资源要求极高。) return # 验证因子 if p * q ! n: print(\n[-] 错误找到的因子乘积不等于N) return print(f\n[*] 因子验证成功: {p} * {q} {n}) # 计算私钥并解密 print(\n[*] 计算私钥指数 d...) d compute_private_exponent(p, q, e) print(f[*] 私钥指数 d: {d}) print(\n[*] 解密密文...) plaintext decrypt_message(c, d, n) print(f\n[] 解密后的明文内容) print(- * 40) print(plaintext) print(- * 40) if __name__ __main__: main()这个脚本提供了一个自动化的攻击流程框架。在实际使用中你可能需要根据具体情况调整各个攻击函数的参数如迭代次数、B值、试除范围。对于真正强壮且无缺陷的1024比特RSA密钥这个脚本最终会失败并提示你需要更强大的因式分解工具。6. 拓展思考与更高级的工具如果上述所有快速攻击都失败了那说明目标密钥很可能是“健康”的。这时破解就变成了一个纯粹的计算数学问题大整数分解。这通常需要动用更专业的工具和更多的计算资源。YAFU (Yet Another Factoring Utility)一个自动化程度很高的整数分解工具它内部集成了多种算法包括ECM、QS、NFS等会自动选择最适合当前数字的算法。对于1024比特的RSA如果密钥没有弱点YAFU可能会尝试使用数域筛法NFS这需要大量的内存和计算时间个人电脑可能难以承受。CADO-NFS当前最流行的开源通用数域筛法实现是分解大整数的“重型火炮”。它支持分布式计算可以在计算机集群上运行。分解一个1024比特的RSA密钥即使使用CADO-NFS也需要庞大的计算资源。Msieve另一个高效的因式分解库通常与GMP-ECM等工具配合使用。使用这些工具通常涉及复杂的配置和漫长的运行时间数天、数周甚至更久。它们超出了本次“实战案例”的范畴因为我们的案例恰恰利用了密钥生成的缺陷避免了这场“硬仗”。这个案例深刻地揭示了一个道理在密码学中实现与算法同等重要。一个理论上安全的算法可能因为一个糟糕的实现比如生成过于接近的素数而变得不堪一击。作为开发者理解这些潜在陷阱并坚持使用标准、经过严格审计的密码学库是构建安全系统的第一道防线。而对于安全研究者来说在发起“正面强攻”之前系统地排查这些“侧门”和弱点往往是最高效的突破口。