lattice_oracle问题data文件{ n: 6, q: 97, m: 30, A: [ [ 94, 13, 86, 94, 69, 11 ], [ 54, 4, 3, 11, 27, 29 ], [ 77, 3, 71, 25, 91, 83 ], [ 69, 53, 28, 57, 75, 35 ], [ 20, 89, 54, 43, 35, 19 ], [ 43, 13, 11, 48, 12, 45 ], [ 77, 33, 5, 93, 58, 68 ], [ 48, 10, 70, 37, 80, 79 ], [ 73, 24, 90, 8, 5, 84 ], [ 37, 10, 29, 12, 48, 35 ], [ 81, 46, 20, 47, 45, 26 ], [ 34, 89, 87, 82, 9, 77 ], [ 21, 68, 93, 31, 20, 59 ], [ 34, 81, 88, 71, 28, 87 ], [ 7, 29, 4, 40, 51, 34 ], [ 27, 72, 91, 40, 27, 83 ], [ 50, 82, 58, 18, 33, 17 ], [ 95, 71, 68, 33, 95, 74 ], [ 74, 51, 46, 28, 17, 65 ], [ 11, 96, 6, 14, 19, 80 ], [ 87, 54, 76, 8, 49, 48 ], [ 59, 67, 32, 70, 1, 87 ], [ 14, 87, 68, 96, 34, 82 ], [ 14, 37, 55, 20, 58, 0 ], [ 92, 33, 64, 22, 64, 13 ], [ 38, 81, 64, 77, 25, 19 ], [ 20, 69, 67, 0, 76, 41 ], [ 2, 14, 46, 39, 30, 7 ], [ 72, 10, 10, 93, 62, 8 ], [ 16, 16, 84, 60, 70, 21 ] ], b: [ 56, 74, 51, 28, 10, 30, 34, 45, 82, 56, 62, 52, 5, 71, 35, 41, 86, 47, 8, 27, 64, 29, 57, 92, 34, 55, 57, 70, 87, 28 ], iv: bcdad772f7a0ec967887f7b8f36234c8, enc: 00ac1bac207e84d91c6243c4aead3576a20f996a5420eea7bfa0df3b61d68c83f283bd31f1fedf7465b6445d7a58dcdc }问题代码from Crypto.Cipher import AES import hashlib, os, json, random flag b? n 6 q 97 m 30 s [random.randint(0, 3) for _ in range(n)] A [] b [] for _ in range(m): a_i [random.randint(0, q - 1) for _ in range(n)] e_i random.randint(-1, 1) b_i (sum(x * y for x, y in zip(a_i, s)) e_i) % q A.append(a_i) b.append(b_i) key hashlib.sha256(str(s).encode()).digest()[:16] iv os.urandom(16) pad_len 16 - len(flag) % 16 enc AES.new(key, AES.MODE_CBC, iv).encrypt(flag bytes([pad_len]) * pad_len) print(fn {n}) print(fq {q}) print(fm {m}) print(fA {A}) print(fb {b}) print(fiv {iv.hex()}) print(fenc {enc.hex()}) n 6 q 97 m 30 A [[94, 13, 86, 94, 69, 11], [54, 4, 3, 11, 27, 29], [77, 3, 71, 25, 91, 83], [69, 53, 28, 57, 75, 35], [20, 89, 54, 43, 35, 19], [43, 13, 11, 48, 12, 45], [77, 33, 5, 93, 58, 68], [48, 10, 70, 37, 80, 79], [73, 24, 90, 8, 5, 84], [37, 10, 29, 12, 48, 35], [81, 46, 20, 47, 45, 26], [34, 89, 87, 82, 9, 77], [21, 68, 93, 31, 20, 59], [34, 81, 88, 71, 28, 87], [77, 29, 4, 40, 51, 34], [27, 72, 91, 40, 27, 83], [50, 82, 58, 18, 33, 17], [95, 71, 68, 33, 95, 74], [74, 51, 46, 28, 17, 65], [11, 96, 6, 14, 19, 80], [87, 54, 76, 8, 49, 48], [59, 67, 32, 70, 1, 87], [14, 87, 68, 96, 34, 82], [14, 37, 55, 20, 58, 0], [92, 33, 64, 22, 64, 13], [38, 81, 64, 77, 25, 19], [20, 69, 67, 0, 76, 41], [2, 14, 46, 39, 30, 7], [72, 10, 10, 93, 62, 8], [16, 16, 84, 60, 70, 21]] b [56, 74, 51, 28, 10, 30, 34, 45, 82, 56, 62, 52, 5, 71, 35, 41, 86, 47, 8, 27, 64, 29, 57, 92, 34, 55, 57, 70, 87, 28] iv bcdad772f7a0ec967887f7b8f36234c8 enc 00ac1bac207e84d91c6243c4aead3576a20f996a5420eea7bfa0df3b61d68c83f283bd31f1fedf7465b6445d7a58dcdc 解题代码题目给出了n6, q97, m30, A和b以及iv和enc。秘密向量s每个分量在0-3之间共4^64096种可能。对于每个候选s计算每个方程的误差e_i b_i - dot(A_i, s) mod q但需注意模q后误差应在[-1,0,1]范围内实际因为e_i随机取-1,0,1且b_i (dot e_i) mod q所以计算差值后应落在{0, q-1, q-2} 注意模运算若dot e_i在[0,q-1]内则b_i dote_i若为负数则加q。所以实际误差e_i (b_i - dot) mod q结果应为0, 1, 或q-1对应-1。因此检查条件e_i 0 or e_i 1 or e_i q-1。找到唯一s后计算key值然后用AES CBC解密得到flag.from Crypto.Cipher import AES import hashlib n 6 q 97 m 30 A [[94,13,86,94,69,11],[54,4,3,11,27,29],[77,3,71,25,91,83],[69,53,28,57,75,35],[20,89,54,43,35,19],[43,13,11,48,12,45],[77,33,5,93,58,68],[48,10,70,37,80,79],[73,24,90,8,5,84],[37,10,29,12,48,35],[81,46,20,47,45,26],[34,89,87,82,9,77],[21,68,93,31,20,59],[34,81,88,71,28,87],[77,29,4,40,51,34],[27,72,91,40,27,83],[50,82,58,18,33,17],[95,71,68,33,95,74],[74,51,46,28,17,65],[11,96,6,14,19,80],[87,54,76,8,49,48],[59,67,32,70,1,87],[14,87,68,96,34,82],[14,37,55,20,58,0],[92,33,64,22,64,13],[38,81,64,77,25,19],[20,69,67,0,76,41],[2,14,46,39,30,7],[72,10,10,93,62,8],[16,16,84,60,70,21]] b [56,74,51,28,10,30,34,45,82,56,62,52,5,71,35,41,86,47,8,27,64,29,57,92,34,55,57,70,87,28] iv bytes.fromhex(bcdad772f7a0ec967887f7b8f36234c8) enc bytes.fromhex(00ac1bac207e84d91c6243c4aead3576a20f996a5420eea7bfa0df3b61d68c83f283bd31f1fedf7465b6445d7a58dcdc) # 枚举所有可能的s (每个分量0-3) from itertools import product candidates [] for s in product(range(4), repeatn): valid True for i in range(m): dot sum(A[i][j] * s[j] for j in range(n)) % q e (b[i] - dot) % q if e not in (0, 1, q-1): valid False break if valid: candidates.append(s) print(Found candidates:, candidates) s candidates[0] key hashlib.sha256(str(list(s)).encode()).digest()[:16] cipher AES.new(key, AES.MODE_CBC, iv) flag cipher.decrypt(enc) pad_len flag[-1] if pad_len 16: flag flag[:-pad_len] print(flag.decode())three_friends问题from Crypto.Util.number import * flag b*********** L len(flag) m1 bytes_to_long(flag[:L//3]) m2 bytes_to_long(flag[L//3:2*L//3]) m3 bytes_to_long(flag[2*L//3:]) p getPrime(512) q getPrime(512) r getPrime(512) e 65537 n1 p * q n2 q * r n3 p * r c1 pow(m1, e, n1) c2 pow(m2, e, n2) c3 pow(m3, e, n3) print(fn1 {n1}) print(fn2 {n2}) print(fn3 {n3}) print(fe {e}) print(fc1 {c1}) print(fc2 {c2}) print(fc3 {c3}) n1 110479112338979326841231465480900311437095583241804968504367003268478785311645575853029227541889465070127417880290972698509502098875302777600751062235679028180932171554996023850242418398546147652141811910224228666917788640895453721648601609529326886128507435254380985821439510394329605362511800619781782498829 n2 95225891725804035729098697183853172993650305271540351260130976375990969994680256179992972429701670943885218431291657615581872984046365977866046911929212400122026478512046580419614160900113488336302811792780327677539930592604198331529856760869923384410189400614767668529075682332352478496830621674767765967989 n3 111603865467493745511917065096450766019551858630764507502030413922630178420561431122201021143404521026218410173550594126191240832822627851633700772093095150654117699219949636045712687320990198957564564857885138504872560550777788915442814980338401072475446362026076893466520135409327492048388030114969050367401 e 65537 c1 83456548767677952158133165776385438048214812740470347872014544040241661979735585698444752238351578159480247608435786172021153411975720140472715451216442036398970558532828923787921375318802867775369825882219621531795085442575971814645729572790836415339290407608988460626504016819536559945368010686567075802413 c2 55598291653542627898994967211126815679185160762475277667203320398466974811147081936849639204784572327753766773503264941715352990434513737784771805183050575481575095545922660276426069697449001567347723946016416649932633528235458091960122921036028416845355866656581114844470311590282808396786169332755296721792 c3 99617304265145206462280689337024202287720390645940568836285315412577937662785727570612881726190729195621460858194592258472873348744392240254689998279616123901037173010035977506212880680604466077172284894508163086916852071659627506881093976971048133795462670278664801263633610021626528113016267024450025017002 解题代码RSA多素数问题三个模数n1p*q, n2q*r, n3p*r。已知n1, n2, n3, e, c1, c2, c3。我们需要恢复flag。flag被分成三部分m1, m2, m3分别加密。由于我们知道n1, n2, n3我们可以通过gcd(n1, n2)得到q然后p n1//qr n2//q。然后解每个密文得到m1, m2, m3。但注意m1, m2, m3是flag的一部分可能长度不是正好整除但这里使用了L//3分片所以每个部分长度大致相等。我们需要将三个数字转换为字节并拼接得到flag。from Crypto.Util.number import long_to_bytes from math import gcd n1 110479112338979326841231465480900311437095583241804968504367003268478785311645575853029227541889465070127417880290972698509502098875302777600751062235679028180932171554996023850242418398546147652141811910224228666917788640895453721648601609529326886128507435254380985821439510394329605362511800619781782498829 n2 95225891725804035729098697183853172993650305271540351260130976375990969994680256179992972429701670943885218431291657615581872984046365977866046911929212400122026478512046580419614160900113488336302811792780327677539930592604198331529856760869923384410189400614767668529075682332352478496830621674767765967989 n3 111603865467493745511917065096450766019551858630764507502030413922630178420561431122201021143404521026218410173550594126191240832822627851633700772093095150654117699219949636045712687320990198957564564857885138504872560550777788915442814980338401072475446362026076893466520135409327492048388030114969050367401 e 65537 c1 83456548767677952158133165776385438048214812740470347872014544040241661979735585698444752238351578159480247608435786172021153411975720140472715451216442036398970558532828923787921375318802867775369825882219621531795085442575971814645729572790836415339290407608988460626504016819536559945368010686567075802413 c2 55598291653542627898994967211126815679185160762475277667203320398466974811147081936849639204784572327753766773503264941715352990434513737784771805183050575481575095545922660276426069697449001567347723946016416649932633528235458091960122921036028416845355866656581114844470311590282808396786169332755296721792 c3 99617304265145206462280689337024202287720390645940568836285315412577937662785727570612881726190729195621460858194592258472873348744392240254689998279616123901037173010035977506212880680604466077172284894508163086916852071659627506881093976971048133795462670278664801263633610021626528113016267024450025017002 # 1. 通过 gcd 恢复公共质因数 q gcd(n1, n2) # n1 p*q, n2 q*r p n1 // q r n2 // q # 验证 n3 assert n3 p * r, n3 与 p*r 不匹配 # 2. 计算每个模数的欧拉函数值并求私钥 d phi1 (p-1)*(q-1) d1 pow(e, -1, phi1) m1 pow(c1, d1, n1) phi2 (q-1)*(r-1) d2 pow(e, -1, phi2) m2 pow(c2, d2, n2) phi3 (p-1)*(r-1) d3 pow(e, -1, phi3) m3 pow(c3, d3, n3) # 3. 将整数转为字节串并拼接 flag long_to_bytes(m1) long_to_bytes(m2) long_to_bytes(m3) print(flag.decode())phantom_sign问题data.join文件{ curve: { p: 115792089237316195423570985008687907853269984665640564039457584007908834671663, a: 0, b: 7, n: 115792089237316195423570985008687907852837564279074904382605163141518161494337, Gx: 55066263022277343669578718895168534326250603453777594175500187360389116729240, Gy: 32670510020758816978083085130507043184471273380659243275938904335757337482424 }, Q: [ 14381884142053692010670248998801769124914487901414773974015654681034012688255, 64375051673746957361995109041219741865161910617387712088184757596175025053122 ], messages: [ transaction_0000, transaction_0001, transaction_0002, transaction_0003, transaction_0004, transaction_0005, transaction_0006, transaction_0007, transaction_0008, transaction_0009, transaction_0010, transaction_0011, transaction_0012, transaction_0013, transaction_0014, transaction_0015, transaction_0016, transaction_0017, transaction_0018, transaction_0019, transaction_0020, transaction_0021, transaction_0022, transaction_0023, transaction_0024, transaction_0025, transaction_0026, transaction_0027, transaction_0028, transaction_0029, transaction_0030, transaction_0031, transaction_0032, transaction_0033, transaction_0034, transaction_0035, transaction_0036, transaction_0037, transaction_0038, transaction_0039 ], signatures: [ [ 68623012658964044762439342088012968624675690473816447637600910564419537238371, 15409910140266829196412141913285986302804004110236621771020575869065555663696, 16231690641092882005648985285611869113359556603583525880749701446944482280021 ], [ 77431396449219903473500735584772748401805492235548758593058094014043985134432, 67863597065431736744341440973090277252500853536893508765834799618806098271971, 24087909208373904843980482690084775866515137017280314586016074922674852950253 ], [ 100248368000649436610187738005377683213071492466205694786382250978121304847477, 77042059530731000421700136088737254781902047732199473207102292532379790077908, 83201196234278745618633371284537877693294166569777892443609588916214395800793 ], [ 98710888583712501637271528817394350172330702312562091976971223086960770939229, 16520271882082076261873400787434335823842832075059532024002551383223716751788, 22820724369261883837345916363412287825209317160882909337420597055559178152516 ], [ 59967080355028192107558514795652734650395409012132756087245876704745319277923, 47136580854696294822924432914322852109262249675142496795370609257457164594314, 13682716447356676108782599637577879405582127040964001655868876522076601805986 ], [ 109549518366107268175566420541647014431304106391008133537387771704686987061848, 42693721873458957430095521557168807764715953946858801334925813349834102476268, 80412604504881303613607760025259664985035514562950545552680307442529482563178 ], [ 32891620902205917973749212388363625471988247490866368122783178116254114716840, 23468412712478130166174673844108979598723413685258787747162405930509276876504, 95694506365701709993200278888122095662942876004812269473949018644610368529945 ], [ 7034130388458250359073433784976303090373666812632229911026234082900858319745, 39521869922052069350514363141850998159800210216399500967932590206699536627841, 84353561963465987590756504434712708320467880003431220998255132049603443566767 ], [ 81603082497512549594737087912428025636236701602760455573358977688837607027030, 70468775971037345019568151925840035810953592003694890746728099612852733316781, 60188526646767806213578866692609585353411998783011605223221841743702035165689 ], [ 468820956173341373421250975133053620084677820114822054364619276486853657378, 97617802742831258133389306842926539984189205376012132788295743866240138393796, 86197308671240955856792900537452586282633455973411628672881311684985478392023 ], [ 34198855384118055989774019714084284607152642751190185031160830737984106466825, 50091975249850495590192550928077098526392126317690594853380942936943511566748, 82821224010440219461116506221592230660592360305266834070956225480688805987782 ], [ 44692908537542921388721557652293950830728673227605735396255620821721247706746, 86303046675560156022221798070497825327652849653693114279064416140443550145135, 25774132105242471740738652205562372489424541515376008388300106346755509211237 ], [ 103371574413557665181969748049543969481794604073622278983532046290983238979971, 15864399438093679710696118414562945892156489123355478934030614804022876369983, 54776456658598351376132617111181472299022005760051955110025505232956220720011 ], [ 63341128072830221873124956390298090362285184652738502327724967039766171538206, 11733122287893233193041134288448337239823392760363833328527972874375992506185, 55589451739589363242556596652770241463015149077817786903879419739309759578175 ], [ 27288717930840976736680809241382164215651583919640225703008945311488199140521, 70952066043757850812973802542731941610375006626643053263121657775586502932574, 70999334731245338502230582908105212782583996043864821203745436191377548842962 ], [ 46977534818805503250026505243185583478497804552247128876416946585364297578313, 85888803887249272531039133914745482794189393882435176657644947019816666997866, 115439058221796341851223357555191987336992737315776925913826898155265301156513 ], [ 108742045161968083170793999806136654493975359192544979494514159017986130950145, 55276373164891899555674217114895276904618874120130236173518191824641067518095, 38249790543512769372950721119118070697179260436542072817927568583554674034872 ], [ 80679385259005022311454077061638968975436785982614413209061244151516600200604, 38830127938935154036365672021650382727492249584897878321818743263930063797867, 1615604521298534145852491795189029226912426630714907710141135634092303903692 ], [ 68426646935507652864321803938637509374411880258163567604422214441877403558563, 49485206808907344546224756822956202192819461158084832051644535076762086911094, 5506738747141944929476836768389643342000107449635926313949384197297785179392 ], [ 75749110106887185029696128609664986507851190155862064026568376511601948342562, 103134910436105078628750146848715499694625558345743178409736128330081634012939, 44629335752019242725824498152097689780496323404757053504483657690141328743571 ], [ 91018041996616883539059450083078485404853400346892984297021173939461655057767, 11461890292925254499816979898090493650892053286982534818266508401647599070685, 40031373887348334200664348038188275286628600246735900840022955444430590281855 ], [ 1370687679926407589411963949541005511534305373551132425701086586910259635693, 107619305183424867953063642433255944948673145351534928767503637716296709264685, 85513484602329200511731250031521439738521337009477868919113331987207571383694 ], [ 44944287357591856363247256091485039648533597543208271827409192476451290982779, 23175840683019426535583923882772506992218394035175827240603279300793913605553, 80031135715265348665934774384368935350707832014864718995937062885248400818264 ], [ 17694567492186494847567960676252271679297743299805709379745528289640192535059, 71355530734203596192754364284929825508213810679176506903309636275867854701706, 102233035159694340569371315519189828565187309319219185159132617914136413644659 ], [ 54456482747307877036840932303806534594320856321791174091833811110252672255623, 32998682782651923096991067227828367025494847948287781286016129232181211768899, 18443963929422435176984400249169266653848364275404381769823306629634461819686 ], [ 2404814179589202385430703159800974435225758080132560432960864443808482348681, 33576437303174752996063351920550159305060168912109415419982873233118909715201, 100614626430112511848206158910219447084927962265787443711244786060546283770750 ], [ 115745414399683823307868521314846890210612184688338219317351943089729115155364, 79438235079169283727785836919328790019797981743656243081628185669211413227225, 102806512769931746523999370669354592734153941662103644543564851908427108413913 ], [ 18426657627489841307261634267238401226059547378719104932708309997051748743769, 62590041951703184253678233264344446748127485210977060559306195540330092605362, 101530409927644823892719262290513582065237179361817304023613215463814779925895 ], [ 74386971640345348892273553558534056423360473891327412428528026398196155593717, 112531297864138795074095127404777305273759611453695096499330894409552283933946, 18823749967655963380272028819243750152361266207453980896157770996332423395082 ], [ 19106188598360386995507879795657171606222760661548416372498541207700966318284, 100617844853844596276395700912501356057588002934486917893968678432205687541476, 43736575626650901378832954845740205926921653011368690509563749617513006791484 ], [ 90826305454088332506331106642552006622072207363916469718022991443620544472546, 53758585234453282306365116576836864660792431524619925164067935733611806020238, 82201873555529998458133190118421768098123248026473202342997665073076665973761 ], [ 26964884110356441854854146441983840112586567210061799395519700568901705979391, 1501580300208786477647896676022784131292995291248556256029839365072061388853, 74663505428203350509657969904492520642046783183792753210740041094249533787195 ], [ 30867701522043889635892145388908689718746952318295454393379231437327806517839, 103976891956739383229279105730248953588226973172938577085394805051492378931690, 95050317462894118042891010248169813822197290013821053762551094263011582770872 ], [ 91625463520733170536123384098608666318804256815524871957315735711271742421480, 18421764663198939270481619830994446270847508651060531249062628134724012834678, 48334336563886233195718722096743040222545484109821164105150318374001163713165 ], [ 103064540920389706885216566103866388349445461442577057115890241415106585943059, 93557418383080341475950855462894077919034434666441577156007046090636823710718, 5027052615852822061753823925815925894133647383995174293658504267200461685357 ], [ 92080617417968225877643047516649852660902234175180899982216286691685945363569, 16410973208434267587548600922795823406156890013721990057263520578610923809844, 67365944641539915969665344202352251869423069523524222146230967868391275008227 ], [ 6159561898351927490523303554903483755096522561484631083019517022991878007250, 40353595861455770779106431851830080611219657721423578311317916723690860959197, 70771528439745244346695359744161029464126444827213217436535504331137136741465 ], [ 26014860908695329456449800888732251794635965791744084336829431449032048912766, 97126322320255761721732297914656320097635724679029727859661301686364386778040, 29627148788686640914536827943478838605842335191276479094899001742330086803923 ], [ 95638155978081454594748375621553851019955800860992571438989927312610110006635, 106704752213663488838283609628683569783251650568773792767027643662696040553298, 16725629198799460288259231610659921992174496734119920477389778451623621034370 ], [ 86374304417545719890118180914775030188473989874917183072739411192768588646497, 112793359871613653484714387011745700719066770376294753104591899106143083860660, 93975497629053209581870367660816868978543483441305949414816232807735190601440 ] ], iv: d76bc487aedfe1aedeb9ae3ef867b81f, enc: c661c1ca54c4142afc81f5ea94256137c77e96eae909254cdaa2e4409e90fc3551b14b9d33b7e2a0fea48e18f12a9aa7 }问题代码import os, hashlib, json from Crypto.Cipher import AES from Crypto.Util.Padding import pad from Crypto.Util.number import long_to_bytes, bytes_to_long p 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F a 0 b 7 n 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141 Gx 0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798 Gy 0x483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8 def inv_mod(val, mod): return pow(val, -1, mod) def point_add(P, Q): if P is None: return Q if Q is None: return P x1, y1 P x2, y2 Q if x1 x2 and y1 ! y2: return None if P Q: lam (3 * x1 * x1 a) * inv_mod(2 * y1, p) % p else: lam (y2 - y1) * inv_mod(x2 - x1, p) % p x3 (lam * lam - x1 - x2) % p y3 (lam * (x1 - x3) - y1) % p return (x3, y3) def point_mul(k, P): R None Q P while k 0: if k 1: R point_add(R, Q) Q point_add(Q, Q) k 1 return R G (Gx, Gy) flag bDASCTF{************************************} d bytes_to_long(os.urandom(32)) % n Q point_mul(d, G) NUM_SIGS 40 messages [] sigs [] for i in range(NUM_SIGS): msg ftransaction_{i:04d}.encode() h_i int(hashlib.sha256(msg).hexdigest(), 16) % n k_i bytes_to_long(os.urandom(31)) R_i point_mul(k_i, G) r_i R_i[0] % n s_i inv_mod(k_i, n) * (h_i d * r_i) % n messages.append(msg.decode()) sigs.append((h_i, r_i, s_i)) key hashlib.sha256(long_to_bytes(d)).digest()[:16] iv os.urandom(16) enc AES.new(key, AES.MODE_CBC, iv).encrypt(pad(flag, 16)) output { curve: {p: p, a: a, b: b, n: n, Gx: Gx, Gy: Gy}, Q: [Q[0], Q[1]], messages: messages, signatures: [(h, r, s) for h, r, s in sigs], iv: iv.hex(), enc: enc.hex(), } with open(data.json, w) as f: json.dump(output, f, indent2)解题代码ECDSA 签名中的随机数 k_i 只用了 31 字节248 bits远小于曲线阶 n256 bits。这是一个经典的 有偏 nonce攻击。SageMath LLL对每个签名计算 c_i s_i · r_i⁻¹ mod nv_i −h_i · r_i⁻¹ mod n消去 d 得到 k_i ≡ α_i · k₀ β_i (mod n) 方程组构造 41 维格矩阵所有短向量分量 2^248BKZ-30 归约恢复 k₀ → 反推 d。import json, sys with open(data.json) as f: data json.load(f) n int(data[curve][n]) p int(data[curve][p]) Gx int(data[curve][Gx]) Gy int(data[curve][Gy]) Qx int(data[Q][0]) Qy int(data[Q][1]) sigs data[signatures] K 2^248 # 椭圆曲线 F GF(p) E EllipticCurve(F, [0, 7]) G E(Gx, Gy) Q E(Qx, Qy) m len(sigs) # Step 1: 计算 c_i, v_i c_list [] v_list [] for sig in sigs: hi, ri, si int(sig[0]), int(sig[1]), int(sig[2]) ci (si * inverse_mod(ri, n)) % n vi (-hi * inverse_mod(ri, n)) % n c_list.append(ci) v_list.append(vi) # Step 2: 消去 d得到 k_i α_i * k_0 β_i (mod n) alpha_list [] beta_list [] c0, v0 c_list[0], v_list[0] for i in range(1, m): ci_inv inverse_mod(c_list[i], n) ai (ci_inv * c0) % n bi (ci_inv * (v0 - v_list[i])) % n alpha_list.append(ai) beta_list.append(bi) # Step 3: 构造 (m1) × (m1) 格矩阵 dim (m - 1) 2 # 41 MM matrix(ZZ, dim, dim) for i in range(m - 1): MM[i, i] n # n 对角线 k0_col m - 1 for i in range(m - 1): MM[m - 1, i] alpha_list[i] # α₁..α₃₉ MM[m - 1, k0_col] 1 # k₀ 系数 const_col m for i in range(m - 1): MM[m, i] beta_list[i] # β₁..β₃₉ MM[m, const_col] K # K # Step 4: BKZ LLL 归约 L MM.BKZ(block_size30, fprr, precision200) L2 MM.LLL() # Step 5: 从短向量提取 k₀ → 计算 d def verify(dc): 验证 Q d*G 且 k_i K dc_int int(dc) if dc_int 0 or dc_int n: return False if (dc_int * G) ! Q: return False for i in range(min(3, m)): hi, ri, si sigs[i] kc (inverse_mod(si, n) * (hi dc_int * ri)) % n if kc K: return False return True d_found None for name, L_mat in [(BKZ, L), (LLL, L2)]: for i, row in enumerate(L_mat[:80]): if abs(int(row[-1])) K: # 最后一列 ±K k0 abs(int(row[-2])) # 倒数第二列 k₀ if 0 k0 K: dc (c0 * k0 v0) % n # d c₀k₀ v₀ (mod n) if verify(dc): d_found dc break if d_found: break print(fd {d_found})再利用key SHA256(long_to_bytes(d))[:16]AES-CBC 解密得到 flagimport hashlib from Crypto.Cipher import AES from Crypto.Util.Padding import unpad from Crypto.Util.number import long_to_bytes d 69733894115169365517439430123407937761015055472912247236884018827222720875663 iv bytes.fromhex(d76bc487aedfe1aedeb9ae3ef867b81f) enc bytes.fromhex(c661c1ca54c4142afc81f5ea94256137c77e96eae909254cdaa2e4409e90fc3551b14b9d33b7e2a0fea48e18f12a9aa7) key hashlib.sha256(long_to_bytes(d)).digest()[:16] cipher AES.new(key, AES.MODE_CBC, iv) flag unpad(cipher.decrypt(enc), 16) print(flag.decode())
2026DASCTF夏季赛WP-Crypto
lattice_oracle问题data文件{ n: 6, q: 97, m: 30, A: [ [ 94, 13, 86, 94, 69, 11 ], [ 54, 4, 3, 11, 27, 29 ], [ 77, 3, 71, 25, 91, 83 ], [ 69, 53, 28, 57, 75, 35 ], [ 20, 89, 54, 43, 35, 19 ], [ 43, 13, 11, 48, 12, 45 ], [ 77, 33, 5, 93, 58, 68 ], [ 48, 10, 70, 37, 80, 79 ], [ 73, 24, 90, 8, 5, 84 ], [ 37, 10, 29, 12, 48, 35 ], [ 81, 46, 20, 47, 45, 26 ], [ 34, 89, 87, 82, 9, 77 ], [ 21, 68, 93, 31, 20, 59 ], [ 34, 81, 88, 71, 28, 87 ], [ 7, 29, 4, 40, 51, 34 ], [ 27, 72, 91, 40, 27, 83 ], [ 50, 82, 58, 18, 33, 17 ], [ 95, 71, 68, 33, 95, 74 ], [ 74, 51, 46, 28, 17, 65 ], [ 11, 96, 6, 14, 19, 80 ], [ 87, 54, 76, 8, 49, 48 ], [ 59, 67, 32, 70, 1, 87 ], [ 14, 87, 68, 96, 34, 82 ], [ 14, 37, 55, 20, 58, 0 ], [ 92, 33, 64, 22, 64, 13 ], [ 38, 81, 64, 77, 25, 19 ], [ 20, 69, 67, 0, 76, 41 ], [ 2, 14, 46, 39, 30, 7 ], [ 72, 10, 10, 93, 62, 8 ], [ 16, 16, 84, 60, 70, 21 ] ], b: [ 56, 74, 51, 28, 10, 30, 34, 45, 82, 56, 62, 52, 5, 71, 35, 41, 86, 47, 8, 27, 64, 29, 57, 92, 34, 55, 57, 70, 87, 28 ], iv: bcdad772f7a0ec967887f7b8f36234c8, enc: 00ac1bac207e84d91c6243c4aead3576a20f996a5420eea7bfa0df3b61d68c83f283bd31f1fedf7465b6445d7a58dcdc }问题代码from Crypto.Cipher import AES import hashlib, os, json, random flag b? n 6 q 97 m 30 s [random.randint(0, 3) for _ in range(n)] A [] b [] for _ in range(m): a_i [random.randint(0, q - 1) for _ in range(n)] e_i random.randint(-1, 1) b_i (sum(x * y for x, y in zip(a_i, s)) e_i) % q A.append(a_i) b.append(b_i) key hashlib.sha256(str(s).encode()).digest()[:16] iv os.urandom(16) pad_len 16 - len(flag) % 16 enc AES.new(key, AES.MODE_CBC, iv).encrypt(flag bytes([pad_len]) * pad_len) print(fn {n}) print(fq {q}) print(fm {m}) print(fA {A}) print(fb {b}) print(fiv {iv.hex()}) print(fenc {enc.hex()}) n 6 q 97 m 30 A [[94, 13, 86, 94, 69, 11], [54, 4, 3, 11, 27, 29], [77, 3, 71, 25, 91, 83], [69, 53, 28, 57, 75, 35], [20, 89, 54, 43, 35, 19], [43, 13, 11, 48, 12, 45], [77, 33, 5, 93, 58, 68], [48, 10, 70, 37, 80, 79], [73, 24, 90, 8, 5, 84], [37, 10, 29, 12, 48, 35], [81, 46, 20, 47, 45, 26], [34, 89, 87, 82, 9, 77], [21, 68, 93, 31, 20, 59], [34, 81, 88, 71, 28, 87], [77, 29, 4, 40, 51, 34], [27, 72, 91, 40, 27, 83], [50, 82, 58, 18, 33, 17], [95, 71, 68, 33, 95, 74], [74, 51, 46, 28, 17, 65], [11, 96, 6, 14, 19, 80], [87, 54, 76, 8, 49, 48], [59, 67, 32, 70, 1, 87], [14, 87, 68, 96, 34, 82], [14, 37, 55, 20, 58, 0], [92, 33, 64, 22, 64, 13], [38, 81, 64, 77, 25, 19], [20, 69, 67, 0, 76, 41], [2, 14, 46, 39, 30, 7], [72, 10, 10, 93, 62, 8], [16, 16, 84, 60, 70, 21]] b [56, 74, 51, 28, 10, 30, 34, 45, 82, 56, 62, 52, 5, 71, 35, 41, 86, 47, 8, 27, 64, 29, 57, 92, 34, 55, 57, 70, 87, 28] iv bcdad772f7a0ec967887f7b8f36234c8 enc 00ac1bac207e84d91c6243c4aead3576a20f996a5420eea7bfa0df3b61d68c83f283bd31f1fedf7465b6445d7a58dcdc 解题代码题目给出了n6, q97, m30, A和b以及iv和enc。秘密向量s每个分量在0-3之间共4^64096种可能。对于每个候选s计算每个方程的误差e_i b_i - dot(A_i, s) mod q但需注意模q后误差应在[-1,0,1]范围内实际因为e_i随机取-1,0,1且b_i (dot e_i) mod q所以计算差值后应落在{0, q-1, q-2} 注意模运算若dot e_i在[0,q-1]内则b_i dote_i若为负数则加q。所以实际误差e_i (b_i - dot) mod q结果应为0, 1, 或q-1对应-1。因此检查条件e_i 0 or e_i 1 or e_i q-1。找到唯一s后计算key值然后用AES CBC解密得到flag.from Crypto.Cipher import AES import hashlib n 6 q 97 m 30 A [[94,13,86,94,69,11],[54,4,3,11,27,29],[77,3,71,25,91,83],[69,53,28,57,75,35],[20,89,54,43,35,19],[43,13,11,48,12,45],[77,33,5,93,58,68],[48,10,70,37,80,79],[73,24,90,8,5,84],[37,10,29,12,48,35],[81,46,20,47,45,26],[34,89,87,82,9,77],[21,68,93,31,20,59],[34,81,88,71,28,87],[77,29,4,40,51,34],[27,72,91,40,27,83],[50,82,58,18,33,17],[95,71,68,33,95,74],[74,51,46,28,17,65],[11,96,6,14,19,80],[87,54,76,8,49,48],[59,67,32,70,1,87],[14,87,68,96,34,82],[14,37,55,20,58,0],[92,33,64,22,64,13],[38,81,64,77,25,19],[20,69,67,0,76,41],[2,14,46,39,30,7],[72,10,10,93,62,8],[16,16,84,60,70,21]] b [56,74,51,28,10,30,34,45,82,56,62,52,5,71,35,41,86,47,8,27,64,29,57,92,34,55,57,70,87,28] iv bytes.fromhex(bcdad772f7a0ec967887f7b8f36234c8) enc bytes.fromhex(00ac1bac207e84d91c6243c4aead3576a20f996a5420eea7bfa0df3b61d68c83f283bd31f1fedf7465b6445d7a58dcdc) # 枚举所有可能的s (每个分量0-3) from itertools import product candidates [] for s in product(range(4), repeatn): valid True for i in range(m): dot sum(A[i][j] * s[j] for j in range(n)) % q e (b[i] - dot) % q if e not in (0, 1, q-1): valid False break if valid: candidates.append(s) print(Found candidates:, candidates) s candidates[0] key hashlib.sha256(str(list(s)).encode()).digest()[:16] cipher AES.new(key, AES.MODE_CBC, iv) flag cipher.decrypt(enc) pad_len flag[-1] if pad_len 16: flag flag[:-pad_len] print(flag.decode())three_friends问题from Crypto.Util.number import * flag b*********** L len(flag) m1 bytes_to_long(flag[:L//3]) m2 bytes_to_long(flag[L//3:2*L//3]) m3 bytes_to_long(flag[2*L//3:]) p getPrime(512) q getPrime(512) r getPrime(512) e 65537 n1 p * q n2 q * r n3 p * r c1 pow(m1, e, n1) c2 pow(m2, e, n2) c3 pow(m3, e, n3) print(fn1 {n1}) print(fn2 {n2}) print(fn3 {n3}) print(fe {e}) print(fc1 {c1}) print(fc2 {c2}) print(fc3 {c3}) n1 110479112338979326841231465480900311437095583241804968504367003268478785311645575853029227541889465070127417880290972698509502098875302777600751062235679028180932171554996023850242418398546147652141811910224228666917788640895453721648601609529326886128507435254380985821439510394329605362511800619781782498829 n2 95225891725804035729098697183853172993650305271540351260130976375990969994680256179992972429701670943885218431291657615581872984046365977866046911929212400122026478512046580419614160900113488336302811792780327677539930592604198331529856760869923384410189400614767668529075682332352478496830621674767765967989 n3 111603865467493745511917065096450766019551858630764507502030413922630178420561431122201021143404521026218410173550594126191240832822627851633700772093095150654117699219949636045712687320990198957564564857885138504872560550777788915442814980338401072475446362026076893466520135409327492048388030114969050367401 e 65537 c1 83456548767677952158133165776385438048214812740470347872014544040241661979735585698444752238351578159480247608435786172021153411975720140472715451216442036398970558532828923787921375318802867775369825882219621531795085442575971814645729572790836415339290407608988460626504016819536559945368010686567075802413 c2 55598291653542627898994967211126815679185160762475277667203320398466974811147081936849639204784572327753766773503264941715352990434513737784771805183050575481575095545922660276426069697449001567347723946016416649932633528235458091960122921036028416845355866656581114844470311590282808396786169332755296721792 c3 99617304265145206462280689337024202287720390645940568836285315412577937662785727570612881726190729195621460858194592258472873348744392240254689998279616123901037173010035977506212880680604466077172284894508163086916852071659627506881093976971048133795462670278664801263633610021626528113016267024450025017002 解题代码RSA多素数问题三个模数n1p*q, n2q*r, n3p*r。已知n1, n2, n3, e, c1, c2, c3。我们需要恢复flag。flag被分成三部分m1, m2, m3分别加密。由于我们知道n1, n2, n3我们可以通过gcd(n1, n2)得到q然后p n1//qr n2//q。然后解每个密文得到m1, m2, m3。但注意m1, m2, m3是flag的一部分可能长度不是正好整除但这里使用了L//3分片所以每个部分长度大致相等。我们需要将三个数字转换为字节并拼接得到flag。from Crypto.Util.number import long_to_bytes from math import gcd n1 110479112338979326841231465480900311437095583241804968504367003268478785311645575853029227541889465070127417880290972698509502098875302777600751062235679028180932171554996023850242418398546147652141811910224228666917788640895453721648601609529326886128507435254380985821439510394329605362511800619781782498829 n2 95225891725804035729098697183853172993650305271540351260130976375990969994680256179992972429701670943885218431291657615581872984046365977866046911929212400122026478512046580419614160900113488336302811792780327677539930592604198331529856760869923384410189400614767668529075682332352478496830621674767765967989 n3 111603865467493745511917065096450766019551858630764507502030413922630178420561431122201021143404521026218410173550594126191240832822627851633700772093095150654117699219949636045712687320990198957564564857885138504872560550777788915442814980338401072475446362026076893466520135409327492048388030114969050367401 e 65537 c1 83456548767677952158133165776385438048214812740470347872014544040241661979735585698444752238351578159480247608435786172021153411975720140472715451216442036398970558532828923787921375318802867775369825882219621531795085442575971814645729572790836415339290407608988460626504016819536559945368010686567075802413 c2 55598291653542627898994967211126815679185160762475277667203320398466974811147081936849639204784572327753766773503264941715352990434513737784771805183050575481575095545922660276426069697449001567347723946016416649932633528235458091960122921036028416845355866656581114844470311590282808396786169332755296721792 c3 99617304265145206462280689337024202287720390645940568836285315412577937662785727570612881726190729195621460858194592258472873348744392240254689998279616123901037173010035977506212880680604466077172284894508163086916852071659627506881093976971048133795462670278664801263633610021626528113016267024450025017002 # 1. 通过 gcd 恢复公共质因数 q gcd(n1, n2) # n1 p*q, n2 q*r p n1 // q r n2 // q # 验证 n3 assert n3 p * r, n3 与 p*r 不匹配 # 2. 计算每个模数的欧拉函数值并求私钥 d phi1 (p-1)*(q-1) d1 pow(e, -1, phi1) m1 pow(c1, d1, n1) phi2 (q-1)*(r-1) d2 pow(e, -1, phi2) m2 pow(c2, d2, n2) phi3 (p-1)*(r-1) d3 pow(e, -1, phi3) m3 pow(c3, d3, n3) # 3. 将整数转为字节串并拼接 flag long_to_bytes(m1) long_to_bytes(m2) long_to_bytes(m3) print(flag.decode())phantom_sign问题data.join文件{ curve: { p: 115792089237316195423570985008687907853269984665640564039457584007908834671663, a: 0, b: 7, n: 115792089237316195423570985008687907852837564279074904382605163141518161494337, Gx: 55066263022277343669578718895168534326250603453777594175500187360389116729240, Gy: 32670510020758816978083085130507043184471273380659243275938904335757337482424 }, Q: [ 14381884142053692010670248998801769124914487901414773974015654681034012688255, 64375051673746957361995109041219741865161910617387712088184757596175025053122 ], messages: [ transaction_0000, transaction_0001, transaction_0002, transaction_0003, transaction_0004, transaction_0005, transaction_0006, transaction_0007, transaction_0008, transaction_0009, transaction_0010, transaction_0011, transaction_0012, transaction_0013, transaction_0014, transaction_0015, transaction_0016, transaction_0017, transaction_0018, transaction_0019, transaction_0020, transaction_0021, transaction_0022, transaction_0023, transaction_0024, transaction_0025, transaction_0026, transaction_0027, transaction_0028, transaction_0029, transaction_0030, transaction_0031, transaction_0032, transaction_0033, transaction_0034, transaction_0035, transaction_0036, transaction_0037, transaction_0038, transaction_0039 ], signatures: [ [ 68623012658964044762439342088012968624675690473816447637600910564419537238371, 15409910140266829196412141913285986302804004110236621771020575869065555663696, 16231690641092882005648985285611869113359556603583525880749701446944482280021 ], [ 77431396449219903473500735584772748401805492235548758593058094014043985134432, 67863597065431736744341440973090277252500853536893508765834799618806098271971, 24087909208373904843980482690084775866515137017280314586016074922674852950253 ], [ 100248368000649436610187738005377683213071492466205694786382250978121304847477, 77042059530731000421700136088737254781902047732199473207102292532379790077908, 83201196234278745618633371284537877693294166569777892443609588916214395800793 ], [ 98710888583712501637271528817394350172330702312562091976971223086960770939229, 16520271882082076261873400787434335823842832075059532024002551383223716751788, 22820724369261883837345916363412287825209317160882909337420597055559178152516 ], [ 59967080355028192107558514795652734650395409012132756087245876704745319277923, 47136580854696294822924432914322852109262249675142496795370609257457164594314, 13682716447356676108782599637577879405582127040964001655868876522076601805986 ], [ 109549518366107268175566420541647014431304106391008133537387771704686987061848, 42693721873458957430095521557168807764715953946858801334925813349834102476268, 80412604504881303613607760025259664985035514562950545552680307442529482563178 ], [ 32891620902205917973749212388363625471988247490866368122783178116254114716840, 23468412712478130166174673844108979598723413685258787747162405930509276876504, 95694506365701709993200278888122095662942876004812269473949018644610368529945 ], [ 7034130388458250359073433784976303090373666812632229911026234082900858319745, 39521869922052069350514363141850998159800210216399500967932590206699536627841, 84353561963465987590756504434712708320467880003431220998255132049603443566767 ], [ 81603082497512549594737087912428025636236701602760455573358977688837607027030, 70468775971037345019568151925840035810953592003694890746728099612852733316781, 60188526646767806213578866692609585353411998783011605223221841743702035165689 ], [ 468820956173341373421250975133053620084677820114822054364619276486853657378, 97617802742831258133389306842926539984189205376012132788295743866240138393796, 86197308671240955856792900537452586282633455973411628672881311684985478392023 ], [ 34198855384118055989774019714084284607152642751190185031160830737984106466825, 50091975249850495590192550928077098526392126317690594853380942936943511566748, 82821224010440219461116506221592230660592360305266834070956225480688805987782 ], [ 44692908537542921388721557652293950830728673227605735396255620821721247706746, 86303046675560156022221798070497825327652849653693114279064416140443550145135, 25774132105242471740738652205562372489424541515376008388300106346755509211237 ], [ 103371574413557665181969748049543969481794604073622278983532046290983238979971, 15864399438093679710696118414562945892156489123355478934030614804022876369983, 54776456658598351376132617111181472299022005760051955110025505232956220720011 ], [ 63341128072830221873124956390298090362285184652738502327724967039766171538206, 11733122287893233193041134288448337239823392760363833328527972874375992506185, 55589451739589363242556596652770241463015149077817786903879419739309759578175 ], [ 27288717930840976736680809241382164215651583919640225703008945311488199140521, 70952066043757850812973802542731941610375006626643053263121657775586502932574, 70999334731245338502230582908105212782583996043864821203745436191377548842962 ], [ 46977534818805503250026505243185583478497804552247128876416946585364297578313, 85888803887249272531039133914745482794189393882435176657644947019816666997866, 115439058221796341851223357555191987336992737315776925913826898155265301156513 ], [ 108742045161968083170793999806136654493975359192544979494514159017986130950145, 55276373164891899555674217114895276904618874120130236173518191824641067518095, 38249790543512769372950721119118070697179260436542072817927568583554674034872 ], [ 80679385259005022311454077061638968975436785982614413209061244151516600200604, 38830127938935154036365672021650382727492249584897878321818743263930063797867, 1615604521298534145852491795189029226912426630714907710141135634092303903692 ], [ 68426646935507652864321803938637509374411880258163567604422214441877403558563, 49485206808907344546224756822956202192819461158084832051644535076762086911094, 5506738747141944929476836768389643342000107449635926313949384197297785179392 ], [ 75749110106887185029696128609664986507851190155862064026568376511601948342562, 103134910436105078628750146848715499694625558345743178409736128330081634012939, 44629335752019242725824498152097689780496323404757053504483657690141328743571 ], [ 91018041996616883539059450083078485404853400346892984297021173939461655057767, 11461890292925254499816979898090493650892053286982534818266508401647599070685, 40031373887348334200664348038188275286628600246735900840022955444430590281855 ], [ 1370687679926407589411963949541005511534305373551132425701086586910259635693, 107619305183424867953063642433255944948673145351534928767503637716296709264685, 85513484602329200511731250031521439738521337009477868919113331987207571383694 ], [ 44944287357591856363247256091485039648533597543208271827409192476451290982779, 23175840683019426535583923882772506992218394035175827240603279300793913605553, 80031135715265348665934774384368935350707832014864718995937062885248400818264 ], [ 17694567492186494847567960676252271679297743299805709379745528289640192535059, 71355530734203596192754364284929825508213810679176506903309636275867854701706, 102233035159694340569371315519189828565187309319219185159132617914136413644659 ], [ 54456482747307877036840932303806534594320856321791174091833811110252672255623, 32998682782651923096991067227828367025494847948287781286016129232181211768899, 18443963929422435176984400249169266653848364275404381769823306629634461819686 ], [ 2404814179589202385430703159800974435225758080132560432960864443808482348681, 33576437303174752996063351920550159305060168912109415419982873233118909715201, 100614626430112511848206158910219447084927962265787443711244786060546283770750 ], [ 115745414399683823307868521314846890210612184688338219317351943089729115155364, 79438235079169283727785836919328790019797981743656243081628185669211413227225, 102806512769931746523999370669354592734153941662103644543564851908427108413913 ], [ 18426657627489841307261634267238401226059547378719104932708309997051748743769, 62590041951703184253678233264344446748127485210977060559306195540330092605362, 101530409927644823892719262290513582065237179361817304023613215463814779925895 ], [ 74386971640345348892273553558534056423360473891327412428528026398196155593717, 112531297864138795074095127404777305273759611453695096499330894409552283933946, 18823749967655963380272028819243750152361266207453980896157770996332423395082 ], [ 19106188598360386995507879795657171606222760661548416372498541207700966318284, 100617844853844596276395700912501356057588002934486917893968678432205687541476, 43736575626650901378832954845740205926921653011368690509563749617513006791484 ], [ 90826305454088332506331106642552006622072207363916469718022991443620544472546, 53758585234453282306365116576836864660792431524619925164067935733611806020238, 82201873555529998458133190118421768098123248026473202342997665073076665973761 ], [ 26964884110356441854854146441983840112586567210061799395519700568901705979391, 1501580300208786477647896676022784131292995291248556256029839365072061388853, 74663505428203350509657969904492520642046783183792753210740041094249533787195 ], [ 30867701522043889635892145388908689718746952318295454393379231437327806517839, 103976891956739383229279105730248953588226973172938577085394805051492378931690, 95050317462894118042891010248169813822197290013821053762551094263011582770872 ], [ 91625463520733170536123384098608666318804256815524871957315735711271742421480, 18421764663198939270481619830994446270847508651060531249062628134724012834678, 48334336563886233195718722096743040222545484109821164105150318374001163713165 ], [ 103064540920389706885216566103866388349445461442577057115890241415106585943059, 93557418383080341475950855462894077919034434666441577156007046090636823710718, 5027052615852822061753823925815925894133647383995174293658504267200461685357 ], [ 92080617417968225877643047516649852660902234175180899982216286691685945363569, 16410973208434267587548600922795823406156890013721990057263520578610923809844, 67365944641539915969665344202352251869423069523524222146230967868391275008227 ], [ 6159561898351927490523303554903483755096522561484631083019517022991878007250, 40353595861455770779106431851830080611219657721423578311317916723690860959197, 70771528439745244346695359744161029464126444827213217436535504331137136741465 ], [ 26014860908695329456449800888732251794635965791744084336829431449032048912766, 97126322320255761721732297914656320097635724679029727859661301686364386778040, 29627148788686640914536827943478838605842335191276479094899001742330086803923 ], [ 95638155978081454594748375621553851019955800860992571438989927312610110006635, 106704752213663488838283609628683569783251650568773792767027643662696040553298, 16725629198799460288259231610659921992174496734119920477389778451623621034370 ], [ 86374304417545719890118180914775030188473989874917183072739411192768588646497, 112793359871613653484714387011745700719066770376294753104591899106143083860660, 93975497629053209581870367660816868978543483441305949414816232807735190601440 ] ], iv: d76bc487aedfe1aedeb9ae3ef867b81f, enc: c661c1ca54c4142afc81f5ea94256137c77e96eae909254cdaa2e4409e90fc3551b14b9d33b7e2a0fea48e18f12a9aa7 }问题代码import os, hashlib, json from Crypto.Cipher import AES from Crypto.Util.Padding import pad from Crypto.Util.number import long_to_bytes, bytes_to_long p 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F a 0 b 7 n 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141 Gx 0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798 Gy 0x483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8 def inv_mod(val, mod): return pow(val, -1, mod) def point_add(P, Q): if P is None: return Q if Q is None: return P x1, y1 P x2, y2 Q if x1 x2 and y1 ! y2: return None if P Q: lam (3 * x1 * x1 a) * inv_mod(2 * y1, p) % p else: lam (y2 - y1) * inv_mod(x2 - x1, p) % p x3 (lam * lam - x1 - x2) % p y3 (lam * (x1 - x3) - y1) % p return (x3, y3) def point_mul(k, P): R None Q P while k 0: if k 1: R point_add(R, Q) Q point_add(Q, Q) k 1 return R G (Gx, Gy) flag bDASCTF{************************************} d bytes_to_long(os.urandom(32)) % n Q point_mul(d, G) NUM_SIGS 40 messages [] sigs [] for i in range(NUM_SIGS): msg ftransaction_{i:04d}.encode() h_i int(hashlib.sha256(msg).hexdigest(), 16) % n k_i bytes_to_long(os.urandom(31)) R_i point_mul(k_i, G) r_i R_i[0] % n s_i inv_mod(k_i, n) * (h_i d * r_i) % n messages.append(msg.decode()) sigs.append((h_i, r_i, s_i)) key hashlib.sha256(long_to_bytes(d)).digest()[:16] iv os.urandom(16) enc AES.new(key, AES.MODE_CBC, iv).encrypt(pad(flag, 16)) output { curve: {p: p, a: a, b: b, n: n, Gx: Gx, Gy: Gy}, Q: [Q[0], Q[1]], messages: messages, signatures: [(h, r, s) for h, r, s in sigs], iv: iv.hex(), enc: enc.hex(), } with open(data.json, w) as f: json.dump(output, f, indent2)解题代码ECDSA 签名中的随机数 k_i 只用了 31 字节248 bits远小于曲线阶 n256 bits。这是一个经典的 有偏 nonce攻击。SageMath LLL对每个签名计算 c_i s_i · r_i⁻¹ mod nv_i −h_i · r_i⁻¹ mod n消去 d 得到 k_i ≡ α_i · k₀ β_i (mod n) 方程组构造 41 维格矩阵所有短向量分量 2^248BKZ-30 归约恢复 k₀ → 反推 d。import json, sys with open(data.json) as f: data json.load(f) n int(data[curve][n]) p int(data[curve][p]) Gx int(data[curve][Gx]) Gy int(data[curve][Gy]) Qx int(data[Q][0]) Qy int(data[Q][1]) sigs data[signatures] K 2^248 # 椭圆曲线 F GF(p) E EllipticCurve(F, [0, 7]) G E(Gx, Gy) Q E(Qx, Qy) m len(sigs) # Step 1: 计算 c_i, v_i c_list [] v_list [] for sig in sigs: hi, ri, si int(sig[0]), int(sig[1]), int(sig[2]) ci (si * inverse_mod(ri, n)) % n vi (-hi * inverse_mod(ri, n)) % n c_list.append(ci) v_list.append(vi) # Step 2: 消去 d得到 k_i α_i * k_0 β_i (mod n) alpha_list [] beta_list [] c0, v0 c_list[0], v_list[0] for i in range(1, m): ci_inv inverse_mod(c_list[i], n) ai (ci_inv * c0) % n bi (ci_inv * (v0 - v_list[i])) % n alpha_list.append(ai) beta_list.append(bi) # Step 3: 构造 (m1) × (m1) 格矩阵 dim (m - 1) 2 # 41 MM matrix(ZZ, dim, dim) for i in range(m - 1): MM[i, i] n # n 对角线 k0_col m - 1 for i in range(m - 1): MM[m - 1, i] alpha_list[i] # α₁..α₃₉ MM[m - 1, k0_col] 1 # k₀ 系数 const_col m for i in range(m - 1): MM[m, i] beta_list[i] # β₁..β₃₉ MM[m, const_col] K # K # Step 4: BKZ LLL 归约 L MM.BKZ(block_size30, fprr, precision200) L2 MM.LLL() # Step 5: 从短向量提取 k₀ → 计算 d def verify(dc): 验证 Q d*G 且 k_i K dc_int int(dc) if dc_int 0 or dc_int n: return False if (dc_int * G) ! Q: return False for i in range(min(3, m)): hi, ri, si sigs[i] kc (inverse_mod(si, n) * (hi dc_int * ri)) % n if kc K: return False return True d_found None for name, L_mat in [(BKZ, L), (LLL, L2)]: for i, row in enumerate(L_mat[:80]): if abs(int(row[-1])) K: # 最后一列 ±K k0 abs(int(row[-2])) # 倒数第二列 k₀ if 0 k0 K: dc (c0 * k0 v0) % n # d c₀k₀ v₀ (mod n) if verify(dc): d_found dc break if d_found: break print(fd {d_found})再利用key SHA256(long_to_bytes(d))[:16]AES-CBC 解密得到 flagimport hashlib from Crypto.Cipher import AES from Crypto.Util.Padding import unpad from Crypto.Util.number import long_to_bytes d 69733894115169365517439430123407937761015055472912247236884018827222720875663 iv bytes.fromhex(d76bc487aedfe1aedeb9ae3ef867b81f) enc bytes.fromhex(c661c1ca54c4142afc81f5ea94256137c77e96eae909254cdaa2e4409e90fc3551b14b9d33b7e2a0fea48e18f12a9aa7) key hashlib.sha256(long_to_bytes(d)).digest()[:16] cipher AES.new(key, AES.MODE_CBC, iv) flag unpad(cipher.decrypt(enc), 16) print(flag.decode())
