RSA简介

1.encrypt

生成两个大素数p,q

计算 作为模数，计算Euler函数 然后随机生成公钥e,满足 当N，e公开作为公钥之后

任何人都可以用公钥加密

2.decrypt

计算私钥 解密

只有拥有私钥d的人可以解密

但是，往往由于参数生成不当，RSA可以被破解

相关数论算法

1.Eculid算法

用一个递归很容易实现

1
2
3
4
5
6
def eculid(x,y):
    r =  x % y 
    if r == 0:
        return y
    else:
        return eculid(y,r)

时间复杂度是O()

2.Extend Eculid算法

也是递归

1
2
3
4
5
6
def gcdext(x,y):
    r = x % y
    if r == 0:
        return [0,1]
    else:
        return [gcdext(y,r)[1],gcdext(y,r)[0] - x//y * gcdext(y,r)[1]]

注意到 由于x可以由y和x%y表示，那么

只需求 的解，注意到 那么 即 此算法可以直接由gmpy2的库调用，即gmpy2.gcdext

返回的是d,x,y的元组

公钥e相关攻击

1.small exponent attack

如果e太小，我们可以直接枚举k开根,m如果比较小的话，甚至k=0 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
from Crypto.Util.number import *
from gmpy2 import *
import random
p,q = getPrime(512),getPrime(512)
N = p*q
phi = (p-1)*(q-1)
m = bytes_to_long(b'flag{You_really_got_it!}')
while(1):
    e = random.randint(2,10)
    if GCD(e,phi) == 1:
        break
c = pow(m,e,N)
print(f'c={c}')
print(f'e={e}')
for k in range(100):
    if iroot(c+k*N,e)[1]:
        m =  iroot(c+k*N,e)[0]
        print(f'k={k}')
        print(long_to_bytes(m))
        break

考虑最严苛的情况，m=N-1

那么也就是 由于c是小于N的，那么 一般情况来说，假设N为1024bit 我们的枚举上限大概是2^32左右，而且32需要非常久的时间，在有限时间内，我们不妨假设上限是2的16次方

那这样的话，可以知道 如果e=7的话，m最多148位，也就是18个字左右

但实际上18个字其实是144-152之间，经过实测18个字的话k基本都是0

模数N相关攻击

1.共模攻击

如果Alice一直不更换模数N，只更换e，那么加密同一条信息就可以被攻击 我们想办法统一指数，这样我们就可以使用孙子定理（等式一边都是x）

考虑Bezout定理 我们可以用extend Eculid算法来计算x,y

1.互素

这是比较简单的情况，因为 那么直接有 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
from Crypto.Util.number import *
from gmpy2 import *
import random
p,q = getPrime(512),getPrime(512)
N = p*q
phi = (p-1)*(q-1)
m = bytes_to_long(b'flag{You_got_it!}')
while(1):
    e1,e2 = random.randint(1,phi),random.randint(1,phi)
    if GCD(e1,e2) == 1 and GCD(e1,phi) == 1 and GCD(e2,phi) == 1:
        break
c1,c2 = pow(m,e1,N),pow(m,e2,N)
print(c1,c2)
x,y = gcdext(e1,e2)[1:]
m = pow(c1,x,N)*pow(c2,y,N) % N
print(long_to_bytes(m))

2.不互素

这样的话其实就是情况1加上small exponent attack

如果两个的公因数不大的话，是可以解决的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
from Crypto.Util.number import *
from gmpy2 import *
import random
p,q = getPrime(512),getPrime(512)
N = p*q
phi = (p-1)*(q-1)
m = bytes_to_long(b'flag{You_got_it!}')
while(1):
    e1,e2 = random.randint(1,phi),random.randint(1,phi)
    if GCD(e1,phi) == 1 and GCD(e2,phi) == 1:
        break
c1,c2 = pow(m,e1,N),pow(m,e2,N)
print(c1,c2)
e,x,y = gcdext(e1,e2)
print(f'e={e}')
mpow = pow(c1,x,N)*pow(c2,y,N) % N
for k in range(2**22):
    if iroot(mpow+k*N,e)[1]:
        m =  iroot(mpow+k*N,e)[0]
        print(f'k={k}')
        print(long_to_bytes(m))
        break

私钥d相关攻击

1.d泄露

如果我们知道d，当然所有消息都能求解了，不过，知道d可以分解N？这就很反常识了！

d的相关等式只有一个 那理论上来说，直接分解de-1就可以求解了 但问题是，k和phi可能都是合数，那这样它们的因数会混淆，无法得到结果

其实归根结底就是，我们知道phi的倍数

那么，phi又涉及到哪个等式呢？ 那么 这个式子有什么用呢，我们可以开方，不断的开方

假设 我们的主要想法还是去分解n，那么就要找到一个数，他和n的最大公因数是p或者q

那么这样的数怎么去构造？

我们随机选择和n互素的a，如果 那我们就找到了一个非平凡平方根，那么假设 不断平方，知道 一旦找到这样的，那么 那么很明显两个因式都不是n的倍数，那么只有一种可能，他们分别是p，q的倍数

所以 

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
from Crypto.Util.number import *
from gmpy2 import *
import random
p,q = getPrime(512),getPrime(512)
N = p*q
phi = (p-1)*(q-1)
m = bytes_to_long(b'flag{You_got_it!}')
e = 65537
d = inverse(e,phi)
c = pow(m,e,N)
print(f'N={N}')
print(f'd={d}')
print(f'c={c}')
K = d*e-1
while(K%2 ==0):
    K = K//2
t = K
while(True):
    a = random.randint(2,N)
    if N % a == 0:
        print(a)
        break
    while(pow(a,t,N)!= 1): 
        a = a*a
    a = gmpy2.iroot(a,2)[0]
    p = GCD(pow(a,t,N)-1,N)
    if p != 1:
        q = N // p
        print('分解成功')
        print(p,q)
        break

2.d太小（Wiener's Atta）

如果 那么是可以回复出d的

注意到 展开一下就是 我们把公钥都放一起，就是已知的e和N，同时不妨记p+q=s

那么 即 注意到 由于 而 则 由 则 于是有 根据Legendre定理

k/d是e/N的渐进分数，于是就求出了k和d