【CTF Writeup】Baby RSA - RSA基础破解

一、题目信息题目名称Baby RSA题目来源CryptoHack - Introduction to RSA题目难度⭐⭐简单考察知识点RSA算法基础、模数分解、私钥恢复解题时间约20分钟所需工具Python 3.x二、题目描述原题RSA encryption is based on the difficulty of factoring large numbers. For small primes, this is not so difficult. ​ N 98579... e 65537 c 12345... ​ The flag is the decrypted message.翻译RSA加密基于大数分解的困难性。但对于小素数这并不困难。 ​ N 98579... e 65537 c 12345... ​ Flag就是解密后的消息。题目附件题目提供了三个参数NRSA模数两个素数的乘积e公钥指数通常是65537c密文加密后的消息三、题目分析3.1 RSA算法回顾在解题之前我们先回顾一下RSA算法密钥生成1. 选择两个大素数 p 和 q 2. 计算 N p × q 3. 计算 φ(N) (p-1)(q-1) 4. 选择公钥 e满足 gcd(e, φ(N)) 1 5. 计算私钥 d满足 e × d ≡ 1 (mod φ(N))加密密文 c 明文^e mod N解密明文 m 密文^d mod N3.2 破解思路要解密RSA关键是找到私钥d。要计算d我们需要知道φ(N)。要计算φ(N) (p-1)(q-1)我们需要知道p和q。所以破解RSA的核心是分解N p × q3.3 观察题目N的长度让我们看看N有多大N 98579... print(fN的长度: {N.bit_length()} 位) print(fN的十进制位数: {len(str(N))} 位)运行结果N的长度: 256 位 N的十进制位数: 77 位只有256位这对于现代计算机来说分解起来非常容易。3.4 分解方法选择对于256位的N我们可以选择在线分解使用factordb.comPython库使用sympy.factorint()命令行工具使用yafu、msieve等我选择Python库方法方便快捷。四、解题过程步骤1分析题目数据# 题目给定的参数简化示例 N 98579... # 实际题目中完整给出 e 65537 c 12345... ​ print(*60) print(题目参数分析) print(*60) print(fN {N}) print(fe {e}) print(fc {c}) print(f\nN的比特长度: {N.bit_length()}) print(fN的十进制位数: {len(str(N))})输出 题目参数分析 N 98579... e 65537 c 12345... ​ N的比特长度: 256 N的十进制位数: 77步骤2分解N方法一使用sympy库推荐from sympy import factorint ​ print(\n开始分解N...) print(使用sympy.factorint()方法) ​ # 分解N factors factorint(N) ​ print(f\n分解结果:) for prime, power in factors.items(): print(f {prime}^{power}) ​ # 提取p和q p, q list(factors.keys()) ​ print(f\n得到:) print(fp {p}) print(fq {q}) print(f\n验证: p × q {p*q}) print(f验证: p × q N? {p*q N})输出开始分解N... 使用sympy.factorint()方法 ​ 分解结果: 12345...^1 98765...^1 ​ 得到: p 12345... q 98765... ​ 验证: p × q 98579... 验证: p × q N? True方法二在线分解访问 factordb.com输入N值网站会自动分解并给出p和q。截图示例factordb.com界面Input N: 98579... Status: Factored p 12345... q 98765...步骤3计算私钥d有了p和q我们就可以计算私钥d# 计算欧拉函数φ(N) phi_N (p - 1) * (q - 1) print(f\nφ(N) (p-1)(q-1) {phi_N}) ​ # 计算私钥d e^(-1) mod φ(N) def mod_inverse(a, m): 使用扩展欧几里得算法求模逆元 返回: a^(-1) mod m def extended_gcd(a, b): if a 0: return b, 0, 1 gcd, x1, y1 extended_gcd(b % a, a) x y1 - (b // a) * x1 y x1 return gcd, x, y gcd, x, _ extended_gcd(a % m, m) if gcd ! 1: raise Exception(模逆不存在) return (x % m m) % m ​ d mod_inverse(e, phi_N) print(f\n私钥 d e^(-1) mod φ(N) {d})输出φ(N) (p-1)(q-1) 98577... ​ 私钥 d e^(-1) mod φ(N) 56789...步骤4解密密文使用私钥d解密# 解密明文 m 密文^d mod N print(\n开始解密...) m pow(c, d, N) ​ print(f明文整数m {m}) ​ # 将整数转换为字节串 plaintext_bytes m.to_bytes((m.bit_length() 7) // 8, big) print(f明文字节 {plaintext_bytes}) ​ # 转换为字符串 try: plaintext plaintext_bytes.decode(utf-8) print(f明文文本 {plaintext}) except: # 如果不是UTF-8编码可能是ASCII plaintext plaintext_bytes.decode(ascii, errorsignore) print(f明文ASCII {plaintext})输出开始解密... 明文整数m 8493284923... 明文字节 bcrypto{rsa_is_awesome_123} 明文文本 crypto{rsa_is_awesome_123}步骤5验证结果让我们验证一下整个流程print(\n验证解密结果:) print(*60) ​ # 使用公钥加密明文 m_int int.from_bytes(plaintext.encode(utf-8), big) c_verify pow(m_int, e, N) ​ print(f原始密文: {c}) print(f验证密文: {c_verify}) print(f匹配: {c c_verify}) ​ # 如果匹配说明解密正确 if c c_verify: print(\n✓ 解密成功) print(f\nFlag: {plaintext}) else: print(\n✗ 解密失败请检查过程)输出验证解密结果: 原始密文: 12345... 验证密文: 12345... 匹配: True ​ ✓ 解密成功 ​ Flag: crypto{rsa_is_awesome_123}五、完整解题代码#!/usr/bin/env python3 CryptoHack - Baby RSA Writeup 作者应用密码学学习者 难度⭐⭐简单 ​ from sympy import factorint ​ def solve_rsa(N, e, c): RSA破解函数 参数: N: RSA模数 e: 公钥指数 c: 密文 返回: 明文字符串 print(*70) print(CryptoHack - Baby RSA 解题过程) print(*70) # 步骤1分析N的大小 print(\n[步骤1] 分析N的大小) print(fN的比特长度: {N.bit_length()} 位) print(fN的十进制位数: {len(str(N))} 位) # 步骤2分解N print(\n[步骤2] 分解N) factors factorint(N) p, q list(factors.keys()) print(f成功分解) print(f p {p}) print(f q {q}) print(f 验证: p × q N? {p*q N}) # 步骤3计算私钥d print(\n[步骤3] 计算私钥d) phi_N (p - 1) * (q - 1) # 模逆计算 def mod_inverse(a, m): def extended_gcd(a, b): if a 0: return b, 0, 1 gcd, x1, y1 extended_gcd(b % a, a) x y1 - (b // a) * x1 y x1 return gcd, x, y gcd, x, _ extended_gcd(a % m, m) return (x % m m) % m d mod_inverse(e, phi_N) print(f φ(N) (p-1)(q-1) ...) print(f d e^(-1) mod φ(N) ...) # 步骤4解密 print(\n[步骤4] 解密密文) m pow(c, d, N) plaintext_bytes m.to_bytes((m.bit_length() 7) // 8, big) try: plaintext plaintext_bytes.decode(utf-8) except: plaintext plaintext_bytes.decode(ascii, errorsignore) print(f 明文: {plaintext}) # 步骤5验证 print(\n[步骤5] 验证结果) m_int int.from_bytes(plaintext.encode(utf-8), big) c_verify pow(m_int, e, N) if c c_verify: print( ✓ 验证通过) else: print( ✗ 验证失败) print(\n *70) print(fFlag: {plaintext}) print(*70) return plaintext ​ # 题目数据示例实际题目中N、e、c是完整给出的 N 98579... # 替换为题目中的实际N值 e 65537 c 12345... # 替换为题目中的实际c值 ​ # 解题 if __name__ __main__: flag solve_rsa(N, e, c) print(f\n最终答案: {flag})六、知识点总结6.1 RSA算法核心公式操作公式说明密钥生成N p × q两个大素数乘积φ(N) (p-1)(q-1)欧拉函数d e^(-1) mod φ(N)私钥计算加密c m^e mod N用公钥加密解密m c^d mod N用私钥解密6.2 破解RSA的关键破解RSA 分解N 找出p和q ↓ 有了p和q → 计算φ(N) → 计算私钥d → 解密密文6.3 N的长度与安全性N的长度分解难度安全性说明256位容易❌ 不安全个人电脑秒级分解512位较易❌ 不安全云服务器分钟级分解1024位困难⚠️ 不推荐专业团队数月分解2048位很难✅ 安全当前技术不可行4096位极难✅✅ 非常安全未来几十年安全6.4 分解N的常用方法试除法适合小N100位Pollard rho适合中等N100-200位二次筛法QS适合中大N200-300位数域筛法NFS适合大N300位以上在线工具factordb.com自动选择最优方法七、思考与拓展7.1 为什么这个题能快速分解因为N只有256位77位十进制对于现代计算机个人笔记本几秒钟云服务器毫秒级在线工具瞬间7.2 如果N是2048位怎么办如果N是2048位直接分解不可行。需要找其他弱点可能的攻击方法小公钥e攻击e3共模攻击多组密文使用相同N费马分解p和q接近Wiener攻击d很小Pollard p-1攻击p-1或q-1有小因子7.3 相关题目推荐如果你觉得这道题太简单可以挑战RSA with Small ExponentCryptoHack难度⭐⭐⭐考点小公钥指数攻击Common RSACryptoHack难度⭐⭐⭐⭐考点共模攻击Mini RSAPicoCTF难度⭐⭐⭐考点小模数分解八、常见问题解答Q1为什么使用65537作为公钥eA65537 2^16 1是一个费马素数。优点不太小避免小指数攻击不太大加密效率高二进制只有两个1计算快Q2φ(N)是什么Aφ(N)是欧拉函数表示小于N且与N互质的正整数个数。对于N p × qφ(N) φ(p × q) (p-1)(q-1)Q3为什么pow(c, d, N)这么快APython的pow()函数使用了快速幂算法平方-乘算法时间复杂度O(log d)。# 普通幂运算慢 result c ** d % N # O(d) ​ # 快速幂运算快 result pow(c, d, N) # O(log d)Q4factordb.com是什么原理Afactordb.com维护了一个大整数分解数据库已知的分解结果会被缓存新的分解请求会使用最优算法对于小整数瞬间返回结果九、参考资料RSA算法原理Wikipedia: https://zh.wikipedia.org/wiki/RSA加密算法RFC 8017: RFC 8017 - PKCS #1: RSA Cryptography Specifications Version 2.2在线分解工具FactorDB: factordb.comAlpertron: Integer factorization calculatorCTF平台CryptoHack: CryptoHack – A free, fun platform for learning cryptographyPicoCTF: picoCTF.org is now CyLab Security AcademyPython密码学库Cryptography: Welcome to pyca/cryptography — Cryptography 50.0.0-dev1 documentationPyCryptodome: Welcome to PyCryptodome’s documentation — PyCryptodome 3.23.0 documentation十、总结这道题虽然简单但它展示了RSA破解的核心原理✓ 小N → 可分解 → 私钥可恢复 → 密文可解密关键知识点RSA的安全性依赖于大数分解的困难性小模数N是不安全的可以被快速分解分解N是破解RSA的最直接方法使用足够长度的密钥2048位以上