RSA攻击方法总结

一个多月没学密码学方面的东西了…赶紧补补

相关定理

欧拉函数

设n是一个正整数,小于n且与n互素的正整数的个数称为欧拉函数,记为φ(n)。欧拉函数具有以下性质:

(1) 如果n是素数,则φ(n) = n-1
(2) 如果m和n互素,则φ(mn) = φ(m)φ(n)
(3) 如果

n = p1^a1 x p2^a2 ... x pt^at

其中,p1<p2<…<pt都是素数,ai>0(i=1, 2, …, t),则

φ(n) = n(1-1/p1)(1-1/p2)...(1-1/pt)

欧几里得除法

欧几里得除法是用于计算两个整数a和b的最大公因子d = gcd(a, b)的常用方法:

用较小数除较大数,再用出现的余数(第一余数)去除除数,再用出现的余数(第二余数)去除除数,如此反复,直到最后余数是0为止。如果是求两个数的最大公约数,那么最后的除数就是这两个数的最大公约数

使用python表示如下:

1
2
3
4
5
6
def gcd(m,n):
while n:
r=m%n
m=n #经过一次求余数,进入第二轮相除,即n的值扮演了被除数的角色
n=r #r的值扮演了余数的角色
return m #这里return m的原因是,n作为最后一轮的除数已经赋值给了m

扩展欧几里得除法

设a、b是两个不全为0的整数,则存在两个整数x,y,使得:gcd(a, b) = ax + by

使用python求x、y表示如下:

1
2
3
4
5
6
def egcd(a, b):
if a == 0:
return (b, 0, 1)
else:
g, y, x = egcd(b % a, a)
return (g, x - (b // a) * y, y)

普通RSA算法

1.秘钥生成

(1) 选取两个保密的大素数p和q
(2) 计算n = pq,φ(n) = (p-1)(q-1)
(3) 随机选取整数e,1<e<φ(n),满足gcd(e, φ(n)) = 1
(4) 计算d,满足de ≡ 1 mod φ(n)
(5) 公钥为(e, n),私钥为d

2.加密

c ≡ m^e mod n

3.解密

m ≡ c^d mod n

公钥加密文件

描述

此类题目一般会给一个公钥文件(结尾通常为.pem或.pub)和密文(如flag.enc)。公钥文件内容格式如下:

-----BEGIN PUBLIC KEY-----
MDwwDQYJKoZIhvcNAQEBBQADKwAwKAIhAMJjauXD2OQ/+5erCQKPGqxsC/bNPXDr
yigb/+l/vjDdAgMBAAE=
-----END PUBLIC KEY-----

可以使用openssl来提取e和n:

openssl rsa -in pubkey.pem -pubin -noout -text -modulus

也可使用Crypto库:

1
2
3
4
5
6
7
8
from Crypto.PublicKey import RSA
from Crypto.Util.number import inverse, long_to_bytes
from Crypto.Cipher import PKCS1_v1_5
import base64

public_key = RSA.importKey(open("pubkey.pem").read())
n = public_key.n
e = public_key.e

例题

pubkey.pem:

-----BEGIN PUBLIC KEY-----
MDwwDQYJKoZIhvcNAQEBBQADKwAwKAIhAMJjauXD2OQ/+5erCQKPGqxsC/bNPXDr
yigb/+l/vjDdAgMBAAE=
-----END PUBLIC KEY-----

flag.enc(hex):

6D 3E B7 DF 23 EE E1 D3 87 10 BE BA 78 A0 87 8E
0E 9C 65 BD 3D 08 49 6D DA 64 92 41 99 11 0C 79

解题思路

首先提取n和e:

1
2
3
4
5
from Crypto.PublicKey import RSA

public_key = RSA.importKey(open("pubkey.pem").read())
n = public_key.n
e = public_key.e

将n使用工具yafu分解(或在线分解质数网站:http://factordb.com),得到p和q;之后生成私钥文件:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
from Crypto.PublicKey import RSA
from Crypto.Util.number import inverse, long_to_bytes

p = 275127860351348928173285174381581152299
q = 319576316814478949870590164193048041239
nn = (p-1)*(q-1)
d = inverse(e, nn)

keypair = RSA.generate(1024)
keypair.p = p
keypair.q = q
keypair.e = e
keypair.n = n
keypair.d = d

private_key = keypair.exportKey().decode('utf-8')
f = open('private.pem', 'w')
f.write(private_key)

最后使用openssl解密即可:

openssl rsautl -decrypt -in flag.enc -inkey private.pem -out flag.txt 

多素数RSA算法

描述

多素数RSA系统可以使用超过两个素数的乘积作为模。秘钥生成算法如下:

(1) 选取k个保密的大素数p1,p2,…,pk
(2) 计算n = p1p2…pk,φ(n) = (p1-1)(p2-1)…(pk-1)
(3) 随机选取整数e,1<e<φ(n),满足gcd(e, φ(n)) = 1
(4) 计算d,满足de ≡ 1 mod φ(n)
(5) 公钥为(e, n),私钥为d

多素数RSA加密和解密算法与普通RSA的相同

例题

n= 703739435902178622788120837062252491867056043804038443493374414926110815100242619
e= 59159
c= 449590107303744450592771521828486744432324538211104865947743276969382998354463377
m=???

解题思路

首先将n分解,得到三个素数:

P1 = 1108609086364627583447802163
P2 = 810971978554706690040814093
P3 = 782758164865345954251810941

脚本:

1
2
3
4
5
6
7
8
9
10
11
12
n= 703739435902178622788120837062252491867056043804038443493374414926110815100242619
e= 59159
c= 449590107303744450592771521828486744432324538211104865947743276969382998354463377
p1 = 1108609086364627583447802163
p2 = 810971978554706690040814093
p3 = 782758164865345954251810941
from Crypto.Util.number import inverse, long_to_bytes
nn = (p1-1)*(p2-1)*(p3-1)
d = inverse(e, nn)
m = pow(c, d, n)
flag = long_to_bytes(m)
print(flag)

RSA共享素数攻击

描述

当使用了p、q1和p、q2生成了n1和n2,就可以说p被n1和n2共享了。如果我们知道了这两个n,那么就可以很容易得到p、q1和q2,因为此时:

p = gcd(n1, n2)
q1 = n1/p
q2 = n2/p

例题

flag=open("flag","rb").read()

from Crypto.Util.number import getPrime,bytes_to_long
p=getPrime(1024)
q=getPrime(1024)
e=65537
n=p*q
m=bytes_to_long(flag)
c=pow(m,e,n)
print c,e,n

p=getPrime(1024)
e=65537
n=p*q
m=bytes_to_long("1"*32)
c=pow(m,e,n)
print c,e,n

'''
output:
2482083893746618248544426737023750400124543452082436334398504986023501710639402060949106693279462896968839029712099336235976221571564642900240827774719199533124053953157919850838214021934907480633441577316263853011232518392904983028052155862154264401108124968404098823946691811798952747194237290581323868666637357604693015079007555594974245559555518819140844020498487432684946922741232053249894575417796067090655122702306134848220257943297645461477488086804856018323986796999103385565540496534422406390355987976815450744535949785073009043007159496929187184338592859040917546122343981520508220332785862546608841127597 65537 14967030059975114950295399874185047053736587880127990542035765201425779342430662517765063258784685868107066789475747180244711352646469776732938544641583842313791872986357504462184924075227433498631423289187988351475666785190854210389587594975456064984611990461126684301086241532915267311675164190213474245311019623654865937851653532870965423474555348239858021551589650169602439423841160698793338115204238140085738680883313433574060243600028500600824624358473403059597593891412179399165813622512901263380299561019624741488779367019389775786547292065352885007224239581776975892385364446446185642939137287519945974807727
3829060039572042737496679186881067950328956133163629908872348108160129550437697677150599483923925798224328175594483217938833520220087230303470138525970468915511111320396185482564783975435346354440035776909781158407636044986403819840648379609630039348895415045723208843631191252142600667607807479954194447237061080618370787672720344741413537975922184859333432197766580150534457001196765621678659952108010596273244230812327182786329760844037149719587269632133595149294067490955644893402708720284179715002149224068928828656515326446881791228638008572889331511945042911372915003805505412099102954073299010951896955362470 65537 14624662628725820618622370803948630854094687814338334827462870357582795291844925274690253604919535785934208081825425541536057550227048399837243392490762167733083030368221240764693694321150104306044125934201699430146970466657410999261630825931178731857267599750324918610790098952520113593130245010530961350592735239454337631927669542026935873535964487595433984902529960726655481696404006628917922241666148082741874033756970724357470539589848548704573091633917869387239324447730587545472564561496724882799495186768858324490838169123077051890332313671220385830444331578674338014080959653201802476516237464651809255679979
'''

解题思路

由题目可知第二次加密使用的q是相同的

脚本:

1
2
3
4
5
6
7
8
9
10
11
12
13
n1 = 14967030059975114950295399874185047053736587880127990542035765201425779342430662517765063258784685868107066789475747180244711352646469776732938544641583842313791872986357504462184924075227433498631423289187988351475666785190854210389587594975456064984611990461126684301086241532915267311675164190213474245311019623654865937851653532870965423474555348239858021551589650169602439423841160698793338115204238140085738680883313433574060243600028500600824624358473403059597593891412179399165813622512901263380299561019624741488779367019389775786547292065352885007224239581776975892385364446446185642939137287519945974807727
n2 = 14624662628725820618622370803948630854094687814338334827462870357582795291844925274690253604919535785934208081825425541536057550227048399837243392490762167733083030368221240764693694321150104306044125934201699430146970466657410999261630825931178731857267599750324918610790098952520113593130245010530961350592735239454337631927669542026935873535964487595433984902529960726655481696404006628917922241666148082741874033756970724357470539589848548704573091633917869387239324447730587545472564561496724882799495186768858324490838169123077051890332313671220385830444331578674338014080959653201802476516237464651809255679979
e = 65537
c = 2482083893746618248544426737023750400124543452082436334398504986023501710639402060949106693279462896968839029712099336235976221571564642900240827774719199533124053953157919850838214021934907480633441577316263853011232518392904983028052155862154264401108124968404098823946691811798952747194237290581323868666637357604693015079007555594974245559555518819140844020498487432684946922741232053249894575417796067090655122702306134848220257943297645461477488086804856018323986796999103385565540496534422406390355987976815450744535949785073009043007159496929187184338592859040917546122343981520508220332785862546608841127597

from Crypto.Util.number import GCD, long_to_bytes, inverse

q = GCD(n1, n2)
p1 = n1//q
nn1 = (p1-1)*(q-1)
d = inverse(e, nn1)
flag = pow(c, d, n1)
print(long_to_bytes(flag))

RSA共模攻击

描述

该攻击的基本条件:

  • 同一份明文m使用不同的秘钥加密了两次或两次以上
  • 生成秘钥时模数n相同但加密指数e不相同,e1、e2互素
  • 我们能拿到不同的密文c1、c2和模数n、加密指数e1、e2

此时可在不知道d1、d2的情况下解出m,原理详见文章

例题

n = 116547141139745534253172934123407786743246513874292261984447028928003798881819567221547298751255790928878194794155722543477883428672342894945552668904410126460402501558930911637857436926624838677630868157884406020858164140754510239986466552869866296144106255873879659676368694043769795604582888907403261286211
c1 = 78552378607874335972488545767374401332953345586323262531477516680347117293352843468592985447836452620945707838830990843415342047337735534418287912723395148814463617627398248738969202758950481027762126608368555442533803610260859075919831387641824493902538796161102236794716963153162784732179636344267189394853
c2 = 98790462909782651815146615208104450165337326951856608832305081731255876886710141821823912122797166057063387122774480296375186739026132806230834774921466445172852604926204802577270611302881214045975455878277660638731607530487289267225666045742782663867519468766276566912954519691795540730313772338991769270201
e1 = 1804229351
e2 = 17249876309

解题思路

脚本:

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
from Crypto.Util.number import inverse, long_to_bytes
from libnum import xgcd

def common_attack(n,c1,c2,e1,e2):
s = xgcd(e1, e2)
s1 = s[0]
s2 = s[1]
# 求模反元素
if s1 < 0:
s1 = - s1
c1 = inverse(c1, n)
elif s2 < 0:
s2 = - s2
c2 = inverse(c2, n)
m = pow(c1, s1, n) * pow(c2, s2, n) % n
return m

n = 116547141139745534253172934123407786743246513874292261984447028928003798881819567221547298751255790928878194794155722543477883428672342894945552668904410126460402501558930911637857436926624838677630868157884406020858164140754510239986466552869866296144106255873879659676368694043769795604582888907403261286211
c1 = 78552378607874335972488545767374401332953345586323262531477516680347117293352843468592985447836452620945707838830990843415342047337735534418287912723395148814463617627398248738969202758950481027762126608368555442533803610260859075919831387641824493902538796161102236794716963153162784732179636344267189394853
c2 = 98790462909782651815146615208104450165337326951856608832305081731255876886710141821823912122797166057063387122774480296375186739026132806230834774921466445172852604926204802577270611302881214045975455878277660638731607530487289267225666045742782663867519468766276566912954519691795540730313772338991769270201
e1 = 1804229351
e2 = 17249876309

result=common_attack(n,c1,c2,e1,e2)
print(long_to_bytes(result))

如果题目给了多组(>2组)c和n,那么需要通过遍历去找哪两个e是互素的,之后再使用上面的方法求解即可

e=1

描述

当e为1时:

c ≡ m^e mod n = m mod n
m = c + n*k (k=0,1,2...)

例题

N=0x180be86dc898a3c3a710e52b31de460f8f350610bf63e6b2203c08fddad44601d96eb454a34dab7684589bc32b19eb27cffff8c07179e349ddb62898ae896f8c681796052ae1598bd41f35491175c9b60ae2260d0d4ebac05b4b6f2677a7609c2fe6194fe7b63841cec632e3a2f55d0cb09df08eacea34394ad473577dea5131552b0b30efac31c59087bfe603d2b13bed7d14967bfd489157aa01b14b4e1bd08d9b92ec0c319aeb8fedd535c56770aac95247d116d59cae2f99c3b51f43093fd39c10f93830c1ece75ee37e5fcdc5b174052eccadcadeda2f1b3a4a87184041d5c1a6a0b2eeaa3c3a1227bc27e130e67ac397b375ffe7c873e9b1c649812edcd
e=0x1
c=0x4963654354467b66616c6c735f61706172745f736f5f656173696c795f616e645f7265617373656d626c65645f736f5f63727564656c797d

解题思路

脚本:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
from Crypto.Util.number import long_to_bytes

N=0x180be86dc898a3c3a710e52b31de460f8f350610bf63e6b2203c08fddad44601d96eb454a34dab7684589bc32b19eb27cffff8c07179e349ddb62898ae896f8c681796052ae1598bd41f35491175c9b60ae2260d0d4ebac05b4b6f2677a7609c2fe6194fe7b63841cec632e3a2f55d0cb09df08eacea34394ad473577dea5131552b0b30efac31c59087bfe603d2b13bed7d14967bfd489157aa01b14b4e1bd08d9b92ec0c319aeb8fedd535c56770aac95247d116d59cae2f99c3b51f43093fd39c10f93830c1ece75ee37e5fcdc5b174052eccadcadeda2f1b3a4a87184041d5c1a6a0b2eeaa3c3a1227bc27e130e67ac397b375ffe7c873e9b1c649812edcd
e=0x1
c=0x4963654354467b66616c6c735f61706172745f736f5f656173696c795f616e645f7265617373656d626c65645f736f5f63727564656c797d
n = int(N)
c = int(c)
k = 0
while 1:
m = c + n*k
s = long_to_bytes(m)
if '{' and '}' in str(s):
print(s)
break
else:
k += 1

费马小定理与二项式

描述

直接上结论:

已知x,y,n,且:

n = p*q
x = (p+q)^2019 mod n 
y = (p+2019)^q mod n

那么x - (y-2019)^2019 mod n是q的整数倍

例题

rsa.py:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
from Crypto.Util.number import *
flag = "flag{xxxxxxxxxxxxxxxxxxx}"
m = bytes_to_long(flag)

p = getPrime(512)
q = getPrime(512)
n = p*q
e = 65537

c = pow(m, e, n)

print(n)

print(c)

print(pow(p+q, 2019, n))

print(pow(p+2019, q, n))

cipher.txt:

96780461394033337689567108259893748486002236738582736851233917468787524740624888972342563373512353586255114495079107335758288612338495963159612655318462375582406898270689435326368556558777898332573467628654624176029376998056045209679733660069957700185941370295208768680659384859188808356284395145787167822039
40902682922928025118571286152821100197674619815758133392785930170320910852655524737284528223471081642113214606615949067348943884072834222360537528813694188078856744138052033683982573167279077201980728210288846946841629237854328330529467598310598928680582754313029091620726738078049238979066396109902383779474
1085028795352905556943262835596573622075429386738984173331064472484066570876869315098105988053006079365050850500671807631253369854693004975237940840141074816205938760953784453832187957129220977719685389206024588149832914477308077438518601216192362909946961689725801155118156088666938733672414905904034952121
58990774595434377063777726247309387841479057068955206198202064573296964307379687905049181435740384194830759666167579369083224550401718886673825411413076522799129655186877044125596908766674290986472905901356969650876446443052520830234766043256136817920934130392728788803076056174028811029278351458894807475631

解题思路

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
x = 1085028795352905556943262835596573622075429386738984173331064472484066570876869315098105988053006079365050850500671807631253369854693004975237940840141074816205938760953784453832187957129220977719685389206024588149832914477308077438518601216192362909946961689725801155118156088666938733672414905904034952121

y = 58990774595434377063777726247309387841479057068955206198202064573296964307379687905049181435740384194830759666167579369083224550401718886673825411413076522799129655186877044125596908766674290986472905901356969650876446443052520830234766043256136817920934130392728788803076056174028811029278351458894807475631

n = 96780461394033337689567108259893748486002236738582736851233917468787524740624888972342563373512353586255114495079107335758288612338495963159612655318462375582406898270689435326368556558777898332573467628654624176029376998056045209679733660069957700185941370295208768680659384859188808356284395145787167822039

c = 40902682922928025118571286152821100197674619815758133392785930170320910852655524737284528223471081642113214606615949067348943884072834222360537528813694188078856744138052033683982573167279077201980728210288846946841629237854328330529467598310598928680582754313029091620726738078049238979066396109902383779474

e = 65537

from Crypto.Util.number import GCD, inverse, long_to_bytes

q = GCD(x-pow(y-2019, 2019, n), n)
p = n//q

nn = (p-1)*(q-1)

d = inverse(e, nn)

print(long_to_bytes(pow(c, d, n)))

Wiener Attack

描述

当:

d < (N/3)^-4

或当e很大时

例题

N : 460657813884289609896372056585544172485318117026246263899744329237492701820627219556007788200590119136173895989001382151536006853823326382892363143604314518686388786002989248800814861248595075326277099645338694977097459168530898776007293695728101976069423971696524237755227187061418202849911479124793990722597
e : 354611102441307572056572181827925899198345350228753730931089393275463916544456626894245415096107834465778409532373187125318554614722599301791528916212839368121066035541008808261534500586023652767712271625785204280964688004680328300124849680477105302519377370092578107827116821391826210972320377614967547827619

enc : 38230991316229399651823567590692301060044620412191737764632384680546256228451518238842965221394711848337832459443844446889468362154188214840736744657885858943810177675871991111466653158257191139605699916347308294995664530280816850482740530602254559123759121106338359220242637775919026933563326069449424391192

解题思路

现成脚本:https://github.com/pablocelayes/rsa-wiener-attack

clone下来,编辑RSAwienerHack.py,在test_hack_RSA()函数中将n和e传进去,之后运行即可得到d,再根据d解出明文即可