Chestnut's blog

且停且忘且随风，且行且看且从容

2025-强网拟态(final)-crypto

发布于 2025-11-29 | 32分钟 | 5703字数 | 浏览量::

开始拿了个三血，好不容易把ctf打完了，但是由于落后太多，队友决定搞别的赛道，最后因为没好好看任务书，痛失1w😭

密码除了777基本都可以ai秒了，所以就先写下777的题解吧

777

题目：

from Crypto.Util.Padding import pad
from Crypto.Util.number import *
from Crypto.Cipher import AES
from random import randint, choices
from hashlib import md5
from secret import flag
import string
import os

m = 16
n = 64
p = getPrime(256)
a = randint(0, p^2 - 1)
Px = bytes_to_long("".join(choices(string.hexdigits.lower(), k = 45)).encode())
Py = bytes_to_long("".join(choices(string.hexdigits.lower(), k = 64)).encode())
b = (Py^2 - Px^3 - a * Px) % p^2
E = EllipticCurve(Zmod(p ^ 2), [a, b])

P = E(Px, Py)
Q = [randint(0, p - 1) * P for _ in range(m)]
c = [os.urandom(m) for _ in range(n)]
R = [sum([x * y for x, y in zip(ci, Q)]) for ci in c]

key = md5(str(sum(Q)).encode()).digest()
aes = AES.new(key = key, mode = AES.MODE_ECB)
ct = aes.encrypt(pad(flag, 16))

with open("output.txt", "w") as f:
    f.write(str(Px % p) + "\n")
    f.write(str([Ri.xy() for Ri in R]) + "\n")
    f.write(ct.hex() + "\n")
92020820868814394988968261411073571398478104763002140061700066014545477552236
[(7832000319321902840924190957670151715675571485860838902321372894997642643673661023957091223514051514913311703968283009805587763430593610229066189899894825, 444825685313585513545849208358663306086154920936288703312594242624507658663896758548493691017995002173226554523050517603110158795338022039757153079367934), (1231655299550013972827619528510625751791973825345338692532318514227001218674580903396417662634357527502279061801025418779677522866993955003760451526407390, 6427654245685315382112196783616297196361326346984196792323745620469216149119440844772524941115107662594603249248630403185036604982562824915358137771728748), (6432796327758238988804887340727451314389424208676705904965119372096555085131434376140753478770461384479389373076108324434861600441685595571757762730611122, 6851023037329568050428787347723369056876702529997328866976365333697487339111012266183981805061548792496406643243684164692130962896552019462568874989596591), (1423655977420968989359080839604162736280419479453252732176736234871386945340904613258160634420851093095580643493101239854137844119565023947993624183932308, 3519715376987604665520863406619131530683708263448866506209893539753021807546272062663152085866098122518099163370386328398460756863286068504631244745193843), (3545567878831312529438800764696484060762827181938251523405843195271139082170261260017415865123197142926595658853606965073041729406826433111377901250075809, 4591777476020597828787399836091706132305277414874856222262736625110518678388733643679959458346458910661041876088286739677718352541912487011818899505990325), (6276204541129895851206450822549898715658329698082026705733412784889040724438918713683672001765004004752945163817976721284136739758261664917864935238406999, 6005207694743735643767250249409069442588553188771823311968286162838623317987732812440912626321576265720391104724406960972827128419871301361662530998872892), (2273007899002357403077961797154434495142823881986690506205507944914174143056031326574716229761811577727445876292621444752202677443796845929957587304731851, 4155406765597365122076234309755319872523369088397649457433596396273342795151749494277776704000691261632231447064828998952641771683102076388723639603857187), (2808632261843274867774419683814321192075649718938830400112890578541740593002748461073456085244994822100146968065569983549789440168698204742120370405166941, 4595317630617247634040884107868557273411400040202055649058077367822220736155036935085235722637599980830836640897705084567949810549146771116728711807226491), (1704707996480073168206824776502609928360395055955675306865337662812231958553679221382587128474490302218474684542255444313201675701465545633860690734055286, 7550557589656611170938151992223019283170907459108799892245479143568742947930574349702012070084201490770536424241437809167257561840062861309817666441045787), (4417418165917724086691239446678868059518140558562900635399653751356621132482607226355585787213048342781621713244546587726714733969955769543936801031481262, 5938208435317039272029132843828198709554193305867447671995280375382696321339237781057614673807314595498492506620269991825036039784092556326080133756775159), (1084783665076903219376349107806920891639407227400399164005136555631438572407050830009689931142415168928432186091795762724224453617253861442568638849785613, 7644535633994316708617341511731555258607873885153584946642223463791954300660648815682428666018873773756213617331411206655414676267807683277089977914889822), (1978534532159494454388773159140061665682403169418807583247868431398808072245650632453615937388729351101618268467935472361774934881373465253893308971802696, 7081198628956149590246701693204043667465322996896685482353043899845910470727644338885714592395030474546156892252366355868360376603677417460156020245411734), (4649017188029587984875725044412568813269908037543145125024966102796173492263236493089716242018069471604242146339536894632784566053275035262483695569742454, 1955545184603289064545842165005948842016338342818296013711137170952926118528872411221325984936883428971755049271650631670790004518752304007941656600280068), (2304848916919727914632838416427751837205398284908239403805457133686041880640444151758046263315840816296184641775933356458396068313532079522545717895821800, 705247675227721441406918331531982193305043625439178922288687556646871104035225926519140339786356519698715972574841902251959529839691924397993926086750302), (9053912322397724083712281419186382951981373834826228146503314111229075776227634088085713647384152306075851602865387592176538167199351210022149824766133891, 6171639950034752564460853528531985550509197096556769691726391464654037395084913224108625927679420491523104270954669880958014138089393895498990698373779816), (4986723676063871003462083814219964442556611821661800751909133061872722266192211789394554129427843147605486281339830592982486798007414898811390215831499951, 8771004514858913141693643749086782820480119930130006977804333125971027943109148602418648175993962419052424218461760972124683804111184174390706944594784991), (7795200089286277798687290059901676152900867961291294736353907787487318226216030930451990278979983541102219855694470637221058541485815816398578882646743483, 7852212908361523696352774616738903741590637324807833955932788461941938159180971794756322703606816656657787839925299005885074701494919357667997835640703263), (3422934079656178873748022756307377952595161025165070764455518119613595330873106558836095266546048795425822410601403426887761752284276680742526024044466883, 6882568660638586919915745277407247580517812793797006545521481538990072012386441672580088347744840968557478673995032158097402548556902990494648347760856685), (1901798007219923877282588227635062081194842040899409682256292058727602804678781572051417502377435717032608451312750976116954909736884579452136297873841605, 4455227945171084137537280107728697521688494855846643943972685068423484137285888614787120646741204979457386389172090606790747476416166314584825918654743961), (835005647255660272215068277664278004628661040046786684336690903708965830739120305779944832601730161127037656328971356411813278929635833204823107970237822, 7670725274522156690491260284641913261514514347955929860572920484471333992231500498914951155416802849454863525804434766489067139904946875141278267467331833), (8951897053859272772356483023534624396409991422111258651103371677871068049109076244034414586932663971700270731365181698932561132351895074764365568654084605, 5027640803201192080369736231259476181493804377784996526797429545343982874129018435177171310695598096473907988115287355961156047667064841468246430890406807), (2105658808019287179792558039106236020623025727454418260107540594821916314691221499331590823306909636125201941069517117309883714365916211540000798271153073, 147800561436770405610963595267328616609477403898949831570906870734146379964976484053025724587470581833823089285450666857063476565702290145998603139924318), (7130194681977755451746180366016252811833900699433598677336347694801056507268628055288415444364900010342161075360729117608371705681470452030364463903477343, 7680079287366207936361626980563511923438130327089825711055834711806674517696005810707019857030734639845710461912829697064444153009781244835744965520353368), (788401349728479676328885016552051915214942452004487693830557213302649998554219518367960645884249653946109245961887664298867981688685278721874085197509079, 3563030654514063294693113672680338345709220804273500078757474796445396659327017240635976265875291158868385945968929551720646063708535671342630747979857417), (1602018545534939236708203564880725692965240041980516990195818727854217241193805878091020469107548363424567526350328553959300778247750776511349402213890227, 7596040946269022006261242439473796678387111060645472879547102196445732979764689664038518792619454411985820177381236948242125873020785557371886917439778925), (5752199097038672946919478957001487477260855595447895783647257692284097657690004559804228009016380270398091504323682520666002224185159849197496329352696919, 4574336977529375895792915715970229385072933758481198462178259357695743283058235353526602836693268529413990048907013091734877159816551744710302253554200470), (183067538240491667039697419224090279275178789543126460963070276905707991706553554874361948757165573309471296369908815793091087150482243978379990943397752, 4024092656102821675961772860851209856658253675866315956759418085602713161632511264378667287017802907284920566465507510960220872591031722173347881131954057), (5966193634361020371843356783211110192595361825336139448193945411031621191450948452366710802622168415374180883664895067701132832546423002367462681264481547, 6018063181438437735974835401702055491857648527032844441457973483089618666103771460182039079932355797786797736284338660921369315921823800016477333034280776), (3795102657173611758316323707705811934626765033865924382115534571748194877297358987445514104787361425605239504683094065006249660767641361534447971529535921, 9427698068836711549582685797691902472811394668483832470094490985752979955481713349589666666245204253415296899163352086951563257305167072268697817895865451), (2577904878613675429117329395638402370742484848591312292153540139449726836524856686759048046407275830310306328149512320003319254867025111480246314986249683, 7348986112942761506352184060501760264882467276364503106019915146432327580601511926170570193062439277615648056837288732706135591229817375213072784738908164), (19381705269582952479629805875471923177386918603193769763010119806110285629356731134568372429161537759723007442943452636791065300701590030688949799211447, 6286040652106586318278156590818304228413480331719424331886505625464892115028397711614801040033961066006715282544903788991558705372998286070143934709297893), (2767195907361083611806485992890207244289959855817142265541207761166700791008745494639955618209309526575718124210542182432082204731471029975075106514222259, 755995866208117484194013889089923683381214534096342270244045203010950776540734858339397776270899914942735639588822825952892502376795453884163864047176244), (1048793186341836445418349698704806663912369845180154831278792041723707892807031074982355282018564533792427783711853361144335519029810172676106183939791528, 3730289845455024052764592780626057501964728482418850830979805065178758188091292913041240915002405956040690496963271359760774894296779522362897738111983414), (850767203815301303900801002227053632826523051336263746441863922486748540572914462938390139918412698710588790437503769510400335320422286377530823888816218, 8060017122111927430499546360306971298443954937160955398609903950537212011337858113666938313070159246747490679743100622200422953285912137690837994319947839), (5930068598450223765586653254624530491158827983167130784772940939001454442182137439976159810474766868089978025605065566074109563938784701442172322916924653, 3622002769197497718238515954189612662859918196882108968645897167269112014384146153726547408919049311678288199584324091176588608842776413365728052414155218), (2146535786146639962940315341429838823736962639638404187021207826168809861354800376714829843953740415909810186889446567066963197881380179231836327793016771, 403533625908769829857240236309234068443255415605535850649511080244940934413992990898576485780943699542596028798716428488758044720046250868019237989737539), (7294953674466136477949453438783785863341106745989225973691001985200150547575332027274655921911078307752657674441790020513621286055145495785656690324365708, 2782831054402374209178003248306005838226688805924359672677380933119852751829805558645635819415324972706712212323312315412488463941460455776447220947188463), (5414020108457834231068677828987022622548695084833508603182621260222381842929122671929789174075542263423152954246220452061945927853168410629487414785600736, 7740628036463490171863448459979829034847125587800340102607944135317230237034829888239477901750424087041441871737923902153900287121234875628772657078729467), (3884650767696067233469532311046758499214077112703345642615260271884577536500014610569881103633940319098857787936823943706826700761864286015162782770092558, 8401201031381614943949900578257973429011967090200091035251243583605918012580283015520360851652552406904385287182655878779470697496731867875511564206701139), (3623245329331100080037200881874588299061220559230260015075645280839422860369257215318116458114851997390743828072709131827358872371935937409888071505315775, 885322482804629291221264334866502603621116229338643457558780696339240287008449043282876488088175277175885324269852600643991855638359630627837343557586216), (4376605911470497017393453219809726034452117435111928492509316251024410563649639563908311035673737946545168394053038370358380613164449366584808548047190994, 6260668829645793014449260502703449862083682781547147252366933997104455667445263508169391243944519670832300729944728521521337424587319681060212995152394473), (7479395642331251546639099189639122109778760270531880920938162220358667635823684203092053304493800520812974433907538383521812437996907394461865205535232236, 1052737876879106907739471788645695257532250293104727777672133812026985875018262039087346339352807560841557795422996064808092025483613769376254667344117510), (554623736483147680587469009026007699467440211456202915596779947090139504889781972625637208968084254530185205089420431378158132623544489597702721695684558, 5042814662720426792147808061914148439375212208463290274194971642709138342010829546377091237931318036476949004071384977336529939976529038932688530344007465), (8093965947299080546275107266862701744860186148076170609341594810120013217916095884058983906675296868483516898112018864952125752150459683590983816139478384, 4852519808225456660668994434422808847964611977050177575356538012027874032915274386644880618362588003585156944922701168011682757106084596809653295846270145), (4606234802851368480307574799176995460965009530629625509272155685933611861369592121519121869121240562637010313033429844415880506456677935721489590167600825, 7393509629154311219948069891588092970132331860213899679880848191958509607265913579506483223721299173873979897858284040035880312446337299862907950371395938), (1776773971563949454218459273710620647185556220867016809412703114252574227538086236047392928876409977248861863943946680993569584737877643682182878649890818, 6691264349228380825302035210418452806460002391937613367434236336363366100139980530323498971834739437365922760864077113483325693588029575376606035368496537), (2476183393535617507137330749042570193023665729355636803582748764264711270766407892458490886915236188782759392065140921686993455430174280287861437740379414, 3836340244029771200303683042880877381400788344400297136279923859296609000572983851990729227823222199341277553022420774881707791605976654606798958083022311), (2281710978855715968012286203113486289556408337054467036099687981078817844818513726614865605090834290726734803875382857926286201708856659912605790641338207, 5949445246107981375644033915397361345332663715572921180218564516295194632494649612595261312147007510550693872096137896128286164349794634475291972628131303), (4216941899836036523495953356453184530117278257669709149458673789440132489256147703283801419119173903888241905231763348960841340660234955184812604367194675, 9398784135953445732545861817441607958218718389674509000115224279606723565309339841443277387919787182925479084298993595536634875069686089122032685652951314), (1062605311375975400777538566901017687008369235899451250515495128358050995996559449710549803879809542709549827975784258548068080019400894301091393032002785, 7833017076679674393389641140938266862121296936528427579738006490822149213872280962432479419485243983947214022923050478943549280528717690195796122824378939), (2439384968905095025144950573845634703550486169099235374247518310002566134346364165557580282956736775168095860987590010171680545254593095116426377057166558, 633268368757363401531122573824014297353073588102647566410491130412178842159946902607936665160713540696281573267047808062361396387035353032130730903964038), (8983023132575618234528631552838576441534442735962242022028236231540997202441492038046573346115315749029576306237043641180405677974842976854774805480900947, 7964577584823326955704549975733437644324419884284382447172761201112292946857104453343309883437433224468495844242723025824875072606796492751082509139246356), (9202163774339702930052477539188219538568835701364725048748173659586429602183390279759450423037898033187480613185904056196043855910252846356428503524584802, 2191005014793929046555023908302442932147079057656038866887280336761305479192075151600123882801745635701139973179068266833438328996542104380297388671290790), (2171878153727980938202126119564637508725080744272715396530846127796959439064029498979938520450347628674447433424347884462320843764759585830653439361096659, 7490921142616162960776726949369862846765201209559215116988148994084528888102661487203967009457885730060519043703520087419555866178701128086672560989716294), (2833536380370293268482593560347669379183887138311227313517785007087192956898724643334211191815163277935130742371505967496708491857730128024026861030082368, 1174217771831591995160556970256846800058555470148501610890919848794238843299807777085203674411465216634476259744068196514904809983181222298156266964990896), (665911421902955568512851595493466718450463371722278894716999178795187571116826652011827522976988440963506368402759535643527628542568885097509598385503082, 1689005586079471999331989840660126259739501794636773142596100869193649828285613407629123914204096257660313788885046526083780622247811838571584188231337631), (2128749083496476521148208711905247419847533164088849807712301815442528103035223188834521253074105438898822698608726190447089965919964676824146425062042340, 8576591182535963673844032617503583488584162594191961843840492516618499034407013314045503497877446690838191968590405984837170404374671115700964442002666668), (3650984148569047306135647180839592436162637123998221991226165509663927341328605067988772694449321362998506685795183453832499099143770256734792818246552123, 4499295145892557745736396430335127900918742953663087260185211138514764162487193655166024054451880406886509589422136540319859382544443721609822107266131999), (4063139595111664223873081309036546070009171358557536775576800037121272282520039934008730646373010066307192128900499981854703133200615107930858845279360264, 9020930347045521774460282072824820683797679002191412407787305388144022464605972480813354633389736180876546775520608025134965742192578319052038561740925801), (751498501435849924160728341592136617274223769162787790087765654229295984653259878156149347541500032213451846843921037653313515334544094162704934460249988, 4932671623121299750128264473311826975086534781678478940866497206417159826413190090174218596620943170167455276059457984074706356513532079547744604393781541), (6926146779455615877715002813301024550808148104608793486446924578849603190274539441737472351880807565944114213683280760046866855045054449896669890021084485, 1308053561392491263959142286245309091146945197055847377855235218815195257744567800813756790056903079336039078999002005136270979219301050583712675714393067), (1600072776861439435527709065723594484599300839305081197118383180839466714290470860971256618590838102578047180631581640180692093479792915101915267527617129, 8102890361311731420232087922093380243170147592566562917888978380243933782231008497775444563436144428591977790410582714386873731087447899730178559694599000), (6467379408268170202516821998742543057974225346588426301006543372458495000714411569223915391327698197143474286461583399922634639154801739000306720776006136, 9234771131215449554785556050394895294768316271607553574884508113524958372365904526439812958214798228881012535849512255030156232041932310347502344888755841), (9410452032352799818953466738470460276199795118264415368770935691754492285371361446792144335811543237354291149324285174344005154056518449182625770980630650, 2346269269700581641202731236246492250613329199001411698278358311547917360851186769019234870838138467111555414672672891372132294240887607029491280842022667)]
11bc7ed97bbe78d20b47be587b5cf5fe3f79c4823d8f56c3057fb0a3b57738bbd2940600bf2520e0fcd7b8d6be5abe98

题目给了
P.x() % p
给了64个R点，可以用下式表示RiR_i,其中的kiPk_iP就是QiQ_i

(k0P,k1P,...,k15P)(c0,0c0,1…c0,62c0,63c1,0c1,1…c1,62c1,63c2,0c2,1…c2,62c2,63⋮⋮…⋮⋮c14,0c14,1…c15,62c15,63c15,0c15,1⋯c16,62c16,63)=(R0,R1,...,R63)(k_0 P, k_1P,...,k_{15}P) \left( \begin{matrix} c_{0,0} & c_{0,1} & \ldots & & c_{0,62} & c_{0,63} \\ c_{1,0} &c_{1,1} & \ldots & & c_{1,62} &c_{1,63} \\ c_{2,0} &c_{2,1} & \ldots & & c_{2,62}& c_{2,63}\\ \vdots & \vdots & \ldots & & \vdots & \vdots \\ c_{14,0} & c_{14,1} & \ldots & & c_{15,62} & c_{15,63}\\ c_{ 15,0} & c_{15,1} & \cdots & &c_{16,62} & c_{16,63}\\ \end{matrix} \right) = (R_0, R_1,...,R_{63})

Ri≡∑j=115ci,jkjP R_i \equiv \sum_{j=1}^{15}{c_{i,j}}k_jP

第一步就是先恢复一下参数，题目给了很多曲线上的点，列式：

yi2−xi3≡axi+bmod  p2y_i^2 - x_i^3 \equiv ax_i +b \mod p^2

把yi2−xi3y_i^2 - x_i^3写作V_i，选取两个点得到：

Vi−Vi+1≡a(xi−xi+1)mod  p2V_i - V_{i+1} \equiv a(x_i - x_{i+1}) \mod p^2

取两组

Vi−Vi+1≡a(xi−xi+1)mod  p2V_i - V_{i+1} \equiv a(x_i - x_{i+1}) \mod p^2

Vj−Vj+1≡a(xj−xj+1)mod  p2V_j - V_{j+1} \equiv a(x_j - x_{j+1}) \mod p^2

1式乘(xj−xj+1)(x_j - x_{j+1})，2式乘(xi−xi+1)(x_i - x_{i+1})相消得到：

(Vj−Vj+1)∗(xi−xi+1)−(Vi−Vi+1)∗(xj−xj+1)≡0mod  p2(V_j - V_{j+1})*(x_i - x_{i+1}) - (V_i - V_{i+1})*(x_j - x_{j+1}) \equiv 0 \mod p^2

然后再取一个这样的式子求gcd就可以得到p2p^2
把p带回a≡(Vi−Vi+1)∗(xi−xi+1)−1mod  p2a \equiv (V_i - V_{i+1})*(x_i - x_{i+1})^{-1} \mod p^2这个式子，就可以求出来
再把a带到b≡yi2−xi3−aximod  p2b \equiv y_i^2 - x_i^3 - ax_i \mod p^2
即可恢复参数
然后观察到P点的生成方式很奇怪

Px = bytes_to_long("".join(choices(string.hexdigits.lower(), k = 45)).encode())
Py = bytes_to_long("".join(choices(string.hexdigits.lower(), k = 64)).encode())

感觉是可以用格恢复的，但是实际上我这道题并没有恢复出P，测试发现我直接使用PxP_x%p当作P'的横坐标，完全把P'当作P来用

R=kP′R = k P'

使用smart attack

vi=∑j=115ci,jkjmod  p v_i = \sum_{j=1}^{15}{c_{i,j}}k_j \mod p

c是0-256的小值，想到用正交格来打

from sage.all import *
from hashlib import md5
from Crypto.Cipher import AES
from Crypto.Util.Padding import unpad
import ast

# ==========================================
# 1. 填入题目数据
# ==========================================
# 从 output.txt 读取
try:
    with open("output.txt", "r") as f:
        Px_val = int(f.readline().strip())
        R_coords = ast.literal_eval(f.readline().strip())
        ct_hex = f.readline().strip()
        ct = bytes.fromhex(ct_hex)
except:
    print("[-] 请确保文件路径正确，或者手动填入 Px, R_coords, ct")
    exit()
print(ct)
# ⚠️ 必须填入题目 print(c) 输出的列表数据 ⚠️
# c 应该是一个包含 64 个 byte string 的列表，或者 64 个整数列表
# 例如: c_data = [b'\x01...', b'\x02...', ...]
# 如果你没有 c 的数据，这道题无法解出 (因为 c 是 os.urandom 生成的)
c_data = []

if not c_data:
    print("[-] Error: 你需要填入 c_data (题目中 print(c) 的输出)")
    print("[-] 如果只有 output.txt，请检查是否遗漏了其他信息来源。")
    # 为了演示代码逻辑，此处不退出，但后续步骤会失败
    # exit()

# ==========================================
# 2. 恢复参数 p, a, b, P
# ==========================================
print("[*] Recovering parameters...")
R_points = [(int(x), int(y)) for x, y in R_coords]

# 恢复 p
vals = [y ** 2 - x ** 3 for x, y in R_points]
diffs = []
for i in range(len(R_points) - 1):
    diffs.append((vals[i] - vals[i + 1], R_points[i][0] - R_points[i + 1][0]))

p2_candidates = []
for i in range(len(diffs) - 1):
    D1, dx1 = diffs[i]
    D2, dx2 = diffs[i + 1]
    # D = a * dx mod p^2 -> D1*dx2 = D2*dx1 mod p^2
    val = D1 * dx2 - D2 * dx1
    if val != 0:
        p2_candidates.append(abs(val))

p2_recovered = p2_candidates[0]
for val in p2_candidates[1:]:
    p2_recovered = gcd(p2_recovered, val)

p = isqrt(p2_recovered)
# 有时候 gcd 可能会包含小因子，取最大的素因子平方根
# 这里假设 p2_recovered 就是 p^2 的倍数
while p % 2 == 0: p //= 2  # 去除可能的因子
# 简单验证
if pow(p, 2) > p2_recovered:  # 如果 p^2 远大于 recover 值，可能取错了，但在 CTF 中通常是对的
    pass
print(f"[+] p = {p}")

# 恢复 a, b
x1, y1 = R_points[0]
x2, y2 = R_points[1]
num = (y1 ** 2 - x1 ** 3) - (y2 ** 2 - x2 ** 3)
den = x1 - x2
a_curve = (num * inverse_mod(den, p ** 2)) % (p ** 2)
b_curve = (y1 ** 2 - x1 ** 3 - a_curve * x1) % (p ** 2)

# 恢复 Py
E_ring = EllipticCurve(Zmod(p ** 2), [a_curve, b_curve])
try:
    P = E_ring.lift_x(Px_val)  # 尝试自动恢复 y
    print(f"[+] P = {P}")
except:
    # 手动恢复 y
    rhs = (Px_val ** 3 + a_curve * Px_val + b_curve) % (p ** 2)
    Py_val = int(Zmod(p ** 2)(rhs).sqrt())
    P = E_ring(Px_val, Py_val)


print(f"[+] P = {P}")

#
# print(f"[+] P = {P}")

# ==========================================
# 3. Smart's Attack (p-adic Logarithm)
# ==========================================
print("[*] Solving DLP modulo p...")
# 提升到 Qp
Qp_field = Qp(p, 2)  # 精度 2 足够
E_Qp = EllipticCurve(Qp_field, [a_curve, b_curve])
E_Fp = EllipticCurve(GF(p), [a_curve, b_curve])
N = E_Fp.order()
print(f"[+] N = {N}")
print(a_curve,b_curve)


def smart_log_simple(G_point, T_point):
    """
    不依赖 Qp 库，直接在 Z/p^2Z 上计算。
    原理：在 Kernel 上，log(P) = X/Y (或者类似线性关系)。
    """
    # 1. 乘上阶 N，将点移入 Kernel (Z/p^2Z 上运算)
    G_ker = N * G_point
    T_ker = N * T_point

    # 2. 提取坐标并转为纯整数 (避免 Mod 类型干扰)
    xg, yg = int(G_ker[0]), int(G_ker[1])
    xt, yt = int(T_ker[0]), int(T_ker[1])

    # 3. 计算斜率 (Log Map): lambda = X / Y
    # 我们要求 k = lambda_T / lambda_G mod p
    # k = (xt / yt) / (xg / yg) = (xt * yg) / (yt * xg)

    # 注意：xg, xt 都是 p 的倍数，直接除以 yg, yt (它们互质于 p)
    # 为了避免精度问题，我们在整数域上交叉相乘

    numerator = xt * yg
    denominator = yt * xg

    # 4. 消除 p 的因子 (因为分子分母都是 p 的倍数)
    # 这一步是解决 "ZeroDivisionError" 的关键
    while numerator % p == 0 and denominator % p == 0:
        numerator //= p
        denominator //= p

    # 5. 在 GF(p) 上做除法
    try:
        k = (numerator * inverse_mod(denominator, p)) % p
        return k
    except ZeroDivisionError:
        print("[-] Error: Denominator is 0 mod p after reduction.")
        return 0


# ==========================================
# 计算 v_mods
# ==========================================
v_mods = []
for i, r_pt in enumerate(R_points):
    # 构造 Sage 点 (在 Z/p^2Z 上)
    R_sage = E_ring(r_pt)
    val = smart_log_simple(P, R_sage)
    v_mods.append(val)
print(v_mods)
B =  v_mods
p = p
m = 64
n = 16
B = vector(B)
def find_ortho_fp(*vecs):
    assert len(set(len(v) for v in vecs)) == 1
    L = block_matrix(ZZ, [[matrix(vecs).T, matrix.identity(len(vecs[0]))], [ZZ(p), 0]])
    print("LLL", L.dimensions())
    nv = len(vecs)
    L[:, :nv] *= p
    L = L.LLL()
    ret = []
    for row in L:
        if row[:nv] == 0:
            ret.append(row[nv:])
    return matrix(ret)


def find_ortho_zz(*vecs):
    assert len(set(len(v) for v in vecs)) == 1
    L = block_matrix(ZZ, [[matrix(vecs).T, matrix.identity(len(vecs[0]))]])
    print("LLL", L.dimensions())
    nv = len(vecs)
    L[:, :nv] *= p
    L = L.LLL()
    ret = []
    for row in L:
        if row[:nv] == 0:
            ret.append(row[nv:])
    return matrix(ret)


Mhe = find_ortho_fp(B)
# print(Mhe)
assert Mhe * B % p == 0
A = find_ortho_zz(*Mhe[: m - n])
print(A)

这个求出来的A，所有数并不是在0~256之间，应该是经过线性变换的，并且测试发现A的最后一行总是等于c的其中一行或者是其中一行的负数，在这个基础上进行线性变换

from sage.all import *

# 1. 这里填入题目给出的完整 B 数据（字符串形式）
# 请把之前题目中那一大段 B 的内容完整粘贴到这里
B_str = """
[-140  -25   47 -128  -32    4  -40   17 -172  -49   32  -83   79  -48  -12   25  -75   67   62   30 -111    3   47  -32  133   53  -89   68  -93  -59   70 -178  -41 -133  -39  119   58 -148   76   94   86   91 -101  -27 -178   55   57  102   52  118  -74   60  -18    7   12    7  139  -49  -10   16   18   14 -101   -6]
[  89  -30  -44  -59  -38   60  -10  126    1  -37   49   15  -27    0  119  177   20 -169  -92 -171    1 -105   63   88 -136 -115 -109 -141   95   43 -118  176   34  -27   56  -38  -19   28    6 -112  -76   17   -4   95  142  -17  -86   30 -103 -211  -95  128  -82  126   21  -96   38  214  141  -50    3  173  -91    0]
[-104   80   81  122  141 -139  190  -89  172  -28    5  -31  -58  220  -33  -79  -17   57   23  143  -95  104 -106   60  -23   24    0   71 -123   -1   55   43  222  115   84   16  -72  185  -39  -39   39 -102  -30 -129  110   75 -148  -63  -95  -34   52    5  121 -130   -1   24 -131 -103 -100   61   59  -13  -12  -25]
[  71  -48 -101   15   -3  -39    2  -12    5   31  -37  119   60  -71   12    2   91 -192   86 -104  -19   47  -40 -181  -33  -78  198   24  -10  -39 -221  107  -84  -43 -157   -8   45   22   -7  -20   35  -55  117  119  117 -121   32    9   17  -38  114  -95  -46  173 -146  -85  127  -90  139   34    2 -140  121  -52]
[  -4 -102   46  -27  -76  107 -101 -107   48   83 -106  196  -44 -184  168  170  137 -160  -16 -185   39   -6  142   60  -50  -69   77 -198  144   54   83   25  -59  -51   -9 -166  -37   64   25  102  -72  107  -12  -48   69  -21 -113  -10  -39  -47 -156  135  -38   -8  106   76  -88   38  -65 -193   19   32  -20   35]
[ -45  -48  102   80   34 -163   49  -28 -207  -70  199  -79  -20  108  -32 -112 -184   13   56  203  -22    8  -30  -74   71  -18  -89   68  -90 -202  -68  -38   86   -3   -3  -51   33   85  -65  112  -72  -11 -110  -61  -18  146   48   17  143  146  116   78  207   34 -170  -78   97 -160   18  133   59   31  -92  -90]
[ -76  105  -15   77 -108  101 -182 -218   75  135 -152  114 -115 -143  -26   20  168  181  166  100   17  108  -26    8 -105  142  120  -26   28   76  138  -25 -131  -23  -58  110 -144  -45  -16   -3  126 -100  -31   93 -114  -96   35  -18  -46   15  151   -7   84   33  -31  172 -175   37  -50 -165  -81  -79  230   77]
[  64  -17    6 -104 -189   41 -120   -7   52  -86  -38   73  -12  -74  133  207  -54   10  -64    4  -11   18   35   57  -52  -49 -151  -47  -96  166  106  -70 -145 -157   92  205  -92 -151   30  206  -18  -40   94   -7  -77  -75  -50   84   18  -28 -134  116 -198  167  157  -37  190   28  -56 -165 -155   -8  -17   90]
[   4    9  -73  -27  -90   14  -85  -72  139   61   -7  107   54   46  227  195  173   29   41  -84   41   -1  -75  173 -185 -156 -113  -15  100   71 -139   30  -60  -20  178 -165  -70    4 -130  134  -86 -110  -32  132   43 -132   51 -120   21   23  -34  109  -87   25  124    1 -105   97  -53 -221 -115   25   25   31]
[  -3 -109  -79   54  -66  -24  -55  -50  132  150  -61   72  -56  -52   16  185  185  -92   46   -2  176 -147  -14  167   -6  -72  -11  -95   92  136 -103  237  -67   24   41 -104 -142   21  -19   87  -83    7  118  -29  -15   34   85   89  -18   11 -158   66 -105  138    5   86 -151  128  146  -47 -150   22  -71  -60]
[  93  -41   81  -24  -81  141  -31  -80   47   47  -18   40  114 -183  -30  211  -56    7   72  -24   77  -32   47  118  -27  -96    3   66  -74  145  115   49   -6 -161   45  102 -125  -44  132   13  117   73   10   36 -221   13  -35  148   36   27 -184   -7  -26   20   37  -91   71  185   56   -3 -154   30  -96 -141]
[-158   90  114   78  -54  -20  120   17  -96  -73  -15  -49  100  183 -217  -57   37   97  114   92  -98  -38   51  -97   16   18 -128   13 -170 -231   68  -65  170  -26    2   68   87   10  104  -35   29  -87  -50 -165   48  116   95  -83  205  102  153  -80   76 -109 -131  141  134  -46  -37   66   19 -144    6  -74]
[  95   20  -68   34  202  -34  151   45    2  111   82 -115 -104  180   23 -125   27   13   75   51  -98   13 -129   80   20  133   51   87  -27   16 -165   44   87    5   53 -163  -44   75  -70 -168 -166 -150  -82 -157    4  -48   54   28  148  -59   22   16  229 -198  -64   43   11 -180  -34  134   78  -64  127   89]
[  73   82 -134   16   27  -78    8  216  -73  -75  156 -155  -61   75    0   26   59 -243 -131 -218 -222 -180  -72   17   50  -32  -92  -91 -137 -145 -166  108   38   84   82 -111  174  -39  101  -58   24   18  -50  -62   67   90 -148  116 -145  -53  -34  -24  137   20 -181 -135  120   -4    5   17  200  -10  -63    8]
[  63    4  113 -101 -126   42   15  159  -48  -86 -102  113   35 -167   -2   -2  131   -4   80    7   36  -77   62   -4  -39  -22   52  -14  134  183  148   27  -70 -178  -94    9 -118 -160  153  206  154  119 -145   -6  -50  -96   36  135    9   37  -79  229  -64  140   69 -131  192  126  127 -185 -175  116  -49  -80]
[ 111   92  144    0   37  231   18  160   74  127   84  143  183   14  225  245  133  141  142   80  128   99  215  165  140   80   53  106  157  190  177   76   18    3  153  206   79   13  197  231  177  206  106  168    4  121  183  213  101  143   18  233    4  205  215  118  201  204  165   48   75  229   61  106]
"""
from sage.all import *




def parse_B_str(s):
    rows = []
    for line in s.strip().split('\n'):
        line = line.replace('[', '').replace(']', '')
        if line.strip():
            rows.append([int(x) for x in line.split()])
    return Matrix(ZZ, rows)


B_mat = parse_B_str(B_str)


# 2. 检查函数 (优化：排除全 0 向量)
def check_valid(v, min_val=0, max_val=256):
    try:
        # 排除全 0 向量 (CTF 题目中 flag/明文通常不会整行都是0)
        if v.is_zero():
            return False
        return all(min_val <= x <= max_val for x in v)
    except TypeError:
        return False


# 3. 优化的求解函数
def solve_optimized(B_matrix, target_n=16):
    # --- 关键改进 1: 使用 LLL 规约基 ---
    # LLL 后的基向量更短，更容易通过简单的加减法遍历到目标向量
    print("[*] 正在计算 B 的 LLL 规约基...")
    LLL_B = B_matrix.LLL()

    # 我们的搜索“步长”集合包括：原始 B 的行 + LLL 后的 B 的行
    # 混合使用效果通常最好
    Ker = [row for row in B_matrix] + [row for row in LLL_B]

    # 种子向量: -B[-1]
    hint_row = B_matrix.row(B_matrix.nrows() - 1)
    seed_vector = hint_row

    print(f"[*] 种子向量前5位: {seed_vector[:5]}")

    found_vectors = []
    seen_hashes = set()

    # 将种子加入
    if check_valid(seed_vector):
        found_vectors.append(seed_vector)
        seen_hashes.add(tuple(seed_vector))

    queue = [seed_vector]

    # --- 关键改进 2: 放宽搜索停止条件 ---
    # 我们多找几个，防止漏掉，最后再取前 target_n 个或者人工筛选
    search_limit = target_n + 50

    print("[*] 开始 BFS 搜索...")

    while queue:
        # 只要找到足够数量，且队列不为空，继续找一会也没事
        if len(found_vectors) >= target_n:
            # 如果已经找够了，我们可以选择停止，或者继续为了确保覆盖
            pass

        # 防止无限循环，设置一个硬上限
        if len(found_vectors) > 30:
            break

        curr_v = queue.pop(0)

        for basis_vec in Ker:
            for sign in [1, -1]:
                next_v = curr_v + sign * basis_vec

                if check_valid(next_v):
                    h_v = tuple(next_v)
                    if h_v not in seen_hashes:
                        seen_hashes.add(h_v)
                        found_vectors.append(next_v)
                        queue.append(next_v)

                        print(f"[+] 找到新向量: {len(found_vectors)} (前5位: {next_v[:3]}...)")

        # 队列空了但没找齐？
        if not queue and len(found_vectors) < target_n:
            print("[-] 队列已空，未找齐所有向量。")
            break

    print(f"[*] 搜索结束，共找到 {len(found_vectors)} 个非零向量。")
    return Matrix(ZZ, found_vectors)


# 4. 执行
recovered_matrix = solve_optimized(B_mat, 16)

print("\n=== 恢复结果 (自动过滤了全0向量) ===")
# 打印所有找到的向量
for i, row in enumerate(recovered_matrix):
    # 这里只打印前 16 个，如果找到了更多
    if i < 16:
        print(row)

这个矩阵的每一行都在c矩阵里面，顺序就不用太管了，因为最后是求sum
现在式子变成

Ri=∑j=115ci,j∗QiR_i = \sum_{j=1}^{15}{c_{i,j}} *Q_i

求Q
直接求逆元发现不互素，我就直接丢给ai了
他直接取16*16的满秩矩阵，然后求出来了

from sage.all import *
from hashlib import md5
from Crypto.Cipher import AES
from Crypto.Util.Padding import unpad

# ================= 1. 题目参数 =================
p = 97583294997903710061682705938563475074806432220861017204432576442085954413293
a = 3636271379795948121887425406703083426662628216950067503303448932204441789640022265666101088777982159985498385878360417609284301832494786019126184078242847
b = 6077340442526640022665537465219787630537230277969120411064283843587089394490119534899442656903416344103640047309444477354914248313841074243127877657504600
N_order = 97583294997903710061682705938563475074682287001359757565551325259841439345853

# 完整的 R 数据 (64个点)
R_data_raw = [(7832000319321902840924190957670151715675571485860838902321372894997642643673661023957091223514051514913311703968283009805587763430593610229066189899894825, 444825685313585513545849208358663306086154920936288703312594242624507658663896758548493691017995002173226554523050517603110158795338022039757153079367934), (1231655299550013972827619528510625751791973825345338692532318514227001218674580903396417662634357527502279061801025418779677522866993955003760451526407390, 6427654245685315382112196783616297196361326346984196792323745620469216149119440844772524941115107662594603249248630403185036604982562824915358137771728748), (6432796327758238988804887340727451314389424208676705904965119372096555085131434376140753478770461384479389373076108324434861600441685595571757762730611122, 6851023037329568050428787347723369056876702529997328866976365333697487339111012266183981805061548792496406643243684164692130962896552019462568874989596591), (1423655977420968989359080839604162736280419479453252732176736234871386945340904613258160634420851093095580643493101239854137844119565023947993624183932308, 3519715376987604665520863406619131530683708263448866506209893539753021807546272062663152085866098122518099163370386328398460756863286068504631244745193843), (3545567878831312529438800764696484060762827181938251523405843195271139082170261260017415865123197142926595658853606965073041729406826433111377901250075809, 4591777476020597828787399836091706132305277414874856222262736625110518678388733643679959458346458910661041876088286739677718352541912487011818899505990325), (6276204541129895851206450822549898715658329698082026705733412784889040724438918713683672001765004004752945163817976721284136739758261664917864935238406999, 6005207694743735643767250249409069442588553188771823311968286162838623317987732812440912626321576265720391104724406960972827128419871301361662530998872892), (2273007899002357403077961797154434495142823881986690506205507944914174143056031326574716229761811577727445876292621444752202677443796845929957587304731851, 4155406765597365122076234309755319872523369088397649457433596396273342795151749494277776704000691261632231447064828998952641771683102076388723639603857187), (2808632261843274867774419683814321192075649718938830400112890578541740593002748461073456085244994822100146968065569983549789440168698204742120370405166941, 4595317630617247634040884107868557273411400040202055649058077367822220736155036935085235722637599980830836640897705084567949810549146771116728711807226491), (1704707996480073168206824776502609928360395055955675306865337662812231958553679221382587128474490302218474684542255444313201675701465545633860690734055286, 7550557589656611170938151992223019283170907459108799892245479143568742947930574349702012070084201490770536424241437809167257561840062861309817666441045787), (4417418165917724086691239446678868059518140558562900635399653751356621132482607226355585787213048342781621713244546587726714733969955769543936801031481262, 5938208435317039272029132843828198709554193305867447671995280375382696321339237781057614673807314595498492506620269991825036039784092556326080133756775159), (1084783665076903219376349107806920891639407227400399164005136555631438572407050830009689931142415168928432186091795762724224453617253861442568638849785613, 7644535633994316708617341511731555258607873885153584946642223463791954300660648815682428666018873773756213617331411206655414676267807683277089977914889822), (1978534532159494454388773159140061665682403169418807583247868431398808072245650632453615937388729351101618268467935472361774934881373465253893308971802696, 7081198628956149590246701693204043667465322996896685482353043899845910470727644338885714592395030474546156892252366355868360376603677417460156020245411734), (4649017188029587984875725044412568813269908037543145125024966102796173492263236493089716242018069471604242146339536894632784566053275035262483695569742454, 1955545184603289064545842165005948842016338342818296013711137170952926118528872411221325984936883428971755049271650631670790004518752304007941656600280068), (2304848916919727914632838416427751837205398284908239403805457133686041880640444151758046263315840816296184641775933356458396068313532079522545717895821800, 705247675227721441406918331531982193305043625439178922288687556646871104035225926519140339786356519698715972574841902251959529839691924397993926086750302), (9053912322397724083712281419186382951981373834826228146503314111229075776227634088085713647384152306075851602865387592176538167199351210022149824766133891, 6171639950034752564460853528531985550509197096556769691726391464654037395084913224108625927679420491523104270954669880958014138089393895498990698373779816), (4986723676063871003462083814219964442556611821661800751909133061872722266192211789394554129427843147605486281339830592982486798007414898811390215831499951, 8771004514858913141693643749086782820480119930130006977804333125971027943109148602418648175993962419052424218461760972124683804111184174390706944594784991), (7795200089286277798687290059901676152900867961291294736353907787487318226216030930451990278979983541102219855694470637221058541485815816398578882646743483, 7852212908361523696352774616738903741590637324807833955932788461941938159180971794756322703606816656657787839925299005885074701494919357667997835640703263), (3422934079656178873748022756307377952595161025165070764455518119613595330873106558836095266546048795425822410601403426887761752284276680742526024044466883, 6882568660638586919915745277407247580517812793797006545521481538990072012386441672580088347744840968557478673995032158097402548556902990494648347760856685), (1901798007219923877282588227635062081194842040899409682256292058727602804678781572051417502377435717032608451312750976116954909736884579452136297873841605, 4455227945171084137537280107728697521688494855846643943972685068423484137285888614787120646741204979457386389172090606790747476416166314584825918654743961), (835005647255660272215068277664278004628661040046786684336690903708965830739120305779944832601730161127037656328971356411813278929635833204823107970237822, 7670725274522156690491260284641913261514514347955929860572920484471333992231500498914951155416802849454863525804434766489067139904946875141278267467331833), (8951897053859272772356483023534624396409991422111258651103371677871068049109076244034414586932663971700270731365181698932561132351895074764365568654084605, 5027640803201192080369736231259476181493804377784996526797429545343982874129018435177171310695598096473907988115287355961156047667064841468246430890406807), (2105658808019287179792558039106236020623025727454418260107540594821916314691221499331590823306909636125201941069517117309883714365916211540000798271153073, 147800561436770405610963595267328616609477403898949831570906870734146379964976484053025724587470581833823089285450666857063476565702290145998603139924318), (7130194681977755451746180366016252811833900699433598677336347694801056507268628055288415444364900010342161075360729117608371705681470452030364463903477343, 7680079287366207936361626980563511923438130327089825711055834711806674517696005810707019857030734639845710461912829697064444153009781244835744965520353368), (788401349728479676328885016552051915214942452004487693830557213302649998554219518367960645884249653946109245961887664298867981688685278721874085197509079, 3563030654514063294693113672680338345709220804273500078757474796445396659327017240635976265875291158868385945968929551720646063708535671342630747979857417), (1602018545534939236708203564880725692965240041980516990195818727854217241193805878091020469107548363424567526350328553959300778247750776511349402213890227, 7596040946269022006261242439473796678387111060645472879547102196445732979764689664038518792619454411985820177381236948242125873020785557371886917439778925), (5752199097038672946919478957001487477260855595447895783647257692284097657690004559804228009016380270398091504323682520666002224185159849197496329352696919, 4574336977529375895792915715970229385072933758481198462178259357695743283058235353526602836693268529413990048907013091734877159816551744710302253554200470), (183067538240491667039697419224090279275178789543126460963070276905707991706553554874361948757165573309471296369908815793091087150482243978379990943397752, 4024092656102821675961772860851209856658253675866315956759418085602713161632511264378667287017802907284920566465507510960220872591031722173347881131954057), (5966193634361020371843356783211110192595361825336139448193945411031621191450948452366710802622168415374180883664895067701132832546423002367462681264481547, 6018063181438437735974835401702055491857648527032844441457973483089618666103771460182039079932355797786797736284338660921369315921823800016477333034280776), (3795102657173611758316323707705811934626765033865924382115534571748194877297358987445514104787361425605239504683094065006249660767641361534447971529535921, 9427698068836711549582685797691902472811394668483832470094490985752979955481713349589666666245204253415296899163352086951563257305167072268697817895865451), (2577904878613675429117329395638402370742484848591312292153540139449726836524856686759048046407275830310306328149512320003319254867025111480246314986249683, 7348986112942761506352184060501760264882467276364503106019915146432327580601511926170570193062439277615648056837288732706135591229817375213072784738908164), (19381705269582952479629805875471923177386918603193769763010119806110285629356731134568372429161537759723007442943452636791065300701590030688949799211447, 6286040652106586318278156590818304228413480331719424331886505625464892115028397711614801040033961066006715282544903788991558705372998286070143934709297893), (2767195907361083611806485992890207244289959855817142265541207761166700791008745494639955618209309526575718124210542182432082204731471029975075106514222259, 755995866208117484194013889089923683381214534096342270244045203010950776540734858339397776270899914942735639588822825952892502376795453884163864047176244), (1048793186341836445418349698704806663912369845180154831278792041723707892807031074982355282018564533792427783711853361144335519029810172676106183939791528, 3730289845455024052764592780626057501964728482418850830979805065178758188091292913041240915002405956040690496963271359760774894296779522362897738111983414), (850767203815301303900801002227053632826523051336263746441863922486748540572914462938390139918412698710588790437503769510400335320422286377530823888816218, 8060017122111927430499546360306971298443954937160955398609903950537212011337858113666938313070159246747490679743100622200422953285912137690837994319947839), (5930068598450223765586653254624530491158827983167130784772940939001454442182137439976159810474766868089978025605065566074109563938784701442172322916924653, 3622002769197497718238515954189612662859918196882108968645897167269112014384146153726547408919049311678288199584324091176588608842776413365728052414155218), (2146535786146639962940315341429838823736962639638404187021207826168809861354800376714829843953740415909810186889446567066963197881380179231836327793016771, 403533625908769829857240236309234068443255415605535850649511080244940934413992990898576485780943699542596028798716428488758044720046250868019237989737539), (7294953674466136477949453438783785863341106745989225973691001985200150547575332027274655921911078307752657674441790020513621286055145495785656690324365708, 2782831054402374209178003248306005838226688805924359672677380933119852751829805558645635819415324972706712212323312315412488463941460455776447220947188463), (5414020108457834231068677828987022622548695084833508603182621260222381842929122671929789174075542263423152954246220452061945927853168410629487414785600736, 7740628036463490171863448459979829034847125587800340102607944135317230237034829888239477901750424087041441871737923902153900287121234875628772657078729467), (3884650767696067233469532311046758499214077112703345642615260271884577536500014610569881103633940319098857787936823943706826700761864286015162782770092558, 8401201031381614943949900578257973429011967090200091035251243583605918012580283015520360851652552406904385287182655878779470697496731867875511564206701139), (3623245329331100080037200881874588299061220559230260015075645280839422860369257215318116458114851997390743828072709131827358872371935937409888071505315775, 885322482804629291221264334866502603621116229338643457558780696339240287008449043282876488088175277175885324269852600643991855638359630627837343557586216), (4376605911470497017393453219809726034452117435111928492509316251024410563649639563908311035673737946545168394053038370358380613164449366584808548047190994, 6260668829645793014449260502703449862083682781547147252366933997104455667445263508169391243944519670832300729944728521521337424587319681060212995152394473), (7479395642331251546639099189639122109778760270531880920938162220358667635823684203092053304493800520812974433907538383521812437996907394461865205535232236, 1052737876879106907739471788645695257532250293104727777672133812026985875018262039087346339352807560841557795422996064808092025483613769376254667344117510), (554623736483147680587469009026007699467440211456202915596779947090139504889781972625637208968084254530185205089420431378158132623544489597702721695684558, 5042814662720426792147808061914148439375212208463290274194971642709138342010829546377091237931318036476949004071384977336529939976529038932688530344007465), (8093965947299080546275107266862701744860186148076170609341594810120013217916095884058983906675296868483516898112018864952125752150459683590983816139478384, 4852519808225456660668994434422808847964611977050177575356538012027874032915274386644880618362588003585156944922701168011682757106084596809653295846270145), (4606234802851368480307574799176995460965009530629625509272155685933611861369592121519121869121240562637010313033429844415880506456677935721489590167600825, 7393509629154311219948069891588092970132331860213899679880848191958509607265913579506483223721299173873979897858284040035880312446337299862907950371395938), (1776773971563949454218459273710620647185556220867016809412703114252574227538086236047392928876409977248861863943946680993569584737877643682182878649890818, 6691264349228380825302035210418452806460002391937613367434236336363366100139980530323498971834739437365922760864077113483325693588029575376606035368496537), (2476183393535617507137330749042570193023665729355636803582748764264711270766407892458490886915236188782759392065140921686993455430174280287861437740379414, 3836340244029771200303683042880877381400788344400297136279923859296609000572983851990729227823222199341277553022420774881707791605976654606798958083022311), (2281710978855715968012286203113486289556408337054467036099687981078817844818513726614865605090834290726734803875382857926286201708856659912605790641338207, 5949445246107981375644033915397361345332663715572921180218564516295194632494649612595261312147007510550693872096137896128286164349794634475291972628131303), (4216941899836036523495953356453184530117278257669709149458673789440132489256147703283801419119173903888241905231763348960841340660234955184812604367194675, 9398784135953445732545861817441607958218718389674509000115224279606723565309339841443277387919787182925479084298993595536634875069686089122032685652951314), (1062605311375975400777538566901017687008369235899451250515495128358050995996559449710549803879809542709549827975784258548068080019400894301091393032002785, 7833017076679674393389641140938266862121296936528427579738006490822149213872280962432479419485243983947214022923050478943549280528717690195796122824378939), (2439384968905095025144950573845634703550486169099235374247518310002566134346364165557580282956736775168095860987590010171680545254593095116426377057166558, 633268368757363401531122573824014297353073588102647566410491130412178842159946902607936665160713540696281573267047808062361396387035353032130730903964038), (8983023132575618234528631552838576441534442735962242022028236231540997202441492038046573346115315749029576306237043641180405677974842976854774805480900947, 7964577584823326955704549975733437644324419884284382447172761201112292946857104453343309883437433224468495844242723025824875072606796492751082509139246356), (9202163774339702930052477539188219538568835701364725048748173659586429602183390279759450423037898033187480613185904056196043855910252846356428503524584802, 2191005014793929046555023908302442932147079057656038866887280336761305479192075151600123882801745635701139973179068266833438328996542104380297388671290790), (2171878153727980938202126119564637508725080744272715396530846127796959439064029498979938520450347628674447433424347884462320843764759585830653439361096659, 7490921142616162960776726949369862846765201209559215116988148994084528888102661487203967009457885730060519043703520087419555866178701128086672560989716294), (2833536380370293268482593560347669379183887138311227313517785007087192956898724643334211191815163277935130742371505967496708491857730128024026861030082368, 1174217771831591995160556970256846800058555470148501610890919848794238843299807777085203674411465216634476259744068196514904809983181222298156266964990896), (665911421902955568512851595493466718450463371722278894716999178795187571116826652011827522976988440963506368402759535643527628542568885097509598385503082, 1689005586079471999331989840660126259739501794636773142596100869193649828285613407629123914204096257660313788885046526083780622247811838571584188231337631), (2128749083496476521148208711905247419847533164088849807712301815442528103035223188834521253074105438898822698608726190447089965919964676824146425062042340, 8576591182535963673844032617503583488584162594191961843840492516618499034407013314045503497877446690838191968590405984837170404374671115700964442002666668), (3650984148569047306135647180839592436162637123998221991226165509663927341328605067988772694449321362998506685795183453832499099143770256734792818246552123, 4499295145892557745736396430335127900918742953663087260185211138514764162487193655166024054451880406886509589422136540319859382544443721609822107266131999), (4063139595111664223873081309036546070009171358557536775576800037121272282520039934008730646373010066307192128900499981854703133200615107930858845279360264, 9020930347045521774460282072824820683797679002191412407787305388144022464605972480813354633389736180876546775520608025134965742192578319052038561740925801), (751498501435849924160728341592136617274223769162787790087765654229295984653259878156149347541500032213451846843921037653313515334544094162704934460249988, 4932671623121299750128264473311826975086534781678478940866497206417159826413190090174218596620943170167455276059457984074706356513532079547744604393781541), (6926146779455615877715002813301024550808148104608793486446924578849603190274539441737472351880807565944114213683280760046866855045054449896669890021084485, 1308053561392491263959142286245309091146945197055847377855235218815195257744567800813756790056903079336039078999002005136270979219301050583712675714393067), (1600072776861439435527709065723594484599300839305081197118383180839466714290470860971256618590838102578047180631581640180692093479792915101915267527617129, 8102890361311731420232087922093380243170147592566562917888978380243933782231008497775444563436144428591977790410582714386873731087447899730178559694599000), (6467379408268170202516821998742543057974225346588426301006543372458495000714411569223915391327698197143474286461583399922634639154801739000306720776006136, 9234771131215449554785556050394895294768316271607553574884508113524958372365904526439812958214798228881012535849512255030156232041932310347502344888755841), (9410452032352799818953466738470460276199795118264415368770935691754492285371361446792144335811543237354291149324285174344005154056518449182625770980630650, 2346269269700581641202731236246492250613329199001411698278358311547917360851186769019234870838138467111555414672672891372132294240887607029491280842022667)]

# c 矩阵的完整数据 (从你之前的消息中恢复)
full_c_str = """
[111 251   7  47  18 206  48 162 255 206 247 254  93  78 238 235]
[ 92 117 172 109 133 112  88 147 219  69 108 226 207 124  42 229]
[144  97 225 138  63  76  31 141  51 199 170 176 211 124 156   7]
[  0 128 122 104  24  34 101 187 155 208 155  74 206 137 110 203]
[ 37  69 178 226 118 239 163 107 145 103 159 135  15 175 215 134]
[231 227  92 190  90 197 189 167 120  64 213 251 207  53  66  89]
[ 18  58 208 138  49 169   3  68 159 107 143 113 178 210 250  76]
[160 143  71 167 240 205   1  17 250 115 215 193 160  59 235 233]
[ 74 246 246  22  27  76 122 245 198  39 107 114 150 251 170 172]
[127 176  99 213  80 238 213 213  93 106 115  26 103 130  78 138]
[ 84  52  89 122 102 166 186   3 158 251  59 113  37  52 155 159]
[143 226 112  70 103  28  30 211  30 147 119 154 177 231  97  56]
[183 104 125 195  69  79 148 131 148  84  50 160 204 185 246  70]
[ 14  62 234  88 197 194 181  62 246 170  16 114 245 163 205 137]
[225 237 192  92 255 248 227 118  69 205  10 221  20 204 144 118]
[245 220 166  38  34 120 247  43  50 108  25  35 163 168  23  69]
[133 208 116 187 189 160   2 188  71  24  35  23 245 207  20 247]
[141  74 198 131 134 154 145 243 234  87  45 166 171   6  62   0]
[142  80 165 206  70 217  62 172  96 136  39  34 194 251   6  41]
[ 80  50 223  76 104 131  73 221 235 253 134  52 142 119 121   3]
[128 239  33 139  51  30  92 238 200 217 198  63 141  14 221  16]
[ 99  96 203  81 131 112 176 201 102 104  97 243  58 250  93  21]
[215 168 109 180 168  86 153 105  26 138 243 182 219  69 131  33]
[165 197 225 108  47 245 169 109 137 123  24  30 100  44 101 126]
[140   7 117 192 167 160 179 143  57  78 192  13  23  84 248 193]
[ 80  27 104 129 176 213 102 142  96   9 183  99  45  26   0 110]
[ 53 142  53 204  50 104   1 251  65  53 255 153  14 251 131 159]
[106  38 177 153  40 193 120 179 236 106  53 133  51 201 205  88]
[157 250  34 253 231 130  23 155 106 160 150 158  80  24 127  18]
[190 249 189  24  45 206   7 206 195  47 178 113  18 150 130  61]
[177 107 232  71  62  12  29 225  24  39 246 210 175  11  87  59]
[ 76 254 119 146  27 120  49  78 229 216 224  17 189 226 103 186]
[ 18  59 240 163  24 105  88  25 118 145 119 126 229 156 156  63]
[  3 136 118 160 164   8 181 163 187 133 156 112 110  75 186 247]
[153 192 237  61 108 206 247 136 201 189  14 151 194  80 194 218]
[206  87 222   1 104  43 197 125 253  36 252 191 155 214  15  14]
[ 79  21   7 171 204  35 197  40  58  54  91 163 108  52 184 214]
[ 13 161 198 164  57  88 173 133  97 246 157 140 171 220 178  94]
[197 121 158 167  65 127  44 115  96  56 251 140 225 151 131 216]
[231 137 192  25 218  63  25 249  35 249   3  50 102 172 252 191]
[177  91 216 195  60  11  23 167 163  19 177 174 120 251  41 191]
[206 115 104 246 133  56  87  98   8 104 225 108  28  49 198 116]
[106 207  76  12  96  24 251 211 219  97 239  89 157 193 242 161]
[168 195  39 175 132  11 174 100 243 134  63 224  30 158   7  38]
[  4 182 114  81 225   8  54  40 113 164 139 197 230 231 154 107]
[121  66 196 196 108  73 217  83  87 212 198  32 182  75 179 173]
[183 126  35 233 218 237 147 212 239 174  75  41 221  67 177  64]
[213 111 150 129  65 241  78  81 121 128 231  22  28 159  99 197]
[101  49   6  83  65 249  92 152  88 192  28  67 254  23 198   7]
[143  25 109 171 116  84 106 236  72 171   2  14 127  71 221 183]
[ 18  92  70 152 202  40  97 187 248 208 126 250 245 184  36 153]
[233 173 238 117 240 249   4  45  38 251  64 107  93 143  52  21]
[  4  22 125 202  30 233  68 104  60 229 109 127  98  79  20 241]
[205 198  75  38 185   7  65  72 206 232 173  60  89 248  39  92]
[215 203 214  58 178 151 146 182  97  33  79 198  72  68 213   1]
[118 111 142 155 209 161 249 207  35  33 110  25 252  57  35  72]
[201  62  70  11 130 212   9  24 150 159 167 213 196 197 199 144]
[204 253 101 176  19  24  78  39 215  93 156 125 207  11   2  35]
[165 175  65 221 109 131  38  34 240 193 228  29 138 204  84  39]
[ 48  32 109 213  51 182 233  82 225 165 253  79  98 143 247  99]
[ 75  57 134 230 229 153 250  54  38 116 172 207  76 136 135 254]
[229 215 216 237 199 165 113  42 183 246 190 193  71  76 121  32]
[ 61 162  49  78 157 188 110 253 182  70 137 233 168 170  23 190]
[106 112  81  16 247 195 186 112  77  22  81 172  38  29  35 120]


"""

# ================= 2. 初始化环境 =================
curve_order = p * N_order
E = EllipticCurve(Zmod(p ** 2), [a, b])
print(f"[*] Curve initialized over Zmod(p^2).")

# 解析 R
R_points = []
for coords in R_data_raw:
    pt = E(coords[0], coords[1])
    R_points.append(pt)

# 解析 C
full_c_matrix = []
for line in full_c_str.strip().split('\n'):
    if not line.strip(): continue
    row = [int(x) for x in line.replace('[', '').replace(']', '').split()]
    full_c_matrix.append(row)

# ================= 3. 寻找可逆矩阵 =================
m = 16
M_ring = Zmod(curve_order)
final_indices = []
M_final = None
M_inv = None

# 自动选行算法：遍历64行，寻找能构成秩为16的组合
# 或者简单点：我们尝试找到一个行列式与 order 互质的子矩阵
print("[*] Searching for an invertible sub-matrix...")

# 这里我们直接使用 Sage 的 solve_right，它会自动处理超定方程组
# 如果解存在，它会直接给出
try:
    # 构造完整的大矩阵 (64 x 16)
    Full_M = matrix(M_ring, full_c_matrix)

    # 构造结果向量，注意向量元素是椭圆曲线点，这比较特殊
    # 传统的 matrix * vector = vector 在 Sage 中如果元素是自定义对象(Point)可能报错
    # 所以我们还是得回退到寻找可逆子矩阵的方法
    pass
except:
    pass

# 手动寻找 16 个线性无关的行
import random

found = False

# 尝试按顺序添加行，检查行列式
# 由于计算大数行列式比较慢，这里使用一种启发式方法：
# 随机打乱行号，取前16个，看是否可逆，多试几次
row_indices = list(range(64))

for attempt in range(100):
    random.shuffle(row_indices)
    subset_indices = row_indices[:16]

    sub_matrix_data = [full_c_matrix[i] for i in subset_indices]
    M_try = matrix(M_ring, sub_matrix_data)

    try:
        M_inv = M_try.inverse()
        print(f"[*] Found invertible matrix at attempt {attempt + 1}!")
        final_indices = subset_indices
        found = True
        break
    except ZeroDivisionError:
        continue

if not found:
    print("[!] Could not find invertible matrix after 100 attempts.")
    exit()

# ================= 4. 恢复 Q =================
print("[*] Recovering Q...")
Q_recovered = []
subset_R = [R_points[i] for i in final_indices]

for i in range(m):
    Qi = E(0)
    for j in range(m):
        scalar = int(M_inv[i][j])
        Qi += scalar * subset_R[j]
    Q_recovered.append(Qi)
print(Q_recovered)
# ================= 5. 解密 Flag =================
sum_Q = sum(Q_recovered)
print(f"Sum of Q: {sum_Q}")

key = md5(str(sum_Q).encode()).digest()

print(key)
print(f"Key: {key.hex()}")

# 注意：这里应该是 decrypt 而不是 encrypt，因为你提供的是密文
# 密文: b'\x18\xf6Q;\xfaI<\x04)\x91HR]\xe1\xcaZ'
ciphertext = b'\x11\xbc~\xd9{\xbex\xd2\x0bG\xbeX{\\\xf5\xfe?y\xc4\x82=\x8fV\xc3\x05\x7f\xb0\xa3\xb5w8\xbb\xd2\x94\x06\x00\xbf% \xe0\xfc\xd7\xb8\xd6\xbeZ\xbe\x98'

aes = AES.new(key=key, mode=AES.MODE_ECB)
try:
    pt = aes.decrypt(ciphertext)
    # 尝试去填充，如果去填充成功，说明解密成功
    flag = pt
    print(f"\n[+] FLAG: {flag.decode()}")
except Exception as e:
    print(f"\n[-] Decryption failed or padding error: {e}")
    print(f"[-] Raw decrypted: {pt}")
2025-RCTF-crypto 下一篇
已运行:
浏览数: 次 | 访客数: 人
Powered by Gridea
0%