WKCTF2024 fl@g:排列组合计数生成 p 的 RSA——用容斥公式算 real_n 后 nextprime 解 n
crypto/rsa · verified
一句话结论
题目用 myprime() 暴力枚举字符表的所有排列,统计包含 flag/FLAG/f14G/7!@9/F1ag 任一子串的排列数 num,再返回 nextprime(num) 作为 RSA 的 p;不必跑阶乘级枚举,文章用容斥公式 real_n = 62!*63*4 - 4*58!*59*60 + 54!*55*56*57 直接算出该计数,p = nextprime(real_n)、q = n // p,再按标准 RSA 求 d 解密。
原理
- myprime 的定义:
myprime()对长度为 62 的字符表做permutations全排列,把每个排列拼成字符串;若其中包含flag、FLAG、f14G、7!@9、F1ag任一子串就计数,最后nextprime(num)返回素数作为 RSA 的 p。直接跑 62! 次枚举不可行,必须用组合数学算num。 - 把模式当成“块”:一个 4 字符模式出现在排列中,可把它视为一个整体块;块的位置数乘以其余字符的排列数就是“包含该模式”的排列数。多个模式同时出现时,用容斥减去重叠、加回三重交叠。
- 文章的闭式:
text real_n = factorial(62)*63*4 - 4*factorial(58)*59*60 + factorial(54)*55*56*57第一项是各模式的“块”计数(62!*63 = 63!再乘原文系数 4;原文注释列了 5 个模式,系数与模式数的对应原文未展开);第二项减去两两重叠的计数(58!*59*60 = 60!乘系数 4);第三项加回三重交叠(54!*55*56*57 = 57!)。系数/项数取决于字符表与模式的重叠关系,关键是先识别“块 + 容斥”的结构;文章用该式得到的real_n与myprime的暴力计数一致。 - 为什么能用 nextprime 作为 p:题目把 p 定义成“计数后的下一个素数”,因此 p 不是随机素数,而是由公开的字符表/模式完全决定的;攻击者只要重算计数就能得到 p,进而
q = n // p分解 n。这是“p 的生成算法可复现”类 RSA 题,而不是依赖分解难题。 - 标准 RSA 收尾:
phi=(p-1)*(q-1)、d=invert(e,phi)、m=pow(c,d,n)、long_to_bytes(m)得 flag。
触发条件
- RSA 题给出
n、e、c,同时给出myprime()一类“用排列/组合计数生成 p”的源码或描述。 - 字符表长度、模式集合、计数规则可复现(或可从源码读出);
nextprime的行为明确。 p只由该计数决定,n = p*q且 q 为普通素数;没有其他隐藏随机性。- 允许用 Python
math.factorial/sympy.nextprime/gmpy2做高精度计算。
利用步骤
- 读
myprime():确认字符表长度、模式列表、计数条件、nextprime的调用位置。 - 用“块 + 容斥”推导
real_n;文章直接给出62!*63*4 - 4*58!*59*60 + 54!*55*56*57。若字符表/模式不同,按同样结构重算(必要时用小规模暴力校验公式)。 p = nextprime(real_n);q = n // p;检查p*q == n。phi=(p-1)*(q-1);d=invert(e,phi);m=pow(c,d,n);long_to_bytes(m)。- 若
nextprime结果不整除 n,尝试prevprime/邻近素数,或检查公式的边界(模式是否可重叠、是否允许重复字符)。
PoC
import gmpy2
from sympy import nextprime, factorial
from Crypto.Util.number import long_to_bytes
n = 10179374723747373757354331803486491859701644330006662145185130847839571647703918266478112837755004588085165750997749893646933873398734236153637724985137304539453062753420396973717
c = 1388132475577742501308652898326761622837921103707698682051295277382930035244575886211234081534946870195081797116999020335515058810721612290772127889245497723680133813796299680596
e = 65537
# 文章用容斥公式直接算 myprime() 的计数(不用跑 62! 全排列)
real_n = factorial(62) * 63 * 4 - 4 * factorial(58) * 59 * 60 + factorial(54) * 55 * 56 * 57
p = nextprime(real_n)
q = n // p
assert p * q == n
phi = (p - 1) * (q - 1)
d = gmpy2.invert(e, phi)
flag = long_to_bytes(pow(c, d, n))
print(flag)
变体与关联
- 计数结构变体:模式长度/数量不同、字符表有重复字符、模式可重叠/不可重叠;容斥的系数和阶乘项需按实际重算,必要时用 DP/自动机计数替代闭式。
- 素数生成变体:
nextprime(num)、prevprime(num)、num附近偏移、sympy.nextprime与自定义 Miller-Rabin 的差异;先验证p*q==n。 - RSA 收尾变体:若
e与phi不互素,需用e的因子/AMM 开根;若 n 有多个因子,先分解再逐个求逆。 - 关联:[[crypto-rsa-pell-equation-prime-generation]](另一类结构化 p 生成)、[[crypto-rsa-next-prime-square-moduli-continued-fraction]](next-prime 结构)、[[crypto-rsa-prime-bit-chunks-multivariate-coppersmith-tiered]](p 的比特/结构线索)、[[crypto-rsa-hidden-e-prime-counting-close-prime]](用素数计数恢复参数)。
- 边界:若
myprime还混入随机数/时间/隐藏表,计数不可复现,本链不成立;若n不是两个素数之积,q=n//p不成立。
检测与防御
- 题目设计视角:不要用“可复现的计数/公式”生成 RSA 素数 p;p 必须来自密码学安全的随机源。
- 审计:检查 RSA 密钥生成代码是否
p = nextprime(f(public_data))一类可预测结构;用已知算法复算 p 并验证 n。 - 检测:CTF 中先看
n是否有结构化因子;若 p 由计数生成,重算real_n与nextprime通常即可分解。 - 说明:本文为 CTF 数学题解法,不是现实漏洞;公式中的系数依赖题目字符表/模式,换题需重新推导。