Framist's Little House

◇ 自顶而下 - 面向未来 ◇

0%

【现代密码学】大作业

发表于 更新于 分类于 ，

RSA 大礼包

摘要

本题内容是首届（2016）全国高校密码数学挑战赛的赛题三——RSA 加密体质破解。

利用多种针对 RSA 的攻击，和针对随机数发生器的攻击，如 RSA 共模攻击、pollard、低加密指数法、因数碰撞法、Fermat 攻击等，尽可能多得在所截获的数据中，挖掘出明文和参数。

题目描述

有人制作了一个 RSA 加解密软件（这个加密软件估计有些地方不规范，导致了被攻击的可能）。已知该软件发送某个明文的所有参数和加密过程的全部数据（有已知明密文攻击，还能知道加密的中间数据）。Alice 使用该软件发送了一个通关密语，且所有加密数据已经被截获，运用 RSA 相关攻击手段，仅从加密数据恢复该通关密语及 RSA 体制参数。

过程

公共模数攻击：frame 0、4

原理

RSA 加密中的四个参数 ${d,p,q,\phi(N)}$ 是同等重要的，任何一个参数泄露都会给其余三个的安全性带来威胁。但是，如果在 RSA 加密中使用相同的模数，那么有可能在不知道四个参数知识的情况下，攻击得到 RSA 加解密体制参数。

模数一样，待加密的明文一样，公钥互素

  • Alice: $(n_1,e_1,m_1)$, Bob: $(n_2,e_2,m_2)$
  • $n_1 = n_2$
  • $m_1 = m_2$
  • $gcd(e_1,e_2) = 1$

则可以轻松地恢复 $m$
$$
存在 (s,t) \quad s.t.\ e_1s+e_2t=gcd(e_1,e_2)=1 \
c_1^s \cdot c_2^t \equiv (m^{e_1})^s \cdot (m^{e_2})^t \equiv m^{e_1s+e_2t} \equiv m \pmod n
$$

步骤

1
2
3
4
5
6
7
8
9
10
11
12
13
14
from Crypto.Util.number import inverse
from gmpy2 import gcdext

def common_modulus(e1, e2, n, c1, c2):
    # 调用扩展的欧几里得算法函数
    g, s, t = gcdext(e1, e2)
    # 求模反元素
    if s < 0:
        s = -s
        c1 = inverse(c1,n)
    if t < 0:
        t = -t
        c2 = inverse(c2,n)
    return pow(c1,s,n)*pow(c2,t,n)%n

结果

1
2
b'\x98vT2\x10\xab\xcd\xef\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00My secre'
My secre

公共模数攻与因数碰撞法 frame 0,4；1、18

原理

当系统中不同的消息共用一个模数 N，只有 e 和 d 不同，系统将是危险的，此时，攻击者可能无需分解 N 就能够恢复明文。

前提条件

  • $gcd(n1,n2)!=1$
  • $n_1 \neq n_2$

攻击原理
$$
最大公因数获取其中一个大素数：p = gcd(n1,n2) \
n 除 p 获取另一个大素数：q_i = n_i \div p \quad (i=1 \ or \ 2) \
phi_i(n) = (q_i-1)(p-1) \
d_i = inverse(e_i,n_i) \
m_i \equiv c_i^{d_i} \pmod n_i
$$

步骤

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
def same_factor():
    print('因数碰撞法')
    plaintext = []
    index = []
    for i in range(21):
        for j in range(i + 1, 21):
            if int(ns[i], 16) == int(ns[j], 16):
                continue
            prime = gmpy2.gcd(int(ns[i], 16), int(ns[j], 16))
            if prime != 1:
                index.append(i)
                index.append(j)
                p_of_frame = prime
    q_of_frame1 = int(ns[index[0]], 16) // p_of_frame
    q_of_frame18 = int(ns[index[1]], 16) // p_of_frame
 
    phi_of_frame1 = (p_of_frame - 1) * (q_of_frame1 - 1)
    phi_of_frame18 = (p_of_frame - 1) * (q_of_frame18 - 1)
 
    d_of_frame1 = gmpy2.invert(int(es[index[0]], 16), phi_of_frame1)
    d_of_frame18 = gmpy2.invert(int(es[index[1]], 16), phi_of_frame18)
 
    plaintext_of_frame1 = gmpy2.powmod(int(cs[index[0]], 16), d_of_frame1, int(ns[index[0]], 16))
    plaintext_of_frame18 = gmpy2.powmod(int(cs[index[1]], 16), d_of_frame18, int(ns[index[1]], 16))
 
    final_plain_of_frame1 = binascii.a2b_hex(hex(plaintext_of_frame1)[-16:]).decode('ascii')
    final_plain_of_frame18 = binascii.a2b_hex(hex(plaintext_of_frame18)[-16:]).decode('ascii')
    
	print('Frame', index[0], ':', final_plain_of_frame1, sep='')
    print('Frame', index[1], ':', final_plain_of_frame18, sep='')
    
    return 0

结果

1
2
3
4
Frame 1 
b'\x98vT2\x10\xab\xcd\xef\x00\x00\x00\x0b\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00. Imagin'
Frame 18
b'\x98vT2\x10\xab\xcd\xef\x00\x00\x00\n\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00m A to B'

费马 (Fermat) 分解法：frame 10

原理

为了降低模数 N 被试除法攻破的可能性，算法设计者通常选择具有相同比特大小的参数 p 和 q，然而，如果 p 和 q 太过接近，就可以利用费马分解法找到它们。

费马分解法基于如下思想：设 $N=p q$, 其中 $p \leq q$ 都是奇数，然后令 $x=\frac{1}{2}(p+q)$, $y=\frac{1}{2}(q-p)$, 可以找到 $N=x^{2}-y^{2}=(x+y)(x-y)$ 或 $y^{2}=x^{2}-N$ 。

定理 设 $N=p q$, 其中 $p>q$ 且 $\Delta=p-q$, 则当 $\Delta<N^{\frac{1}{4}}$ 时，费马分解法可 以有效地分解 $N$ 。

步骤

1
2
3
4
5
6
7
8
9
10
11
12
from gmpy2 import iroot
def Fermat_factorization(num):
    x,flag_x = iroot(num,2)
    if pow(x,2)<num:
        x+=1
    while True:
        temp = pow(x,2) - num
        y,flag_y = iroot(temp,2)
        if flag_y:
            break
        x+=1
    return int((x+y)),int((x-y))

结果

1
2
3
frame 10
b'\x98vT2\x10\xab\xcd\xef\x00\x00\x00\x08\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00will get'
will get

Pollard’s p-1 分解法：frame 2,6,19

原理

RSA 加密算法中，素数 $p$ 和 $q$ 应该满足：$p \pm 1$ 和 $q \pm 1$ 至少有一个素因子大于 $10^{20}$, 否则，要分解的整数 $N$ 有一个素因数 $p$, 且 $(p-1)$ 有小的素因数时就可以 利用 Pollard $p-1$ 分解法有效分解模数 $N$, 从而得到 $p$ 。

设 $N=p q$, 其中 $p、q$ 为两个不同素数。选取一个整数 $k$ 使其满足 $(p-1) \mid k !$, 根据欧拉定理，对任意与 $p$ 互素的整数 $g$ 可以得到 $g^{p-1} \equiv 1(\bmod p)$, 因此，有 $g^{k !} \equiv 1(\bmod p)$, 即：$p \mid g^{k !}-1$; 又由于 $p \mid n$, 因此 $p \mid\left(\left(g^{k !} \bmod n\right)-1\right)$ 。但是，如何 选取 $k$ 是该算法中的关键问题，如果 $k$ 选取太小，则可能不满足关系 $p-1 \mid k !$; 如 果 $k$ 选取太大 (比如令 $k=p-1$ ), 算法执行的复杂度就会急剧加大。因此，在执 行算法前，先对可能满足关系 $p-1 \mid k !$ 的 $k$ 进行猜测，并根据计算能力进行设定。

算法

  • 设置$ a = 2$(或者其他方便的数字)

  • 循环$j = 2,3,\cdots B$

    若$p_1,p_2,\cdots,p_n$这些素数是随机在小 s 于 B 的数中选的，那么最大的素数大概率要大于 0.8B

    因此在$j<0.8B$之前不计算 gcd，可以节省时间

    • 令$a \equiv a^j \pmod n$
    • 计算$d = gcd(a-1,n)$
    • 如果$1<d<n$, 则返回$d$

步骤

1
2
3
4
5
6
7
8
9
10
11
12
13
from Crypto.Util.number import GCD
def pollard_p_1(n,B):
    a = 2
    false_range = int(0.8*B)
    for j in range(2,false_range):
        a = pow(a, j, n)

    d = 0
    for j in range(false_range,B+1):
        a = pow(a, j, n)
        d = GCD(a-1, n)
        if 1<d<n:
            return d

结果

1
2
3
4
5
6
7
8
9
frame 2
b'\x98vT2\x10\xab\xcd\xef\x00\x00\x00\x06\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00 That is'

frame 6
b'\x98vT2\x10\xab\xcd\xef\x00\x00\x00\x07\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00 "Logic '

frame 19
b'\x98vT2\x10\xab\xcd\xef\x00\x00\x00\x05\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00instein.'

低加密指数攻击：frame 7,11,15; 3,8,12,16,20

原理

在设计算法时为了加速计算，常常使用较小的加密指数 e，但是这种做法存在很大的安全隐患。如果相同的消息使用同样的加密指数加密后发送给不同的接收者，则该明文消息可以被非常有效的恢复。该攻击方法基于著名的中国剩余定理。

中国剩余定理

选取了相同的加密指数 e（这里取 e=3），对相同的明文 m 进行了加密并进行了消息的传递，那么有：
$$
c_1 \equiv m^3 \pmod {n_1} \
c_2 \equiv m^3 \pmod {n_2} \
c_3 \equiv m^3 \pmod {n_3} \
$$
对上述等式运用中国剩余定理，在 e=3 时，可以得到：
$$
N = n_1\cdot n_2\cdot n_3 \
c_x \equiv m^3 \pmod N
$$
通过对 $c_x$ 进行三次开方就可以求得明文

步骤

结果

1
2
3
4
5
6
7
8
9
- 7
b'\x98vT2\x10\xab\xcd\xef\x00\x00\x00\x02\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00amous sa'
- 11
b'\x98vT2\x10\xab\xcd\xef\x00\x00\x00\x03\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00ying of '
- 15
b'\x98vT2\x10\xab\xcd\xef\x00\x00\x00\x04\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00Albert E'

b'\x98vT2\x10\xab\xcd\xef\x00\x00\x00\x01\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00t is a f'

语义猜测：frame 2,3,4,9,12,13,14,15

根据已知的明文便可通过猜测 + 穷举的方法恢复出剩余的明文：

1
My secret is a famous saying of Albert Einstein. That is "Logic will get you from A to B. Imagination will take you everywhere."

总结

对 RSA 加密算法的原理、应用与破译有了更深入的了解和认识；学习了 RSA 有关的数论知识；加深了对信息安全的认识。

附录

备注

因为时间所限制，有些内容未认真完成。如后续有更新，将会发布在前文的博客链接中。

参考文献

RSA 加密体制破译报告——双河安团队答题卷

CTF Wiki (ctf-wiki.org)

RSA 共模攻击_reforever 的博客-CSDN 博客_rsa 共模攻击

因子分解算法——Pollard 的 p-1 方法_国科大网安二班的博客-CSDN 博客

密码学实验报告_cdcq__的博客-CSDN 博客