RSA 已知 m^e 与 m^(p+q):扩展欧几里得线性组合直接恢复明文
crypto/rsa · verified
一句话结论
同一 RSA 模数下若同时给出 ct1 = m^e mod N 和 ct2 = m^(p+q) mod N,由 φ(N)=N+1-(p+q) 与欧拉定理可得 m^(N+1) ≡ ct2 (mod N);再用扩展欧几里得求 a*e + b*(N+1) = 1,即可用 ct1^a * ct2^b mod N 直接还原 m,无需分解 N。
原理
- RSA 中
φ(N) = (p-1)(q-1) = N + 1 - (p+q)。 - 若
gcd(m,N)=1,欧拉定理给出m^φ(N) ≡ 1 (mod N),即m^(N+1-(p+q)) ≡ 1,两边乘m^(p+q)得m^(N+1) ≡ m^(p+q) = ct2 (mod N)。 - 已知
ct1 = m^e,且ct2 = m^(N+1);只要gcd(e, N+1)=1,扩展欧几里得可求整数a,b使a*e + b*(N+1) = 1。 - 于是
m = m^(a*e + b*(N+1)) = ct1^a * ct2^b mod N;指数为负时用模逆(Python 3.8+ 的pow(base, -exp, N)直接支持)。 - 更一般地:只要拿到同一明文的两个幂
m^x、m^y且gcd(x,y)=1,就能用 Bézout 系数把m^1线性组合出来;本题x=e、y=N+1。 - 边界:若
gcd(m,N)>1,欧拉定理不再直接成立,但此时gcd(m,N)已经泄露 N 的因子,可改用分解路线。
触发条件
- 同一 RSA 模数 N 下加密同一明文两次,分别泄露
m^e与m^(p+q)(或m^φ、m^(N+1)等等价幂)。 gcd(e, N+1)=1(本题 e=65537 与 N+1 互素)。- 明文未使用随机填充,两次输出对应同一 m。
- 目标未对同态线性组合做防护(纯 textbook RSA)。
利用步骤
- 确认两组密文
ct1、ct2对应同一明文与同一 N,且指数分别为 e 与 p+q。 - 由
φ=N+1-(p+q)推出m^(N+1) ≡ ct2。 - 用扩展欧几里得求
a*e + b*(N+1) = 1。 - 计算
m = ct1^a * ct2^b mod N(负指数转模逆)。 long_to_bytes(m)得到 flag;若结果异常,检查 gcd(m,N) 是否泄露因子。
PoC
from Crypto.Util.number import long_to_bytes
def egcd(a, b):
if a == 0:
return (b, 0, 1)
g, x1, y1 = egcd(b % a, a)
return (g, y1 - (b // a) * x1, x1)
g, a, b = egcd(e, N + 1) # a*e + b*(N+1) = 1
msg = (pow(ct1, a, N) * pow(ct2, b, N)) % N
print(long_to_bytes(msg).decode())
完整数据代入(原文 N、ct1、ct2、e=65537)可解出:
ISCTF{Congratulations_you_master_Mathematical_ability}
变体与关联
- 指数变体:
m^(p-q)、m^φ、m^(N-1)等只要与e互素,都能用同一 Bézout 组合恢复;若两个指数不互素,只能得到m^gcd(x,y)。 - 若第二个幂未知但知道 φ 或 p+q,可先按 [[crypto-rsa-known-prime-sum-quadratic-factorization]] 分解 N,再常规解密。
- 关联:[[crypto-rsa-common-modulus]](同模数不同指数)、[[crypto-rsa-franklin-reiter-affine-related-message]](相关明文)。
- 边界:带随机填充或两次明文不同(如 OAEP)时攻击失效。
检测与防御
- 检测:同一 N 下出现两个相关幂的密文;CTF 中检查
ct2是否等于m^(p+q)、m^φ等。 - 防御:使用 OAEP/PKCS#1 v1.5 等随机化填充;不要泄露同一明文的多个幂;避免 textbook RSA 直接加密。
- 加固:若必须多 exponent,使用互素指数并加随机化;轮换密钥,避免 p+q/φ 通过侧信道或调试输出泄漏。