1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142
| from sage.all import * from math import gcd
pts =[(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)]
n = len(pts)
def recover_curve(points): g = 0 for i in range(len(points) - 3): (x1,y1),(x2,y2),(x3,y3),(x4,y4) = points[i:i+4]
t1 = y2^2 - y1^2 - x2^3 + x1^3 t2 = y3^2 - y2^2 - x3^3 + x2^3 t3 = y4^2 - y3^2 - x4^3 + x3^3
k1 = t1*(x3-x2) - t2*(x2-x1) k2 = t2*(x4-x3) - t3*(x3-x2) k3 = t1*(x4-x3) - t3*(x2-x1)
g = gcd(g, abs(int(k1))) g = gcd(g, abs(int(k2))) g = gcd(g, abs(int(k3)))
p = ZZ(g)
# 去掉小因子(这题通常会多一个 2) for q in prime_range(2, 2000): while p % q == 0: cand = p // q if all(px < cand and py < cand for px, py in points): p = cand else: break
for i in range(len(points)): for j in range(i + 1, len(points)): x1, y1 = points[i] x2, y2 = points[j] if gcd(int(x2 - x1), int(p)) == 1: f1 = (y1*y1 - x1*x1*x1) % p f2 = (y2*y2 - x2*x2*x2) % p a = ((f2 - f1) * inverse_mod(x2 - x1, p)) % p b = (f1 - a*x1) % p return p, a, b
raise ValueError("recover curve failed")
def SmartAttack(P, Q, p): E = P.curve()
Ep = EllipticCurve( Qp(p, 2), [ZZ(t) + ZZ.random_element(0, p) * p for t in E.a_invariants()] )
# lift P for cand in Ep.lift_x(ZZ(P.xy()[0]), all=True): if GF(p)(cand.xy()[1]) == P.xy()[1]: P_Qp = cand break else: raise ValueError("lift P failed")
# lift Q for cand in Ep.lift_x(ZZ(Q.xy()[0]), all=True): if GF(p)(cand.xy()[1]) == Q.xy()[1]: Q_Qp = cand break else: raise ValueError("lift Q failed")
pP = p * P_Qp pQ = p * Q_Qp
xP, yP = pP.xy() xQ, yQ = pQ.xy()
phiP = -(xP / yP) phiQ = -(xQ / yQ)
return ZZ(phiQ / phiP)
def vec_to_flag(v): return bytes([int(t) & 0xff for t in v])
print("[+] recovering curve ...") p, a, b = recover_curve(pts) print("[+] p =", p) print("[+] a =", a) print("[+] b =", b)
E = EllipticCurve(GF(p), [a, b])
for i, (xx, yy) in enumerate(pts): _ = E(xx, yy) print("[+] all points are on the curve")
ordE = E.order() print("[+] #E(F_p) =", ordE) assert ordE == p, "this solver expects an anomalous curve"
G = E.gens()[0] print("[+] generator =", G)
print("[+] running Smart attack on all points ...") d = [] for i, pt in enumerate(pts): di = SmartAttack(G, E(pt), p) % p d.append(ZZ(di)) print(f" done {i+1}/{n}")
print("[+] building lattice ...") K = 2^100 L = Matrix(ZZ, n + 1, n + 1) for i in range(n): L[i, i] = 1 L[i, n] = d[i] * K L[n, n] = p * K
B = L.LLL()
# 原关系有 3 列,所以取 n-3 行构造正交约束 rows = n - 3 R = Matrix(ZZ, rows, n) for i in range(rows): R[i] = B[i][:n]
print("[+] kernel basis ...") KB = Matrix(ZZ, R.right_kernel().basis()) KB = KB.LLL()
print("[+] candidates:") for i, v in enumerate(KB): c1 = vec_to_flag(v) c2 = vec_to_flag(-v) print(f"[{i}] {c1}") print(f"[{i}] {c2}") if b"flag{" in c1: print("\n[FOUND]", c1) if b"flag{" in c2: print("\n[FOUND]", c2)
|