1.基础模板（分解N）

攻击条件

\(N\) 可以通过常见手段直接分解出来.

攻击脚本
1
2
3
4
5
import libnum
phi = (p-1)*(q-1)
d = libnum.invmod(e,phi)
m = pow(c,d,n)
print(libnum.n2s(m))

2. \(N\) 共有因子攻击(共享素数)

攻击条件

有两个公钥 \(N1\) 和 \(N2\) ，它们有共同因子 \(p\)，可以通过求解它们的最大公因数得到 \(p\).

特征

\(N\) 不相同，\(e\) 相同.

攻击脚本
1
2
3
4
5
6
7
import libnum
p = libnum.gcd(n1,n2)
q = n1//p
phi = (p-1)*(q-1)
d = libnum.invmod(e,phi)
m = pow(c1,d,n1)
print(libnum.n2s(m))

3.共模攻击

攻击条件

当两个用户使用相同的模数 \(N\),不同的私钥 \(d\) 时，加密同一明文消息时即存在共模攻击.

特征

\(N\) 相同，\(e\) 不相同.

攻击原理

\[ \begin{aligned} c_1 \equiv m ^{e_1} \mod N \\ c_2 \equiv m ^{e_2} \mod N \end{aligned} \] 通过扩展欧几里得定理求得 \(r\) 和 \(s\)，即 \[ \begin{split} r \times e_1 + s \times e_2 = 1 = \gcd (e1,e2) \\ \end{split} \] 然后，通过如下方法即可求得明文 \(m\). \[ \begin{split} c_1^rc_2^s &\equiv m^{re_1}m^{se_2} \mod N \\ &\equiv m^{re_1+se_2} \mod N \\ &\equiv m \mod N \end{split} \] 如果 \(r\) 和 \(c\) 中有一个是负数，那么就先取反，再将 \(c1\) 或者 \(c2\) 换成对应的逆元即可. ##### 攻击脚本 

1
2
3
4
5
6
7
8
9
10
import libnum
r,s,temp = libnum.xgcd(e1,e2)
if r < 0:
    r = -r
    c1 = libnum.invmod(c1,n)
if s < 0:
    s = -s
    c2 = libnum.invmod(c2,n)
m = (pow(c1,r,n)*pow(c2,s,n))%n
print(libnum.n2s(m))

4.小公钥指数攻击

攻击条件

\(e\) 特别小.

攻击原理

根据加密原理 \[ \begin{split} c \equiv m^e \mod N \end{split} \] 可以得出 \[ \begin{split} m^e = k \times N + c \end{split} \] 此时，暴力枚举 \(k\) ，计算出 \(k \times N +c\)，再开 \(e\) 次方即可.

攻击脚本
1
2
3
4
5
6
7
8
import libnum
for k in range(100000):
    temp = k * n + c
    m = libnum.nroot(temp,e)
    flag = libnum.n2s(m)
    if b'flag' in flag:
        print(flag)
        break

5.维纳攻击

攻击条件

\(d < \frac{1}{3}N^\frac{1}{4}\)

特征

\(e\) 极大或极小.

攻击脚本
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
import gmpy2
import libnum
  
def transform(x, y):  # 使用辗转相处将分数 x/y 转为连分数的形式
    res = []
    while y:
        res.append(x // y)
        x, y = y, x % y
    return res

def continued_fraction(sub_res):
    numerator, denominator = 1, 0
    for i in sub_res[::-1]:  # 从sublist的后面往前循环
        denominator, numerator = numerator, i * numerator + denominator
    return denominator, numerator  # 得到渐进分数的分母和分子，并返回

# 求解每个渐进分数
def sub_fraction(x, y):
    res = transform(x, y)
    res = list(map(continued_fraction, (res[0:i] for i in range(1, len(res)))))  # 将连分数的结果逐一截取以求渐进分数
    return res
    
def get_pq(a, b, c):  # 由p+q和pq的值通过维达定理来求解p和q
    par = gmpy2.isqrt(b * b - 4 * a * c)  # 由上述可得，开根号一定是整数，因为有解
    x1, x2 = (-b + par) // (2 * a), (-b - par) // (2 * a)
    return x1, x2
  
def wienerAttack(e, n):
    for (d, k) in sub_fraction(e, n):  # 用一个for循环来注意试探e/n的连续函数的渐进分数，直到找到一个满足条件的渐进分数
        if k == 0:  # 可能会出现连分数的第一个为0的情况，排除
            continue
        if (e * d - 1) % k != 0:  # ed=1 (mod φ(n)) 因此如果找到了d的话，(ed-1)会整除φ(n),也就是存在k使得(e*d-1)//k=φ(n)
            continue
        phi = (e * d - 1) // k  # 这个结果就是 φ(n)
        px, qy = get_pq(1, n - phi + 1, n)
        if px * qy == n:
            p, q = abs(int(px)), abs(int(qy))  # 可能会得到两个负数，负负得正未尝不会出现
            d = gmpy2.invert(e, (p - 1) * (q - 1))  # 求ed=1 (mod  φ(n))的结果，也就是e关于 φ(n)的乘法逆元d
            return d
    print("该方法不适用")

c = 
n = 
e = 
d = wienerAttack(e, n)
m=pow(c, d, n)
print(libnum.n2s(int(m)))