20210814-InCTF & RACTF & SSTF-Crypto & OSINTSecPartWrtieUp

 

InCTF

Crypto-Gold_digger

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
import random
from Crypto.Util.number import *

flag=open("flag","rb").read()

def encrypt(msg, N,x):
msg, ciphertexts = bin(bytes_to_long(msg))[2:], []
for i in msg:
while True:
r = random.randint(1, N)
if gcd(r, N) == 1:
bin_r = bin(r)[2:]
c = (pow(x, int(bin_r + i, 2), N) * r ** 2) % N
ciphertexts.append(c)
break
return ciphertexts

N = 76412591878589062218268295214588155113848214591159651706606899098148826991765244918845852654692521227796262805383954625826786269714537214851151966113019

x = 72734035256658283650328188108558881627733900313945552572062845397682235996608686482192322284661734065398540319882182671287066089407681557887237904496283

flag = (encrypt(flag,N,x))

open("handout.txt","w").write("ct:"+str(flag)+"\n\nN:"+str(N)+"\n\nx:"+str(x))
1
ct = [3266754124418328672247866726679755848701520371443746634280907120024788951726790644565764235065010905480462052367779604906344974859812257431783971523801, 3910983850369346009480778834354740700744997092428714236904249742230620033736627429141128095231382899913639523058150705425021618891808444602545149939881, 27317810920765841342086929111042193579497353621610031484780035299001131982878467015665982909548553024787488715133220729973409548284520639203793990800234, 19049253826935282403928205549454387993361811589455900176398242634533643728656774386121481735599403129610194786842490901299693831767348811888295572944767, 46808271552976597930710682808639501725087745986478512439110229094106054260700609611651592136108105668095803793135384187386798141424456627246934054212204, 64663556663887876448521825389171681970226171803335047116994602631060184771208916838907061325157227065717836207677682181791737509930934478006410977305334, 71370989878902473729538075992611793835381097916199691855392840013136471258314666533631139620910819776545627240136734304044689167904095661008959427867080, 5120760109829368119622569216249179916662286493867330392301836160719483165296740657195693270825905530901001014831402378828989266553129276910799248011107, 25246762200155764725674915117428266946351252223920353292846537142043123004108726846560540427413694348662172063837532573805768559923596757914542578491702, 49840420035538562259818077270014233135437467586063205683943769627434293016547018393482060398482431118280370380641405128927430840198536985630649859298809, 84232356416028819831566679779591187299787046636995543449314912076840614265866721410586346948877186101748353344277333107087862936903079928428665929615, 56255989340747188472994001728565823905145449088080608312012473951209435572526372645545998691635581191431650844541918635345655144222239028951168850704422, 45785662740328453859890278502445450606890445328720454060032120470673511251330845850132591950890320517787732079986810994883608872640852386167756195212718, 54029870403864304285925769805259101311108719589466350768320792251083544066361265116520351278475192456130712826836166473186592532002794991923508524064620, 46624268375793936417415940726172495902868488296085533559474078710715899350421256180929703375516133001459740255662121433900562906914369420876721969039630, 15921219479965848802750013085928522470790034679969324752503581385316275799836521901155562358852385602763599760409651828923729107636248359311532535412386, 20190562475428250717792767608071965792428019405686414394515731600072635056217537304104019807474440130549050089029499956554142652193502911411782760901078, 41983059548033663270367946174234103357083211319135434721003248220792550449588248783877660929189053228157142988622736136441291989249080446689516065393435, 71609539411413240194556215042709157212260128588149087141493760115962392075268935955309314240733799741213805554924840687486128939284886391947755983910372, 48382284720865851648431016945797183660266155498343626372038256476287293528764330285514661435350058162782747986164808116116765643203666318480114386099343, 46730320638656612110889821918114226564809934661179594844549753878327086621670111917286750423548271235812428733761683357631975738361840732519608444014971, 55158112951581407023186496177304925445962183673199215662079568367093310059249411803313113095482726739394326470492736668839734286312650343715767983610363, 37112980203698874196497763225414417374526380133937967213841831269520374856619110460606542911440228172533968362786931746291414834514997777285267403140559, 63322083017732869600484256664107952565424442164218942893502809096945827312745918616246499734990787742358551946831008809185624657787375819807019566756170, 7131499419559104886376982790578102463139236264237964490683901837397932220525370218090186039561412497537162063460706345433646970829567561962759102801409, 58987942295441295007027662413419316243220623197071846210550338622495407069803847200822547917184493216087823262589570286179930999452321610193662415873715, 40463068017819882296397975257296430843199918804116579332129293544451758450871632123477648266871632208235745045407313414566869271527363707673269415792748, 63039255605860594706235701802182469722575918347437216391785141811844940190196047005143996180367679119101277408375635148536688180427946019402484987272510, 71847518795481381405870318786706930914683598350750876400219210332724219278096576686583523369096072741462359686018334607665415715621892012499046687826381, 26337284123753874828319186304791211620930566566120195495665155862853854859543475630545175774334287940418892288697324254994533678098095744373749417045163, 21764014175912521244824061176843027159941043924315159175826402721445924610127916171029483226782579782895796672888523861781938366363972830257845406910975, 3435623095726196844062581172306260159832381716480005885061523285318057788012070798019652466654719345533109449262217283547667486720590207050726788521007, 45919770921828919777762020824998206274312663582623531457423945627938988437572523960733207639926323480092557203738058449123337560810938710160906364447620, 10316176533060759533513950331093265748621797961634020464599935470363429799039909475463319253036787910300618231860969786155510737831206632050394210070451, 59917326034119369331371808884574791893663783551610720886605582940613080599142224466706727532690507606452696459627055492221262118596727675146540248450673, 10842419169283306075038519352806019318831568946592817182841197553628341894023325198625377701960932683672886924641591814480224960323114162850149838499007, 66742064034192815235690238007451310177229882619802417230057418182591053854863990729434269230203542276063435489487230228617313299686445072114861937495520, 17337799506489098810311640536792733150718613880893950634528762031894931254405830986337609675999763577152750890798518494436701133617817677416137197595268, 11805355039774973413960279981353089487026545524788641978782960297317350024970913592970423213016483957303390870999692309756230863161264738948268751555880, 59489883634739735974968870045855217812381229180244297407474712914329781106395937678986012546789197922278383445284656100208400201934959073937202913889830, 11401451000912707217036107785027425488005850574045702577420854119932133317734234141433888477046072783546143158822115361906593423801947424855735138806051, 18179963830269752328347012892189518105760526272986096873166870569368065912159690171168153334762363786860481716195666269739056960619187285110236225225886, 62509640700826594197993512978970850974297618960597709071687370554258739737985841220615247665877415157805625480566585584212254522216095818226299866458643, 5990222180228599266357925284831684381480268959200508566159335502046629155561009569578204543747284027605121962752167560001557422741943001415508677363231, 33433077637882273687249451259081443266379398604904264246156118486060075935455701873884654140790578203732502170849912443469942139967789200144428417241869, 67390195969105286284597473259273322568348281288068806381991832178917414558751508417404533918515282632113916633995251246834970162639704436292989924347318, 51701910800009973400544456943096381774979876707129028438769990843089912852448841473885556005345531439548870638966325407697691571465101340746897457585835, 64048417355580136172437626164825086735195128281991270452716237192859126404734412422587916788587067007095933362505117338589065656344579539799999449469574, 11024312233820256409788185405651410973909901139662527410532287633062222198961951836395718214894529860296406012036221609952405828243329490439564855935053, 45329081591634176909575079913822799290480598748734762443445536547105615371937523789002728790051543635047627596020113965500849934460327043133518899375170, 50858826475819728877134521770119997192668235111631842299351867815878082946160808043722869955055965555491424602575020061945411539811210145167251037970092, 35605374328853657972896594891951135620842006755668179374120075488686032129628717565054614577034983995013621326992214854694654154462512740843488210469396, 31170348521031754418118681749590239915934031936796619456246634052178959509402331720360681877547395350885325824851456359846571423553040992405912065457755, 59235278298913032815919203840415209842948518118915680147287275616028831011314878653857791522574491917033065613888064574586219759420566309846454002915944, 55319991676617828235828390538945693681702722602937980374183338775928431972606168528372504847459436496193456215997930129475890947660295696626996070685399, 7946870457459059970109585629186928476241935128637094143300110711234966048431895814853588251934003626794436938278721281017542468015907670659174126094588, 60110891503272403664065394170003816011867116599893134107795360372565178776851374128429405006507718785684697472100752699732488483946804818800187786578649, 28279251639525643355877411167790163315397766491944901475131371705035937611147913823680263340304888492788066877865697182783730607520500342177273147964465, 6673833370069672035529220709936517797053812916528936873626422295997956892073437608466673345610466591708954318522770521974566575022354974853539867139350, 5879041803124517031806630247719802188447725120442888110855907546956543471854281435506980968790820321124201724811614798792144878116655764899307623320136, 46864340634794085287213925222361157745729562024150128352765398567593088408221097741325336534579587914360401522890993826689469607826752680659459769771431, 8194451314034121623645292874953043868906899758451558731238739345182971126911643030327002247089719765234796367899874722374131450517330794969184864265713, 54446936497825800023536609025402128927467216919569806105966992425350211112265310321871365273194069612198965714146835792444278709366308142096412297265032, 49664620584746459632512586261608724278384529510561086522888627087059419641518391472859742516411690833878920555447289023607513439888401052315872395574373, 34156898638495828862328276933343254635452063265485210177467337609797392315838078769011438130125084767966982454733534259502040326632050149471710348508666, 30492198670321094942861049272814891796315708599800847931912081071102611152253093617978259071301664216033027428630697510455458584066407898917345416941984, 3613793784149192211009755488607428877163935560348733114269389687951497165685491322762261041825459125734297171440959408110806113464512878353595621354124, 12279705763694970673180436576088750272877526458037348371251591370848320075305832402846262804422841673867165174198233855848053055868119847638872372525395, 40877345239599080056832127332813108739794170402420519232059882581963379407650348756595927322565602511487901201482080745481960512748979230428566291962209, 50546970004760152402741173485014399024368459266914425153586817660910717388484363246842197469386308850948569760187130921902062389896918698251273033571856, 64662267274327121405145824520139519983970096850456319521102019795323464547250680114959766238015838060324781632896477707391370458399641977648129612809038, 74823756640316025618954831379580570287967795410041950245729147391511040327761948655357633338389729152644316098558070852276949927895715141311841068142683, 762075440208372468457962518481032774485090765040784352734612009016363153625431711847941729511572440976615875367460547015734181996995485157260725662952, 64718051366850823837872791256009130717247018020738367732669264535095514823570679009829052437291714822262216686090867379415239832447699096227625953654575, 14328318579478329070293281000390592890070295919392789967087225586048036901970102398921920034252680786983029475504846324077453670966766712985708086115150, 47819508550033678412702853706889631101410669749660665471143943281512698676783617665357189652026699097954120882414001154717918997258089353475775017452185, 5917167011870468624934459756466041916210766501691207791054221150438479042997857395302149649641551035080177809428783031566380296513853795548449641628586, 41372363122583466455014083650227416026095961915774665002591710993359438876577512822289349596872352743367616920266534220322805021770081399906934762996032, 28647102763694202026999877209365618843600517790276376715320831598625371231696971200891830639779198173374611170197106904989505701448484935534416324731169, 53461351058252039600406409020962287941814731855470754786484336480708351831993692806078731253573365307629429835558250376047395072489343618190215178696516, 43211630519982808255325055496431416562222405741391065144006747207494590517094963089326646224294212750016402493438856500908215224317253710640894768430281, 8489708911460505185941816612455271338936811013379084567101550260456573945478649038478506124294118197300669469552705017177655827270944844418578645699152, 22739718474207416860681516907108136245175908110579776599221423813780736521274509818317809641049136756126199753989311235943226623196775082849059257738072, 41216499670212294334651280812035668747548709105131700794545752519540336375321441907637985149672677540242864272713496740582094257029359109571709000713825, 48436506165397582669698530270507359120085582624990229731099970062649834008095239898512290025067179859801307370381405935208194802989995664780696159389689, 1585369946799131155304166792386457012394172770118639384910000681642835771323532468563585207012194611439135457247277948695062359471337941009175179750235, 8603288144119666511944003354168237303458523480925560370062388564635953061635422717389647940009966345557089758149833309897265764908036946377403726618906, 64101222620087611592309324709486851372656586138648891623135538258769906088025167941884507437869898345591373545551263183771852460865686465909022927922823, 16527144583489800339074589267622703740391892670414596775572362839811603852353263595287933280097926247287643050855717192439454800012237185587025342258030, 43667276680817082856834267636292121806981833777605458119209912299727781374012735950942847681976014650650405115417073655652257330450319405915928655376177, 39140951449701344166515688244374428886790877436502233180291072955127927101012734150869177569984136037272345222078216497684424410082172979920851697773975, 15537931042700254522587611176252004453412359577558220416074867095513378168984740154709389168969110367119587635943911825884344749910502795904913565227171, 57584115592473254303228454322525041631785171154103151093178874729079883455704358742586133432524956311883692239859557427834314150568077783639133527406561, 15902237980034809502971143965910358380816080400139184729125764474998259483264801894369466939263995676073257771273315544988512081225248999046822890564977, 50859432507876871258927044776148363731406483617554361871324332579365392377864999224029880363976243413656509052039814721618557677796897407829481142501716, 50060798173579642460106276365259395020688179551858830324826993612669623395929348865201104783185027263959131007321716038538876728815916511632533475508787, 21093401456079234258633171367778610446554117298173713744762450971193474816596635169881513417411413038931760122717931556008404922107697781138738323563002, 50871264470134644149642093828613407668761384164010018255643103521706312798607261474006789318936113229951254769246573651604524869541390940231104684687828, 65838555702814180296502565256444943340789146155658490130335701086297475619402177576374380169326664726736494368635345919297077269982160643735772030139293, 24183722911773924891963995001641331599594300538730494876239125258440555112551130346374041352293686484865295711516004079542559716598370506355252388731350, 70606983798229863770250838918961585630206515326394820998515905465501611723197873446221977733861919908305182573091789028866133518127760978086624785572904, 11574928020551879788627561129470863705564562907388661456838163800143145198992173457723644287037869966419076396134774957477432556478226898353190935778723, 61029601692381479053663587491935218989230811632558264300601308877354851284048932424730379285115898154959889378242675070408077916548569590745161494020674, 34604770125285800302365085079448294275594244440799617063053747652130859109690225689984871840665734961588683955127558201536801499336385265078556174141724, 11825597588617747085813837160017740648061802450778741359221519197975620769557373411105506691743139890711450252799721855339832409870791189985511619821148, 34221142804688884612787234476210488966584817478740599608446861479556501184308249517667796316433825013495886774426619501938042883318353949169073622932744, 18626654830829475933724422229531521260247749630282640788454897823986815196267646960322528599768563257608682140163517447300417938175281593596472310333259, 15709074995155666536793599438372653599673735072188045774362669512451580013591611414407383605083544686738323270765329148547175040050934619370240766488333, 1807120755932854104162772993352975977760368638030857510642192355770896237772277641435107116319434482498433810059226241520094868716474796133993906931214, 37175875591621937319620824075660098532446211618393274891254086565846020184454461310691428746518208846269028512685632952791283499316042277840066268195129, 14652938444415650146108426727368774911315569390356725236669074038662370902353854430602299285995671388121797270924184989138832895927715432624521826601309, 47503054411496613094174186159972883477343149161393992519368436992417560814175528597285395254700710111273038321292730265852161368920471476449693712252218, 34793266164410375187844704085373206595298873402664366666028335804777378715412285901615379046498740410095606705388808078973507358398160040266718217946420, 235777724023845578015968861685977896665545490030219293563237196041336651532625951991560690649655213041706956579810596768294392894560876103128919580119, 71699058026409903383591705758367140642656320715564592776562414985231704111130111268636522681868943716260492033121836183918600499109157978582867307435478, 5937340281741409173867715448617422850056083505252299835611627207868477902961686067795913449403704616805095770356914061148217655631521545003566311163286, 64970050684346645753410765937802248505636168494626578887182023273794960033653433460563394458144307982586048416865603229619651223215132716189029755965020, 28870151994623151917023631120163925496751172862446820796983669340074436826020543852010174031614232391623084724927387919132365749617232754179670252501288, 69316076200432522853422621078078479151899079890475362712069060151657101527879255706785128065088204453815353722430442067537036693490873329815183509775, 3656051605191401898523989951955450249753486544663894178988712577274662300636794652573077192350683038887211374712971200623563954853720538374525587861947, 59586376996345945899321257213258255736309213120802065827823301801096000077211540336197804819829222638564990740367120689915041923060818536969845303336048, 15209485646348568900613966175730263254996829574333766936919924747188067731995601898247851968054973155712860201835166302413341122127777858826564815332009, 65755944655354291863629481839344898125814080585489634477140449461486313994489712061017959934634948723074739252828514224659794230711270273986941151181246, 50044404782587975442358611321418585899140310908021360331315863141057616552340669011243801143395299815080254884794259990877619054315600014568718678262588, 18558186313286434827342393130857688381981240522540569652973740316924906520700554828290216461503534361328921396613229114436061029645283726932096210928365, 68121379646664377662543670223776546293099986219464564654888075357435343435295885243745380118444351548491552692045476944398276755320279785851733710778053, 69676172471015297584764278648519463973205605601973973954462659583351488700599697084095357354579852852975382605861180382202167440159214607938057506594888, 39868944884482077091789165603089328814636077812394209556130445270433071989411476864469152420597572325645830729366730705237597203343357461240500600362535, 23984225124526499163679989394300108542505969311640364168939273256169801709960904670771326948340213899233512604169808182913494660805720194941581797486789, 35140762457338703522439666809223184036794921565129617900381351263704514634805278362132497435138148263120289598367498165241519353320876411527172006380453, 24710691291453760841127687544504422972359827070499809049833293022746980471322200519845199709962567026745924106667690801956717451739332740526036551644785, 42582526200077717150143034364406179825370961007062721122124035466123261273825712581697916024437162094418224246572238536860392260236391392047271653531524, 67857483194339954482708519285879971058057170331448036301958621715916752108065210839856796360751666320642447394109637904785042539162094111072802047335497, 2599658436887948510146428121143122270311474436315255066097573906424588555325614896291500818473644752988078154748378704726917749596783076943413881775398, 62417511462783839398179767060659880783567096687315782396857233019238764137474740645399882358829642616473826449427654813700282313879746864145085481696994, 25046815174632206886915532324638612752235046746052396556181373371408959007980374964947016992667728355879280189035456444140202956919168084330921175866799, 26746087245003271019093242066186960118445359886088854449367123073505725700064370270771541201830383789978922299669035082389492227282511856195439127986603, 12899941330821578969367955126377518942374396461212099980148272913670808413456822700739908200534046934604705454192034690229329311450091796802978183417118, 34759455078337466713687570837759299391145888134102277551962358024620758688171187801911667844577854548914263100454305449832301751244677050808326765573935, 62641568509833713711570997042380165235664835417880047834887119941106533946838625165485309542062874513558580937837811401775554996056276012858548810747347, 54194019664134441577306366078821449269779438459243001896266057182634402737447514629588811251761251129611153860195003472642962987782051611103708961485272, 9676719975605727589576567594806284175654511463346916758560517020880951689432081269100395625675818196925127997734215947176763303327133107063728652865092, 63566749489727772620392173241354690191479996208515013140899609482323018089891274628587945348053732850402777375616488219134732475021167536614183749124234, 41389623900588800459370336537971008333777146975023702675438708757749752963555785484099714125932669585301871871129676831310055260650788211828337348491635, 47917075128910721336524911506477538308166963835676033239879005679388922099453013708492602384789333571083037290234698623216184215279113464823730289467631, 42078396965923796292197567173986146390599180034726305403980989544300924488594853500670135297251227759567949453084387623824589172575028323672347374791941, 26303467325603478409681425746270561760458104487375750208136288587139525406524153947947748518132616711483856699835473508339705278736292600540239815382909, 70210903943912719585335197681971161149552376713285943471513533016171830587948389001752097220135466501852133147457131249134740746493652843424857558685008, 10982176703594503335099043190281003439554172817765519010960096427582643358491587999013894116717272583614348843361339369352126040302498012513340173620179, 15375296014322542477512079793365451835294548632729239177298243608312496055206983209051785207816356014706827464682118103802848458765231022530576526601610, 60741281657044949725279101097916718408759978002888427225701082044375050708404243485772424286061753927582296860956198565404203687044663002010199141883054, 51453860908549486935732242355904656953839434743576398315040968465095709554302378990788844834564479090576226704624193613651209306174501876260882175512600, 42121429843235634165003593566253812713226165431603117921955402685633741429269868521680013286432815656510584597940543612666107258425775935790786790012041, 75847336522995708598859507481988194486014177305660997189842728336432951513069707589487951184161881119260090343324285618931758405413108075158339567925903, 65758341817222621457885108916596158755098306658220921631792142654742204146490776266664280599781759820995333825069037428985525987702654906233411792587673, 15752213867601716547875293001866113163887582411052023985266075351056384315464535935735251239301973973233286836062255507777260674731895530600057333994665, 11151506009425616448244747739591250923500688700709156802826028410961247750111513167162557346776825044249732147604063296508981593009108961067551626395468, 24988307810903416422223700059042860807188507865378899213217629974481150832035797596850622418574087799771865200841087717335083639492611011968919584986991, 19188983999068145211485730840887302107035995560988908325822555747788727142296909943420991730736407232657762626482614632643567904876131676294106469080567, 49165807149291610078767263213011932229369890095374948339130583996779251886618924483782989424700910216292003196618943704463960760836284727712556416138720, 20880120825314766313470865125308572795577662008420147141189550790502101907656949439065273036601014525812307321695409142098153427350456159779924065995426, 3134148277638552172931615388909963243267631440500151801678408733633678460466625580372490623855596910321277808417815986593695645228186837564359773545208, 76027513376813747014021359611570577983815818102025816667258692296115385413227296619875774704856616068742697489757991264586446726640812185996619526500868, 9576386300219383458921907336704987148002255976652861754527672989041213499573772344464927344170160854134801169030299424714027104595802440175290118115467, 47846312343889535970416011840273559470023183338680746515101124658408961305018438134079804670804491884363672682872663103910308908246260073683029778116394, 16836020225895041283399865570278952563361372411312099179664436864693089583825672663104654006872379721154178277022850302378558639898531813871944866012688, 29312555443866353115375285797020858933593819317714753848974053207751144798790489316607442702651597786670972424273015577465723971183954317290632255518341, 45952399494660064838144555112298851928990690958591804048587523480566851679383669387866668507436863822348953169424458480096739821837326801953301622926562, 68334876517321835871217564446395717515355168304996149895652706727069147165281984411219162106481594608000995755151779899698717529318256390790021401438718, 25861029641666972527634309013968274542799402009868571607186682711883347548473260695668831750252078832274943353602464264720165568888925706728574087342628, 68551775088688184199771942195355426911668032674229430062997403726538379537067490978577329178497921291686561217843648566010918593439905810598612318905217, 37765025505682583464362211182398757603423382509025947521873112343726694702300573134890794527289002851767037029190171815999811136695377397688834815605025, 4249505767147772196031020651289585799937480050894276528897542147646240685440344617119239879135528543262687454500110733454342336571756916026373576137223, 12211897746552190684252135375038193571224731278828097646293011671737319460987527595630272305866452394238518927533887961137804982383129793243658322073814, 63672159925831702084608593770871378832840634765254242580922793878262780657303215300065343199745082617326364301567988188247544290658412323708309128521112, 5916152400097580259043801191542869219461022009826571612531294723654814844742388313101200734677007620911765056890963706507708736854388938954261090636816, 14317119988771636810566962078982667504680472212731015560163258949791136175315507709882234357375608038567842467558284485862323906865760782946330956519430, 73425426498763600363398477632846027187594993874507584521147927260063731277446622859480454490655597092173511066199697647323557539421105251159917461116448, 51291671008697812263954316353958818245358049801515013402923829127778604245127923912127853869137576703271789663513404617700625997281587078815337810294446, 16764552517838375964591874922821157969132749425046056275194064910709033826102499972685485237677710147299249213993545772193666719202717777304436525138230, 59295557012652744772208090497926508763666861380190571969243245501411454118387516963262188176132218639685609791422928694949362661989298405412386894959364, 65680239245306856298345111605806359497039862013602921288801762280364506136494777241063396949184533793043022857539147614816975238609243733604742559030417, 72375457889148576789811045675763717743813326782917792391377546702617598519587357238716263943784839291085690192526337648486979325162244907674119290503179, 53234077992007207968984629907955923807193864660771571665077871505422718966065301015318200429417886713035533081206849701294144524970607157018727881011421, 15886483931792974203050424700896494469022632750392566017940896092113020011301447115452279047200702841646809408874121286006915340993084644941811925011891, 4000026211601185502106663641762011708725430703734671920980073131891918285295081752549137630953921078183393375323131848411438504218653510143085517924354, 10319649624556731904039447425825069667183347360430256330142417710766254562223686734071109743956144803418154942873286729125709953817180715625501589162545, 2959127299070091142116584970101314098498259209023373122113534164489561723834616597754357457826712259811824721968019042637401460259286073863020743546081, 26966963187874068549615333973802158799875048269647561639319582873986161093336638373947258726531714616272425009280351155372607494769526061426271185799776, 60480379686940304504344210934804247883844503527104600258142856523953218645216216990403655911740533083627163777976245336274909972984546880202034729883312, 27261558287522575971851824442111090365144022873658966480485633047176320843612473205407488091205599851003730101551213929420057107039313052216522197198978, 5924889509968412055641812913053199966953595678605910723404383140816995621145232830288766243387119999521206867701900470658723204158233731531189957564758, 23453156796655450247116141307366623758418077565767073760208454382429546186654265548677867775354067560840816391896631759441083435660495001159025898492686, 76150503404358535746322203310861113340536545623277464771697476586798690077324876584398928162593218798780607052161166996099801460843556940059525992786824, 37727315876172847591393275092226735197131216415762771377741373327831827247473435512306043337156965991700136410696885151255831157825105690279082625332709, 34063446655575684287153287784734254171212485972386063875998727605151998698499957152558118780955043931859154057516779473847326673786233294077986859617690, 47483470590782205333078496439458525138609729122382072733999354756246820163015660201372672052476227811848001151006206216443241731573155888424535367176708, 39218420907233152349337503997750016372701524044569318259499048063748671531881474959351678569430809988119317210858114117053551093965393011243381378492998, 346813155305357896000101560296376715878805746572198412084124073507251650659757384260350199082220679479346402180280656007677537505603012072956567379200, 45220337350144137249456097166594787592336841735274298685371711994002352406886579127021444669722143416211134915968064654027096905338300592093107053708512, 5460012104494377033762803353668672910910932872167923235617032840897986334654385783555614999313086224242950388742840844011136027857375260879396677603020, 37023646144423321174994717117908019318650072460288262938875273128986672114185107589432972031304290211565654988060691997961153590815964538144365251181775, 63177477223445910049201384279690078930019819284264306067500875252847796215965700799007341759196250450491593055470958720571995993265879745352512656382848, 1700583012951649590611729034981286100342721588558142880964582566799910787514220066268682066981428229558226944161013518056229007812176089692828860741392, 17246038765173067313249878215359330957527587326662502645985291635246053470015915728537330740772303686721906455426913214534530261079901607192934039938060, 45987434147399996197496782026993298557958954570476732783848760609793549635871429620277069591160239426699116842877955529435739418658862835669098411826316, 21111490547303152987944854108036303223281643522396150653972569704379156697301910516727830184770144662770080107913540137717531007645289253745952440414926, 10698232879034106801260353759116257884533008949848502754162380992641437894367605208136298588395112435423177990947470598835570681171317007264887720823778, 54293643078851172364687836934990821579687484157127703064858191752204436487026179374856533544917557799042002597904530828982489891703237561281336459590518, 47797005580077273834483109591754793806985949961317398846769483505668568755603394284565164912646840149645763801903493468755606222509979288885436039797214, 37386506628153260384840150994124701181836200890809074083427785298815850467904026208990622829408207112968603273995655647351172691130659109869622941513399, 13057205711934046467118008739652612675758052758290552436105179764903448469199957925782089342100034435811618076856898039125384846873718510721165423899617, 18016141907808433145961025284467589788900284749942923516457310468709437001788966178751079198067783831673559463585356851811413814896939807067475555427374, 28185214541499079104899299096705844476508797918674889724218918359491538627046768060739267262641563085978395547302726213511677754065988144474006421669919, 8541173904106443905299905768662395072832935944800738204096451433781271007344649650999312461498262780266939438629628997360503524609987694055871540797822, 55583856938965878851727772532012615591107008734179599213849731144139750332990774963054496728870626955960023548737488241552231532876910895970717980723626, 73126878881701489711684528170287200941163894464677667890357697623803069282892472939945202511068349041064012766273020456331595582239718607715580058967921, 70354401173234203817094603858861728539350610438961386996586323986304956626309069628495646684906850309442426229300586236137286868518741887422968392162548, 8914284227759075166669843800606112854269465008336756701964119837078732698537791220276520358004294502231788167963298136537379442577658229609166991435663, 71679986255547965813146878140040664201073433340974131720089263707910307438689531571321153842267530643245284971416280923014280802420073531897677737784480, 12700447152069741878296970568845043035888752941098126195431952022535521184822464642258479573298459505834137899501751562570215414736024639835136989283837, 6343004739661668027332689782225036016497158024551360141260369562409298110062110418091776522944654709730459185916638767661342308594945318353078260927349, 63964337492108130229534104366403606549429509425838893610762333683602786560375188874744626561075352358482069214498737114463864688224040094143695973321979, 67331564851630274889744575564877053915024320348750381733860879963760029288286952415043130610380611202287853110449108590432736764101996881476127456612908, 53280882069162605530191514443798777810028687362597894103548425458220909107156582202503516464523795628658208894147158134959433009893999958404472326887421, 33987412638079761735126555460021225568819079582348419476130572631524190951142125555279430092745231216914642104268144970982726216308555881726629242470610, 13682406178752200853488921722342196537145987369704113476544421137346145516814433815172365070204243148827801660590665538792993163703633151871356444406959, 59463989125735016166555373271475329218895751331847622880739844997590477284788570075116983616019629056762256994818763091149753839468824722562416533043843, 67281682017361977913152739570150548267207777610917492408365814330418488902058223459045634717266171571439824557859718739925029610690419177548771060547694, 39405781498711220413739963695737002658793585701279503786490288662610492817823621117021234029885675098802400891723678776479565707731211683846374263316873, 53034807419358874766350432376315742395296988744022530785117462484846925513344688866349068005871824739673532913987445237461471468400241186927222857371834, 68305629722812234698423066134000790386970292527553321835797323301872488612831063496859128755927745930236100965836720379665554220277417403641562506589739, 15838477469714165090920618367681569358742354857430493842822269635842365646470133405526909343100727954425645887159301780057362634821410546797188280600973, 24406667934205773393486573213298175430629511700972743156092216312470305819697796258655710647669449052724920514990995515510027140733652668755162210879284, 68460243344752374579091832429666515661775987782765587913153602252111004705931127037248902092418367233502792799588802584226718845415421737479907804077611, 63808325950210035810812291635020630613732453561277058010602422073363230632345954950950233595453773160105621255639806986604615621453822332892789828462090, 35920729037346907063152399926080706264554331849560440381191227037937910244659464632447084476697840313861056020706495596126485303699013742182912707172975, 70315041903670157336851359766913844259670523706324294379204277248685999742047453561977925733597786796424146533733873673211660303409007875211743693703450, 39300531126860319955398345847761010603834225325535364925973189673883589019704883130648163179767141337507300067661030698253528221916592525918624340607537, 15496845894895615630021254140566466646250515307806313944390059489493636414202320808813409873352911875321240477276777125460299625425443517127346136060402, 6918931991334214049432302933214038877664252698312543806498810568265540530745938020106356587006559879317556154131091801485516823150639771462068552490458, 13284319826136226129231185037901985819553434334436034136363422696599972727231112997735289148332196516271619405264890626985179077260440615779761000533675, 47141354451986229521055621338816842478003758611988390046169176610982917702117914199406800715608779829266151978859414114993007913651989935003014956276172, 62006071231519162075067533854248673825540723340885150250907087023728863043449786611822047715700318722376817127112362733271740625676783440798426908449101, 63893521915695074076473015870298955838191664815517808757499000857893428891197252747360448837407785054229725838898014349928665255821170162098307539344307, 53724997828497244329408633732485843721280646497077186636538276560039817034467049143979659252524650609122526779152238242200009648428459318191364710668758, 59560026843867449601276263740933112576182129239752897447857785482266968806850863675639974741623809306675891510190099978299125663568621065833548636364530, 40908904103345585788262408080445592912077785202466130402193215696781356453887694866479723318713262095397682184771025397015406424244516593134998423540293, 21520846393831470685610096190168502256530920634386412660925756889910811879936477244071180593183278964080595838026896057947192168361175044065775753001472, 71994121934100897695373777005150806654834175335935905432800180220212844161938577456202364343367762384804519329089155317640274999082541777992495590496300, 59953753983754938792876611451670073996692753691715543251991783347838397186003557839758271745884505324101699352687982352675858568077550526416572161213218, 32018619708338154045357870379406367509414130390075786097563998491238705394761106321287493739342215745501191759206980684126857845949108887540197973688400, 19753200456167466465779432336842541030557413397596794468519345155114986012441764419115444925556673818310817249150486960437725537702448521078373504867565, 7342484858213250235462608889213386080064726860046853081716849206494415366815619844020076108010255128616757216474086252862052951751272920557333252010431, 4769896687715967889336481310203290840512712756999532930891000782787932528428270382724343267441239836234899104850512445829826485709802266593256527297538, 74355004258607576571833753840053548463378928267424658977196161874473156579212738683557688699040100682847094105589799689843205305201454653584801640872249, 6690892016551814532110082014788257179806167058472941857479165541743120455147037200870473223869330191373716321809815790713607069279076031653761661498152, 20929231349749029774507043474913656384295114733554322493333103320239789344142773690393384176681858129568549611334486303260091934120991115068065757099304, 17153283710807583417797086518064762512344132499163280505223698478090291002458606163847203257279411593037898263419480619904785414327965511942845045917778, 22050651142736213565244963818664170172032916896662073301155387192243089695489247087391670138735276225579775431936391388626697441900275744645141428022189, 50937819965132153811444565518964927860475724053299129557722050639198908074429589460667005191838429306196635373570825296681353003427220426130286971585939, 58913284462604187700172393158100310168635473835280983484905632522707627578956876728290392755044023467406825316230706821238436272638921714237556770859104, 17681890152946896225972804441881107507903984131878871289374213139906663030958773969339053682624067346901991714169068086996858271362082589139087115054292, 3909112468307243293324758000901176555871642123266849529594698077998545905775916220352604577315589652297068228906040474063596051918710761329690286227933, 26659357996912432362440742895222637274276390173496378252980802667664532931418023547469963558051869368670035728144595039473629042831713113176157537965085, 17179226767528485522234897181377818519983080414340110997618943993801738768695017677485273725010927951188829959293549597122347814093251802798150160484484, 19844433737083054737496998287597016986512276379827687999223100265664593048556212270024309974344283154237055912105437530884588065558856906602096195808242, 47348710551114046556019331306794334756808275356761888394461758029243482669094351826152778467123320068123601738366945029608823621120671776870709906375117, 9700117555541147957162539236799929299304670997996359585230076707723964209982089821563932293396563832179879999190357045199347391324979469059773776588627, 13467002873626636888949523271031927213159346608965094817646302401288661282610791478079736771259321566155237819209065435898148651759189622569101507485715, 63037961235817497070200076262785758477371602688561664152916441494722106004437031909053699035623597319059285567182742183641167584128065475289227729777632, 64218176089111895416869027246603819970664313506455920488148791215602497569336950361142384744880154632841827794749450034276833675991153288511197242689683, 47942263513439392830167504616104953960109996199015457630131745546068423701013642403323839156160826426619128873229034532556824671458723559069019818844664, 68742746222182563249219749720388662956433689017106697510006439927726538907944533506432387677351240369908865156490610628224604208935896518456792275951386, 52212644024277302202964993748543423030284246877586585223549426038195599560460361521694871178577347471545868137719848759593471592105056983977953734420504, 70264906652847626089535377366020042773837334827875270446429461263902560176829906570391678559378185295380703037786129287917380381287801134465465850277689, 70338735306991917918870792762895693400859231411804513011341248280823069527131025167916532212139891844804984508688078627963308722454289725189496741592783, 11202943024812091871968653090774694646166527588230230055019610642288376456094708642854597051283662781541220199344624011347563372208585467149576852176942, 45465287772079811194403031363838060966264660784435391586286323915162071710978408348641606715517047525841527692603591534466833484617776719296902254451809, 15169623996435078849216247400427343363968733516560810866651811037320678250903315110528158438221622688297331087485255287010416118126711779737721856328337, 28852475740061878372356478463808810042887244041514447822647154314012875742232208435189321135142249111535515768003337785061252044994754401654492928310569, 5964830405726355845868918682783030011195532635722675073707557787272120274893377363927170466481373691893436275201727030031846950955144759398184269785791, 34240000270864477532075102450968450839470355528222720094068701617005525747220229570079432765968261626445996576859553932062082807188947122110205121541573, 36066847009381278750262267643160682991490266290788266279454640758898653971700345576937422987472907571638424055138191448503121311206068403152358903727931, 11170091007234975852711136174576640764201643584673042209824904622333149479149743689621256091273212460852711241325787976935346940110932656520985022456280, 58258126945548764950797717782798700624779811959209396814323548509396126011391646953885580742437208484260400477925904686859314497837461751795642440123737, 19967926920673152856540078688569687894710262985783180877581399859282901459026334508029201347173518578230966148855216358303416030336039471203130056025847, 23595548276608645278366664833783341231551328905679099443768564892841143279319379101358803895431983463285466294746298308657854039318187145804362431897564, 2893474370961335486456525824174663168081310809497129676211358076233834398745859402822323873444488074719052580697214253881106450534065425461738291869558, 5958907829034425034060316070647535655459615550109982419322554756251664155034664518669276533235954875314578002477545778915463022354241496629192604779196, 27788566883685737903481747231933802166299928088919432671260904020088637407292302594730412087020004041723078159004193447947542516090218561430792231480922, 20532093112179185521013377866112742417812622082022290708449532178388359732865119787523382224112648787182208662206608003197496180647105678758158192400715, 53650577218203110600410729325998398766865814136267255360061172788801435890073996725463408842308335996720339673250282900111659334006005865543492882410994, 27945606735686322555814229684881151888663150442470178076013292048060839982203053567640973752973606459118462199368045579874974993094749585683152306114353, 7830111257927859573531774147894277110055421603464794311873488150838576658890506727221887391800809154699966290549716428882127868574637820957455771454946, 25025808677568131096842775102792540807686366181393166426022508716670220871341079639434019763537052343485081027257058743353860070591961282205809544500182, 5727554508299281734853143508379520041502848342636591640239397030993361937011007794354012913783223878938187192585041630893973877566528148234547516190549, 34125297955221973416857421179727086657998910466291260285578023763300602193457505573438526997539188005416829176125101756371491215872928342534317152560632, 32748794215539175827451064809169640707872656691637312790248785369034804895807371648792467471366168858175551862032815723885968389112394766296982682443669, 19316062337601046084359756740917069089224659580679757830844402882574641776835008814717493659219551992308545704093654161563862554123430967564362043544475, 16698150154757920977809280429499684949586664950572392192530208431996083807110717281687762672769576510155761079366746466550237192996169124113339334886230, 44572056955848609010373092439149356067260311771322096152721745227413956103682879244155534554941522431647827072846297085468860260003046353502705163208246, 27628575438344418993708339803452443890754069104828236665940305554239599902121186251891130374253429078333471004275298197440209461188118994332259999120164, 61919652562044972586438492785212427980643594673222454260723387039610192124396273187701658792233976764341751602543127060384407044689376048608848519817966, 46109764189688329101004508471171450628496264955374314980452086114935940284534425097345137553792317990951285615961627798248025371385228530104733124807466, 46817387909791035117400619877531601085593430973492709899023738884533565717056702943707383750398878694854456668238661907490893742791290178958747041681661, 59056224920609792204565568830061390745355488565348333616939229708289518825178885105132973296275188941665728400536826108349556934037483523802869792969716, 66604984921500741665478926723143420146438008068509389500728173853359052714091540238730324836724525809382581628360434354102848448924156047215001921555337, 31419582430779462840265313481263250807512794931203141071416250525469576085849479844947749880276719895647109269316672096266294357898786379072006529876864, 39183832730973061755201647330753616948134226115790320443363338294219451770753694348259167324654888119971382851094286357667963928230844906403886283289603, 3283255784320516413168899839829830028094602407822730101434806505467144706365783146560674309642101764920423301535255518747699612103072011492758793346946, 33368835974991525266725023131287562136839356113213003074639977323208007298803414289567135487257122997245456354564103035169531096968774429702946303497005, 69846025000402574364962470590372113840860535424086059210489025038699977139863035493677207474408680292062773766558077221180073317914557709977751070278701, 34224232632002355134365134629936005598177140616238858498314305970780852215452788902032135977405618831573456053924472889839514221495216331158722016210045, 65658980938469147193290995330802413952882415964793941700703938082218727023573782508973634540422819521500781964327919480012170455893980979452781727496450, 9665250348154536654206530131694515665172789483002642996612304591358982054881243090223340150894464762416439064809966191601896552757074713738589101038945, 8284215764601217981544785999422488229859061814390197195042613376491836774363916339272149964393696441572819237956327108891284365148450554717902579008885, 53839210761275384122812678155375624236213180995083637849090835596108532323779151952329262056317064448003166882964978836017773003455831766519615849734309, 8879066950085937295713426375145168962599389613745881844691288681084047755219605949515654929255916456463715160675759365433899307173061948451396093081300, 44846522954890932053452170548384737961090700275209642378685662035957105157761437451596217747093401844478988631729230318383327981353712362273424303455125, 43158163002980268176859470096906775042752252325756903267533186654149503438997066932081638361997913554233587761452222246607235427619695339583560854453989, 52573321691121279494123052995574692408510998007843795734096932344446198410817800561173257074232286807684589742033894643046244979672762218377487299434722, 7897550374384904887513967113216775000773764113952765407625043995683474308691357357102548770113514399030757334911738320038416173083084558400152128218597, 16715592176910978920444709654700402674087729403854503083620096481591569067609291105780994401753704255670785725498133269560763193450380953726654434098377, 13997295715451071253747239124428639199617619156231247326729836233417198543504118262938847989649348778500848314555687607052915438695191930013893628900615, 47229599794488613098124056349473823155280392998354765758670868622165063315177232324540165316843226647506443608478789352548001630604076040168618807914792, 35258213694320046701654200010884312588312321572105544777004280046591344354420706119915893205430664500593588418655204102873984500148524518893396701626955]

ctftime上有原题,但是略有不同,更简单了;它提供了私钥可以分解n,参考https://ctftime.org/writeup/16120

顺着知道这是Goldwasser-Micali加密系统,参考la佬的博客

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#!/usr/bin/env python
# -*- coding: utf-8 -*-
from Crypto.Util.number import long_to_bytes
import gmpy2
N = 76412591878589062218268295214588155113848214591159651706606899098148826991765244918845852654692521227796262805383954625826786269714537214851151966113019

ct = [3266754124418328672247866726679755848701520371443746634280907120024788951726790644565764235065010905480462052367779604906344974859812257431783971523801, 3910983850369346009480778834354740700744997092428714236904249742230620033736627429141128095231382899913639523058150705425021618891808444602545149939881, 27317810920765841342086929111042193579497353621610031484780035299001131982878467015665982909548553024787488715133220729973409548284520639203793990800234, 19049253826935282403928205549454387993361811589455900176398242634533643728656774386121481735599403129610194786842490901299693831767348811888295572944767, 46808271552976597930710682808639501725087745986478512439110229094106054260700609611651592136108105668095803793135384187386798141424456627246934054212204, 64663556663887876448521825389171681970226171803335047116994602631060184771208916838907061325157227065717836207677682181791737509930934478006410977305334, 71370989878902473729538075992611793835381097916199691855392840013136471258314666533631139620910819776545627240136734304044689167904095661008959427867080, 5120760109829368119622569216249179916662286493867330392301836160719483165296740657195693270825905530901001014831402378828989266553129276910799248011107, 25246762200155764725674915117428266946351252223920353292846537142043123004108726846560540427413694348662172063837532573805768559923596757914542578491702, 49840420035538562259818077270014233135437467586063205683943769627434293016547018393482060398482431118280370380641405128927430840198536985630649859298809, 84232356416028819831566679779591187299787046636995543449314912076840614265866721410586346948877186101748353344277333107087862936903079928428665929615, 56255989340747188472994001728565823905145449088080608312012473951209435572526372645545998691635581191431650844541918635345655144222239028951168850704422, 45785662740328453859890278502445450606890445328720454060032120470673511251330845850132591950890320517787732079986810994883608872640852386167756195212718, 54029870403864304285925769805259101311108719589466350768320792251083544066361265116520351278475192456130712826836166473186592532002794991923508524064620, 46624268375793936417415940726172495902868488296085533559474078710715899350421256180929703375516133001459740255662121433900562906914369420876721969039630, 15921219479965848802750013085928522470790034679969324752503581385316275799836521901155562358852385602763599760409651828923729107636248359311532535412386, 20190562475428250717792767608071965792428019405686414394515731600072635056217537304104019807474440130549050089029499956554142652193502911411782760901078, 41983059548033663270367946174234103357083211319135434721003248220792550449588248783877660929189053228157142988622736136441291989249080446689516065393435, 71609539411413240194556215042709157212260128588149087141493760115962392075268935955309314240733799741213805554924840687486128939284886391947755983910372, 48382284720865851648431016945797183660266155498343626372038256476287293528764330285514661435350058162782747986164808116116765643203666318480114386099343, 46730320638656612110889821918114226564809934661179594844549753878327086621670111917286750423548271235812428733761683357631975738361840732519608444014971, 55158112951581407023186496177304925445962183673199215662079568367093310059249411803313113095482726739394326470492736668839734286312650343715767983610363, 37112980203698874196497763225414417374526380133937967213841831269520374856619110460606542911440228172533968362786931746291414834514997777285267403140559, 63322083017732869600484256664107952565424442164218942893502809096945827312745918616246499734990787742358551946831008809185624657787375819807019566756170, 7131499419559104886376982790578102463139236264237964490683901837397932220525370218090186039561412497537162063460706345433646970829567561962759102801409, 58987942295441295007027662413419316243220623197071846210550338622495407069803847200822547917184493216087823262589570286179930999452321610193662415873715, 40463068017819882296397975257296430843199918804116579332129293544451758450871632123477648266871632208235745045407313414566869271527363707673269415792748, 63039255605860594706235701802182469722575918347437216391785141811844940190196047005143996180367679119101277408375635148536688180427946019402484987272510, 71847518795481381405870318786706930914683598350750876400219210332724219278096576686583523369096072741462359686018334607665415715621892012499046687826381, 26337284123753874828319186304791211620930566566120195495665155862853854859543475630545175774334287940418892288697324254994533678098095744373749417045163, 21764014175912521244824061176843027159941043924315159175826402721445924610127916171029483226782579782895796672888523861781938366363972830257845406910975, 3435623095726196844062581172306260159832381716480005885061523285318057788012070798019652466654719345533109449262217283547667486720590207050726788521007, 45919770921828919777762020824998206274312663582623531457423945627938988437572523960733207639926323480092557203738058449123337560810938710160906364447620, 10316176533060759533513950331093265748621797961634020464599935470363429799039909475463319253036787910300618231860969786155510737831206632050394210070451, 59917326034119369331371808884574791893663783551610720886605582940613080599142224466706727532690507606452696459627055492221262118596727675146540248450673, 10842419169283306075038519352806019318831568946592817182841197553628341894023325198625377701960932683672886924641591814480224960323114162850149838499007, 66742064034192815235690238007451310177229882619802417230057418182591053854863990729434269230203542276063435489487230228617313299686445072114861937495520, 17337799506489098810311640536792733150718613880893950634528762031894931254405830986337609675999763577152750890798518494436701133617817677416137197595268, 11805355039774973413960279981353089487026545524788641978782960297317350024970913592970423213016483957303390870999692309756230863161264738948268751555880, 59489883634739735974968870045855217812381229180244297407474712914329781106395937678986012546789197922278383445284656100208400201934959073937202913889830, 11401451000912707217036107785027425488005850574045702577420854119932133317734234141433888477046072783546143158822115361906593423801947424855735138806051, 18179963830269752328347012892189518105760526272986096873166870569368065912159690171168153334762363786860481716195666269739056960619187285110236225225886, 62509640700826594197993512978970850974297618960597709071687370554258739737985841220615247665877415157805625480566585584212254522216095818226299866458643, 5990222180228599266357925284831684381480268959200508566159335502046629155561009569578204543747284027605121962752167560001557422741943001415508677363231, 33433077637882273687249451259081443266379398604904264246156118486060075935455701873884654140790578203732502170849912443469942139967789200144428417241869, 67390195969105286284597473259273322568348281288068806381991832178917414558751508417404533918515282632113916633995251246834970162639704436292989924347318, 51701910800009973400544456943096381774979876707129028438769990843089912852448841473885556005345531439548870638966325407697691571465101340746897457585835, 64048417355580136172437626164825086735195128281991270452716237192859126404734412422587916788587067007095933362505117338589065656344579539799999449469574, 11024312233820256409788185405651410973909901139662527410532287633062222198961951836395718214894529860296406012036221609952405828243329490439564855935053, 45329081591634176909575079913822799290480598748734762443445536547105615371937523789002728790051543635047627596020113965500849934460327043133518899375170, 50858826475819728877134521770119997192668235111631842299351867815878082946160808043722869955055965555491424602575020061945411539811210145167251037970092, 35605374328853657972896594891951135620842006755668179374120075488686032129628717565054614577034983995013621326992214854694654154462512740843488210469396, 31170348521031754418118681749590239915934031936796619456246634052178959509402331720360681877547395350885325824851456359846571423553040992405912065457755, 59235278298913032815919203840415209842948518118915680147287275616028831011314878653857791522574491917033065613888064574586219759420566309846454002915944, 55319991676617828235828390538945693681702722602937980374183338775928431972606168528372504847459436496193456215997930129475890947660295696626996070685399, 7946870457459059970109585629186928476241935128637094143300110711234966048431895814853588251934003626794436938278721281017542468015907670659174126094588, 60110891503272403664065394170003816011867116599893134107795360372565178776851374128429405006507718785684697472100752699732488483946804818800187786578649, 28279251639525643355877411167790163315397766491944901475131371705035937611147913823680263340304888492788066877865697182783730607520500342177273147964465, 6673833370069672035529220709936517797053812916528936873626422295997956892073437608466673345610466591708954318522770521974566575022354974853539867139350, 5879041803124517031806630247719802188447725120442888110855907546956543471854281435506980968790820321124201724811614798792144878116655764899307623320136, 46864340634794085287213925222361157745729562024150128352765398567593088408221097741325336534579587914360401522890993826689469607826752680659459769771431, 8194451314034121623645292874953043868906899758451558731238739345182971126911643030327002247089719765234796367899874722374131450517330794969184864265713, 54446936497825800023536609025402128927467216919569806105966992425350211112265310321871365273194069612198965714146835792444278709366308142096412297265032, 49664620584746459632512586261608724278384529510561086522888627087059419641518391472859742516411690833878920555447289023607513439888401052315872395574373, 34156898638495828862328276933343254635452063265485210177467337609797392315838078769011438130125084767966982454733534259502040326632050149471710348508666, 30492198670321094942861049272814891796315708599800847931912081071102611152253093617978259071301664216033027428630697510455458584066407898917345416941984, 3613793784149192211009755488607428877163935560348733114269389687951497165685491322762261041825459125734297171440959408110806113464512878353595621354124, 12279705763694970673180436576088750272877526458037348371251591370848320075305832402846262804422841673867165174198233855848053055868119847638872372525395, 40877345239599080056832127332813108739794170402420519232059882581963379407650348756595927322565602511487901201482080745481960512748979230428566291962209, 50546970004760152402741173485014399024368459266914425153586817660910717388484363246842197469386308850948569760187130921902062389896918698251273033571856, 64662267274327121405145824520139519983970096850456319521102019795323464547250680114959766238015838060324781632896477707391370458399641977648129612809038, 74823756640316025618954831379580570287967795410041950245729147391511040327761948655357633338389729152644316098558070852276949927895715141311841068142683, 762075440208372468457962518481032774485090765040784352734612009016363153625431711847941729511572440976615875367460547015734181996995485157260725662952, 64718051366850823837872791256009130717247018020738367732669264535095514823570679009829052437291714822262216686090867379415239832447699096227625953654575, 14328318579478329070293281000390592890070295919392789967087225586048036901970102398921920034252680786983029475504846324077453670966766712985708086115150, 47819508550033678412702853706889631101410669749660665471143943281512698676783617665357189652026699097954120882414001154717918997258089353475775017452185, 5917167011870468624934459756466041916210766501691207791054221150438479042997857395302149649641551035080177809428783031566380296513853795548449641628586, 41372363122583466455014083650227416026095961915774665002591710993359438876577512822289349596872352743367616920266534220322805021770081399906934762996032, 28647102763694202026999877209365618843600517790276376715320831598625371231696971200891830639779198173374611170197106904989505701448484935534416324731169, 53461351058252039600406409020962287941814731855470754786484336480708351831993692806078731253573365307629429835558250376047395072489343618190215178696516, 43211630519982808255325055496431416562222405741391065144006747207494590517094963089326646224294212750016402493438856500908215224317253710640894768430281, 8489708911460505185941816612455271338936811013379084567101550260456573945478649038478506124294118197300669469552705017177655827270944844418578645699152, 22739718474207416860681516907108136245175908110579776599221423813780736521274509818317809641049136756126199753989311235943226623196775082849059257738072, 41216499670212294334651280812035668747548709105131700794545752519540336375321441907637985149672677540242864272713496740582094257029359109571709000713825, 48436506165397582669698530270507359120085582624990229731099970062649834008095239898512290025067179859801307370381405935208194802989995664780696159389689, 1585369946799131155304166792386457012394172770118639384910000681642835771323532468563585207012194611439135457247277948695062359471337941009175179750235, 8603288144119666511944003354168237303458523480925560370062388564635953061635422717389647940009966345557089758149833309897265764908036946377403726618906, 64101222620087611592309324709486851372656586138648891623135538258769906088025167941884507437869898345591373545551263183771852460865686465909022927922823, 16527144583489800339074589267622703740391892670414596775572362839811603852353263595287933280097926247287643050855717192439454800012237185587025342258030, 43667276680817082856834267636292121806981833777605458119209912299727781374012735950942847681976014650650405115417073655652257330450319405915928655376177, 39140951449701344166515688244374428886790877436502233180291072955127927101012734150869177569984136037272345222078216497684424410082172979920851697773975, 15537931042700254522587611176252004453412359577558220416074867095513378168984740154709389168969110367119587635943911825884344749910502795904913565227171, 57584115592473254303228454322525041631785171154103151093178874729079883455704358742586133432524956311883692239859557427834314150568077783639133527406561, 15902237980034809502971143965910358380816080400139184729125764474998259483264801894369466939263995676073257771273315544988512081225248999046822890564977, 50859432507876871258927044776148363731406483617554361871324332579365392377864999224029880363976243413656509052039814721618557677796897407829481142501716, 50060798173579642460106276365259395020688179551858830324826993612669623395929348865201104783185027263959131007321716038538876728815916511632533475508787, 21093401456079234258633171367778610446554117298173713744762450971193474816596635169881513417411413038931760122717931556008404922107697781138738323563002, 50871264470134644149642093828613407668761384164010018255643103521706312798607261474006789318936113229951254769246573651604524869541390940231104684687828, 65838555702814180296502565256444943340789146155658490130335701086297475619402177576374380169326664726736494368635345919297077269982160643735772030139293, 24183722911773924891963995001641331599594300538730494876239125258440555112551130346374041352293686484865295711516004079542559716598370506355252388731350, 70606983798229863770250838918961585630206515326394820998515905465501611723197873446221977733861919908305182573091789028866133518127760978086624785572904, 11574928020551879788627561129470863705564562907388661456838163800143145198992173457723644287037869966419076396134774957477432556478226898353190935778723, 61029601692381479053663587491935218989230811632558264300601308877354851284048932424730379285115898154959889378242675070408077916548569590745161494020674, 34604770125285800302365085079448294275594244440799617063053747652130859109690225689984871840665734961588683955127558201536801499336385265078556174141724, 11825597588617747085813837160017740648061802450778741359221519197975620769557373411105506691743139890711450252799721855339832409870791189985511619821148, 34221142804688884612787234476210488966584817478740599608446861479556501184308249517667796316433825013495886774426619501938042883318353949169073622932744, 18626654830829475933724422229531521260247749630282640788454897823986815196267646960322528599768563257608682140163517447300417938175281593596472310333259, 15709074995155666536793599438372653599673735072188045774362669512451580013591611414407383605083544686738323270765329148547175040050934619370240766488333, 1807120755932854104162772993352975977760368638030857510642192355770896237772277641435107116319434482498433810059226241520094868716474796133993906931214, 37175875591621937319620824075660098532446211618393274891254086565846020184454461310691428746518208846269028512685632952791283499316042277840066268195129, 14652938444415650146108426727368774911315569390356725236669074038662370902353854430602299285995671388121797270924184989138832895927715432624521826601309, 47503054411496613094174186159972883477343149161393992519368436992417560814175528597285395254700710111273038321292730265852161368920471476449693712252218, 34793266164410375187844704085373206595298873402664366666028335804777378715412285901615379046498740410095606705388808078973507358398160040266718217946420, 235777724023845578015968861685977896665545490030219293563237196041336651532625951991560690649655213041706956579810596768294392894560876103128919580119, 71699058026409903383591705758367140642656320715564592776562414985231704111130111268636522681868943716260492033121836183918600499109157978582867307435478, 5937340281741409173867715448617422850056083505252299835611627207868477902961686067795913449403704616805095770356914061148217655631521545003566311163286, 64970050684346645753410765937802248505636168494626578887182023273794960033653433460563394458144307982586048416865603229619651223215132716189029755965020, 28870151994623151917023631120163925496751172862446820796983669340074436826020543852010174031614232391623084724927387919132365749617232754179670252501288, 69316076200432522853422621078078479151899079890475362712069060151657101527879255706785128065088204453815353722430442067537036693490873329815183509775, 3656051605191401898523989951955450249753486544663894178988712577274662300636794652573077192350683038887211374712971200623563954853720538374525587861947, 59586376996345945899321257213258255736309213120802065827823301801096000077211540336197804819829222638564990740367120689915041923060818536969845303336048, 15209485646348568900613966175730263254996829574333766936919924747188067731995601898247851968054973155712860201835166302413341122127777858826564815332009, 65755944655354291863629481839344898125814080585489634477140449461486313994489712061017959934634948723074739252828514224659794230711270273986941151181246, 50044404782587975442358611321418585899140310908021360331315863141057616552340669011243801143395299815080254884794259990877619054315600014568718678262588, 18558186313286434827342393130857688381981240522540569652973740316924906520700554828290216461503534361328921396613229114436061029645283726932096210928365, 68121379646664377662543670223776546293099986219464564654888075357435343435295885243745380118444351548491552692045476944398276755320279785851733710778053, 69676172471015297584764278648519463973205605601973973954462659583351488700599697084095357354579852852975382605861180382202167440159214607938057506594888, 39868944884482077091789165603089328814636077812394209556130445270433071989411476864469152420597572325645830729366730705237597203343357461240500600362535, 23984225124526499163679989394300108542505969311640364168939273256169801709960904670771326948340213899233512604169808182913494660805720194941581797486789, 35140762457338703522439666809223184036794921565129617900381351263704514634805278362132497435138148263120289598367498165241519353320876411527172006380453, 24710691291453760841127687544504422972359827070499809049833293022746980471322200519845199709962567026745924106667690801956717451739332740526036551644785, 42582526200077717150143034364406179825370961007062721122124035466123261273825712581697916024437162094418224246572238536860392260236391392047271653531524, 67857483194339954482708519285879971058057170331448036301958621715916752108065210839856796360751666320642447394109637904785042539162094111072802047335497, 2599658436887948510146428121143122270311474436315255066097573906424588555325614896291500818473644752988078154748378704726917749596783076943413881775398, 62417511462783839398179767060659880783567096687315782396857233019238764137474740645399882358829642616473826449427654813700282313879746864145085481696994, 25046815174632206886915532324638612752235046746052396556181373371408959007980374964947016992667728355879280189035456444140202956919168084330921175866799, 26746087245003271019093242066186960118445359886088854449367123073505725700064370270771541201830383789978922299669035082389492227282511856195439127986603, 12899941330821578969367955126377518942374396461212099980148272913670808413456822700739908200534046934604705454192034690229329311450091796802978183417118, 34759455078337466713687570837759299391145888134102277551962358024620758688171187801911667844577854548914263100454305449832301751244677050808326765573935, 62641568509833713711570997042380165235664835417880047834887119941106533946838625165485309542062874513558580937837811401775554996056276012858548810747347, 54194019664134441577306366078821449269779438459243001896266057182634402737447514629588811251761251129611153860195003472642962987782051611103708961485272, 9676719975605727589576567594806284175654511463346916758560517020880951689432081269100395625675818196925127997734215947176763303327133107063728652865092, 63566749489727772620392173241354690191479996208515013140899609482323018089891274628587945348053732850402777375616488219134732475021167536614183749124234, 41389623900588800459370336537971008333777146975023702675438708757749752963555785484099714125932669585301871871129676831310055260650788211828337348491635, 47917075128910721336524911506477538308166963835676033239879005679388922099453013708492602384789333571083037290234698623216184215279113464823730289467631, 42078396965923796292197567173986146390599180034726305403980989544300924488594853500670135297251227759567949453084387623824589172575028323672347374791941, 26303467325603478409681425746270561760458104487375750208136288587139525406524153947947748518132616711483856699835473508339705278736292600540239815382909, 70210903943912719585335197681971161149552376713285943471513533016171830587948389001752097220135466501852133147457131249134740746493652843424857558685008, 10982176703594503335099043190281003439554172817765519010960096427582643358491587999013894116717272583614348843361339369352126040302498012513340173620179, 15375296014322542477512079793365451835294548632729239177298243608312496055206983209051785207816356014706827464682118103802848458765231022530576526601610, 60741281657044949725279101097916718408759978002888427225701082044375050708404243485772424286061753927582296860956198565404203687044663002010199141883054, 51453860908549486935732242355904656953839434743576398315040968465095709554302378990788844834564479090576226704624193613651209306174501876260882175512600, 42121429843235634165003593566253812713226165431603117921955402685633741429269868521680013286432815656510584597940543612666107258425775935790786790012041, 75847336522995708598859507481988194486014177305660997189842728336432951513069707589487951184161881119260090343324285618931758405413108075158339567925903, 65758341817222621457885108916596158755098306658220921631792142654742204146490776266664280599781759820995333825069037428985525987702654906233411792587673, 15752213867601716547875293001866113163887582411052023985266075351056384315464535935735251239301973973233286836062255507777260674731895530600057333994665, 11151506009425616448244747739591250923500688700709156802826028410961247750111513167162557346776825044249732147604063296508981593009108961067551626395468, 24988307810903416422223700059042860807188507865378899213217629974481150832035797596850622418574087799771865200841087717335083639492611011968919584986991, 19188983999068145211485730840887302107035995560988908325822555747788727142296909943420991730736407232657762626482614632643567904876131676294106469080567, 49165807149291610078767263213011932229369890095374948339130583996779251886618924483782989424700910216292003196618943704463960760836284727712556416138720, 20880120825314766313470865125308572795577662008420147141189550790502101907656949439065273036601014525812307321695409142098153427350456159779924065995426, 3134148277638552172931615388909963243267631440500151801678408733633678460466625580372490623855596910321277808417815986593695645228186837564359773545208, 76027513376813747014021359611570577983815818102025816667258692296115385413227296619875774704856616068742697489757991264586446726640812185996619526500868, 9576386300219383458921907336704987148002255976652861754527672989041213499573772344464927344170160854134801169030299424714027104595802440175290118115467, 47846312343889535970416011840273559470023183338680746515101124658408961305018438134079804670804491884363672682872663103910308908246260073683029778116394, 16836020225895041283399865570278952563361372411312099179664436864693089583825672663104654006872379721154178277022850302378558639898531813871944866012688, 29312555443866353115375285797020858933593819317714753848974053207751144798790489316607442702651597786670972424273015577465723971183954317290632255518341, 45952399494660064838144555112298851928990690958591804048587523480566851679383669387866668507436863822348953169424458480096739821837326801953301622926562, 68334876517321835871217564446395717515355168304996149895652706727069147165281984411219162106481594608000995755151779899698717529318256390790021401438718, 25861029641666972527634309013968274542799402009868571607186682711883347548473260695668831750252078832274943353602464264720165568888925706728574087342628, 68551775088688184199771942195355426911668032674229430062997403726538379537067490978577329178497921291686561217843648566010918593439905810598612318905217, 37765025505682583464362211182398757603423382509025947521873112343726694702300573134890794527289002851767037029190171815999811136695377397688834815605025, 4249505767147772196031020651289585799937480050894276528897542147646240685440344617119239879135528543262687454500110733454342336571756916026373576137223, 12211897746552190684252135375038193571224731278828097646293011671737319460987527595630272305866452394238518927533887961137804982383129793243658322073814, 63672159925831702084608593770871378832840634765254242580922793878262780657303215300065343199745082617326364301567988188247544290658412323708309128521112, 5916152400097580259043801191542869219461022009826571612531294723654814844742388313101200734677007620911765056890963706507708736854388938954261090636816, 14317119988771636810566962078982667504680472212731015560163258949791136175315507709882234357375608038567842467558284485862323906865760782946330956519430, 73425426498763600363398477632846027187594993874507584521147927260063731277446622859480454490655597092173511066199697647323557539421105251159917461116448, 51291671008697812263954316353958818245358049801515013402923829127778604245127923912127853869137576703271789663513404617700625997281587078815337810294446, 16764552517838375964591874922821157969132749425046056275194064910709033826102499972685485237677710147299249213993545772193666719202717777304436525138230, 59295557012652744772208090497926508763666861380190571969243245501411454118387516963262188176132218639685609791422928694949362661989298405412386894959364, 65680239245306856298345111605806359497039862013602921288801762280364506136494777241063396949184533793043022857539147614816975238609243733604742559030417, 72375457889148576789811045675763717743813326782917792391377546702617598519587357238716263943784839291085690192526337648486979325162244907674119290503179, 53234077992007207968984629907955923807193864660771571665077871505422718966065301015318200429417886713035533081206849701294144524970607157018727881011421, 15886483931792974203050424700896494469022632750392566017940896092113020011301447115452279047200702841646809408874121286006915340993084644941811925011891, 4000026211601185502106663641762011708725430703734671920980073131891918285295081752549137630953921078183393375323131848411438504218653510143085517924354, 10319649624556731904039447425825069667183347360430256330142417710766254562223686734071109743956144803418154942873286729125709953817180715625501589162545, 2959127299070091142116584970101314098498259209023373122113534164489561723834616597754357457826712259811824721968019042637401460259286073863020743546081, 26966963187874068549615333973802158799875048269647561639319582873986161093336638373947258726531714616272425009280351155372607494769526061426271185799776, 60480379686940304504344210934804247883844503527104600258142856523953218645216216990403655911740533083627163777976245336274909972984546880202034729883312, 27261558287522575971851824442111090365144022873658966480485633047176320843612473205407488091205599851003730101551213929420057107039313052216522197198978, 5924889509968412055641812913053199966953595678605910723404383140816995621145232830288766243387119999521206867701900470658723204158233731531189957564758, 23453156796655450247116141307366623758418077565767073760208454382429546186654265548677867775354067560840816391896631759441083435660495001159025898492686, 76150503404358535746322203310861113340536545623277464771697476586798690077324876584398928162593218798780607052161166996099801460843556940059525992786824, 37727315876172847591393275092226735197131216415762771377741373327831827247473435512306043337156965991700136410696885151255831157825105690279082625332709, 34063446655575684287153287784734254171212485972386063875998727605151998698499957152558118780955043931859154057516779473847326673786233294077986859617690, 47483470590782205333078496439458525138609729122382072733999354756246820163015660201372672052476227811848001151006206216443241731573155888424535367176708, 39218420907233152349337503997750016372701524044569318259499048063748671531881474959351678569430809988119317210858114117053551093965393011243381378492998, 346813155305357896000101560296376715878805746572198412084124073507251650659757384260350199082220679479346402180280656007677537505603012072956567379200, 45220337350144137249456097166594787592336841735274298685371711994002352406886579127021444669722143416211134915968064654027096905338300592093107053708512, 5460012104494377033762803353668672910910932872167923235617032840897986334654385783555614999313086224242950388742840844011136027857375260879396677603020, 37023646144423321174994717117908019318650072460288262938875273128986672114185107589432972031304290211565654988060691997961153590815964538144365251181775, 63177477223445910049201384279690078930019819284264306067500875252847796215965700799007341759196250450491593055470958720571995993265879745352512656382848, 1700583012951649590611729034981286100342721588558142880964582566799910787514220066268682066981428229558226944161013518056229007812176089692828860741392, 17246038765173067313249878215359330957527587326662502645985291635246053470015915728537330740772303686721906455426913214534530261079901607192934039938060, 45987434147399996197496782026993298557958954570476732783848760609793549635871429620277069591160239426699116842877955529435739418658862835669098411826316, 21111490547303152987944854108036303223281643522396150653972569704379156697301910516727830184770144662770080107913540137717531007645289253745952440414926, 10698232879034106801260353759116257884533008949848502754162380992641437894367605208136298588395112435423177990947470598835570681171317007264887720823778, 54293643078851172364687836934990821579687484157127703064858191752204436487026179374856533544917557799042002597904530828982489891703237561281336459590518, 47797005580077273834483109591754793806985949961317398846769483505668568755603394284565164912646840149645763801903493468755606222509979288885436039797214, 37386506628153260384840150994124701181836200890809074083427785298815850467904026208990622829408207112968603273995655647351172691130659109869622941513399, 13057205711934046467118008739652612675758052758290552436105179764903448469199957925782089342100034435811618076856898039125384846873718510721165423899617, 18016141907808433145961025284467589788900284749942923516457310468709437001788966178751079198067783831673559463585356851811413814896939807067475555427374, 28185214541499079104899299096705844476508797918674889724218918359491538627046768060739267262641563085978395547302726213511677754065988144474006421669919, 8541173904106443905299905768662395072832935944800738204096451433781271007344649650999312461498262780266939438629628997360503524609987694055871540797822, 55583856938965878851727772532012615591107008734179599213849731144139750332990774963054496728870626955960023548737488241552231532876910895970717980723626, 73126878881701489711684528170287200941163894464677667890357697623803069282892472939945202511068349041064012766273020456331595582239718607715580058967921, 70354401173234203817094603858861728539350610438961386996586323986304956626309069628495646684906850309442426229300586236137286868518741887422968392162548, 8914284227759075166669843800606112854269465008336756701964119837078732698537791220276520358004294502231788167963298136537379442577658229609166991435663, 71679986255547965813146878140040664201073433340974131720089263707910307438689531571321153842267530643245284971416280923014280802420073531897677737784480, 12700447152069741878296970568845043035888752941098126195431952022535521184822464642258479573298459505834137899501751562570215414736024639835136989283837, 6343004739661668027332689782225036016497158024551360141260369562409298110062110418091776522944654709730459185916638767661342308594945318353078260927349, 63964337492108130229534104366403606549429509425838893610762333683602786560375188874744626561075352358482069214498737114463864688224040094143695973321979, 67331564851630274889744575564877053915024320348750381733860879963760029288286952415043130610380611202287853110449108590432736764101996881476127456612908, 53280882069162605530191514443798777810028687362597894103548425458220909107156582202503516464523795628658208894147158134959433009893999958404472326887421, 33987412638079761735126555460021225568819079582348419476130572631524190951142125555279430092745231216914642104268144970982726216308555881726629242470610, 13682406178752200853488921722342196537145987369704113476544421137346145516814433815172365070204243148827801660590665538792993163703633151871356444406959, 59463989125735016166555373271475329218895751331847622880739844997590477284788570075116983616019629056762256994818763091149753839468824722562416533043843, 67281682017361977913152739570150548267207777610917492408365814330418488902058223459045634717266171571439824557859718739925029610690419177548771060547694, 39405781498711220413739963695737002658793585701279503786490288662610492817823621117021234029885675098802400891723678776479565707731211683846374263316873, 53034807419358874766350432376315742395296988744022530785117462484846925513344688866349068005871824739673532913987445237461471468400241186927222857371834, 68305629722812234698423066134000790386970292527553321835797323301872488612831063496859128755927745930236100965836720379665554220277417403641562506589739, 15838477469714165090920618367681569358742354857430493842822269635842365646470133405526909343100727954425645887159301780057362634821410546797188280600973, 24406667934205773393486573213298175430629511700972743156092216312470305819697796258655710647669449052724920514990995515510027140733652668755162210879284, 68460243344752374579091832429666515661775987782765587913153602252111004705931127037248902092418367233502792799588802584226718845415421737479907804077611, 63808325950210035810812291635020630613732453561277058010602422073363230632345954950950233595453773160105621255639806986604615621453822332892789828462090, 35920729037346907063152399926080706264554331849560440381191227037937910244659464632447084476697840313861056020706495596126485303699013742182912707172975, 70315041903670157336851359766913844259670523706324294379204277248685999742047453561977925733597786796424146533733873673211660303409007875211743693703450, 39300531126860319955398345847761010603834225325535364925973189673883589019704883130648163179767141337507300067661030698253528221916592525918624340607537, 15496845894895615630021254140566466646250515307806313944390059489493636414202320808813409873352911875321240477276777125460299625425443517127346136060402, 6918931991334214049432302933214038877664252698312543806498810568265540530745938020106356587006559879317556154131091801485516823150639771462068552490458, 13284319826136226129231185037901985819553434334436034136363422696599972727231112997735289148332196516271619405264890626985179077260440615779761000533675, 47141354451986229521055621338816842478003758611988390046169176610982917702117914199406800715608779829266151978859414114993007913651989935003014956276172, 62006071231519162075067533854248673825540723340885150250907087023728863043449786611822047715700318722376817127112362733271740625676783440798426908449101, 63893521915695074076473015870298955838191664815517808757499000857893428891197252747360448837407785054229725838898014349928665255821170162098307539344307, 53724997828497244329408633732485843721280646497077186636538276560039817034467049143979659252524650609122526779152238242200009648428459318191364710668758, 59560026843867449601276263740933112576182129239752897447857785482266968806850863675639974741623809306675891510190099978299125663568621065833548636364530, 40908904103345585788262408080445592912077785202466130402193215696781356453887694866479723318713262095397682184771025397015406424244516593134998423540293, 21520846393831470685610096190168502256530920634386412660925756889910811879936477244071180593183278964080595838026896057947192168361175044065775753001472, 71994121934100897695373777005150806654834175335935905432800180220212844161938577456202364343367762384804519329089155317640274999082541777992495590496300, 59953753983754938792876611451670073996692753691715543251991783347838397186003557839758271745884505324101699352687982352675858568077550526416572161213218, 32018619708338154045357870379406367509414130390075786097563998491238705394761106321287493739342215745501191759206980684126857845949108887540197973688400, 19753200456167466465779432336842541030557413397596794468519345155114986012441764419115444925556673818310817249150486960437725537702448521078373504867565, 7342484858213250235462608889213386080064726860046853081716849206494415366815619844020076108010255128616757216474086252862052951751272920557333252010431, 4769896687715967889336481310203290840512712756999532930891000782787932528428270382724343267441239836234899104850512445829826485709802266593256527297538, 74355004258607576571833753840053548463378928267424658977196161874473156579212738683557688699040100682847094105589799689843205305201454653584801640872249, 6690892016551814532110082014788257179806167058472941857479165541743120455147037200870473223869330191373716321809815790713607069279076031653761661498152, 20929231349749029774507043474913656384295114733554322493333103320239789344142773690393384176681858129568549611334486303260091934120991115068065757099304, 17153283710807583417797086518064762512344132499163280505223698478090291002458606163847203257279411593037898263419480619904785414327965511942845045917778, 22050651142736213565244963818664170172032916896662073301155387192243089695489247087391670138735276225579775431936391388626697441900275744645141428022189, 50937819965132153811444565518964927860475724053299129557722050639198908074429589460667005191838429306196635373570825296681353003427220426130286971585939, 58913284462604187700172393158100310168635473835280983484905632522707627578956876728290392755044023467406825316230706821238436272638921714237556770859104, 17681890152946896225972804441881107507903984131878871289374213139906663030958773969339053682624067346901991714169068086996858271362082589139087115054292, 3909112468307243293324758000901176555871642123266849529594698077998545905775916220352604577315589652297068228906040474063596051918710761329690286227933, 26659357996912432362440742895222637274276390173496378252980802667664532931418023547469963558051869368670035728144595039473629042831713113176157537965085, 17179226767528485522234897181377818519983080414340110997618943993801738768695017677485273725010927951188829959293549597122347814093251802798150160484484, 19844433737083054737496998287597016986512276379827687999223100265664593048556212270024309974344283154237055912105437530884588065558856906602096195808242, 47348710551114046556019331306794334756808275356761888394461758029243482669094351826152778467123320068123601738366945029608823621120671776870709906375117, 9700117555541147957162539236799929299304670997996359585230076707723964209982089821563932293396563832179879999190357045199347391324979469059773776588627, 13467002873626636888949523271031927213159346608965094817646302401288661282610791478079736771259321566155237819209065435898148651759189622569101507485715, 63037961235817497070200076262785758477371602688561664152916441494722106004437031909053699035623597319059285567182742183641167584128065475289227729777632, 64218176089111895416869027246603819970664313506455920488148791215602497569336950361142384744880154632841827794749450034276833675991153288511197242689683, 47942263513439392830167504616104953960109996199015457630131745546068423701013642403323839156160826426619128873229034532556824671458723559069019818844664, 68742746222182563249219749720388662956433689017106697510006439927726538907944533506432387677351240369908865156490610628224604208935896518456792275951386, 52212644024277302202964993748543423030284246877586585223549426038195599560460361521694871178577347471545868137719848759593471592105056983977953734420504, 70264906652847626089535377366020042773837334827875270446429461263902560176829906570391678559378185295380703037786129287917380381287801134465465850277689, 70338735306991917918870792762895693400859231411804513011341248280823069527131025167916532212139891844804984508688078627963308722454289725189496741592783, 11202943024812091871968653090774694646166527588230230055019610642288376456094708642854597051283662781541220199344624011347563372208585467149576852176942, 45465287772079811194403031363838060966264660784435391586286323915162071710978408348641606715517047525841527692603591534466833484617776719296902254451809, 15169623996435078849216247400427343363968733516560810866651811037320678250903315110528158438221622688297331087485255287010416118126711779737721856328337, 28852475740061878372356478463808810042887244041514447822647154314012875742232208435189321135142249111535515768003337785061252044994754401654492928310569, 5964830405726355845868918682783030011195532635722675073707557787272120274893377363927170466481373691893436275201727030031846950955144759398184269785791, 34240000270864477532075102450968450839470355528222720094068701617005525747220229570079432765968261626445996576859553932062082807188947122110205121541573, 36066847009381278750262267643160682991490266290788266279454640758898653971700345576937422987472907571638424055138191448503121311206068403152358903727931, 11170091007234975852711136174576640764201643584673042209824904622333149479149743689621256091273212460852711241325787976935346940110932656520985022456280, 58258126945548764950797717782798700624779811959209396814323548509396126011391646953885580742437208484260400477925904686859314497837461751795642440123737, 19967926920673152856540078688569687894710262985783180877581399859282901459026334508029201347173518578230966148855216358303416030336039471203130056025847, 23595548276608645278366664833783341231551328905679099443768564892841143279319379101358803895431983463285466294746298308657854039318187145804362431897564, 2893474370961335486456525824174663168081310809497129676211358076233834398745859402822323873444488074719052580697214253881106450534065425461738291869558, 5958907829034425034060316070647535655459615550109982419322554756251664155034664518669276533235954875314578002477545778915463022354241496629192604779196, 27788566883685737903481747231933802166299928088919432671260904020088637407292302594730412087020004041723078159004193447947542516090218561430792231480922, 20532093112179185521013377866112742417812622082022290708449532178388359732865119787523382224112648787182208662206608003197496180647105678758158192400715, 53650577218203110600410729325998398766865814136267255360061172788801435890073996725463408842308335996720339673250282900111659334006005865543492882410994, 27945606735686322555814229684881151888663150442470178076013292048060839982203053567640973752973606459118462199368045579874974993094749585683152306114353, 7830111257927859573531774147894277110055421603464794311873488150838576658890506727221887391800809154699966290549716428882127868574637820957455771454946, 25025808677568131096842775102792540807686366181393166426022508716670220871341079639434019763537052343485081027257058743353860070591961282205809544500182, 5727554508299281734853143508379520041502848342636591640239397030993361937011007794354012913783223878938187192585041630893973877566528148234547516190549, 34125297955221973416857421179727086657998910466291260285578023763300602193457505573438526997539188005416829176125101756371491215872928342534317152560632, 32748794215539175827451064809169640707872656691637312790248785369034804895807371648792467471366168858175551862032815723885968389112394766296982682443669, 19316062337601046084359756740917069089224659580679757830844402882574641776835008814717493659219551992308545704093654161563862554123430967564362043544475, 16698150154757920977809280429499684949586664950572392192530208431996083807110717281687762672769576510155761079366746466550237192996169124113339334886230, 44572056955848609010373092439149356067260311771322096152721745227413956103682879244155534554941522431647827072846297085468860260003046353502705163208246, 27628575438344418993708339803452443890754069104828236665940305554239599902121186251891130374253429078333471004275298197440209461188118994332259999120164, 61919652562044972586438492785212427980643594673222454260723387039610192124396273187701658792233976764341751602543127060384407044689376048608848519817966, 46109764189688329101004508471171450628496264955374314980452086114935940284534425097345137553792317990951285615961627798248025371385228530104733124807466, 46817387909791035117400619877531601085593430973492709899023738884533565717056702943707383750398878694854456668238661907490893742791290178958747041681661, 59056224920609792204565568830061390745355488565348333616939229708289518825178885105132973296275188941665728400536826108349556934037483523802869792969716, 66604984921500741665478926723143420146438008068509389500728173853359052714091540238730324836724525809382581628360434354102848448924156047215001921555337, 31419582430779462840265313481263250807512794931203141071416250525469576085849479844947749880276719895647109269316672096266294357898786379072006529876864, 39183832730973061755201647330753616948134226115790320443363338294219451770753694348259167324654888119971382851094286357667963928230844906403886283289603, 3283255784320516413168899839829830028094602407822730101434806505467144706365783146560674309642101764920423301535255518747699612103072011492758793346946, 33368835974991525266725023131287562136839356113213003074639977323208007298803414289567135487257122997245456354564103035169531096968774429702946303497005, 69846025000402574364962470590372113840860535424086059210489025038699977139863035493677207474408680292062773766558077221180073317914557709977751070278701, 34224232632002355134365134629936005598177140616238858498314305970780852215452788902032135977405618831573456053924472889839514221495216331158722016210045, 65658980938469147193290995330802413952882415964793941700703938082218727023573782508973634540422819521500781964327919480012170455893980979452781727496450, 9665250348154536654206530131694515665172789483002642996612304591358982054881243090223340150894464762416439064809966191601896552757074713738589101038945, 8284215764601217981544785999422488229859061814390197195042613376491836774363916339272149964393696441572819237956327108891284365148450554717902579008885, 53839210761275384122812678155375624236213180995083637849090835596108532323779151952329262056317064448003166882964978836017773003455831766519615849734309, 8879066950085937295713426375145168962599389613745881844691288681084047755219605949515654929255916456463715160675759365433899307173061948451396093081300, 44846522954890932053452170548384737961090700275209642378685662035957105157761437451596217747093401844478988631729230318383327981353712362273424303455125, 43158163002980268176859470096906775042752252325756903267533186654149503438997066932081638361997913554233587761452222246607235427619695339583560854453989, 52573321691121279494123052995574692408510998007843795734096932344446198410817800561173257074232286807684589742033894643046244979672762218377487299434722, 7897550374384904887513967113216775000773764113952765407625043995683474308691357357102548770113514399030757334911738320038416173083084558400152128218597, 16715592176910978920444709654700402674087729403854503083620096481591569067609291105780994401753704255670785725498133269560763193450380953726654434098377, 13997295715451071253747239124428639199617619156231247326729836233417198543504118262938847989649348778500848314555687607052915438695191930013893628900615, 47229599794488613098124056349473823155280392998354765758670868622165063315177232324540165316843226647506443608478789352548001630604076040168618807914792, 35258213694320046701654200010884312588312321572105544777004280046591344354420706119915893205430664500593588418655204102873984500148524518893396701626955]

plaintext = ''
n = N
for cipher in ct:
if gmpy2.jacobi(cipher, n) == -1:
plaintext += '1'
else:
plaintext += '0'
print(long_to_bytes(int(plaintext, 2)))

所谓的同态加密,简单介绍下

  • 密钥生成

    和RSA一样,先选取两个大素数p和q,N=pq,z是N的二次非剩余中的一个随机数

    pk=(N, z),sk=(p, q)

  • 加密

    明文空间是{0, 1}

    对于明文m,从取随机数$r\in \mathbb{Z}^*_N$,$c=r^2z^m\ mod\ n$

  • 解密

    对于密文c,如果c是模n的二次剩余,则m=0,否则为1

为什么安全呢?

GM加密系统的安全性是基于模n的二次剩余问题。对于私钥的拥有者,知道大整数n的因子分解,求解模n的二次剩余问题是容易的;而对于攻击者,无法获知n的因子分解,求解模n的二次剩余问题是困难的,继而保证了该加密方案的安全性

虽然我连n都分解不了,但是用雅克比可以做出来

Really Awesome CTF

莫得密码学

  • OSINT(Open source intelligence),公开来源情报,社工方向。比如这里有几题就是给一张照片,然后根据图上的信息,在比赛方提供的小地图上标出该照片拍摄的位置,应该要求精确度挺高的

OSINT-Triangles

https://files-2021.ractf.co.uk/challenge-files/25/e206b85e2467a1d7dda65e4954da58b1/triangles.jpg

主要的信息是一个广告牌和指路牌,首先定位是意大利的拉古萨,然后根据指路牌上的一些景点的名字找到

Triangles

OSINT-Skyline(not solve)

Skyline

没有文字信息有点难,wiki上的摩天轮都看了遍,应该不在那上面

OSINT-Silver Darlings

Silver Darlings

这道题有文字信息啊,而且是家知名的宾馆之类的吧,提取照片中的Cafe de la Mairie还有Chambre dhôtes等字样就能直接用搜索引擎搜到,位于法国

OSINT-John Poet

John Poet

主要抓住R.H.C.,一开始还以为是香水店,最后发现是酒店Rail House Café

image-20210818133239653

OSINT-50m on the Right

50m on the Right

翻译了几乎所有的文字的,但是搜索无果

先来看广告牌上的信息

  • Bistrô是葡萄牙语小酒馆的意思,并不是特定的店名
  • 紧接着的两句话,上面一句是葡萄牙语Cozinhar com Estilo,Saborear com Prazer,在线翻译是烹饪风格,愉快地品尝,也对应下面英文的解释
  • 接下来两个模块的字有点重影看不清
  • 左下角是三个葡萄牙的电视:sport tv,enfica tv,eleven sports
  • 右下角好像是地图一样的东西,难道是临海的意思?

然后再来看交通指示牌上面混合用着西班牙语,葡萄牙语以及加利西亚语,应该是某些禁止的意思,但没什么用

看到车牌56-UZ-11,查了一下葡萄牙的车牌符合此格式

所以综上应该是葡萄牙或者是葡萄牙上面的西班牙的加利西亚自治区

然后就没有然后了

评论区师傅提醒我了,竟然直接搜葡萄牙 bistro 24就有,这家餐馆的名字确实是叫bistro 24;当初我还以为是24小时营业的意思,还是不能放过细节。也确实该地在葡萄牙沿海

SSTF

Crypto-RSA101

开胃菜题,不会有tutorial

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
# nc rsa101.sstf.site 1104

from base64 import b64encode, b64decode
from Crypto.Util.number import getStrongPrime, bytes_to_long, long_to_bytes
from os import system

p = getStrongPrime(512)
q = getStrongPrime(512)
n = p * q
e = 65537
d = pow(e, -1, (p - 1) * (q - 1))

print("[RSA parameters]")
print("n =", hex(n))
print("e =", hex(e))

def sign(msg):
m = bytes_to_long(msg)
s = pow(m, d, n)
return long_to_bytes(s)

def verify(s):
s = bytes_to_long(s)
v = pow(s, e, n)
return long_to_bytes(v)

def welcome():
print("\nWelcome to command signer/executor.")
print("Menu : 1. Verify and run the signed command")
print(" 2. Generate a signed command")
print(" 3. Base64 encoder")
print(" 4. Exit")

while True:
welcome()
sel = input(" > ").strip()
if sel == "1":
sgn = input("Signed command: ").strip()
sgn = b64decode(sgn)
cmd = verify(sgn)

commands = ["ls -l", "pwd", "id", "cat flag"]
if cmd.decode() in commands:
system(cmd)
else:
print("Possible commands: ", commands)

elif sel == "2":
cmd = input("Base64 encoded command to sign: ")
cmd = b64decode(cmd)
if cmd == b"cat flag":
print("It's forbidden.")
else:
print("Signed command:", b64encode(sign(cmd)).decode())

elif sel == "3":
cmd = input("String to encode: ").strip().encode()
print("Base64 encoded string:", b64encode(cmd).decode())

elif sel == "4":
print("bye.")
exit()

else:
print("Invalid selection.")

大致意思是要用d给cat flag的字节流进行加密才能真正获得flag,这个过程相当于用RSA签名;但是cat flag被滤过,有web那味儿了

虽然可以获得用同一个d签名后的ls -lpwdid,但仔细一想并不能构成什么攻击,我的解释是因为虽然有过了一段时间就换密钥的说法,但是才3次应该还不构成攻击;这条路行不通

不知道有没有命令行的绕过方法,比如用;之类的

看了眼提示。既然另外三个没什么软用,直接从cat flag下手,易得bytes_to_long(b'cat flag')=7161132565001953639=103 * 408479 * 170205956447,全部不行就一个一个来,最后因为遵从
$$
m^d\equiv (m_1m_2m_3)^d\equiv (m_1^d\ mod\ n)(m_2^d\ mod\ n)(m_3^d\ mod\ n)\equiv c\ (mod\ n)\notag
$$
就可以成功在最后拼凑成cat flag,并执行

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#!/usr/bin/env python
# -*- coding: utf-8 -*-

# nc rsa101.sstf.site 1104.
from base64 import b64encode, b64decode
from Crypto.Util.number import getStrongPrime, bytes_to_long, long_to_bytes
from pwn import *

context(log_level='debug')

sh = remote('rsa101.sstf.site', 1104)
sh.recvuntil(b'n =')
n = int(sh.recvline().decode()[3:], 16)

cf = b'cat flag'
cf = bytes_to_long(cf)
d = factor(cf)
mi = []
m = 1
for i in range(len(d)):
sh.recvuntil(b'>')
sh.sendline(b'2')
sh.recvuntil(b'Base64 encoded command to sign:')
sh.sendline(b64encode(long_to_bytes(d[i][0])))
sh.recvuntil(b'Signed command:')
mi.append(sh.recvline())
m *= bytes_to_long(b64decode(mi[i]))

m = m % n
# sh.recvuntil(b'v')
sh.sendline(b'1')
sh.recvuntil(b'Signed command:')
sh.sendline(b64encode(long_to_bytes(m)))
sh.recvline()
sh.recvline()
sh.recvline()
sh.recvline()
sh.recvline()