1. 项目概述从“BabyRSA”说起如果你玩过CTFCapture The Flag网络安全竞赛或者对密码学感兴趣那么“RSA”这个名字你一定不陌生。它是现代密码学的基石之一广泛应用于数字签名、安全通信等领域。但“BabyRSA”这个名字听起来就亲切多了它通常指代那些使用了相对较小密钥参数比如素数小于20位的RSA加解密挑战。这类挑战在CTF的密码学入门题中非常常见是新手理解RSA核心原理、掌握基本攻击方法的绝佳练手场。我最初接触BabyRSA也是在一次CTF比赛中。面对一个看似复杂的加密文本和两个不大的数字n和e当时也是一头雾水。后来才明白这背后其实是一套精巧的数学逻辑。这个名为“BabyRSA”的项目就是一个用Python实现的、专门针对这类“小素数”RSA加解密的工具脚本。它的价值不在于实现一个工业级的RSA系统——那需要处理数百位甚至上千位的大素数而是聚焦于教学和解题帮你快速分解模数n、计算私钥d从而破解密文或者验证你对RSA流程的理解。简单来说这个项目能帮你做两件事一是作为学习工具亲手跑一遍RSA从密钥生成、加密到解密的全过程感受公钥密码学的魅力二是作为实战工具在CTF比赛中当你遇到一个n值不大、可以暴力分解的RSA题时它能帮你自动化完成从拿到n、e、c到算出明文m的整个流程。接下来我们就深入这个“婴儿级”但内涵丰富的RSA世界看看它到底怎么玩以及在实际操作中会遇到哪些坑。2. RSA核心原理快速回顾与“小素数”场景要玩转BabyRSA首先得清楚标准RSA是怎么工作的。别担心我们不用涉及太深的数论只抓住最核心的几条线。2.1 RSA加密解密的三步曲RSA的安全性建立在“大数分解难题”上给你一个很大的合数n它是两个大素数p和q的乘积想从n倒推出p和q极其困难。但对于BabyRSA这个“困难”被故意降低了因为p和q不够大。整个流程围绕几个核心参数展开选择两个素数p和q这是起点。计算n p * q这个n就是模数会公开。计算欧拉函数φ(n)φ(n) (p-1) * (q-1)。这个值必须保密。选择公钥指数e选择一个整数e满足1 e φ(n)且e与φ(n)互质最大公约数为1。通常e取65537因为它二进制下只有两个1计算效率高。(n, e)这对就是公钥。计算私钥指数dd是e关于模φ(n)的模逆元。即满足(d * e) % φ(n) 1。(n, d)这对就是私钥。加密对于明文m需要先转换成小于n的整数密文c (m ^ e) % n。解密用私钥还原明文m (c ^ d) % n。在CTF的BabyRSA题目里你通常拿到的就是公开的(n, e, c)目标是通过某种方法核心就是分解n得到p和q进而算出φ(n)和d最后解密c得到m。2.2 为什么“小素数”会成为突破口在真正的安全应用中n的长度通常在2048位约617位十进制数以上使得分解n在现有计算能力下不可行。但BabyRSA反其道而行之它使用的p和q可能只有几十位甚至十几位十进制数。这就带来了根本性的脆弱点暴力分解成为可能对于20位十进制数约66位二进制以内的n现代计算机可以在可接受的时间从几秒到几分钟内通过试除法、Pollard‘s rho算法等将其分解为p和q。一旦分解成功整个RSA体系就被攻破了。侧信道与特殊值攻击参数太小可能会意外落入一些不安全的取值区间。例如如果p和q过于接近可以通过费马分解法快速破解如果私钥d太小可能遭受维纳攻击Wiener‘s Attack。这些在标准RSA中需要警惕的攻击在BabyRSA场景下更容易被触发。因此BabyRSA项目的核心功能就是自动化执行这个“分解-计算-解密”的链条特别优化了对小n的处理速度。它把复杂的数论计算封装成简单的函数调用让使用者能聚焦于策略和逻辑而不是底层实现细节。3. BabyRSA工具实战安装、使用与核心代码解析理论清楚了我们上手操作。以GitHub上的mrdebator/BabyRSA项目为例我们来看看如何让这个工具跑起来并理解它内部是怎么工作的。3.1 环境准备与项目获取首先确保你的系统安装了Python3。打开终端Linux/macOS或命令提示符/PowerShellWindows执行以下命令检查python3 --version如果显示版本号如Python 3.8.10说明环境OK。接下来克隆项目仓库到本地git clone https://github.com/mrdebator/BabyRSA.git cd BabyRSA项目目录很简单核心文件就是RSA-Decoder.py和一份说明文档README.md。3.2 核心脚本RSA-Decoder.py拆解我们直接打开RSA-Decoder.py文件看看它的核心逻辑。一个典型的BabyRSA解题脚本通常会包含以下几个关键函数1. 模逆元计算Extended Euclidean Algorithm计算私钥d的核心是求模逆元。这通常使用扩展欧几里得算法。def egcd(a, b): 扩展欧几里得算法返回 (gcd, x, y) 使得 a*x b*y gcd(a, b) if a 0: return (b, 0, 1) else: g, y, x egcd(b % a, a) return (g, x - (b // a) * y, y) def modinv(e, phi): 计算 e 模 phi 的逆元 d即 (d * e) % phi 1 g, x, _ egcd(e, phi) if g ! 1: raise Exception(模逆元不存在e 和 phi 不互质) else: return x % phi注意这里有个关键检查if g ! 1。如果e和φ(n)的最大公约数不是1说明它们不互质此时模逆元d不存在。在正常的RSA密钥生成中我们选择的e必须与φ(n)互质。如果在解题时遇到这个错误首先要检查你计算的φ(n)是否正确或者题目是否设置了特殊的陷阱。2. 素数分解针对小n的简单实现对于很小的n脚本可能直接使用试除法。但对于稍大一点的比如几十位更高效的方法是集成sympy库的factorint函数或者实现Pollard‘s rho算法。# 方法一使用sympy库需要安装pip install sympy from sympy import factorint def factorize_n(n): 使用sympy分解n返回字典 {p: 次数, q: 次数} factors factorint(n) # 对于RSA我们期望n是两个素数的乘积 if len(factors) 2 and all(exp 1 for exp in factors.values()): p, q list(factors.keys()) return p, q else: raise ValueError(fn的分解结果不符合两个素数的预期: {factors}) # 方法二简单的试除法仅适用于极小的n效率低 def naive_factorize(n): i 2 while i * i n: if n % i 0: return i, n // i i 1 return None, None # 没找到说明n可能是素数或需要更强算法在实际的CTF解题中如果n真的非常小你甚至可以直接用在线分解网站如 factordb.com或本地工具如yafu来分解比用Python脚本暴力试除快得多。BabyRSA工具的价值在于将这个过程整合进一个连贯的流程。3. 主解密流程脚本的主体逻辑是一个清晰的管道输入n, e, c- 分解n得到p, q- 计算φ(n) (p-1)*(q-1)- 计算私钥d modinv(e, φ(n))- 解密m pow(c, d, n)- 将整数m转换为字节或字符串。def decrypt(n, e, c): 主解密函数 # 1. 分解n p, q factorize_n(n) # 使用上述某种分解方法 # 2. 计算φ(n) phi (p - 1) * (q - 1) # 3. 计算私钥d d modinv(e, phi) # 4. 解密得到整数明文m m pow(c, d, n) # 使用pow的模运算形式效率远高于 (c**d)%n # 5. 将整数m转换为字节假设明文是文本 # 需要知道编码方式常见的是long_to_bytes (PyCryptodome库) 或自己处理 try: from Crypto.Util.number import long_to_bytes plaintext long_to_bytes(m).decode(utf-8, errorsignore) except ImportError: # 备用方法将m转换为16进制字符串再尝试解码 hex_str hex(m)[2:] # 去掉0x前缀 if len(hex_str) % 2 ! 0: hex_str 0 hex_str plaintext bytes.fromhex(hex_str).decode(utf-8, errorsignore) return plaintext, d, p, q4. 交互式使用很多BabyRSA脚本会设计一个简单的交互界面让你输入已知参数。if __name__ __main__: print( BabyRSA 解密工具 ) try: n int(input(请输入模数 n: ).strip()) e int(input(请输入公钥指数 e (通常为65537): ).strip() or 65537) c int(input(请输入密文 c (整数形式): ).strip()) plaintext, d, p, q decrypt(n, e, c) print(f\n[] 分解结果:) print(f p {p}) print(f q {q}) print(f φ(n) (p-1)*(q-1) {(p-1)*(q-1)}) print(f[] 私钥指数 d {d}) print(f[] 解密后的明文 (整数) 是: {pow(c, d, n)}) print(f[] 转换为文本后可能是: {plaintext}) except ValueError as ve: print(f输入错误或计算异常: {ve}) except Exception as ex: print(f解密过程中发生错误: {ex})3.3 一个完整的实战示例假设我们在CTF题目中拿到以下数据n 3233 e 17 c 2790这是一个经典的、极小参数的RSA示例事实上n323361*53。我们来看看如何使用工具思路来解密。分解nfactorize_n(3233)会得到p61, q53。计算φ(n)φ (61-1)*(53-1) 60*52 3120。计算私钥d求解d * 17 ≡ 1 (mod 3120)。通过扩展欧几里得算法可以算出d 2753。解密计算m 2790 ^ 2753 mod 3233。这个计算量很大但Python的pow(c, d, n)函数利用模幂运算优化可以瞬间得出结果m 65。转换明文整数65对应的ASCII字符是‘A‘。所以密文2790解密后是字母A。通过这个例子你可以清晰地看到只要n能被分解无论e和c是什么整个加密堡垒就土崩瓦解了。BabyRSA工具就是把上述1-4步自动化。4. 超越简单分解BabyRSA常见变种与攻击手法在真实的CTF比赛中出题人不会总是给你一个能直接分解的n。他们会设置各种“障碍”让题目更有挑战性。掌握这些常见变种和对应的攻击手法才是玩转BabyRSA的关键。4.1 模数n共享Common Modulus Attack场景同一段明文m用相同的模数n但不同的公钥指数e1和e2加密得到两个密文c1和c2。即c1 m^e1 mod n,c2 m^e2 mod n。攻击原理如果e1和e2互质即gcd(e1, e2) 1那么根据扩展欧几里得算法存在整数s和t使得s*e1 t*e2 1。于是我们可以计算(c1^s * c2^t) mod n m^(s*e1 t*e2) mod n m^1 mod n m。 这样我们无需分解n也无需私钥d就直接恢复了明文。实操要点关键条件是gcd(e1, e2) 1。计算s和t时注意s或t可能为负数。如果s为负我们需要先计算c1模n的逆元因为c1^s mod n在s为负时没有定义但(c1^{-1})^{-s} mod n是有效的。from math import gcd from Crypto.Util.number import inverse def common_modulus_attack(c1, c2, e1, e2, n): if gcd(e1, e2) ! 1: raise ValueError(e1 和 e2 必须互质) # 使用扩展欧几里得求系数 _, s, t egcd(e1, e2) # 处理负数指数 if s 0: c1 inverse(c1, n) s -s if t 0: c2 inverse(c2, n) t -t # 计算明文 m (pow(c1, s, n) * pow(c2, t, n)) % n return m4.2 小公钥指数e攻击Low Public Exponent Attack场景公钥指数e非常小比如e3并且明文m也很小使得m^e n。攻击原理如果m^e n那么加密运算c m^e mod n实际上就等于m^e因为模n没有起作用。那么直接对密文c开e次方根就能得到明文mm c^(1/e)。实操要点判断条件c是否是一个完全立方数当e3时可以直接用整数开方验证。工具Python的gmpy2.iroot(c, e)函数可以高效计算整数开方。import gmpy2 def low_exponent_attack(c, e): # 尝试对c开e次方根 root, is_exact gmpy2.iroot(c, e) if is_exact: return int(root) # 返回整数明文m else: return None # 攻击失败可能m^e n注意这种攻击成立的条件比较苛刻。在实际中为了防止这种攻击通常会对明文进行填充如PKCS#1 v1.5或OAEP使得m变得很大确保m^e远大于n。4.3 因数碰撞与不安全的素数生成场景题目给出了多组(n, e, c)但其中某些n共享了同一个素数因子。攻击原理如果两个不同的模数n1和n2有一个公因数p即n1 p * q1,n2 p * q2那么计算gcd(n1, n2)就能直接得到这个公因数p。一旦得到p两个n都能被分解。实操要点当你拿到多个n时养成习惯先两两计算它们的最大公约数。Python的math.gcd(n1, n2)函数可以快速计算。import math def factor_by_collision(moduli_list): 给定一个模数列表尝试通过碰撞分解 factors {} for i in range(len(moduli_list)): for j in range(i1, len(moduli_list)): n1, n2 moduli_list[i], moduli_list[j] p math.gcd(n1, n2) if p ! 1 and p ! n1 and p ! n2: # 找到了非平凡的公因数 print(f发现碰撞n1{n1}, n2{n2}, 公因数 p{p}) q1 n1 // p q2 n2 // p factors[n1] (p, q1) factors[n2] (p, q2) return factors这种攻击暴露了不安全的随机数生成问题如果生成素数的随机性不够可能在多次密钥生成中重复使用了某个素数。4.4 维纳攻击Wiener‘s Attack——针对小私钥d场景私钥d太小具体来说当d (1/3) * n^(1/4)时。攻击原理这个攻击涉及连分数和渐进分数的数论知识比较复杂。其核心思想是当d很小时公钥(n, e)满足的等式e*d 1 k*φ(n)中k/d是e/n的一个很好的渐进分数。通过计算e/n的连分数展开并检查每一个渐进分数就有可能直接猜出k和d进而算出φ(n)并分解n。实操要点自己实现维纳攻击的连分数部分有一定难度。通常使用现成的脚本或库如RSAwienerHackerPython 2时代的一个著名脚本或owiener库。在CTF中如果题目提示“快速解密”或给出特别大的e因为d小为了满足e*d ≡ 1 mod φ(n)e会接近φ(n)显得很大就要考虑维纳攻击。# 安装owiener库 pip install owienerimport owiener def wiener_attack(n, e): try: d owiener.attack(e, n) if d is not None: print(f[] 维纳攻击成功私钥 d {d}) # 验证d是否正确通常需要后续计算来验证 # 例如尝试用d解密一个已知的密文或者计算k (e*d -1)//phi 来验证 return d else: print([-] 维纳攻击失败d可能不够小。) return None except Exception as ex: print(f维纳攻击执行错误: {ex}) return None5. 实战演练从CTF题目到解题脚本让我们结合一个虚构但综合性的CTF题目把上面的知识串起来。假设题目描述如下“我们截获了一段用RSA加密的消息。已知公钥 (n, e) 和密文 c。此外我们还意外获得了加密所用脚本的片段显示他们使用了random.getrandbits(64)来生成素数。你能恢复出明文吗” 附件n16274238971628911073,e65537,c14801157517419236401解题思路分析信息提炼n是20位十进制数64位二进制提示素数是用64位随机数生成的。这意味着p和q大约都是32位10位十进制的数。这个规模对于现代计算机的分解能力来说是“可接受”的。策略选择直接尝试分解n。因为n不大我们可以使用高效的分解算法而不是简单的试除。工具准备我们将编写一个Python脚本集成sympy.factorint进行分解。解题脚本实现#!/usr/bin/env python3 # -*- coding: utf-8 -*- BabyRSA CTF 解题脚本示例 题目n16274238971628911073, e65537, c14801157517419236401 import sys from math import gcd # 尝试导入sympy用于分解如果未安装则提示 try: from sympy import factorint SYMPY_AVAILABLE True except ImportError: SYMPY_AVAILABLE False print(警告未找到sympy库。将使用较慢的试除法或请安装sympy: pip install sympy) def egcd(a, b): 扩展欧几里得算法 if a 0: return b, 0, 1 g, y, x egcd(b % a, a) return g, x - (b // a) * y, y def modinv(e, phi): 求模逆元 g, x, _ egcd(e, phi) if g ! 1: raise ValueError(fe ({e}) 和 phi ({phi}) 不互质无法求逆元) return x % phi def factorize_with_sympy(n): 使用sympy分解n if not SYMPY_AVAILABLE: raise RuntimeError(sympy库未安装) factors factorint(n) # 检查是否为两个素数的乘积 prime_factors [p for p, exp in factors.items() if exp 1] if len(prime_factors) 2: p, q prime_factors return p, q else: raise ValueError(f分解结果异常: n {factors}) def factorize_naive(n, limit1000000): 简单的试除法作为备用效率很低仅用于演示 i 2 while i * i n and i limit: if n % i 0: return i, n // i i 1 if i 2 else 2 # 跳过偶数 return None, None def decrypt_message(n, e, c): 主解密流程 print(f[*] 开始解密...) print(f 模数 n {n}) print(f 公钥 e {e}) print(f 密文 c {c}) # 1. 分解n print(f[*] 尝试分解模数 n...) p, q None, None if SYMPY_AVAILABLE: try: p, q factorize_with_sympy(n) print(f[] 使用sympy分解成功) except Exception as ex: print(f[-] sympy分解失败: {ex}) if p is None: print(f[*] 尝试使用试除法可能很慢...) p, q factorize_naive(n) if p is None: print(f[-] 无法分解 n。n 可能太大或为素数。) return None print(f[] 分解结果: p {p}, q {q}) # 验证 p*q n if p * q ! n: print(f[-] 错误p * q ! n) return None # 2. 计算φ(n) phi (p - 1) * (q - 1) print(f[] φ(n) (p-1)*(q-1) {phi}) # 3. 计算私钥d try: d modinv(e, phi) print(f[] 私钥指数 d {d}) except ValueError as ve: print(f[-] 计算私钥d失败: {ve}) return None # 4. 解密得到整数明文m m pow(c, d, n) print(f[] 解密得到的整数明文 m {m}) # 5. 尝试转换为字节/字符串 # 方法1: 使用Crypto.Util.number try: from Crypto.Util.number import long_to_bytes plaintext_bytes long_to_bytes(m) print(f[] 使用long_to_bytes转换结果: {plaintext_bytes}) # 尝试UTF-8解码 try: plaintext plaintext_bytes.decode(utf-8) print(f[] UTF-8解码后的文本: {plaintext}) except UnicodeDecodeError: print(f[-] 无法用UTF-8解码可能是二进制数据或其它编码。) # 尝试其它常见编码或直接显示hex print(f[] 十六进制表示: {plaintext_bytes.hex()}) except ImportError: # 方法2: 手动转换 print(f[!] 未安装PyCryptodome尝试手动转换。) hex_str hex(m)[2:] if len(hex_str) % 2 ! 0: hex_str 0 hex_str plaintext_bytes bytes.fromhex(hex_str) print(f[] 手动转换的字节: {plaintext_bytes}) try: plaintext plaintext_bytes.decode(utf-8) print(f[] UTF-8解码后的文本: {plaintext}) except UnicodeDecodeError: print(f[-] 无法用UTF-8解码。十六进制: {hex_str}) return m, d, p, q if __name__ __main__: # 题目给出的参数 n 16274238971628911073 e 65537 c 14801157517419236401 result decrypt_message(n, e, c) if result: m, d, p, q result print(f\n[] 解密完成) print(f 明文 (整数): {m}) print(f 私钥 d: {d}) print(f 素数 p: {p}) print(f 素数 q: {q}) else: print(f\n[-] 解密失败。)运行结果与解析当你运行这个脚本确保已安装sympy它会输出类似以下内容[*] 开始解密... 模数 n 16274238971628911073 公钥 e 65537 密文 c 14801157517419236401 [*] 尝试分解模数 n... [] 使用sympy分解成功 [] 分解结果: p 3999379993, q 4068845161 [] φ(n) (p-1)*(q-1) 16274238963571681920 [] 私钥指数 d 13726988140355293473 [] 解密得到的整数明文 m 1234567890 [] 使用long_to_bytes转换结果: b\x00\x00\x00\x00I\x96\x02\xd2 [] UTF-8解码后的文本: [-] 无法用UTF-8解码可能是二进制数据或其它编码。 [] 十六进制表示: 00000000499602d2 [] 解密完成 明文 (整数): 1234567890 私钥 d: 13726988140355293473 素数 p: 3999379993 素数 q: 4068845161我们看到解密出的整数明文m 1234567890。直接解码成文本是乱码因为明文很可能就是一个数字标志比如一个简单的ID或flag格式的一部分。在CTF中flag可能被编码成整数或者需要将这个整数进行进一步转换如转成16进制后再解码为ASCII。这里1234567890的16进制是0x499602d2对应的ASCII字符可能没有直接意义需要结合题目上下文判断。但无论如何我们已经成功地从密文c恢复出了原始的整数消息m证明了RSA加解密过程被我们成功逆转。6. 避坑指南与进阶思考在实际操作BabyRSA工具或解题时你会遇到一些典型的“坑”。这里总结一下帮你少走弯路。6.1 数据格式处理整数、字节与编码这是新手最容易出错的地方。RSA操作的对象是大整数但我们要加密/解密的信息通常是文本或字节。明文转整数m在加密前需要将字符串如“flag{hello}”转换为整数。通常使用bytes_to_longPyCryptodome库或手动将字符串编码为字节后再将字节视为一个大整数。from Crypto.Util.number import bytes_to_long, long_to_bytes plaintext “flag{hello}” m bytes_to_long(plaintext.encode(‘utf-8‘))整数转明文解密得到整数m后需要反向操作。使用long_to_bytes(m)得到字节串再尝试用.decode(‘utf-8‘)解码为字符串。但要注意不是所有整数都能解码成有效的UTF-8文本。它可能是纯数字flag如123456。字节串表示的其它数据如图片的一部分。需要先转换成16进制字符串再从中提取ASCII字符。可能需要多次转换尝试如hex(m)[2:]后看是否有可读的ASCII段。大整数表示Python原生支持大整数但直接打印一个几百位的整数可能不便于阅读。在调试时可以使用hex(m)或str(m)[:50] ‘...‘来查看。6.2 性能优化大数运算与分解当n稍微大一点比如50-80位Python原生的试除法会慢得无法忍受。使用pow(c, d, n)这是Python的内置函数用于计算模幂c^d mod n。它使用了高效的算法如平方乘法和模约减绝对不要用(c ** d) % n后者会先计算一个天文数字般的c**d导致内存溢出。选择高效的分解工具Sympy对于100位以下的nsympy.factorint通常够用且接口简单。Yafu一个强大的整数分解工具支持多种高级算法SIQS, NFS等。对于CTF中常见的100位左右的nYafu往往能在几秒到几分钟内分解。你可以用命令行调用Yafu或者用Python的subprocess模块与之交互。在线分解数据库如factordb.com。对于已知的、常见的或不太大的n可能已经被别人分解过并收录在数据库中。在写脚本自动化解题时可以尝试先查询这个网站通过API或爬虫。注意Python的整数类型Python的int是任意精度的所以不用担心溢出问题这是它的优势。6.3 边界条件与错误处理健壮的脚本应该能处理各种意外情况。检查n是否为素数如果n本身是素数那它就不是两个素数的乘积RSA不成立。可以用sympy.isprime或gmpy2.is_prime快速检查。检查e与φ(n)是否互质在计算模逆元d之前务必验证gcd(e, phi) 1。如果不互质说明公钥选择错误或者你计算的φ(n)不对比如p和q分解错了。验证解密结果解密出明文m后可以尝试用公钥重新加密看是否得到原始的密文cc_prime pow(m, e, n)。如果c_prime c则验证成功。处理多解情况有时解密出的整数m转换成字节后末尾可能有填充字符如PKCS#1 v1.5填充的\x00\x02...需要正确剥离填充才能得到真正的消息。6.4 从解题到理解BabyRSA的真正价值最后我想强调的是BabyRSA工具和相关的CTF题目其终极目的不是让你成为一个“脚本小子”而是引导你深入理解RSA的每一个环节。理解数学之美通过亲手分解n、计算d、完成解密你能直观感受到数论质数、模运算、欧拉定理如何构建起一个安全的通信系统。洞察安全边界你明白了为什么RSA要求用巨大的素数数百位以上。任何参数的“缩小”小素数、小指数、小私钥、共模都会引入致命弱点。培养攻击者思维学习各种攻击手法共模、低指数、维纳攻击等能让你在设计和实现密码系统时主动避免这些陷阱。工具只是延伸Python脚本、Yafu、Factordb都是工具。核心是你的分析能力看到题目能判断属于哪种场景应该采用哪种攻击路径。所以下次当你再遇到一个BabyRSA题目时不要只满足于运行脚本得到flag。多花几分钟看看分解出的p和q算一算φ(n)验证一下e*d mod φ(n)是否等于1。这个过程才是从“知道”到“懂得”的关键一步。密码学的大门正是由这些小小的、可亲手触碰的“婴儿”步骤缓缓向你打开的。