W'Blog

Wbuildings的自勉小屋

0%

RSA之共模攻击

发表于 分类于 Valine：
本文字数： 18k 阅读时长 ≈ 16 分钟

最近遇到几种不同的共模攻击变形，记录一下

共模攻击

1
2
3
4
5
6
7
8
9
10
11
12
13
14
import gmpy2
import libnum

n= 25333966058003377512707481338795714713737652659944601834182685873529702913988641983855700459996104700470621411559153944988952210084014634675583566338568882440708528997808798650962116756969822211586531522430245040013570571043385238601846104615050089457836721437790715225367971106085839523500735480715155424498941150468093083816830215632716244390679417218873179734276657411907216486790815037105108306055794473002315541787461904728375164737225486501009857299717749346279371251245318729951905832578739696926931502225899707226264570557623527701806829827566904224572897378639191756878049342203546309520458672464170859577433
e1= 2333
c1= 11355981897781478907853356911752561659125575027336719997290835661089901154031171698660586203170528368228850895159361637188990782030255983633790580700032092629587631108597144196551438410868034739981960656110887650747325311613900008001234835897835613759692146419080113176963747835592656185435741504176116672174539018089139547795447109458469225330809064539216773123671814859510069089532677704482026169178543062578686794346026774853085101278125763460212801929360456888869350105294595904940799522522144740464043605342348269086324747729288399275079874271519208155039364092577755518532799345651172433227745483422620900776136
e2= 23333
c2= 1326499538902841116411674554069945581390130048432351353260154261863309471312810811160302458644816390944833633923435634961251092531893503039914793217247984595331920909367627316087404934402312358642315675486438968585084964845763881078835787872160374025547400141298650794551970291119975344578667689961134814676553190178139842507675899262024572370313939107080072875068218336255452161407859907308656094331557912187788276334833723893856310434523337557011032081467262457427167978528280339494077785813461280853735266463152709443731638714219391773144349752633555310299318290576258086971373777118482642702020599928071855133041

s,s1,s2 = gmpy2.gcdext(e1,e2)
m = (pow(c1,s1,n) * pow(c2 ,s2 ,n)) % n
print(libnum.n2s(int(m)))

# flag{6ed4c74e022cb18c8039e96de93aa9ce}

e1、e2不互素，开根的共模攻击

1
2
3
4
5
6
7
8
9
10
11
12
13
import gmpy2
import libnum

n= 19006830358118902392432453595802675566730850352890246995920642811967821259388009049803513102750594524106471709641202019832682438027312468849299985832675191795417160553379580813410722359089872519372049229233732405993062464286888889084640878784209014165871696882564834896322508054231777967011195636564463806270998326936161449009988434249178477100127347406759932149010712091376183710135615375272671888541233275415737155953323133439644529709898791881795186775830217884663044495979067807418758455237701315019683802437323177125493076113419739827430282311018083976114158159925450746712064639569301925672742186294237113199023
c1= 276245243658976720066605903875366763552720328374098965164676247771817997950424168480909517684516498439306387133611184795758628248588201187138612090081389226321683486308199743311842513053259894661221013008371261704678716150646764446208833447643781574516045641493770778735363586857160147826684394417412837449465273160781074676966630398315417741542529612480836572205781076576325382832502694868883931680720558621770570349864399879523171995953720198118660355479626037129047327185224203109006251809257919143284157354935005710902589809259500117996982503679601132486140677013625335552533104471327456798955341220640782369529
c2= 11734019659226247713821792108026989060106712358397514827024912309860741729438494689480531875833287268454669859568719053896346471360750027952226633173559594064466850413737504267807599435679616522026241111887294138123201104718849744300769676961585732810579953221056338076885840743126397063074940281522137794340822594577352361616598702143477379145284687427705913831885493512616944504612474278405909277188118896882441812469679494459216431405139478548192152811441169176134750079073317011232934250365454908280676079801770043968006983848495835089055956722848080915898151352242215210071011331098761828031786300276771001839021
e1=55
e2=200
s,s1,s2 = gmpy2.gcdext(e1,e2)
print(s)
m = pow(c1,s1,n)*pow(c2,s2,n)%n
print(libnum.n2s(int(libnum.nroot(m,s))))
# SICTF{S0_Great_RSA_Have_Y0u_Learned?}

[黑盾杯 2020]Daylight

附件

1
2
3
4
5
n =24030381175065789627867818021031309186965318861955402618375094156989560631225056400068280970357343617465261811691559275086986164901405512215968447835573713149231336594364799146504286982124850979481910739400555900516891562640944424296188089156508429086638459243074623801424444379741940400624550247210709108293164193827193821978694274672716764474152393429524314859853376325015012885883855819552203740904895242301492787682366135817255276597250505586595070110209229270379691148517421288247672403709484984083988966720494416926899250840012575481136166618973367329708626081023089829778864549053830890201012932527796486827519
c1=7706442311376298907118381553814187694306437942337200300920018382827744477296762105669322390236380377042026460058526286493515418722731849971411879053724334926597860433790660568227623266459105700578574867980278136078799958698624620338469216407947276632981229373095281141319203245321172350378427449842394930055529441744690732690189155630980736716300509547085032174345753133838250340838995285142338255951756404101946977370148727459867175980397841996210997274012491629791252693401571504945522427861126234928419824136852180508014703063857673244567242488630499415730763245048617632714296374909199028722650732705222178007385
c2=22423938730620301024336096061283705945892027623793660306239291359418958473934583979350384252488494023600239884048653436314101275290157972045454993641659471672605679497398173588217340705125922148550132426481727445141158741816240665812195493040369287582638492321538655028939958996384211181094086886177394010485535445009088322043647955338445795429449360349339936606800994026319620067195422963814641797851423046506617965736694331256799051468484280532276344029152140431817760731420316457245257243157665090587855008596785240088881665435451552191237548113820151383474872494353994135644477990413743416249730006854238049329690
e1=35
e2=42

共模攻击开方解不出

正常的 $e_1s_1 + e_2s_2 = gcd(e_1,e_2)=1$ ，于是 $m = m^{e_1s_1 + e_2s_2}=c_1^{s_1}c_2^{s_2} \bmod n$

但如果不互素的话，本题中 $gcd(e_1,e_2)=7$ ，则 $c_1^{s_1}c_2^{s_2}=(m^{7})^{as_1}(m^{7})^{bs_2}=m^7 \bmod n$

所以 $m^7 = c_1^{s_1}c_2^{s_2} + kn$

这里就踩了一个坑，直接开7次方解不出来，就需要爆破一下 k

exp：

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
from Crypto.Util.number import *
import gmpy2

n =24030381175065789627867818021031309186965318861955402618375094156989560631225056400068280970357343617465261811691559275086986164901405512215968447835573713149231336594364799146504286982124850979481910739400555900516891562640944424296188089156508429086638459243074623801424444379741940400624550247210709108293164193827193821978694274672716764474152393429524314859853376325015012885883855819552203740904895242301492787682366135817255276597250505586595070110209229270379691148517421288247672403709484984083988966720494416926899250840012575481136166618973367329708626081023089829778864549053830890201012932527796486827519
c1=7706442311376298907118381553814187694306437942337200300920018382827744477296762105669322390236380377042026460058526286493515418722731849971411879053724334926597860433790660568227623266459105700578574867980278136078799958698624620338469216407947276632981229373095281141319203245321172350378427449842394930055529441744690732690189155630980736716300509547085032174345753133838250340838995285142338255951756404101946977370148727459867175980397841996210997274012491629791252693401571504945522427861126234928419824136852180508014703063857673244567242488630499415730763245048617632714296374909199028722650732705222178007385
c2=22423938730620301024336096061283705945892027623793660306239291359418958473934583979350384252488494023600239884048653436314101275290157972045454993641659471672605679497398173588217340705125922148550132426481727445141158741816240665812195493040369287582638492321538655028939958996384211181094086886177394010485535445009088322043647955338445795429449360349339936606800994026319620067195422963814641797851423046506617965736694331256799051468484280532276344029152140431817760731420316457245257243157665090587855008596785240088881665435451552191237548113820151383474872494353994135644477990413743416249730006854238049329690
e1=35
e2=42

t = gmpy2.gcd(e1,e2)
if t == 1:
    s,x,y = gmpy2.gcdext(e1,e2)
    m = (pow(c1,x,n)*pow(c2,y,n))%n
    print(long_to_bytes(m))
else:
    s,x,y = gmpy2.gcdext(e1,e2)
    k = 0
    while 1:
        m = gmpy2.iroot((pow(c1,x,n)*pow(c2,y,n))%n +k*n,t)
        if m[1]:
            print(long_to_bytes(m[0]))
            break
        else:
            k += 1
            
# flag{1_0nly_see_d4ylight_d4ylight}

也可以用有限域开根：

共模攻击求出的m等效于我们平时所见的 

1
2
d = libnum.invmod(e//6,phi)
c = pow(c,d,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
import gmpy2
from Crypto.Util.number import *

n =24030381175065789627867818021031309186965318861955402618375094156989560631225056400068280970357343617465261811691559275086986164901405512215968447835573713149231336594364799146504286982124850979481910739400555900516891562640944424296188089156508429086638459243074623801424444379741940400624550247210709108293164193827193821978694274672716764474152393429524314859853376325015012885883855819552203740904895242301492787682366135817255276597250505586595070110209229270379691148517421288247672403709484984083988966720494416926899250840012575481136166618973367329708626081023089829778864549053830890201012932527796486827519
c1=7706442311376298907118381553814187694306437942337200300920018382827744477296762105669322390236380377042026460058526286493515418722731849971411879053724334926597860433790660568227623266459105700578574867980278136078799958698624620338469216407947276632981229373095281141319203245321172350378427449842394930055529441744690732690189155630980736716300509547085032174345753133838250340838995285142338255951756404101946977370148727459867175980397841996210997274012491629791252693401571504945522427861126234928419824136852180508014703063857673244567242488630499415730763245048617632714296374909199028722650732705222178007385
c2=22423938730620301024336096061283705945892027623793660306239291359418958473934583979350384252488494023600239884048653436314101275290157972045454993641659471672605679497398173588217340705125922148550132426481727445141158741816240665812195493040369287582638492321538655028939958996384211181094086886177394010485535445009088322043647955338445795429449360349339936606800994026319620067195422963814641797851423046506617965736694331256799051468484280532276344029152140431817760731420316457245257243157665090587855008596785240088881665435451552191237548113820151383474872494353994135644477990413743416249730006854238049329690
e1=35
e2=42

s,s1,s2 = gmpy2.gcdext(e1,e2)

m_7 = pow(c1,s1,n)*pow(c2,s2,n) % n

e = s
P.<a>=PolynomialRing(Zmod(n),implementation='NTL')
f=a^e-m_7
mps=f.monic().roots()
for i in mps:
    print(i)
    flag=long_to_bytes(int(i[0]))
    if b'flag' in flag:
        print(flag)

# flag{1_0nly_see_d4ylight_d4ylight}

三个e的共模攻击

和两个e的共模攻击同理，只不过再算了一次

exp：

1
2
3
4
5
6
7
8
9
10
11
12
# import gmpy2
# import libnum
#
# e1e2,s1,s2 = gmpy2.gcdext(e1,e2)
# c12 = pow(c1,s1,n)*pow(c2,s2,n)%n
#
# e2e3,s2,s3 = gmpy2.gcdext(e2,e3)
# c23 = pow(c2,s2,n)*pow(c3,s3,n)%n
#
# s12,s23,gcd = gmpy2.gcdext(e1e2,e2e3)
# m = pow(c12,s12,n)*pow(c23,s23,n1)%n
# print(libnum.n2s(m))

没有直接给出e1、e2，需要爆破

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
from Crypto.Util.number import *
import gmpy2

# n =24030381175065789627867818021031309186965318861955402618375094156989560631225056400068280970357343617465261811691559275086986164901405512215968447835573713149231336594364799146504286982124850979481910739400555900516891562640944424296188089156508429086638459243074623801424444379741940400624550247210709108293164193827193821978694274672716764474152393429524314859853376325015012885883855819552203740904895242301492787682366135817255276597250505586595070110209229270379691148517421288247672403709484984083988966720494416926899250840012575481136166618973367329708626081023089829778864549053830890201012932527796486827519
# c1=7706442311376298907118381553814187694306437942337200300920018382827744477296762105669322390236380377042026460058526286493515418722731849971411879053724334926597860433790660568227623266459105700578574867980278136078799958698624620338469216407947276632981229373095281141319203245321172350378427449842394930055529441744690732690189155630980736716300509547085032174345753133838250340838995285142338255951756404101946977370148727459867175980397841996210997274012491629791252693401571504945522427861126234928419824136852180508014703063857673244567242488630499415730763245048617632714296374909199028722650732705222178007385
# c2=22423938730620301024336096061283705945892027623793660306239291359418958473934583979350384252488494023600239884048653436314101275290157972045454993641659471672605679497398173588217340705125922148550132426481727445141158741816240665812195493040369287582638492321538655028939958996384211181094086886177394010485535445009088322043647955338445795429449360349339936606800994026319620067195422963814641797851423046506617965736694331256799051468484280532276344029152140431817760731420316457245257243157665090587855008596785240088881665435451552191237548113820151383474872494353994135644477990413743416249730006854238049329690
# e1=35
# e2=42

def solve_sharemoudle(n,c1,c2,e1,e2):
    t = gmpy2.gcd(e1,e2)
    if t == 1:
        s,x,y = gmpy2.gcdext(e1,e2)
        m = (pow(c1,x,n)*pow(c2,y,n))%n
        print(long_to_bytes(m))
    else:
        s,x,y = gmpy2.gcdext(e1,e2)
        k = 0
        # while 1:
        for k in range(10000):
            m = gmpy2.iroot((pow(c1,x,n)*pow(c2,y,n))%n +k*n,t)
            if m[1]:
                print(long_to_bytes(m[0]))
                break
            else:
                k += 1

e1e2= 83317
n= 19361442710572745971265661179912428614335978862294499554478708154961900725571203060796104846289397242207304532314240136962004100859120350866177200389723065658762704195258332314791286248842309297348039111045266185355903400590470820183877252896166548216731371364979378507526744861441605219478410567943584909399458417880788827318597539692741384869777249157338164956516233081381729474311604082892186490173033244693551617094635430697205804969501877592642316320873084247185093376277647579480643486369145925195734181193015900482737320548696928588870712293186252013457131251209473809656777543374500592007808404407059561585875569527546497652518580045435210514546460508584320606314122520882426004609258608147903667923350952560862343978526661419457923377730038903725129920335146125419046956321000719022303404018007514471776998828154744785228693422230685108494515083105086516002742258455143048441346760686508352771381755359768486489070279892078844716848637514485979868052449468414483027672075237348001190373461535494802211938683204976566773050049547807712425194913096401165728862378611187510228222428679755307056276133497536735863204478321549958435946853973687386589497836951783399492540878952618631792625025126620608024559471293131768988077589502325651357976822933654550846615039529755326862460868499406888969184042128071
c1= 8461455935702774839606732696628583481106108739457157757237961493721249315707058365854463354773540401038228236301572933195823206925383589280380438344346918293151928169930134045632956081184945062566817678757614816611860006425866597730747864519352309046720733870943424680296477704991108084039103348714387678260925701357278152801810444616098214964231942511332731906589339642434586792884729500618636404879133808745489823990051381479316035290316511507860259556699539853817794899071305575419968794233519130191693519669424965740754005557268523536259961342893331243822271702601491251166024629032785331163334845458532041066873062181204642511730061193181806412423310871852101503714865811232852678040552266896756835104015126426669170036333066668010437674021104622132437422087899276215087590613842963706972249810831528040008304175911799215946803926073839260039708714727246670180210772138254229999545871929350538204078637835690649108982156556159082202035891312400182426109033284706424624286874595070797624804888642649414098331802113837492380725023537502746076689560748513729573164798419260068335949704460969862627638288475890309143274515210188524564546972793051029662396980537597835874860939675476734819945549433268818379519178647303476509820821756282974287073312744339124424284365074314353072957540119217061097316369179812
c2= 6204846642785521340470513546335239064256758077473460303136152226321426573866713276868303467627807818878464124001025948893472833684203082226317608116339642653526005250588488719287359040352790572959995584093188339849695217956472022875459556871491299322868787108334073007332501731796096022506406756118808831646084743403979543281704069120640233328839980099290857269846287187888156728145277024309531510105331797866833685076835273931526615042292719970926967658919153638762985362453791732734631621502983351581711188066449777097203043897589205329057225446193852593056040301734809364853181753118739604843784216536562612033307359103893806510482236157475021740603255590914121641809865052126419196638531405221094438510231726208366630512008162663744010330103156199459170979721924714894281792427651932643530734043790246173905509400532261288534889712214483873969552991657537356198890952147322594953541508366871552561029095676172024539741525694906063413062943730465813047155464168544196529490081901356676689826701155342513241655234549380041635792150618405682571311160853526719882812618473055821608217492122688669131559593093840370537049894579011917334477512297137182557102626033423909278319394496823138854073015927815382203590762482110896381565689852266596980436613904791614372199019839459027972129220041158226866818118745059

def fator_e1e2(e1e2):
    for e1 in range(3, e1e2):
        if e1e2 % e1 == 0:
            e2 = e1e2 // e1
            solve_sharemoudle(n, c1, c2, e1, e2)

if __name__ == '__main__':
    # solve_sharemoudle(n, c1, c2, e1, e2)
    fator_e1e2(e1e2)

# flag{6ff24d84-4310-4ff3-a5d0-d96558f21f18}
-------------　　　　本文结束　　感谢阅读　　　　-------------