Rhyton

Contrary to their simple and attractive appearance, rhytons have a complex design and a complicated implementing process. We invite you to drink in an attractive rhyton.

#!/usr/bin/env python3

from Crypto.Util.number import *
from flag import flag

def gen_rhyton(nbit, delta, L):

	p, q = [getPrime(nbit) for _ in '01']
	n = p * q
	D = int(n ** (1 - delta))	
	phi = (p - 1) * (q - 1)

	V = [getRandomRange(1, n - 1) for _ in range(L)]
	U = [phi * v // n for v in V]

	W, i = [], 0
	while True:
		w = getRandomRange(phi * V[i] - U[i] * n - D, phi * V[i] - U[i] * n + D)
		if abs(phi * V[i] - U[i] * n - w) < D and w < n:
			W.append(w)
			i += 1
		if i == L:
			break
	return (p, q, U, V, W)

def encrypt(msg, p, q):
	m, n = bytes_to_long(msg), p * q
	assert m < p * q
	e = 65537
	return pow(m, e, n)

nbit, delta, L = 512, 0.14, 110
p, q, U, V, W = gen_rhyton(nbit, delta, L)

enc = encrypt(flag, p, q)

print(f'n = {p * q}')
print(f'V = {V}')
print(f'W = {W}')
print(f'enc = {enc}')

n = 49591240968755429312049716457401995044426228002042796673181723541052680686607142887478520649618793698962090278633758513884171676353727006663491490879076122806832591078074115708337594057067669644204000056843957586023240832467089341357479281915585002907388803865098521478310733618496248846355733226548228547757
V = [18195649916055395820860323022336271650763072026697032564658041131161984264176129949637202989635534186979956352747599323285514815878978947708943150049427449068203756416583494315306586505409445611598480145974729328526246475084339296160043060232765034431332538888947260688436691194836846783099866834018415851993, 27183989479184855579071234549433514666463245249548905046669995939490825610826412699804225128894902745320728257433585491165415447411315898024599086683537147870401897644530505329216579063999184613413983132784095340721334260997525646104932765375139158295725852059141413363094998922430374253809334078874237642516, 49527419342655780190580888657111446394759262001970009186524993557451455267641630781560575611414926510537372342723133645713219891202092781315289927101065265396634833822327579319336103975136209786969633164663793457605618280351966345693379745463785701662731025286744303189161921049993960494187865075252105344665, 23127600422120175914745332993925770141196376121125627490151274189044980178186553737296983439902455858643033099812199325522697841970136761146009953170590398383741262087371633643415904470174465317780261638204898517962809393435558189944589441293734678325402794173757670076130227419065608602675888770560239133295, 2060982192720362156731515997818486262143480370158456291632251469153388255062414718549103133507056586937565568936437110111754674250895233852005979604761139776353322371609455427480861852695035697655096241439626189314476742987278329065017754801236072347819712836485415671749240858018674822379841478301049101083, 33222764431955022846462566375262888700051558337856025575334253091047986128191220017537062144029394633430244757134473345198596551945777498678916644508705412951981460305257016535592983609132751740730008532576388445224117043444976181438066280849471963859614313950358048479649132814739494041621150478897578558246, 25528839409096781185663441308826634664657962931892145815575818380194638712096183016083438256985407518618332643200920300159044445354946854803360832556716541735571105310756010588106739550820093720436281085520639725333584424310224164876097788366012048088730071501895818954531059399296690890397175138806835347421, 11344204673923803412739423041332497984733056851738638761485855465585065844965923202971089895543931852711563571026233715972605737877187803285583916729461273919882711765749706205283073349191063926494027610505115334100863029798186309513465755834413209132191947793797902884895452169911034916996316007554916317184, 15848968256315855091042060434660990121795977828649123003561307582158286409588367287352203778549325686827078150907778821145687699442610968717852223794723371721665310726689289576304741640899819703223664181762264469507274156171106211811312345709685201427408122041102199690818156131238089616022946800901304404489, 33202000212281082381755674439492186246108036981953358355553674428483646763594648594095287883998414593016169020530886866802144553911942788492349515124181534970862508642597183296559694485076962778177606172417935561397025119170452842879553083631232707654974860492090802889740479776910944224874654584681910075085, 43129332020006141907894958309003873050690894579346836800532453091150209295548956530744317486118259855711600942933548043549607819702050129571211338529937678526135680248064939836245145625155820428618182730897203149821560193471747013620704423957961355270172611536647399161763632700960220791695922536779459211867, 1400207245103670059083256191967334823248952256990422331672398774332900759849280241399230585375618667527167409895027064876462585596792678195734945987267938136158590407038817128816150267092999510274532831143168122745672343351850023551411517502191342712541390124105225513714353332974189039545882047272610002860, 41583667849894747140665364165056187828973240586238709437465564995804218388531992138987557724259271723400986779937286844504376983332045331368407405160594266511583572213228910079303627143478824028552179327200436207771016086109278256109847649537628366648036101325094585915609422329344897998808255326018784642285, 3398340585759893015334747255600081175737468900245045028171851544037525171421868902505548132697611249631945307202417184437482461945800898699417597196344771846408407702420391979828884637149884267976136832863935208680825871470245542899836631080968761450360844740522734708216006215927900750153194840117092966131, 14023684567797672699377381757065107132318797710013136851334604410254148109428970989555963440498603788575546292063374042761730511394335305143196110980096596500007019758216513014696875227046378244208020728772500970885604091595371825326173229989997851237042391064125155715364728415810139261221462567540868200071, 45030168091075350744927226975498262098593257796543149029593576996866494140799359938396886288089373807478981528977356928814230353365180493120937840896669875898847329020963713828725285056167076769719216947887205947506415175956483645678988878186085850411513100327874187931045987393964927738562296089358947775515, 29095766731556894990548467045109651215631625089615423374726482514853149499994024406710955413763981473188190842667782618942420713624323764886730975011734004351307507434770075331383401374700916970569607586256177949443314819924642878874995732278854656482002987510700560935025737360959378433281884688006399936422, 12383294736527394440925425724022622871450894498425382203279325219497048295963605106862421869224212579881635618875238963873377587486920776847002096018464739275455641652294754510264059609259505039145315881968787105718339937880535285229729677078382036150045365943202532567953317729262784938171992580187607760771, 39001274370997888900536864640687684899329198306403167425648710738688819922354301013109679897398663123376608704322631729800502547783297715126455046969345438514258848397946099593445819453439657423539018392946798905222230868029011543063809690961803525709769944904720107850470878215353165457313797436237427165950, 45654847846771197263648584146473797032272571327382402706921037114288040619473847658946077233787525400115810044883677106419752051697553584152030687303892119562247423972009398069199898357471167528459511728044103083747516118542407457195763309423293228437816709742888407947191388023548896689341783262613847011521, 13514641621839945592184975082509137576312147507643353019935406546508722637255173654220577567262384003078571869994034008653730374463006054540190170923003548279530901659366870279309034855983845270471879643732899236964094230315776397932978154151996706502240192692849351765292684494131745905956986666297904308375, 16646540472915397810507024697200195609411702961367645247323266435887516618435946409948101192035611994773293958656641537597449875226729429017220418579309719103000284993140338420124339679799702823313145096288311217707133825003651565680283188463440824337980885600907269742682428093353779705628951441342772539278, 22608669318953369913591788385649108222042586770002461067072010259169632310582702180517599618436908973418891002703926187819707393701118361544892188490910975926460927933558639858696640105220329653333682199494773577621469321213752027473553606095115324156686800684852205691064073920126101529870957867107557942355, 22290438616108953449564908671485029050742191304298993449715136657617519219350883088832719931815033652473335415069189960800916410044706966774060700367181470866325755080488530989860419484931434830103501632457178013560808861485670993671832281654852074543818105462100248460430475932787435739621539900716802397771, 26313525442773118796472439881180000593413475536670800833765754617023479439041985888236181001291778952241391286493792607180162587699507101753127111749569436265434063234046373610736720773677654299230077987157804813954855912106131767913429520687413056853443704958789230790611937735273191070012394695312248086670, 9718508661832099888537268805172754322990890120472002263544929439558028053505616300561807837589359411463880380432623341039005688820073170655352515165926111451732769988020981166620502294002007015090298301777697677343036908411494902312379817971677733777766716723397289671655508975426089037288122757120264934666, 5198233706417049050526788205974521334958380090498684795238985692484064505986982337666174378303062955907201478241404307321285667215997635510876943047591214872788821396401372751381375303533386533072836846174677845237037671299983234252325761849334576337253979248615416614015899472655220127168139875677055283292, 1566829052261527442053910316080296843709946526955561778914740124294460614133980049133092962994308891210509142505388718327489762450590675291279577300570425114285117628523304251239410814741776435208784152593228801661587621856422999734796527554126001010455151747522697058478610707088001708786113718584825309666, 35070118611683204511425607503296308775479919383288101966591488000935971219221824028399612402241514341588829984552884352496303373335258195902044756922736059103427735311063198948558744626052105156216234163431795726594348751767178207270427392456182539370507452571683055814099654102312931199528536679756050497259, 29922669038910086563914602509847736051569398007403418395551720041981832931684633939375620256163584595334287548217179185754005099646423679125128430936450749930434291490129485057945168260839683946476294262581217453363710448833689742933135265514012814581803348036769869124257467847980081320496667094431183886866, 17571641073858786966688583697629954164684774702344538335109539746864072885425671635075066367923414899274901060948527349203326998381064902000084467806362698818110586741108843470129634668160651813875577271608106733262050997779408426241152558319656265951651870778984539456631141240729156919460726293347636498582, 35390999646774664743088717508481622009176340574439849952854103289790679191930090717416289861254706920241224385033411806065029271117425583211734576033066414475773414608406279933945098078542000233291078473165238953103836333739626645029452684249501945365310717644644837300221968927579769809539848445751323779161, 14416078823007532809137389285856479250002914939050121928299645041946627654032759635161252334445098922924439381681698447120358466233949177683842924819729095232620824094683236223174279327377845501554009120851877689789555502848322132075189867938567452389102843578475252213834029037572613378657591155200473487459, 9007143659375457788124829314822746098789834246812509588738267718764257387004966115984665144364265553688515569885233380614171552747080885574192620609197031033110621293900813418802734109595378258715035098454814410177050067429962634873226844898418063376237336880980779191973031786713195243794180884669136878967, 14199853083277099674510246173940329601522091819111098159551559938968959792821334572167678022645025587874030303109762499968118683138554536516332833886572391589573027351790942625833406730855688372631578955090666857763346800345888213739712042970823356641798096145339438292061617616688650136957943973591142016166, 7610266457660028526560554888210271349827519170536174122588552633962844038049378901600127468434330737947052070755517156922215619401881466147938371319552221198024371227054281319710396836121013275998039288404958482166581133583094058033428781155527982540218820986922261654183933593616089396119915065267437436569, 24611252710347080972123575798263344063657604608070390788989008934892691847209461022924021841911456458538121687207346292154946196363925726461456666310411628674624527196932367768398233769557645818028129915518723485780393349078371992462266583818896540997960131825036180538804689189150559172677457044224428292454, 45568038237063528858335965113899174383284262218026823123036473062568179721472982579527757830768450406073393336154093982315227210270012718925120316273558625583339888126652253345029978601171937672179001895900669497465813248573884399733997710498307779868134163743720382000192429217796094834260957456958647838285, 4819321693568767736011866957940210392361208472659630897339800216087832562730017462077348662978929480031893212022290048598979288015698203439436348598154857862768706046400464432527293598184922394263019725276653716111919827700929866713666495959358799734404579282301412560457319728448688385015643005505425537352, 12320233987916684027719064852031395474652537482196202096211548739109753985545030941420338053685634627921278027781104722563109257883796525897635971497856183773638347379618513321836481344690037454795771602141313108390340827303774374255137094918292739106686027730449465389031971632092078520332062033983343856213, 9490130149626411459390051019517963022264512491627842592474545272977842779679648275046430571236251739974766115427452233009825620247415145811652647152318876080292445120236063332100333512481007854835397979546469890723482995420637633542895454146753695910589023473512567493531247762693422858557634886713498216627, 40057927478298253414664508131469741150096069193234414089273991497175944248207325757542271984073253701472775091306063533281619695877730441648181485895527869329662135036174095950582100277155291952219069558686686335705967354804933760382737489163666692218097336188028300211363534880288712295273888730220642362300, 15917066928082589730488896486503547257949947158257616195134512919870534794199707953567016088468120797267976751396978816113642384081926517461506834167587489866311082933950930929460699582486251329121162992399922206520178800380780697116664985234926023660563448825455161434425919851286377194432237099847376635154, 24826118721874528586019294185386974308630258532229499649639583586572191793063398453752696832443976744966749203639553991292240521096045316910097792284970158641619335278857042782811945442435592285918118344718250583522120750292304932895422518769966070208580669757823119927175236580657087811956697951863064774206, 4452107161938082557611482341435162618633236384542543195563172386136637192570068802018943308903462331733513767096356126338469227820913723256288423352276848953565335501300877437689270020566973339892861581368630762399401150598104031718843948131016408558293051352324343061148750267192650269571538124493266651927, 43921388457538787947571286999916746178021749727533661262592768806073527719893197879591249329809024971041504322860295747922650612967004903528640210834217491813144001949526543203552526234504246100148864305824674933215487271850284623694789925647809043723336629322192884680271926659608230275262971219217471150896, 47125232869104288294102600319880234201380063932807866932847315995496884350254970255625199870727148117602141335241520234628582375882072133053322043520462894735423679052382874402360559735279632588440230584170203679784739804244646982502481379721022412862670068890365075070770326958715991013296726445183181920221, 4819464157704980253989862706985001432989649773218634044156112742049986054401596235409389945783499732669594024713566489467038130855362078542403094810018516528874190475595692188033842342142337468884550228237912388987636384240695649521124010319074813052691630165652521942995840651087205601128947228624451414539, 7785442449466158559778578675523807399792215697274792337793678827199960927903214734698125093405770374247216140467308916203017218876817385785469365039023245932075145266188814707134160523408462643215808872604005155290925509073732737231717441547402964459110098336712806848585958351463250548566884299301752663690, 2049916654595382684390808547351800472412541489338980843777698146787475987400924820318230616382279588556849842394437264725082807142990134392366469915741410869823454828018772167796799121056722144863160071763639266348758088381370134382619888985343204082771265087724039140854049284485441621710127308616906646998, 33335725324064903251062345913712971438010179380806514977450729968912470348600034335226098039487046797332291327702022795480327267066596479539688713361469900211110292084192866332236939906595399284797209050817948127117230299888871742898315167358368526781446787203056929623123860675152035797452777340821895459168, 21926844671281585900390839434301706113936010119755179763701655058832050489631559472662181376002287841428987785194131402340015125119864222019969572262641331594098969426543353446598911628888985768017947315393690475073076605703450943282694015699132607795047733958758749442339940328026087873387229734014382953346, 23841677717054850131351640507920088978210162114659480779350485956754034690099600848285363988190414459215113517711085841429203654863774793481473380167991401225094999148333525875839710053846533497329613837924840448355515878021482428878317788453611939622764732277177335949671406297962763091140660801494969590680, 15619506681459503135550932999887981391139208863979367021194797885858847662257282638671895734788290066662389751512942373329410691189206246373880143767355129209426302704164368117551834785407171764188275127407101842127606476437843515306853946790708833835474109783741026120492332525301137757299924759453372778312, 13526722360006868017239252826137545799700301850384225183468481684194353186868059859077901488690006443210372205327317779381779462375844948991254613871564859233389609177948293384945215499209809875603878386244027831076696027120143948760707590288176251320920725037946416719628534178382687686957309654866700307578, 7437276182299704317994051680384261777181169759646880867651481533122845564037620320713902718362446110826997813918709276550583406555093690536237789686989478295494020969400043858320446445409616708628507878567513132169003675802956847307190298530092062879140077649697897250705803717041441110469308092234419744710, 28395627959125507001403633404172616125938843410893560136794198340837580043520309015997333120606526656163512718487790268292796758420532951306997164891343647228230923041614467501189735641177117278844203554196104190407399924440904312793038839758737973916480114662527720528787912335435115807941493355719413808854, 46913676146519510582162835439728680250012097087044870535339317957127759480570811904928022914750119023230218712054838646751670769920759912791535696181216805786323235413018839654185381539593946295212625288957657546793377548417643200941654777958589979368499685293202261349603594485592900665896159413386371425635, 23317739939637439733339539925510772016491469072811452913198645306100776701902892061582285181087143385472665860918990171124242252484505058374558816572957186657945568270060183390999266907903291777651437475184928981958107112959893301797285003120744570285352643385486337519487580290765008763367269916363456825668, 12575497781702236328580754866941340883527550157902543449755206904590527690300884516436547453980663067503766066940574480857995945121677027136578529166383471102383798514924865458554887784773265515522041517745488712996733154668083700835493376836874609831614147075528376387930139159368102044884052532160598638207, 14641567315723761339415331775753302681807625890854245349769655335972140667762789416277426819895529204845575275423458668572710797895974648259592641107008148063899077193020741740995457663941913962271998814722597894840656851454242895883324547130377738413984174696655974458267221549326883859710468467463900588384, 12631850894482452139446615317618885531851775288654856146672634363523422975342051461675786284400440719535335285369626970843557453852428930319107900186891806078034470405463383973676445116354461111017384054234189690590781711280916752812681606585215356079650144048781550677361192986087770535878439045875733442181, 15634792548946126649420795887999019999506932071707133504353256560278389509774836227462641619894219777022054470584507960692283585780132754003114289276635584373565908156419535828155320703938871279888823185997775725818083300524231885109059995050683565826415962010485842285277980077434730386265872251881682760293, 12672520194633546160114886329051162596090737269476481404895380054264047828699416553844515224600190581461655231282531261415291509667281594940670977652482270056190112848980978251057668556976438558787253861994951549292071722543154799319897670838556552156722806900278546215556886427647707776573888380747042711658, 22226786367812370633442402577914099792811326514747442973236688545824267634204168669436721843750397687207399379648004058958543133246725478031017356295887921546923093247863296741241653616133221623432314591379687509363878065356313124128084139080701100918675297013834846172882477734889263569170967553848893770741, 49032552252081643783937643327953907716296067087602378912788617556738169002930610733052178327907740804875085580142903765464332366326481397785581105502402490535595782545689935535079241766754993409732523414388680414581952496444429361299211876351130560000061461045120117616340376515936320096759976670347531197764, 19335555031210553862793316986768248190511990839984653015218911544848332569168229086925779675895128964940023222073621776025316811166447418123049566141828199287786807445919100046434776312484090565562815054137115058567240822058278518468941551729360141041620354130276707876561902330463828657065244092168907041097, 24454671955545510305380936062287179770478188265908812386393889619669891677801809459784076793631911167835569330685310761909515335337856971107848776895204128335659369402795030316720545502506914290673371168418812908037157684297472563523912182548307720298468697480905050601751669990874104245764214659503527193847, 42995283160098965321148831923966517200092071680376231028614753809039744236247766613945547522617242110252561746003723795328919102286057192696062222912149399515313452256934442166490971610249641690202753477199544017063912866830419941112232642655341724916086089793123145389001214428974503781786441643406370290515, 36019637340196420609817991867649355581155485381516119100760116319584954069983981016301289841798853793762763406176229013891820846432404364584281819606762537640525102788687999335218780856513149452776729591423340810400662402816136721810170101501008542886847166115667209623533777370221991960333391178217699462003, 13276709809205855951751069985757771264884639353189901553207926968936800287156085683115923867380328932983900816846989908884248700186799074055866215128136984743909052664930789127226936513652470025129885659431682050681305947677469095569669029779532721975963582601798762135432554381684134583679106506763082247740, 26574360495216031606540292214395307908703850101916772241258937016580036897368779746910822106702775485575784146727179634257978463828309256900787614830315691272472664629902034285302330020655565692340029575763178961011764882843783140029556766991517664475756148721813232185220100344773877012795108940601524408035, 31918958097682158453143311270929672690639586761023867702748750011617806884977891145377628454542525931910821654890303495340489861682087070219983604841431466352121045575914775065469618973985071354713516618850756086338726980370548977603244856911938444324879687143328060192686373410464200752611451684098410165815, 27330072316517110115042666128269934961259029238772890351568125540788335422478528654863191267460816830660312672625114225347932580411326965208060524365529476155844066465066644518613166173787216846657247470367472256366727522020967492123323919105084270779563710297907950506499778036737988935428518789788793936030, 23223086029138115149052023910142687995866476475411940583366231630226972424940400973624861318521794615994833321549072624695737153974083591172450563925166423613781839133835093620228357120952539377378727138497308841374980552571367630596992142083649741239017211868302980350321368219679950421577075793834783332169, 9579473979553693596815283211110997468229809846848359583927497661974854609743307522445537688569325182590665162194499149285201063154062918574462290167696338290522558579134109821287418199452286671995235964117949415829902883249275010794144224565877884588422790096097373473180689624170364818058093121420456781890, 21025503151442933453003665960299535590345762475590510062224502752304953051367460694103094835272384852828361161137329631249710351449044901768468722513730377918466116885268442865832396044494204755539121983304261982744955225347848859692643986656888785069175658455840962324855445890407431942778465546728703128230, 20173312839615462252112405425537629534911408247501923309226178085945729872301493267833257848706670275829901974916954610277685153783232809974079285202136392627345324991718317790898453330975200409355411026683762891998352427309588341241146174412435684621354619745593885505122023945746316293010354150586786700556, 38701365036873536483851959729680880040194660840087026755549796191082926136332070985814664457213461536382177178645868853627373139725303919122219490869897625948130314156372952697504632386106972307085298119454128773876155924402927562284415847764141697668985414427940023823931823070696017743270444494741158322120, 8037553997285622284016976888591854039660883517994630886406514742331390437720655670806232856928812815458785188910884123566893023085106835080984206327422715031635805715239438498738657617099378586592085107617285692065966481979283668323000058263152981034819564000613018916879113069529839684282004351869809800513, 29339337015198828650420232600724397518513548835552096352218799241737894101579959433041386584071105106879967421920249688200675152207207509223679475615728221598979440833043848193684556620140371295004971341981290033182482143998679363497655360764848674419812864541691317190143466409893368948235401603924645102629, 20776114507812039643723169341003164260929238503835798745407995169277565848211963783666001993573543012696197690943914086624857042001375339751270791421610656411193834438117416621526263697908815091346766659122683571130942910319277804334228341221922521590742194125792647658573845432930816654532828228635332540443, 15960530281215910165285860086768823023113842896618888493286476891303969978847780448939975512024039901147406045261109827688858563207498671761095913105748939252288910281346782513003859777181647285147759932906540382059975438788696590911661145917272536209077922881260426056555520622808229565259653641883052055251, 23449716711210484647861282696895889443844446723994941826694174472483766215353190601775255230495432676280756647510021174117910934369990834689209978220492404585276694867302590006028625032028547875249964216808809749457322096670879627599834246893056612058073137917769906898295598132015356001404542577461711067078, 33605107656584896149355738183637949728848492452726144343559087642123417364129517918141118948184507722873309967606872860393439326613654230930980651525913890462047462763003782689884179595676913600617421026410209340658427580937343251779868312356818840404737410880252694562212466849722199090128262876934501724128, 42903094562484105188390785462822770817445990447314966473294513223793506356165265705011994070191730135606413274916835775958132187651088035142490769205237372740453539245929807768008830571652717170403759561289133722472828733970163219211961949643495796517773233999784691882135164328947289348716852832023578602349, 10630175745084116455853912296688839930364312498278626312535040972710433517324871798659904121451084943005887925388679712790415856177867608416455947547660257594404273388337868889240617776291555839428097088510771691805056843041475777644918087177812499002041076551950843350095910909884602570388746488520208554035, 30509144365194509096752703429492220079925097574990414032376330604949283666640047726633048616901846211822509934611402724058916374449024525799175744119836224589561246695295694480478969414526614870858449735826195586630895169062746765845811201988692280848319233644360109236826510483507353244305150638932045552507, 49005908148181716739814056065234529746497374096425078653400171532245317114330170890235082062383393997864780677804379535552885218040956874049418586734021736586439933512102218737727120785000010040853083486327329027875691272108218555879835195765178712743408497701386188427559382489811638465016883582991682775418, 28178489815165107693902863472009101513303245162841209685436441338713368127517152817857364291993920475516480758481504231108997257851520669242171783685793163376907936828249880444395781686642148921311837786381028478485110462046262246663766643019633254633643475117964340494517618367654968819135982953633387850971, 25142191054496832191039674078301779792039617377174297614915369952430454216384777309241307339072308779202446298316058563292759301809850631610037919313462769825454194532021598869273264256111057200168947969832673767371609007706593072667195837928330758752261630255899974305417636954783396297674628973247617901316, 14002760882290695275275007116689845138292411043970693280547913072639975461439836289426635624851971038499369087972579196259735920764469052333315565320127561036046968559224302231032598284720090976967558688588893467144246007594063756046910892221016534432891081930157641353145287832429060506148469420326321055085, 2144664444191928519065522487285227941823786830668804835948018164210736266117367866979860035518903837515300749036620809746024799429200223640110741076469373519138615482792112770350668748262253489193084179742284964298668525379473451780953826591865614125347074280106072720381740946204276396245689982252083989912, 38113997836062547264398805664107715287099052097451183041451312757442970371133209285626081256667275154665390219187061436014832813811744218078226257091854737590137735443678938132709949297187462651583714306820331302406821476124891734363576541770558508571575576063527424549844375551962473693458257312421002816683, 22741824541884775600411048764301100799608719601885442547025637483898509154517554045787714655321175061309094456052024641240458067966168289298780519396542946215018431942720503477549113612432607445499173594871097280131763392752955097909882818009968982718374702878358257962198705468694363838971751222294591854382, 569729163228679955908173212960304766926190955542715361379643858383118779854058903232694825510362503868128180771865384581269073344861674570273018361228407894968032464099577469969566276903770242867626469017048058949412881013838887782624496019307570925412053946411667416901628193637736950145012198910366623788, 30992173027054867364369195196429049954124517183387046840354438417782772453531104091318699900512815137247958914935759151114516870865757629729790648676453463289030166459351473570518046076163391200968965105439086913866702623802526466009498375703781123327565912274012384149329499763813117670265921892398847141788, 40233973909128854698684290565745679409712024714095261446846056473052694081216320503086634037766343814494831542945078163749240956242077352152194031092418884013253367283441782960810944089363041170877291964264758932330844840656437395170919532756382168363671227619957311407193568045145782294788833552091926990644, 22744510601809983651886194851561382712668202492114588666445557807667993036974149816788466712116901537619100678397064469329384363370972138358548267051805253850915903226164911460771710408363208552255323256011080166497718117720386974468884047828980292395537898385064409470127747654063953711390321977941314503534, 14937729270552648660136601332553956553912189103389103246693563550667135444821131940091743050883602058694947197461644282710922808772898124521307139599919540157575752919853806840206010363739394679903729791532356485552616167782500256171446751090605172184911139375955098387797655234035115642198134359675691846173, 31987397963541593524844349802719371789055313157232376792164671243643292931628149537770271560917025633060782039274720443266995562182097524972893036149573452543992160968820030313826693980106199945559482122561549827926975486713924285213037753109163619026172366443309309343908639537886533379470305245740630468871, 5960967033589209639588214635519333874188497335781260186096838367763525362312356803700293403695870120763904027145483641584098991385355461093143455614622871834732740610604008377436224388451819432985458003751901423638997028448881979458988562118174998761829952445485363541086702305140450061610112228776842566334, 26416688012066968547269445977370734308057702052652948876653185387484449270624905729635201556120231464038501101806971371943229557444975709831387889965933482009407190161963871701383787566095972147211933598142880665308129169844840839502053304005433861598683310430072872561855405164414597483594125352374313748735, 25016807045229543709112349554432121360845037328166263875424598554839232741587439715708261282401001912618965161298855091444622397357555789356098827835016262438167669613973821092839662350832663168120119200476290144751693759192516750125258562004133210963697728639522311047191774189176621721225817451478875491213, 33684543976341329459714899677013279065841491985960449916747316509469440550054855231818413918621915425535299273921422107858176016387474591645942655977174565456232393249918815793482138960653745431533284341854835832318846417071835956008081159498349582907304629139230329069858011078399428672846083950742082883017, 31716121967438955680611405811273320970164548659410868987343866615635808825585566051283565046879197093761615305459845068188363681304563202479239203688986220959018371669317594211899999835134092121969342630250535926744658243345075184913064977276322293773995208288254028963325694377120761629904018360342335755154, 28706928059686990197922108722589925294466877042472169711833305958389153422073641361672558745309374042939665585228643255713355305578174765393084640389120140661833378527267544202578482328706709524233809917875911395889385246397616309472583256155018266977585132778292841722735756652592086960891862143629787349358, 20868329238051618072014157130908342828536410523039022414697931232809063769543349651324136022523045897440058042750372345423052373485269178154911752540917690703984947407926706071446280575020653733644064801997751608522260182700069861859239515757282427560269411201548879325058200182145798903033831650367741311568, 24125168361218660191456576125615311430057527349506930680891616997287715657945904594449193874967781828130023846367799464315791313134968303084998475035525361382830026023789955780262807271020763368740398274710409517527888237062572536684154197438635749089050782274149515595397212041311819478061256033456367050110, 5279669284907894286457450137120673609907950616050116428612340564129364547026533377501839755363634006783284518587776351911049927297448226854820144209936390232465463210824971223724065486714915074281015423809913434770528106823497761509614112352262585305744518424165030913018253711258573711186443234628434272461]
W = [43189728060732263546376032573024542914827655835955777783058868212372782311345869818185026232917545884098357229920197134243943238474820103455643184758798408023732191841644095333069856663149097127806034231497808475711834894541648557086352517442382251562616409586469621031515901349604969148251571634036735249025, 14962335039269846625252211723261183845270395619801039190744690019901645055422929998717991893886254094862274708106304533843826740540797631423953125585796567308364473767735747660915685493777458828007357093052488211945951581853974924710106994403758790123427195883592412138852389811184834260972823996770403124241, 17748434527808669590363852190042645266624109140772455723470028167110439642963291101327996610824100919183285713951433823167407819281478730577001182379623890498395166000397169377430495137808569771592109229411337008604346314524241321852359866048384253259386130693837149767871794736360662255694788216246902470869, 11963461533405538944903175511386753717056029095862435529438842260220937567110650750805058478194636978730293062181665181380102751824368434321726499436622813091487218712241177821865101133989605281456610379055384099517837823738010184174522178697405855814267193496679678042345682030655414142714554609142314535731, 35207422141667164643537562671571562295538172251658697399361667887943157443271137894880486619597365479462543221925583701838986346193566895904695849247963660105436594982844284031154385405284568314863041731269391844774166002853962574857072804521215003484376718303102778949166055643052685099239191429663079607519, 8017123881910708699371833090709208887283186647394363912030862252860260537214926091886848610145547128429613260958199577728943114950171865985899402168536819457606904848890515709345080822686387330019438937509448684532208728135330183513857902800441687916147600824609590362312889721330882104636023606018759759962, 43667584634392258138578731042150067963758933670161985927873351504173419654587071385230749239685467889624357021553994279628434085617018273067361261230037675088181420338831360656785163279936366678455657476403338579319181737890517570002805819210516600185847006448996558777084845078716886753707370801132601974125, 21752797633789903098556977265332728954536954155620906112448902355409146805787743989533364318908106725078785432633237916749149907791295493694328305128620059034727397113120597311605302889073776568528253541567842752085028179351662206339647756835734478640207919169862953217256912008681796269523212528801093393101, 17680934145618253565784915521820798937964900689098048721935682997643438950660917059022784267717614649037749197694175788103156868053183409937252098684678247885928795965867108793783556697208582341947355906635664516292956345822918216249920346942110434380796818309887673046058447572479002026987252122134063930865, 1351334461323643682793529369003886057864160969436984692618182723702253712335303902882833246786829263121238026931126872966946294350022046295285953138148429971222772915120538660236288408132851817869287689361270382536364605961508551582079540549174015845900419378603030351570505354632536512534170982175594973631, 44398965783668215246345803985219325125242992151291791214766586175260061564008644034598013469857615316762905389055074675415013902317506206864145577948191459384177746856307409948539339085599442351556753844040538710950093590747888021736781185316814990515964240529635564252880940543497998016848118311241997894913, 2721868508097099742775614856961317720966791554715503564939398865542068913859365598199372647828680813059500473797813652993710369562219662708038874471014155171471429222592306538331772739261909004694665769678717907501011268114582742233987394265403616762724568356221981934697004565971218318957909853918148915389, 47303310477527648504147354312897828048602104230752987030164377622674673551814066188333651336580405990069230658727492483980814098081271996172452572692263803103724341088096027791628480048507690356094190287571055876090870308582071908320503129113733961416399539559037703687711977247059653517295718736647567563974, 16049953578503552345846170204030747311857588917777214398599850022089667952760025737728730624240568754493236053151413843616967222672399768428002988774582385722567449730479407858647523474812628390427051523177699998935012809865239131877141966835047563995990348703454003232833199635834909508490877637538091311474, 22893360075577786222692880277252256943283949991491913917682167475261586921550492727995590648865959820737368425815402517673591430178799785598442567803265822031910418971834539618872695967619252856500949098166335272353428341730073754664886170163972900485566450150206302872730858728418373208670643615753991848068, 44914329193889761820371468655910135494452984136693717148807443419600973001486977255342048924429910050118240197339037316823808445129416121592062995769513281193125487070761144429637824126690416377190792770825971287873241454628034834570023678764095698977833035467127606827859887768288108337227291322594772209753, 11429761501824531708380571921023716657398989228514055378984299156316029530976352094391933564741430978564969726187258339011690990235788309355990173248100801383948565183745751306779509845629435580069039068205477491980835252320640101649330045547080978063065698740547623323876875122985272347734101546618722648242, 21066618403394808383171121119515802881312940924890200914585278330778092678800494545120732479780563831377754509738419403114655009552701721779721428180409032873120798893958481975928640118513805779914920479268805500642988756989947087220295924206027397442238049444510798776469425583480236296131173778503875383351, 31688143881773135548330234283090511139303571053572970398050365339156994300014651223212969739531697688702003871416108799186660539655749762722516465792914602329197043623204249394309398560538161055346981565427356281983923713937130934090914405558056743052697900399926128960787719320160058702239025923585682899553, 9422825887946849855466807148921950859831215311010931332130194752694503045349910304362987825833294391073705468609190464799743327222155844033832491910651136085590561734057180624492404167508582584257523409775437011096208916244998916632749630423430503130732556802020726810751455228018881135916918255899769333347, 32920205433669050092978787109577429693191205329210281848897210762851135741859779529370077698542191993385546656238312003747846136205707507310359649593297725195279085723759460133887642980613624399450316482913411133720382490237265937193838629750298807461523087161789184682400327336382704926769448019486702233182, 33536185840281417675936994506417660341108849404072531235458532331120012353740569335244471946202376476592113165708182617894623586556418063009442287066301531483297471780891129214160281109218340368875024252273848087346337015867744632170836308619671054195834035773673269453605504384433969523643499812326388391843, 37121258793552341080709037429942796994875687089471319023799733367862165204628533581711599529331351228199183989564042233979588954710551867550759760593135548596604161322967321442296643293078364865187868926667452131467660014701290099324371257324861723757402479917403549647202958784368530641305064176711572415241, 10050489096921030010163651842736662241144812111809089393410482504144302061035707529998398235372714656890688834481130766767406287070669313695378776993509113521973393955902809700418295820923516920814601262353799433584313120708509280808880702376126719018493816655303883277706687604320670412021958245468837417522, 5014868023872113728109334324530571373502697499829427770261865098807354457803708923844149442152076445667620625280885550221276038387865259745426847628205512882909528342286399275646416462143314522875679221861866605893180099186038456196410737298094050974220253373528676219902740693091319862009843771357463324957, 7755761922380772694276295941287473861901146890714308930872828241441390197102804666509406357066009755019179231381774190094855983602007860933143068730560498879641027253877550408868774480399733919626942149731455121890607792486171109864861990109788265502135032393081168106497999606049985687572259135755707351284, 17450107366246207128708170695790915799461464243014731674942755538636064160354460214529053957320912030566343295101441890783578449945628570005320171615154013189197047399439418470982274268363835595224719910121361758169319634540493426435545651729042380321066898643446344666423068753243635781629480627961064849211, 1405100728237389301598604124950882607062996218049632681587906502261185079307538435385904533528549035592651228494143320338038672773363955818374457126673407008996670557285153156527125148720768561673487788735284628155403464879333072517652030357539126652492448391251447000497139000933416850589606985136088016891, 19029155064595159491723226272192352557369543207520532646369575782012470651921410984015245805689323392631976761064586697487325920311248542770233484628740210732111045871972667855133696527841359384589723329764296050144277000769164903809845867259208480060971987556314647094570231864444764351368027321054185268595, 46869183188091074442686188084719341764347449591081393274222031175533933472275520043969962837734850234988624417319910259159133276592361713795660963025477897689091895513235790397419320482976968463844483561549068790541568688931540338792824160630986559058157332948196002473003703050981753537431096034210216832053, 49155903313866110897752092521753490520531018410558715959036136447396618093844528715326643676244637119902227923465682722723346747067700284589309746625904077565603696120199220311657419054911777519743145700169527008485173910785274829838981454659837186693259674549358984724581625846184127282221894322335471840500, 32373162891139372956845302174536565176642588819513835244406829501328686565117319356786319741664416697093093304464793673391721920366816629833171898841801322469350102953509976380467552265973354901702032507238643396948314260460209314979656040198548052029217324775374664078437920360401099736878994836112902017449, 40355347488007397356056946294073005153923448533553643859796918358010286068255895439689773035324667362213592315236475163732395255960445073818698715413664004890281908130307841181616103032881967107549526639384239216946763371061830162851465792107924980719698576938544442962423573418600901839125426694360651594185, 43679320945263446393961866232506553621427272451028793983736937864842387659196575467619000438838808785554851954083178913271836491148228853436360608175519407117030952678133341725356069840708237940579405552695402260218346906103683325422283802500799979865025968857340415557549372445088514384872508022176625358104, 29667963632085469081649186817573213762301735532634052198480299480095883167670684459091216399608532568829399088306169908155408145583618007942654693537343241685969347826476118785406189398927151066147363376222109209638416191183828893776902760134092295720514389413596080599920091326042207982044895799419074023322, 25965161881709408174742985764529987452854635150001697131253879448723383743620098778447040348005621142301340080917198484455977330890054885186099821709575883097057733376161206136623894687063502785658775189182471023258660456949857901425080896368104679838754632950807720856634160339694171658230424121798006093786, 41925273442224985140979599545243188917437189148723856672410451590528614661393879067264783443444720484165190170733505134205091260654230677962557332562179240691083872212443664028292935571016707600822102787062546647632309908448405826157137777782791092249453297274648739582899149032680465632190031511238170518364, 9037797863269597916563697274301130983084463544521039018208246818176641158024043859662330604363888461462223097096931694033159038733815988138717110630702883789740717125725203115634463527703681296289186465836056873600278838637101989063034605539462511427171429087071480534332157491126842424871228875337344813723, 41730284372681761866964945127822650899240514724720834476123005435058161661131206921160843607246066437233254968725318859029804170190232163714466456100761306268434019926501137690901937127638203848501101557840655457416672610215856649182105873376370677615242211193648478942011659049938039944038051492950954642343, 36840567487540951754011444312056311867060444888504512790381783407527270900060312343480385142186224250014988111579796591392438410491760444229120194463887654919411968745477231992110291459205790498190080071245191145249604314774735264806253631753176959446403984002176632061478642510885796697185179437199856083417, 10268236963862577948047734024136983396149293004795626657420145641941657230544725160513178683877560613137017423250045855725879540110100717347944482250788832901089469080753883891653273521003399602344534921524814661493236928278121882093147562538374230501123591261928918818596421691401261257918681969273736593206, 42810307202616055060329863576047689822955844291326897691774069972103438257473264471124326065547813811164565372128313665303044805252266565168424065780629066907175591561015162408924408430509201414186990092530468249842668177897341787594977490474588794250934034845547279977455950107442289155385889741853615082248, 10674334356138020009700469447362112099528319659695130944653145238006726744338046197451730768741295090392996260019813075106651530752321078783661051761116057941311752453807130211659058604149275635228218138534400341229199316442269074928318769266821327942372124091230323136807444680475453877000425543871647771153, 6487928949602132546726589188695403383772673829893376578179990223509121136801615746558129053327293419778505778728037170555398255970104118729574412879686565408076950529323025102951598688453096314732664009436058581752200900336211125712290484275947368274840007240394345255394963820548231158190934663630876095422, 2278221001488546122162472468650246730118062282755742723863848214039567382824435695235124784056671310762521766923650769445342499654986392814238610281136854515175981983901978146325339374178397279454057619395141657607880961980428681866169242220802124889581845513647479125182765911137811193423718717541797481951, 48410869909557667149655352715955790139326849376239449680065601740203918358748864675223574885046790655667494905194422246649233047087892425409426257652519490611764527033524084265897412228631790876550522052948298098779295959293980978864209607887075928009247331540953436458368057780790593542330667628198553004373, 47292157327572865975618383638300427817081259364158114487792385815237039057293415481611429889154144916135593587557477815001693385435263882491195799330523846599334699704535416915308935458519949736395756568023117730348126832057266476788168879016721671575143470228708380550913983480060259011589110282896901854691, 6190811132064679113314911768026171389447987222736759946343619405407408167181796509501107778154831203359447193381169027686713107938551743820268174216410966630535385995344523015688453347653283655205413907651346371552314345096662245980904545711716509327662403406484797681631513773452033036021449726358028031188, 27542865241192758945674280953119165995733752253790929644645305304241660495137340308443020105566307940367736201729614969107170565872947043999754759131251227233536114758177518063733251835401668710733249712629361842845736351971271861358733139308221249078049298642828683737414228853666549568485084190045324533971, 10862546510296195484951352264802497835781648491234165226826291591393281806303419458318929099583681672499609378829003109113185459224781400352500347698178191000753740272544624769248834486089142998546483403462555970645956728508802908236059534619617798565995194268080330851218445841844413971581928217658542412376, 44333441385889039273538909503978971731671373525911088280564563852179773627468390842936063359495025782830290897965678421172512617116563803025471049900336440243940522387982829586055172082861555021965888836277768579190698331255333955866592533251194756265604873346453078873902473439879548700306883467770783814427, 20337530876139030319389262421973790050026542815022270288820099107271577779246979035938554183903982813234731618864512085013359516027777092741716932313704218971253188449324218590629387331343312992226702119895817717777402338305505572397138331947836031325712725204422295901255148174359668805260337587470043821436, 26828382654783478253517214754614767944948832774789878839744148405108206312137346021526854441504440359024683016372238581230188537198787558482134410511766365766654290535971696152365943860433759917462165789694650037925030388562595113002523927167162863844656126109039919202701047375372281222162177055356313357690, 32655728280105271757596414074840653622856213473311016788075765562349914455900888604415299202255008249635300415697028136358057282445223802039905419693420789161356993399619307938455096003845096537805935674799196102298422863491130584425741893590119832735810016807712842397398649608137166373159632781742273635516, 11592387122810644947186541954834290064650979924536964101058691992296066469544807836516967623424099478486717628052653810219657365283551710606439853733869820724324918807788489896231196041175916513617059055266464929404763244984718791505530476510789704756881489395120399341225970796796763576470409303158195079177, 23501238131484968254479922290501357599662385127744608386954995627309889594930000524704750583694563924845145521674863754402889945887108160513635225534294856002019611934351525558511578306031256984281923444680501272989039243709697233791008767648002423645282257848910151138907535246342940650335067546612491772193, 40120203464385174042419333112434003927930065010916299984555752388188318525486870346756266871253563855921153701013191922156774027611074119990860488969403388771026650179079615184835196622907391261549240703643510467613151544125633844432480461000371728504828376564487644980661367158072650942669732918621403874073, 1353494041986032052847909857677287905408360952690466996975005489369664540346814293824444123165025757081931747645154522274293003067460463433675787898706391325873439689924095752178486196178678486219444671132656486604594988669748282847425473351762728935506424912134623503365243780472812080897948385718431444034, 5168593185400425978993132371503076772199015933291482340775090639668516399432255590516685638321485581941663881573837944013966532818372038945262994674990051277358469244476236156442596476635663503581929597154314610310907430560971930407997339429495386917042753345681552201682403660868583616157061954344462178126, 49027310891078262997731928776548650326701856846920874966793250860707339696643346041970536376286952630328434251964873398571427830198867953273287958937946677439433301272264714823004973500481904428405350755061772067242082719079745364243063521796895337367529188051110252000126554814997026393168681143144147547804, 3622019495255601101034766910804519437866190590608835109790780685674108557274099658079304432070033827285714066064149204790538416436862173886505735705353977450716031266379717217107722434395926899291682376489753574277995625387662883371865376696835765978896025509961309402874120192791867716702367082200097415860, 18180627873608615122818574345168352600957061369054921880325435172677437454091642723797451362624890707064362313750025666035504519469971152938493642957464835749827624469657923654904266701949090872664691459970857059336693020439142184415163691491486427784111304170582927246475303647306654990654536661762604122218, 35555489161764442021329805921426915451061631667421046233547053115071388494135971250280981935716368923020195332176807233345863322255381227761435060206572000416940619435180247835946536975019344640067039440193943306081768779977829853909596669101408270268624582199851029386570823715785459985234009777504871116854, 24993295082449024542994422529912287249452985846727613831247520220963294586915536968731527816867970062972107908545122118231510985174208872927667233190558911412307315143030462491713552081015354817690023464088429921307998075900421613411019034388977638499189556343193073100596271658988127394475216432535029938281, 46418707755393001988414094680696457490134206447172846241834825600842962494206661176892205735696798619051280331640819877122972069884462058671156197241211345397545688241519882466744006210809986346547719665104933248604048261078473947454458167824971348992517461516559700939952143150088674373028067519311869333517, 35515149069199846193267043445993221013889357708563552463728290288907184773375106486181196767619028885314911294467485051186305557275068009565461696679739512368171434307544837259560091594390035716703360161609706782237236261224399157465323632751639904322772562749882045292626847678287550909200310253708159001923, 18045104573824500208348977120366137335305573342823112169844973117150545706348305904873049070433907750350146263722496493182930489571344555234081029139773196994418515490960010217609943562750027338480758618632019255588017360233359701981073626232920419616635247671163444887812425803944716684659532965150496325623, 32654572000587294016536724698162482504140848788701457421886300623270963939781965056013342628831661328449136360224967754668796547542798336840601841097524794567249768624544724746245872028248479134164980689395090812999650607672065241713043600096192851969723842982799950123321718380920319530210447183605342521100, 5944932167097741832371535707855242771445441882748559712901671894278811896260866837329645797366568263364652363389355095079532822130205444236410199833625014313345560752871178343095072803560607558679528031592779705114389604683247292803273052696067928606678077256989928805765789229809977042224072193147542383551, 34059664080453166691925889432236963746990119657984495358915644639393774916507324412694577202247414961618578506831605760501048585163720844757532278152706760774086884209294430079702358825676037475752765586560196107632367299550689219149542629732056091462845159053043542037262626608051352585053121547646817508151, 19857438137938352916818785631359863939280508269053856035454105688026063135056312265527473573509487873088982025199186356459013164807031515475406487682701715836171803749422404143919424948990580939773975415436320863794096330920783849479624510930370052428702015549989845929687504979478135815720264642761966877468, 18815199748740854879799822524727518739754429945485919320879586615033661686125539965956763123333302410508487862084432466610104222458714635391992691419449098222277555348784995925952134573731615310942340958825495497754686863378039850454013527042633217451928058711421717011124921420916211933297785717541354510228, 37911587732290805909192379443742003047556687038004714612193642622330138059111794761303692605764664687804978005910058040580357948045068360074166329541115193226710420603165305947988326469950069841418296531010326986782942430319659591274557448558354664744161905656440853777938135837022688021922485946886057010974, 9455181496183850580971489387482472391273199148185499048017845220876259507027253138678263690835389894178417923352035781796130100116545690945407056913262699422117802250518733002254742693029112292181818600197554445645056874544189475701849100110002777984968241026251616707242850456587708650471008557425809911001, 16307739596434468014678243444304972166586590754968760505814014408226265969432161481747043158626122144000820158788256339113664410666341552232272727990669997673879968704200232198476548795771824725969676482823561054549828741461474308710799009447955727731750843732635198176906936570919912755891354896080434781966, 3559086079390154472795600956119837158300882984384640677550473586460543966952392729518806908308406933738973846303685110734686051758940148059497363951236056851628407438688116112070114744140196984431612950484855110544406464293465177917711043872296119006955496360424315845982684677147851174443980843075356663795, 41133940167019868009072956470402781561028499557177819180267344708139752869134084633778590591799190685457951075426458237007042321084381698100771968168672694759268411461574687708983296481492436122644554257845630417613261064317210986171683677210013630619380014916708561528650072367668689384823959684836900640993, 17814474993005019094037705097513806214446869825249929000151809833223021880907480989183678509144884101113659442774996856948928450897212092877757923423468338538327047133930302000086637057913494301983377099724143029186634777142018413830422740198018363150607220219984205531863470750060364258407942547873601919092, 42610568046198599407140541436359092291579003357534783514279042775628663598614445958554622403081064725837597829079897143996573748906238933310783202845778040216516385468547759223158058372133614939485266978852350470096149391192982653368652580150566975410317139919080533874940749528939191692628831167940532424401, 7982207265551131909632195330171494848955376391965276616879289879945188418306621501913592165479118898837501471905931147088451009501146398139836858592463034454700903564999904007532605837032457193781814104949742233322118506924301944034324521001572318639430677538663971317526239730062560902402161793484930581871, 43079508483116123451897329431375576154380601426619998014953769288013442850597592844076234536108844872389978135301098157642893916062087885231518988490050219246316604234539137899807182397959624765841622916254122991713230396652490417255244975229289483422207164164346446458208214709515405578068284803927862759963, 19599951512847245308388630746162774035605428971952301136218703402212953499707784639875383282084441070199806739736239535779127226625707664820297035963996432434883062584286163323399716213581953103021121110616222504613024879545680861811805247706573320789715783827772393131618638948907039939434531379106162512274, 47501311799357625410588542559800216812885363370315184879470040936698537885785828705433011592491271297819422627584351664106694827605617483835503977613450050352396713687657658884153801002052214306923534873861462106220640988807956095498178841962076771162877547579601088011005894547049624750004987015022331238670, 14856161787846054577036176377508660635840279226915906618180327299668808265782632529935703576718594573279141551380556150425074568064604327096102142992067956845344128911782514877694973135128506735498228296585798187164436633076026393050678945149020432562641946733450368203156780067661642320798073953282630690462, 46800680073115762706207789890526460188040382635775200922323614284712916141937352136288532163878831374477374800780455130105977010652047606227139835677540422760914936437879523438638710725796036791894860893211555120460043522703314543229127931199121230421862693646181624029001280440585763018330900898623596728499, 10013984420066630831198807987467561819636055645421845447448469376309654111738034551801914796883115391769709118564733814809594319343596802888191178177417761773421477196562608704565845604381131557694588052252620188706589013567182315107144713546848685100072335507538072600905893432889576749587983932128737595720, 23347366833488945577522770190344052463552447290282613806217776572194025199796325191717650898738332461881596628462112385129343217600280476582007523588515708953028544570720358557612052103253575447938628365783570103132812736218963200048170267570758029638200264790853212579188932380947257145861534109566114302153, 25793253068634215620209579235864512266135062012110338473771427633673859835565710846761651032529981468457667831319919439091006575696530089313847046551406626252852943609638450829634122332775978871709152805711859053841436148228868078563577893754911133189830193907412760606482338040605273426392081053377916634455, 10808247766974994471457917660358707065931406393637473751144008453963044724285218946611805736305430864540274646345109797095338409197789707266008090581220241217942937131802002202668669978719009743897040042202743540793709818969127157528344420632207496282033030945334291803646856388537304974871293738866589338432, 46870694370092237031685317725537229415029650116660379294104928968896347904569924030197388895467574099498413587824855250512474434786887292179700463968521873900761610108358570797204856521982153266759917528728580176222992776866039012185694041222603338561899261783277022720025299301587562857966129234247486514265, 2595483077071612307064755082875717600804510951438298044567923169793372546637958145445954009207686512826725162945711521911894411940035321420336246496779394828454875636675804509637851107046739291304185683081469491016223401724512173763196834065090184814762178818355866416362793036766662423988369779215140800713, 25992373926815317960271031851089395034139041206315068154859351030873882623953461886850688564717908326173422909324420786030546905892638580614623268482364416037376669775024400025613241631565223009180134652817034969552684001476124296268735883476788514705321103042923941875279507496422149948281373169289423214875, 12529883610352219335323673932018159972519206549213123817117680769650484453538406647592296137662949225282152277409283798569120081504198672804367731346502380764655814650946673078398521686904014084235983530511725308078323636404560131289912089103458074606666749733682587127194351122150840743638724451585302434281, 47134031967746652932218547760296239471832411535750788181242084298545339822850438336961855321670635008584980540836390405980651783972567674661355974570711169080655729007003171351463468448816287409701326836930622340844668328053025540840963363095398122547332820213819811716192288326257174931717402905444895473804, 22030537833922114150693500192010761599918122381792179731888974692049341255480730380924778595781467634955358718544446328395187672191355417616651394662656822037000788328939227973685749894158335873112025930944244543444145387597658460430558596274682501065373275941902143275969414903907548106844054475981956928688, 43883400135613086617315986019909562148364837191141077194027575455009718910298385989100376359543781097071309432201581213181114182481005198133241301587205316381986148151777763134183966613224027154605176257589551088066564113812536021291427104014377325829281848511517613575858647680304197786144326616968078238792, 45733366721706076192149315568442563731937278174073678736476522614230938784730170224776882758678980299411221992980336084912525391184727485978916201670680990051022225205110096747604504333291556565074285678270405527500948148089278561815347385264056433746099974470510257601893985155449849130597315047673499326441, 123142244209918192466725925319319433489506260121742034158465076600131777756398288272944537925745491249409773992030221957508819113590118045963504121027850269220420181032422868243183513607917795249667085471415995269400712891402308055814501521685311633595463441023908761154732649889117867153969737374465016630, 1463939650201584804474216408407951767754939904084565286352137957907979812152302511004898163721768323634220847593573155201448872108227602937945652851683610986500702813544930141268524144882772218162559613718788519495521297452125843089951679332810715622622982435729786333923660187565697318636313631411904897866, 48491911459921202065947886530699553044426695808664225326977947905064855356750346223742655543374861293801252609236030862141829394451648144162580969455998579211308243092143950836137910073185120091452132784280463859700746117648592148404402847986399762226117216882520362477420222209615916836684807705725469735942, 34492233151139408086780213209986614655898446854082760665559902382226587779127737045547580420508450346097671250855922295969828346082275149848713075256509433855448061347341951585671508796240096866297930475384706564478234421668910954254942364818164278454562964776812313731459207859059668375222525093087635315752, 22618595695443382580420119114505532117540860973933393955419841600918654352834841971893466994325343604063170430750903005701517300801451400214398837072249075349470102998991844714924986537235428615560161654074773349687833055475256434816661280219865309590619792606546028437310465769490120776188880434290072608518, 4617309100175368989092785511798258976016342785065212393013549313124937682904193785912988549384149407592669998114821228569732564349010432206031414122076180543971724289410559500578673186173964094556802303515632351837245086352766306270106359283269361342917240689227822502681526856840816397407142352598303896404, 24522961282280701126454289003665239736695294155742737645604088227459524253131099839163935403944977743059954980653082967681963057968612261258959470571853341546452782938581061253986328332376043314273737898387197696586635197645338944802877420308327330341560580629732790107502812523503391015504886933857935805239, 33195899244687578004367779898658666193485349681453543767049155095589304794147392833841013507210626771643852118349001561352249851864522755233783827670399810789013354348355824651152048972472925446153713015104308408242302494499374376689526003013811129026800125583059421128934316902553798442488553284997289057511, 44010465073414381322028930043548233681223299411617915893010801519709476250615831495853212375483729609795266536218025640381619806605232727899160012229694318918266377209452893788506571956751921299276376636750162611726104179267020637863348794829593110282184381226038969123434726717000931724314504407041712699861, 48372614154786543612166581509734942202763877872782530349997494552533245099624085034100274340063701480696642211601846794934321899613449303550432031007406487629907282175501311111333651749975088740080628869424121395046113070228939422141062199970726015721936325356114515128533251605289368389567069189794821995973, 49043507036093189462671827190398676891045383689683577641199259494952420849031587213751572424215624326043501994332783856949988262673496408665629129840474269295612876258446509775786384982899729548525009723304306449700759614980212586604331795370783977588186719407835415466797645607664177944933745577084289996908, 38439605734139653209653747450010182864235050375640665576479307825772111205395285893307664059262441506263712189731801622839323008046891106660743117468752511111106132914380434900938487434668556958628893409118035449136143833555315477810637928536598623166658172689997691247094976014711617053588706071986886807955, 9853911590521548475277997724673389852055909854466768149180301371702288434115331052791970351587448054463935944139813570906450293350903905402839729820753247945903633067736924331765488889482110406943678980494129455760322130296478933445541442130984488696166988319591273341372004354045707048026897324371627825063]
enc = 47858489062144805163281411939584577717174860521919255578828332646567438982131914521952743120765491011506849641890834320164420942706349241751704051236273132534564193594191323630112007275647830208761946974181246383497807893030289450213882818653359694803798055036610195286860642344771183212992236113518207558799

Challenge Overview

In this challenge, we have the flag encrypted under an RSA public key which we are given along with some hints we must use to recover the private key. Specifically, we are given $n, V, W, c$ where

$n = pq$ for random 512-bit primes $p$ and $q$
$V$ is a list of $\ell = 110$ random numbers in the range $[1, n)$
$W$ is a list of $\ell$ random numbers that satisfy a specific condition involving $\phi(n)$
$c = \mathrm{flag}^e \pmod n$ , where $e = 65537$

$W$ is interesting because it reveals some information about $\phi(n)$ which we can use to decrypt the RSA ciphertext. Specifically, we know that it satisfies the relation:

|\phi(n) v_i - u_i n - w_i| < D

where $v_i$ are the elements of $V$ , $w_i$ are the elements of $W$ , $u_i = \lfloor \frac{\phi(n) v_i}{n} \rfloor$ and $D = \lfloor n^{0.86} \rfloor$ .

That we have a seemingly arbitrary inequality and number of samples already suggests that this will be a lattice problem, so let's see how to construct the lattice!

Solution

One thing we can do to simplify the expression is to rewrite the inequality as an equality:

\phi(n) v_i - u_i n - w_i = \beta_i \qquad |\beta_i| < D

Also noting that $\phi(n) = (p - 1)(q - 1) = n - p - q + 1$ , we can rewrite $\phi(n)$ as $\phi(n) = n + \delta$ where $|\delta| = |1 - p - q| < 2^{512}$ . Similarly, we may write $u_i = v_i + s_i$ where $|s_i| < 2^{512}$ . Rewriting the expression with these substitutions, we get:

\begin{aligned} (n + \delta) v_i - (v_i + s_i) n - w_i &= \beta_i \\ \implies n v_i + \delta v_i - v_i n - s_i n - w_i &= \beta_i \\ \implies \delta v_i - s_i n - w_i &= \beta_i \end{aligned}

Consider the lattice generated by the rows of the matrix $M$ :

M = \begin{bmatrix} v_1 & \cdots & v_{\ell} & 1 & 0 \\ w_1 & \cdots & w_{\ell} & 0 & 1 \\ n & & & 0 & 0 \\ & \ddots & & \vdots & \vdots\\ & & n & 0 & 0 \end{bmatrix}

The linear combination $\mathbf{t} = (\delta, -1, -s_1, \ldots, -s_{\ell})$ gives the lattice vector $\mathbf{x} = (\beta_1, \ldots, \beta_{\ell}, \delta, -1)$ . That is, $\mathbf{t} M = \mathbf{x}$ . Furthermore, $\mathbf{x}$ is "small" and contains the secret value $\delta$ from which we can fully recover $\phi(n)$ . Because $\mathbf{x}$ is small, it is likely to be found among the basis vectors of an LLL-reduced basis for this lattice.

To more convincingly reason about this, we can consider the size of our target vector relative to the determinant of the lattice. Because all entries of $\mathbf{x}$ are bounded by $D$ , we can say that $||x|| < D \approx 2^{880}$ . The determinant of a lattice can be computed with a simple matrix determinant computation. Furthermore, we have the following theorem due to Minkowski:

Theorem (Minkowski's bound on the shortest vector): Let $L$ be a full-rank $n$ dimensional lattice. Then the shortest vector in $L$ is bounded above by $\sqrt{n} |\det(L)|^{1/n}$ .

In practice, LLL tends to find a vector quite close to this bound. If we compute this bound on our lattice, we'll see that the size of our target vector is much smaller than it, so we can hope that lattice reduction will be helpful in revealing it. We also find that we only need 13 samples to recover the target vector, and that 12 samples is insufficient.

from sage.modules.free_module_integer import IntegerLattice
from Crypto.Util.number import long_to_bytes

def minkowski_svp_bound(L):
	n = L.dimensions()[0]
	return int(sqrt(n) * IntegerLattice(L).volume()^(1/n))

n, V, W, enc = None, None, None, None
exec(open('./output.txt', 'r').read())
V = V[:13]
W = W[:13]
l = len(V)

M = Matrix(V).stack(Matrix(W))
M = M.stack(n * Matrix.identity(l))
M = M.augment(vector([1] + [0] * (l + 1)))
M = M.augment(vector([0] + [1] + [0] * l))
print(f'shortest vector <= 2^{minkowski_svp_bound(M).bit_length()}')
M = M.LLL()
phi = n - M[0][-2] * M[0][-1]
d = pow(0x10001, -1, int(phi))
m = pow(enc, int(d), n)
print(long_to_bytes(m).decode())

# ASIS{tH3_h1dDeN_NuM8Er_pr0bLEm_w!Th_nOn_PrIm3_m0dULu5!}