结构化素数 p=s²+s+3 与椭圆曲线阶泄露:模平方根枚举 t 恢复 p 并解 AES-CTR
ctf/crypto · verified
一句话结论
当私钥素数具有 p = s² + s + 3(s 为约 256 位)的结构,且程序泄露 gift = E.order() mod mod(mod 也是约 256 位素数)时,利用 Hasse 定理把 E.order 近似为 p,在模 mod 下解二次方程 s² + s − (gift−3) ≡ 0(判别式 D = 1 + 4R,用 Tonelli-Shanks 求模平方根),得到两个残类后在合理位宽内枚举少量 t,即可恢复 p;再用 long_to_bytes(p)[:16] 作 AES-CTR 密钥解密 flag 密文。
原理
- 结构化素数:
p = s(s+1) + 3,s为 256-bit 随机数,p约 512-bit。已知p就等价于已知s,而s ≈ √p。 - 椭圆曲线阶泄露:程序计算某条曲线(isogeny 后)的阶
E.order()并对 256-bit 的mod取余输出gift。Hasse 定理给出|#E(F_p) − (p+1)| ≤ 2√p,因此E.order ≈ p;在模mod下可近似认为p ≡ gift (mod mod)(误差项1−t相对mod很小,必要时对少量偏移枚举)。 - 模二次方程:由
p − 3 = s(s+1)得s² + s − (gift−3) ≡ 0 (mod mod)。判别式D = 1 + 4·(gift−3);若mod为素数且D是二次剩余,Tonelli-Shanks 求出sqrt(D) mod mod,两个根为s ≡ (−1 ± sqrt(D)) · 2⁻¹ (mod mod)。 - 枚举真实 s:真实
s约在[2^255, 2^257),而mod也是 256-bit,故s = s_res + t·mod中t的范围很小(通常 0..几)。对每个候选计算p = s(s+1)+3,按位宽/素性/AES 解密结果筛选。 - AES key 派生:程序用
long_to_bytes(p)[:16]作为 AES 密钥,AES.MODE_CTR使用给定 8 字节 nonce(PyCryptodome 默认 counter=0);对每个候选p尝试解密,命中QnQSec{/flag{即正确。 - 为什么成立:泄露把 512-bit 的
p压缩成 256-bit 模方程的两个残类;结构化又把剩余搜索空间压到个位数候选,整体从 2^512 降到多项式级。
触发条件
- 已知
gift、mod、AES-CTR 密文 c、nonce,且mod为素数(或至少能求模平方根)。 - 私钥素数满足可写成
s² + s + 3(或类似低次多项式)的结构,s位宽与mod相当。 - 泄露值来自
E.order() mod mod,且 Hasse 误差相对mod可忽略或可枚举。 - AES 密钥直接取
long_to_bytes(p)的前 16 字节;CTR 的 nonce 已知,counter 初值可推断(常为 0)。 - 有 Tonelli-Shanks/模平方根与大整数运算能力。
利用步骤
- 从题目代码确认素数结构
p = pp^2 + pp + 3、gift = int(E_.order()) % mod、AES key=long_to_bytes(p)[:16]、AES.MODE_CTR(nonce=...)。 - 计算
R = (gift − 3) mod mod、D = (1 + 4R) mod mod;用 Tonelli-Shanks 求sqrtD = D^((mod+1)/4) mod mod(mod ≡ 3 mod 4时)或通用算法。 - 计算
inv2 = pow(2, -1, mod),得到两个残类s0 = (−1 + sqrtD)·inv2 mod mod、s1 = (−1 − sqrtD)·inv2 mod mod。 - 对每个残类,按
s的预期位宽(如[2^255, 2^257))计算t_min/t_max,枚举t得到候选s = s_res + t·mod,再算p = s(s+1)+3。 - 过滤:
p位宽合理、素性测试通过(可选);用long_to_bytes(p)[:16]作 key、给定 nonce 解 AES-CTR,检查明文是否含 flag 前缀。 - 命中后输出 flag;若 Hasse 误差不可忽略,对
gift附近的小偏移(±1, ±2, ...)重复步骤 2-5。
PoC
from Crypto.Util.number import long_to_bytes
from Crypto.Cipher import AES
def tonelli_shanks(n, p):
n %= p
if n == 0: return 0
if p % 4 == 3:
x = pow(n, (p + 1) // 4, p)
return x if x * x % p == n else None
# 通用 Tonelli-Shanks:分解 p-1=q*2^s,找非剩余 z,迭代求根
q, s = p - 1, 0
while q % 2 == 0:
q //= 2; s += 1
z = 2
while pow(z, (p - 1) // 2, p) != p - 1:
z += 1
m, c, t, r = s, pow(z, q, p), pow(n, q, p), pow(n, (q + 1) // 2, p)
while t != 1:
i, t2 = 0, t
while t2 != 1:
t2 = t2 * t2 % p; i += 1
b = pow(c, 1 << (m - i - 1), p)
m, c = i, b * b % p
t, r = t * c % p, r * b % p
return r
R = (gift - 3) % mod
D = (1 + 4 * R) % mod
sqrtD = tonelli_shanks(D, mod)
inv2 = pow(2, -1, mod)
for s_res in {((-1 + sqrtD) * inv2) % mod, ((-1 - sqrtD) * inv2) % mod}:
lo, hi = 1 << 255, 1 << 257
for t in range((lo - s_res) // mod, (hi - s_res) // mod + 2):
s = s_res + t * mod
p = s * (s + 1) + 3
key = long_to_bytes(p)[:16]
pt = AES.new(key, AES.MODE_CTR, nonce=nonce).decrypt(c)
if b"QnQSec{" in pt or b"flag{" in pt:
print(pt)
变体与关联
- 变体:
E.order与p的偏差(Hasse 误差、同源映射引入的小因子)不可忽略时,枚举gift + δ的小δ再解方程。 - 变体:结构化素数可能是
p = a·s² + b·s + c、p = s² + 1、p = P(B−1)² + B·S²等;都在模mod下化为一元二次/低次方程。 - 关联:[[crypto-rsa-structured-modulus-b-minus-one-square-e8-sqrt]](另一类结构化模数恢复)、[[crypto-rsa-perfect-square-modulus-p-squared]](完全平方模数)、[[ctf-crypto-small-discrete-log-crt-channel-selection]](模方程 + 小范围枚举思路)。
- 边界:
mod必须是素数才能用 Tonelli-Shanks(合数需分解或换算法);t范围随mod与s的位宽差增大;AES-CTR 的 counter 初值不对会导致解密失败。
检测与防御
- 检测(CTF):题目给出
gift = E.order() % mod、prime 结构与 AES-CTR 参数;先验证D的二次剩余性,再枚举t。 - 修复(真实设计):不要用可预测结构的素数;密钥不要直接取素数字节;使用标准 KDF(HKDF)派生 AES 密钥并配合随机 nonce/认证加密。
- 加固:泄露曲线阶时避免与私钥素数产生可解模方程;对敏感参数做白盒/常量时间处理,避免侧信道与结构泄露。