1. 项目概述BabyRSA是什么以及它为何在CTF圈子里火了如果你玩过网络安全竞赛CTF尤其是其中的密码学Crypto题目那你大概率见过“BabyRSA”这个名字。它不是一个具体的工具而是一类题目的统称特指那些使用RSA加密算法但参数设置存在明显“弱点”或“瑕疵”的挑战。这类题目通常作为密码学方向的入门题旨在引导选手理解RSA的基本原理并学会利用其实现上的不严谨来破解加密。我接触过不少刚入门的CTF选手他们往往对RSA望而生畏觉得涉及大数分解、模运算门槛太高。但BabyRSA恰恰是打破这种恐惧的绝佳入口——它把复杂的密码学原理简化成了一个可以“手撕”或者用简单脚本就能解决的谜题。简单来说RSA的安全性建立在“大整数分解难题”之上给你一个巨大的合数比如两个数百位质数相乘的结果在有限时间内你几乎无法将它分解回原来的两个质数。但BabyRSA反其道而行之它给出的“大整数”一点也不大可能只有几十位甚至十几位或者它虽然数字大但暴露了太多关键信息比如公钥指数e极小、私钥d泄露、或者两个密文共用了一个模数。这些“婴儿级”的漏洞让看似坚固的RSA堡垒出现了裂缝。而网络上流传的诸如mrdebator/BabyRSA这类Python脚本就是针对这些特定裂缝打造的“开锁工具包”。它们封装了针对常见弱点的攻击算法让解题者无需从零开始推导数学公式只需填入题目给出的参数就能快速得到flag。这大大降低了参与门槛也使得BabyRSA成为CTF密码学中最受欢迎、也最出名的题型之一。所以当你看到“BabyRSA”这个标题时它背后指向的不仅仅是一个GitHub仓库更是一个庞大的实战场景CTF竞赛、密码学教育、以及对于RSA算法核心脆弱性的探索。接下来我会从一个CTF老兵的角度带你彻底拆解BabyRSA的常见套路、攻击原理并手把手教你如何复现和编写自己的解题脚本。你会发现破解它需要的不是高深的数学而是清晰的思路和对细节的把握。2. BabyRSA的常见“弱点”模式与攻击原理全解析为什么叫“Baby”就是因为它的设置不够“成人”留下了诸多可乘之机。这些弱点模式经过多年CTF出题人和解题者的博弈已经形成了相当固定的几个类别。理解这些模式就等于拿到了解题的路线图。2.1 模数N过小直接暴力分解这是最经典、最“Baby”的情况。RSA的模数N p * q其中p和q是两个大质数。如果N本身很小比如小于256位那么在现代计算机上利用高效的分解算法如Pollards rho、二次筛法甚至在线数据库如factordb.com可以在极短的时间内分解出p和q。攻击原理一旦分解出p和qRSA的整个防线就崩溃了。我们可以计算出欧拉函数φ(N) (p-1)*(q-1)然后根据公钥指数e计算出私钥d即e关于φ(N)的模逆元d ≡ e^(-1) mod φ(N)。有了私钥d解密就是一次模幂运算明文 m ≡ c^d mod N。实操中的关键点判断N是否“小”是一个经验值。十年前512位的N被认为是不安全的如今对于CTF题目768位以下的N通常都可以尝试用yafu或sage等工具在个人电脑上分解。而对于真正的“Baby”题N可能只有几十位用Python的sympy库里的factorint函数一秒就能出结果。注意在真实世界的RSA应用中N的长度至少应为2048位3072位或4096位正成为新的标准。CTF中的小N纯粹是为了教学和竞技。2.2 公钥指数e过小或过大导致特定攻击公钥指数e通常取655370x10001这是一个在安全性和计算效率之间取得平衡的值。但当e偏离这个常规值时就可能引发问题。情况一e过小比如e3且明文m也很小。如果m^e N那么加密过程c ≡ m^e mod N中的模运算实际上没有起作用因为m^e根本就没超过N。此时密文c就是明文m的e次方直接对c开e次方根比如在整数域内开立方根就能得到m。情况二e过大导致私钥d过小。如果私钥d很小比如小于N的0.292次方那么可以使用Wiener攻击或Boneh-Durfee攻击通过连分数逼近的方法从公钥对 (N, e) 中恢复出私钥d。这在CTF题中也很常见题目可能会给一个异常大的e暗示你要往这方面想。2.3 共模攻击Common Modulus Attack这是非常经典的一种场景。题目给出了两段不同的密文c1和c2它们是用相同的模数N但不同的公钥指数e1和e2加密同一段明文m得到的。即c1 ≡ m^(e1) mod Nc2 ≡ m^(e2) mod N攻击原理如果e1和e2互质gcd(e1, e2) 1那么根据扩展欧几里得算法我们可以找到两个整数s和t使得e1*s e2*t 1。注意s或t可能是负数。假设s为负数我们可以计算c1^(-s)在模N下的逆元。最终我们可以恢复明文m ≡ (c1^s * c2^t) mod N这个攻击的精妙之处在于它不需要分解N也不需要知道私钥仅凭两组公钥和密文就能还原消息。2.4 已知私钥d的部分位或相关信息有些题目会玩“泄露”的游戏。比如不小心泄露了私钥d的一部分比特或者泄露了p或q的高位或低位。这类题目需要利用Coppersmith攻击。Coppersmith定理是密码学中一个强大的工具它告诉我们如果知道一个模多项式在模N下的根的一部分那么在多项式次数和已知比特数满足一定条件时可以在多项式时间内求出完整的根。实战举例题目给了N和e同时提示“私钥d的512位中最低的200位泄露了是0x1234...”。我们可以利用泄露的d低位构造一个关于未知高位和已知低位的方程然后使用Coppersmith方法通常通过SageMath实现来求解完整的d。这类题目对数学要求稍高但SageMath已经封装好了相关函数如small_roots()使用起来并不复杂。2.5 选择密文攻击CCA的简化版——签名伪造在更进阶的BabyRSA题中可能会模拟一个签名场景给你一个“签名” oracle你可以提交任何消息除目标消息外服务器会用私钥对其进行签名即解密操作。你的任务是伪造对目标消息的签名。这本质上是利用RSA的同态性(m1 * m2)^d ≡ m1^d * m2^d mod N。通过巧妙构造提交给oracle的消息可以间接获得目标消息的签名。这类题目考察的是对RSA算法代数结构的深入理解。3. 手把手实战构建你自己的BabyRSA解题工具包看懂了原理我们就要动手了。单纯使用别人写好的脚本比如开头的那个RSA-Decoder.py虽然快但不利于真正理解。我建议你跟着我用Python从头搭建一个包含常见攻击方法的工具箱。我们将主要依赖gmpy2用于高精度大数运算和pycryptodome用于标准的RSA操作和格式解析这两个库。3.1 环境准备与基础函数首先安装必要的库pip install gmpy2 pycryptodome然后我们创建一个babyrsa_toolkit.py文件写入一些基础函数import gmpy2 from gmpy2 import mpz import binascii from Crypto.Util.number import long_to_bytes, bytes_to_long, inverse def bytes_to_int(b): 将字节串转换为大整数 return bytes_to_long(b) def int_to_bytes(i): 将大整数转换为字节串自动处理前导零 return long_to_bytes(i) def modinv(a, m): 计算a在模m下的逆元使用gmpy2加速 return int(gmpy2.invert(mpz(a), mpz(m))) def is_prime(n, k10): 使用gmpy2的Miller-Rabin素性测试 return gmpy2.is_prime(mpz(n), k)这些函数构成了我们所有操作的基础。gmpy2的mpz类型可以处理任意大的整数并且运算速度远快于Python原生整数。3.2 攻击实现一小模数N分解当N很小时我们可以尝试直接分解。这里我演示两种方式对于极小的N 100位用sympy对于稍大的N可以调用系统命令使用yafu。import subprocess import tempfile import os def factorize_small_n(n): 分解小整数N适用于几十位的N try: import sympy factors sympy.factorint(n) # 假设是RSA的p*q这里应该只有两个质因子 if len(factors) 2 and all(exp 1 for exp in factors.values()): p, q list(factors.keys()) return int(p), int(q) else: raise ValueError(N does not factor into two distinct primes.) except ImportError: print(sympy not installed. Trying alternative method...) # 可以尝试简单的试除法仅用于演示效率极低 i 2 while i * i n: if n % i 0: return i, n // i i 1 if i 2 else 2 # 跳过偶数 return None def factorize_with_yafu(n, yafu_path./yafu): 通过yafu分解较大的N需要预先安装yafu with tempfile.NamedTemporaryFile(modew, deleteFalse, suffix.txt) as f: f.write(ffactor({n})) input_file f.name try: # 运行yafu注意路径可能需要调整 cmd [yafu_path, factor, f{input_file}] result subprocess.run(cmd, capture_outputTrue, textTrue, timeout30) output result.stdout # 解析yafu输出寻找P和Q lines output.split(\n) p q None for line in lines: if line.startswith(P ): p int(line.split()[1].strip()) elif line.startswith(Q ): q int(line.split()[1].strip()) elif in line and * not in line: # 简单结果行如 1234567 127 * 9721 parts line.split() if len(parts) 2: factors parts[1].split(*) if len(factors) 2: p, q int(factors[0].strip()), int(factors[1].strip()) if p and q: return p, q else: print(Yafu output could not be parsed.) print(output) return None except FileNotFoundError: print(fYafu not found at {yafu_path}. Please install yafu or specify correct path.) return None except subprocess.TimeoutExpired: print(Yafu factorization timed out.) return None finally: os.unlink(input_file) def rsa_decrypt_from_factors(n, e, c, p, q): 已知p, q, e, c解密得到明文m phi (p - 1) * (q - 1) d modinv(e, phi) m pow(c, d, n) return m实操心得在CTF比赛中如果题目给的N无法用本地工具快速分解第一个反应应该是去factordb.com这个网站查一下。这个网站收录了海量已知的整数分解结果很多出题人为了省事会直接使用该数据库里已有的合数作为N。用脚本自动查询factordb也是一个常见的技巧。3.3 攻击实现二低加密指数攻击e3当e很小且明文m也不大时直接开方。def low_encryption_exponent_attack(n, e, c): 低加密指数攻击例如e3且 m^e n # 尝试在整数域内直接开e次方 root, exact gmpy2.iroot(mpz(c), e) if exact: return int(root) else: # 如果开方不精确说明 m^e n模运算生效了此攻击无效 print(fFailed: c^{1/e} is not an exact integer. m^e may be n.) return None # 示例假设e3, c 27, 显然明文m3 # m low_encryption_exponent_attack(n999999, e3, c27) # 会返回3注意事项这种攻击成立的条件非常苛刻m^e N。在现实中消息m在加密前会进行填充如PKCS#1 v1.5或OAEP填充后的消息会变得很大使得这个条件几乎不可能满足。但CTF题中为了考察这个知识点出题人往往会故意不填充或者使用极小的m。3.4 攻击实现三共模攻击这是我最喜欢的攻击之一优雅且实用。def common_modulus_attack(n, e1, c1, e2, c2): 共模攻击已知同一明文m用(N, e1)和(N, e2)加密的密文c1, c2 # 使用扩展欧几里得算法求系数s, t使得 e1*s e2*t gcd(e1, e2) # 因为通常e1和e2互质所以gcd1 gcd, s, t gmpy2.gcdext(mpz(e1), mpz(e2)) s, t int(s), int(t) if gcd ! 1: raise ValueError(e1 and e2 are not coprime, common modulus attack may not work.) # 如果s为负数需要计算c1的模逆元 if s 0: c1_inv modinv(c1, n) m (pow(c1_inv, -s, n) * pow(c2, t, n)) % n elif t 0: c2_inv modinv(c2, n) m (pow(c1, s, n) * pow(c2_inv, -t, n)) % n else: m (pow(c1, s, n) * pow(c2, t, n)) % n return m原理回顾这个实现完全对应了之前的数学推导。gmpy2.gcdext函数一次性返回最大公约数和贝祖系数s, t。计算时一定要注意系数的正负负数次方意味着需要先计算模逆元。3.5 攻击实现四Wiener攻击小私钥d攻击当私钥d很小时Wiener攻击可以通过连分数展开公钥e/N来逼近私钥d。实现起来稍复杂但算法是固定的。def continued_fraction(e, n): 计算e/n的连分数展开 cf [] while n: q e // n cf.append(q) e, n n, e - q * n return cf def convergents(cf): 根据连分数展开计算收敛子 convs [] for i in range(len(cf)): if i 0: h, k cf[0], 1 elif i 1: h, k cf[1]*cf[0] 1, cf[1] else: h cf[i]*convs[i-1][0] convs[i-2][0] k cf[i]*convs[i-1][1] convs[i-2][1] convs.append((h, k)) return convs def wiener_attack(e, n): Wiener攻击尝试从e和n中恢复小私钥d cf continued_fraction(e, n) convs convergents(cf) for k, d in convs: if k 0: continue # 检查ed - 1是否能被k整除 if (e * d - 1) % k ! 0: continue phi (e * d - 1) // k # 解方程 x^2 - (n - phi 1)x n 0根应为p和q b n - phi 1 discriminant b*b - 4*n if discriminant 0: continue sqrt_disc, is_square gmpy2.iroot(mpz(discriminant), 2) if not is_square: continue sqrt_disc int(sqrt_disc) p (b sqrt_disc) // 2 q (b - sqrt_disc) // 2 if p * q n: return d, p, q return None使用技巧Wiener攻击成立的条件是d (1/3) * N^(1/4)。在CTF题目中如果看到公钥指数e特别大比如和N一个数量级就要高度怀疑是Wiener攻击或它的变种Boneh-Durfee攻击适用于d稍大的情况。这个脚本能自动遍历连分数收敛子并验证是否找到了正确的d。4. 综合实战解剖一道经典的BabyRSA CTF题让我们把上面的工具组合起来模拟解决一道虚构但非常典型的CTF题目。题目描述如下我们截获了一段用RSA加密的消息。已知公钥 (N, e) 和密文 c。 N 1522605027922533360535618378132637429718068114961380688657908494580122963258952897654000350692006139 e 65537 c 126028558760741438230925566962334702896791270808414391828894437291120207835997354509410869568173448979784329516392078311028442458946906210498176026685581176779209904039179175088984829699783861789249260322822491502790157863487861171337660785254139478229397872969136220001367017765809130698515063339265165085655此外我们还从另一个信道获得了用相同N但不同e加密的同一明文的密文e2 10001 c2 1022080150954344337686329871900977554684843055400924271757265898185924210581391133206669925796972917我们的任务是解密出原始消息。4.1 第一步观察与策略选择首先我们拿到N先看看它有多大N 1522605027922533360535618378132637429718068114961380688657908494580122963258952897654000350692006139 print(fN的位数: {len(str(N))}) # 输出: N的位数: 97N只有97位这非常小我们的第一反应应该是尝试分解N。同时题目给了两组密文但模数N相同公钥指数e不同。这强烈暗示了共模攻击的可能性。我们可以双管齐下。4.2 第二步尝试分解N我们用之前写的factorize_small_n试试需要安装sympyp, q factorize_small_n(N) print(fp {p}) print(fq {q}) # 输出: # p 37975227936943673922808872755445627854565536638199 # q 40094690950920881030683735292761468389214899724061成功了N被成功分解。现在我们可以用常规RSA解密了。4.3 第三步常规解密已知p, qfrom Crypto.Util.number import long_to_bytes def decrypt_rsa(n, e, c, p, q): phi (p-1)*(q-1) d modinv(e, phi) m pow(c, d, n) return m m1 decrypt_rsa(N, 65537, c, p, q) print(f解密结果 (方法一): {long_to_bytes(m1)})运行后我们得到了可读的明文。4.4 第四步验证共模攻击虽然我们已经解出来了但为了演示共模攻击我们也用第二组密文试试。m2 common_modulus_attack(N, 65537, c, 10001, c2) print(f解密结果 (共模攻击): {long_to_bytes(m2)})你会发现m1和m2的结果是一样的。这验证了我们的攻击是有效的。在实际比赛中如果N无法分解共模攻击就是唯一的出路。4.5 第五步结果与反思这道题完美地结合了两种最基础的BabyRSA攻击小N分解和共模攻击。出题人的意图很明显如果你发现N很小就去分解如果你发现有两组密文共用模数就用共模攻击。两者都能通向终点。踩坑记录在实际操作中我曾遇到过因为gmpy2数值类型转换问题导致计算错误的情况。gmpy2.mpz和Python的int在混合运算时有时会出问题。我的经验是在调用pow函数进行模幂运算时确保底数和指数都是Python的int类型而模数可以是int或mpz。或者全程使用gmpy2.powmod函数它接受mpz参数效率更高也更稳定。5. 进阶挑战与工具链整合当你熟练掌握了上述基础攻击后CTF中的BabyRSA题目会变得更加“狡猾”。它们可能会将多种弱点组合或者需要一些额外的步骤。5.1 从PEM或DER格式中提取参数真实的RSA公钥通常以PEM格式-----BEGIN PUBLIC KEY-----或DER编码给出。我们需要从中提取出N和e。pycryptodome库的Crypto.PublicKey.RSA模块可以轻松处理。from Crypto.PublicKey import RSA def extract_key_from_pem(pem_data): 从PEM格式的公钥中提取N和e key RSA.import_key(pem_data) return key.n, key.e # 示例 pem -----BEGIN PUBLIC KEY----- MIGfMA0GCSqGSIb3DQEBAQUAA4GNADCBiQKBgQC1ASz6...... -----END PUBLIC KEY----- n, e extract_key_from_pem(pem)5.2 处理十六进制、Base64编码的数据CTF题目中N、e、c常常以十六进制或Base64字符串的形式给出。我们需要熟练转换。import base64 def parse_rsa_params_from_hex(hex_n, hex_e, hex_c): n int(hex_n, 16) e int(hex_e, 16) c int(hex_c, 16) return n, e, c def parse_rsa_params_from_base64(b64_n, b64_e, b64_c): n bytes_to_int(base64.b64decode(b64_n)) e bytes_to_int(base64.b64decode(b64_e)) c bytes_to_int(base64.b64decode(b64_c)) return n, e, c5.3 使用SageMath应对Coppersmith等高级攻击对于涉及部分密钥泄露、已知明文高位等复杂问题Python原生库可能力不从心。这时就需要祭出神器——SageMath。它是一个基于Python的数学软件系统集成了大量数论和密码学算法。你可以在本地安装Sage或者使用在线的CoCalc平台。一个典型的Coppersmith攻击场景已知p的高位在Sage中可能这样写# 假设在SageMath环境中运行 n 123456789... # 已知模数N p_high 0x12340000... # 已知p的高位比特总位数约为p的一半 # 构造多项式 f(x) p_high x 在模p下f(x) 0 有一个小根x0即p的低位未知部分 PR.x PolynomialRing(Zmod(n)) f p_high x # 寻找小根 roots f.small_roots(X2^p_low_bit_length, beta0.5) # X是根的上界beta通常取0.5 if roots: p p_high int(roots[0]) if n % p 0: q n // p print(fFound p: {p})经验之谈在CTF比赛中如果题目提示了“泄露”、“部分”、“高位”、“低位”这些词并且常规攻击无效立刻想到Coppersmith。花时间学习Sage的基本用法和small_roots函数绝对是值得的投资。5.4 构建自动化解题流水线对于高频参赛者可以构建一个自动化的解题脚本。思路是给定一组参数脚本按顺序尝试各种攻击。检查N大小尝试查询factordb或本地分解。如果有多组(N, e, c)尝试共模攻击。检查e是否很小如3尝试低加密指数攻击。检查e是否很大尝试Wiener攻击。尝试从文本中提取可能泄露的p、q、d的信息片段。将所有尝试结果明文转换为字节并尝试用常见编码UTF-8解码搜索flag格式如flag{,CTF{。这种“暴力枚举”式的解题流程在面对简单的BabyRSA时往往能一键出结果。6. 从解题到出题深入理解RSA安全性的边界玩转了各种攻击我们不妨换个角度如果让你出一道BabyRSA题你会怎么设计这个过程能让你对RSA的理解更深一层。出题思路一隐藏的公约数。给出多个RSA公钥它们的N不同但其中某两个N有一个不为人知的巨大公约数gcd(N1, N2) 1。一旦发现这个公约数就能立刻分解这两个N。解题的关键是批量计算所有N两两之间的gcd。出题思路二错误的参数生成。使用不安全的素数生成方法比如p和q过于接近|p-q|很小那么可以通过费马分解法或直接对N开平方根附近进行搜索来分解。或者φ(N)与N有公因子导致私钥d无法计算。出题思路三侧信道与错误注入。这不是纯数学攻击而是模拟物理攻击。题目可能给出一个在执行RSA解密时发生故障如计算错误的服务器根据错误的输出结果来推断密钥信息。这需要了解Bleichenbacher攻击或Fault Attack的基本概念。安全启示所有这些BabyRSA攻击在现实世界的RSA应用中都是可以通过遵循最佳实践来避免的使用足够长的密钥目前推荐2048位以上。使用安全的随机数生成器生成大素数p和q。使用标准的公钥指数e65537。对消息进行标准的、随机化的填充如OAEP。绝不重复使用模数N。保护私钥的每一位防止任何形式的泄露。CTF中的BabyRSA就像武术中的套路练习它把现实中的安全威胁放大、简化让我们在安全的环境中看清攻击的原理。当你下次再看到“BabyRSA”时希望你的感觉不再是迷茫而是跃跃欲试的兴奋因为你已经拥有了拆解它的全套工具和思维框架。记住密码学的乐趣一半在于构建坚不可摧的体系另一半则在于寻找那细微裂缝时闪现的智慧火花。
CTF密码学入门：BabyRSA常见攻击模式与实战脚本解析
1. 项目概述BabyRSA是什么以及它为何在CTF圈子里火了如果你玩过网络安全竞赛CTF尤其是其中的密码学Crypto题目那你大概率见过“BabyRSA”这个名字。它不是一个具体的工具而是一类题目的统称特指那些使用RSA加密算法但参数设置存在明显“弱点”或“瑕疵”的挑战。这类题目通常作为密码学方向的入门题旨在引导选手理解RSA的基本原理并学会利用其实现上的不严谨来破解加密。我接触过不少刚入门的CTF选手他们往往对RSA望而生畏觉得涉及大数分解、模运算门槛太高。但BabyRSA恰恰是打破这种恐惧的绝佳入口——它把复杂的密码学原理简化成了一个可以“手撕”或者用简单脚本就能解决的谜题。简单来说RSA的安全性建立在“大整数分解难题”之上给你一个巨大的合数比如两个数百位质数相乘的结果在有限时间内你几乎无法将它分解回原来的两个质数。但BabyRSA反其道而行之它给出的“大整数”一点也不大可能只有几十位甚至十几位或者它虽然数字大但暴露了太多关键信息比如公钥指数e极小、私钥d泄露、或者两个密文共用了一个模数。这些“婴儿级”的漏洞让看似坚固的RSA堡垒出现了裂缝。而网络上流传的诸如mrdebator/BabyRSA这类Python脚本就是针对这些特定裂缝打造的“开锁工具包”。它们封装了针对常见弱点的攻击算法让解题者无需从零开始推导数学公式只需填入题目给出的参数就能快速得到flag。这大大降低了参与门槛也使得BabyRSA成为CTF密码学中最受欢迎、也最出名的题型之一。所以当你看到“BabyRSA”这个标题时它背后指向的不仅仅是一个GitHub仓库更是一个庞大的实战场景CTF竞赛、密码学教育、以及对于RSA算法核心脆弱性的探索。接下来我会从一个CTF老兵的角度带你彻底拆解BabyRSA的常见套路、攻击原理并手把手教你如何复现和编写自己的解题脚本。你会发现破解它需要的不是高深的数学而是清晰的思路和对细节的把握。2. BabyRSA的常见“弱点”模式与攻击原理全解析为什么叫“Baby”就是因为它的设置不够“成人”留下了诸多可乘之机。这些弱点模式经过多年CTF出题人和解题者的博弈已经形成了相当固定的几个类别。理解这些模式就等于拿到了解题的路线图。2.1 模数N过小直接暴力分解这是最经典、最“Baby”的情况。RSA的模数N p * q其中p和q是两个大质数。如果N本身很小比如小于256位那么在现代计算机上利用高效的分解算法如Pollards rho、二次筛法甚至在线数据库如factordb.com可以在极短的时间内分解出p和q。攻击原理一旦分解出p和qRSA的整个防线就崩溃了。我们可以计算出欧拉函数φ(N) (p-1)*(q-1)然后根据公钥指数e计算出私钥d即e关于φ(N)的模逆元d ≡ e^(-1) mod φ(N)。有了私钥d解密就是一次模幂运算明文 m ≡ c^d mod N。实操中的关键点判断N是否“小”是一个经验值。十年前512位的N被认为是不安全的如今对于CTF题目768位以下的N通常都可以尝试用yafu或sage等工具在个人电脑上分解。而对于真正的“Baby”题N可能只有几十位用Python的sympy库里的factorint函数一秒就能出结果。注意在真实世界的RSA应用中N的长度至少应为2048位3072位或4096位正成为新的标准。CTF中的小N纯粹是为了教学和竞技。2.2 公钥指数e过小或过大导致特定攻击公钥指数e通常取655370x10001这是一个在安全性和计算效率之间取得平衡的值。但当e偏离这个常规值时就可能引发问题。情况一e过小比如e3且明文m也很小。如果m^e N那么加密过程c ≡ m^e mod N中的模运算实际上没有起作用因为m^e根本就没超过N。此时密文c就是明文m的e次方直接对c开e次方根比如在整数域内开立方根就能得到m。情况二e过大导致私钥d过小。如果私钥d很小比如小于N的0.292次方那么可以使用Wiener攻击或Boneh-Durfee攻击通过连分数逼近的方法从公钥对 (N, e) 中恢复出私钥d。这在CTF题中也很常见题目可能会给一个异常大的e暗示你要往这方面想。2.3 共模攻击Common Modulus Attack这是非常经典的一种场景。题目给出了两段不同的密文c1和c2它们是用相同的模数N但不同的公钥指数e1和e2加密同一段明文m得到的。即c1 ≡ m^(e1) mod Nc2 ≡ m^(e2) mod N攻击原理如果e1和e2互质gcd(e1, e2) 1那么根据扩展欧几里得算法我们可以找到两个整数s和t使得e1*s e2*t 1。注意s或t可能是负数。假设s为负数我们可以计算c1^(-s)在模N下的逆元。最终我们可以恢复明文m ≡ (c1^s * c2^t) mod N这个攻击的精妙之处在于它不需要分解N也不需要知道私钥仅凭两组公钥和密文就能还原消息。2.4 已知私钥d的部分位或相关信息有些题目会玩“泄露”的游戏。比如不小心泄露了私钥d的一部分比特或者泄露了p或q的高位或低位。这类题目需要利用Coppersmith攻击。Coppersmith定理是密码学中一个强大的工具它告诉我们如果知道一个模多项式在模N下的根的一部分那么在多项式次数和已知比特数满足一定条件时可以在多项式时间内求出完整的根。实战举例题目给了N和e同时提示“私钥d的512位中最低的200位泄露了是0x1234...”。我们可以利用泄露的d低位构造一个关于未知高位和已知低位的方程然后使用Coppersmith方法通常通过SageMath实现来求解完整的d。这类题目对数学要求稍高但SageMath已经封装好了相关函数如small_roots()使用起来并不复杂。2.5 选择密文攻击CCA的简化版——签名伪造在更进阶的BabyRSA题中可能会模拟一个签名场景给你一个“签名” oracle你可以提交任何消息除目标消息外服务器会用私钥对其进行签名即解密操作。你的任务是伪造对目标消息的签名。这本质上是利用RSA的同态性(m1 * m2)^d ≡ m1^d * m2^d mod N。通过巧妙构造提交给oracle的消息可以间接获得目标消息的签名。这类题目考察的是对RSA算法代数结构的深入理解。3. 手把手实战构建你自己的BabyRSA解题工具包看懂了原理我们就要动手了。单纯使用别人写好的脚本比如开头的那个RSA-Decoder.py虽然快但不利于真正理解。我建议你跟着我用Python从头搭建一个包含常见攻击方法的工具箱。我们将主要依赖gmpy2用于高精度大数运算和pycryptodome用于标准的RSA操作和格式解析这两个库。3.1 环境准备与基础函数首先安装必要的库pip install gmpy2 pycryptodome然后我们创建一个babyrsa_toolkit.py文件写入一些基础函数import gmpy2 from gmpy2 import mpz import binascii from Crypto.Util.number import long_to_bytes, bytes_to_long, inverse def bytes_to_int(b): 将字节串转换为大整数 return bytes_to_long(b) def int_to_bytes(i): 将大整数转换为字节串自动处理前导零 return long_to_bytes(i) def modinv(a, m): 计算a在模m下的逆元使用gmpy2加速 return int(gmpy2.invert(mpz(a), mpz(m))) def is_prime(n, k10): 使用gmpy2的Miller-Rabin素性测试 return gmpy2.is_prime(mpz(n), k)这些函数构成了我们所有操作的基础。gmpy2的mpz类型可以处理任意大的整数并且运算速度远快于Python原生整数。3.2 攻击实现一小模数N分解当N很小时我们可以尝试直接分解。这里我演示两种方式对于极小的N 100位用sympy对于稍大的N可以调用系统命令使用yafu。import subprocess import tempfile import os def factorize_small_n(n): 分解小整数N适用于几十位的N try: import sympy factors sympy.factorint(n) # 假设是RSA的p*q这里应该只有两个质因子 if len(factors) 2 and all(exp 1 for exp in factors.values()): p, q list(factors.keys()) return int(p), int(q) else: raise ValueError(N does not factor into two distinct primes.) except ImportError: print(sympy not installed. Trying alternative method...) # 可以尝试简单的试除法仅用于演示效率极低 i 2 while i * i n: if n % i 0: return i, n // i i 1 if i 2 else 2 # 跳过偶数 return None def factorize_with_yafu(n, yafu_path./yafu): 通过yafu分解较大的N需要预先安装yafu with tempfile.NamedTemporaryFile(modew, deleteFalse, suffix.txt) as f: f.write(ffactor({n})) input_file f.name try: # 运行yafu注意路径可能需要调整 cmd [yafu_path, factor, f{input_file}] result subprocess.run(cmd, capture_outputTrue, textTrue, timeout30) output result.stdout # 解析yafu输出寻找P和Q lines output.split(\n) p q None for line in lines: if line.startswith(P ): p int(line.split()[1].strip()) elif line.startswith(Q ): q int(line.split()[1].strip()) elif in line and * not in line: # 简单结果行如 1234567 127 * 9721 parts line.split() if len(parts) 2: factors parts[1].split(*) if len(factors) 2: p, q int(factors[0].strip()), int(factors[1].strip()) if p and q: return p, q else: print(Yafu output could not be parsed.) print(output) return None except FileNotFoundError: print(fYafu not found at {yafu_path}. Please install yafu or specify correct path.) return None except subprocess.TimeoutExpired: print(Yafu factorization timed out.) return None finally: os.unlink(input_file) def rsa_decrypt_from_factors(n, e, c, p, q): 已知p, q, e, c解密得到明文m phi (p - 1) * (q - 1) d modinv(e, phi) m pow(c, d, n) return m实操心得在CTF比赛中如果题目给的N无法用本地工具快速分解第一个反应应该是去factordb.com这个网站查一下。这个网站收录了海量已知的整数分解结果很多出题人为了省事会直接使用该数据库里已有的合数作为N。用脚本自动查询factordb也是一个常见的技巧。3.3 攻击实现二低加密指数攻击e3当e很小且明文m也不大时直接开方。def low_encryption_exponent_attack(n, e, c): 低加密指数攻击例如e3且 m^e n # 尝试在整数域内直接开e次方 root, exact gmpy2.iroot(mpz(c), e) if exact: return int(root) else: # 如果开方不精确说明 m^e n模运算生效了此攻击无效 print(fFailed: c^{1/e} is not an exact integer. m^e may be n.) return None # 示例假设e3, c 27, 显然明文m3 # m low_encryption_exponent_attack(n999999, e3, c27) # 会返回3注意事项这种攻击成立的条件非常苛刻m^e N。在现实中消息m在加密前会进行填充如PKCS#1 v1.5或OAEP填充后的消息会变得很大使得这个条件几乎不可能满足。但CTF题中为了考察这个知识点出题人往往会故意不填充或者使用极小的m。3.4 攻击实现三共模攻击这是我最喜欢的攻击之一优雅且实用。def common_modulus_attack(n, e1, c1, e2, c2): 共模攻击已知同一明文m用(N, e1)和(N, e2)加密的密文c1, c2 # 使用扩展欧几里得算法求系数s, t使得 e1*s e2*t gcd(e1, e2) # 因为通常e1和e2互质所以gcd1 gcd, s, t gmpy2.gcdext(mpz(e1), mpz(e2)) s, t int(s), int(t) if gcd ! 1: raise ValueError(e1 and e2 are not coprime, common modulus attack may not work.) # 如果s为负数需要计算c1的模逆元 if s 0: c1_inv modinv(c1, n) m (pow(c1_inv, -s, n) * pow(c2, t, n)) % n elif t 0: c2_inv modinv(c2, n) m (pow(c1, s, n) * pow(c2_inv, -t, n)) % n else: m (pow(c1, s, n) * pow(c2, t, n)) % n return m原理回顾这个实现完全对应了之前的数学推导。gmpy2.gcdext函数一次性返回最大公约数和贝祖系数s, t。计算时一定要注意系数的正负负数次方意味着需要先计算模逆元。3.5 攻击实现四Wiener攻击小私钥d攻击当私钥d很小时Wiener攻击可以通过连分数展开公钥e/N来逼近私钥d。实现起来稍复杂但算法是固定的。def continued_fraction(e, n): 计算e/n的连分数展开 cf [] while n: q e // n cf.append(q) e, n n, e - q * n return cf def convergents(cf): 根据连分数展开计算收敛子 convs [] for i in range(len(cf)): if i 0: h, k cf[0], 1 elif i 1: h, k cf[1]*cf[0] 1, cf[1] else: h cf[i]*convs[i-1][0] convs[i-2][0] k cf[i]*convs[i-1][1] convs[i-2][1] convs.append((h, k)) return convs def wiener_attack(e, n): Wiener攻击尝试从e和n中恢复小私钥d cf continued_fraction(e, n) convs convergents(cf) for k, d in convs: if k 0: continue # 检查ed - 1是否能被k整除 if (e * d - 1) % k ! 0: continue phi (e * d - 1) // k # 解方程 x^2 - (n - phi 1)x n 0根应为p和q b n - phi 1 discriminant b*b - 4*n if discriminant 0: continue sqrt_disc, is_square gmpy2.iroot(mpz(discriminant), 2) if not is_square: continue sqrt_disc int(sqrt_disc) p (b sqrt_disc) // 2 q (b - sqrt_disc) // 2 if p * q n: return d, p, q return None使用技巧Wiener攻击成立的条件是d (1/3) * N^(1/4)。在CTF题目中如果看到公钥指数e特别大比如和N一个数量级就要高度怀疑是Wiener攻击或它的变种Boneh-Durfee攻击适用于d稍大的情况。这个脚本能自动遍历连分数收敛子并验证是否找到了正确的d。4. 综合实战解剖一道经典的BabyRSA CTF题让我们把上面的工具组合起来模拟解决一道虚构但非常典型的CTF题目。题目描述如下我们截获了一段用RSA加密的消息。已知公钥 (N, e) 和密文 c。 N 1522605027922533360535618378132637429718068114961380688657908494580122963258952897654000350692006139 e 65537 c 126028558760741438230925566962334702896791270808414391828894437291120207835997354509410869568173448979784329516392078311028442458946906210498176026685581176779209904039179175088984829699783861789249260322822491502790157863487861171337660785254139478229397872969136220001367017765809130698515063339265165085655此外我们还从另一个信道获得了用相同N但不同e加密的同一明文的密文e2 10001 c2 1022080150954344337686329871900977554684843055400924271757265898185924210581391133206669925796972917我们的任务是解密出原始消息。4.1 第一步观察与策略选择首先我们拿到N先看看它有多大N 1522605027922533360535618378132637429718068114961380688657908494580122963258952897654000350692006139 print(fN的位数: {len(str(N))}) # 输出: N的位数: 97N只有97位这非常小我们的第一反应应该是尝试分解N。同时题目给了两组密文但模数N相同公钥指数e不同。这强烈暗示了共模攻击的可能性。我们可以双管齐下。4.2 第二步尝试分解N我们用之前写的factorize_small_n试试需要安装sympyp, q factorize_small_n(N) print(fp {p}) print(fq {q}) # 输出: # p 37975227936943673922808872755445627854565536638199 # q 40094690950920881030683735292761468389214899724061成功了N被成功分解。现在我们可以用常规RSA解密了。4.3 第三步常规解密已知p, qfrom Crypto.Util.number import long_to_bytes def decrypt_rsa(n, e, c, p, q): phi (p-1)*(q-1) d modinv(e, phi) m pow(c, d, n) return m m1 decrypt_rsa(N, 65537, c, p, q) print(f解密结果 (方法一): {long_to_bytes(m1)})运行后我们得到了可读的明文。4.4 第四步验证共模攻击虽然我们已经解出来了但为了演示共模攻击我们也用第二组密文试试。m2 common_modulus_attack(N, 65537, c, 10001, c2) print(f解密结果 (共模攻击): {long_to_bytes(m2)})你会发现m1和m2的结果是一样的。这验证了我们的攻击是有效的。在实际比赛中如果N无法分解共模攻击就是唯一的出路。4.5 第五步结果与反思这道题完美地结合了两种最基础的BabyRSA攻击小N分解和共模攻击。出题人的意图很明显如果你发现N很小就去分解如果你发现有两组密文共用模数就用共模攻击。两者都能通向终点。踩坑记录在实际操作中我曾遇到过因为gmpy2数值类型转换问题导致计算错误的情况。gmpy2.mpz和Python的int在混合运算时有时会出问题。我的经验是在调用pow函数进行模幂运算时确保底数和指数都是Python的int类型而模数可以是int或mpz。或者全程使用gmpy2.powmod函数它接受mpz参数效率更高也更稳定。5. 进阶挑战与工具链整合当你熟练掌握了上述基础攻击后CTF中的BabyRSA题目会变得更加“狡猾”。它们可能会将多种弱点组合或者需要一些额外的步骤。5.1 从PEM或DER格式中提取参数真实的RSA公钥通常以PEM格式-----BEGIN PUBLIC KEY-----或DER编码给出。我们需要从中提取出N和e。pycryptodome库的Crypto.PublicKey.RSA模块可以轻松处理。from Crypto.PublicKey import RSA def extract_key_from_pem(pem_data): 从PEM格式的公钥中提取N和e key RSA.import_key(pem_data) return key.n, key.e # 示例 pem -----BEGIN PUBLIC KEY----- MIGfMA0GCSqGSIb3DQEBAQUAA4GNADCBiQKBgQC1ASz6...... -----END PUBLIC KEY----- n, e extract_key_from_pem(pem)5.2 处理十六进制、Base64编码的数据CTF题目中N、e、c常常以十六进制或Base64字符串的形式给出。我们需要熟练转换。import base64 def parse_rsa_params_from_hex(hex_n, hex_e, hex_c): n int(hex_n, 16) e int(hex_e, 16) c int(hex_c, 16) return n, e, c def parse_rsa_params_from_base64(b64_n, b64_e, b64_c): n bytes_to_int(base64.b64decode(b64_n)) e bytes_to_int(base64.b64decode(b64_e)) c bytes_to_int(base64.b64decode(b64_c)) return n, e, c5.3 使用SageMath应对Coppersmith等高级攻击对于涉及部分密钥泄露、已知明文高位等复杂问题Python原生库可能力不从心。这时就需要祭出神器——SageMath。它是一个基于Python的数学软件系统集成了大量数论和密码学算法。你可以在本地安装Sage或者使用在线的CoCalc平台。一个典型的Coppersmith攻击场景已知p的高位在Sage中可能这样写# 假设在SageMath环境中运行 n 123456789... # 已知模数N p_high 0x12340000... # 已知p的高位比特总位数约为p的一半 # 构造多项式 f(x) p_high x 在模p下f(x) 0 有一个小根x0即p的低位未知部分 PR.x PolynomialRing(Zmod(n)) f p_high x # 寻找小根 roots f.small_roots(X2^p_low_bit_length, beta0.5) # X是根的上界beta通常取0.5 if roots: p p_high int(roots[0]) if n % p 0: q n // p print(fFound p: {p})经验之谈在CTF比赛中如果题目提示了“泄露”、“部分”、“高位”、“低位”这些词并且常规攻击无效立刻想到Coppersmith。花时间学习Sage的基本用法和small_roots函数绝对是值得的投资。5.4 构建自动化解题流水线对于高频参赛者可以构建一个自动化的解题脚本。思路是给定一组参数脚本按顺序尝试各种攻击。检查N大小尝试查询factordb或本地分解。如果有多组(N, e, c)尝试共模攻击。检查e是否很小如3尝试低加密指数攻击。检查e是否很大尝试Wiener攻击。尝试从文本中提取可能泄露的p、q、d的信息片段。将所有尝试结果明文转换为字节并尝试用常见编码UTF-8解码搜索flag格式如flag{,CTF{。这种“暴力枚举”式的解题流程在面对简单的BabyRSA时往往能一键出结果。6. 从解题到出题深入理解RSA安全性的边界玩转了各种攻击我们不妨换个角度如果让你出一道BabyRSA题你会怎么设计这个过程能让你对RSA的理解更深一层。出题思路一隐藏的公约数。给出多个RSA公钥它们的N不同但其中某两个N有一个不为人知的巨大公约数gcd(N1, N2) 1。一旦发现这个公约数就能立刻分解这两个N。解题的关键是批量计算所有N两两之间的gcd。出题思路二错误的参数生成。使用不安全的素数生成方法比如p和q过于接近|p-q|很小那么可以通过费马分解法或直接对N开平方根附近进行搜索来分解。或者φ(N)与N有公因子导致私钥d无法计算。出题思路三侧信道与错误注入。这不是纯数学攻击而是模拟物理攻击。题目可能给出一个在执行RSA解密时发生故障如计算错误的服务器根据错误的输出结果来推断密钥信息。这需要了解Bleichenbacher攻击或Fault Attack的基本概念。安全启示所有这些BabyRSA攻击在现实世界的RSA应用中都是可以通过遵循最佳实践来避免的使用足够长的密钥目前推荐2048位以上。使用安全的随机数生成器生成大素数p和q。使用标准的公钥指数e65537。对消息进行标准的、随机化的填充如OAEP。绝不重复使用模数N。保护私钥的每一位防止任何形式的泄露。CTF中的BabyRSA就像武术中的套路练习它把现实中的安全威胁放大、简化让我们在安全的环境中看清攻击的原理。当你下次再看到“BabyRSA”时希望你的感觉不再是迷茫而是跃跃欲试的兴奋因为你已经拥有了拆解它的全套工具和思维框架。记住密码学的乐趣一半在于构建坚不可摧的体系另一半则在于寻找那细微裂缝时闪现的智慧火花。
