1. 项目概述从“BabyRSA”说起如果你玩过CTFCapture The Flag网络安全竞赛或者对密码学有点兴趣那你大概率见过“BabyRSA”这个词。它不是一个具体的工具或标准而更像是一个圈子里的“黑话”特指那些使用了RSA加密算法但参数尤其是质数p和q选得特别小、特别“弱”的题目或场景。这类题目通常出现在CTF的入门级密码学挑战中目的是让新手在相对简单的环境下理解RSA的核心原理和常见的攻击手法比如因式分解、共模攻击、低加密指数攻击等。所以当你看到“BabyRSA”这个标题它背后指向的其实是一个充满实践乐趣的密码学学习领域如何利用“脆弱”的RSA实现来逆向还原出明文信息。我自己在带新人入门CTF密码学方向时发现很多朋友一上来就被RSA那一堆数学公式欧拉函数、模逆元吓退了。但“BabyRSA”恰恰是打破这个恐惧的最佳切入点。它剥离了工业级RSA那种天文数字般的大素数带来的计算复杂性让你可以专注于算法流程和攻击逻辑本身。通过动手解决一个个“Baby”级别的题目你能清晰地看到一个理论上坚不可摧的密码系统如果在使用上“偷工减料”会暴露出多少致命的破绽。这不仅是解题更是一种深刻的安全思维训练——让你明白安全是一个系统工程任何一个环节的疏忽都可能导致全线崩溃。接下来我会围绕“BabyRSA”这个核心拆解它涉及的密码学原理、常见的脆弱场景、实用的攻击工具脚本比如如何用Python快速实现解密以及你在实际操作中一定会遇到的坑和技巧。无论你是想入门CTF还是单纯对“如何破解简单密码”感到好奇这篇文章都能给你一套可以直接上手操作的“地图”。2. RSA算法原理快速回顾与“Baby”的由来要理解为什么“BabyRSA”能被破解首先得知道标准的RSA应该是什么样子的。别担心我们不用深究所有数学证明只抓和破解相关的核心流程。2.1 RSA加密解密的核心步骤RSA是一种非对称加密算法也就是说加密和解密用的是不同的钥匙。这里涉及几个关键角色p和q两个非常大的、随机的质数。这是整个系统安全的基石。n模数。n p * q。这个n是公开的。φ(n)欧拉函数。对于两个质数p和qφ(n) (p-1)*(q-1)。这个值必须严格保密。e加密指数。一个与φ(n)互质的数通常是65537。这个e是公开的。d解密指数。e关于φ(n)的模逆元即满足(e * d) mod φ(n) 1。这个d是私钥的核心必须绝对保密。加密过程对于明文m需要先转换成数字计算密文c m^e mod n。解密过程用私钥d计算明文m c^d mod n。整个系统的安全性建立在“大数分解难题”上从公开的n反向推导出p和q是计算上不可行的。只要p和q足够大比如2048位以上以目前人类的计算能力想分解n需要的时间可能是宇宙的年龄那么长。2.2 “Baby”在哪里脆弱性根源分析所谓“BabyRSA”就是人为地削弱了上述某个或某几个环节使其从“计算不可行”变成了“计算可行”。常见的“放水”点有质数太小n太小这是最经典的“Baby”特征。比如p和q只有几十位甚至十几位十进制数。这样n也很小现代计算机可以在毫秒级内完成因式分解。一旦分解出p和q就能立刻算出φ(n)和私钥d整个加密体系瞬间崩塌。加密指数e太小如果e非常小比如3而明文m也不大可能导致m^e n。这时加密操作c m^e mod n就等于m^e本身因为没超过模数n取模无效果。攻击者直接对密文c开e次方根就能得到明文m完全绕过了分解n。解密指数d太小如果私钥d选得太小可能存在一种叫做“维纳攻击”的方法通过连分数逼近直接从公开的e和n中恢复出d。共模攻击如果同样的明文m用相同的n但不同的e加密了两次得到两个密文c1和c2。那么在不分解n的情况下也有可能恢复出明文。模数n重用或存在公因子如果多个RSA密钥对使用了相同的n或者不同的n之间存在公因子那么安全性会急剧下降。在CTF的“BabyRSA”题目里出题人往往会故意设置这些脆弱条件目的就是考察你对这些特定攻击场景的识别和利用能力。它就像一把故意没锁好的锁让你练习开锁技巧而不是去暴力砸墙。3. 实战工具链手把手打造你的BabyRSA解密脚本光说不练假把式。接下来我们用一个Python脚本将上述攻击思路具体化。这个脚本的目标是给定一组“脆弱”的RSA参数可能是从CTF题目中提取的自动判断可能的攻击路径并完成解密。我会分模块讲解你可以把它们组合成一个完整的工具。3.1 环境准备与核心库首先你需要一个Python3环境。核心库是sympy和gmpy2。sympy用于符号计算和质数相关操作gmpy2则提供了高性能的大整数运算在处理稍大的数时比Python原生整数更快、更稳定。pip install sympy gmpy2如果安装gmpy2遇到困难特别是在Windows上可以暂时只用sympy对于真正的“Baby”级数字它也完全够用。3.2 脚本骨架与参数输入我们设计脚本能通过命令行参数或直接修改代码来输入题目信息。一个典型的CTF RSA题目会给你n, e, c模数、加密指数、密文有时还会给一些其他提示。import sys from math import isqrt, gcd import sympy from Crypto.Util.number import long_to_bytes, bytes_to_long # 示例参数 - 在实际使用时替换成题目给你的值 n 742449129124467073921545687640895127535705902454369756401331 e 65537 c 39207274348578481322317340648475596807303160111338236677373 def main(): print(f[*] 题目参数: n{n}, e{e}) print(f[*] 待解密密文 c: {c}) # 攻击流程将在这里展开3.3 攻击模块一因式分解当n很小这是最直接、最暴力的方法也是“BabyRSA”得名的原因。思路很简单尝试把n分解成两个质数p和q。def factorize_small_n(n): 尝试分解较小的n print(f[*] 尝试因式分解 n...) # 方法1: 使用sympy的factorint对小整数非常高效 try: factors sympy.factorint(n) if len(factors) 2 and all(v 1 for v in factors.values()): p, q list(factors.keys()) print(f[] 分解成功! p {p}, q {q}) return p, q else: print(f[-] 分解结果不是两个质数: {factors}) return None, None except Exception as e: print(f[-] sympy分解失败: {e}) # 方法2: 简单试除法仅适用于极小的n用于理解原理 print(f[*] 回退到试除法...) for i in range(2, isqrt(n) 1): if n % i 0: p i q n // i if sympy.isprime(p) and sympy.isprime(q): print(f[] 试除分解成功! p {p}, q {q}) return p, q print([-] 分解失败n可能不是两个质数的乘积或者需要更强大的分解方法。) return None, None注意sympy.factorint对于几十位的整数分解很快但如果n超过100位速度会急剧下降。对于真正的“BabyRSA”这足够了。如果题目给的n略大可能需要用到更专业的分解算法或网站如 factordb.com但那就超出“Baby”的范围了。3.4 攻击模块二低加密指数攻击e很小如3当e很小且明文m也不大时可能存在m^e n此时c m^e。def low_encryption_exponent_attack(c, e): 低加密指数攻击直接对密文开e次方 print(f[*] 尝试低加密指数攻击 (e{e})...) # 尝试在整数范围内开方 root, exact sympy.integer_nthroot(c, e) if exact: m root print(f[] 攻击成功! 直接开{e}次方得到明文: {m}) print(f[] 明文(字节): {long_to_bytes(m)}) return m else: print(f[-] 攻击失败c 不是某个整数的 {e} 次幂。) return None3.5 攻击模块三计算私钥d并解密一旦成功分解n得到p和q万事俱备。接下来就是标准的RSA解密流程。def compute_private_key_and_decrypt(p, q, e, c): 已知p, q, e, c计算私钥d并解密 if p is None or q is None: return None print(f[*] 计算欧拉函数 φ(n) (p-1)*(q-1)...) phi (p - 1) * (q - 1) print(f[*] 计算私钥d即e关于φ(n)的模逆元...) try: d sympy.mod_inverse(e, phi) print(f[] 私钥 d {d}) except Exception as e: print(f[-] 计算模逆元失败: {e}。e和φ(n)可能不互质。) return None print(f[*] 使用私钥d解密密文c...) m pow(c, d, n) # 使用pow的第三个参数进行模幂运算效率极高 print(f[] 解密得到的数字明文 m {m}) # 尝试将数字转换为可读的字节/字符串 try: flag long_to_bytes(m).decode(utf-8) print(f[] 成功! 明文为: {flag}) except UnicodeDecodeError: print(f[] 明文转换为字节: {long_to_bytes(m)}) # 可能不是UTF-8文本可能是其他数据 return m3.6 主流程控制将上述模块串联起来形成一个有逻辑的攻击流程。def attack_rsa(n, e, c): print(*60) print(开始BabyRSA自动攻击流程) print(*60) # 第一步尝试低加密指数攻击最省事 if e 10: # 通常e3, 5等小值时尝试 m low_encryption_exponent_attack(c, e) if m is not None: return # 第二步尝试因式分解nBabyRSA最常见 p, q factorize_small_n(n) if p and q: compute_private_key_and_decrypt(p, q, e, c) return # 第三步如果前两步都失败提示可能需要其他攻击方式 print(\n[-] 常规攻击失败。可能情况) print( 1. n 并非‘Baby’级别需要更强大的分解工具如yafu、factordb。) print( 2. 存在其他脆弱性如共模攻击、维纳攻击、广播攻击等。) print( 3. 题目参数不完整或需要其他前置步骤。) # 这里可以后续扩展其他攻击模块把main()函数改成调用attack_rsa(n, e, c)一个基础的BabyRSA破解工具就成型了。4. 深入原理为什么这些攻击会奏效掌握了工具我们再来深入一层理解这些攻击背后的数学原理。这能帮助你在遇到变形题时举一反三。4.1 因式分解攻击的数学本质RSA的解密密钥d由公式d ≡ e^(-1) mod φ(n)定义。而φ(n) (p-1)(q-1)。所以整个解密过程依赖于p和q的保密性。一旦n被分解p和q暴露φ(n)就不再是秘密d也就唾手可得。对于大素数分解是难的但对于小素数分解就是简单的计算问题。在CTF中出题人故意选择小素数就是为了让选手能够轻松完成这个“本应不可行”的步骤从而聚焦于RSA流程本身。4.2 低加密指数攻击的边界条件这种攻击成立的关键条件是m^e n。为什么回顾加密公式c m^e mod n。“mod n”意味着取余数。如果m^e本身就比n小那么除以n的商就是0余数就是m^e本身即c m^e。去掉了“模运算”这个非线性环节加密过程就退化成了简单的幂运算自然可以轻松开方逆转。在实际中如果e3只要m小于n^(1/3)攻击就有效。出题人常通过填充padding来避免这种情况但“Baby”题有时会省略填充以简化题目。4.3 共模攻击的原理简述假设同一个明文m用相同的n但两个不同的互质的加密指数e1和e2加密得到c1和c2。即c1 ≡ m^e1 (mod n)c2 ≡ m^e2 (mod n)根据扩展欧几里得算法可以找到两个整数s和t使得e1*s e2*t gcd(e1, e2) 1。 那么我们可以计算(c1^s * c2^t) mod n ≡ m^(e1*s) * m^(e2*t) mod n ≡ m^(e1*s e2*t) mod n ≡ m^1 mod n ≡ m这样在不分解n、不知道d的情况下我们就恢复了明文m。这种攻击提醒我们绝对不要用同一个模数n为多个用户生成密钥对。5. 从解题到出题BabyRSA的常见变种与陷阱玩转了破解我们不妨换个视角看看出题人怎么设置“BabyRSA”题目。理解出题思路能让你在解题时更快地抓住要害。5.1 变种一给出多个n寻找公因子有时题目会给你多个RSA的模数n1, n2, n3... 和它们对应的密文。如果这些n是在生成时使用了不独立的随机数可能会存在相同的质数即公因子。你可以通过计算gcd(n1, n2)来快速检查。如果最大公约数大于1那么恭喜你你找到了一个质因子可以瞬间分解这两个n。def common_factor_attack(n_list): 检查一组模数是否存在公因子 for i in range(len(n_list)): for j in range(i1, len(n_list)): g gcd(n_list[i], n_list[j]) if g 1: print(f[] 发现公因子! gcd(n{i}, n{j}) {g}) return g print([-] 未发现公因子。) return None5.2 变种二给出d恢复其他参数有一种不太常见但很巧妙的题型只给你解密指数d和模数n的一部分信息或者e让你恢复出完整的私钥或明文。这通常需要利用e*d ≡ 1 mod φ(n)这个关系式以及φ(n)与n非常接近的性质通过数学推导来暴力枚举可能的φ(n)和k其中e*d k*φ(n) 1。这更考验你对RSA等式关系的理解。5.3 变种三隐藏的编码与转换“BabyRSA”的难点有时不在RSA本身而在前后处理。比如明文m不是直接flag解密出来的数字m可能需要转换成十六进制再解码为ASCII字符串。有时这个字符串可能还是Base64编码需要再次解码。数字很大需要特殊处理Python的int类型可以处理任意大整数但有些语言需要特别注意。在将密文c或明文m转换为整数时要确保编码/解码方式正确通常是bytes_to_long和long_to_bytes。参数以非常规形式给出比如p和q以十六进制字符串、Base64编码甚至藏在图片的像素值里。第一步永远是正确提取并转换为Python整数。5.4 刻意设置的陷阱不是UTF-8文本解密出的字节可能不是可读的文本而是其他格式的数据如PNG文件头。不要一看到乱码就放弃用long_to_bytes(m)查看原始字节并用file命令或十六进制编辑器查看其结构。需要多次解密有时flag被用相同的RSA密钥加密了多次或者外层是RSA内层是其他编码。需要耐心地一层层剥开。e和φ(n)不互质这是最阴险的陷阱之一。如果gcd(e, φ(n)) ! 1那么解密指数d就不存在标准RSA解密流程会失败。这种情况下需要利用中国剩余定理(CRT)或其他方法进行解密。在“Baby”题中这通常意味着p或q的选取有问题比如p-1或q-1与e有公因子。6. 实战演练解剖一道经典BabyRSA题目让我们用一个虚构但非常典型的例子把上面的知识串起来。题目如下n 742449129124467073921545687640895127535705902454369756401331 e 65537 c 39207274348578481322317340648475596807303160111338236677373你的任务是解密c得到flag。第一步观察e是常见的65537不算小所以低加密指数攻击可能性低。焦点在n上。n的长度大约是21位十进制数对于现代计算机来说这绝对属于“Baby”级别。第二步分解n我们使用脚本中的factorize_small_n函数。实际上你可以直接在网上找一个在线的质数分解计算器或者用Python的sympy.factorint。import sympy n 742449129124467073921545687640895127535705902454369756401331 print(sympy.factorint(n))输出{7527087888371655903: 1, 9863696825852819933: 1}成功p 7527087888371655903,q 9863696825852819933。第三步计算私钥并解密p 7527087888371655903 q 9863696825852819933 e 65537 c 39207274348578481322317340648475596807303160111338236677373 n p * q # 验证一下确实等于题目给的n phi (p-1)*(q-1) d sympy.mod_inverse(e, phi) m pow(c, d, n) print(m) print(long_to_bytes(m).decode(utf-8))输出数字m然后转换为字节很可能得到像flag{s0m3th1ng_l1k3_th1s}这样的字符串。第四步验证与提交将解密出的字符串提交到CTF平台完成挑战。整个过程的核心就是分解n。在真实的CTF中你可能需要把这一步自动化到脚本里。这个例子展示了最基础的BabyRSA形态小n导致可分解。7. 进阶思考与工具扩展当你熟练解决基础BabyRSA后可以尝试以下方向来提升7.1 集成更多攻击向量将我们之前讨论的其他攻击方法模块化加入到主攻击脚本中使其成为一个更全面的RSA多功能测试工具。例如共模攻击模块输入(n, e1, c1), (n, e2, c2)输出明文m。维纳攻击模块当d较小时利用连分数逼近法求解。广播攻击模块相同的明文m用相同的e但不同的n加密当e较小时可利用中国剩余定理(CRT)求解。Factordb查询模块对于稍大的n自动连接 factordb.com 这样的在线分解数据库尝试查询。7.2 理解Padding的重要性真实的RSA加密绝不会直接对原始消息m进行运算。因为直接加密存在很多弱点如确定性加密、小明文攻击等。因此在实际应用和更高级的CTF题中你会遇到各种填充方案如PKCS#1 v1.5, OAEP等。这些填充方案引入了随机性使得即使加密相同的明文每次产生的密文也不同并且能有效抵御低加密指数等攻击。学习这些填充方案及其可能存在的漏洞是走出“Baby”阶段的关键。7.3 从Python到更专业的工具虽然Python脚本灵活方便但在CTF比赛中你可能会遇到需要快速尝试多种攻击的情况。一些成熟的工具链能极大提高效率RsaCtfTool一个功能极其强大的RSA攻击工具集用Python编写集成了数十种攻击方法。对于不熟悉脚本编写的选手这是“瑞士军刀”般的存在。sageMath一个基于Python的数学计算系统在代数、数论方面功能超强。很多复杂的RSA攻击如基于格归约的攻击在sage中都有现成的函数或脚本示例。yafu一个强大的整数分解工具对于中等大小的整数比如100-200位十进制数它的分解速度远超一般脚本。我的建议是初期用自己写的脚本加深理解后期熟练使用这些专业工具来提升解题速度。理解原理永远是第一位的。8. 避坑指南与心得分享最后分享一些我在折腾BabyRSA和更复杂的RSA题目时踩过的坑和总结的经验希望能帮你少走弯路。坑1编码转换的魔鬼细节这是新手最容易出错的地方。CTF题目中密文c和明文m常常以十六进制字符串或Base64字符串的形式给出。你必须准确地将其转换为Python的int类型。十六进制字符串转intint(0xabc..., 16)或int(abc..., 16)Base64字符串转int需要先base64.b64decode成字节再用bytes_to_long或int.from_bytes()转成int。反之解密后的int转回字符串先long_to_bytes然后尝试.decode(utf-8)。如果不是UTF-8可能是ASCII、十六进制表示、或直接是二进制数据如图片。实操心得写一个通用的转换函数并打印中间结果。比如在解密出m后不仅打印long_to_bytes(m)也打印其十六进制表示hex(m)。有时flag就藏在十六进制里。坑2Python大整数运算的“隐形”错误Python的int虽然支持大数但直接写c**d % n这种表达式在指数d很大时会先计算一个天文数字般的中间结果c**d导致内存溢出。务必使用三参数形式的pow(c, d, n)它采用模幂算法高效且不会产生巨大的中间值。坑3误判攻击路径看到e65537就埋头分解n结果n根本分解不动。或者看到n很小就以为一定能分解却忽略了题目可能考察的是其他知识点比如给出的n根本不是两个质数的乘积。一定要先全面审视题目给的所有信息包括文件名、注释、描述可能都隐藏着提示。尝试最简单的攻击如低加密指数后再尝试分解。如果都不行就要思考是否是共模、广播、维纳攻击等场景。坑4忽略数学前提比如进行共模攻击时必须确保gcd(e1, e2) 1。计算中国剩余定理(CRT)时必须确保模数两两互质。在写脚本时加入这些条件判断能让你的工具更健壮也帮你理清思路。一个重要的心态不要把“BabyRSA”仅仅当作是简单的、用来得分的题目。它是你理解现代密码学一个核心概念的绝佳沙盒。通过它你能直观地感受到“计算安全性”的含义——一个系统的安全不是绝对的而是基于当前计算能力的“实践安全”。当参数选择不当安全边界就被打破了。这种体会比单纯记下几个攻击脚本的命令要宝贵得多。当你能够游刃有余地解决各种变形的BabyRSA并且能清晰地跟别人解释每一步为什么这样做时你就已经打下了坚实的密码学实战基础。接下来你就可以充满信心地去挑战那些更复杂、更精妙的非对称密码学题目了。
从BabyRSA入门CTF密码学：原理、攻击脚本与实战解析
1. 项目概述从“BabyRSA”说起如果你玩过CTFCapture The Flag网络安全竞赛或者对密码学有点兴趣那你大概率见过“BabyRSA”这个词。它不是一个具体的工具或标准而更像是一个圈子里的“黑话”特指那些使用了RSA加密算法但参数尤其是质数p和q选得特别小、特别“弱”的题目或场景。这类题目通常出现在CTF的入门级密码学挑战中目的是让新手在相对简单的环境下理解RSA的核心原理和常见的攻击手法比如因式分解、共模攻击、低加密指数攻击等。所以当你看到“BabyRSA”这个标题它背后指向的其实是一个充满实践乐趣的密码学学习领域如何利用“脆弱”的RSA实现来逆向还原出明文信息。我自己在带新人入门CTF密码学方向时发现很多朋友一上来就被RSA那一堆数学公式欧拉函数、模逆元吓退了。但“BabyRSA”恰恰是打破这个恐惧的最佳切入点。它剥离了工业级RSA那种天文数字般的大素数带来的计算复杂性让你可以专注于算法流程和攻击逻辑本身。通过动手解决一个个“Baby”级别的题目你能清晰地看到一个理论上坚不可摧的密码系统如果在使用上“偷工减料”会暴露出多少致命的破绽。这不仅是解题更是一种深刻的安全思维训练——让你明白安全是一个系统工程任何一个环节的疏忽都可能导致全线崩溃。接下来我会围绕“BabyRSA”这个核心拆解它涉及的密码学原理、常见的脆弱场景、实用的攻击工具脚本比如如何用Python快速实现解密以及你在实际操作中一定会遇到的坑和技巧。无论你是想入门CTF还是单纯对“如何破解简单密码”感到好奇这篇文章都能给你一套可以直接上手操作的“地图”。2. RSA算法原理快速回顾与“Baby”的由来要理解为什么“BabyRSA”能被破解首先得知道标准的RSA应该是什么样子的。别担心我们不用深究所有数学证明只抓和破解相关的核心流程。2.1 RSA加密解密的核心步骤RSA是一种非对称加密算法也就是说加密和解密用的是不同的钥匙。这里涉及几个关键角色p和q两个非常大的、随机的质数。这是整个系统安全的基石。n模数。n p * q。这个n是公开的。φ(n)欧拉函数。对于两个质数p和qφ(n) (p-1)*(q-1)。这个值必须严格保密。e加密指数。一个与φ(n)互质的数通常是65537。这个e是公开的。d解密指数。e关于φ(n)的模逆元即满足(e * d) mod φ(n) 1。这个d是私钥的核心必须绝对保密。加密过程对于明文m需要先转换成数字计算密文c m^e mod n。解密过程用私钥d计算明文m c^d mod n。整个系统的安全性建立在“大数分解难题”上从公开的n反向推导出p和q是计算上不可行的。只要p和q足够大比如2048位以上以目前人类的计算能力想分解n需要的时间可能是宇宙的年龄那么长。2.2 “Baby”在哪里脆弱性根源分析所谓“BabyRSA”就是人为地削弱了上述某个或某几个环节使其从“计算不可行”变成了“计算可行”。常见的“放水”点有质数太小n太小这是最经典的“Baby”特征。比如p和q只有几十位甚至十几位十进制数。这样n也很小现代计算机可以在毫秒级内完成因式分解。一旦分解出p和q就能立刻算出φ(n)和私钥d整个加密体系瞬间崩塌。加密指数e太小如果e非常小比如3而明文m也不大可能导致m^e n。这时加密操作c m^e mod n就等于m^e本身因为没超过模数n取模无效果。攻击者直接对密文c开e次方根就能得到明文m完全绕过了分解n。解密指数d太小如果私钥d选得太小可能存在一种叫做“维纳攻击”的方法通过连分数逼近直接从公开的e和n中恢复出d。共模攻击如果同样的明文m用相同的n但不同的e加密了两次得到两个密文c1和c2。那么在不分解n的情况下也有可能恢复出明文。模数n重用或存在公因子如果多个RSA密钥对使用了相同的n或者不同的n之间存在公因子那么安全性会急剧下降。在CTF的“BabyRSA”题目里出题人往往会故意设置这些脆弱条件目的就是考察你对这些特定攻击场景的识别和利用能力。它就像一把故意没锁好的锁让你练习开锁技巧而不是去暴力砸墙。3. 实战工具链手把手打造你的BabyRSA解密脚本光说不练假把式。接下来我们用一个Python脚本将上述攻击思路具体化。这个脚本的目标是给定一组“脆弱”的RSA参数可能是从CTF题目中提取的自动判断可能的攻击路径并完成解密。我会分模块讲解你可以把它们组合成一个完整的工具。3.1 环境准备与核心库首先你需要一个Python3环境。核心库是sympy和gmpy2。sympy用于符号计算和质数相关操作gmpy2则提供了高性能的大整数运算在处理稍大的数时比Python原生整数更快、更稳定。pip install sympy gmpy2如果安装gmpy2遇到困难特别是在Windows上可以暂时只用sympy对于真正的“Baby”级数字它也完全够用。3.2 脚本骨架与参数输入我们设计脚本能通过命令行参数或直接修改代码来输入题目信息。一个典型的CTF RSA题目会给你n, e, c模数、加密指数、密文有时还会给一些其他提示。import sys from math import isqrt, gcd import sympy from Crypto.Util.number import long_to_bytes, bytes_to_long # 示例参数 - 在实际使用时替换成题目给你的值 n 742449129124467073921545687640895127535705902454369756401331 e 65537 c 39207274348578481322317340648475596807303160111338236677373 def main(): print(f[*] 题目参数: n{n}, e{e}) print(f[*] 待解密密文 c: {c}) # 攻击流程将在这里展开3.3 攻击模块一因式分解当n很小这是最直接、最暴力的方法也是“BabyRSA”得名的原因。思路很简单尝试把n分解成两个质数p和q。def factorize_small_n(n): 尝试分解较小的n print(f[*] 尝试因式分解 n...) # 方法1: 使用sympy的factorint对小整数非常高效 try: factors sympy.factorint(n) if len(factors) 2 and all(v 1 for v in factors.values()): p, q list(factors.keys()) print(f[] 分解成功! p {p}, q {q}) return p, q else: print(f[-] 分解结果不是两个质数: {factors}) return None, None except Exception as e: print(f[-] sympy分解失败: {e}) # 方法2: 简单试除法仅适用于极小的n用于理解原理 print(f[*] 回退到试除法...) for i in range(2, isqrt(n) 1): if n % i 0: p i q n // i if sympy.isprime(p) and sympy.isprime(q): print(f[] 试除分解成功! p {p}, q {q}) return p, q print([-] 分解失败n可能不是两个质数的乘积或者需要更强大的分解方法。) return None, None注意sympy.factorint对于几十位的整数分解很快但如果n超过100位速度会急剧下降。对于真正的“BabyRSA”这足够了。如果题目给的n略大可能需要用到更专业的分解算法或网站如 factordb.com但那就超出“Baby”的范围了。3.4 攻击模块二低加密指数攻击e很小如3当e很小且明文m也不大时可能存在m^e n此时c m^e。def low_encryption_exponent_attack(c, e): 低加密指数攻击直接对密文开e次方 print(f[*] 尝试低加密指数攻击 (e{e})...) # 尝试在整数范围内开方 root, exact sympy.integer_nthroot(c, e) if exact: m root print(f[] 攻击成功! 直接开{e}次方得到明文: {m}) print(f[] 明文(字节): {long_to_bytes(m)}) return m else: print(f[-] 攻击失败c 不是某个整数的 {e} 次幂。) return None3.5 攻击模块三计算私钥d并解密一旦成功分解n得到p和q万事俱备。接下来就是标准的RSA解密流程。def compute_private_key_and_decrypt(p, q, e, c): 已知p, q, e, c计算私钥d并解密 if p is None or q is None: return None print(f[*] 计算欧拉函数 φ(n) (p-1)*(q-1)...) phi (p - 1) * (q - 1) print(f[*] 计算私钥d即e关于φ(n)的模逆元...) try: d sympy.mod_inverse(e, phi) print(f[] 私钥 d {d}) except Exception as e: print(f[-] 计算模逆元失败: {e}。e和φ(n)可能不互质。) return None print(f[*] 使用私钥d解密密文c...) m pow(c, d, n) # 使用pow的第三个参数进行模幂运算效率极高 print(f[] 解密得到的数字明文 m {m}) # 尝试将数字转换为可读的字节/字符串 try: flag long_to_bytes(m).decode(utf-8) print(f[] 成功! 明文为: {flag}) except UnicodeDecodeError: print(f[] 明文转换为字节: {long_to_bytes(m)}) # 可能不是UTF-8文本可能是其他数据 return m3.6 主流程控制将上述模块串联起来形成一个有逻辑的攻击流程。def attack_rsa(n, e, c): print(*60) print(开始BabyRSA自动攻击流程) print(*60) # 第一步尝试低加密指数攻击最省事 if e 10: # 通常e3, 5等小值时尝试 m low_encryption_exponent_attack(c, e) if m is not None: return # 第二步尝试因式分解nBabyRSA最常见 p, q factorize_small_n(n) if p and q: compute_private_key_and_decrypt(p, q, e, c) return # 第三步如果前两步都失败提示可能需要其他攻击方式 print(\n[-] 常规攻击失败。可能情况) print( 1. n 并非‘Baby’级别需要更强大的分解工具如yafu、factordb。) print( 2. 存在其他脆弱性如共模攻击、维纳攻击、广播攻击等。) print( 3. 题目参数不完整或需要其他前置步骤。) # 这里可以后续扩展其他攻击模块把main()函数改成调用attack_rsa(n, e, c)一个基础的BabyRSA破解工具就成型了。4. 深入原理为什么这些攻击会奏效掌握了工具我们再来深入一层理解这些攻击背后的数学原理。这能帮助你在遇到变形题时举一反三。4.1 因式分解攻击的数学本质RSA的解密密钥d由公式d ≡ e^(-1) mod φ(n)定义。而φ(n) (p-1)(q-1)。所以整个解密过程依赖于p和q的保密性。一旦n被分解p和q暴露φ(n)就不再是秘密d也就唾手可得。对于大素数分解是难的但对于小素数分解就是简单的计算问题。在CTF中出题人故意选择小素数就是为了让选手能够轻松完成这个“本应不可行”的步骤从而聚焦于RSA流程本身。4.2 低加密指数攻击的边界条件这种攻击成立的关键条件是m^e n。为什么回顾加密公式c m^e mod n。“mod n”意味着取余数。如果m^e本身就比n小那么除以n的商就是0余数就是m^e本身即c m^e。去掉了“模运算”这个非线性环节加密过程就退化成了简单的幂运算自然可以轻松开方逆转。在实际中如果e3只要m小于n^(1/3)攻击就有效。出题人常通过填充padding来避免这种情况但“Baby”题有时会省略填充以简化题目。4.3 共模攻击的原理简述假设同一个明文m用相同的n但两个不同的互质的加密指数e1和e2加密得到c1和c2。即c1 ≡ m^e1 (mod n)c2 ≡ m^e2 (mod n)根据扩展欧几里得算法可以找到两个整数s和t使得e1*s e2*t gcd(e1, e2) 1。 那么我们可以计算(c1^s * c2^t) mod n ≡ m^(e1*s) * m^(e2*t) mod n ≡ m^(e1*s e2*t) mod n ≡ m^1 mod n ≡ m这样在不分解n、不知道d的情况下我们就恢复了明文m。这种攻击提醒我们绝对不要用同一个模数n为多个用户生成密钥对。5. 从解题到出题BabyRSA的常见变种与陷阱玩转了破解我们不妨换个视角看看出题人怎么设置“BabyRSA”题目。理解出题思路能让你在解题时更快地抓住要害。5.1 变种一给出多个n寻找公因子有时题目会给你多个RSA的模数n1, n2, n3... 和它们对应的密文。如果这些n是在生成时使用了不独立的随机数可能会存在相同的质数即公因子。你可以通过计算gcd(n1, n2)来快速检查。如果最大公约数大于1那么恭喜你你找到了一个质因子可以瞬间分解这两个n。def common_factor_attack(n_list): 检查一组模数是否存在公因子 for i in range(len(n_list)): for j in range(i1, len(n_list)): g gcd(n_list[i], n_list[j]) if g 1: print(f[] 发现公因子! gcd(n{i}, n{j}) {g}) return g print([-] 未发现公因子。) return None5.2 变种二给出d恢复其他参数有一种不太常见但很巧妙的题型只给你解密指数d和模数n的一部分信息或者e让你恢复出完整的私钥或明文。这通常需要利用e*d ≡ 1 mod φ(n)这个关系式以及φ(n)与n非常接近的性质通过数学推导来暴力枚举可能的φ(n)和k其中e*d k*φ(n) 1。这更考验你对RSA等式关系的理解。5.3 变种三隐藏的编码与转换“BabyRSA”的难点有时不在RSA本身而在前后处理。比如明文m不是直接flag解密出来的数字m可能需要转换成十六进制再解码为ASCII字符串。有时这个字符串可能还是Base64编码需要再次解码。数字很大需要特殊处理Python的int类型可以处理任意大整数但有些语言需要特别注意。在将密文c或明文m转换为整数时要确保编码/解码方式正确通常是bytes_to_long和long_to_bytes。参数以非常规形式给出比如p和q以十六进制字符串、Base64编码甚至藏在图片的像素值里。第一步永远是正确提取并转换为Python整数。5.4 刻意设置的陷阱不是UTF-8文本解密出的字节可能不是可读的文本而是其他格式的数据如PNG文件头。不要一看到乱码就放弃用long_to_bytes(m)查看原始字节并用file命令或十六进制编辑器查看其结构。需要多次解密有时flag被用相同的RSA密钥加密了多次或者外层是RSA内层是其他编码。需要耐心地一层层剥开。e和φ(n)不互质这是最阴险的陷阱之一。如果gcd(e, φ(n)) ! 1那么解密指数d就不存在标准RSA解密流程会失败。这种情况下需要利用中国剩余定理(CRT)或其他方法进行解密。在“Baby”题中这通常意味着p或q的选取有问题比如p-1或q-1与e有公因子。6. 实战演练解剖一道经典BabyRSA题目让我们用一个虚构但非常典型的例子把上面的知识串起来。题目如下n 742449129124467073921545687640895127535705902454369756401331 e 65537 c 39207274348578481322317340648475596807303160111338236677373你的任务是解密c得到flag。第一步观察e是常见的65537不算小所以低加密指数攻击可能性低。焦点在n上。n的长度大约是21位十进制数对于现代计算机来说这绝对属于“Baby”级别。第二步分解n我们使用脚本中的factorize_small_n函数。实际上你可以直接在网上找一个在线的质数分解计算器或者用Python的sympy.factorint。import sympy n 742449129124467073921545687640895127535705902454369756401331 print(sympy.factorint(n))输出{7527087888371655903: 1, 9863696825852819933: 1}成功p 7527087888371655903,q 9863696825852819933。第三步计算私钥并解密p 7527087888371655903 q 9863696825852819933 e 65537 c 39207274348578481322317340648475596807303160111338236677373 n p * q # 验证一下确实等于题目给的n phi (p-1)*(q-1) d sympy.mod_inverse(e, phi) m pow(c, d, n) print(m) print(long_to_bytes(m).decode(utf-8))输出数字m然后转换为字节很可能得到像flag{s0m3th1ng_l1k3_th1s}这样的字符串。第四步验证与提交将解密出的字符串提交到CTF平台完成挑战。整个过程的核心就是分解n。在真实的CTF中你可能需要把这一步自动化到脚本里。这个例子展示了最基础的BabyRSA形态小n导致可分解。7. 进阶思考与工具扩展当你熟练解决基础BabyRSA后可以尝试以下方向来提升7.1 集成更多攻击向量将我们之前讨论的其他攻击方法模块化加入到主攻击脚本中使其成为一个更全面的RSA多功能测试工具。例如共模攻击模块输入(n, e1, c1), (n, e2, c2)输出明文m。维纳攻击模块当d较小时利用连分数逼近法求解。广播攻击模块相同的明文m用相同的e但不同的n加密当e较小时可利用中国剩余定理(CRT)求解。Factordb查询模块对于稍大的n自动连接 factordb.com 这样的在线分解数据库尝试查询。7.2 理解Padding的重要性真实的RSA加密绝不会直接对原始消息m进行运算。因为直接加密存在很多弱点如确定性加密、小明文攻击等。因此在实际应用和更高级的CTF题中你会遇到各种填充方案如PKCS#1 v1.5, OAEP等。这些填充方案引入了随机性使得即使加密相同的明文每次产生的密文也不同并且能有效抵御低加密指数等攻击。学习这些填充方案及其可能存在的漏洞是走出“Baby”阶段的关键。7.3 从Python到更专业的工具虽然Python脚本灵活方便但在CTF比赛中你可能会遇到需要快速尝试多种攻击的情况。一些成熟的工具链能极大提高效率RsaCtfTool一个功能极其强大的RSA攻击工具集用Python编写集成了数十种攻击方法。对于不熟悉脚本编写的选手这是“瑞士军刀”般的存在。sageMath一个基于Python的数学计算系统在代数、数论方面功能超强。很多复杂的RSA攻击如基于格归约的攻击在sage中都有现成的函数或脚本示例。yafu一个强大的整数分解工具对于中等大小的整数比如100-200位十进制数它的分解速度远超一般脚本。我的建议是初期用自己写的脚本加深理解后期熟练使用这些专业工具来提升解题速度。理解原理永远是第一位的。8. 避坑指南与心得分享最后分享一些我在折腾BabyRSA和更复杂的RSA题目时踩过的坑和总结的经验希望能帮你少走弯路。坑1编码转换的魔鬼细节这是新手最容易出错的地方。CTF题目中密文c和明文m常常以十六进制字符串或Base64字符串的形式给出。你必须准确地将其转换为Python的int类型。十六进制字符串转intint(0xabc..., 16)或int(abc..., 16)Base64字符串转int需要先base64.b64decode成字节再用bytes_to_long或int.from_bytes()转成int。反之解密后的int转回字符串先long_to_bytes然后尝试.decode(utf-8)。如果不是UTF-8可能是ASCII、十六进制表示、或直接是二进制数据如图片。实操心得写一个通用的转换函数并打印中间结果。比如在解密出m后不仅打印long_to_bytes(m)也打印其十六进制表示hex(m)。有时flag就藏在十六进制里。坑2Python大整数运算的“隐形”错误Python的int虽然支持大数但直接写c**d % n这种表达式在指数d很大时会先计算一个天文数字般的中间结果c**d导致内存溢出。务必使用三参数形式的pow(c, d, n)它采用模幂算法高效且不会产生巨大的中间值。坑3误判攻击路径看到e65537就埋头分解n结果n根本分解不动。或者看到n很小就以为一定能分解却忽略了题目可能考察的是其他知识点比如给出的n根本不是两个质数的乘积。一定要先全面审视题目给的所有信息包括文件名、注释、描述可能都隐藏着提示。尝试最简单的攻击如低加密指数后再尝试分解。如果都不行就要思考是否是共模、广播、维纳攻击等场景。坑4忽略数学前提比如进行共模攻击时必须确保gcd(e1, e2) 1。计算中国剩余定理(CRT)时必须确保模数两两互质。在写脚本时加入这些条件判断能让你的工具更健壮也帮你理清思路。一个重要的心态不要把“BabyRSA”仅仅当作是简单的、用来得分的题目。它是你理解现代密码学一个核心概念的绝佳沙盒。通过它你能直观地感受到“计算安全性”的含义——一个系统的安全不是绝对的而是基于当前计算能力的“实践安全”。当参数选择不当安全边界就被打破了。这种体会比单纯记下几个攻击脚本的命令要宝贵得多。当你能够游刃有余地解决各种变形的BabyRSA并且能清晰地跟别人解释每一步为什么这样做时你就已经打下了坚实的密码学实战基础。接下来你就可以充满信心地去挑战那些更复杂、更精妙的非对称密码学题目了。
