糖醋小鸡块的blog
0%

Crypto趣题-Lattice

发表于 更新于 分类于 Valine：

该文章主要记录一些格相关的趣题

转化AGCD

题目来源：暂不明确

题目：

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
from Crypto.Util.number import *
from random import randint
from secret import flag

nbits = 512
delta = .93
kbits = int(nbits*delta) >> 1
bound = 2**kbits

m = 53
p = getPrime(nbits)
x = randint(2, p - 1)
a = [randint(2, bound) for i in range(m)]
b = [inverse(a[i] * x + randint(2, bound), p) for i in range(m)]
print(f"{a = }\n{b = }")

e = 0x10001
n = p * getPrime(nbits)
c = pow(bytes_to_long(flag), e, n)
print(f"{e = }\n{n = }\n{c = }")
'''
a = [226623173423524660762660587272926713775967113908071780918074044654746571, 99264763681859867816401881797921542580399607408617989905539839585323915, 177386736426181055874933306917112626356703658087900095566603898769091471, 5081587307910189127020749833744000992860852972311811125838243285877024, 411574110749659943703486080205654180795533263258790540505729307655142415, 1932137082695732276757073197845160804183868657578020568122170798605640, 103124563846054461729937757543103647655652920105466714505493351091607258, 65504504807895104765113845019342631211794998326986693051403166347389343, 151981136459515488882551190881724794060443302721456924436833810784219984, 3718222682937746804225225548712093487815785751144078132168082568580360, 113510621144631490440930342566441462111997352193075435129065142534001691, 120974784665251812036673794948678799274628176126865320042025545119228958, 193781634902416477262894357163294897773986019836290716577623654684669134, 24723078645443091017196603549741156206848230267873373213787667300835247, 113165730428784680251415263617027036564335843097634063978942541861726366, 407969345567975756778713582637075079783087682011802438819519567067241979, 151997755976755754648644424339697978791639952976423703068460739754839735, 253811682402531882908516509348937060650658679039884817907013090700281326, 404019046883201096048575369492824679211148242588135515488831100750933, 216725815105749574244056185735609680710954976727370948136589694286539150, 131605791470353972911656132280131756304373156215254629027113994962767833, 180190835657942894146705472335255090682179032409197893415067330574923084, 280086867488286721744184104208965143004904898002959657537412170401510680, 141039650035922882497777354937772530276454847300329950111476878397654053, 319858542602843767926919031049756704694256249776295683733693049522108872, 135633729043152514436339515687850041275739968837263316059461122379487161, 5038078437655552457504448170918674775639811066221990939957937239270167, 31918623105281221407484700216805581554894830335850729735403857505547002, 424092292941284354705774693468403308534554297314522980647422106907791591, 300635399575681097924575337707842439619576566621368558814406755486658723, 323686536134235835297820679361020300261642147835330856978902402517820801, 392620731408972775834827063986182511057173023783228673505487358356342114, 108681888409433100038410892044516773350200560613740266422720530715166828, 182338238967593331173372924666322484559869636981878410128856193538847678, 242630103099393630296862580986126439159331512930513337684897019399319621, 439737851682655515589311041364295341910822514202794661846391952824593066, 84115222835816390632388766236883091861894245716624041418721833768917547, 83926810016448863267608537461154878096011055852547156452557576634691363, 354588657997053098464002945990025178880458974438409486331146607111950617, 170413334241108032297843362994773587930354677207616527135896108692092457, 283185550452196010949673962093382632839937948488235076418296451706429923, 390000015988537819093964185756696910433784324036454283227484980367608884, 121370082693927496814267201484843687844578996855559797026014779421645731, 357164702199289826402900456464935203585119719343409406742172822868770420, 124276883926433089715798954125363260298740714164810098876501303684201565, 122912426324401068572433533096099229494021528981601203447594706478943744, 287527827124819650763642012585104162743364640051014410357971387706781531, 135819408760576908301747047938951002691288880199213610653148681326046091, 239644892459756283997004399339163555215985564639569406081575642996080481, 241513055132921096791997556818670497379598444881679976542299970876463098, 144152466563589166040797814966860917437020789050031353309848917297959088, 120162009732086541189519736083838746833770360960800721525565383293404918, 121547756201941339094205049920057111793191461762212554355070565584802804]
b = [6914108949558554967947157128371931777410399406424987472871265954007536210016000226325059466226417032321637768264366355381358552354005990800271210820573485, 4243350947524503250221141283676871054961767761533372535893799777316644277502608136805589201625364130457811586620275507258712882614289496389903620348266876, 7207723049065039433195103268720351560639394404931218738588797743896531445162073256971205066381805731964498662913612257697112297701515506572915529630749649, 9478867353430476119494189313998177997736272254097122188128236485373498544996365281925749885278741955783336542038044934310609039388320259421902808190444639, 10092751897940937230080778690510245631681516769761757712615337492357689455504789850857408988921202275660819814611602363226676960504340172006698418415173603, 5925826079655586275072881965974452367893696237983922405515651101142466142890347074549417916208251973477786424292583294611467079137685936757690986611634840, 2705681917429356111941316419951220642197423059675588735077708172236184161647753066851383893342803615318493417826483637576437939588768131347824859258545037, 5793481213766970753853702438948943122939283534830229656699291673833482520096412620329053619097899786691202045974184168665694248732396928571682405270896258, 3212965229314647637209688663583343281038324880827825190075824389072703574155472958687615046177029380089781167897141334668918512246004114927754397070032450, 507858897452123392345795058512546587866098555419275815786154069852495346820264502978622507708545904809967228104858456493411165322256241259977367791849042, 1910673108437857460691507244808588742883010826641687685721219894695257479961884688001651060796296482279750896861871054549713247272267814842634417960819168, 2886899741243848325873884252302617091514751717162909139186588257257958079130295099942906361136727891394692438504521454612873780003451672796809495226053047, 9475112027697464127079619380873273645977046666164164866182205134451664768516062572467782141714310693479352016031210905832129007401065693258638549100340615, 6500556077535313473248384729914564751019267303740919343852356539545383313100771434642240039386190890442297569489225045989569513367190888305128046797790102, 4352575880916080525863863641402979108455803235156616467981920947190189719209876636528864672410548581564537392488508689158499605332674737341258230577454475, 8855806560115120193748486720541724804359134126331550182497194629659837334220708039976726151383523965042432921330088347099157101222325916589506823343303429, 2774687136241363374520941544838376461935832170671324174983217598018541119488143069001573950404074015672792681188308412236177101695870429933915439814455887, 3592625154014227818614640279472091377202566130067513443394635609406915223429475106920133466069573358784994632708606215548054720669924050172507230811524716, 6955167231829680836198358545532458408492109230130585460528670650387346748536700767474985024643177587060440925065292948599577822789464670224006606550191671, 9194240450171813716718107852597217121362901491312541712415368806074976814988492806542250961496723482200369134039024809109124268301878344007510329535899615, 5950577443108124534632225089717156798651285826327691188035165834526053749015025923590404663092184546183617748745220821771671541995250149683517797527521402, 8147536282406177354958293970877926560729452459282692121940762677425779306283487924160782780299072205173184092679363257393333408904258459452274140791704067, 2559838851622656651952688025212080768394118716136473174419624432065878751831257138924556995347285973152404103332115858073203707432778426111325160735797721, 4949359541993387232537947394033362386729434824378846379892748514319807403496542405321037377319385099259508143211518009425440208974571177165892037150309091, 1811673815510905036234500180939767229691774807773077679609856974935852997557959138952513786288094951891092390620085630282790435640054840555430191851155313, 4777885082419038381870076531532991228660498200204585112220314790970263737966241042846160101892845251352987027168075888559622541458466624868511496707956221, 10238413710887745087366241938666680877364662925315040665408262063559110391570620624035047723405526398382375337996702653261521046541231508963525281969167278, 3473340971529025694371400010471019993671985537666177271712164477185774211271764180735799413043127038518985595844132844447764288680922052782557764949946998, 867350328105510555601266520733196439839458877892746826352327206388533426010006967907349245075237097927904721917883721235095421696529792601733014134854086, 2222551217354471458254572360148123193413834831993026644829243162796014361851880328878269533732240093458365703558737637137958860294765246560791514120259973, 11135205396103944017696365595462393888434601100415179875833418713405171505514194213145570969708606144837327906949671055964664374675657263466390592843391795, 8522093767526974938129274822063573020978729589640216089964237075835492415426711219243729120235033613444547687888110911207624759350428715822663409802746531, 618066223420558653541360712487038985426207412776033652080372792996567809564864490136174039188920973110051946250308952735815050129654446357610891600358247, 9409683398358516350960966400164689353665188916574105692687503875332913200043983566205433723664581043184720605266180639045542588369320481456882129188045630, 10444912184036485133367095187175276878779180732948191228469107836744786278456394810069942330852023901190983084405589604802372025661121698806608507168815980, 5576808818750933483753823503921696491223987341840901931564632327098735945058071342467846031030536056935288275893098409520502499556978787294107531192342888, 11386170831130547392066338523237385342399839863674855226178213470159061980868639851406716227763244070078162813390834461297132500087558187715637626334931068, 9266567474732845229716988973436914937598698459994255583719094874193822181675544832905800318876640152861212158602258489908050910803591150200525814954449464, 783592057196685768383414375510915255040313296240508052297125547577301394194342174502254618660494179262947294784116190346971775913769035176336764690986707, 9105502180406569116340185218615179260760299848734930041602247299415927012355894700609320722623370139135122342263713846033304524885782445949914570572453737, 2297513067567074587355421795953863750627166311403426281361312466297059134183355298180726594771668216966732975569375780641995446201527865824229865021970151, 11188600115372846854366137972585164923834717935898376598627276542371780275188751807941476083838808640337088079259756154889298297211898790479562768420072518, 9656534484640562909118084019762167873291009773232637365213178341424207965285682074941363264934464618450896824843786922345950140473512635227211478685645772, 9343461413426168572561103655466265435717795505657355206522619014228487030194629865342342831380623629471381377128476731390629039248389925891691539701146309, 8681682631345831952913045584970984843073645909076987924890403622460027832467542651987623584349089629585531159664847835287269602153108548311564650707486153, 2656022193773767486949157049738671449721427276944394094199310567891807831351152318018854466905531462256724938253289337125816757790150607033652302227218868, 8508384570273623974802293014504152838556567399448174508834295467479347400327605230626491770497722014885725768213847610504091563629074470937893415637338996, 9716708016762837073052660164394053927821481998442639097920157163041635386583167412600530638659299593644342722890385260143682043966383262553995449944733956, 10231440381205182517403356785692369093270060843919065205063057623835967990844569366866607452179015606536153761832574542432676397053147658371344410148994418, 5146017765041682548648007957706007143803297597587388958721578537741505373387718545092695689770641249769257901519197825087801304735466239843061128683798476, 5222787643951107881679620487297380490422971146509273142662864657570322385794688143091615970726544447887548792995773377472568754141261595697499826832283200, 10464709627510729920064247596403868144579001206027850090117534773353171042729174225448975480540265139445689560336303762183734720331072177316589830221880977, 8615548684371129329547908465444932886632829509038689025840147771114904826804441395348568994340729561487767929565347408386252378372026787346043297419998538]
e = 65537
n = 97853623351997296064353255135588846396569970130207954701198599507389250544514082114957455795330569730103385876268186267851194017938003005329258612122178955978821786063623918361705120943030241043571056282806763102278839262572943852578441568495106906583558313075633340995336324665255745279078992160547871869557
c = 44431449479567561261917922338101462065458737366369232901780150553091038211618354850829522817943842817713545313017593484450672219262670055539455602698182643653128488160901383204333856589371756831501857423631322915113418699087489759910739942878900174507138454184974875778861767989603951090385047953725189919178
'''

观察题目，题目给了如下形式的53组等式：

其中，各个值的已知信息如下：

  • x 为 (2，p - 1) 之间的随机数，并且在53组等式中保持不变
  • a、r 为 (2，2**238) 之间的随机数
  • 给出 a 、b

首先，有两点信息暗示要用格：

1、a、r 限制了数据范围，可以看作是小量，暗示用LLL

2、多组线性等式，暗示用矩阵


所以关键就是转化到一个可以运用格的问题形式，推导如下：

首先要想明白下面的式子：(推导比较容易，就不讲了)

然后就可以将问题按下面的方式逐步转化：

1、将b逆元转化到模n

​ 代入上面的式子，变成：

​ 同理：

2、联立消元

​ 相减得到：

​ 有没有发现，小量已经全部移到了等式同一边

3、转化为AGCD问题

将模等式利用同余定理展开：

​ 此时，问题已经变成了AGCD问题，这是因为：

​ AGCD问题通常形式：

​ 在本题中，各个量如下：

至此问题推导就结束了。

exp.py：

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
from Crypto.Util.number import *

P_bits = 512
Q_bits = 238+1024-512
R_bits = 238+238
e = 0x10001

a = [226623173423524660762660587272926713775967113908071780918074044654746571, 99264763681859867816401881797921542580399607408617989905539839585323915, 177386736426181055874933306917112626356703658087900095566603898769091471, 5081587307910189127020749833744000992860852972311811125838243285877024, 411574110749659943703486080205654180795533263258790540505729307655142415, 1932137082695732276757073197845160804183868657578020568122170798605640, 103124563846054461729937757543103647655652920105466714505493351091607258, 65504504807895104765113845019342631211794998326986693051403166347389343, 151981136459515488882551190881724794060443302721456924436833810784219984, 3718222682937746804225225548712093487815785751144078132168082568580360, 113510621144631490440930342566441462111997352193075435129065142534001691, 120974784665251812036673794948678799274628176126865320042025545119228958, 193781634902416477262894357163294897773986019836290716577623654684669134, 24723078645443091017196603549741156206848230267873373213787667300835247, 113165730428784680251415263617027036564335843097634063978942541861726366, 407969345567975756778713582637075079783087682011802438819519567067241979, 151997755976755754648644424339697978791639952976423703068460739754839735, 253811682402531882908516509348937060650658679039884817907013090700281326, 404019046883201096048575369492824679211148242588135515488831100750933, 216725815105749574244056185735609680710954976727370948136589694286539150, 131605791470353972911656132280131756304373156215254629027113994962767833, 180190835657942894146705472335255090682179032409197893415067330574923084, 280086867488286721744184104208965143004904898002959657537412170401510680, 141039650035922882497777354937772530276454847300329950111476878397654053, 319858542602843767926919031049756704694256249776295683733693049522108872, 135633729043152514436339515687850041275739968837263316059461122379487161, 5038078437655552457504448170918674775639811066221990939957937239270167, 31918623105281221407484700216805581554894830335850729735403857505547002, 424092292941284354705774693468403308534554297314522980647422106907791591, 300635399575681097924575337707842439619576566621368558814406755486658723, 323686536134235835297820679361020300261642147835330856978902402517820801, 392620731408972775834827063986182511057173023783228673505487358356342114, 108681888409433100038410892044516773350200560613740266422720530715166828, 182338238967593331173372924666322484559869636981878410128856193538847678, 242630103099393630296862580986126439159331512930513337684897019399319621, 439737851682655515589311041364295341910822514202794661846391952824593066, 84115222835816390632388766236883091861894245716624041418721833768917547, 83926810016448863267608537461154878096011055852547156452557576634691363, 354588657997053098464002945990025178880458974438409486331146607111950617, 170413334241108032297843362994773587930354677207616527135896108692092457, 283185550452196010949673962093382632839937948488235076418296451706429923, 390000015988537819093964185756696910433784324036454283227484980367608884, 121370082693927496814267201484843687844578996855559797026014779421645731, 357164702199289826402900456464935203585119719343409406742172822868770420, 124276883926433089715798954125363260298740714164810098876501303684201565, 122912426324401068572433533096099229494021528981601203447594706478943744, 287527827124819650763642012585104162743364640051014410357971387706781531, 135819408760576908301747047938951002691288880199213610653148681326046091, 239644892459756283997004399339163555215985564639569406081575642996080481, 241513055132921096791997556818670497379598444881679976542299970876463098, 144152466563589166040797814966860917437020789050031353309848917297959088, 120162009732086541189519736083838746833770360960800721525565383293404918, 121547756201941339094205049920057111793191461762212554355070565584802804]
b = [6914108949558554967947157128371931777410399406424987472871265954007536210016000226325059466226417032321637768264366355381358552354005990800271210820573485, 4243350947524503250221141283676871054961767761533372535893799777316644277502608136805589201625364130457811586620275507258712882614289496389903620348266876, 7207723049065039433195103268720351560639394404931218738588797743896531445162073256971205066381805731964498662913612257697112297701515506572915529630749649, 9478867353430476119494189313998177997736272254097122188128236485373498544996365281925749885278741955783336542038044934310609039388320259421902808190444639, 10092751897940937230080778690510245631681516769761757712615337492357689455504789850857408988921202275660819814611602363226676960504340172006698418415173603, 5925826079655586275072881965974452367893696237983922405515651101142466142890347074549417916208251973477786424292583294611467079137685936757690986611634840, 2705681917429356111941316419951220642197423059675588735077708172236184161647753066851383893342803615318493417826483637576437939588768131347824859258545037, 5793481213766970753853702438948943122939283534830229656699291673833482520096412620329053619097899786691202045974184168665694248732396928571682405270896258, 3212965229314647637209688663583343281038324880827825190075824389072703574155472958687615046177029380089781167897141334668918512246004114927754397070032450, 507858897452123392345795058512546587866098555419275815786154069852495346820264502978622507708545904809967228104858456493411165322256241259977367791849042, 1910673108437857460691507244808588742883010826641687685721219894695257479961884688001651060796296482279750896861871054549713247272267814842634417960819168, 2886899741243848325873884252302617091514751717162909139186588257257958079130295099942906361136727891394692438504521454612873780003451672796809495226053047, 9475112027697464127079619380873273645977046666164164866182205134451664768516062572467782141714310693479352016031210905832129007401065693258638549100340615, 6500556077535313473248384729914564751019267303740919343852356539545383313100771434642240039386190890442297569489225045989569513367190888305128046797790102, 4352575880916080525863863641402979108455803235156616467981920947190189719209876636528864672410548581564537392488508689158499605332674737341258230577454475, 8855806560115120193748486720541724804359134126331550182497194629659837334220708039976726151383523965042432921330088347099157101222325916589506823343303429, 2774687136241363374520941544838376461935832170671324174983217598018541119488143069001573950404074015672792681188308412236177101695870429933915439814455887, 3592625154014227818614640279472091377202566130067513443394635609406915223429475106920133466069573358784994632708606215548054720669924050172507230811524716, 6955167231829680836198358545532458408492109230130585460528670650387346748536700767474985024643177587060440925065292948599577822789464670224006606550191671, 9194240450171813716718107852597217121362901491312541712415368806074976814988492806542250961496723482200369134039024809109124268301878344007510329535899615, 5950577443108124534632225089717156798651285826327691188035165834526053749015025923590404663092184546183617748745220821771671541995250149683517797527521402, 8147536282406177354958293970877926560729452459282692121940762677425779306283487924160782780299072205173184092679363257393333408904258459452274140791704067, 2559838851622656651952688025212080768394118716136473174419624432065878751831257138924556995347285973152404103332115858073203707432778426111325160735797721, 4949359541993387232537947394033362386729434824378846379892748514319807403496542405321037377319385099259508143211518009425440208974571177165892037150309091, 1811673815510905036234500180939767229691774807773077679609856974935852997557959138952513786288094951891092390620085630282790435640054840555430191851155313, 4777885082419038381870076531532991228660498200204585112220314790970263737966241042846160101892845251352987027168075888559622541458466624868511496707956221, 10238413710887745087366241938666680877364662925315040665408262063559110391570620624035047723405526398382375337996702653261521046541231508963525281969167278, 3473340971529025694371400010471019993671985537666177271712164477185774211271764180735799413043127038518985595844132844447764288680922052782557764949946998, 867350328105510555601266520733196439839458877892746826352327206388533426010006967907349245075237097927904721917883721235095421696529792601733014134854086, 2222551217354471458254572360148123193413834831993026644829243162796014361851880328878269533732240093458365703558737637137958860294765246560791514120259973, 11135205396103944017696365595462393888434601100415179875833418713405171505514194213145570969708606144837327906949671055964664374675657263466390592843391795, 8522093767526974938129274822063573020978729589640216089964237075835492415426711219243729120235033613444547687888110911207624759350428715822663409802746531, 618066223420558653541360712487038985426207412776033652080372792996567809564864490136174039188920973110051946250308952735815050129654446357610891600358247, 9409683398358516350960966400164689353665188916574105692687503875332913200043983566205433723664581043184720605266180639045542588369320481456882129188045630, 10444912184036485133367095187175276878779180732948191228469107836744786278456394810069942330852023901190983084405589604802372025661121698806608507168815980, 5576808818750933483753823503921696491223987341840901931564632327098735945058071342467846031030536056935288275893098409520502499556978787294107531192342888, 11386170831130547392066338523237385342399839863674855226178213470159061980868639851406716227763244070078162813390834461297132500087558187715637626334931068, 9266567474732845229716988973436914937598698459994255583719094874193822181675544832905800318876640152861212158602258489908050910803591150200525814954449464, 783592057196685768383414375510915255040313296240508052297125547577301394194342174502254618660494179262947294784116190346971775913769035176336764690986707, 9105502180406569116340185218615179260760299848734930041602247299415927012355894700609320722623370139135122342263713846033304524885782445949914570572453737, 2297513067567074587355421795953863750627166311403426281361312466297059134183355298180726594771668216966732975569375780641995446201527865824229865021970151, 11188600115372846854366137972585164923834717935898376598627276542371780275188751807941476083838808640337088079259756154889298297211898790479562768420072518, 9656534484640562909118084019762167873291009773232637365213178341424207965285682074941363264934464618450896824843786922345950140473512635227211478685645772, 9343461413426168572561103655466265435717795505657355206522619014228487030194629865342342831380623629471381377128476731390629039248389925891691539701146309, 8681682631345831952913045584970984843073645909076987924890403622460027832467542651987623584349089629585531159664847835287269602153108548311564650707486153, 2656022193773767486949157049738671449721427276944394094199310567891807831351152318018854466905531462256724938253289337125816757790150607033652302227218868, 8508384570273623974802293014504152838556567399448174508834295467479347400327605230626491770497722014885725768213847610504091563629074470937893415637338996, 9716708016762837073052660164394053927821481998442639097920157163041635386583167412600530638659299593644342722890385260143682043966383262553995449944733956, 10231440381205182517403356785692369093270060843919065205063057623835967990844569366866607452179015606536153761832574542432676397053147658371344410148994418, 5146017765041682548648007957706007143803297597587388958721578537741505373387718545092695689770641249769257901519197825087801304735466239843061128683798476, 5222787643951107881679620487297380490422971146509273142662864657570322385794688143091615970726544447887548792995773377472568754141261595697499826832283200, 10464709627510729920064247596403868144579001206027850090117534773353171042729174225448975480540265139445689560336303762183734720331072177316589830221880977, 8615548684371129329547908465444932886632829509038689025840147771114904826804441395348568994340729561487767929565347408386252378372026787346043297419998538]
e = 65537
n = 97853623351997296064353255135588846396569970130207954701198599507389250544514082114957455795330569730103385876268186267851194017938003005329258612122178955978821786063623918361705120943030241043571056282806763102278839262572943852578441568495106906583558313075633340995336324665255745279078992160547871869557
c = 44431449479567561261917922338101462065458737366369232901780150553091038211618354850829522817943842817713545313017593484450672219262670055539455602698182643653128488160901383204333856589371756831501857423631322915113418699087489759910739942878900174507138454184974875778861767989603951090385047953725189919178

N = []
for i in range(51):
    N.append(a[i+1]*inverse(b[i],n) - a[i]*inverse(b[i+1],n))
X = 2**R_bits
m = len(N)

PR = PolynomialRing(ZZ, names=[str('x%d' % i) for i in range(1, 1 + m)])

h = 3
u = 1
variables = PR.gens()

gg = []
monomials = [variables[0]**0]
for i in range(m):
    gg.append(N[i] - variables[i])
    monomials.append(variables[i])

print(len(monomials), len(gg))
print('monomials:', monomials)

B = Matrix(ZZ, len(gg), len(monomials))
for ii in range(len(gg)):
    for jj in range(len(monomials)):
        if monomials[jj] in gg[ii].monomials():
            B[ii, jj] = gg[ii].monomial_coefficient(monomials[jj]) * monomials[jj]([X] * m)

B = B.LLL()
print('-' * 32)

new_pol = []
for i in range(len(gg)):
    tmp_pol = 0
    for j in range(len(monomials)):
        tmp_pol += monomials[j](variables) * B[i, j] / monomials[j]([X] * m)
    new_pol.append(tmp_pol)

if len(new_pol) > 0:
    Ideal = ideal(new_pol[:m-1])
    GB = Ideal.groebner_basis()
    function_variables = var([str('y%d' % i) for i in range(1, 1 + m)])
    res = solve([pol(function_variables) for pol in GB], function_variables)

    print('got %d basis' % len(GB))
    print('solved result:')
    print(res)
    PRRR.< x, y> = PolynomialRing(QQ)
    q = abs(PRRR(res[0][0](x, y)).coefficients()[0].denominator())
    p = N[-1] // q

p = abs(int(p))
q = n//p
d = inverse(e,(p-1)*(q-1))
m = int(pow(c,d,n))
print(long_to_bytes(m))

#flag{755f85c2723bb39381c7379a604160d8}



Matrix

题目来源：暂不明确

题目：

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
#!/usr/bin/env sage
# Problem by rec, with nothing.
import os
import secret
import hashlib
from Crypto.Util.number import getPrime
from Crypto.Util.Padding import pad

LEN = 32

def xor(a, b):
    return bytes([a[i%len(a)] ^^ b[i%len(b)] for i in range(max(len(a), len(b)))])

def challenge(m: bytes, pbits: int, level: int=0):
    p = getPrime(pbits)
    M = random_matrix(GF(p), LEN).matrix_from_rows_and_columns(range(LEN), range(LEN-level))
    c = vector(GF(p), m) * M

    return {"p": p, "M": M.list(), "c": c.list()}

args = {
    "chall1": {
        "m": os.urandom(LEN),
        "pbits": 512,
        "level": 0x00
    },
    "chall2": {
        "m": os.urandom(LEN),
        "pbits": 10,
        "level": 0x01
    },
    "chall3": {
        "m": os.urandom(LEN),
        "pbits": 256,
        "level": 0x10
    }
}

out = dict()
enc = pad(secret.flag, LEN)
for i in range(3):
    out[f"chall{i+1}"] = challenge(**args[f"chall{i+1}"])
    enc = xor(enc, hashlib.sha512(args[f"chall{i+1}"]["m"]).digest())
out["enc"] = enc.hex()
with open('output.txt', 'w') as f:
    f.write(f"{out = }")

梳理一下解密流程：

  • 先将flag串填充至32的整数倍
  • 生成三组challenge需要的参数：m，pbits，level
  • 将每一组的m用sha512加密后，依次与flag异或
  • 给出每组challenge的对应输出与最终密文值

其中，challenge的各个参数值在加密过程中的作用依次是：

  • 生成一个pbits的素数p，并以该p生成一个有限域Gf(p)
  • 将m的32个随机字节转换成Gf(p)下的长度为32的向量
  • 生成一个大小为32*(32-level)的矩阵M，M中元素均为Gf(p)中的随机数
  • 计算c=m*M，并给出p、M和c

因此，我们要做的就是由c、M反解出m，并计算其sha512值后与密文依次异或，就能得到明文，但是三次求解的方法由M的大小而产生不同。

challenge1

第一轮，M的大小为32*32，因此有：

可以看作是m的32个变量对应了32组方程，因此满秩，可以直接求解线性方程组(数据有点大，想要复现的师傅可以联系我)：

1
2
3
4
5
6
7
8
p = 
M = []
c = []

c = vector(GF(p),c)
m = matrix(GF(p),32,32,M)
flag1 = m.solve_left(c)
flag1 = bytes(flag1)


challenge2

第二轮，M的大小为32*31，因此有：

也就是说，m的32个变量只有31组方程了，因此可以求出无穷多组解。不过由于只差一组方程，因此也只需要选取一个自由变量，并从c中对应减去其值后，解一个31变量的满秩方程。而判断解正确的依据就是解出来的m向量中所有值均在0-256之间。

说起来可能不那么明白，还是上个例子，这里以下面这个线性方程组简单说明一下：

写出来：

变成方程组形式就是：

现在我们假设已经知道了x4的值(对应于题目中，就是在0-256中爆破)，那么把方程组中含x4的项都移到右边，就变成：

接下来解的就是这个满秩方程：

很容易想到，当解出的向量 $ (x_1,x_2,x_3)$ 均在0-256之间时，就正确求解了。放在本题中也不过是对这个例子的扩大而已，取x32进行爆破，方法是完全一样的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
p = 
M = []
c = []

c = vector(GF(p),c)
m = matrix(GF(p),32,31,M)
MM = m.delete_rows([31])
M_ = m[-1]
k = 0
for i in range(256):
	cc = c - i * M_
	ans = MM.solve_left(cc)
	if all(ans[i] <= 256 for i in range(31)):
		k = i
		break
flag2 = bytes(list(ans)+[k])


challenge3

第三轮，M的大小为32*16，因此有：

可以想到，如果继续用第二轮中的方法，那么需要爆破256的16次方种可能，数量级达到了2^128，是显然不可能的，所以需要另谋他法。而其实你应该早就想到了，m在每个challenge中，都是一个由32个0-256的值组成的向量。0-256意味着，在模p下这些值都很小，因此很自然地就会联想到格。

所以challenge3其实是一个格基规约问题，但是想构造出这样的格还是有点难度的。首先还是列出构造格需要的多个等式：

从这个矩阵乘法中，可以提取出其中的十六个等式：(i = 1,2,…,16)

以这些等式为基础，我们构造出下面的格：

1
2
3
4
5
MM = matrix(ZZ,32,16,M)
E = diagonal_matrix([1]*32)
P = diagonal_matrix([p]*16)
C = matrix(ZZ,c)
L = block_matrix(ZZ,[[MM,E],[P,0],[C,0]])

写清楚点就是：

这是一个49x48的矩阵，而我们用这个矩阵规约的依据等式是：

可以看出，规约出的向量 $(0,0,…,0,x_1,x_2,…,x_{32})$ 是非常短的，因此LLL就能得到这个解(不过实际操作会发现满足要求的向量在第二行)：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
p = 
M = []
c = []

MM = matrix(ZZ,32,16,M)
E = diagonal_matrix([1]*32)
P = diagonal_matrix([p]*16)
C = matrix(ZZ,c)
L = block_matrix(ZZ,[[MM,E],[P,0],[C,0]])
ML = L.LLL()
ans = list(ML[1][16:])
for i in range(len(ans)):
      ans[i] = -ans[i]
flag3 = bytes(ans)


final

得到三个flag之后，进行sha512后依次与密文异或就好。

exp：

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
import hashlib
from Crypto.Util.number import *

def xor(a, b):
    return bytes([a[i%len(a)] ^^ b[i%len(b)] for i in range(max(len(a), len(b)))])

#part1
p = 
c = vector(GF(p),c)
m = matrix(GF(p),32,32,M)
flag1 = m.solve_left(c)
flag1 = bytes(flag1)


#part2
p = 661
M = []
c = []

c = vector(GF(p),c)
m = matrix(GF(p),32,31,M)
MM = m.delete_rows([31])
M_ = m[-1]
k = 0
for i in range(256):
	cc = c - i * M_
	ans = MM.solve_left(cc)
	if all(ans[i] <= 256 for i in range(31)):
		k = i
		break
flag2 = bytes(list(ans)+[k])

#part3
p = 
M = []
c = []

MM = matrix(ZZ,32,16,M)
E = diagonal_matrix([1]*32)
P = diagonal_matrix([p]*16)
C = matrix(ZZ,c)
L = block_matrix(ZZ,[[MM,E],[P,0],[C,0]])
ML = L.LLL()
ans = list(ML[1][16:])
for i in range(len(ans)):
      ans[i] = -ans[i]
flag3 = bytes(ans)

#final
c = 0x72c0e8ef53c726969a91368ca600a081f38f5cfaa1d0669d9049f278fb2f0fb4f36dced86bf9b7e9ef59af082cc5a5b2458cae490ab23c0c8c5b9361499ae2e2
enc = long_to_bytes(c)
flag = [flag1,flag2,flag3]
for i in range(3):
    enc = xor(enc, hashlib.sha512(flag[i]).digest())
print(enc)

#flag{db1ebd0c-1cac-55d5-763e-b05f3d9af423}



SSSMMM

题目来源：2023福建省工控赛

题目：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
from Crypto.Util.number import long_to_bytes, bytes_to_long, inverse
from Crypto.Util.Padding import pad
from Crypto.Cipher import AES
from random import getrandbits
from secret import flag
import hashlib
import base64

flag = pad(flag, 16)

ecc_table = {
    'n': 'FFFFFFFEFFFFFFFFFFFFFFFFFFFFFFFF7203DF6B21C6052B53BBF40939D54123',
    'p': 'FFFFFFFEFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF00000000FFFFFFFFFFFFFFFF',
    'g': '32c4ae2c1f1981195f9904466a39c9948fe30bbff2660be1715a4589334c74c7'
         'bc3736a2f4f6779c59bdcee36b692153d0a9877cc62a474002df32e52139f0a0',
    'a': 'FFFFFFFEFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF00000000FFFFFFFFFFFFFFFC',
    'b': '28E9FA9E9D9F5E344D5A9E4BCF6509A7F39789F515AB8F92DDBCBD414D940E93',
}

class TSM2(object):
    def __init__(self, sk, ecc_table):
        self.ecc_table = ecc_table
        self.n = int(ecc_table['n'], 16)
        self.para_len = len(ecc_table['n'])
        self.ecc_a3 = (int(ecc_table['a'], base=16) +
                       3) % int(ecc_table['p'], base=16)
 
        self.sk = sk
        self.pk = self._kg(self.sk, ecc_table['g'])
 
    def sign(self, data, K):
        e = data
        d = self.sk
        k = K
 
        P1 = self._kg(k, self.ecc_table['g'])
        x = int(P1[0:self.para_len], 16)
        R = ((e + x) % int(self.ecc_table['n'], base=16))
        if R == 0 or R + k == int(self.ecc_table['n'], base=16):
            return None
        d_1 = pow(
            d+1, int(self.ecc_table['n'], base=16) - 2, int(self.ecc_table['n'], base=16))
        S = (d_1*(k + R) - R) % int(self.ecc_table['n'], base=16)
        if S == 0:
            return None
        else:
            return '%064x%064x' % (R, S)
 
    def verify(self, Sign, data):
        r = int(Sign[0:self.para_len], 16)
        s = int(Sign[self.para_len:2 * self.para_len], 16)
        e = int(data.hex(), 16)
        t = (r + s) % self.n
        if t == 0:
            return 0
 
        P1 = self._kg(s, self.ecc_table['g'])
        P2 = self._kg(t, self.pk)
 
        if P1 == P2:
            P1 = '%s%s' % (P1, 1)
            P1 = self._double_point(P1)
        else:
            P1 = '%s%s' % (P1, 1)
            P1 = self._add_point(P1, P2)
            P1 = self._convert_jacb_to_nor(P1)
 
        x = int(P1[0:self.para_len], 16)
        return r == ((e + x) % self.n)
 
    def _kg(self, k, Point):
        if (k % self.n) == 0:
            return '0' * 128
        Point = '%s%s' % (Point, '1')
        mask_str = '8'
        for i in range(self.para_len - 1):
            mask_str += '0'
        mask = int(mask_str, 16)
        Temp = Point
        flag = False
        for n in range(self.para_len * 4):
            if flag:
                Temp = self._double_point(Temp)
            if (k & mask) != 0:
                if flag:
                    Temp = self._add_point(Temp, Point)
                else:
                    flag = True
                    Temp = Point
            k = k << 1
        return self._convert_jacb_to_nor(Temp)
 
    def _double_point(self, Point):
        l = len(Point)
        len_2 = 2 * self.para_len
        if l < self.para_len * 2:
            return None
        else:
            x1 = int(Point[0:self.para_len], 16)
            y1 = int(Point[self.para_len:len_2], 16)
            if l == len_2:
                z1 = 1
            else:
                z1 = int(Point[len_2:], 16)
 
            T6 = (z1 * z1) % int(self.ecc_table['p'], base=16)
            T2 = (y1 * y1) % int(self.ecc_table['p'], base=16)
            T3 = (x1 + T6) % int(self.ecc_table['p'], base=16)
            T4 = (x1 - T6) % int(self.ecc_table['p'], base=16)
            T1 = (T3 * T4) % int(self.ecc_table['p'], base=16)
            T3 = (y1 * z1) % int(self.ecc_table['p'], base=16)
            T4 = (T2 * 8) % int(self.ecc_table['p'], base=16)
            T5 = (x1 * T4) % int(self.ecc_table['p'], base=16)
            T1 = (T1 * 3) % int(self.ecc_table['p'], base=16)
            T6 = (T6 * T6) % int(self.ecc_table['p'], base=16)
            T6 = (self.ecc_a3 * T6) % int(self.ecc_table['p'], base=16)
            T1 = (T1 + T6) % int(self.ecc_table['p'], base=16)
            z3 = (T3 + T3) % int(self.ecc_table['p'], base=16)
            T3 = (T1 * T1) % int(self.ecc_table['p'], base=16)
            T2 = (T2 * T4) % int(self.ecc_table['p'], base=16)
            x3 = (T3 - T5) % int(self.ecc_table['p'], base=16)
 
            if (T5 % 2) == 1:
                T4 = (T5 + ((T5 + int(self.ecc_table['p'], base=16)) >> 1) - T3) % int(
                    self.ecc_table['p'], base=16)
            else:
                T4 = (T5 + (T5 >> 1) - T3) % int(self.ecc_table['p'], base=16)
 
            T1 = (T1 * T4) % int(self.ecc_table['p'], base=16)
            y3 = (T1 - T2) % int(self.ecc_table['p'], base=16)
 
            form = '%%0%dx' % self.para_len
            form = form * 3
            return form % (x3, y3, z3)
 
    def _add_point(self, P1, P2):
        if P1 == '0' * 128:
            return '%s%s' % (P2, '1')
        if P2 == '0' * 128:
            return '%s%s' % (P1, '1')
        len_2 = 2 * self.para_len
        l1 = len(P1)
        l2 = len(P2)
        if (l1 < len_2) or (l2 < len_2):
            return None
        else:
            X1 = int(P1[0:self.para_len], 16)
            Y1 = int(P1[self.para_len:len_2], 16)
            if l1 == len_2:
                Z1 = 1
            else:
                Z1 = int(P1[len_2:], 16)
            x2 = int(P2[0:self.para_len], 16)
            y2 = int(P2[self.para_len:len_2], 16)
 
            T1 = (Z1 * Z1) % int(self.ecc_table['p'], base=16)
            T2 = (y2 * Z1) % int(self.ecc_table['p'], base=16)
            T3 = (x2 * T1) % int(self.ecc_table['p'], base=16)
            T1 = (T1 * T2) % int(self.ecc_table['p'], base=16)
            T2 = (T3 - X1) % int(self.ecc_table['p'], base=16)
            T3 = (T3 + X1) % int(self.ecc_table['p'], base=16)
            T4 = (T2 * T2) % int(self.ecc_table['p'], base=16)
            T1 = (T1 - Y1) % int(self.ecc_table['p'], base=16)
            Z3 = (Z1 * T2) % int(self.ecc_table['p'], base=16)
            T2 = (T2 * T4) % int(self.ecc_table['p'], base=16)
            T3 = (T3 * T4) % int(self.ecc_table['p'], base=16)
            T5 = (T1 * T1) % int(self.ecc_table['p'], base=16)
            T4 = (X1 * T4) % int(self.ecc_table['p'], base=16)
            X3 = (T5 - T3) % int(self.ecc_table['p'], base=16)
            T2 = (Y1 * T2) % int(self.ecc_table['p'], base=16)
            T3 = (T4 - X3) % int(self.ecc_table['p'], base=16)
            T1 = (T1 * T3) % int(self.ecc_table['p'], base=16)
            Y3 = (T1 - T2) % int(self.ecc_table['p'], base=16)
 
            form = '%%0%dx' % self.para_len
            form = form * 3
            return form % (X3, Y3, Z3)
    
    def _convert_jacb_to_nor(self, Point):
        len_2 = 2 * self.para_len
        x = int(Point[0:self.para_len], 16)
        y = int(Point[self.para_len:len_2], 16)
        z = int(Point[len_2:], 16)
        z_inv = pow(
            z, int(self.ecc_table['p'], base=16) - 2, int(self.ecc_table['p'], base=16))
        z_invSquar = (z_inv * z_inv) % int(self.ecc_table['p'], base=16)
        z_invQube = (z_invSquar * z_inv) % int(self.ecc_table['p'], base=16)
        x_new = (x * z_invSquar) % int(self.ecc_table['p'], base=16)
        y_new = (y * z_invQube) % int(self.ecc_table['p'], base=16)
        z_new = (z * z_inv) % int(self.ecc_table['p'], base=16)
        if z_new == 1:
            form = '%%0%dx' % self.para_len
            form = form * 2
            return form % (x_new, y_new)
        else:
            return None

def leak(start, bits, k):
    return int(bin(k)[2:][-start-bits:-start],2)

sk = getrandbits(256) % int(ecc_table['n'], 16)
sm2 = TSM2(sk, ecc_table)
start = 130
bits = 7
num = 50

sigs = []
L = []
for i in range(num):
    msg = getrandbits(256) % int(ecc_table['n'], 16)
    k = getrandbits(256) % int(ecc_table['n'], 16)
    leaks=leak(start, bits, k)
    L.append(leaks)
    sigs.append(sm2.sign(msg, k))

key = hashlib.md5(str(sk).encode()).digest()
aes = AES.new(key, AES.MODE_ECB)
enc = aes.encrypt(flag)
print(sigs)
print(L)
print(enc)
'''
['1de6f33a8366acbdd0b87ec7beb59e429936b43bae9b8ee2538d2b97d6640c70143fa04e7f1880d22b0e9cbce938edd880d69fc4ed9a6315abd905880a8d38f7', '9d5f8a16fe8d951cbab0a6dca86427286ca389aca6497f20ca3421fa0aa27f4ddf2db6c58229182eaccca41bfebf56961ff1f683ba94b81137c41f61c98c1368', '4d20e1aa4e4f6a4948158fabbdadec3c4d6049b6439981efcb70900d954d0a8f18bce67831d426c12726c321e6eb69e8708739fc74bfde6ad601433bcd896ca7', 'e5358c986a12ec11bcd495e8822c5a71b2545dc11ce09521edaa47c11b739b12bbe76ca89bd08beb969355dec56dfcdd6cff121bb61eaea148d25e9a6e428145', 'fb06d41eafbcc77d464fe41ca356641cbb92289d28b0ff37caad95619c34557969acf9f615214f3ecf6c15943fc63470da0785687ae535045145d5e161a69210', '2e97f02e82642c033af0fc9686788c1acd8841b65228fab3e66f5328e790d702edadb13e99ed1d411482cd913ec6730803e6fcff29206d9e1fc1b68e1f631e25', '4f1ffd080380e945b24596135e5772058ee8adc26272ed3147f0701063b4b9f435e5ac679ef2cd950332ea5139d64ffee7f1211ea64c5beffa162bb942683fac', '0882c54ba0409f28ab3907831eedab320bf3645fd70888266393704f81998ed57778912ededb54c58efd6fc9f22188566824ae312d4585f87d37339fd87827e6', '9dafe7cee839389cbd5a72ac17befad3228b47192ed3a94a319eef67704c094adfeca2f14a1cea54540e7d69c6033c53fdbe60969cc910b31b1fce8c9d6a9d5b', '627357126622ad1b76354b4f6974120f670baf035e24599e36c9f14527f225e6acb0e00482c3ab7442858070181eb3a7fc4acd8de5e5411aa482b094c6e1a1fa', 'a9c7c29b800677ac44427204bc2137f0641465a411a521d3567911ab364c426c7a340ad1dcddb2330667bc78925bbec8bfd47cbf8031496e468f5ff3f9cc8a71', '23429d961d3bcf2e4873379afba581b351441c2d33c37c1fb5e84cdc22045a99bac91b3d8e3c90de3d56d443e439246872ab8fbd4ff42fbbd37509f79ccedd6e', '2847983b8f9492fe88c988d04b8086b94d8f827684e10cf2d4db1f5c65c1a7354c6e15df548df379ea5a56b57de9e36faf36c8d05270dc4bf69577ecbb5c1300', 'c684e4714cd002abea6fa5bd23014a152cf358ab848179fdc29f1b79b090b42c550ea43718e3e2c4bea2ece080db41fb9433539cac0b8ac8e419bcdbb6477017', '34e969156c0ff98ccff9dbe2757a365e24e81857937cc3056a1b837d67a5bc0215c99aa15ac8150c6cee089623000104017ac535ef3a7fd10bb46b008e64bf12', 'b79275b644dd73661b947fb786054b114fc90bcdf19cdd2a4cc96c426a3581d854619d95c3b9864534f9fe66445336e55c1a79527825706500527392ebac7ba6', 'f7302bd4f492be0537536a5327dab593b903346a5e32bf0262f494f11bb3968a736ae1a90abebe7ab600d899b001e8e4704117b862cf7787df29b1b8cda76227', 'e7d378b1f273baaaab041d3d81d669a351abe21d5987403fbb7d35f957a82ebcf0ffbbef77a08c1807d6e19d33053a62801f151bb81d0179bdb09fefd45a845d', '8c8dddfe7c2ee295c4aad0f207517cb00a5870c93c38af0e7438510f80b6788f7e863da10ec0650ab661ead1ae799dc63d3f7115c018a1d1961a068cff25ff21', '7382adaeab3aaed04178cf90bcb2750e11498f17dda2e058bbed931e9ff55faaa3fcc5af423ac139fd936fff916c78a5de316e67b5226d804e2590c65ad191c8', '70385b3c8fa2fd47be6963683256ebcbf2eb0a81f76856cb9524d59dcc1f910f98b0c37687857da008c6901fd78a9cf3b8b0ea9d744c8ab3b3d1b70277372572', '13f510e214b5bb7dbb81fadd772835f6fd0f082252ab775ab72c1b62b1573466a39d634f428202dd67bb4cdbb692a2a5dd148a49504d021d4aa5d903fac02cb1', '0910c842616b8b4c7f2ab265172e1d682a89b79f97019473d517b606dd43999e343ad4b08a71b69a1f4ffc8db39f7deb0a3c51c44652b1c63e090d901f43b33d', '7129bd6c31cc1e7f480fa713d9ba5386fdac580593229ca77baf96ea41e87fcd5b4c83693fc4b6b37959fc80391e05b279acad320fbd03e1c332e4cedc86a5b7', 'b6b80ce7dfe5a9fe066fce563a486c4a5f07611ab484131faf9381dc794a329390c60b53080d8360903f5759a18a1eca1b265655ef43ca213544c31e99fe0087', '7bfdca43b8d21d48e18dae387ea95c4ba690bff5fe22f3a29637c196a2288fdde98ec73554123dc33c8af567c7b98f9775600a0e34f32eae62655b47a0182171', 'b93eb6af65de700306b7a22816a1d461451c694de5ce55464be57cce89e8349f81a6d3fcc52da72c5d14df88bbe5ff683b591788d3edc91006a99ed1171ecce0', '1ab26e7f8a1e8854a73f2904d781f9f551d5b325fea4ec3f7ec45a03fc8d0b087b054f6475c21a473f5b47d6a980539b6a0aaf207bf89b3cc46eaf7fbf63411d', 'bea21a265e48c2624ba85137392dde1971325909fdfb97f57397f422cd6a152ef75c99b0634d6863aa4d7b4f07648d10c7ed3eeb210dc86691d0e2b463471ba8', 'e49e1b08e4865d8da0a278c049b2826a6b97911adbdaa836fd57f509f96db436327318bbf82c98b8d9f607e99c48db663473e4e941eb6109b174375a157eeb60', '72f00c548fc2539a8914b135b80a37e5137fa267579bcf11b566d4c44ee57defced7d0d3a2ec9923aa2790e80ac61a151b79e7b2dd17accbc7dd66c8e41d7489', 'c0d86918879d4ccfa4adf3fbd449c9b26a17b61073221a15d576e9528e0e29fcf3b164020043ac2a5752768ac996fa15e551c36dfd6c1dbf0d24d81d2e5b6724', 'ffd6eca8075af0c4fe4f38d4b3950ed76a4cc1474eadbd65b38484138456a98a4f4cc697c2d455d386e432679722f32cc59d1aa5135eb72cb10b5a82380b4e71', 'a3407cb209c1a6788ba1ca992a7b6cc04ef1130f92be63b9738dae873f3e407b440788115edd81ef3c2e791e10798c3fd1830ca5b4773523ef246cf13fbd5a5c', '3b1fe148835ebeece99b0df444cb2705e195d5d364fdbaf2fa754797c8f7484461327d471b258f9b0b5dcfb757a08d50b0ac334154fd6d4d0d68c2a846de4163', 'cc12da7bed20a53b5af9eebae5a94177f745ed5d48c4690cb462c498019e6a516b52cc9953620c04e12a79b45e99fc8164a79f00268c648801824a690a01b78f', 'e4e36894a7323e5fb1dc54366acd4fd3f6d9ec2817bd1c153d3d84ed544893d6f5c8a7fe839acf4880eb8df6c8ced3f2f7d947835a496da7b010bf6c5b04d669', 'a365dd19731e2d0ad844856da269d53a895ddcf5195b16f4e858ba4f83d99f2bbc49f7e7f61a431297545a3c9f3b99815a5a9645f83b1ac3acf1ca61481812fd', '0feb0860a5f6f2eaffc35e02a63633335b702e8bb1ef5c24dc82848cf3145149f4cede4352366db459784fa843ba0a20cec648b2674704bfe8facc2eb97a0fc5', '47c15d55e9a7f31ad5566213f8d0bdb6c4082b3dc2506f6d9d55af00fefe41a8c7ebe0255430efc5f6e7f5858fadd8478959afaf23ed57871ff78c676d0a1cd0', 'c15d5a156453862bd6d7d3634dbbc711fcbe38e04a71cec69ff936347417fe439343f93a0a0a0d51712ce44fa277861cee82c350341fe00c28448e3fc6956cfa', '42a93a785ff208608b4deeac184a7f882e75c9d45e5c1fec6c4cd08f5efe08c27d5a670676e4c8697ad0813b02fe50f19e7a0bf189716a2796b9804f737d5a98', '33e06326cc15e21e9a7d2f5b45facd397d9ef13315bb792356432fcb63e22ce15f1da0a8db378660ee1b8ce9286f772663f16da0cf6bbce149392d50e24096cc', '1c11c1cbd0b3e468b7671c2ad1030506542935716c27cd0e241bc68144390a615f50af737bc2da9a72872ebae750e962a225d0dff561d879f919d187f95e4878', 'd96905497145789b9734797625ede70eafcb8fc5eedbac4278091aba0d7c4b2bfe74e97ef5f966c1a3b408d91a36290a94027677c8b02d62e1a2b6498550c61a', 'ab5accec0103e2809ff5a59c8b3ac3d1426441981f8c6413003c4b69494f54d1cc7d6bf352373c2d60f8aa3b0b2236d2ae150b02bea2f5d353e9b3400519be8e', '341cd45d80593cf158aac070433333500633f6bca596ea07b758729f7f1c2c9391a9dfa56bfd6810b2e21b0009fc84e4a309805288ace599b80eabe35feaebc7', '944769dafb279eb7998d136427e894cba7fb2fbc7f13e4137eabfaaec26f0bdc0779c212756e5c0ac849d285a5b6900174d2042759eeb1d3f5b0e49c58176e2c', '2dfaea9976d6d33109c778e28acb0647a01a4abff01df29b35d51b2359cccc75bac8772de117a47c64821566087de13bd8ab16f72e189c7a934b19b56734fee0', 'c613ddab5dd81096088f185a1ead16ea0e6d99facd0249535b4327e11bd53fac5fd1b3807fef181a93cc048dbd4387e64c8281ead7bf2a28970739900633b7ad']
[87, 18, 88, 63, 30, 66, 60, 85, 13, 82, 35, 28, 21, 74, 47, 6, 30, 111, 97, 51, 42, 61, 92, 70, 113, 43, 7, 21, 68, 10, 99, 57, 87, 51, 43, 44, 60, 39, 117, 6, 88, 48, 47, 51, 56, 91, 6, 29, 92, 82]
b's\xda\xed\r\x8e/\xde\xa4\x99\x93\xcdCBB\x1c\xae\xcbB\x9f\xdd\xd4\x96\x9f\xa5O\xbf\x16\xa4\xecL\xe7J\x97\x1a\xdf\xa1\xa1\x92i,\xdd\x8a\xb6\xcfp}ho'
'''

题目实现了一个代码很长的椭圆曲线类，不过注意到类中某个函数名：

1
def _convert_jacb_to_nor(self, Point)

而从其他地方了解过，椭圆曲线有一种基于雅可比坐标的计算，可以增加运算效率。具体可以参考：

椭圆曲线—雅可比坐标 - 知乎 (zhihu.com)

那么这些函数应该就是雅可比坐标意义下的点加法和倍乘法的实现，所以可以不用去理解坐标的计算过程，直接把这个ecc_table中的各参数用sage中的标准ECC表示即可：

1
2
3
4
5
6
7
8
9
10
11
ecc_table1 = {
    'n': 'FFFFFFFEFFFFFFFFFFFFFFFFFFFFFFFF7203DF6B21C6052B53BBF40939D54123',
    'p': 'FFFFFFFEFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF00000000FFFFFFFFFFFFFFFF',
    'gx': '32c4ae2c1f1981195f9904466a39c9948fe30bbff2660be1715a4589334c74c7',
    'gy': 'bc3736a2f4f6779c59bdcee36b692153d0a9877cc62a474002df32e52139f0a0',
    'a': 'FFFFFFFEFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF00000000FFFFFFFFFFFFFFFC',
    'b': '28E9FA9E9D9F5E344D5A9E4BCF6509A7F39789F515AB8F92DDBCBD414D940E93',
}

ecc1 = EllipticCurve(GF(int(ecc_table1['p'],16)),[int(ecc_table1['a'],16),int(ecc_table1['b'],16)])
g1 = ecc1((int(ecc_table1['gx'],16),int(ecc_table1['gy'],16)))

而可以验证，给出的g点是一个满足阶等于曲线阶的生成元，n也就是曲线的阶，并且是一个素数。把ECC这一层理解清楚之后，就明白其实很长一段代码都是不太需要理解的。

因此我们直接来看题目核心的加密任务：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
def leak(start, bits, k):
    return int(bin(k)[2:][-start-bits:-start],2)

sk = getrandbits(256) % int(ecc_table['n'], 16)
sm2 = TSM2(sk, ecc_table)
start = 130
bits = 7
num = 50

sigs = []
L = []
for i in range(num):
    msg = getrandbits(256) % int(ecc_table['n'], 16)
    k = getrandbits(256) % int(ecc_table['n'], 16)
    leaks=leak(start, bits, k)
    L.append(leaks)
    sigs.append(sm2.sign(msg, k))

key = hashlib.md5(str(sk).encode()).digest()
aes = AES.new(key, AES.MODE_ECB)
enc = aes.encrypt(flag)
print(sigs)
print(L)
print(enc)

可以看到，给出了一个leak函数，它可以泄露一个数k的中间130-136比特，共7比特。然后题目给出了如下加密过程：

  • 随机生成一个数sk，并以其作为私钥生成一个TSM2的类对象sm2
  • 进行50次基于ECC的变种签名操作，并给出每一次的临时密钥(nonce)k的leak，以及每一次的签名值(R,S)
  • 用私钥sk作为AES密钥，对flag进行加密，并给出密文

那么思路就是从50次签名操作的泄露信息中，还原出私钥sk，并解AES得到flag。因此我们主要关注签名操作：

  • 计算kg的横坐标作为x，其中g为给定的生成元，k为该次签名的临时密钥(nonce)
  • 计算
  • 计算(n是一个素数，所以可以由费马小定理推出下式)
  • 计算

然后将(R,S)作为本次签名值返回，并每次泄漏k的中间7比特。

其实看到比特泄漏就能想到应该是构造HNP求解，那么什么是我们需要的短向量呢？

首先注意到，每一次的临时密钥k可以写成如下形式：

也就是把k分成三部分，高位、leak位和低位，其中高位和低位是未知的，其比特数大概为119比特和130比特。而这就是我们构造HNP的关键，短向量中要有每个临时密钥的高位和低位！而我们只要能恢复任何一个临时密钥k，我们就可以通过S的签名式，计算出sk的值。

而显然我们需要根据S的这个等式构造格：

如何构造呢？我们简单变形一下：

移项，并乘逆元至左端：

再移个项，这样做是为了把k置于一端，其他置于另一端：

然后我们知道，sk是一个256比特的量，我们是不希望他出现在规约后的结果中的，因此想办法联立两个式子把他消去，这里我们取i=0与i!=0的式子做消除，如下：

上下各自乘上对应系数：

作差：

左边是个已知的数字，为了表示方便，我们把这个先写成一个简单形式bi：

即：

然后为了找到HNP的形式，我们继续移一下项：

此时我们把k展开为三部分形式：

然后由于kleak已知，那么又可以剔出一部分常量：

移项：

然后为了表示方便，更新一下bi：

那么又有：

然后我们把(S0+R0)乘到右边去：

此时，应该可以发现HNP形式了，我们令：

则有：

把模n去掉，写成等式形式：

那么我们就可以根据这个等式构造格，请注意我们构造格的目的是想要kh与kl在规约出的向量中，因此构造如下格：

这样写可能有点不太清楚，直接上分块矩阵的代码好明白一点：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
length = 50

O = matrix(ZZ,(length-1),(length-1)+3)
E = diagonal_matrix([2^11]*((length-1)+3))
T1 = diagonal_matrix([n]*((length-1)))
T2 = matrix(ZZ,(length-1)+3,length-1)
for i in range(length-1):
    T2[i,i] = 2^137
    T2[-1,i] = -B[i]
    T2[-2,i] = -A[i]
    T2[-3,i] = -A[i] * 2^137

L = block_matrix(ZZ,[[T1,O],[T2,E]])

K = 2^130
L[-1,-1] = K
L[-2,-2] = 1
L[-3,-3] = 2^11

把刚才的格记为L，对该格有如下线性关系：

如此一来规约出的向量数量级相当，均为2^130比特左右，因此对L进行规约有机会找到这个向量，从而恢复k，进而解密出sk。

事实上，采用BKZ算法，该向量会出现在每项均非0的第一行，问题得解

exp：

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
from Crypto.Util.number import *
from Crypto.Cipher import AES
import hashlib

ecc_table1 = {
    'n': 'FFFFFFFEFFFFFFFFFFFFFFFFFFFFFFFF7203DF6B21C6052B53BBF40939D54123',
    'p': 'FFFFFFFEFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF00000000FFFFFFFFFFFFFFFF',
    'gx': '32c4ae2c1f1981195f9904466a39c9948fe30bbff2660be1715a4589334c74c7',
    'gy': 'bc3736a2f4f6779c59bdcee36b692153d0a9877cc62a474002df32e52139f0a0',
    'a': 'FFFFFFFEFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF00000000FFFFFFFFFFFFFFFC',
    'b': '28E9FA9E9D9F5E344D5A9E4BCF6509A7F39789F515AB8F92DDBCBD414D940E93',
}

ecc1 = EllipticCurve(GF(int(ecc_table1['p'],16)),[int(ecc_table1['a'],16),int(ecc_table1['b'],16)])
g1 = ecc1((int(ecc_table1['gx'],16),int(ecc_table1['gy'],16)))

sigs = ['1de6f33a8366acbdd0b87ec7beb59e429936b43bae9b8ee2538d2b97d6640c70143fa04e7f1880d22b0e9cbce938edd880d69fc4ed9a6315abd905880a8d38f7', '9d5f8a16fe8d951cbab0a6dca86427286ca389aca6497f20ca3421fa0aa27f4ddf2db6c58229182eaccca41bfebf56961ff1f683ba94b81137c41f61c98c1368', '4d20e1aa4e4f6a4948158fabbdadec3c4d6049b6439981efcb70900d954d0a8f18bce67831d426c12726c321e6eb69e8708739fc74bfde6ad601433bcd896ca7', 'e5358c986a12ec11bcd495e8822c5a71b2545dc11ce09521edaa47c11b739b12bbe76ca89bd08beb969355dec56dfcdd6cff121bb61eaea148d25e9a6e428145', 'fb06d41eafbcc77d464fe41ca356641cbb92289d28b0ff37caad95619c34557969acf9f615214f3ecf6c15943fc63470da0785687ae535045145d5e161a69210', '2e97f02e82642c033af0fc9686788c1acd8841b65228fab3e66f5328e790d702edadb13e99ed1d411482cd913ec6730803e6fcff29206d9e1fc1b68e1f631e25', '4f1ffd080380e945b24596135e5772058ee8adc26272ed3147f0701063b4b9f435e5ac679ef2cd950332ea5139d64ffee7f1211ea64c5beffa162bb942683fac', '0882c54ba0409f28ab3907831eedab320bf3645fd70888266393704f81998ed57778912ededb54c58efd6fc9f22188566824ae312d4585f87d37339fd87827e6', '9dafe7cee839389cbd5a72ac17befad3228b47192ed3a94a319eef67704c094adfeca2f14a1cea54540e7d69c6033c53fdbe60969cc910b31b1fce8c9d6a9d5b', '627357126622ad1b76354b4f6974120f670baf035e24599e36c9f14527f225e6acb0e00482c3ab7442858070181eb3a7fc4acd8de5e5411aa482b094c6e1a1fa', 'a9c7c29b800677ac44427204bc2137f0641465a411a521d3567911ab364c426c7a340ad1dcddb2330667bc78925bbec8bfd47cbf8031496e468f5ff3f9cc8a71', '23429d961d3bcf2e4873379afba581b351441c2d33c37c1fb5e84cdc22045a99bac91b3d8e3c90de3d56d443e439246872ab8fbd4ff42fbbd37509f79ccedd6e', '2847983b8f9492fe88c988d04b8086b94d8f827684e10cf2d4db1f5c65c1a7354c6e15df548df379ea5a56b57de9e36faf36c8d05270dc4bf69577ecbb5c1300', 'c684e4714cd002abea6fa5bd23014a152cf358ab848179fdc29f1b79b090b42c550ea43718e3e2c4bea2ece080db41fb9433539cac0b8ac8e419bcdbb6477017', '34e969156c0ff98ccff9dbe2757a365e24e81857937cc3056a1b837d67a5bc0215c99aa15ac8150c6cee089623000104017ac535ef3a7fd10bb46b008e64bf12', 'b79275b644dd73661b947fb786054b114fc90bcdf19cdd2a4cc96c426a3581d854619d95c3b9864534f9fe66445336e55c1a79527825706500527392ebac7ba6', 'f7302bd4f492be0537536a5327dab593b903346a5e32bf0262f494f11bb3968a736ae1a90abebe7ab600d899b001e8e4704117b862cf7787df29b1b8cda76227', 'e7d378b1f273baaaab041d3d81d669a351abe21d5987403fbb7d35f957a82ebcf0ffbbef77a08c1807d6e19d33053a62801f151bb81d0179bdb09fefd45a845d', '8c8dddfe7c2ee295c4aad0f207517cb00a5870c93c38af0e7438510f80b6788f7e863da10ec0650ab661ead1ae799dc63d3f7115c018a1d1961a068cff25ff21', '7382adaeab3aaed04178cf90bcb2750e11498f17dda2e058bbed931e9ff55faaa3fcc5af423ac139fd936fff916c78a5de316e67b5226d804e2590c65ad191c8', '70385b3c8fa2fd47be6963683256ebcbf2eb0a81f76856cb9524d59dcc1f910f98b0c37687857da008c6901fd78a9cf3b8b0ea9d744c8ab3b3d1b70277372572', '13f510e214b5bb7dbb81fadd772835f6fd0f082252ab775ab72c1b62b1573466a39d634f428202dd67bb4cdbb692a2a5dd148a49504d021d4aa5d903fac02cb1', '0910c842616b8b4c7f2ab265172e1d682a89b79f97019473d517b606dd43999e343ad4b08a71b69a1f4ffc8db39f7deb0a3c51c44652b1c63e090d901f43b33d', '7129bd6c31cc1e7f480fa713d9ba5386fdac580593229ca77baf96ea41e87fcd5b4c83693fc4b6b37959fc80391e05b279acad320fbd03e1c332e4cedc86a5b7', 'b6b80ce7dfe5a9fe066fce563a486c4a5f07611ab484131faf9381dc794a329390c60b53080d8360903f5759a18a1eca1b265655ef43ca213544c31e99fe0087', '7bfdca43b8d21d48e18dae387ea95c4ba690bff5fe22f3a29637c196a2288fdde98ec73554123dc33c8af567c7b98f9775600a0e34f32eae62655b47a0182171', 'b93eb6af65de700306b7a22816a1d461451c694de5ce55464be57cce89e8349f81a6d3fcc52da72c5d14df88bbe5ff683b591788d3edc91006a99ed1171ecce0', '1ab26e7f8a1e8854a73f2904d781f9f551d5b325fea4ec3f7ec45a03fc8d0b087b054f6475c21a473f5b47d6a980539b6a0aaf207bf89b3cc46eaf7fbf63411d', 'bea21a265e48c2624ba85137392dde1971325909fdfb97f57397f422cd6a152ef75c99b0634d6863aa4d7b4f07648d10c7ed3eeb210dc86691d0e2b463471ba8', 'e49e1b08e4865d8da0a278c049b2826a6b97911adbdaa836fd57f509f96db436327318bbf82c98b8d9f607e99c48db663473e4e941eb6109b174375a157eeb60', '72f00c548fc2539a8914b135b80a37e5137fa267579bcf11b566d4c44ee57defced7d0d3a2ec9923aa2790e80ac61a151b79e7b2dd17accbc7dd66c8e41d7489', 'c0d86918879d4ccfa4adf3fbd449c9b26a17b61073221a15d576e9528e0e29fcf3b164020043ac2a5752768ac996fa15e551c36dfd6c1dbf0d24d81d2e5b6724', 'ffd6eca8075af0c4fe4f38d4b3950ed76a4cc1474eadbd65b38484138456a98a4f4cc697c2d455d386e432679722f32cc59d1aa5135eb72cb10b5a82380b4e71', 'a3407cb209c1a6788ba1ca992a7b6cc04ef1130f92be63b9738dae873f3e407b440788115edd81ef3c2e791e10798c3fd1830ca5b4773523ef246cf13fbd5a5c', '3b1fe148835ebeece99b0df444cb2705e195d5d364fdbaf2fa754797c8f7484461327d471b258f9b0b5dcfb757a08d50b0ac334154fd6d4d0d68c2a846de4163', 'cc12da7bed20a53b5af9eebae5a94177f745ed5d48c4690cb462c498019e6a516b52cc9953620c04e12a79b45e99fc8164a79f00268c648801824a690a01b78f', 'e4e36894a7323e5fb1dc54366acd4fd3f6d9ec2817bd1c153d3d84ed544893d6f5c8a7fe839acf4880eb8df6c8ced3f2f7d947835a496da7b010bf6c5b04d669', 'a365dd19731e2d0ad844856da269d53a895ddcf5195b16f4e858ba4f83d99f2bbc49f7e7f61a431297545a3c9f3b99815a5a9645f83b1ac3acf1ca61481812fd', '0feb0860a5f6f2eaffc35e02a63633335b702e8bb1ef5c24dc82848cf3145149f4cede4352366db459784fa843ba0a20cec648b2674704bfe8facc2eb97a0fc5', '47c15d55e9a7f31ad5566213f8d0bdb6c4082b3dc2506f6d9d55af00fefe41a8c7ebe0255430efc5f6e7f5858fadd8478959afaf23ed57871ff78c676d0a1cd0', 'c15d5a156453862bd6d7d3634dbbc711fcbe38e04a71cec69ff936347417fe439343f93a0a0a0d51712ce44fa277861cee82c350341fe00c28448e3fc6956cfa', '42a93a785ff208608b4deeac184a7f882e75c9d45e5c1fec6c4cd08f5efe08c27d5a670676e4c8697ad0813b02fe50f19e7a0bf189716a2796b9804f737d5a98', '33e06326cc15e21e9a7d2f5b45facd397d9ef13315bb792356432fcb63e22ce15f1da0a8db378660ee1b8ce9286f772663f16da0cf6bbce149392d50e24096cc', '1c11c1cbd0b3e468b7671c2ad1030506542935716c27cd0e241bc68144390a615f50af737bc2da9a72872ebae750e962a225d0dff561d879f919d187f95e4878', 'd96905497145789b9734797625ede70eafcb8fc5eedbac4278091aba0d7c4b2bfe74e97ef5f966c1a3b408d91a36290a94027677c8b02d62e1a2b6498550c61a', 'ab5accec0103e2809ff5a59c8b3ac3d1426441981f8c6413003c4b69494f54d1cc7d6bf352373c2d60f8aa3b0b2236d2ae150b02bea2f5d353e9b3400519be8e', '341cd45d80593cf158aac070433333500633f6bca596ea07b758729f7f1c2c9391a9dfa56bfd6810b2e21b0009fc84e4a309805288ace599b80eabe35feaebc7', '944769dafb279eb7998d136427e894cba7fb2fbc7f13e4137eabfaaec26f0bdc0779c212756e5c0ac849d285a5b6900174d2042759eeb1d3f5b0e49c58176e2c', '2dfaea9976d6d33109c778e28acb0647a01a4abff01df29b35d51b2359cccc75bac8772de117a47c64821566087de13bd8ab16f72e189c7a934b19b56734fee0', 'c613ddab5dd81096088f185a1ead16ea0e6d99facd0249535b4327e11bd53fac5fd1b3807fef181a93cc048dbd4387e64c8281ead7bf2a28970739900633b7ad']
leak = [87, 18, 88, 63, 30, 66, 60, 85, 13, 82, 35, 28, 21, 74, 47, 6, 30, 111, 97, 51, 42, 61, 92, 70, 113, 43, 7, 21, 68, 10, 99, 57, 87, 51, 43, 44, 60, 39, 117, 6, 88, 48, 47, 51, 56, 91, 6, 29, 92, 82]
enc = b's\xda\xed\r\x8e/\xde\xa4\x99\x93\xcdCBB\x1c\xae\xcbB\x9f\xdd\xd4\x96\x9f\xa5O\xbf\x16\xa4\xecL\xe7J\x97\x1a\xdf\xa1\xa1\x92i,\xdd\x8a\xb6\xcfp}ho'

n = int('FFFFFFFEFFFFFFFFFFFFFFFFFFFFFFFF7203DF6B21C6052B53BBF40939D54123',16)
R = []
S = []
for i in sigs:
    R.append(int(i[:64],16))
    S.append(int(i[64:],16))

length = 50
A = []
B = []
for i in range(1,length):
    temp = inverse((S[0]+R[0]),n) * (S[i]+R[i])
    temp = temp % n
    A.append(temp)
for i in range(1,length):
    temp = R[0]*(S[i]+R[i]) - R[i]*(S[0]+R[0]) + 2^130*leak[0]*(S[i]+R[i])  - 2^130*leak[i]*(S[0]+R[0])
    temp = temp * inverse((S[0]+R[0]),n) % n
    B.append(temp)

O = matrix(ZZ,(length-1),(length-1)+3)
E = diagonal_matrix([2^11]*((length-1)+3))
T1 = diagonal_matrix([n]*((length-1)))
T2 = matrix(ZZ,(length-1)+3,length-1)
for i in range(length-1):
    T2[i,i] = 2^137
    T2[-1,i] = -B[i]
    T2[-2,i] = -A[i]
    T2[-3,i] = -A[i] * 2^137

L = block_matrix(ZZ,[[T1,O],[T2,E]])

K = 2^130
L[-1,-1] = K
L[-2,-2] = 1
L[-3,-3] = 2^11

temp = L.BKZ()
#print(temp)


#从上面的格中找到满足要求的一行
k0h = 127539877108597124515923590046076573696 // (2**11)    
k0l = 62747361493076885745985101978595693282
k0leak = 87

k0 = k0h*2**137 + k0leak*2**130 + k0l
S0 = 9158674732422433584753600528499586749789902603207175171281211487385948076279
R0 = 13525126135691078619994352845806011492310052282990714228513050055938589068400
n = int('FFFFFFFEFFFFFFFFFFFFFFFFFFFFFFFF7203DF6B21C6052B53BBF40939D54123',16)

sk = ((k0+R0)*inverse(S0+R0,n) - 1) % n

enc = b's\xda\xed\r\x8e/\xde\xa4\x99\x93\xcdCBB\x1c\xae\xcbB\x9f\xdd\xd4\x96\x9f\xa5O\xbf\x16\xa4\xecL\xe7J\x97\x1a\xdf\xa1\xa1\x92i,\xdd\x8a\xb6\xcfp}ho'
key = hashlib.md5(str(sk).encode()).digest()
aes = AES.new(key, AES.MODE_ECB)
dec = aes.decrypt(enc)
print(dec)

#flag{cfe090d0-2888-a84d-ac6e-0e6aef017744}



e2D1p

这一题我是跟着maple的wp复现的，原wp指路：

N1CTF 2023 Writeups | 廢文集中區 (maple3142.net)

主要详细记录一下自己的思考。

题目来源：N1CTF 2023

题目：

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
from Crypto.Util.number import *
import os
FLAG = os.environ.get('FLAG', b'n1ctf{XXXXFAKE_FLAGXXXX}')
assert FLAG[:6] == b'n1ctf{' and FLAG[-1:] == b'}'
FLAG = FLAG[6:-1]


def keygen(nbits):
    while True:
        q = getPrime(nbits)
        if isPrime(2*q+1):
            if pow(0x10001, q, 2*q+1) == 1:
                return 2*q+1

def encrypt(key, message, mask):
    return pow(0x10001, message^mask, key)


p = keygen(512)
flag = bytes_to_long(FLAG)
messages = [getRandomNBitInteger(flag.bit_length()) for i in range(200)]
enc = [encrypt(p, message, flag) for message in messages]

print(f'message = {messages}')
print(f'enc = {enc}')

题目内容比较简短，其加密流程如下：

  • 生成一个素数p，满足p=2q+1，且q是一个512比特的大素数
  • 生成200个与flag同比特(159比特)的message，作为之后加密的mask
  • 用这200个message分别进行encrypt加密，并给出这200个message与对应密文，要求还原flag

其中，encrypt函数加密如下：

一些预备

首先肯定要恢复p，而如果指数上没有异或这个未知的flag的话，那么问题变成已知多组如下形式的等式，恢复模数p：

这个问题其实就是NSS二周年的一道题，具体分析过程可以看我的这篇：

NSSCTF-2nd-wp-crypto | 糖醋小鸡块的blog (tangcuxiaojikuai.xyz)

不过这里我仍然简单写一下构造格的思路，我们期望找到一组a，满足：

这样我们就有：

如果我们能找到多组满足条件的较小的a，我们就能在较短时间内算出多组整数域上的下式：

然后求解gcd即可恢复模数。而为了找到这样的多组满足条件的较小的a，我们构造了如下格：

他满足下面的关系式：

所以我们对格进行规约，取规约出的前几行短向量作为我们需要的a，然后按上述方法计算出多个kp并求解gcd即可恢复p。

恢复p

回到本题，这个题目在指数上异或了未知的flag：

那么我们就没法知道每一组密文对应的幂次具体是多少，所以上面问题中的格也就无从构造。但问题依然是相似的，我们仍然是想找到多组满足条件的a，去求解gcd从而恢复p。那么就要想办法将问题转化成较为简单的形式。

首先要理解一点，指数上的异或究竟指什么？我们不妨拆开这个问题，先只关注异或：

我们把mi拆成159个二进制位，记作mij(j从0到158)，同理flag的159个比特位也记作flagj，那么其实异或就是对flag进行了如下的改变得到ti：

一眼看上去是有点复杂，但其实他表达的意思很简单，我们取mi的任意一个二进制位mij做如下说明：

  • mij有0、1两个取值。取0，说明这一位不发生翻转，也就是对ti没有影响；取1，说明这一位发生了翻转
  • 而发生翻转又有两种情况：0->1和1->0，这要视flagj的取值而定，flagj同样有0、1两种取值。因此可以以(-1)^(flagj)来表示翻转情况
  • 2^j表示的是翻转的具体量

举个简单的例子：假设flag二进制为101，message为011，那么异或其实也就是：

  • 最后一位1->0
  • 倒数第二位0->1
  • 最高位不翻转

那么这样计算出ti其实就等于：

这就是说，我们可以把异或转化为一种加法形式表示，那么我们再把这种形式放回指数上，又会如何呢？

也就可以写成：

而正如刚才讲的预备题目中所说，我们要恢复模数p，就要找到多组满足如下条件的a，然后求解gcd：

代入到本题中的式子，就会有如下形式：

又因为右边底数部分e是相同的，因此累乘可以变成指数上的累加：

所以我们其实希望有：

那么其实也就是有：

所以现在我们的目标就是靠这个式子，去找到若干组较小的a满足上式，然后就可以求gcd得到p了。而想要达到这个目的其实也很容易，注意到这个等式其实由可以拆成两部分组成：

那么我们不妨使两部分均为0，那么其和也肯定为0，也就是：

而如何使两部分分别为0呢？首先，对于第一部分，显而易见只要使得：

也就是ai的和为0就可以。而对于第二部分，列式观察就会发现，我们也只需要满足下式即可：

由这两个关系我们可以构造如下矩阵：

这个矩阵具有如下线性关系：

其中，L的最后一列是满足刚才写的第一部分，而L的前面的列是满足第二部分。

这样一来，我们能够看出，我们想要的满足条件的a其实就是L的左核空间中的向量，而为了让他更小，我们对左核空间的基向量组进行规约即可。

规约后我们取几组a按照上面所说的办法就能得到p。

求解flag

有了p之后，我们仍然要继续想办法用已知的如下式子恢复flag：

显然如果我们能求解DLP得到指数部分的话，就能再异或mi得到flag。不过由于题目中，p由2q+1的方式生成，所以p-1肯定不光滑，并且也没有别的好的方式直接求解这个离散对数。

不过之前翻春哥文章看到过一篇，用调cado求解这种p-1只有一个大素因子的离散对数问题：

[调包侠] 利用cado-nfs计算离散对数的调包记录 暨 第四届“强网”拟态防御国际精英挑战赛 Crypto - speedrun writeup - 知乎 (zhihu.com)

不过这个要使用好像挺麻烦，不知道在这里是否可行

回到正题，既然直接求解这个离散对数问题是难解的，那么就要另寻办法。这个时候再观察我们刚才的式子：

里面的这一部分是由flag的每一个二进制比特计算得到的：

那么我们是否可以利用这个式子逐比特恢复flag？首先仍然注意刚才的矩阵：

刚才我们求解这个矩阵的左核空间并规约，求gcd并去除小因子得到了p。之所以能这么做，是基于我们拆出了下面这个式子，并令两部分分别为0的缘故：

这个时候我们找到的ai满足：

而如果我们改变右边的解为：

这时候如果我们能解矩阵方程得到a，那么向量a应该满足：

也就是说，我们分割出的两部分和，此时第二部分仍为0，而第一部分变成了1，也就是：

此时我们再求c的累乘，得到的就应该是e的flag次方。但是我们好像仍然没有办法求解离散对数得到flag，并且更绝望的是，这个矩阵方程无解。

然后看maple的思路，发现大致相同，但是他发现如果target向量是如下形式的话都有解：

而这其实就给我们逐比特还原flag带来了机会，比如我们第一次以第一个向量作为目标向量求解矩阵方程，会得到一个向量a，然后我们用这个向量a进行累乘，得到的结果应该是：

k在这里是最高比特位，flagk也就是flag的最高比特位，也就是1。然后我们把这次累乘的结果记作y1：

然后，我们选择第二个向量求解矩阵方程，并且同样用结果进行累乘得到第二组结果y2：

可以发现y1、y2具有如下关系：

然后你会发现，由于flag的每一比特只有两种取值，因此这个部分也只有两种取值：

我们算出这两种取值，然后分别与y1相乘看哪个等于y2，就得到了flag的这一比特位。往后也同理，由此我们就可以逐比特还原flag的所有比特位了。

这里有一点需要注意，虽然解矩阵方程的矩阵和目标向量都定义在ZZ域上，但是实际解出来并不是整数，所以计算累乘时需要额外处理一下。我这里就直接用了maple的field_exp函数。并且由于最后一步模的计算较多我就用了powmod加快，虽然好像效果并不是非常明显。

exp：

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
from Crypto.Util.number import *
from gmpy2 import powmod
from output import message,enc
from tqdm import *

#part1 recover p
L = Matrix(ZZ,200,160)
for i in range(200):
    temp = bin(message[i])[2:]
    for j in range(159):
        L[i,j] = int(temp[j])
    L[i,-1] = 1
L_kernel = L.left_kernel().basis()
res = Matrix(ZZ,L_kernel).LLL()

kp = []
for i in range(2):
    left = 1
    right = 1
    a = res[i]
    for j in range(len(a)):
        if(a[j] > 0):
            left *= pow(enc[j],a[j])
        else:
            right *= pow(enc[j],-a[j])
    kp.append(left-right)
p = GCD(kp[0],kp[1])

for i in range(2,10000):
    while(p % i == 0):
        p //= i
print(p)
#25070940894294854944213724808057610995878580501834029791436842569011975159898869595617649716256078890953233822913946718277574163417715224718477846001735447


#part2 Get flag
L = Matrix(ZZ,200,160)
for i in range(200):
    temp = bin(message[i])[2:]
    for j in range(159):
        L[i,j] = int(temp[j])
    L[i,-1] = 1

def field_exp(el, e):
    a, b = e.numerator(), e.denominator()
    el **= a
    q = el.parent().characteristic() // 2
    d = inverse(b, q)
    return el**d

y1 = 0
y2 = 0
flag = ""
for i in trange(159):
    target = vector(ZZ,[1 for j in range(i+1)] + [0 for j in range(158-i)] + [1])
    s = L.solve_left(target)
    F = GF(p)
    c = product([field_exp(F(y), z) for y, z in zip(enc, s)])
    if(i == 0):
        y1 = c
        flag += "1"
        continue
    else:
        y2 = c
    temp = powmod(65537,2**(158-i),p)
    if(temp*y1 % p == y2):
        flag += "0"
    else:
        flag += "1"
    y1 = c

print(long_to_bytes(int(flag,2)))

#n1ctf{30o0_ezzz_dLLLp%$#@!}

总的来说这题对我来说难度还是很大，路还很长。



vector

题目来源：暂不明确

题目：

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
from base64 import b64encode, b64decode
from random import randint, getrandbits, choices
from Crypto.Util.number import getPrime, long_to_bytes
from Crypto.Cipher import AES
from secret import flag
import signal

def genX(rho, eta, gam, p):
    return p * getrandbits(gam-eta) + getrandbits(rho)

rho = 12
eta = 256
gamma = 1000
x = getPrime(256)
X = genX(rho, eta, gamma, x)
p = getPrime(int(X.bit_length() * 2.5))
A = randint(2, p - 1)
B = randint(2, p - 1)

print(b64encode(long_to_bytes(p)).decode())
signal.alarm(30)
while True:
    choice = input().strip()
    if choice == "reset1":
        y = randint(1, X)
        a = randint(1, p - 1)
        b = (y**2 - (X**3 + a*X)) % p
        A = a
        B = b
        print("reset successful.")
        print(b64encode(long_to_bytes(A) + b"||" + long_to_bytes(B)).decode())
    elif choice == "reset2":
        X = genX(rho, eta, gamma, x)
        print("reset successful.")
    elif choice == "check":
        user_input = int(input().strip())
        if user_input == x:
            print(flag)
        else:
            exit(-1)
    else:
        exit(-1)

是一个师傅问我的一道靶机题，但是我没有环境，所以就讲讲思路。

题目任务如下：

  • 生成一个256bit的素数x，同时生成一个X，满足：
  • 生成一个2500bit数量级的p并发送给我们，然后限时30s，交互开始

交互开始后，我们在时间允许范围内有无限次交互机会，每次交互我们可以：

  • 输入”reset1”，题目会随机生成yi、ai，并计算出对应bi后，发送(ai，bi)给我们。满足(X,yi)在下面的椭圆曲线上：
  • 输入”reset2”，题目会更新X的值
  • 输入”check”，我们可以给靶机核对小写x(就是最初生成的256bit的素数)的值，正确则可以得到flag

那么首先就要明白reset1、reset2这两个交互功能各有什么作用。首先我们知道有：

那么如果能知道多组X的值，这就变成了一个AGCD问题，这也就是reset2的作用。

因此，我们的想法就是：

  • 每次reset2，得到一个未知的Xi
  • 想办法用reset1来解出Xi的值
  • 得到多组Xi后，解AGCD得到x去通过核验，拿到flag

那么接下来的任务就落在了如何利用reset1上。我们已知每次reset1会提供给我们一组满足如下等式的(ai，bi)：

看上去是引导人往椭圆曲线想，就会自然想到groebner，但是稍微再想一想就知道变量多了，肯定groebner不出来。

而实际上，既然我们可以多次reset1，那么这其实也是一个HNP问题。我们把模等式展开：

那么我们完全可以同样用HNP构造格的思路，构造下面的格来求解X：

这个格具有如下线性关系：

然后，我们配平一下这个格并进行规约就有机会得到目标向量。经过测试，申请四组(ai，bi)，就可以在第三行得到我们需要的目标向量，并且所用时间也很短，符合要求。

得到一个Xi后我们就reset2更新下一个Xi，并继续按这个方法求解即可。然后有多组Xi就可以AGCD求x了。

由于没有靶机，这里我就放一下我本地验证HNP问题的exp：

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
from Crypto.Util.number import *
from random import randint, getrandbits, choices
from tqdm import *

def genX(rho, eta, gam, p):
    return p * getrandbits(gam-eta) + getrandbits(rho)

rho = 12
eta = 256
gamma = 1000
x = getPrime(256)
X = genX(rho, eta, gamma, x)
p = getPrime(int(X.bit_length() * 2.5))

Alist = []
Blist = []
round = 4
for i in range(round):
    y = randint(1, X)
    a = randint(1, p - 1)
    b = (y**2 - (X**3 + a*X)) % p
    Alist.append(a)
    Blist.append(b)

L = Matrix(ZZ,3+round,3+round)
K = 2^1000
for i in range(round):
    L[i,i] = p*K
    L[-3,i] = 1*K
    L[-2,i] = Alist[i]*K
    L[-1,i] = Blist[i]*K

L[-3,-3] = 1
L[-2,-2] = 2^2000
L[-1,-1] = 2^3000
print(X)
print(abs(L.LLL()[2][-2]) // 2^2000)



HNP

题目来源：暂不明确

题目：

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
from Crypto.Util.number import *
from secrets import flag, x, y, z
from sympy.ntheory import prevprime
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad

Round = 32
q = 2 ** 256
for i in [x,y,z]:
    assert i.bit_length() == 256

A = []
B = []
for i in range(Round):
    a = getRandomInteger(256)
    A.append(a)
    b = (a * x % q) >> (256 - 8)
    B.append(b)
print(A)
print(B)
'''
[3561678147813669042672186969104055553515262226168087322052560790885260761433, 17346407693442644010055116546363960164095133759884497841925887458500171929994, 10970839811545507511408260800883769581649579684426188079142754412064502787585, 109417222922540235139013912297145185193443712852193270682885305502867182588403, 88171850234002600580608014259219586239590114856448092326801813245774395730496, 5113619435362108938262679062561727235116615800676783173565082653599747645155, 54576089683044230333058389148818602636893918880220233916359714009830588044131, 46319652232696496987147414399965164805770427009639155019904825551069668519260, 92142202700489403870481152403139465532735056770434774464930082474517829581964, 9084526539780165183228300902059842905058839285187659313361650962576085292818, 89120115360204223476154240731792191817638074392691790750005020564226279037550, 108874944765319253896194176909539011617418473448207058050594223215460183828033, 48697630410338199345605370644643425030874923782845194702123578264330641464094, 90490831141215467713642375752174358047945797806394912036159392371419919773636, 5407847525945777533863763148921176292074562577253075889320641646783216244238, 95326999116234880776873896438659550308182265903511015349887289749187746932743, 13848646478536701368088661040908693291788138011605835864557858216170511016083, 12688154545015600072136788151484672710661959298941783293908174000377900727747, 103416430654164637952330806792686485956010294787748757584715063906414248209722, 36213989454986448247979083323211284869162879484215027121399406834805531673463, 83477199408920970502661396196378764693640078246444907844363833717275362253336, 54685544287120130615023910691215446521783587675140445694155062634358785975223, 57209914633582227771666953772776413914105217956486621477363100169491699389485, 60722705656546434007907580733214759241271810206392571495455413850603913610651, 62666312072142619643565102615355724228875566515181602729719018682721112131326, 17892029370519322177254795109531838575579273633357811419566887056272012019617, 23387537005911727415991488713130020055341902697712259630978747015670850612866, 57084096974333718635810536400151484653413307540676932220675888461543384910791, 64672020284448913361212245534680048800817888816777270292913433441383929287826, 30879668079119218442051482226185849538064516289533962210948424807374221747937, 67805294126621083377517953883639091568886644480832055617022550683600509359637, 80971248361778969534551851802629859076303703583702628504189145200772632698437]
[185, 121, 74, 192, 66, 208, 189, 5, 248, 216, 222, 49, 199, 122, 212, 109, 36, 135, 9, 43, 94, 192, 67, 176, 165, 34, 241, 27, 255, 216, 71, 156]
'''
q = prevprime(q)
print(q)
A = []
B = []
for i in range(Round+1):
    a = getRandomInteger(256)
    A.append(a)
    b = (a * y % q) & (2 ** 8 - 1)
    B.append(b)
print(A)
print(B)
'''
115792089237316195423570985008687907853269984665640564039457584007913129639747
[46504565744057869379592149118750005180204315285587793650459698458291497313095, 58007957093934046182693035826219870499452741234326847327688846747059237094075, 50185124619087453830679170251457196445767905313509337058697814870412730362947, 13460057838246434192804076595664204927155595158673092664009965681276162112064, 1701081975560116286696366369808334022446618430663926380667987754925635360535, 26884871731419084105623632272724863769910293366201375037286643905133449526668, 86148369125917615329995354501659454507150263427394081644953922899405044908942, 86965847264933041291798488655625963084424620038983026175910367027955449692128, 51359332101276868450990110421905601457823984827989287103931757850844231666586, 48796757902016638482644909388959646721244669665114474829651238484065619118952, 100070448202859232758452766870542683109402601193511866026529530855112793822109, 96580256984898125874774601478072811945116066886633284314860596683569097605765, 38808894076998102467847013020946201384521577320197543440467015636483307894892, 4134554141092625841029701614640247691101835437566908306546904884177729072687, 74873085435488619613395208820994521773265984299598688734149106712561237976724, 15654842239708870234259249156913701671624803564647865424705391694462101457862, 88322093034453332197643606249439750127876581478584569790806716889277489637972, 22499556277754006237442593359493863007223009260764163505327306701416065559119, 67089035688878297307085968283413144678391442218184879365509351597884743967932, 27674630243557284124557851587722479960748242794492773619925160133318279977692, 9119521864491019262790789925266797995577993021425216600126182732190292182948, 101288882073195598657612116292233377922026161322404160341330451374348438098216, 67804446744028818432860934046262550895247933787912806120088242004054790700495, 26086948144209799352019678059923693118044934151861294461002114985645656470189, 38144657569843600236424138168852321656171547769351620499893335164030638528328, 29607623036881080673594862278805535156351844098214001235565521439825687173709, 73322408962909922161031457562287596779866102699954700495813418822123077110802, 71841446787131237842866428647552570448973984694577468650052516966413175250298, 1230436323839997562475731649322922330998915952913300933165504728647309839568, 107223013661981482036189531938571461516528131559156846625598018135279924645933, 40439925178577390217639900040814034803597438472158408491211685077053585300286, 26978587850306490903937574562860250724695533954879823140348556476663322417613, 82195886203427304567763311291077205482622324404366375181470500496565215770146]
[115, 240, 228, 198, 160, 178, 214, 160, 96, 140, 89, 186, 159, 102, 192, 93, 135, 30, 17, 9, 138, 224, 109, 116, 76, 116, 180, 196, 121, 187, 210, 208, 14]
'''

q = 2**256
A = []
B = []
for i in range(103):
    a = getRandomInteger(256)
    A.append(a)
    b = (a * z % q) >> (256 - 4)
    B.append(b)
print(A)
print(B)
'''
[56666422659665306957613341966104139188430887040369382699811066965734652038579, 41608423494025514337106193470276163502869431432921281068110444274310186909892, 95312645577996377489331859379729367791539181995403307071242251663306260824059, 114007089082826788908311397311915638668862713690403097281136795912671634293903, 77470602549297888428039543840134276433567854766634294661906479236200644990851, 67265570384781545307301479187933437206481537999752352862466291209724038113997, 101015220564168271842813302532972922828562060680762307341661161853013181455988, 73596220918173964622453801478597395507613363519777836354319778006747628725943, 80276240092293162850897330969848557221924558822619435206166856373482558821153, 60387041856575123107349887176488814324533329129026453912394888320971261329267, 37588667650535221417005569007639921039223353621264869144904381190769978830432, 30201673227033963823582196954697293400001560479877858941307825349312312395908, 46517796724693810353256110303591718873843585558937781709113232176049614134229, 110476911183528409932385631377040635032167229294859921626233104995069707326026, 33913880276956766352570275848477001195330941450588079882929631222080051897977, 108738411950576541236703456832793461013595057668683247592686862598082364613770, 87211442745029489881514515811064102429019356351722823450170249465088775249507, 39600946693670273230261533720839589755726946308581706825676138619972092199256, 4979886914346369664911891403751631037886315717549974065878536283157637402320, 22272529908653383795002294860870129574984518813560375272257703512940569602004, 100135751785995415247695765442899140606914076750888419237400306294448451415863, 85613534858376605408667291532701284666560850915689941354202786014968649139457, 38496246133430733988750968353732662162312705079114417415163071485082991344590, 55980481790171446152748793757788577465044360548729573345122559743628093363153, 71280277172994137969689292719624075379102489317199533126561191722460505314026, 110446223482446943024326135434573497276437669060614612856002207641927747194266, 16456085922385532110267651711339329146652084370610067373716816178321924748791, 101653629730678493695114228522885120593522618541788967122785214737946157867999, 74467527492811608068163160348674720595757862332879609098404557441577413104820, 41884843126443673947662657085537596879702074001592844509379139860812151553968, 29815687077578101251522932333124915023192910276895021601688368611558697857638, 44840628789800333625015337751638405696233468515566263356197320268202190223769, 102427595787595418722722430130631701884337456325150921017413824991597185452849, 2975107125099035075044003816426206055437890428466365543585422202932381886186, 94699511483779321185024950255977801474453881858185354369860946591141828290326, 31810607567540037649472765223870019465281477418301020106850480432511306591757, 75713781109794200255529510371465092460190607870508383754795316160075282283862, 55429849762380955520557448208384572772400405309708977900727750338226215580736, 71351843550447097631722656769410630908972124288367169285559142896305583201390, 84145371680533342029399999651802676680665442500082991947093355443249540103162, 18059328520840928370924328960454198116073475240703647573736616851363995779497, 83839387396741626377342400188482404639827411621171844172874897800772466334269, 25788978353065311499638204532308969267343091396798096623404684254370926606489, 46416171203559401945669998573205329748734005210989064607057470628982156110053, 42839223735347899899704913105525407073907314464785013094063759450820513757342, 88826657766811054515837039931572449230721258604658317309512814974116100196733, 53796508595019468595537500010909399217450133587528313928622717009905225347437, 56531378551320964008977461547054273860909442858252049481923559030063639435057, 48217679285988263588226655808041000825638438349841115697751615792350031644869, 64424297190010710116212288045994884168253983939992794298642423963632550451160, 46474911280506479688705284230861217499981118516937627597481370505066926962182, 64032029526907010327735757773865326038078238679652707012855320952596919166618, 5529383900219431454017233184818428510888383480088262580036064976358985800985, 69322608357555546086372761692837205200171798855109065251575534608627560525776, 76098979682650954216202311601813089916970156784884278240596741668163729505020, 91674126062289237651839995587104059408995800143522837051179562018281051100557, 90571390404208688843585603192800843878382529323359914123528861146103857760661, 72012664155317843790423022518639753138262519729890141457716216773019826138388, 66863180243825712563555363518892364864799935770917594234609418534062748300787, 5838945753982677965177087293687053018953448675487050703226841119623778529018, 4440280122867898274880560103713163505203269339591832639427292037957483435863, 113585052040012311817152621651926546174704034369418207806360593735979071392560, 96503008028224334771028807273628056037391407459560685791940303889130903300826, 67050454088005224845748627326789053425990922831763041158174139321910165797537, 56354656300386637831392267891729486882144501924180334206591055551662859511145, 108875538744684454340615686969559999736352047181969993978724550037003168200211, 105856150301241056513738964497224079598648612469774416566110150235952602587129, 103072133631485922917570773603973545510240103328265914435430955113182187850847, 105071449786380370702657927006338895312230491406739601631939501577997184496876, 101559564666645844079948496433098525970583827093303201782110972272082979410831, 45696832977481706385123240351386677526237953026854755659089774125668886575190, 92930863035601609905246064160817660898443604755800516139761871009073979122573, 7136157467487063026530735850363136522687472196852313490264738121297870888865, 62220552837071854508303645903133799707167271140998125870619424819338409845248, 71964156627499707284955744986659480338185350890617779236004729406075442337650, 56432954135882530785013240455908855171502152827770214700998108134515682426307, 24818258540494883741910232014072726664585493319546426193565346084848631309292, 68946604449180849807706382163388201284725162066731407078323925073762784383918, 78305860067531640486978712479618549593532447916095131216323237767823095149213, 40019412274222034245452650116905171509558126077504657023971877193155638952620, 6226049816877252622825028481234412013581804081798123571329306780957341285518, 72008834916679466207298598830558721788070004796890262626592503036925690499953, 24120184417962346330989331701326680837413020607663960631051474032512470756250, 106358126840983882959473879360172954895361540456426525458062716824086971706859, 96125062326106069117227627865988038851006615609777159985287487409738006940292, 33054514553432552301350757403482219452773112411443533998213496297361397155535, 41581969631676286214097564630767898944747546622643163224140263014954932195321, 22904365609725269502635057676962583581851475921482302591306344959978794545764, 64290237869656947632842147827818163107378784367086448814380499121557877108860, 30680084243764095315357070546550118749025091482163732007754607769361116153541, 13691292022145271355849518605344621718116294468846185203111794890637243685470, 25132284761110457596793743234989234799586919369754843892751414241493192284491, 12389505381820778753642609476404562621082110924974170017133920070419933455780, 71535924312884292159182314202796515340797288002505186265430063222078901533504, 12742977582401193716850400144097310370558409977576217736024733304490605337769, 75139886864475235332970108571588085544527733256425836467715638485512421268158, 106812400623906721014312287501764424395430875573845869345085033374152396156108, 91345106193584221920864389152087560188260652160092982315871571692181571481755, 65785148879985691725045496265911886841068140761050563941336015575029243383380, 1452703135528066004669796386925101704795733053841911703671961494738444465175, 44818107645190027629062089844645267760294751459286511227307352668787518517867, 26767624780451051554599928370950639364780468287039403780345758419855142782301, 73520682616655688427241752929498638616275480985470608873569998909405046919540]
[11, 14, 12, 1, 13, 15, 1, 14, 12, 12, 15, 6, 2, 15, 13, 15, 6, 6, 11, 12, 2, 9, 3, 15, 0, 14, 10, 10, 13, 10, 6, 13, 6, 9, 0, 4, 9, 0, 15, 5, 2, 13, 12, 12, 5, 11, 3, 3, 12, 13, 5, 5, 14, 15, 12, 10, 9, 6, 8, 5, 8, 4, 12, 1, 15, 1, 14, 11, 11, 14, 6, 10, 6, 3, 14, 10, 10, 14, 5, 15, 6, 4, 13, 1, 5, 4, 7, 4, 13, 7, 0, 14, 6, 7, 2, 14, 1, 14, 6, 9, 14, 4, 13]
'''
# enc
key = x ^ y ^ z
key = long_to_bytes(key)
aes = AES.new(key,mode = AES.MODE_ECB)
print(aes.encrypt(pad(flag,16)))
# b'\xda\xfc\xb7\x93\xfb\x9d\xbe\x82\xb3\xb5\x87`]}\x0b*\xd53AR\x8bb\xfeQ,\xd9\xff\xf6\n\xa2\x1b)H\\\xf24>E\xac+\x01\xf3)F\x8c\xee\xb8j\x18zb\xa8\x8b\xba\xbc\xbb\x03\xbb}\xb6\x8cO#\xeb\x0c\xce\xbd\x07\x8aWP\x90\xf2\xaep\x02\x11{\xdf\xc5'

有两个师傅今天都问到了我这个题目，乍一看是很经典的HNP，但是做的过程中会发现这题没有那么简单，需要做不少优化处理，因此还是写一写。

基本HNP构造格的思路可以参考：

[HNP] 一类基于各种DSA的HNP问题求解 - 知乎 (zhihu.com)

简而言之，题目任务为：

  • 三部分HNP，每部分分别对应一个待求数x、y、z，用x^y^z组成AES密钥并对flag进行加密
  • 第一部分HNP，给了32组数据，泄漏高8位
  • 第二部分HNP，给了33组数据，泄漏低8位
  • 第三部分HNP，给了103组数据，泄漏高四位

那么接下来就逐个部分说明。每部分还是会简单写一写题目内容和其最基本的格构造方法。

泄露高8位

a、b具有如下关系：

然后，题目给出32组ai以及bi的高八位，要求解出x。由于bi只有高八位知道，所以我们把bi拆成以下形式：

为了转化为HNP形式，我们将第i组数据与第0组数据两两作差消除x：

即得到：

ai以及b的高位bhi均为已知值，进行移项：

然后把a0的逆元乘至右侧(注意q是2^256，所以需要选一个逆元存在的当作a0，不过这一题正好a0逆元存在)，即得到HNP形式：

其中：

将模等式展开得到：

因此我们可以构造如下形式的格：

这个格具有如下线性关系：

那么一般来说我们对这个格进行LLL规约就能得到我们的目标向量。但是试一试会发现完全不行，规约出的向量最后一列几乎全为0，而不是我们期望的2^248。

然后我就按照上面参考文章那样，试了试BKZ，结果同样是不乐观的，没有办法得到我们的目标向量。

然后计算格的高斯启发式，会发现数量级与我们的目标向量非常相近，这说明我们的方法并没有错，而是被卡了界。给32、33、103组数据的目的估计就在于此，经过我自己测试，给的数据多几组，BKZ确实是可以得到结果的。

那么接下来就是如何优化这个格，而显然这个格的行列式基本变不了多少，所以不能显著提高其高斯启发式，因此只能从缩短目标向量入手。

而要缩短目标向量，就要改变bhi的数量级，因此我采用的办法是改变最初的拆分策略。最初的拆分策略是：

这样拆分是因为题目给了我们bhi，所以会这么思考也很正常。这样其实也保证了bli是一个正数。而现在需要思考：我们好像不一定需要bhi是一个正数，我们想要的是缩小他的数量级，那么有没有什么拆分方式可以使他的数量级从2^248缩小一些？

所以我采用了如下方式：

此时，用这种拆分去构造格，规约出的向量的每一项就变成了如下的形式：

其预期的平均数量级就成功下降了1比特。事实证明这就是压垮骆驼的最后一根稻草，因为这样我们就能用BKZ算法规约出我们需要的向量了。

当然，我测了几组数据发现目标向量并不一定就在第一行，因此还需要加一个核验。核验思路也很简单，直接用求出的x与给定的32组ai去计算bi高位，看看与题目给的是不是相同即可。

不过我这里应该还是有点小bug的，因为bli-2^247应该有正有负，求x0时需要把两种情况都算一遍，但是既然能出结果我也就不调了，以后遇到再说。

第一部分exp：

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
from Crypto.Util.number import *
from Crypto.Cipher import AES

def check_high(res,A1,B1,q,bits):
    if(res[-1] == 0):
        return False
    
    B0_low = res[-2]
    B0 = B1[0] - B0_low
    x0 = inverse(A1[0],q)*B0 % q

    B_1 = [(i-2^(bits-1)) >> bits  for i in B1] 
    B_2 = [(i*x0 % q) >> bits for i in A1]

    if(B_1 == B_2):
        return True
    else:
        return False

    
#part1 high_8_bits
Round = 32
q = 2 ** 256
A1 = [3561678147813669042672186969104055553515262226168087322052560790885260761433, 17346407693442644010055116546363960164095133759884497841925887458500171929994, 10970839811545507511408260800883769581649579684426188079142754412064502787585, 109417222922540235139013912297145185193443712852193270682885305502867182588403, 88171850234002600580608014259219586239590114856448092326801813245774395730496, 5113619435362108938262679062561727235116615800676783173565082653599747645155, 54576089683044230333058389148818602636893918880220233916359714009830588044131, 46319652232696496987147414399965164805770427009639155019904825551069668519260, 92142202700489403870481152403139465532735056770434774464930082474517829581964, 9084526539780165183228300902059842905058839285187659313361650962576085292818, 89120115360204223476154240731792191817638074392691790750005020564226279037550, 108874944765319253896194176909539011617418473448207058050594223215460183828033, 48697630410338199345605370644643425030874923782845194702123578264330641464094, 90490831141215467713642375752174358047945797806394912036159392371419919773636, 5407847525945777533863763148921176292074562577253075889320641646783216244238, 95326999116234880776873896438659550308182265903511015349887289749187746932743, 13848646478536701368088661040908693291788138011605835864557858216170511016083, 12688154545015600072136788151484672710661959298941783293908174000377900727747, 103416430654164637952330806792686485956010294787748757584715063906414248209722, 36213989454986448247979083323211284869162879484215027121399406834805531673463, 83477199408920970502661396196378764693640078246444907844363833717275362253336, 54685544287120130615023910691215446521783587675140445694155062634358785975223, 57209914633582227771666953772776413914105217956486621477363100169491699389485, 60722705656546434007907580733214759241271810206392571495455413850603913610651, 62666312072142619643565102615355724228875566515181602729719018682721112131326, 17892029370519322177254795109531838575579273633357811419566887056272012019617, 23387537005911727415991488713130020055341902697712259630978747015670850612866, 57084096974333718635810536400151484653413307540676932220675888461543384910791, 64672020284448913361212245534680048800817888816777270292913433441383929287826, 30879668079119218442051482226185849538064516289533962210948424807374221747937, 67805294126621083377517953883639091568886644480832055617022550683600509359637, 80971248361778969534551851802629859076303703583702628504189145200772632698437]
B1 = [185, 121, 74, 192, 66, 208, 189, 5, 248, 216, 222, 49, 199, 122, 212, 109, 36, 135, 9, 43, 94, 192, 67, 176, 165, 34, 241, 27, 255, 216, 71, 156]
for i in range(len(B1)):
    B1[i] = (B1[i]<<248) + 2^247

L1 = Matrix(ZZ,1+len(A1),1+len(A1))
for i in range(len(A1)-1):
    L1[i,i] = q
    L1[-2,i] = inverse(A1[0],q)*A1[i+1]%q
    L1[-1,i] = inverse(A1[0],q)*(B1[0]*A1[i+1]-B1[i+1]*A1[0])%q
L1[-2,-2] = 1
L1[-1,-1] = 2^247

res = L1.BKZ(block_size=16)
for i in res:
    if(check_high(i,A1,B1,q,248) == True):
        B0_low = i[-2]
        B0 = B1[0] - B0_low
        x = inverse(A1[0],q)*B0 % q
        print(x)
        break
print("Part1 Done!")


泄露低8位

与泄漏高八位异曲同工，我们仍然按刚才的方式，消除x转化到HNP。然后也和预期一样，直接LLL或BKZ都出不了，界依然被卡了，所以还是要改变拆分方式。

已知低八位时，正常应该如下拆分：

同样的道理，我们现在规约出来的目标向量的每一项应该是bhi，要想办法降低他的数量级。所以处理手段也基本一样，我们拆成如下形式就好：

最要命的是这样规约依然出不了，但是没想到其他优化方式了，于是就只能不断抬高BKZ算法的blocksize，发现由于格的维数并不高，所以blocksize提高很多也不会有多慢，抬到30后总算是出结果了。

依然也需要核验，不过道理相同，同样也应该会存在bug。

这一部分exp：

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
from Crypto.Util.number import *
from Crypto.Cipher import AES

def check_low(res,A1,B1,q,bits):
    if(res[-1] == 0):
        return False
    
    B0_high = res[-2]
    B0 = 2^bits*B0_high + B1[0]
    x0 = inverse(A1[0],q)*B0 % q

    B_1 = [i-2^255 for i in B1] 
    B_2 = [(i*x0 % q) & ((2^bits)-1) for i in A1]

    if(B_1 == B_2):
        return True
    else:
        return False

    
#part2 low_8_bits
Round = 33
q = 115792089237316195423570985008687907853269984665640564039457584007913129639747
A1 = [46504565744057869379592149118750005180204315285587793650459698458291497313095, 58007957093934046182693035826219870499452741234326847327688846747059237094075, 50185124619087453830679170251457196445767905313509337058697814870412730362947, 13460057838246434192804076595664204927155595158673092664009965681276162112064, 1701081975560116286696366369808334022446618430663926380667987754925635360535, 26884871731419084105623632272724863769910293366201375037286643905133449526668, 86148369125917615329995354501659454507150263427394081644953922899405044908942, 86965847264933041291798488655625963084424620038983026175910367027955449692128, 51359332101276868450990110421905601457823984827989287103931757850844231666586, 48796757902016638482644909388959646721244669665114474829651238484065619118952, 100070448202859232758452766870542683109402601193511866026529530855112793822109, 96580256984898125874774601478072811945116066886633284314860596683569097605765, 38808894076998102467847013020946201384521577320197543440467015636483307894892, 4134554141092625841029701614640247691101835437566908306546904884177729072687, 74873085435488619613395208820994521773265984299598688734149106712561237976724, 15654842239708870234259249156913701671624803564647865424705391694462101457862, 88322093034453332197643606249439750127876581478584569790806716889277489637972, 22499556277754006237442593359493863007223009260764163505327306701416065559119, 67089035688878297307085968283413144678391442218184879365509351597884743967932, 27674630243557284124557851587722479960748242794492773619925160133318279977692, 9119521864491019262790789925266797995577993021425216600126182732190292182948, 101288882073195598657612116292233377922026161322404160341330451374348438098216, 67804446744028818432860934046262550895247933787912806120088242004054790700495, 26086948144209799352019678059923693118044934151861294461002114985645656470189, 38144657569843600236424138168852321656171547769351620499893335164030638528328, 29607623036881080673594862278805535156351844098214001235565521439825687173709, 73322408962909922161031457562287596779866102699954700495813418822123077110802, 71841446787131237842866428647552570448973984694577468650052516966413175250298, 1230436323839997562475731649322922330998915952913300933165504728647309839568, 107223013661981482036189531938571461516528131559156846625598018135279924645933, 40439925178577390217639900040814034803597438472158408491211685077053585300286, 26978587850306490903937574562860250724695533954879823140348556476663322417613, 82195886203427304567763311291077205482622324404366375181470500496565215770146]
B1 = [115, 240, 228, 198, 160, 178, 214, 160, 96, 140, 89, 186, 159, 102, 192, 93, 135, 30, 17, 9, 138, 224, 109, 116, 76, 116, 180, 196, 121, 187, 210, 208, 14]
for i in range(len(B1)):
    B1[i] += 2^255
L1 = Matrix(ZZ,1+len(A1),1+len(A1))
for i in range(len(A1)-1):
    L1[i,i] = q
    L1[-2,i] = inverse(A1[0],q)*A1[i+1]%q
    L1[-1,i] = inverse(A1[0]*2^8,q)*(B1[0]*A1[i+1]-B1[i+1]*A1[0])%q
L1[-2,-2] = 1
L1[-1,-1] = 2^247

res1 = L1.BKZ(block_size=30)
for i in res1:
    if(check_low(i,A1,B1,q,8)):
        B0_high = i[-2]
        B0 = 2^8*B0_high + B1[0]
        y = inverse(A1[0],q)*B0 % q
        print(y)
print("Part2 Done!")


泄露高4位

这一部分和第一部分就没什么差别了，优化手段也是一样，但是blocksize要适当提高，我这里是抬到22后出了结果。而且由于数据也更多，耗时也会相对更久。

这一部分exp：

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
from Crypto.Util.number import *
from Crypto.Cipher import AES

def check_high(res,A1,B1,q,bits):
    if(res[-1] == 0):
        return False
    
    B0_low = res[-2]
    B0 = B1[0] - B0_low
    x0 = inverse(A1[0],q)*B0 % q

    B_1 = [(i-2^(bits-1)) >> bits  for i in B1] 
    B_2 = [(i*x0 % q) >> bits for i in A1]

    if(B_1 == B_2):
        return True
    else:
        return False

    
#part3 high_4_bits
Round = 103
q = 2**256
A1 = [56666422659665306957613341966104139188430887040369382699811066965734652038579, 41608423494025514337106193470276163502869431432921281068110444274310186909892, 95312645577996377489331859379729367791539181995403307071242251663306260824059, 114007089082826788908311397311915638668862713690403097281136795912671634293903, 77470602549297888428039543840134276433567854766634294661906479236200644990851, 67265570384781545307301479187933437206481537999752352862466291209724038113997, 101015220564168271842813302532972922828562060680762307341661161853013181455988, 73596220918173964622453801478597395507613363519777836354319778006747628725943, 80276240092293162850897330969848557221924558822619435206166856373482558821153, 60387041856575123107349887176488814324533329129026453912394888320971261329267, 37588667650535221417005569007639921039223353621264869144904381190769978830432, 30201673227033963823582196954697293400001560479877858941307825349312312395908, 46517796724693810353256110303591718873843585558937781709113232176049614134229, 110476911183528409932385631377040635032167229294859921626233104995069707326026, 33913880276956766352570275848477001195330941450588079882929631222080051897977, 108738411950576541236703456832793461013595057668683247592686862598082364613770, 87211442745029489881514515811064102429019356351722823450170249465088775249507, 39600946693670273230261533720839589755726946308581706825676138619972092199256, 4979886914346369664911891403751631037886315717549974065878536283157637402320, 22272529908653383795002294860870129574984518813560375272257703512940569602004, 100135751785995415247695765442899140606914076750888419237400306294448451415863, 85613534858376605408667291532701284666560850915689941354202786014968649139457, 38496246133430733988750968353732662162312705079114417415163071485082991344590, 55980481790171446152748793757788577465044360548729573345122559743628093363153, 71280277172994137969689292719624075379102489317199533126561191722460505314026, 110446223482446943024326135434573497276437669060614612856002207641927747194266, 16456085922385532110267651711339329146652084370610067373716816178321924748791, 101653629730678493695114228522885120593522618541788967122785214737946157867999, 74467527492811608068163160348674720595757862332879609098404557441577413104820, 41884843126443673947662657085537596879702074001592844509379139860812151553968, 29815687077578101251522932333124915023192910276895021601688368611558697857638, 44840628789800333625015337751638405696233468515566263356197320268202190223769, 102427595787595418722722430130631701884337456325150921017413824991597185452849, 2975107125099035075044003816426206055437890428466365543585422202932381886186, 94699511483779321185024950255977801474453881858185354369860946591141828290326, 31810607567540037649472765223870019465281477418301020106850480432511306591757, 75713781109794200255529510371465092460190607870508383754795316160075282283862, 55429849762380955520557448208384572772400405309708977900727750338226215580736, 71351843550447097631722656769410630908972124288367169285559142896305583201390, 84145371680533342029399999651802676680665442500082991947093355443249540103162, 18059328520840928370924328960454198116073475240703647573736616851363995779497, 83839387396741626377342400188482404639827411621171844172874897800772466334269, 25788978353065311499638204532308969267343091396798096623404684254370926606489, 46416171203559401945669998573205329748734005210989064607057470628982156110053, 42839223735347899899704913105525407073907314464785013094063759450820513757342, 88826657766811054515837039931572449230721258604658317309512814974116100196733, 53796508595019468595537500010909399217450133587528313928622717009905225347437, 56531378551320964008977461547054273860909442858252049481923559030063639435057, 48217679285988263588226655808041000825638438349841115697751615792350031644869, 64424297190010710116212288045994884168253983939992794298642423963632550451160, 46474911280506479688705284230861217499981118516937627597481370505066926962182, 64032029526907010327735757773865326038078238679652707012855320952596919166618, 5529383900219431454017233184818428510888383480088262580036064976358985800985, 69322608357555546086372761692837205200171798855109065251575534608627560525776, 76098979682650954216202311601813089916970156784884278240596741668163729505020, 91674126062289237651839995587104059408995800143522837051179562018281051100557, 90571390404208688843585603192800843878382529323359914123528861146103857760661, 72012664155317843790423022518639753138262519729890141457716216773019826138388, 66863180243825712563555363518892364864799935770917594234609418534062748300787, 5838945753982677965177087293687053018953448675487050703226841119623778529018, 4440280122867898274880560103713163505203269339591832639427292037957483435863, 113585052040012311817152621651926546174704034369418207806360593735979071392560, 96503008028224334771028807273628056037391407459560685791940303889130903300826, 67050454088005224845748627326789053425990922831763041158174139321910165797537, 56354656300386637831392267891729486882144501924180334206591055551662859511145, 108875538744684454340615686969559999736352047181969993978724550037003168200211, 105856150301241056513738964497224079598648612469774416566110150235952602587129, 103072133631485922917570773603973545510240103328265914435430955113182187850847, 105071449786380370702657927006338895312230491406739601631939501577997184496876, 101559564666645844079948496433098525970583827093303201782110972272082979410831, 45696832977481706385123240351386677526237953026854755659089774125668886575190, 92930863035601609905246064160817660898443604755800516139761871009073979122573, 7136157467487063026530735850363136522687472196852313490264738121297870888865, 62220552837071854508303645903133799707167271140998125870619424819338409845248, 71964156627499707284955744986659480338185350890617779236004729406075442337650, 56432954135882530785013240455908855171502152827770214700998108134515682426307, 24818258540494883741910232014072726664585493319546426193565346084848631309292, 68946604449180849807706382163388201284725162066731407078323925073762784383918, 78305860067531640486978712479618549593532447916095131216323237767823095149213, 40019412274222034245452650116905171509558126077504657023971877193155638952620, 6226049816877252622825028481234412013581804081798123571329306780957341285518, 72008834916679466207298598830558721788070004796890262626592503036925690499953, 24120184417962346330989331701326680837413020607663960631051474032512470756250, 106358126840983882959473879360172954895361540456426525458062716824086971706859, 96125062326106069117227627865988038851006615609777159985287487409738006940292, 33054514553432552301350757403482219452773112411443533998213496297361397155535, 41581969631676286214097564630767898944747546622643163224140263014954932195321, 22904365609725269502635057676962583581851475921482302591306344959978794545764, 64290237869656947632842147827818163107378784367086448814380499121557877108860, 30680084243764095315357070546550118749025091482163732007754607769361116153541, 13691292022145271355849518605344621718116294468846185203111794890637243685470, 25132284761110457596793743234989234799586919369754843892751414241493192284491, 12389505381820778753642609476404562621082110924974170017133920070419933455780, 71535924312884292159182314202796515340797288002505186265430063222078901533504, 12742977582401193716850400144097310370558409977576217736024733304490605337769, 75139886864475235332970108571588085544527733256425836467715638485512421268158, 106812400623906721014312287501764424395430875573845869345085033374152396156108, 91345106193584221920864389152087560188260652160092982315871571692181571481755, 65785148879985691725045496265911886841068140761050563941336015575029243383380, 1452703135528066004669796386925101704795733053841911703671961494738444465175, 44818107645190027629062089844645267760294751459286511227307352668787518517867, 26767624780451051554599928370950639364780468287039403780345758419855142782301, 73520682616655688427241752929498638616275480985470608873569998909405046919540]
B1 = [11, 14, 12, 1, 13, 15, 1, 14, 12, 12, 15, 6, 2, 15, 13, 15, 6, 6, 11, 12, 2, 9, 3, 15, 0, 14, 10, 10, 13, 10, 6, 13, 6, 9, 0, 4, 9, 0, 15, 5, 2, 13, 12, 12, 5, 11, 3, 3, 12, 13, 5, 5, 14, 15, 12, 10, 9, 6, 8, 5, 8, 4, 12, 1, 15, 1, 14, 11, 11, 14, 6, 10, 6, 3, 14, 10, 10, 14, 5, 15, 6, 4, 13, 1, 5, 4, 7, 4, 13, 7, 0, 14, 6, 7, 2, 14, 1, 14, 6, 9, 14, 4, 13]
for i in range(len(B1)):
    B1[i] = (B1[i]<<252) + 2^251

L1 = Matrix(ZZ,1+len(A1),1+len(A1))
for i in range(len(A1)-1):
    L1[i,i] = q
    L1[-2,i] = inverse(A1[0],q)*A1[i+1]%q
    L1[-1,i] = inverse(A1[0],q)*(B1[0]*A1[i+1]-B1[i+1]*A1[0])%q
L1[-2,-2] = 1
L1[-1,-1] = 2^251

res = L1.BKZ(block_size=22)
for i in res:
    if(check_high(i,A1,B1,q,252) == True):
        B0_low = i[-2]
        B0 = B1[0] - B0_low
        z = inverse(A1[0],q)*B0 % q
        print(z)
        break
print("Part3 Done!")


完整exp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
from Crypto.Util.number import *
from Crypto.Cipher import AES
from gmpy2 import *
import math

def guass_Heuristic(L):
    n = L.nrows()
    efficient = (n/(2*math.pi*math.e))**(0.5)
    return int(efficient*iroot(abs(L.det()),n)[0])

def check_high(res,A1,B1,q,bits):
    if(res[-1] == 0):
        return False
    
    B0_low = res[-2]
    B0 = B1[0] - B0_low
    x0 = inverse(A1[0],q)*B0 % q

    B_1 = [(i-2^(bits-1)) >> bits  for i in B1] 
    B_2 = [(i*x0 % q) >> bits for i in A1]

    if(B_1 == B_2):
        return True
    else:
        return False

def check_low(res,A1,B1,q,bits):
    if(res[-1] == 0):
        return False
    
    B0_high = res[-2]
    B0 = 2^bits*B0_high + B1[0]
    x0 = inverse(A1[0],q)*B0 % q

    B_1 = [i-2^255 for i in B1] 
    B_2 = [(i*x0 % q) & ((2^bits)-1) for i in A1]

    if(B_1 == B_2):
        return True
    else:
        return False
    
#part1 high_8_bits
Round = 32
q = 2 ** 256
A1 = [3561678147813669042672186969104055553515262226168087322052560790885260761433, 17346407693442644010055116546363960164095133759884497841925887458500171929994, 10970839811545507511408260800883769581649579684426188079142754412064502787585, 109417222922540235139013912297145185193443712852193270682885305502867182588403, 88171850234002600580608014259219586239590114856448092326801813245774395730496, 5113619435362108938262679062561727235116615800676783173565082653599747645155, 54576089683044230333058389148818602636893918880220233916359714009830588044131, 46319652232696496987147414399965164805770427009639155019904825551069668519260, 92142202700489403870481152403139465532735056770434774464930082474517829581964, 9084526539780165183228300902059842905058839285187659313361650962576085292818, 89120115360204223476154240731792191817638074392691790750005020564226279037550, 108874944765319253896194176909539011617418473448207058050594223215460183828033, 48697630410338199345605370644643425030874923782845194702123578264330641464094, 90490831141215467713642375752174358047945797806394912036159392371419919773636, 5407847525945777533863763148921176292074562577253075889320641646783216244238, 95326999116234880776873896438659550308182265903511015349887289749187746932743, 13848646478536701368088661040908693291788138011605835864557858216170511016083, 12688154545015600072136788151484672710661959298941783293908174000377900727747, 103416430654164637952330806792686485956010294787748757584715063906414248209722, 36213989454986448247979083323211284869162879484215027121399406834805531673463, 83477199408920970502661396196378764693640078246444907844363833717275362253336, 54685544287120130615023910691215446521783587675140445694155062634358785975223, 57209914633582227771666953772776413914105217956486621477363100169491699389485, 60722705656546434007907580733214759241271810206392571495455413850603913610651, 62666312072142619643565102615355724228875566515181602729719018682721112131326, 17892029370519322177254795109531838575579273633357811419566887056272012019617, 23387537005911727415991488713130020055341902697712259630978747015670850612866, 57084096974333718635810536400151484653413307540676932220675888461543384910791, 64672020284448913361212245534680048800817888816777270292913433441383929287826, 30879668079119218442051482226185849538064516289533962210948424807374221747937, 67805294126621083377517953883639091568886644480832055617022550683600509359637, 80971248361778969534551851802629859076303703583702628504189145200772632698437]
B1 = [185, 121, 74, 192, 66, 208, 189, 5, 248, 216, 222, 49, 199, 122, 212, 109, 36, 135, 9, 43, 94, 192, 67, 176, 165, 34, 241, 27, 255, 216, 71, 156]
for i in range(len(B1)):
    B1[i] = (B1[i]<<248) + 2^247

L1 = Matrix(ZZ,1+len(A1),1+len(A1))
for i in range(len(A1)-1):
    L1[i,i] = q
    L1[-2,i] = inverse(A1[0],q)*A1[i+1]%q
    L1[-1,i] = inverse(A1[0],q)*(B1[0]*A1[i+1]-B1[i+1]*A1[0])%q
L1[-2,-2] = 1
L1[-1,-1] = 2^247

res = L1.BKZ(block_size=16)
for i in res:
    if(check_high(i,A1,B1,q,248) == True):
        B0_low = i[-2]
        B0 = B1[0] - B0_low
        x = inverse(A1[0],q)*B0 % q
        print(x)
        break
print("Part1 Done!")


#part2 low_8_bits
Round = 33
q = 115792089237316195423570985008687907853269984665640564039457584007913129639747
A1 = [46504565744057869379592149118750005180204315285587793650459698458291497313095, 58007957093934046182693035826219870499452741234326847327688846747059237094075, 50185124619087453830679170251457196445767905313509337058697814870412730362947, 13460057838246434192804076595664204927155595158673092664009965681276162112064, 1701081975560116286696366369808334022446618430663926380667987754925635360535, 26884871731419084105623632272724863769910293366201375037286643905133449526668, 86148369125917615329995354501659454507150263427394081644953922899405044908942, 86965847264933041291798488655625963084424620038983026175910367027955449692128, 51359332101276868450990110421905601457823984827989287103931757850844231666586, 48796757902016638482644909388959646721244669665114474829651238484065619118952, 100070448202859232758452766870542683109402601193511866026529530855112793822109, 96580256984898125874774601478072811945116066886633284314860596683569097605765, 38808894076998102467847013020946201384521577320197543440467015636483307894892, 4134554141092625841029701614640247691101835437566908306546904884177729072687, 74873085435488619613395208820994521773265984299598688734149106712561237976724, 15654842239708870234259249156913701671624803564647865424705391694462101457862, 88322093034453332197643606249439750127876581478584569790806716889277489637972, 22499556277754006237442593359493863007223009260764163505327306701416065559119, 67089035688878297307085968283413144678391442218184879365509351597884743967932, 27674630243557284124557851587722479960748242794492773619925160133318279977692, 9119521864491019262790789925266797995577993021425216600126182732190292182948, 101288882073195598657612116292233377922026161322404160341330451374348438098216, 67804446744028818432860934046262550895247933787912806120088242004054790700495, 26086948144209799352019678059923693118044934151861294461002114985645656470189, 38144657569843600236424138168852321656171547769351620499893335164030638528328, 29607623036881080673594862278805535156351844098214001235565521439825687173709, 73322408962909922161031457562287596779866102699954700495813418822123077110802, 71841446787131237842866428647552570448973984694577468650052516966413175250298, 1230436323839997562475731649322922330998915952913300933165504728647309839568, 107223013661981482036189531938571461516528131559156846625598018135279924645933, 40439925178577390217639900040814034803597438472158408491211685077053585300286, 26978587850306490903937574562860250724695533954879823140348556476663322417613, 82195886203427304567763311291077205482622324404366375181470500496565215770146]
B1 = [115, 240, 228, 198, 160, 178, 214, 160, 96, 140, 89, 186, 159, 102, 192, 93, 135, 30, 17, 9, 138, 224, 109, 116, 76, 116, 180, 196, 121, 187, 210, 208, 14]
for i in range(len(B1)):
    B1[i] += 2^255
L1 = Matrix(ZZ,1+len(A1),1+len(A1))
for i in range(len(A1)-1):
    L1[i,i] = q
    L1[-2,i] = inverse(A1[0],q)*A1[i+1]%q
    L1[-1,i] = inverse(A1[0]*2^8,q)*(B1[0]*A1[i+1]-B1[i+1]*A1[0])%q
L1[-2,-2] = 1
L1[-1,-1] = 2^247

res1 = L1.BKZ(block_size=30)
for i in res1:
    if(check_low(i,A1,B1,q,8)):
        B0_high = i[-2]
        B0 = 2^8*B0_high + B1[0]
        y = inverse(A1[0],q)*B0 % q
        print(y)
print("Part2 Done!")


#part3 high_4_bits
Round = 103
q = 2**256
A1 = [56666422659665306957613341966104139188430887040369382699811066965734652038579, 41608423494025514337106193470276163502869431432921281068110444274310186909892, 95312645577996377489331859379729367791539181995403307071242251663306260824059, 114007089082826788908311397311915638668862713690403097281136795912671634293903, 77470602549297888428039543840134276433567854766634294661906479236200644990851, 67265570384781545307301479187933437206481537999752352862466291209724038113997, 101015220564168271842813302532972922828562060680762307341661161853013181455988, 73596220918173964622453801478597395507613363519777836354319778006747628725943, 80276240092293162850897330969848557221924558822619435206166856373482558821153, 60387041856575123107349887176488814324533329129026453912394888320971261329267, 37588667650535221417005569007639921039223353621264869144904381190769978830432, 30201673227033963823582196954697293400001560479877858941307825349312312395908, 46517796724693810353256110303591718873843585558937781709113232176049614134229, 110476911183528409932385631377040635032167229294859921626233104995069707326026, 33913880276956766352570275848477001195330941450588079882929631222080051897977, 108738411950576541236703456832793461013595057668683247592686862598082364613770, 87211442745029489881514515811064102429019356351722823450170249465088775249507, 39600946693670273230261533720839589755726946308581706825676138619972092199256, 4979886914346369664911891403751631037886315717549974065878536283157637402320, 22272529908653383795002294860870129574984518813560375272257703512940569602004, 100135751785995415247695765442899140606914076750888419237400306294448451415863, 85613534858376605408667291532701284666560850915689941354202786014968649139457, 38496246133430733988750968353732662162312705079114417415163071485082991344590, 55980481790171446152748793757788577465044360548729573345122559743628093363153, 71280277172994137969689292719624075379102489317199533126561191722460505314026, 110446223482446943024326135434573497276437669060614612856002207641927747194266, 16456085922385532110267651711339329146652084370610067373716816178321924748791, 101653629730678493695114228522885120593522618541788967122785214737946157867999, 74467527492811608068163160348674720595757862332879609098404557441577413104820, 41884843126443673947662657085537596879702074001592844509379139860812151553968, 29815687077578101251522932333124915023192910276895021601688368611558697857638, 44840628789800333625015337751638405696233468515566263356197320268202190223769, 102427595787595418722722430130631701884337456325150921017413824991597185452849, 2975107125099035075044003816426206055437890428466365543585422202932381886186, 94699511483779321185024950255977801474453881858185354369860946591141828290326, 31810607567540037649472765223870019465281477418301020106850480432511306591757, 75713781109794200255529510371465092460190607870508383754795316160075282283862, 55429849762380955520557448208384572772400405309708977900727750338226215580736, 71351843550447097631722656769410630908972124288367169285559142896305583201390, 84145371680533342029399999651802676680665442500082991947093355443249540103162, 18059328520840928370924328960454198116073475240703647573736616851363995779497, 83839387396741626377342400188482404639827411621171844172874897800772466334269, 25788978353065311499638204532308969267343091396798096623404684254370926606489, 46416171203559401945669998573205329748734005210989064607057470628982156110053, 42839223735347899899704913105525407073907314464785013094063759450820513757342, 88826657766811054515837039931572449230721258604658317309512814974116100196733, 53796508595019468595537500010909399217450133587528313928622717009905225347437, 56531378551320964008977461547054273860909442858252049481923559030063639435057, 48217679285988263588226655808041000825638438349841115697751615792350031644869, 64424297190010710116212288045994884168253983939992794298642423963632550451160, 46474911280506479688705284230861217499981118516937627597481370505066926962182, 64032029526907010327735757773865326038078238679652707012855320952596919166618, 5529383900219431454017233184818428510888383480088262580036064976358985800985, 69322608357555546086372761692837205200171798855109065251575534608627560525776, 76098979682650954216202311601813089916970156784884278240596741668163729505020, 91674126062289237651839995587104059408995800143522837051179562018281051100557, 90571390404208688843585603192800843878382529323359914123528861146103857760661, 72012664155317843790423022518639753138262519729890141457716216773019826138388, 66863180243825712563555363518892364864799935770917594234609418534062748300787, 5838945753982677965177087293687053018953448675487050703226841119623778529018, 4440280122867898274880560103713163505203269339591832639427292037957483435863, 113585052040012311817152621651926546174704034369418207806360593735979071392560, 96503008028224334771028807273628056037391407459560685791940303889130903300826, 67050454088005224845748627326789053425990922831763041158174139321910165797537, 56354656300386637831392267891729486882144501924180334206591055551662859511145, 108875538744684454340615686969559999736352047181969993978724550037003168200211, 105856150301241056513738964497224079598648612469774416566110150235952602587129, 103072133631485922917570773603973545510240103328265914435430955113182187850847, 105071449786380370702657927006338895312230491406739601631939501577997184496876, 101559564666645844079948496433098525970583827093303201782110972272082979410831, 45696832977481706385123240351386677526237953026854755659089774125668886575190, 92930863035601609905246064160817660898443604755800516139761871009073979122573, 7136157467487063026530735850363136522687472196852313490264738121297870888865, 62220552837071854508303645903133799707167271140998125870619424819338409845248, 71964156627499707284955744986659480338185350890617779236004729406075442337650, 56432954135882530785013240455908855171502152827770214700998108134515682426307, 24818258540494883741910232014072726664585493319546426193565346084848631309292, 68946604449180849807706382163388201284725162066731407078323925073762784383918, 78305860067531640486978712479618549593532447916095131216323237767823095149213, 40019412274222034245452650116905171509558126077504657023971877193155638952620, 6226049816877252622825028481234412013581804081798123571329306780957341285518, 72008834916679466207298598830558721788070004796890262626592503036925690499953, 24120184417962346330989331701326680837413020607663960631051474032512470756250, 106358126840983882959473879360172954895361540456426525458062716824086971706859, 96125062326106069117227627865988038851006615609777159985287487409738006940292, 33054514553432552301350757403482219452773112411443533998213496297361397155535, 41581969631676286214097564630767898944747546622643163224140263014954932195321, 22904365609725269502635057676962583581851475921482302591306344959978794545764, 64290237869656947632842147827818163107378784367086448814380499121557877108860, 30680084243764095315357070546550118749025091482163732007754607769361116153541, 13691292022145271355849518605344621718116294468846185203111794890637243685470, 25132284761110457596793743234989234799586919369754843892751414241493192284491, 12389505381820778753642609476404562621082110924974170017133920070419933455780, 71535924312884292159182314202796515340797288002505186265430063222078901533504, 12742977582401193716850400144097310370558409977576217736024733304490605337769, 75139886864475235332970108571588085544527733256425836467715638485512421268158, 106812400623906721014312287501764424395430875573845869345085033374152396156108, 91345106193584221920864389152087560188260652160092982315871571692181571481755, 65785148879985691725045496265911886841068140761050563941336015575029243383380, 1452703135528066004669796386925101704795733053841911703671961494738444465175, 44818107645190027629062089844645267760294751459286511227307352668787518517867, 26767624780451051554599928370950639364780468287039403780345758419855142782301, 73520682616655688427241752929498638616275480985470608873569998909405046919540]
B1 = [11, 14, 12, 1, 13, 15, 1, 14, 12, 12, 15, 6, 2, 15, 13, 15, 6, 6, 11, 12, 2, 9, 3, 15, 0, 14, 10, 10, 13, 10, 6, 13, 6, 9, 0, 4, 9, 0, 15, 5, 2, 13, 12, 12, 5, 11, 3, 3, 12, 13, 5, 5, 14, 15, 12, 10, 9, 6, 8, 5, 8, 4, 12, 1, 15, 1, 14, 11, 11, 14, 6, 10, 6, 3, 14, 10, 10, 14, 5, 15, 6, 4, 13, 1, 5, 4, 7, 4, 13, 7, 0, 14, 6, 7, 2, 14, 1, 14, 6, 9, 14, 4, 13]
for i in range(len(B1)):
    B1[i] = (B1[i]<<252) + 2^251

L1 = Matrix(ZZ,1+len(A1),1+len(A1))
for i in range(len(A1)-1):
    L1[i,i] = q
    L1[-2,i] = inverse(A1[0],q)*A1[i+1]%q
    L1[-1,i] = inverse(A1[0],q)*(B1[0]*A1[i+1]-B1[i+1]*A1[0])%q
L1[-2,-2] = 1
L1[-1,-1] = 2^251

res = L1.BKZ(block_size=22)
for i in res:
    if(check_high(i,A1,B1,q,252) == True):
        B0_low = i[-2]
        B0 = B1[0] - B0_low
        z = inverse(A1[0],q)*B0 % q
        print(z)
        break
print("Part3 Done!")


#part4 getflag
enc = b'\xda\xfc\xb7\x93\xfb\x9d\xbe\x82\xb3\xb5\x87`]}\x0b*\xd53AR\x8bb\xfeQ,\xd9\xff\xf6\n\xa2\x1b)H\\\xf24>E\xac+\x01\xf3)F\x8c\xee\xb8j\x18zb\xa8\x8b\xba\xbc\xbb\x03\xbb}\xb6\x8cO#\xeb\x0c\xce\xbd\x07\x8aWP\x90\xf2\xaep\x02\x11{\xdf\xc5'
key = x ^^ y ^^ z
key = long_to_bytes(key)
aes = AES.new(key,mode = AES.MODE_ECB)
print(aes.decrypt(enc))

#flag{Even_jus7_le4k_l1ttle_B1ts_We_CAN_Sovle_The_H1dd3n_Numb3r_Pr0blem}



pack

题目来源：JQCTF 2023

题目描述：

1
hint:实测LLL后剔除不满足向量再做BKZ效果有提升

题目：

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
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)))

output较长这里不放出，需要的师傅可以找我要或者去NSSCTF上下载附件。

简单阐述一下题目内容：

  • 将flag转化为二进制序列，并将长度补齐至8的整数倍
  • 对flag的二进制序列进行两次如下加密

每一次加密的具体加密流程为：

1.先进行pack

  • 随机生成长度为127的列表a，每一个元素为256bit的素数
  • 随机生成长度为128的列表s，每一个元素为-1或1
  • 通过计算a的最后一个元素，来保证a和s列表具有如下关系：
  • 返回a和s列表，用于epack加密

2.进行epack

epack在这里我认为就是error-pack的意思，具体来说，他将flag的二进制序列当作error，然后按如下流程加密：

  • 先将pack得到的列表s转换成01列表s1，具体为：-1->0，1->1
  • 将s1与error逐比特异或得到s2
  • 最后一步就是个普通的01背包

然后，题目提供给我们两次加密的列表a1、a2，和对应的子集和sum1、sum2，需要我们还原error。

首先这个背包的密度只有0.5左右，因此我觉得可以直接LLL求解出两次的s2，但是事实上不行。(这是我直到做完这个题目也没有想通的一点，密度这么小为什么不行？开始觉得可能是因为a的最后一个元素是负数的缘故，但自己生成了几组全是正数的数据也规约不出来。)

然后就照着题目提示尝试了一下先LLL再BKZ(如果目标向量够短，这肯定是可行的，因为这实际上就是在LLL得到的一组格基中，继续用BKZ寻找更短的格基)，但是block_size提升到24也出不来结果，提升到26又一直跑不完，太慢了，但是按照题目提示来说肯定就是这个方法没错，因此要么就是继续硬跑更大的block_size，要么就是做一点格的优化。

因此我用上了一个我之前考虑过的优化背包格的方法，正常来说背包格是如下形式：

对这个格，01向量s满足下式：

目标向量也是0、1向量，虽然是短向量，但是它内部的数量级在这个小范围内其实并不相当(0是0bit，1是1bit)。而我们可以改变格为如下形式：

对于同一个0、1向量s，线性关系变成了：

而此时，s’是一个由-1，1组成的向量，因此数量级相当，更有利于对目标向量的规约。事实上改成这样后，LLL+block_size=24的BKZ就可以规约出两次epack用的s2了。

有了两个s2后，要解出error可能有以下两个方向：

  • 想办法解出两个s，然后与对应s2异或即得到error
  • 直接规约出error

对于第一个方向，实际上跟刚才的背包差不多，区别在于s本身就是个由-1、1组成的向量，因此格可以直接用最原始的背包格去掉最后一行就好，然后依然LLL+block_size=24的BKZ莽使一波——并没有想要的结果。

那么就走第二个路子：直接规约出error。而对于error我们有如下信息可用，首先是两组：

然后我们知道，s到s1经历了如下变换：

那么代入原式就有：

而对于s1，我们又知道：

因此有：

那么继续代入求和式：

由于s2、error都是按比特取值，所以一共只有四种组合，很轻松就能找到一个同态来把异或运算同态到乘法：

然后把这个式子组合一下：

这就又变成了一个背包问题，但是加密了两次，就对2errori-1组成的向量有两组约束，因此可以写到同一个格中进行规约，规约出2errori-1后，将-1，1组成的向量映射回01向量就好。

然后需要注意的是规约出的向量与本身目标向量的正负可能是相反的，因此把两种情况都考虑到更好(de一次bug太久了)。

exp：

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
from Crypto.Util.number import *
from pack_output import *

#part1 get epack's s1,s2
def mapping(vec):
    n = len(vec)
    temp = vector(ZZ,n)
    for i in range(n):
        temp[i] = (vec[i] + 1) // 2
    return temp

def check(vec):
    for i in vec:
        if(i != -1 and i != 1):
            return False
    return True

def pack_reduction(L):
    res = L.LLL()[:-1]
    res = res.BKZ(block_size=24)[0]
    return res

def epack(a,sum,n):
    K = 2^100
    L = Matrix(ZZ, n+1, n+1)
    for i in range(n):
        L[i,i] = 2
        L[i,-1] = K*a[i]
        L[-1,i] = -1
    L[-1,-1] = -K*sum

    res = pack_reduction(L)[:-1]
    if(check(res)):
        return mapping(res)

dim = 128
epack_s1 = epack(a1,sum1,dim)
epack_s2 = epack(a2,sum2,dim)


#part2 get pack's error
K = 2^100
L = Matrix(ZZ,dim,dim+2)
for i in range(dim):
    L[i,i] = 1
    L[i,-2] = K*(2*epack_s1[i]-1)*a1[i]
    L[i,-1] = K*(2*epack_s2[i]-1)*a2[i]
res = pack_reduction(L)[:-2]
res = mapping(res)
flag = ""
for i in res:
    if(i == 1):
        flag += "0"
    else:
        flag += "1"
print(long_to_bytes(int(flag,2)))

#flag{n0is3_41way5_bad}



Lattice

题目来源：强网杯 2022

题目：

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
from sage.modules.free_module_integer import IntegerLattice
from Crypto.Cipher import AES
from base64 import b64encode
from hashlib import *
from secret import flag
import signal

n = 75
m = 150
r = 10
N = 126633165554229521438977290762059361297987250739820462036000284719563379254544315991201997343356439034674007770120263341747898897565056619503383631412169301973302667340133958109

def gen(n, m, r, N):
    t1 = [ZZ.random_element(-2^15, 2^15) for _ in range(n*m)]
    t2 = [ZZ.random_element(N) for _ in range(r*n)]
    B = matrix(ZZ, n, m, t1)
    L = IntegerLattice(B)
    A = matrix(ZZ, r, n, t2)
    C = (A * B) % N
    return L, C

def pad(s):
    return s + (16 - len(s) % 16) * b"\x00"

signal.alarm(60)
token = input("team token:").strip().encode()
L, C = gen(n, m, r, N)
print(C)
key = sha256(str(L.reduced_basis[0]).encode()).digest()
aes = AES.new(key, AES.MODE_ECB)
ct = b64encode(aes.encrypt(pad(flag))).decode()
print(ct)

题目基于如下一个矩阵等式：

其中，A是一个由小于N的随机数组成的矩阵，B是一个-2^15到2^15的随机数组成的矩阵。题目用矩阵B进行LLL后的第一行当作AES密钥加密flag，并给出密文和矩阵C，要求还原flag。

先说结论：这是一个比较典型的正交格攻击(Orthogonal Lattice Attack)，在当时应该是一篇论文题，论文为：

461.pdf (iacr.org)

不过他的核心思路还是能够理解的，这里就介绍一下。

首先，由于矩阵B本身元素就很小，再LLL一遍第一行应该会更小，所以是有希望用格找到他的。首先转置一下得到：

然后假设可以找到这样一个矩阵M，使得他和C^T正交，也就是：

那么对于原式就会有：

再转置回来就有：

那么B的向量应该都在M^T的左核空间中，且由于B中向量都较短，所以对左核空间的基向量进行规约就有机会能找到B了。

而为了找到这样的M，方式就是构造一个如下形式的格：

那么对于满足如下条件的m向量：

那么这样的m向量就在M中。论文也提到了这样预期规约出的前m-n-1行会是需要的向量，不过感觉理论上来说B^T的左核会有m-n个向量，事实上也有m-n个向量符合条件。

找到这样的M矩阵后对其转置矩阵M^T求左核后LLL，其第一行也就是矩阵B进行LLL后的第一行，然后分正负两个情况去尝试解密AES得到flag就好。

不过实际操作会发现，sage求左核真的有点慢，而细想一下我们其实也就是想找到短向量b使得bM^T=0而已，所以依然可以用前一个格来解决，只是需要在最后一些列配上一个大系数(一般配N就合适)。这样就一分钟之内就能搞定。

同时，由于M和B都是小量，所以模不模N其实没差，因此最后的格还可以优化掉一些行，进一步减少耗时，虽然减少的并不多。

规约出来不是需要的向量也是正常的，多来几次就好。

exp：

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
from Crypto.Util.number import *
from Pwn4Sage.pwn import *
from Crypto.Cipher import AES
from base64 import *
from hashlib import sha256,sha1

sh = remote("node4.anna.nssctf.cn", 28571)
sh.sendline(b"token")

n = 75
m = 150
r = 10
N = 126633165554229521438977290762059361297987250739820462036000284719563379254544315991201997343356439034674007770120263341747898897565056619503383631412169301973302667340133958109

#part1 handle the data
C = [[0 for i in range(m)] for i in range(r)]
for i in range(r):
    temp = sh.recvline().strip().decode()[1:-1].split(" ")
    for k in range(len(temp)-1,-1,-1):
        if temp[k] == '':
            temp.remove('')
    for j in range(m):
        C[i][j] = int(temp[j])
C = Matrix(ZZ,C)
enc = b64decode(sh.recvline().strip().decode())


#part2 get M satisfying MC = 0 % N
L = block_matrix(
    [
        [identity_matrix(m),C.T],
        [matrix.zero(r,m),identity_matrix(r)*N]
    ]
)
res = L.LLL()

M = []
for i in res:
    if(all(j == 0 for j in i[-r:])):
        M.append(i[:-r])
    else:
        break
M = Matrix(ZZ,M)
MT = Matrix(ZZ,M).T


#part3 get B.LLL()[0]
L = block_matrix(
    [
        [identity_matrix(m),MT*N],
        #[matrix.zero(n,m),identity_matrix(n)*N*N]  no need of these rows cause B and M both short
    ]
)
res = L.LLL()[0][:m]


#part3 decrypt the message and get flag
key1 = sha256(str(res).encode()).digest()
key2 = sha256(str(-res).encode()).digest()
aes = AES.new(key1, AES.MODE_ECB)
print(aes.decrypt(enc))
aes = AES.new(key2, AES.MODE_ECB)
print(aes.decrypt(enc))


#NSSCTF{c6678b20-be7a-4792-af76-6c4da9a95102}



crys

题目来源：强网杯 2022

题目：

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
import hashlib

flag = open("flag.txt","rb").read()
assert len(flag) == 32

def gpp(eta,etamin=256):
  if eta<=(2*etamin):
    return random_prime(2^eta,False,2^(eta-1))
  else:
    return random_prime(2^etamin,False,2^(etamin-1))*gpp(eta-etamin)
    
p = 2*gpp(3217)+1
while p not in Primes():
    p = 2*gpp(3217)+1 
g=Zmod(p)(4)
padding=randint(0,2^3217)
x=Zmod((p-1)//2)(int.from_bytes(flag,'big')^^padding)
y=g^x
# Fast RNG Init
a, b = [], []
for i in range(168):
    a.append(randint(1,(p-1)//2))
    b.append(g^a[i])

output = open("output.txt","w")
for i in range(14500):
    r = 1
    k = 0
    for j in range(168):
        if randint(0,1):
            r*=b[j]
            k+=a[j]
    e = int(hashlib.sha256(f"c{r}ys".encode()).hexdigest(), 16)
    s = k - x*e
    assert e == int(hashlib.sha256(f"c{g^s*y^e}ys".encode()).hexdigest(), 16)
    print(s, e, file=output)

print(p, y, padding, file=output)

题目首先生成一个3217bit数量级的素数p，使得它是2t+1的形式，其中t是一个难以分解的合数(这样做的目的应该是难以求模p下的DLP)。然后题目生成了一个2^3217以内的padding，并将其与flag异或，并模(p-1)//2得到x，在下文为了方便表示，把(p-1)//2记作q。

之后题目做的事情就比较奇怪了，首先取g=4作为底数，然后生成两个长为168的列表a、b。其中，a中元素ai是小于q的随机数，b是模p下g的对应ai次幂。之后进行了14500次操作，这一过程可以写成矩阵形式：

其中k又可以写为：

X是一个仅由0、1组成的矩阵。那么整个式子就可以写作：

后面的assert其实并不重要，这也侧面说明r的值以及列表b其实没什么用。因此我们的目的就是根据上面这个式子去求出x来。

而我们拥有的所有信息是：

  • p、s、e的值
  • X是一个01矩阵
  • e是一个较小的量

由第二条可以看出应该还是与正交格有关，事实上上面论文中也有提及过这个问题，叫做ahssp(Affine Hidden Subset Sum Problem)。而了解了上一个题目原理的话，这个题目就应该会有些思路，如下：

先是找到一个矩阵M，使得：

那么就有：

转置一下得到：

you因为T是01矩阵，非常小，所以在M^T的左核里LLL应该就能找到T矩阵来。找到T之后再找M’矩阵，使得：

代回原式就有：

就可以解出向量a，然后再代回去就可以取一个值算出x了。如何找到这样的M、M’矩阵在上面的Lattice一题已经提到过。

但是有一个很严峻的问题就是，这一题的向量长度达到了14500。而一般来说格的维度达到几百的话规约已经相当慢了，所以全部用上并不现实。

事实上14500这个数值和论文附录H里提及到的数字$\frac{n^2 + 3n}{2}$很接近，但是我没有看太明白

然后我的思路就是取用其中一些数据来做，综合考虑了一下耗时与规约效果决定最终取700条数据。跑了一个多小时后跑完了，发现很悲剧，应该是数据组数不太够，导致求X的那一步并不对，求出来的不是01矩阵。

今晚挂一下900组数据看看，再高的话感觉就是做法有点问题了。

(2.27更新)

挂了一晚上还是没跑出正确结果，再多选数据应该也跑不出来了。今早上就自己生成了一些数据做观察，发现两个有点古怪的地方：

  • q是不是素数，会对规约的正确性有影响
  • e的大小会对规约的正确性有影响

试了一下发现当e比较小，且q不是素数的时候(也就是题目的情况)，上面的方法就会出错。然后发现一个事实：要按照论文的要求，严格取前面的m-n-1行来组成M(论文里也限制了e的取值范围在2^t以内，也就是一个较小值)，进而求X。多取一行规约结果就会很差。

不过道理我也没有想的太明白，也许是因为e比较小，所以对于他来说没有必要模q？

然后测试出来也是取2n组数据一般就够了，保险起见我多取了一些，sage10.2差不多要做20min左右。得到x后还有一个小问题就是padding是略大于q的，所以要用带余除法算出原本没有模q的x，再去求flag。

exp：

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
from Crypto.Util.number import *

m = 350
n = 168

p = 
y = 
padding = 
h = 
e = 

q = (p-1) // 2
h = Matrix(ZZ,h[:m])
e = Matrix(ZZ,e[:m])

#solve
def solve():  
    #part1 get M satisfying Me=Mh=0
    he = block_matrix(
        [
            [h.T,e.T]
        ]
    )
    L = block_matrix(
        [
            [he , identity_matrix(m)],
            [identity_matrix(2)*q,0]
        ]
    )
    res = L.LLL()

    M = []
    for i in res:
        if(all(j == 0 for j in i[:2])):
            M.append(i[2:])
    M = Matrix(ZZ,M)
    rows = M.dimensions()[0]



    #part2 get X
    L = block_matrix(
        [
            [(M.T)*q , identity_matrix(m)],
            [identity_matrix(rows)*q^2,matrix.zero(rows,m)]
        ]
    )
    L = L.LLL()

    XT = []
    for i in range(n):
        XT.append(L[i][rows:])
    XT = Matrix(ZZ,XT)
    X = XT.T



    #part3 get Me satisfying Me*e = 0
    L = block_matrix(
        [
            [e.T , identity_matrix(m)],
            [identity_matrix(1)*q,0]
        ]
    )
    L[:,:1] *= q
    res = L.LLL()

    Me = []
    for i in res:
        if(all(j == 0 for j in i[:1])):
            Me.append(i[1:])
    Me = Matrix(Zmod(q),Me)


    #part4 solve Matrix_equation
    MeX = Me*X
    alpha = MeX.solve_right(Me*(h.T))


    #part5 get flag
    x = (X*alpha - h.T)[0][0] * inverse(e[0][0],q) % q

if(0):
    solve()

x = 612117363963183636384061017748874955672735689361723523166934161930548362110528132748854224889132227134892963632264858985504494256041853933575304930051002962832249221199876875543858197143759437040160522812192609322189381152131402557127123821310897832468959454180821245363122106475904047956246627954600562153927507243637604870409543115797000848798496677735276442207321208207152206767495046709649070876719645211337462313662076313345513936632345901891335824932718521304752750587670681073748814081161674853723409391972492346216963887247812043140850467713372670135733019783395613050323976347922050060487216125158440171495374240242317148655318512620613495467419513956899948386217293379511094515632848050969451203204086978507123045301979514289179539758858640669371414569240445681550159551534183557059019194621042018552549142048047790277281807582292279323528024506734559017221580490929648282577700618947071089744735643102170603675086599861420840111753270894635567521740077793
i = padding // q
m = (x + i*q) ^^ padding
print(long_to_bytes(m))


#flag{AFF1NE_HSSSSSSSP_T4KE_E4SY}