Instantly share code, notes, and snippets.

Embed
What would you like to do?
#!/usr/bin/env python3
#
# Common Modulus Attack
#
import gmpy2,binascii
n = int(input('n:'))
e1 = int(input('e1:'))
e2 = int(input('e2:'))
c1 = int(input('c1:'))
c2 = int(input('c2:'))
val = gmpy2.gcdext(e1,e2)
print("[+] gcd(e1,e2) : {}".format(val[0]))
print("[+] a:{}, b:{}".format(val[1],val[2]))
print("[+] e1*a + e2*b == gcd(e1,e2)? : {}".format((e1*val[1]+e2*val[2]) == val[0]))
if val[1] < 0:
a = -val[1]
b = val[2]
c1_inv = gmpy2.invert(c1,n)
c1a = pow(c1_inv, a, n)
c2b = pow(c2, b, n)
else:
a = val[1]
b = -val[2]
c2_inv = gmpy2.invert(c2,n)
c1a = pow(c1, a, n)
c2b = pow(c2_inv, b, n)
m = (c1a * c2b)%n
m,result = gmpy2.iroot(m,val[0])
print("[+] gmpy2.iroot(m,gcd(e1,e2)) : {}".format(result))
print("[+] m^e1(mod n) == c1? : {}".format(pow(m,e1,n) == c1))
print("[+] m^e2(mod n) == c2? : {}".format(pow(m,e2,n) == c2))
try:
flag = binascii.unhexlify(format(m, 'x')).decode()
except Exception as e:
flag = m
print("FLAG: {}".format(flag))
;
; Common Modulus Attack sample - Codeblue CTF 2017 - Common Modulus 1
;
n:791311309087374588934274354916349141233150778762086315374343850126808782284294921228110916322178898551691669133101997907127587121520288166574468605214516304122927763843434653215681360872523253290766297044510870617745122997739814947286892376888776319552516141136363673315815999597035068706744362048480852074989063152333880754375196551355543036200494314973628012006925154168913855587162465714207917714655810265293814697401062934881400969828166519415465439814160673468968009887672546243771190906300544375962002574334018175007498231632240021805593635057187842353840461973449205839419195826992169177108307004404365745462706797969436718212150888171299620800051183755681631250040936288149592343890616920153400691102933966724025765766418338452595218861582008026186067946508221264938736562082192890727980844444978081110599714993030990031363457184296168457089953510500474033234298252385232725393194957086065274263743550741242453140557383981358497807318476777558208795816650619401057283873302725816795298930817307745973266335447938091252055872816232968635169429875153933553733116356920185396530990560434510949092154539711124052490142742567527833751624924993906099869301505096094512729115132147653907827742334805918235749308541981388529841813147
e1:813647
e2:846359
c1:767202255403494641285723819543278226263601155898823605265497361830705668240032418501494959141449028517100422081272691883369257107388411439611318808983979122090486252578041006071999581282663085495058515958745546211668701835250122032715473014598395050184702983368667972803718169481809394565706175141425650370279775233813674442957760484285820381853600163980060348710028919659329781877491724136976028815641232407109144869660767954119268355348405951052583739555066569345526640029961785158127382321111833599691079949415049786723663210542733655554868327542833053024595895523192888118675763242352407948643537985861448788568550308481655116845634952516676905251579084404308314639717162526798451410767058423619677212069270398132021729448047980766312818656065369023093123058422620085273728481545680423266197847937925342263870309939913221308330842487685037638837340238355192125668409039255551545407800543798158964963358868702135730305156935767426581823180696819366253148799571923731323928995477390559418822575259531941023518182807739949726026157027426545624061195471888653152768495272113769751755053321333829345939391638863918920798107792346015224509118930143010726156407828938941341788657835191853473698010478888928860138978235297618195944868175
c2:393205642868817442649216793359718556278406137459770244761832906195960432918468617731069456704644789806507809829093842629745066759599286729538728368882491382997337611417441529220397067642218119525968897551289230558627870154984979444195757677411673096443476021362319325097662392808170632471553717355895219405644518503783235536597143112954291157798713583737689125917709618182162360535659223966858707155741267214975141963463832314566520144602105237041672437684177707624423211972004800873375670613148140256099552724408192217550331987310558991433383571470532995856778764797540637679226825577553396934734325550293550389623919904744913990305949697308222046594160302362669510242921299755255790640101006152269619965560742243168099219363626217512940995615730916134775134764069912120583282148219405178065222313607957426887495658080497917440100549199528894874905968298614233827155712422019324710018755792249855902168601927285980197334672067920857960628679370550895555840658121626134216719240409691397735762685349162277111815727100169755960553688569326705249270662470879197234836585418835845237231721910938341557726245940031873345666571751867755961294973426045629909899256967038811807893676700888551318830676356324765330202998096318754445585853694
[+] gcd(e1,e2) : 1
[+] a:14877, b:-14302
[+] e1*a + e2*b == gcd(e1,e2)? : True
[+] gmpy2.iroot(m,gcd(e1,e2)) : True
[+] m^e1(mod n) == c1? : True
[+] m^e2(mod n) == c2? : True
FLAG: CBCTF{6ac2afd2fc108894db8ab21d1e30d3f3}
;
; Common Modulus Attack sample - kosensc2017 - Weak RSA2
;
n:15620594388031266473712197182475401349767058475004272224536225648625952854897365941672814814279333073858254829580868738008914764200900970816497912510360543912576564493343805445025709928720849734646456324926157789117630436365389163740755803508552528581884072989427047817466199091956971202594169215137811755824226260563197033762229828516931685661716640702851860618004147473654194699872663323713081865134559047690101137746846052872766057239471941861178242802245323235655974041818544934629078008209255370053896111737087831087011650112842648525928751876926708669947901109909413734984869911340235105269214508784024367437953
e1:65537
e2:65539
c1:1489339754254835944677817314156282333390420547822585047855038563837425349664194850427115746596887213776055939099564558606337055512116152708397846771996964510378668840230909565544664963310261652925078679498650790381754626497493158792557390482082573480212247709568460489056108142552816301497747321257232440135839929603826233477775774821500965278201630483068367395608986530462394069768248345356496649844524484174543476759824253644298849853595634079532089280524931251869742857752978697126429863924143953454746075801930602577660175830635621109439756450373000808212559121842164656100986032352919953870573034007586691572423
c2:8937852908134130987306629574212610585870355427149438575409310990721292816465794336063622070701241632165975343736107666017483999564028889523529815370891549255738484538948306769705294545796448878619345994465089208610331683024233794031754249094350901527624987088546851077662835034720521633888549528955396181369564105250206441938210096873324891523699556663493825747077759200653146111288180531806191004735381569983983004774687680500543972478695930507359686485047486651425834899677627088843750201678265731343452734974295913237386547145723229171516297836237470372655702578565577725744629493384561781549781547455844816880977
[+] gcd(e1,e2) : 1
[+] a:32769, b:-32768
[+] e1*a + e2*b == gcd(e1,e2)? : True
[+] gmpy2.iroot(m,gcd(e1,e2)) : True
[+] m^e1(mod n) == c1? : True
[+] m^e2(mod n) == c2? : True
FLAG: SCKOSEN{Comm0n_Modu1us_d1ff3rent_pubkey_1s_n0t_s4fe}
;
; Common Modulus Attack sample - Volga CTF Quals 2013 - Crypto 200
;
n:108039548283467910018636019706918049787296862983920390620425680109149061265582938100265640505395436176923520902062289606379329490555998996693285930619495040456388113166495283026905991110314710632437395833112529488024010984327573108928719840003018232385552027586272040584786259207191357206321725581066222359269709853312236804681275337051689984480610347322381805920314518020927280061535012383180989715215061621017100281215170089223279840979641688194933238176625422507335413025975742216947757245112001827202742177202602339368271393570814426349
e1:599703852157208324988436697659896404638315905290324375700570316485421693
e2:2021187385200166516022746434619391941987919206967476592818217288363509
c1:64192679490201084919864109589711225051306895753052452251471181011935890793544442381990900483806859201269602393008215002967277584404244028747557515652983421402831933955031514949051711613799413945375516057965907322753883557356486350981432321137639633448144656731569958858836168965404795837648422955123798171558220417018614361054908596961274183141350877544714255973182298022152382603068819975693640211216195897799698027064327186095742305485491820097943409724898378023689276832524319007493796910829806469346146322827201567159126666629388322479
c2:59479689549560080704719346207028172045832447629676482962810835773815464251268645222410752554301728769639790100177113106905240622051153394111672911715955043318248120741697967901541458159847100613910368380426590912304442624789475183028091060736577136778183984119998489277854012692016578461901960239232919085733417338853775102362931632001858570236887517967863584958729992234586883928904928030598648389127230808653922583812124081813290524003879897252243176409322823308176329788244775196386356286749265723818517581499920415831945106137632995322
[+] gcd(e1,e2) : 1
[+] a:-3047508293327982779161516622450839163404526801300587435875399397355, b:904222179681195587324531859318948099549580203141997568283661184044224
[+] e1*a + e2*b == gcd(e1,e2)? : True
[+] gmpy2.iroot(m,gcd(e1,e2)) : True
[+] m^e1(mod n) == c1? : True
[+] m^e2(mod n) == c2? : True
FLAG: 4561387865153841354984687512687489546516849543684654468465495143548954351686168165161
;
; Common Modulus Attack sample - Codeblue CTF 2017 - Common Modulus 2
;
n:691611766208546073444876122261067788277978858453710639029761974358666489171591889808344592871468081368348731289584873825685836699513369087940744233044470468106283756269016888690397802087612562650740690626844050981638158798650899164329024889012339813251634342169796374490173324858177655412520581064091323105709703802894635752243504165527728325493775585018099572491218738859140069209745383085972126419677929983854492018948495162457428459536088314487922683148031388611849013227501962458386817851194913551405843074740308192841259015955432216658418219471365781271743026881045054161177699500233983945284463060091084401032681620162554495490307966608011765399197534175588394769839991952726269105973546086964385977836193216093842605576347580465390858378577913173391209728199847916944392685608959720919745441534152140791433228642857247821519585327091864890122871765266988285510728943279970135846908966516130597249552710186071954611133294079017500030355232895541367427153922527925908108643934213023557398363684188823565535815365161748782796247844503993809352854741573950620787090272760236473228652960605730173150252619759400890068298838592790770868307280012495168740250977525199965477849089021924445456338550258621310346872587368865023459114279
e1:2623119
e2:2611101
c2:632613645684838434911920364870092246688638723680203743297038042884981435531349983627632652213126007404455112992754038899192740232209237012089852184466576496173356903126767617531366105427616049893559911396536574555008451239827427140619373005107923039458285095437111146013805698400274937791209388463040761234346114146112603113513874269976957472698342250573902102976387047390228485927254752372525379266486917620487089416581168720140744193600912161065888758451629009978676721731074043142666019127528370181044741033938879227651226413524178992155234346229899043794846119210274959231350300191718278291314079326011260972911790929707654859407903619102516710246683375658271085356783673232677699444921875427077745087507202504075374873842972977165904031632108921391219453633100007509368853543202918527396858214941532156620908283394786740941868393377733920317480973184132461984594109692489226477402338664642727766514992506288377119275635222078018270479534265371971469799345627297451492177595572561618185463142728664331779856911512823762928116551034186671353283417747535010208121962539603383913657773795358612010178381857101029638404248669376029927680328805839410427459248430136708902815920536603541943356116875656311481908672896225539754812052984
c1:473583830101449207063655453483957320801977763405664178108962387145963115641321631378723122470718049239150183483107837540062110255460217493574236417576528210993551734521104360323008425196350719034294427914294044848231276934402896045785500160974092767601908407706594433190832523140982335688121038712802163776950422665847149664034820576774873956120202470663588902529914328392634164212558025176982387474287314624421143326789371057668708456922968762564019631616913937820209470604081356673188045257490667304640155390478645279862586730343779998826931285683980941686981775369499484033439920659579124275957233449431588512697916708510428626881790592757578867152025501459202793986322020476004209777449674143157280081483085868896558215825742742029607229809248023263081810931655981810534293127835168642962477010095223356972141559004635008185531900175232541978761179342338914489553003329293031284557554252476291770973145365678145226167965362251186233138510776436645583796590010200995100899736056399413460647507781994189935869541735701599175369334170081795310585938471394672279359692859881857399434361716843681313191143289947464231132723256066979526475873327590657111481299295002695482778491520250596998683754980263059514032256777144682239680031331
[+] gcd(e1,e2) : 3
[+] a:-195322, b:196221
[+] e1*a + e2*b == gcd(e1,e2)? : True
[+] gmpy2.iroot(m,gcd(e1,e2)) : True
[+] m^e1(mod n) == c1? : True
[+] m^e2(mod n) == c2? : True
FLAG: CBCTF{d65718235c137a94264f16d3a51fefa1}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment