当前位置：首页 > news >正文

CTF实战：巧用费马小定理破解特殊构造的RSA（以[NCTF2019]childRSA为例）

news 2026/5/27 22:30:23

1. 题目背景与核心漏洞分析

这道来自NCTF2019的childRSA题目，乍一看是个标准的RSA加密问题——给出了公钥(n,e)和密文c。但关键在于它采用了特殊的素数生成方式：从前10000个小素数列表中随机选择若干素数相乘，直到乘积加1成为大素数（代码中的getPrime函数）。这种构造方式看似安全，实则暗藏致命漏洞。

我最初看到题目时，注意到两个关键特征：首先，p和q的生成都依赖前10000个素数的乘积；其次，题目名称暗示了费马小定理的应用。这让我立即联想到Pollard's p-1算法——当p-1的所有素因子都较小时，可以通过计算2^B! mod n来高效分解n。但本题的素数生成方式更为特殊，直接使用已知素数集合的乘积。

2. 费马小定理的巧妙应用

费马小定理告诉我们：若p是素数且a不被p整除，则a^(p-1) ≡ 1 mod p。这个看似简单的定理在本场景下成为破解的关键。让我们分步拆解：

设primes是前10000个素数的集合，令PRD为其乘积
根据题目，p = k * PRD + 1（其中k是某个整数）
由费马小定理：2^(p-1) ≡ 1 mod p → 2^(k*PRD) ≡ 1 mod p
这意味着(2^PRD - 1) ≡ 0 mod p，即p整除(2^PRD - 1)

实际操作中，我们不需要计算巨大的2^PRD值，而是计算2^PRD mod n。因为：

若p | (2^PRD - 1)，则(2^PRD mod n) ≡ 1 mod p
因此gcd(2^PRD mod n -1, n)很可能就是p

这个优化将计算复杂度从O(2^PRD)降到O(log PRD)，使得攻击在普通电脑上几秒内就能完成。

3. 完整攻击流程实现

基于上述理论，我整理出可复现的攻击步骤：

计算前10000个素数的乘积：

prd = 1 for p in primes: # primes是前10000个素数的列表 prd *= p

关键模幂运算：

from gmpy2 import powmod, gcd x = powmod(2, prd, n) - 1 # 计算2^prd mod n

分解n：

p = gcd(x, n) q = n // p

常规RSA解密：

d = invert(e, (p-1)*(q-1)) m = powmod(c, d, n)

实测在i7处理器上，整个攻击过程耗时不到3秒。这提醒我们：在CTF竞赛中，遇到特殊构造的RSA题目时，首先要分析其素数生成方式的潜在弱点。

4. 防御措施与扩展思考

虽然这道题被成功破解，但其中蕴含的密码学原理值得深入探讨。在实际应用中，为避免此类攻击：

素数生成规范：必须确保p-1包含大素因子，可以通过选择安全素数（p=2q+1，q也是素数）或使用强素数
参数检查：部署RSA前应检查(p-1)和(q-1)是否有小因子积
替代方案：考虑使用基于椭圆曲线的加密方案，其安全性不依赖大数分解

在CTF实战中，类似的变种题目还有很多。比如有些题目会使用斐波那契数列生成素数，或者要求参赛者自己构造不安全的素数对。掌握费马小定理的灵活应用，往往能发现出人意料的解题路径。

5. 深入理解数学原理

为什么这个方法能奏效？核心在于群论中的阶概念。在模p乘法群中，元素的阶必须整除群的阶(p-1)。当p-1由小素数构成时，群阶过于"光滑"，使得我们能够构造出揭示p的信息。

具体到本题：

计算PRD时实际上构造了(p-1)的倍数
根据拉格朗日定理，2^PRD ≡ 1 mod p必然成立
但2^PRD ≡ r mod q（r通常≠1），因此gcd结果会暴露p

这种思路不仅适用于RSA，在其他基于离散对数问题的密码系统中，类似的光滑数攻击也经常出现。理解其数学本质，才能举一反三应对各种变体。

6. 实战中的注意事项

在真实解题过程中，我遇到了几个容易踩坑的地方：

素数列表范围：必须确认使用的是前10000个素数，而非前10000以内的素数。两者差异巨大，前者包含104729（第10000个素数），后者只到104729但数量更少。
模幂运算优化：直接计算2^PRD会引发内存溢出，必须使用powmod的三参数形式。我曾因忘记这点导致程序卡死。
数据类型处理：Python的int类型虽无上限，但大数运算效率低下。使用gmpy2库可以显著提升性能，特别是在处理2048位大数时。
边界情况处理：当gcd(2^PRD-1, n)==n时，说明PRD选择不当，可能需要调整素数集合或检查算法假设。