CTF实战：手把手教你用费马小定理破解NCTF2019这道特殊的RSA题（附完整Python脚本）

当你第一次在BUUCTF平台遇到这道名为"childRSA"的题目时，可能会被它看似标准的RSA加密所迷惑。但仔细观察题目描述中关于素数生成的细节，就会发现这是一道考察数学洞察力的好题。本文将带你从零开始，一步步拆解这道NCTF2019的经典题目，重点讲解如何利用费马小定理这一数学工具来破解特殊构造的RSA模数。

1. 题目分析与关键发现

首先我们来看题目给出的核心代码片段：

from random import choice
from Crypto.Util.number import isPrime, sieve_base as primes

def getPrime(bits):
    while True:
        n = 2
        while n.bit_length() < bits:
            n *= choice(primes)  # primes为前10000个素数的列表
        if isPrime(n + 1):
            return n + 1

这段代码揭示了p和q的生成方式：

1. 初始值为2
2. 不断乘以前10000个素数中的随机素数，直到达到指定位数
3. 检查n+1是否为素数，如果是则返回

这种生成方式意味着：

• p-1和q-1都是由前10000个素数中的某些素数相乘得到的
• 因此，前10000个素数的乘积∏必然是(p-1)和(q-1)的公倍数

关键洞察 ：这种性质让我们联想到费马小定理的应用场景，特别是当模数的构造具有特殊形式时。

2. 费马小定理的深入理解与应用

费马小定理告诉我们：如果p是素数，且a不是p的倍数，那么：

a^(p-1) ≡ 1 mod p

将这个定理扩展一下，我们可以得到：

a^(k*(p-1)) ≡ 1^k ≡ 1 mod p

这意味着a^(k*(p-1)) - 1是p的倍数。

回到我们的题目：

• 设前10000个素数的乘积为∏
• 由于∏是(p-1)的倍数，我们可以表示为∏ = k*(p-1)
• 根据费马小定理：2^∏ ≡ 1 mod p
• 因此2^∏ - 1 ≡ 0 mod p，即2^∏ - 1是p的倍数

由于n = p*q，我们可以计算gcd(2^∏ - 1, n)来得到p。但直接计算2^∏会遇到大数计算问题，我们需要更聪明的方法。

3. 优化计算：模幂运算的巧妙应用

直接计算2^∏会得到一个极其庞大的数字，这在实践中不可行。我们需要利用模运算的性质来优化：

2^∏ ≡ 1 mod p ⇒ 2^∏ - 1 ≡ 0 mod p
2^∏ ≡ x mod n (x = 2^∏ % n)

因为n = p*q，所以：

x ≡ 2^∏ mod p
x ≡ 2^∏ mod q

根据前面的推导，2^∏ ≡ 1 mod p，所以：

x ≡ 1 mod p

这意味着x - 1是p的倍数，因此：

gcd(x - 1, n) = p

这样我们只需要计算2^∏ mod n，这可以通过Python的pow函数高效完成。

4. 完整解题步骤与Python实现

现在我们将上述思路转化为具体的解题步骤：

1. 计算前10000个素数的乘积∏
2. 计算2^∏ mod n
3. 计算gcd(2^∏ mod n - 1, n)得到p
4. 用p计算q = n / p
5. 计算私钥d = e^-1 mod (p-1)(q-1)
6. 解密ciphertext得到flag

以下是完整的Python实现：

import gmpy2
import binascii
from Crypto.Util.number import isPrime, sieve_base as primes

# 题目给定的参数
e = 0x10001
n = 32849718197337581823002243717057659218502519004386996660885100592872201948834155543125924395614928962750579667346279456710633774501407292473006312537723894221717638059058796679686953564471994009285384798450493756900459225040360430847240975678450171551048783818642467506711424027848778367427338647282428667393241157151675410661015044633282064056800913282016363415202171926089293431012379261585078566301060173689328363696699811123592090204578098276704877408688525618732848817623879899628629300385790344366046641825507767709276622692835393219811283244303899850483748651722336996164724553364097066493953127153066970594638491950199605713033004684970381605908909693802373826516622872100822213645899846325022476318425889580091613323747640467299866189070780620292627043349618839126919699862580579994887507733838561768581933029077488033326056066378869170169389819542928899483936705521710423905128732013121538495096959944889076705471928490092476616709838980562233255542325528398956185421193665359897664110835645928646616337700617883946369110702443135980068553511927115723157704586595844927607636003501038871748639417378062348085980873502535098755568810971926925447913858894180171498580131088992227637341857123607600275137768132347158657063692388249513
c = 26308018356739853895382240109968894175166731283702927002165268998773708335216338997058314157717147131083296551313334042509806229853341488461087009955203854253313827608275460592785607739091992591431080342664081962030557042784864074533380701014585315663218783130162376176094773010478159362434331787279303302718098735574605469803801873109982473258207444342330633191849040553550708886593340770753064322410889048135425025715982196600650740987076486540674090923181664281515197679745907830107684777248532278645343716263686014941081417914622724906314960249945105011301731247324601620886782967217339340393853616450077105125391982689986178342417223392217085276465471102737594719932347242482670320801063191869471318313514407997326350065187904154229557706351355052446027159972546737213451422978211055778164578782156428466626894026103053360431281644645515155471301826844754338802352846095293421718249819728205538534652212984831283642472071669494851823123552827380737798609829706225744376667082534026874483482483127491533474306552210039386256062116345785870668331513725792053302188276682550672663353937781055621860101624242216671635824311412793495965628876036344731733142759495348248970313655381407241457118743532311394697763283681852908564387282605279108

# 步骤1：计算前10000个素数的乘积
prd = 1
for prime in primes:
    prd *= prime

# 步骤2和3：计算p
p = gmpy2.gcd(gmpy2.powmod(2, prd, n) - 1, n)
q = n // p

# 步骤5：计算私钥d
phi = (p - 1) * (q - 1)
d = gmpy2.invert(e, phi)

# 步骤6：解密
m = gmpy2.powmod(c, d, n)
flag = binascii.unhexlify(hex(m)[2:])
print(flag)

运行这段代码，你将得到flag：

b'NCTF{Th3r3_ar3_1ns3cure_RSA_m0duli_7hat_at_f1rst_gl4nce_appe4r_t0_be_s3cur3}'

5. 关键点回顾与经验分享

在解决这道题目的过程中，有几个关键转折点值得特别注意：

1. 素数生成方式的观察 ：识别出p-1和q-1都是由小素数相乘得到这一特性是解题的起点。在实际CTF比赛中，仔细阅读题目给出的所有代码片段至关重要。

2. 数学定理的选择 ：费马小定理在这里的应用非常巧妙。在CTF密码学题目中，常见的数学工具包括：

   • 费马小定理
   • 中国剩余定理
   • 欧拉定理
   • 二次剩余理论

3. 计算优化 ：直接计算大指数会导致性能问题，使用模幂运算（powmod）是必须掌握的技巧。在Python中，内置的pow函数或gmpy2的powmod都能高效处理这类计算。

在实际比赛中遇到类似题目时，建议按照以下步骤思考：

• 分析密钥生成过程的特殊性
• 寻找可能应用的数学定理
• 设计可行的计算方法
• 考虑计算效率优化

这道childRSA题目很好地展示了即使看起来安全的RSA实现，如果参数生成不当，也会存在致命漏洞。理解这些漏洞背后的数学原理，不仅能帮助你在CTF比赛中得分，更能加深对密码学安全性的认识。