CodeBlue Crypto 17 - Common Modulus 1,2,3

Inroduction

CodeBlue CTF 2017 - Common Modulus 1,2,3

Description

Common Modulus 1: Simple Common Modulus Attack Common Modulus 2: Common Modulus Attack with common exponent divisor Common Modulus 3: Common Modulus Attack with common exponent divisor + message padding

Writeup

The challenge title was pretty self explanatory.

textbook RSA is vulnerable to Common Modulus Attack

RSA works like the following \(c = m^e \mod N\) If you encrypt the same message with the same N like: \(C_1 = M^{e_1} \mod N\) \(C_2 = M^{e_2} \mod N\)

Then \(\gcd(e_1, e_2)=d\) , this means that a and b exists such that \(e_1a + e_2b=d\).

This is usefull since:

\[\begin{align} C_B^{s_1}*C_C^{s_2}&=(M^{e_B})^{s_1}*(M^{e_C})^{s_2}\\ &=M^{e_Bs_1}*M^{e_Cs_2}\\ &=M^{e_Bs_1+e_Cs_2}\\ &=M^1\\ &=M \end{align}\]

In the case where \(e_1\) and \(e_2\) don’t share any factor, \(\gcd(e_1, e_2)=1\) so \(M^d = M^1 = M\) . In the case where \(e_1\) and \(e_2\) share some factors, we end up with \(M^d\). Common Modulus 1 was the first easy case.

In Common Modulus 2 both the exponents were multiplied by \(3\), so \(d=3 then M^d=M^3\) Luckily our \(M^3\) is smaller than our N so we can retrive the flag by applying the cube-root.

In Common Modulus 3, the greatest common divisor is \(17\) and unfortunately \(M^{17}>N\). We need to remove the padding from M until \(M^{17} < N\) then take the 17th-root as before.

The message/flag is padded with the following code:

flag = key.FLAG.encode('hex')

while len(flag) * 4 < 8192:
  flag += '00'

FLAG = long(flag[:-2], 16)

len(FLAG) should be 2046, the previous flags were CBCTF{<32_char_here>} so converted in hex we have len(flag) = 78

\[2046-78=1968\]

Adding 00 to an hex number it’s the same as multiplying by \(2^4\), so we need to multiply the padded M by \(2^{-4}\) to remove all the 00

Let \(d=17\) and \(i=1968\), retrive \(M\) with \(\begin{align} M''&=C_1^{a}*C_2^{b}\\ M'&=M''*2^{-d*4*i}\\ M&=\sqrt[d]{M'}\qquad \end{align}\)

Pyhton Script

from libnum import *

def common_modulus(e1, e2, c1, c2, N):
    # Extended Euclidean algorithm
    a, b, d = xgcd(e1,e2)
    
    # Invert negative factor
    if b < 0:
        c2 = invmod(c2, N)
        b = -b
    if a < 0:
        c1 = invmod(c1, N)
        a = -a
    
    # Get the message (c1^a * c2^b) % N
    m = (pow(c1,a,N) * pow(c2,b,N)) % N
    return [m, a, b, d]
    
def pad(m, d, i, N):
    if -d*4*i < 0:
        f = pow(invmod(2, N), d*4*i, N)
    else:
        f = pow(2, -d*4*i, N)
    return m * f % N


## Common Modulus 1
N = 791311309087374588934274354916349141233150778762086315374343850126808782284294921228110916322178898551691669133101997907127587121520288166574468605214516304122927763843434653215681360872523253290766297044510870617745122997739814947286892376888776319552516141136363673315815999597035068706744362048480852074989063152333880754375196551355543036200494314973628012006925154168913855587162465714207917714655810265293814697401062934881400969828166519415465439814160673468968009887672546243771190906300544375962002574334018175007498231632240021805593635057187842353840461973449205839419195826992169177108307004404365745462706797969436718212150888171299620800051183755681631250040936288149592343890616920153400691102933966724025765766418338452595218861582008026186067946508221264938736562082192890727980844444978081110599714993030990031363457184296168457089953510500474033234298252385232725393194957086065274263743550741242453140557383981358497807318476777558208795816650619401057283873302725816795298930817307745973266335447938091252055872816232968635169429875153933553733116356920185396530990560434510949092154539711124052490142742567527833751624924993906099869301505096094512729115132147653907827742334805918235749308541981388529841813147L
e1 = 813647
c1 = 767202255403494641285723819543278226263601155898823605265497361830705668240032418501494959141449028517100422081272691883369257107388411439611318808983979122090486252578041006071999581282663085495058515958745546211668701835250122032715473014598395050184702983368667972803718169481809394565706175141425650370279775233813674442957760484285820381853600163980060348710028919659329781877491724136976028815641232407109144869660767954119268355348405951052583739555066569345526640029961785158127382321111833599691079949415049786723663210542733655554868327542833053024595895523192888118675763242352407948643537985861448788568550308481655116845634952516676905251579084404308314639717162526798451410767058423619677212069270398132021729448047980766312818656065369023093123058422620085273728481545680423266197847937925342263870309939913221308330842487685037638837340238355192125668409039255551545407800543798158964963358868702135730305156935767426581823180696819366253148799571923731323928995477390559418822575259531941023518182807739949726026157027426545624061195471888653152768495272113769751755053321333829345939391638863918920798107792346015224509118930143010726156407828938941341788657835191853473698010478888928860138978235297618195944868175
e2 = 846359
c2 = 393205642868817442649216793359718556278406137459770244761832906195960432918468617731069456704644789806507809829093842629745066759599286729538728368882491382997337611417441529220397067642218119525968897551289230558627870154984979444195757677411673096443476021362319325097662392808170632471553717355895219405644518503783235536597143112954291157798713583737689125917709618182162360535659223966858707155741267214975141963463832314566520144602105237041672437684177707624423211972004800873375670613148140256099552724408192217550331987310558991433383571470532995856778764797540637679226825577553396934734325550293550389623919904744913990305949697308222046594160302362669510242921299755255790640101006152269619965560742243168099219363626217512940995615730916134775134764069912120583282148219405178065222313607957426887495658080497917440100549199528894874905968298614233827155712422019324710018755792249855902168601927285980197334672067920857960628679370550895555840658121626134216719240409691397735762685349162277111815727100169755960553688569326705249270662470879197234836585418835845237231721910938341557726245940031873345666571751867755961294973426045629909899256967038811807893676700888551318830676356324765330202998096318754445585853694

m, _, _, _ = common_modulus(e1,e2,c1,c2,N)
flag = n2s(m)
print(flag)


## Common Modulus 2
N = 691611766208546073444876122261067788277978858453710639029761974358666489171591889808344592871468081368348731289584873825685836699513369087940744233044470468106283756269016888690397802087612562650740690626844050981638158798650899164329024889012339813251634342169796374490173324858177655412520581064091323105709703802894635752243504165527728325493775585018099572491218738859140069209745383085972126419677929983854492018948495162457428459536088314487922683148031388611849013227501962458386817851194913551405843074740308192841259015955432216658418219471365781271743026881045054161177699500233983945284463060091084401032681620162554495490307966608011765399197534175588394769839991952726269105973546086964385977836193216093842605576347580465390858378577913173391209728199847916944392685608959720919745441534152140791433228642857247821519585327091864890122871765266988285510728943279970135846908966516130597249552710186071954611133294079017500030355232895541367427153922527925908108643934213023557398363684188823565535815365161748782796247844503993809352854741573950620787090272760236473228652960605730173150252619759400890068298838592790770868307280012495168740250977525199965477849089021924445456338550258621310346872587368865023459114279L
e1 = 2623119
c1 = 632613645684838434911920364870092246688638723680203743297038042884981435531349983627632652213126007404455112992754038899192740232209237012089852184466576496173356903126767617531366105427616049893559911396536574555008451239827427140619373005107923039458285095437111146013805698400274937791209388463040761234346114146112603113513874269976957472698342250573902102976387047390228485927254752372525379266486917620487089416581168720140744193600912161065888758451629009978676721731074043142666019127528370181044741033938879227651226413524178992155234346229899043794846119210274959231350300191718278291314079326011260972911790929707654859407903619102516710246683375658271085356783673232677699444921875427077745087507202504075374873842972977165904031632108921391219453633100007509368853543202918527396858214941532156620908283394786740941868393377733920317480973184132461984594109692489226477402338664642727766514992506288377119275635222078018270479534265371971469799345627297451492177595572561618185463142728664331779856911512823762928116551034186671353283417747535010208121962539603383913657773795358612010178381857101029638404248669376029927680328805839410427459248430136708902815920536603541943356116875656311481908672896225539754812052984
e2 = 2611101
c2= 473583830101449207063655453483957320801977763405664178108962387145963115641321631378723122470718049239150183483107837540062110255460217493574236417576528210993551734521104360323008425196350719034294427914294044848231276934402896045785500160974092767601908407706594433190832523140982335688121038712802163776950422665847149664034820576774873956120202470663588902529914328392634164212558025176982387474287314624421143326789371057668708456922968762564019631616913937820209470604081356673188045257490667304640155390478645279862586730343779998826931285683980941686981775369499484033439920659579124275957233449431588512697916708510428626881790592757578867152025501459202793986322020476004209777449674143157280081483085868896558215825742742029607229809248023263081810931655981810534293127835168642962477010095223356972141559004635008185531900175232541978761179342338914489553003329293031284557554252476291770973145365678145226167965362251186233138510776436645583796590010200995100899736056399413460647507781994189935869541735701599175369334170081795310585938471394672279359692859881857399434361716843681313191143289947464231132723256066979526475873327590657111481299295002695482778491520250596998683754980263059514032256777144682239680031331

m, _, _, d = common_modulus(e1,e2,c1,c2,N)
m3 = nroot(m, d)
flag = n2s(m3)
print(flag)


## Common Modulus 3
N = 968303207185607392933798782387689522656147561712795299283882287440997111985337043607347852676675972362918419582716466493901827460706450708953088746657795254328535683015238473202723829157430427867421087226189467195646844668802837819623414935635764658530099227590830741510249221895574884771436827770318305551317176839494597881542410308108175111834839215570956517340899194288784858826431213509713952528866287993390613948062491441610747107348648602379185114554723774040662560407455840832110271813933032624805073788024993067973148443925303253795470847563536231692617336003345253420781728080545107013979989225215051608062044642404350318860297552684325830122651066498471494796197140830046228424107290568844093340204267361082742078820287806283549564233943675107998076566543352390069511549956964748416720763513751358887667167332126080075430087233981966806427580520370257808050907653401104327326631097877139317246068499669501296942050536122626128764679345686334508003799157031148558906404519754488943090430614449734145826672306815863417618237639635345018467258462900064790890385390508718602990300495726938127324285656651880960536234978827321187318512537049899040749483345012221361131129792213254633506153185302186568540749980375628514235030855807045314709882496753074374605804287524700316006092896795420448048753563680014346711220542647330945566829248331838201572696721484611259634434782075831402355726031168909134250473545733318680648535591393583591753681796583867361941369612638709097786386797652973805166862674686551290098101135899770942208220247225222462958306451292887778107274202080862990165408064372884914158792725013116440247234948462221463395579778209416361358418236648009499845276591742121866289571920719060295618309551857388542560147442529378101156132620061921583469878917947302508627776695573047820182057510772384875135795550437710313658255283287862276198618250884260442348343850066240114035518636573845052654416580159067713183299304803538785632234238046467384672538122045063632667757962772674939972792679509851714820791391542209183895101043149418861154827906828713093460640624918161442498432261330207213585143333235283987920999836862245963629061098253465280043891903366631221500293216287006734530837307036369234284523611530022158837165369780256375911835104289853776157817361701638375344905311830460059612259798600223588322136072986423796319913187356442617636479007538166981641749486826645166479345057550622122298936583765413411917302326827553940008588471939786317L
e1 = 13218197
c1 = 421111161283346431452404838872906910488956231402567019627078538397015129219548039141380131693083805603634832115136344104821561027925864923901767159809798556819390401416411855168293007844311613426948800208007055064348403326803934387258467126612219000171854953396242427891713082121012531213725355828779993888182933907101893044052692649728535361366924432892126370724588453260805681821935597271080255619110465374127164951502400983809536186925456642086304791751551216044579863129291165009342909475237361181743987301745314378124693429484474503217504889965795409106282650296184945237152875186651795552666842345066169360660546054986708172417429052514059615434084086154415920830883055729609108788179781445658162049137989591033198225687070565856609516100367268190340309308157085784134411282761584130225746032198957351227779773001865341915642873414205377145922729731246073639219795924517066513774579919237687232502798978463575009663263447306363691670476046609459059167879832079562689979943552446917015778003739858532004479603764374411135699895655736013845369551111690464128448955486337191304960262873891918387298035244888743768954328136862535082300010994461970837930794524673040694310506226189740828318579439950518115967189869637345638498098713092489244636082588805772227797143449747153355341250697133905040459624514982099584435140538668878747129925880019957973864264834954951976218071371679757509297492047186840975743403271896047156768874314108910566561868784522463064748746223313798316236978642468003218086919263188950066989044210829301678555320837086377545741001736801163743516580353549217680694256032377932133575488109549594325464409000682442042651791171660390153162096538381581148625792618196174157168997050557100450557288143739840824092541232969307054965994887340364612034225310418659933594966854225109483090892335755747449339249960596843266176465016510244036725441439565001070917883074011690676911331738356675397441288471244334501091751395240775991013123686801229872759306547212076067886148629332008410208267030715989530663720054487572883736818402878156320070866728567321649066842627412668340251628750512807830348760198570727092664649603270152943231283098179852700308804060616603604109118233213539629764618927518884532667481665405755714542980086417296700138731812815602896287231173509006149715343922041354056256194681983557852276963918040964106582078239501915086320391282791023780691061950154312894926940866878046518974877055347229774579384836298084254309194742164500782
e2 = 13325773
c2 = 905336011260893181451937420601175770518313987534058470576409049452599974940736949020892631904955374029696187995214208522797070994604711663756814784706053753391830801248808142181434422224620348115969075398677162880328104668870990618955018212918253536803780269490731174871303579036880145367252409300321511403369634435527150000969450834032455903281526350857234024199221097951905683106432984567192925721856154512618509568221546898136983740670694848845816274649037002810596080076911851084982546841069002779200879395931456796911067433329924739943299552475793965462348342813683729525726622940637841204356613245154725191731818570068876251576706021876289420301350487275708440713574921631267131651109260124766475594710481161866254565495750886839979733888772439130815149472846472765436552529628205718020374215877005469575372812773398343007234021177110808440750777736752300216949812950208548770769356889084232841311299404061610926387440620373137543532240294565244268885021138356121583352086433040479579285669028705571672002026293450745788592556823683194951826864141604029265650908715426822940827714455571796485962047146479512064410497475912291097113335318214286537554114706858926411912595063427662813512257156617697572638072509013871077829931469009241562237896598800666350337578826848041056097241547835195327840625894306586665539851835002956883837883293039313345815320389859457247452362675082429215289259947007386622301346393036750250168159297672722825807855637539796284414040339895615478904699195785762873300869004533530925681372154050324943727448464697359515536114806520493724557784204316395281200493439754546212305945038548703862153513568552164320556554039878316192239576925690599059819274827811660423411125130527352853059068829976616766635622188402967122171283526317336114731850274527784991508989562864331372520028706424190362623058696630974348010681878756845430600722349325469186628612347668798617024215127322351935893754437838675067920448401031834465304168738463170328598024532652790234530162187677742373772610227011372650971705426850962132725369442443471111605896253734934335599889785048210986345764273409091402794347076211775580564523705131025788768349950799136508286891544854890654019681560870443838699627458034827040931554727774022911060988866035389927962128604944287104134091087855031454577661765552937836562030914936714391213421737277968877508252894207799747341644008076766221537325719773971004607956958298021339118374168598829394997802039272072755111105775037781715

m, _, _, d = common_modulus(e1,e2,c1,c2,N)

for i in range(1900, 2048):
    m_unpadded = pad(m, d, i, N)
    m17 = nroot(m_unpadded, d)
    flag = n2s(m17)
    if 'CTF{' in flag:
        print(flag)
        break 

Solution

` Flag is Captured ` »

CBCTF{6ac2afd2fc108894db8ab21d1e30d3f3}
CBCTF{d65718235c137a94264f16d3a51fefa1}
CBCTF{b5c96e00cb90d11ec6eccdc58ef0272d}