2023巅峰极客 Crypto Rosita

标签：Qp Rosita 极客 Crypto xy pmatrix x1 dec vdots

解题思路

根据以上方法求出模数p

def find_gcd(numbers):   #求c中各元素的最大公约数
    result = numbers[0]
    for num in numbers[1:]:
        result = gcd(result, num)
    return result
x=[(4713513545399586887294281187501009141689080934674926984853052046637141607331993392136186920709675152470824454822335527736604585312216293390500894812356575, 10152198551269550712132843544953877513974069303791371586626547671550636936369607844350995807520993189830394615282586805640124173078292476320861958178531199), (8497709856659541496506566158438727086633064779296427286612559352247045304592577869075723270252557382159636274220949698085489427175611575498725494187042219, 9116811362014883884879981282521462123463402369273722016008105935084826801111377968641225157887930975588405833350168170885178864192235006321249285744756607), (9370988588550376568847533229569651406006327680521920971380933472551236466257993862023372207379492794618019196741718902793769742423589142369766582541381456, 2964764716081715738931864218952095017577031943078710662273038672326443429898927649838098895380036049701254956968440876093577389832396678079667784517400438), (9780561431490704165761200835168742342147019392307027843608906950941244751705916411353543429159840043103272583252784603317509552870673884311510395715589823, 4512360262119206250842086638048812502384840258083296584133384225879227543325169341795597008831855800692604773248185325609068166181249185285419214480894245), (9753892250466466740522543908112180868496775086018060713800521963469049945379911034546236677650557303039887137123496849920375395729255201971208204340312401, 1938991444752122074176200366358680893894177968559383024484416921026824613924903539687055302548680671218740698360348493115771464268448199996301653785482255), (3956377375220167264841327493686873211450973487259797861617968170206067349893946190638797758839551762336875162001035221844923167039774464458844780587411290, 2811884831397970155720238376608187196147035379379721383527942003189302602153280352219864817477497801745704924766135613808068056390979231466645561668031024), (9666287196438318899841485440079998120284795375413795856320443556455924086216013060731258663630259450515687636598820588811051314151419247760340027636254010, 6242436280614711684558785155511593403934172620329392146413928090178040475814185607897887229598797388837994931615621147403337923088271068952762638016855590), (6410558156839007797687898586831013305762106341458065938664504823229266562576428647033727809573119925974366171334827235046449418027002452010139094706683524, 166040140975198871456147224171862912756049890094169801765109995587970035602951233459371050668124316347586947163116257377961189202602060040019748070219990), (7487523686996071358586432253848922887425506981897556365676381361674713123268395354139090901692108603574450937831189242041732109717228219023361891682059858, 3833064097409451074126677286511876656776323298352406335396385518824369065179582162537034691375770260284647652021989411071188459726289169799948499527352978), (4729078931071331163964102690008525906997212672160480378168436234117369684502122703336874338708993594555380660201608846607091713539215909055852251780666200, 9671005639423355090071773219691535311565452170612214746096012853592987212889402308479743500146866239496815147634771960998944036591154433878637345854681580), (6821686173012785249374727322813382690658902308759017953636851870535291459139748120517278436478763860649866374062463951709695342159037267531366354633119425, 454109349563783364627292840194986877835558881374972642229389545049685682117058018008055923374865359150490448558569535600064463313774005486853335528084868), (8097352798426399714734815712595721555460575301502694560292887744521254417566780198441732519052015108845518267351690594699620710114415927821492280557184961, 3143117134725172187551030220914090560736539268901574157885702648644662853782339667244393783677404575650558122950108703297687085677618671682413400999092492), (6513183126611071344734801408546155978497170719570544711452832905026449120538993019567678246149684116904668717489068578437282308835637038352023972256007784, 8595256417577044566295431272464816721415384447710220168112404314046298881021487795315799293386989967911497645651199195527326646204582743481992783130665695), (2076200911997145561230367295021401989448362508676000676577311337299144867938580996744776932574458926497687916072562094577782433445706636680764023115075901, 4185181876972327147075282615187299338935965887368883151241490415013808432719173146515945602139988343152455030760117095904414901357566253216420331574702142), (8381148261138239703852416544878169891675330535019140791244013907671539392169214622437710482164782450053349339730858222886346055951588212694455090992026758, 10163796644510826165062555164776253676683391937554299535024512638738572461507137822548694428887856947619206289961946341513952367341327961199388454010911345), (7082052828661106343309085153914890287304976485666067977869367415115311594266326288964638667384892162749794084356403456012624482827804555380041185165461610, 10970779558480467455850489414892463070247230105462800369438019696961142385993997445973377590939104585064920741469159965752608152462788217994666526971187676), (10925547866913717228347553467715877154535344097358915967045800604047245512707552888643862816712660316383731871281241836192113460647119393339781321061847546, 6055866638544128750097137956427321128332370171075374382430335937167361572997526522356283730243910934362510966098560693257514648296238021784063773472282317), (6785790260925369751944279679131967774385917676053671994816660134554688581275392628347250117223466845286763120154394370759728270091856895114610818897127496, 6944819097069963408944767211243358274272483862643515403213512319523594830818990162549356650095103065424909926139792747369879142585803045804022938030858720), (10150680299085473411999071651257510437835183830128617479150385170276511661416391671621212657988922640891651500543376218492424168354335425534467598112916367, 6888072072792068816925242651491095512907051998862014192078971292171690924351979706726926617264447271133901394941261441480528738783229729193335653038691067), (6144733739837148454772329326705634341817968434802231929905485148699984301367998724275922187148848520362233957437728130259536441574897386258118529064688341, 6922401772481881149066720640583520627817261494001167856510602081133635708642763148740953963043376201851410699406141136890064725776678780016786484847583214), (7183537698681045949875783519960782529707812105971837366532045033353552615284313247237848218535204838266158925723440665819577893781022458960790760810597397, 972458879736849097211443260725151606545512204610922585342131271017385141140207247723299888723549405720647865837813721206081762170996939779151465778359883), (1703616895475378292849103149650192818023569782199400711730101432265869461747826906638002389489855890866591624514624290243581490849013123852690673668158707, 3965658649904842831282861075974019284939181243027712551012404295076584641786237749626883865637323655400727181532596793962284990080186320814580576232764219), (8963495302555958703784098831852945750716266028695276241049279835560446187278067379699423883547371501029976357779282379030218705676796414104820180108129131, 9560675517442950285567098226729931887208424165598207710747610570352243682357219160075511868468892440533601005756017577676212645247627512657664612197886753), (5895842943761546170585247530130278876214835406657491371251930010354754539149126507657276091840277248547506799183780141446090851820226059572960774100958968, 7502656301329564949518360786200839569606634784837274630989884217434653385706698020742131117367834019542645778778345958194210006811683442080243977814147856), (8640100751937124680820611508642732502895060458726683545757217842488862932846036386984435316630861618902973439137510767460729980613091227298179451141360505, 8882095605573426533581887021721414251562279415082941499209814199741153497994653123467952083382221269756103559259084746736753166028905023164640314021714001), (8388247659079623573428713053298218758880959226750090682709831798344118488654853756660826146966546928039026596856245651901691263742527856567914497516291114, 2554686546158926080572492543354230379583890635573966376628896520173183537504248326545786454456701917490537148658673048732906884172862899535090764870061838), (3522972508923517458292353763302819930303577548750539717212833970429996939300225630636854038507526101228562069393852224597963907070523982294660351842280633, 2722886940087289673479756522605024512774339223436171406753474672760772800787941732367711740776438505211011207232095730057266822772428493683405241349648820), (5747287482977987126791251898912454610276486805219445014219573080628876839977604195669030439484891046209507206924952426057204453046696371912908633064230479, 6888743201368571672232377272185024669203662616683269994478128192921909999937032609025815813649655882205087573705374103086536384400013495005395551198713651), (5395805452593588173733709867409415556635519685320679663417386653285203287195773348337753725970479425032796150389196920192180585906474753231777661079289437, 2049198785703634792274246696306539108405783634680414306952855128318576045437021450775416575637372374508674635396511497565807111357058258974223438148878139), (1106569381500878776327074503776544923606655454675632799210090625837364461937678338160512692988670222225824403087574662143185601960224018905113923782270539, 7807167264259112235256140538958359886355420172448675887504580682313196334695678083464576229080110711789720570909552233828459789174622915149390826529983979), (774420854887127501308191286785213114311123916232266805877360705182482499403790079656851056723325281443761295724878231930299234031094963169518924985204326, 1823239988080736026294280175757387698370391442147440999541017982717190148487204580007594680643967202283878443924878273089191744975594960310070541049913208), (10390768586716868216274885948565940967753406041172076158220674075063692958975829973565237035576416388533593319064806625802185370125475892280705287378008167, 7936898961487579224597034819214266150399838606754275451599382249114378117387985558608837253849686999975720266799298482522115282514491361371396094456368516), (6559061475296632413236056122203276549479841984223974661947570674250692681575131892757949944065429272895838779365614183240180694750678008976228961748322336, 473245583943987902110281484140499960244770537636405429845479764689369773269971976056888748769095922326063256384576160463655904425218553458364943959899086), (6990897946181173410381225887279699398546212633701662109218390739579375069633389645336979977106684274400300780444554545122065074307060125703820181316384214, 7819208183328181779638777784468566190149101582692741398921460936301776675490965897874825617770665564614702759841245059168666900633861059762858637125280948), (7747435518316782982483754090978229664138034777481959364950240813857697188791265248527812695232235005608599944025036371707403013790647331893879773212237043, 3159418369091201654146413539772282132593105789449657281371263577186276285132860600728403344673301949317743362672738811296195856181843548485016286031920833), (3369791038393301556741708575440525525282467890252654592506744643498949048083071439806419974633826916428682344210022547978555038915574927383371276122836437, 1254207105162683404624839305815976360434593439971534044690683811862373371974690050945107547088863949294187872065584471393112103746592673505295745839104903), (12559802051565696220908490791176980888215159475214543819591025553038397887258210157937107348856671923347442195747214530113819589139784491311068764022315, 92137825928577563592704152890340316446433940657283569689729668523058912940157586067464548561955548003087234875918821018302106943344124622115389236652708), (5530860676475771990691794230197843848995136632588902707671870008682291466072853151674692329856555254129777934598717106397379676504637402898491515647019614, 7607657346401777274388222553201723127198119754377956597528780653945092019992176978208398510287887955973308860512490030992878891943040624792754656069217442), (8656514966764534509634687395591541433018230421930114964742418579055006526313285528361583224660642964199912067740313821869193158938537412710631568658169841, 4116821657037353549042717433725360946713128495027684788081224012710596099770343092504822988643111922114078504358308321081016458737603136815718086377286312), (8100831214626791708799713927585164778396993990058862482613985356488740056554280863238290359683223040430278300948843843441559818431263141038149252959678174, 7157146800294342965648679696235976006969454630987554609240655182227200766624871072125866911886299487131892259075918834107331341357650921521849485533872689), (10890755415745834079684707961450267393014312434887212673127786238658853553163490057950949556382435981261018626537652744836077613969932720662450748419434520, 5279648749877701240684141308917960279039127385754415377927568487239966645994472078390526598966778096179381589406514532819180811465019758802791435100869881), (9060075587488082866770299601000001129096055062459420816879850056758836467625363905808761432389493095202971219869587736150065097181836148704494938392336936, 3043213364684213962601012696251843801198320049133534260158876000568009047174757647991108751400672840493299153730363664649892567435814928501814954691990523), (3900860495400935419474632339214283753209440821844587105288679983316600743413043557244051819610723553012673147837484933074775700024738029322306219374175466, 8776159342624965969607240788610667981250366112487928135123108438906795434150675020540621553123713010466600434042759568095802865668466320036637390801734330), (8892508982428674296232570395108858435301220674549059757865650461633339757693888275460458282826216723318314278599996754746396225250466370460643994463970197, 9849460100328796212561749973397004158854148228901082087955317687788087821727683490635917903048647923933946683751563384919385239051043522197194110574632931), (10923358262051920487577188144536432256688530690409723011811352726717234614031126144612568470205593144080520262586830305738866710154785063559118988651582041, 4278762242548247544689233335926765616778120425273995711653646115727314071200548262199619769930492354067641770131381420729138534905254921562061287863678579), (8521580982419336726352152980518468054450102755517772937105339841639190905405892229656525386511809992487375982957938116145220023166622765996136275506785708, 10265827555400740987534703970942130173226636930554901199221250047258482081430913795266364437774976529788958093275042612558863535039271906282995137107627584), (2430642973360021054121784023477961807614448837359566950318322641585771572293505818234749487480093838215922820793766334539353762952507350475454732071659280, 2400499438983618692940189159631700542159222145491707907027391147659206494582970021302820336545010218513371064646527061311337068413980426448598708547679798), (6379663781361193014611200449797118722129634709503471706511279908764536219938459648859196147463736132344180113778601092741603098330061376323115464482342107, 8629554835368413912047551895840667218749053694545768537773896290059422290401463412017509705385398630783522251377233215565765194397930999511058978622876057), (7039065139500440281589307484102024271785176578683825020200946781098528981772443757014579531023297605219645322785589400163170871971836743493541233816898079, 4593229824372611907908775103450734214568303649676465133144653410051204005622425211159365276096465994869689264858974694128055897237933264343138656426877465), (11088093414029687628702921161107971796563312667327731805188741006469622384974659087755849834839203706047127005849568892168009150026723050453762252290082778, 2151567957127055257938140101478880653268415988826108946410001040705617336396510646577379112035863270338411831043142418830961326317785031136861804470304272), (10527694926095406031055185608275990554917090867921483961252788111078656198776927709171605054020314909280105508156201380170019108019175165984666471816770594, 10044940218068599613230634351641979827962921774265515550080566334481685130172827660677357621962754333445207367021790472455047451902749027433440310564392697), (9392436380839172882423963605949104094720677145349689577098509262697547555527268631599802779619266044983435905142007889266132399049867054730413893986040305, 164988482694870464413980138114343351662368942522471497717693908999698594387612234316498805037115936509113904833527763580932561835992784658496880185984866), (6956127737676490531426292131711872627247522259519705465384740100713218133674100965647277804272106953560643561751864433453923392267380411688968307071846307, 9164160949738360274512571610611956476656760651609341958216699025952454982289806396960546657642237157594546056678501123816848520997714132881419972438316403), (811174123406561700124279452048287283175389028135402047183215845338560775921962161974354282314553287452152276791227225547913526788464685283530555377504007, 4788900230259888619400556812427804331693848584040562124584037893249458247256424125541021023833225951620197555951694180569171171724979793094969554101952303), (1736682233486154410683835113015869629344648044580356253776803828767105159078666677116346579157444431929727831155640042184966782986536913298785407623707811, 5956479242552381563937300276377111345336991759070088400187861710482585910274532388075515699967940448034902119327442934275702408190006193692603919706443549), (4013279525694194347173154308911473420544385422498550718364692313155299215442908150551148501460496135245782361634203378846625926895085512415201537236895566, 1902753177706390097624306921789800778334195217542569757651857913301043355955459634821266031304005762631830538130632222369647843207148891353757813170297434), (4067507997965444976624685861896057234479418730640313763444629188870627444034819511881954765484464718227600918892299096151015302916608648437841689686039317, 4527385289218936918812173343439467707015227095224290359264738892108388706321564070183843485435827312334758607812585337722137614610114122030643878945779279), (338997763033935532814869176902554820400024788841829984365895451611815957160485020645467219597211333339002110402243665331243416196279868343210212041580190, 3485582242772643502405014036023218379736455098673589612235775614645540773027817032226979547104676034198998099892299215333525232022350297267244591667693912), (5766985815237821769598206059493311507378085744889305837305779902407188403983388373601086132780913691855876288394922334989682149049340300098915770228030905, 7753334190670676538446720585641859573433398743249700376484724298227907926849838085521963801408733235146240320346355009426906239872747392144736251780704977), (8299099631691361462893953510891571024438769990517881312043204121912273865770751850474084908124074498491364123876411607614783809672532677182810786551530236, 1850925269241030992691402475818420047494547060148283456210768271370265182087692429342859918730723443662381559466247461949717812910218990345175688951352463), (3153803035425954485388059217642503655668114692609711492446855252064443129547366536023055176005359522287016316267760750993074929407215122939099849400146684, 8212436592957141471533918899961881794532929265974532094198335625261970575879354714612726011218656880333087010971396164348888163103134249685035160466428893), (382776251972683162969137667785567984384290833592973844371610020937563323010839647792998943194116498772324465856791567205427662610024045091038814208263484, 676358016809511771333866886614256139498887961722630346274766646920140715993325241881077698730828177418833236078140586896144370558347572672150244705573519), (1691433422586309279816119068813544959916209612536303370492461656830904826416690221284704787208252738787389369317471538526983395018421865500920840681245663, 8403443691175628318411736415339597118989092964994031807359279687811927434675239227236567940010318597393775103350326829250819642598243721575412700792498900), (275806834075046641013656845029727938896135374487534330613029156229251702278764369369772064852312559831504835339696564904539551736015140639067445623431152, 6577150175375314081077722739090578027857810661765284783984639508642933027085377135918361786655916167922282799254162203359610957807591620427815841742171461), (5265903652703527428854672016212551093754479669961028121145288016160652115123235984477569118169510725255823273484188886656577477765631533875862655774967430, 5844658045975164560536702755522017021201699068948110473314041745782236538859637867917515787652073246575417282155529807235915240553861762687257791282155929), (10755958150627542439503991149243528352912807333945079169841313114537575617416916501230841947227017430365733523282575886141873994964186782784247910600422133, 5972264584103791666713406043123051515895497479181511683362693289465234484963177727868977634921335668191515839158160927877388276628500805325129382626589797), (2874899664578375983080728195667256942067344855479531687322864765538594373911892436945087043415841955863427589850322111827927636477081217711280709118874318, 6540406788521211835470251698063051662706898704267381715107551456767052583629832166003961937569833997328861496038345512332340380114045088129481899031991893), (10795521906690341353772601060644892051620578172176883594482772326651448283948314165229282203906464168702495741643062598036232174174127695291083810624554942, 6652625472869226167056761848338668216933432909457328262989386117179784558643677636006127533672984402759443631020780356519352673431773730684756836190699340), (7339235419213163414750352747610057623136858889814642133567062936815360603250260207647872023306809097694736247194874624893003076242957235361364339586853021, 5187782095170398198551458757942377008246293708992561530628060270139209180654493648130056902725573769819246400643646671985350867705852058069312175673985488), (1544129876235167854544782762775365882656702052172506506203380863898952829453926276823950429505877949412168631783546594771357821378503365392208987072003559, 7026458087980163221460582764199084613389639975772226907928090721491161856198484784481090429561216394513350683361380545854827390987196197393969946368336077), (4094944404044760466250567205213975777639108577925836641304058380946558879157675988189822587708635799268789931461760616526159151649612261301752329740376656, 7617445993346577313348341154852822159574750640978221029227889101432976720566638790653213605802846155613066288875992779638873350568769501902070806146693014), (1047171724289918884443388054089002620955976095601018978652974915706602837727859687503476839868655128412771307298616261093422446641323802691951730338375391, 8493097817612495005746562525578439841199022041487535790695823855541167774591234650229306314838514318082659056478241723539512908482058250795367549468045818), (6125277953182773690703210994168685482252039068786421523819650920598144427039838999734754427347812527212592563571649142129834001856311497237125332427371662, 8395574928161472064627370271176385006792228123838986698825194540578364280845737652181986634254146175463330719501615174747454931644314818285496715282911319)]
c=[]
for i in range(0,68,4):
    x1,y1=x[i]
    x2,y2=x[i+1]
    x3,y3=x[i+2]
    x4,y4=x[i+3]
    x_1=(x1-x3)*((y1^2-x1^3)-(y2^2-x2^3))-(x1-x2)*((y1^2-x1^3)-(y3^2-x3^3))
    x_2=(x1-x4)*((y1^2-x1^3)-(y2^2-x2^3))-(x1-x2)*((y1^2-x1^3)-(y4^2-x4^3))
    c.append(gcd(x_1,x_2))
p=find_gcd(c)

通过Gröbner基求出a，b

P.<a,b>=PolynomialRing(Zmod(p))
F=[]
f1 = x[0][0]^3 + a*x[0][0] + b - x[0][1]^2 
f2 = x[1][0]^3 + a*x[1][0] + b - x[1][1]^2
f3 = x[2][0]^3 + a*x[2][0] + b - x[2][1]^2
F.append(f1)
F.append(f2)
F.append(f3)

Ideal = P.ideal(F)
I = Ideal.groebner_basis()
# 求解参数a b n
res=[x.constant_coefficient() for x in I]
a = -res[0]%p
b = -res[1]%p

G是椭圆曲线的生成元可以通过E.gens()求出，那么通过smart's attack可以恢复出r*mi+e*ni+c+si的值

G = E.gens()[0]
def SmartAttack(P,Q,p):
    E = P.curve()
    Eqp = EllipticCurve(Qp(p, 2), [ ZZ(t) + randint(0,p)*p for t in E.a_invariants() ])

    P_Qps = Eqp.lift_x(ZZ(P.xy()[0]), all=True)
    for P_Qp in P_Qps:
        if GF(p)(P_Qp.xy()[1]) == P.xy()[1]:
            break

    Q_Qps = Eqp.lift_x(ZZ(Q.xy()[0]), all=True)
    for Q_Qp in Q_Qps:
        if GF(p)(Q_Qp.xy()[1]) == Q.xy()[1]:
            break

    p_times_P = p*P_Qp
    p_times_Q = p*Q_Qp

    x_P,y_P = p_times_P.xy()
    x_Q,y_Q = p_times_Q.xy()

    phi_P = -(x_P/y_P)
    phi_Q = -(x_Q/y_Q)
    k = phi_Q/phi_P
    return ZZ(k)
dec=[]
for i in x:
    dec.append(SmartAttack(G, E(i), p))
print(dec)
'''
dec=[1381140140387636499139721584594533513403436296579237811059271836196634019933110018051466994606177308742137962282353245071087454177569406479620399793267478, 6469068932534693823875159856666839625297907709293445857058184431423506747749027189320168773672683219068856404481354623002127709051192009573572742534557705, 4815470229510188878073055703710105464075385800932336151006561051327956350309645252575382616197804241464089113112798990498887244313464452463134675899694221, 10260085650592880353250536739681623840274147231096430590258588787254224075357841059381527133099021397986592013437943527299103578506759050179821558034953208, 3176541704960552801385852355564639628740881095457959630879279459343243459384295912674208332661042575486094825402088750775138046895142004669429911396468841, 8853899814731061316717441448266440275257654061258882629243238227728398771349819462321965089473005441551728388444990288120702567376936742983029364732645972, 9130850126759834833512584527964836925576384280425819633290670764369430042915858784877339229236998589519028605135309082602356344489815639609088128605497620, 4669557623573101547008048952276378266567735353763980073756959807883568915825466939280109081566606460456893548991747011151545386305940776537575638686107637, 999642048675513608846510569508244162588603730598805855318520972273733646301980393426595343466518365389752392432208643900868443653909957896419629044814799, 8490069661726698699704932410976097984776443788515884940524081039340419056519715681038926345890008322417091760306931082039815709658505150048320933922406056, 6828610315161630164616317609286164167971008618521456074838302633972102635346871376144681769091161990608862397197643725975083107852145070283223782204050010, 5893850280958176962609785967379929912592231853375990442647107876288724419064589704414000163841517139622354164044528356070042108706593423378985402785550833, 1641119885182410236144150830024926000707143945315807892411071358959075313306401600397562353005044637067648018649525510099499009432336287430536561328655287, 7473555778542418366298309615272949429197219582351926164129584456181599648916516895612139595759037005593537529128312605241973121065040162423659456325296701, 5474683745009548374533938284744457487846929405978403169969037803155023783045198870116957606274512763953453238322033381726967290528731854640010619839838621, 5300326910763946709761529716561694656502224516838298395207847790339143344312185136996620047421455927971690315910792073013330324546681376848333597297718872, 4514056417754055602361085897934561993771675566202232303886904016581240561871334190991142036583837475963275419000884873681726571095378033695040274067085488, 110455462723091880684285536641673102559201889806923679414507232553858732057921777510414605767530198233585689015493965074384105023342969219492222068431565, 3459270039184384313603065897105869695932389107482945100450928420183780259771690692320356028567507880544496827826126358792655254614447350905004253055515153, 3313351827332344821992775669775109749616297534202151659421507682719680731655580195336831035292104540647618329865220300500062029547613418805554866046636801, 675851532531360954642631315816617141150637803825442974665409343038033881697400984947946974345961905318156998667194704466043129471150257895721906448929945, 5325369494355298267198094009065316966510460742805252440958934262108395415677907994893872812221801751764960796499798071907802322618713714861068484545319861, 1641800597938021999398046782140335215305061906426607124090775551570113129791207988182231729132739977414794429238528752729246378667907554234195224418097854, 11068682734374528062919699929759177522722290814450300139244813629387979314283664866991691276486786994432224273099574612619827842144366542805436719450913017, 7781776484634083869260434204884007980906894175020027022071353285315628036183134930534488503758114200536568572191632322606594198863702306773419401499036817, 7997151894587105424775113729932802971685765132896379734250054372566717366465250520464907740121985061964604093878193121096675538760874117705705074775875241, 583033961737808854583950024325876440644055685379617221047278100081889867748800553079130730581648147853101597995380377454227019495742333634187707858997754, 10481995901920189590060842305338505507881922104604159772874455718462236108341033706417104893003032259672563387873139030838301241931534426059995499798987374, 10374163377218649252409863684021924455675439331233253354850315959391981445527516332786097733378385450074342336556390627680513811120895216613745855338462002, 3867380698317144929533030064426769222709909748444158488937489516843912899739754843073219757267817816224305639325338672136523983781326333431437447191674879, 9139497503456795643343691517086180890804651052360371738844491087673496700013358391578905506050801848109640369522408600236350956615018849214929661367482518, 6518723328614417195680598722488273794281007835713154593229758388275822439043976880116636236126357708666522779157413135193729436559708298247263521259734508, 5672854759315025147667634206335330290683589515154444019300776038634399007728205829815227777527333733760751481331287835295466797630783819034594608866374772, 1669162040716646837117444980127413279907629017010882146246497960432097633441204196618827068851544007250995950735917925613905279377768034311954081618612354, 11017869574693733258981740523994988396276247542293594951162535989385026700973138801773671750951362402657620147850669595044422933809723392166304362055283705, 7879105747984719346192073394382031351939180714825366123343068936495293088942054765896510665880077293312331462464791515374564089829063912822881948727078948, 9827533696214182132950655790734705872660406639701031998315042929467116208855132541566206910247463863762480624289787395396367914756961710295610067554737226, 1284177479418451047684137642963714213655885690508200233791234026539295583747015832652255866466885179645116126664288783515066956419444781437293044604049553, 2165331829752472138569772322582102670582905457569593371801886974455969901858907418821623949671833684631095570548600461166338703045272989441112540771954398, 6485014255482033894084633321433901773263863328155424575829646146730249737699279651030598031885275340286375830002976465328163940234710983894256279561966828, 4692079003728075900657511519084428705965756088001951635331172065716433331551420035445905282043771994444421389509061724935752064852169228897857571387320268, 7046685352177210747706736367484516606680117046628979226791782269675617628514090036573356252028088535010366015295239213003107727135729050380929320839333605, 7425507887451600556439178394620727565084656013029411029076670286919784278302393550847573774850181861261420883567826771905049600925769765064845949489128631, 10404159457793474905850614625848371371014097328011874960309551692263618325477983274656495449115918951047926771289457087984742073108607160810529662977535226, 4209220643330910530141426941434102457248006697472429223787576790799411676550898653194743021942218491899965574822795424692192662877339097254195797401823101, 10663501966340995847948305248567809289477192662209534332944288851243294059371685304695885583967460719420306738786730758345470094471723328136891912392472578, 3457637590879785922659004105176670080360066495236616126419681858497542144741223995729147591727427330981731566141653905759076814309925125018021138068968072, 1825329694701477182710212251991058419794630154584440732609772552701430849256538441159267771981346607441379349661430751934524244532143057509613615239384259, 6342643662123635298666845621673877342494143936923579794235729248747295048051554259155627926872336624249777529960587943894005921110730767840858865086697529, 7349051056859626470526099859480854861583514398692900299776385704429696495115898946578026526010563130069848337674376992202508265306112110308667818431467601, 975484534373720353514745699582025795725457841387562543903770981060686237557304043110387918966037188162796689224228551278590891462944009249863886571751668, 3390164651775100965743985199861217313055288327972884055518256640344282906851781885266843759090418974966876355771595559863888398889337146013979367975764528, 1532044182452440739253511735047732415547717143478292628713724862041102648137031138311820408664021608159970618078493317132194331440934136738567625136953022, 10916326041670546168867406054763982324931625508695741104309278140748030554008550429486388231008708465653118373884600937986813585721343144838757745590070297, 1831897607926785847189098742284077090135048317990680296558185826681249355924971926783173251892092892286446933650640589720302265522088907877563992785172450, 9063041152400345938792037542203844764606997806972887869055599068256742210920154086199840471974935257148085212642746091425515435500337824721284070851165150, 7348929381912468031813417975879595644028434946370954687011194097157133281205875700761443964738097361859803610089028085234351352552080223164400583855672871, 4899509850261996786478410232782267710719795004170119026844844791415049575809444752068108409283092174583644168392378273525619572597356827925502191113747397, 4167086806877654999775714431600944032166888679343084464690901195583082913177079536859416116467300513383499281472471351923108907451693403251879056463523664, 5230232806768308371365097923332730635814063589333681172979822932908924007821068146158822897308436066634936030965415180379511257327479585396163594403090379, 3214168337869955826822144983131294444124801746507614254895508040200603298777998703801074461653027179768660163765269513703116707842028059697996883966871599, 3158278863418749661351993118020091719387404658806286561383939033979716487522876472212825927226213574421599740033787474988204219392369934906722782678673017, 1507809474539839036207364938825809315498239722360654574197065565032789631556273804493015225368753563023524838523140682113919953929752457015292820423078934, 6984393290955894311400461357986888335280143777365161801944278535923604829698562575922093599631284608423709002904631741275492723129458069377136743795182567, 8008696293363279527424506452303387179504454634648868560266316012027176027099167618797486260711197435642782077801622128810823182011829517019300163531904463, 4318805974973371828217913838010031932903593670455830582610262110827531344070941227020840966235921098895075153019924882880959587895575699510810222399342924, 3504792024705329894440868447539311044265200333674250451992113076247495711150354544981369636684114071404034352098362543621958725998961113216357187190148198, 9152057987156977782344923581548541108896225361407993852135289126938439378375333727337720646585481019680837467010125152475914604636927494386360905681773269, 8909691746291593951573721563179165811276347908483428808845199592162157898178598999481309117628685432013297803562722126242667570381288396253782917793253144, 1443777848661803092753301775226212323455824036856706893230569017348297680163063529568181348106134741723047280510368409839217651780740432059177624399067613, 5916553952809093231614949131360561688934130250533549628139643251889128228439577835028811179524361146293570779965151822187030753511970687468686316352101217, 8056640581357594367370851125513888055696243443077079201997071806612452712612680931245575068135707225011380689800512817685068435780232073489461588936996770, 5548828368117601232695900023154508260834707210749907929086438617285447614801527358738080693886851594102821442273616440262587103493560145425414666999270474]
'''

求出dec，那么就需要造格来求flag了。

\[\begin{pmatrix} m_0 & n_1 & s_1 \\ \vdots & \vdots & \vdots\\ m_{72} & n_{72} & s_{72} \\ \end{pmatrix} * \begin{pmatrix} r \\ e \\ c \\ \end{pmatrix}=\begin{pmatrix}dec_0 \\ \vdots \\ dec_{72} \\ \end{pmatrix}\\ \]

\[设M=\begin{pmatrix} m_0 & n_1 & s_1 \\ \vdots & \vdots & \vdots\\ m_{72} & n_{72} & s_{72} \\ \end{pmatrix},D=\begin{pmatrix}dec_0 \\ \vdots \\ dec_{72} \\ \end{pmatrix}\\ 假设存在一个与D正交的矩阵R，使得\\ R*D=\begin{pmatrix}0 \\ \vdots \\ 0 \\ \end{pmatrix}\\ 那么R*M=\begin{pmatrix} 0 & 0 & 0 \\ \vdots & \vdots & \vdots \\ 0 & 0 & 0 \\ \end{pmatrix} \]

求正交矩阵R

那么需要找到这个正交矩阵，大佬也没说啥原理，就告诉我这样造格：

\[.\begin{pmatrix} E & D \\ 0 & p \end{pmatrix}\\ 格基规约后\\ \begin{pmatrix} R & 0 \\ 0 & p \\ \end{pmatrix} \]

这里格基规约后的R就是我们要求的正交矩阵，理想情况下最后一列的D都会被规约成0，但是不一定所以行都能规约成R。题目中的是73行，只有70行正交化了。这里可以自行规约一下结果，看最后一行的值是否为0，不为0则没有被正交化。

看2022强网杯 Lattice例题，这里满足n>m/2就能通过右核矩阵还原出M。其中n是规约后正交的行数，m为给出的数据行数。所以得到的正交行数是70行，可以还原出M。

还原M

这里涉及到右核矩阵，先解释一下什么是右核矩阵。右核矩阵指的是矩阵的右零空间的一种表示方式，右零空间是指所有使得矩阵与其右边乘积结果为零向量的向量的集合。右核空间的基可以使用sagemath中的right_kernel().basis()函数求出。

这里\(R*M=\begin{pmatrix} 0 & 0 & 0 \\ \vdots & \vdots & \vdots \\ 0 & 0 & 0 \\ \end{pmatrix}\)，因为M的每一列左乘R都是零向量，所以M的每一列都是矩阵R的右核解，我们要求的M第一列的值是在R的右核格上。

格基规约后的每行正交性是不变的。且M的第一列是短向量，期望对R求右核矩阵然后规约即可还原出M的第一列。

所以最终的exp：

#sage
from Crypto.Util.number import *

def find_gcd(numbers):   #求c中各元素的最大公约数
    result = numbers[0]
    for num in numbers[1:]:
        result = gcd(result, num)
    return result
x=[(4713513545399586887294281187501009141689080934674926984853052046637141607331993392136186920709675152470824454822335527736604585312216293390500894812356575, 10152198551269550712132843544953877513974069303791371586626547671550636936369607844350995807520993189830394615282586805640124173078292476320861958178531199), (8497709856659541496506566158438727086633064779296427286612559352247045304592577869075723270252557382159636274220949698085489427175611575498725494187042219, 9116811362014883884879981282521462123463402369273722016008105935084826801111377968641225157887930975588405833350168170885178864192235006321249285744756607), (9370988588550376568847533229569651406006327680521920971380933472551236466257993862023372207379492794618019196741718902793769742423589142369766582541381456, 2964764716081715738931864218952095017577031943078710662273038672326443429898927649838098895380036049701254956968440876093577389832396678079667784517400438), (9780561431490704165761200835168742342147019392307027843608906950941244751705916411353543429159840043103272583252784603317509552870673884311510395715589823, 4512360262119206250842086638048812502384840258083296584133384225879227543325169341795597008831855800692604773248185325609068166181249185285419214480894245), (9753892250466466740522543908112180868496775086018060713800521963469049945379911034546236677650557303039887137123496849920375395729255201971208204340312401, 1938991444752122074176200366358680893894177968559383024484416921026824613924903539687055302548680671218740698360348493115771464268448199996301653785482255), (3956377375220167264841327493686873211450973487259797861617968170206067349893946190638797758839551762336875162001035221844923167039774464458844780587411290, 2811884831397970155720238376608187196147035379379721383527942003189302602153280352219864817477497801745704924766135613808068056390979231466645561668031024), (9666287196438318899841485440079998120284795375413795856320443556455924086216013060731258663630259450515687636598820588811051314151419247760340027636254010, 6242436280614711684558785155511593403934172620329392146413928090178040475814185607897887229598797388837994931615621147403337923088271068952762638016855590), (6410558156839007797687898586831013305762106341458065938664504823229266562576428647033727809573119925974366171334827235046449418027002452010139094706683524, 166040140975198871456147224171862912756049890094169801765109995587970035602951233459371050668124316347586947163116257377961189202602060040019748070219990), (7487523686996071358586432253848922887425506981897556365676381361674713123268395354139090901692108603574450937831189242041732109717228219023361891682059858, 3833064097409451074126677286511876656776323298352406335396385518824369065179582162537034691375770260284647652021989411071188459726289169799948499527352978), (4729078931071331163964102690008525906997212672160480378168436234117369684502122703336874338708993594555380660201608846607091713539215909055852251780666200, 9671005639423355090071773219691535311565452170612214746096012853592987212889402308479743500146866239496815147634771960998944036591154433878637345854681580), (6821686173012785249374727322813382690658902308759017953636851870535291459139748120517278436478763860649866374062463951709695342159037267531366354633119425, 454109349563783364627292840194986877835558881374972642229389545049685682117058018008055923374865359150490448558569535600064463313774005486853335528084868), (8097352798426399714734815712595721555460575301502694560292887744521254417566780198441732519052015108845518267351690594699620710114415927821492280557184961, 3143117134725172187551030220914090560736539268901574157885702648644662853782339667244393783677404575650558122950108703297687085677618671682413400999092492), (6513183126611071344734801408546155978497170719570544711452832905026449120538993019567678246149684116904668717489068578437282308835637038352023972256007784, 8595256417577044566295431272464816721415384447710220168112404314046298881021487795315799293386989967911497645651199195527326646204582743481992783130665695), (2076200911997145561230367295021401989448362508676000676577311337299144867938580996744776932574458926497687916072562094577782433445706636680764023115075901, 4185181876972327147075282615187299338935965887368883151241490415013808432719173146515945602139988343152455030760117095904414901357566253216420331574702142), (8381148261138239703852416544878169891675330535019140791244013907671539392169214622437710482164782450053349339730858222886346055951588212694455090992026758, 10163796644510826165062555164776253676683391937554299535024512638738572461507137822548694428887856947619206289961946341513952367341327961199388454010911345), (7082052828661106343309085153914890287304976485666067977869367415115311594266326288964638667384892162749794084356403456012624482827804555380041185165461610, 10970779558480467455850489414892463070247230105462800369438019696961142385993997445973377590939104585064920741469159965752608152462788217994666526971187676), (10925547866913717228347553467715877154535344097358915967045800604047245512707552888643862816712660316383731871281241836192113460647119393339781321061847546, 6055866638544128750097137956427321128332370171075374382430335937167361572997526522356283730243910934362510966098560693257514648296238021784063773472282317), (6785790260925369751944279679131967774385917676053671994816660134554688581275392628347250117223466845286763120154394370759728270091856895114610818897127496, 6944819097069963408944767211243358274272483862643515403213512319523594830818990162549356650095103065424909926139792747369879142585803045804022938030858720), (10150680299085473411999071651257510437835183830128617479150385170276511661416391671621212657988922640891651500543376218492424168354335425534467598112916367, 6888072072792068816925242651491095512907051998862014192078971292171690924351979706726926617264447271133901394941261441480528738783229729193335653038691067), (6144733739837148454772329326705634341817968434802231929905485148699984301367998724275922187148848520362233957437728130259536441574897386258118529064688341, 6922401772481881149066720640583520627817261494001167856510602081133635708642763148740953963043376201851410699406141136890064725776678780016786484847583214), (7183537698681045949875783519960782529707812105971837366532045033353552615284313247237848218535204838266158925723440665819577893781022458960790760810597397, 972458879736849097211443260725151606545512204610922585342131271017385141140207247723299888723549405720647865837813721206081762170996939779151465778359883), (1703616895475378292849103149650192818023569782199400711730101432265869461747826906638002389489855890866591624514624290243581490849013123852690673668158707, 3965658649904842831282861075974019284939181243027712551012404295076584641786237749626883865637323655400727181532596793962284990080186320814580576232764219), (8963495302555958703784098831852945750716266028695276241049279835560446187278067379699423883547371501029976357779282379030218705676796414104820180108129131, 9560675517442950285567098226729931887208424165598207710747610570352243682357219160075511868468892440533601005756017577676212645247627512657664612197886753), (5895842943761546170585247530130278876214835406657491371251930010354754539149126507657276091840277248547506799183780141446090851820226059572960774100958968, 7502656301329564949518360786200839569606634784837274630989884217434653385706698020742131117367834019542645778778345958194210006811683442080243977814147856), (8640100751937124680820611508642732502895060458726683545757217842488862932846036386984435316630861618902973439137510767460729980613091227298179451141360505, 8882095605573426533581887021721414251562279415082941499209814199741153497994653123467952083382221269756103559259084746736753166028905023164640314021714001), (8388247659079623573428713053298218758880959226750090682709831798344118488654853756660826146966546928039026596856245651901691263742527856567914497516291114, 2554686546158926080572492543354230379583890635573966376628896520173183537504248326545786454456701917490537148658673048732906884172862899535090764870061838), (3522972508923517458292353763302819930303577548750539717212833970429996939300225630636854038507526101228562069393852224597963907070523982294660351842280633, 2722886940087289673479756522605024512774339223436171406753474672760772800787941732367711740776438505211011207232095730057266822772428493683405241349648820), (5747287482977987126791251898912454610276486805219445014219573080628876839977604195669030439484891046209507206924952426057204453046696371912908633064230479, 6888743201368571672232377272185024669203662616683269994478128192921909999937032609025815813649655882205087573705374103086536384400013495005395551198713651), (5395805452593588173733709867409415556635519685320679663417386653285203287195773348337753725970479425032796150389196920192180585906474753231777661079289437, 2049198785703634792274246696306539108405783634680414306952855128318576045437021450775416575637372374508674635396511497565807111357058258974223438148878139), (1106569381500878776327074503776544923606655454675632799210090625837364461937678338160512692988670222225824403087574662143185601960224018905113923782270539, 7807167264259112235256140538958359886355420172448675887504580682313196334695678083464576229080110711789720570909552233828459789174622915149390826529983979), (774420854887127501308191286785213114311123916232266805877360705182482499403790079656851056723325281443761295724878231930299234031094963169518924985204326, 1823239988080736026294280175757387698370391442147440999541017982717190148487204580007594680643967202283878443924878273089191744975594960310070541049913208), (10390768586716868216274885948565940967753406041172076158220674075063692958975829973565237035576416388533593319064806625802185370125475892280705287378008167, 7936898961487579224597034819214266150399838606754275451599382249114378117387985558608837253849686999975720266799298482522115282514491361371396094456368516), (6559061475296632413236056122203276549479841984223974661947570674250692681575131892757949944065429272895838779365614183240180694750678008976228961748322336, 473245583943987902110281484140499960244770537636405429845479764689369773269971976056888748769095922326063256384576160463655904425218553458364943959899086), (6990897946181173410381225887279699398546212633701662109218390739579375069633389645336979977106684274400300780444554545122065074307060125703820181316384214, 7819208183328181779638777784468566190149101582692741398921460936301776675490965897874825617770665564614702759841245059168666900633861059762858637125280948), (7747435518316782982483754090978229664138034777481959364950240813857697188791265248527812695232235005608599944025036371707403013790647331893879773212237043, 3159418369091201654146413539772282132593105789449657281371263577186276285132860600728403344673301949317743362672738811296195856181843548485016286031920833), (3369791038393301556741708575440525525282467890252654592506744643498949048083071439806419974633826916428682344210022547978555038915574927383371276122836437, 1254207105162683404624839305815976360434593439971534044690683811862373371974690050945107547088863949294187872065584471393112103746592673505295745839104903), (12559802051565696220908490791176980888215159475214543819591025553038397887258210157937107348856671923347442195747214530113819589139784491311068764022315, 92137825928577563592704152890340316446433940657283569689729668523058912940157586067464548561955548003087234875918821018302106943344124622115389236652708), (5530860676475771990691794230197843848995136632588902707671870008682291466072853151674692329856555254129777934598717106397379676504637402898491515647019614, 7607657346401777274388222553201723127198119754377956597528780653945092019992176978208398510287887955973308860512490030992878891943040624792754656069217442), (8656514966764534509634687395591541433018230421930114964742418579055006526313285528361583224660642964199912067740313821869193158938537412710631568658169841, 4116821657037353549042717433725360946713128495027684788081224012710596099770343092504822988643111922114078504358308321081016458737603136815718086377286312), (8100831214626791708799713927585164778396993990058862482613985356488740056554280863238290359683223040430278300948843843441559818431263141038149252959678174, 7157146800294342965648679696235976006969454630987554609240655182227200766624871072125866911886299487131892259075918834107331341357650921521849485533872689), (10890755415745834079684707961450267393014312434887212673127786238658853553163490057950949556382435981261018626537652744836077613969932720662450748419434520, 5279648749877701240684141308917960279039127385754415377927568487239966645994472078390526598966778096179381589406514532819180811465019758802791435100869881), (9060075587488082866770299601000001129096055062459420816879850056758836467625363905808761432389493095202971219869587736150065097181836148704494938392336936, 3043213364684213962601012696251843801198320049133534260158876000568009047174757647991108751400672840493299153730363664649892567435814928501814954691990523), (3900860495400935419474632339214283753209440821844587105288679983316600743413043557244051819610723553012673147837484933074775700024738029322306219374175466, 8776159342624965969607240788610667981250366112487928135123108438906795434150675020540621553123713010466600434042759568095802865668466320036637390801734330), (8892508982428674296232570395108858435301220674549059757865650461633339757693888275460458282826216723318314278599996754746396225250466370460643994463970197, 9849460100328796212561749973397004158854148228901082087955317687788087821727683490635917903048647923933946683751563384919385239051043522197194110574632931), (10923358262051920487577188144536432256688530690409723011811352726717234614031126144612568470205593144080520262586830305738866710154785063559118988651582041, 4278762242548247544689233335926765616778120425273995711653646115727314071200548262199619769930492354067641770131381420729138534905254921562061287863678579), (8521580982419336726352152980518468054450102755517772937105339841639190905405892229656525386511809992487375982957938116145220023166622765996136275506785708, 10265827555400740987534703970942130173226636930554901199221250047258482081430913795266364437774976529788958093275042612558863535039271906282995137107627584), (2430642973360021054121784023477961807614448837359566950318322641585771572293505818234749487480093838215922820793766334539353762952507350475454732071659280, 2400499438983618692940189159631700542159222145491707907027391147659206494582970021302820336545010218513371064646527061311337068413980426448598708547679798), (6379663781361193014611200449797118722129634709503471706511279908764536219938459648859196147463736132344180113778601092741603098330061376323115464482342107, 8629554835368413912047551895840667218749053694545768537773896290059422290401463412017509705385398630783522251377233215565765194397930999511058978622876057), (7039065139500440281589307484102024271785176578683825020200946781098528981772443757014579531023297605219645322785589400163170871971836743493541233816898079, 4593229824372611907908775103450734214568303649676465133144653410051204005622425211159365276096465994869689264858974694128055897237933264343138656426877465), (11088093414029687628702921161107971796563312667327731805188741006469622384974659087755849834839203706047127005849568892168009150026723050453762252290082778, 2151567957127055257938140101478880653268415988826108946410001040705617336396510646577379112035863270338411831043142418830961326317785031136861804470304272), (10527694926095406031055185608275990554917090867921483961252788111078656198776927709171605054020314909280105508156201380170019108019175165984666471816770594, 10044940218068599613230634351641979827962921774265515550080566334481685130172827660677357621962754333445207367021790472455047451902749027433440310564392697), (9392436380839172882423963605949104094720677145349689577098509262697547555527268631599802779619266044983435905142007889266132399049867054730413893986040305, 164988482694870464413980138114343351662368942522471497717693908999698594387612234316498805037115936509113904833527763580932561835992784658496880185984866), (6956127737676490531426292131711872627247522259519705465384740100713218133674100965647277804272106953560643561751864433453923392267380411688968307071846307, 9164160949738360274512571610611956476656760651609341958216699025952454982289806396960546657642237157594546056678501123816848520997714132881419972438316403), (811174123406561700124279452048287283175389028135402047183215845338560775921962161974354282314553287452152276791227225547913526788464685283530555377504007, 4788900230259888619400556812427804331693848584040562124584037893249458247256424125541021023833225951620197555951694180569171171724979793094969554101952303), (1736682233486154410683835113015869629344648044580356253776803828767105159078666677116346579157444431929727831155640042184966782986536913298785407623707811, 5956479242552381563937300276377111345336991759070088400187861710482585910274532388075515699967940448034902119327442934275702408190006193692603919706443549), (4013279525694194347173154308911473420544385422498550718364692313155299215442908150551148501460496135245782361634203378846625926895085512415201537236895566, 1902753177706390097624306921789800778334195217542569757651857913301043355955459634821266031304005762631830538130632222369647843207148891353757813170297434), (4067507997965444976624685861896057234479418730640313763444629188870627444034819511881954765484464718227600918892299096151015302916608648437841689686039317, 4527385289218936918812173343439467707015227095224290359264738892108388706321564070183843485435827312334758607812585337722137614610114122030643878945779279), (338997763033935532814869176902554820400024788841829984365895451611815957160485020645467219597211333339002110402243665331243416196279868343210212041580190, 3485582242772643502405014036023218379736455098673589612235775614645540773027817032226979547104676034198998099892299215333525232022350297267244591667693912), (5766985815237821769598206059493311507378085744889305837305779902407188403983388373601086132780913691855876288394922334989682149049340300098915770228030905, 7753334190670676538446720585641859573433398743249700376484724298227907926849838085521963801408733235146240320346355009426906239872747392144736251780704977), (8299099631691361462893953510891571024438769990517881312043204121912273865770751850474084908124074498491364123876411607614783809672532677182810786551530236, 1850925269241030992691402475818420047494547060148283456210768271370265182087692429342859918730723443662381559466247461949717812910218990345175688951352463), (3153803035425954485388059217642503655668114692609711492446855252064443129547366536023055176005359522287016316267760750993074929407215122939099849400146684, 8212436592957141471533918899961881794532929265974532094198335625261970575879354714612726011218656880333087010971396164348888163103134249685035160466428893), (382776251972683162969137667785567984384290833592973844371610020937563323010839647792998943194116498772324465856791567205427662610024045091038814208263484, 676358016809511771333866886614256139498887961722630346274766646920140715993325241881077698730828177418833236078140586896144370558347572672150244705573519), (1691433422586309279816119068813544959916209612536303370492461656830904826416690221284704787208252738787389369317471538526983395018421865500920840681245663, 8403443691175628318411736415339597118989092964994031807359279687811927434675239227236567940010318597393775103350326829250819642598243721575412700792498900), (275806834075046641013656845029727938896135374487534330613029156229251702278764369369772064852312559831504835339696564904539551736015140639067445623431152, 6577150175375314081077722739090578027857810661765284783984639508642933027085377135918361786655916167922282799254162203359610957807591620427815841742171461), (5265903652703527428854672016212551093754479669961028121145288016160652115123235984477569118169510725255823273484188886656577477765631533875862655774967430, 5844658045975164560536702755522017021201699068948110473314041745782236538859637867917515787652073246575417282155529807235915240553861762687257791282155929), (10755958150627542439503991149243528352912807333945079169841313114537575617416916501230841947227017430365733523282575886141873994964186782784247910600422133, 5972264584103791666713406043123051515895497479181511683362693289465234484963177727868977634921335668191515839158160927877388276628500805325129382626589797), (2874899664578375983080728195667256942067344855479531687322864765538594373911892436945087043415841955863427589850322111827927636477081217711280709118874318, 6540406788521211835470251698063051662706898704267381715107551456767052583629832166003961937569833997328861496038345512332340380114045088129481899031991893), (10795521906690341353772601060644892051620578172176883594482772326651448283948314165229282203906464168702495741643062598036232174174127695291083810624554942, 6652625472869226167056761848338668216933432909457328262989386117179784558643677636006127533672984402759443631020780356519352673431773730684756836190699340), (7339235419213163414750352747610057623136858889814642133567062936815360603250260207647872023306809097694736247194874624893003076242957235361364339586853021, 5187782095170398198551458757942377008246293708992561530628060270139209180654493648130056902725573769819246400643646671985350867705852058069312175673985488), (1544129876235167854544782762775365882656702052172506506203380863898952829453926276823950429505877949412168631783546594771357821378503365392208987072003559, 7026458087980163221460582764199084613389639975772226907928090721491161856198484784481090429561216394513350683361380545854827390987196197393969946368336077), (4094944404044760466250567205213975777639108577925836641304058380946558879157675988189822587708635799268789931461760616526159151649612261301752329740376656, 7617445993346577313348341154852822159574750640978221029227889101432976720566638790653213605802846155613066288875992779638873350568769501902070806146693014), (1047171724289918884443388054089002620955976095601018978652974915706602837727859687503476839868655128412771307298616261093422446641323802691951730338375391, 8493097817612495005746562525578439841199022041487535790695823855541167774591234650229306314838514318082659056478241723539512908482058250795367549468045818), (6125277953182773690703210994168685482252039068786421523819650920598144427039838999734754427347812527212592563571649142129834001856311497237125332427371662, 8395574928161472064627370271176385006792228123838986698825194540578364280845737652181986634254146175463330719501615174747454931644314818285496715282911319)]
c=[]
for i in range(0,68,4):
    x1,y1=x[i]
    x2,y2=x[i+1]
    x3,y3=x[i+2]
    x4,y4=x[i+3]
    x_1=(x1-x3)*((y1^2-x1^3)-(y2^2-x2^3))-(x1-x2)*((y1^2-x1^3)-(y3^2-x3^3))
    x_2=(x1-x4)*((y1^2-x1^3)-(y2^2-x2^3))-(x1-x2)*((y1^2-x1^3)-(y4^2-x4^3))
    c.append(gcd(x_1,x_2))
p=find_gcd(c)
P.<a,b>=PolynomialRing(Zmod(p))
F=[]
f1 = x[0][0]^3 + a*x[0][0] + b - x[0][1]^2 
f2 = x[1][0]^3 + a*x[1][0] + b - x[1][1]^2
f3 = x[2][0]^3 + a*x[2][0] + b - x[2][1]^2
F.append(f1)
F.append(f2)
F.append(f3)

Ideal = P.ideal(F)
I = Ideal.groebner_basis()
# 求解参数a b n
res=[x.constant_coefficient() for x in I]
a = -res[0]%p
b = -res[1]%p
E = EllipticCurve(GF(p), [a, b])
G = E.gens()[0]
def SmartAttack(P,Q,p):
    E = P.curve()
    Eqp = EllipticCurve(Qp(p, 2), [ ZZ(t) + randint(0,p)*p for t in E.a_invariants() ])

    P_Qps = Eqp.lift_x(ZZ(P.xy()[0]), all=True)
    for P_Qp in P_Qps:
        if GF(p)(P_Qp.xy()[1]) == P.xy()[1]:
            break

    Q_Qps = Eqp.lift_x(ZZ(Q.xy()[0]), all=True)
    for Q_Qp in Q_Qps:
        if GF(p)(Q_Qp.xy()[1]) == Q.xy()[1]:
            break

    p_times_P = p*P_Qp
    p_times_Q = p*Q_Qp

    x_P,y_P = p_times_P.xy()
    x_Q,y_Q = p_times_Q.xy()

    phi_P = -(x_P/y_P)
    phi_Q = -(x_Q/y_Q)
    k = phi_Q/phi_P
    return ZZ(k)
dec=[]
#计算有点久
for i in x:
    dec.append(SmartAttack(G, E(i), p))
# print(dec)

M=Matrix(ZZ,74,74)
for i in range(73):
    M[i,i]=1
    M[i,-1]=dec[i]
M[-1,-1]=p
R=M.LLL()
LK=[]
for i in R:
    if i[-1]!=0:
        break
    else:
        LK.append(i[:-1])
print(len(LK))
LK=Matrix(ZZ,LK)
LK1=LK.right_kernel().basis()  #LK.right_kernel().basis()计算右零空间的基
print(len(LK1))
key=Matrix(ZZ,LK1).LLL()[0] 
for i in key:
    print(chr(long_to_bytes(ZZ(i))[-1]),end='')
#flag{893d041e-c0a2-3145-5320-cdee7d3c87fb}

参考：https://blog.csdn.net/qq_41626232/article/details/131861414

标签：Qp,Rosita,极客,Crypto,xy,pmatrix,x1,dec,vdots
From： https://www.cnblogs.com/L00kback/p/17573063.html