Python实战RSA加密漏洞分析与攻击复现1. RSA加密原理与常见漏洞场景RSA作为最广泛使用的公钥加密算法其安全性基于大整数分解的困难性。但在实际应用中参数选择不当会导致严重安全隐患。让我们先理解RSA的核心数学原理密钥生成过程选择两个大素数p和q计算模数N p × q计算欧拉函数φ(N) (p-1)(q-1)选择加密指数e满足1 e φ(N)且gcd(e, φ(N)) 1计算解密指数d ≡ e⁻¹ mod φ(N)常见漏洞场景模数N过小易被暴力分解p与q接近易受费马分解法攻击p-1或q-1光滑Pollards p-1方法可分解低加密指数当e过小且明文较小时可能直接开方共模攻击多个用户使用相同N不同e提示实际CTF比赛中约60%的RSA题目涉及参数选择不当导致的分解漏洞2. 环境配置与工具准备2.1 安装必要库pip install pycryptodome gmpy2 sympy2.2 核心工具函数from Crypto.Util.number import * import gmpy2 import math def bytes_to_long(s): return int.from_bytes(s, big) def long_to_bytes(n): return n.to_bytes((n.bit_length()7)//8, big)3. 费马分解法实战当p和q接近时存在整数x、y使得 N x² - y² (xy)(x-y)攻击实现def fermat_factorization(n): a gmpy2.isqrt(n) 1 b2 a*a - n while not gmpy2.is_square(b2): a 1 b2 a*a - n b gmpy2.isqrt(b2) return (ab, a-b) # 示例分解高校密码挑战赛题目中的N n 0xA5F51EB02EA9C0CC9B96926A08A761FE3E7CDB6E5B348DBEAEC761DBCFCDB15A6C76F8EE08196008AE60E396D7E228C6DAFC3CC1127F16EC87576B89C151F20F99098621FD46872BC92CDA8C915B758E5C0CACB994F55B8705B938126E08589E2502A7B9019C9A62E82392E8449E00CFC7DA17B8CDE92F9516CE9A2009F42DD9 p, q fermat_factorization(n) print(f分解结果: p{hex(p)}\nq{hex(q)})输出示例分解结果: p0xc60c5f1b997ed8a5e340023f33d2e269cfb423a3cf66b46d3f686747403a92b1265cb12b9a4e0135b890254f31a2c3f96a0427b39a36defdeeb85c57a80a9641 q0xd684da331ab6157da338b6d7b08ab4c1b72c29bb7f9ef445466056dfdbf29809c4d4a2435986a40de688afe7cc5a5c519f7c63cb486e44d523b0e1ef21c221994. Pollards p-1分解法当p-1的质因数较小时该算法可高效分解Ndef pollard_p_1(n, B10**6): a 2 for p in sieve_base(B): # 预计算小于B的素数 a pow(a, p**int(math.log(B,p)), n) d math.gcd(a-1, n) if 1 d n: return d return None # 优化版实现 def pollard_optimized(n): a 2 for j in range(2, 100000): a pow(a, j, n) d math.gcd(a-1, n) if d 1: return d return None # 攻击示例 n 0xBA645145D9DE58B0FFA6FC4624A2815092D2A2DC405E7A2515F985727D3C52F479A4D04694568CA9B08391BE79BD122808CF6034AB7251088687BFF5916A4F4723FE1372DCF9B069CAB269A9F8F47CB50078D3279B9452C9B3B65A07B49C793783EDB8EB8D8F1A220D9EFED33147483103A2551A96932738255493F13B511953 p pollard_optimized(n) print(f分解结果: p{hex(p)})5. 完整攻击流程与明文恢复结合上述方法实现从密文到明文的完整攻击def rsa_attack(c, e, n): # 尝试费马分解 try: p, q fermat_factorization(n) except: # 费马失败则尝试Pollard p pollard_optimized(n) q n // p # 计算私钥 phi (p-1)*(q-1) d gmpy2.invert(e, phi) # 解密 m pow(c, d, n) return long_to_bytes(m) # 实战解密 e 0x10001 c 0x9726C82FED1E6CD58DE825528AE5634653C9921CAE02AFF7325F20D6E7085B7C8E3DC78D7518A78A8BC7D07E2E837083324579510851827794AE3D1FB9BAB360B1413A8F171A83804CEA73DFBC1248139BB27EB7D5BAD724AD8B08F51888B90562AF950725ACDD698F817AE62746CEA09479A191A6552B0116830355C68D0F61 n 0xA5F51EB02EA9C0CC9B96926A08A761FE3E7CDB6E5B348DBEAEC761DBCFCDB15A6C76F8EE08196008AE60E396D7E228C6DAFC3CC1127F16EC87576B89C151F20F99098621FD46872BC92CDA8C915B758E5C0CACB994F55B8705B938126E08589E2502A7B9019C9A62E82392E8449E00CFC7DA17B8CDE92F9516CE9A2009F42DD9 plaintext rsa_attack(c, e, n) print(f解密结果: {plaintext})6. 防御措施与最佳实践安全参数选择指南参数安全建议不安全实践模数N≥2048比特1024比特素数p,q随机生成差值大接近或规律生成p-1/q-1有大素因子光滑数加密指数e65537(0x10001)3或过小填充方案OAEP无填充或PKCS#1 v1.5安全实现示例from Crypto.Cipher import PKCS1_OAEP from Crypto.PublicKey import RSA # 安全密钥生成 key RSA.generate(2048) # 标准加密 cipher PKCS1_OAEP.new(key.publickey()) ciphertext cipher.encrypt(bSecure Message) # 标准解密 cipher PKCS1_OAEP.new(key) plaintext cipher.decrypt(ciphertext)7. CTF实战技巧与自动化工具常见解题思路检查N是否可分解factordb.com尝试已知攻击方法低指数、共模等分析加密流程的特殊实现实用工具链# RsaCtfTool - 多功能RSA攻击工具 python RsaCtfTool.py --publickey key.pub --uncipherfile cipher.txt # SageMath - 高级数论计算 sage -q # 启动交互环境 N 123456...; factor(N) # 尝试分解进阶攻击示例Wiener攻击 当d (1/3)N^(1/4)时可通过连分数展开恢复私钥def wiener_attack(e, n): # 连分数展开 def cf_expansion(e, n): q [] while n: q.append(e // n) e, n n, e % n return q # 收敛项计算 def convergents(q): c [] for i in range(len(q)): a, b 1, 0 for j in range(i, -1, -1): a, b q[j]*a b, a c.append((a, b)) return c q cf_expansion(e, n) conv convergents(q) for k, d in conv: if k 0: continue phi (e*d - 1) // k # 解二次方程求p,q a 1 b -(n - phi 1) c n disc b*b - 4*a*c if disc 0: t gmpy2.isqrt(disc) if t*t disc: p (-b t) // (2*a) q (-b - t) // (2*a) if p*q n: return d return None通过本教程我们系统性地剖析了RSA算法的安全边界复现了典型攻击场景并提供了防御方案。在CTF比赛中这些技术能帮助快速识别和利用漏洞而在实际开发中理解这些原理则能避免安全误用。
手把手教你用Python破解RSA加密案例（附实战代码）
发布时间：2026/5/21 2:37:08
Python实战RSA加密漏洞分析与攻击复现1. RSA加密原理与常见漏洞场景RSA作为最广泛使用的公钥加密算法其安全性基于大整数分解的困难性。但在实际应用中参数选择不当会导致严重安全隐患。让我们先理解RSA的核心数学原理密钥生成过程选择两个大素数p和q计算模数N p × q计算欧拉函数φ(N) (p-1)(q-1)选择加密指数e满足1 e φ(N)且gcd(e, φ(N)) 1计算解密指数d ≡ e⁻¹ mod φ(N)常见漏洞场景模数N过小易被暴力分解p与q接近易受费马分解法攻击p-1或q-1光滑Pollards p-1方法可分解低加密指数当e过小且明文较小时可能直接开方共模攻击多个用户使用相同N不同e提示实际CTF比赛中约60%的RSA题目涉及参数选择不当导致的分解漏洞2. 环境配置与工具准备2.1 安装必要库pip install pycryptodome gmpy2 sympy2.2 核心工具函数from Crypto.Util.number import * import gmpy2 import math def bytes_to_long(s): return int.from_bytes(s, big) def long_to_bytes(n): return n.to_bytes((n.bit_length()7)//8, big)3. 费马分解法实战当p和q接近时存在整数x、y使得 N x² - y² (xy)(x-y)攻击实现def fermat_factorization(n): a gmpy2.isqrt(n) 1 b2 a*a - n while not gmpy2.is_square(b2): a 1 b2 a*a - n b gmpy2.isqrt(b2) return (ab, a-b) # 示例分解高校密码挑战赛题目中的N n 0xA5F51EB02EA9C0CC9B96926A08A761FE3E7CDB6E5B348DBEAEC761DBCFCDB15A6C76F8EE08196008AE60E396D7E228C6DAFC3CC1127F16EC87576B89C151F20F99098621FD46872BC92CDA8C915B758E5C0CACB994F55B8705B938126E08589E2502A7B9019C9A62E82392E8449E00CFC7DA17B8CDE92F9516CE9A2009F42DD9 p, q fermat_factorization(n) print(f分解结果: p{hex(p)}\nq{hex(q)})输出示例分解结果: p0xc60c5f1b997ed8a5e340023f33d2e269cfb423a3cf66b46d3f686747403a92b1265cb12b9a4e0135b890254f31a2c3f96a0427b39a36defdeeb85c57a80a9641 q0xd684da331ab6157da338b6d7b08ab4c1b72c29bb7f9ef445466056dfdbf29809c4d4a2435986a40de688afe7cc5a5c519f7c63cb486e44d523b0e1ef21c221994. Pollards p-1分解法当p-1的质因数较小时该算法可高效分解Ndef pollard_p_1(n, B10**6): a 2 for p in sieve_base(B): # 预计算小于B的素数 a pow(a, p**int(math.log(B,p)), n) d math.gcd(a-1, n) if 1 d n: return d return None # 优化版实现 def pollard_optimized(n): a 2 for j in range(2, 100000): a pow(a, j, n) d math.gcd(a-1, n) if d 1: return d return None # 攻击示例 n 0xBA645145D9DE58B0FFA6FC4624A2815092D2A2DC405E7A2515F985727D3C52F479A4D04694568CA9B08391BE79BD122808CF6034AB7251088687BFF5916A4F4723FE1372DCF9B069CAB269A9F8F47CB50078D3279B9452C9B3B65A07B49C793783EDB8EB8D8F1A220D9EFED33147483103A2551A96932738255493F13B511953 p pollard_optimized(n) print(f分解结果: p{hex(p)})5. 完整攻击流程与明文恢复结合上述方法实现从密文到明文的完整攻击def rsa_attack(c, e, n): # 尝试费马分解 try: p, q fermat_factorization(n) except: # 费马失败则尝试Pollard p pollard_optimized(n) q n // p # 计算私钥 phi (p-1)*(q-1) d gmpy2.invert(e, phi) # 解密 m pow(c, d, n) return long_to_bytes(m) # 实战解密 e 0x10001 c 0x9726C82FED1E6CD58DE825528AE5634653C9921CAE02AFF7325F20D6E7085B7C8E3DC78D7518A78A8BC7D07E2E837083324579510851827794AE3D1FB9BAB360B1413A8F171A83804CEA73DFBC1248139BB27EB7D5BAD724AD8B08F51888B90562AF950725ACDD698F817AE62746CEA09479A191A6552B0116830355C68D0F61 n 0xA5F51EB02EA9C0CC9B96926A08A761FE3E7CDB6E5B348DBEAEC761DBCFCDB15A6C76F8EE08196008AE60E396D7E228C6DAFC3CC1127F16EC87576B89C151F20F99098621FD46872BC92CDA8C915B758E5C0CACB994F55B8705B938126E08589E2502A7B9019C9A62E82392E8449E00CFC7DA17B8CDE92F9516CE9A2009F42DD9 plaintext rsa_attack(c, e, n) print(f解密结果: {plaintext})6. 防御措施与最佳实践安全参数选择指南参数安全建议不安全实践模数N≥2048比特1024比特素数p,q随机生成差值大接近或规律生成p-1/q-1有大素因子光滑数加密指数e65537(0x10001)3或过小填充方案OAEP无填充或PKCS#1 v1.5安全实现示例from Crypto.Cipher import PKCS1_OAEP from Crypto.PublicKey import RSA # 安全密钥生成 key RSA.generate(2048) # 标准加密 cipher PKCS1_OAEP.new(key.publickey()) ciphertext cipher.encrypt(bSecure Message) # 标准解密 cipher PKCS1_OAEP.new(key) plaintext cipher.decrypt(ciphertext)7. CTF实战技巧与自动化工具常见解题思路检查N是否可分解factordb.com尝试已知攻击方法低指数、共模等分析加密流程的特殊实现实用工具链# RsaCtfTool - 多功能RSA攻击工具 python RsaCtfTool.py --publickey key.pub --uncipherfile cipher.txt # SageMath - 高级数论计算 sage -q # 启动交互环境 N 123456...; factor(N) # 尝试分解进阶攻击示例Wiener攻击 当d (1/3)N^(1/4)时可通过连分数展开恢复私钥def wiener_attack(e, n): # 连分数展开 def cf_expansion(e, n): q [] while n: q.append(e // n) e, n n, e % n return q # 收敛项计算 def convergents(q): c [] for i in range(len(q)): a, b 1, 0 for j in range(i, -1, -1): a, b q[j]*a b, a c.append((a, b)) return c q cf_expansion(e, n) conv convergents(q) for k, d in conv: if k 0: continue phi (e*d - 1) // k # 解二次方程求p,q a 1 b -(n - phi 1) c n disc b*b - 4*a*c if disc 0: t gmpy2.isqrt(disc) if t*t disc: p (-b t) // (2*a) q (-b - t) // (2*a) if p*q n: return d return None通过本教程我们系统性地剖析了RSA算法的安全边界复现了典型攻击场景并提供了防御方案。在CTF比赛中这些技术能帮助快速识别和利用漏洞而在实际开发中理解这些原理则能避免安全误用。
