素数域矩阵 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,需改用矩阵阶或特征多项式求解)。
利用步骤
- 从输出取
p、e、矩阵B。 d = inverse(e, p-1)。- 在
GF(p)上计算A = B^d。 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做可对角化检查。