♧ Godown 安全知识树

素数域矩阵 RSA:d=e^{-1} mod (p-1) 对密文矩阵求幂还原明文

crypto/rsa · verified

一句话结论

把明文放进 2×2 矩阵 A 的一个元素、在 GF(p)(p 为素数)上计算 B = A^e 的「矩阵 RSA」,在 A 可对角化且特征值落在 GF(p) 时满足 A^{p-1} = I,因此取 d = e^{-1} mod (p-1)、计算 B^d 即可还原 A 读出明文。

原理

  • 加密是群上的幂运算:A ∈ M_2(GF(p)),B = A^e。要解密就是求 e 在 A 所属循环子群中的逆元 d,使 A^{ed} = A。
  • 若 A 在 GF(p) 上可对角化,A = P·diag(λ1, λ2)·P^{-1},且 λ1, λ2 ∈ GF(p)^{*},则 λ_i^{p-1} = 1(费马小定理),于是 A^{p-1} = P·diag(1,1)·P^{-1} = I。
  • 所以 ed ≡ 1 (mod p-1) 时 A^{ed} = A^{1+k(p-1)} = A·(A^{p-1})^k = A,直接用标量 φ = p-1 求逆即可解出。
  • 严格来说 GL(2,p) 的阶是 (p^2-1)(p^2-p),特征值可能落在 GF(p^2)(此时需 A^{p^2-1}=I);本题 p ≡ ?、矩阵随机,约一半概率特征值在 GF(p) 内,出题人正是依赖这一情形,故不是对所有矩阵都成立。
  • 明文放在 A[0][0],故解密后取 B^d[0][0] 转字节即可。

触发条件

  • 加密在素数域 GF(p) 上做矩阵幂,p 公开;
  • e 与 p-1 互素(可求逆);
  • A 可对角化且特征值在 GF(p) 中(否则 A^{p-1} ≠ I,需改用矩阵阶或特征多项式求解)。

利用步骤

  1. 从输出取 p、e、矩阵 B。
  2. d = inverse(e, p-1)。
  3. 在 GF(p) 上计算 A = B^d。
  4. long_to_bytes(int(A[0][0])) 得明文。

PoC

from Crypto.Util.number import long_to_bytes, inverse
from sage.all import GF, matrix

e = 65537
p = 8147594556101158967571180945694180896742294483544853070485096002084187305007965554901340220135102394516080775084644243545680089670612459698730714507241869
B = [[2155477851953408309667286450183162647077775173298899672730310990871751073331268840697064969968224381692698267285466913831393859280698670494293432275120170,
      4113196339199671283644050914377933292797783829068402678379946926727565560805246629977929420627263995348168282358929186302526949449679561299204123214741547],
     [3652128051559825585352835887172797117251184204957364197630337114276860638429451378581133662832585442502338145987792778148110514594776496633267082169998598,
      2475627430652911131017666156879485088601207383028954405788583206976605890994185119936790889665919339591067412273564551745588770370229650653217822472440992]]

P = GF(p)
d = inverse(e, p - 1)
A = matrix(P, B) ** d
print(long_to_bytes(int(A[0][0])))

变体与关联

  • 变体:若 A^{p-1} ≠ I(特征值在 GF(p^2)),需用 A 的特征多项式求其在 GL(2,p) 中的阶,或直接在 GF(p^2) 上解离散对数。
  • 变体:模数换成合数 n 且 φ(n) 未知 → 退化为「矩阵 RSA 隐藏 φ」,需 Boneh-Durfee 类格攻击。
  • 关联:[[crypto-rsa-matrix-rsa-hidden-phi-n4-boneh-durfee]](矩阵 RSA + 隐藏 φ 的格攻击)、[[crypto-rsa-prime-modulus-phi-n-minus-1]](同源「φ 取值错误」思路)。
  • 边界:e 与 p-1 不互素时需分解 e 或改用扩展欧几里得的多解处理。

检测与防御

  • 检测(CTF 视角):看到 matrix(P, ...) ** e 且模数为素数,先试 d = e^{-1} mod (p-1)。
  • 防御(实现视角):不要自造矩阵 RSA;若必须用,密钥生成阶段应明确群阶(|GL(2,p)|)并校验 A^{ed} = A,同时对 A 做可对角化检查。