Wiener攻击
RSA公钥加密算法中：
- 两个大素数\(p\)和\(q\)，\(N = p \cdot q\)
- 欧拉函数\(\phi(N) = (p-1)(q-1)\)
- 公钥指数\(e\)，满足\(1 < e < \phi(N)\)且\(\gcd(e, \phi(N)) = 1\)
- 私钥指数\(d\)，满足\(e \cdot d \equiv 1 \pmod{\phi(N)}\)
即存在整数\(k\)，使得：
1. 近似关系
由于\(\phi(N) = N - (p+q) + 1\)，且\(p\)和\(q\)都很大，有：
\(
|\phi(N) - N| = |p+q-1| \approx 2\sqrt{N} \quad (\text{当 } p \approx q)
\)
2. 从(1)式推导
由(1)式：
\(
e \cdot d = k \cdot (N - (p+q-1)) + 1
\)
整理得：
\(
e \cdot d = k \cdot N + [1 - k \cdot (p+q-1)]
\)
设：
\(
s = p+q-1
\)
则：
3. 重要不等式
由(2)式两边除以\(d \cdot N\)：
取绝对值：
由于\(k \cdot s \approx k \cdot 2\sqrt{N}\)，且\(k \approx \frac{e \cdot d}{\phi(N)} \approx \frac{e \cdot d}{N}\)，有：
\(
|1 - k \cdot s| \approx |k \cdot s| \approx k \cdot 2\sqrt{N}
\)
代入得：
\(
\left| \frac{e}{N} - \frac{k}{d} \right| \approx \frac{k \cdot 2\sqrt{N}}{d \cdot N} = \frac{2k}{d \cdot \sqrt{N}}
\)
连分数逼近条件
连分数：https://www.cnblogs.com/luminescence/p/18646273
1. 连分数定理
定理：如果\(\left| \alpha - \frac{p}{q} \right| < \frac{1}{2q^2}\)，那么\(\frac{p}{q}\)是\(\alpha\)的连分数展开的一个收敛子。
2. 满足条件
我们需要证明：
\(
\left| \frac{e}{N} - \frac{k}{d} \right| < \frac{1}{2d^2}
\)
根据前面的近似：
\(
\frac{2k}{d \cdot \sqrt{N}} < \frac{1}{2d^2}
\)
即：
3. 估计k的范围
由(1)式：\(k = \frac{e \cdot d - 1}{\phi(N)}\)，由于\(e < \phi(N)\)且\(d < \phi(N)\)，有：
\(
k = \frac{e \cdot d}{\phi(N)} - \frac{1}{\phi(N)} < \frac{e \cdot d}{\phi(N)}
\)
通常e与N同数量级，而\(\phi(N) \approx N\)，所以：
\(
k \approx d
\)
4. 最终条件
将\(k \approx d\)代入(4)式：
\(
4d^2 < \sqrt{N} \quad \Rightarrow \quad d < \frac{1}{2} N^{1/4}
\)
得到Wiener定理：
Wiener定理：如果\(d < \frac{1}{3} N^{1/4}\)，那么\(\frac{k}{d}\)一定是\(\frac{e}{N}\)的连分数展开的一个收敛子。
攻击步骤
1. 计算连分数展开
对\(\frac{e}{N}\)进行连分数展开：
\(
\frac{e}{N} = a_0 + \frac{1}{a_1 + \frac{1}{a_2 + \frac{1}{\cdots}}}
\)
得到系数序列\([a_0, a_1, a_2, \dots]\)
2. 计算收敛子
收敛子序列为：
\(
\frac{p_0}{q_0}, \frac{p_1}{q_1}, \frac{p_2}{q_2}, \dots
\)
其中：
\(
\begin{aligned}
p_{-2} &= 0, \quad p_{-1} = 1 \\
q_{-2} &= 1, \quad q_{-1} = 0 \\
p_n &= a_n p_{n-1} + p_{n-2} \\
q_n &= a_n q_{n-1} + q_{n-2}
\end{aligned}
\)
3. 测试每个收敛子
对每个收敛子\(\frac{p_i}{q_i}\)：
- 设\(k = p_i\)，(d = q_i$
- 由(1)式计算\(\phi(N) = \frac{e \cdot d - 1}{k}\)
- 如果\(k\)不能整除\(e \cdot d - 1\)，跳过
- 否则，从\(\phi(N)\)恢复\(p\)和\(q\)
4. 从\(\phi(N)\)恢复\(p, q\)
由：
\(
\phi(N) = (p-1)(q-1) = N - (p+q) + 1
\)
得：
\(
p+q = N - \phi(N) + 1
\)
解二次方程：
\(
x^2 - (p+q)x + N = 0
\)
判别式：
\(
\Delta = (p+q)^2 - 4N
\)
如果\(\Delta\)是完全平方数，则找到整数解\(p\)和\(q\)。
5. 验证
验证：
\(
e \cdot d \equiv 1 \pmod{\phi(N)}
\)
如果成立，攻击成功。
实现
rsa_wiener_attack.py
"""
RSA小解密指数攻击 - 连分数方法当RSA的解密指数d较小时，可以通过连分数展开方法进行攻击。
如果d < (1/3) * N^(1/4)，则可以通过连分数方法恢复d。
"""import math
def extended_gcd(a, b):if a == 0:return b, 0, 1gcd, x1, y1 = extended_gcd(b % a, a)x = y1 - (b // a) * x1y = x1return gcd, x, ydef mod_inverse(a, m):gcd, x, _ = extended_gcd(a % m, m)if gcd != 1:raise ValueError()return (x % m + m) % mdef continued_fraction(numerator, denominator):"""计算分数的连分数表示返回连分数的系数列表"""cf = []a = numeratorb = denominatorwhile b != 0:quotient = a // bcf.append(quotient)a, b = b, a % breturn cfdef convergents_from_cf(cf):"""从连分数系数计算收敛子返回分子和分母的列表"""convergents = []if len(cf) == 0:return convergents# 初始化前两个收敛子p0 = cf[0]q0 = 1convergents.append((p0, q0))if len(cf) == 1:return convergentsp1 = cf[1] * cf[0] + 1q1 = cf[1]convergents.append((p1, q1))# 计算后续收敛子for i in range(2, len(cf)):p = cf[i] * p1 + p0q = cf[i] * q1 + q0convergents.append((p, q))p0, p1 = p1, pq0, q1 = q1, qreturn convergentsdef rsa_fraction_attack(N, e):"""使用连分数方法攻击RSA小解密指数如果找到小解密指数d，返回 (d, k)，否则返回 None"""print(f"开始对RSA(N={N}, e={e})进行连分数攻击...")cf = continued_fraction(e, N)print(f"e/N的连分数表示: {cf}...")convergents = convergents_from_cf(cf)print(f"收敛子数量: {len(convergents)}")for k, d in convergents:if k == 0:continue# 检查 d 是否可能为解密指数# 需要满足: e*d ≡ 1 (mod φ(N))# 但由于不知道φ(N)，我们使用 N-1 作为近似if d == 0:continue# 计算 ed - 1，应该等于 k*φ(N)ed_minus_1 = e * d - 1# 尝试分解 ed_minus_1 来找到φ(N)的可能值# 如果 ed - 1 = k * φ(N)，那么 φ(N) = (ed - 1)/kphi = ed_minus_1 // kif k * phi != ed_minus_1:continue # 不是整除# 尝试从φ(N)恢复p和q# 对于N = p*q，有φ(N) = (p-1)(q-1) = N - p - q + 1# 所以 p + q = N - φ(N) + 1s = N - phi + 1 # p + qdiscriminant = s * s - 4 * Nif discriminant < 0:continuesqrt_discriminant = int(math.sqrt(discriminant))if sqrt_discriminant * sqrt_discriminant != discriminant:continueif (s + sqrt_discriminant) % 2 != 0:continuep = (s + sqrt_discriminant) // 2q = (s - sqrt_discriminant) // 2if p * q == N and p > 1 and q > 1:print(f"找到可能的解: d = {d}, k = {k}")print(f"分解得到: p = {p}, q = {q}")# 验证phi_actual = (p - 1) * (q - 1)if (e * d) % phi_actual == 1:print(f"验证成功: e*d ≡ 1 (mod φ(N))")return d, kelse:print(f"验证失败: e*d ≢ 1 (mod φ(N))")print("连分数攻击失败，未找到小解密指数")return Nonedef main():n = int(input("RSA模数n: "))e = int(input("公钥指数e: "))result = rsa_fraction_attack(n, e)if result:found_d, k = resultprint(f"找到解密指数 d = {found_d}")else:print("攻击失败")if __name__ == "__main__":main()
"""
RSA模数n: 2447482909
公钥指数e: 58549809
开始对RSA(N=2447482909, e=58549809)进行连分数攻击...
e/N的连分数表示: [0, 41, 1, 4, 23, 78, 1, 6, 8, 1, 1, 1, 4, 3, 2]...
收敛子数量: 15
找到可能的解: d = 209, k = 5
分解得到: p = 60317, q = 40577
验证成功: e*d ≡ 1 (mod φ(N))
找到解密指数 d = 209
"""