三顺七的笔记
0%

2023-JQCTF-Crypto-WP

发表于 更新于 分类于 Valine：

Pack:

题目：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
from Crypto.Util.number import *
import random
import os
FLAG = os.environ.get('FLAG', 'flag{XXXXFAKE_FLAGXXXX}')
assert FLAG[:5] == 'flag{' and FLAG[-1] == '}'
FLAG = FLAG[5:-1]

def pack(dim):
    sc = [-1, 1]
    a = [getPrime(256) for _ in range(dim-1)]
    s = [sc[random.randint(0, 1)] for _ in range(dim)]
    a.append(-s[-1]*sum(a[i]*s[i] for i in range(dim-1)))
    return a, s

def epack(error, dim):
    a, s_ = pack(dim)
    s = [i if i>0 else i+1 for i in s_]
    for _ in range(dim):
        s[_] ^= int(error[_])
    return a, sum(a[_]*s[_] for _ in range(dim))

if __name__ == "__main__":
    bits = bin(bytes_to_long(FLAG.encode()))[2:].zfill(len(FLAG)*8)
    for _ in range(2):
        print(epack(list(bits), len(bits)))
'''
([72596016824297326039370614840223966829493875863735465775262041696688112497553, 105145394038695953002583813160909610696267420771241826933119961752457682988383, 83658914208392780064232691507374638400049384179390200034414606841108622736117, 107030598803958805128598551819120306962530271429215965748462693229508654035701, 63150326678399826054512019522679275231861333279338026423872662901186176688419, 105521690887711112796251885817457347678273300487384002254187649276013375337659, 87319795044818162385547809431547159314383116594070144274240357247749788976981, 80953774246276599882312478763664213737224471640660071968048226581932522525783, 104720720977103956896781371565933496575548097350184428228277424867879185481993, 64888008985943523420633254524783796873061037262172382275693360508888498580189, 69789095666734332195748819409914040076935630638765623269495190483947710436677, 109168297066169596376071518628222504348015594738095730699376918857158972288103, 58093440391721118368204835559472667958963540126231052777452413678251213240429, 59839046246087569777640654726000154684478484149434780532122923446263204099979, 91792213218058331185742762605016400631607489819531201803774083864256441518851, 99312630227534321306675113390226243222790444525956628077098890402364180235101, 115487341043777700952931608026201677442773520881509441558948245664412062829893, 85262000110952311039142991698052387420584290881244088718838543860129773339647, 103810644423213057480726321867721449956700251023045430109403241693756304849709, 114069216300586669913396209331559581546551080031886399734225000177874746146977, 86137283973592422007213856604280377778882411909873773920572911551239660103429, 103599414639283917392806973166177527358575464125591946121298928578257610863189, 110464909612523015007137862683529770780510143318769312878974606163298635517171, 99520466820298265135037509557792842110780157327875344093458321328525267136603, 93761452118368973940514699218394428016758834076861227324053376856145826832523, 72298507366826809111573159043184286037486275285734769564994669403141519351761, 69941346261563709740995942570418425027076599587883275792923838232289043956527, 77628246049356222643756604750514334713059773551684231754798788746059818652033, 84176437815130849217947352327262320861384110799398904084417524854799920267749, 109614219554147566444452736685614279670785883144219361907620166381997476539197, 88447987800397946137057165542495541429810078859347058176798273886181571716467, 67300862572955835569732296763875683450467134725690083451837533985199476749573, 72366375264156034242322710095167325465872703575595176710687403092479249188639, 109539809261279723387064107493302754374872844842779755294307671691163271785399, 74406004545155010536541063937388510365857763857087557483777221737447580096681, 64268394629183557424911262543441056803310919160057842358809019060925897700779, 98669990017363780994862365433420661301917188671505703406000227708344456950239, 105924699325818993711350234513868328755125600764646635245647278188001906870523, 113878319115924329510762068764117093531721901409944554514897548786620608765479, 81904320530938258878252589945476056089090125405586608639857785386007154121011, 108333220881977025482063840041489756426928463541693923780737855561434902460721, 99311444461755727651625208315294339692449956168461880618351333201127783170241, 89193042233677445607128269729057405647958513136541235011353070917936224812361, 83072940172970512336994702281537100726523636526697864832714879905354268573421, 76108640468059458555333369044925091884914426570733964515776454785225896585229, 72929642339439715276210916967095297563286900575665126455571607537655922272761, 87685480931121280201867480837190906428491166018374773578092382233630648493673, 88737018606473437083253240616437123486813669763550775712620125835719466510507, 65302772643922286875718511133900959132785809720501426624452002101694613322267, 97000141473543900716944440330502954560614040700077240433141919638747144089037, 58058642146612055451968532107861750403038062828722457618771601960116905798617, 108331564571427502334243814226376491250261728741562437032163859968644752292347, 76647699092812486829834271215160724638194922371809146384175930005912043663769, 92354355564197310614468905169482120904868612877689706894547299917427557581431, 95082519556237975661107635932327800418386371308428403863511756097954465379037, 107489085366154814367214207203828432929899771186827212622375460299369733329523, 106619314959374205048893750268204454640991784037063500574822945099415972118949, 63851825269822379788473550870465926928582421449177926432168141267490960771981, 90951648181483760053955405953300762171870427405484219056320160382236446188317, 76873231850736196896906387831190521899120539607299319583342376930840920840733, 104742614379287273868971104027359670452615254047225213774378607157248789017883, 84549778911049021712390238487483948531082995175786526822454645289149172900627, 112577733900272823262360804831628422023142755259149104936101825246650136912157, 110482242865278717076688613605567298906016599918910743044490643339923228130021, 109190393964100765772463483479413308641481989424970537761678017691243321355417, 101339282590875769629498545550546026789118495746374109068736799750290086672369, 62556703532758300581263342465552912809743561174402690826566621336350198379017, 76904459848109976352606737011565674428546485324300268207462694425047175179877, 81357725993070389096136668871218295575136057273365229421982553661796346896993, 67387767396290347944658923787593985943038632492497343461335710833707116942073, 60441370368505270051328116212775633341557338861909817145952058685539065161931, 97378411177373381432869510428673710678006916113157713025680988489582141545097, 86462177426767570514083466045963803749162497387450792133744311347648764092531, 82586785474867470655275926807522435502624021968202020072373140902601018477237, 75714206241559882346819317143934410394234087820926519940365495368720016754587, 99428041509180448641963018539382484851740275040803163793696316834835273469817, 61719782640758552700641943313784015478660827830943126566071689509151050350499, 82619908871256569599961883605357477525260850553950498128086541209759225456007, 69339326637259882483686158663959840632916277593402188778534179417505846620371, 63501178230690931424465220248966452108894081509215273494273696145859980030687, 83273500769695918583238143299188557443665934533014300696010690450704149444933, 79671986980009098799687049565179722788618787280237507652202331933958593641789, 70974815413667267583175514515442682676322740364000987826163372731280924719827, 73143180633006337388398487503748410282706264434994890435835837576775372823067, 58170812869701196695833987901356578107497513597766999987228496665291711012397, 105534973675139211426430244900844139520862210561438962598711426456365443698959, 67410386667205264454175396614747504760446187110765226246532907435393313313111, 91537699637372932572189725720490136049810940459162823764476937508005961946221, 105348387443400641390893859865626293090907273991467324938186367401153886618149, 99255480874212723633889966290605323473850194346854142304760353920759745697281, 108544876763836088834822547696052274913515326479006004098752935442904146712991, 93076997675820364593222453480662954467460781476125245609079748879083459248541, 58558982326235359384232253016186406931472947281706247904362979989111056126019, 107298777968413318372565588058606590435699805137872499251985073634084051431589, 61535156531722556035095681357757246604859468275944414633811975045804878931227, 95016471173412632362663744156174093887967434380024447522907081517099899461233, 103024372929770131121743012996159065806349850704219123401195373460226435071843, 101694310316882688332544849289280992981945538456579830929961420775937985375703, 63538649601003720241287082537221000926756843015996057648918953011618643010243, 79694939248569940914117551616356646635434965608928924205665084574674230337013, 78533284464543393660311966021749240015776682024092542506094790773411365368199, 93900698909829287799869728734485319081765150457869090621339241411555706177663, 70169625486402221055737804293478688369542796940042370596718634544980887666963, 105831260744424364250242446303834359603177763311218787520338093955973224815813, 61054718888040126424644276627237520829209960991846304593116305650642457110461, 59526895543428084431880998344240659542067703640554464865288473249727653771557, 89286818078081758189589555116750491923904265518853737314104704460038316699513, 99338995703118201090625422267670228903027626265815888475596144455148184411093, 83426848571645085571592550405076673379919232688255873441005573462121451085597, 115387746546165347616627327930189003238140945333061540692943956879449219215187, 89893078002917142941973457390197991534839095377571965022889933088556880150457, 103234208405950182330208917744593078670707769254663805398625975284709323561581, 60309355443384988637228584745257242590442868644836341322281522872894886474793, 111137747302156603001840238208132576937582043721951502314759190776303608895051, 109269195871514253949095609989130667445972556961032275984314392355903136830901, 64385136507396251323661706592230248247511082418508259788945704588349144290257, 80913797294845319276947413828151836886286706629689647680338387240490409384991, 64424017415838131537499608323310979827483433118529509208758054942383837606281, 89123052313929623659865157486840204159849047719303802848593683464826371154221, 70876499124401751765953266144659983692632026739769563290258570552581046420723, 82400229733415244341322886454051260123192014039862429120000560520770728575963, 99376145681403994073989484897117016352708531055804857929032220347865208838501, 82143051134972058140917788019089204979887907218412083920927059686248853105239, 102895110795615838623267884193939989003621718191085572693332043670152476397123, 105556692584669760323371742315079037068494318717874002848570826542520515585177, 113028239995125576848550556779062554035146617130976774741146374166382505557791, 89424666662860204723969131032549141658476437774809976595361252008445689616527, -1887128825137006233312861916760907617424462061634354492375838616203237936451221], 4154703519412721925735340639704234534272945597867226307980013053053929101006010)
([76667738435239895094871596404419855909375460462274401338344349202493728860007, 94224419169775509137639708024167893549075980105814429893241591639470458680371, 93065230782200159338734176661894456885357447621333944460823033924596343750201, 97039264121819928119324738650806759604198601849925210336688310856965964556703, 80666507226208846348154667892897759938630313606354662221899686365055068485879, 76988446053431226728143881381258425769573323036410139936553460358779587998671, 80412041893688729757393240327962753465390035253690183478720723301311952016789, 90920631369420018699004271208065264998779818328196422026815618156791607337789, 69150657572252876908252782954853669231696755067025684535014059810382898746111, 66994460827109214248793411218871466378372643374794946814488677885375602736683, 94875431673808914811195320627265968536904836571464860778221380844554279653123, 103580302040057128440743260786261459342285137777912893543105830765699137850267, 96338217380428662809325297452317908205533742389442907800646247789485347886869, 112317194825305412229858133480615796337922920160998307753573468341962687098129, 72170084000761778966109740375734667659313472968723326042784462726427748160699, 112450972653411463130559826081584045068429448571138404747328052777055382408889, 76860953554631463611408108297050300878025680793564885725053002151137850732891, 99647857717533040125731134191336469899564684397890201393635262658555160261851, 79026996197896713917867295508625323373673362257045025021155883489652450496243, 71843673783728517215551287208021331773062367226494536781412929023852383203783, 102072795949315489243618497048697995224557677021448310775173267189646004725883, 101344983825110882501766876762708363887022277827998975823621091288960426886689, 101280989212086848265002810754250935520387204620021465312314756163614169957529, 83487043698379895556833072564569144970492716623512928205913078513853609429931, 76042746349621892667055854096698999956378733284750322692661188723501305398311, 103826703755729474416001844195349841446779304345354614625499339704257126387107, 112982099469468627546517534569522304912753524436951492659753690415377415990889, 70423727226032159678537984675203799321805587288387706032230783743382486256837, 115026053569610805469649555713735458865887580608854471674875458853993102576041, 95804622197829406477423755382397123412483501803456967153770204357578684284259, 77029613047702287892494346996651011353647464770841370786470638095474734339113, 96717681279002466523203494358608686274394654448371542115505049374623311809711, 65458512673545422940595579092761285378814138906197721153940390698162354700237, 103810786045681983488252678723090769190013666837695932846020079593627164879439, 64878989647401773817723255909686603400458164730737630727735466274698224365579, 62669190863258084768221883311348711818377954441109463198595654382271915364099, 62714287025389897322801566091349632198612457682178423966411871435140291671991, 104400127515691816155268432357044469523164304312808724436142002250765751557331, 101193934758482242945020937907964927616198621886489297415284366989078473664187, 66513470981695620191758939267465536396372772894160805885385944675602290376441, 64253862727943997976839743227250222521421491216492211015183359811596042793791, 77746614800529477861844917829666279682472252018274302284704998041640365990179, 79426204952031809486985732938578380393756599400192110084470375846227253958311, 97869474541745024020502790355109645342928867177537370028098017371897208226357, 115539686581730090747578683893323550741311219722714796478450916628510418056001, 75031067706155561408946703581739434384353821896569901489384694119054075129247, 106863816172655908128641934500689827898093652213271184893012170136663055494131, 84188512275156277484751971709108439558246927540810788386321098477978056927487, 83255671767240578404886444134509247333604116613349945049221799703469862177043, 65172202335207853984423622019063852459381611088754012136885871019234827440323, 97145588007249782552722588730661504995998948301924672923596117891922753913201, 112587268744786495199418394549595744556250022149548207179818697518299034079753, 80396373629259239273152022175043994367524668497740221070915708802061886909297, 85864044724567608238975828312961201072583800341785598507138481774836998085547, 87225858981527229643632044713429772971896540029470195252507239452794153448717, 101026174428753708810368458534923059124766007057999352199099334622236968005053, 72147407549554168083244287702378731415204658088218239317399061551770866973867, 110865024768222120856062388502292327687573974576009463947786643752429097989509, 60239023506310998548116794705078552286240366047014146782307571148458297589293, 108654302348384474601064962804784055410918758429572066719591058947852102630849, 112803300524341654574202783129280667973232452364549982528819754719278989544883, 73925494076444113866096878589621757231361407986169293028453910873177789864617, 82868466282766394894578054685788211837970435360088092526132304224884866963233, 67691517236614158435072168907612001986864806777662150952294674839601124128203, 67572389253800130549432172968950701186218232719691362720827622210338178877507, 67290387038104782794283094108487616312287705281864383977977422318694867255649, 90650887446579000496424947139297192874507476058763446707509689051869029362733, 97161676438897595595167005970351579864048599472215344538912815195347733419407, 114479205527549165178883914308586346929900010117107378091764216194589308200427, 88457092433781423642234121257945317500181363930571887120670865741632134999897, 95246655025839460839846075673298933155151547309794412818931714986478986791169, 86700061550359899441093284564514664537281977734449298835879024497486549182289, 58088578288947504632125877466049569833099276456997482087682090494781468472081, 79490622575380000672594047378335151091824550790881600452354133914709515463697, 64135144988838580348517544305202481745049232039843924814143506421312668019667, 83696119701180786375226564533862179062271107224305305141786161055045880471697, 101453778303665595472610549701497829911375504684339604968650295602462229892111, 114081353021324656305343761788743020312393328210236056159821536016993815106831, 57957821888624172908357967070416406703502624795464490782639826314883651887029, 61155446796043816751470061469444534255170180150630149674738910229269544311759, 66632400259876759578863918616179387997443449152645852265326281388652578163667, 88973388857973170725803193804499622895421134167706501633605475239215852524859, 110664031987216676701608801449996504989244199594519760840102046775227016821717, 101410882316395412140132863111963742415546086235201091798078833962076948434787, 68613705663191618080693948764946450760773074064858446879339835947756957327923, 112836649507907488937004726233475265487973637214175101684872332053128440211493, 88879249451085895426212817504097516259251987465333931438335908431157470377413, 87817512968670367131679502135014019208226757825780596346926785108004269160651, 66087734766644838384382395729255406342908431457271255171231192142831818687337, 68447713221559317640945049313087270820398721392517566936189030199566998917949, 99830132221000551076087604831937728815410539372041777063898918202491269145083, 89394161092471370632748875434242265181658707432318873844987961400760521994341, 114756013003762632531703713604852959551878362870705133314932235216896192422819, 107790963264147395694221708908864776196403632360074485948364226697675720673397, 90413919057404141106501671632022064471298825633091417024932488440563939485307, 69396973047568782955722225230443360827930030945279548025586475771182632675403, 82813098940704425609024485483571841783571281907726819476252795183164098715807, 73294853646579701061261033956817798719736291442817376020298267964534081119977, 95492202170442960016279599552330706055746428022472721665149518213792002336039, 80258569113776289436222772883818840959709435182463917174878076106276115002587, 106723710156161198772011014606446243705570875421533882203197975720136506449591, 75972152305157434925754409645276686433170040690361625716962091330687683023523, 97093823884815242682976389678674112225202909126475145388606000146199315093907, 94148709241928106998061782902470190801743374969892333570472211050469439905911, 105567249886048538493311206945245791170237605159622209331981769033103926098603, 82517530047587282396625086611314965874279217761819306752308434313533630519787, 60944665024725298671743446007496651520291359155182364662201362504536490866999, 97110782664077727955934636649541050870931874968606705966043610727627458466087, 86849439389775601095119433106783934959219159582791067121931943421074447653719, 99621740433569308104270219127087587849776650175199641279473325266244857466207, 75945811488671847486893841936987916347720790794258747426633984718204134897523, 82012919033096061480423356959577465392196714829869882675006103548899211623699, 75367122042924207790250712049474737744496813456842918339321668828822661643259, 73726498823044490484749141650258421831415911910985768466854115606985480745207, 62764972651938276404966718859458728625454464091218720244927301052993878545099, 88284250401687465012056068502407716251058467880057357760021748334448078040251, 101197300961367485202674487273228842675385694788739033593359862863277622433641, 91889676932716615596472140385137779537713516675645133470518033106836832245023, 104787691198121773847803917937325665295362746668614867417731743169052697965523, 103033036012066031042105866887946171266989777000400028792907749101521943056413, 106835134111309807281509158967880945929152501100644730059192338146154885212039, 85548842267721815195883037791197535018145267191197806766174633766228710207249, 108571501214360432711517161995794799228207786445990904587963366001746857456369, 76275581804134364061606140057524440005933127488997321898949581492263950360233, 74673506423909591622367981956227394193429315477834559698031755216382906357063, 69120979287513127042096895700811544233228356243864724579108083086837448243907, 89036891915393412196207159437996087610506662961731523754745678934304964414233, -449125597304489491002788040081208646968442708796151991203578196099202279718073], 5256112472331167908894486688120087849589928922924868527122389889471942039497562)

'''

hint: LLL后剔除多余的向量，再用BKZ会得到更好的基

分析&解题：

提供了一份质数列表：a

将flag的bit作为error与secret_bits进行异或

设异或后的比特表为out_bits

输出a与s的向量内积：

a_{1}s_1+a_2s_{2}+…+a_{n}*s_{n}=output

大概就是这样，思路也是及其简单的：

一眼就知道这个就是背包问题，但是难在哪里呢？——维度太高了。

常规的背包格构造是这样的：

[s_1,s_2,s_3,s_4,…,s_n,1]\left[ \begin{matrix} 2 & 0 & 0 & 0 & M_1 \ 0 & 2 & 0 & 0 & M_2 \: & : & : & : & :\0 & 0 & 0 & 2 & M_n\1 & 1 & 1 & 1 & sum \end{matrix} \right] \=[2s_1-1,2s_2-1,2s_3-1,2s_4-1,…,2s_n-1,0]

我们想要得到的规约后的结果就是下面的向量，其中因为s属于{0,1}，所以我们得到的结果理论上是由1与-1构成的。

按理来说，我们在赛题里面规约后得到的东西都应该是能出的来的（只要会造格子就完了），但是背包格不太一样，当维度上去之后光是LLL得到的基的性质(长得不好看)就是不太行了。

那么我就按照题目的要求去利用LLL后再利用BKZ规约：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#part1:
T=([72596016824297326039370614840223966829493875863735465775262041696688112497553, 105145394038695953002583813160909610696267420771241826933119961752457682988383, 83658914208392780064232691507374638400049384179390200034414606841108622736117, 107030598803958805128598551819120306962530271429215965748462693229508654035701, 63150326678399826054512019522679275231861333279338026423872662901186176688419, 105521690887711112796251885817457347678273300487384002254187649276013375337659, 87319795044818162385547809431547159314383116594070144274240357247749788976981, 80953774246276599882312478763664213737224471640660071968048226581932522525783, 104720720977103956896781371565933496575548097350184428228277424867879185481993, 64888008985943523420633254524783796873061037262172382275693360508888498580189, 69789095666734332195748819409914040076935630638765623269495190483947710436677, 109168297066169596376071518628222504348015594738095730699376918857158972288103, 58093440391721118368204835559472667958963540126231052777452413678251213240429, 59839046246087569777640654726000154684478484149434780532122923446263204099979, 91792213218058331185742762605016400631607489819531201803774083864256441518851, 99312630227534321306675113390226243222790444525956628077098890402364180235101, 115487341043777700952931608026201677442773520881509441558948245664412062829893, 85262000110952311039142991698052387420584290881244088718838543860129773339647, 103810644423213057480726321867721449956700251023045430109403241693756304849709, 114069216300586669913396209331559581546551080031886399734225000177874746146977, 86137283973592422007213856604280377778882411909873773920572911551239660103429, 103599414639283917392806973166177527358575464125591946121298928578257610863189, 110464909612523015007137862683529770780510143318769312878974606163298635517171, 99520466820298265135037509557792842110780157327875344093458321328525267136603, 93761452118368973940514699218394428016758834076861227324053376856145826832523, 72298507366826809111573159043184286037486275285734769564994669403141519351761, 69941346261563709740995942570418425027076599587883275792923838232289043956527, 77628246049356222643756604750514334713059773551684231754798788746059818652033, 84176437815130849217947352327262320861384110799398904084417524854799920267749, 109614219554147566444452736685614279670785883144219361907620166381997476539197, 88447987800397946137057165542495541429810078859347058176798273886181571716467, 67300862572955835569732296763875683450467134725690083451837533985199476749573, 72366375264156034242322710095167325465872703575595176710687403092479249188639, 109539809261279723387064107493302754374872844842779755294307671691163271785399, 74406004545155010536541063937388510365857763857087557483777221737447580096681, 64268394629183557424911262543441056803310919160057842358809019060925897700779, 98669990017363780994862365433420661301917188671505703406000227708344456950239, 105924699325818993711350234513868328755125600764646635245647278188001906870523, 113878319115924329510762068764117093531721901409944554514897548786620608765479, 81904320530938258878252589945476056089090125405586608639857785386007154121011, 108333220881977025482063840041489756426928463541693923780737855561434902460721, 99311444461755727651625208315294339692449956168461880618351333201127783170241, 89193042233677445607128269729057405647958513136541235011353070917936224812361, 83072940172970512336994702281537100726523636526697864832714879905354268573421, 76108640468059458555333369044925091884914426570733964515776454785225896585229, 72929642339439715276210916967095297563286900575665126455571607537655922272761, 87685480931121280201867480837190906428491166018374773578092382233630648493673, 88737018606473437083253240616437123486813669763550775712620125835719466510507, 65302772643922286875718511133900959132785809720501426624452002101694613322267, 97000141473543900716944440330502954560614040700077240433141919638747144089037, 58058642146612055451968532107861750403038062828722457618771601960116905798617, 108331564571427502334243814226376491250261728741562437032163859968644752292347, 76647699092812486829834271215160724638194922371809146384175930005912043663769, 92354355564197310614468905169482120904868612877689706894547299917427557581431, 95082519556237975661107635932327800418386371308428403863511756097954465379037, 107489085366154814367214207203828432929899771186827212622375460299369733329523, 106619314959374205048893750268204454640991784037063500574822945099415972118949, 63851825269822379788473550870465926928582421449177926432168141267490960771981, 90951648181483760053955405953300762171870427405484219056320160382236446188317, 76873231850736196896906387831190521899120539607299319583342376930840920840733, 104742614379287273868971104027359670452615254047225213774378607157248789017883, 84549778911049021712390238487483948531082995175786526822454645289149172900627, 112577733900272823262360804831628422023142755259149104936101825246650136912157, 110482242865278717076688613605567298906016599918910743044490643339923228130021, 109190393964100765772463483479413308641481989424970537761678017691243321355417, 101339282590875769629498545550546026789118495746374109068736799750290086672369, 62556703532758300581263342465552912809743561174402690826566621336350198379017, 76904459848109976352606737011565674428546485324300268207462694425047175179877, 81357725993070389096136668871218295575136057273365229421982553661796346896993, 67387767396290347944658923787593985943038632492497343461335710833707116942073, 60441370368505270051328116212775633341557338861909817145952058685539065161931, 97378411177373381432869510428673710678006916113157713025680988489582141545097, 86462177426767570514083466045963803749162497387450792133744311347648764092531, 82586785474867470655275926807522435502624021968202020072373140902601018477237, 75714206241559882346819317143934410394234087820926519940365495368720016754587, 99428041509180448641963018539382484851740275040803163793696316834835273469817, 61719782640758552700641943313784015478660827830943126566071689509151050350499, 82619908871256569599961883605357477525260850553950498128086541209759225456007, 69339326637259882483686158663959840632916277593402188778534179417505846620371, 63501178230690931424465220248966452108894081509215273494273696145859980030687, 83273500769695918583238143299188557443665934533014300696010690450704149444933, 79671986980009098799687049565179722788618787280237507652202331933958593641789, 70974815413667267583175514515442682676322740364000987826163372731280924719827, 73143180633006337388398487503748410282706264434994890435835837576775372823067, 58170812869701196695833987901356578107497513597766999987228496665291711012397, 105534973675139211426430244900844139520862210561438962598711426456365443698959, 67410386667205264454175396614747504760446187110765226246532907435393313313111, 91537699637372932572189725720490136049810940459162823764476937508005961946221, 105348387443400641390893859865626293090907273991467324938186367401153886618149, 99255480874212723633889966290605323473850194346854142304760353920759745697281, 108544876763836088834822547696052274913515326479006004098752935442904146712991, 93076997675820364593222453480662954467460781476125245609079748879083459248541, 58558982326235359384232253016186406931472947281706247904362979989111056126019, 107298777968413318372565588058606590435699805137872499251985073634084051431589, 61535156531722556035095681357757246604859468275944414633811975045804878931227, 95016471173412632362663744156174093887967434380024447522907081517099899461233, 103024372929770131121743012996159065806349850704219123401195373460226435071843, 101694310316882688332544849289280992981945538456579830929961420775937985375703, 63538649601003720241287082537221000926756843015996057648918953011618643010243, 79694939248569940914117551616356646635434965608928924205665084574674230337013, 78533284464543393660311966021749240015776682024092542506094790773411365368199, 93900698909829287799869728734485319081765150457869090621339241411555706177663, 70169625486402221055737804293478688369542796940042370596718634544980887666963, 105831260744424364250242446303834359603177763311218787520338093955973224815813, 61054718888040126424644276627237520829209960991846304593116305650642457110461, 59526895543428084431880998344240659542067703640554464865288473249727653771557, 89286818078081758189589555116750491923904265518853737314104704460038316699513, 99338995703118201090625422267670228903027626265815888475596144455148184411093, 83426848571645085571592550405076673379919232688255873441005573462121451085597, 115387746546165347616627327930189003238140945333061540692943956879449219215187, 89893078002917142941973457390197991534839095377571965022889933088556880150457, 103234208405950182330208917744593078670707769254663805398625975284709323561581, 60309355443384988637228584745257242590442868644836341322281522872894886474793, 111137747302156603001840238208132576937582043721951502314759190776303608895051, 109269195871514253949095609989130667445972556961032275984314392355903136830901, 64385136507396251323661706592230248247511082418508259788945704588349144290257, 80913797294845319276947413828151836886286706629689647680338387240490409384991, 64424017415838131537499608323310979827483433118529509208758054942383837606281, 89123052313929623659865157486840204159849047719303802848593683464826371154221, 70876499124401751765953266144659983692632026739769563290258570552581046420723, 82400229733415244341322886454051260123192014039862429120000560520770728575963, 99376145681403994073989484897117016352708531055804857929032220347865208838501, 82143051134972058140917788019089204979887907218412083920927059686248853105239, 102895110795615838623267884193939989003621718191085572693332043670152476397123, 105556692584669760323371742315079037068494318717874002848570826542520515585177, 113028239995125576848550556779062554035146617130976774741146374166382505557791, 89424666662860204723969131032549141658476437774809976595361252008445689616527, -1887128825137006233312861916760907617424462061634354492375838616203237936451221], 4154703519412721925735340639704234534272945597867226307980013053053929101006010)


tmp = [[0 for _ in range(len(a)+1)] for i in range(len(a))]

for i in range(len(a)):
    tmp[i][-1]= a[i]
    tmp[i][i] = 2
last = [1 for i in range(len(a)+1)]
last[-1] = sum_
A = tmp+[last]
A = Matrix(ZZ,A)

TEST = (A.LLL())
print(TEST[0])
print(TEST[:].BKZ(block_size=26)[0])
#(-30, -8, 12, -12, -2, -10, 8, 4, -2, -4, -18, -2, -14, -2, 26, 2, -18, 0, -2, 12, 8, 16, -12, 30, -10, -4, 16, 10, -6, -10, -22, -28, -24, 18, -6, 16, 6, -14, 4, 0, -18, -4, 28, 4, -10, 8, -14, -4, 4, 2, 16, 12, 10, 8, 4, -6, 6, -2, 12, 4, 4, 6, 0, -4, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 3)
#(-1, 1, -1, 1, 1, 1, 1, 1, 1, 1, 1, -1, -1, -1, 1, -1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, -1, -1, 1, 1, -1, 1, -1, 1, 1, 1, 1, 1, -1, 1, -1, -1, 1, 1, -1, 1, -1, 1, -1, -1, 1, 1, 1, 1, 1, 1, -1, 1, -1, -1, -1, 1, 1, -1, 1, 1, -1, 1, 1, 1, -1, -1, 1, -1, -1, 1, -1, -1, -1, -1, -1, 1, 1, -1, 1, 1, 1, -1, 1, -1, -1, 1, 1, 1, 1, -1, -1, -1, -1, -1, 1, 1, 1, 1, 1, 1, 1, -1, -1, -1, -1, -1, -1, 1, -1, 1, -1, 1, 1, -1, 1, 1, 1, 1, 1, 0)

得到的结果确实也对，确实也美丽。

赛场上懒得去算BKZ_blocksize多少合适了，随着这个size越高，时间越长，但是得到的基的性质就越良好，越接近于最短向量(我们想要规约的结果)。

蛋疼的是到了26之后一次规约就要10分钟左右，第一组出来之后，我还在想这样卡时间的题不至于没人拿一血吧，哈哈还真是。

得到s向量之后(与error发生关系后的结果)，我们很自然的就想利用同一个关系去规约出s_，求出error向量对吧，那么稍微改变一下脚本的参数:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
T=([76667738435239895094871596404419855909375460462274401338344349202493728860007, 94224419169775509137639708024167893549075980105814429893241591639470458680371, 93065230782200159338734176661894456885357447621333944460823033924596343750201, 97039264121819928119324738650806759604198601849925210336688310856965964556703, 80666507226208846348154667892897759938630313606354662221899686365055068485879, 76988446053431226728143881381258425769573323036410139936553460358779587998671, 80412041893688729757393240327962753465390035253690183478720723301311952016789, 90920631369420018699004271208065264998779818328196422026815618156791607337789, 69150657572252876908252782954853669231696755067025684535014059810382898746111, 66994460827109214248793411218871466378372643374794946814488677885375602736683, 94875431673808914811195320627265968536904836571464860778221380844554279653123, 103580302040057128440743260786261459342285137777912893543105830765699137850267, 96338217380428662809325297452317908205533742389442907800646247789485347886869, 112317194825305412229858133480615796337922920160998307753573468341962687098129, 72170084000761778966109740375734667659313472968723326042784462726427748160699, 112450972653411463130559826081584045068429448571138404747328052777055382408889, 76860953554631463611408108297050300878025680793564885725053002151137850732891, 99647857717533040125731134191336469899564684397890201393635262658555160261851, 79026996197896713917867295508625323373673362257045025021155883489652450496243, 71843673783728517215551287208021331773062367226494536781412929023852383203783, 102072795949315489243618497048697995224557677021448310775173267189646004725883, 101344983825110882501766876762708363887022277827998975823621091288960426886689, 101280989212086848265002810754250935520387204620021465312314756163614169957529, 83487043698379895556833072564569144970492716623512928205913078513853609429931, 76042746349621892667055854096698999956378733284750322692661188723501305398311, 103826703755729474416001844195349841446779304345354614625499339704257126387107, 112982099469468627546517534569522304912753524436951492659753690415377415990889, 70423727226032159678537984675203799321805587288387706032230783743382486256837, 115026053569610805469649555713735458865887580608854471674875458853993102576041, 95804622197829406477423755382397123412483501803456967153770204357578684284259, 77029613047702287892494346996651011353647464770841370786470638095474734339113, 96717681279002466523203494358608686274394654448371542115505049374623311809711, 65458512673545422940595579092761285378814138906197721153940390698162354700237, 103810786045681983488252678723090769190013666837695932846020079593627164879439, 64878989647401773817723255909686603400458164730737630727735466274698224365579, 62669190863258084768221883311348711818377954441109463198595654382271915364099, 62714287025389897322801566091349632198612457682178423966411871435140291671991, 104400127515691816155268432357044469523164304312808724436142002250765751557331, 101193934758482242945020937907964927616198621886489297415284366989078473664187, 66513470981695620191758939267465536396372772894160805885385944675602290376441, 64253862727943997976839743227250222521421491216492211015183359811596042793791, 77746614800529477861844917829666279682472252018274302284704998041640365990179, 79426204952031809486985732938578380393756599400192110084470375846227253958311, 97869474541745024020502790355109645342928867177537370028098017371897208226357, 115539686581730090747578683893323550741311219722714796478450916628510418056001, 75031067706155561408946703581739434384353821896569901489384694119054075129247, 106863816172655908128641934500689827898093652213271184893012170136663055494131, 84188512275156277484751971709108439558246927540810788386321098477978056927487, 83255671767240578404886444134509247333604116613349945049221799703469862177043, 65172202335207853984423622019063852459381611088754012136885871019234827440323, 97145588007249782552722588730661504995998948301924672923596117891922753913201, 112587268744786495199418394549595744556250022149548207179818697518299034079753, 80396373629259239273152022175043994367524668497740221070915708802061886909297, 85864044724567608238975828312961201072583800341785598507138481774836998085547, 87225858981527229643632044713429772971896540029470195252507239452794153448717, 101026174428753708810368458534923059124766007057999352199099334622236968005053, 72147407549554168083244287702378731415204658088218239317399061551770866973867, 110865024768222120856062388502292327687573974576009463947786643752429097989509, 60239023506310998548116794705078552286240366047014146782307571148458297589293, 108654302348384474601064962804784055410918758429572066719591058947852102630849, 112803300524341654574202783129280667973232452364549982528819754719278989544883, 73925494076444113866096878589621757231361407986169293028453910873177789864617, 82868466282766394894578054685788211837970435360088092526132304224884866963233, 67691517236614158435072168907612001986864806777662150952294674839601124128203, 67572389253800130549432172968950701186218232719691362720827622210338178877507, 67290387038104782794283094108487616312287705281864383977977422318694867255649, 90650887446579000496424947139297192874507476058763446707509689051869029362733, 97161676438897595595167005970351579864048599472215344538912815195347733419407, 114479205527549165178883914308586346929900010117107378091764216194589308200427, 88457092433781423642234121257945317500181363930571887120670865741632134999897, 95246655025839460839846075673298933155151547309794412818931714986478986791169, 86700061550359899441093284564514664537281977734449298835879024497486549182289, 58088578288947504632125877466049569833099276456997482087682090494781468472081, 79490622575380000672594047378335151091824550790881600452354133914709515463697, 64135144988838580348517544305202481745049232039843924814143506421312668019667, 83696119701180786375226564533862179062271107224305305141786161055045880471697, 101453778303665595472610549701497829911375504684339604968650295602462229892111, 114081353021324656305343761788743020312393328210236056159821536016993815106831, 57957821888624172908357967070416406703502624795464490782639826314883651887029, 61155446796043816751470061469444534255170180150630149674738910229269544311759, 66632400259876759578863918616179387997443449152645852265326281388652578163667, 88973388857973170725803193804499622895421134167706501633605475239215852524859, 110664031987216676701608801449996504989244199594519760840102046775227016821717, 101410882316395412140132863111963742415546086235201091798078833962076948434787, 68613705663191618080693948764946450760773074064858446879339835947756957327923, 112836649507907488937004726233475265487973637214175101684872332053128440211493, 88879249451085895426212817504097516259251987465333931438335908431157470377413, 87817512968670367131679502135014019208226757825780596346926785108004269160651, 66087734766644838384382395729255406342908431457271255171231192142831818687337, 68447713221559317640945049313087270820398721392517566936189030199566998917949, 99830132221000551076087604831937728815410539372041777063898918202491269145083, 89394161092471370632748875434242265181658707432318873844987961400760521994341, 114756013003762632531703713604852959551878362870705133314932235216896192422819, 107790963264147395694221708908864776196403632360074485948364226697675720673397, 90413919057404141106501671632022064471298825633091417024932488440563939485307, 69396973047568782955722225230443360827930030945279548025586475771182632675403, 82813098940704425609024485483571841783571281907726819476252795183164098715807, 73294853646579701061261033956817798719736291442817376020298267964534081119977, 95492202170442960016279599552330706055746428022472721665149518213792002336039, 80258569113776289436222772883818840959709435182463917174878076106276115002587, 106723710156161198772011014606446243705570875421533882203197975720136506449591, 75972152305157434925754409645276686433170040690361625716962091330687683023523, 97093823884815242682976389678674112225202909126475145388606000146199315093907, 94148709241928106998061782902470190801743374969892333570472211050469439905911, 105567249886048538493311206945245791170237605159622209331981769033103926098603, 82517530047587282396625086611314965874279217761819306752308434313533630519787, 60944665024725298671743446007496651520291359155182364662201362504536490866999, 97110782664077727955934636649541050870931874968606705966043610727627458466087, 86849439389775601095119433106783934959219159582791067121931943421074447653719, 99621740433569308104270219127087587849776650175199641279473325266244857466207, 75945811488671847486893841936987916347720790794258747426633984718204134897523, 82012919033096061480423356959577465392196714829869882675006103548899211623699, 75367122042924207790250712049474737744496813456842918339321668828822661643259, 73726498823044490484749141650258421831415911910985768466854115606985480745207, 62764972651938276404966718859458728625454464091218720244927301052993878545099, 88284250401687465012056068502407716251058467880057357760021748334448078040251, 101197300961367485202674487273228842675385694788739033593359862863277622433641, 91889676932716615596472140385137779537713516675645133470518033106836832245023, 104787691198121773847803917937325665295362746668614867417731743169052697965523, 103033036012066031042105866887946171266989777000400028792907749101521943056413, 106835134111309807281509158967880945929152501100644730059192338146154885212039, 85548842267721815195883037791197535018145267191197806766174633766228710207249, 108571501214360432711517161995794799228207786445990904587963366001746857456369, 76275581804134364061606140057524440005933127488997321898949581492263950360233, 74673506423909591622367981956227394193429315477834559698031755216382906357063, 69120979287513127042096895700811544233228356243864724579108083086837448243907, 89036891915393412196207159437996087610506662961731523754745678934304964414233, -449125597304489491002788040081208646968442708796151991203578196099202279718073], 5256112472331167908894486688120087849589928922924868527122389889471942039497562)


a = T[0]
a_sum = -a[-1]#sum([i for i in a[:-1]])+a[-1]

tmp = [[0 for _ in range(len(a))] for i in range(len(a)-1)]
for i in range(len(a)-1):
    tmp[i][-1]= a[i]
    tmp[i][i] = 2
last = [1 for i in range(len(a))]
last[-1] = a_sum
A = tmp+[last]
A = Matrix(ZZ,A)

test = A.LLL()
print(test[0])

test = test.BKZ(block_size=30)

print(test[0])

这时候就出事了，规约一次起码一两小时都有可能，而且不一定对，赛场期间因为 跑错数据，调错参数，没造好格子，搞了半天汗流浃背的，心态炸了，结果到最后都没敢去跑这个脚本，但是出题人又说预期解就是这样卡时间的，，，

就是这样吧，总之……

Br0kenAuth:

题目:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
from hashlib import sha256
from base64 import b64encode as b64e, b64decode as b64d
from secret import n
import os
FLAG = os.environ.get('FLAG', 'flag{XXXXFAKE_FLAGXXXX}')

class HECDSA:
    def __init__(self, q):
        self.q = q
        self.sk = randint(0, self.q) #相当于私钥
        self.G, self.J = self.curve_init()

        assert self.q*self.G == self.J.an_element()
        
        self.P = self.sk*self.G #公钥
        self.fault_mod = self.q^^1 #错误模的最低位不太一样，说明这个模数是可以分解的

    def curve_init(self):
        f = x^7+x^5+x+1
        sy = f(F.fetch_int(31337)).nth_root(2)
        HC = HyperellipticCurve(f, 0)
        J = HC.jacobian()(F)
        return J(HC(F.fetch_int(31337), sy)), J #给了基点和曲线
    
    def encode(self, c): #把参数，化成点
        x, y = c
        px = PR(list(map(F.from_integer, x)))
        py = PR(list(map(F.from_integer, y)))
        return self.J((px, py))
    
    def decode(self, c): #decode得到一个点
        x, y = c
        x = [i.to_integer() for i in x]
        y = [i.to_integer() for i in y]
        return x, y

    def fault_sign(self, msg):
        e = int(sha256(msg.encode()).hexdigest(), 16)
        k = randint(0, self.q)
        r = k*self.G
        r_ = int(sha256(str(r).encode()).hexdigest(), 16)%self.fault_mod
        s = inverse_mod(k, self.fault_mod)*(e+r_*self.sk)%self.fault_mod
        return (*self.decode(r), s)

    def verify(self, msg, sig):
        rx, ry, s = sig
        s = int(s)
        r = self.encode((rx, ry))
        r_ = int(sha256(str(r).encode()).hexdigest(), 16)%self.q
        e = int(sha256(msg.encode()).hexdigest(), 16)
        if s*r == e*self.G+r_*self.P:
            return True
        return False
    
def menu():
    MENU = """
            /----------------------------\\
            |          options           |
            | [G]enrate Token            |
            | [L]ogin                    |
            \\----------------------------/
            """
    print(MENU)
    
def print_token(sig):
    token = "Your Token: "
    for i in sig:
        token += '#'
        token += b64e(str(i).encode()).decode()
    print(token)
    
def input_token(token):
    token = token.split('#')[1:]
    sig = []
    for obj in token[:-1]:
        sig.append(b64d(obj).decode().strip('[]').split(','))
    sig.append(b64d(token[-1]).decode())
    return sig
        
def Auth():
    menu()
    while True:
        op = input("choice > ").strip()
        if op == 'G':
            username = input("Name: ").strip('')
            if username == "admin":
                print("No can do...")
            else:
                while True:
                    try:
                        signature = signer.fault_sign(username)
                        print_token(signature)
                        break
                    except:
                        continue
        elif op == 'L':
            username = input("Name: ").strip()
            token = input("Token: ").strip()
            if signer.verify(username, input_token(token)):
                if username == "admin":
                    print(f"Hi, admin. Your flag here {FLAG}!")
                else:
                    print(f"Hi, {username}")
            else:
                print("Wrong Token!")


if __name__ == "__main__":
    try:
        F = GF(3^71)
        PR.<x> = PolynomialRing(F)
        signer = HECDSA(n)
        Auth()
    except:
        print("error!")

分析：

一眼下去ECDSA，再去看k大小(0,p)，这题在之前0xGame就有搞过，就是想办法去构造HNP的解法就弄出来了——但是真的有那么简单吗……看完题目我只想感慨，还得是多读书才好啊。

回到题目本身：

  • 题目本身的曲线是HyperellipticCurve，点的表示形式都用的Jacobian矩阵来表示。
  • 上面说的东西我个人也不是很懂，毕竟数学水平一般，但是有几个东西还是明确知道的，这个曲线想要用的就是多项式来表达曲线上的点，这个曲线是在GF(3^71)上的阿贝尔群，随便抄抄题目输出看看就知道，其实就是基点从数字变成了多项式，问题不是很大也能处理的。而且签名的时候也不是直接使用点去签，而是经过了一定的编码。
  • 说回这个DSA签名，题目是在fault_mod上签名的，我们也无法去通过题目的环境直接验签，那么第一个思路就自然而然地来了：
  • 求出原来的模数q

求出原来的模数q就完了，这道题就是那么简单。

简单地源审之后发现： assert self.q*self.G == self.J.an_element()

这个是一句提示也是一个关键点，G点和J的表达都是已知的，但是怎么求q呢……只恨自己读书太少，这个曲线相关的东西都没学过，也就止步于此了。

总结：

  • 全部密码题一共三道，全场只有两个解，有一个解还用的是他们课题组那边的黑科技(外挂)，全体密码手都来坐牢咯。不过这个问题也不大，这次线下能和其他地方的师傅见见，了解行业前沿还是挺好的。
  • 这次确实思路都有，但是切不进题目的入手点，上手的门槛太高了，还得多读书多看书。
  • 题目出的挺好，就是蛮搞人心态的。