♧ Godown 安全知识树

矩阵 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 成立)。

利用步骤

  1. 从题目读取 e、n、C(6×6 整数矩阵),计算 e.bit_length() 与 n.bit_length(),确认 e ≈ n^4。
  2. 令 N = n^4,用 Boneh-Durfee(delta 取 0.18~0.22,m 从小到大尝试)求 d:构造 pol = 1 + x*(A + y)、A=(N+1)//2,LLL 后取短向量求结式。
  3. 用求得的 d 计算 M = C^d mod n(Sage:C = matrix(Zmod(n), C); M = C^d)。
  4. 按 M[i,j] 的顺序 long_to_bytes 并拼接,得到 flag。
  5. 若 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。