CRYPTO-RSA编码

Posted on

概论

RSA算法

RSA算法是现今使用最广泛的公钥密码算法，也是号称地球上最安全的加密算法。根据密钥的使用方法，可以将密码分为对称密码和公钥密码。对称密码：加密和解密使用同一种密钥的方式，公钥密码：加密和解密使用不同的密码的方式，因此公钥密码通常也称为非对称密码。

RSA加密

加密要用到公匙（n，e），公匙是公开的任何人可见，通式

1
c ≡ m^e (mod n)

其中m就是明文了，但m必须是整数（字符串可以取ascii值或unicode值），且m必须小于n。

RSA解密

得到c，使用私匙（n，d）解密，私匙是私有的，通式

1
m＝c^d mod n

RSA加密原理

步骤 说明 描述 备注
1 找出质数 p 、q -
2 计算公共模数 n = p * q -
3 欧拉函数 φ(N) = (p-1)(q-1) -
4 计算公钥e 1 < e < φ(N) e的取值必须是整数 e和 φ(n) 必须是互质数
5 计算私钥d e * d % φ(n) = 1 -
6 加密 c＝m^e mod n c：密文 m：明文
7 解密 m＝c^d mod n c：密文 m：明文

RSA算法原理详解参考文章：http://www.ruanyifeng.com/blog/2013/07/rsa_algorithm_part_two.html

例题

实验吧 - RSAROLL

题目地址：http://www.shiyanbar.com/ctf/1918

打开链接

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
{920139713,19}
 
704796792
752211152
274704164
18414022
368270835
483295235
263072905
459788476
483295235
459788476
663551792
475206804
459788476
428313374
475206804
459788476
425392137
704796792
458265677
341524652
483295235
534149509
425392137
428313374
425392137
341524652
458265677
263072905
483295235
828509797
341524652
425392137
475206804
428313374
483295235
475206804
459788476
306220148

分析可知，{920139713,19}是公匙，n=920139713，e=19，下面的就是密文了也就是c={704796792
，752211152，……}，根据这些求明文{m1，m2，……}

解题步骤：

1.分解n，得到p，q

1
2
3
4
5
6
7
8
def crackN(n):
    i=2
    while i<n:
        if n % i==0:
          break
        i=i+1
 
    return(i)

2.根据p,q获得欧拉数

1
o_n=int(p-1)*int((n/p)-1)

3.根据扩展欧几里得算法获得d

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
def exgcd(m,n,x,y):
        if n == 0:
                x = 1
                y = 0
                return (m,x,y)
        a1 = b = 1
        a = b1 = 0
        c = m
        d = n
        q = int(c/d)
        r = c%d
        while r:
                c = d
                d = r
                t = a1
                a1 = a
                a = t-q*a
                t = b1
                b1 = b
                b = t-q*b
                q = int(c/d)
                r = c%d
        x = a
        y = b
        return (d,x,y)

返回值为数组

1
d=exgcd(o_n,e,0,0)[2]

4.根据d解密密文c获得m

1
chr(pow(c,d,n))

5.遍历密文数组c获得m序列

1
2
3
4
s=""
while k<len(c):
              s=s+(chr(pow(c[k],d,n)))
              k=k+1

最终脚本：

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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85

e=19
n=920139713
c=[
704796792,
752211152,
274704164,
18414022,
368270835,
483295235,
263072905,
459788476,
483295235,
459788476,
663551792,
475206804,
459788476,
428313374,
475206804,
459788476,
425392137,
704796792,
458265677,
341524652,
483295235,
534149509,
425392137,
428313374,
425392137,
341524652,
458265677,
263072905,
483295235,
828509797,
341524652,
425392137,
475206804,
428313374,
483295235,
475206804,
459788476,
306220148,
]
def exgcd(m,n,x,y):
        if n == 0:
                x = 1
                y = 0
                return (m,x,y)
        a1 = b = 1
        a = b1 = 0
        c = m
        d = n
        q = int(c/d)
        r = c%d
        while r:
                c = d
                d = r
                t = a1
                a1 = a
                a = t-q*a
                t = b1
                b1 = b
                b = t-q*b
                q = int(c/d)
                r = c%d
        x = a
        y = b
        return (d,x,y)
def crackN(n):
    i=2
    while i<n:
        if n % i==0:
          break
        i=i+1
 
    return(i)
p=crackN(n)
k=0
o_n=int(p-1)*int((n/p)-1)
d=exgcd(o_n,e,0,0)[2]
s=""
while k<len(c):
              s=s+(chr(pow(c[k],d,n)))
              k=k+1
print(s)

运行

1

得到flag：flag{13212je2ue28fy71w8u87y31r78eu1e2}

参考文章：https://blog.csdn.net/janelml/article/details/89877099

总结

CTF中关于RSA的题还是挺多的，而且是有点难的，基本上都要写脚本才能做出来，也需要一些辅助的工具什么的，比如yafu、rsatool等。有一个很重要也是必须的一个库就是gmpy2，gmpy2是Python的一个扩展库，是对GMP的封装，它的前身是gmpy，经过其作者的调整和封装，使得gmpy2的使用大大简化，可以先安装下。本来还要写Jarvis OJ上的几道RSA的题，脚本要在网上找但是都要用到这个gmpy2但是这个gmpy2我弄个快一天了还是没弄好自己又不会写脚本，所以就没写，等之后把gmpy2装好了再补吧。

Jarvis OJ：平台地址：www.jarvisoj.com

yafu：下载地址：https://sourceforge.net/projects/yafu/安装使用：https://www.cnblogs.com/pcat/p/7508205.html

gmpy2：安装使用：https://blog.csdn.net/x_yhy/article/details/83903367、https://www.cnblogs.com/pcat/p/5746821.html

其他常用工具：https://www.lizenghai.com/archives/24289.html

CTF中RSA常见攻击方法：https://www.anquanke.com/post/id/84632