RISC CTF Writeups

Multicast

Crypto: Multicast (Håstad’s Broadcast Attack)

Challenge Description

Hahahahha Are you kidding me? Seriously? There’s no way! Amazing! Damn this one wasn’t in the slides :( Sorry!

Attachments

chal.py

from Crypto.Util.number import getPrime, bytes_to_long
from gmpy2 import iroot

e = 17

with open("flag.txt", 'r') as f:
    flag = f.read().encode()

m = bytes_to_long(flag)

moduli = []
ciphers = []

for _ in range(e):
    while True:
        p = getPrime(1024)
        q = getPrime(1024)
        n = p * q

        c = pow(m, e, n)

        x, exact = iroot(c, e)
        if not exact:
            break

    moduli.append(n)
    ciphers.append(c)

with open('output.txt', 'w') as f:
    for i in range(e):
        f.write(f"n{i+1} = {moduli[i]}\n")
        f.write(f"c{i+1} = {ciphers[i]}\n")

output.txt

n1 = 17414378074962211907668262783357654709017858508943980829432647157830899245418013802602288154688975172268203056107194484473180983893839747691067368255451473645352472677462045491875156991903121436257019682502842481818451508856805604369972407961546939583736215146566974486072062393021233854136433234610302193190421517738045035497259745945646617314003988282369017620443815122671031227730761761329854708161430433638460769138068937194820308932716357293231498813473582630841734066815441316399012034862134434233451774634810735966345138359852306550585155200845885995438357504965938134974666607089885457014096316723372699790767
c1 = 16304813610585247080996509603968627233031198428098364906317923529571364732341076186255906679442693135543038576053780557038963382621529654701309179930977637434947813022135531123001361629480870221945235746990346892573442557057154088600866393432221388491215644719739151413066963236374345832749591127837772343004632200424062397842250271291995325063050370917285719650486853872102549477551231212962778502283533315502396383625715469151735351005473230349189242081113861860723850980722553218355142476155431575711073112662508871371915127357178000240286871834244125568108173914293415673159659173759387848333164358605231404581804
n2 = 11763169744296035944375454645570118216416074937557595149585465636949408768412412341337523483869910389521112049303399789331879684369328983273405416550578135666433640822771598321723669882274264235533217238136138087846282956614431279590295073615342779791292317171164233010974371705955607318262762161201846363437164638915350939624628498097383905160914005451700784026693435351608305396882947183155227872160981704780498149288899306956562027742892848509264733038912121414651548931342290987449083964583627476430997074743589140141283412243710515672787943216859514643211807365842452983599158775400596217339147653722830412531241
c2 = 6484698528947115110747175872047669822539960359834513311161338895373688938012617971877294720538077064674105274172508446731678618585055340881529988813478506776636434526685268440257312739536191423303491402913762001709889304153845964306008330146932585375422689822838118694382793264312712058044846849045981840573337194374705589191669659562572391670562766293660977982247146702288917216594112974160567304658608825783928401576999384067978978522747358283132990591855955610492750507548969626078894560130406088342545325119098003927894900187937121355216391336293151624661313619134775335382738704687085889029689074273269654167715
n3 = 16625810416692743086722338956750911050963597213774293596933049816380135384458861852764215741829897214091916949411791618882614976970344438638997074063348534420300757698507286075745220747470295932789197712321288255864993924933410691019048870923272312695706468070712834048680027237080279925666000496304860324334226851108322085534418127687929186061492331339391802586189113193203234760595102847723502355512191384971304396645054065985419215290937957177546279961631075756803379305719579191167275675404135848339198640475675397402681859399584442453774210850110852327785920034981282622956889578541125954534062517354696618631351
c3 = 14276131190269613145460845339854754469539593082802840501782746548381835898538096054942589555030986926054261041857274914492581289390319817207881407155764534607833125552793200171870518100082181850195764679516748935532665729877537615450674425659563231396690202524448809065237956870450206606654497324433876250078616798601094623869086790923443789031143069205337516127849438899361276329683702922943339059446378965042612743625334234736153506114653220480465056008456584741484034996242986858737860254134036050992037376993430891685917045755798662457537803401997945105514836100905189899292709283011868519811592936612330425095661
n4 = 22186472822684728953171900828914482833293976389248668145417515739253907786492628251194804899380473253396109800495823118350560692409983427403294631355395485012475241600761225781446127036722754408640361817016618793096200966875957731544221383969734441026158238710844627113603700615002694742365866379927149968330009976589020541078724223193833083958016999812952170311532652941865967424389885911019023940373586293119790651240226797808395745098607240010878808609291705197124042151420317680100326121307055516651794917399129066474058742412965934593746006030973919771719403958927971877386760015780643679922273362912426200997763
c4 = 15101985754854570364106816994185133177762647125011739756385504384177394658356788303605085354664510866491023136819663435073537007434571519525829983375844657255425018064778693376892544171322884375921299914423797551964267953932015076062961839307546367761143360904058243350373525792966953838362157230191946316814747064319320972413710576835262934189972734503954375820439247792123159443303704070430392401373387519175565044813491835296706889783941061343431176522160768477944004652466989569369157023520225779421921870393426419101808482140811933035393786211212556833203923392205571115501448716378134506153350275755505327815316
n5 = 9453613260395253557275978555631951776313426009235777070417309805876498883482953892627887009897533444550629310978373613096359235987178799703727768724268723554988412114991368378144745819993422242306882984745067747251024585432427588713845025189074178872172406549509314640586383652286218244288862076241921924235534972712694178791781827511108839888595481797531882260112958253684072458344404101255940302104406905142222577453564991577179031129815335004720408362981187775330395970117112413397845270094968815978178918473360421449600856518975316445755271919027915810130247149749551462870634223133232606518620695141119405365263
c5 = 9280665356424654734723710935675706453632394069521771942730958985526798622867838877736662794169040187828698514209500767599338358202168074657958413842736638290015578323706536013169103354935973639919415841878014606138534002257174655190307058091094335687165729477085309023311220551005572389214878785178570813429646475307550112127539787521662483527459735841742399766027028672421367481502853444062215444696759195235284081204844850437873186112488653990435126696719448226963666924781389299884636238074111806195375939517002866366109711186581205410254761188518386376134224610354623870549061485165715811990718199545173020681536
n6 = 12179151561062796341000099258057904377825547535432040283513796441092273994160959435272403605525310896427030069001366184620158772880803057792421011169144230462608762185803328464108368240728048547597109604736034171854679653957518720157918335665745071644827348692284547891601750740055757473891280513047508579012335456671317380183796451648962913469542720278742922657725311432977271975025227439055869827381179531659226484570343705623444283758488842368007540963854008033588914528146742886617922254793399775281433463474730655757718774220122920595158850904688877588903733052617639349499045041361680895390227734845195013100651
c6 = 1591737461544718043717823899350127096432669071531520857508339996715885119233857141737855407602014367439840283722776277770336490767779450588835294929202341482590866600954864840844041639258520474944416763610110650933665142629712285592259765651110847623433526741740159583823941595866957240393582380302825115433060191497641530569642750311107899804330085922053859025016160174176814815708283603816558361382937491609924608523202569993754886143744302350229268048341098769710865913320934135796320150211359792718645135040205129831836170877990304987268909099739087580271178769553449364582932340379681867324432361901958314003968
n7 = 23622456249166138375425869392941596873562869716571572480646412811103035207008568478493146988709091620748478701806376454683512115806202795250741092218334093558132301499455204267998852781874934550785684430850185130359697340839259567555975397776814941528438923957854938778661668114603952983601548214837944621019367195949877474130038605074374915833489476217591747692978222449312813586217429370284382196202506348143165970102666949484454036757273421337395858972706622777980054471993458938536521479675620409216260894649208707313139786490273248001802727121562383769584562753099234249468863435199155877735106121103559487154859
c7 = 13070905938869468739221114477191593513344483749939888274830739696552114220706294499555282936014695218083197570133330229562536655451066596639746404461189913095264536662220877479867284361173765882802612936997640765846213861378146111737001567487208482664932679523977892254737340919826052713630047436903008233879176007098443291490003083854902594792434730247881711109268487203804714705539588504314128385338492607508062944058291379311204357961378408805730001152718815953995836988865055968937543366130770687614443032797528044306934319846011008457778292427713955021984978431050962459121060846837252984915776635604478319927977
n8 = 11434056373089230682174893681785607962372856395642753472059540645639060216123372712932925356186944036517917150515720329451980414601631354475844268572099022496061962990888467999031444173399539880139179169666622052161275429374846548297103079486005224897057822418062896615100733983086879405916867087699896445291232617243992743135879600840609664752860522136162226719189935366331992313633896291582152321465281071899890325023993735919760100154932809477607774609259066837541286722501546499863400870137570850620259848445961691524217274576881945709862636910943495280452738949176925540881055986054989386755872503757925294202091
c8 = 10310865899003734543155921306375532885659338190184200774071040373759932470721475548282864391676441060725290688254494601783332098981110760699955860465210713832084153928533750847384661501050680021006121971896294561955331570485848290019096332317159311298496254258044183789456580019757341556058223835306113292833582965755515995679558040014330760996627296780341956012494070841356659389167224748194245133793423673543167232318871402508329863872850334848681997553567886645412623836931537741056532484004994224433792479833498057808623935363703390591248000323314302020342210334769097895026288660418605906635394371120688094709351
n9 = 26494075685680260114987258846164985436495488474656184237309210243246128144242758827927705813264697220551540580592672252051025331811464922409247975765248162393597275430244801418819389854579358915213484096891956416005242523108047322098016774092303802698232377086303952732620069610636187112000547912214557853701593589185357537627754671827252265338386709314662483631833289252591772588940245213921136953107431570777399679910553161739710108942179649783245085090252163719681415535773458048226074058111989832272024443672988739834330613716938702835971941485481382094488583542588529010233988188487224894843334595345337330193891
c9 = 15636165370385412052854599722633833199503103419377180255472563449511264779214732889122226394833032453511306861184499362690335184475696093804686547000153649271101057572634330439668923927563561835112903757927469768732225908430813952584804434071537091150872422924478465985325307877719853166733742079544954617595269142730044566594389199325082798483088952080270136158523107452657488278436361552433904222309384940625030850778478389670762747090512144113096618580083510070431829649947556686296909958050503823097235479644099142637232739358590906772812836263062361806709952416533622691232565475012739417847836435092819144413098
n10 = 24447782562079561639442774373737599330339223005686672604237026537155759795940404862619313660997622336572435727052364950461374634216360733604516147637871583485197018449125524197659451939920065781692331904220880996674583780887894295945829501317133243770933990928389905768814617443379014011855233867347153621663312073009526252858751359536241449815393500380695919895178463102844986932767544198722060323882362064150237863198594259190981593734750513667679782714845385265549251064673231705885002450146890266269106934397670266889511513480152441211547138848108588497718011277938974062746690834117784573025401242102781429660923
c10 = 18235863373018430220390508648758862339870361513422918113551012018541134031872960395192929544293047376768626842582397622647667821965300728564771219073267322347802591800778872103566853407696763997514354745540103358718678549588835217225282099131970644641476150121497180348239272752270927329658878858525656594397129934703246526884010710738004528204112786371032737098949156809277661105104008198845810699704740108183000536037290917121646954743652947987223962686938497917078780588903131152668980204190124475570122999879126717283989305142566266588476200585400726131760896647271358149493311784015121639967148478087984845123107
n11 = 18805691383464123955827027460105928573162618290533877883712122445987372878831307069033210093488885668803161472505612568126138659203979383704444511765787194528710221934171414481607344994825206618456257725844884157651821303029094579138100592003674889834205277378838543436988327625612202340211452806673383035111626884173183785924495115230812253762911509140353891432351879551359480733781695504700927749557846959278119843289324336153996320638177615605493581719305747469093578753498473102849867351417960407720552952740424089523789397186032368987926452016212045350625742112753442690101481053346245953576741522749241089254681
c11 = 18489339067532179671952170863746543514967844514419548582741176940535911470371146944010646697768913600629162019324328713189398884488975655388964057034182964743088291118343054432466293374569032336821764271682125630700303415234955953070617124180813141416037162538511841374420256225267872517180665175939853834205815098761241209799499700867576111539856010460022839280548457537560504954639739524453376774861081209446637691795049616678720396615464053491121834041353301281315852084386676250274821385634425769481406264720107307359091247553078968593741342990406733784412514977198333286878672844937011691512791609413316698142330
n12 = 13545491676600921382089856183727728877670375023010141840795580065539435574433250937545770572822594681162579396839384604893005509643252734772980391092188415856606910586156526375054259139288644596956702916764216270654993256297782471257956428854036522043683334824017016748392009577557307604353356230054432146397190159584084492726721268121508803998445374150652843607629467363591580793220981183351891388663031305505047138224922493660511384286603527833104112566048276517195200045110879194261407624642683056052775280060149859820199167502595957828710298498234848544363153962261584544022035902060481959708795979445267454594619
c12 = 4377623485085826301367743293677149339956000384496551400548942547363934130329440383702802039730429463319538350998537133758147621803275729930421551080448520405361521016347890158091446856384548029714772192248554585084064769521850756413021202781269425819870609906856281968849067485829096229439018122544218110247485370785073272330751391049732497308328645093939076653174239589412313473627121443129950055547374691887835464512398702813013930480823640755685852706883509725706694323069464174751083587495831602903641195627012327654571321296794532702817987367390547865211385020201647326605843658318337595506932538261480891112021
n13 = 24204819990235049994054015447124567090898523164550078561380555041399034086781344243032861783681215607210599327450420231538403085407471454541988166284533360762406638645760053944857994998605509795025479884916145151760707735633109835830689821691013712969116921042304112979058838113319092732629442768058338121297248925550189362693611930722429303550180977453234501783351583885850165347332002994618002598630336012367454246946192612754138391635713664806326622154288490019216335930966283269822750397994007545737055327632139535124501085519365098894181867720572539356270286549734897830285290524961567185348464971756113964717367
c13 = 15315201506255046156121279272633556070937415853668975753238411994021863957280622187066197025167806705166066970147013609718814225363146575366201033802690782386969096204260894306874059704299752597639848103479062475179898082191061240467374300950053300847086741632351264947556502547208002696726172297905235812631583304828013887039754351387464451419643091399260737520375026796380154727614972208944888958561712723494605527436489958321710082892521322607841672902389968289258676061968090598682743968106007349228053494265922513205793406588322920353598524092720618807751027869042266724758269941023121499645175808799316565386183
n14 = 16317706672268581018638918374141619544247270583871679804682417706701393526360978291209599726803536583996456833519247303442699009259945506560141969226659124515509861650768435614099413664865795812284048122718055287356070389453370318000010397416954612416897922013175868062671954512074667799128581489710448565414967386370241755786986582801242598673920254895319970339706642977100056913142569611327130868092257113824680178512501931077059134063561368971494631077900770257207541513897498773082896599982742745611705403315018473119177933040246667381613439132668631209478868137242894931330531105223626607929272135530078934242961
c14 = 4487757863381715344774560494316313995857603061161412892690069019689823342013027495674518771733127129436172017763577001201211399130121417032361842307941737689161252438550979944992719655242192285107526862700115079328920822305433984239117402094436743123550320990889139537887386121437877771501907282806480983497778261256698958997418408663148427836198226350941239244653245958820582065243921206926246010287052287590013531216526080309795278505659521484804186639244937846413651726455165753824323704206505743775707537755490782540722168774113388491799455255360460323832044226189889693069582834891586205696278054054430585084317
n15 = 16198513926567334740556930081912042820164954450216818554423661065711802280737167156975157254156094091793696498584934809816471236358141588271347930833429910957234353540693550038241817891110665595559191210111888772158206499897302446425299282951237121444061321634361527408342460172810910581545321316820735592425873512338496825830489615143801376468671920499656226514481824934098100268969225175326099897548846536719629471149974040302967497129904490943085381909120817232391570749552363013101474540770243887011470472662217520195817562243917681703095655124761511520303617610687510753544603063215241135725249049014786698995943
c15 = 2977297277552676061067150130724537158209288014507394407926144194024372814383316058460760535163418129236715963823194637790678174520535290916078439381340369459409515733868514399919180956148050509425737123475878582635478861898366528524165686826716335325272435359570308734190437308360732582346236318632382248998724656679950074501704462600575346665874692276792579526466553767534459453000456431266881817139678626034465936340854952366096780599321073146631393018665281141449045713291372469798134318240420959341146140142050050784856121713205494145680514451995040827742881637344622278906819196439623668250941815546173669282377
n16 = 24108415635634685053953944985224670535024128928050423653443759903897099571730594377427188558590859292411510946825925866400558543812408442649637049591607158236513568376781897262217800783937506642083121788871567869878927671758283771823519832894546642543058575700728383950688920672263209956727203563973010968586842762332973078913198703532494003199430285966287705259001813595329752131442406497030613605211507342797957342441593568453241444263207033013749007176011702654463111954480400437877652309872608965386248008625085948838538799409058348924649742691376092551747754858119369993164112535049228112588305484904524281079117
c16 = 8054771491285315706504069327425702746471826819418835464783729522694875933862811790182074034106617594637596443526828385810649441796295375019194740568455325332825643118578760967780876572057040253888861802892479643379396157000112158357877091932575706433120432551015891421493331912745284281467120649357308361064135027010267386533408904463894571846344194843993272540573761855617638978964163054864267810557290443255538688936406574859167947804966402112061895662740483520087242703792903889453074254487261799551469330625285029517714111697511890749652993023419805975410563900777795649757245531629312719339673996417183696180239
n17 = 16649003884582696835406759802496978877388376398976916972883915376607137774018540428699236440296426708499462071519526178020403122594527031004164370837805445201907401867820669365336153683802553249326984509903497956377113941011637102091037856723803630728819366595955574150693026593427798553945485995102274060181403206411547612835459801033547601582456660930318600451981241217097564865397853689662843881674681811938376276589068603624009624809655280841316148072110924573043979956140632219881425879059075140062709279305078523185449154928208448348239055636761871382953177327131627381963083631834533289380398430556011824077739
c17 = 1418561451454094106262022851398966849467957509478769369219487331223043758331039654990474574162954589125637638590544413343095287141723841705152553970253352210262546020818046429820713413293827143146585725275166571201808912319499943184011290305006727438294264295295990023786799418646639763995438568513834385890309171735186804402334754278011858629176269771826816238165062173372793060270613895691515942742311781162834251534638962318368144563935905322974914617871124782221633656200213419889008677239294227318121140164440079813617080829024829811360436953384020419618488995731498504046538256129828519836664721551347973119404

Approach

This challenge encrypts the same message $m$ with public exponent $e=17$ to $e$ distinct public keys:

  • For each $i \in {1,\dots,e}$ we have a pair $(n_i, c_i)$ with $c_i \equiv m^e \pmod{n_i}$.
  • All $n_i$ are essentially guaranteed to be pairwise coprime.
  • By the Chinese Remainder Theorem (CRT), there exists a unique $C \bmod N$ (with $N=\prod_i n_i$) such that $C \equiv c_i \pmod{n_i}$ for all $i$.
  • Taking the $e$-th root of $C$ yields $m$. This is precisely Håstad’s broadcast attack.

Essentially, since $m<n_i$ for all $i$, we can safely say that $m^e<N$ since $N=n_1\cdot{n_2}\cdot\dots\cdot{n_e}$. The CRT tells us that there exists some $C \pmod{N}$ that satisfies all of:

$$ \begin{align*} C &= k_1\cdot{n_1}+c_1\\ C &= k_2\cdot{n_2}+c_2\\ &...\\ C &= k_e\cdot{n_e}+c_e\\ \end{align*} $$

CRT in a nutshell

Given lists $n=[n_1,\dots,n_e]$ and $c=[c_1,\dots,c_e]$, we want $C$ such that $C \equiv c_i \pmod{n_i}$ for all $i$.

Define:

$$ N=\prod_{i=1}^{e} n_i,\qquad N_i=\frac{N}{n_i},\qquad m_i \equiv N_i^{-1}\pmod{n_i}. $$

Then the CRT tells us we can find a solution as:

$$ C \equiv \sum_{i=1}^{e} c_i,m_i,N_i \pmod{N}. $$

TLDR of why it works (see wikipedia for a better explanation):

  • For each $i$, $m_i N_i \equiv 1 \pmod{n_i}$.
  • Therefore the $i$-th term $c_i m_i N_i \equiv c_i \pmod{n_i}$.
  • For $j\neq i$, $N_i$ is a multiple of $n_j$, so $c_i m_i N_i \equiv 0 \pmod {n_j}$.
  • Hence $\sum_i c_i m_i N_i$ matches all residues simultaneously: $x \equiv c_k \pmod{n_k}$ for every $k$.
  • $x$ is unique modulo $N$.

Solve Script

The below script more or less does the attack described above.

from Crypto.Util.number import long_to_bytes
from gmpy2 import iroot, invert

with open('output.txt', 'r') as f:
    lines = [line.strip() for line in f.readlines()]
    lines = [line for line in lines if line != '']

n = []
c = []

for i in range(0, len(lines), 2):
    n.append(int(lines[i].split('=')[1].strip()))
    c.append(int(lines[i+1].split('=')[1].strip()))

def crt(m, r):
    N = 1
    for ni in m:
        N *= ni

    res = 0
    for ni, ri in zip(m, r):
        Ni = N // ni
        mi = invert(Ni, ni)
        res += ri * mi * Ni

    return res % N, N

x, mod = crt(n, c)
m, exact = iroot(x, 17)

print(long_to_bytes(m).decode())

Output:

RISC{br04dc4st1ng_th3_s4m3_m3ss4g3_e_t1m3s_1snt_v3ry_s3cur3_668ff03512cb6e5591ae1b5c2728dc5d63bf01}