In this CTF challenge, we are given the following encryption script:
from Crypto.Util.number import *
from secrets import randbits
def getRandSum():
res = 0
for _ in range(64):
res += randbits(1)*randbits(256)
return res
def getPrimeSum(Primes):
res = 0
for i in range(64):
res += randbits(1)*Primes[i]
return res
flag = open("flag.txt", "rb").read().strip()
m = bin(bytes_to_long(flag))[2:]
Primes = []
for _ in range(64):
Primes.append(getPrime(256))
out = []
for c in m:
if c == "0":
out.append(getRandSum())
else:
out.append(getPrimeSum(Primes))
print(f"{Primes}")
print(f"{out}")
As well as the lists primes and out in output.txt
[72631919237287927717402325207066133372227433253296739177918376436148037178709, 113353610291242016590065192873217709952603000986249688822443880798128343484243, 61233066689578933084047067233486334593864627770848707460125612953653435525433, 77978495575166025609783168685853318929929985120608382285997233070243753385193, 80417172361794527546157297403719656639313353810617700273168888986350803004203, 93800524062346599265231876057535203946903026875666516269890416900099617168269, 97119169071341082676466697825381644482201126912248293435182129435216726548277, 90832133440133156989159367279306176825998079966947793083692222518066327714289, 111156153696251933778615089796986226303676502808517311473776412932401230476889, 96876329906549730024451384329729713704506332533562500650498800553860101511563, 86286584634698122955683719925475582532115192185246692159668723874434524279659, 65903466048748173224590166091273334517945429553166084561141664315404238203907, 80257644525014402296950785012990048502725806405293146360109821535239650852907, 58373867077613198457078300893876782065732447821855506855323213372595523275789, 70307897209099281479027830823136514151063615523489003132414884551468231257349, 111433863257040047657057024064485609580701784312490549902307306283243603655901, 88549800795939126019069388048803588676552691797977376332734685232332072164611, 86476382757716587211956370701024351863110631836242977802213434730486621965127, 82148112346979254967951647310613710507093341929507534256164313491746002586951, 106206517690710852498098306083737354679143918661360147773439327973136200544311, 68502501866658798329225146058538660769659746373219280578608307065801979206749, 60672358951835789704908924536327269229608581722109307581332432233259563717309, 70488882148348465045675146058646614599668994423589427829886289191979266309117, 64185058633455168148710182741821325813221678857870192808147347568058420273539, 91724253020456850774223452039983162340908864012274266250017725349818456783109, 71618237842953542929146771617756902175854017308219041983516624045533290148671, 75197023276518530624655228580159958392853075363846419358432337879052466834339, 93456081017428039908487992063415745064639093391962404368815742573133865752437, 79035499415501060554217818757856129296904865755428035853024745565351157316251, 59805093199483411592634594659959433594218194158384486422971106353915012766411, 111919408600330285952702240192537220923756596627204818717634835189071000322683, 75262644644049693251845454083264477166054642560145713740591274195595930738857, 63107291444793410808481539494468138648438940305354720490618782409929413465861, 100744061032607556872054413723197117826172064576093844455427086156246778889609, 69944098927494206498383429919111314297649499702904660445522561403747921262421, 113346972396001245314933795479549184611487155362285473220811161155716839719327, 74218688380879993148756363091257639519963552776768614571709238172311300379603, 62830315819802766439595083912661717804465372324778782249424277268108619546433, 103264161057748215037613232072468966385010093608920012110892839613159235177147, 111745284062876886448826120017412504536248941666698326600263722937179667853781, 102714811226433002942383499624250583152662882905940125612155350448548464659233, 70611222487436709133983543636965319174743496572075436130858190029811590943047, 99496810066970068259786437030853049423281070820256977962618890794465017825307, 71897979109619597470537943896799947425548512082291096317243737612115174228909, 104187436607185844120347890155645701189598399837540491971438994225658781627931, 62626312997351703501975166956924773510053238259969168260649056012070009346129, 113589663301872140232122306385311526651909749000264118788303971823137568335927, 61024064022365023006890119146557953676560021212017134989942000718839066371191, 67026055890389695260806295983401484022484207056900797118789120807500773539953, 86815148471309876492491436734517739148151702571685443764968941852499867942769, 71271715405688825890556685001974607477934703744599035510306362314132173537477, 99601448482842965306181001731134137098858054201123395666516878215267767241199, 113333426140866487376554632761477764435792220853166221631449357955587299983789, 72828024963517400487779049720080074711403344159975411686009397463831059644137, 95860312447047952148765088986164717003567500104677736410327958593198109354407, 80253883455538900223099283453614543220661664473671073544320428968033889527471, 103875607752185714512846589096341482991367292949192208298733200829187258671351, 62561055349714801292067442755895194201721853024266377169040217309869576245841, 73521338255369954464887173385770028245451155962437070627520638378004981137099, 62515182894498950668092010345264549688065719192878104686749339401615027858943, 75835218084739868375808444485023469969077788504144911291940699066842732630177, 59459793441768929943273834094267805463472005475964506059806584926516896170787, 105671365703942819551817230317199973226465615061686381878212933469608213104791, 78371883059256395153567659973332888704799612827628137474389521102815015551753]
[2819156815559098608935907144572220067802239722477811081781526014230815206143508, 2445222963144912170178987069682029265091235658826949940106147055263923553533629, 1903920232368917874988192424627324450235235658985487184886880478410683087792453, 2813221616898999319078173561719808991996933181529211199247718014749471761929473, 2415317622707046015771404986131301659380189613747377882523905789358464245805261, 2348523668852265507160083343621769660315154058706123058500525154384194150702687, 2507695532453621805796926889796960598878592310480558358405686855827420862837893, 1907141158421921299837854094999465484306927424258825549221658114723429318131800, 2996584876130431493975535586331439098020486704416414144352617491038777966622026, 2841914974487872424057865893430216860909258234230655793947295714954938560858141, 2117193585089230557096034014862868497434663348391069775085361601423465450067018, 1618663543487567888006759147344706501846991096986990711044152446484281789092728, 2051102508394283286598498094689699993985391855870591140003037895002327443967078, 2669090149346309750541187701674005414846285203668431896934154038082184277619487, 2821099205382051817689533851435604893781741191048584470901901981584399503252461, 1865954045962192539436077393382831106338177626620667766785969091756695991376972, 2834906719283370643135074456045826212415690516444993198590544038983805430549716, 3058345091889641880414874285391801133784878450057729860963845535706661712766583, 2653042015966370288730193574681974757937960717309316465953319052871479994033878, 1788584754515047633120809432697937475480742012061242716418696450961540809452374, 2778277203488613589832969148165909575833274521043706044098629995730733708920929, 2224400384415239578333692162811620743296388325332026485724809120569740438120124, 1972940461789417047227766171894128324311970620153289908353435148885058189880133, 1939948360526548190060387013721468591297090070359598090670159708826556568545839, 2818991601490249808138281165356864885716943957945691816617065879361927463800526, 2413553262118714460433349452670472062344099074014288014307335920153767804918120, 2413408800394460311364369792044980960839523519084508082211467486837363000827481, 1758845426962602600761866862339677239161642023927162827960263751844389125896820, 3233495076000044704300506440819729106639319294573782017725443419307932794713315, 2708355596539216171690103715674029628340788100952569621670228934102283487612686, 1536652946359811468561318815856138090872457809794218679329504600452203252121629, 2327165482735512477249691747760690742878483734660461193688694660880638031420606, 2550687440844783131751933234767946237202902423067833745512891069590063347516760, 2481177146135062825829716208896765976351123371323909570126219611506346709136544, 2976906326202019421699257927192517202347665946583804579082838347322272835955292, 2909029092339889063676233410972251606598736781501969698497611221586863427582444, 1798168243495600724582836684300392122016253713231480820900737994151692535621603, 2664817016106873773717597564360502202007571267185845325419923202388752047491200, 2546620205597503490932601602466124914531025221973697650652600774749315385983563, 1804691119541549731083265041619037469167936079860917628791885523586484670389517, 2993720664170395904909588354135052455143402349099705390593820631482848174273290, 2824574876463230873723626432904311683584749415106379741312890350093471390708956, 2178703956912849180607179809502047743725546451796949709962564121093430758925487, 2015984983682985181359500837085489870066576772548483853603306753416391570995652, 2825886744264603050250570710182276613361768413096941638852875242334626590323394, 1842366850389524393863483299415974342118431714168940010525357278313698104545686, 1890692228347751845977588240213788310482016364994323180433181094057080388377341, 1859570245693698000930635066477255198791798456916690502550935397773277654892786, 2125075140724245092030270985636432641827993478574472770023332164359192925667914, 2676755446455257799105999866711022387760341685507440939934907661068577868325690, 2127492815150892523930677422663426899493881960036299948563967902858352278756381, 2214414669786315022585169610350112451053743209985881827547493375134440269841335, 3287270883919895663649415935008492686272583218112557495688303747999607127347485, 1464885862912061941360124921607846166739201296269644683550488862315316621168915, 2509523466354990323289405019390879993989971624147206461818727132356459058566874, 1908179787903012986073536362508511663101907793909103292522128933290356486740831, 2756805796292724316578649442951105668045760292153123880799123727624430139834784, 2535051048687395125596454929207466830174234064994395507994578679918815348311204, 1803956415800944523172461231393963076071547374162301111338088773341404180366095, 1581427673457587965377040867880744385708196297129034872673417280313414009367552, 2210767855216344078808268682929389681422344682528936968055695504737022629851880, 2550877767452648921597688620286108961639250879503878114842193772033576204495050, 2756447633884757327126748105695942994431200035562027053510977246623093748665864, 1964779505858686501383673184089092976925707496895287157463367011777877630214817, 1711601297301999862146389758002427112641271299995210895971794979535949846981662, 2603372280135481877885014637230736101699219758925563658302680157251609514729763, 2667368415669419620483366371882587489517753424105473575306644788864390049717122, 2375381791051675212713652990248979670250212118711539078479113604716354841854844, 2493019084337584580000577145137347950270131374601477024044058401572003131171703, 2510272034609038717473097414524000178497639528965708166872787898622112571433878, 3376645650205558777740641900007720202740974970958294476802138375965090427473755, 1675454950441201753341148918023526478031944115873936771857166782930709781514176, 2295573600228045311698664671032537593950444762263429917312199003345978643927531, 2989232564205545757256184449992766612296977264754661974992606639914166850018847, 1868488082029996620995659067458996737428518781510041614792233972151493754021593, 1892797289282204998558656233944707165344792878835655367911040680710800217026842, 2387274259011256581212632921041457702119262115024449666940614377355894562863869, 1983881332955491024985326286718581476273785076433829348701324483746422111982812, 2062767935119595318038310126927517801164698007835687279422680554697212705483997, 1813426760548272486587501966021027363576238607043680794995756040734812014712643, 1562722510157661651420650013368819014831598048375840600129656685790447905077365, 2503673291651808329507024991940471465924677096391781913465384267653316557369694, 3062166182385308323163803924577776096950506098179031933671983253622594360543831, 1587591727372004646650383007276778974486973795582795614543330273924194355879822, 2124191961778288686577724783613312141001752051971190691410871783736806888118043, 2807161639821718296747775878877393924108396927585322529661889069690379681631831, 2733246030913567509280676058184785395993901538144190159673188530100162954586757, 2095734027587628478963707980384021314089446286378559071426863977096549124105443, 2988941018164239592895981954356834130422828926400913046430556106893050888967261, 1808937486427315645718998608467510156824996634701840345775870478636993074414998, 2703685611351166699001869484070817849345096649407749301012107683124291961022814, 3102613448307372159580295514146090155031564221004892924292098653939442448602987, 2177101615271107571142318136385894289129856690017106068932561385040022673438923, 2937151057349964713327739484700778587301119004787857337542161351225777024384191, 3284853954926625174312940587880762860995369578650383285440565102632766263047228, 1445263692951995462669671350436071269459804664046732803232667890225299584565948, 3098676865357167767681695819580978584292551422560325551761761261030493576490054, 2785990764438332102573798945869163846058964169046667905446760842139596358710096, 2286672499975498339110837294171463889505598069964900735273552787076262216195906, 2391874898075608542385911568726340514438277750074914316438113074664500269203548, 2605723731444632182682979422507162229453344556769061654841867236618061760791325, 1704836746065631894082906921469595231141025078554131926066714879810005676323751, 2268547330405383390451485215576699310201492241110811312277295403794298328525318, 2257279690119315586453943222353936242022588071540577167031856674546385664274173, 2872612890312518257758936879530195946285789167890762413291543959195362374746469, 2782503101773215051391891616156069531578324959687740312811009067332251738718639, 2138140684559184701106744969820800303534456927075159680357462604985136618973448, 3095278460762504782170722834315395471811818415470674607477221955419939863412688, 1918147505022892323887450400533906049794530447772075631502966582700819074987318, 1707010156387988967567351309817287890962086105434244078370980148566691847226989, 2314881420429035304174113419210131391725806719440675908882594861083902503989894, 1747310534609110545360894267130302582086449810852064052514438793880321649681103, 3080886800074193535767113381895308001287890199225312650567732780605043357281585, 1703302394447278966593359250968585558627874162942204836180727596194447436704731, 2669959616748655909038072864148442141347343478193254233924937012286825458693418, 2678347981660125571899295349441122811861081559641451673761407195954761042620360, 2991379536309166201033224610863206913612841270474721698767515583673314564634450, 2523223616403538242735730838547058862626362247959528229773500469162355596137501, 2642334249408957788795981926934456200612035825182578292078882855617370677855476, 1569264447503315408491941272069637567187075617506995254256292388264423968802988, 2882151918273286344356356582994818011404936455027402382189340156913800330427975, 2158967947928376114000914445674913628201764160381348927457320635619197102958046, 2051737874569931765249515775461268812640666956809870235551742670881277489362727, 1763323742103061035663123542430905313899541445815905288785170098209590602129239, 2713986379520959678928522767197552952345350348987283755564726696384571034845768, 2537378599555526856829858853624086645778822512223537633689220391093349190349778, 1559241246373570128428798700624771661010342250781098062213106558536948558050766, 2279150628340411933639371451926359538099865357708465543071800823000587477815011, 2898997193141068749321572525457620525323957690056983345387036999017795349699409, 2522226015585642028656627937913370376228450166094635794231237529375655653354731, 1976905875820155215040299709744110576065821433679615259775310771962543694656698, 3146904959601041464677308813467361006584585805682305551431275878689319837940924, 2693972707687221507896250578017189021477213697938899249523534331595305491495324, 1624327598106729094885115301581437685380703813627081789404977021142280698320107, 1953514564966249010069920346168045652870850335033365089388414276370477434371002, 1626888973038960042489813971944630122654048243552668114260339025510208408311822, 1691170441751836250949367136389943978609695857804909953940716207113664903533044, 2872352457635317352383489529000387930132790666173838033868080090425309904205463, 2863893510770920872155566640788223513715980556898590207492297802804734220666273, 1664325124883579998946067059421408604232610753151100601467802141679596987515744, 3241231581569478941168907165945341550977831562153048119560311010399685701948601, 1361807005173976916825978829400623371016110290335271142789044365351489158265785, 1406627349406527471168668282696809465701018718681981074249372097245594123964851, 1971525597164878946966277125289812240116013457995908459722202952295120967951958, 2786911678726247421699703800762265831545443241798747206478605511107149362330097, 2439508492564866839705294296041842112712325553837677868579211795105087869136093, 2059191048467669923967691687228577391906624742849738642011719916045439079304823, 1570106312941323008471547510823923094983111141481917147880596218618909287869316, 2122987705390617331128483361876664852958813888207310728315947431193637092615610, 2801489830287263060085120056123289367371498556308329538059159707855810575200325, 2603504643744222599357535179213179516289477923306029799301160287585889511538186, 1579559950022451616002666575318998221718261186164798108063013638204271323515426, 2946959687392272154774154223307645704738122794108855599681623985844195753004336, 1692770221755889837201538695387588277166659470005431078018491728102054788606405, 2659449088987888852195471961116502165033707350474142851843714185859896260654058, 3505646321172760059446810399769341926141272269356767693575285534015133195241233, 2530481419181774953758830811170792749065265404043551952628317101074384012856365, 2712291448546463050414385318858256938602633632117389382231541762951484136569160, 2771788380581020235551999360102117509781311204513808674596945948863545438935552, 1955826919431026980944761018180907821649592615023066213634119373120418173949204, 2233584311947835760483846096048038712598649182856770677618031551939193923070629, 3394595068511229452615822692260046682896960654048194476745024879264499379417364, 2712573898841928347986369197314358548875252769951810734215760791710091814581815, 1748981602423073911431838108063086650192315739500168302252222265177547421664563, 2918701578242467135076226389338480065735119480562687109522929797564227072493184, 2164542802657835484124827216032688263572786614573372525249065148400873809020470, 1135304887972847560145538866404958097776596359071002711002875129077851779982891, 2205584540603634087173783390627256443719846063793628767797341432227402910992158, 2690352932777477095639383802001157556275154650146494280789592444767406723210088, 2303944374984763927616623281091903699148030217974972202655946341959198480366990, 1826879964307133264320563754533689815425723980821932135389272772715666899003374, 2411535830583065044709148037012533536301300387611929837028371177053977732254183, 3102248701716368945194959238072315916896617832833372561718927136392499451559578, 2659059708824611624428432407423533442925665544505963263289772494964288235307875, 2122091574300829544940359499145373746146266675687307129711907050808965471122010, 1700916444187293837558906660368523799466101955714678788331652720755325956184538, 2567718060732115690755878753641406930783934887601526519050886636729753186426791, 1952081132214229966862614041338565988918704651475436080348360529823670476859620, 1660215762591901715725992379790262398087569715838733505603236713521769589358820, 1719279125595280317066033690110562638515279430979107832569413806636508635211996, 3150257746796819704620980918552950504464974368953784237516693028734092071089047, 1533483464980797817093734747462583125027126533889191512411074224355529845622071, 2488961034310705334758521978741509630299502434569628208806014299768156795682257, 1949296862369855738672364903506625258331673226248095354317656816116053344797835, 3314180997278886324171475580120649860821510669127198863042562159001687994942122, 1835912431730828052486567697931843664151353173587570710495449691984382497927315, 2490573473773652707889662396932059726458725983603386101684045752109912066544351, 2034391449976822309453187815141830984379516892947671482205865823880790979367955, 2904021828859719234045989645729651328223671397095849600652399072239977584752185, 2898092590337486358630458611863555173232553156056707848156576249041471235470768, 3020050896501407718070202328514173978695297814931297739049640810470505425773745, 1162913829573891584933621423487787462781528876246539914934653605693493109367743, 2411509537509594942434869563398255803405247485496687541554728239521209563719728, 3240460093945381326170175021314548622274008446302186694162254988437882522956789, 2042576958259566656441090421986717161687799145769915833228519921746477531448760, 2553411758242921025239995694953337401215433895789864555503864382953439429213802, 2820514264957484223884788232888402572082052875947845405781652420449215392785603, 2641370591795997642215472507781953866796675755685964449326951672513035331652719, 2823035270072193806363721364627815545328685374442891399776824815269510767922152, 1989373778720753497822506435334497629024665265080539577357802530369873476548739, 1862386424241098951111754027338499846132635633222316642962968740112589660520830, 2976767130013568871382359613949325813684341929036309541118080812240632837951917, 2032079799183763407608429385442348826534633217836159747315522261005324747502541, 2708285103915655469463038547427063010568545575090977468837676375353975489314033, 1763806042471114758817803518721264989399707893537069108192481105750144308762714, 1937326669619940914067700437225091575824756751300418686192482170396808556973038, 2435703549632943593049899499355898299013949956078689678733600487087852297494155, 1564269996471702815616616340843697420448380748563779822431189073561802077443811, 2456980081971515876372636881680154805873081926372199873790185654198943312487861, 2114228222599900470093715633907929439859036580370529231708091911394217318192346, 2412504259980354806049559188591922758532822094151137644379211660889448844429578, 2635073202673673572264139459896284480350454830352313451411706615748140392229736, 2725320685400498493268546434049721871475577064325227566368156917361595597089351, 3037867883571431356133279924916838430904119854900038874159214526715272191199734, 2824971163661740859800864424701755168512099695296428827528594616947609789856313, 1719312755020161540743541987056216628179475180251054784014251838005404915359190, 3012080368518302834546286001958441602695677482755944367912995252821821409322630, 2595410720707289052259292382365869693173486839668185767458178220761996549540776, 1730386135469589080821808335571789810133070354002257675548380927002483585203525, 2183488429559972081266293580805381776596408303103494625441288200546469064198052, 1586663745637750938560919751995751853774793809756290411350824056092900626767581, 2633560016633693373820917408699356704371120444974417409768038767304741258416882, 1588266791029338678483285861004896440056893325470901832575017393368494381844313, 2062140763508547310649316830659374267702516490495399524838782204228464817557303, 2210631662045486660045329182773925615869393461089725622733280699922614662573188, 2459357704199420786919294385229487410232263583838342283632925369162881135458784, 2613643032209168797222243130152765007369922353402246208144392804402308111491213, 1710948753142088971871638997633063611816787381413888582644218262719506545790814, 2370888885585089451526475579030868634013098608165933127887831074072488486211027, 1874802131193521153356429186932124966125006368474096875577533362925609490873675, 2257490811907741146287835975463592107772672753660997437720973452168570067018183, 2027396376118176181554556587461857799175262388659116515495331190904871780900168, 2629203400695349534340609904454384114924188013467883308551455289883598277506576, 2890142848965203803657678020364632618710915881162439911156088498054480848444284, 2219081521671625674270988735444011710759687035389885997488568461190702712665391, 2380376764714634310626713438415734647767006799419143228948264493667246616324693, 2814638103849795047350222194926779177051843856327710877892295181020329663696490, 2047838076416771508199337081863868486021562878681029339974246205098649513457324, 1784932180402383121530422581359653305472252436816341976330551492781428029261514, 1941527319325036462639722135771653972446143884927214478817515634545849137431669, 2907563421094345848181477200768863573314924396229466732653561249857033838608028, 3000337261597585046467954498628106745718605542524330400603607525806097908557040, 2786351435794517058372407045515681838202163268432832568806234013222378647734555, 1836092084933347325356728587763659299616726483980078801819666587432774417206073, 1574796707547605480163763402663498447991988000366600032231056878314794495735406, 2353612553114861608109605098910218987289338082728729053511317177449593301899294, 2248699009001439455571494271407476531250809026878799237531708891383695128771122, 2417476639863872938259290255198814812522944882305274702168279778861529389946164, 2971783285485191513675004761256201878142447913010923130203347305001342064598990, 2142943014519370915558067112669312116295755777127417301618377823907694765946338, 2661527100047693021718564373867938790031132276013799786506265512546563727003637, 2789161914059543582404778858005723463894421641256844424769515176678453044603337, 3040014096172959690905204596262839182154829748346494437618210463868135852399494, 2635917392114338296279286936931727170162216403550460752678274156631579609014634, 2739029817120645069226715038276509821027853672448467093767065178330079288792182, 1484738110125237820910555901588888998435780560979615982696803082959376104709161, 2372999157870072620027636129336264510265625974962517451119668258432432453459291, 2455687222461827602660206191412397063350581337238480459622011027481646403606246, 1876432865628323024983726722907298656929294958135555012103492960934104600220219, 1307841776873030596697898086313556358231717270837313632583014388160388520957206, 1930461711710915408769618026875738822780815121368520129692337068401427296313373, 3325280034101518748159577481976984799447956248994089550885201924665697013425938, 2141730641878301259755102172773233369139906794041664225968362000101121750584861, 1375656209370479485060378259057252116555118144818855052445166926233837043706214, 2977769163020142792135228863060463623818385890145164352689707153311169566103001, 2002834314014321054187636141249638087852858776899333125132657509142700920915899, 2851322935231676704267708179361053286697597203152531856687447152874802460360864, 2992147055296731103287336167512602309601875655087942903948613982271058288601610, 1726152188820994697022282207330085869001951550140404285145456533691648598100569, 1888604908855715245619198652572645357831264155960901438791523139267142437922964, 2352448954998759084316420067380678866770050286925503771493227478020356378487607, 2048308642686539346926409497753971725904482476842642143130646956853793335448162, 2501794434297131030946196089001233568215948580707283625912119735439908255378216, 1903581457860725006292290733111833468722059955064722300000621986075260984730890, 3091137366193643814130757614246951323703457976373978819948176036606067628695033, 2320974233653240015647239860333344772512164840786841438935137525814103134556389, 2685814581994945080754008326997111441187184408176728102326696887317673828436881, 2000735932503291577967925242471844116928558854574240520790749980890194978580328, 2420029456477865293042005101867311660978152293635853664008446797812937597305509, 2129555161426105317333875952515114347501476208979636012506937915200909157703983, 2582947141522611573263255922392440642592155092034175475551805098992649126512502, 2007387202205259405202080331409071622936010454228446167685562218123845168427194, 1555346362119608126365015153381797593304002606210833679794143799398649488008709, 2627310074157008615051031552873690677995763263775766597112117219178356232254138, 2614870511241382676735961019792996302007146563530003061044256637662310198888354, 1835517951630184004031358550557037074114640173264557591588255546633305636557964, 2191360283419900545159044662092406127521650045451596375234153785353085173024074, 1633587445499810699103350031108401299972286118612069333913054471891868634481981, 2244506220430518115591858883493205895321869570070556445420237854928896037980916, 1701933270297668456594030101250077900332487913784571880972700238355040675454480, 2073349787428363296079890283770992319911798913918743690389931150271611080940175, 2554199147351498854198124357914578384080971977075570829246726644622890103967478, 2869859353109108769884032621260179038333321889811803968916073817470951304600426, 2163535859846850182293040680340377227423216011265031881108965948829531859829146, 2127374883010589876012860539719535092731861273867713812127079127126859754504360, 1938864159337265849599773369625058562249980220372090673684508081397701999600056, 2757117073936544413482459237210873364734485018520440516659943461070434895539784, 2173928418091053227417706702891687012126191118333695997916756600408543226601665, 1231466375392538328694612130964071690021805034621412520944511481512279507297777, 2349648477640756485993251301906725341047132183382215279465438497793389660839109, 3099111297578477135779886526345743640311475435758824993734579420700333420488649, 1690664359964097576800556030074459924192324269317618913545738475596847587203311, 2054265318601641370989870371763207271922774837760458400854115401387162521953106, 1455042222594995300357946948940506176079473202745755539315170165422919837214987, 2737703901230648620119729675184516215498340228498747075833558529322741550448515, 1847489593766622016816587362489572976735325020357364005648973154291576153981323, 2920110538280520314747827961178189014514998204549518095761788407950255153847540, 2958268500396601269761423235959825847393704227293222157799335793319669060622825, 2345985542180934042839128223629154919627988311400089812717130377891745822434700, 2241014203060338070745691577758044738147586031133732693491353306115564095153519, 2870347637439131502185386213581689360274632975558359807782293631067782158330598, 1852634989733999093426874218169458195422557079581034231098762933704435006044887, 1862388256084067824430383892323053894335290341611286789184625594484340897283766, 2840894927901654909141739161619191856732681195736147467945179479863663606830039, 2402361678063385966682160132501003561188266731404508880379614200749592715079467, 1909915635563467518852047815113709884418039180699302428128451374644140267941130, 1658926823813195282852604374649678095399363082284848840092112243331543914063209, 3246219477051766010472120322020803795950363636590298249520227420314197051320180, 1917533171125817291632511547114825642767636167947706046118285318907308481349834, 1732529573776954215396883824592109278461465616296113719187362257221124050421297, 2814263652577009321513917897615787457764472311899563306422689175146400874504093, 2324993916740169682393708336019975558244948129067453744986371404324519261398643, 1503532043620487999925454219611892452064871526670005017321304231576559050996563, 1699050200327606267818057665406833317372501004260777756764072516881987595376191, 1472586941034140862204493262409660776093862810910579498650970236100393355808389, 2029713505933905447328187739983632511774919013593902578922419593584096403736957, 3225171083287582817199300358232903389164407358944150878502408641001476881116329, 2002739705085819696773726906427925703939222313302954137977322923239129980777347, 2977185366949025183951676661737118397967970692854945619333644262933483104988303, 2947173195366661114129705192992773919565837049152232827162046911232264006182254, 1754887252759358888503156014386972306424663301077620313505515454966154084372388, 1907405965907142420721338795834817757376940109196779186347981266665613826233212, 2015330364408646879738783215328681821738282240814572865785393505480211039640066, 2727893473289569333590201710166502128438404920873958155705550313677854946255891, 2285909249720592854317361245045521549583079701492605951982463479972983290870664, 1845999854724343976570027772639141428826241063271141835304228421100708367103569, 2363672791141786231097409217383362655763662840519306763732391294439966071060443, 2806936541429868513549845833892240163395528940507540978740415968116778710515102, 2697219364136050209859748029002897741198163283378001317797626490633055309788843, 2247184701442480681779249398438744369415499975031480815364948207694623966199387, 3231086019038147296220763915450735650568111238173220866389065299438632440751237, 1832276392976999556129354128814768583897218865356710089662798671135934832729329, 1917342661910522861149489645623396859753824081005762371765834098322307654497381, 1568017253990396537784321601698015449451817832281251660296025502053520561811812, 2941616922582905030134617392243899143088159369106475594003645096550740211691295, 2683368351117012950411179150631678778651588063084420106900764888746387687168222, 1778420058969534218383812868489034592227993121385588230014110347522765607535946, 1923764582860656292136186495617159929691221984386016458167256338158112818097098, 2656631653745695250048441951987799766681703378345466605375664608750138267094490, 1691142612544234157420807122078777197042131796182931240632840532974741207366554, 2507486372683720823405119393792056270780488181696931417677286972451364222324898, 2447484598394060182059875442220084043147995607049408859564736403691102277754703, 2595545091473159386760353940687413026143395465208155790570429164011691489970522, 2202408778718364092229680334582879965674953387559013630876726207304442759100950, 1434044264080765552621476110745390069274931289997241169288539930228352180841157, 1730963110434177443493191358945360130890936890712807539961534419929496768666853, 1814514698770987074692007368337406747271432147111293957177097586796743335366864, 2019810504329770248199484256164192365539847161241402784488318370955221358775583, 1956536334521214519139005513274352058427551797660335556789649011126122469394621, 1694989916853171959536869648489026282016518865526156952107205253569208427588802, 1770954866648012756428357246696467696128773908163230225537396522364937343241454, 2802996166579840936213980653413335387241497268210450195945009691876958816391301, 2644513999224447293556676912891272387168542381412380571251701553565002974065160, 2463113107479271232731543030008511295698209596496337911158126811719994524730804, 1334261391981801071990435527914252759589346447377833542541150596820934615355804, 2279003943573323534404267206493585478080811684601838324835345540797019580209881, 2120333317125642116907729078091221616419400615377299883141448350668604241449740, 1756076625856166082841036230119144332034421616895963015504269044505034917059399, 2207615431411605687205294013132826939107597873984017330939473488301182073661283, 3402307618965454186510075915629520371557316035524100232971772642879541133866581, 2257357821930382005896155137026800185487154395207884048113343615729127921819640, 1551825494936649699327478596078225912177508474254549041414169792254557027355217, 1365732972487952087912201569843410874792402112231916794732119488395781020203311, 1807495973197443225501042200464935032992636693133827521190080032536875399246452, 3066548428950611112157801870665061157137219961909600957576183226324708978020683, 1827692464083287200286079376258081926585195439691129818155557308275829855008347, 2177950758759980504779021451412567471817907630921840590750050627364220415245388, 2500408490068677256675931862459954402673338550184480122429756334963949542806122, 2134138149727797607166351547030249872845232722149691714081305131457344525454827, 2332811982231893523373224098520580507465485470638866226523073135090091836623660, 2230040524682264142564447094948233324847290581046122443235354731861026477584174, 2331535816974572878114135820359512753886735587931098018590107412165934055193524, 2865092118462007871887135714513386199315743927247622435497167687480635403743332]
The encryption script converts the flag into bits, and depending on whether the bit is 1 or 0, generates sums of different numbers. To get the flag, we must somehow differentiate between the two types of sums.
The encryption script defines a list of 64 prime numbers in the list Primes. If the flag bit is 1, then the sum is calculated using these primes like so:
def getPrimeSum(Primes):
res = 0
for i in range(64):
res += randbits(1)*Primes[i]
return res
The sum will consist of around half of the primes at random. This is a low density subset problem. Given the primes, and the result res, we can find out exactly which primes were used in the sum. To do this, we can utilize the CJLOSS solver from https://github.com/hyunsikjeong/LLL/tree/master/low-density-attack. The solver will find the list of random bits $b \in{0,1}$ and subsequently the prime numbers used in the sum. If the solver is not able to recover the list of bits, then res was generated with random bits instead of Primes.
So, by iterating over every element in the list out, we can attempt to solve the low density subset problem and determine whether the bit was 0 or 1, thus recovering the flag!
bitstring = ""
for T in output:
attack = CJLOSSAttack(primes, T)
subset = attack.solve() # returns None or a list
bitstring += "1" if subset else "0"
print(f"Iteration {len(bitstring)} / {len(output)}")
print(bytes.fromhex(f"{int(bitstring, 2):x}").decode())
And we get our flag:
ictf{dec1d3_my_fl4g_4nd_m9_b1ts_by_LLL_3ac4ed91}
class HighDensityException(Exception):
pass
# https://github.com/hyunsikjeong/LLL/tree/master/low-density-attack
class CJLOSSAttack:
def __init__(self, array, target_sum, try_on_high_density=False):
self.array = array
self.n = len(self.array)
self.target_sum = target_sum
self.density = self._calc_density()
self.try_on_high_density = try_on_high_density
def _calc_density(self):
return self.n / log(max(self.array), 2)
def _check_ans(self, ans):
calc_sum = sum(map(lambda x: x[0] * x[1], zip(self.array, ans)))
return self.target_sum == calc_sum
def solve(self):
if self.density >= 0.9408 and not self.try_on_high_density:
raise HighDensityException()
# 1. Initialize Lattice
L = Matrix(ZZ, self.n + 1, self.n + 1)
N = ceil(self.n ^ 0.5 / 2)
for i in range(self.n + 1):
for j in range(self.n + 1):
if j == self.n and i < self.n:
L[i, j] = 2 * N * self.array[i]
elif j == self.n:
L[i, j] = 2 * N * self.target_sum
elif i == j:
L[i, j] = 2
elif i == self.n:
L[i, j] = 1
else:
L[i, j] = 0
# 2. LLL!
B = L.LLL()
# 3. Find answer
for i in range(self.n + 1):
if B[i, self.n] != 0:
continue
if all(v == -1 or v == 1 for v in B[i][:self.n]):
ans = [ (-B[i, j] + 1) // 2 for j in range(self.n)]
if self._check_ans(ans):
return ans
# Failed to find answer
return None
primes = [72631919237287927717402325207066133372227433253296739177918376436148037178709, 113353610291242016590065192873217709952603000986249688822443880798128343484243, 61233066689578933084047067233486334593864627770848707460125612953653435525433, 77978495575166025609783168685853318929929985120608382285997233070243753385193, 80417172361794527546157297403719656639313353810617700273168888986350803004203, 93800524062346599265231876057535203946903026875666516269890416900099617168269, 97119169071341082676466697825381644482201126912248293435182129435216726548277, 90832133440133156989159367279306176825998079966947793083692222518066327714289, 111156153696251933778615089796986226303676502808517311473776412932401230476889, 96876329906549730024451384329729713704506332533562500650498800553860101511563, 86286584634698122955683719925475582532115192185246692159668723874434524279659, 65903466048748173224590166091273334517945429553166084561141664315404238203907, 80257644525014402296950785012990048502725806405293146360109821535239650852907, 58373867077613198457078300893876782065732447821855506855323213372595523275789, 70307897209099281479027830823136514151063615523489003132414884551468231257349, 111433863257040047657057024064485609580701784312490549902307306283243603655901, 88549800795939126019069388048803588676552691797977376332734685232332072164611, 86476382757716587211956370701024351863110631836242977802213434730486621965127, 82148112346979254967951647310613710507093341929507534256164313491746002586951, 106206517690710852498098306083737354679143918661360147773439327973136200544311, 68502501866658798329225146058538660769659746373219280578608307065801979206749, 60672358951835789704908924536327269229608581722109307581332432233259563717309, 70488882148348465045675146058646614599668994423589427829886289191979266309117, 64185058633455168148710182741821325813221678857870192808147347568058420273539, 91724253020456850774223452039983162340908864012274266250017725349818456783109, 71618237842953542929146771617756902175854017308219041983516624045533290148671, 75197023276518530624655228580159958392853075363846419358432337879052466834339, 93456081017428039908487992063415745064639093391962404368815742573133865752437, 79035499415501060554217818757856129296904865755428035853024745565351157316251, 59805093199483411592634594659959433594218194158384486422971106353915012766411, 111919408600330285952702240192537220923756596627204818717634835189071000322683, 75262644644049693251845454083264477166054642560145713740591274195595930738857, 63107291444793410808481539494468138648438940305354720490618782409929413465861, 100744061032607556872054413723197117826172064576093844455427086156246778889609, 69944098927494206498383429919111314297649499702904660445522561403747921262421, 113346972396001245314933795479549184611487155362285473220811161155716839719327, 74218688380879993148756363091257639519963552776768614571709238172311300379603, 62830315819802766439595083912661717804465372324778782249424277268108619546433, 103264161057748215037613232072468966385010093608920012110892839613159235177147, 111745284062876886448826120017412504536248941666698326600263722937179667853781, 102714811226433002942383499624250583152662882905940125612155350448548464659233, 70611222487436709133983543636965319174743496572075436130858190029811590943047, 99496810066970068259786437030853049423281070820256977962618890794465017825307, 71897979109619597470537943896799947425548512082291096317243737612115174228909, 104187436607185844120347890155645701189598399837540491971438994225658781627931, 62626312997351703501975166956924773510053238259969168260649056012070009346129, 113589663301872140232122306385311526651909749000264118788303971823137568335927, 61024064022365023006890119146557953676560021212017134989942000718839066371191, 67026055890389695260806295983401484022484207056900797118789120807500773539953, 86815148471309876492491436734517739148151702571685443764968941852499867942769, 71271715405688825890556685001974607477934703744599035510306362314132173537477, 99601448482842965306181001731134137098858054201123395666516878215267767241199, 113333426140866487376554632761477764435792220853166221631449357955587299983789, 72828024963517400487779049720080074711403344159975411686009397463831059644137, 95860312447047952148765088986164717003567500104677736410327958593198109354407, 80253883455538900223099283453614543220661664473671073544320428968033889527471, 103875607752185714512846589096341482991367292949192208298733200829187258671351, 62561055349714801292067442755895194201721853024266377169040217309869576245841, 73521338255369954464887173385770028245451155962437070627520638378004981137099, 62515182894498950668092010345264549688065719192878104686749339401615027858943, 75835218084739868375808444485023469969077788504144911291940699066842732630177, 59459793441768929943273834094267805463472005475964506059806584926516896170787, 105671365703942819551817230317199973226465615061686381878212933469608213104791, 78371883059256395153567659973332888704799612827628137474389521102815015551753]
output = [2819156815559098608935907144572220067802239722477811081781526014230815206143508, 2445222963144912170178987069682029265091235658826949940106147055263923553533629, 1903920232368917874988192424627324450235235658985487184886880478410683087792453, 2813221616898999319078173561719808991996933181529211199247718014749471761929473, 2415317622707046015771404986131301659380189613747377882523905789358464245805261, 2348523668852265507160083343621769660315154058706123058500525154384194150702687, 2507695532453621805796926889796960598878592310480558358405686855827420862837893, 1907141158421921299837854094999465484306927424258825549221658114723429318131800, 2996584876130431493975535586331439098020486704416414144352617491038777966622026, 2841914974487872424057865893430216860909258234230655793947295714954938560858141, 2117193585089230557096034014862868497434663348391069775085361601423465450067018, 1618663543487567888006759147344706501846991096986990711044152446484281789092728, 2051102508394283286598498094689699993985391855870591140003037895002327443967078, 2669090149346309750541187701674005414846285203668431896934154038082184277619487, 2821099205382051817689533851435604893781741191048584470901901981584399503252461, 1865954045962192539436077393382831106338177626620667766785969091756695991376972, 2834906719283370643135074456045826212415690516444993198590544038983805430549716, 3058345091889641880414874285391801133784878450057729860963845535706661712766583, 2653042015966370288730193574681974757937960717309316465953319052871479994033878, 1788584754515047633120809432697937475480742012061242716418696450961540809452374, 2778277203488613589832969148165909575833274521043706044098629995730733708920929, 2224400384415239578333692162811620743296388325332026485724809120569740438120124, 1972940461789417047227766171894128324311970620153289908353435148885058189880133, 1939948360526548190060387013721468591297090070359598090670159708826556568545839, 2818991601490249808138281165356864885716943957945691816617065879361927463800526, 2413553262118714460433349452670472062344099074014288014307335920153767804918120, 2413408800394460311364369792044980960839523519084508082211467486837363000827481, 1758845426962602600761866862339677239161642023927162827960263751844389125896820, 3233495076000044704300506440819729106639319294573782017725443419307932794713315, 2708355596539216171690103715674029628340788100952569621670228934102283487612686, 1536652946359811468561318815856138090872457809794218679329504600452203252121629, 2327165482735512477249691747760690742878483734660461193688694660880638031420606, 2550687440844783131751933234767946237202902423067833745512891069590063347516760, 2481177146135062825829716208896765976351123371323909570126219611506346709136544, 2976906326202019421699257927192517202347665946583804579082838347322272835955292, 2909029092339889063676233410972251606598736781501969698497611221586863427582444, 1798168243495600724582836684300392122016253713231480820900737994151692535621603, 2664817016106873773717597564360502202007571267185845325419923202388752047491200, 2546620205597503490932601602466124914531025221973697650652600774749315385983563, 1804691119541549731083265041619037469167936079860917628791885523586484670389517, 2993720664170395904909588354135052455143402349099705390593820631482848174273290, 2824574876463230873723626432904311683584749415106379741312890350093471390708956, 2178703956912849180607179809502047743725546451796949709962564121093430758925487, 2015984983682985181359500837085489870066576772548483853603306753416391570995652, 2825886744264603050250570710182276613361768413096941638852875242334626590323394, 1842366850389524393863483299415974342118431714168940010525357278313698104545686, 1890692228347751845977588240213788310482016364994323180433181094057080388377341, 1859570245693698000930635066477255198791798456916690502550935397773277654892786, 2125075140724245092030270985636432641827993478574472770023332164359192925667914, 2676755446455257799105999866711022387760341685507440939934907661068577868325690, 2127492815150892523930677422663426899493881960036299948563967902858352278756381, 2214414669786315022585169610350112451053743209985881827547493375134440269841335, 3287270883919895663649415935008492686272583218112557495688303747999607127347485, 1464885862912061941360124921607846166739201296269644683550488862315316621168915, 2509523466354990323289405019390879993989971624147206461818727132356459058566874, 1908179787903012986073536362508511663101907793909103292522128933290356486740831, 2756805796292724316578649442951105668045760292153123880799123727624430139834784, 2535051048687395125596454929207466830174234064994395507994578679918815348311204, 1803956415800944523172461231393963076071547374162301111338088773341404180366095, 1581427673457587965377040867880744385708196297129034872673417280313414009367552, 2210767855216344078808268682929389681422344682528936968055695504737022629851880, 2550877767452648921597688620286108961639250879503878114842193772033576204495050, 2756447633884757327126748105695942994431200035562027053510977246623093748665864, 1964779505858686501383673184089092976925707496895287157463367011777877630214817, 1711601297301999862146389758002427112641271299995210895971794979535949846981662, 2603372280135481877885014637230736101699219758925563658302680157251609514729763, 2667368415669419620483366371882587489517753424105473575306644788864390049717122, 2375381791051675212713652990248979670250212118711539078479113604716354841854844, 2493019084337584580000577145137347950270131374601477024044058401572003131171703, 2510272034609038717473097414524000178497639528965708166872787898622112571433878, 3376645650205558777740641900007720202740974970958294476802138375965090427473755, 1675454950441201753341148918023526478031944115873936771857166782930709781514176, 2295573600228045311698664671032537593950444762263429917312199003345978643927531, 2989232564205545757256184449992766612296977264754661974992606639914166850018847, 1868488082029996620995659067458996737428518781510041614792233972151493754021593, 1892797289282204998558656233944707165344792878835655367911040680710800217026842, 2387274259011256581212632921041457702119262115024449666940614377355894562863869, 1983881332955491024985326286718581476273785076433829348701324483746422111982812, 2062767935119595318038310126927517801164698007835687279422680554697212705483997, 1813426760548272486587501966021027363576238607043680794995756040734812014712643, 1562722510157661651420650013368819014831598048375840600129656685790447905077365, 2503673291651808329507024991940471465924677096391781913465384267653316557369694, 3062166182385308323163803924577776096950506098179031933671983253622594360543831, 1587591727372004646650383007276778974486973795582795614543330273924194355879822, 2124191961778288686577724783613312141001752051971190691410871783736806888118043, 2807161639821718296747775878877393924108396927585322529661889069690379681631831, 2733246030913567509280676058184785395993901538144190159673188530100162954586757, 2095734027587628478963707980384021314089446286378559071426863977096549124105443, 2988941018164239592895981954356834130422828926400913046430556106893050888967261, 1808937486427315645718998608467510156824996634701840345775870478636993074414998, 2703685611351166699001869484070817849345096649407749301012107683124291961022814, 3102613448307372159580295514146090155031564221004892924292098653939442448602987, 2177101615271107571142318136385894289129856690017106068932561385040022673438923, 2937151057349964713327739484700778587301119004787857337542161351225777024384191, 3284853954926625174312940587880762860995369578650383285440565102632766263047228, 1445263692951995462669671350436071269459804664046732803232667890225299584565948, 3098676865357167767681695819580978584292551422560325551761761261030493576490054, 2785990764438332102573798945869163846058964169046667905446760842139596358710096, 2286672499975498339110837294171463889505598069964900735273552787076262216195906, 2391874898075608542385911568726340514438277750074914316438113074664500269203548, 2605723731444632182682979422507162229453344556769061654841867236618061760791325, 1704836746065631894082906921469595231141025078554131926066714879810005676323751, 2268547330405383390451485215576699310201492241110811312277295403794298328525318, 2257279690119315586453943222353936242022588071540577167031856674546385664274173, 2872612890312518257758936879530195946285789167890762413291543959195362374746469, 2782503101773215051391891616156069531578324959687740312811009067332251738718639, 2138140684559184701106744969820800303534456927075159680357462604985136618973448, 3095278460762504782170722834315395471811818415470674607477221955419939863412688, 1918147505022892323887450400533906049794530447772075631502966582700819074987318, 1707010156387988967567351309817287890962086105434244078370980148566691847226989, 2314881420429035304174113419210131391725806719440675908882594861083902503989894, 1747310534609110545360894267130302582086449810852064052514438793880321649681103, 3080886800074193535767113381895308001287890199225312650567732780605043357281585, 1703302394447278966593359250968585558627874162942204836180727596194447436704731, 2669959616748655909038072864148442141347343478193254233924937012286825458693418, 2678347981660125571899295349441122811861081559641451673761407195954761042620360, 2991379536309166201033224610863206913612841270474721698767515583673314564634450, 2523223616403538242735730838547058862626362247959528229773500469162355596137501, 2642334249408957788795981926934456200612035825182578292078882855617370677855476, 1569264447503315408491941272069637567187075617506995254256292388264423968802988, 2882151918273286344356356582994818011404936455027402382189340156913800330427975, 2158967947928376114000914445674913628201764160381348927457320635619197102958046, 2051737874569931765249515775461268812640666956809870235551742670881277489362727, 1763323742103061035663123542430905313899541445815905288785170098209590602129239, 2713986379520959678928522767197552952345350348987283755564726696384571034845768, 2537378599555526856829858853624086645778822512223537633689220391093349190349778, 1559241246373570128428798700624771661010342250781098062213106558536948558050766, 2279150628340411933639371451926359538099865357708465543071800823000587477815011, 2898997193141068749321572525457620525323957690056983345387036999017795349699409, 2522226015585642028656627937913370376228450166094635794231237529375655653354731, 1976905875820155215040299709744110576065821433679615259775310771962543694656698, 3146904959601041464677308813467361006584585805682305551431275878689319837940924, 2693972707687221507896250578017189021477213697938899249523534331595305491495324, 1624327598106729094885115301581437685380703813627081789404977021142280698320107, 1953514564966249010069920346168045652870850335033365089388414276370477434371002, 1626888973038960042489813971944630122654048243552668114260339025510208408311822, 1691170441751836250949367136389943978609695857804909953940716207113664903533044, 2872352457635317352383489529000387930132790666173838033868080090425309904205463, 2863893510770920872155566640788223513715980556898590207492297802804734220666273, 1664325124883579998946067059421408604232610753151100601467802141679596987515744, 3241231581569478941168907165945341550977831562153048119560311010399685701948601, 1361807005173976916825978829400623371016110290335271142789044365351489158265785, 1406627349406527471168668282696809465701018718681981074249372097245594123964851, 1971525597164878946966277125289812240116013457995908459722202952295120967951958, 2786911678726247421699703800762265831545443241798747206478605511107149362330097, 2439508492564866839705294296041842112712325553837677868579211795105087869136093, 2059191048467669923967691687228577391906624742849738642011719916045439079304823, 1570106312941323008471547510823923094983111141481917147880596218618909287869316, 2122987705390617331128483361876664852958813888207310728315947431193637092615610, 2801489830287263060085120056123289367371498556308329538059159707855810575200325, 2603504643744222599357535179213179516289477923306029799301160287585889511538186, 1579559950022451616002666575318998221718261186164798108063013638204271323515426, 2946959687392272154774154223307645704738122794108855599681623985844195753004336, 1692770221755889837201538695387588277166659470005431078018491728102054788606405, 2659449088987888852195471961116502165033707350474142851843714185859896260654058, 3505646321172760059446810399769341926141272269356767693575285534015133195241233, 2530481419181774953758830811170792749065265404043551952628317101074384012856365, 2712291448546463050414385318858256938602633632117389382231541762951484136569160, 2771788380581020235551999360102117509781311204513808674596945948863545438935552, 1955826919431026980944761018180907821649592615023066213634119373120418173949204, 2233584311947835760483846096048038712598649182856770677618031551939193923070629, 3394595068511229452615822692260046682896960654048194476745024879264499379417364, 2712573898841928347986369197314358548875252769951810734215760791710091814581815, 1748981602423073911431838108063086650192315739500168302252222265177547421664563, 2918701578242467135076226389338480065735119480562687109522929797564227072493184, 2164542802657835484124827216032688263572786614573372525249065148400873809020470, 1135304887972847560145538866404958097776596359071002711002875129077851779982891, 2205584540603634087173783390627256443719846063793628767797341432227402910992158, 2690352932777477095639383802001157556275154650146494280789592444767406723210088, 2303944374984763927616623281091903699148030217974972202655946341959198480366990, 1826879964307133264320563754533689815425723980821932135389272772715666899003374, 2411535830583065044709148037012533536301300387611929837028371177053977732254183, 3102248701716368945194959238072315916896617832833372561718927136392499451559578, 2659059708824611624428432407423533442925665544505963263289772494964288235307875, 2122091574300829544940359499145373746146266675687307129711907050808965471122010, 1700916444187293837558906660368523799466101955714678788331652720755325956184538, 2567718060732115690755878753641406930783934887601526519050886636729753186426791, 1952081132214229966862614041338565988918704651475436080348360529823670476859620, 1660215762591901715725992379790262398087569715838733505603236713521769589358820, 1719279125595280317066033690110562638515279430979107832569413806636508635211996, 3150257746796819704620980918552950504464974368953784237516693028734092071089047, 1533483464980797817093734747462583125027126533889191512411074224355529845622071, 2488961034310705334758521978741509630299502434569628208806014299768156795682257, 1949296862369855738672364903506625258331673226248095354317656816116053344797835, 3314180997278886324171475580120649860821510669127198863042562159001687994942122, 1835912431730828052486567697931843664151353173587570710495449691984382497927315, 2490573473773652707889662396932059726458725983603386101684045752109912066544351, 2034391449976822309453187815141830984379516892947671482205865823880790979367955, 2904021828859719234045989645729651328223671397095849600652399072239977584752185, 2898092590337486358630458611863555173232553156056707848156576249041471235470768, 3020050896501407718070202328514173978695297814931297739049640810470505425773745, 1162913829573891584933621423487787462781528876246539914934653605693493109367743, 2411509537509594942434869563398255803405247485496687541554728239521209563719728, 3240460093945381326170175021314548622274008446302186694162254988437882522956789, 2042576958259566656441090421986717161687799145769915833228519921746477531448760, 2553411758242921025239995694953337401215433895789864555503864382953439429213802, 2820514264957484223884788232888402572082052875947845405781652420449215392785603, 2641370591795997642215472507781953866796675755685964449326951672513035331652719, 2823035270072193806363721364627815545328685374442891399776824815269510767922152, 1989373778720753497822506435334497629024665265080539577357802530369873476548739, 1862386424241098951111754027338499846132635633222316642962968740112589660520830, 2976767130013568871382359613949325813684341929036309541118080812240632837951917, 2032079799183763407608429385442348826534633217836159747315522261005324747502541, 2708285103915655469463038547427063010568545575090977468837676375353975489314033, 1763806042471114758817803518721264989399707893537069108192481105750144308762714, 1937326669619940914067700437225091575824756751300418686192482170396808556973038, 2435703549632943593049899499355898299013949956078689678733600487087852297494155, 1564269996471702815616616340843697420448380748563779822431189073561802077443811, 2456980081971515876372636881680154805873081926372199873790185654198943312487861, 2114228222599900470093715633907929439859036580370529231708091911394217318192346, 2412504259980354806049559188591922758532822094151137644379211660889448844429578, 2635073202673673572264139459896284480350454830352313451411706615748140392229736, 2725320685400498493268546434049721871475577064325227566368156917361595597089351, 3037867883571431356133279924916838430904119854900038874159214526715272191199734, 2824971163661740859800864424701755168512099695296428827528594616947609789856313, 1719312755020161540743541987056216628179475180251054784014251838005404915359190, 3012080368518302834546286001958441602695677482755944367912995252821821409322630, 2595410720707289052259292382365869693173486839668185767458178220761996549540776, 1730386135469589080821808335571789810133070354002257675548380927002483585203525, 2183488429559972081266293580805381776596408303103494625441288200546469064198052, 1586663745637750938560919751995751853774793809756290411350824056092900626767581, 2633560016633693373820917408699356704371120444974417409768038767304741258416882, 1588266791029338678483285861004896440056893325470901832575017393368494381844313, 2062140763508547310649316830659374267702516490495399524838782204228464817557303, 2210631662045486660045329182773925615869393461089725622733280699922614662573188, 2459357704199420786919294385229487410232263583838342283632925369162881135458784, 2613643032209168797222243130152765007369922353402246208144392804402308111491213, 1710948753142088971871638997633063611816787381413888582644218262719506545790814, 2370888885585089451526475579030868634013098608165933127887831074072488486211027, 1874802131193521153356429186932124966125006368474096875577533362925609490873675, 2257490811907741146287835975463592107772672753660997437720973452168570067018183, 2027396376118176181554556587461857799175262388659116515495331190904871780900168, 2629203400695349534340609904454384114924188013467883308551455289883598277506576, 2890142848965203803657678020364632618710915881162439911156088498054480848444284, 2219081521671625674270988735444011710759687035389885997488568461190702712665391, 2380376764714634310626713438415734647767006799419143228948264493667246616324693, 2814638103849795047350222194926779177051843856327710877892295181020329663696490, 2047838076416771508199337081863868486021562878681029339974246205098649513457324, 1784932180402383121530422581359653305472252436816341976330551492781428029261514, 1941527319325036462639722135771653972446143884927214478817515634545849137431669, 2907563421094345848181477200768863573314924396229466732653561249857033838608028, 3000337261597585046467954498628106745718605542524330400603607525806097908557040, 2786351435794517058372407045515681838202163268432832568806234013222378647734555, 1836092084933347325356728587763659299616726483980078801819666587432774417206073, 1574796707547605480163763402663498447991988000366600032231056878314794495735406, 2353612553114861608109605098910218987289338082728729053511317177449593301899294, 2248699009001439455571494271407476531250809026878799237531708891383695128771122, 2417476639863872938259290255198814812522944882305274702168279778861529389946164, 2971783285485191513675004761256201878142447913010923130203347305001342064598990, 2142943014519370915558067112669312116295755777127417301618377823907694765946338, 2661527100047693021718564373867938790031132276013799786506265512546563727003637, 2789161914059543582404778858005723463894421641256844424769515176678453044603337, 3040014096172959690905204596262839182154829748346494437618210463868135852399494, 2635917392114338296279286936931727170162216403550460752678274156631579609014634, 2739029817120645069226715038276509821027853672448467093767065178330079288792182, 1484738110125237820910555901588888998435780560979615982696803082959376104709161, 2372999157870072620027636129336264510265625974962517451119668258432432453459291, 2455687222461827602660206191412397063350581337238480459622011027481646403606246, 1876432865628323024983726722907298656929294958135555012103492960934104600220219, 1307841776873030596697898086313556358231717270837313632583014388160388520957206, 1930461711710915408769618026875738822780815121368520129692337068401427296313373, 3325280034101518748159577481976984799447956248994089550885201924665697013425938, 2141730641878301259755102172773233369139906794041664225968362000101121750584861, 1375656209370479485060378259057252116555118144818855052445166926233837043706214, 2977769163020142792135228863060463623818385890145164352689707153311169566103001, 2002834314014321054187636141249638087852858776899333125132657509142700920915899, 2851322935231676704267708179361053286697597203152531856687447152874802460360864, 2992147055296731103287336167512602309601875655087942903948613982271058288601610, 1726152188820994697022282207330085869001951550140404285145456533691648598100569, 1888604908855715245619198652572645357831264155960901438791523139267142437922964, 2352448954998759084316420067380678866770050286925503771493227478020356378487607, 2048308642686539346926409497753971725904482476842642143130646956853793335448162, 2501794434297131030946196089001233568215948580707283625912119735439908255378216, 1903581457860725006292290733111833468722059955064722300000621986075260984730890, 3091137366193643814130757614246951323703457976373978819948176036606067628695033, 2320974233653240015647239860333344772512164840786841438935137525814103134556389, 2685814581994945080754008326997111441187184408176728102326696887317673828436881, 2000735932503291577967925242471844116928558854574240520790749980890194978580328, 2420029456477865293042005101867311660978152293635853664008446797812937597305509, 2129555161426105317333875952515114347501476208979636012506937915200909157703983, 2582947141522611573263255922392440642592155092034175475551805098992649126512502, 2007387202205259405202080331409071622936010454228446167685562218123845168427194, 1555346362119608126365015153381797593304002606210833679794143799398649488008709, 2627310074157008615051031552873690677995763263775766597112117219178356232254138, 2614870511241382676735961019792996302007146563530003061044256637662310198888354, 1835517951630184004031358550557037074114640173264557591588255546633305636557964, 2191360283419900545159044662092406127521650045451596375234153785353085173024074, 1633587445499810699103350031108401299972286118612069333913054471891868634481981, 2244506220430518115591858883493205895321869570070556445420237854928896037980916, 1701933270297668456594030101250077900332487913784571880972700238355040675454480, 2073349787428363296079890283770992319911798913918743690389931150271611080940175, 2554199147351498854198124357914578384080971977075570829246726644622890103967478, 2869859353109108769884032621260179038333321889811803968916073817470951304600426, 2163535859846850182293040680340377227423216011265031881108965948829531859829146, 2127374883010589876012860539719535092731861273867713812127079127126859754504360, 1938864159337265849599773369625058562249980220372090673684508081397701999600056, 2757117073936544413482459237210873364734485018520440516659943461070434895539784, 2173928418091053227417706702891687012126191118333695997916756600408543226601665, 1231466375392538328694612130964071690021805034621412520944511481512279507297777, 2349648477640756485993251301906725341047132183382215279465438497793389660839109, 3099111297578477135779886526345743640311475435758824993734579420700333420488649, 1690664359964097576800556030074459924192324269317618913545738475596847587203311, 2054265318601641370989870371763207271922774837760458400854115401387162521953106, 1455042222594995300357946948940506176079473202745755539315170165422919837214987, 2737703901230648620119729675184516215498340228498747075833558529322741550448515, 1847489593766622016816587362489572976735325020357364005648973154291576153981323, 2920110538280520314747827961178189014514998204549518095761788407950255153847540, 2958268500396601269761423235959825847393704227293222157799335793319669060622825, 2345985542180934042839128223629154919627988311400089812717130377891745822434700, 2241014203060338070745691577758044738147586031133732693491353306115564095153519, 2870347637439131502185386213581689360274632975558359807782293631067782158330598, 1852634989733999093426874218169458195422557079581034231098762933704435006044887, 1862388256084067824430383892323053894335290341611286789184625594484340897283766, 2840894927901654909141739161619191856732681195736147467945179479863663606830039, 2402361678063385966682160132501003561188266731404508880379614200749592715079467, 1909915635563467518852047815113709884418039180699302428128451374644140267941130, 1658926823813195282852604374649678095399363082284848840092112243331543914063209, 3246219477051766010472120322020803795950363636590298249520227420314197051320180, 1917533171125817291632511547114825642767636167947706046118285318907308481349834, 1732529573776954215396883824592109278461465616296113719187362257221124050421297, 2814263652577009321513917897615787457764472311899563306422689175146400874504093, 2324993916740169682393708336019975558244948129067453744986371404324519261398643, 1503532043620487999925454219611892452064871526670005017321304231576559050996563, 1699050200327606267818057665406833317372501004260777756764072516881987595376191, 1472586941034140862204493262409660776093862810910579498650970236100393355808389, 2029713505933905447328187739983632511774919013593902578922419593584096403736957, 3225171083287582817199300358232903389164407358944150878502408641001476881116329, 2002739705085819696773726906427925703939222313302954137977322923239129980777347, 2977185366949025183951676661737118397967970692854945619333644262933483104988303, 2947173195366661114129705192992773919565837049152232827162046911232264006182254, 1754887252759358888503156014386972306424663301077620313505515454966154084372388, 1907405965907142420721338795834817757376940109196779186347981266665613826233212, 2015330364408646879738783215328681821738282240814572865785393505480211039640066, 2727893473289569333590201710166502128438404920873958155705550313677854946255891, 2285909249720592854317361245045521549583079701492605951982463479972983290870664, 1845999854724343976570027772639141428826241063271141835304228421100708367103569, 2363672791141786231097409217383362655763662840519306763732391294439966071060443, 2806936541429868513549845833892240163395528940507540978740415968116778710515102, 2697219364136050209859748029002897741198163283378001317797626490633055309788843, 2247184701442480681779249398438744369415499975031480815364948207694623966199387, 3231086019038147296220763915450735650568111238173220866389065299438632440751237, 1832276392976999556129354128814768583897218865356710089662798671135934832729329, 1917342661910522861149489645623396859753824081005762371765834098322307654497381, 1568017253990396537784321601698015449451817832281251660296025502053520561811812, 2941616922582905030134617392243899143088159369106475594003645096550740211691295, 2683368351117012950411179150631678778651588063084420106900764888746387687168222, 1778420058969534218383812868489034592227993121385588230014110347522765607535946, 1923764582860656292136186495617159929691221984386016458167256338158112818097098, 2656631653745695250048441951987799766681703378345466605375664608750138267094490, 1691142612544234157420807122078777197042131796182931240632840532974741207366554, 2507486372683720823405119393792056270780488181696931417677286972451364222324898, 2447484598394060182059875442220084043147995607049408859564736403691102277754703, 2595545091473159386760353940687413026143395465208155790570429164011691489970522, 2202408778718364092229680334582879965674953387559013630876726207304442759100950, 1434044264080765552621476110745390069274931289997241169288539930228352180841157, 1730963110434177443493191358945360130890936890712807539961534419929496768666853, 1814514698770987074692007368337406747271432147111293957177097586796743335366864, 2019810504329770248199484256164192365539847161241402784488318370955221358775583, 1956536334521214519139005513274352058427551797660335556789649011126122469394621, 1694989916853171959536869648489026282016518865526156952107205253569208427588802, 1770954866648012756428357246696467696128773908163230225537396522364937343241454, 2802996166579840936213980653413335387241497268210450195945009691876958816391301, 2644513999224447293556676912891272387168542381412380571251701553565002974065160, 2463113107479271232731543030008511295698209596496337911158126811719994524730804, 1334261391981801071990435527914252759589346447377833542541150596820934615355804, 2279003943573323534404267206493585478080811684601838324835345540797019580209881, 2120333317125642116907729078091221616419400615377299883141448350668604241449740, 1756076625856166082841036230119144332034421616895963015504269044505034917059399, 2207615431411605687205294013132826939107597873984017330939473488301182073661283, 3402307618965454186510075915629520371557316035524100232971772642879541133866581, 2257357821930382005896155137026800185487154395207884048113343615729127921819640, 1551825494936649699327478596078225912177508474254549041414169792254557027355217, 1365732972487952087912201569843410874792402112231916794732119488395781020203311, 1807495973197443225501042200464935032992636693133827521190080032536875399246452, 3066548428950611112157801870665061157137219961909600957576183226324708978020683, 1827692464083287200286079376258081926585195439691129818155557308275829855008347, 2177950758759980504779021451412567471817907630921840590750050627364220415245388, 2500408490068677256675931862459954402673338550184480122429756334963949542806122, 2134138149727797607166351547030249872845232722149691714081305131457344525454827, 2332811982231893523373224098520580507465485470638866226523073135090091836623660, 2230040524682264142564447094948233324847290581046122443235354731861026477584174, 2331535816974572878114135820359512753886735587931098018590107412165934055193524, 2865092118462007871887135714513386199315743927247622435497167687480635403743332]
bitstring = ""
for T in output:
attack = CJLOSSAttack(primes, T)
subset = attack.solve() # returns None or a list
bitstring += "1" if subset else "0"
print(f"Iteration {len(bitstring)} / {len(output)}")
print(bytes.fromhex(f"{int(bitstring, 2):x}").decode())
# ictf{dec1d3_my_fl4g_4nd_m9_b1ts_by_LLL_3ac4ed91}