CryptoCTF 2025

Giải lại các chall trong giải CryptoCTF 2025
Xem các chall tại đây Github

Welcome

Welcome!

We just learned Base64, so we hid half the flag with it. Decoding is optional… if you like flags!

CCTF{w3lc0m3_T0_7h3_m4dh0u5e_aDR2M180X1M0bjE3eV81QW5kdzFjaCF9

Bài sanity check vui vẻ, phần sau của flag sau khi decode base64 sẽ là h4v3_4_S4n17y_5Andw1ch!}

Vinad

Vinad

Vinad’s ‘random’ keys are as unpredictable as a cat. Poke its weak spots, steal the flag—chaos included!

Source code của bài:

#!/usr/bin/env python3
 
from Crypto.Util.number import *
from flag import flag
 
def parinad(n):
	return bin(n)[2:].count('1') % 2
 
def vinad(x, R):
	return int(''.join(str(parinad(x ^ r)) for r in R), 2)
 
def genkey(nbit):
	while True:
		R = [getRandomNBitInteger(nbit) for _ in range(nbit)]
		r = getRandomNBitInteger(nbit)
		p, q = vinad(r, R), getPrime(nbit)
		if isPrime(p):
			e = vinad(r + 0x10001, R)
			if GCD(e, (p - 1) * (q - 1)) == 1:
				return (e, R, p * q), (p, q)
 
def encrypt(message, pubkey):
	e, R, n = pubkey
	return pow(message + sum(R), e, n)
 
nbit = 512
pubkey, _ = genkey(nbit)
m = bytes_to_long(flag)
assert m < pubkey[2]
c = encrypt(m, pubkey)
 
print(f'R = {pubkey[1]}')
print(f'n = {pubkey[2]}')
print(f'c = {c}')

output.txt

R = [9765507689557698353272499404376055006893114870722334943829066982323649854068670692016090678182002045854934465496255639568419408057967403077442935343626825, 11708898940537916806152001023915219039254376113964318646846468851082862998474307181449263359025364805731589596633658749151565367764957039398127836183355773, 12669179058860264531287509749033656639714912455141413836571455208331612009073261317846891011360139750565008606283828854617732022759044690597726610423842306, 8077978446545940752393539454138471756479629349687913903696824137482277851253389433983596973344259642939665632837117616919395672787907082418194190775089107, 8614110157141031165356634580939732362388616840839234150391192983993712015062756021521314005957472425836289494798892173997264892789412148966197694660703117, 11200422887640018916451068227417366461911524989297558606490635349305963739100610033950044371242333111323214224770762216521059100303944952985746475079748611, 13344967541918888350493621536064107613996935355929459462556969193217066151051813141305753196562646036951018522336875527234616765944842322571767325716825932, 11981765598933934215777031359217259391491032718492218537362638328430450533079579349217361987426931674053079751146155733914706189885662702132824987662710697, 8336735961875398528252663816688783160531281752736009834879166463079240506155985556972742196248747367208401431514654182921869396379563488799913364346952188, 11959349876622190886381031277440051157488649895018773836776860622450715877546788197836334577239868529908410947178119188739343681671610436055640349901450266, 8713800234391515391137777364808424262191583263090427510150907224331911893244284936334728098164518514295695826664947408590786555500906470663644484392359673, 11134180574585062013117510768632111383234906916157000172365317117842125169271157531902453528431835402606642971428041371920695019876139310840748751494664571, 10672652517826163337002387782583208795478924753693432954564907660500242525112627833939183341101880246958783456221484007058769382926806521545508340259928911, 11052213791816507764521786707929984417724955398072552720917821300699970235403878647749425640958128559421388850210410847786205471678928314136593027891348657, 10997086355911954357285260863710321076625143089230057073701515340391578579472483962825050765697366816433033684300108324869249390812625345787203357375505645, 9259378462951400827773760047163574216481945591448733806403566359893004965921114269192616272868594836774054422407031376231983024320153921112329634243718058, 12670744942332745741628454097348015719255102170334721862294873067773086176370793696694157936759535644768697193682907110309877985352047076219254412266801483, 9940286533203675368847536532435289050978071003936295870885728466328400976797641608266543590592895588496931031974175109736555507329484924328396111439724101, 11874878410563715804328962342618410397887694391575270407099579577083854140823236269744127719831500518874126854718998860005377805750045959302356274666444521, 8760902842013892706202918426280596679209881828540131076347737649813986635151072512142894706393493465980197591630117120522186656315995109507650394998210835, 10882824053261945770697289864571552333702327619124167249216771538330336539851262692345403606791233141421921281129193644611023781181459820500206304553125290, 7454599811028934726924349797748754018494352827091759081718298681594368701885229607205368227063104674468619223989778407520768628711709924139840762344798508, 7673408571977803421923725270855779960077566424605198139315219837777107190125682591505651885807015887026877246652670206275086484391174466036194759233085461, 9764314620056331134735434109242224517090029667187245516734910300002131687456666885365595362823545736444926455962200022785336120060535075113911216882084652, 8000829143730379818306183173407774208535860577462923063727114159812436011014859941613866952333492839326813915853698689744314644064537369333691286985962161, 10195654161507924191224577052901150820643542194442215265310936076748754918495242252869124423389484872616131103146109347861246679891685574723547330988418683, 10744712041578349312446779630758730960762975325295669941382941777740737465530944400680211911683841701220372873919233692500372828484253039766134982834330698, 9342132294080944564417767794248346772584524622651203468430082388878186318567314924340811893870840389084281785786677364979532873815510047265428358334142244, 9968491906009711132674426520143234556718655501605743603680404620829540785128780325250260224975409994847610820575637032941851077120448225211115007403023533, 8054167053434586385924426434078323848045668917887659074083356936388623053762507651545016267570347764526827603298257430638961704127444872505939903435292845, 11268073099594638989751385384877880607150664405478249235172623883821745152743738963164324090215811111506421885956169389537453098325923311680866531493037382, 13154007080520176004368515670173789443674181836876040273043121665621334385264602612581965665962115690005120079389383201473214229037752365307042263031968890, 7239152673967717720245958533547337919184552072534618290405473820376926487623570609775052709639113634342053313806770772573845859921208408832610007766284165, 7317004587665687405477759032181045474821663897627906437438772262468232586371432571893376993062848683255953572514706228789047872166666975513023714510798998, 7946751767847232148716608741180129679429009333451629867228126367660849025603350862478105828706577026380588532952378913179187924354273339200301415844992779, 12139348145684697735346696332867125959862788480821836851533177971377538275591402189884596118021878953930615037428724755806958033899027001615774290985059325, 8375342021368890530398936923370840532620637174398438384389080604938594945412965944720181956194963153622036065851894393757963923852339067182029939051964345, 7095685895077802513284823877460279835398123254012827253107720758619664197288048475028171880339939415945977650417326843709550050783621013665155038176094817, 12759538435491280914283948396202602795181080560934308784041234028703811119465363271556177715649425027399313630038242152814490671994726555961980519180821927, 11406103055719349101611473496401686906969258469100336782400837979833356291165196935115057281367332707583672394025586572405831445446772033522538830045119291, 6706957824608617904015230182926416876278050606981055838523060222851342039773499255262676120600934486993694037559110578986294935400117663539156558098270549, 8116681431977905525475261664164017064691417230047121658582699342266461415653830852688333429446620736350894839717238921158699630205786597625618056603941061, 13363655721358738378731925201803521982419994743792921421625745475936619369221449151636682138046595402237297673762509119862775992703320581819811466502956112, 7243461905671561223149044115899634428754067764871766350134852603725986710755312941216029623289034828639617414602688224694122502200197004661641528090356132, 7629897642506794216614822180757330840924585397754965259163764398977377296905023207670266813421348572378172673483308623256337292671233386999640546324745302, 11230186414421152421513485242505246798739025958862376635412751985784872171924486231671606405602029974473193107834270702242422630959052050906605386144671051, 7894246900051463259721204728456954122636442572146670079460099627162900155262918361027044755175359466173378141817737471886793690513570443130679935390926691, 10850679393815069823632306808515864071809629105311315015335985146130923739506002923002122350244641953434640665020159203453861930607038231337991066697065356, 12992328181815140376281384857000810530067703511373906320617748662010274822711360919808694932595810258760221942667078930849436891973957626919026708281222426, 12198730689009751986943778352077030768217204171074610573674148163372883006343183374060073511145692102299087970024432850325204189616250341710141607770516295, 10938261163018397220835941049954393853469419471549747759410469046282567598498145860311779109293721189456622067345991101792462701377592580887083696745190087, 12838262034378083737003873818397431640361522802784821845915940876640465197245705221543204077277785657227214047004681556349041437821384106381792976465824189, 7978352578642251592158857639533124529882260946078985083556853653692206800423348549724488795887790590940438191427090819896668865271868294551636203946837107, 9028992793088939343924906597535164127357847405873889408828160346496143790660326298485824352129111562795442293087312710240272693277461052147688390357713182, 9768860913741139581325371467147936924011801217538853298781734814111902492066419420014075780562575666622645565006188390747787433042996969300778215149601605, 13184044500466062368350979184555872939107478147449313021987665509414651659752718034265510537469260204575678632960233408297584457726441380810979992507824574, 8752281370594154967384140828317540591734409600988921254294534398309748528857807357795787545437641686810967016793514964864139891993118929426312759472698197, 13210260993687275837322876872888968304958366670930346384532934546496324912353821635981533617461904375785973194445804856055709294176935266175669129542975935, 9954542178404071015896308465711071080142350321244669612247010468448346748225709591869448898752052479099022911022376226304527677233864899726848727925336843, 9112588304976137706747112647488676859266706013410076656230239026800919969369046417932889837040560420975435832980361538366365667658893637054328008408333949, 12884487968232549194059195082712078172641939283528748103914493441347590376730449690580858203539788436175924156421657226777775130860560315967413859055503981, 11509057645066914427289705951422592296041372429030059922430226007431746284715920510172262482806158634950041986103583373545279494426692437098692102371257907, 9248822754928977323183746401001258444472691376682974416293350711457913420000562889571138259309098308682997109825580833597872892771022457569873916157557814, 12885940949471392502219181524250678591866698575912075164277895891766259512464073582202925232906018128556643078966469162576944638680160783546054033618266142, 11840029945413806918334797107218192110777612320642910467490574362320745770602510070067121264495972919653580153426684389943375557917669937300915181440473471, 10272057427532725454858619263466714735756223355884246857311194445165799880349500551408481338659496041772428414145843645652222695497763380767438612207360906, 6837020171906240847366641882180281366824917749082601777947757798030803083820673536126384955465809995834057289723048235231695942695813575504259615636055305, 8414736429107930724145866329896351996015637364827507939128231758964506091833977854969435354848806484625824968753314295805107335028313876568517618595955262, 7036583608551513269952191589210097832117741779015734497819532869013916774402641657487905596151450314190976955200157147794878261943144572511683071639340563, 9870478073613448959961953485710429260223154322560940037363495766377549524310476677553057848450934294590971816070047657003093033306613391840887078862801180, 9555407628717634361769840012860763782045171659753390030492327009234833599292311539946925193352869562150747926131792144262092348158188095203507519282204000, 13161821201149406552150919409908814415654308810979625364375877878254852222350455931324438395584525455493261178329182536281735602420761616257755968522526127, 11893883846150249843787844760529354700146564650373127426202316169666580865358814385693036948793756415282175134172795808098211015993009699759206823866088742, 11487409013300454931924058458397177139692956773765621582554012913968674352491865163559050488488889931420749726937086547894145360244288999792652643355501630, 10387943868642399206997199989123083120402320291774432587392665047008994672785101380387218209318433947459671207515604137462743253807816887099488549448766752, 13113974281506974205247126068187404561669221199113812084857688138227237562335149959740390980232959702517025035930292148886488885236520441332212367352421658, 7678016973403436757776995982143165195003351095618687850088557225481639635493120114400487695578598785020036584662567650118757926742525024540438388198793532, 11622880867938002272577419231823717509597570623966033131647695903968319409141430814961943749532131835795261744625896484841740929512525484170588028828293598, 9879545854516077312061995106220044355028565372709213786019194155310082954687354117718642447622455157041078228595029003075469354442736572922485500451941868, 8350428329394096735310291738341802337508925156568119723741360892344140985426548661285940669073224843411519783997898446793848225695348757748244750038826475, 9086908792595138685010581450530598772387472411166215226514075533062000676155655844756351511537748357548755488117365449617271454440963550324962705863268191, 10410601197119394605087070480956858510743706576301921440112473270639088056389512135121568505177657881343246863535192747539285808721608095778373889442856307, 7427537786640889266784010314713705847672563859470080089844747722842884178117241254241025568739322725772634681490115276400760639331514545436331358587750970, 9725837727464677771077352206673204310349967514007452305994495620460715440442993354336316016293262331721486272177144943182499787346830248099750243147242406, 11293316634906133765994628450779498325572673198382435856510557904404924016092155099217931876346246090552707982356227728153432443319003208339701356505034466, 9489698169771902760435745829962364123625264318278565321735635780495348059911563898077946904117620467600465906221186719840346283265168392092131320218277927, 9433283685974905541807101637731784546715594207808340043266960973839060426096953397589916880000499191077327869095742620353620753285482839176920046200618506, 13216274641224736138778027310461611185439621603528952109057678151714987446162309842836057168154632271690621412429726913494812552000270650622518002579865208, 9793247891964561873966433050421361780432553469801579174679539096647732997830273186564083077167764683390763585088187536602478281559354862438471647609796541, 8580357715414281452834106803713281903138736880866705495068206955478338197722287666322146966105585699736683690466652182920862048551294020838187884222713066, 8942036944437019063411928885347564748746426482858562156168232545467106387944391401324234735630809732051918684088302793112556103158394538727150800171234277, 10011534459963216352518703187678043231895177081893644289106595321290144914645189012479659201778174849972270940673079189269766829891054515972395084065294015, 10683829848241168541901616024469708100123068585034590613832469345416807549399760082661889289593815828768139082137084602607807516600486955815369469996976395, 10386501316881417444395407255465841712188966269096137518735554034979890820146879973897982301466069300684506250245706025943718179915802110916400247168928907, 8052450922302657747513660649563435988929390497908013343552505784932408572188769780782788185694360021072126585987292027481523762992179546777812940506635202, 12899781378027930134142931257425978661419945900627912428328016239588522747314946166666688534113379817551021614583860834214407610962039401114345068337017275, 7057995933615737927720038278416039610983955887271393484907028459898433158102663263986499448900862248806340193061179431931120439073768510581458840538645777, 11468128779338977627454991170077373434242662956982112374458022091799685205403739958174924656890782545985379300627220047333243221728273141268224705661724176, 12206783062193015248733718432107818979470218981382517484347399166581995220414179983209475367874885213749853792828665165419831572541488299606844410356929672, 9087644374503936422445713042262519495354015269242378663845727379671593471242553046277093282282972375042232692944817557617072928163957738086516902072926845, 10856912422509010409287844347820164231430023063083550436343906560612749384883302779955525130668557771446978715558633981721919462068155927788670765106120635, 13281414084154167463353150244480033434034591030048418283886193725790240477823155624718242265381815231284078438367030292015583825485238265699726875464138708, 13100735713929425461393585752455449243360997992484593200643212150313970813007635702752078078959005851428027515589627868595109359794717741936626684524262053, 9358546290787177499822464635126445828612338364997580581504220924364781200731136534667374146693178767296480111217891225208667316120724954786593710099385040, 11641941920102948337376031142391790797818052483113770884269155817903532335408273774257071126898619182129421203907358137604989652103236178165798191782020408, 11901865501750504580750552789852196780602085718916531586857438483441274288671853735492473647472323280664271144023442888491714562627296864368310292915435403, 9202097195736982476865652239267259934079977330899940536217069452795428428328661162806418315882755882624066720677313351717149143260722250323896190572845357, 8715429250935854863560034121423857388672722049899916597596112361019380744187072603062825340370776066776751087294057292937439931072821949899309299404915670, 12649300588476492188432266169004400880223674588131049271240572368905944588545338507988814699124640761965537204527873738494814235248352773972572647765818123, 8078448758194169347817404456085515421995635233850529793655274650917149507961623250702464671696315766331341429609291883028497429566927299847488655070969639, 9919442470699907135885936625292147291647655068189415853341202287200708550126235102611042029923751239105625302100478069117981855643073974953044630421792110, 13154112393366942311034337871684304841281306609067360467242038625507155197799330414153106316636708269577580362995439938526552260535225413916212222162801258, 6728533096895170728290546991968071192407359694551308158358159074775718711000686767207677210839206375288937150858177594270288435184864729630045664860139015, 11942303492885686960311133450578089736785328591873543615300945642360126758856501266184258298279818214333681673127128805349186712829387381839120785802399267, 13345683431318975866703169999993354304695103915856944893766485066955225916178282592261063464759534979672697159028208625003035112583504541391550898006304888, 7093679947096256544768097511035763571983054131775430797804996243523853145109325731007515001511901385799801064540291932705255184803038106705890061584166512, 12723797634500418612920650968763516600198674512720414993839551542952970776995975419777202130438585789721243418680885897916062201958072521036598596772128751, 10778109694460313425645579717661983852614125557957609223971496828356777326102046832865712943247623491438144460075962596001805881410226359218084570597412056, 10423541827372084142670512035067691617318424824756351976638058233766877923859708198312874891248181898744306366097400115542604101360727154921557885211720046, 12390616653022677930988756873993293017466462450470608774075888659378445025858534037207898876108908025433889565881652686192443226407297376837365218610153272, 13214144131387153988631995569445800808964986623570679523774605726293477092793736732597097037538231040069583877963619224374101000936973675676817140444904397, 7240028537725443231570804129133776489715860365388073186684389462471597155276866433636865345858256549361173340368524559558955818080501278546897672825685818, 8053650032502804075624943991375584143062863056584587112469847155079407236937641290823866546268310706602594566013969573660972697726115305794536053694685921, 8520439885572768423963931180067130863883533343052593335015818735812333277983033346539209049444443308229823879778689871064927366294394808213987716359551096, 9126204548092137976767284546202004027799106127135241221070264590228289313913474792887574860956593352183907302039741847540259406161659955202949609809040030, 9550907682038058714386739422314349636261045227805730964745676193375541424135400841290025246935937974729510057792687507264874848774652208036921648592962081, 7440642854357776337048579068617117485651029778879405706828547386451294213946889033215743291208426943040864939337181380154461744004544007740911349063225729, 6819690117486137064912949975106764274359977431500467109505452849487693038122366573681979680015517899373719198388429065297490031210279735965876374124645449, 9679099154386234316326418405202781262133540330721787174005755795164334785995166690688239053602657612152547488765376091930401937590087701772090541312930577, 8534111422080577658809717482596652587656120603857586950289649977168198794038703111510373789051593498246098519651565938536837972350778651102006539571216980, 12840421595405256224478975260362230965996750667469327451384774681106694917172176439246105002832300076390212312140177995553912757222180940339819232084004573, 8050226088150179999145956381061276759081257932642470610797905402182678838915273907677299566290753284028936100730343885276855050321002671302222926927204385, 8248492535425213697999433714094882905437232292389640852104774195042234348396693735829092245797516767805852999481772588819354100795221567840557647048288620, 10630341576317662589061017968615941340246165385734252728025994860361369276448142976973805331658290633480845871522485843968047595697181140599390545396720079, 10840210151261741717085985050270986188148185310800509167125706773849158997207879928892842862164374557632331077160035055525409908068817740963417430673309072, 12180929929181968007320426053956887766917181592525795118306852882543664453492839617350106585041623437169790598962646880125831094338324544759407361644646246, 7617834830019741569950617654332572094492426813235024439866787650104654643021047802893701833732909520076331491365002126154188123051289098339882428426324453, 10344906677353185999621937444922859046819863617750086540046173966295098164873995956063693773297315537658833449977248185053017736320947792190018029778504511, 7403905336133886280059955232321711450793485629417965421180669920540194422700026113781116210053535247132832541523049387589495123121303222413828221387566460, 7333040452271211065397208154116437447863934064626117777894972781203635927630239126281119478720865523753354768417405994903814370876885619380484296435808248, 9895214979244478269445311154584597354155941059435635818553627404939999309472377106745725740154650139115102956621883253937150294799523600366483321103026549, 12451232399704989724645160974285013084806098936526254092803077178597675750758351020154451133923668535989676733271505618903665435848631135637706258869227711, 11870669387160915420257152850248518151229316682414671192900680768398636432904557530055109053328080650162521964996178976598158982686938327352583159462042814, 7335490981407520030206384849453237410219218713178977632387453772779314594554506921866664437289526317764128833859796270591870345195215961335982397083255799, 11267169268947272856801668608179257225875945252447145087738512845074571486249227988056917205059414957383890731074379195337479944898102424352868548731552426, 12430827577102921000688691394135068794773372601392001866641407868270360828050434319966859441729571636308351744175900833485367998694239160022946227147286896, 7248669289347255212048832003912910492422003701685298530168869087866714893003193868754769014286855001023939047950742675425635316056242247486196098019375813, 9810689298720253206391958707763636424944526273886880496277078768414785708895556767707021167338223731300354453645637969600743559539267257384314338328037907, 12508028956672792201180885353021440167831708620116022468434833200751434177565950911664973589885649095102248931640201639566124657162507475458587661561791342, 8028105696217268794369985057715982795351143958981123845409809733046123730095797393805361734284163625064033811941819476439872758201571550218527551379308441, 11430320114587340480828697696716295670619027723099658665534540158604115523522273290757091114339249162131919936074601482231823528085444346352317842005655805, 11661074358687877120802075152417998220658510314314827377834003024694333856112615397666455060139481149875353977678489346110866454777680122895106162043092433, 11082374714785522271396571674959364898892655935355213729562550443247853722267290700139920866650405399859899792410921799855431442676730936517769304958918439, 10019961785412835302533150321475384734650520002886772524147316912104346587245355896281718855306840621917770557923602379815826907974348862075149012883972683, 12636806704090790310902646028877338426007567924465335411146557344537259682860256061281690029758451490627338925021737269239963700420791961418473293905647216, 8780921664732693360064484332991669546167796076785324919923384229602620867652892909006139033231513614734933075302018634762468669278914370966895652837616579, 8318931732691378617057776159907381026199101548707632193225248332342935783775824588681928727632576102149728663412751243645410203231947762027743898238398115, 10073314085791344990617472560871429432279449918482908226871570220904789786330815288373588032530970077963175757898271247258169175910620229645824063525004907, 10589367166266972511669471247453975133006823090461509966480844973371289930664520082564512001829958454386598033079420324989085216844085172427186269327762382, 10891886281402591047218486831781335343418974149448763132472938378995890906478644634903528784801058785782870935272031427534064544153347024096738051570078188, 11999016958564523544649172910441586713001491137938675701794067706947677643418986173362714498441071726502468556343111730939732562727391337288405851025685307, 10038592395973711425122226721158717956196785233928470748946854911073298476271370926567836129177582353371052286411799558829443913447052058105140466085457734, 9277403933471415160857999616693547183627008195140920510632203239076828404680524854775184046239384948027445724894467776664919779733555915426157716953262228, 7866233010123947810125020909329404359030991639508354245781256153191896865511342150006823940635159243142089477204325286270685308943093254303485819985114204, 8227536329083255135504737451960160869240717715386762411495964691623572601944275902911609572185172553381915693496602775637757249688579559335692495285625592, 10949820602908207578636868310052406717791733196690480252595813194626492065482128622389570448202409970405825438211087364022490623659171556770847150849254295, 11319726536972048530668730590750791293555082869794986722609898658405901047722223433870817988661252511971529468508464659650384451768476113062040466516233158, 9507368416552016919906732772811556797027945509167320474764665241956267451091520976683458518405227174288663825884203409392439199110338784105196303596846329, 9403549966391431219266035461645005130807666887531106344667858296659123074010384765262791270748889535541569024046883737927554040758438250689637034172197230, 9993118469288760204007960953471334930317152139818029577721545254298740331997002483847550569140440198842435855387193438116930714213926523362677859622372200, 7976886859383559474100304518823203125814692297000447747212681880750334081985806383912801672701699913669131161038842307445403085035978394540115572139800560, 7944305846299050414738394196622465849059448410557456843944489918932474240601308299101243775298795058938370617827369056781757957785365715492884383126771383, 7654068509518280121759333833615136766579798223611745432711397099394478071109087141555264474207207449978716356419884200244457645864722546598832855888777305, 12975621656758766992713374805071820941526449056669306156364611490134277142040988477067865793260618787221048038627230946564589005716145899227826476581039178, 9522154267720622448565046352488393684912383524230725156098168505033035725511494862101952100228325037779506806684056456580002488084086469415304969598916808, 12112477499954740690411513558309770736294529122124222471867540850304562021738763280765186695588278728777655653239595072463648730455724579685275581026072803, 6729712838354523777021851984654683564235312909486095561588684079507453745181219444391181549720162750148497050451612962583995816989200314935669453006815914, 10552983052100386334186489319068266412259356909173751618198663186232800989793913231802677944260842621058360109831940922419512303977662314311010487286955136, 10754897920088864437664850042118942770637606691983043518149415985722669898057612528434306373846656713299313660720170185091996762919233082012250426078584480, 7837346671193529921731128598984458398751439205085803745204593901587873709287123843765599855914396457272924556699124939648392053351192907957630563039390971, 10449603911563389779250484136473387720593104139292268659221908370714268630821982680498639623711568854136453980235486882491721805297362663926557728926148608, 9825632432728386970831720791447945237978030284938627349506075967146919927715187128480702522860425535571079561853508389536185419297998695800359220387148660, 7154827621313479073625603304217726206395558722232456118575199712370087747224324126880209594694954201854603439039430157491985566929470451509946747802581806, 7690116921518355664013582137647591660614867122810512586343196427223900273527024599036154620409223810354311568886956456683954102311030299318930557689130017, 11528017622873901890722326105752559491633149845942781985862741395018389064891346384364953047277200095874247031571869747978027367290392295250639014200472746, 11294595289497268782671709656912475701127800594424483981883830353670734190546149201211505977315174304011553046031638945678467349196351200701540145234747627, 10541579905047319183337957806039659807989242961210366273794282752899803036352602348582619441613524485278990500842649067929095284018730940213240137774197138, 12003157381079704247794922292984481588770046488609594520467344003893163238098717671640224442600014972045530034569632023190342947870907931056977864520010233, 10363246272037319980274785806436106464565851925850980499375457305306266661465192440260564985688546919888901041706924396693868546743458699398852442495208684, 9975393665920945183699555331987413110710638650394941810697223879462129393686606473819476911474288899040574263745266917965020160852475199086359777779923357, 10608422952742963576882124861267920794859563648989501746864473541140252345912842690431512564138151028897495066346472771540750236998680308997866107322918424, 12009021060577161222322591827603919365442696121805060601734620904798488381533692858910363600457645083018809881114749535397830251125523534113458688441832103, 8122658777621689610278510474305804150760336058504077191461738577981690953767532068472728969570850863018651605556682308871127108743207272252634329210778757, 8384652746854882735893055931304305322716115799154659961378047630429191883189654454998857662583637298714989601223161861592831710188407660318472257406550583, 9736892929802809482651057548892162262636110725983582020019302624585803980261682942749052248219732232436114292204745757871948933634198755125949876820084905, 11719750118276924327212364842924557047747167468794554128645037640109768222231472329255042228623225901156781142399423170845626468820730003625013981986506661, 8792678120079418261417428807583566647690456857180041334143111908675205197581229225702600916305920243746296919951315003069627924621403808450239313882302529, 12115456928759403934818184386592785722989603438892849241076009140445910557159293484648468641472545326003456050445886704568117359490633783231718237419534780, 12520130204978428768411510587849482698369824285378131129733581761148332197774657728487790879293865426228146064613348226215876730332511196995672988059966329, 11682312790762617516755801589618095533488941194671039687208558678227283420012372608029824434788820481939735609840395916999453999096018077546355341862905991, 8311141296413714625581618796803099584572727145428553382924911568673773961316613396593149687564507584747059996537166808129935969266770813872422868572427876, 7052235710832500906716207078684154847180279787060291752736768662363678541389815975000616433509362469406083227958138654636001715240981932788790783148748444, 7718390381262931034927284957687729739244155500501019863635697133159142099005790963958856545325292659822869491025355688339237033336149399689284507126798678, 10018035566862579217130740844236410587337910052337462403701867936663173893300990019392152121501686992346112953976419155310474164624120415248977532562140902, 8442190930048456327898472944285040559833837503179813531066229755038046102238779060337787304310582758967192365235406447193234158405211307012248849930196170, 9225139587383814902064428118047764034390757190984839366696999819818128416153338040047597278874920397097427509046782386099390198423022535770020511888361264, 12104575279355545132277192646396906702411411712586521314090584113297193886692670192215286047310037507176700351090934059100836214512719862622556724562597118, 9719884596863970064986120845914715893260161243150062719455313454988290767996195032561146506697233812348812279031924675483896838243115461501552169943392605, 9394913372731884499590425171422265827368303575089508735326573239351005474872601426612376012408692889162928365128440247786336065300775497623565141153228858, 7866978803758026418046208783963233897318154222452348915931075660849692199093199544476106476956888563453041130751429324625720135341823239184609586867335462, 11611403647846416977708021627838825146004556701331725558876240904271584379072874916276731576058043141594197552163146357332401693819623256450433266940355702, 9739017284073542812417030041993036726605236792277947483441777359209601308263540490068986008406231023680207786718823016073184536959438649614871231802757206, 8104645849700881768765026740329198716469764261029190256109965638591821189204030611068000231418532264019252365808845997337198264237836261429091607549937930, 12571604126440318959064515961357478554286540671781612844706715145505184915504257358137606444604512975413148235096172886063289189095854856548584813895029359, 12136602077139014301905671762040083031403472506074049134824586729346232839089376636423610052720904531117193847528901339610588211314655218301855573091272900, 7439977749206185432332581600000233561471476666838404012471373134093175533973685762857027125650734655132135686999574289456477058583095324702943815213435738, 11631138282927546389637756612062964312962350471145919784173947466746784561665471978061690430022684306123337373572328888186204225084116324475744913033869003, 11769367582838889226754572097677727163598036039826928325781683619031787696952047957104135346733170573511895625635487582611268619267287893245486660785029756, 7725340929897505859457548301797021980418070318790119658774384402625742752508054440568560540302552708854861835709298853705138339507911211286229926500587755, 9667989822089362278871736117318742390572410932276207589807258382279539472040041207043861586545917135152740181633941018366682110123450512054670425437694373, 10810974627898396386441284310596721581002432947144489627285742689830688232477288104602078676635075281563714746959527763425355030715902297440959371151239132, 7318445431895060850687525716599491619346585767535036101300128831801418919197251596589952982021623941159999753015904811985424869907193486996015417029183279, 8408815864648426035573038425012983618682790032966215426945297844316374054278896272697694158473100952061300439207536952970724876958798674288691381852351907, 12024741602188119304397233606778599200115900170944864038240334714847746641809121071901807191879397675464787691353153395832150821045732317486702797569053623, 12330883208603966175365524491109827901112778207622136394657829220441727784920274904454484317335708509406246804330019864370402669780726550454805354039845736, 7540090440636882064307549720054430729725760174949257524105012139272132608493480186238711391160911666834572798945532016039255021244505075928376570067651482, 12216557600130522840165674051491415158997069317129543508367283917009795565739697686026223624935476882244076580009619418487939588652582069671148217958559308, 9503751769501044003088823796197518377940568109475210370472267575765438373037101258338868421222281852080035602440965385360389246874922214610443281526134656, 11319055825719288050167904868424160856091908864391902404271415873141956509884065374566992670481061665297637903119244840452914621344438076785990102053511726, 7771936076620780399983284881600673837907849893955494031338403197410410399712939743183764108911963063090139022333746215893994284686606387251735185479188561, 11112743870490209651813909001373659304651650776933064349301118299976978314748019987701197677760707517051834718401331628273708499947220682400445238356859987, 9786673421440168043788578691503900397944111033698850287047726707638516458368786824050723049042466811828285006692527805153879063131458698791047886753308444, 11178317981412574545733650806280315833675884716076361706914563223413041955304003471794437690560655884317639421602036759146746385388602755390890212662484066, 10498028825856692490251827095323979390692350604715861252569496705370131724222362544349862878148408197368722562830225806776086435665509419028369013029273350, 13142960762736230998603470297772020158002356686861566425664910230556679715428134559533198180994379268899927918801695030330933702557191555886555918419445806, 7593938346620739986156543498058505054059852310887462447092144053963102119073471965885406007723295696109692116206796754604162117295691131062017100747247397, 9568833876565947399114008867289645583234470262723919870312670885539497411617909830702438970643489717307548398176023351368701974653155659191563966759192603, 12627214774165533030147445169367356101502056702989509243754815812642214762915456618017662848698105228615577014798162081763835339270965607728540017745286131, 13143947088694446215663634682492541746568991818038151079223748616963239406387831875226591156247257314571761380359607430177106620965615439730498061591900816, 10247653788515455464541927243685317044391012941692643025090884340634552372322067973420750917978261401465688687777919662588367610143295668039423923054686314, 12673425581500636452984529911658286448629587800706793556955632654023241284743522957241387227630822030977921957176671052765557895209648404031119785960979766, 10189845921441114737051911526718134649936331800644602635870289911638398727735918172062909766628771705053121122435385221149448289672478946969257237920592254, 8107276377917047822887269982788903899930081926593411206127981166600230942909504176699123746447914617443727851546347966084750077874794863038250156188609257, 12830741726745389634567375622620297890714424200467208743166830098051560756100183725331197483937874510563594794328823641120710406763993881737633361344201355, 7314556475681893361966614691686304284179933633750602338345715358916203085525424087246889780785599018499798631366793416527235675930361707568371114733885840, 13305247953800373632230732430595471486050678559971068587351030889429396800313842412960569491011323028100573335237843265762708755394197510116406714510242989, 10103863939495205171774823434258039500535693159073684733762787249945249620105556183448289288884845356411608334784414659759505049158928919785665257132184746, 9185110027272424546590606244058506210762040914097130685598767140926204163560238990421253052808642350630398284273671734156002492317547707069619520039534902, 12413894671398918796716607557164468542384750983058027294132765131641353665524112928446858780014105225140477356690820207528461720560992094336612232931527372, 12504479968514895069900692329096755404794866083004995517141220564400851125106191448106821720663013351408886380327826587928481990672207651483737152859528611, 11056930039205900265000238305604310639391527277689255380537577919331894854830631575282888396300346729226176723068327535847472975288140387386951603227293378, 7001781113797770108508107186732628526653805209989004454765594465107300921718892867762096980825667211886328773599221660189543136406977644896913228734145851, 7415951511697221502183910247640956356932370537996602260616666078025264355520903057565964158575132196015491667871248454925238869273702918167983206518942585, 10913235812639641284216521530862686885991799293670451381877254141069555339568773949231410562195391300214617394016490837163167033490800050062406322760419301, 7812066784856883217609896455500534039932753182278317434329441805700785961221760249429831824769017328495604344168109729972206627896625221682747652533413505, 7254699017417812990907755207283021597698294568349666218917337893909951989299026292450448042430374572000159042799411322203943129961672462655734249288131186, 8722380001585453257526667495298751725246345021647677473511772696552192214394296104350389063474061886391237002822545572539983567361077385499839269780859567, 10499842811964227941202604300833883996588905549731337950202668780729331784690014718691544657564823513041655128984888734495197534878711447143647740741055923, 11273766631582460139157512265137115225101308444320924824608549220122690470053025866382824180288600941401357775479248261857663255418116277978307366808068285, 7725471829048774178957361392167013905137389566082560581509066027583354317060631585289255121665863423139052226383705718555726697246144952164217922599707127, 10463540713624532646401470856617482208819341496285590514048271158966961822989281624198616692354403774969456818306071258367577923940352626688242963399188003, 7267521812303651930003118584226210663710810804742226743755687095908590787825714236290063446465468872569452003553736790381533721910515530421358925166231602, 9507561313779904895942860601264508427679966957090320851271585645106165149669663959560602297243051329692322276144105028383456222154279476091593468122246924, 7401742423834267209246114777443353394707029473016505937132378943043086298865053918725829567793929795419736251831046764355696666829014930145107135073890168, 13306132454434925497200003833830925700259016952441992796331378125396032200061057765409069899182082742015743943902370052054551296838383361803267238687930790, 11573411995227536647233948333114094362452698600684292960631950942465630708158674787068804128161596160251913672092078913307620798192211546951683170474467658, 13389645614868146441075152526614222858838556298552323574850401033646839600317910465572975707165646096284549705090695343451124256928691511081524372248611680, 8191162170284319433517581064384052160117895982019619907660074331353254140583880801637000879456537417311758868293550044811969185135511147755745188415434586, 11046244313029199298904840125221331660437494868256270403815169163603166320900500445508432260990716592007928633126011033783611771708773028054011196070356622, 6805703966597041605180164049884704368007351316389446428649116505606841292517276620156238292042595944199391064231837533135022135445075786522045345366041790, 8128283468575860041784829211407816906621696311384558633974276347867312268270586410283628934741668111327508149885546106432427053150443013539788288482644788, 10853348307646873978225054263497012092453408065917179709023592848029411310516109948972993583346074611396147985081699034303809887290215200904530514416446030, 11859450315531688510505842312848537002042091923235766409062237237226610505280234465764617191065209234049392230724876421885467789547385454174686429221887222, 9872815938376102530419513621633246886118887895244795283564691378669235579389414344446405665323339062604187030792296815750210514310724193989799133488671267, 11329386500201708195751605488036781818718121692892719324664640985757110067828420401395566341755255908618299905320870414846133880116096537560434234176476427, 10771136999704034217791183725162123468758108499170304279791441854127941042041307426577259064920155126816961268219933345635618825987200412552493404819330792, 12465663653808460721462573995639987077653420396551011468353993259824639584779016061936383231105733354521942531108186206586996531538748045300236321511501858, 8819948555824359594099710857159226717896801039373670208920487857890828455528989332089597197681152029246866843295395467416146004889524165021490251158955663, 8353212720860946140361863702836324482097870169505964585921155419345189849453454176403671576843478650596298454408398659500583433006366909499543741735067682, 12589699877818716149194062868687439357889786182820247208151350645184901279884287221940309161406685376094573322243174980267058326322335218908239497031639131, 10228441102321506291622720905520208305927490562607839022345800352462710022051022024723214579439901522497132428089854942289089117966040543555961762389859202, 11818122804240399677210722664107888684056004966729480328317108937625109448769762985216784723636532432020150918150104523069375998146734359822775844216590808, 8823190634255781728062456497560958686710026778438892947715577545075302125000612001895442682855976184400235229302734292103173098045522617525809847804700503, 12775935369502833145105477617334770885693715749293909168653420434520448155894968610544091335669861242877366443978821492093822603760031422631868345707334107, 13100599692465916164065520582251656891975462820372439978525679271640193071840348485633821796667614546722480312073088507633274243428458912648548644490681311, 11077528913660562349682509841790599162717540862549798571400129573954785240607223335920141654978602659357842006145579330596115205251488144457120236645139272, 8414397956763959849964685099029126154431095749529147867988745592385495194574699823460989879152586105535721763080350037576728575046347830616538931603530310, 8312390328196716323998768012371203650704451241204664681056569256525545712677151340943469999392509998453957497626108166439938957644328581184514454573646629, 7739197384902284958942037524040114970234541340606380521769371925516693860715879842646805925347532276984477084381914175523381957689868881954896295974969343, 7338747031631008473301693976477232502377825975497418498042752163198992263009021607458269258573728827272470515457064518432323494904264287031437190872674016, 9856891011718741451628845782266319278741662042518274173446074041766032419560952719116314740197721677084083670098991190608878468611615115528249785698082567, 7542560801858429414364156064686695118413098353809825409665177410710879578560573298477888927956081970928709229220103626406564882653624958096721749571812656, 10042427458758656793266686653194152705066463445022392186845759803396963848443812273733149746736545054006692007096008116553162096525070010205889432856722439, 6736527112958516253524796232210135812594917126769287053443626076890047953442405044296828827741095127256997270710716509569113091906499472145560721188864238, 12466107010742694768124523399535147612922821860153923284952232813415740568075236000400688728994430115162622970391799803268572116669269507978868248034189878, 11276620004983136375738167577937715258813442128927785406586976914613442528382276840921848435449431144907535787992879727918428121524483265432292844942414883, 7074458826381871278611314769695793146413577120906913111554570569331864198166002243920429990662333813384292968552384584135882303499506027099550614246755846, 7892744768980974906233985340725738787404628264990575185232193861536470250552136481300506064784237828654130859684578597863148597181437670833240904290943701, 11119401050907549286337128294465752892770984247387467814453382105412718448581798646315763440568185416840143002749033384136540353646322853418296802898848033, 11340294283386601079006393719461344066087019958970545729164798287825322619643292239502155338635790719547819561605909358263881571474175311484243368397356372, 7362095896683912106049486279989839055611599413101930140223564343081813409788459341875800884557776267643695431195746612818257750020473411217098877789427513, 6762064643437613509882149810426851850125464732157813384519193937151323782768401927858877948312054268808311272530618648834585871777874275662971313717309067, 11545021681268590963570347539879863450081277550723838550520696395984950474259733888096969924611290955894324883286139128813966595451541632705793669663634037, 8922422370516517762789337726296888284092110817922047104722805116254822897111291733509251296663544072096840003851512517910946426002243970767056008061182627, 11521088785894965809401380617190127015838176770514337584192275805880159669966971463113160305209701007847258930552362690664969841683631633672867747914084244, 12745333544384836300972415943644831224066430916431362068898031176492667754656688744676035977418061398734288875892309767370092915268645930648782667805345588, 8233736940741101078544408052879560942504645756419731033328005904542170150323559909373799782871672790653901393835428191135538154004232827668921624345161181, 12322195481947932139865853543394836233357546310983741367694040834414659598788176072230827593155807463698635515876110659370745713817615755815157572100939552, 9629627693069015611498074236913029455670082090610977289448179838503086937615540327873768199766762794363174268074558604863447658295638233490032540648095367, 8192669345847103730969303698513056529301815932763125439453708463907887177287699077414732639425228606320601612595014180765160279083832289515562618873320201, 7061494772993362152013461558836469027853206744702033394543480293914076625850115192996140806782169224299103528947083334441731977593519841073515177535592683, 11362594656774202452080436244771787429830088378154146374949515151116009259970605486991847405157900814680884730267050943424012261523824254360597526336965070, 7077646908162264289536425336429803643008618806876517291568823521354049970634971045725388049123390290758398144008691765418116305759620769043714673446505869, 8901956714671859106239326981082697080737606940061930734609976271218319886099701504714680363348444610386474438653287244435014146594538578209288915063343024, 8478889766601577905626667946686056539383926562500779117644290243342311983264510178282333434153105048707531926646492631571910684567820005115632242898833472, 8844650361233844277139755393412630047118269806815306036323373647969845855687852518825834171523135811299851058938814047887617685391329512761837789952586614, 12952815215678220942624650893725942016208077745992626650716250854982968900052008095000877335158283892987426095123971371695665489203836072504872711970119679, 11476910437263589515664642081530499728809065634772128306627037441213964979220041719481580038473002905916359019822871585295794165446264368118565896157889613, 10946033008198525090565612664709458838641655969736623942827738986008333958347459927034881501912283934386787941580149634369585522077677593136707134091729784, 6903956975205550049491403347678188993531590942999702819680498431933525123265550961607056937134027689310069558545528547906945184831732194077062217591375748, 13183375748045659954685749585828490765093119973337667454208548756421827220353235611185539266230363169565463751646233506781710921898018613172661394859033908, 9471276558829810584874786199165112403974001026069950136642094603374876032385847131503146638343469618500785643484527489619871674961762351136367294456474490, 12446790280669647184647117454365198571227895757879237325425449530361461539033320760956116735601518201631869807466983364266209840985032555063667242541091644, 9441546911441631995261202228188141261078568281348921262786659327670679874304303878926308791768240716215685010714520656289878291851184001119993257356133870, 12208738000668244593876259450469251566679254279037876243035457012253396599959761558587565469636786499702018829198303288540319317366540874260452350553990466, 12203895481322375650511667440787086801462251934991618688380893537243880224212833888485116615618664665063675550571626974428078540163630143480545339617279858, 12504134496532681248467737910621189420887914253253500525060060671810737634332466387281858268668172313830988958495382706849779372568806964975508373283015209, 9226208709293694728919291430987249340133381047750494431621363441174445503462270922164480132130542146140158585764770270743352502126901032093960396538363377, 12655886054762800775240503618149648209836835490532658330104942362211444519459208786179298717094009652261040977757633764795384798876128450684940378549062274, 11956248486247390249577160686072947591549950082513817478653660861723343598954508058632427916943047966537283668738602771059720312779082273746321449512756127, 10125914201692997129504193821697144167672639686328655028409181668931146143321233825825892287107091068560890423971297037398479882022062191985266332885831305, 9940627015089551776345690554124477668900674765657217087717574309940728223618211059304798673502428804996908916887252880857441917532395346249579980276370027, 9951109751252009411474907744499482099083473171040776360216192306768349038337344300528555748904598016052240654411671039861068694177155580983839170869947368, 12386883445757328715524015108014636537545219212419577776214309816344396692022851732944397754842250393802822006659151016050079969620424406513131174772809634, 13048431999881102924100137862995757853315079819829426659066294851607357886535585584052469136729601851162062073418631978468628570984667374722872917757710689, 9333344559044138603605686257496745633677716647161941350517955458149353429457965064139261141837799662223066896709406802713532709233378475409623249928262260, 11482787030494939690895922380443421767258331254107518366507351244627184975108556083064688711269002160333169636828842682511380293883899978961296352165138640, 11863736996347341491382851294016677098220534700510043031750813015181668397985376365508183553474506333447178321375142868391411496835099059449196341862131887, 13050167104995108464015639161762699724319985015804742261229092554243707982203782242446802765752076770644981440134918902271737529086890323980667128671378802, 13401646968259879304394578903522633077727267166513903611628292862081601317751696595847272338368056059703591341658698285515948346556559153900404214328319482, 7242795428796190502767894898329630206068082333138490172052956664040056238831597150263819183297496604100788227294397926881013343826527980928725870014339876, 11110024933657775903046622457597697021263288862495023549011546281365941026337670997480337558134049410191239412819147695952407992698639362218723170956897919, 9575286247057728582330605485635757495502895393140299008250932938902956225625026959453663047356840014040134142916068233954910410348016527812109694399381618, 8425444223467578447261512441794119759299167104472824741922293988958003335634511540761096899483555111654860662354448193980710603859646963193477466705627815, 10725463746461660514032344483601728985997998712612054853546657300235100686004027578101907092198018934450681191152930376690002924852450939144205214258108670, 11231766131301298535849488283197107172730907917531672263760739268496593764125458069552711672191075497346134522920398557036448036842897050200509652554634681, 9565916970851796401885780141322140436072311553046670529543153288957543450464203755497741887501730980330035802688211784557528710577852636929891962174499134, 10192512708922211909409913272901270044305958901446557059905466073819269675429806848195729732478657724276415748551728995092445362411655591540166960758358290, 9876985400538634115870917106175567433039387029655577452030487944149695332029212031676744627798491642743311502328024796851325176133623621246147621393435878, 10794239944185207659948851750968938836412660239162382178530958885139074575057640305737606633547864650871429991357952509575281695356884205005568708706277090, 11130907694882256561518287535128420003794586079127051178956408399518059333653650996757014959644073540555168430331568701599257743165231636560216642378106727, 10611613320240755295631398119611049200346200498025633208657231929947261760584864854695278006639764096023370292581796781435672939286882473878712371502511661, 12963121717290776893024383282024437404115160551989012791246478623677117964033531902400495299264062395772074670033324500956924777519520861651916345310177994, 13223968702637983616213801718246385913337191039739761965757686207466455784911322471006428560203386236594789624269441099377298345830119329623531794962366244, 8370112398979725091704623908833917644487594708929903351452208495131910883301331122116822578408434587865900418887758891510828992727706239617776384369746058, 11372164363370857962640223871324875857850892105862274501689791835040916176259847690967537618358195104376740252307391827103243052533079761371988495745789279, 11492592376460687854166192095489668743378142610619420978918752250240114445899311129687579103942670204701537754501414912271678982966277381281389729174992962, 11119554285621404510469758550846948411583033315560631772503658562122517115428219951690411757421413696739726148744394186874149999977177244663614062531578977, 13232567556670675674987005406727869423487102327167360512601328147709062962696959552101487596290402940291061190682946066503600410795051713440342938413802599, 12577060017828532265628954803573223929096809180361269868045865337973674491810569053504900590740146236252014652772778391944621718121648971837164355935511084, 12260179164898570376209781522263223175517023345992235282226558801863911525264464973868033786784173988027722963814371789760322897432317409193067799827487491, 9089237981270601508918144441549496108327269154506436262955436919447439351790898499446844400576049542573226757322353214234454668005743647665240863578208328, 9354478917499774994694702689750675860062204339868958341930286976609486249714135659471809235727462716573095859593745700270543508962601323458789690623494776, 6733464243379041663386906341680630112520475254949693423268163303926650637825564610317771393358913559830397818255694848374291990967210221648696768983624323, 7884539229390629013418864537418705685629172551476567569101235106199473527901135366428179740601934570502822333990590601432201905437783003674060378196213049, 7142160129761604222071610537649208774443660574945944448984585089941452214181188681692991137941339665476435986514122136892598552274797018787516097451159578, 8202619938093151307972924570327452436165211131864791289741046962718992442819142418369121183763936730667808818724336805002649704195267819037469244952601785, 12309505757000644058163863789974432585656140511723812341638451750480125795339746831821242563912878380338873205829442296681266644269357350364117154480738861, 9427260716621805970528638061315956058690139676251884901210286135247046302875494324918475611121675204837605907641348106383232959617716690237557435565111198, 10564202857994065111393547880645251178272883989091662322926538117319878432736191255021584452078150595501973774866011810362628693221145487469693737829200383, 12280287372326889960058735723945388524941236194991220873019043205542308103155918129805263169248253576006353180937005508566535224983442257241572804641152426, 11925191918672244515278232269335187821495224324683091848920308746323029386207173462856629554668584177019719583318278759034034599496414911807326743929742783, 8681558174025541011736083260401681666724594308238702621814134214027616699233673968763037410024997130477047754948085180261248179935861957097734922118061060, 7421760901942600346273680662142416316666603470146232686148031074274579330925592316005490283863352596277971195286682092853049669158727791916914495886443866, 12718280316714974272565847994888010737621216266507899738540581152134126698856246587873904410718112658609463981997040301757808092029693908405279171541492496, 9732793095252434749963060917387723352208080051374214787045085885311319643865211928359465510544451603752403131693330866151499272294611118747328249752668719, 10649399380706413639949826640708205017558897015026736026675138633099374048709584849813036754038576754370070774972538785800540800838374686276814987660089591, 12750011730465910557781320358689897902639952697256697204764564985662185710378487944776963124799511133309854613386364374226869126900973627887741757877439032, 12282996816948857509581119405286122968975340682696788068186075073654989524887778043005913914778014003386618365244169755291655027778405089997623923617660325, 12839378613874614267798211852429412809886686352129932594919863726963711637066095978744474462446360106596073325914814819272840493160080521888215197533032513, 10358709104243600410703526277458148720338091943328799275800174743846532163567820635206792395936381788393969950256688671762889577767095914438338603340828338, 9873257080620858568674791652081627992486894026323344704211227067248308228317825180815820219421875743611936054896855875422768517776032850188833728733445595, 8389675923609696337548643228663299051342953983995801001983404754266919289694939761230472351442838514333250392809289832547868220650294832608120817507197763, 12078149509484809269046716364831436416980970210756313194588477537619003048810741511494726042112157310903539523731474341296485873311360608697015894580489054, 7488678661593562160422453904434268768963208540115661416280600748747276254619939578659884658047902409362123614585208647023568222682822898325778328923892846, 8425192873119881201693739950488712015964225578993290379844038460153438542121508219494330885704331074682903059856693784509382369914654805199321850478191379, 7219787071755769504741028253901520723929152174869957070907865648382767645551559422575424410436754505119473890369368642541097953665085290048105541796085768, 10746198877910720260524263236860964771121401427126816398500123210542632691353295114891914877713799283380939970385761923695789598662306574252512339627089709, 13384505673404409675098432005948426847068134987109295820384261979680517149908289762280996920650119209897911507972973134653728823245305600258864667775042166, 10184934147380994726277725404878733792549426789107970489721181902584272821826856092173445773413825777174016405315011562829723009379657508440746287556027050, 9036149919742427845553607017750340310891934553462811743667744640768457682553618073595375215873050933190876979564601427434559695276864234892042444722578401, 11120993541372778696648016938899308585826679016714679609717987112186356687538436347095526929168712319412079011439164159733117679703457078489227682906390096, 12882628689763515767395868921144432335501067230015238472256480668967186748576650562394447059544444037458764404953994439434118699732764231610231970343289459, 7442715826874554354676865519359627454386458623048765887946825913446256999256266429251533231782491753588534199928058986431130143819618656928017425423149707, 7964405287202080342179662020661779562856068295525295681267766448837747272082738774511397684272680611350344176536559910504497307034880553213338577000829961, 13322667051582098349132316757378868996178443762044835034512388114015267003931206644863203084096905707698939166744304343641974059995288500891884740532503520, 9448450516836465584579172385352690170202687742890888649721036046420421906507032304970513449813453161151428394490056694539374281209427721626460681088027772, 12961141973790693646691156903880982156147419270579958568305973226519539789202377359256833502160089584123902356302644272962954973582957791441532607926496651, 11266725033407389830497977257211492382543600146696809090150412437681893445916047063107041273224336331355419594538473158253848672050419367429131096129506716, 7597558620427593547939372473767189711509252476877664934679775714395474783561517822569461007241053021723045556559428211614014647660115725621411237423077988, 10316294475212487346106885988215875471579705441085550216908233994549578339387490009208995003610956133346153554171691485338184066361644380813110530224869877, 12690777770239154507675561681469310466474524463587482162804558792905776631956207061641209124089142658764702336075173799684560273010378680590200475825215277, 12274752319475565251628796391303423038062173448519820201337702763628555051772757898411224457527123964108991583185632929307036348135675927338395936653448833, 8132144911973512270251163410577017049199867010272325747192996369269983477503774176981216697140382895091971584663812393594201281094194000993995576485689712, 13233780203945330052199410805979805000669892078077480172109786919046480694241517292497339122944481584089835811933352494635588461682660304490481539636347027, 7475157845722070403095811259118578650977085938447921162867878620236647221023172828671738063756351143579516187603451375581267923480506119715994258586363326, 10938916359741770194742693878943465598380064558998134120220734369525050460666579927341107197147034801965604758816585350898856358067169777639990811234259319, 11514813772506059359799930426895381781838673160049019439384857476915466373956568819774350142159832354802997678783546907166310420424665931026901006380678556, 12296707733480650813853874287123257976593122304619349428073759479997302005956968461004077345551926146493731641370188726468778254341866912829531890091189152, 10489113621780242161096420088694940253852906622609454895548536724988220736621583256223111721152457977195012232072539001243468801981420036966505445855073042, 10369006273892428067763204259065944420375713190022072966517550953412204159094146435207551865489898427768948937000841756213514809185531413978425945060334768, 13264725271782237148366063449121483549408494918551886384844053229481201840098196192543597224761817286833769383233580809184283606115605173852587770214806099, 9662072757531234716824780272388992502986278211582481525837536429447395598455230637946272640956526395525744888972099409465561688265581112032526820039045666, 12044732083773310600992978633773096994802224481087382696032567022821473424910803080306846411825753489264000362188291376931778386440648549619490502826207040, 10608755788158669888045411794173293239577000191602616266433849093790037882284751041294411192317439153921890885554167037200293760895867295530715302127423425, 8483575995914325021515271538665073403337540875906750869792808676720420246575894209986593877934210300406486792380103635778773660751735005402629175071396325, 13286038972627727018318261823012406383508481055880524181384447338958396921098185416043363344335714146624191377819224876160297831124368415595159814934884986, 11473896849905633318466756638710166200502999913985514849812883993136304961722382120797040750086227540242485165730900733779087144282060320337923031442528110, 8708525386068400697309781194510844007087656899607737871548744513777975044033694737980625075923081399310547985970890568631790967768041805135044068578236398, 7894718919380593935170650018112763488507510920086526087048014676760553958737351377990135424850854276756598820798742231158604385827893682040080518521723178, 12266446141066400444611491690198230567188584154274393172102093955768568529185651701200559623270680130001455463322031820043190370582442311815007043349162708, 12649914684999681018231244277727979882828337551653036715049153040313968940892560377243908720365779938516959150329477969437369055145637849253019864244510671, 12710875287736060776630917666097331800459926369870826279524458245052218279480507791586841308021391228545713667229643553624446972742556689301011780664343583, 9333308488314126649339629664371723012014627332700436065661153266464992286962574969769991824982373053593428773089707810941666593346198677853791779836303861, 11442724383659467804578423920247692750091220654347400004704329800053274321719865569214773371127430973467655915153623436676948657103530575447885406270396615, 11035203009190565083146123603053403456035954778267372708482889269460180536322294846487651106794019582227986060653542317243912030794250698941514931037076213, 9301944566991165034014915702805440921705244389599424291348832345408938002136609153823859470690036980033237825423340421133281016208201150507271437530672684, 12994294972053640612032545797264458118633289076921659182286917217114018124767929657202819478367179158098565264955649933494701648198019517069336376592568103, 9305330463380544061573097743576872023126935689804417993565400052070453775302825889512890445470179394575247213488940461942931679236377564753428351493883870, 10243622989611100407239519241875791159993730562682321627585932476213506154594633708901797746010259485876166157006123538589950571616678583922110267874749147, 11405464221115459846586499351615089836262864822732296053699947528433721286644268489300504236557346063702684398610816088717744432442192094361416435377185153, 9846871184725811313256689540524805177861702919857096099095120938123181633576443785560633848944134220640613451483481597488676361699908009719508486175407602, 8552212542468855721702376276525178755103871854849589710035912304672106752020570818853718892682865930752705446060255314448169862495642705945884157941884558, 8225111166012248729226480978179677872617546742192983984900363342759678966029182354923767705044011358898335600020159190872157681922553822880098663924020743, 7482494570894490265743731969534606399668202045355500715548712924332439741699079808906110851200678596890365739112363959735481987908970193906786293941842409, 12083847566342191237233937406751890021383111340631111905912781970620224704228493269341428435613762965093560667232740937637923074246663253973813287812830920, 10594066261750332058974635701597775665367697493523345115606286486617690107385722162520167932024038121829580740292629484064009379186215223597790563879120601, 7247129890243357762054491825067135561265258621889569646027875402642825719631550299864958946306768856506937186358137043301761489401324506766135864468386891, 12460155883473959121464388638656632542941340285173809363321560201858660097897781551882361963725784812829139860625547877491354465485468006127597768496104487, 8059454935270798361515372056991160709341247254902102267653114103513902342196240022466556892300242417565049032323733357598998758630594366088218001248688225, 10204749175065440688138800547618307825374172507823677078496346370921336112848031949515041893661175734014640753684287975267475061777456422321518746981280661, 10490695413678853922448076447859895294642903449605336396487112600196528755193527582458444983515606825487055967634732278168883596915558770355277030757271430, 12612050711499777144961488863332098071227028907576137059959713190628722222929706016607238310395812656174942153242003738231358252385347078038899611656392118, 9170678761807120001761515107339842367839806040602783575862828102153584153826513012004339033122113368737188975571087962838875417696978408240619961522774765, 10067666479090800076639571170712154139610706422225051333851496276851891025065073065090254616738470844180858993232416206403456758717084477096437518103717755, 9715651803342736196528986269506763849952462520096339588897275031345871085666881932299008110239840498475566763584906863526126988148432197484258106693352630, 7099987069478807106863398413477700497558261261654601775280210573693653609893925144650769798555583854311799336865141480317618208120973081314544091929293092, 11465108303309074079777846301227782791282078042151712595108904140925107541932354637692875275007168916110323407725532393780240790866886065208154529913469112, 9904930059818148806140809486390460548930375579315967308493382907027112467243726454658804300784453936614364834858685496702951671926542647423118794523386987, 9478499159325476786481075519278386565429264287057628046436916497851338820120913790982421023516528639145595469547354401810074092803440912161233790996146931, 11252239218061057841296940171637150186296793820862966369127309104567931517566534900440627331201546295320085241123825371771858199976495926952914973191759032, 12515793901191909375110203870037965305459220013298857734328739709097295976618871177393856526769327849137800025647848944501259149431419355306996442310648519, 10376413529767157376342804044816322715388450350485864166674671039397457381872434674751592873301617805011000242393974252800002987877637297538276774891678884, 13029944477419558002176957562029876914635936318723837586422380574186145375888988275077921941317412498738339399505836732583749028614401817563579472260562640, 9128973335410036432600056443901535952009382709835907375093618651758378722544053344494652437039441540313776715819428837874459601980087191955184492028389857, 12593082072038783271498516772963445124041185525938380308324990765558831149181638485094164505896832485761388658651338614637165343461595947218579731812372528, 11735077618674013612958820277328911531712056625782436487029546732268919017259298703917806002101583054245699020720687772508773715281974339096924201583660574, 7728784794272114065122251432569539367347669308435288683752010693247072719737935809354007319392196737344427297861905440100229532645519580981409977875477389, 7428247123612091434393868203105301144353738609125850521562292641267220723343764024923540679070061995033156020359443332402625848142710250478784927289822628, 7175631974722981646128907593630467512452568751413750660744598769656813582511577653449757709452871141988712102890994785889561778896828321219141776092936568, 11712729924217277711865941037353225655482144725132027647664241337404336587970198887018281992403024816325689402771466343696962527091043127373644051644499287, 11224922155881774876594420721948586946393014125972323121120123075745041422974431140306033119082716867866743249075099557462815732359026328549852192450607741, 7231424949131490246727570429582622002892820539158734542873543907718273873792106728737316038356516071485540926921685587333249754995404998273036282309214062, 12114026385457326314841814285471275326758879303751936710201161387722392263618638519770458330763258760723127567043511482427579569131629531264626128510587534, 11825196773678792668072747036231219052787265543710658792398946607772166234189107016805561245838528067132361784466616653131913402382816329156230169174829506, 8245008652627109779307969764316435426741245787633187676521341079921989988009890995149923524480201528984525419037000932803530272348039818862385946189208378, 11416872024745001893455670680441271032680429820629322910942279643546706696238412593818592206887249291314614269393564833810186179898019659753291792503054054, 9508103517738598162567515490140029522340899875468997709060843634300311903124525372677517883001094310168739759480427719014989087786724662462104776498860492, 12591666699340031784535689393492723021027581380950031341932492829215243597157543657985259006753398140540174561527921998646985165856089250965827305580428252, 10562979121148553681972944438801187843886610211327188638714789615417095614977184159083271923313990107523324317881077372619688918935360186670705758515614034, 9178837496809599045862745747101563821807913158145203001105088869347588283288513025992623864883370514373305323099410924866631466342279879940019297435884676, 11956643437497544605884776011280542209055203080772831562110377479125001713625733896960800643053248723958226539435343822578679360319361571672850494732543203, 12184355754385604285228006766001493884035295482237476094611620279035873563440114270062886517280622409270838457351277493919048715221447196547677444490691428, 7878417430173149671564700676946725257620857391247396621737200901555751594355240811350122547844039571130689835702513106338478637248022086359181651252812508, 13312813158209676681570719426324572903483261973326824942607834418275619060627332751222240122553605976861705748558407537736583816980351762638561898934449301, 11600762468969696953863595008447206152295524364501612305105479840520264188050378119439443203571526874409556122686633577611416718983525459649817246832984255, 7250768579343183955676652663488588363560421183517593418767904737219889802958466575474882474424337833305409871428784423676588437843576573576224901442209548, 10979128067448567633752026435877176848974411275103795791726934781479688433453345740452608682907863444272819558497652231413335004661278269156475578086255981, 7436255105275100420460511416898153049291713468966622217617088662643222540983734860154725001150551006725308043007333856948772534422998385295038520876220598, 10027187252357663308571702526178408111815034757583877140083937931534908669521303896957717717513954786265692860219593930801897757979055340414529113917679988, 8336020549751622981511233584077476561842805462625479276723362357288093796941615289966840970742892124083139760416284132806511693877286341727360200395852231, 13054661861061728198679569261116855487163066351871684551433842964991655043382533802861526981328329680081967902271755936958553327473926624447437145495116253, 8634658049427271062042590042368462997697805854519689956002345693547396306577472725817611605315158187595693984537899870869612598389538231647705566671059418, 8218859159159519121578038598020467460281694222407262298629402803476144685651239390515718883553322566586506442021743499760039042307986552346745440499993959, 11801501626217591270438739508546003475402288406666108366097163000458374631971333879472147966648996405509001738318767513711820489138111353353525840194189509, 8605785955844728062986856030603676194251525921293060970100816477468100045047992796026633064050929577214302592581667869654622678073625124202832059251400297, 10117229838996011301883144129611091204008442240435959965329058887856264697365669296641014806682180111992415128091448183791184716776608499705464667586037677, 12321041828110011457615402015754690522658254207385169331221314421844640651871934686472644492199794918256175508918654693602027901572746319106401436817684747, 11246283725752645417309801718187628770004918555044609288449505048463338475720605453424713083126772025117549401384876556341543977652136472148796626328425414, 12831414075418083029159814264534637503514734115414213445265644481423314888168579038364434837209331748540081856777262291691395427444632482037010325077486944, 9595966467704475383634944984603715362413078383908189132703471957517990025096255540029920933892252363222342509620123169951479165959399421494839281662981676, 8210490200722254391151906559848796059453183915837396987244211442829943382005628703724695234417959734186563078140839179155844980203792133728316128013516459, 6772737541220477638159499252508190255552737394375891863077243378899267608924108126989158371039643311108142669239413004969376222683419863566922553604258368, 10184023085368966148882996065749308368116427013211338160561701288471509497238447433784802152303568669892114745065012908072175121692281777812676413937295697, 11127358062138750248053934470898107749742646904916348813766599458316583175418861124570116362190130205034453819816078608295458976718118630886200466488100967, 11529460248614240296791427195154646599246525154206478576803758495983973025866809998957157546756808200578349799003627023322509515227283481790254725268885477, 12505621444657702877876739396548470369230403642305039653182152126534701367345992713776844611661039509728232070774873193447802782288920587303349560570712431, 12337656523046134837796036105124507500143381364164038917449860382700442342458628489308556317737273024038630915766720966264442092397495182424426360640336865, 10096911411989343401267191377928312934098560942232245075079600048783991448108424147699470190548394862446086923835310653725309152450997002711842610348743685, 7536528374946626787967288767876941313511898500716930016389502139719460486496704526601531264032647710884356580156855892377130570194635815454209797883778712, 11714773544931520071330775066817901860521542882972499602179556555429751439737889316284829231302244442396757773980879353474860837811614915458624808969806765, 12675953244323030707184386243568044000487235537178395012260497075543046976750897231903498878822254142182428659335451969469787713135399727308864597104444945, 8426855509697546440323016770896042150174290751983772023561120617087320182091222636357237548239185014642742164372015268862802199403827427912103379437899585, 7358031133410933718618323927731196031130633291023516275633596111347201585917729679362334066818111716891194152906469009157548249693007418787373617425702675, 6857509265718723627041261393029482099210922361466451711589121319063064231528784098105686582153577949069545474457975771137471905216089431588759498103552581, 11041975321164286355214218915135068262323251092906754493652880931822678298134179716931882673819543970319701909064440755540762201428571429583633706970143396, 6913386380903477835454690385930585000117422493822910396076262281782848662925197567392854391120069101351367334101730451462588374025250973256929569334364836, 12992425255590926782042858261897315381688346050527924628935396615272259508489461407871947957460459424172482142763610270875313779577319565954247824077745661, 11038447624549545775541007087817446204683054050075818424154602297279529534041124812421663731970648463874362136420108305010061276192575929564521964904227776, 10672541722819899103483728733076765816908124918856132730612730889182919902422018924804647626496958937605714703384215978820876132733110072193233069231189815, 7448922368464509925970050780962230079654847870268825683258611007545247803919150658973723771159476901487418708315752451400549902833407581146959902018328417, 13123685873482264099061779728220668251370698878627857386253702725357658914679172121473922993891533392463294057656858575004478432263422702544529977587941261]
n = 58113574203067314600162910771848744432179168354040678920098167335472534222998261639291145191568159464990603689062679467360303185717662426122140998218656632568172511390111887830539687208220100574329903748617343193392646019854280519859403817579746765861359633174218846216669659258251676438195667516224684805919
c = 56754194307199340085459028397027924827853574000671575387226403396873568994756738512141122143372650573201079937375922460851170745485734799044781029943783218210457587599666501326645229924138230588050782907693019958930006807017898115655426823272342984109999519420817119999272583495848119171867835187241510764427

Phân tích từng hàm:

def parinad(n):
	return bin(n)[2:].count('1') % 2

Đếm số chữ số 1 trong biểu diễn nhị phân của $n$ rồi kiểm tra xem nó chẵn hay lẻ

def vinad(x, R):
	return int(''.join(str(parinad(x ^ r)) for r in R), 2)

x^r tức là nó lấy x xor với mỗi số r trong danh sách R rồi đưa vào hàm parinad để output ra bit 1 hoặc 0. Rồi sau đó nối lại và chuyển sang hệ thập phân.

def genkey(nbit):
	while True:
		R = [getRandomNBitInteger(nbit) for _ in range(nbit)]
		r = getRandomNBitInteger(nbit)
		p, q = vinad(r, R), getPrime(nbit)
		if isPrime(p):
			e = vinad(r + 0x10001, R)
			if GCD(e, (p - 1) * (q - 1)) == 1:
				return (e, R, p * q), (p, q)
 
def encrypt(message, pubkey):
	e, R, n = pubkey
	return pow(message + sum(R), e, n)

Hàm genkey tạo danh sách R và số r để lấy p = vinad(r,R) . Nếu nó là số nguyên tố thì tạo public key gồm e = vinad(r+0x10001, R) .

Message được mã hóa bởi $(m+\sum R{)}^e\mathrm{mod}n$.

Ở bài này thì ta biết $R,n$ nhưng không biết $e$.

Hàm parinad như đã nói ở trên là hàm lấy parity của số bit 1 trong biểu diễn nhị phân của một số nguyên. Hàm này có tính chất $p(a\oplus b)=p(a)\oplus p(b)$. Vì thực chất để lấy $p(a)$ ta cần phải XOR tất cả các bit của $a$ lại. Nếu số lượng số 1 là lẻ thì kết quả là 1 còn không thì là 0. Cho nên $p(a\oplus b)$ cũng tương tự việc ta lấy $p(a)\oplus p(b)$.

Bây giờ p = vinad(r,R) thì lúc này mỗi bit của p được biểu diễn dưới dạng parinad(x^r) với mỗi số r trong R. Mà parinad(x) thì chỉ rơi vào 1 trong 2 giá trị là 0 hoặc 1 cho nên ta sẽ thử hết cả hai trường hợp để tìm ra p . Cụ thể:

p_A = int(''.join(str(parinad(r) ^ 1)for r in R),2)
p_B = int(''.join(str(parinad(r) ^ 0)for r in R),2)
factor = [p_A,p_B]
for i in factor:
	if (GCD(n,i)>1):
		p = i
		q = n//p
		print(i)
	# 4913890306465850945743279986732975023621535300705873453376575032987569618716523492520261817155685147554314907745575146259961875978458921002453631822141879

Sau khi có $p$ thì có thể khôi phục lại $r$ được để tính $e$. Để tính lại $r$ thì mình chuyển về một hệ phương trình tuyến tính trên $GF(2)$ như sau: Bây giờ ta coi mỗi bit của $r$ là một ẩn. Chẳng hạn $r_i$.
Từ phép toán parinad(x^r) for r in R thì

$$r_1+r_2+...+r_{512}+R_i=p_i$$

Đưa về hệ

$$Ax=v$$

ta cần tìm $x$. Mỗi hàng trong $A$ sẽ là các vector $[1,1,...,1]$ , $x$ là nghiệm cần tìm còn $v$ sẽ là vector cột chứa các giá trị $p_i\oplus parinad(R_i)$.

Script:

from Crypto.Util.number import *
import random
from z3 import *
R = []
n = 58113574203067314600162910771848744432179168354040678920098167335472534222998261639291145191568159464990603689062679467360303185717662426122140998218656632568172511390111887830539687208220100574329903748617343193392646019854280519859403817579746765861359633174218846216669659258251676438195667516224684805919
c = 56754194307199340085459028397027924827853574000671575387226403396873568994756738512141122143372650573201079937375922460851170745485734799044781029943783218210457587599666501326645229924138230588050782907693019958930006807017898115655426823272342984109999519420817119999272583495848119171867835187241510764427
def parinad(n):
	return bin(n)[2:].count('1') % 2
def vinad(x, R):
	return int(''.join(str(parinad(x ^ r)) for r in R), 2)
# check 
a = random.randrange(2**16)
b = random.randrange(2**16)
resA = parinad(a^b)
resB = parinad(a)^parinad(b)
print(resA,"\\n")
print(resB)
 
def bits_to_int(bits):
	res = ''.join(str(b) for b in bits)
	return int(res,2)
p_A = int(''.join(str(parinad(r) ^ 1)for r in R),2)
p_B = int(''.join(str(parinad(r) ^ 0)for r in R),2)
factor = [p_A,p_B]
for i in factor:
	if (GCD(n,i)>1):
		p = i
		q = n//p
		print(i)
def gauss_xor(matrix, rhs, nvars):
    A = [row[:] for row in matrix]
    b = rhs[:]
    row = col = 0
    where = [-1] * nvars
    while row < len(A) and col < nvars:
        sel = None
        for i in range(row, len(A)):
            if A[i][col]:
                sel = i
                break
        if sel is None:
            col += 1
            continue
        A[row], A[sel] = A[sel], A[row]
        b[row], b[sel] = b[sel], b[row]
        where[col] = row
        for i in range(len(A)):
            if i != row and A[i][col]:
                for j in range(col, nvars):
                    A[i][j] ^= A[row][j]
                b[i] ^= b[row]
        row += 1
        col += 1
    x = [0] * nvars
    for i in range(nvars):
        if where[i] != -1:
            x[i] = b[where[i]]
    return x
nbit = len(R)
 
p_bits = list(map(int, bin(p)[2:].zfill(nbit)))
 
A = []
rhs = []
for j in range(nbit):
    row = [1] * nbit  
    rhs_val = p_bits[j] ^ (bin(R[j]).count("1") & 1)
    A.append(row)
    rhs.append(rhs_val)
 
solution = gauss_xor(A, rhs, nbit)
r = sum((bit << (nbit-1-i)) for i, bit in enumerate(solution))
print(r)
e = vinad(r + 0x10001, R)
phi = (p-1)*(q-1)
d = pow(e,-1,phi)
m = pow(c,d,n)- sum(R)
print(long_to_bytes(m))

Thử bằng sage thì nghiệm nó lại bị lệch 1 so với cách dùng gauss trên

from Crypto.Util.number import *
import random
from sage.all import *
R = []
n = 58113574203067314600162910771848744432179168354040678920098167335472534222998261639291145191568159464990603689062679467360303185717662426122140998218656632568172511390111887830539687208220100574329903748617343193392646019854280519859403817579746765861359633174218846216669659258251676438195667516224684805919
c = 56754194307199340085459028397027924827853574000671575387226403396873568994756738512141122143372650573201079937375922460851170745485734799044781029943783218210457587599666501326645229924138230588050782907693019958930006807017898115655426823272342984109999519420817119999272583495848119171867835187241510764427
def parinad(n):
	return bin(n)[2:].count('1') % 2
def vinad(x, R):
	return int(''.join(str(parinad(x ^ r)) for r in R), 2)
# check 
# a = random.randrange(2**16)
# b = random.randrange(2**16)
# resA = parinad(a^b)
# resB = parinad(a)^parinad(b)
# print(resA,"\\n")
# print(resB)
 
def bits_to_int(bits):
	res = ''.join(str(b) for b in bits)
	return int(res,2)
p_A = int(''.join(str(parinad(r) ^ 1)for r in R),2)
p_B = int(''.join(str(parinad(r) ^ 0)for r in R),2)
factor = [p_A,p_B]
for i in factor:
	if (GCD(n,i)>1):
		p = i
		q = n//p
		print(i)
nbit = len(R)
 
F = GF(2)
A = []
b = []
p_bits = list(map(int, bin(p)[2:].zfill(nbit)))
R_bits = [list(map(int, bin(R[j])[2:].zfill(nbit))) for j in range(nbit)]
 
for j in range(nbit):
	row = [1] * nbit
	A.append(row)
	rhs_val = p_bits[j] ^ (bin(R[j]).count("1") & 1 )
	b.append(rhs_val)
 
M = Matrix(F, A)
v = vector(F, b)
sol = M.solve_right(v)
solution = [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
 
r = sum((bit << (nbit-1-i)) for i, bit in enumerate(solution))
print(r)
e = vinad(r + 0x10001 , R)
phi = (p-1)*(q-1)
d = pow(e,-1,phi)
m = pow(c,d,n)- sum(R)
print(long_to_bytes(m))

Một cách ngắn gọn hơn của bạn mình (somehow it worked lol)

from Crypto.Util.number import long_to_bytes
from sage.all import gcd, inverse_mod, is_prime
 
V = 0
for r in R:
    num = bin(r).count('1') % 2
    V = (V << 1) | num
 
for p in [V, (1 << 512) - 1 - V]:
    if p > 1 and n % p == 0 and is_prime(p):
        q = n // p
        if is_prime(q):
            break
 
phi = (p - 1) * (q - 1)
for e in [V, (1 << 512) - 1 - V]:
    if gcd(e, phi) == 1:
        e = e
        break
 
d = inverse_mod(e, phi)
m = pow(c, d, n) - sum(R)
flag = long_to_bytes(m)
print(flag.decode())

matemith

Solving Matemith’s polynomial equations is easier than pronouncing ‘Matemith’, but that’s not saying much!

Source code của bài:

#!/usr/bin/env sage
 
from Crypto.Util.number import *
from flag import flag
 
l, flag = 14, flag.lstrip(b'CCTF{').rstrip(b'}')
FLAG = [flag[l * i:l * (i + 1)] for i in range(len(flag) // l)]
M = [bytes_to_long(_) for _ in FLAG]
p = getPrime(313)
 
R.<u, v, w, x, y, z> = PolynomialRing(QQ)
 
COEFS = [getRandomRange(1, p - 1) for _ in range(21)]
 
f = COEFS[0] * u * v + COEFS[1] * u + COEFS[2] * v
g = COEFS[3] * u * x * y + COEFS[3] * x + COEFS[5] * y + COEFS[6] * v
h = COEFS[7] * u * w + COEFS[8] * w + COEFS[9] * u
i = COEFS[10] * v * y * z + COEFS[11] * y + COEFS[12] * z + COEFS[13] * w
j = COEFS[14] * v * w + COEFS[15] * v + COEFS[16] * w
k = COEFS[17] * w * z * x + COEFS[18] * z + COEFS[19] * x + COEFS[20] * u
 
f, g, h, i, j, k = R(f), R(g), R(h), R(i), R(j), R(k)
CNST = [_(M[0], M[1], M[2], M[3], M[4], M[5]) for _ in [f, g, h, i, j, k]]
f, g, h, i, j, k = [[f, g, h, i, j, k][_] + (p - CNST[_]) % p for _ in range(6)]
 
print(f'{p = }')
print(f'{f = }')
print(f'{g = }')
print(f'{h = }')
print(f'{i = }')
print(f'{j = }')
print(f'{k = }')
 

output.txt

p = 9892984422801315119260311427714389408772405421306235794826917610128461644036928139298330716261
f = 8593371583346286129538282168765198524220954884352992069219549555526097253129502925759872761483*u*v + 8192555264287905175212103898575474256555217842060435386769432116145712989123062847161390929397*u + 9598573789403814092125115160545174167539204328557118715540593719644188998531033259685435430387*v + 5738603225260621554442220996093767502015758942320213371600986432070445300427944977409453429117
g = 7737077144206080155196706693824644356475708615710271404071364943161652008584970269394416250641*u*x*y + 6282097687310252658473848438985225466620614743750918909885172321224925965646628839166491648752*v + 7737077144206080155196706693824644356475708615710271404071364943161652008584970269394416250641*x + 3354788147890488743832873565215769634619909759459203496980671578348799162553954862104978291860*y + 2560270290674636359252235177920929027441112715609783111306743340637878970846852799006820932563
h = 6107224904478508858527197508483774405356161856691777460732363192128980355274418091837270668258*u*w + 3584245173493717638976874408629921683995390608944250077841702023698807664457252845973088744491*u + 5646173287331462026544218972062953582608380797148923127395811758145598594972832047259631339566*w + 1994681139685786114971936867358158466232859433926848067961874687630342141141862187589124089741
i = 7622670835797214156123791992548663880284352234566921286637648219243086701251627093499322050472*v*y*z + 6026769215097777844835562389865313764490318485655789123763637718591748620654875700763740623760*w + 8145050175261359549200629067766090532616263522561328878195831921153188650784907223634130346224*y + 3622105614070476540808786980829452605696331317022729645355376801209444137548670550164418237117*z + 4800360746061605999597274870855047707130861888252519642520437605796496240599924899885487900040
j = 1912186465211454827473018892315659311053527670028135595953520151335825509122313783795561869379*v*w + 6246883466276200389231653597272295993565421216541002743075041326054203024921176043191679609212*v + 4002308425802254921531592700910138281674785127934610897914017993007060136199147207365547047048*w + 973159800079995512996976852328990077106942094656694887771601292254542762394381629810393447820
k = 1423338294606985951732736428034353751447528399559929388138157330118213387990891693204997290038*w*x*z + 784018806462384388182217012266169299116410899849461442885543245867941419322406775218178098109*u + 7684681843989505989596042520590550892565982707534588920361260899638313817214040416765327284778*x + 4982848574842913858489870338816729222210785430242027484672099513487039514577513464674726403409*z + 7781690757622738625626304200561818137843970209349935834539461705684625161407233281360563620790
 

Phân tích:

Đầu tiên ta có

l, flag = 14, flag.lstrip(b'CCTF{').rstrip(b'}')

Lấy flag và bỏ phần bọc bên ngoài ra, chỉ lấy nội dung bên trong. Sau đó chia flag thành các phần có độ dài là l.

M = [bytes_to_long(_) for _ in FLAG]
p = getPrime(313)

Chuyển các giá trị này thành số nguyên và sinh một số nguyên tố p .

Tạo một vành đa thức $\mathbb{Q}[x,y,z,u,v,w]$ với các biến $x,y,z,u,v,w$ với một tập gồm 20 hệ số

R.<u, v, w, x, y, z> = PolynomialRing(QQ)
 
COEFS = [getRandomRange(1, p - 1) for _ in range(21)]
 

Phần chính của bài:

f = COEFS[0] * u * v + COEFS[1] * u + COEFS[2] * v
g = COEFS[3] * u * x * y + COEFS[3] * x + COEFS[5] * y + COEFS[6] * v
h = COEFS[7] * u * w + COEFS[8] * w + COEFS[9] * u
i = COEFS[10] * v * y * z + COEFS[11] * y + COEFS[12] * z + COEFS[13] * w
j = COEFS[14] * v * w + COEFS[15] * v + COEFS[16] * w
k = COEFS[17] * w * z * x + COEFS[18] * z + COEFS[19] * x + COEFS[20] * u
 
f, g, h, i, j, k = R(f), R(g), R(h), R(i), R(j), R(k)
CNST = [_(M[0], M[1], M[2], M[3], M[4], M[5]) for _ in [f, g, h, i, j, k]] 
f, g, h, i, j, k = [[f, g, h, i, j, k][_] + (p - CNST[_]) % p for _ in range(6)]

Ta có các đa thức như sau

$$\begin{array}{l}f=c_{0}uv+c_{1}u+c_{2}v\\ g=c_{3}uxy+c_{3}x+c_{5}y+c_{6}v\\ h=c_{7}uw+c_{8}w+c_{9}u\\ i=c_{10}vyz+c_{11}y+c_{12}z+c_{13}w\\ j=c_{14}vw+c_{15}v+c_{16}w\\ k=c_{17}wzx+c_{18}z+c_{19}x+c_{20}u\end{array}$$

Sau đó ta sẽ thay các giá trị FLAG vào $f(m_0,m_1,m_2,m_3,m_4,m_5),...,k(m_0,m_1,m_2,m_3,m_4,m_5)$.

Dòng sau:

f, g, h, i, j, k = [[f, g, h, i, j, k][_] + (p - CNST[_]) % p for _ in range(6)]

Biến mỗi đa thức $f,g,h,i,j,k$ thành các đa thức mới thỏa mãn

$$\begin{array}{l}f(m_0,...,m_5)\equiv 0\mathrm{mod}p\\ ...\\ k(m_0,...,m_5)\equiv 0\mathrm{mod}p\end{array}$$

Các đa thức này nhận nghiệm là các thành phần của flag.

Hmmm vậy h nên làm gì để tìm lại các nghiệm này.

Nghiệm chung của các đa thức này trên ${\mathbb{F}}_p[x,y,z,u,v,w]$ là các thành phần của flag.

Groebner basis có vẻ không ổn lắm

from Crypto.Util.number import *
from sage.all import *
p = 9892984422801315119260311427714389408772405421306235794826917610128461644036928139298330716261
 
R = PolynomialRing(GF(p),['u','v','w','x','y','z'])
u,v,w,x,y,z = R.gens()
f = 8593371583346286129538282168765198524220954884352992069219549555526097253129502925759872761483*u*v + 8192555264287905175212103898575474256555217842060435386769432116145712989123062847161390929397*u + 9598573789403814092125115160545174167539204328557118715540593719644188998531033259685435430387*v + 5738603225260621554442220996093767502015758942320213371600986432070445300427944977409453429117
g = 7737077144206080155196706693824644356475708615710271404071364943161652008584970269394416250641*u*x*y + 6282097687310252658473848438985225466620614743750918909885172321224925965646628839166491648752*v + 7737077144206080155196706693824644356475708615710271404071364943161652008584970269394416250641*x + 3354788147890488743832873565215769634619909759459203496980671578348799162553954862104978291860*y + 2560270290674636359252235177920929027441112715609783111306743340637878970846852799006820932563
h = 6107224904478508858527197508483774405356161856691777460732363192128980355274418091837270668258*u*w + 3584245173493717638976874408629921683995390608944250077841702023698807664457252845973088744491*u + 5646173287331462026544218972062953582608380797148923127395811758145598594972832047259631339566*w + 1994681139685786114971936867358158466232859433926848067961874687630342141141862187589124089741
i = 7622670835797214156123791992548663880284352234566921286637648219243086701251627093499322050472*v*y*z + 6026769215097777844835562389865313764490318485655789123763637718591748620654875700763740623760*w + 8145050175261359549200629067766090532616263522561328878195831921153188650784907223634130346224*y + 3622105614070476540808786980829452605696331317022729645355376801209444137548670550164418237117*z + 4800360746061605999597274870855047707130861888252519642520437605796496240599924899885487900040
j = 1912186465211454827473018892315659311053527670028135595953520151335825509122313783795561869379*v*w + 6246883466276200389231653597272295993565421216541002743075041326054203024921176043191679609212*v + 4002308425802254921531592700910138281674785127934610897914017993007060136199147207365547047048*w + 973159800079995512996976852328990077106942094656694887771601292254542762394381629810393447820
k = 1423338294606985951732736428034353751447528399559929388138157330118213387990891693204997290038*w*x*z + 784018806462384388182217012266169299116410899849461442885543245867941419322406775218178098109*u + 7684681843989505989596042520590550892565982707534588920361260899638313817214040416765327284778*x + 4982848574842913858489870338816729222210785430242027484672099513487039514577513464674726403409*z + 7781690757622738625626304200561818137843970209349935834539461705684625161407233281360563620790
F = [f,g,h,i,j,k]
G = Ideal(F).groebner_basis()
for g in G:
    print(g,"\\n")
''' 
verbose 0 (3848: multi_polynomial_ideal.py, groebner_basis) Warning: falling back to very slow toy implementation.
x^2 + 624920207501363192367281928881573415517079225824154025706645360217104570332569151305785085592*x + 7464919848382306919559995662593809398583906167231917414575851313560171120953298377686640540660*y + 5276670820925818706192217867333032768163478153806749492560540113515158461375058938505716890616*z + 4543055670837435553530951141170031640037926432058186187581447392555219812939668534418739959933 
 
x*y + 3962091338848393905677936286012127797047048242618748929840241973274669127535729777049950819895*x + 5236431834906753720181325761186027134539046316885141894092112692862846005308355770440130337372*y + 5125650562911467719733777828273140301363867088774833237822035979286969584554071590327201829166*z + 3757340660981437428682692396045901397654000368866666743923169359945730590254601510207431168221 
 
y^2 + 6658923546207369408434539535372024515060139838743301581167209697623308804965278090849183495563*x + 8878384405547295690109890126115187543735314287275556008539632147895235863208042323059620991993*y + 8895714131430653314957883027081435881010835725211004495245092137965897379072812112253131578917*z + 2774749087432903125077931213389490361303647465663997693171202335761338438175346948242147160777 
 
x*z + 4986388841393333460621869716035305934398196594117801761833935404383394026534578005033622693582*x + 4123085051959735120263083040478368037079309932332146058082457154541241054721317469863599304010*y + 2458290216073643210927971522061241366743702347012178675190155557789281150495266683284795865133*z + 595998207486584826270811128547130323256607454526401025788997792124023709860298604130893418836 
 
y*z + 5214953212896890369451819334827708447960241137917756011755855054739874318160774165797821440466*x + 5825512176676461375082060659537885280292936652555833512093126868754664311335386295189648669504*y + 3267158023299953268600152886612093435240223016774521310631173320704526214557071204843609897363*z + 1061599456934329096214156323615177183709056083837140001597189720038243172159355899601246657031 
 
z^2 + 1432872050234882864395516010680957228510792077270734936377565740835441416422421941892067426800*x + 4507109717001709510831696479576097306163496469303356734593304730121120393685666298426114311260*y + 6210868991834979639062492130246742979845866545958461575932012283523160150969546930104999734078*z + 3697417358925813166308630851752520978498621652138597304592366655284871892186014223832434317601 
 
u + 9278059260927794625321822521445150709925989348199550227539018734257217333155253421906997535184*x + 8448761634028956410528911781238729498451220906568524310219824841324137446537586214296021618303*y + 8832923846876892468664467862366245924256914356941763689573886659181473460260016336177890742462*z + 6222026266229455098581548668905780547435323354175322166684186804438675930293185506378599302869 
 
v + 2856406640129254927027476906283620669647760161242188164647875301297863984616179666389588786040*x + 7547885649598994473453601797483929388994770687549010756576201311304175193232991465676229350225*y + 7063931180022227535019566532096486842628351110756319183931492995289585551986752686035100980252*z + 8693815681325957620821232151875903538834208184880857286627457793946833993287358258510903277766 
 
w + 1717231562191321157334629945811010410099853821434770073134153869445378776340235294384281516760*x + 1141764791981958828834229106092156218986720487172049623865150175898307587627569023296679328078*y + 9284787453738801484991918405952556972015979041247864886372137642820906132986432684976717807617*z + 1742833796903100907615534838805446594930171572727059706374413348359928730539465306111678325918 
'''

Nhưng có một điểm khá thú vị là 6 đa thức đầu là các đa thức theo biến $x,y,z$ nên mình tiếp tục xài Groebner basis với 6 đa thức này.

R_lex = PolynomialRing(Fp, ['x','y','z'], order='lex')
x,y,z = R_lex.gens()
f1 = x**2 + 624920207501363192367281928881573415517079225824154025706645360217104570332569151305785085592*x + 7464919848382306919559995662593809398583906167231917414575851313560171120953298377686640540660*y + 5276670820925818706192217867333032768163478153806749492560540113515158461375058938505716890616*z + 4543055670837435553530951141170031640037926432058186187581447392555219812939668534418739959933 
f2 = x*y + 3962091338848393905677936286012127797047048242618748929840241973274669127535729777049950819895*x + 5236431834906753720181325761186027134539046316885141894092112692862846005308355770440130337372*y + 5125650562911467719733777828273140301363867088774833237822035979286969584554071590327201829166*z + 3757340660981437428682692396045901397654000368866666743923169359945730590254601510207431168221 
f3 = y**2 + 6658923546207369408434539535372024515060139838743301581167209697623308804965278090849183495563*x + 8878384405547295690109890126115187543735314287275556008539632147895235863208042323059620991993*y + 8895714131430653314957883027081435881010835725211004495245092137965897379072812112253131578917*z + 2774749087432903125077931213389490361303647465663997693171202335761338438175346948242147160777 
f4 = x*z + 4986388841393333460621869716035305934398196594117801761833935404383394026534578005033622693582*x + 4123085051959735120263083040478368037079309932332146058082457154541241054721317469863599304010*y + 2458290216073643210927971522061241366743702347012178675190155557789281150495266683284795865133*z + 595998207486584826270811128547130323256607454526401025788997792124023709860298604130893418836 
f5 = y*z + 5214953212896890369451819334827708447960241137917756011755855054739874318160774165797821440466*x + 5825512176676461375082060659537885280292936652555833512093126868754664311335386295189648669504*y + 3267158023299953268600152886612093435240223016774521310631173320704526214557071204843609897363*z + 1061599456934329096214156323615177183709056083837140001597189720038243172159355899601246657031 
f6 = z**2 + 1432872050234882864395516010680957228510792077270734936377565740835441416422421941892067426800*x + 4507109717001709510831696479576097306163496469303356734593304730121120393685666298426114311260*y + 6210868991834979639062492130246742979845866545958461575932012283523160150969546930104999734078*z + 3697417358925813166308630851752520978498621652138597304592366655284871892186014223832434317601 
eq = [f1,f2,f3,f4,f5,f6]
G1 = Ideal(eq).groebner_basis()
for g1 in G1:
    print(g1,"\\n")
'''
x + 5287817177255572353561709069477238346211323543432345022760649006980481237742439145322709945747*z^3 + 2294701677793561789500916668873926598062561788726297004522894255222901064334900131530886143650*z^2 + 133200961167624039083561806466483955734916575928095198057015435551150078138842369803227298296*z + 9476405390512761679830579178992878394541970475730767652118293885045128734612488535784100149849 
 
y + 9269499828888469266996390876331458069878314607398568884170622585033905057340503646645621132715*z^3 + 7782701596176596603057875730380512023245010801640694628450626466245857296361651719923385707372*z^2 + 9313822945699953022081995949448125019595421004471241160567474135343182895029763501967586681403*z + 1545247208559051759591106206699393531649904700246194288802884763029210484983569270154160935780 
 
z^4 + 7129785587103459355506111078105544785764594371325861055032156946532756844802583091029940380903*z^3 + 5587635262602597609650333768611219949696820549291115517260341565549524195071106244443429259793*z^2 + 1388172903343175464573935697507463604528982473364345912677864317989643138078920967254076552870*z + 725772276065471746120788740308410096314921224935273100792206765543487746615394775367426538799 
 
'''

Đa thức cuối là đa thức đơn biến theo biến $z$ nên mình sẽ giải lấy nghiệm của nó.

f_z = z**4 + 7129785587103459355506111078105544785764594371325861055032156946532756844802583091029940380903*z**3 + 5587635262602597609650333768611219949696820549291115517260341565549524195071106244443429259793*z**2 + 1388172903343175464573935697507463604528982473364345912677864317989643138078920967254076552870*z + 725772276065471746120788740308410096314921224935273100792206765543487746615394775367426538799 
roots = f_z.univariate_polynomial().roots(multiplicities=False)
print(roots)
# [4770453019325870905337936375351021260986815961838868610602658504874560459357193877676598504213, 1362759193209085863333245994737983]

Lấy nghiệm nhỏ hơn ta được

>>> print(long_to_bytes(1362759193209085863333245994737983))
b'C0pp3r5m17h!!?'

Làm tương tự cho các phần còn lại

from Crypto.Util.number import *
from sage.all import *
p = 9892984422801315119260311427714389408772405421306235794826917610128461644036928139298330716261
Fp = GF(p)
# R = PolynomialRing(GF(p),['u','v','w','x','y','z'])
# u,v,w,x,y,z = R.gens()
# f = 8593371583346286129538282168765198524220954884352992069219549555526097253129502925759872761483*u*v + 8192555264287905175212103898575474256555217842060435386769432116145712989123062847161390929397*u + 9598573789403814092125115160545174167539204328557118715540593719644188998531033259685435430387*v + 5738603225260621554442220996093767502015758942320213371600986432070445300427944977409453429117
# g = 7737077144206080155196706693824644356475708615710271404071364943161652008584970269394416250641*u*x*y + 6282097687310252658473848438985225466620614743750918909885172321224925965646628839166491648752*v + 7737077144206080155196706693824644356475708615710271404071364943161652008584970269394416250641*x + 3354788147890488743832873565215769634619909759459203496980671578348799162553954862104978291860*y + 2560270290674636359252235177920929027441112715609783111306743340637878970846852799006820932563
# h = 6107224904478508858527197508483774405356161856691777460732363192128980355274418091837270668258*u*w + 3584245173493717638976874408629921683995390608944250077841702023698807664457252845973088744491*u + 5646173287331462026544218972062953582608380797148923127395811758145598594972832047259631339566*w + 1994681139685786114971936867358158466232859433926848067961874687630342141141862187589124089741
# i = 7622670835797214156123791992548663880284352234566921286637648219243086701251627093499322050472*v*y*z + 6026769215097777844835562389865313764490318485655789123763637718591748620654875700763740623760*w + 8145050175261359549200629067766090532616263522561328878195831921153188650784907223634130346224*y + 3622105614070476540808786980829452605696331317022729645355376801209444137548670550164418237117*z + 4800360746061605999597274870855047707130861888252519642520437605796496240599924899885487900040
# j = 1912186465211454827473018892315659311053527670028135595953520151335825509122313783795561869379*v*w + 6246883466276200389231653597272295993565421216541002743075041326054203024921176043191679609212*v + 4002308425802254921531592700910138281674785127934610897914017993007060136199147207365547047048*w + 973159800079995512996976852328990077106942094656694887771601292254542762394381629810393447820
# k = 1423338294606985951732736428034353751447528399559929388138157330118213387990891693204997290038*w*x*z + 784018806462384388182217012266169299116410899849461442885543245867941419322406775218178098109*u + 7684681843989505989596042520590550892565982707534588920361260899638313817214040416765327284778*x + 4982848574842913858489870338816729222210785430242027484672099513487039514577513464674726403409*z + 7781690757622738625626304200561818137843970209349935834539461705684625161407233281360563620790
# F = [f,g,h,i,j,k]
# G = Ideal(F).groebner_basis()
# for g in G:
#     print(g,"\\n")
 
R_lex = PolynomialRing(Fp, ['x','y','z'], order='lex')
x,y,z = R_lex.gens()
# f1 = x**2 + 624920207501363192367281928881573415517079225824154025706645360217104570332569151305785085592*x + 7464919848382306919559995662593809398583906167231917414575851313560171120953298377686640540660*y + 5276670820925818706192217867333032768163478153806749492560540113515158461375058938505716890616*z + 4543055670837435553530951141170031640037926432058186187581447392555219812939668534418739959933 
# f2 = x*y + 3962091338848393905677936286012127797047048242618748929840241973274669127535729777049950819895*x + 5236431834906753720181325761186027134539046316885141894092112692862846005308355770440130337372*y + 5125650562911467719733777828273140301363867088774833237822035979286969584554071590327201829166*z + 3757340660981437428682692396045901397654000368866666743923169359945730590254601510207431168221 
# f3 = y**2 + 6658923546207369408434539535372024515060139838743301581167209697623308804965278090849183495563*x + 8878384405547295690109890126115187543735314287275556008539632147895235863208042323059620991993*y + 8895714131430653314957883027081435881010835725211004495245092137965897379072812112253131578917*z + 2774749087432903125077931213389490361303647465663997693171202335761338438175346948242147160777 
# f4 = x*z + 4986388841393333460621869716035305934398196594117801761833935404383394026534578005033622693582*x + 4123085051959735120263083040478368037079309932332146058082457154541241054721317469863599304010*y + 2458290216073643210927971522061241366743702347012178675190155557789281150495266683284795865133*z + 595998207486584826270811128547130323256607454526401025788997792124023709860298604130893418836 
# f5 = y*z + 5214953212896890369451819334827708447960241137917756011755855054739874318160774165797821440466*x + 5825512176676461375082060659537885280292936652555833512093126868754664311335386295189648669504*y + 3267158023299953268600152886612093435240223016774521310631173320704526214557071204843609897363*z + 1061599456934329096214156323615177183709056083837140001597189720038243172159355899601246657031 
# f6 = z**2 + 1432872050234882864395516010680957228510792077270734936377565740835441416422421941892067426800*x + 4507109717001709510831696479576097306163496469303356734593304730121120393685666298426114311260*y + 6210868991834979639062492130246742979845866545958461575932012283523160150969546930104999734078*z + 3697417358925813166308630851752520978498621652138597304592366655284871892186014223832434317601 
# eq = [f1,f2,f3,f4,f5,f6]
# G1 = Ideal(eq).groebner_basis()
# for g1 in G1:
#     print(g1,"\\n")
 
f_z = z**4 + 7129785587103459355506111078105544785764594371325861055032156946532756844802583091029940380903*z**3 + 5587635262602597609650333768611219949696820549291115517260341565549524195071106244443429259793*z**2 + 1388172903343175464573935697507463604528982473364345912677864317989643138078920967254076552870*z + 725772276065471746120788740308410096314921224935273100792206765543487746615394775367426538799 
roots_z = f_z.univariate_polynomial().roots(multiplicities=False)
r1, r2 = roots_z
 
f_yz = y + 9269499828888469266996390876331458069878314607398568884170622585033905057340503646645621132715*z**3 + 7782701596176596603057875730380512023245010801640694628450626466245857296361651719923385707372*z**2 + 9313822945699953022081995949448125019595421004471241160567474135343182895029763501967586681403*z + 1545247208559051759591106206699393531649904700246194288802884763029210484983569270154160935780 
f_y = f_yz(z=r2).univariate_polynomial()
roots_y = f_y.roots(multiplicities=False)
print(long_to_bytes(ZZ(roots_y[-1])))
 
f_xz = x + 5287817177255572353561709069477238346211323543432345022760649006980481237742439145322709945747*z**3 + 2294701677793561789500916668873926598062561788726297004522894255222901064334900131530886143650*z**2 + 133200961167624039083561806466483955734916575928095198057015435551150078138842369803227298296*z + 9476405390512761679830579178992878394541970475730767652118293885045128734612488535784100149849 
f_x = f_xz(z=r2).univariate_polynomial()
roots_x = f_x.roots(multiplicities=False)
print(long_to_bytes(ZZ(roots_x[-1])))
R = PolynomialRing(GF(p),['u','v','w','x','y','z'])
u,v,w,x,y,z = R.gens()
f_uxyz = u + 9278059260927794625321822521445150709925989348199550227539018734257217333155253421906997535184*x + 8448761634028956410528911781238729498451220906568524310219824841324137446537586214296021618303*y + 8832923846876892468664467862366245924256914356941763689573886659181473460260016336177890742462*z + 6222026266229455098581548668905780547435323354175322166684186804438675930293185506378599302869 
 
f_u = f_uxyz(x=roots_x[-1],y=roots_y[-1],z=r2).univariate_polynomial()
 
roots_u = f_u.roots(multiplicities=False)
print(long_to_bytes(ZZ(roots_u[-1])))
 
f_vxyz = v + 2856406640129254927027476906283620669647760161242188164647875301297863984616179666389588786040*x + 7547885649598994473453601797483929388994770687549010756576201311304175193232991465676229350225*y + 7063931180022227535019566532096486842628351110756319183931492995289585551986752686035100980252*z + 8693815681325957620821232151875903538834208184880857286627457793946833993287358258510903277766 
f_v = f_vxyz(x=roots_x[-1],y=roots_y[-1],z=r2).univariate_polynomial()
roots_v = f_v.roots(multiplicities=False)
print(long_to_bytes(ZZ(roots_v[-1])))    
 
f_wxyz =w + 1717231562191321157334629945811010410099853821434770073134153869445378776340235294384281516760*x + 1141764791981958828834229106092156218986720487172049623865150175898307587627569023296679328078*y + 9284787453738801484991918405952556972015979041247864886372137642820906132986432684976717807617*z + 1742833796903100907615534838805446594930171572727059706374413348359928730539465306111678325918 
f_w = f_wxyz(x=roots_x[-1],y=roots_y[-1],z=r2).univariate_polynomial()
roots_w = f_w.roots(multiplicities=False)
print(long_to_bytes(ZZ(roots_w[-1])))    
 
print(b'CCTF{'+long_to_bytes(ZZ(roots_u[-1]))+long_to_bytes(ZZ(roots_v[-1]))+long_to_bytes(ZZ(roots_w[-1]))+long_to_bytes(ZZ(roots_x[-1]))+long_to_bytes(ZZ(roots_y[-1]))+long_to_bytes(ZZ(roots_z[-1]))+b'}')
# b'CCTF{50lv!n6_7H3_H1dD3n__num8Ers_Pr08l3m_f0r_C51dH_4nd_C5uRf_v14_4uT0m473d_C0pp3r5m17h!!?}'
 

Note: Sub giá trị trong sage

from sage.all import *
def poly_sub(f, x, y):
    ret = f.parent().zero()
    for c, m in f:
        while m % x == 0:
            m //= x
            c *= y
        ret += c * m
    return ret
 
def poly_sub2(f, x, y):
    # <https://ask.sagemath.org/question/25972/substitute-xy-by-u/#post-id-25996>
    Q = f.parent().quotient(x - y)
    return Q(f).lift()
 
for R in [ZZ, Zmod(17 * 19), GF(2 ** 8), CyclotomicField(17)]:
    PR = R["x, y, z"]
    x, y, z = PR.gens()
    assert poly_sub((x * y + 1) ** 7, x * y, z) == (z + 1) ** 7
    assert poly_sub2((x * y + 1) ** 7, x * y, z) == (z + 1) ** 7
    assert poly_sub((x**2 * y + 1) ** 3, x * y, z) == (z * x + 1) ** 3
    assert poly_sub2((x ** 2 * y + 1) ** 3, x * y, z) == (z * x + 1) ** 3

Chỉnh lại syntax theo python là xài được oke.

silky

Silky’s ‘noisy’ equations are like static on a radio—annoying, but solvable if you tune just right.

nc 91.107.252.0 31131

Source code của bài:

#!/usr/bin/env sage
 
import sys
from Crypto.Util.number import *
from flag import flag
 
def die(*args):
	pr(*args)
	quit()
	
def pr(*args):
	s = " ".join(map(str, args))
	sys.stdout.write(s + "\\n")
	sys.stdout.flush()
	
def sc():
	return sys.stdin.buffer.readline()
 
def randroad(B):
	return vector(ZZ,[randint(-B, B) for _ in range(n)])
 
def roadband():
	return randroad(B * (D + 1))
 
def silky(key):
	while True:
		R = roadband()
		_R = R - key
		if min(_R) >= - B * D and max(_R) <= B * D:
			return R
 
def main():
	border = "┃"
	pr(        "┏━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┓")
	pr(border, ".:::      Welcome to the Silky cryptography oracle task!     :::.", border)
	pr(border, "Your mission is to find flag by analyzing this weird oracle! :-) ", border)
	pr(        "┗━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┛")
	global flag, B, n, D, t
	B, n = 5, 19
	D, t = 110, 128
	l = int(4 * D * B / t)
	c, key = 0, randroad(B)
	while True:
		c += 1
		if c >= 12:
			die(border, "My brain is fried, quitting...")
		pr(f"{border} Options: \\n{border}\\t[G]et flag! \\n{border}\\t[M]ake Silky! \\n{border}\\t[Q]uit")
		ans = sc().decode().strip().lower()
		if ans == 'm':
			R = [silky(key) for _ in range(int(l * t // 2))]
			for i in range(len(R) // 16):
				pr(border, f"{str(R[16 * i:16 * (i + 1)]).replace(',', '')}")
		elif ans == 'g':
			pr(border, f'Please submit the secret key: ')
			inp = sc().decode().strip()
			try:
				_key = vector(ZZ, [int(_) for _ in inp.split(',')])
			except:
				die(border, f'The input you provided is not valid! Bye!!')
			if _key == key:
				die(border, f'Congrats! You got the flag: {flag}')
			else:
				die(border, f'Your key is incorrect!')
		elif ans == 'q':
			die(border, "Quitting...")
		else:
			die(border, "Bye...")
 
if __name__ == '__main__':
	main()

Có lẽ là cái này eprint.iacr.org/2024/1261.pdf

Solve script:

from pwn import *
deltaB = 550
B = 5
while True:
    try:
        r = remote("91.107.132.34", 31131)
        for _ in range(4):
            r.recvline()
        lines = []
        for _ in range(10):
            r.recvuntil(b"[Q]uit")
            r.sendline(b"m")
            r.recvline()
            for _ in range(68):  
                line = r.recvline()[4:].strip()[2:-2].split(b") (")
                for vec in line:
                    vec_ints = list(map(int, vec.strip().split(b" ")))
                    lines.append(vec_ints)
        key = []
        for i in range(19):
            f_i_vals = [vec[i] for vec in lines]
 
            a_i = min(min(f + deltaB, B) for f in f_i_vals)
            b_i = max(max(f - deltaB, -B) for f in f_i_vals)
 
            est = round((a_i + b_i) / 2)
            key.append(max(-B, min(B, est))) 
 
        print(key)
        r.recvuntil(b"[Q]uit")
        r.sendline(b"g")
        r.recvuntil(b"submit the secret key: ")
        r.sendline(",".join(map(str, key)).encode())
        res = r.recvall(timeout=1)
        if b'CCTF{' in res:
            print(res.decode())
            break
        r.close()

Sobata

Source code của bài:

#!/usr/bin/env sage
 
import sys
from Crypto.Util.number import *
from flag import FLAG
 
def die(*args):
	pr(*args)
	quit()
	
def pr(*args):
	s = " ".join(map(str, args))
	sys.stdout.write(s + "\\n")
	sys.stdout.flush()
 
def sc(): 
	return sys.stdin.buffer.readline()
 
def gen_params(nbit):
	while True:
		p = getPrime(nbit)
		if p % 6 == 1:
			F = GF(p)
			R = [F.random_element() for _ in '01']
			a, b = [R[_] ** ((p - 1) // (3 - _)) for _ in [0, 1]]
			if a != 1 and b != 1:
				c, d = [F.random_element() for _ in '01']
				E = EllipticCurve(GF(p), [0, d])
				return (p, E, a, b, c)
 
def walk(P, parameters):
	p, E, a, b, c = parameters
	x, y = P.xy()
	Q = (a * x, b * y)
	assert Q in E
	return int(c) * E(Q)
 
def jump(P, n, parameters):
	_parameters = list(parameters)
	_parameters[-1] = pow(int(_parameters[-1]), n, _parameters[1].order())
	return walk(P, _parameters)
 
def main():
	border = "┃"
	pr(        "┏━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┓")
	pr(border, ".::               Welcome to the Sobata challenge!            ::. ", border)
	pr(border, " You should analyze this weird oracle and break it to get the flag", border)
	pr(        "┗━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┛")
	nbit = 512
	parameters = gen_params(nbit)
	E = parameters[1]
	m = bytes_to_long(FLAG)
	assert m < parameters[0]
	while True:
		try:
			P = E.lift_x(m)
			break
		except:
			m += 1
	while True:
		pr("| Options: \\n|\\t[E]ncrypted FLAG \\n|\\t[W]alking with P \\n|\\t[J]umping over P \\n|\\t[Q]uit")
		ans = sc().decode().strip().lower()
		if ans == 'e':
			_P = walk(P, parameters)
			pr(border, f'The encrypted flag is: {_P.xy()}')
		elif ans == 'w':
			pr(border, 'Please send your desired point over E: ')
			Q = sc().decode().strip().split(',')
			try:
				Q = [int(_) for _ in Q]
			except:
				die(border, 'Your input is not valid!!')
			if Q in E:
				pr(border, f'The result of the walk is: {walk(E(Q), parameters).xy()}')
			else:
				die(border, 'Your point is not on the curve E! Bye!!')
		elif ans == 'j':
			pr(border, 'Send your desired point over E: ')
			Q = sc().decode().strip().split(',')
			pr(border, 'Let me know how many times you would like to jump over the given point: ')
			n = sc().decode().strip()		
			try:
				Q = [int(_) for _ in Q]
				n = int(n)
			except:
				die(border, 'Your input is not valid!!')
			if Q in E:
				pr(border, f'The result of the jump is: {jump(E(Q), n, parameters).xy()}')
			else:
				die(border, 'Your point is not on the curve E! Bye!!')
		elif ans == 'q': die(border, "Quitting...")
		else: die(border, "Bye...")
 
if __name__ == '__main__':
	main()

Script solve:

from pwn import *
from math import gcd
from sage.all import *
from Crypto.Util.number import *
 
io = remote('91.107.161.140', 11177)
 
io.recvuntil('[Q]uit\\n')
io.sendline(b'e')
io.recvuntil('encrypted flag is: ')
enc_flag = io.recvline().strip().decode()[1:-1]
enc_flag = map(int, enc_flag.split(', '))
x1, y1 = enc_flag
 
io.recvuntil('[Q]uit\\n')
io.sendline(b'j')
io.recvuntil('Send your desired point over E: ')
io.sendline(f'{x1}, {y1}'.encode())
io.recvuntil('Let me know how many times you would like to jump over the given point: ')
io.sendline(b'0')
io.recvuntil('result of the jump is: ')
result = io.recvline().strip().decode()[1:-1]
result = map(int, result.split(', '))
x2, y2 = result
 
p = max(gcd(y1**2 - y2**2, x1**3 - x2**3), gcd(x1**3 - y1**2, x2**3 - y2**2))
b1 = GF(p)(y1**2 - x1**3)
b2 = GF(p)(y2**2 - x2**3)
assert b1 == b2
d = b1
 
E = EllipticCurve(GF(p), [0, d])
 
def find(exp):
    x = PolynomialRing(GF(p), 'x').gen()
    f = x**exp - 1
    factors = f.factor()
    res = []
    for factor, multiplicity in factors:
        root = -factor[0]
        assert pow(root, exp, p) == 1
        res.append(root)
 
    return res
 
_a, _b = find(3), find(2)
 
def jump(x, y, n):
    io.recvuntil('[Q]uit\\n')
    io.sendline(b'j')
    io.recvuntil('Send your desired point over E: ')
    io.sendline(f'{x}, {y}'.encode())
    io.recvuntil(b'Let me know how many times you would like to jump over the given point: ')
    io.sendline(str(n).encode())
    io.recvuntil('result of the jump is: ')
    result = io.recvline().strip().decode()[1:-1]
    result = map(int, result.split(', '))
    return result
 
for a in _a:
    for b in _b:
        _x1 = x1 * inverse(a, p) % p
        _y1 = y1 * inverse(b, p) % p
        new_x, new_y = jump(_x1, _y1, -1)
        flag = new_x * inverse(a, p) % p
        print(long_to_bytes(int(flag)))

Toffee

Source code của bài:

 
#!/usr/bin/env sage
 
import sys
from Crypto.Util.number import *
from hashlib import sha512
from flag import flag
from sage.all import *
 
def die(*args):
pr(*args)
quit()
 
def pr(*args):
s = " ".join(map(str, args))
sys.stdout.write(s + "\\n")
sys.stdout.flush()
 
def sc():
return sys.stdin.buffer.readline()
 
def sign(msg, skey):
global k
h = bytes_to_long(sha512(msg).digest())
k = toffee(u, v, k)
P = k * G
r = int(P.xy()[0]) % _n
s = inverse(k, _n) * (h + r * skey) % _n
return (r, s)
 
def toffee(u, v, k):
return (u * k + v) % _n
 
def main():
border = "┃"
pr(        "┏━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┓")
pr(border, ".:::    Welcome to the Toffee chocolate cryptography task!    ::.", border)
pr(border, ".:  Your mission is to find flag by analyzing the signatures!  :.", border)
pr(        "┗━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┛")
global flag, u, v, k, _n, G
skey = bytes_to_long(flag)
p = 0xaeaf714c13bfbff63dd6c4f07dd366674ebe93f6ec6ea51ac8584d9982c41882ebea6f6e7b0e959d2c36ba5e27705daffacd9a49b39d5beedc74976b30a260c9
a, b = -7, 0xd3f1356a42265cb4aec98a80b713fb724f44e747fe73d907bdc598557e0d96c5
_n = 0xaeaf714c13bfbff63dd6c4f07dd366674ebe93f6ec6ea51ac8584d9982c41881d942f0dddae61b0641e2a2cf144534c42bf8a9c3cb7bdc2a4392fcb2cc01ef87
x = 0xa0e29c8968e02582d98219ce07dd043270b27e06568cb309131701b3b61c5c374d0dda5ad341baa9d533c17c8a8227df3f7e613447f01e17abbc2645fe5465b0
y = 0x5ee57d33874773dd18f22f9a81b615976a9687222c392801ed9ad96aa6ed364e973edda16c6a3b64760ca74390bb44088bf7156595f5b39bfee3c5cef31c45e1
F = FiniteField(p)
E = EllipticCurve(F, [a, b])
G = E(x, y)
u, v, k = [randint(1, _n) for _ in ';-)']
while True:
pr(f"{border} Options: \\n{border}\\t[G]et toffee! \\n{border}\\t[S]ign message! \\n{border}\\t[Q]uit")
ans = sc().decode().strip().lower()
if ans == 'g':
pr(border, f'Please let me know your seed: ')
_k = sc().decode().strip()
try:
_k = int(_k)
except:
die(border, 'Your seed is not valid! Bye!!')
pr(f'{toffee(u, v, _k) = }')
elif ans == 's':
pr(border, f'Please send your message: ')
msg = sc().strip()
r, s = sign(msg, skey)
pr(border, f'{r = }')
pr(border, f'{s = }')
elif ans == 'q':
die(border, "Quitting...")
else:
die(border, "Bye...")
 
if __name__ == '__main__':
main()
 

Script solve:

from pwn import *
from sage.all import *
from Crypto.Util.number import *
from hashlib import sha512
p = 0xaeaf714c13bfbff63dd6c4f07dd366674ebe93f6ec6ea51ac8584d9982c41882ebea6f6e7b0e959d2c36ba5e27705daffacd9a49b39d5beedc74976b30a260c9
a, b = -7, 0xd3f1356a42265cb4aec98a80b713fb724f44e747fe73d907bdc598557e0d96c5
_n = 0xaeaf714c13bfbff63dd6c4f07dd366674ebe93f6ec6ea51ac8584d9982c41881d942f0dddae61b0641e2a2cf144534c42bf8a9c3cb7bdc2a4392fcb2cc01ef87
x = 0xa0e29c8968e02582d98219ce07dd043270b27e06568cb309131701b3b61c5c374d0dda5ad341baa9d533c17c8a8227df3f7e613447f01e17abbc2645fe5465b0
y = 0x5ee57d33874773dd18f22f9a81b615976a9687222c392801ed9ad96aa6ed364e973edda16c6a3b64760ca74390bb44088bf7156595f5b39bfee3c5cef31c45e1
F = FiniteField(p)
E = EllipticCurve(F, [a, b])
G = E(x, y)
r = remote("91.107.188.9", 31111)
for _ in range(4):
    print(r.recvline().decode().strip())
r.recvuntil(b"[Q]uit")
def get_toffee(val):
    r.sendline(b'g')
    r.recvuntil(b'seed:')
    r.sendline(str(val).encode())
    while True:
        res = r.recvline().decode().strip()
        if "toffee" in res:
            break
    nonce = int(res.split("=")[-1].strip())
    return nonce
k0 = 100
k1 = 101
x0 = get_toffee(k0)
x1 = get_toffee(k1)
assert gcd(k1 - k0, _n) == 1  
u = ((x1 - x0) * inverse(k1 - k0, _n)) % _n
v = (x0 - u * k0) % _n
print(f"u = {u}")
print(f"v = {v}")
 
def get_signature(msg):
    r.sendline(b's')
    r.recvuntil(b'Please send your message:')
    r.sendline(msg.encode())
    r.recvuntil(b"r = ")
    r_line = r.recvline().decode().strip()
    r_val = int(r_line)
    r.recvuntil(b"s = ")
    s_line = r.recvline().decode().strip()
    s_val = int(s_line)
    return r_val, s_val
 
msg1 = 'sample1'
msg2 = 'sample2'
h1 = bytes_to_long(sha512(msg1.encode()).digest())
h2 = bytes_to_long(sha512(msg2.encode()).digest())
r1,s1 = get_signature(msg1)
r2,s2 = get_signature(msg2)
num = (u * s2 * h1 - h2 * s1 + v * s1 * s2) % _n
den = (r2 * s1 - u * r1 * s2) %_n
d = (num * inverse(den, _n)) % _n
print(long_to_bytes(d))

Juliax

Source code của bài :

#!/usr/bin/env sage
 
from Crypto.Util.number import *
from flag import flag
 
nbit, ebit, xbit = 512, 72, 313
Q = 2 ** (nbit - xbit)
 
def keygen(nbit):
	while True:
		p, q = [getPrime(nbit) for _ in ':)']
		n, phi = p * q, (p - 1) * (q - 1)
		if n.bit_length() == 2 * nbit:
			e = getPrime(ebit)
			if GCD(e, phi) > 1:
				continue
			u, v = [inverse(e, _ - 1) for _ in [p, q]] 
			k = (e * u - 1) // (p - 1)
			l = (e * v - 1) // (q - 1)
			if GCD(2 * e, k) == 1:
				break
	U, V = u % Q, v % Q
	return n, e, U, V
 
n, e, U, V = keygen(nbit)
m = bytes_to_long(flag)
assert m < n
c = pow(m, e, n)
 
print(f'{e = }')
print(f'{n = }')
print(f'{U = }')
print(f'{V = }')
print(f'{c = }')

output.txt:

e = 4680013789992958764661
n = 113512878655961571626610562291692317083167898593072246908072509473338669866931624486434843922077792562235492835323939380660867587409311081240029070350808655984402585845023288249807250489084430773691893497493957878187939757801622886103893275017257035278212160216032814012251157961899906789943525036078018769313
U = 1931999207628789396725122770203483408911326042952326921451
V = 799504796180001663308018451701479236857150404193865300422493
c = 94105129348907954980205351665290609913865320383526984688577432708537003146181471259880907643772804194349299707552600926808992628679380768658711570812064692302538521952981150231103309549852666196113547591789678339722493939214907786911484309585843582998176263433226474196365066591224488571958002184788519619403

Logic chính của bài nằm ở hàm sau:

 
def keygen(nbit):
	while True:
		p, q = [getPrime(nbit) for _ in ':)']
		n, phi = p * q, (p - 1) * (q - 1)
		if n.bit_length() == 2 * nbit:
			e = getPrime(ebit)
			if GCD(e, phi) > 1:
				continue
			u, v = [inverse(e, _ - 1) for _ in [p, q]] 
			k = (e * u - 1) // (p - 1)
			l = (e * v - 1) // (q - 1)
			if GCD(2 * e, k) == 1:
				break
	U, V = u % Q, v % Q
	return n, e, U, V
 

Đầu tiên ta có hai số nguyên tố $p,q$ , mỗi số 512 bit. Số mũ $e$ là số nguyên tố, như bình thường thì ta cũng chọn $e=65537$ nhưng số mũ này không lớn lắm. Bây giờ ta có $u=e^{-1}\mathrm{mod}p-1$ và $v=e^{-1}\mathrm{mod}q-1$. Tức là

$$\begin{gathered} u\equiv d\mathrm{mod}p-1 \\ v\equiv d\mathrm{mod}q-1 \end{gathered}$$

Ta cũng có

$$\begin{gathered} k=(e\times u-1)//(p-1) \\ l=(e\times v-1)//(q-1) \end{gathered}$$

Vì ta có $eu-1=k(p-1)$ nên ta chia để lấy giá trị $k$.

Cuối cùng ta lấy

$$u\mathrm{mod}Q,v\mathrm{mod}Q$$

tương đương với việc lấy 200 bits cuối của $u$ và $v$ vì $Q=2^{199}$

Ý tưởng của bài trên nằm trong paper sau:

https://eprint.iacr.org/2022/1163.pdf

Ta được cho biết các giá trị

$$n,e,U,V$$

trong đó $U,V$ là các LSB của $d_p,d_q$ trong đó $d_p=d\mathrm{mod}p-1$ và $d_q=d\mathrm{mod}q-1$

Mình sẽ giải thích lại những gì mình hiểu từ paper này cũng như cách để làm bài trên.

Bài toán chia thành 2 bước

Bước 1: Ta cần tính lại các số $k,l$ thỏa mãn

$$\begin{gathered} e{d}_p=1+k(p-1) \\ edq=1+l(q-1) \end{gathered}$$

Ta sẽ dùng Coppersmith small roots cho bước này.

Mọi người xem phần 3.3 của paper trên cho trường hợp leak LSB.

Điều kiện để giải được trong thời gian đa thức là $\delta <1/2-2\alpha -2\gamma$.

Đầu tiên ta có

$$\begin{gathered} k^{\prime }p=k^{\prime }-1+e{d}_p^{\prime } \\ {l}^{\prime }q=l^{\prime }-1+e{d}_q^{\prime } \end{gathered}$$

Lấy tích của 2 phương trình ta đưa về

$$k^{\prime }{l}^{\prime }N=(k^{\prime }-1)(l^{\prime }-1)+e{d}_p^{\prime }(l^{\prime }-1)+e{d}_q^{\prime }(k^{\prime }-1)+e^2{d}_p^{\prime }{d}_q^{\prime }$$

Ta biểu diễn theo LSB và MSB như sau

$$d_p^{\prime }=d_p^{\prime (M)}{2}^i+d_p^{\prime (L)}$$

Tương tự với $d_q^{\prime }$ và thay lại vào phương trình trên

$$k^{\prime }{l}^{\prime }N\equiv (k^{\prime }-1)(l^{\prime }-1)+e{d}_p^{\prime (L)}(l^{\prime }-1)+e^2{d}_p^{\prime (L)}{d}_q^{\prime (L)}(\mathrm{mod}{2}^{i}e)$$

Đặt $A\equiv -e^2{d}_p^{\prime (L)}{d}_q^{\prime (L)}+e{d}_q^{\prime (L)}+e{d}_p^{\prime (L)}-1$ và đưa về

$$k^{\prime }{l}^{\prime }(N-1)-k^{\prime }\left(e{d}_q^{\prime (L)}-1\right)-l^{\prime }\left(e{d}_p^{\prime (L)}-1\right)+A\equiv 0\mathrm{mod}{2}^{i}e$$

Ta xây dựng đa thức $f(x,y)$ với nghiệm là $(k^{\prime },l^{\prime })$ và dùng Copper smith đa biến. $2^i$ thì $i$ ở đây chính là 199, phần bit bị leak của $d_p,d_q$

$$f(x,y)=(N-1)xy-x(e{d}_q^{\prime (L)}-1)-y(e{d}_q^{\prime (L)}-1)+A$$

Bước 2. Factor $n$, dựa vào $k$. Tác giả có đề cập đến Howgrave-Graham’s approximate divisor algorithm

Script:

# part 1 
from Crypto.Util.number import *
from sage.all import *
import itertools
 
def small_roots(f, bounds, m, d):
    R = f.base_ring()
    N = R.cardinality()
    f = f.change_ring(ZZ) 
    G = Sequence([], f.parent())
    for i in range(m+1):
        base = N**(m-i) * f**i
        for shifts in itertools.product(range(d), repeat=f.nvariables()):
            g = base * prod(map(power, f.variables(), shifts))
            G.append(g)
    B, monomials = G.coefficient_matrix()
    monomials = vector(monomials)
    factors = [monomial(*bounds) for monomial in monomials]
    for i, factor in enumerate(factors):
        B.rescale_col(i, factor)
 
    B = B.dense_matrix().LLL()
    B = B.change_ring(QQ)
    for i, factor in enumerate(factors):
        B.rescale_col(i, 1/factor)
 
    H = Sequence([], f.parent().change_ring(QQ))
    for h in filter(None, B*monomials):
        H.append(h)
        I = H.ideal()
        if I.dimension() == -1:
            H.pop()
        elif I.dimension() == 0:
            roots = []
            for root in I.variety(ring=ZZ):
                root = tuple(R(root[var]) for var in f.variables())
                roots.append(root)
            return roots
    return []
 
e = 4680013789992958764661
n = 113512878655961571626610562291692317083167898593072246908072509473338669866931624486434843922077792562235492835323939380660867587409311081240029070350808655984402585845023288249807250489084430773691893497493957878187939757801622886103893275017257035278212160216032814012251157961899906789943525036078018769313
U = 1931999207628789396725122770203483408911326042952326921451
V = 799504796180001663308018451701479236857150404193865300422493
c = 94105129348907954980205351665290609913865320383526984688577432708537003146181471259880907643772804194349299707552600926808992628679380768658711570812064692302538521952981150231103309549852666196113547591789678339722493939214907786911484309585843582998176263433226474196365066591224488571958002184788519619403
l_dp = U
l_dq = V
nbit, ebit, xbit = 512, 72, 313
i = nbit - xbit
P = PolynomialRing(Zmod(e*2**i),['x','y'])
x,y = P.gens()
A = e*(l_dp + l_dq) - e**2 * l_dp * l_dq - 1
f = (n-1)*x*y - (e*l_dq-1)*x - (e*l_dp-1)*y + A
roots = small_roots(f, (e,e),m=2,d=3)[0]
print(roots)
# k, l = 4198425198326169691467, 134913244452494180544 
 
# part 2
from sage.all import *
from Crypto.Util.number import *
 
# Data
e = 4680013789992958764661
n = 113512878655961571626610562291692317083167898593072246908072509473338669866931624486434843922077792562235492835323939380660867587409311081240029070350808655984402585845023288249807250489084430773691893497493957878187939757801622886103893275017257035278212160216032814012251157961899906789943525036078018769313
U = 1931999207628789396725122770203483408911326042952326921451
V = 799504796180001663308018451701479236857150404193865300422493
c = 94105129348907954980205351665290609913865320383526984688577432708537003146181471259880907643772804194349299707552600926808992628679380768658711570812064692302538521952981150231103309549852666196113547591789678339722493939214907786911484309585843582998176263433226474196365066591224488571958002184788519619403
k, l = 4198425198326169691467, 134913244452494180544
nbit, xbit = 512, 313
i = nbit - xbit
 
def solve(f_poly, X, m, t):
    X = Integer(X)
    S = [x**j for j in range(m+1)]
    F = [f_poly**j * k**(m-j) * n**max(0, t-j) for j in range(m+1)]
    cols = len(F)
    M = Matrix(ZZ, [
        [int(c) for c in (Fi(x*X)).coefficients(sparse=False) + [0]*cols][:cols]
        for Fi in F
    ]).LLL()
    S_vals = [Integer(S[j](X)) for j in range(cols)]
    roots = []
    for row in M:
        try:
            poly = sum((row[j] // S_vals[j]) * S[j] for j in range(cols))
            roots += [int(r) for r, _ in poly.roots() if r in ZZ]
        except (ZeroDivisionError, TypeError):
            pass
    return sorted(set(roots))
 
R = PolynomialRing(QQ, 'x'); x = R.gen()
modulus = k * n
a = ((e * U + k - 1) * pow(e * 2**i, -1, modulus)) % modulus
f = x + a
X = 2**(512 - i)
for h_dp in solve(f, X, m=20, t=10):
    p = gcd(int(f(x=h_dp)), n)
    if 1 < p < n and is_prime(p):
        q = n // p
        d = inverse_mod(e, (p-1)*(q-1))
        print(long_to_bytes(pow(int(c), int(d), int(n))))
        break