RSA爆破攻击方法汇总

Ant大约 3 分钟

RSA爆破攻击方法汇总

一、低加密指数分解攻击

特点： e=2或e=3，m与c的关系如下

m^e=k*n+c

情景一： 当k=0时，直接对密文开平方或者开三次方

gmpy2.isqrt( m ) 对m进行开平方计算

gmpy2.iroot( m , 3 ) 对m进行开三次方计算

脚本： RSA3.pyopen in new window

import gmpy2
import libnum

c = XXX

#开平方
m = gmpy2.isqrt(c)
#开三次方
# m = gmpy2.iroot(m,3)

m = int(m)
flag = libnum.n2s(m)
print(flag)

情景二： 当k!=0时，则要对k进行爆破。

m^e=k*n+c

思路一的代码做相应的修改

import gmpy2
import libnum

c = XXX
n = XXX
for k in range(10)
    #计算m^e
    me = c + k * n
    #开e次方
    m = gmpy2.iroot(me,e)
    m = int(m)
    flag = libnum.n2s(m)
    print(flag)

二、Roll按行加密

特点：明文有多行数据，加密时按行进行加密

思路：将密文保存到文件中，按行进行解密

解密脚本

import gmpy2
from Crypto.Util.number import long_to_bytes

n = XXX
p = XXX
q = XXX
e = XXX

phi = (p-1)*(q-1)
d = gmpy2.invert(e,phi)
m = ""
with open('cipher.txt','r') as f:
    for c in f.readlines():
        c = int(c)
        #m+=long_to_bytes(gmpy2.powmod(c,d,n))
        md = str(gmpy2.powmod(c,d,n))
        m+=chr(int(md))
print(m)

三、模不互素

特点：

存在两个或多个模式n，记作n1，n2。
且gcd(n1,n2)!=1 即n1和n2不互质。
此时n的值特别大，无法使用工具进行分解。

思路： 先计算n1,n2的最大公因数作为q，再用n1/q和n2/q计算p1和p2。

脚本：

import gmpy2
from Crypto.Util.number import long_to_bytes

c1 = XXX
c2 = XXX
n1 = XXX
n2 = XXX

q = gmpy2.gcd(n1,n2)
if(q==1):
    print("n1和n2互质")
else:
    p1 = n1 // q
    p2 = n2 // q
    e = 65537

    phi_n1 = (p1-1)*(q-1)
    phi_n2 = (p2-1)*(q-1)

    d1 = gmpy2.invert(e,phi_n1)
    d2 = gmpy2.invert(e,phi_n2)

    m1 = gmpy2.powmod(c1,d1,n1)
    m2 = gmpy2.powmod(c2,d2,n2)

    print(long_to_bytes(m1)+long_to_bytes(m2))

四、共模攻击

特点： 明文m和模数n相同，公钥指数e和密文c不同，e1和e2互质，即gcd(e1,e2)==1。

思路： 先用扩展欧几里德算法求得贝祖等式的两个系数s1和s2,然后利用如下公式计算m，其中C1、C2为e1和e2对应的密文。

C_1^{s1}*C_2^{s2}=m

公式推导：

脚本

import gmpy2
from Crypto.Util.number import long_to_bytes

e1 = X
e2 = XXX
n = XXXX
c1 = XXX
c2 = XXX

#计算e1、e2的贝祖等式系数s1和s2
gcd_value,s1,s2 = gmpy2.gcdext(e1,e2)

m = gmpy2.powmod(c1,s1,n)*gmpy2.powmod(c2,s2,n)%n
print(long_to_bytes(m))

五、低解密指数攻击

在RSA中d为解密指数

特点： e过大或过小

思路： 在e过大或过小的情况下，可以通过wiener攻击从e中快速推断出d的值，进而求出m

解题脚本：

下载rsa-wiener-attack源码：https://github.com/pablocelayes/rsa-wiener-attackopen in new window <笔者环境：脚本位于kali ～/Software/rsa-wiener-attack目录下>

将下面的RSA_attack_script.py脚本放入rsa-wiener-attack的根目录下执行

import gmpy2
from Crypto.Util.number import long_to_bytes
from RSAwienerHacker import hack_RSA

n=12238605063252292170613110607692779326628090745751955692266649177882959231822580682548279800443278979485092243645806337103841086023159482786712759291169541633901936290854044069486201989034158882661270017305064348254800318759062921744741432214818915527537124001063995865927527037625277330117588414586505635959411443039463168463608235165929831344586283875119363703480280602514451713723663297066810128769907278246434745483846869482536367912810637275405943566734099622063142293421936734750356828712268385319217225803602442033960930413469179550331907541244416573641309943913383658451409219852933526106735587605884499707827

e=11850552481503020257392808424743510851763548184936536180317707155841959788151862976445957810691568475609821000653594584717037528429828330763571556164988619635320288125983463358648887090031957900011546300841211712664477474767941406651977784177969001025954167441377912326806132232375497798238928464025466905201977180541053129691501120197010080001677260814313906843670652972019631997467352264392296894192998971542816081534808106792758008676039929763345402657578681818891775091140555977382868531202964486261123748663752490909455324860302967636149379567988941803701512680099398021640317868259975961261408500449965277690517

c=9472193174575536616954091686751964873836697237500198884451530469300324470671555310791335185133679697207007374620225900775502162690848135615431624557389304657410880981454777737587420426091879654002644281066474715074536611611252677882396384453641127487515845176069574754606670518031472235144795376526854484442135299818868525539923568705203042265537204111153151119105287648912908771710419648445826883069030285651763726003413418764301988228077415599665616637501056116290476861280240577145515875430665394216054222788697052979429015400411487342877096677666406389711074591330476335174211990429870900468249946600544116793793

d = hack_RSA(e,n)
m = gmpy2.powmod(c,d,n)
print(long_to_bytes(m))

六、低加密指数广播攻击

RSA中e为加密指数

特点： n和c不同，m和e相同

思路： 根据下面的公式可知，在c、e和n已知的情况下，对k进行爆破可得到明文m

c=m^e+kn

解题脚本： RSA4


import gmpy2

e = 3
# 读入 n, 密文
n = 114976915747243387792157708464120735018971336213935438953074748276198282761939060395482051056351068439137722626185590043024556656813730840050547350912425438364703854627760482842307943026011880815011654341047422453012558617703411700393668892701036222135444420377515575624398723436532681305293727164639582093389
c = 5828813410620741112500628876643872258919868379601617907887884191584237969605489971465692568848339200057188383649365078832766143513766368216471491824042974016773526107276856706832404477882581400769791378958901067683158857990261489285951805740071223765359992165262854641069674603160977034446644199945940251030
k = 239000000 # i 应该是未知的。这里缩短一下距离, 防止跑得太久


while 1:
	m, b = gmpy2.iroot(c + k * n, 3)
	if b:
		m = hex(m).replace('0x','')
		m_str=bytes.fromhex(m)
		print(m_str)
		break
	k += 1

使用中国剩余定理

import binascii,gmpy2
from functools import reduce
 
import libnum
 
 
def CRT(mi, ai):
    assert(reduce(gmpy2.gcd,mi)==1)
    assert (isinstance(mi, list) and isinstance(ai, list))
    M = reduce(lambda x, y: x * y, mi)
    ai_ti_Mi = [a * (M // m) * gmpy2.invert(M // m, m) for (m, a) in zip(mi, ai)]
    return reduce(lambda x, y: x + y, ai_ti_Mi) % M
 
e= 29
n= [30327806559308143170251580709344293187241377730282921872781575442079759214585250363018838833645033147048274099882927502135822532658361986843089038971809699440265951177983452623836631182131316783838858410002798162604085127069663694047960859197275399255233610031615817404372364349637055800705223698180870067436988096453852212302215116141417320041306889953482862584091194471138823690888819261753453934793173621702326066309884946089600954181869152898879815596750534117681142535676578782280108274188679221706983417414010745084946761574988283779791817969892384961589321416872995532377690950727835973399647956491090102555409, 21201945432185822273274384690776217497058902883149769388717005633136179247488270702594230376181288768858812012728332675867062647184506694171059959523739358150427193785288862325490483145892589156285417654675409522395461778047750713685913892924628709666682898716590870448590373784915689173142592010032611604863227130433544024508077340982534157235155525782725897976772958969688875400789351919632303930452916408599309209320071861151825269791353531470198408880292345886431587538581009065968803858039954194364023302947597373427552936469472639511930960050054058074397349282354505376836608524919420271358644040625272611834141, 22066722902445052583751020956045490471001229482392491124491605354676847417172264621341464938604744547196288089839857467414993454346487337649230414610787992018112868327537703873968574017809192037003789320466268844177192403612544118218277599434212247848173311593650429895564484864389688450385022488374534161927558878171030816097844863947341831453646609936063871558801826304657779664413322335636640541461530342335752307248094073705764721946570652851209785138013258495645549732438232440380725327458972312411697319199017195198686877941387699409525165884596929130086232751883272627080260637468553554114550895128931332556731, 22201854184449819277142185267444382273897841368693102934683821764656962395743826157719287435432760269046740745554089225345079284556882054478011586504345324432037743900501514661174050074095054738909658615769021337525829263909874107830437595890817773992121956416657353703784722839247395770361048793369307710079965231303120658766595423843609770605074056488132086912631857454296414163240447182566834479775710868231123976843543989150070863055009604342636257860806777650229259057896505901924417615469387152636729167180379751548900559610148369495057752373605259839922528981148145028120068953655171238962097381144518051147647, 23083840233620992224264526611828536460163558999895002497626591923027006640369297896797243966752151170505775381864181314027021495993588967339108820520528972816379841269197877268187639445751437743759925034716110259215833511647315164717603384871571434294945499053929574035111488209616165563966647430661297795173473421242368063748311843339991310650516321423828411278303633083702771322000349673510635860126984256969661571754688788776209025080804889751723316765593984981235995307564443348633486717797511234178142487310778666548407208267425343907584339092352000989025888560813696453621147789642611872568202165905056714548393, 23218822553600624275851570918327600443202628196986792799225558073420180848161120578874626283971398879263850567245985782927539083923897342980706479709569579629418591343916765139087666874177802508777776627037319228004136490718510415593236575453393195566284309655647871922536044561206875353630359295663312099218766232095780724182736486077598036512073334536846225792741359530446751954255489310204542643379502811042809497521182466190499994814904710462792494798490083908932248164953870969612782940162469775904944210724177461134898671189252356405455733124848794067548040801451291259009951270923040763880342053172756399581161, 15537621716770448782502134748692657546482394987891814167799488723003580500457315182184780510271452262025473252065075152671351786862081823121704341999623090322622893909472600153140827895279392030437881151726836273881483138361166633444702898613389403354997826623821941237846412179222285546753657710048063757827302566538233983504273873252358216792306525072453406699162260561047287090285490165275142295462447156551127598082848917540871566229207376989948730655600666112133543582179171414297735210520886697976984424647098383547804465263579778326244367614695099540268893495474464880528394459062149362976029449912614166126761]
c= [6046094125227689870033870506917812276305436053796436442363822401342062726188042561670757795460948077415972706427946093618320717744079441259077874700893204459036501380012163686628771354515016380758564221578468509762354597066344146672996248499856111282865676568650895987550682149774776905594210993204175895358464315828610392955454920047755436033052407392579110231386427222684373442110938309074563238848319417352567379700597401198483471415807726938645013860932841996827926718400267742249916874079269259123794751964917045940979213140450626289795549071713337129466329394763935853156424248229732551544822323764365359825485, 5845552286578226566598806127534836409831300694599972428266617271147189508983086233231766595846029052663890341733882461545982026551439575193608090205669127833427025577685774642780332691084053603909859869193052420285065348378657385164191605378649460509586471212644006322411828860570889277856429353408252263239239828396565949357208821626888694650997167695580553398057963048443171407094467284923234982142222808183498767632834628360161922076588397865384233638848062174627983119799111822718694488311274624762022407317556646065445367315918249540635444036633880194363965914260210883151429898423440605220973034396774973125632, 15903392352203298605877945674465143966769721737532685945162112598239954843499500918942681985964024463454447115748161245918002002655617193080894539813344429249706695035313266913563071057661003650948948239324748886703222675088558181086755212852968181312257303494407773363350004731534848190264255069536036133029778028229221293469762527695954265711168400217935692988501544247020837424584759831204521029707454822146517072769268420888169838807185669690437151962231817248323732857623620673773191557407520247312964435867860663874242179929967218588152288202476576081222176785925045418916462303292404117304143574686336544149629, 9669717038949021329020108540640237663067756966280810642417630134992373130879787768749181913381401511774773393506456589516952861294673561533008751071662723277608866325874519278507984666760149692092823573606053373801025601646795839172562607132726532904679698936251789947925155456255628127932509101557747423647220724762995217296493861282238350001729340519429193525028741636093329396359178973155083792632330011484299821599210312002159965537430090985352568581714148228760952230630659713444400585630168629530652207170759737992501963831886075598264013355139219445863531555822055994574891400262563108434859568651780227557975, 7914090642636266923294026791261427849044695562739254282481166732020837928041454353817133871854948761397284836379753705671724947241779482598081203575216043223216563037754382992648875469848870865515423794755447621640988585802308628444956443228403796584499863761840901610073862093944795357445536465073500157568848798543720484354000858578319564737563857043549861785205215491288782410945294230845471220683129677585701046542907136512616807429274294758158965956146717352157078092334387660733724142855367118044193694310952976603009653011262032422467651663006916850935081716939520365535884320814471253649009945816472423048447, 11988310991395265980081594718856590638441631362665678269045945813797124375621091172731397011814305000162712601455584541005431841875115788140698346738764417691906578333694503756521160780120138569779573589730959145320537390172280626510886154211649716255438845119004751973530199741765756641003306339421117668796100661313571568100843237996562080095649017634551873879219917272328238629844657368364890324594141674498942544827428056492747949043332622214494766621587698339619576784948756333563714427524714670635509179215190783959390410232309595570890592221268445440689742423642145049491551659385729937300897657450196112613804, 13758385300968829470189169449584800778823082473607121434049610051116374924292341244419430157132107552964735632092568046439074559673147580828760077490267517852677562615547566840913903686439783964549498803731879665085652815249977620067028187162008373600851339874309707587214786555705953533197711132611955125553398328736012543728815790951625456481002420603689802771155816294782083229750332438335093308789359642911367376579780093093577929312234635979675059828551040384269343053231849182709709271027703443106568079145606579815607660891685636327906452992083196131013003312334278998794497774078191519059014857427818993752773]
 
m=gmpy2.iroot(CRT(n, c), e)[0]
print(m)
print(libnum.n2s(int(m)))

RSA爆破攻击方法汇总

# RSA爆破攻击方法汇总

RSA爆破攻击方法汇总