1. RSA基本方程
对于RSA，我们知道：
\(n = p·q\)，其中p、q为大素数
\(φ(n) = (p-1)(q-1)\)
\(e·d ≡ 1 (mod φ(n)) ⇒ e·d = k·φ(n) + 1\)
关键等式
将e·d = k·φ(n) + 1代入欧拉定理：
\(a^{(e·d)} ≡ a^{(k·φ(n)+1)} ≡ (a^{φ(n)})^k·a ≡ 1^k·a ≡ a (mod n)\)
这是RSA的解密基础
但我们更关心：
\(a^{(e·d - 1)} ≡ a^{(k·φ(n))} ≡ (a^{φ(n)})^k ≡ 1^k ≡ 1 (mod n)\)
所以对于任意与n互素的a，有：
\(a^{(e·d - 1)} ≡ 1 (mod n)\)
攻击原理推导
步骤1：分解指数e·d-1
设：
\(e·d - 1 = 2^s·t\)
其中t是奇数（即不断除以2直到得到奇数）
步骤2：构建平方序列
由前面推导得：
\(a^{(2^s·t)} ≡ 1 (mod n)\)
我们定义序列：
\(x_0 = a^t (mod n)\)
\(x_1 = x_0^2 = a^{(2t)} (mod n)\)
\(x_2 = x_1^2 = a^{(2^2·t)} (mod n)\)
\(...\)
\(x_s = x_{s-1}^2 = a^{(2^s·t)} ≡ 1 (mod n)\)
步骤3
引理1：如果对于某个i（1 ≤ i ≤ s），有：
\(x_i ≡ 1 (mod n) 且 x_{i-1} ≠ ±1 (mod n)\)
那么x_{i-1}是1模n的一个非平凡平方根。
证明：
因为\(x_i = x_{i-1}^2 ≡ 1 (mod n)\)，所以\(x_{i-1}^2 ≡ 1 (mod n)\)
又因为\(x_{i-1} ≠ ±1 (mod n)\)，所以它是非平凡的
非平凡平方根分解n
定理1：
如果x满足\(x^2 ≡ 1 (mod n)\) 且 \(x ≠ ±1 (mod n)\)，那么\(gcd(x-1, n)\)和\(gcd(x+1, n)\)都是n的非平凡因子。
证明：
-
由\(x^2 ≡ 1 (mod n)\)得：
\( x^2 - 1 ≡ 0 (mod n) ⇒ n | (x-1)(x+1) \) -
因为x ≠ 1 (mod n)，所以n ∤ (x-1)
-
因为x ≠ -1 (mod n)，所以n ∤ (x+1)
-
但n整除乘积(x-1)(x+1)，所以n的每个素因子p必须整除(x-1)或(x+1)，但不能同时整除两者（否则p会整除它们的差2，而p是奇素数，所以不可能）。
-
因此：
- p | (x-1) 且 q ∤ (x-1) 或者
- p | (x+1) 且 q ∤ (x+1)
-
所以：
\(gcd(x-1, n) = p\) 或 \(gcd(x+1, n) = p\)
另一个因子可以通过n除以这个因子得到。
完整算法形式化描述
输入：
- RSA公钥(n, e)
- 私钥d
输出：
- n的素因子p和q
算法：
- 计算 M = e·d - 1
- 分解 M = 2^s·t，其中t为奇数
- 重复直到找到因子：
- 随机选择 a ∈ [2, n-1]
- 如果 gcd(a, n) > 1，则已找到因子，结束
- 计算序列：
\( x₀ = a^t (mod n) x_i = x_{i-1}^2 (mod n), i = 1, 2, ..., s \) - 寻找最小的i使得 x_i ≡ 1 (mod n)
- 如果 i > 0 且 x_{i-1} ≠ ±1 (mod n)：
- p = gcd(x_{i-1} - 1, n)
- q = n / p
- 返回(p, q)
示例：n = 15 = 3·5，φ(n) = 8
假设我们已知e=3，d=3（因为3×3=9≡1 mod 8）
-
计算 M = e·d - 1 = 9 - 1 = 8 = 2^3·1，所以s=3，t=1
-
选择a=2：
- x₀ = 2^1 mod 15 = 2
- x₁ = 2^2 mod 15 = 4
- x₂ = 4^2 mod 15 = 1
找到i=2使x₂=1，且x₁=4 ≠ ±1
gcd(4-1,15)=gcd(3,15)=3 → p=3
q=15/3=5 -
验证：3×5=15 ✓
实现
rsa_d_leakage_attack
"""
RSA分解算法 - 已知解密指数d和公钥(n, e)分解n当已知RSA的解密指数d和公钥(n, e)时，可以通过以下方法分解n：
1. 利用 ed ≡ 1 (mod φ(n)) 的关系
2. 得出 ed - 1 = kφ(n)
3. 随机构造一个数a，计算a^k mod n
4. 通过寻找非平凡的平方根来分解n
"""import random
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 power_mod(base, exp, mod):result = 1base = base % modwhile exp > 0:if exp % 2 == 1:result = (result * base) % modexp = exp >> 1base = (base * base) % modreturn resultdef gcd(a, b):while b:a, b = b, a % breturn adef factorize_with_d(n, e, d):"""利用已知的解密指数d分解RSA模数n"""print(f"开始分解: n = {n}, e = {e}, d = {d}")ed_minus_1 = e * d - 1print(f"步骤1: 计算 ed - 1 = {e} * {d} - 1 = {ed_minus_1}")s = 0t = ed_minus_1while t % 2 == 0:t //= 2s += 1print(f"步骤2: 将 ed - 1 分解为 2^{s} * {t} 的形式")# 随机选择一个数a，使得 2 <= a <= n-1attempts = 0max_attempts = 100 #limitwhile attempts < max_attempts:a = random.randint(2, n - 1)print(f"\n尝试 #{attempts + 1}: 选择 a = {a}")g = gcd(a, n)if g > 1:print(f" 找到因子: gcd({a}, {n}) = {g}")return g, n // gx = power_mod(a, t, n)print(f" 计算 x = {a}^{t} mod {n} = {x}")#x ≡ 1 (mod n) 或 x ≡ -1 (mod n)if x == 1 or x == n - 1:print(f" x ≡ {x} (mod {n}), 重新选择a")attempts += 1continue# 迭代计算 x 的平方，直到找到非平凡平方根或达到终止条件found = Falsefor i in range(s):x_prev = xx = (x * x) % nprint(f" 第{i+1}次迭代: x = {x_prev}^2 mod {n} = {x}")# 如果 x ≡ 1 (mod n) 且 x_prev ≠ 1, n-1，则找到了非平凡平方根if x == 1 and x_prev != 1 and x_prev != n - 1:print(f" 找到非平凡平方根: {x_prev}^2 ≡ 1 (mod {n})")# 计算 gcd(x_prev - 1, n) 和 gcd(x_prev + 1, n)factor1 = gcd(x_prev - 1, n)factor2 = gcd(x_prev + 1, n)print(f" 计算 gcd({x_prev} - 1, {n}) = gcd({x_prev - 1}, {n}) = {factor1}")print(f" 计算 gcd({x_prev} + 1, {n}) = gcd({x_prev + 1}, {n}) = {factor2}")if factor1 > 1 and factor1 < n:print(f" 找到因子: p = {factor1}, q = {n // factor1}")return factor1, n // factor1elif factor2 > 1 and factor2 < n:print(f" 找到因子: p = {factor2}, q = {n // factor2}")return factor2, n // factor2else:print(" 没有找到非平凡因子，继续尝试")found = Truebreakelif x == n - 1:print(f" x ≡ -1 (mod {n}), 重新选择a")breakif found:breakattempts += 1print(f"经过{max_attempts}次尝试后未能分解n")return Nonedef verify_rsa_factors(n, e, d, p, q):print(f"\n验证分解结果:")print(f"n = {n}")print(f"p = {p}")print(f"q = {q}")print(f"p * q = {p * q}")if p * q == n:print("验证通过")else:print("验证失败")return Falsephi = (p - 1) * (q - 1)print(f"φ(n) = ({p} - 1) * ({q} - 1) = {phi}")if (e * d) % phi == 1:print(f"验证通过: {e} * {d} = {(e * d)}, ({e * d}) mod {phi} = {(e * d) % phi}")else:print(f"验证失败: {e} * {d} = {(e * d)}, ({e * d}) mod {phi} = {(e * d) % phi}")return Falsereturn Truedef main():print("RSA分解算法 - 已知解密指数d和公钥(n, e)分解n")p1, q1 = 61, 53n1 = p1 * q1phi1 = (p1 - 1) * (q1 - 1)e1 = 17d1 = mod_inverse(e1, phi1)print(f"原始参数: p = {p1}, q = {q1}, n = {n1}, e = {e1}, d = {d1}")result1 = factorize_with_d(n1, e1, d1)if result1:p_found, q_found = result1verify_rsa_factors(n1, e1, d1, p_found, q_found)else:print("分解失败")try:n = int(input("RSA模数n: "))e = int(input("公钥指数e: "))d = int(input("解密指数d: "))print(f"\n输入参数: n = {n}, e = {e}, d = {d}")result2 = factorize_with_d(n, e, d)if result2:p_found, q_found = result2success = verify_rsa_factors(n, e, d, p_found, q_found)if success:print(f"\n成功分解: n = {p_found} * {q_found}")else:print("\n分解结果验证失败")else:print("分解失败")except ValueError:print("输入格式错误，请输入有效的整数")except KeyboardInterrupt:pass