[巅峰极客2023]Rosita题解

Author：苏氨酸
发布时间：January 8, 2024
252 views
2 comments
52122 words
Categories： CTF题解

从2022年强网杯的Lattice开始，正交格攻击这个套路在CTF比赛中已经出现很多次了，不过我一直没接触。最近读到tl2cents的格密码分析：正交格攻击，读了几篇paper才发现，仅仅作为脚本小子解这些CTF题来说，并不需要深入搞懂它是怎么work的。掌握问题形式之后就是"基于Ctrl+C和Ctrl+V的复现"（春言春语）。

接下来记录一道关于HLCP（HSSP的扩展形式，换汤不换药）的题目的解法。

题目

from Crypto.Util.number import *
from hashlib import sha256
from os import urandom
from Crypto.Util.number import bytes_to_long as b2l

from secret import p, a, b, flag

p=getPrime(512)
flag=b'flag{??????????????}'
a=randint(1,p-1)
b=randint(1,p-1)
ECC = EllipticCurve(GF(p), [a, b])
R, E, C = [ECC.random_point() for _ in range(3)]
M=Matrix(ZZ,len(flag),3)
pad = lambda m: urandom(8) + m + b'\x00' * (ZZ(p).nbits() // 8 - len(m) - 8 - 1)
out = list()
for i in range(len(flag)):
m = pad(chr(flag[i]).encode())
nonce = urandom(16)
sh = sha256(nonce + m).digest()
Q = b2l(m)*R + b2l(nonce)*E + b2l(sh)*C
out.append(Q)

with open('out.tuo', 'w') as f:
f.write(str(out))

[(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)]

第一步：恢复曲线参数

我们唯一已知的就是一系列点$Q_i$，也就是已知：

$$ \begin{align} y_0^2 &\equiv x_0^3 + ax_0 + b &\pmod{p} \\ y_1^2 &\equiv x_1^3 + ax_1 + b &\pmod{p} \\ y_2^2 &\equiv x_2^3 + ax_2 + b &\pmod{p} \\ &\cdots \end{align} $$

对一对点$(x_0,y_0),(x_1,y_1)$进行分析：

$$ \begin{align} y_0^2 &\equiv x_0^3 + ax_0 + b &\pmod{p}\\ y_1^2 &\equiv x_1^3 + ax_1 + b &\pmod{p} \\ \hline & & \text{subtract}\\ y_0^2 - y_1^2 &\equiv x_0^3 - x_1^3 + a (x_0 - x_1) &\pmod{p}\\ a (x_0 - x_1) &\equiv (y_0^2 - y_1^2) -(x_0^3 - x_1^3) &\pmod{p}\\ a&\equiv [(y_0^2 - y_1^2) -(x_0^3 - x_1^3)] \cdot (x_0 - x_1)^{-1} &\pmod{p}\\ \end{align} $$

如果$p$已知的话按上面的推导即可求出$a$。不过这里我们并不知道$p$，最后一步没法求逆元。所以另谋它法，先考虑消去$a$求$p$。加入另一对点的关系来消去$a$：

$$ \begin{align} (y_0^2 - y_1^2) -(x_0^3 - x_1^3)&\equiv a (x_0 - x_1) &\pmod{p}\\ (y_1^2 - y_2^2) -(x_1^3 - x_2^3)&\equiv a (x_1 - x_2) &\pmod{p}\\\\ \end{align} $$

$$ \begin{align} [(y_0^2 - y_1^2) -(x_0^3 - x_1^3)](x_1-x_2)&\equiv a (x_0 - x_1)(x_1-x_2) &\pmod{p}\\ [(y_1^2 - y_2^2) -(x_1^3 - x_2^3)](x_0-x_1)&\equiv a (x_0-x_1)(x_1 - x_2) &\pmod{p}\\ \hline & & \text{subtract}\\ [(y_0^2 - y_1^2) -(x_0^3 - x_1^3)](x_1-x_2)-[(y_1^2 - y_2^2) -(x_1^3 - x_2^3)](x_0-x_1)&\equiv 0 &\pmod{p} \end{align} $$

也就是说我们可以用3个点的坐标，来求出$p$的一个倍数。我们对已知的所有点$Q_i$求长度为3的全排列，结果取gcd：

out = '[(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)]'
Qs = eval(out)

from itertools import permutations
kps = []
for triplet in permutations(Qs, int(3)):
    x0, y0 = triplet[0]
    x1, y1 = triplet[1]
    x2, y2 = triplet[2]
    kp = ((y0^2-y1^2)-(x0^3-x1^3))*(x1-x2) - ((y1^2-y2^2)-(x1^3-x2^3))*(x0-x1)
    kps.append(kp)
  
p = gcd(kps)
assert is_prime(p)
print("Found p:", p)
# Found p: 11093300438765357787693823122068501933326829181518693650897090781749379503427651954028543076247583697669597230934286751428880673539155279232304301123931419

恢复$a,b$。此处变量名应该用EC（EllipticCurve）更合适，但遵照题目附件，仍用ECC。

a = ((y0^2-y1^2)-(x0^3-x1^3)) * inverse_mod(x0-x1, p) % p
b = (y0^2 - x0^3 - a*x0) % p
ECC = EllipticCurve(GF(p), [a, b])
print(ECC)
# Elliptic Curve defined by y^2 = x^3 + 490963434153515882934487973185142842357175523008183292296815140698999054658777820556076794490414610737654365807063916602037816955706321036900113929329671*x + 7668542654793784988436499086739239442915170287346121645884096222948338279165302213440060079141960679678526016348025029558335977042712382611197995002316466 over Finite Field of size 11093300438765357787693823122068501933326829181518693650897090781749379503427651954028543076247583697669597230934286751428880673539155279232304301123931419

第二步：Smart's Attack

直接把恢复出来的参数拿去搜索引擎一搜，发现好几道Smart Attack的题用的都是这个参数，可能是出题人没找到生成anomalous curve的方法，所以都抄来抄去233。经过一番探索，找到一个工具ecgen可以用于生成曲线参数。

扯远了，回到做题人视角。$Q_i$被表示为

$$ Q_i=m_iR_i+n_iE_i+s_iC_i $$

设$R=rG,E=eG,C=cG$，则有

$$ Q_i=(m_ir+n_ie+s_ic)G $$

这样只要求一步ECDLP，就拿到了一系列方程：

$$ \textbf{h}=r\textbf{m}+e\textbf{n}+c\textbf{s}\pmod{p} $$

其中只有$\textbf{h}$和$p$已知。

由于 ECC.order() == p，直接应用Smart's Attack求解ECDLP即可。板子)

第三步：隐藏线性组合问题（HLCP）

上面得到的式子实际上属于隐藏线性组合问题（Hidden Linear Combination Problem，HLCP），这个概念是在Provably Solving the Hidden Subset Sum Problem via Statistical Learning中提出的，是对隐藏子集和问题（Hidden Subset Sum Problem，HSSP）的一般化，把随机向量的分量取值从$\{0,1\}$扩展到了$[0,B]\cap \mathbb{Z}$。

直接对Nguyen-Stern算法进行扩展即可求解HLCP，不需要用文献中新提出的统计学习方法。具体分析可以阅读原文献。

回到题目，分析几个向量的分量大小：

$m_i$ : 504bit
$n_i$ : 128bit
$s_i$ : 256bit
$p$ : 1024bit

这个$m_i$比较大，然而注意到$m_i$的低位是54个 \x00（即432bit），我们可以记$m_i$高位的72bit为$m_i'$，构成向量$\textbf{m}'$，记$r'=2^{432}\cdot r$，便得到了：

$$ \textbf{h}=r'\textbf{m}'+e\textbf{n}+c\textbf{s}\pmod{p} $$

这样上界$B$就大大缩小。

接下来我们来逐步实现Nguyen-Stern算法（本文就题论题，针对本题做了简化，更多细节可以参看A Polynomial-Time Algorithm for Solving the Hidden Subset Sum Problem及其提供的实现）

Step 1：从$\textbf{h}$确定$\bar{\mathcal{L}_x}$（正交格攻击）

首先构造$\mathcal{L}_0$的一个基

$$ \mathcal{L}_0 = \left(\begin{array}{cccc} p & & & & \\ -h_2\cdot h_1^{-1}[p] & 1 & & \\ -h_3\cdot h_1^{-1}[p] & & 1\\ \vdots & & & \ddots & \\ -h_m\cdot h_1^{-1}[p] & & & & 1 \\ \end{array}\right)_{m \times m} $$

# We generate the lattice of vectors orthogonal to h modulo p
def orthoLattice(h, p):
    m = h.length()
    L0 = Matrix(ZZ, m, m)

    for i in range(1, m):
        L0[i, i] = 1
    L0[1:m, 0] = -h[1:m] * inverse_mod(h[0], p)
    L0[0, 0] = p

    for i in range(1, m):
        L0[i, 0] = mod(L0[i, 0], p)

    return L0

我们知道，给定一个格$\mathcal{L}$，使用LLL算法可以计算出$\mathcal{L}^\perp$的LLL-reduced基。

这里在$\mathbb{Z}_p$下计算$\mathcal{L}_0^\perp$的LLL-reduced基。

L0 = orthoLattice(h, p)
L0_perp = L0.LLL()

取出$\mathcal{L}_0^\perp$的LLL-reduced基的前$m-n$个向量，恰好就是$\mathcal{L}_x^{\perp}$的一个生成集。

Lx_perp = L0_perp[:m-n]

最后在$\mathbb{Z}$下计算$\mathcal{L}_x^{\perp}$的一个右核空间$\bar{\mathcal{L}_x}={(\mathcal{L}_x^{\perp})}^\perp$：

def kernelLLL(M):
    n=M.nrows()
    m=M.ncols()
    if m<2*n: return M.right_kernel().matrix()
    K=2^(m//2)*M.height()
    
    MB=Matrix(ZZ,m+n,m)
    MB[:n]=K*M
    MB[n:]=identity_matrix(m)
    
    MB2=MB.T.LLL().T
    
    assert MB2[:n,:m-n]==0
    Ke=MB2[n:,:m-n].T
 
    return Ke
Lx_bar = kernelLLL(Lx_perp)

kernelLLL()实现的原理还有待进一步分析（还没很好地把握LLL在这里怎么work的，经过初步探索找到这篇paper，有时间再读）。

至此我们完成了第一步的任务。

Step 2：从$\bar{\mathcal{L}_x}$恢复向量$\textbf{x}_i$，再恢复权重$\alpha_i$

对于标准Nguyen-Stern算法，从$\bar{\mathcal{L}_x}$恢复$x_i$是通过计算BKZ-reduced基，并筛选符合条件的基。由于这个算法的复杂度是$n$的指数级别，所以$n$大一点的时候就需要采用A Polynomial-Time Algorithm for Solving the Hidden Subset Sum Problem里边改进的多项式时间算法。论文的实现是先做LLL，然后依次尝试BKZ-10、BKZ-20、BKZ-30。

对于本题，n=3，仅用LLL算法即可求解，一发入魂！同时本题flag是嵌入在向量中的，无需进一步恢复权重。

# Step 2
flag = bytes(m & 0xFF for m in Lx_bar.LLL().list())
print(flag)

总结

从仅有的一系列点坐标中竟然能恢复这么丰富的信息，Crypto真好玩.jpg

本题完整exp如下：solve.ipynb。

Last modification：January 9, 2024

如果觉得我的文章对你有用，请随意赞赏

2 comments

diffany
January 10th, 2024 at 01:04 pm

alert(1)

Reply
[IrisCTF2024]Crypto部分题解（二）——manykey - 苏氨酸
January 9th, 2024 at 08:51 pm

[...]# 6276558150548653530270409953235291693375654678911154305751在[[巅峰极客2023]Rosita题解](http://www.thr-sec.com/index.php/archives/4/)中，我们提到了一个生成曲线参数的工具，它可以"Generate a curve with given ORDER (using Complex M[...]

Reply

[巅峰极客2023]Rosita题解

苏氨酸 • 2024 年 01 月 08 日

从2022年强网杯的Lattice开始，正交格攻击这个套路在CTF比赛中已经出现很多次了，不过我一直没接触。最近读到tl2cents的<a class="no-external-link" href="https://tl2cents.github.io/2023/12/12/Orthogonal-Lattice-Attack/" target="_blank">格密码分析：正交格攻击</a>，读了几篇paper才发现，仅仅作为脚本小子解这些CTF题来说，并不需要深入搞懂它是怎么work的。掌握问题形式之后就是"基于Ctrl+C和Ctrl+V的复现"（春言春语）。接下来记录一道关于HLCP（HSSP的扩展形式，换汤不换药）的题目的解法。<h1>题目</h1><pre><code class="lang-python">from Crypto.Util.number import *
from hashlib import sha256
from os import urandom
from Crypto.Util.number import bytes_to_long as b2l

from secret import p, a, b, flag

p=getPrime(512)
flag=b'flag{??????????????}'
a=randint(1,p-1)
b=randint(1,p-1)
ECC = EllipticCurve(GF(p), [a, b])
R, E, C = [ECC.random_point() for _ in range(3)]
M=Matrix(ZZ,len(flag),3)
pad = lambda m: urandom(8) + m + b'\x00' * (ZZ(p).nbits() // 8 - len(m) - 8 - 1)
out = list()
for i in range(len(flag)):
m = pad(chr(flag[i]).encode())
nonce = urandom(16)
sh = sha256(nonce + m).digest()
Q = b2l(m)*R + b2l(nonce)*E + b2l(sh)*C
out.append(Q)

with open('out.tuo', 'w') as f:
f.write(str(out))</code></pre><pre><code>[(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)]</code></pre><h1>第一步：恢复曲线参数</h1>我们唯一已知的就是一系列点$Q_i$，也就是已知：$$
\begin{align}
y_0^2 &amp;\equiv x_0^3 + ax_0 + b &amp;\pmod{p} \\
y_1^2 &amp;\equiv x_1^3 + ax_1 + b &amp;\pmod{p} \\
y_2^2 &amp;\equiv x_2^3 + ax_2 + b &amp;\pmod{p} \\
&amp;\cdots
\end{align}
$$对一对点$(x_0,y_0),(x_1,y_1)$进行分析：$$
\begin{align}
y_0^2 &amp;\equiv x_0^3 + ax_0 + b &amp;\pmod{p}\\
y_1^2 &amp;\equiv x_1^3 + ax_1 + b &amp;\pmod{p} \\
\hline &amp; &amp; \text{subtract}\\
y_0^2 - y_1^2 &amp;\equiv x_0^3 - x_1^3 + a (x_0 - x_1) &amp;\pmod{p}\\
a (x_0 - x_1) &amp;\equiv (y_0^2 - y_1^2) -(x_0^3 - x_1^3) &amp;\pmod{p}\\
a&amp;\equiv [(y_0^2 - y_1^2) -(x_0^3 - x_1^3)] \cdot (x_0 - x_1)^{-1} &amp;\pmod{p}\\
\end{align}
$$如果$p$已知的话按上面的推导即可求出$a$。不过这里我们并不知道$p$，最后一步没法求逆元。所以另谋它法，先考虑消去$a$求$p$。加入另一对点的关系来消去$a$：$$
\begin{align}
(y_0^2 - y_1^2) -(x_0^3 - x_1^3)&amp;\equiv a (x_0 - x_1) &amp;\pmod{p}\\
(y_1^2 - y_2^2) -(x_1^3 - x_2^3)&amp;\equiv a (x_1 - x_2) &amp;\pmod{p}\\\\
\end{align}
$$$$
\begin{align}
[(y_0^2 - y_1^2) -(x_0^3 - x_1^3)](x_1-x_2)&amp;\equiv a (x_0 - x_1)(x_1-x_2) &amp;\pmod{p}\\
[(y_1^2 - y_2^2) -(x_1^3 - x_2^3)](x_0-x_1)&amp;\equiv a (x_0-x_1)(x_1 - x_2) &amp;\pmod{p}\\
\hline &amp; &amp; \text{subtract}\\
[(y_0^2 - y_1^2) -(x_0^3 - x_1^3)](x_1-x_2)-[(y_1^2 - y_2^2) -(x_1^3 - x_2^3)](x_0-x_1)&amp;\equiv 0 &amp;\pmod{p}
\end{align}
$$也就是说我们可以用3个点的坐标，来求出$p$的一个倍数。我们对已知的所有点$Q_i$求长度为3的全排列，结果取gcd：<pre><code class="lang-python">out = '[(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)]'
Qs = eval(out)

from itertools import permutations
kps = []
for triplet in permutations(Qs, int(3)):
 x0, y0 = triplet[0]
 x1, y1 = triplet[1]
 x2, y2 = triplet[2]
 kp = ((y0^2-y1^2)-(x0^3-x1^3))*(x1-x2) - ((y1^2-y2^2)-(x1^3-x2^3))*(x0-x1)
 kps.append(kp)
 
p = gcd(kps)
assert is_prime(p)
print(&quot;Found p:&quot;, p)
# Found p: 11093300438765357787693823122068501933326829181518693650897090781749379503427651954028543076247583697669597230934286751428880673539155279232304301123931419</code></pre>恢复$a,b$。此处变量名应该用EC（EllipticCurve）更合适，但遵照题目附件，仍用ECC。<pre><code class="lang-python">a = ((y0^2-y1^2)-(x0^3-x1^3)) * inverse_mod(x0-x1, p) % p
b = (y0^2 - x0^3 - a*x0) % p
ECC = EllipticCurve(GF(p), [a, b])
print(ECC)
# Elliptic Curve defined by y^2 = x^3 + 490963434153515882934487973185142842357175523008183292296815140698999054658777820556076794490414610737654365807063916602037816955706321036900113929329671*x + 7668542654793784988436499086739239442915170287346121645884096222948338279165302213440060079141960679678526016348025029558335977042712382611197995002316466 over Finite Field of size 11093300438765357787693823122068501933326829181518693650897090781749379503427651954028543076247583697669597230934286751428880673539155279232304301123931419</code></pre><h1>第二步：Smart's Attack</h1>直接把恢复出来的参数拿去搜索引擎一搜，发现好几道Smart Attack的题用的都是这个参数，可能是出题人没找到生成anomalous curve的方法，所以都抄来抄去233。经过一番探索，找到一个工具<a class="no-external-link" href="https://neuromancer.sk/page/ecgen" target="_blank">ecgen</a>可以用于生成曲线参数。扯远了，回到做题人视角。$Q_i$被表示为$$
Q_i=m_iR_i+n_iE_i+s_iC_i
$$设$R=rG,E=eG,C=cG$，则有$$
Q_i=(m_ir+n_ie+s_ic)G
$$这样只要求一步ECDLP，就拿到了一系列方程：$$
\textbf{h}=r\textbf{m}+e\textbf{n}+c\textbf{s}\pmod{p}
$$其中只有$\textbf{h}$和$p$已知。由于 <code>ECC.order() == p</code>，直接应用Smart's Attack求解ECDLP即可。<a class="no-external-link" href="[https://](https://github.com/jvdsn/crypto-attacks/blob/master/attacks/ecc/smart_attack.py" target="_blank">板子</a>)<h1>第三步：隐藏线性组合问题（HLCP）</h1>上面得到的式子实际上属于隐藏线性组合问题（Hidden Linear Combination Problem，HLCP），这个概念是在<a class="no-external-link" href="https://eprint.iacr.org/2021/1007.pdf" target="_blank">Provably Solving the Hidden Subset Sum Problem via Statistical Learning</a>中提出的，是对隐藏子集和问题（Hidden Subset Sum Problem，HSSP）的一般化，把随机向量的分量取值从$\{0,1\}$扩展到了$[0,B]\cap \mathbb{Z}$。<img src="/usr/uploads/2024/01/2834022817.png" alt="image.png" title="image.png" style="">直接对Nguyen-Stern算法进行扩展即可求解HLCP，不需要用文献中新提出的统计学习方法。具体分析可以阅读原文献。回到题目，分析几个向量的分量大小：<ul><li>$m_i$ : 504bit</li><li>$n_i$ : 128bit</li><li>$s_i$ : 256bit</li><li>$p$ : 1024bit</li></ul>这个$m_i$比较大，然而注意到$m_i$的低位是54个 <code>\x00</code>（即432bit），我们可以记$m_i$高位的72bit为$m_i'$，构成向量$\textbf{m}'$，记$r'=2^{432}\cdot r$，便得到了：$$
\textbf{h}=r'\textbf{m}'+e\textbf{n}+c\textbf{s}\pmod{p}
$$这样上界$B$就大大缩小。接下来我们来逐步实现Nguyen-Stern算法（本文就题论题，针对本题做了简化，更多细节可以参看<a class="no-external-link" href="https://eprint.iacr.org/2020/461.pdf" target="_blank">A Polynomial-Time Algorithm for Solving the Hidden Subset Sum Problem</a>及其提供的<a class="no-external-link" href="https://pastebin.com/ZFk1qjfP" target="_blank">实现</a>）<h2>Step 1：从$\textbf{h}$确定$\bar{\mathcal{L}_x}$（正交格攻击）</h2>首先构造$\mathcal{L}_0$的一个基$$
\mathcal{L}_0 = 
\left(\begin{array}{cccc}
p &amp; &amp; &amp; &amp; \\
-h_2\cdot h_1^{-1}[p] &amp; 1 &amp; &amp; \\
-h_3\cdot h_1^{-1}[p] &amp; &amp; 1\\
\vdots &amp; &amp; &amp; \ddots &amp; \\
-h_m\cdot h_1^{-1}[p] &amp; &amp; &amp; &amp; 1 \\
\end{array}\right)_{m \times m}
$$<pre><code class="lang-python"># We generate the lattice of vectors orthogonal to h modulo p
def orthoLattice(h, p):
 m = h.length()
 L0 = Matrix(ZZ, m, m)

for i in range(1, m):
        L0[i, i] = 1
    L0[1:m, 0] = -h[1:m] * inverse_mod(h[0], p)
    L0[0, 0] = p

for i in range(1, m):
        L0[i, 0] = mod(L0[i, 0], p)

return L0</code></pre>我们知道，给定一个格$\mathcal{L}$，使用LLL算法可以计算出$\mathcal{L}^\perp$的LLL-reduced基。这里在$\mathbb{Z}_p$下计算$\mathcal{L}_0^\perp$的LLL-reduced基。<pre><code class="lang-python">L0 = orthoLattice(h, p)
L0_perp = L0.LLL()</code></pre>取出$\mathcal{L}_0^\perp$的LLL-reduced基的前$m-n$个向量，恰好就是$\mathcal{L}_x^{\perp}$的一个生成集。<pre><code class="lang-python">Lx_perp = L0_perp[:m-n]</code></pre>最后在$\mathbb{Z}$下计算$\mathcal{L}_x^{\perp}$的一个右核空间$\bar{\mathcal{L}_x}={(\mathcal{L}_x^{\perp})}^\perp$：<pre><code class="lang-python">def kernelLLL(M):
 n=M.nrows()
 m=M.ncols()
 if m&lt;2*n: return M.right_kernel().matrix()
 K=2^(m//2)*M.height()
 
 MB=Matrix(ZZ,m+n,m)
 MB[:n]=K*M
 MB[n:]=identity_matrix(m)
 
 MB2=MB.T.LLL().T
 
 assert MB2[:n,:m-n]==0
 Ke=MB2[n:,:m-n].T
 
 return Ke
Lx_bar = kernelLLL(Lx_perp)</code></pre><code>kernelLLL()</code>实现的原理还有待进一步分析（还没很好地把握LLL在这里怎么work的，经过初步探索找到<a class="no-external-link" href="https://hal.science/hal-01921335/document" target="_blank">这篇paper</a>，有时间再读）。至此我们完成了第一步的任务。<h2>Step 2：从$\bar{\mathcal{L}_x}$恢复向量$\textbf{x}_i$，再恢复权重$\alpha_i$</h2>对于标准Nguyen-Stern算法，从$\bar{\mathcal{L}_x}$恢复$x_i$是通过计算BKZ-reduced基，并筛选符合条件的基。由于这个算法的复杂度是$n$的指数级别，所以$n$大一点的时候就需要采用<a class="no-external-link" href="https://eprint.iacr.org/2020/461.pdf" target="_blank">A Polynomial-Time Algorithm for Solving the Hidden Subset Sum Problem</a>里边改进的多项式时间算法。论文的实现是先做LLL，然后依次尝试BKZ-10、BKZ-20、BKZ-30。对于本题，n=3，仅用LLL算法即可求解，一发入魂！同时本题flag是嵌入在向量中的，无需进一步恢复权重。<pre><code class="lang-python"># Step 2
flag = bytes(m &amp; 0xFF for m in Lx_bar.LLL().list())
print(flag)</code></pre><h1>总结</h1>从仅有的一系列点坐标中竟然能恢复这么丰富的信息，Crypto真好玩.jpg本题完整exp如下：<a class="no-external-link" href="http://43.156.8.20/usr/uploads/2024/01/378560821.ipynb" target="_blank">solve.ipynb</a>。

[巅峰极客2023]Rosita题解

题目

第一步：恢复曲线参数

第二步：Smart's Attack

第三步：隐藏线性组合问题（HLCP）

Step 1：从$\textbf{h}$确定$\bar{\mathcal{L}_x}$（正交格攻击）

Step 2：从$\bar{\mathcal{L}_x}$恢复向量$\textbf{x}_i$，再恢复权重$\alpha_i$

总结

2 comments

Leave a Comment Cancel reply
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

[巅峰极客2023]Rosita题解

[IrisCTF2024]4个简单Crypto

[IrisCTF2024]manykey

[MapnaCTF2024]be_fast

[L3HCTF2024]can_you_guess_me

[L3HCTF2024]can_you_guess_me

[IrisCTF2024]4个简单Crypto

[巅峰极客2023]Rosita题解

[IrisCTF2024]manykey

[MapnaCTF2024]be_fast

[巅峰极客2023]Rosita题解

题目

第一步：恢复曲线参数

第二步：Smart's Attack

第三步：隐藏线性组合问题（HLCP）

Step 1：从$\textbf{h}$确定$\bar{\mathcal{L}_x}$（正交格攻击）

Step 2：从$\bar{\mathcal{L}_x}$恢复向量$\textbf{x}_i$，再恢复权重$\alpha_i$

总结

2 comments

Leave a Comment Cancel reply 使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

[巅峰极客2023]Rosita题解

Leave a Comment Cancel reply
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款