RSA 隐藏私钥指数 c 的多项式导数泄露:量级差恢复系数 + 枚举 8-bit k
crypto/rsa · verified
一句话结论
题目把 RSA 私钥指数 c 藏在三次多项式 f(x)=x^3-a x^2+b x-c-k n 的常数项里,只泄露某点 x1 的一阶导数;由于 x1 是 511 bit 而 a,b 只有约 120 bit,2a x1 压倒 b,可由导数恢复 a,b,再把 c 写成 x1^3-a x1^2+b x1-k n,枚举 k 的全部 8-bit 素数并检查明文前缀即可解出。
原理
- RSA 结构:
e = inverse(c, phi),cipher = m^e mod n;只要恢复c,就有m = cipher^c mod n。 - 多项式与导数:
f(x) = x^3 - a x^2 + b x - c - k n,f'(x) = 3x^2 - 2a x + b。题目输出x1与deriv1_num = f'(x1)。 - 量级差:
x1约 511 bit,a,b约 120 bit,因此2a x1远大于b。令T = 3x1^2 - deriv1_num = 2a x1 - b,则a = floor(T/(2x1)) + 1(b只是小修正),b = deriv1_num - 3x1^2 + 2a x1。 - 恢复 c:由
f(x1) = 0 mod n得c = x1^3 - a x1^2 + b x1 - k n(在整数上成立,k为多项式构造时的乘数)。 - 枚举 k:
k = getPrime(8),即 8-bit 素数,只有几十个。对每个k计算c,再算m = cipher^c mod n,检查明文是否以已知 flag 前缀开头;唯一命中即正确。 - 为什么可行:直接枚举
c是 1024-bit 空间不可行;但导数泄露把a,b固定,c只随 8-bitk变化,搜索空间从 2^1024 降到几十次模幂。 - 注意:
a的取整方向依赖b的符号/大小;用b回代验证deriv1_num是否一致,必要时在floor附近微调。
触发条件
- RSA 使用自定义指数关系
e = inverse(c, phi),且c被嵌入某个含n倍数的多项式。 - 题目泄露多项式在某点的导数值,且
x1与系数a,b存在明显量级差。 k是小空间参数(如 8-bit 素数),可枚举。- 已知明文前缀(如
flag{)用于唯一筛选。 - 攻击者能拿到
n、e、cipher、x1、deriv1_num。
利用步骤
- 由
T = 3*x1*x1 - deriv1_num,计算a = T // (2*x1) + 1,再回代b = deriv1_num - 3*x1*x1 + 2*a*x1。 - 验证
3*x1^2 - 2*a*x1 + b == deriv1_num;若不等,在a附近枚举 ±1 修正。 - 对
k取 8-bit 素数(primerange(2,256)),计算c = x1^3 - a*x1^2 + b*x1 - k*n。 - 计算
m = pow(cipher, c, n),转字节并检查是否以flag{/xmctf{等前缀开头。 - 命中后输出明文;若多个候选,增加前缀长度或检查可打印性。
PoC
from sympy import primerange
n = ...; x1 = ...; deriv1_num = ...; cipher = ...
T = 3 * x1 * x1 - deriv1_num
a = T // (2 * x1) + 1
b = deriv1_num - 3 * x1 * x1 + 2 * a * x1
assert 3 * x1 * x1 - 2 * a * x1 + b == deriv1_num
for k in primerange(2, 256):
c = x1 ** 3 - a * x1 ** 2 + b * x1 - k * n
m = pow(cipher, c, n)
msg = m.to_bytes((m.bit_length() + 7) // 8, "big")
if msg.lower().startswith(b"xmctf{"):
print(k, msg.decode())
break
# 例:k=173,明文 xmctf{e6d787beb9230217e692e130f718cdeb}
变体与关联
- 多项式变体:三次式可换成二次/四次,只要导数泄露足以恢复除
c外的系数;量级差是关键。 - 参数变体:
k可换成小范围整数、小素数、时间戳等;搜索空间越大越需要更多泄露。 - 关联:[[crypto-rsa-e3-small-plaintext-integer-cube-root]](小指数直接开方)、[[crypto-rsa-franklin-reiter-affine-related-message]](相关明文 GCD)、[[crypto-rsa-partial-plaintext-high-bits-coppersmith]](部分明文泄露)。
检测与防御
- 检测:自定义 RSA 实现中指数由隐藏参数派生;题目/接口泄露多项式系数或导数值;
k等参数空间过小。 - 防御:使用标准 RSA 密钥生成(
e=65537,随机d),不要把私钥指数嵌入可泄露的代数结构;避免小参数空间;使用 OAEP 填充。 - 加固:对错误信息/调试输出做脱敏;密钥材料不要参与可被观测的多项式运算;定期轮换密钥。