Schmidt-Samoa 密码系统:已知 N、c、d 用 gcd(a^{Nd}-a,N) 恢复 pq 并解密
crypto/rsa · verified
一句话结论
Schmidt-Samoa 密码系统使用 N=p^2·q、私钥 d=N^{-1} mod λ(pq)、加密 c=m^N mod N、解密 m=c^d mod pq。一旦攻击者同时拿到 N、c、d,由 N·d ≡ 1 (mod λ(pq)) 可知 a^{N·d} ≡ a (mod pq),于是 gcd(N, a^{N·d}-a) 给出 pq,再用 c^d mod pq 即可恢复明文。
原理
- 密钥生成:
N=p^2·q,d = N^{-1} mod lcm(p-1,q-1);公钥是N(加密指数即N),私钥是d,加密c = m^N mod N,解密m = c^d mod pq。 - 因为
N·d ≡ 1 (mod λ(pq)),对任意与pq互素的a,由 Carmichael 定理a^{λ(pq)} ≡ 1 (mod pq),所以a^{N·d} = a·(a^{λ(pq)})^t ≡ a (mod pq)。 - 因此
pq | a^{N·d}-a;而N=p^2·q也包含因子pq。计算g = gcd(N, a^{N·d}-a),结果通常是pq(若同时被p^2整除则可能是N,换一个底数a重试即可)。 - 得到
pq后,c^d = m^{N·d} ≡ m (mod pq),直接解出明文m。 - 私钥
d本应保密;该场景说明在 Schmidt-Samoa 中泄露d等价于泄露pq,系统随即被完全解密,而不是像标准 RSA 那样只泄露一个指数。
触发条件
- 目标使用 Schmidt-Samoa 密码系统:
N=p^2·q,加密指数为N,解密模数为pq。 - 攻击者已知
N、目标密文c,以及私钥d(例如密钥文件泄露、调试接口返回、CTF 题目直接给出)。 - 能计算大整数模幂与 gcd;
N的规模在可计算范围内。 a与pq互素(取 2、3、5 等小素数通常满足)。
利用步骤
- 确认
N的结构为p^2·q(可通过题目描述或N的因子分布判断),并确认加密/解密公式。 - 取小底数
a=2,计算mid = pow(a, N*d, N) - a。 - 计算
g = gcd(N, mid);若g等于N,换a=3,5,7…重试,直到1 < g < N。 - 令
n = g(应为pq),计算m = pow(c, d, n)。 - 将
m转字节得到明文;用pow(m, N, N) == c或题目格式校验。
PoC
import math
from Crypto.Util.number import long_to_bytes
c = ...
N = ...
d = ...
a = 2
mid = pow(a, N * d, N) - a
n = math.gcd(N, mid)
m = pow(c, d, n)
print(long_to_bytes(m))
若
gcd返回N,说明该底数同时命中了p^2因子,换a=3,5,…再试;也可以对多个底数的 gcd 结果取交/比较。
变体与关联
- 变体:若只泄露
d而不泄露c,仍可用gcd恢复pq,进而分解N=p^2·q,之后可解密任意密文。 - 变体:Schmidt-Samoa 的签名/加密变体可能使用不同的指数关系,但“
d泄露 →pq泄露”的核心不变。 - 关联:[[crypto-rsa-rabin-random-square-root-oracle]](解密预言机导致分解)、[[crypto-rsa-common-modulus]](RSA 参数复用)、[[crypto-rsa-partial-prime-high-bits-coppersmith]](分解
N的其他路径)。
检测与防御
- 防御:Schmidt-Samoa 的私钥
d必须与标准 RSA 私钥同等保护,绝不能出现在日志、调试接口或客户端。 - 防御:优先使用标准 RSA-OAEP 等经过广泛分析的方案;自制密码系统需经过形式化安全证明与代码审计。
- 检测:审计
N是否为完全平方因子结构(N可被p^2整除)、私钥材料是否泄露、接口是否返回d或可推导d的字段。 - 响应:确认
d泄露后立即轮换密钥,并假定该密钥下所有历史密文均可被解密。