RSA简单学习

简单学习RSA加密算法以及攻击方法

RSA简介

密钥体制

设$n=pq$,其中$p$,$q$都是素数,设$\mathcal{P=C=}\mathbb{Z_n}$,且定义

对于$K=(n,p,q,a,b)$,定义

$(x,y\in\mathbb{Z_n})$,值$n$和$b$组成公钥,且值$p$,$q$和$a$组成私钥

事实上,RSA可以这么来理解,假设Alice和Bob要通信,为了确保两人之间的安全性,Alice选取这样的通信方式

  1. Alice选取两个不同的整数$p$,$q$,然后令$N=p\cdot q$
  2. Alice利用$N$,计算$r=\phi(N)=\phi(p)\cdot \phi(q)=(p-1)\cdot (q-1)$
  3. Alice再找一个$e<r$且$e$和$r$互质
  4. Alice还需计算$d$,使得$e\cdot d\equiv 1(\mathrm{mod}r)$
  5. Alice得到了公钥$(N,e)$,和私钥$(N,d)$,并将公钥发送给Bob
  6. Bob利用公钥加密信息$m$,即$c\equiv m^e(\mathrm{mod}N)$,并将$c$发送给Alice
  7. Alice利用私钥解密信息$c$,即$m\equiv c^d(\mathrm{mod}N)$

可以解密的原因在于

由于

由费马欧拉定理

所以

下面用一个例子来具体说明

  1. Alice选取$p=101,q=113$,$N=101\cdot 113=114113$
  2. Alice计算$r=\phi(N)=\phi(p)\cdot\phi(q)=(p-1)\cdot(q-1)=100\cdot112=11200$
  3. Alice计算$e$,由于$r=11200=2^6\cdot 5^2\cdot 7$,则$e$不能为$2,5,7$的倍数(实际上Alice不会分解$\phi(N)$,而是利用拓展欧几里得算法来验证$gcd(r,e)=1$,同时计算出$e^{-1}$,假定此处选$e=3533$
  4. Alice计算$d$,$d=e^{-1}(\mathrm{mod}r)=6597$
  5. Alice得到了公钥$(114113,3533)$,私钥$(114113,6597)$,Bob也得到了公钥$(114,113)$
  6. Bob利用公钥加密信息$m=9726$,即$c\equiv m^e(\mathrm{mod}N)=9726^{3533}(\mathrm{mod}\ 114113)\equiv 5761$
  7. Alice利用私钥解密信息$c=5761$,即$m\equiv c^d(\mathrm{mod}N)=5761^{6597}(\mathrm{mod}\ 114113)\equiv 9726$

RSA算法的安全性基于相信加密函数$e_K(x)=x^e(\mathrm{mod}N)$是一个单向函数这一事实,Alice之所以能解密是因为知道$N=p\cdot q$,所以可以计算$r=\phi(N)=\phi(p)\cdot \phi(q)=(p-1)\cdot (q-1)$,进而可以解得$d=e^{-1}(\mathrm{mod}r)$,而其余人只知道公钥和密文,想破解密文,只能试图将$N$分解,爆破$p,q$的值,当$N$很大时,这是不可破的

目前的分解算法能够分解512比特二进制的整数,为了安全着想,一般推荐选取$p,q$均为512比特位的素数,那么$n$就是1024比特位的模数,分解这样长度的整数大大超出了现有的分解因子算法的能力,不过随着量子计算机的发展,大整数分解的难题也会被超高算力解决

代码实现

python在计算这方面很方便,因此使用python来简单实现

首先我们先假设$p,q$是特定的,那么计算$r$的方法也就是按照定义给出

1
2
def phi(p, q):
return (p - 1) * (q - 1)

再假设$e$也是特定的,接下来要判断$ (e,r)=1$,可由广义欧几里得算法得出

1
2
def gcd(a, b):
return a if b == 0 else gcd(b, a % b)

接着要计算$d=e^{-1}(\mathrm{mod} r)$,即解同余式$e\cdot d\equiv 1(\mathrm{mod} r)$,该式子求解我们可以利用如下关系式

该式即为贝祖等式,取$d=s$,贝祖等式的求解过程如下

$j$ $s_j$ $t_j$ $q_{j+1}$ $r_{j+1}$
-3 a
-2 1 0 b
-1 0 1 $q_0$ $r_0$
0 $s_0$ $t_0$ $q_1$ $r_1$
$n-1$ $s_{n-1}$ $t_{n-1}$ $q_n$ $r_n$
n $s_n$ $t_n$ $q_{n+1}$ $r_{n+1}=0$

其中对于$j=0,1,2,\cdots ,n$,有

当$r_{n+1}=0$时,$s=s_n$,$t=t_n$,使得$s\cdot a+t\cdot b=(a,b)$成立,且$\mathrm{gcd}(a,b)=r_n$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def ext_euclid(a, b):
s = [1, 0]
t = [0, 1]
q = [0, 0]
r = [a, b]
i = 2
while r[len(r) - 1] != 0:
q.append(r[i - 2] / r[i - 1])
r.append(r[i - 2] % r[i - 1])
s.append(s[i - 2] - q[i] * s[i - 1])
t.append(t[i - 2] - q[i] * t[i - 1])
i += 1
return r[len(r) - 2], s[len(s) - 2], t[len(t) - 2]


def multi_inverse(e, r):
ans = ext_euclid(e, r)
if ans[0] == 1:
return ans[1] % r
return -1

接着就可以加密了,加密函数和解密函数其实本质是一样的,都是模运算中的指数运算,只不过是指数不同,python中的pow函数已经具备这样的功能了,这里简单实现一下

通常要对大整数模$m$和大整数$n$计算

当然可以递归的计算,需要进行$n-1$次运算

观察发现

可以优化模$m$运算,将指数$n$写成二进制形式

则模指数运算可化为下式,最多做$2[\mathrm{log}_2n]$次乘法

求解过程如下

$i$ $n_i$ $a_i$ $b_i$
0 $n_0$ $a_0$ $b_0$
1 $n_1$ $a_1$ $b_1$
$k-2$ $n_{k-2}$ $a_{k-2}$ $b_{k-2}$
$k-1$ $n_{k-1}$ $a_{k-1}$ $b_{k-1}$

其中对于$i=0,1,2,\cdots ,k-1$,有

最后的$a_{k-1}$即为$b^n(\mathrm{mod}m)$

1
2
3
4
5
6
7
8
def poww(b, n, m):
a = b**(n & 1)
n = n >> 1
while n != 0:
b = b**2 % m
a = a * (b**(n & 1)) % m
n = n >> 1
return a

基于上述代码,我们就可以实现RSA的加解密了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
p = 101
q = 113
N = p * q
r = phi(p, q)
e = 3533
d = multi_inverse(e, r)
pub = (N, e)
pri = (N, d)
m = 9726
c = poww(m, e, N)
j = poww(c, d, N)

print "p: %d q: %d N: %d" % (p, q, N)
print "r: %d e: %d d: %d" % (r, e, d)
print "m: %d encode(m): %d" % (m, c)
print "c: %d decode(c): %d" % (m, j)
1
2
3
4
p: 101 q: 113 N: 11413
r: 11200 e: 3533 d: 6597
m: 9726 encode(m): 5761
c: 9726 decode(c): 9726

当然python也有相关的密码库使用,安装gmpy2和pycrypto库,使用也很方便,不过gmpy2的安装比较麻烦,详细可以去搜索一下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
# coding:utf-8
import gmpy2
from Crypto.Util.number import *

p = getPrime(100) # 取100比特位数的随机素数
q = getPrime(100)
n = p * q
r = (p - 1) * (q - 1)
print "p: %d q: %d \nn: %d" % (p, q, n)
e = getPrime(50)
d = inverse(e, r)
print "e: %d d: %d" % (e, d)
messgae = "Hello RSA"
m = bytes_to_long(messgae) # 字符串和整数之间的转换
print " code: %d" % m
en = pow(m, e, n)
print "encode: %d" % en
de = pow(en, d, n)
print "decode: %d" % de
print long_to_bytes(de)
1
2
3
4
5
6
7
p: 999888327573055247949516599603 q: 1059527615891715252132953467667 
n: 1059409295871433637249789092446097120226832968229597245536201
e: 1074714102821353 d: 387903743304521283807735432973179496419127520601191722810881
code: 1335473908826942624577
encode: 626186704828904039570319502278290494028394937864340073481856
decode: 1335473908826942624577
Hello RSA

公钥/密钥格式

RSA的公钥密钥在存储和传播的过程中当然不是像上述那样$(e,N),(d,N)$,这样存放,而是有其特定的格式

  • DER

Distinguished Encoding Rules (DER) is a binary serialization of ASN.1 format. It is often used for cryptographic data such as certificates, but has other uses.

DER就是ASN.1格式的二进制形式

  • PEM

PEM格式是将DER进行base64编码,经解码后还原成DER格式

PEM格式是纯文本文件,其中存了许多密钥或证书对象,每个对象都是由 “—–BEGIN …—–” 开头 “—–END …—–” 为结尾的这样的格式进行存储,如下

1
2
3
4
5
6
-----BEGIN RSA PUBLIC KEY-----
MIGfMA0GCSqGSIb3DQEBAQUAA4GNADCBiQKBgQChHmaw+WUhWrStdxWBcAR39i2e
3yz+vfLiDALeTpWIH1jKiYtvw4nMg6453pXAJSvPn7mKaiGiC3USIt8qTL4eCPi9
yNRDpZ1JRHI8M87VYB4c9KMk6IuVFiYyZ4MBTP87t89yeL9EOrAD0eFgi5fPx3g8
b9QrmnyPhMVjP7ct+wIDAQAB
-----END RSA PUBLIC KEY-----

公钥密钥的ASN.1格式也是不同的,当然也分有PKCS #1和PKCS #8两种格式,下面是PKCD #1格式的

公钥的ASN.1格式通常为

1
2
3
4
RSAPublicKey ::= SEQUENCE {
modulus INTEGER, -- n
publicExponent INTEGER -- e
}

密钥的ASN.1格式通常为

1
2
3
4
5
6
7
8
9
10
11
12
RSAPrivateKey ::= SEQUENCE {
version Version,
modulus INTEGER, -- n
publicExponent INTEGER, -- e
privateExponent INTEGER, -- d
prime1 INTEGER, -- p
prime2 INTEGER, -- q
exponent1 INTEGER, -- d mod (p-1)
exponent2 INTEGER, -- d mod (q-1)
coefficient INTEGER, -- (inverse of q) mod p
otherPrimeInfos OtherPrimeInfos OPTIONAL
}

可以看到,公钥只能拿到$n$,$e$的值,私钥是有全部参数的

可以使用pycryptodome模块来快速生成密钥对,密钥对的存储与读取

1
2
3
4
5
6
7
8
9
10
11
12
13
from Crypto.PublicKey import RSA

key = RSA.generate(1024)
f = open("mykey.pem", "wb")
f.write(key.export_key("PEM"))
f.close()
f = open("mykey.pem", "r")
key = RSA.import_key(f.read())
print key.p
print key.q
print key.n
print key.e
print key.d
1
2
3
4
5
9614464373834197078834725819880155850689906840963153579458105697290188042084255637109603138231222362294240363535389934309817977723512190851734907795330477
11349265977109359569032111006269962623184443937724314789199144289279704766338463427996951734082233845832195796473653279222152778683030713820969048265189139
109117113406086495626328833349482229819865023595458750195021213684473482919029514880442301058625364597290440890952709020012899385586954577691695735570153177537253667898602049764359650446770654445315445052050312259055733091452112003117102187751182635970898989494232721487374551211434125015598402563973416089303
65537
40886658741066360576403514969608543535505521833982033485498816614273087264333243769458803227133727183356903077027109501570971668093730923972335813027698110471581123555625828682995376600285145769278107205319724568252189104321708622973810162243279255840109610206709058997074357225587419816804857167286360387641

当然也可以直接读公钥,不过只能取到$e$,$n$的值

RSA密码分析

RSA的安全性在于大整数分解的难题,但是攻击RSA密码体制的最明显方式就是试图分解公开模数$N$,当然也有针对公钥、密钥的攻击,侧信道攻击,选择明文攻击等

模数攻击

对于大整数分解最有效的三种算法就是二次筛法(quadratic sieve)、椭圆曲线分解算法(elliptic curve factoring)和数域筛法(number field sieve),当然还有著名的包括Pollard的$\rho$方法(rho-method)和$p-1$算法、William的$p+1$算法、连分式算法(continued fraction)、试除法(trial division)

暴力分解

当$N$足够小时,比如比特位数小于512的时候,可以尝试爆破每一个值,来获得$p$,$q$

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

print bf(322831561921859)
1
(13574881, 23781539)

p,q选取不当

当$p$,$q$选取不当的时候,也可以进行攻击

|p-q|很大

这种情况,某一个值必定很小,则暴力分解具有一定的可行性

1
2
3
4
5
6
7
8
9
10
def bf(n):
i = 3
while i < n:
if n % i == 0:
return i, n / i
i += 2


n = 10383841723631405391142277711740545301295283570059262478017275067196808038213372865035023699844199641752369181197875854506822943839335574218715733520612434279158378207807225419712681150812446108834225562499843378488583475212561277470383990333682307577817588424786923362983929426327938412427977703603508438549587
print bf(n)
1
(79, 131441034476346903685345287490386649383484602152648892126800950217681114407764213481455996200559489136105939002504757651985100554928298407831844728109018155432384534276040828097628875326739824162458551424048650360614980698893180727473215067514965918706551752212492700797264929447189093828202249412702638462653L)

当然这是比较理想化的模型,实际上并没有什么用处

|p-q|很小

因为

当$|p-q|$很小时

通过遍历$\sqrt{n}$附近的整数$x$,得$x^2-n$是一个整数,设为$y$,则

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# coding: utf-8
import gmpy2
from Crypto.Util.number import *
n = 172355971411815348492469043443924510983571094325817726067049399577371757842171934011753547469827430648060595944847795114807511062944175009125030776287884569163222526575198366744310542551747620002671662518425259691326146606518945918794536821807016661091041047097679532806514241211388008811662625886196021773385
base = gmpy2.iroot(n, 2)[0]
x = 0
y = 0
i = 1
while i < 1e2:
s = base + i
ans = gmpy2.iroot(s * s - n, 2)
if ans[1] == True:
x = s
y = ans[0]
break
i += 2
p = x + y
q = x - y
print "p: %d\nq: %d\nn: %d" % (p, q, p * q)
1
2
3
p: 13128441316920122048539704150044265974748946166426893797203721014318534205222290428670497764369950571559577155742270764247628030964962438281290801010127615
q: 13128441316920122048539704150044265974748946166426893797203721014318534205222290428670497764369950571559577155742270764247628030964962422218901253738377399
n: 172355971411815348492469043443924510983571094325817726067049399577371757842171934011753547469827430648060595944847795114807511062944175009125030776287884569163222526575198366744310542551747620002671662518425259691326146606518945918794536821807016661091041047097679532806514241211388008811662625886196021773385

p-1光滑

当$p$是$N$的因数,且$p-1$光滑的时候,可以使用 Pollard’s p − 1 算法来分解 $N$,但是也不是完全可以成功的

光滑数(smooth number)的概念是如果一个整数的所有素因子都不大于B,我们称这个整数是B-Smooth数

模光滑数(powersmooth number)的概念是如果一个整数的所有素因子的对应指数次幂不大于B,我们称这个整数是B-powersmooth数

如$1620=2^2\cdot 3^4\cdot 5$,$1620$是5-smooth​数,​16-powersmooth数

Pollard’s p − 1 算法通过输入一个待分解的整数$N$和一个预先指定的界数$B$,来求出因数$p$

该算法的原理是,假设$N$是一个合数,其中一个质数$p$,由费马小定理有

如果$x\equiv1(\mathrm{mod}p)$,就有$p|\mathrm{gcd}(x-1,n)$

该算法的思想是构造$p-1$,其有多个素因子,并且每个素因子的powersmooth不超过B,开始时随机选取一个$x$,计算

如果有

那么就相当于找到了一个素数$p$,否则重新选取$B$

在算法的简单实现中,我们可以先计算

接着计算

如果$1<d<n$,则$d$就是因数$p$,否则就得重新选取$B$

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
# coding:utf-8
import gmpy2
from Crypto.Util.number import *


def pollard_p_1(n, B):
i = 2
a = 2
while i <= B:
a = pow(a, i, n)
i += 1
d = GCD(a - 1, n)
if 1 < d and d < n:
return d
return -1


n = 15770708441
B = 2
while B <= int(1e5):
p = pollard_p_1(n, B)
if p != -1:
print "p: %d\nq: %d" % (p, n / p)
break
B += 1
1
2
p: 135979
q: 115979

实际上$p-1=135978=2\cdot 3\cdot 131 \cdot 173$,因此当$B\geq173$时,满足$p-1|B!$,即可解

当然此算法的缺陷是要求$N$有一个因数$p$,$p-1$是光滑的,很容易在构造$N=p \cdot q$时使得此算法失效,一般是选取两大整数$p_1,q_1$,使得$p=2\cdot p_1+1,q=2\cdot q_1+1$,此时$N=p\cdot q$将能抵挡此算法的分解

p+1光滑

当$p$是$N$的因数,且$p+1$光滑的时候,可以使用 Williams’s p + 1算法来分解 $N$,但是也不是完全可以成功的

这个还不太懂,先放着

模不互素

当存在两个公钥,且两个公钥的模数不互素,很显然我们可以直接对两个模数求最大公因数,进而直接得到因数

共模攻击

当两个用户使用相同的模数$N$,不同的私钥时,加密同一明文消息的时候会存在共模攻击

假设两个用户的加密指数分别为$e_1$和$e_2$,且$\mathrm{gcd}(e_1,e_2)=1$,对同一明文进行加密

由于$e_1,e_2$互质,求解贝祖等式

得到$s,t$,由此可得

解出明文m

如果s或t为负数的时候,转换为正数,再把对应的$c_1$或$c_2$求自己的模逆,才能继续计算

计算N

在已知$N$和$\phi(N)$的情况下,是可以求解出$p,q$的,因为

使用$q=N/p$代入,求解方程

方程的两个根即为$p,q$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# coding: utf-8
import gmpy2
from Crypto.Util.number import *


def cal_from_phi(N, phi):
a = 1
b = -(N - phi + 1)
c = N
p = int((-b + pow(b * b - 4 * a * c, 0.5)) / (2 * a))
q = int((-b - pow(b * b - 4 * a * c, 0.5)) / (2 * a))
return p, q


print cal_from_phi(84773093, 84754668)
1
(9539, 8887)

解密指数

已知d

如果解密指数$e$和解密指数$d$已知,那么$N$是可以被分解的,为了保证安全性,此时重新选择一个加密指数$e$是不行的,必须重新选择模数$N$

该算法是一个Las Vegas型的随机算法,具有一定的几率计算成功,原理还不是很懂,先贴上一个简单实现,等日后在补上原理

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
# coding: utf-8
import gmpy2
from Crypto.Util.number import *


def cal_from_d(N, e, d):
r = e * d - 1
s = 2
while r % s == 0:
s *= 2
r = r / (s / 2)
w = getRandomRange(1, N)
x = GCD(w, N)
if 1 < x and x < N:
return x, N / x
v = pow(w, r, N)
if v % N == 1:
return -1, -1
v_ = 0
while v % N != 1:
v_ = v
v = pow(v, 2, N)
if v_ % N == N - 1:
return -1, -1
p = GCD(v_ + 1, N)
return p, N / p


N = 89855713
e = 34986517
d = 82330933
print cal_from_d(N, e, d)
1
2
3
4
➜  RSA /usr/bin/python /mnt/d/Crypto/RSA/test.py
(-1, -1)
➜ RSA /usr/bin/python /mnt/d/Crypto/RSA/test.py
(9871, 9103)

求解d

M.Wiener提出过一种攻击方式,在满足前提如下前提的时候,可以计算出$d$,称为低解密指数攻击

如果$N$的二进制表示有$l$比特位,那么当$d$的二进制表示位数小于$l/4-1$,$p$和$q$相距不太远的时候攻击有效

由于解密过程是要对密文进行$d$次幂,所以选择较小的$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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
# coding: utf-8
import gmpy2
from Crypto.Util.number import *


def cal_d(N, e):
q = [0]
a = e
b = N
while b != 0:
q.append(a / b)
t = a
a = b
b = t % b
r = a
cl = [1, q[1]]
d = [0, 1]
j = 2
while j < len(q):
cl.append(q[j] * cl[j - 1] + cl[j - 2])
d.append(q[j] * d[j - 1] + d[j - 2])
j += 1
if (d[j - 1] * e - 1) % cl[j - 1] == 0:
a = 1
b = -(N - (d[j - 1] * e - 1) / cl[j - 1] + 1)
c = N
if ((-b + pow(b * b - 4 * a * c, 0.5)) % (2 * a)) == 0:
p = int(((-b + pow(b * b + 4 * a * c, 0.5)) / (2 * a)))
else:
continue
if ((-b - pow(b * b - 4 * a * c, 0.5)) % (2 * a)) == 0:
q = int(((-b + pow(b * b - 4 * a * c, 0.5)) / (2 * a)))
else:
continue
if (p < N and q < N):
return p, q

return -1, -1


N = 160523347
e = 60728973
print cal_d(N, e)
1
(30594, 13001)

加密指数

当加密指数$e$比较小的时候,由于

我们很容易计算出

遍历一波$k$值使得上式为等式即可

Rabin是RSA的衍生密码算法,其加密指数$e$恒为2,加密是这样处理的

解密如下

由于$p,q$互质,求出贝祖等式

解出四个明文

如果$p\equiv q\equiv 3(\mathrm{mod}\ 4)$,则

四个明文都是可能解,实际中按照明文语义来排除

选择明文攻击

假设我们可以不知道$N,e$,但是存在一个交互加密自定义明文并回显,那么就可以使用选择明文攻击,如加密2,4,8,16

又因为

故而

求两式的最大公因数,很大概率是$N$

选择密文攻击

假设我们已经知道了$N,e$和密文$c$,还存在一个交互解密自定义密文并回显,当然这里不允许直接解密$c$

选择一个$x$使得$(x,N)=1$,构造密文

获得解密后的数据

进而可以求出明文$m$

现成工具

http://factordb.com/

factordb这个网站会首先查询这个整数是否有记录,有就会直接给出,是个很好用的网站

https://sourceforge.net/projects/yafu/

yafu这个项目是在本地尝试分解,内部集成了多种分解算法

https://github.com/Ganapati/RsaCtfTool

https://github.com/ius/rsatool

RSA python脚本

常见式子

总结

RSA就是基于数论的一种加密算法,这几天看下来,觉得自己的数学基础还是太薄弱了,很多都是一知半解的

还有很多种分析方式因为数学底子不好,根本无法理解下去,先占坑,等以后学好了信安数基再来写一写

参考

  1. CTF Wiki
  2. 《信息安全数学基础》
  3. 《密码学原理与实践》

  cryptorsa

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×