RSA 模数本身是素数时 φ(n)=n-1 直接求 d 解密
crypto/rsa · verified
一句话结论
若题目/实现把 n 直接取成一个 1024 位素数(n = getPrime(1024) 而不是 p*q),则 φ(n) = n-1,任何人拿到 n 就能求 d = e^{-1} mod (n-1) 并直接解密,无需分解。
原理
- RSA 解密依赖
m^{ed} ≡ m (mod n),其成立条件是ed ≡ 1 (mod λ(n)),而λ(n)由n的因子结构决定(n=pq时φ=(p-1)(q-1))。 - 当
n本身是素数时,Z_n的乘法群阶为n-1,即φ(n)=n-1;因子结构完全已知(n就是它自己),安全性归零。 - 因此攻击者只需做一次素性判断确认
n是素数(或发现试除到√n都没有因子、gcd类分解全部失败),就能立刻算出私钥。 - 为什么容易误判:出题/实现脚本常写
n = getPrime(k)图省事,而n的位长、e、c与正常 RSA 完全一致,只有做过素性检验才能发现。
触发条件
- 给定
n, e, c,且isPrime(n)为真(或n为素数幂,需按φ(p^k)=p^{k-1}(p-1)处理); e与φ(n)互素(否则需先求gcd(e, φ)再处理不可逆情形);- 明文
m < n,否则需注意m被截断。
利用步骤
- 对
n做素性检验:is_prime(n)、Miller-Rabin 或sympy.factorint(n)。 - 令
phi = n - 1,求d = inverse(e, phi)。 m = pow(c, d, n),long_to_bytes(m)即明文。- 若
n是素数幂p^k,先开方求p,再phi = p**(k-1)*(p-1)。
PoC
from Crypto.Util.number import long_to_bytes, inverse, isPrime
n = 150624321883406825203208223877379141248303098639178939246561016555984711088281599451642401036059677788491845392145185508483430243280649179231349888108649766320961095732400297052274003269230704890949682836396267905946735114062399402918261536249386889450952744142006299684134049634061774475077472062182860181893
e = 65537
c = 22100249806368901850308057097325161014161983862106732664802709096245890583327581696071722502983688651296445646479399181285406901089342035005663657920475988887735917901540796773387868189853248394801754486142362158369380296905537947192318600838652772655597241004568815762683630267295160272813021037399506007505
assert isPrime(n) # 确认模数本身是素数
d = inverse(e, n - 1) # φ(n) = n - 1
print(long_to_bytes(pow(c, d, n)))
变体与关联
- 变体:
n = p^2时φ = p(p-1),先对n开平方;n为多素数乘积时需分解。 - 变体:
n是素数但e与n-1不互素,需用e的因子分组求解(类似 Rabin)。 - 关联:[[crypto-rsa-perfect-square-modulus-p-squared]](素数平方模数)、[[crypto-rsa-phi-divisor-factoring-multiprime-power]](多素数 φ)。
- 边界:
n为合数时本卡不成立;但即使n合数,若给出的是「错误 φ」也可用φ反推因子,思路一致。
检测与防御
- 检测(CTF/审计视角):生成脚本中
n未由两素数相乘得到;对n做素性检验即可发现。 - 防御(实现视角):用成熟库生成密钥(OpenSSL/
rsa.generate_private_key),并对生成的n做「不是素数、不是素数幂、不是完全平方」的自检;密钥生成后校验p*q == n。