1. 项目概述从“破解”到“理解”RSA看到“破解RSA”这个标题很多人的第一反应可能是觉得这很酷或者认为这触及了某种技术禁区。但作为一名在信息安全领域摸爬滚打多年的从业者我必须先澄清一个核心观点我们这里探讨的“破解”绝非指在现实世界中攻击一个正确实现、参数足够大的RSA加密系统。那在现有计算能力下几乎是不可能的。我们真正的目标是通过Python亲手实践去深刻理解RSA加密算法的数学原理、实现细节以及当实现“不完美”时可能暴露出的致命弱点。这就像学习开锁不是为了当小偷而是为了成为一名更出色的锁匠或安全评估员。通过动手“拆解”一个加密算法你能获得的认知深度是单纯阅读理论文档无法比拟的。你会明白为什么教科书上总强调“选择大素数”、“随机性至关重要”、“不要自己实现加密”。本次实战我们将从零开始用Python实现一个简易的RSA加密解密过程然后针对几种常见的、因参数选择不当或信息泄漏导致的脆弱场景编写“攻击”脚本。整个过程你将用到random,math和sympy用于更便捷的素数处理等库代码总行数不多但行行都指向RSA的核心。2. RSA算法原理快速回顾与Python建模在动手写代码之前我们必须把RSA的数学骨架搭清楚。RSA的安全性建立在“大数分解难题”之上即将两个大质数相乘很容易但想将它们的乘积分解回原来的两个质数却极其困难。2.1 密钥生成一切的起点RSA密钥对的生成围绕三个核心步骤展开我们将用数学公式和即将编写的Python代码来对应理解。第一步选择两个大素数p和q。这是整个体系安全性的基石。p和q必须足够大、随机且独立。在教学中为了演示我们可能选择较小的数但心中要时刻牢记实战中它们通常是1024位约308位十进制数或更大的整数。import sympy def generate_large_prime(bit_length512): 生成一个指定位长度的大素数教学演示用生产环境应使用加密安全随机数生成器。 return sympy.randprime(2**(bit_length-1), 2**bit_length) # 示例生成两个16位的素数仅用于演示实际太小 p generate_large_prime(16) # 例如 54449 q generate_large_prime(16) # 例如 61927 print(fp {p}, q {q})第二步计算模数n和欧拉函数φ(n)。模数n p * q这是公钥和私钥都会用到的一部分是公开的。欧拉函数φ(n) (p-1) * (q-1)这个值必须绝对保密它直接关系到私钥的生成。n p * q phi_n (p - 1) * (q - 1) print(fn p*q {n}) print(fφ(n) (p-1)*(q-1) {phi_n})第三步选择公钥指数e和计算私钥指数d。公钥指数e需要满足两个条件1 e φ(n)且e与φ(n)互质最大公约数为1。通常选择65537因为它二进制表示中1很少只有两个计算效率高且是一个够大的素数与大多数φ(n)互质。 私钥指数d是e关于模φ(n)的模逆元。即满足(d * e) % φ(n) 1。计算d需要使用扩展欧几里得算法。import math def extended_gcd(a, b): 扩展欧几里得算法返回 (gcd, x, y) 使得 a*x b*y gcd(a, b) if b 0: return a, 1, 0 gcd, x1, y1 extended_gcd(b, a % b) x y1 y x1 - (a // b) * y1 return gcd, x, y def modinv(e, phi): 计算 e 模 phi 的乘法逆元 d即 (d*e) % phi 1 gcd, x, _ extended_gcd(e, phi) if gcd ! 1: raise ValueError(fe ({e}) 和 φ(n) ({phi}) 不互质无法求逆元) return x % phi e 65537 # 常见的公钥指数 # 确保 e 与 φ(n) 互质 if math.gcd(e, phi_n) ! 1: # 如果65537不互质极小概率事件则顺序取下一个素数 e sympy.nextprime(e) while math.gcd(e, phi_n) ! 1: e sympy.nextprime(e) d modinv(e, phi_n) print(f公钥 (e, n) ({e}, {n})) print(f私钥 (d, n) ({d}, {n}))至此我们得到了完整的RSA密钥对公钥(e, n)用于加密私钥(d, n)用于解密。2.2 加密与解密过程加密过程很简单对于明文消息m需要是小于n的整数计算密文c m^e mod n。 解密则是逆过程对于密文c计算明文m c^d mod n。这里的关键是“模幂运算”。直接计算m^e可能会得到一个天文数字e是65537在Python中直接计算效率低下且可能内存溢出。因此必须使用快速模幂算法如平方乘算法。def fast_pow_mod(base, exponent, modulus): 快速模幂运算计算 (base^exponent) % modulus 的高效算法。 result 1 base base % modulus while exponent 0: # 如果当前指数位为1则将当前的base乘入结果 if exponent 1: result (result * base) % modulus # 将base平方为下一次循环做准备 base (base * base) % modulus # 指数右移一位 exponent 1 return result def rsa_encrypt(m, e, n): RSA加密将整数明文m加密为整数密文c。 if m n: raise ValueError(明文 m 必须小于模数 n) return fast_pow_mod(m, e, n) def rsa_decrypt(c, d, n): RSA解密将整数密文c解密为整数明文m。 return fast_pow_mod(c, d, n) # 示例加密解密一个数字 m_original 123456 # 假设的明文数字 ciphertext rsa_encrypt(m_original, e, n) plaintext rsa_decrypt(ciphertext, d, n) print(f原始明文: {m_original}) print(f加密后密文: {ciphertext}) print(f解密后明文: {plaintext}, 验证 {成功 if m_original plaintext else 失败})注意上述流程加密的是整数。对于文本消息需要先通过编码如PKCS#1 OAEP等填充方案将其转换为整数。但为了聚焦核心原理我们的演示暂不涉及复杂的填充方案这会引入额外的安全性和复杂性。自己实现填充极易出错生产环境务必使用成熟库如cryptography。3. 实战“破解”针对不完美实现的攻击现在我们进入了标题中最吸引人的部分——“破解”。请再次明确以下所有攻击场景都基于一个前提RSA的实现或使用方式存在缺陷。我们的代码将扮演“攻击者”的角色利用这些缺陷来恢复明文或私钥。3.1 场景一模数n过小导致因式分解攻击这是最直接的理论攻击。如果公钥中的模数n太小现代计算机可以在可接受的时间内将其分解为p和q。一旦得到p和q我们就能计算出φ(n)和私钥d。import math import sympy def factorize_n(n, bit_length_limit64): 尝试分解模数n。对于教学演示的小n有效对大n无效。 if n.bit_length() bit_length_limit: print(f警告n的位长度为{n.bit_length()}超过{bit_length_limit}位因式分解将非常困难或不可能。) return None, None # 方法1使用sympy的factorint函数对小整数有效 factors sympy.factorint(n) if len(factors) 2 and all(exp 1 for exp in factors.values()): p, q list(factors.keys()) return p, q else: print(f分解失败或n不是两个素数的乘积。因数分解结果{factors}) return None, None def attack_via_small_n(e, n, ciphertext): 攻击场景已知公钥(e, n)和密文c且n较小可分解。 print(f\n 攻击场景1小模数n分解攻击 ) print(f已知e{e}, n{n}, 密文c{ciphertext}) p, q factorize_n(n, 64) if p and q: print(f[] 成功分解 n: p{p}, q{q}) phi_n_attacked (p-1)*(q-1) try: d_attacked modinv(e, phi_n_attacked) print(f[] 计算出 φ(n) {phi_n_attacked}) print(f[] 计算出私钥 d {d_attacked}) decrypted_msg rsa_decrypt(ciphertext, d_attacked, n) print(f[] 解密得到明文: {decrypted_msg}) return decrypted_msg except ValueError as ve: print(f[-] 计算私钥d失败: {ve}) else: print([-] 无法分解n攻击失败。) return None # 模拟一个脆弱的密钥对使用小素数 p_small 101 q_small 113 n_small p_small * q_small phi_n_small (p_small-1)*(q_small-1) e_small 65537 # 确保e与φ(n)互质 while math.gcd(e_small, phi_n_small) ! 1: e_small 2 d_small modinv(e_small, phi_n_small) # 模拟加密一个消息 m_secret 42 c_small rsa_encrypt(m_secret, e_small, n_small) # 发动攻击攻击者只知道 e_small, n_small, c_small recovered_m attack_via_small_n(e_small, n_small, c_small) print(f原始明文是 {m_secret}攻击恢复的明文是 {recovered_m}{攻击成功 if m_secret recovered_m else 攻击失败。})这个攻击演示了使用过短密钥如512位以下的风险。如今1024位RSA已被认为不够安全推荐使用2048位或更长。3.2 场景二共模攻击假设同一个消息m用相同的模数n但不同的公钥指数e1和e2进行加密得到两个密文c1和c2。即c1 m^e1 mod nc2 m^e2 mod n如果e1和e2互质通常如此攻击者无需知道私钥仅利用扩展欧几里得算法就能恢复明文m。def common_modulus_attack(c1, c2, e1, e2, n): 共模攻击在相同n下用两个互质的e加密同一消息m。 print(f\n 攻击场景2共模攻击 ) print(f已知n{n}, e1{e1}, c1{c1}, e2{e2}, c2{c2}) # 使用扩展欧几里得算法找到满足 r*e1 s*e2 1 的整数 r 和 s gcd, r, s extended_gcd(e1, e2) if gcd ! 1: print(f[-] e1({e1}) 和 e2({e2}) 不互质共模攻击不适用。) return None print(f[] 找到系数: r{r}, s{s}) # 注意r或s可能为负数。如果r为负则计算 c1^r mod n 需要先求 c1 的模逆元。 # 因为 m (c1^r * c2^s) mod n当r为负时c1^r mod n (c1^{-1})^{-r} mod n if r 0: # 计算 c1 模 n 的逆元 c1_inv modinv(c1, n) part1 fast_pow_mod(c1_inv, -r, n) else: part1 fast_pow_mod(c1, r, n) if s 0: c2_inv modinv(c2, n) part2 fast_pow_mod(c2_inv, -s, n) else: part2 fast_pow_mod(c2, s, n) # 恢复明文 m (part1 * part2) % n recovered_m (part1 * part2) % n print(f[] 计算 part1 {part1}, part2 {part2}) print(f[] 恢复的明文 m {recovered_m}) return recovered_m # 模拟场景 # 使用之前生成的小n_small和同一个消息m_secret e1 3 # 注意实际中应避免使用过小的e如3 e2 65537 # 确保e1, e2与φ(n)互质 (此处简化假设已满足) c1_cm rsa_encrypt(m_secret, e1, n_small) c2_cm rsa_encrypt(m_secret, e2, n_small) recovered_m_cm common_modulus_attack(c1_cm, c2_cm, e1, e2, n_small) print(f原始明文是 {m_secret}共模攻击恢复的明文是 {recovered_m_cm}{攻击成功 if m_secret recovered_m_cm else 攻击失败。})这个攻击告诉我们绝对不要使用相同的模数n为多个用户生成密钥对。每个密钥对应唯一的n。3.3 场景三低加密指数攻击如e3与广播攻击当公钥指数e非常小比如3并且加密的消息m满足m^e n时加密运算c m^e mod n实际上没有发生模运算因为m^e比n小那么c m^e。攻击者只需要对密文c开e次方根就能得到明文m。def low_exponent_attack(c, e, n): 低加密指数攻击当 e 很小且 m^e n 时。 print(f\n 攻击场景3低加密指数攻击 (e{e}) ) print(f已知密文 c{c}, e{e}) # 尝试对c开e次方根 # 使用整数近似检查结果是否恰好是整数的e次幂 m_candidate sympy.integer_nthroot(c, e) if m_candidate[1]: # 如果第二个返回值为True表示c是一个完美的e次幂 recovered_m m_candidate[0] print(f[] 发现 c 是 {recovered_m}^{e}直接恢复明文: {recovered_m}) return recovered_m else: print(f[-] c 不是某个整数的{e}次幂低加密指数攻击失败。可能因为 m^e n。) return None # 模拟一个脆弱的场景e3, m较小 e_low 3 # 为了满足 m^e n我们需要一个比 n 的立方根大的 n但 m 要小。这里我们构造一个场景。 # 选择 m 使得 m^3 是一个不太大的数 m_small 100 # 100^3 1,000,000 # 我们需要 n 1,000,000 p_temp sympy.randprime(200, 300) # 生成一个素数确保n足够大 q_temp sympy.randprime(200, 300) n_low p_temp * q_temp # n 大约在 40,000 到 90,000 之间大于 1,000,000不一定这里仅为演示逻辑。 # 为了确保演示成功我们手动确保 n m_small**3 n_low 2000000 # 手动设置一个大于 1,000,000 的 n c_low rsa_encrypt(m_small, e_low, n_low) # 因为 m_small**31,000,000 n_low所以加密就是 m_small**3 print(f构造场景m{m_small}, e{e_low}, n{n_low}, cm^e{c_low}) recovered_m_low low_exponent_attack(c_low, e_low, n_low)广播攻击是低加密指数攻击的扩展如果同一个消息m用相同的低指数e如3加密但发送给了三个不同的接收者使用三个不同的模数n1, n2, n3攻击者利用中国剩余定理就能恢复m。实现代码稍复杂但其核心思想是利用多个方程求解一个未知数。实操心得这些攻击代码虽然简短但它们清晰地揭示了RSA安全使用的“禁忌清单”不要用小模数、不要重用模数、不要用小公钥指数加密短消息。在真实开发中直接使用cryptography这类高级库它们默认就帮你避开了这些坑。4. 从“攻击”中领悟的安全编码实践写完攻击代码我们不是要去“搞破坏”而是为了在今后构建系统时能清晰地知道雷区在哪里。以下是我从这些实践中总结出的、比理论更深刻的几点体会第一密码学原语Primitives不要自己实现。我们上面的RSA实现是高度简化的教学模型。它缺少了至关重要的填充方案如OAEP。没有填充的RSA称为“教科书RSA”是确定性的并且对多种攻击如选择密文攻击毫无抵抗力。生产环境中务必使用经过严格审计的库如Python的cryptography库。它的RSA实现包含了正确的填充和密钥管理。# 使用 cryptography 库进行正确的RSA操作生产环境推荐 from cryptography.hazmat.primitives.asymmetric import rsa, padding from cryptography.hazmat.primitives import hashes from cryptography.hazmat.primitives.serialization import load_pem_public_key, load_pem_private_key import os # 生成密钥对 private_key rsa.generate_private_key(public_exponent65537, key_size2048) public_key private_key.public_key() # 加密使用OAEP填充 message bA secret message that needs padding. ciphertext public_key.encrypt( message, padding.OAEP( mgfpadding.MGF1(algorithmhashes.SHA256()), algorithmhashes.SHA256(), labelNone ) ) # 解密 decrypted_message private_key.decrypt( ciphertext, padding.OAEP( mgfpadding.MGF1(algorithmhashes.SHA256()), algorithmhashes.SHA256(), labelNone ) ) print(f解密成功: {decrypted_message.decode()})第二密钥管理是生命线。算法再安全私钥泄露一切都完蛋。私钥文件必须严格权限控制如600绝不能硬编码在代码或配置文件里。考虑使用硬件安全模块或云服务的密钥管理服务来存储私钥。第三理解“安全参数”的含义。通过分解小n的练习你会对“2048位密钥”有具象的认识——那是一个617位的十进制数以目前公开的算力分解它需要耗费天文数字的资源和时间。选择密钥长度不是拍脑袋而是基于对当前计算能力的评估和未来一段时间的预测。第四侧信道攻击是另一维度。我们的攻击集中在数学层面。现实中计时攻击、功耗分析、电磁泄漏等侧信道攻击可能更致命。这些攻击不破解算法本身而是通过测量计算机执行解密操作所花费的时间、消耗的功率等物理信息来推断出密钥。这要求安全实现不仅要逻辑正确还要在物理执行层面是“恒定时间”的。5. 常见问题与调试实录在编写和运行上述代码时你可能会遇到一些典型问题。这里记录一下我踩过的坑和解决方法。问题1sympy.randprime生成大素数很慢。现象当设置bit_length512或更大时生成素数可能需要几秒甚至更久。 原因生成大素数本身就是一个概率性测试过程需要时间。 解决对于教学演示可以将bit_length设置为32或64足够看清原理即可。生产环境密钥生成慢是正常的且通常只在初始化时做一次。问题2计算模逆元modinv时抛出“e和φ(n)不互质”的错误。现象ValueError: e (65537) and φ(n) (...) are not coprime原因这是一个极其罕见但理论上可能的事件即你随机生成的p和q使得φ(n) (p-1)*(q-1)与65537有公因子因为65537是费马素数p-1或q-1是65537的倍数概率极低。 解决在密钥生成代码中我们已经加入了检查机制。如果遇到就顺序取下一个素数作为e。在实际中也可以选择重新生成一对p和q。问题3加密解密数字没问题但加密文本时乱码或出错。现象将字符串转换成整数加密后再解密得到的字符串是乱码。 原因1没有使用标准的填充方案。教科书RSA要求加密的整数m必须小于n。直接将长字符串编码成的大整数可能超过n。 原因2编码字符串到整数和解码整数到字符串过程不一致或不完整。常见的做法是使用PKCS#1 OAEP填充它会处理消息分段和随机化。 解决永远不要自己处理文本到整数的转换和填充。使用像cryptography这样的库它提供的encrypt/decrypt方法直接接受和返回字节串内部帮你完成了所有符合安全标准的处理。问题4广播攻击或共模攻击的代码恢复出的明文是负数或很大。现象恢复的m是一个负数或一个明显不对的巨大数字。 原因在计算c1^r或c2^s时如果r或s是负数我们需要计算的是模逆元c1^{-1} mod n的-r次幂。如果c1与n不互质几乎不可能因为n是两个素数乘积c1是密文则模逆元不存在攻击失败。另外在中国剩余定理的实现中模数必须两两互质。 解决仔细检查处理负指数的代码逻辑。确保在计算模逆元前使用math.gcd(c1, n) 1进行验证理论上应成立。对于广播攻击确保所有模数n_i是两两互质的在RSA中由于都是大素数乘积它们互质的概率极高。最后我想强调的是密码学是一个深奥且严谨的领域。这趟“破解”之旅的目的是为你打开一扇理解的大门而不是给你一把万能钥匙。真正的安全源于对原理的敬畏、对最佳实践的遵循以及对成熟库的信任。希望这些代码和解释能让你下次看到“RSA”时不再觉得它是一个黑盒而是一个由精妙数学构建的、需要谨慎使用的强大工具。