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=kn 密文2790解密后为65
B使用A的公钥对明文m进行加密得到c,通过网络传输给A,A使用自己的私钥对密文c进行解密得到m。
工具
RSA Tool 2 对上面的数字进行测试
openssl 密钥生成与加密解密
生成私钥
1 | ➜ rsa ls |
生成的私钥格式为
1 | -----BEGIN RSA PRIVATE KEY----- |
这里1
2
3
4
5
6modulus:
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 | privateExponent: |
表示模反元素d。
1 | prime1: |
表示质数1 p。
1 | prime2: |
表示质数2 q。
通过私钥计算公钥
1 | ➜ rsa ls |
使用公钥加密
1 | ➜ rsa ls |
openssl rsautl -in msg.txt -out msg.txt.enc -inkey public.key -pubin -encrypt -pkcs这里-pkcs表示加密处理过程中数据的填充方式,默认为pkcs,其他的还有-oaep,-ssl,-raw
使用公钥加密
1 | ➜ rsa ls |
明文通过公钥加密后得到密文,再经过私钥解密后得到的明文与原明文相同。
现在假设我们只有公钥和明文加密后得到密文,我们想得到明文。根据前面的公式,要得到明文,需要知道私钥才行。
公钥由(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 | ➜ rsa ls |
因式分解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
50C:\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 pycrypto1
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
17C:\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.txt1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24C:\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