从CTF babyRSA题解析RSA加密原理与费马分解实战

1. 从一道CTF题看RSA的“baby”级陷阱

最近在整理一些老的CTF题目，又翻到了这道来自NCTF2019的babyRSA。题目名字叫“baby”，听起来人畜无害，但很多刚接触密码学或者RSA的朋友，往往就在这种看似简单的题目上栽了跟头。RSA作为非对称加密的基石，其核心安全性建立在“大数分解难题”之上，但题目设计者总能在参数选择、加密流程或者信息泄露上设置一些精巧的“陷阱”，让标准的解密流程失效。这道babyRSA就是一个典型的例子，它考察的不是对RSA算法本身的背诵，而是对算法实现细节、数学性质以及给定数据敏锐的洞察力。今天，我们就来彻底拆解这道题，看看“baby”之名下，到底藏着哪些需要成年人来处理的“坑”。

通常，一个完整的RSA题目会给你公钥（n, e）和密文c，你的任务是恢复出明文m。私钥d的推导依赖于n的分解。如果n很小，你可以直接暴力分解；如果n很大但格式特殊，你可能需要用到费马分解、Pollard‘s p-1等方法。而babyRSA这道题，恰恰在第一步——分解n——就设置了障碍，但它给出的障碍并非坚不可摧，而是需要你转换思路。很多人在网上搜索“RSA解题技巧”时，会看到“rsa public key not find”、“tooooo many rsa! tooooo easy encrypt!”这类错误信息或调侃，这反映了在实战中，机械地套用工具而不知其所以然，很容易碰壁。我们解决这道题的过程，就是一个完整的密码学分析思维训练：观察数据特征、提出假设、验证并利用已知数学定理或工具。

2. 题目数据初步观察与反常之处

首先，我们假设题目提供了类似如下的数据（这是此类题目的常见格式，具体数值是示例，但结构特征一致）：

n = 189935798005902887335567623164658543956546... e = 65537 c = 183288709028589007338385265552465547...

拿到数据的第一步，永远是尝试最直接的方法：对n进行分解。我们会习惯性地使用yafu、factordb.com或者自己写个小脚本尝试暴力。如果n在256bit以下，现代计算机可以快速分解；如果达到512bit或以上，通用分解算法在有限时间内可能无法完成。这时，题目名字“baby”就在暗示：分解n可能不是难点，或者根本不需要分解n。

一个关键的思维转折点在于：仔细检查题目是否只给了n, e, c？很多进阶的RSA题目会给出更多信息，比如多个n共享同一个素数、dp/dq泄露、e极大或极小、明文与n存在某种关系等。对于babyRSA，经过对题目文件的仔细审计（可能是py脚本、txt描述或流量包），我们往往能发现一个被忽略但至关重要的细节：题目可能直接给出了素数p和q，或者给出了与p、q强相关的其他参数。

例如，题目描述或注释里可能有一行像是废码的字符串，或者附件里除了常规的output.txt还有一个hint.txt。举个例子，可能看起来是这样的：

# Maybe this will help you? p = 1234567890123456789012345678901234567890123456789012345678901234567 q = n // p

或者，更隐晦地，它可能给出了phi(n)（欧拉函数值），或者d（私钥）本身。在真正的babyRSA题目中，一种经典的“baby”级陷阱就是：它直接把p和q放在了源代码或注释里，等待粗心的选手去发现。这听起来很滑稽，但恰恰符合“baby”的定位——考察你的细心程度和基本的数据检索能力，而不是高深的数论知识。

假设我们在题目提供的Python加密脚本中发现了如下代码：

import gmpy2 from Crypto.Util.number import * flag = b'NCTF{...}' m = bytes_to_long(flag) p = getPrime(512) q = getPrime(512) n = p * q e = 65537 c = pow(m, e, n) print(f'n = {n}') print(f'e = {e}') print(f'c = {c}') # 下面这行被很多人忽略 print(f'# Just for debugging: p = {p}, q = {q}')

输出文件里，最后一行注释可能被当成无关内容过滤掉了。但如果你仔细查看完整的输出，就能直接拿到p和q。这就是第一个“坑”：不要想当然，务必审查每一行输出、每一个文件、甚至网页源代码的注释。

3. 当分解不可行时的核心突破口：利用已知数学关系

如果题目没有这么“仁慈”地直接给出因子，我们就要进入更典型的分析流程。让我们假设一个稍微复杂一点，但仍是“baby”级别的场景：题目给出的n、e、c是标准的，但n无法直接分解。然而，题目名字暗示存在捷径。这时，我们需要排查RSA的各类已知攻击场景：

1. 小公钥指数攻击（e很小）：如果e=3，并且明文m很小，使得 m^e < n，那么加密过程实际上没有取模，c = m^e。直接对c开e次方根即可得到m。但本题e=65537，属于常规值，排除。
2. 小私钥指数攻击（d很小）：通常需要d小于n的0.292次方，利用Wiener攻击或Boneh-Durfee攻击。但题目未给出d，且“baby”题一般不会涉及这种较复杂的连分数攻击。
3. 模数不互素：如果给出两个密文c1、c2，对应不同的模数n1和n2，但共享一个素数因子，可以通过计算gcd(n1, n2)来分解。但本题只有一个n。
4. 共模攻击：同一个明文m，用相同的n但不同的e1、e2加密，得到c1、c2。如果e1和e2互素，可以通过扩展欧几里得算法恢复m。本题只有一个e。
5. 费马分解法：当p和q非常接近，即|p-q|很小的时候，n可以表示为两个相近数的平方差，可以通过枚举尝试分解。对于512bit的素数，如果它们真的非常接近，费马分解是有效的。我们可以尝试一下。

用Python演示费马分解的思路：

import gmpy2 from math import isqrt def fermat_factorization(n): a = gmpy2.isqrt(n) + 1 # 取n的平方根并向上取整 b2 = a*a - n while not gmpy2.is_square(b2): a += 1 b2 = a*a - n b = gmpy2.isqrt(b2) p = a + b q = a - b return int(p), int(q) n = 1899357... # 替换为题目中的n p, q = fermat_factorization(n) print(f"p = {p}") print(f"q = {q}")

如果p和q接近，这个算法会很快（几秒内）返回结果。在很多“baby”级题目中，出题人为了确保选手能轻松分解，会故意让p和q非常接近，从而使得费马分解法瞬间成功。这就是“baby”的另一种含义：利用简单的数学性质，绕过暴力分解的复杂性。

6. Pollard‘s p-1 分解法：当p-1或q-1的因子都很小时，这个算法能快速分解n。对于特意构造的“平滑”的p-1，这也是一种常见考点。

from Crypto.Util.number import * def pollard_p_minus_1(n, max_iter=100000): a = 2 for j in range(2, max_iter): a = pow(a, j, n) d = GCD(a-1, n) if 1 < d < n: return d return None n = 1899357... p = pollard_p_minus_1(n) if p: q = n // p print(f"Found factor via p-1: p={p}, q={q}")

如果题目中的p-1是由大量小素数乘积构成的（例如2^a * 3^b * 5^c ...），那么这个方法也会很快奏效。

对于babyRSA，经过尝试，费马分解法有极高的成功率。这很可能就是出题人预设的解题路径。它不需要你理解复杂的数论，只需要你知道“两个大素数如果生成得太接近会有安全风险”这个知识点，并且会使用平方差公式进行分解。

4. 获取私钥与解密完整流程

一旦我们成功分解n，得到p和q，剩下的就是RSA解密的标准化流程了。我们来详细走一遍，并解释每一个步骤背后的数学原理，这对于理解RSA至关重要。

步骤1：计算欧拉函数 φ(n)RSA中，φ(n) = (p-1) * (q-1)。这个值代表了在模n下与n互质的整数个数，是密钥对生成的核心。

phi = (p-1) * (q-1)

步骤2：计算私钥指数 d私钥d是公钥e关于模φ(n)的模逆元。即满足 e * d ≡ 1 (mod φ(n))。这意味着e和d在模φ(n)的乘法运算中互为倒数。

import gmpy2 d = gmpy2.invert(e, phi) # gmpy2.invert(a, m) 返回 a 模 m 的逆元

这里使用gmpy2库是因为它支持大整数运算，速度快且准确。Python内置的pow(a, -1, m)在3.8+版本也可以实现，但gmpy2在处理CTF中的超大整数时更稳定。

步骤3：解密密文 c明文m由密文c通过私钥d解密得到： m ≡ c^d (mod n)。

m = pow(c, d, n) # Python内置的pow支持模幂运算，非常高效

步骤4：将整数明文转换为字节得到的m是一个大整数，我们需要将其转换回字节串，也就是我们想要的flag。

from Crypto.Util.number import long_to_bytes flag = long_to_bytes(m) print(flag)

如果flag格式正确，你会看到类似b‘NCTF{...’}的输出。

整个过程的数学原理回顾： RSA加密： c = m^e mod n RSA解密： m = c^d mod n 其正确性基于欧拉定理：若m与n互质，则 m^φ(n) ≡ 1 (mod n)。因为 ed ≡ 1 (mod φ(n))，所以存在整数k使得 ed = 1 + kφ(n)。那么解密时： c^d ≡ (m^e)^d ≡ m^(ed) ≡ m^(1 + k*φ(n)) ≡ m * (m^φ(n))^k ≡ m * 1^k ≡ m (mod n)。 即使m与n不互质（概率极低），利用中国剩余定理（CRT）也能证明解密过程依然成立。这就是RSA为什么能工作的核心。

在babyRSA的语境下，一旦分解了n，这些步骤就是机械的。但这里有一个至关重要的实操细节：确保你计算出的d是正确的。一个简单的验证方法是：用公钥(e, n)重新加密解密得到的m，看是否等于原始的c。即pow(m, e, n) == c。如果相等，说明密钥计算和加解密过程无误。

5. 实战演练与脚本编写：从数据到Flag

现在，让我们用一个模拟的、但高度贴近原题的数据，编写一个完整的解题脚本。我们将假设通过费马分解法成功获得了p和q。

#!/usr/bin/env python3 # -*- coding: utf-8 -*- # solve_babyRSA.py import gmpy2 from Crypto.Util.number import long_to_bytes, bytes_to_long import sys def fermat_factorization(n): """ 使用费马分解法分解n。 当p和q接近时，此方法效率很高。 """ a = gmpy2.isqrt(n) + 1 b2 = a*a - n count = 0 max_count = 1000000 # 安全限制，防止无限循环 while not gmpy2.is_square(b2): a += 1 b2 = a*a - n count += 1 if count > max_count: print("Fermat factorization failed. p and q may not be close enough.") return None, None b = gmpy2.isqrt(b2) p = a + b q = a - b return int(p), int(q) def main(): # 题目给出的数据（此处为示例，需替换为真实数据） n = 0xDEADBEEF... # 替换为真实的n，十六进制或十进制整数 e = 65537 c = 0xCAFEBABE... # 替换为真实的c print("[*] Attempting Fermat factorization on n...") p, q = fermat_factorization(n) if p is None or q is None: print("[-] Failed to factor n using Fermat‘s method. Exiting.") sys.exit(1) print(f"[+] Factorization successful!") print(f" p = {p}") print(f" q = {q}") print(f" n = {n}") print(f" p*q == n? {p * q == n}") # 验证分解结果 # 计算私钥 print("[*] Calculating private key d...") phi = (p - 1) * (q - 1) try: d = gmpy2.invert(e, phi) except Exception as ex: print(f"[-] Failed to calculate modular inverse: {ex}") print(f" Check that e ({e}) and phi are coprime. gcd(e, phi) = {gmpy2.gcd(e, phi)}") sys.exit(1) print(f"[+] Private key d calculated.") # 解密密文 print("[*] Decrypting ciphertext c...") m = pow(c, d, n) print(f"[+] Decrypted message (as integer): {m}") # 转换为字节 flag = long_to_bytes(m) print(f"[+] Potential flag: {flag}") # 可选：验证解密结果 print("[*] Verifying decryption...") c_verif = pow(m, e, n) if c_verif == c: print("[+] Verification successful! Decryption is correct.") else: print("[-] Verification failed! Something went wrong in the calculation.") if __name__ == "__main__": main()

脚本使用说明与注意事项：

1. 数据替换：务必将脚本中n和c的示例值替换为题目给出的真实数值。数值可以是十进制大整数，也可以是十六进制字符串（以0x开头）。
2. 库依赖：确保你的Python环境安装了gmpy2和pycryptodome（后者提供了Crypto.Util.number）。安装命令通常为pip install gmpy2 pycryptodome。在某些系统上，gmpy2的安装可能需要系统级的GMP库支持。
3. 分解失败：如果费马分解长时间不返回（脚本中设置了100万次迭代上限），说明这道题可能不是用“素数接近”这个点。你需要重新审视题目，尝试其他方法，比如检查是否有p-1平滑的特性（用Pollard‘s p-1），或者回头更仔细地寻找是否直接给出了因子。
4. 结果验证：验证步骤（c_verif == c）非常关键。它能帮你确认从分解到解密的整个链条没有出错。如果验证失败，请按以下顺序排查：
   • 检查n, e, c的数值是否复制正确。
   • 检查分解得到的p和q是否正确（通过p*q == n验证）。
   • 检查phi的计算是否正确。
   • 检查d的计算是否成功（e和phi必须互质）。
5. 输出解读：最终输出的flag可能是字节串。如果flag包含不可打印字符，可能会显示为\x的形式。如果输出看起来是乱码，可以尝试用flag.decode(‘utf-8‘, errors=‘ignore‘)或flag.hex()查看其十六进制形式，有时flag可能被编码或填充了。

6. 常见错误与排查指南：为什么你的脚本不工作？

在实战解这类题时，90%的问题都出在数据准备和环境配置上。下面我罗列了几个最常见的坑点及其解决方案。

问题1：gmpy2或Crypto模块导入失败。

• 错误信息：ModuleNotFoundError: No module named ‘gmpy2‘或ModuleNotFoundError: No module named ‘Crypto‘。
• 原因：Python环境没有安装必要的库。
• 解决：
  • 使用pip安装：pip install gmpy2 pycryptodome。注意库名是pycryptodome，不是pycrypto（已废弃）。
  • 如果安装gmpy2失败，可能是缺少GMP或MPIR数学库。在Ubuntu/Debian上可以尝试sudo apt-get install libgmp-dev，在macOS上brew install gmp，然后再安装gmpy2。
  • 如果实在装不上gmpy2，对于“baby”级题目，数字可能不大，可以尝试使用Python内置的pow(a, -1, m)求模逆（Python 3.8+），但大数运算速度会慢。

问题2：分解出的p和q是小数，或者p*q不等于n。

• 原因：费马分解法失败了，但程序没有正确判断。可能b2恰好是一个平方数，但不是正确的解。
• 解决：在fermat_factorization函数中，增加一个强验证：if p * q == n: return p, q else: continue searching。确保返回的因子乘积严格等于n。

问题3：计算私钥d时出错，提示“inverse does not exist”。

• 错误信息：ZeroDivisionError或gmpy2抛出的类似异常。
• 原因：公钥指数e和欧拉函数phi不互质，即gcd(e, phi) != 1。这在标准RSA中是不应该发生的，因为e需要在1 < e < phi且与phi互质中选择。如果发生，说明：
  1. 你的p和q分解错了，导致计算出的phi是错误的。
  2. 题目本身是非标准的，e可能故意选得与phi不互质，这时需要其他方法（比如计算e和phi的最大公约数，在子群中解密），但这超出了“baby”范畴。首先强烈怀疑情况1。
• 解决：重新检查分解步骤。打印gcd(e, phi)的值。如果分解正确，gcd(e, phi)应该为1。

问题4：解密出的整数m转换成的字节串不是可读的flag。

• 现象：long_to_bytes(m)输出像b‘\x85\xa3\xf2...‘这样的乱码。
• 原因：
  1. 最可能：你解密出的m是正确的，但flag可能被填充了（例如PKCS#1 v1.5填充），或者flag本身不是UTF-8编码的文本。CTF中的flag通常是flag{...}或NCTF{...}格式的字符串，但有时会经过一层编码（如Base64、Hex）后再加密。
  2. 解密错误，得到了错误的m。
• 排查：
  • 首先验证加解密：用你得到的m重新加密，看是否等于原始c。如果不等，说明解密错误，回到问题3。
  • 如果验证通过，说明解密正确。尝试将m以十六进制形式输出：print(hex(m))。观察开头和结尾的字节。常见的flag格式flag{对应的十六进制是66 6c 61 67 7b（ASCII）。如果你在hex(m)的开头看到了666c61677b，那么后面部分就是flag内容，可能被一些非打印字符隔开了。你需要手动提取并转换。
  • 尝试其他解码方式：

    # 尝试直接解码为ASCII/UTF-8，忽略错误 print(flag.decode(‘utf-8‘, errors=‘ignore‘)) # 尝试Base64解码（如果flag是Base64编码的字符串） import base64 try: print(base64.b64decode(flag).decode()) except: pass # 尝试Hex解码 try: print(bytes.fromhex(flag.hex()).decode()) except: pass

问题5：脚本运行速度慢，尤其是费马分解部分。

• 原因：如果p和q并不接近，费马分解的循环次数会急剧增加，甚至达到上亿次，对于Python来说会很慢。
• 解决：
  • 首先确认题目是否真的是“素数接近”考点。可以尝试用yafu的factor(n)命令，或者去factordb.com查询n是否已被分解。
  • 如果必须用费马分解且确实慢，可以考虑用gmpy2重写核心循环，或者用multiprocessing进行并行搜索。但对于CTF题目，出题人通常会让分解在合理时间内完成（几秒到几分钟）。

7. 举一反三：从babyRSA到更一般的RSA题目思维

解完这道babyRSA，我们不应该只停留在“会用费马分解”这个技巧上。更重要的是建立起一套面对RSA题目的通用分析思维框架。这套框架可以帮助你应对更复杂的挑战。

第一步：数据收集与观察

• 拿到所有题目文件：.py、.txt、.pcap、图片（可能隐写数据）、网页源代码。
• 仔细阅读每一行代码、注释、输出。用strings命令查看二进制文件中的可读字符串。
• 提取所有数字：大的整数（可能是n, c, e, p, q, d, dp, dq）、指数、系数。记录它们的含义和关系。

第二步：识别模式与潜在攻击面根据收集到的数据，快速匹配已知的RSA攻击场景：

第三步：工具准备与尝试

• 分解：yafu、factordb.com、sage（内置强大的分解和Coppersmith方法）。
• 计算：Python+gmpy2/sage、RsaCtfTool（集成了多种攻击的自动化工具）。
• 解码：Python的long_to_bytes、bytes_to_long、base64、binascii。

第四步：验证与迭代

• 任何中间结果都要验证：分解后验证p*q == n；计算出d后验证e*d ≡ 1 mod phi；解密出m后验证m^e ≡ c mod n。
• 如果一条路走不通，回到第二步，重新审视数据，看看是否有遗漏的信息或另一种攻击模式。

对于babyRSA，我们走完了“观察（发现n）-> 模式识别（猜测素数接近）-> 工具尝试（费马分解）-> 验证解密”的全流程。它像一把钥匙，帮你打开了RSA密码学挑战的大门。下次再看到“baby”这个词，你不会掉以轻心，而是会心一笑，知道该从哪里开始你的“狩猎”。