RSA算法体系研究

「 密码学 」 January 03, 2020

RSA算法体系研究

Words count 23k Reading time 21 mins. Read count 0

在打0CTF时看到了RSA的那题，但是不会做，于是先学习一波RSA吧，算做入门，自己也喜欢数学，正好积累下，RSA是非对称加密，相对于DES对称加密而言的，下面进去正题。

一、欧拉定理：

如果两个正整数a和n互质，则n的欧拉函数 φ(n) 可以让下面的等式成立：

image.png

这是个很重要的公式，先来理解下，首先n = pq（q和p互为质数），欧拉函数 φ(p) = p-1（表示与p互质的数的个数为p-1个，下同）， φ(q) = q-1，所以 得到

推理1：φ(n) = φ(p)φ(q) = (p-1)(q-1)

上式可以转成

a^φ(n)%n = 1，也就是说a的φ(n)次幂对n求余为1，设φ(n)=k=(p-1)*(q-1)， 也就是a^k%n=1，那么可以知道a^kt%n=1也成立~

二、密钥的计算获取过程

密钥的计算过程为：首先选择两个质数p和q，令n=p*q。

令k=ϕ(n)=(p−1)(q−1)，上面讲过了，这里再给一个推理：

推理2：ab%n=a%nb%n(乘积的余数等于余数的乘积)

证明：假设a和b除以n的余数为c1,c2。a和b可以写成a=nt1+c1,b=nt2+c2。那么，ab=n2t1t2+nt1c2+nt2c1+c1c2=n(nt1t2+t1c2+t2c1)+c1c2=nt3+c1c2。因此ab除以n的余数为c1c2。即ab%n=a%nb%n

选择任意整数d，保证其与k互质，

取整数e，使得de%k=1。也就是说de=kt+1，t为某一整数，这样私钥d和公钥e就生成了，这里d就是e相对于k的逆元，（这里知道了e就可以求d，或者知道了d就可以求e），那么逆元怎么求呢？有很多方法，这里推荐个最好用的方法：

1
d = gmpy2.invert(e,k)

接着看一下一个重要的推理：

z为小于n的任意一个数，z^(de)%n=z^(kt+1)%n=(z^(kt)z)%n=((z^kt)%n*z%n)%n= z%n=z （z%n<n，所以再求一次余还是z） ，解释下，因为(z^k)%n = 1，所以(z^kt)%n=1，得到

推理3：z^(de)%n=z%n=z

三、加密与解密过程

A发送信息m给B，利用公钥e加密成密文c，B利用私钥d解密出明文信息m

1、加密

设明文为m，密文为c，首先把用户A发送的信息字符m转成整数，找到一个与m互为质数的n，

随机地选择一个正整数e，1<e<ф(n)且gcd(e，ф(n))=1，将e公开，根据ed=1 mod ф(n)，求出d，并对d保密。

即可生成公钥对(n，e)和私钥对(n，d)，加密公式：m^e%n = c，加密结束。

2、解密

解密公式：c^d%n=m，解密结束。

3、证明解密过程的正确性：
推理4：(m^e%n)^d=m^ed%n=m%n

证明：设[m^e/n]表示求余，[m^e/n]^d = [m^ed/n^d]，可以看成[[m^ed/n]/n]…/n]，这里有d个n，因为算出第一个余数x，一定有x<n，后面恒有[x/n]=x，所以可以知道，(m^e%n)^d=m^ed%n（余数的幂等于被除数的幂的余数）

因为m^e%n = c，

所以c^d%n = (m^e%n)^d%n = (m^ed%n)%n =m%n=m（m<n）

得证合理性！

四、做一波题目巩固下

1、模数分解型：

57518754770

给了c、n和e，要求m，最简单的题型，把n写入我们的pcat.txt，这里直接先雅虎分解n：

1
./yafu-x64.exe "factor(@)" -batchfile pcat.txt   #输入完n记得换行

57518779973

得到了p和q就好办了，直接求逆元得到d，最后解密即可：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#coding=utf8
#openssl rsa -pubin -in pubkey.pem -text -modulus
from gmpy2 import *
import libnum
from Crypto.Util.number import *
n=3161262255255421133292506694323988711204792818702640666084331634444148712428915950639954540974469931426618702044672318134908678730641981414037034058320359158246813987154679178159391832232990193738454116371045928434239936027006539348488316754611586659587677659791620481200732564068367148541242426533823626586574915275209508300120574819113851895932912208783915652764568319771482309338434364094681579135086703127977870534715039005822312878739611630155714313119545610939253355808742646891815442758660278514976431521933763272615653261044607041876212998883732724662410197038419721773290601109065965674129599626151139566369
e=65537
c=631583911592660652215412683088688785438938386403323323131247534561958531288570612134139288090533619548876156447498627938626419617968918299212863936839701943643735437264304062828205809984533592547599060829451668240569384130130080928292082888526567902695707215660020201392640388518379063244487204881439591813398495285025704285781072987024698133147354238702861803146548057736756003294248791827782280722670457157385205787259979804892966529536902959813675537028879407802365439024711942091123058305460856676910458268097798532901040050506906141547909766093323197363034959926900440420805768716029052885452560625308314284406
p = 56225103425920179745019828423382255030086226600783237398582720244250840205090747144995470046432814267877822949968612053620215667790366338413979256357713975498764498045710766375614107934719809398451422359883451257033337168560937824719275885709824193760523306327217910106187213556299122895037021898556005848927
q = 56225103425920179745019828423382255030086226600783237398582720244250840205090747144995470046432814267877822949968612053620215667790366338413979256357713975498764498045710766375614107934719809398451422359883451257033337168560937824719275885709824193760523306327217910106187213556299122895037021898556005848447

d = invert(e,(p-1)*(q-1))
m = pow(c,d,n)
print long_to_bytes(m)

57518790052

*公约数模数分解，c1，e1，n1和c2，e2，n2，这里先测试下gcd(n1,n2)!=1,那么我们就可以尝试分解n1和n2，就可以得到想要的q和p值。

2、共模攻击型：

由原理部分我们可以知道，e的范围是1<e<ϕ(n)，也就是说e是可以随机选取的，这时候，就可以使用不同的e对相同的m加密，得到2个不同的密文，而共模体现在使用的模数n不变，画个图：

57518809717

演示共模攻击，重点是找到r和s，因为n比较难分解，如果满足下面的条件：

1
2
1 = gcd(e1,e2)
r*e1 + s*e2 = 1

这里计算r和s要用到扩展欧几里得算法：

1
2
3
a = gcdext(e1,e2)
s = a[1]
r = a[2]

57518911657

这里可以知道m>n：

1
(c1**s)*(c2**r) = m%n

通过变换可以知道：

1
m = (c1**s)*(c2**r)%n

讲完了原理，下面开始做题：

57519678948

这里给出了2组的信息，n，e1，e2，c1，c2，这题直接yafu是跑不出n的分解情况的，所以是共模攻击类型：

按照我们前面所说的解题顺序，可以知道结果。

那么我们的脚本就如下：

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=utf8
#openssl rsa -pubin -in pubkey.pem -text -modulus
from gmpy2 import *
import libnum
from Crypto.Util.number import *
n = 21660190931013270559487983141966347279666044468572000325628282578595119101840917794617733535995976710097702806131277006786522442555607842485975616689297559583352413160087163656851019769465637856967511819803473940154712516380580146620018921406354668604523723340895843009899397618067679200188650754096242296166060735958270930743173912010852467114047301529983496669250671342730804149428700280401481421735184899965468191802844285699985370238528163505674350380528600143880619512293622576854525700785474101747293316814980311297382429844950643977825771268757304088259531258222093667847468898823367251824316888563269155865061
e1 = 65537
c1 = 11623242520063564721509699039034210329314238234068836130756457335142671659158578379060500554276831657322012285562047706736377103534543565179660863796496071187533860896148153856845638989384429658963134915230898572173720454271369543435708994457280819363318783413033774014447450648051500214508699056865320506104733203716242071136228269326451412159760818676814129428252523248822316633339393821052614033884661649376604245744651142959498917235138077366818109892738298251161767344501687113868331134288984466294415889635863660753717476594011236542159800099371872396181448655448842148998667568104710807411358117939831241620315

e2 = 70001
c2 = 8180690717251057689732022736872836938270075717486355807317876695012318283159440935866297644561407238807004565510263413544530421072353735781284166685919420305808123063907272925594909852212249704923889776430284878600408776341129645414000647100303326242514023325498519509077311907161849407990649396330146146728447312754091670139159346316264091798623764434932753276554781692238428057951593104821823029665203821775755835076337570281155689527215367647821372680421305939449511621244288104229290161484649056505784641486376741409443450331991557221540050574024894427139331416236263783977068315294198184169154352536388685040531

a = gcdext(e1,e2)
#扩展欧几里得算法求s和r
if a[1]<0:
	s = -a[1]
	r = a[2]
	c1 = invert(c1, n)
if a[2]<0:
	s = a[1]
	r = -a[2]
	c2 = invert(c2, n)
#这里一个数的负数次幂求解，用中国剩余定理去求出对应的逆元再运算
m = (pow(c1,s,n)*pow(c2,r,n))%n
print long_to_bytes(m)

57519702410

3、小指数明文爆破攻击

这里如果使用的e太小的话，比如e=3，而且m也比较小的情况下，就有这种可能：

1
c+k*n<m^3<(k+1)*n+c

那么我们可以通过爆破的方式直接开3次根，解得m值，来一道题看看：

57520553436

小指数的e，所以我们直接尝试着使用小指数明文爆破的方式去做这题：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#coding=utf8
#openssl rsa -pubin -in pubkey.pem -text -modulus
from gmpy2 import *
import libnum
from Crypto.Util.number import *
n = 47966708183289639962501363163761864399454241691014467172805658518368423135168025285144721028476297179341434450931955275325060173656301959484440112740411109153032840150659
e = 3
c = 10968126341413081941567552025256642365567988931403833266852196599058668508079150528128483441934584299102782386592369069626088211004467782012298322278772376088171342152839
i = 0
while 1:
	m = iroot(c+i*n,3)
	if m[1]==1:
		print long_to_bytes(m[0])
		break
	i += 1

57520561484

4、选择密文攻击

这里相当于给了一个orancle，攻击者拥有了加密和解密的服务，但是无法直接获得想要的n和e，我们只知道c，这时如果我们选择了一个r，满足r<n，可以知道：

1
2
3
4
5
6
7
8
9
10
11
若x = r^e mod n
则r = x^d mod n
得到y = x*c mod n
选择t = r^(-1) mod n
选择u = y^d mod n
那么我们有：
t*u mod n = ((r^(-1) mod n)*(y^d mod n)) mod n
=(r^(-1)*(x^d)*(c^d)) mod n
=(r^(-1)*r*c^d) mod n
=c^d mod n
=m

由此通过选择密文攻击的方式，我们可以解密出明文。

5、广播攻击

广播攻击是低指数攻击的一种，通常情况下，是利用相同的e对不同的n进行加密，这样我们就可以得到很多组同余的方程式：

1
2
3
4
5
6
7
c1≡m^e mod n1
c2≡m^e mod n2
c3≡m^e mod n3
对上述等式运用中国剩余定理，可以得到：
cx≡m^e mod n1n2n3
这里的e一般是小指数，比如3或者9
可以知道m^e = cx mod n1n2n3

已经知道d、e和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
32
import random  
def gcd(a, b):  
   if a < b:  
     a, b = b, a  
   while b != 0:  
     temp = a % b  
     a = b  
     b = temp  
   return a  
def getpq(n,e,d):
    p = 1  
    q = 1  
    while p==1 and q==1:  
        k = d * e - 1  
        g = random.randint ( 0 , n )  
        while p==1 and q==1 and k % 2 == 0:  
            k /= 2  
            y = pow(g,k,n)  
            if y!=1 and gcd(y-1,n)>1:  
                p = gcd(y-1,n)  
                q = n/p  
    return p,q  

n=0x96ed2727e4446e26c84552a9a19640c7d720c9b6e661cfcfec03463e92a9d0b228ddc9847c0daa137a19db67294626c535fe71c388f6ea3eb8cb5dbf09a84374eb021c9297a29394cf77da157c1b8be77b09a4fcbe54bf3dc93d33539e842766ad8e38369093ddc034ac32583a48e299a4d8b31b606b1729298ee136664b8b77
e=0x10001
d=0x7d12e57b1aa157038ebe5c45b56256270671e6984b0dcdf10a2ea07ce480143240c9a3e1c60870e499306a717073f157476aa88e99a7bdf1e2a4adf8ce21025cc6c05035c4a1d7e3b6f061464872e65118384999f0154f3c1761fa68d4685126b7fc98f4c2cdc41c98aa4e099a868a89099dd2170664647efca2c8d8e06a2e49
# phi = 0x96ed2727e4446e26c84552a9a19640c7d720c9b6e661cfcfec03463e92a9d0b228ddc9847c0daa137a19db67294626c535fe71c388f6ea3eb8cb5dbf09a84373552f3ae326ed80690d123ce71b3059d75095dcf839cdd0dc79ff6077ae979b1fe2267a0f698dd27cbc1adc82cba32a8289faf953279fdb3651f0a66d0cdbe478
p,q=getpq(n,e,d)
print("p=",p)
print("q=",q)
print(p*q==n)
print hex((p-1)*(q-1))

V1ct0r

Where there is a will,there is a way！
0%