周六打了下DASCTF
没了
complex_enc
题目描述： 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 from Crypto.Util.number import *import randomfrom secret import flagdef GET_KEY (n ): sum =2 key=[1 ] for i in range (n): r=random.randint(0 ,1 ) x=sum +random.randint(0 ,n)*r key.append(x) sum +=x return key def enc (m,k ): cipher_list = [] for i in range (len (m)): if m[i] == 1 : cipher_list.append(m[i] * k[i]) cipher = sum (cipher_list) return cipher m=bytes_to_long(flag) m = [int (bit) for byte in flag for bit in format (byte, '08b' )] key=GET_KEY(len (m)) c=enc(m,key) with open ('output.txt' , 'w' ) as f: f.write(str (c)) f.write(str (key))
超递增序列
exp:
1 2 3 4 5 6 7 8 9 10 11 from Crypto.Util.number import *c = 287687761937146187597379915545639385740275457170939564210821293233370716878150576 key = [1 , 2 , 87 , 99 , 190 , 380 , 760 , 1702 , 3350 , 6712 , 13302 , 26669 , 53257 , 106512 , 213212 , 426262 , 852583 , 1705083 , 3410164 , 6820581 , 13640909 , 27281818 , 54563749 , 109127508 , 218254958 , 436509851 , 873019897 , 1746039768 , 3492079367 , 6984158992 , 13968317822 , 27936635563 , 55873271257 , 111746542368 , 223493084736 , 446986169472 , 893972338944 , 1787944677888 , 3575889355776 , 7151778711750 , 14303557423366 , 28607114846668 , 57214229693336 , 114428459386792 , 228856918773559 , 457713837547023 , 915427675094046 , 1830855350188252 , 3661710700376344 , 7323421400752912 , 14646842801505675 , 29293685603011275 , 58587371206022773 , 117174742412045483 , 234349484824090806 , 468698969648181659 , 937397939296363271 , 1874795878592726601 , 3749591757185453143 , 7499183514370906547 , 14998367028741812852 , 29996734057483625898 , 59993468114967251756 , 119986936229934503501 , 239973872459869007099 , 479947744919738013939 , 959895489839476027878 , 1919790979678952055983 , 3839581959357904111739 , 7679163918715808223719 , 15358327837431616447319 , 30716655674863232894717 , 61433311349726465789458 , 122866622699452931578804 , 245733245398905863157495 , 491466490797811726314990 , 982932981595623452629980 , 1965865963191246905260222 , 3931731926382493810520182 , 7863463852764987621040623 , 15726927705529975242080987 , 31453855411059950484161974 , 62907710822119900968323970 , 125815421644239801936647918 , 251630843288479603873295836 , 503261686576959207746591710 , 1006523373153918415493183613 , 2013046746307836830986367190 , 4026093492615673661972734253 , 8052186985231347323945468456 , 16104373970462694647890936894 , 32208747940925389295781874025 , 64417495881850778591563748059 , 128834991763701557183127495888 , 257669983527403114366254991760 , 515339967054806228732509983520 , 1030679934109612457465019967093 , 2061359868219224914930039934133 , 4122719736438449829860079868450 , 8245439472876899659720159736935 , 16490878945753799319440319473651 , 32981757891507598638880638947330 , 65963515783015197277761277894728 , 131927031566030394555522555789579 , 263854063132060789111045111579109 , 527708126264121578222090223158048 , 1055416252528243156444180446316096 , 2110832505056486312888360892632193 , 4221665010112972625776721785264450 , 8443330020225945251553443570528835 , 16886660040451890503106887141057670 , 33773320080903781006213774282115477 , 67546640161807562012427548564230882 , 135093280323615124024855097128461699 , 270186560647230248049710194256923398 , 540373121294460496099420388513846796 , 1080746242588920992198840777027693592 , 2161492485177841984397681554055387246 , 4322984970355683968795363108110774528 , 8645969940711367937590726216221549105 , 17291939881422735875181452432443098117 , 34583879762845471750362904864886196180 , 69167759525690943500725809729772392360 , 138335519051381887001451619459544784838 , 276671038102763774002903238919089569616 , 553342076205527548005806477838179139174 , 1106684152411055096011612955676358278348 , 2213368304822110192023225911352716556750 , 4426736609644220384046451822705433113446 , 8853473219288440768092903645410866226907 , 17706946438576881536185807290821732453830 , 35413892877153763072371614581643464907890 , 70827785754307526144743229163286929815519 , 141655571508615052289486458326573859631099 , 283311143017230104578972916653147719262229 , 566622286034460209157945833306295438524626 , 1133244572068920418315891666612590877049074 , 2266489144137840836631783333225181754098066 , 4532978288275681673263566666450363508196132 , 9065956576551363346527133332900727016392264 , 18131913153102726693054266665801454032784553 , 36263826306205453386108533331602908065569081 , 72527652612410906772217066663205816131138180 , 145055305224821813544434133326411632262276342 , 290110610449643627088868266652823264524552684 , 580221220899287254177736533305646529049105368 , 1160442441798574508355473066611293058098210736 , 2320884883597149016710946133222586116196421472 , 4641769767194298033421892266445172232392842944 , 9283539534388596066843784532890344464785686063 , 18567079068777192133687569065780688929571371951 , 37134158137554384267375138131561377859142743902 , 74268316275108768534750276263122755718285487804 , 148536632550217537069500552526245511436570975608 , 297073265100435074139001105052491022873141951360 , 594146530200870148278002210104982045746283902576 , 1188293060401740296556004420209964091492567805360 , 2376586120803480593112008840419928182985135610512 , 4753172241606961186224017680839856365970271221024 , 9506344483213922372448035361679712731940542442048 , 19012688966427844744896070723359425463881084884096 , 38025377932855689489792141446718850927762169768220 , 76050755865711378979584282893437701855524339536412 , 152101511731422757959168565786875403711048679072824 , 304203023462845515918337131573750807422097358145648 , 608406046925691031836674263147501614844194716291296 , 1216812093851382063673348526295003229688389432582797 , 2433624187702764127346697052590006459376778865165617 , 4867248375405528254693394105180012918753557730331006 , 9734496750811056509386788210360025837507115460662129 , 19468993501622113018773576420720051675014230921324265 , 38937987003244226037547152841440103350028461842648406 , 77875974006488452075094305682880206700056923685296910 , 155751948012976904150188611365760413400113847370593722 , 311503896025953808300377222731520826800227694741187444 , 623007792051907616600754445463041653600455389482374933 , 1246015584103815233201508890926083307200910778964749821 , 2492031168207630466403017781852166614401821557929499642 , 4984062336415260932806035563704333228803643115858999284 , 9968124672830521865612071127408666457607286231717998666 , 19936249345661043731224142254817332915214572463435997301 , 39872498691322087462448284509634665830429144926871994535 , 79744997382644174924896569019269331660858289853743989190 , 159489994765288349849793138038538663321716579707487978260 , 318979989530576699699586276077077326643433159414975956596 , 637959979061153399399172552154154653286866318829951913129 , 1275919958122306798798345104308309306573732637659903826311 , 2551839916244613597596690208616618613147465275319807652591 , 5103679832489227195193380417233237226294930550639615305147 , 10207359664978454390386760834466474452589861101279230610294 , 20414719329956908780773521668932948905179722202558461220588 , 40829438659913817561547043337865897810359444405116922441176 , 81658877319827635123094086675731795620718888810233844882508 , 163317754639655270246188173351463591241437777620467689764860 , 326635509279310540492376346702927182482875555240935379529854 , 653271018558621080984752693405854364965751110481870759059704 , 1306542037117242161969505386811708729931502220963741518119363 , 2613084074234484323939010773623417459863004441927483036238705 , 5226168148468968647878021547246834919726008883854966072477346 , 10452336296937937295756043094493669839452017767709932144954692 , 20904672593875874591512086188987339678904035535419864289909384 , 41809345187751749183024172377974679357808071070839728579818768 , 83618690375503498366048344755949358715616142141679457159637536 , 167237380751006996732096689511898717431232284283358914319275072 , 334474761502013993464193379023797434862464568566717828638550144 , 668949523004027986928386758047594869724929137133435657277100288 , 1337899046008055973856773516095189739449858274266871314554200576 , 2675798092016111947713547032190379478899716548533742629108401375 , 5351596184032223895427094064380758957799433097067485258216802527 , 10703192368064447790854188128761517915598866194134970516433605054 , 21406384736128895581708376257523035831197732388269941032867210108 , 42812769472257791163416752515046071662395464776539882065734420216 , 85625538944515582326833505030092143324790929553079764131468840607 , 171251077889031164653667010060184286649581859106159528262937681073 , 342502155778062329307334020120368573299163718212319056525875362112 , 685004311556124658614668040240737146598327436424638113051750724224 , 1370008623112249317229336080481474293196654872849276226103501448448 , 2740017246224498634458672160962948586393309745698552452207002896896 , 5480034492448997268917344321925897172786619491397104904414005793914 , 10960068984897994537834688643851794345573238982794209808828011587706 , 21920137969795989075669377287703588691146477965588419617656023175412 , 43840275939591978151338754575407177382292955931176839235312046350824 , 87680551879183956302677509150814354764585911862353678470624092701691 , 175361103758367912605355018301628709529171823724707356941248185403485 , 350722207516735825210710036603257419058343647449414713882496370806824 , 701444415033471650421420073206514838116687294898829427764992741613648 , 1402888830066943300842840146413029676233374589797658855529985483227499 , 2805777660133886601685680292826059352466749179595317711059970966454839 , 5611555320267773203371360585652118704933498359190635422119941932909634 , 11223110640535546406742721171304237409866996718381270844239883865819325 , 22446221281071092813485442342608474819733993436762541688479767731638735 , 44892442562142185626970884685216949639467986873525083376959535463277328 , 89784885124284371253941769370433899278935973747050166753919070926554729 , 179569770248568742507883538740867798557871947494100333507838141853109648 , 359139540497137485015767077481735597115743894988200667015676283706219166 , 718279080994274970031534154963471194231487789976401334031352567412438331 , 1436558161988549940063068309926942388462975579952802668062705134824876530 , 2873116323977099880126136619853884776925951159905605336125410269649753060 , 5746232647954199760252273239707769553851902319811210672250820539299506381 , 11492465295908399520504546479415539107703804639622421344501641078599012695 , 22984930591816799041009092958831078215407609279244842689003282157198025444 , 45969861183633598082018185917662156430815218558489685378006564314396050678 , 91939722367267196164036371835324312861630437116979370756013128628792101318 , 183879444734534392328072743670648625723260874233958741512026257257584202636 , 367758889469068784656145487341297251446521748467917483024052514515168405272 , 735517778938137569312290974682594502893043496935834966048105029030336810544 , 1471035557876275138624581949365189005786086993871669932096210058060673621088 , 2942071115752550277249163898730378011572173987743339864192420116121347242216 , 5884142231505100554498327797460756023144347975486679728384840232242694484649 , 11768284463010201108996655594921512046288695950973359456769680464485388969041 , 23536568926020402217993311189843024092577391901946718913539360928970777938082 , 47073137852040804435986622379686048185154783803893437827078721857941555876305 , 94146275704081608871973244759372096370309567607786875654157443715883111752579 , 188292551408163217743946489518744192740619135215573751308314887431766223505070 , 376585102816326435487892979037488385481238270431147502616629774863532447010118 , 753170205632652870975785958074976770962476540862295005233259549727064894020344 , 1506340411265305741951571916149953541924953081724590010466519099454129788040580 , 3012680822530611483903143832299907083849906163449180020933038198908259576081160 , 6025361645061222967806287664599814167699812326898360041866076397816519152162452 , 12050723290122445935612575329199628335399624653796720083732152795633038304324883 , 24101446580244891871225150658399256670799249307593440167464305591266076608649853 , 48202893160489783742450301316798513341598498615186880334928611182532153217299508 , 96405786320979567484900602633597026683196997230373760669857222365064306434599262 , 192811572641959134969801205267194053366393994460747521339714444730128612869198530 , 385623145283918269939602410534388106732787988921495042679428889460257225738396863 ] key_dict = {i: key[i] for i in range (len (key))} tmp = [0 ] * len (key) for index,i in enumerate (key[::-1 ]): if c >= i: tmp[index] = 1 c -= i print (long_to_bytes(int ('' .join(str (i) for i in tmp[::-1 ][:-1 ]),2 )))
1z_RSA
题目描述：
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 sympy import *import osfrom secrets import flagnbit =130 e = 3 l = getPrime(505 ) m = bytes_to_long(flag + os.urandom(64 )) assert len (flag) == 29 while True : p, q = getPrime(nbit), getPrime(nbit) PQ = int (str (p<<120 )+str (q)) QP = int (str (q<<120 )+str (p)) if isPrime(PQ) and isPrime(QP): break n = PQ * QP PP = nextprime((PQ >> 190 ) * (QP & (2 ** 190 - 1 ))) QQ = nextprime((QP >> 190 ) * (PQ & (2 ** 190 - 1 ))) N = PP * QQ M = pow (m,1 ,l) c = pow (m,e,N) print ('n =' , n)print ('M =' , M)print ('l =' , l)print ('c =' , c)''' n = 18339446336492672809908730785358232636383625709800392830207979464962269419140428722248172110017576390002616004691759163126532392634394976712779777822451878822759056304050545622761060245812934467784888422790178920804822224673755691 M = 36208281423355218604990190624029584747447986456188203264389519699277658026754156377638444926063784368328407938562964768329134840563331354924365667733322 l = 56911058350450672322326236658556745353275014753768458552003425206272938093282425278193278997347671093622024933189270932102361261551908054703317369295189 c = 720286366572443009268610917990845759123049408295363966717060100862857351750759651979922104897091176824666482923148635058966589592286465060161271579501861264957611980854954664798904862706450723639237791023808177615189976108231923 '''
题目分析： \[
\begin{align*}
&PQ = p * 2^{120} * 10^{40} + q\\
&QP = q * 2^{120} * 10^{39} + p\\
&n = PQ * QP = pq * (2^{240} * 10^{79} + 1) + (p^2 + 10 * q^2) *
2^{120} * 10^{39}\\
&可以知道(2^{240} * 10^{79} + 1) < (p^2 + 10 * q^2) * 2^{120} *
10^{39}\\
&不过它们相差并不大，((p^2 + 10 * q^2) * 2^{120} *
10^{39})//(2^{240} * 10^{79} + 1) = 一个很小的数a\\
&故pq = n // (2^{240} * 10^{79} + 1) - a\\
&爆破即可得到pq,得到pq后(p^2 + 10 * q^2)也就出来了\\
&之后解方程即可得到p,q,如此PQ和QP也就出来了
\end{align*}
\]
PS：p，q的10进制位数可能是39，也可能是40
此处具体是什么可以通过n的位数来确定。（自行去测一测就知道了）
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 sympy import *n = 18339446336492672809908730785358232636383625709800392830207979464962269419140428722248172110017576390002616004691759163126532392634394976712779777822451878822759056304050545622761060245812934467784888422790178920804822224673755691 nn = n // (2 ** 240 * 10 ** 79 + 1 ) cnt = 0 for i in range (nn - 500 ,nn + 500 ): cnt += 1 print (cnt) if (n - i * (2 ** 240 * 10 ** 79 + 1 )) % (2 ** 120 * 10 ** 39 ) == 0 : leak = (n - i * (2 ** 240 * 10 ** 79 + 1 )) // (2 ** 120 * 10 ** 39 ) p,q = symbols('p q' ) res = solve([p ** 2 + 10 * q ** 2 - leak, p * q - i],[p,q]) for pp,qq in res: if pp > 0 and qq > 0 : PQ = int (str (int (pp) << 120 ) + str (int (qq))) QP = int (str (int (qq) << 120 ) + str (int (pp))) print (PQ) print (QP) break break ''' PQ = 1612551962023919669547657045404858968387328704389406190014139631069342728192855604426214387476576649090490109822073 QP = 11372933566416532007055156607134588768203078133513243807951567056424906260481213149261930568621267125437333569321667 '''
PQ，QP得到之后N也就得到了 \[
\begin{align*}
&m的位数：(29 + 64) * 8 = 744\\
&可以知道m = M + k * l\\
&m-744bit,M-505bit,l-505bit\\
&=>k-239bit，那么copper一下\\
&f = (M + k * l)^3
\end{align*}
\] 未知位数239
大概粗略算一下：\(N - 760bit，760 * (1/3 -
0.02) \approx 238\) ，接近239，那我们把eplison设成0.02就行
1 2 3 4 5 6 7 8 9 10 11 12 13 from Crypto.Util.number import *N = 763933528218428362740063144747893290714655295576768532896029874141179804730143020017430379534079773751531037961074867132893544981605022026151484151321515584652838724809597675412676810669583078026377048734720511960708515190930979 M = 36208281423355218604990190624029584747447986456188203264389519699277658026754156377638444926063784368328407938562964768329134840563331354924365667733322 l = 56911058350450672322326236658556745353275014753768458552003425206272938093282425278193278997347671093622024933189270932102361261551908054703317369295189 c = 720286366572443009268610917990845759123049408295363966717060100862857351750759651979922104897091176824666482923148635058966589592286465060161271579501861264957611980854954664798904862706450723639237791023808177615189976108231923 PR.<k> = PolynomialRing(Zmod(N)) f = (M + k * l) ^ 3 - c f = f.monic() kk = f.small_roots(X = 2 ^ 239 , epsilon = 0.02 )[0 ] m = M + kk * l print (long_to_bytes(int (m)))
found
题目描述：
task.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 from Crypto.Util.number import *from random import *from secret import flagfrom sympy import *bits = 1024 l = 138833858362699289505402947409766595473722379891580589518174731439613184249727659678966809301611194545239974736175752769503863392697421092435438747741790652435801956708356186578269272819715592752821497122516109657809748674185639254430403157877064556216401002688452227124543508128414591884297632663910714681207 assert isPrime(l)def generate_prime (bits ): return randprime(2 **(bits-1 ), 2 **bits) def fun (data,y,n ): return sum ([data[i] * pow (y,i,n) for i in range (len (data))]) % n def gen (x, y, z, w, n ): data = [randint(n // 4 , n) for _ in range (10 )] leak1 = pow (x + pow (y, z, n), w, n) leak2 = fun(data, y, n) return data, leak1, leak2 def encrypt (l,m,n ): mm = bin (m)[2 :].zfill((m.bit_length() // 8 + 1 ) * 8 ) length = len (mm) c = [] s = [] for i in range (length): a = randint(1 , n) s.append(pow (a, length, n)) for j in range (length): c.append(pow (a,int (mm[j]),n) * s[j] % n) return c p, q = [generate_prime(bits) for _ in range (2 )] r = generate_prime(bits // 4 ) n = p ** 2 * q * r e1 = generate_prime(128 ) e2 = generate_prime(128 ) phi1 = p * (p - 1 ) * (q - 1 ) * (r - 1 ) phi2 = (p - 1 ) * (p - 2 ) * (q - 2 ) * (r - 2 ) d1 = inverse(e1, phi1) d2 = inverse(e2, phi2) t = getRandomRange(n // 4 , n) data, leak1, leak2 = gen(r, t, e1, d1, n) m = bytes_to_long(flag) c = encrypt(l, m, n) with open ('output.txt' ,'w' ) as f: f.write(f'n = {n} \n' ) f.write(f'e1 = {e1} \n' ) f.write(f'ed = {e2 * d2} \n' ) f.write(f'data = {data} \n' ) f.write(f'leak1 = {leak1} \n' ) f.write(f'leak2 = {leak2} \n' ) f.write(f'c = {c} ' )
output.txt: 1 2 3 4 5 6 7 n = 214189098485907407681203562477141616514627803973812423866137712061520397412283304756125615530911730190509122275581663270324067756428063773995710185422014937638013530995658678484408224195008950739065869752467503449898424403807629035201754909341605483646512086652631108980705938767234014655512244203488129210213088484751842078315616338034946509581920246058635374657554442252420460618886159118637553788160140879059706396460523335509806462257352635091258764319929220939182156189941663585022210802535804264016891744621140144859992731921592420695928759275864955373537480452694672023754214092487216273962896544919015905264313446548396379618341043583032673900608611135254563997519445284222602183035105369017270389887769617942348731416370092842162632579589494341854993600540689280924183073089475208340685636482246115054414077320832052204722015428500812923185709772796221129375539131726373252482799298746655947376656143301849009181701495003174228813534439192414768762803822975277797520157025175837722175072241107 e1 = 228246137071395297228647198378234575667 ed = 8238783462304466047370608758999664260116370123313022088538091162770601739116628806460542503654403361322931229200817491683096695046254053538710523477982774850621979868926682997393573131262930645387042545807254462907502249936746101134745335780459335767976492133149192198880107516742633966664923533160167069625322094242414191994000927842976472080411237834215691897822371792754587587715760051582955795834883174474583440371035173351136370107484245425758954400434828144460697864191261513214008084848001467959369934964428291290009392620134215667173457413630882523557102057539902909381706460767916715499306316003286608457624713509816056636249181986636842368337873445101552453774405927824096616431732124001038586048766823358751593885500314021939046991953062562270782883182855487098328026196086288533138907969729187779739950764344200364360079479047132746676799216491472345637845220255139152063453462176656553357596450484408472263570570448409671724853674399060252094955913831086556844240273178815236110565265190938731402297513542863173575371193878977 data = [193603701385184594048276446297744737347844155455814199029229254370819095264220091974816768902119954926302801843118379533491441884584844862023717354363708931808754214591949274005116312602470266455224300745234378334739914442825957439676825816095286879671572856543573545412426697260350097106803125967045751538098379621554276706631902573968990932601545418908413611604795306678592420345368691508562784200191380882967774951366660610843674931403729350555093525384690652277519795623276235852980416858565358154003587878300208098528966832086239417979777391494681625422699075412054104555896375767200357780876214697482279539710617118624420492042212547431773629635909699586152943845737306422831568007133429913359996553231286016257371771084485222883699365371680464830578176541643800648575916368592100327219233106270736571096051012729364523664646596211619481067284511430638593710269523511115314879651675455928382531667709288358296983594144246374318217425898507659427332121250143906371370125596969310464798423126240249 , 83232380612179085215826775913833896343479487597490293209447462059425432761467292984732079051574095682196847182332185514688509237497856017321217461683610482188959719499015629286095774176457491111653557957143999953334057852475101888350978943356388186642898590728812465940108330672190227928625421072749647024169559486983638480319685288547544296403054632634251404824205877193034192901652740716146996859596783202683876256251962212218890324498229265768330077077203057547593303563888024392129443843671073192707033672163475010779991178255053309612338324024330477838635221307103942083495150839612907917081589848058122439842094169468710994236662623064896345386689141107875109648711753412281754135052688257147784328999027173384430726870349245991383171344678832691432716926162465638492315682356063658116939771331253319156940745604345000062001181547782395699365598033029965876642506023695814759189319385499447252988850495864839083230318317981608453608237316346106115145618735235568065107952583780196118328790150668 , 124029091531781837962028113090891229294114028863714189021516519574129047489034463881315547790172815327938355138914693838967798779443291333910534381361187962962211286653473935493258148348900967873113580541784043054246605269411211310480597957210474116510188315932965508355182797058421774750514302992909396649836444171237873614791492630901328222719225432769644902694765224307250768110734386675470368037103624198545718645570697628428375762234137964943035358096894458271219594556780565100705603065942562805910805066341463216433921785734441069232766996055943985958999873124870066787588298481039034434476751819151203006932390088920722328035663237500463244782778252107794331963770339097484572423150244547488177952379501831335246484556589748671930152229193892849375083425231974250212167003455883859682356631577573979316259041674248398278005715972754743850288109105734019931884984180815338839040427348281561428946450368116928309897833525540729557152994911327587253232221945691931715727233240239217766670302737797 , 183843790887043402011598370503205679765096296266458133303727667969475876955550067091982110668362517989161075686937475587191630156303515396551552747395896439855271453014845870528495608475291770177930209914889772055798265588308998461073614393953301177130478090234899660317573598133689999452854596939233245447620411925677910051195341774760199462465323236659615328986387497112194938688648467440994427880524194706366507582972449860152444844726883830270055690915264386828203868698790531311672618879594353865799279708001022240970903686800926148905846427187554297638489620066186565413471680781555570353090800565169455785422276246128112933238219941576176045528857395489547919586696112825074357320009241545156387826567778313197682430812363865044448037674266021191342500951073854543139099758191759460732927377434328243127385966404963426977560325865114581829641002303741276624429925421529144276258595779792107410344907550974793123288477149591078697881754824614502477971850569510391169576115446384775760103371690229 , 77181491333455945581964325242677895484087511641751638314025871031862188693342644422469926996751891933595312224562658710026977124351245625357567306610633026710034325228119776532079710870381262899079582973396369685760835988946858436651701992338270031045842329350320465948557706153142357507371547722657387245712169797514661857231296527340158271569274281050502803588443964415706473620778191218694301701995011516227595325346642614102935318547327371194448611519374355163992727724271920609636416752265268455625828475046309417411350641630824310335290833466766886410952996256873847584658405040284125564777295671150020378326447929383302767250744865021112478842971725353014525757485093025086515069618536327355110519111251250847040981340091015719687780422065271394384964197564928514715001571354599930804427809172147344985789390354365168200779032355336019869878365166731683726800165060752463551011275760601115775930309162497471542196168545689657524323611832924586057251037468277241392800206625479037786453164131995 , 73205035147442530516214566541083478692362666963351034174641204890993061156341833361471382741487873993415218899233020829417422641475896996781945068981179750572071381475551179347015232091326075147030318977902658370163575233636401307304118105596868322641969122224481337149842240110750279029669943793523807188344793098836560729793248976539513619414902542761745226667216171972158652220051070681390437970409917700389687006847358602838776592534429644530645228108318238605302552858660163726279648930505220310801443744840742779282348562009764207578257256917013697781985201356590904691201881074465767578202400193526454559744215480337739543855294040255939855585220261434451321167296169707368494834534854246202066172245412926996804327758827974522254706927188752034945933413541030683585047306280808869310753485476053485102398055904623441252859333696664969196044181265131793421817842193722029204872190808835304869795476166974073284194940969149929858850315553170586579171931372841255653797967227240150024403686700318 , 130922536449620721874430591834893344565723848082365964975014011192154824561533294364763636501156167569463116422347814651711098794556121000604933883961221890226068691344209984798909070560094790519968140590302350163451597933415038932984088770323319866954739644053901699360711398638558276166591969032158320702311949515391689147215823312531012728672496602856530523058425713194004118786776568670195495029709727771569268007731817731032818592168140535384065850014708458707271415054346637938854605806067654806771791955707476012409629452391154116323782276692248254897822717314913613684100590993004116312109008343947373009165942573493957812296495916988918921330041670596637737127687419791813256185588201214925999361831016131784946056151576400022233684255417352789020121504134033344037825435901589346081468061266546900318139206924847037632306967700883103715011898296806759649283235666950730021534650640616764140909410457672528061603571546896273073945589966941026845451260864816435395290788038177260424513262717147 , 96020307736423653849681099694795070685318392824245445231848257362698325458566036467905776769825156536584712839602346179866978464981920356841237715655104343433403974116231994567630132803569400576444622531225108131322496097985483053317699953160469549824368749143254898694578961392541769475761696371400655038962884511045507167846158292753076394297765351578172464979038847441532742344288573442736399426813737731962675826287940983072154853450868147991567341729978830384900766355148407527995483455876179619037540839473665468552119956231652786409322560587534009434185272785914134531600273010117895225594128038118745517974999777061068383501122026199178725628075723534153891577896276333860794903571069058930821070459114902328164990286376387263324567783343401640370228177304680590970952056142474240123353904350590944037465570541270903463939790277478872854503844901980335251732525427700804955963610238700131824229633507486167186619924488205009021735744358474958921593273970059532393434485837844520676695250253818 , 70179739856827882014533856258768933317172692318810033540306741590616707369209255146711184424982274791424446113402776415419489619900890685813416198088324683031475573905382337205219919194813095298781099206022303955476518699780836375262573969549719034778449632890439019791098837172928410660181948068014058495402879740138532367574756729124558973222555734037856119443124996050898550301911936236705827128102625880992585253317343783711017535277283723063735482936442251712028665628766822410874182346801488486349311864283205496069261051995801486733862085378587473487850400998268984959754900117535252200774455334314910199051566060772584757900692014336924837851470210768677685669414832993403833367649813099107659677783796393020061413738567093031888744434338562745357883186640322598165729511817308735087619672370347973626978927281950583105981796610501521512515754484015947888094170824846319485769273061345748077326435513773977764989015743820427944157836645251581638303303228323898709077613114299155476100313184864 , 175652862673132475686135264158791277818478759588755931484235300532096345677648348588548215587849294084744263688721294017179822791852874995430439770093077380941242256704253340009646924105298769803641006601733958786682523820789623229457197488801223995838476613815010250443077607721307486493845540520896295758708091075424003453148901604173203609500517681152737967682849411739285402305515347569269249451853704828406093324891360458117496271442944605647179886014243335325177990618809463830971905827773785311843128136687528632548334476401223625520208122482489755175042406263025133251070642315226465801303000300019213393276150665866439726799770645200082982057683225700125654562928186376718742163294884560481313657925863409955867645132050087094728187550662632446842091403257126146302052277968469833986267484560410928566363881330254151524449882128468203017476574322404834981270285221728133785929308192500229958517894515501598313596447501741967442356143089865549390247424732308735417202543341648593495568759658573 ] leak1 = 63782905210425530505481328470901215858602521952143268285063726975781165023862017491713165035148561758359744187691236004961476685244204729186881465294593870263295057863529224333542417669099353919134017169079021119796312127454942459097916913630160780015465159099215782449518378655317557377730943183040588156411578967503892807601657964531263531800827109319360771506028467872403505576255454079928964831924379679811693997670940970879328723956168008599678202445646778122559604109680197340923640067256165995420276085239676074114984790470621236336955442487022895961512902129409872825988384566511568931733560589196495514916064010319354972344856680662983166422683519534959690898549129176191205471975798892082872953657585129852579114400603842863919636216016448322273003250153436580085016262564726570590917521967949071809656413167808022466093370500545030093675230568578130810948637578959017259848848965235015851786609346028580181557524008598197188435907179498427167374290247239043475093622634785391672663701563780 leak2 = 164672413727166337721772866174120090001862616525169315969424174412610694486913567414752676879059000161543960191013302451482547492432115422013012298207836023164304846473827400728343336837942904216130312606263701738236734690810362403432673024164173553927215310314954308227523856745581991136694642282091216197557529027661009649424727525610143053300188875828126262928055570667149587498799717883989617748569211692521249022845364829999098999961242961288235871016302642964967134624027387692331993011337128668923750920957011101171731606359456882239434664044073802224898066537743795029258834874316830952385525877115357530711935126892113666494741955018064580597273121999829121331202610749992150039102390905826245578147065592557989341002712478086016329470790557522670767213438205465130632789767891535615426167314729003703510227816955522793268816231554088672856958206359854051313036334217540137808313082440476308616336781858361392907337038725576212779598635717453175121497869836504186991949457946397544924556583220 c = []
题目分析
通过 \(e_2d_2\) 和 \(n\) 我们知道： \[
\begin{align*}
&e_2d_2-1=k*phi_2\\
&e_2d_2-1=k(p - 1)(p - 2)(q - 2)(r - 2)\\
&e_2d_2-1=k(p^2qr - 2p^2q - 2p^2r - 3pqr + ...)\\
&目的是求k进而求phi2\\
&\frac{e_2d_2-1}{n}=k+\frac{k(- 2p^2q - 2p^2r - 3pqr + ...)}{n}\\
&显然k(- 2p^2q - 2p^2r - 3pqr + ...)<n\\
&而(- 2p^2q - 2p^2r - 3pqr + ...) < 0\\
&所以\frac{k(- 2p^2q - 2p^2r - 3pqr + ...)}{n}=-1\\
&\Rightarrow k = \frac{e_2d_2 - 1}{n} + 1\\
&\Rightarrow phi2 = \frac{e_2d_2 - 1}{k}\\
&so现在已知的是phi2和n，但是里面有3个未知数，所以还得求出一个东西来\\
\end{align*}
\]
我们知道有: \[
\begin{align*}
&leak_1 \equiv (r + t^{e_1})^{d_1} \pmod n \\
&leak_2 \equiv\sum_{i=0}^{9}data_i * t^i\pmod n\\
&两个式子，两个未知数，这里毫无疑问是求\ r \ 了\\
&看到的想法就是通过\ leak_2\ 把\ t \ 求出来，然后计算\ (leak_1^{e_1}
- t^{e_1}) \ 就能得到\ r\ 了\\
&但是这个\ t \ 并不小，这种方式似乎求不出来\\
&那么能否消掉它呢
\end{align*}\\
\] 我们将式子变一下 \[
\begin{align*}
&f(t,r) \equiv (r + t^{e_1}) - leak_1^{e_1} \pmod n\\
&g(t) \equiv \sum_{i=0}^{9}data_i * t^i - leak_2\pmod n\\
\end{align*}\\
\] 对两个式子做一个结式，把 t 给消掉，但是由于 \(e_1\) 太大，故我们需要优化一下，考虑到
\(g(t) \equiv \sum_{i=0}^{9}data_i * t^i -
leak_2\pmod n\) ，即 \(g(t) =
kn\) ，我们知道在模 \(kn\)
下满足的式子，在模 \(n\)
下一定成立，所以在求 \(t^{e_1}\)
的时候再模一下多项式 \(g(t)\) ，这样得到的 \(f(t,r)\) 的度就低于10，之后让 \(f(t,r)\) 和 \(g(t)\) 做结式即可得到 \(r\)
(经过测试当调到 epsilon = 0.03 时我们能求出 \(r\) 来)
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 from Crypto.Util.number import * from random import *with open ('output.txt' ) as f: exec (f.read()) R.<t,r>=PolynomialRing(Zmod(n)) g = sum ([int (data[i]) * t ** i for i in range (len (data))]) - leak2 asist = t t_e = 1 cnt = 1 for i in bin (e1)[2 :][::-1 ]: cnt += 1 print (cnt) if i == '1' : t_e = (t_e * asist) % g asist = (asist * asist) % g f = r + t_e - pow (leak1,e1,n) h = f.sylvester_matrix(g, t).det().univariate_polynomial().monic() res = h.small_roots(X = 2 ** 256 ,epsilon = 0.03 ) if res: print (res[0 ])
\(如此r，phi_2，n均已知道，解个方程即可得到p，q\)
\[
\begin{align*}
&p,q求出后发现pow(l,\frac{p - 1}{2},p) = pow(l,\frac{q - 1}{2},q) =
-1\\
&所以可以知道l是p和q的二次非剩余\\
&又s \equiv a^{len(mm)} \mod n，其中len(mm)为偶数\\
&c_i = \begin{cases}
l * s^{len(mm)},j = 1\\
s^{len(mm)},j = 0
\end{cases}\\
&\Rightarrow(小费马)\\
&(l * s^{len(mm)})^\frac{p-1}{2} \equiv -1 \mod p\\
&\ \ \ \ \ (s^{len(mm)})^\frac{p-1}{2} \equiv \ \ \ 1 \mod p\\
&若pow(c_i,(p-1)//2,p) = -1,则x = 1\\
&若pow(c_i,(p-1)//2,p) = \ \ \ 1, 则x = 0\\
&由此得到flag\\
\end{align*}\\
\] exp2:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 from Crypto.Util.number import *from z3 import *with open ('output.txt' ) as f: exec (f.read()) r = 77477547161688496725906506626131775883966333151442864639104100690032824193233 k = (ed - 1 ) // n + 1 phi2 = (ed - 1 ) // k p = 168207689659417173628607066039457820275276732311636007089001107530860513351122555769649031031435042743185528528881857626080873859026128498997148721030271703030768717788591275936600239642357340350598106488044312274746860587888105379606096757814370419770414183228756583472285941821276338279728115488001890742673 q = 97707929018805957546753225343143490125285071269910025402668681477127527381672117514147518538470060994557862749309042238326448721045026099601424607832524228224510318920129326794773863846005792678034679056020514793964664097594210383339219122809427128901179158534676129014329576699155669500220463663254504200451 flag = '' for i in c: if pow (i,(p - 1 ) // 2 ,p) == 1 : flag += '0' else : flag += '1' print (long_to_bytes(int (flag,2 )))
Finally:
赛后看到别人wp 写的知道了令一种解法，直接求p，绕过了leak，这里贴一下：
\[
\begin{align*}
&ed \equiv 1\mod (p - 1)(p - 2)(q - 2)(r - 2)\\
&2^{ed} \equiv 2 + 2^{k(p - 1)(p - 2)(q - 2)(r - 2)} \equiv 2 \pmod
p\\
&p = gcd(2^{ed} - 2, n)
\end{align*}
\]
EZshamir
题目描述：
task.sage
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 import osfrom random import getrandbitsfrom hashlib import sha256, md5from Crypto.Util.number import *from Crypto.Cipher import AESfrom Crypto.Util.Padding import padfrom secret import flagclass Shamir : def __init__ (self, pbits, noise_bit, n, m ): self .pbits = pbits self .noise_bit = noise_bit self .n = n self .m = m self .p = getPrime(pbits) P.<x> = PolynomialRing(Zmod(self .p)) self .poly = P([bytes_to_long(sha256(os.urandom(32 )).digest()) for i in range (self .n)]) def sample (self ): t = getrandbits(self .pbits) y = int (self .poly(t)) noise = getrandbits(noise_bit) return (t, y | noise) def get_msg (self ): res = [] for i in range (self .m): res.append(self .sample()) return res pbits = 400 noise_bit = 32 n = 100 m = 75 shamir = Shamir(pbits, noise_bit, n, m) coefficient = shamir.poly() key = "" .join([str (i) for i in list (coefficient)[1 :]]) key = md5(key.encode()).digest() aes = AES.new(key = key, mode = AES.MODE_ECB) ct = aes.encrypt(pad(flag, 16 )) with open ("data.txt" , "w" ) as f: f.write(str (shamir.p)+'\n' ) f.write(str (shamir.get_msg())+'\n' ) f.write(str (bytes_to_long(ct))+'\n' )
data.txt
1 2 3 p = 1914861180127910915217161496032452354459288330404267938814385633318816795789745430689392291853522228462459760259540145551 a = [(871685718803663381427930478762339134295053004512609923589551466783266783810259304828550374243064535763376291757646963959 , 202160546047966750331912360731430418240633973593625005229082586127891061162361922677243409978233971196981357156050665207 ), (880630661134451484589856936400581718913135314681369937077374828269467594291354487238721693384105758714624990294669591318 , 1095968002726348118037606681187141462053336336722142181092378890939072246257043346524710197351420437134900753767241347071 ), (2201481802919131040050333908088433208558917203945919199978631826943299343536825970006258238556122903076523292840756434743 , 692254736946777374134144410762495005358360246411034340533738679554417430991182506230475828234351704793913692448647675007 ), (1378304382181829689586748896745391077371970833336011385982116414924775680216930605930619270704824436444608781376558454118 , 1349836972600983636760377380443471914884359770040030987799061599827409370783772298884084190105572886840534075250106753145 ), (1353153805805015283526548792279508930383121644895000056925297797888893262990508466655386951026647093911241738634749231794 , 708640659789589986759360580045421230914410242138084549192350870784628479597574645622638880069506009868145944996982225278 ), (1060943952101159814075555130286870049673510249558382992676797709837360932812847335287824269141102612270742087176360534041 , 1039246257482395034113137526078027968667726416005827851568387262127498749146041230779139405404483176650987996444622585854 ), (2424118466972165402210232064008571072995878364648534891594437945505312271409808703384482184386252162745547514610618028336 , 635156696412302837761915637951567688860519995373738062624916498633145442364997312202584276482319362616731324143180341246 ), (1772241931859851196567261257895529032033057998867860001437142889635454121520207911859978309001300625929738493595845855555 , 500604911497932506773931452024208499570885483407547558939058205116845746585850868300414311672651970998734159786902749117 ), (187044491746709666918227023301039735707457548611767420757592410489694090421689472337383722846260140189038198219461031942 , 227360883946968296249705407270310276359769497016888615738491818601296225309783611129587894811655567646792586796017233916 ), (698522560244433302990615272949028179635002687309158390959480083880213377867539289895143372657572453749378003459093150970 , 1438446488346299625609140434323525340139617346663444436909013102079035123226801253230191914228775608263694160574643826415 ), (1314293541818269470008262253418684239221368418527916534392752287558240541875482130114787897305513520252998018265836595136 , 933106402921508526957532367623168847119197804766985507707958985877339350054085035066950570021869141193740290685053960123 ), (1501745172784237049923522578654390251325669575513607134910901665808936517556360097769749957840258117848678845196676974438 , 1516777488301366348170721193695469080262430948767494893352311177358850775942249045078694319757619073073088994542922628861 ), (1718313250889012550002734353486104431289067168806022987862850465345813017177898627414672453244745977044381286178413506161 , 506057417158279773145112367533063233326190899630436097648290976200406049591277922238049560242268646574334872382933403615 ), (2574114678492270903282456732270950593394194358462333441160509514501148947640703147403802718744307473847235179125898798831 , 1503310774908591444184865449721473627976722270933784408676574059139777045024294387334806494605277115228299871854598791166 ), (1770243408559044970812149306040976785192946281881654467315187543403793080522851914844996680381886937167658398949087446193 , 1099237075950355774454839935750271630613513947414691912497783029355832037700530351594087156234712938075324990262460261245 ), (2166086041023587382902739106621961372440200378327129977520031042444044378994128764308981213008281610274832831816068579582 , 662709908868241192557028160616176772511764390044399310771390622778705044736473497185759270701465132475627229112002146287 ), (2170463762878343673691652149382892550249493539913487563393294153717628928418073705621516968910372026548584895576642432967 , 1413676394542378061807394780263485269329077458637078447074464881203630348193024572124672013567573482444837133106653543455 ), (1129266289804637843248865446624604876222278055268049666382746600434990532837254822384883357227875808573227656504651891817 , 1535832745242864345604750984721590856572422259228943440577864210008688452305222147646810543026576688303372824677842288383 ), (2306555154959167883502684934268021903550464872811594873384525370627065323932167910172723635326929186844444801386870524867 , 574207014379682600904001842474004352741607105704886122985304177072984415266547565043126591318153332317051149516485422972 ), (1724617341290962542300349861015192124473593787607849187241871123866653776294891983393875816012660538610025134685453770248 , 1037506311823536647118763707562050051146414393535410677631530307480219373475166677371198285257502421566885284344997084663 ), (202616766252415923229841624622749382197002736241072130496684863225861466295470440453433729087043063339640795866357221636 , 1486069111757435527648291199412538135459418727823506381342991481853059317128849411787275828115963269643450637901851750359 ), (782072578333357184532047183424922628763983310554137973249125608272717772586145583974361061586170067251618252434433193104 , 283757911494107775111019950316083145592345149507512192994272372101655062364071745340414019692327679359235776555825852415 ), (2197595167942118116042253773798345585826387963460510458606977372991191820486797272252095468231729659915814456157670560486 , 955293934596965502510872570415413020132164928134045802395033751487848017887015144832326371969637236306696054523237785589 ), (1098157283702819563820742199423754909028104781243946454418867995181539307551856844793857199640783377355282394025101300655 , 635111390180648841537968959615311456853925067622053148053038395898914597955860998732345527697104011201693008366561317143 ), (1539369283131984995745859995105101736066475537281347948822432206665809508754710210661232887491808392388057664234877214907 , 1873336536033306125287332317304933459481487853852475402907316652085126765046749618993624553154025815108827029610442783458 ), (2105684701096534411811602939870350859970761398331640507345513836997797916059406457337165075287082983610738904681969289045 , 1070056100602518593988818068846549889380286647944194826819905043161724050669042969316031968306712388470995120352413349630 ), (142489011778634823488933340993644406251365634143001554672065147110660487229716505211502368066478460823953952289740995290 , 1600505031347134429197259601839106217157515935077383802359036680943190353630112460191899585397343290624969344500745894703 ), (554711031900068277207319195022074787064807351540056727585559478009641245829914129658355024028140622126230477378977389537 , 65339521639683012798947456976243744037602872322070608133060186211835711806848370610017017866030009537787109068192454654 ), (532900849979395683891747931991929993723658239680866376615001124559008204600725833769158798743570050012188528983307982345 , 334144016771241488303216672075523455061388505657739817526966708251875900758813513342313135616513439456734341083743369135 ), (869702918099306179247127839502723535611690279734139047798433105147760657329410795136726045654330604238870805984709621246 , 1169351283105013313749641940783038490083938869389146122787264490618765187367135121126934960933658038044552677868393266925 ), (786239400981081690761967926939692614214352370457999126682279606306346828244856149092806342991454830115357428173569519111 , 341229317116770102168944480795910149567176593419165900124153031167345358788428115442807890687039322892597408592425778007 ), (2064213065995911617919315029041029121543167107287437882288959061187785048503282055451690399898250479932109432366548223997 , 865205430622864313641681018820800198136329954993789609121686669624009340125228193996720833574248608603224773986947432415 ), (1996571933560681341081972550429260163713030332385776633835663546385508374790580854691775408939051083454291050879529580125 , 559622002964744852554436566542525646157533309978763685146044798881793139644019170010343656282702809565334484141114392471 ), (1665201866056279622733275067329071022333699015026928761307123522986743452132023670960400981020146860918570153444345681972 , 1206659985279999461070238583934930315667638779868565409888110141662803190569415230894181412146290317311945493517622418483 ), (1515824630378748853880547205191400487565887686063520538971380532161078510669610334484477786016989319170924543667026641318 , 154768510600010010017326698396207970330238438685198973674456030784650112353692986269413531937661879315225602124927708924 ), (2400640362993011976891348699605911902016988451462173893625476704482508356176787307014920885489349704332546642981698540069 , 1121421906118323024216284095711804126345276955926784522370067713782427318851230923383318334457757167182928811853910539965 ), (914679394823164487648957492231711749917619119979512000391828434330805091270968219541264417579001916453063785209093025303 , 374627069056072738750323688310128739794138886219071824099120374559973078400286337012659440934169856150484268780102828020 ), (1021972013999414078223981430633642397558044349935082594710388870307835007718638824792649139809042384573145837264785258692 , 102093917357525962153933641992946656421204665316272197308632790969421027148825374536157392412871816080580115446708002591 ), (1090613002154339666672492884775405717313689831457406446112184992081112549743653583926163772335048052650217605191460964064 , 1013686859153230698540678410867250429548404782986370285534810877495709441098450523218264937019132584108142305563714746606 ), (2161046501022327990933396497482765893753709560942237251106031463450880235879988355009303131242535391464106086265266338474 , 1842825126623549349236000977359585068860414649531034170142594564984327572182360450517454690000097975914639809219290654045 ), (734600260267770729123110997283110745757092649194443870464263775523592639286156519663230810008655565992062564338915033184 , 1439472390868656814802271856900227714476824912359664972147156053839098765837149646453806800388007932953080250670815772651 ), (881335900275714936417588963897633003585264162416587081468620588101288614371107988322661634495058217226298025521720126634 , 1438060177355585280770231938473797663421441580729795412881287946986577092068342750409767988724102261013424113586148457982 ), (876173729780067336779925806297809473013555554668200124165269741312909223647316933287442159368855433236050789576297672813 , 584722637090302053439384198012199760324880317678105782762720083676914628942486088928409942979389876557255132127516159991 ), (1733558429089397683359597663185076627234549140640918522337597781379981378009350733554208954192805660163725305958818509205 , 1010477387678444338602582972843701290504497269295430761287923107029938822433731115008623372768060580369747062615441406973 ), (1758000758086776729345325124199287880198692107697670885448853730203070351345566212118269510767350031899984650531292511829 , 1484408939224604508966101404659297622265311898991708197399154932571955375325130297122648740841893311564144118335134464767 ), (1804131890436486866363129670875272535127829613109307224638927349502815652920038318044827248066297349084047126682198723537 , 205851561043462971495790984180238782403371191306463313748537952075031757233102533087892093246459879467418213080624418525 ), (115055233675952369353652759916228030654313474433562820828539341357745365094094469880187786426435712648771454584499932530 , 1176080864489594177205517592453183512444290818765306305520846987245653463202230068116379056777589684194022156652500590286 ), (2328185963017050382404641363914321749130815400658884925780323745763587492366183441185791654864416499947607965414839983680 , 1886972372164945427290729032551681924723044624295253696412030824048931146570915452349880650169939511030432165431905079162 ), (1187461847839408713851221476312312384869325749843380494840008651043567024911068726332857155522639869883501560564590472502 , 14245981570273560431111454126826341091354415427387740559245555665941487543601004914128539171516718107049427670791071455 ), (1275402030469087379247637832029139314437943507754693234009807154397029994354617242802931983091961356790463942774885431413 , 1244618585414033483912499539268357193993901084573974055024618656871349876744646123907837743332137138284077968028988239205 ), (434412507816189969843251866894800201497317336949194643079967243932448367734854234524383921690504689272627248814185361829 , 1193224411748734492892063266412070819051994764468021617840046995194588804893634149301845035319723286201666783735434959871 ), (967206800413690215868425566102618623559678834432686964828977512828919721907280699739833113197470139412151190023683313494 , 1808530961381834386234136376719035780314110457320233165055990056489953593025409242256807470925700807422319096558572795309 ), (313624779412398332754376720890766035026328871037358868168298423270666735999144035960122672900278781994670311217953770375 , 1686899500506262775384473022726677756466624697749756704659992441285341042856582261569357914257097304916151170085370461887 ), (2503049409019801269651799221722260539204050296212337202096008034125758666888245353212657377647881087341258220743220151950 , 1805670425703721038437117454438319230600703158318099419770216013430708468787297957979021344350598998116788430512286857710 ), (542793615526234040152647477936504636873290026979804505200706031754909176961382452267207291751054204331474258583862955704 , 137413216840404664240606423528330611923289618863367088636432169005845572010429296034368451334357274658088690084213739519 ), (1278727765228747216000039330509641392475448645848420065175572576050796418025108532539983143839105111868933395201633094022 , 23388499359309984016274969787898858204391606769507546898645785064534114465222342746534462082168690576567031618802237437 ), (1012848580192164395816758294581574397534987673377799482227399907475636722043236850766024023620412517564680586256857352143 , 1905214326869438439368196073362306288481014496204443072620153943726399155969870686475260450389360494546627630953811148739 ), (14681804970662677021409260234892378252555735233958673970664432299644093318314837872915339633110893420712659256185701001 , 1011761630527797621590321605066946971053085037922024159289431337005985850853467103097812975363878048453898707806902513147 ), (1285297724752785338545033366325253262303128927017049271006754406539647664563391436762226286574374768602309413720192759993 , 1493631305230939817393915729396076315723258260416123252804505906893714637325280535095299471289740565654113670071232495263 ), (1936455326607738910358536004445045468685935298243245355139607465446389473389575731412354107347767379820812067955096505581 , 17221509529814003689149745147239645298120184452011530064684368807629510922529681925724732647573630702864807669020485630 ), (1712173121206746224826777847167590088908487771935061508185448418705799456315866273530139739504675597716276421618856320329 , 863258960233895711001625204805338525869459949675833484269384656157104193362371966225031203968537041681324265578127949567 ), (122947819386929089053369455928546401519366926955589935482151285368760894784571110782585692673158533373827447719944343791 , 1029102739229804972707735760530574223266205866939373652705629746591419564062928935797957680207632040596245681227704817914 ), (2385767142510533504647214446664898369383090132453476416454822794037991187237960157132343084153289103535309857420295111775 , 1761624877069474386824225334992881109136596455709107320013742630575693526591737171363464568721656277644139593399384668014 ), (812771942753829583712722765469520203663717266127958627830326203252222513862479475416772893289895236549766564327139922612 , 1400551965978757484763340299740157171921224208542574495162921941233365483529203665206398541892811136907423472715818784767 ), (1730447421466464570286474725493766890793606044225883792125770759375672642470742177732074062181325776806752255986611978352 , 1227172422842784980554449107675660327741994737748190415035709694965213848256121533465275911556767542681543052337917439991 ), (884876570094879628298320898305798783174822422253214800767481822053599408285668812621687108791956015225332329856833897849 , 753204920370187659065626153785437381083012604855618525406022085513242388007754850086113679887120336586260993544726445815 ), (2423878693124084232298267862648738136330397292982760413012437397441533882471872339001090243864079240084356627531832647422 , 77986001656302970387684242942282141405916785932070787943262406584312194694807333266164831908062494860407574874622803959 ), (1290185371498453630061135665764650237444736789468400436115999443209964260044045414036036267228562648112405016415084034369 , 68976337771940690010768399948574523361633543589446521911372413501313976435844421496476544211566756895340409483041171429 ), (534185007935476498632058534030834014275044346188926848916387521022740118957225895686427252642167800163347935460364558055 , 731879744398464762194277983635893240035937844142280555568092822946046633080006561051406094554262898470573348173297417945 ), (2009543648096147223331131572743756103868310430657031922289948135024763757031731292638042205835167380178315151642456024876 , 864568612425196666545678285566636785636433247142630432401391420609479878443671268150141447157212173236963221732165810175 ), (1757088643325711453646774590651240485497713141719261877086100356614624931730830270746024611221269656481354818801893802862 , 974732470392774737526017597270025996122553373618728789664042196211840392818797860303355085148223560919202565975591828989 ), (288236986926014229269042124754978817491981631142567735873084199780621570926784314358694003281689620128867232148908447783 , 1677180488607905300411659606081989540342864981198203708964066014660249657102993313228752304204059137461689367948628457454 ), (2357100534536251965755486926312170142467175578829851375102247846264889085384519286073305902768874043332485938824401972401 , 701015346799246873651989606339191939588270778423404768025441929439466616345395882534334734331126078737835606277756551038 ), (361601359553041584651624082197420503156194921051661310152767809536879950298413026398079782027847432778044471125267794148 , 338870184820594722235914590766168929044789583242319904735556030852263040707796808350885054449714833051229949699390437343 ), (437493113470125074131702090577490292225129373521518638964839429915294209870286662477332241046314129156199317300178856910 , 304951333972637627160342487320016313244618388459742922018615396895218523409067458512473044675590109759792913998170528746 )] ct = 14058554635665083618818231958810639805770645952778992611953881143316377164307777281092527452513347998950720853358361
题目分析：
知道如下关系式：
\[
\begin{align*}
x_1 + y_1 \equiv m_{99} * t_1^{99} + m_{98} * t_1^{98} + ... + m_0 \pmod
p\\
x_2 + y_2 \equiv m_{99} * t_2^{99} + m_{98} * t_2^{98} + ... + m_0 \pmod
p\\
...\\
x_{75} + y_{75} \equiv m_{99} * t_{75}^{99} + m_{98} * t_{75}^{98} + ...
+ m_0 \pmod p\\
\end{align*}
\]
构造如下格：
\[
M = \begin{pmatrix}
1&&&&&t_{1}^0&t_{2}^0&\cdots&t_{75}^0\\
&1&&&&t_{1}^1&t_{2}^1&\cdots&t_{75}^1\\
&&\ddots&&&&&\ddots\\
&&&1&&_{1}^{99}&t_{2}^{99}&\cdots&t_{75}^{99}\\
&&&&2^{256}&-y_1&-y_{2}&\cdots&-y_{75}\\
&&&&&p&&&&\\
&&&&&&p&&&\\
&&&&&&&\ddots&&\\
&&&&&&&&p\\
\end{pmatrix}
\]
最后75列乘上A = \(2^{256}//2^{32}\) 来平衡目标向量中的元素
得到下面对应的目标向量：
\[
(m_0,m_1,...,m_{99},1,k_1,k_2,...,k_{75}) * M =
(m_0,m_1,...,m_{99},2^{256},Ax_1,Ax_2,...,Ax_{75})
\]
\(m_i\) 即我们要得到的一系列系数项
最后将它们拼接一下即可得到最后的结果
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 from hashlib import *from Crypto.Util.number import *from Crypto.Cipher import AESwith open ('data.txt' , 'r' ) as f: exec (f.read()) T = [i[0 ] for i in a] Y = [i[1 ] for i in a] M = matrix(ZZ,100 + 75 + 1 , 100 + 75 + 1 ) for i in range (75 ): for j in range (100 ): M[j, i + 101 ] = pow (T[i], j, p) M[100 , i + 101 ] = Y[i] M[100 + 1 + i, i + 101 ] = p M *= 2 ** (256 - 32 ) for i in range (100 ): M[i, i] = 1 M[100 , 100 ] = 2 ** 256 M = M.LLL() print (M)for i in M.list (): if i[100 , 100 ] == 2 ** 256 : res = i[1 :100 ] key = "" .join([str (i) for i in res]) key = md5(key.encode()).digest() aes = AES.new(key = key, mode = AES.MODE_ECB) print (aes.decrypt(long_to_bytes(int (ct))))
DAS_DSA
题目描述：
DDAASSSAA.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 from Crypto.Util.number import *import hashlibb2l=lambda x:bytes_to_long(x) l2b=lambda x:long_to_bytes(x) def xor (A,B ): return bytes ([a ^ b for a, b in zip (A, B)]) class SimpleDSASigner : def __init__ (self, p, q, g, x,KEY ): self .p = p self .q = q self .g = g self .x = x self .y = pow (self .g, self .x, self .p) self .KEY=KEY def sign (self, message ): h = int (hashlib.sha256(message).hexdigest(), 16 ) k = b2l(xor(message,self .KEY)) r = pow (self .g, k, self .p) % self .q s = (inverse(k, self .q) * (h + self .x * r)) % self .q if r != 0 and s != 0 : return (r, s) def verify (self, message, r, s ): h = int (hashlib.sha256(message).hexdigest(), 16 ) w = inverse(s, self .q) u1 = (h * w) % self .q u2 = (r * w) % self .q v = ((pow (self .g, u1, self .p) * pow (self .y, u2, self .p)) % self .p) % self .q return v == r def give_gift (self ): return (self .p,self .q,self .g,self .y)
task.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 import randomfrom DDAASSSAA import *from Crypto.Util.Padding import padfrom flag import FLAGALPHABET = "DAS" KEY_LENGTH = 32 def generate_random_string (length, chars ): return '' .join(random.choice(chars) for _ in range (length)) def get_message (num_messages ): return [generate_random_string(random.randint(20 , 32 ), ALPHABET) for _ in range (num_messages)] def get_key (): return generate_random_string(KEY_LENGTH, ALPHABET).encode() def get_strong_prime (kbits ): while True : q = getPrime(kbits) p = q * 2 + 1 if isPrime(p): return p, q def write_to_file (filename, data, rwx="w" ): with open (filename, rwx) as file: for item in data: file.write(f"{item} \n" ) if __name__ == "__main__" : num_messages = 2024 // 65 messages = get_message(num_messages) p, q = get_strong_prime(256 ) x = random.randrange(q) key = get_key() signer = SimpleDSASigner(p, q, 2 , x, key) write_to_file("GIFT.txt" , messages) signatures = [signer.sign(pad(msg.encode(), 32 )) for msg in messages] write_to_file("enc.txt" , map (str , signatures)) write_to_file("enc.txt" , [str (signer.give_gift())],"a" ) assert FLAG==b"DASCTF{" +key+b"}"
GIFT.txt
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 SDSSDASSAAASSDADSASADASSSSADDS SADADDAASSAASDSAAAAADS SSASDDDSSSSDDSDAAAAAASAASDSA SASSDSDSSSDSSDSDASADDA SDDAAASASADDAADDSSSSDASAASADSA AASADASADDSDDASADSAS DASDDDDAASADDASADAAAAAADS DSAAAASASDDDDDDSSASDADSASDDA ADSSSSAADDSDDDADAADD ASDDSADAASSASSDSDDSSD SASSDDAASDDSADSDSSDAASSAD DADSDAASAADDAAASASSSA DADDADSSDADAADSSADDADDDSSDAS AAASDSSDSAASDADDSADSDA ASDASSDSDDADADSDSDDDDADSSAADAS SDSASDADDASDASSDSAAASSASSDADA AADDSSDSDADSASDDSASSDDD SAADASAADAASDDDSASSDAASAAAS SSDDADSAADSDSSADSADSAASASDSAS DSDDAAASDDDSAASSDDDAASADSS SASSAAAAAAADSDASSDASSDAS DDDASAASDAADSSSASAAAADSDD SASADSSSAADDASADDDADD ASDDDDSDDSSSAASASDSSDDASA DSAASDSDAADAAAAASADSDDDDAAA ADSDADDDASASDSDADSADADDSASSSD ADADDASSDSDASADDSADSD SASAASDSDDASADASSSDSAAA SASDDADSSDASDDSSDSDA ADAASDSSDSDASSASADDSDDASAS AADADDSAADDDSASADASSDAADADAA
enc.txt 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 (59254487398967388114905667045028363843329923626238494813205814542210325221866 , 38134152657262330507433713437784426184950965354807113354631630191330303144120 ) (7272091585909282735283006759301331954064261183899338079418296410637263888770 , 25499964678151126566605578540840513489434638253159604087981425065951344757164 ) (6899645492048427857621143178962093646174799398991863666101058693217698732368 , 9791582686238213337967141368906212036310014918808878260483336268832064128819 ) (25004120896291255053237639070744331951278481119827357255754648579794346195560 , 141512006531073436448016797005260994098008785866923890662245540709534244927 ) (2970680424634969125510981613739745658897845410407912521400879068659540408508 , 21793011307831199247000930716490000926029175766326909085969585420590222327264 ) (54566000630497640561512172245143554745650114820675965968691149808463168361994 , 14349862994826483344159692458388566295460798903541941504424537018216650283613 ) (75159685495692974866291952764676724718763580667689472941977359299782008334398 , 70458140884809949567915541063312538538372757595177423386408938073672211639375 ) (20041025052466338500977838626769109456575569706600589389016534358968746705758 , 65530083011107720400920780939345704754954869671333734672594688826098321351660 ) (70127192435034402135747706941502224672808592757766109942714487474501491910214 , 57063474646503909216126596725677068514339517777473453937098665282959018241139 ) (9691674719110233709152049443866537766465800386755314400120771762265195237696 , 62093763551744197212031574855244002702924782008725363963219173846480120194830 ) (71705536377844454384479609516094364197930343317149881589774662842233960882414 , 77374603032347186343803094100249733360600621594214414598796066240713702791608 ) (52879693221782582945807231749976747516107564896599455986464226581743117039645 , 1344584960351311598238142429846629993914377848692708811135221930719773821079 ) (77382790022991362370508965243223326049308313776687214599186184000848696471646 , 43641233828500431963081402892838426285406919342406723474664571883294369141394 ) (56346141869522955969887972614456267251604757060687228073793419107933969328162 , 76285674574149814839616688665569434237657824816977670694242559140508233840268 ) (13673786393914569132256858604647869957632869873889606981549833789272316263013 , 55327829510120473782794486945583818434703312785066895788282945944551470490709 ) (64767740468987944636292946852714160626094908713011502873333251460983428727987 , 13259490361346409766866273875042192439139048727072955549892484859673179719539 ) (3957421961183318932163297455146838208380750250268324980567615749312524020603 , 26882140137481455957383933013829466811327529673163422516945649296787438630196 ) (26427922029900012253901950242265848521558605010629901777129266992870754082725 , 69951840114040217998552588969628162605092507207522992695398095063314527794456 ) (41377529326816743042387061355650636824586430044255853849728865473372840135697 , 11219359019456290145545276763003725218855047474525360923001515509608652449000 ) (25716607607446503241765016815241812755718791371526314953930748513731536667770 , 28453782213087434330094261632474010077787574243224303728751260500450723227337 ) (19800391798756020076641438144957219387739406397111495660920822320302304854123 , 45451686690348328576376896082606976500453603983712180502700202971927238065259 ) (38726290839677684687529233274549282905118675478275260942535144771737271586397 , 40829316203033016996956478373044348905634931325393076578307296318880401948880 ) (39209612764454560795450300186392582769693156243512973558204034254768849812055 , 1354495451811853700039180690705948597695565424847801455594169929311025313998 ) (65513712517147774905818288938959930101260466094015953149923879872714745367445 , 15372704507991354781967074099137226451034611060413049367266363154832614415805 ) (15729001560566023616632342669016214191974988848807788455841465085832368458445 , 16327134664007312833089147621817036851276111964898734022794700122827444854947 ) (42181696175119369852613642818168055609726913997313538977450877772345284116500 , 9844926061501886811803369928846120575402269452312877926396348651872911440254 ) (66136301537002842836817588252827389434354772150463143258637074246966542574050 , 40179237579762663098604891208246052072476264271372972425562554108399403298795 ) (28759447425094984124057238672075080352158483766211322160596339820824930247130 , 31809179023991813094371890170356817265600467849999331763205655801654108159032 ) (46713611880672324334213026166944979498146683097425440783760089321619754080806 , 23270114877894114090584274918755188867365261145736710892185678426446455871613 ) (57079205189933243387798430767693634017842334556643904914267966016857671112460 , 18247249527866143497935092319901700668290600772967638096649240924154901762810 ) (10688647176294432598580110142909961685073598720504815121442568862023227643325 , 54331697420125697460151875535555752680845260504979536685075170636565355173106 ) (156169498993837300941969389078565637464689185713213578550979549862042014984607 , 78084749496918650470984694539282818732344592856606789275489774931021007492303 , 2 , 59080272611010540206200716660225398487916425104605746321153704646003914371135 )
这题没看，赛后复现的
参考来源：https://tangcuxiaojikuai.xyz/post/83b88224.html#more
题目分析：
已知： \[
\begin{align*}
&k_i \equiv s_i^{-1} * (h_i + x * r_i) \pmod q\\
&k_i \equiv s_i^{-1} * h_i + x * r_i * s_i^{-1}\pmod q\\
&k_i太大了，故爆破2字节\\
&k_{ih} * 256^{30} + k_{il} \equiv s_i^{-1} * h_i + x * r_i *
s_i^{-1}\pmod q\\
&k_{il} \equiv s_i^{-1} * h_i + x * r_i * s_i^{-1} - k_{ih} *
256^{30}\pmod q\\
&k_{0l} \equiv s_0^{-1} * h_0 + x * r_0 * s_0^{-1} q - k_{0h} *
256^{30}\pmod q\\
&接下来消掉x\Rightarrow\\
&s_i * r_0 * k_{il} - s_0 * r_i * k_{0l} \equiv h_i * r_0 - h_0 *
r_i + s_0 * r_i * k_{0h} - s_i * r_0 * k_{ih} \pmod q
\end{align*}
\] 令\(c_i = h_i * r_0 - h_0 * r_i +
s_0 * r_i * k_{0h} - s_i * r_0 * k_{ih}\)
从而构造如下格： \[
M = \begin{pmatrix}
1&&&&&&s_0r_1&s_{0}r_2&\cdots&s_{0}r_{30}\\
&1&&&&&s_{1}r_0&&&\\
&&1&&&&&s_{2}r_0&&&\\
&&&\ddots&&&&&\ddots&\\
&&&&1&&&&&s_{30}r_0\\
&&&&&256^{30}&c_1&c_{2}&\cdots&c_{30}\\
&&&&&&q&&&&\\
&&&&&&&q&&&\\
&&&&&&&&\ddots&&\\
&&&&&&&&&q\\
\end{pmatrix}_{31 + 1 + 30}
\] 最后30列乘上\(2^{256}\) 使得到的最小向量和目标向量大小接近
得到目标向量：
\((k_0, -k_1, -k_2,...,-k_{30}, 1, l_1,
l_2, ..., l_{30}) * M = (k_0, -k_1, -k_2,...,-k_{30},
256^{30}, 0,0,...,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 from itertools import productfrom Crypto.Util.Padding import padfrom hashlib import *from Crypto.Util.number import *from tqdm import tqdmp, q, g, y = (156169498993837300941969389078565637464689185713213578550979549862042014984607 , 78084749496918650470984694539282818732344592856606789275489774931021007492303 , 2 , 59080272611010540206200716660225398487916425104605746321153704646003914371135 ) message = ['SDSSDASSAAASSDADSASADASSSSADDS' , 'SADADDAASSAASDSAAAAADS' , 'SSASDDDSSSSDDSDAAAAAASAASDSA' , 'SASSDSDSSSDSSDSDASADDA' , 'SDDAAASASADDAADDSSSSDASAASADSA' , 'AASADASADDSDDASADSAS' , 'DASDDDDAASADDASADAAAAAADS' , 'DSAAAASASDDDDDDSSASDADSASDDA' , 'ADSSSSAADDSDDDADAADD' , 'ASDDSADAASSASSDSDDSSD' , 'SASSDDAASDDSADSDSSDAASSAD' , 'DADSDAASAADDAAASASSSA' , 'DADDADSSDADAADSSADDADDDSSDAS' , 'AAASDSSDSAASDADDSADSDA' , 'ASDASSDSDDADADSDSDDDDADSSAADAS' , 'SDSASDADDASDASSDSAAASSASSDADA' , 'AADDSSDSDADSASDDSASSDDD' , 'SAADASAADAASDDDSASSDAASAAAS' , 'SSDDADSAADSDSSADSADSAASASDSAS' , 'DSDDAAASDDDSAASSDDDAASADSS' , 'SASSAAAAAAADSDASSDASSDAS' , 'DDDASAASDAADSSSASAAAADSDD' , 'SASADSSSAADDASADDDADD' , 'ASDDDDSDDSSSAASASDSSDDASA' , 'DSAASDSDAADAAAAASADSDDDDAAA' , 'ADSDADDDASASDSDADSADADDSASSSD' , 'ADADDASSDSDASADDSADSD' , 'SASAASDSDDASADASSSDSAAA' , 'SASDDADSSDASDDSSDSDA' , 'ADAASDSSDSDASSASADDSDDASAS' , 'AADADDSAADDDSASADASSDAADADAA' ] r = [59254487398967388114905667045028363843329923626238494813205814542210325221866 , 7272091585909282735283006759301331954064261183899338079418296410637263888770 , 6899645492048427857621143178962093646174799398991863666101058693217698732368 , 25004120896291255053237639070744331951278481119827357255754648579794346195560 , 2970680424634969125510981613739745658897845410407912521400879068659540408508 , 54566000630497640561512172245143554745650114820675965968691149808463168361994 , 75159685495692974866291952764676724718763580667689472941977359299782008334398 , 20041025052466338500977838626769109456575569706600589389016534358968746705758 , 70127192435034402135747706941502224672808592757766109942714487474501491910214 , 9691674719110233709152049443866537766465800386755314400120771762265195237696 , 71705536377844454384479609516094364197930343317149881589774662842233960882414 , 52879693221782582945807231749976747516107564896599455986464226581743117039645 , 77382790022991362370508965243223326049308313776687214599186184000848696471646 , 56346141869522955969887972614456267251604757060687228073793419107933969328162 , 13673786393914569132256858604647869957632869873889606981549833789272316263013 , 64767740468987944636292946852714160626094908713011502873333251460983428727987 , 3957421961183318932163297455146838208380750250268324980567615749312524020603 , 26427922029900012253901950242265848521558605010629901777129266992870754082725 , 41377529326816743042387061355650636824586430044255853849728865473372840135697 , 25716607607446503241765016815241812755718791371526314953930748513731536667770 , 19800391798756020076641438144957219387739406397111495660920822320302304854123 , 38726290839677684687529233274549282905118675478275260942535144771737271586397 , 39209612764454560795450300186392582769693156243512973558204034254768849812055 , 65513712517147774905818288938959930101260466094015953149923879872714745367445 , 15729001560566023616632342669016214191974988848807788455841465085832368458445 , 42181696175119369852613642818168055609726913997313538977450877772345284116500 , 66136301537002842836817588252827389434354772150463143258637074246966542574050 , 28759447425094984124057238672075080352158483766211322160596339820824930247130 , 46713611880672324334213026166944979498146683097425440783760089321619754080806 , 57079205189933243387798430767693634017842334556643904914267966016857671112460 , 10688647176294432598580110142909961685073598720504815121442568862023227643325 ] s = [38134152657262330507433713437784426184950965354807113354631630191330303144120 , 25499964678151126566605578540840513489434638253159604087981425065951344757164 , 9791582686238213337967141368906212036310014918808878260483336268832064128819 , 141512006531073436448016797005260994098008785866923890662245540709534244927 , 21793011307831199247000930716490000926029175766326909085969585420590222327264 , 14349862994826483344159692458388566295460798903541941504424537018216650283613 , 70458140884809949567915541063312538538372757595177423386408938073672211639375 , 65530083011107720400920780939345704754954869671333734672594688826098321351660 , 57063474646503909216126596725677068514339517777473453937098665282959018241139 , 62093763551744197212031574855244002702924782008725363963219173846480120194830 , 77374603032347186343803094100249733360600621594214414598796066240713702791608 , 1344584960351311598238142429846629993914377848692708811135221930719773821079 , 43641233828500431963081402892838426285406919342406723474664571883294369141394 , 76285674574149814839616688665569434237657824816977670694242559140508233840268 , 55327829510120473782794486945583818434703312785066895788282945944551470490709 , 13259490361346409766866273875042192439139048727072955549892484859673179719539 , 26882140137481455957383933013829466811327529673163422516945649296787438630196 , 69951840114040217998552588969628162605092507207522992695398095063314527794456 , 11219359019456290145545276763003725218855047474525360923001515509608652449000 , 28453782213087434330094261632474010077787574243224303728751260500450723227337 , 45451686690348328576376896082606976500453603983712180502700202971927238065259 , 40829316203033016996956478373044348905634931325393076578307296318880401948880 , 1354495451811853700039180690705948597695565424847801455594169929311025313998 , 15372704507991354781967074099137226451034611060413049367266363154832614415805 , 16327134664007312833089147621817036851276111964898734022794700122827444854947 , 9844926061501886811803369928846120575402269452312877926396348651872911440254 , 40179237579762663098604891208246052072476264271372972425562554108399403298795 , 31809179023991813094371890170356817265600467849999331763205655801654108159032 , 23270114877894114090584274918755188867365261145736710892185678426446455871613 , 18247249527866143497935092319901700668290600772967638096649240924154901762810 , 54331697420125697460151875535555752680845260504979536685075170636565355173106 ] M = matrix(ZZ,33 ,31 ) khigh = ['' .join(bytes ) for bytes in product("DAS" , repeat=2 )] tmp_1 = matrix.identity(31 + 1 ) tmp_1[-1 , -1 ] = 256 ** 30 tmp_q = matrix.identity(31 - 1 ) tmp_q *= q tmp_0 = matrix.zero(31 - 1 , 31 + 1 ) M = tmp_1.stack(tmp_0) A = matrix(ZZ, 31 + 1 , 31 - 1 ) h0 = int (sha256(pad(message[0 ].encode(), 32 )).hexdigest(), 16 ) for kh in tqdm(khigh): print (kh) k0h = bytes_to_long(bytes ([a ^^ b for a, b in zip (kh.encode(), message[0 ][:2 ].encode())]))* 256 ** 30 for i in range (1 , 31 ): hi = int (sha256(pad(message[i].encode(), 32 )).hexdigest(), 16 ) kih = bytes_to_long(bytes ([a ^^ b for a, b in zip (kh.encode(), message[i][:2 ].encode())])) * 256 ** 30 ci = hi * r[0 ] - h0 * r[i] + s[0 ] * r[i] * k0h - s[i] * r[0 ] * kih A[0 , i - 1 ] = s[0 ] * r[i] %q A[i, i - 1 ] = s[i] * r[0 ] %q A[-1 ,i - 1 ] = ci % q tmp = A.stack(tmp_q) tmp *= 2 ** 256 MM = M.augment(tmp) res = MM.LLL() k0l = abs (res[0 ][0 ]) k0 = k0h + k0l key = long_to_bytes(k0 ^^ bytes_to_long(pad(message[0 ].encode(),32 ))) if (all (j in b"DAS" for j in key)): print (key) break
