矩阵 RSA 私钥 d 偏小:e 约为 n^4 时以 N=n^4 近似隐藏模数跑 Boneh-Durfee 恢复 d
crypto/rsa · verified
一句话结论
题目把 flag 分成 36 段构造 6×6 矩阵 M(元素在 Z_n 中),按 RSA 方式计算 C = M^e,其中 e = d⁻¹ mod φ、φ 未公开;e 长 4093bit(约等于 n^4,而 n 为 1024bit),d 仅 920bit。由于 e 远大于 n,说明隐藏的 φ 与 n^4 同量级而非 φ(n);以 N=n^4 作为 Boneh-Durfee 的近似模数(d/N≈0.2246 < 0.292)可恢复 d,再计算 M = C^d 并按 16 字节分段还原 flag。
原理
- 矩阵 RSA:元素取自
Z_n的 6×6 矩阵构成乘法半群;C = M^e是矩阵快速幂。若e·d ≡ 1 (mod ord(M)),则C^d = M^{e·d} = M,与标量 RSA 的解密条件同构。 - 隐藏模数:
e = inverse(d, φ)返回小于φ的值。本场景e有 4093bit、n只有 1024bit,故φ > e ≈ n^4,不可能是φ(n)(约 1024bit)。实际φ是题目自定义的、约n^4量级且与n互素的数(可能是某个矩阵群阶/其倍数),未公开。 - Boneh-Durfee 的模数选择:BD 需要
e·d - 1 = k·φ'且已知/可近似φ'。把N = n^4当作φ'的近似,构造f(x,y)=1+x(A+y)、A=(N+1)/2;x=2k、y=-(p'+q')/2形式的根在小范围内时,LLL + 结式可解出x、y,进而d=(1+x(A+y))/e。 - 小私钥条件:
d为 920bit,N=n^4为 4096bit,d/N ≈ 0.2246,低于 BD 的N^0.292上界;因此即便φ不是标准φ(N),只要它与n^4的差落在 BD 的误差界内,仍有机会恢复d。 - 解密:得到
d后C^d = M,按M[i,j]的 16 字节块顺序拼接即得 flag。
触发条件
- 题目以矩阵幂代替标量模幂,
n已知、e已知、φ隐藏。 e的位长明显大于n(本例约n^4),提示隐藏模数约为n^4;若错用φ(n)或n做 BD 会失败。d相对该近似模数足够小(d < N^0.292,本例 0.2246)。- 有 Sage 的 Boneh-Durfee 实现或等价格脚本;矩阵在
Z_n上可逆(或至少M^{ed}=M成立)。
利用步骤
- 从题目读取
e、n、C(6×6 整数矩阵),计算e.bit_length()与n.bit_length(),确认e ≈ n^4。 - 令
N = n^4,用 Boneh-Durfee(delta 取 0.18~0.22,m从小到大尝试)求d:构造pol = 1 + x*(A + y)、A=(N+1)//2,LLL 后取短向量求结式。 - 用求得的
d计算M = C^d mod n(Sage:C = matrix(Zmod(n), C); M = C^d)。 - 按
M[i,j]的顺序long_to_bytes并拼接,得到 flag。 - 若 BD 无解,先核实
e的位长是否对应n^4;可尝试N=n^k(k 由e与n的位长比推断)或调整delta/m/t。
PoC
# Sage
from Crypto.Util.number import long_to_bytes
e = 75759282367368799544583457453768987936939259860144125672621728877894789863642594830153210412190846168814565659154249521465974291737543527734700545818480398345759102651419148920347712594370305873033928263715201812217658781693392922382633382112810845248038459857654576967447255765379492937162044564693535012144718871564964154729561032186045816489683161588345299569985304078255628527588710513640102450308662163641732851643593090646321420800552303398630738674858967724338819227042384745213425656939930135311339542647104499427215254435723921505189649944059658797193927706249542240737884739119223756635540945563449010120382834036979025801446796614280064172405549502694658175837126702821804106928800917035327292099385809060363635737715320709749444795680950552240184529017581997661357846852201424248086080872655164246614710423850620222735225702427025180018637830386631573912505087046428427137407828859500285127835020183526681560129322020299774376860830513167598911105104946612301909005028216010756378307303924865571457872055817289904093797943893894249094212422766513999129665299858860878710920689322752152527130981697461526170099006972245891313788064563118647308122107999430867808150749979046611265769861111738145184897880080810883790769899
n = 99231341424553040688931525316017803824870567327100041969103204566938549582832516706206735181835068382521133899811339836861525260134721134887446163174620592328661881621312114348726944317349680760092960665800660405612177225373482880941142930135489885221592416840149732795379174704611605960303340578163595465083
C = [...] # 原文 6x6 矩阵
d = 5625392240871591703674913289176493449351554576001933379885655076380379121373730939272476349026135584314461774818575210968383018641741768873055290364913313885973206167937229668741817076803184617448123799781711736443720192213454840474648356266384085300527439223289199819331996099 # BD 求得
C = matrix(Zmod(n), C)
M = C ** d
for i in range(6):
for j in range(6):
print(long_to_bytes(M[i, j]), end="")
Boneh-Durfee 侧只需把标准脚本的 modulus 设为 N = n**4、delta 取 0.18~0.22、m 逐步增大;原文给出完整脚本但将其注释,最终以硬编码 d 解出 flag。
变体与关联
- 若
e ≈ n^k,可尝试N = n^k作为 BD 模数;k由e.bit_length() / n.bit_length()估计。 - 若
d不够小,考虑d部分位泄露、CRT 提示、多密钥等格攻击。 - 标量 RSA 的小
d标准攻击见 [[crypto-rsa-boneh-durfee-small-private-exponent]];本卡的区别是模数不是已知的n而是由e的位长推断的n^4。
检测与防御
- 该场景是 CTF/自定义密码体制,核心防御是不要使用过小的私钥指数:
d必须与模数同量级,避免落入N^0.292。 - 不要把自定义
φ当作秘密来支撑安全性;RSA 安全性依赖分解困难,而非隐藏群阶。 - 矩阵幂等自定义方案应明确群阶并证明解密正确性;实现上使用成熟库的标准 RSA。