RSA原理简介

RSA原理

RSA加密算法中包含以下数字:

质数、模数与欧拉函数

p 质数1 61
q 质数2 53
n=p*q 模数 3233
φ(n) 欧拉函数 在1到n,有多少个数与n构成互质关系 3120

p与q为两个位数(指2进制位)相差不大的质数,p与q的积称为模数,通常用字母n表示,φ(n)为欧拉函数。n有多少个2进制位,则密钥的位数就是多少。

欧拉函数的计算公式及简便算法

通项公式:
φ(x)=x(1-1/p(1))(1-1/p(2))(1-1/p(3))(1-1/p(4))…..(1-1/p(n)) 其中p(1),p(2)…p(n)为x的所有质因数;x是正整数;
简便算法:

  • n=1 φ(1) =1
  • n为质数 φ(n) =n-1
  • n=p^k(p为质数,k>=1) φ(n) =p^k-p^(k-1)=(p-1)*p^(k-1)
  • n=pq(p,q均为质数) φ(n) = φ(pq)= φ(p)*φ(q)

在RSA算法中,n=pq,使用简便算法可得到欧拉函数φ(n) = φ(pq)= φ(p)φ(q) = (p-1) (q-1)

指数与摸反元素

e 指数 17
d 模反元素 ed-1 = kφ(n) 2753

选择一个e (1<e<φ(n)),且e和φ(n)互质,e称为指数,取e的模反数为d,计算方法: ed ≡ 1 (mod φ(n)),表示存在一个整数d,可以便得ed除以φ(n)的余数等于1。e和d是互为模反数的两个指数。

公钥与私钥

公钥 (n,e) (3233,17)
私钥 (n,d) (3233,2753)

公钥由模数n与指数e组成,用于加密;私钥由模数n与模反元素d组成,用于解密。公钥可以发给任何人,私钥自己保存。

明文与密文

m 明文 65
c 密文 2790

加密与解密

加密 m^e-c=kn 明文65加密后为2790
解密 c^d -m=k
n 密文2790解密后为65

B使用A的公钥对明文m进行加密得到c,通过网络传输给A,A使用自己的私钥对密文c进行解密得到m。

工具

RSA Tool 2 对上面的数字进行测试

RSA Tool 2使用私钥进行解密

openssl 密钥生成与加密解密

生成私钥

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
➜  rsa ls
➜ rsa openssl genrsa -out private.key # 生成私钥,Mac系统下默认的长度为512位,CentOS 7系统下为2048位
Generating RSA private key, 512 bit long modulus
..................++++++++++++
..++++++++++++
e is 65537 (0x10001)
➜ rsa ls
private.key
➜ rsa cat private.key # 生成的私钥文件private.key为文本文件
-----BEGIN RSA PRIVATE KEY-----
MIIBOwIBAAJBAJvwhUOWKlJPJMHJ9r7zkemU2kIo1GpofZ09fGGbixzTHh6rGT0i
DegxbwB52Sbb2hpdyYIKdiSZSff8kH/GQm0CAwEAAQJAXm+9tN2XCbvGTdnKpX+K
aQPtXc2uPjbDg9s9nTr+d1htJX/L9lj2S9XIU+hq0XZMT2Dpm9FvyjbUJzC+reIT
gQIhAM9SDFozN7P3ba6KquHHLT0UTk3DXZi30wcKF7iCrVxNAiEAwI37qgRKmKgX
HnKDmsG/2YJBtfWL3/zkgqF+F/n/DqECIQCFtTnoNp4XQF2Jsz8QTB/eA6mYt4Y2
x1+fa5/uzMC4BQIgOAzcdggbwsYjPKyu3GyLsP/2qsXYOpI93jyuHMKb2SECIQCU
ubUKSdNax4xubFQMsVUVKes4+L+gaKaf6DXplfeHGQ==
-----END RSA PRIVATE KEY-----
➜ rsa openssl rsa -text -modulus -in private.key # 分析私钥
Private-Key: (512 bit)
modulus:
00:9b:f0:85:43:96:2a:52:4f:24:c1:c9:f6:be:f3:
91:e9:94:da:42:28:d4:6a:68:7d:9d:3d:7c:61:9b:
8b:1c:d3:1e:1e:ab:19:3d:22:0d:e8:31:6f:00:79:
d9:26:db:da:1a:5d:c9:82:0a:76:24:99:49:f7:fc:
90:7f:c6:42:6d
publicExponent: 65537 (0x10001)
privateExponent:
5e:6f:bd:b4:dd:97:09:bb:c6:4d:d9:ca:a5:7f:8a:
69:03:ed:5d:cd:ae:3e:36:c3:83:db:3d:9d:3a:fe:
77:58:6d:25:7f:cb:f6:58:f6:4b:d5:c8:53:e8:6a:
d1:76:4c:4f:60:e9:9b:d1:6f:ca:36:d4:27:30:be:
ad:e2:13:81
prime1:
00:cf:52:0c:5a:33:37:b3:f7:6d:ae:8a:aa:e1:c7:
2d:3d:14:4e:4d:c3:5d:98:b7:d3:07:0a:17:b8:82:
ad:5c:4d
prime2:
00:c0:8d:fb:aa:04:4a:98:a8:17:1e:72:83:9a:c1:
bf:d9:82:41:b5:f5:8b:df:fc:e4:82:a1:7e:17:f9:
ff:0e:a1
exponent1:
00:85:b5:39:e8:36:9e:17:40:5d:89:b3:3f:10:4c:
1f:de:03:a9:98:b7:86:36:c7:5f:9f:6b:9f:ee:cc:
c0:b8:05
exponent2:
38:0c:dc:76:08:1b:c2:c6:23:3c:ac:ae:dc:6c:8b:
b0:ff:f6:aa:c5:d8:3a:92:3d:de:3c:ae:1c:c2:9b:
d9:21
coefficient:
00:94:b9:b5:0a:49:d3:5a:c7:8c:6e:6c:54:0c:b1:
55:15:29:eb:38:f8:bf:a0:68:a6:9f:e8:35:e9:95:
f7:87:19
Modulus=9BF08543962A524F24C1C9F6BEF391E994DA4228D46A687D9D3D7C619B8B1CD31E1EAB193D220DE8316F0079D926DBDA1A5DC9820A76249949F7FC907FC6426D
writing RSA key
-----BEGIN RSA PRIVATE KEY-----
MIIBOwIBAAJBAJvwhUOWKlJPJMHJ9r7zkemU2kIo1GpofZ09fGGbixzTHh6rGT0i
DegxbwB52Sbb2hpdyYIKdiSZSff8kH/GQm0CAwEAAQJAXm+9tN2XCbvGTdnKpX+K
aQPtXc2uPjbDg9s9nTr+d1htJX/L9lj2S9XIU+hq0XZMT2Dpm9FvyjbUJzC+reIT
gQIhAM9SDFozN7P3ba6KquHHLT0UTk3DXZi30wcKF7iCrVxNAiEAwI37qgRKmKgX
HnKDmsG/2YJBtfWL3/zkgqF+F/n/DqECIQCFtTnoNp4XQF2Jsz8QTB/eA6mYt4Y2
x1+fa5/uzMC4BQIgOAzcdggbwsYjPKyu3GyLsP/2qsXYOpI93jyuHMKb2SECIQCU
ubUKSdNax4xubFQMsVUVKes4+L+gaKaf6DXplfeHGQ==
-----END RSA PRIVATE KEY-----

生成的私钥格式为

1
2
3
4
5
-----BEGIN RSA PRIVATE KEY-----
Proc-Type: 4,ENCRYPTED
DEK-Info: AES-256-CBC,5584D000DDDD53DD5B12AE935F05A007
Base64 Encoded Data(每64个字符换行)
-----END RSA PRIVATE KEY-----

这里

1
2
3
4
5
6
modulus:
00:9b:f0:85:43:96:2a:52:4f:24:c1:c9:f6:be:f3:
91:e9:94:da:42:28:d4:6a:68:7d:9d:3d:7c:61:9b:
8b:1c:d3:1e:1e:ab:19:3d:22:0d:e8:31:6f:00:79:
d9:26:db:da:1a:5d:c9:82:0a:76:24:99:49:f7:fc:
90:7f:c6:42:6d

表示模数n,这里第30个16进制位换一行,除去前面的00,一共有128个16进制位,即512个2进制位,则称这个RSA算法的密钥为512位的。

1
Modulus=9BF08543962A524F24C1C9F6BEF391E994DA4228D46A687D9D3D7C619B8B1CD31E1EAB193D220DE8316F0079D926DBDA1A5DC9820A76249949F7FC907FC6426D

n的十六进制表示为

1
0x9BF08543962A524F24C1C9F6BEF391E994DA4228D46A687D9D3D7C619B8B1CD31E1EAB193D220DE8316F0079D926DBDA1A5DC9820A76249949F7FC907FC6426D

1
publicExponent: 65537 (0x10001)

表示指数e为65537,十六进制表示为0x10001。

1
2
3
4
5
6
privateExponent:
5e:6f:bd:b4:dd:97:09:bb:c6:4d:d9:ca:a5:7f:8a:
69:03:ed:5d:cd:ae:3e:36:c3:83:db:3d:9d:3a:fe:
77:58:6d:25:7f:cb:f6:58:f6:4b:d5:c8:53:e8:6a:
d1:76:4c:4f:60:e9:9b:d1:6f:ca:36:d4:27:30:be:
ad:e2:13:81

表示模反元素d。

1
2
3
4
prime1:
00:cf:52:0c:5a:33:37:b3:f7:6d:ae:8a:aa:e1:c7:
2d:3d:14:4e:4d:c3:5d:98:b7:d3:07:0a:17:b8:82:
ad:5c:4d

表示质数1 p。

1
2
3
4
prime2:
00:c0:8d:fb:aa:04:4a:98:a8:17:1e:72:83:9a:c1:
bf:d9:82:41:b5:f5:8b:df:fc:e4:82:a1:7e:17:f9:
ff:0e:a1

表示质数2 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
➜  rsa ls
private.key
➜ rsa openssl rsa -in private.key -pubout -out public.key # 通过私钥计算公钥
writing RSA key
➜ rsa ls
private.key public.key
➜ rsa cat public.key # 生成的公钥public.key为文本文件
-----BEGIN PUBLIC KEY-----
MFwwDQYJKoZIhvcNAQEBBQADSwAwSAJBAJvwhUOWKlJPJMHJ9r7zkemU2kIo1Gpo
fZ09fGGbixzTHh6rGT0iDegxbwB52Sbb2hpdyYIKdiSZSff8kH/GQm0CAwEAAQ==
-----END PUBLIC KEY-----
➜ rsa openssl rsa -pubin -text -modulus -in public.key # 分析公钥
Modulus (512 bit):
00:9b:f0:85:43:96:2a:52:4f:24:c1:c9:f6:be:f3:
91:e9:94:da:42:28:d4:6a:68:7d:9d:3d:7c:61:9b:
8b:1c:d3:1e:1e:ab:19:3d:22:0d:e8:31:6f:00:79:
d9:26:db:da:1a:5d:c9:82:0a:76:24:99:49:f7:fc:
90:7f:c6:42:6d
Exponent: 65537 (0x10001)
Modulus=9BF08543962A524F24C1C9F6BEF391E994DA4228D46A687D9D3D7C619B8B1CD31E1EAB193D220DE8316F0079D926DBDA1A5DC9820A76249949F7FC907FC6426D
writing RSA key
-----BEGIN PUBLIC KEY-----
MFwwDQYJKoZIhvcNAQEBBQADSwAwSAJBAJvwhUOWKlJPJMHJ9r7zkemU2kIo1Gpo
fZ09fGGbixzTHh6rGT0iDegxbwB52Sbb2hpdyYIKdiSZSff8kH/GQm0CAwEAAQ==
-----END PUBLIC KEY-----

使用公钥加密

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
➜  rsa ls
private.key public.key
➜ rsa echo 'iphpjs' > msg.txt # 明文
➜ rsa ls
msg.txt private.key public.key
➜ rsa cat msg.txt
iphpjs
➜ rsa openssl rsautl -in msg.txt -out msg.txt.enc -inkey public.key -pubin -encrypt -pkcs # 使用公钥加密
➜ rsa ls
msg.txt msg.txt.enc private.key public.key
➜ rsa xxd msg.txt.enc
00000000: 3bc0 2e81 4eee b840 e329 c58d 39af 8377 ;...N..@.)..9..w
00000010: 7454 fce7 e58a 9669 b8b9 75c1 e9fd bedb tT.....i..u.....
00000020: 5766 b79f 5041 f267 c9ad 687f 62f8 a540 Wf..PA.g..h.b..@
00000030: 3953 7b54 241b 9cba 3c2c a854 311e fec7 9S{T$...<,.T1...

openssl rsautl -in msg.txt -out msg.txt.enc -inkey public.key -pubin -encrypt -pkcs这里-pkcs表示加密处理过程中数据的填充方式,默认为pkcs,其他的还有-oaep,-ssl,-raw

使用公钥加密

1
2
3
4
5
6
7
➜  rsa ls
msg.txt msg.txt.enc private.key public.key
➜ rsa openssl rsautl -in msg.txt.enc -out msg.txt.dec -inkey private.key -decrypt -pkcs
➜ rsa ls
msg.txt msg.txt.dec msg.txt.enc private.key public.key
➜ rsa cat msg.txt.dec
iphpjs

明文通过公钥加密后得到密文,再经过私钥解密后得到的明文与原明文相同。

现在假设我们只有公钥和明文加密后得到密文,我们想得到明文。根据前面的公式,要得到明文,需要知道私钥才行。
公钥由(n,e)组成,私钥由(n,d)组成,这里我们不知道d,需要对其进行计算。
根据公式ed-1 = kφ(n),需要计算φ(n)。
φ(n)=φ(p)φ(q)=(p-1)(q-1),n=pq,我们如果能对n进行因式分解出pq,即可计算出所有的信息。
对于位数比较长的数字,要对n进行因式分解是很困难的,下面介绍进行因式分解的工具。

msieve 因式分解

下载地址: https://sourceforge.net/projects/msieve/

实验吧RSA题目: http://www.shiyanbar.com/ctf/1772

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
➜  rsa ls
RSA RSA.zip
➜ rsa cd RSA
➜ RSA ls
flag.enc public.pem
➜ RSA cat public.pem # 公钥
-----BEGIN PUBLIC KEY-----
MDwwDQYJKoZIhvcNAQEBBQADKwAwKAIhAKQQBt79N4tzlbTi6x7Jv1amHNnDtaCn
NShSHusvuBenAgMBAAE=
-----END PUBLIC KEY-----
➜ RSA xxd flag.enc # 密文
00000000: 49b9 6edb e396 1f58 d529 074b d893 d6e0 I.n....X.).K....
00000010: 36ce af2b 6d21 4b47 0fdc 0d48 723d 6a40 6..+m!KG...Hr=j@
➜ RSA openssl rsa -pubin -text -modulus -in public.pem # 分解公钥得到n
Modulus (256 bit):
00:a4:10:06:de:fd:37:8b:73:95:b4:e2:eb:1e:c9:
bf:56:a6:1c:d9:c3:b5:a0:a7:35:28:52:1e:eb:2f:
b8:17:a7
Exponent: 65537 (0x10001)
Modulus=A41006DEFD378B7395B4E2EB1EC9BF56A61CD9C3B5A0A73528521EEB2FB817A7
writing RSA key
-----BEGIN PUBLIC KEY-----
MDwwDQYJKoZIhvcNAQEBBQADKwAwKAIhAKQQBt79N4tzlbTi6x7Jv1amHNnDtaCn
NShSHusvuBenAgMBAAE=
-----END PUBLIC KEY-----

因式分解

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
C:\Users\suse\Desktop\msieve153>msieve153.exe 0xA41006DEFD378B7395B4E2EB1EC9BF56
A61CD9C3B5A0A73528521EEB2FB817A7 -v


Msieve v. 1.53 (SVN 1005)
Sun Aug 26 01:04:21 2018
random seeds: 084c645c caa709df
factoring 7420762414294524226305703528711098396764602005730782870958796964670136
1764263 (77 digits)
searching for 15-digit factors
commencing quadratic sieve (77-digit input)
using multiplier of 7
using generic 32kb sieve core
sieve interval: 12 blocks of size 32768
processing polynomials in batches of 17
using a sieve bound of 921409 (36471 primes)
using large prime bound of 92140900 (26 bits)
using trial factoring cutoff of 26 bits
polynomial 'A' values have 10 factors
restarting with 19564 full and 188446 partial relations

36840 relations (19564 full + 17276 combined from 188446 partial), need 36567
sieving complete, commencing postprocessing
begin with 208010 relations
reduce to 51950 relations in 2 passes
attempting to read 51950 relations
recovered 51950 relations
recovered 38623 polynomials
attempting to build 36840 cycles
found 36840 cycles in 1 passes
distribution of cycle lengths:
length 1 : 19564
length 2 : 17276
largest cycle: 2 relations
matrix is 36471 x 36840 (5.3 MB) with weight 1107026 (30.05/col)
sparse part has weight 1107026 (30.05/col)
filtering completed in 3 passes
matrix is 25002 x 25063 (4.0 MB) with weight 843666 (33.66/col)
sparse part has weight 843666 (33.66/col)
saving the first 48 matrix rows for later
matrix includes 64 packed rows
matrix is 24954 x 25063 (2.6 MB) with weight 619193 (24.71/col)
sparse part has weight 443745 (17.71/col)
commencing Lanczos iteration
memory use: 2.7 MB
lanczos halted after 397 iterations (dim = 24954)
recovered 18 nontrivial dependencies
p39 factor: 258631601377848992211685134376492365269
p39 factor: 286924040788547268861394901519826758027
elapsed time 00:00:07

p为258631601377848992211685134376492365269
q为286924040788547268861394901519826758027

通过p,q,e计算生成私钥。
crack_rsa.py 环境python2.7, pip install pycrypto

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
#!/usr/bin/env python
# coding=utf-8

import math
import sys
from Crypto.PublicKey import RSA

keypair = RSA.generate(1024)

keypair.p = 258631601377848992211685134376492365269
keypair.q = 286924040788547268861394901519826758027
keypair.e = 65537

keypair.n = keypair.p * keypair.q
Qn = long((keypair.p-1) * (keypair.q-1))

i = 1
while (True):
x = (Qn * i ) + 1
if (x % keypair.e == 0):
keypair.d = x / keypair.e
break
i += 1

private = open('private.pem','w')
private.write(keypair.exportKey())
private.close()

生成私钥并解密

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
➜  RSA ls
crack_rsa.py flag.enc public.pem
➜ RSA python crack_rsa.py
➜ RSA ls
crack_rsa.py flag.enc private.pem public.pem
➜ RSA cat private.pem
-----BEGIN RSA PRIVATE KEY-----
MIGpAgEAAiEApBAG3v03i3OVtOLrHsm/VqYc2cO1oKc1KFIe6y+4F6cCAwEAAQIg
MwIooLvpwRm2uf6zS2c+bZqsOtgUCWlLV2hxUhJUosECEQDCkqJy6DObFF2d9nS5
qHXVAhEA19uPaLzsbXaEs3IBOF0piwIQIzhVzYT4qm6yT4CoOl8jDQIQGufyS0Lp
UYepaNi4EDeEmwIQVJcg1+P8wLPa/twoTpDvmA==
-----END RSA PRIVATE KEY-----
➜ RSA openssl rsautl -in flag.enc -inkey private.pem -out flag.dec -decrypt
➜ RSA ls
crack_rsa.py flag.dec flag.enc private.pem public.pem
➜ RSA cat flag.dec
ISG{256bit_is_weak}%

使用msieve153.exe可以轻松地对331位模数n进行分解得到p,q;目前768位已可轻松因式分解,1024位也可在一定时间内进行因式分解,所以目前现实应用中多是以2048位或4096位的为主。

yafu 因式分解

下载地址: https://sourceforge.net/projects/yafu/

yafu-x64.exe factor(920139713)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
C:\Users\suse\Desktop\yafu-1.34>yafu-x64.exe factor(920139713)


fac: factoring 920139713
fac: using pretesting plan: normal
fac: no tune info: using qs/gnfs crossover of 95 digits
div: primes less than 10000
fmt: 1000000 iterations
Total factoring time = 0.0000 seconds


***factors found***

P5 = 49891
P5 = 18443

ans = 1

yafu-x64.exe “factor(@)” -batchfile modulus.txt

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
C:\Users\suse\Desktop\yafu-1.34>type modulus.txt
3233

C:\Users\suse\Desktop\yafu-1.34>yafu-x64.exe "factor(@)" -batchfile modulus.txt


=== Starting work on batchfile expression ===
factor(3233)
=============================================
fac: factoring 3233
fac: using pretesting plan: normal
fac: no tune info: using qs/gnfs crossover of 95 digits
div: primes less than 10000
Total factoring time = 0.0000 seconds


***factors found***

P2 = 53
P2 = 61

ans = 1

eof; done processing batchfile

在线因分解工具

https://zh.numberempire.com/numberfactorizer.php?number=3233
http://www.atool.org/quality_factor.php
http://www.factordb.com/index.php?query=920139713

RSA攻击方法

模数n攻击

  • 暴力分解n
  • 模不互素
  • 共模攻击

公钥指数e相关攻击

  • 小公钥指数攻击
  • RSA衍生算法 – Rabin算法的攻击

私钥指数d相关攻击

  • d泄漏攻击
  • Wiener’s Attack

Coppersmith 相关攻击

  • Basic Broadcast Attack
  • Broadcast Attack with Linear Padding
  • Related Message Attack
  • Coppersmith’s short-pad attack
  • Known High Bits Message Attack
  • Factoring with High Bits Known
  • Boneh and Durfee attack

RSA 选择密文攻击

  • 任意密文解密
  • RSA parity oracle

RSA 侧信道攻击

Bleichenbacher’s attack

使用量子计算机攻击-秀尔算法

http://www.freebuf.com/news/75346.html