1z_RSA
观察题目，我们看到给与我们的乘值的高位和pq高位相同，此处我们可以利用进行爆破：
for i in range(200):
PQ = pq+i
x = factor(PQ)
print(i,x)
if len(x) == 2 and int(x[1][0]).bit_length() <= 130:
print(x)
break
爆破后我们即可求得准确的p和q值，常规e和phi存在公因数的rsa板子求解即可，总求解代码如下：
from Crypto.Util.number import *
import gmpy2
from sympy import *
nbit =130
e = 3
n = 18339446336492672809908730785358232636383625709800392830207979464962269419140428722248172110017576390002616004691759163126532392634394976712779777822451878822759056304050545622761060245812934467784888422790178920804822224673755691
M = 36208281423355218604990190624029584747447986456188203264389519699277658026754156377638444926063784368328407938562964768329134840563331354924365667733322
l = 56911058350450672322326236658556745353275014753768458552003425206272938093282425278193278997347671093622024933189270932102361261551908054703317369295189
c = 720286366572443009268610917990845759123049408295363966717060100862857351750759651979922104897091176824666482923148635058966589592286465060161271579501861264957611980854954664798904862706450723639237791023808177615189976108231923
x = [1329227995784915872903807060280344576000000000000000000000000000000000000000,13292279957849158729038070602803445760000000000000000000000000000000000000000]
pq_ = n//(x[0]*x[1])
x1,x2 = (pq_*x[0])//(x[0]*x[1]), (pq_*x[1])//(x[0]*x[1])
pq = pq_-x2
for i in range(200):
PQ = pq+i
x = factor(PQ)
print(i,x)
if len(x) == 2 and int(x[1][0]).bit_length() <= 130:
print(x)
break
# p,q = 855604426214387476576649090490109822073,1213149261930568621267125437333569321667
# p,q = int(p),int(q)
# PQ = int(str(p << 120) + str(q))
# QP = int(str(q << 120) + str(p))
# PP = nextprime((PQ >> 190) * (QP & (2 ** 190 - 1)))
# QQ = nextprime((QP >> 190) * (PQ & (2 ** 190 - 1)))
# N = PP * QQ
# print(PP,QQ,N)
P = 3568645677145678186647847767913853195136375094554794216910078595159477139561591230815568312539748091309459843040473
Q = 214068192062555191214464440527253433970199685522983500319669073855320868671968745050948493965230424975401521253723
N = 763933528218428362740063144747893290714655295576768532896029874141179804730143020017430379534079773751531037961074867132893544981605022026151484151321515584652838724809597675412676810669583078026377048734720511960708515190930979
F.<x> = PolynomialRing(Zmod(P))
e = 3
l = 56911058350450672322326236658556745353275014753768458552003425206272938093282425278193278997347671093622024933189270932102361261551908054703317369295189
c = 720286366572443009268610917990845759123049408295363966717060100862857351750759651979922104897091176824666482923148635058966589592286465060161271579501861264957611980854954664798904862706450723639237791023808177615189976108231923
f = x^3-c
m1 = f.monic().roots()[0][0]
F.<x> = PolynomialRing(Zmod(Q))
e = 3
l = 56911058350450672322326236658556745353275014753768458552003425206272938093282425278193278997347671093622024933189270932102361261551908054703317369295189
c = 720286366572443009268610917990845759123049408295363966717060100862857351750759651979922104897091176824666482923148635058966589592286465060161271579501861264957611980854954664798904862706450723639237791023808177615189976108231923
f = x^3-c
m2 = f.monic().roots()[0][0]
M1 = crt([m1,m2],[P,Q])
....: M1 = crt([int(m1),int(m2)],[int(P),int(Q)])
sage: M1
24672457200034589393505297047440242577008257337526825234723934863290296514122729924421261467575257688017066706504146533804164563554650988765778784270714941168394352554100757883446525403314829670523449584997982975624634855686
sage: int(M1).bit_length()
743
sage: from Crypto.Util.number import *
sage: long_to_bytes(M1)
b'DASCTF{Ar3_Y0u_Su93_Abt139??}\xb6C\xda\x90\xa1\xfb\x14\x1as\xc4Sz\x92\xaeg:Z\x16ESH\xd11\x91\xee\x8aF\x9f\x17\xd6\xbb\xf9\x06i\x9e\xc4l\xfcC\x0c\x00\x9e\xdb\x13\x02+yN\xf0\x85\xad\xfe\xfd&\x97T\xbfd\xac\xf8\xff\xaeq\x06'
sage:
Ezshamir
shamir门限方案，存在32比特的误差，格基规约的思想进行求解，格大致如下：
前75列由于结果对应比特数为32比特，而后100列对应为256比特，所以我们需要将前75列乘以2^256，最终求解代码如下：
from Crypto.Util.number import *
import gmpy2
from Crypto.Cipher import AES
from hashlib import *
from subprocess import check_output
from re import findall
def flatter(M):
z = "[[" + "]\n[".join(" ".join(map(str, row)) for row in M) + "]]"
ret = check_output(["flatter"], input=z.encode())
return matrix(M.nrows(), M.ncols(), map(int, findall(b"-?\\d+", ret)))
p = 1914861180127910915217161496032452354459288330404267938814385633318816795789745430689392291853522228462459760259540145551
msg = [(871685718803663381427930478762339134295053004512609923589551466783266783810259304828550374243064535763376291757646963959, 202160546047966750331912360731430418240633973593625005229082586127891061162361922677243409978233971196981357156050665207), (880630661134451484589856936400581718913135314681369937077374828269467594291354487238721693384105758714624990294669591318, 1095968002726348118037606681187141462053336336722142181092378890939072246257043346524710197351420437134900753767241347071), (2201481802919131040050333908088433208558917203945919199978631826943299343536825970006258238556122903076523292840756434743, 692254736946777374134144410762495005358360246411034340533738679554417430991182506230475828234351704793913692448647675007), (1378304382181829689586748896745391077371970833336011385982116414924775680216930605930619270704824436444608781376558454118, 1349836972600983636760377380443471914884359770040030987799061599827409370783772298884084190105572886840534075250106753145), (1353153805805015283526548792279508930383121644895000056925297797888893262990508466655386951026647093911241738634749231794, 708640659789589986759360580045421230914410242138084549192350870784628479597574645622638880069506009868145944996982225278), (1060943952101159814075555130286870049673510249558382992676797709837360932812847335287824269141102612270742087176360534041, 1039246257482395034113137526078027968667726416005827851568387262127498749146041230779139405404483176650987996444622585854), (2424118466972165402210232064008571072995878364648534891594437945505312271409808703384482184386252162745547514610618028336, 635156696412302837761915637951567688860519995373738062624916498633145442364997312202584276482319362616731324143180341246), (1772241931859851196567261257895529032033057998867860001437142889635454121520207911859978309001300625929738493595845855555, 500604911497932506773931452024208499570885483407547558939058205116845746585850868300414311672651970998734159786902749117), (187044491746709666918227023301039735707457548611767420757592410489694090421689472337383722846260140189038198219461031942, 227360883946968296249705407270310276359769497016888615738491818601296225309783611129587894811655567646792586796017233916), (698522560244433302990615272949028179635002687309158390959480083880213377867539289895143372657572453749378003459093150970, 1438446488346299625609140434323525340139617346663444436909013102079035123226801253230191914228775608263694160574643826415), (1314293541818269470008262253418684239221368418527916534392752287558240541875482130114787897305513520252998018265836595136, 933106402921508526957532367623168847119197804766985507707958985877339350054085035066950570021869141193740290685053960123), (1501745172784237049923522578654390251325669575513607134910901665808936517556360097769749957840258117848678845196676974438, 1516777488301366348170721193695469080262430948767494893352311177358850775942249045078694319757619073073088994542922628861), (1718313250889012550002734353486104431289067168806022987862850465345813017177898627414672453244745977044381286178413506161, 506057417158279773145112367533063233326190899630436097648290976200406049591277922238049560242268646574334872382933403615), (2574114678492270903282456732270950593394194358462333441160509514501148947640703147403802718744307473847235179125898798831, 1503310774908591444184865449721473627976722270933784408676574059139777045024294387334806494605277115228299871854598791166), (1770243408559044970812149306040976785192946281881654467315187543403793080522851914844996680381886937167658398949087446193, 1099237075950355774454839935750271630613513947414691912497783029355832037700530351594087156234712938075324990262460261245), (2166086041023587382902739106621961372440200378327129977520031042444044378994128764308981213008281610274832831816068579582, 662709908868241192557028160616176772511764390044399310771390622778705044736473497185759270701465132475627229112002146287), (2170463762878343673691652149382892550249493539913487563393294153717628928418073705621516968910372026548584895576642432967, 1413676394542378061807394780263485269329077458637078447074464881203630348193024572124672013567573482444837133106653543455), (1129266289804637843248865446624604876222278055268049666382746600434990532837254822384883357227875808573227656504651891817, 1535832745242864345604750984721590856572422259228943440577864210008688452305222147646810543026576688303372824677842288383), (2306555154959167883502684934268021903550464872811594873384525370627065323932167910172723635326929186844444801386870524867, 574207014379682600904001842474004352741607105704886122985304177072984415266547565043126591318153332317051149516485422972), (1724617341290962542300349861015192124473593787607849187241871123866653776294891983393875816012660538610025134685453770248, 1037506311823536647118763707562050051146414393535410677631530307480219373475166677371198285257502421566885284344997084663), (202616766252415923229841624622749382197002736241072130496684863225861466295470440453433729087043063339640795866357221636, 1486069111757435527648291199412538135459418727823506381342991481853059317128849411787275828115963269643450637901851750359), (782072578333357184532047183424922628763983310554137973249125608272717772586145583974361061586170067251618252434433193104, 283757911494107775111019950316083145592345149507512192994272372101655062364071745340414019692327679359235776555825852415), (2197595167942118116042253773798345585826387963460510458606977372991191820486797272252095468231729659915814456157670560486, 955293934596965502510872570415413020132164928134045802395033751487848017887015144832326371969637236306696054523237785589), (1098157283702819563820742199423754909028104781243946454418867995181539307551856844793857199640783377355282394025101300655, 635111390180648841537968959615311456853925067622053148053038395898914597955860998732345527697104011201693008366561317143), (1539369283131984995745859995105101736066475537281347948822432206665809508754710210661232887491808392388057664234877214907, 1873336536033306125287332317304933459481487853852475402907316652085126765046749618993624553154025815108827029610442783458), (2105684701096534411811602939870350859970761398331640507345513836997797916059406457337165075287082983610738904681969289045, 1070056100602518593988818068846549889380286647944194826819905043161724050669042969316031968306712388470995120352413349630), (142489011778634823488933340993644406251365634143001554672065147110660487229716505211502368066478460823953952289740995290, 1600505031347134429197259601839106217157515935077383802359036680943190353630112460191899585397343290624969344500745894703), (554711031900068277207319195022074787064807351540056727585559478009641245829914129658355024028140622126230477378977389537, 65339521639683012798947456976243744037602872322070608133060186211835711806848370610017017866030009537787109068192454654), (532900849979395683891747931991929993723658239680866376615001124559008204600725833769158798743570050012188528983307982345, 334144016771241488303216672075523455061388505657739817526966708251875900758813513342313135616513439456734341083743369135), (869702918099306179247127839502723535611690279734139047798433105147760657329410795136726045654330604238870805984709621246, 1169351283105013313749641940783038490083938869389146122787264490618765187367135121126934960933658038044552677868393266925), (786239400981081690761967926939692614214352370457999126682279606306346828244856149092806342991454830115357428173569519111, 341229317116770102168944480795910149567176593419165900124153031167345358788428115442807890687039322892597408592425778007), (2064213065995911617919315029041029121543167107287437882288959061187785048503282055451690399898250479932109432366548223997, 865205430622864313641681018820800198136329954993789609121686669624009340125228193996720833574248608603224773986947432415), (1996571933560681341081972550429260163713030332385776633835663546385508374790580854691775408939051083454291050879529580125, 559622002964744852554436566542525646157533309978763685146044798881793139644019170010343656282702809565334484141114392471), (1665201866056279622733275067329071022333699015026928761307123522986743452132023670960400981020146860918570153444345681972, 1206659985279999461070238583934930315667638779868565409888110141662803190569415230894181412146290317311945493517622418483), (1515824630378748853880547205191400487565887686063520538971380532161078510669610334484477786016989319170924543667026641318, 154768510600010010017326698396207970330238438685198973674456030784650112353692986269413531937661879315225602124927708924), (2400640362993011976891348699605911902016988451462173893625476704482508356176787307014920885489349704332546642981698540069, 1121421906118323024216284095711804126345276955926784522370067713782427318851230923383318334457757167182928811853910539965), (914679394823164487648957492231711749917619119979512000391828434330805091270968219541264417579001916453063785209093025303, 374627069056072738750323688310128739794138886219071824099120374559973078400286337012659440934169856150484268780102828020), (1021972013999414078223981430633642397558044349935082594710388870307835007718638824792649139809042384573145837264785258692, 102093917357525962153933641992946656421204665316272197308632790969421027148825374536157392412871816080580115446708002591), (1090613002154339666672492884775405717313689831457406446112184992081112549743653583926163772335048052650217605191460964064, 1013686859153230698540678410867250429548404782986370285534810877495709441098450523218264937019132584108142305563714746606), (2161046501022327990933396497482765893753709560942237251106031463450880235879988355009303131242535391464106086265266338474, 1842825126623549349236000977359585068860414649531034170142594564984327572182360450517454690000097975914639809219290654045), (734600260267770729123110997283110745757092649194443870464263775523592639286156519663230810008655565992062564338915033184, 1439472390868656814802271856900227714476824912359664972147156053839098765837149646453806800388007932953080250670815772651), (881335900275714936417588963897633003585264162416587081468620588101288614371107988322661634495058217226298025521720126634, 1438060177355585280770231938473797663421441580729795412881287946986577092068342750409767988724102261013424113586148457982), (876173729780067336779925806297809473013555554668200124165269741312909223647316933287442159368855433236050789576297672813, 584722637090302053439384198012199760324880317678105782762720083676914628942486088928409942979389876557255132127516159991), (1733558429089397683359597663185076627234549140640918522337597781379981378009350733554208954192805660163725305958818509205, 1010477387678444338602582972843701290504497269295430761287923107029938822433731115008623372768060580369747062615441406973), (1758000758086776729345325124199287880198692107697670885448853730203070351345566212118269510767350031899984650531292511829, 1484408939224604508966101404659297622265311898991708197399154932571955375325130297122648740841893311564144118335134464767), (1804131890436486866363129670875272535127829613109307224638927349502815652920038318044827248066297349084047126682198723537, 205851561043462971495790984180238782403371191306463313748537952075031757233102533087892093246459879467418213080624418525), (115055233675952369353652759916228030654313474433562820828539341357745365094094469880187786426435712648771454584499932530, 1176080864489594177205517592453183512444290818765306305520846987245653463202230068116379056777589684194022156652500590286), (2328185963017050382404641363914321749130815400658884925780323745763587492366183441185791654864416499947607965414839983680, 1886972372164945427290729032551681924723044624295253696412030824048931146570915452349880650169939511030432165431905079162), (1187461847839408713851221476312312384869325749843380494840008651043567024911068726332857155522639869883501560564590472502, 14245981570273560431111454126826341091354415427387740559245555665941487543601004914128539171516718107049427670791071455), (1275402030469087379247637832029139314437943507754693234009807154397029994354617242802931983091961356790463942774885431413, 1244618585414033483912499539268357193993901084573974055024618656871349876744646123907837743332137138284077968028988239205), (434412507816189969843251866894800201497317336949194643079967243932448367734854234524383921690504689272627248814185361829, 1193224411748734492892063266412070819051994764468021617840046995194588804893634149301845035319723286201666783735434959871), (967206800413690215868425566102618623559678834432686964828977512828919721907280699739833113197470139412151190023683313494, 1808530961381834386234136376719035780314110457320233165055990056489953593025409242256807470925700807422319096558572795309), (313624779412398332754376720890766035026328871037358868168298423270666735999144035960122672900278781994670311217953770375, 1686899500506262775384473022726677756466624697749756704659992441285341042856582261569357914257097304916151170085370461887), (2503049409019801269651799221722260539204050296212337202096008034125758666888245353212657377647881087341258220743220151950, 1805670425703721038437117454438319230600703158318099419770216013430708468787297957979021344350598998116788430512286857710), (542793615526234040152647477936504636873290026979804505200706031754909176961382452267207291751054204331474258583862955704, 137413216840404664240606423528330611923289618863367088636432169005845572010429296034368451334357274658088690084213739519), (1278727765228747216000039330509641392475448645848420065175572576050796418025108532539983143839105111868933395201633094022, 23388499359309984016274969787898858204391606769507546898645785064534114465222342746534462082168690576567031618802237437), (1012848580192164395816758294581574397534987673377799482227399907475636722043236850766024023620412517564680586256857352143, 1905214326869438439368196073362306288481014496204443072620153943726399155969870686475260450389360494546627630953811148739), (14681804970662677021409260234892378252555735233958673970664432299644093318314837872915339633110893420712659256185701001, 1011761630527797621590321605066946971053085037922024159289431337005985850853467103097812975363878048453898707806902513147), (1285297724752785338545033366325253262303128927017049271006754406539647664563391436762226286574374768602309413720192759993, 1493631305230939817393915729396076315723258260416123252804505906893714637325280535095299471289740565654113670071232495263), (1936455326607738910358536004445045468685935298243245355139607465446389473389575731412354107347767379820812067955096505581, 17221509529814003689149745147239645298120184452011530064684368807629510922529681925724732647573630702864807669020485630), (1712173121206746224826777847167590088908487771935061508185448418705799456315866273530139739504675597716276421618856320329, 863258960233895711001625204805338525869459949675833484269384656157104193362371966225031203968537041681324265578127949567), (122947819386929089053369455928546401519366926955589935482151285368760894784571110782585692673158533373827447719944343791, 1029102739229804972707735760530574223266205866939373652705629746591419564062928935797957680207632040596245681227704817914), (2385767142510533504647214446664898369383090132453476416454822794037991187237960157132343084153289103535309857420295111775, 1761624877069474386824225334992881109136596455709107320013742630575693526591737171363464568721656277644139593399384668014), (812771942753829583712722765469520203663717266127958627830326203252222513862479475416772893289895236549766564327139922612, 1400551965978757484763340299740157171921224208542574495162921941233365483529203665206398541892811136907423472715818784767), (1730447421466464570286474725493766890793606044225883792125770759375672642470742177732074062181325776806752255986611978352, 1227172422842784980554449107675660327741994737748190415035709694965213848256121533465275911556767542681543052337917439991), (884876570094879628298320898305798783174822422253214800767481822053599408285668812621687108791956015225332329856833897849, 753204920370187659065626153785437381083012604855618525406022085513242388007754850086113679887120336586260993544726445815), (2423878693124084232298267862648738136330397292982760413012437397441533882471872339001090243864079240084356627531832647422, 77986001656302970387684242942282141405916785932070787943262406584312194694807333266164831908062494860407574874622803959), (1290185371498453630061135665764650237444736789468400436115999443209964260044045414036036267228562648112405016415084034369, 68976337771940690010768399948574523361633543589446521911372413501313976435844421496476544211566756895340409483041171429), (534185007935476498632058534030834014275044346188926848916387521022740118957225895686427252642167800163347935460364558055, 731879744398464762194277983635893240035937844142280555568092822946046633080006561051406094554262898470573348173297417945), (2009543648096147223331131572743756103868310430657031922289948135024763757031731292638042205835167380178315151642456024876, 864568612425196666545678285566636785636433247142630432401391420609479878443671268150141447157212173236963221732165810175), (1757088643325711453646774590651240485497713141719261877086100356614624931730830270746024611221269656481354818801893802862, 974732470392774737526017597270025996122553373618728789664042196211840392818797860303355085148223560919202565975591828989), (288236986926014229269042124754978817491981631142567735873084199780621570926784314358694003281689620128867232148908447783, 1677180488607905300411659606081989540342864981198203708964066014660249657102993313228752304204059137461689367948628457454), (2357100534536251965755486926312170142467175578829851375102247846264889085384519286073305902768874043332485938824401972401, 701015346799246873651989606339191939588270778423404768025441929439466616345395882534334734331126078737835606277756551038), (361601359553041584651624082197420503156194921051661310152767809536879950298413026398079782027847432778044471125267794148, 338870184820594722235914590766168929044789583242319904735556030852263040707796808350885054449714833051229949699390437343), (437493113470125074131702090577490292225129373521518638964839429915294209870286662477332241046314129156199317300178856910, 304951333972637627160342487320016313244618388459742922018615396895218523409067458512473044675590109759792913998170528746)]
ct = 14058554635665083618818231958810639805770645952778992611953881143316377164307777281092527452513347998950720853358361
a = []
for i in range(100):
a1 = []
for j in range(75):
a1.append((msg[j][0]**i % p)*2**224)
for j in range(101):
if j == i:
a1.append(1)
else:
a1.append(0)
a.append(a1)
# print(a[1])
for i in range(75):
a1 = []
for j in range(176):
if i == j:
a1.append(p*2**224)
else:
a1.append(0)
a.append(a1)
a1 = []
for i in range(75):
a1.append(-msg[i][1]*2**224)
for i in range(101):
a1.append(0)
a1[-1] = 2**256
a.append(a1)
a = matrix(ZZ,a)
a_solve = flatter(a)
for i in a_solve:
if abs(i[-1]) == 2**256:
sol = [abs(j) for j in i[-100:-1]]
key = "".join([str(i) for i in sol])
key = md5(key.encode()).digest()
aes = AES.new(key = key, mode = AES.MODE_ECB)
print(aes.decrypt(long_to_bytes(ct)))
found
from Crypto.Util.number import *
from random import *
from tqdm import tqdm
bits = 1024
l = 138833858362699289505402947409766595473722379891580589518174731439613184249727659678966809301611194545239974736175752769503863392697421092435438747741790652435801956708356186578269272819715592752821497122516109657809748674185639254430403157877064556216401002688452227124543508128414591884297632663910714681207
n = 214189098485907407681203562477141616514627803973812423866137712061520397412283304756125615530911730190509122275581663270324067756428063773995710185422014937638013530995658678484408224195008950739065869752467503449898424403807629035201754909341605483646512086652631108980705938767234014655512244203488129210213088484751842078315616338034946509581920246058635374657554442252420460618886159118637553788160140879059706396460523335509806462257352635091258764319929220939182156189941663585022210802535804264016891744621140144859992731921592420695928759275864955373537480452694672023754214092487216273962896544919015905264313446548396379618341043583032673900608611135254563997519445284222602183035105369017270389887769617942348731416370092842162632579589494341854993600540689280924183073089475208340685636482246115054414077320832052204722015428500812923185709772796221129375539131726373252482799298746655947376656143301849009181701495003174228813534439192414768762803822975277797520157025175837722175072241107
e1 = 228246137071395297228647198378234575667
ed = 8238783462304466047370608758999664260116370123313022088538091162770601739116628806460542503654403361322931229200817491683096695046254053538710523477982774850621979868926682997393573131262930645387042545807254462907502249936746101134745335780459335767976492133149192198880107516742633966664923533160167069625322094242414191994000927842976472080411237834215691897822371792754587587715760051582955795834883174474583440371035173351136370107484245425758954400434828144460697864191261513214008084848001467959369934964428291290009392620134215667173457413630882523557102057539902909381706460767916715499306316003286608457624713509816056636249181986636842368337873445101552453774405927824096616431732124001038586048766823358751593885500314021939046991953062562270782883182855487098328026196086288533138907969729187779739950764344200364360079479047132746676799216491472345637845220255139152063453462176656553357596450484408472263570570448409671724853674399060252094955913831086556844240273178815236110565265190938731402297513542863173575371193878977
leak1 = 63782905210425530505481328470901215858602521952143268285063726975781165023862017491713165035148561758359744187691236004961476685244204729186881465294593870263295057863529224333542417669099353919134017169079021119796312127454942459097916913630160780015465159099215782449518378655317557377730943183040588156411578967503892807601657964531263531800827109319360771506028467872403505576255454079928964831924379679811693997670940970879328723956168008599678202445646778122559604109680197340923640067256165995420276085239676074114984790470621236336955442487022895961512902129409872825988384566511568931733560589196495514916064010319354972344856680662983166422683519534959690898549129176191205471975798892082872953657585129852579114400603842863919636216016448322273003250153436580085016262564726570590917521967949071809656413167808022466093370500545030093675230568578130810948637578959017259848848965235015851786609346028580181557524008598197188435907179498427167374290247239043475093622634785391672663701563780
leak2 = 164672413727166337721772866174120090001862616525169315969424174412610694486913567414752676879059000161543960191013302451482547492432115422013012298207836023164304846473827400728343336837942904216130312606263701738236734690810362403432673024164173553927215310314954308227523856745581991136694642282091216197557529027661009649424727525610143053300188875828126262928055570667149587498799717883989617748569211692521249022845364829999098999961242961288235871016302642964967134624027387692331993011337128668923750920957011101171731606359456882239434664044073802224898066537743795029258834874316830952385525877115357530711935126892113666494741955018064580597273121999829121331202610749992150039102390905826245578147065592557989341002712478086016329470790557522670767213438205465130632789767891535615426167314729003703510227816955522793268816231554088672856958206359854051313036334217540137808313082440476308616336781858361392907337038725576212779598635717453175121497869836504186991949457946397544924556583220
data = [193603701385184594048276446297744737347844155455814199029229254370819095264220091974816768902119954926302801843118379533491441884584844862023717354363708931808754214591949274005116312602470266455224300745234378334739914442825957439676825816095286879671572856543573545412426697260350097106803125967045751538098379621554276706631902573968990932601545418908413611604795306678592420345368691508562784200191380882967774951366660610843674931403729350555093525384690652277519795623276235852980416858565358154003587878300208098528966832086239417979777391494681625422699075412054104555896375767200357780876214697482279539710617118624420492042212547431773629635909699586152943845737306422831568007133429913359996553231286016257371771084485222883699365371680464830578176541643800648575916368592100327219233106270736571096051012729364523664646596211619481067284511430638593710269523511115314879651675455928382531667709288358296983594144246374318217425898507659427332121250143906371370125596969310464798423126240249, 83232380612179085215826775913833896343479487597490293209447462059425432761467292984732079051574095682196847182332185514688509237497856017321217461683610482188959719499015629286095774176457491111653557957143999953334057852475101888350978943356388186642898590728812465940108330672190227928625421072749647024169559486983638480319685288547544296403054632634251404824205877193034192901652740716146996859596783202683876256251962212218890324498229265768330077077203057547593303563888024392129443843671073192707033672163475010779991178255053309612338324024330477838635221307103942083495150839612907917081589848058122439842094169468710994236662623064896345386689141107875109648711753412281754135052688257147784328999027173384430726870349245991383171344678832691432716926162465638492315682356063658116939771331253319156940745604345000062001181547782395699365598033029965876642506023695814759189319385499447252988850495864839083230318317981608453608237316346106115145618735235568065107952583780196118328790150668, 124029091531781837962028113090891229294114028863714189021516519574129047489034463881315547790172815327938355138914693838967798779443291333910534381361187962962211286653473935493258148348900967873113580541784043054246605269411211310480597957210474116510188315932965508355182797058421774750514302992909396649836444171237873614791492630901328222719225432769644902694765224307250768110734386675470368037103624198545718645570697628428375762234137964943035358096894458271219594556780565100705603065942562805910805066341463216433921785734441069232766996055943985958999873124870066787588298481039034434476751819151203006932390088920722328035663237500463244782778252107794331963770339097484572423150244547488177952379501831335246484556589748671930152229193892849375083425231974250212167003455883859682356631577573979316259041674248398278005715972754743850288109105734019931884984180815338839040427348281561428946450368116928309897833525540729557152994911327587253232221945691931715727233240239217766670302737797, 183843790887043402011598370503205679765096296266458133303727667969475876955550067091982110668362517989161075686937475587191630156303515396551552747395896439855271453014845870528495608475291770177930209914889772055798265588308998461073614393953301177130478090234899660317573598133689999452854596939233245447620411925677910051195341774760199462465323236659615328986387497112194938688648467440994427880524194706366507582972449860152444844726883830270055690915264386828203868698790531311672618879594353865799279708001022240970903686800926148905846427187554297638489620066186565413471680781555570353090800565169455785422276246128112933238219941576176045528857395489547919586696112825074357320009241545156387826567778313197682430812363865044448037674266021191342500951073854543139099758191759460732927377434328243127385966404963426977560325865114581829641002303741276624429925421529144276258595779792107410344907550974793123288477149591078697881754824614502477971850569510391169576115446384775760103371690229, 77181491333455945581964325242677895484087511641751638314025871031862188693342644422469926996751891933595312224562658710026977124351245625357567306610633026710034325228119776532079710870381262899079582973396369685760835988946858436651701992338270031045842329350320465948557706153142357507371547722657387245712169797514661857231296527340158271569274281050502803588443964415706473620778191218694301701995011516227595325346642614102935318547327371194448611519374355163992727724271920609636416752265268455625828475046309417411350641630824310335290833466766886410952996256873847584658405040284125564777295671150020378326447929383302767250744865021112478842971725353014525757485093025086515069618536327355110519111251250847040981340091015719687780422065271394384964197564928514715001571354599930804427809172147344985789390354365168200779032355336019869878365166731683726800165060752463551011275760601115775930309162497471542196168545689657524323611832924586057251037468277241392800206625479037786453164131995, 73205035147442530516214566541083478692362666963351034174641204890993061156341833361471382741487873993415218899233020829417422641475896996781945068981179750572071381475551179347015232091326075147030318977902658370163575233636401307304118105596868322641969122224481337149842240110750279029669943793523807188344793098836560729793248976539513619414902542761745226667216171972158652220051070681390437970409917700389687006847358602838776592534429644530645228108318238605302552858660163726279648930505220310801443744840742779282348562009764207578257256917013697781985201356590904691201881074465767578202400193526454559744215480337739543855294040255939855585220261434451321167296169707368494834534854246202066172245412926996804327758827974522254706927188752034945933413541030683585047306280808869310753485476053485102398055904623441252859333696664969196044181265131793421817842193722029204872190808835304869795476166974073284194940969149929858850315553170586579171931372841255653797967227240150024403686700318, 130922536449620721874430591834893344565723848082365964975014011192154824561533294364763636501156167569463116422347814651711098794556121000604933883961221890226068691344209984798909070560094790519968140590302350163451597933415038932984088770323319866954739644053901699360711398638558276166591969032158320702311949515391689147215823312531012728672496602856530523058425713194004118786776568670195495029709727771569268007731817731032818592168140535384065850014708458707271415054346637938854605806067654806771791955707476012409629452391154116323782276692248254897822717314913613684100590993004116312109008343947373009165942573493957812296495916988918921330041670596637737127687419791813256185588201214925999361831016131784946056151576400022233684255417352789020121504134033344037825435901589346081468061266546900318139206924847037632306967700883103715011898296806759649283235666950730021534650640616764140909410457672528061603571546896273073945589966941026845451260864816435395290788038177260424513262717147, 96020307736423653849681099694795070685318392824245445231848257362698325458566036467905776769825156536584712839602346179866978464981920356841237715655104343433403974116231994567630132803569400576444622531225108131322496097985483053317699953160469549824368749143254898694578961392541769475761696371400655038962884511045507167846158292753076394297765351578172464979038847441532742344288573442736399426813737731962675826287940983072154853450868147991567341729978830384900766355148407527995483455876179619037540839473665468552119956231652786409322560587534009434185272785914134531600273010117895225594128038118745517974999777061068383501122026199178725628075723534153891577896276333860794903571069058930821070459114902328164990286376387263324567783343401640370228177304680590970952056142474240123353904350590944037465570541270903463939790277478872854503844901980335251732525427700804955963610238700131824229633507486167186619924488205009021735744358474958921593273970059532393434485837844520676695250253818, 70179739856827882014533856258768933317172692318810033540306741590616707369209255146711184424982274791424446113402776415419489619900890685813416198088324683031475573905382337205219919194813095298781099206022303955476518699780836375262573969549719034778449632890439019791098837172928410660181948068014058495402879740138532367574756729124558973222555734037856119443124996050898550301911936236705827128102625880992585253317343783711017535277283723063735482936442251712028665628766822410874182346801488486349311864283205496069261051995801486733862085378587473487850400998268984959754900117535252200774455334314910199051566060772584757900692014336924837851470210768677685669414832993403833367649813099107659677783796393020061413738567093031888744434338562745357883186640322598165729511817308735087619672370347973626978927281950583105981796610501521512515754484015947888094170824846319485769273061345748077326435513773977764989015743820427944157836645251581638303303228323898709077613114299155476100313184864, 175652862673132475686135264158791277818478759588755931484235300532096345677648348588548215587849294084744263688721294017179822791852874995430439770093077380941242256704253340009646924105298769803641006601733958786682523820789623229457197488801223995838476613815010250443077607721307486493845540520896295758708091075424003453148901604173203609500517681152737967682849411739285402305515347569269249451853704828406093324891360458117496271442944605647179886014243335325177990618809463830971905827773785311843128136687528632548334476401223625520208122482489755175042406263025133251070642315226465801303000300019213393276150665866439726799770645200082982057683225700125654562928186376718742163294884560481313657925863409955867645132050087094728187550662632446842091403257126146302052277968469833986267484560410928566363881330254151524449882128468203017476574322404834981270285221728133785929308192500229958517894515501598313596447501741967442356143089865549390247424732308735417202543341648593495568759658573]
# R.<t,r>= PolynomialRing(Zmod(n))
# f2 = sum([int(data[i]) * t ** i for i in range(len(data))]) - leak2
# print(leak2)
#
# te,tmp = 1,t
# for i in bin(e1)[2:][::-1]:
# if i == '1':
# te = (te * tmp) % f2
# tmp = (tmp * tmp) % f2
#
# f1 = r + te - pow(leak1, e1, n)
# h = f1.sylvester_matrix(f2, t).det().univariate_polynomial().monic()
# res = h.small_roots(X = 2 ** 256,epsilon = 0.03)
r = 77477547161688496725906506626131775883966333151442864639104100690032824193233
k2 = (ed-1)//n+1
phi2 = (ed-1)//k2
from z3 import *
s = Solver()
p, q= Ints('p q')
s.add((p - 1) * (p - 2) * (q - 2) * (r - 2) == phi2)
s.add(p ** 2 * q * r == n)
if s.check() == sat:
print(s.model())
p = 168207689659417173628607066039457820275276732311636007089001107530860513351122555769649031031435042743185528528881857626080873859026128498997148721030271703030768717788591275936600239642357340350598106488044312274746860587888105379606096757814370419770414183228756583472285941821276338279728115488001890742673
q = 97707929018805957546753225343143490125285071269910025402668681477127527381672117514147518538470060994557862749309042238326448721045026099601424607832524228224510318920129326794773863846005792678034679056020514793964664097594210383339219122809427128901179158534676129014329576699155669500220463663254504200451
flag = ''
for i in c:
if pow(i,(p - 1) // 2,p) == 1:
flag += '0'
else:
flag += '1'
print(long_to_bytes(int(flag,2)))