♧ Godown 安全知识树

RSA 指数 e 隐藏在素数计数中:埃氏筛求 π(N)−1 恢复 e,再分解近邻素数 n

crypto/rsa · verified

一句话结论

RSA 题不给公钥指数 e,而是给出与“小于 N 的素数个数”相关的线索时,可用埃氏筛(或 Meissel–Lehmer/primecount)算出 π(N) 并按题目定义恢复 e(本例 π(703440151)=36421874,e=36421874−1);n 的两个素因子只相差 210,从 ⌊√n⌋ 向下试除即可快速分解,随后求 d 解密。

原理

  • e 不是秘密,但可以是“未公开的参数”:RSA 的安全性依赖 n 的分解,不依赖 e 的保密;但 CTF 中可以把 e 藏进一个数学定义,迫使攻击者先还原参数。只要定义可由公开信息或可计算函数复现,攻击者就能重建 e。
  • 素数计数函数 π(N):π(N) 表示小于等于 N 的素数个数。本题线索是把 e 定义成 π(703440151) 相关的值;用埃氏筛在 O(N log log N) 时间内枚举 2..N 的素数并计数,得到 36421874,再按题目提示减 1 得 e=36421873。若 N 更大(10^12 以上),改用 Meissel–Lehmer、Lagarias–Miller–Odlyzko 或 primecount/sympy.primepi 等亚线性算法。
  • 威尔逊定理的作用:威尔逊定理给出 (p−1)! ≡ −1 (mod p) 当且仅当 p 为素数(p>1),可用于判断素数或构造与阶乘相关的“校验函数”。本题的辅助函数用阶乘模 e 的累加来做素数性质判断;理解这一点可以确认线索指向素数计数,而不是普通的 e 爆破。
  • 近邻素数分解:若 n=p·q 且 |p−q| 很小,令 x=⌊√n⌋,从 x 开始递减直到 n % x == 0,则 p=x、q=n//x;这与费马分解等价,迭代次数约为 (q−p)²/(8√n),差 210 时几乎瞬间完成。分解后 φ=(p−1)(q−1),d=e^{-1} mod φ,m=pow(c,d,n)。
  • 为什么能成立:e 的定义是确定性的、可公开计算的;n 的因子又因为“近邻素数”生成方式而可分解。两条弱点叠加,RSA 的私钥就被恢复。

触发条件

  • 题目只给 n、c(可能还给 p/q 的生成方式或范围),e 需要通过一个数学定义/函数/提示恢复,且定义可离线计算。
  • 素数计数规模在可计算范围内(本例 N≈7×10^8,筛法可行;更大时需要有亚线性算法或额外提示)。
  • n 的两个素因子接近(由相邻素数、next_prime、p+k 等方式生成),或题目给出 p、q 的高位/差值等可分解信息。
  • 恢复出的 e 与 φ(n) 互素,否则需调整 e 或考虑其他攻击。

利用步骤

  1. 从题面提取 e 的定义:是“小于 N 的素数个数”、第 k 个素数、素数和,还是某个阶乘/威尔逊函数的结果;确定 ± 偏移。
  2. 用筛法计算 π(N)。小 N 直接开 bytearray 筛;大 N 用 sympy.primepi、primecount 或 Meissel–Lehmer 实现。
  3. 按定义得到 e,检查 gcd(e, φ(n)) == 1(φ 未知时先分解 n)。
  4. 分解 n:若 p、q 接近,从 isqrt(n) 向下试除;否则用费马分解、Pollard rho、ECM 等。
  5. 计算 d = invert(e, (p−1)*(q−1)),m = pow(c, d, n),long_to_bytes(m) 取 flag;若 m 的字节长度异常,检查是否需要 CRT/多素数或 m>n 的处理。

PoC

from math import isqrt
from Crypto.Util.number import long_to_bytes, inverse

N = 703440151

def prime_pi(n: int) -> int:
    """埃氏筛统计 <= n 的素数个数;bytearray 比 Python bool 列表省内存。"""
    if n < 2:
        return 0
    sieve = bytearray(b"\x01") * (n + 1)
    sieve[0:2] = b"\x00\x00"
    for i in range(2, isqrt(n) + 1):
        if sieve[i]:
            start = i * i
            sieve[start:n + 1:i] = b"\x00" * (((n - start) // i) + 1)
    return sum(sieve)

pi_n = prime_pi(N)          # 36421874
e = pi_n - 1                # 按题面定义:π(N) - 1
n = 18770575776346636857117989716700159556553308603827318013591587255198383129370907809760732011993542700529211200756354110539398800399971400004000898098091275284235225898698802555566416862975758535452624647017057286675078425814784682675012671384340267087604803050995107534481069279281213277371234272710195280647747033302773076094600917583038429969629948198841325080329081838681126456119415461246986745162687569680825296434756908111148165787768172000131704615314046005916223370429567142992192702888820837032850104701948658736010527261246199512595520995042205818856177310544178940343722756848658912946025299687434514029951
c = 2587907790257921446754254335909686808394701314827194535473852919883847207482301560195700622542784316421967768148156146355099210400053281966782598551680260513547233270646414440776109941248869185612357797869860293880114609649325409637239631730174236109860697072051436591823617268725493768867776466173052640366393488873505207198770497373345116165334779381031712832136682178364090547875479645094274237460342318587832274304777193468833278816459344132231018703578274192000016560653148923056635076144189403004763127515475672112627790796376564776321840115465990308933303392198690356639928538984862967102082126458529748355566

# 近邻素数分解:从 sqrt(n) 向下找因子
x = isqrt(n)
while n % x:
    x -= 1
p, q = x, n // x

phi = (p - 1) * (q - 1)
d = inverse(e, phi)
m = pow(c, d, n)
print(long_to_bytes(m))
# 本题数据输出:
# b'DASCTF{Ot2N63D_n8L6kJt_f40V61m_zS1O8L7}'

变体与关联

  • 定义变体:e 可被定义为“小于 N 的素数个数”“第 n 个素数”“素数之和 mod X”“π(N) 的某几位”“威尔逊函数输出”等;先还原定义,再选择筛法/亚线性算法。
  • 大 N 变体:N 超过筛法内存上限时,使用 Meissel–Lehmer、Lagarias–Miller–Odlyzko、primecount、sympy.primepi;也可利用题目给的区间分段筛。
  • 分解变体:p、q 由 next_prime、p+2k、相邻素数生成时用费马分解/从 √n 递减试除;更一般的情况用 Pollard rho/ECM/二次筛。
  • 关联卡片:[[crypto-rsa-fermat-close-prime-factorization]](近邻素数的费马平方差分解,本卡与其共享分解思路)、[[crypto-rsa-e3-known-prefix-suffix-coppersmith]](另一种参数/明文结构攻击)、[[ctf-crypto-rsa-unknown-e-rail-fence-filter]](e 未知时的暴力+明文筛选)。
  • 边界:若 e 的定义依赖随机数/私密值,或 n 的因子不接近且无法分解,本链不成立;e 与 φ 不互素时需换攻击面。

检测与防御

  • CTF/设计视角:不要用“可被攻击者离线计算的公开函数”隐藏 e;若必须隐藏参数,隐藏 n 的分解而不是 e。
  • 实现视角:RSA 参数应由可信库生成,e 固定为 65537 并公开;p、q 应独立随机且差值足够大,避免近邻素数;对 n 做素性/结构检查。
  • 检测信号:题目/服务端提供的 n 极小或接近完全平方;p、q 差很小;e 缺失但存在可疑的数学函数/常量(大整数、素数计数范围、阶乘和)。
  • 取证:遇到异常 RSA 参数时,先检查 n 是否为完全平方/近邻因子,再检查 e 是否可由题面常量推导,最后才考虑通用分解。