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位），那么在现代计算机上，利用高效的分解算法（如Pollard's rho、二次筛法）甚至在线数据库（如factordb.com），可以在极短的时间内分解出p和q。

攻击原理：一旦分解出p和q，RSA的整个防线就崩溃了。我们可以计算出欧拉函数φ(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通常取65537（0x10001），这是一个在安全性和计算效率之间取得平衡的值。但当e偏离这个常规值时，就可能引发问题。

情况一：e过小（比如e=3），且明文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, k=10): """使用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(mode='w', delete=False, suffix='.txt') as f: f.write(f"factor({n})") input_file = f.name try: # 运行yafu，注意路径可能需要调整 cmd = [yafu_path, "factor", f"@{input_file}"] result = subprocess.run(cmd, capture_output=True, text=True, timeout=30) 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(f"Yafu 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 攻击实现二：低加密指数攻击（e=3）

当e很小，且明文m也不大时，直接开方。

def low_encryption_exponent_attack(n, e, c): """低加密指数攻击，例如e=3，且 m^e < n""" # 尝试在整数域内直接开e次方 root, exact = gmpy2.iroot(mpz(c), e) if exact: return int(root) else: # 如果开方不精确，说明 m^e >= n，模运算生效了，此攻击无效 print(f"Failed: c^{1/e} is not an exact integer. m^e may be >= n.") return None # 示例：假设e=3, c = 27, 显然明文m=3 # m = low_encryption_exponent_attack(n=999999, e=3, c=27) # 会返回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互质，所以gcd=1 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(f"N的位数: {len(str(N))}") # 输出: N的位数: 97

N只有97位，这非常小！我们的第一反应应该是尝试分解N。同时，题目给了两组密文，但模数N相同，公钥指数e不同。这强烈暗示了共模攻击的可能性。我们可以双管齐下。

4.2 第二步：尝试分解N

我们用之前写的factorize_small_n试试（需要安装sympy）：

p, q = factorize_small_n(N) print(f"p = {p}") print(f"q = {q}") # 输出: # p = 37975227936943673922808872755445627854565536638199 # q = 40094690950920881030683735292761468389214899724061

成功了！N被成功分解。现在我们可以用常规RSA解密了。

4.3 第三步：常规解密（已知p, q）

from 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, c

5.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(X=2^p_low_bit_length, beta=0.5) # X是根的上界，beta通常取0.5 if roots: p = p_high + int(roots[0]) if n % p == 0: q = n // p print(f"Found 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。
使用标准的公钥指数e=65537。
对消息进行标准的、随机化的填充（如OAEP）。
绝不重复使用模数N。
保护私钥的每一位，防止任何形式的泄露。

CTF中的BabyRSA，就像武术中的套路练习，它把现实中的安全威胁放大、简化，让我们在安全的环境中看清攻击的原理。当你下次再看到“BabyRSA”时，希望你的感觉不再是迷茫，而是跃跃欲试的兴奋，因为你已经拥有了拆解它的全套工具和思维框架。记住，密码学的乐趣，一半在于构建坚不可摧的体系，另一半则在于寻找那细微裂缝时闪现的智慧火花。