0%

RSA 常见攻击方法

Posted on In

1、共模攻击

描述：对同一明文m多次使用相同n，不同e加密，得到不同密文c

python描述

1
2
3
4
5
6
7
8
9
10
11
12
13
from Crypto.Util.number import *
from egcd import egcd

p = getPrime(32)
q = getPrime(32)
n = p * q

e1 = getPrime(16)
e2 = getPrime(16)

m = 123456
c1 = pow(m, e1, n)
c2 = pow(m, e2, n)

攻击原理

当GCD(e1, e2) == 1时，由扩展欧几里得算法可知必存在s1, s2使 e1s1 + e2s2 = 1，m = pow(m, e1s1+e2s2, n)，而pow(m, e1s1+e2s2, n) = pow(m, e1s1, n) * pow(m, e2s2, n) = pow(c1, s1, n) * pow(c2, s2, n)

python实现

1
2
3
4
5
6
from egcd import egcd
_, s1, s2 = egcd(e1, e2)
if s1 < 0:
    m = pow(inverse(c1, n), -s1, n) * pow(c2, s2, n) % n
else:
    m = pow(c1, s1, n) * pow(inverse(c2, n), -s2, n) % n

2、低解密指数攻击

描述：解密密指数d过小

pyhon 描述

1
2
3
4
d = 3
e = inverse(d, (p - 1) * (q - 1))
c = pow(m, e, n)
m = pow(c, d, n)

攻击原理

详情见Wiener

python实现

1
2
3
4
5
6
7
8
import owiener
e = 3047442173541658754667464233797118324917469250436575767227172319344577259865313428705759330024959317716760816959590728238918140105663188172228696589411452947738069773833351725455888549656717874059636289036277785342126992626060696063089487811946920569580454880169977542532087635095357205433679009382368108273

n = 135568509670260054049994954417860747085442883428459182441559553532993752593294067458983143521109377661295622146963670193783017382697726454953197805014428888491744355387957923382241961401063461549210355871385000347645387907568135032087942016502668629010859519249039662555733548461551175133582871220209515648241

d = owiener.attack(e, n)

print(d)

3、低加密指数攻击

3.1、明文较小

描述：e比较小，一般为3

pyhon 描述

1
2
e = 3
c = pow(m, e, n)

攻击原理

(m=c^d%n,n*x+m=c^d) => m=pow(n*x+c,1/e)，当n比较小时，可以成功开方。

python实现

1
2
3
4
5
6
7
8
9
from Crypto.Util.number import *
from gmpy2 import iroot

def smallEattack(c, e, n):
        for i in range(10 ** 10):
            res = iroot(n * i + c, e)
            if res[1]:
                print(res)
                break

3.2 Hastad广播攻击

描述：使用相同的加密指数 e 加密相同的信息，发送给多于e个不同的人，可能受到低加密指数广播攻击

pyhon 描述

1
2
3
4
e = 3
c1 = pow(m, e, n1)
c2 = pow(m, e, n2)
c3 = pow(m, e, n3)

攻击原理

考虑e=3，假设n1、n2、n3互素，否则可计算最大公约数直接得到p、q，由于n1、n2、n3互素，由中国剩余定理可求得m^e

python实现

1
2
3
4
5
6
7
8
9
from CRT import chinese_remainder
from gmpy2 import iroot

datas = [(5,92270627783020341903769877272635163757611737252302329401876135487358785338853904185572496782685853218459404423868889360808646192858060332110830962463986164014331540336037718684606223893506327126112739408023014900003600028654929488487584130630596342720833061628867179840913592694993869009133576053124769728363,83421434286602546493364204139182949897795123160498680670964040331447569764445309937195566103281638928183742488663157138572020817924561990979723444797045375101801354862472761507421896454904818874439231990567738173059815647539737800523632262742398190575822391771655932895657208471832891505814792263361394479317), (5,102900163930497791064402577447949741195464555746599233552338455905339363524435647082637326033518083289523250670463907211548409422234391456982344516192210687545692054217151133151915216123275005464229534891629568864361154658107093228352829098251468904800809585061088484485542019575848774643260318502441084765867,25585088950095290712328215701309273521406235982885781641137768116285362079062975527364909549362511146004390419156826709543326814581466248280564194951706937822088902607754944405407698735824315900942915322054614437632116732271787823814807624841386886185122143173564380877370643120953803688563589496390425159539), (5,90267480939368160749458049207367083180407266027531212674879245323647502822038591438536367206422215464489854541063867946215243190345476874546091188408120551902573113507876754578290674792643018845798263156849027209440979746485414654160320058352559498237296080490768064578067282805498131582552189186085941328701,44374979291120575503988741531987454898919254880086464254904878064332010355432423956182135846738023874326776872139229379943321321362822522900479438294291206287205647145759972233097276253408812699557305314344220807356024994977399840843758750494467535572805794732065369887057841293267499209427585419962565568495), (5,90673177193017332602781813187879442725562909473411994052511479411887936365983777106776080722300002656952655125041151156684340743907349108729774157616323863062525593382279143395837261053976652138764279456528493914961780300269591722101449703932139132398288208673556967030162666354552157189525415838326249712949,24086371701602948122317790211004032014326487279907486724991846810668564197542368948703436295770758262739732290677177527297040556666434577730354732397784651220918412407485171180732327730242552955646750279842251200227937257322414662213662054605527282812231172173474061845763736546747711105935349033514358348526), (5,90916739755838083837461026375700330885001446224187511395518230504776419813625940046511904838818660297497622072999229706061698225191645268591198600955240116302461331913178712722096591257619538927050886521512453691902946234986556913039431677697816965623861908091178749411071673467596883926097177996147858865293,23204039098754030513954332212496652705175644349879686639449689791620605370809827884267260830136516742466455588549253481016504796674014871020503543639681251834114159250986728840380777774144853925216884802529230212783759821262799845229436535491711201551797166082529740271577684082458494926929260818927584104158)]
nList = [x[1] for x in datas]
cList = [x[2] for x in datas]

print(len(datas))
print(iroot(chinese_remainder(nList, cList), datas[0][0]))

3.3、copperSmith部分信息攻击

描述：已知部分明文

python实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
i = 0x9876543210abcdef0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

smallE = [(5,92270627783020341903769877272635163757611737252302329401876135487358785338853904185572496782685853218459404423868889360808646192858060332110830962463986164014331540336037718684606223893506327126112739408023014900003600028654929488487584130630596342720833061628867179840913592694993869009133576053124769728363,83421434286602546493364204139182949897795123160498680670964040331447569764445309937195566103281638928183742488663157138572020817924561990979723444797045375101801354862472761507421896454904818874439231990567738173059815647539737800523632262742398190575822391771655932895657208471832891505814792263361394479317), (3,155266493936043103849855199987896813716831986416707080645036022909153373110367007140301635144950634879983289720164117794783088845393686109145443728632527874768524615377182297125716276153800765906014206797548230661764274997562670900115383324605843933035314110752560290540848152237316752573471110899212429555149,124929943232081828105808318993257526364596580021564021377503915670544445679836588765369503919311404328043203272693851622132258819278328852726005776082575583793735570095307898828254568015886630010269615546857335790791577865565021730890364239443651479580968112031521485174068731577348690810906553798608040451024), (5,102900163930497791064402577447949741195464555746599233552338455905339363524435647082637326033518083289523250670463907211548409422234391456982344516192210687545692054217151133151915216123275005464229534891629568864361154658107093228352829098251468904800809585061088484485542019575848774643260318502441084765867,25585088950095290712328215701309273521406235982885781641137768116285362079062975527364909549362511146004390419156826709543326814581466248280564194951706937822088902607754944405407698735824315900942915322054614437632116732271787823814807624841386886185122143173564380877370643120953803688563589496390425159539), (3,112306066601652819062206435724795595603085908011001671184332227488970057128128821831260649058569739569103298091727188365019228385820143813415009397359257831092635374404034997011441653286642458431865026213129412677064308342580757248577955071384972714557250468686599901682728173096745710849318629959223270431039,108387832390337770947361518376552702503741092284778824448943971792044922720461955035726863109418657218498659460663504872870862538725835055240750735576735249122665348803252691221869146679004017916359067454693701495389784159620341860394035373599823801288442604273046729873467936004227013186659110262247417571857), (5,90267480939368160749458049207367083180407266027531212674879245323647502822038591438536367206422215464489854541063867946215243190345476874546091188408120551902573113507876754578290674792643018845798263156849027209440979746485414654160320058352559498237296080490768064578067282805498131582552189186085941328701,44374979291120575503988741531987454898919254880086464254904878064332010355432423956182135846738023874326776872139229379943321321362822522900479438294291206287205647145759972233097276253408812699557305314344220807356024994977399840843758750494467535572805794732065369887057841293267499209427585419962565568495), (3,147733349387696521015664992396355145811249793103958464053225389476050097503928022819269482555955365534137156079172704297584033078453033637103720972881068435459202133846880715879894340131656691631756162323422868846616160423755883726450486845175227682329583615739797782025647376042249605775433971714513081755709,52253817590056116368273294519761274350847193477090280916373828903718796358618956145225746496960677477661151583828604021049936963779103440560630451125137344639503705880024677345063113240530798352727432768980751992926293801206779839157443722614687126711272753610923903360818026083573711899014859313677159790039), (5,90673177193017332602781813187879442725562909473411994052511479411887936365983777106776080722300002656952655125041151156684340743907349108729774157616323863062525593382279143395837261053976652138764279456528493914961780300269591722101449703932139132398288208673556967030162666354552157189525415838326249712949,24086371701602948122317790211004032014326487279907486724991846810668564197542368948703436295770758262739732290677177527297040556666434577730354732397784651220918412407485171180732327730242552955646750279842251200227937257322414662213662054605527282812231172173474061845763736546747711105935349033514358348526),(5,90916739755838083837461026375700330885001446224187511395518230504776419813625940046511904838818660297497622072999229706061698225191645268591198600955240116302461331913178712722096591257619538927050886521512453691902946234986556913039431677697816965623861908091178749411071673467596883926097177996147858865293,23204039098754030513954332212496652705175644349879686639449689791620605370809827884267260830136516742466455588549253481016504796674014871020503543639681251834114159250986728840380777774144853925216884802529230212783759821262799845229436535491711201551797166082529740271577684082458494926929260818927584104158)]

for data in smallE:
    n = data[1]
    c = data[2]
    e = data[0]
    for x in range(21):
        try:
            b = i + 0x100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 * x
            kbits=64
            PR.<x> = PolynomialRing(Zmod(n))
            f = (x + b)^e-c
            x0 = f.small_roots(X=2^kbits, beta=1)[0]
            print "x: %s" %hex(int(x0))

            print "m: %s" %hex(int(b + x0))
            print "%x" % e
        except:
            pass