Tags: chinese-remainder hastad crypto rsa
Rating: 3.0
## Description of the challenge
Good old RSA!
Author: NoobMaster
## Solution
When connecting to the remote server, we are given a ciphertext, and the public key ``(e, N)`` for it. Presumably, this ciphertext is encrypted with textbook RSA and it's probably the flag. Knowing ``e = 17`` for every connection, we can attempt a Hastad Broadcast attack.
Basically, by capturing ``x`` ciphertexts, encrypted with the same ``e``, where ``x >= e``, one can find the original plaintext using the Chinese Remainder Theorem. Coincidentally, we have prepared a script for such attack in our [tools repository](https://github.com/dothidden/tools/blob/main/crypto/hastad_attack.py). Minor changes have to be made to accomodate the input of this challenge.
Here is the final (messy) solution:
```py
#!/usr/bin/env python3
import binascii
# find_mult_inv and nth_root stolen from stack overflow
def find_mult_inv(x, n):
a = [0, 1]
q = [None, None]
r = [n, x]
i = 1
while r[i] > 1:
i += 1
r.append(r[i - 2] % r[i - 1])
q.append(r[i - 2] // r[i - 1])
a.append((a[i-2] - q[i] * a[i - 1]) % n)
if r[i] == 1: return a[i]
else: return None
def mul(l):
m = 1
for x in l:
m *= x
return m
def list_to_long(l):
return [int(x) for x in l]
def nth_root(x, n):
# Start with some reasonable bounds around the nth root.
upper_bound = 1
while upper_bound ** n <= x:
upper_bound *= 2
lower_bound = upper_bound // 2
# Keep searching for a better result as long as the bounds make sense.
while lower_bound < upper_bound:
mid = (lower_bound + upper_bound) // 2
mid_nth = mid ** n
if lower_bound < mid and mid_nth < x:
lower_bound = mid
elif upper_bound > mid and mid_nth > x:
upper_bound = mid
else:
# Found perfect nth root.
return mid
return mid + 1
# finds x for len(mod_list) modular congruences
def chinese_remainder_theorem(ct_list, mod_list):
orig_msg = 0
for ct, mod in zip(ct_list, mod_list):
rem_mod_list = mod_list.copy()
rem_mod_list.remove(mod)
mul_res = mul(rem_mod_list)
print(mod)
orig_msg += (ct * mul_res * find_mult_inv(mul_res, mod))
return orig_msg % mul(mod_list)
ct = []
n = []
ct.append('3293847019052727786541035934902720601644695034421577756557859920850498964882906479400870911190874409275908817110481239223728572351677594872155248607951713892417140978176037364974717205548078873211659045692641912497189140180737456350367634475144716592563221116644099427431424924358579441892705875381957916893571690491925540701213634940696854055832967610414391634940251052876872264330723192770544742177209661227660834474879241457106513996774022082980451108351848331572268152360748526251213022943594650000520674030957485527439814582860583093929389045597347728142073760189450793241182618944343638026308593457262386467597')
n.append('15631332602968433177667493381693993667077300771225693841727832462516019712818276142077266948868864369300868156448107322454427278543575642240888474041593666611001825321816644016751099026407758482916765848293629700773271668933733340427188516375482666715099814995588059176975990446871351221343918968061091019804225663068727263945540297891345426243087998727127311977793081225631177636382136620332782520940766829334583131819815460372691741094391653670033513734227476543741718326672394650835888065156886939809074206985101042008426979578996909198844109125628053030555775878866741923064718458884765985410142900695689383674933')
ct.append('14373923153873007437221944363986246678269508377731863815695426961630077183744526455544542128615831797594951818754217413698949703389506555440130960837432117866828777515026460963590706740716288541670646263533757451117002914408007384594157055693120150830789738301950781898637390899040411337677466495109644481186092442537933962172374834885747649848666896838809767473513685669593392909944414292935560713225131891073962315376173040532854111402946636654840106893357152733109255644963870497933921345766685568763997236020778560264828846413139642316561486852449045556735355478383232033451575229666232927695825604066136873323070')
n.append('21146258206239306969189458625795447178662567890038324250190807769957712858930818315160276126992660494786823453500058408674509632027576930659221506328696365523062820976376664241419375856503326133265203659846603834557194683691724003655531675062482083287477594861969630543373320022871362576452034098782886542755343629483447552966237246716161514244397722790893910524878795277536299574979353058053329725575568729514017647571180159327801838355631585973951620199454715328974630897691748662238524428776765786283813300238233186056843085414368759407831979321338862351926354793972128049629280083308772444491244652284366743175921')
ct.append('18103487439582474464892628577920011776886113939961495798127154391321625154209516293146373946112882808062208854140396233959253188962493322536407016250105560323279075605100647804893040738449296555838996414099311941272308479017541390119835669756135325888010445184895970871940680001684124487743196660924780015367131549559632383663242581236973377103179272760949718048075861868425489819057986419956372634466219287776384863322572632851452696957321846046395333494757744198909766277671006393761602920705159811189189521681565410059306880900416935242324428391801634542022481083436279522293061254919539616351277981061165798509646')
n.append('21588415183829505250424190375821640890039729128207299059586721021288465034540369463302180547117864987162165217745450910752149710451991073143461816693964010519030975957343228970752505943680593751373290763738489492810370648351158685477846464286906002457380026741924052897974474192669356389898746506383783711124998523995954854571564931172196807187474339796607299123625343669556512655446682832541889178210958445307348544198683584542190919874927489616194736315699286588069660360893598947216707705710038846656573290957752941503642400422039953245506760764130677343887348186730962067261177306572630090778353629084786218897179')
ct.append('3273631235583850549189228186003021607822692568557287526918956542683894570815107258583071887916809861582029865487041493578177297192134009029747596184516310531282345210692688172765586702140188433323145705363678378286407763448254013724937527670062663108605023358177569766095156221409020250980613375994028660122247326647625184767361952531722370326971850267605724391685178671398945150517171645817667339228049010469005983536913393305448507916971493694824781201411150100025538326956279827074737433604328067525713019944397137439237759342984909800772985982525628445329724781179971359912763333633274740811133938063319442656220')
n.append('11372080655513675397980607672131228081556565199749944319613784284180919588527081385921974846466722202840284074879661172199818187571057367967381158401317570034856553549570413396586584827141732454037782932837160221448309470718955550765102808666934304243554032524271190073287478989808858993785281432386251527800826893781609431556540636727818512937026235297824588547336249867006134321056513406827630510346078471454289118457183902493932479252313809660525137396357129293518834269644642140727554310024428021113657480678790351664604255503599355465003347018618046263269379678980948454926718964314429459697547558537471330209693')
ct.append('6769292561516064397857443604463058252631348524381620795322319126131929201696316509311641579296693819160567794948655571109881485374372680129868031950772367951038199128055084963200327839280665184401291719222702175900458915143054880927640299989362642484267430056242411634452976288430573798887210671180401828261132477639295782434374290202016035818451299687453325346271724413987943770902558472912109079775344800201354308363720648811453327648711820302986054695414469236219275646324622719156420056869344337878412082282036854730575499715006425586250033739251674732907285734402453191095595206947111402563471424522050321443686')
n.append('13785730193679212439516686526546706985685253807949120155311210890327365604403261575664617769500128093624978537595087546357849753720506041647834613715255529581508074924978790159173078392957599579644916299959236585196174695437177894030923578836439516365661347185521065020712460173970443200445644381772207502893809698543018479764599730893370414097137279501296665506020849366064318937737128648510513954708022927676161862641914866374016993615873914439045724380199475726531907404442260485089500854369929129366168579084388598200307312575904061161527824606324860148009900202509513331474851852084424307604700443708850851177453')
ct.append('11502967962949203917105612413117369732777498478963746211270059153357628492212596448138617132660314340301172739375874876397954033679198996981605561213723870899014773705473192097547299402750212807121497856384368586280717819703915033932438535996119979333629910402872892120898559074961271838819196183008723186296154895836574210400865458830021515451645020595566369271485965074444248765638797691356713432867223359978250559527947410229027632984246144348161014761048254411653760250431835274023341141928932314151051224724743991298573134006575561391897697014446571220190819820793468642055746494975551697078640132507161484318242')
n.append('13932420631040705663894352923383372697658473751829903161696729819169051474591823198297204219447806141370195155294616007150797493439041339405169907176223215744756822449140282857122735693823409860523556373858636277567969546294752847054635340879513557818966053985460245550938694357045935259293274633370298927142324675026465660104951771597972967120167995350849195388469891710849126245191126174675237883108308417321951782276640380132223320728524222235180295001033132608337099940635918329016390035960530318405416207560660921251828685919326688464340130878059055886891731351412354540365390652965331682783181810682020262246931')
ct.append('7484710680743386286260949855822636786109943668127839722173513473677448022907030315220596111499066643339029613096436698233179877894237666617319529807343849079188680444847336691140868781165905098251264715297967364450750958137730044129477330758572935764992571301342840736738138523883395072809239528810177715137988920931691642199778577651230643104707796930081420173657982866643660463835065520729402926494162056350585017489127674777471369031109370347565885223775759957472784102908761497959091912765846154260126550769577482114186889372018537521189346669720754600381560300077921773885845834683483637112299105534683848024851')
n.append('23312623205187993159074934976458481433518209125979399519275395668996797170897609314839531029186649778372353959162395884651954202186459096287236014056317238990291090309917857132435640739596827759763145041546132248199949222743517482794296193526344635105987806134080345779579383766170067292873926505699792717565485620396313899806615796753451226336302397859384353281541065951680699615320252955729045887875561977720967330088527880597315286692351549993562604258209763713705596876378055011904233756245656771757845259484825810006487624870363431659256811409301673922819065483586964002982298091786995305809818664808807912364277')
ct.append('23645503373803868400157130718678983139879003481076177079398284347244944717512287188182279927637191509123777930799660742322281583574055847403476026698750671209267000732590781487378674158344553652437893476302751642667226903465908102136674981294963950491070792181826774273571358654491549201821250675231116863568203985183813972982971205503756086968325102384094736663588562830102037299560515737124662951062444916605396128714210131297304578544677825856924782060601146666879528176515669707129147310949043839857136182193193736404959102787314854275411583581358765242503525202345572184914927028484227069709906782324188116694173')
n.append('25303490215035767165157926906313933980992619508533662732762697487844366586209172400414240145429354868225823792363116685840681894398244048406117758830408145751737030627590278532192179691410998855941418108287855660565057607302450589973754167288023376119436184183676859832457007796051276960621977070214060959424518644588979528971145543623875705778063215172524440582581416847466125600905121445378506804174049808635751166096998879208062461437628833038088231066781996288840738123629160750525549056567141195870325512566746706313649413825355872959483372556462378010680902085049892192443618008196594868841912463919461238028563')
ct.append('15407374781673955112529913427864084365304016833068155533292805718194248907958882991420678404933029164019797382928556855106027480872452054488621149487841900038999608219019040583556411464508153836129337793811326813437488899435215464887622001653380580448514012481554609988005815974621820496066017480867845704812666656361159957999911778872244230372203150406554657244905207544000972263781373084520613219269329666622372470832957605396572956958173792937378616127915497802383712061686184152689829078660390839731111073734576724555537762939999759733838533824071242742316457325592637134385371047563455929445401877282164967859550')
n.append('18238313554068672769998388848611997630137391902363871167494221552684281068960151156422992351365363252427753395820037066469104513310348930053168052593317234371321150233825793038770914544669565185779560329120378790528269744621919296110836593709691383374596815805234987142707449717714203255017861831653687709721018997714123849249763318201669992447652595802211308074631479303402103133157341637810846280712286264402190408077833797797229525554075427895846197366742605448326946057700283330789639529185527737383075194754507571213874019510318168840266001362599445964918748330725299752405854743207158007208803311213746104319061')
ct.append('7885891189529070957792026038171056928697184575285989787585529378197717735920875268922673051565163407113215087667433787579679425936126016592104010709926661935823980043802420310106007266747713370173581975543318418880229456232861335414155641232074965426012025584536947564653417110377150179089018574644236175333029553517629284676550096892174706095024371440487155474534223857430581050687587400453690643871712013977711633257178926865784672741548841282068209635737920859528542184615447720297910431692949251461237114340547316516026202041929707048080981052803490127411810102329962077532200568857757260261180909184272451581159')
n.append('12798869881422263043046231014816633956239805359398217119617909108364027373059201745761788998236470378306488525058923782045050451695249876939422005114618672289322283309071165518433103489432369043056475541386450297486759930807311561417014359197252513658495541335382444622465735907353802203885753455694976575165861444260182438737047836789579176646278232563736328985505779211814300377246453437958200096027537366123331988997150348769463526684077784667244235199131896036210225371967081688249716609955319749140077385248942041956996273851828418462291760269371875231366693317501969073878443218071268545532216842582813314120663')
ct.append('3554919909854499304944206273823825975436915133458811933209200212767089465790765996139489768953961194446630598201222589415840499978514282540241593221548496824858099566817082416646349653390554497100562083390649114351007856158684157782828998648230523255901462236875993267780607144724606957509194586296997532088965402963960948704897448849388427480038825957340964372379066132513580563864998436981871085863599726351534420150811661969075362693667394392498209521555097776156519153224981701335783812634236479037079334068230917188054237092537479437532317318428094807511910301683412294128731824899854725438086806628384631013124')
n.append('13763475318550701867222412956097698803087094544999784720127711635034185306863148465432458138779667593903626463234969882310603132505211002401096399159082336965206694165344885062552452059260097369572942923777110004195418258990653950465807187356745167926653310401175074081708177724891775808003410726743778953659262996800550346480756476015734291181975312363482162496784211763545220497446821402928123735734289610747076439956818944730714785269703411956153415764936537338385427859729545279291342965980554688707095985129206062876721864070940880411195115842186132614873185885937406331092792574406750615310218995059704850556341')
ct.append('11392240429201392525890028111488330252042279247797330682889959825078046441257830009987246570869636501989243305731815586654764312369211231556535546375743436178464823462473949797184488342770095241181908066792732222539337973242814828103836108627945986200882854356309298555425917979848383934817927218883137040244344779053907724186296893264263265503562507253065599026627994614505557364326750587617094495815942545243051720149874792377085467303342359607237197495327667810385949727759157966307949872953580798170667882003484373558223602023744029643876153139023464743209377690313060003683708859911579771419751963310660188019715')
n.append('12826192101198505951349372888139022717161769552927348124245095764070607696138444694954185725189087339234622187626079483399784013715606344949685385546898085791952582220915761384083004130791456681230569043883827858152195931160129160152587976674257723464234127838604925800950589142652880257842201274441306654272989632015391023036695098276649491336651698396076838987179338803145076411412031559149882044903019570446223671855020993311680370417471034141224702144910082798197285182791171262244030827229717551205107416869694662255950099080725029179766021242117418021959300187463595968553593121605582421570049417783585029230557')
ct.append('13616191215312047331134816746846133490415763396054139282913208149872669395157720504157936843471994425505054180899718308960990521000907135729589397206097005098756302422040783441500520685155973485345945608619536916728811825896569053807235030467681044832701309317409983524214050182408093258123082994162645571373203075644909817504492588301260717762579340402385237531515311225305411601884042883873485077759325323352172257792699902316134597640546459557034353817992220060506079879057491924875697167567563690696813033246206493172137806646654792253304331291313777755500226083192039803148853610514472782114477784799898406463986')
n.append('14279798949680544682204567563527619430993322982489050498751814731662486540553619324888296681692536664263867479676302859135640554813762125681805173055030820677088883831919206976288621131767647591308193433857403910118711356051385663562533544181105808838669333942848765536729028947100848006305380178136584632200162327215354939377958508204746724189418995987696576155583681056314856560838887374244871813457404932852999764195805896162583690750850830103809704087861643015003962512486156414444411971620105893485319527211348824443321716784176454018030381069778388822568547185195773346096147108151769484788374543235851947063917')
ct.append('9721558501907920925560960929482774049323883089165752118961952805940591743286280510204896020278977415532953405730928235086635911906135783768497697694554010437122124491927524358661815036578109769672864454868231337106640316042529131180526520277747954498384836051325572372346431436927728681884788998654044595423784656114048391435806774960126537301873089667987431477461204090776981995412528357309939854506445846811848548268382866561006697458454439405075055404204121147084578493435921635197931812420192549384182043089905627743435084444843986013990242450247956088525566014740745459380516929264805485857704396383732042972816')
n.append('26066673233480950974303563815907004709039131831016103577593490764619145164103247702538035282172835770675995910753710926824745445365765024393036829596021440265870474055985211837661674269100058911434167866242501863103692102122788304670603502993684882060958934354337212563704608307037177519844426068485568988365898460607750886637993029813409435914068527666109406900706949796747677239207681222274378218500704381056543815545007891391307515537018396827351156997464346080149464697889724929903399689109392743172676468755465756576020219145284709747196732173588598164428790707495183172036187634677562682591301749205241843105803')
ct.append('3528395522767727540008304856756620730186680949887259336651992512319888934011437548348898542648373559682379401304881814858158040811536913586258125028511737936477810338221585374581083248213416199185177097542004746038896957207239935787177286563557616310149646073815166837346611671280781829329467396371984559372498230379529212041721413225032901285513139611328543005257831547143865618093006599507774891300585375591831635302892668180351606226158975784199140548306282592801846545398234702780551165175188352235402337547597636552601571743742198808081558189983970722187535314094639466977204772788897425326852171763733492372038')
n.append('12092029201618369231023916518484817351763657628871748082244493546926976057367602830902099055751328231758732330431611967327382832587818172273594446851760183301071464506198003128867823190004648639523642635966286294222066296514936499471541446874228939004979527639826790218139877971529737214476808902055033480317486203586849916549074499574300982397096048785951921237509764250007775058876880639703714391913796997733722157732311906647996283051271994399581382980208467365388777291721049107669071733675298366349394565807915462623839098328226057573696593787924854527145008750039451723351329373288987989102525366861099062644311')
ct.append('7923687200279588433999079989085468190636544023344533411856559177888405761940562872678781049932539978503618807550642699072907433841521713139388687589446300638627025381870605962978622215343250189782127934745732552857817483251237543524778349089352640390876350236882913016601185673540611036111772802869232100248586846934084371640193346868581330901994715362748597864301887737702115219530166838183120127634420728719067746132504140349481727403415389406093368146991177283069700518385200874524055992172064138915103630217086756150445311294900086938784103062143292282668218992439948586508325944647369065832729392386528455389741')
n.append('14153977638579614706212148755808289483283457621658317652592836124611137590765845003754273085999871075873148404242741935449012917365198726859195470778025293624596647392664283670063397427015386973915828033067095336952338128118625550682214990907550436879577016385115546708717984962553863951282326624440401693574394387545394396078844404706367795904405853123106015199288261937448822720338241172602223242844594696671136453246270883710084763879532450023737720870800259892215089417375532717074758462908467469178264017173089256393918264945069704616690814233871254910140031588758471910132662147472906758403559108207028429203319')
ct.append('15597116852315814475944613633207610376197303578307654027651972236897604421179102401605515539393380026545180041651959341641268217010395892031154263625982956604144177563349644539247057729985779292950320989487145928454896159221659111072719641043835139589946204800357054197562769668902273039382190372707914233820464773715643071556249311854912094788067243231475805185136233046511350913881490947368324062831310418014475409936521348049373942673959354784197275756615800173577082249662134823910930743626593208724246186509698119692308517770848194527756871324649878738947222206701482876861469157821448649837205901037719858083405')
n.append('19334836331858490317349554535957561684018568429466068108825870376277532584702644193437073474768427374685002974585121302754643772266478275081636448589141252735511793770342188346695624794367980225035579007646632158327145959539520271355480321980847013021182476608964724465712559221440499684112309186479491532208532052882748880173109868454978721614912020395538929174078060406815715733124914568250907659797309746153199140980468924491755752722760233216289731122396651906818062238049358740539724319436670630526485749977073462571525481470107689190401773574528835728176814253660011286339762950739954320130898615493912679382321')
ct_list = ct.copy()
mod_list = n.copy()
ct_list = list_to_long(ct_list)
mod_list = list_to_long(mod_list)
orig_msg = chinese_remainder_theorem(ct_list, mod_list)
dec_msg = nth_root(orig_msg, len(mod_list))
print(dec_msg)
print(hex(dec_msg)[2:])
print(bytes.fromhex(hex(dec_msg)[2:]))
```
The ciphertexts and moduli are appended to some temp lists because it was easier to process during the CTF. Function ``list_to_long`` was also modified from its original form to succesfully parse the ints, instead of hex strings.
