N1CTF2020crypto Easy RSA?

60 阅读 0 评论 40 点赞

我是靠谱客的博主甜美金针菇，最近开发中收集的这篇文章主要介绍N1CTF2020crypto Easy RSA?，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

task.sage

from Crypto.Util.number import *
import numpy as np
mark = 3**66
def get_random_prime():
total = 0
for i in range(5):
total += mark**i * getRandomNBitInteger(32)
fac = str(factor(total)).split(" * ")
return int(fac[-1])
def get_B(size):
x = np.random.normal(0, 16, size)
return np.rint(x)
p = get_random_prime()
q = get_random_prime()
N = p * q
e = 127
flag = b"N1CTF{************************************}"
secret = np.array(list(flag))
upper = 152989197224467
A = np.random.randint(281474976710655, size=(e, 43))
B = get_B(size=e).astype(np.int64)
linear = (A.dot(secret) + B) % upper
result = []
for l in linear:
result.append(pow(l, e, N))
print(result)
print(N)
np.save("A.npy", A)

代码审计后发现首先要分解N然后还原linear.
从而得到一个LWE问题.(c=a*s+e mod p)
进而尝试解出secret
记第一次得到的随机值为gen_p 第二次得到的随机值为gen_q
易得: $gen_p=k1*p, gen_q=k2*q$
记 $x=3^{66}$
于是可以得到:
$a * b * N = m_8x^8 + m_7x^7 + m_6x^6 + m_5x^5 + m_4x^4 + m_3x^3 + m_2x^2 + m_1x +m_0$
这里的x之前的系数都是来源于getRandomNBitInteger(32)
我们可以发现,相比于x来说,前面的系数很小.
如果我们可以在一个x的格上找到
${v}={m_8,m_7,m_6,m_5,m_4,m_3,m_2,m_1,m_0}$
那么这个向量很可能就是该格的最短向量.
我们构造一个这样的格
$1&0&cdots&x^{8}\ 0&1&cdots&x^{7}\ vdots&vdots&ddots&vdots\ 0&0&cdots&-N\ end{matrix} right]$
$可以很容易地证明 v 在这个格上$
接着使用sage中的LLL算法即可解出 $v$

x=3**66
M=[]
N=32846178930381020200488205307866106934814063650420574397058108582359767867168248452804404660617617281772163916944703994111784849810233870504925762086155249810089376194662501332106637997915467797720063431587510189901
for i in range(9):
temp=[0]*9
temp[i]=1
if i<8:
temp[-1]=x**(8-i)
else:
temp[-1]=-N
M.append(temp)
#print(M)
M=matrix(M)
res=M.LLL()
ans=res[0]
R.<x>=PolynomialRing(ZZ)
f=ans[0]*x^8+ans[1]*x^7+ans[2]*x^6+ans[3]*x^5+ans[4]*x^4+ans[5]*x^3+ans[6]*x^2+ans[7]*x-ans[8]
print(f.factor())
x=3**66
gen_p=2187594805*x^4 + 2330453070*x^3 + 2454571743*x^2 + 2172951063*x + 3997404950
p=gcd(N,gen_p)
print(p)
print(N//p)
#122286683590821384708927559261006610931573935494533014267913695701452160518376584698853935842772049170451497
#268599801432887942388349567231788231269064717981088022136662922349190872076740737541006100017108181256486533

得到p,q后,就可以还原linear了.
在还原linear后.会得到
linear=A*secret+B (mod upper)
即: A*secret=linear-B (mod upper)
可以得到的是,A*secret会是一个向量,而linear-B也是一个向量.我们可以在A*secret所在空间找到一个距离linear最近的向量,由于B比较小,同时这里的维度不是很大,所以A*secret很可能就是这个向量.这样的话,就可以还原secret了.转置一下为并简写为 $S^TA^T=L^T-B^T(mod P)$
可以构造这么一个格.
$P\ A^T\ end{matrix} right]$
P是对角线全为upper的一个矩阵, $A^T$ 是 $A$ 的转置.
我们可以很容易地证明 $S^TA^T$ 在这个格上.(模P)
这样就转成了CVP问题.
通过CVP找到这个向量,然后再求出S即可.

from sage.modules.free_module_integer import IntegerLattice
def CVP(lattice, target):
gram = lattice.gram_schmidt()[0]
t = target
for i in reversed(range(lattice.nrows())):
c = ((t * gram[i]) /(gram[i] * gram[i])).round()
t -= lattice[i] * c
return target - t
p=122286683590821384708927559261006610931573935494533014267913695701452160518376584698853935842772049170451497
q=268599801432887942388349567231788231269064717981088022136662922349190872076740737541006100017108181256486533
import gmpy2
phi=(p-1)*(q-1)
e=127
n=p*q
d=gmpy2.invert(e,phi)
import numpy as np
A=matrix(np.load("A.npy"))
upper = 152989197224467
result=[10288477425403523485764284944564606793323233804941324200200782200158209397397531902793294439013906011802269020576199119417808165241537707558638135816570959064495676432659923114821240050576648313244213150502641256657, 6008567287706918488154025867465897575999435108962518548540454305122513440000208644114113503654780783271257696845239334013762542725310688474030886304184426455565024015645131857695183824236617914662645365812161531223, 12077110016750710361530896595449770084863704718589721316981142095457402853599325931990801198765985755288906934727626028485515459385285948978327190995149566652870795034130529018785797647118734723046605772519331279730, 7389313281825513530314103668195690983574434006952083549695972551809275934779442432405313141441578691318295829187048507003485257378920473632445521021667536732869373513125507923359405810054919686690389603066930301975, 10729369047603914517840226374468391903294874291534302197445023809394235464749950452651157502399695242979556233732973657417215215539522477839337904741946623476747304944452454042412038128184644747708443175205707513929, 21913412275110010044465922357256253857903529999846787829294480978480789422329782704888134347437097437066223457291148758755588233391273531461284061086447508597320450213978481681541380383662771332661455056480161893110, 5187496382393995386432474583594931004192332271690115749496834290981162344903649681469331078491245716116876770555474605768189328526430656419428840718445525702380018135498444181161596204954417669702620639870271315714, 3854725334968605115509302936341562670636324282095021970505339209775065343553699454873780583147528937240585460741554805556671558639949283418822297565302439577736323681629390362416040300962967336578737241968508194622, 31992950003597355018507676089121630852144072864760243643221871942427807476956930047060808724236385583805223848493927583149855415237925338630790754983546492960275076787462423960739889523663905861923759915204826434254, 25274822350529816744399242511195338309363632807462934027951777807046314661965632355692599416024094696391113072124828734858170701497375788670686582207694302991627701339649377844007202181304640190749965046575636916464, 9921242579575069316689674535333997453932386039756506331627997964908260987403279790768310766586220195079797477942795615423763764068800487032933469748674168491068115793357586152642244881397742333467011936146126178726, 32796274167253663954065825732165402982168382335847556445139653488883044705387679812691021122092050607036140085621593105567592483188134193629047041013590906852774365969966581977224767354377970853634082383152529845069, 26420075175810982250843138759497875863437200398400217382205856762645400687177535779719247269987693124330991899381272998921275797318448685261497677665939138085474654341686719105713752035930058232909137429732062178119, 21409204699260866716361378898297548268913429868071929617189382735609991971831122666111380825537240056284316962060089791177286322723056378163364916212011013258517898818809936966816854970125645088959487022798080538324, 24386800869269589952610728262807753602256362561244576563656081347923577020084143569959504380408746395873601324613603031294139347238025102893045806354381129937740558622461243125471959735920766065526598675543194342392, 11422552671008481701371830020382307162478514636107662749165647382845802313862169526316114854920094904140230710271530512068821363911924373138913107206944533517640367634369066861173606190006161032180585448745775032342, 21943929276300324143257581933397134655086499359562691630845923820072050939559915505378570244717103237099710445695484770007918044611458743396533434933292513573107644105378585709321552310292959297898322419259520011660, 5987096599504303359483678292609724868219394978101594475123016008672888758031866014567773906192208695667050277959318913662510932590997779616288757104123716226146606951660943996247183692463077833323038613625335276879, 25854120161895608522885388404662884025173154906879777178385984477074750521417934710229282742987140807223727866886759286494425574070509350089783248868819116666911518387280996577662620811086810546651234378090497042883, 1770330882435095879768102756729252761246277832313556970562101978122454164815903347674347123075255682210576290395150618594769479309869569648877552516117525557979162776851944348144039603364092784125153169223159318146, 30144287101869538701060645788089186806430629031868744193668853637245492984469680712406741277354189678762703789381132779425689661514424209422905903475710662182173514083284138755679065342736942562472400006244023145602, 18497072241048607861544833245231627275271949224548191256419391308479715053346056773389488548912323454479591310469441407677929962373242455719598948134422602282896785631527402269927982134686647022871931991612736484151, 9365750725111198863425920531238720973611906836441992347882827658140063441607167229319999383455374774296230601130796938584250486860608831279431590414653929002461429104409212131714140047193844755401215435131682451815, 17508084146402515547566337295069031497226250075631034428313468666540673755722523075546499472936788193986139595461423054335245588061349032787909946052657937311867183208916506665118283368959810537374318161670434552114, 12063714453748232758511796084340535761907684677988912092490540707418948414141875836459950732680138577811351842940106649902561618353236241630928061126944638204024429235179446759466336911857207571622747021021725744071, 8190712398562568909496935205200115830516767954077275794003028885406380790147558851914479336460594848107557791843527683822930181641096266975204119690962541507388033367788196255327295315511221851142145423603771588416, 7990602915499416507807188269846182544376306979420421455023268461042627962589309056377158298719327178718879512271479645475488759685941116138755737785027450239219250757544068040735765177247478197722234987042670778019, 19358671143926903562160659734405132160578768526995820245680768384171556919879077951281391131424334803416172527913742743406248275267395837102903609807250739581440424012016655356361481742296525587153005884113980646786, 9399501113271256337469041372503667196731184909481461358999706116636904523474345813635317562424809210890954488779076256514113611337054265631451934711497570993416389448564321095024347269447076928827056122775492537885, 7047719301319088157109011961944395707199805730443106692074995984879872601464178108552721144291813287249081022911220640553529145732996653073946592681011650300703529698765329003317261627649979300325336038537223764841, 13132178094541178599220043623508374378293166017219494844928345596155648519015703478029167686648451725422735381869002166845710213207175290908245363168895232777141606787995915485278514149225498543634441451970567924437, 21332258659030078951412138925755907196085879676933625247618814067025833826202474696185947389878892902583811563030104544824335286409036675536400434873198516883369123579998367174988460419092030808043124848747167293321, 32613075578615383125177906417093796900310990662533522055905550850559453599917812984615873140282993314675177634499581785675181433419724608424717213400768899361881897671327120818536583804992185519287510699529193528526, 8788479101255093451970038450840736454819608595822268110903507600544674117186282819261210762816332873397203017091874778749454465814811320210887086851290532467299421975771432737420118004746885312219838692353610197412, 13284550125686056378920579386925210841415276873440943617579944969205063044500030050947770396588619427319563631577936557855698258184232000060886885679553208819722127264547155085068937838203017220289983016473406278947, 20918840124548065896642712996071579843893927167277636287866061843547482732112632824805386079866076733540122423654399661957637965225028428446157393566685141045632326996522453966326424906124666654878772779229743619951, 14480927249754932402734895471397045399161243325698535103512424279838259421807786500539361485055559131561639504801950260329568617979790680579124423671245354055456770074886200500981399016893127322858575169044974318199, 13552527995195587930416486762203325441685638648053500066832769915408011653359557121708018603795101604826453588699101268466707552208636403709046955744107649468756849058384132042142069811899343531345241389300829138261, 24659210973887967225066746467648729617087885926019397696827320016990015879170003215664798949419662315850671485152004510796087585122786955566280503821365245398678188264448946509427516960006861586769627992649944250422, 16071792543605613856607103218718775032658413402168430358742579484052262095056030514626574056825734480783809316797632868642990225509511881395874820291062696767331889336594240915719910350450824341094578764996286911304, 12576653775554804945956182431661922357074161286902771538718931574010439531280019130379060964960747175693192143814250903064023817674997576419853346155182797958152235767256180714159771938530562230842887209540611848842, 24421010046576684575639330208969777828036525241093239584183904402896825834372069367105814720940918594573654938981664551215993962658271675479173472324293326854036999128550504182097607949677366331227094096244253904168, 3959909042351706547171436368942687010248535978684258830765965500111260255266165366008966030400399699631802683472533767736025319764756449579244926173821099303504957098846973342970084657754991061516990535729255753821, 23837960853660639818122356796338444274934399381540842790068319888411756455519704721623099729013928364063020776290255990065827011469480186948662554074901428245785687673388637649700165977905709450885918143857854579410, 14656758983893048361937282399871250451122978923544968461690160080969618721577653583611818604810894068063509707277632664714151017875158423454326933471191395916478283516599959610103645193257430568588484586204219581568, 22015140795246767624674114120952215569852592049895227617537769944646703993825626406546544484742031155303275233318822735003742839254875903295634750690159308721656273966373411523675500052262760836896038757112859355729, 18963349345344469317538801102891513507125057391476230901317085750286623443063686628565544279595620519200606841020737016508394060312770384540288456347012117493173401410415709072164521026520208255878803508619430245711, 12238301914331463002990126775589922101631644429311430795628908337381730516395727551270437009479293974547563267626764870645339385629126034659428692667236399512183442689086667672992127081921275934392899940081357213927, 22536986979049938410959907342087128692812256739448892754694784974331849666608673493990233194456558261841529197138881649300542277583731175611708983667266336344024138736437417188896335006114944305838151361031975630881, 2619396107033636372645814557595249316160746419874071084615542626853825598112348113444047407844029632870915970690847413019559051331934551408416410002055971640918305882029001256066486288445447270821089052957926735716, 28371902868144155026541372387628424521881655100952451332175080304523583676902193702542076235028689638824585221901511275660662216530264680801182042840930874902632320962386533970630409577860240401187412098658217204457, 11001375102320067702124118561172392306783192767391248685842722159159795540987854811205106649809637797655571583591132419125348978426063853208738299319925814078197503645006669659419532186216811736251752250723392566389, 24937313108414568065177468036226659480640527939603523256887831627780404390158279980843339472005844748341141255765005172044952601460726767283470820132834063908248595509699539792332093610151041552028690839893169893247, 14200083537420304361563458202793824408680282696273589058942784707606076384310395902796950283540580713525270268283586419277784445127922588445624344018853392610964147154766562351827628630630755937279466323257423055656, 11731578368901738190025281613004421125168662444763551313316475893065065861064893282933621937339536353844435620175572644350326477036279845412460676326485231149808466551325136225138841851487149058032993632374701506194, 24789782491136268756178316113647230578831091802770115290352366230949062450153843044054933635371261213878522104223496078841478338831677137447821742741906238969598555691003373263581686146386721670742543356648750432802, 8536529672905011387353949148058833239334218589564086840001873845844151291265323993426229485900929433630078407364254099143745946852330651744073064215579965209348603895213615175370753288133627754094676128130046735844, 177869583497801351591287510885288652042303683180909769062176021322938734922225185394927974793630389453881826428069397030075989373728735315319728347416378178902372761656269103378496891294577329760205336889312542365, 15821686053304372586750461934181562118709267170596063927412370164269428649111801430286811265853699600351638479138616780556293479339496982631433097406929339962124869055470858870255319245479738212117896411243191657757, 10059403992111514802952094163458838349485940966999686917776553144285639145830852917476174805690587351774694692596492984378041635525062287447611459889372317322994436111508103215386374341556579580051466993208569502403, 10586252822821836585950962996144158170579188408667883417057082881718581584089064703271323144784042589633788654424386066238374308413679871553106596546101800214253653240902242336797007878165254953846984827986042852375, 20674524294008763197244275777362932136310067882773134884128354170509478198281713483925893886367976266052878159723814938571153806685148784595499326616211312079988497450701010586622920382102721176477513904325786252365, 26765892214007495758506879912498128740923019255666050917060455929951678354965321251559635006985501235012264464046500556350027396060441826210444905030071991482699649695430953105824297990282175675182721836568121671558, 18272477763459069312757332808415667414728804467606583087676583113661215355225407612159936691556533036231257559912893851929359360643062443967855861451202522499300419256576845536905497487648229363557176561026080025595, 16410561691796410621255962700459073041943812787433455388034633233311911213603398258568901435875143107210746562755946543030341167130246203437565877832155001652247993924081524924750119076766611715393820421133770275346, 28596532024110857288148771537348482753137774639277363847382835672579678644373808857735173060933764609317620826833832295482297017780809020358481042994385366488957586372081143947529118297977322558577275216660475766125, 26422802308709452136952962135246720439198597300964892851931348210667084937067059374505704672423101303136322073851439474880067033961815642428030839194912490390568724781583161686379423612009206743654779368490331673242, 12465035108407244639616129235787618215010504982509628017315333249068462038011394554000591847608277876295552028815689849157325119258157190858801180145373770522273655462358887227908031433537636205574071867130951972249, 19614834640307790951296038329594337430647269983919823281923394710680251403856036053234231114089295103370063717680238695913190083538436749407234605692990316537917266007358625104475011565912240840476391309586853441204, 24300428348470922340768530892755687225174002355500380707831968067327980164846586988487163526771414843829300900180233292744171542763813238749770478028051149732060917470965473330672513697872256567036503553726751366678, 1407239044889032879434270904774028034949008484797553938128570245181480147550567970119517413254737095801464131079764307215153606162960516586098746906708868787926930368547383157076454291489853280514778427293730789003, 29893734712606566187870369648564476990492767707101225437485729287504518565902280232136755169115190896563966955065292667670364647739592481189826230625641341806495661624338692563479238023161516528177436642608790611199, 29792911018495707440268482024292260132146302092944416919189938398104321088093685602855714432073184457605812831997006502453371437545589355175970803696235045778786792311916529048903272245978928353790195028794383249570, 1102179529308719041887924833301291654082898969991471740237238360017293602300164360658454926216261725800731211745022533438266990227193503751042866270953228458022206971756391178960024698900704862368538770921833903080, 14336999170932622179924930104580422114088086545949449778571197703695164839826457511016706096344658706181646816418625672299602558100342049511263698591774226068747610873338769721423034832107963776748719776789077348212, 32508531797596408570079548238412600346647076340743903666995661448573344188483914160040918208708221194252533775132852131135370827380632979355360681174245852787638372165099473468402922023797140002754564617034267555594, 29131203762117114024161577828814992433716016141345260106535724880297053936625529619278932673173092864315780499671578914674535310705495806564634940203322100985515847361329038261193224013599117004311817820422529423331, 26874041605256595646613047351181225683182145413243688823224457141654041469532577447749007427107540571375651407915003230494111010374907829700816996540319298344831381834333727821568087164358717924485981371494898996462, 2866496876001192035440651901248591302650780691982400310908436656660773082125136409675879958129641803125522791183131217620774489234995426692650799119674708484805238596538825062207501519484844013381870038250962655080, 22446413107702745621490485534587579178643958566873276011061667137368463896478249135769153718743581908207258020771868623465285632962030527466856049027712466148265455037182464859137847836647343814327615063549729923036, 5636957350329994543803490192698711190533886311016390252924853659935872166954374695246691199664270052797234439944856964597664648365080862682811712305513222540297647014139371957439765008700359119252749026245179232803, 28982896796754018379663161338791229295159484267843554674172576208874161650320005836426975363605286871871973140611147571868804605134681548488725081365340884340611746187845171600509254219619444182880441417047945085311, 30922873297650698575558777403623297309435921788149106709294294787489054560438384602432150266864088828336844402744216256043821920889575541345040130897313776247885381880335198208468239655858604537084419626042164954231, 7989103348184034712815786333684105885683003581241005201497201610477319046247716756076389067773465814318597901353393552374070006642866765969692933034421516578307336044954010275182327357818860046313499753766177098263, 17182361290475393546913531021548812396114394540771968114461013979225575858043418041903829060980939001090026186998867481408559346071150704725677045562277000617078719836723116109012598617164193339249955166243022537561, 29666197715141120746809800047568417339298519614035454019088545071037514245304036377118656305831890599751145616228542075322042904813100962476087519320142604574135800816306476038849461438180962671985103769201883597966, 30128447784046560709873374337493670082590385674722812546801078343093226453891542926917593964720864758391235268038949812664900495189001714861154080961131367544278192271756982299547445394245084691997879026232272035214, 16563809676356034270681481602267335418474843448375176315514069449455694143381979337597172939548249392824719584779325550783740568715947688875483900569118780987714300036782522153707625338714681532628360819961911010854, 27871660167728058178056691413848877033545975505468981376520399939108012757215144288231261548284906977507572942732839408507307667636840230520014107565524887590748742800154957275409089238925962908736113770045230551718, 21493910616749845221385268770674380147800838450063015707016357273716911116245261372408337626345595584785412584405992597456076201648656240726064237114884617675632495374568497771565908967654521049674935265602520098998, 25027116756002281477012560577633459876088855685080982684829337039125436380776200858350031557160859884673944490495767129424684434228054497689438054025868674769807319958925448716569153807237793046533521434948883772644, 1793320582104487713681632819900895339787620576203679814448684744665381099892720535078863039274441347716011606699063058840074833887709178695965895941906232345232549494568533088600405042251503992194686298013914263588, 27481768977297711398189605897412347820331888239116339735969001314938372111800573775056751086607179524780117113935671078984715040443417403104019826809943544144670153307305192843982289663500522682115239494497522066280, 13410428768450411118687089562126682300692696091850486340546898475287137036016126015450116652958644951868240922789125557056677068563711465952011637904569166141956611695335738454882374341355402135835121405057055451122, 3382816648394214899413448643602141515168685299376652464648063336446881638040442876269997899075184787886793329063714656713317234045729631599473672676545613422958685403180714068090453009714111278868537155090663206089, 5406993056580762357216597504436388960777840330732036708095982563878233281584780477815282847919972159397340374458964147950700210855470566789114667570081666473362604305766256720458540441949080973791225971891769277573, 21233661057023347451034156464508532443959373748692257537291001812243143978069568309106889727292712730452976094423511948298492450827858499132678933076535520168156975704088320834438605710599243247921521337870702105726, 14397685378587504623065095778991235287014093467306836553292195069672380312352691465670407020211023494907821993697798180981223298157843547981248067540161915602358416983904906973731251307777280824563257887867098888356, 26865757210418092344191937525945230189799371961549250287074988889106298479874948846312860229769416368654315730148517070476367793050648928290683516103438154277278823236522039211199965616373990832154991958412080201802, 2630347898491536674208671164109771459118291083027357511177433170842198020765342444311361191167727549495917168050013862417088160118231386207547437717406397306512458207613663894755934005410047224006732567174658246562, 13856193112001898317704709144728127618299329916747060470435801824679913883890418656325826190815922010339267451603453448661138664849823180926669277503231329114216916643952490689615108526940574456016006512662310977563, 23078379849519811339722828793711151031174096487760718578873885549519838943528216842617081539007026270432737497493757729715929904013205795003642028559881784376751626338823974960728395724624569266320677897621290341662, 10241837331532491076944511490337055500300179384514563823768902251546880925000870414919268390074562830934140114634739131484604089343644798541562549142918509714166147696423871031805459630149322856596306289230096390986, 23350470565565381908179935876463624317754920810634144046007283775207637458028238451164058623320017489900850470074034506002042325712631890918137184874835148542692391262922343003419659598921506279654032553088696874784, 29754831400694183747354793141459076720864477690068425401002140730777995812809821435489852180197928101463999114900035450001770541729111644141489248195912892735334033338711573559916169900467940452301480542588993740514, 8913161785050416450521303040972775096757405771608349836721900816794125504190402507464930271628659778269708313158478043756827721703409697436516988190864850659939837555147274277827953541614759541802725899893678196718, 11565227995211778061360803557056548564607068988900302538439896698074813760437713533437168580979315644519042477774925016750423116683651324506957514973212782388884991033707639483641560011894204073561809856317851187583, 14949458306165636974156946454411685177630548897973098556930888693560097034546938992583124935606351738614845265023297291043344730766643320781799901342631083150776685749181573286792265476725364082328665996588688292264, 8484260050843391968183711222139456428193931531457098948159265914460022433585729554901543884168787168197010567184192841660284002769184889984884999319283258776784206260322753085505960362967859423134184422989019153633, 14546449823617802513071734125403543928205235283359355732051273735900166578164509398551697488526590614689995338246884895918797392075800453544966488000762299312045872140844091828322749830281913146903068711699406308427, 25122762146629387480416735540383550733497959708261965727940738526388107681329032111092519520487065602213557331551497291662074188300184253727106266654409443261828841294906312998343155917375466674929493229565225665620, 17155358054820441028253817264842489700807457663182669898700533233922544516244029268017332563725767904463869117083632812818849711469882744286937385888461459428279061898538078491468888857869546586057974932734495478825, 2406556143978211742151517455240344217761631401708804933985823675348678120765281066891611231625246210736773357646565586119871973805415595986632223230348474868192202787222139945420444179833023087489331635136433119109, 21326638643282190935834071734462510540193843628096895446876395972711578682170415404511700847398537944192914714279661412693776779568391752833306746369172675991039243480710405500383594332567022311537949288083912728791, 11533436737513726853342666319657427369182938376711606190405242081871710795306996022139719539284164017347544912087206004081964258388034756757717304588648036082152534873737713229391061417701271966961865213659930716341, 17413578205109047658771068072839740992406940681063893781583805499641454557243011256200324434130248631102059039422588994492717289498385207434846910479788035096366240558507577967719276745076314570329313325875973040412, 8234406578294627565433831834927707454372628388452511303481669983357186671547444201636252481859429081803727456246640879621829076512301716038342940535219339778513405599396311823890104884312267896540515397691487120536, 13459949999212470824214369634465815383981400799953114858877412049058917841564198625308323023359023043642281125191158381452405954408015851346675693315716299524318273130292670120927872318597664828264194523092204882495, 6141454293302269130941902553228926010501600751202019970128390236308731437994927036308455578034422561774171239182392579287631146225477637094365165697954261896970793332084132454844270755018149205369576408830302052166, 23636067008429813254108112915881876688518793539128087922362577771246065511694094670428786068798740254162912853481657859420315325967804784438688960459593709033504544816117889783286983065113715253670046945322158942127, 23524864509988180632873990491229945730386323961764029527895002836823913633509065940631515621529321538014384315694576133326275986741377790785857862214510281677159653108851815774076719939787198476039077592481690948959, 19521520440073584337536440663830210329435017295149118444136203950967934826303762930268598795041630609271764989278372336374885203235022737358063297207167509168963818977306694298399130043515332073153193922213856850464, 241501015666258217049261385744765049272477325969631519833064253881751720490332186831414282573136095610970487860870873386389168873265347957074995532708762409590143277822462331095601596955197873953011037335365558151, 18729543846677004666195208525664845273273979671502841171368065869928871570825183914027701464158282129076542200208750289934221321354408336102478518104309759371201435596308570933973153719344083600662872025245555295362, 702736712699134888963826738763109261166485688561673736739639290362204254539820264150475559773993156250783154405238992337254428557499628064385259498058322473807259225735572556608871102134991319333264637060185365887, 16650119322721685660080639811294132937645686368543549809557249786459137768793496810026360416045895027818782128552114155925583203227255106164341033273856318935168044085375032440584373966248976820634104659827857298878, 15252280762480146653079356593702128563958368039614517999433818352009534682383297595671320938413452988542386051276938926010812459384377369531380446161486274690962665186327505377180765616186516975317125109314224212300]
for i in range(len(result)):
result[i]=gmpy2.powmod(result[i],d,n)
C=vector(ZZ,result)
A=A.transpose()
A=list(A)
temp_p=[[0]*127 for i in range(127)]
for i in range(127):
#print(i)
temp_p[i][i]=upper
#print(temp_p[1][1])
lattice=[]
for v in temp_p:
lattice.append(v)
for v in A:
lattice.append(v)
lattice=matrix(lattice)
lattice=IntegerLattice(lattice,lll_reduce=True)
ans=CVP(lattice.reduced_basis,C)
print(ans)
upper=IntegerModRing(upper)
ans=[31087157982797, 104407786039344, 137686226773297, 122706247879898, 3655653435805, 75939712496394, 23231038469245, 62275128959587, 106568566534989, 139979210268501, 79578952325015, 39814231664618, 136423111991450, 127591081894620, 137994322544573, 78604075943622, 114622235852551, 88755932103963, 106116650561108, 110708979497403, 13385264758440, 74235730861253, 100669691706952, 14891138382800, 125542116499610, 133221001164711, 128410414732011, 8591859221697, 100429843011847, 149288233436677, 118497336519202, 151300808743994, 94906614092869, 39866689255817, 102387722052464, 39836963925492, 87282800140967, 7022222126766, 129977203277254, 48759983962723, 63128134859626, 88570138802849, 6826269841999, 151504656089252, 93761934099357, 90593498845283, 73033798174727, 43387506205960, 47906851298708, 98248454178910, 60699627108226, 102052261408519, 26283939450845, 108411937946188, 137962137325525, 48964082685247, 109663630507518, 150859035456151, 114574205419288, 58781294385634, 116079144233649, 41851533914512, 115615624663629, 117345086133188, 13035149717493, 152219947031771, 54143063217021, 28063583119478, 12418419242524, 84997801980242, 76140535711341, 22782669917859, 99440612067143, 107228647755933, 144139270604673, 85556086412900, 128905302611902, 92851087699852, 142117521891608, 119557654940775, 31943733104263, 78303883202308, 64649956954318, 3549522683129, 40014171078833, 13252757299284, 116045625664257, 14664948290035, 65694839686742, 29518525156129, 150705658696748, 143791484820110, 131475164047563, 62428301185416, 4829603681055, 110933884725039, 2018130983233, 7272655468956, 124815479662231, 56240879680809, 95377339254408, 122049458606077, 147635008188344, 31827700267547, 39321382259771, 20624189318562, 12666661347662, 39748156613371, 73341116342109, 120046631622871, 79299889815491, 55335907796247, 104004761239418, 22242893504659, 35814193716089, 69815844744348, 98813297486221, 52344903586945, 78832812920353, 2440395446187, 151978021667337, 16994146588665, 61036562530961, 75402800673509, 32270398644209, 69141116344105, 58412825281162]
ans=matrix(upper,ans)
A=matrix(upper,A)
flag_encode=A.solve_left(ans)
flag=""
for i in list(flag):
flag+=chr(i)
print(flag)
#N1CTF{f55bfc7e-7955-412a-81a9-ed2650b50564}