同时发布于 https://hello-ctf.com/HC_envSet/Crypto/ / 前言 善于百度, 哪里不懂先去百度, 其实搜索引擎上更推荐 Bing 或是 谷歌, 百度只是要求搜索解决的统一说辞, 还有疑惑则去读 <提问的智慧>, 如果依旧不理解, 可以用从 <提问的智慧> 中学到的提问方式来请教别人.

一年一度的密码盛宴, 看春哥队和 yeye5队乱杀了, 今年 r3k 也进入前十了, 还有南邮以及中科大的队都好猛, 还有不说话只做题的队友 www, 你们 tql / 复现进度 … 先收集一下来自discord 的 wp 如下

PPT(图片)地址 / 视频地址(38 分 40 秒) / 数据生成代码(题目/Sage) from Crypto.Util.number import long_to_bytes, bytes_to_long, getPrime flag = b'flag{xxxLOV3xxx}' m = bytes_to_long(flag) p = getPrime(1024) q = getPrime(1024) n = p * q phi = (p - 1) * (q - 1) e1 = getPrime(30) e2 = getPrime(20) print(f'{e1 = }') print(f'{e2 = }') print(f'{n = }') d1 = inverse_mod(e1, phi) d2 = inverse_mod(e2, phi) c1 = pow(m, e1, n) c2 = pow(m, e2, n) print(f'{c1 = }') print(f'{c2 = }') 推导 如果 e1 与 e2 互素(不互素就先直接算 r, s, 最后开gcd(e1, e2)次根), 则用拓展欧几里得解r, s 如果 r 是负数, (r 和 s 中有一个必定是负数) 那么再用欧几里得算法计算 $c_1^{-1}$, (为什么要求逆) 有: [公式] 证明 [公式] 得出 $e_1, e_2$，接着我们计算 $m$

col ssh 连上执行ls -la看看(-la参数可以浏览文件属性) cat col.c查看源文件 / #include <stdio.h> #include <string.h> unsigned long hashcode = 0x21DD09EC; unsigned long check_password(const char* p){ int* ip = (int*)p; int i; int res=0; for(i=0; i<5; i++){ res += ip[i]; } return res; } int main(int argc, char* argv[]){ if(argc<2){ printf("usage : %s [passcode]\n", argv[0]); return 0; } if(strlen(argv[1]) != 20){ printf("passcode length should be 20 bytes\n"); return 0; } if(hashcode == check_password( argv[1] )){ system("/bin/cat flag"); return 0; } else printf("wrong passcode.\n"); return 0; } 分析出需要执行 col 这个程序时传参, 而且参数需要20bytes长, 同时要求参数经过 check_password() 后等于 hashcode 变量

Misc Corny Kernel 拿到题目看见有源码和一行代码，用来连远端 / socat file:$(tty),raw,echo=0 tcp:corny-kernel.chal.uiuc.tf:1337 源码 -> pwnymodule.c // SPDX-License-Identifier: GPL-2.0-only #define pr_fmt(fmt) KBUILD_MODNAME ": " fmt #include <linux/module.h> #include <linux/init.h> #include <linux/kernel.h> extern const char *flag1, *flag2; static int __init pwny_init(void) { pr_alert("%s\n", flag1); return 0; } static void __exit pwny_exit(void) { pr_info("%s\n", flag2); } module_init(pwny_init); module_exit(pwny_exit); MODULE_AUTHOR("Nitya"); MODULE_DESCRIPTION("UIUCTF23"); MODULE_LICENSE("GPL"); MODULE_VERSION("0.1"); 根据提示连上远端

安利大佬的博客, 讲了 coppersmith 集中玩法: 阮行止的Blog 题目蛮有意思的，共模攻击同时 m 被填充 '00' , 且 $gcd(e1, e2) != 1$ 题目源码（稍作改动 逻辑不变） from Crypto.Util.number import * import gmpy2 # from secret import flag,x x = 13 # 利用e的二进制位长推测出x的二进制位长 flag = r'DASCTF{94c8c21d08740f5da9eaa38d1f175c592692f0d1}' FLAG = hex(bytes_to_long(bytes(flag.encode()))) print(len(FLAG)) while len(FLAG) < 2048: FLAG += '00' # DEBUG """ FLAGa=int(FLAG,16) # 16进制转10进制 print(f'hex->{FLAGa:x}') # hex print(len(bin(FLAGa))) # flag的二进制位长 # 填充前385 # 填充后8xxx """ def task(n, p, q): e = x * getPrime(25) print(e) pk, sk = (n, e), (inverse(e, (p-1)*(q-1))) # print (f"privkey = {sk}") print (f"pubkey = {pk}") assert FLAG < pk[0] c = pow(FLAG, pk[1], pk[0]) # c = FLAG^e mod n print (f"ciphertext = {c}") p = getPrime(4096) q = getPrime(4096) n = p * q task(n, p, q) task(n, p, q) ''' pubkey = (631704658316107316476631662851232513167305743724051186158554607216138665758651383999780489278091838560489032372900267377736237142312800325510839644655041019350454746285608148076069877827331570306531360928735706136940744879296188814218221415268468882601401290453513620058967937490229879350100210840273601673434791156967887168489949398909636232265730565157705645074778099335973868420591684971700842192135737822163092719010899899900906950920588813409920740847058646752828785385873772281705505151082567637301753513073178877382222686947884464356503084436710964721728934103667575388962027500496785366512559779503975171067515648474317451743950311102788378592650584074924518502042800806374634257689006701099537082929839880680716644107887107277545440883202850169389561038503505611543517665847099355309543791726704508828412748648083667615253805811065493087765182890641394941547224007410230582635739282572999784818993426524660322506552777173684682345617903709438634566739636646813598805189824096257101005511591646200477114782395355594700543654172045449061307743391984162366457405661384570894282509109440702579925256407640046816406501144647037050778323528329913821976003677989099891054333950811501262124243258915504259130280580230299912657442669541457718378886950829044993718306207245034570466513477929865019679408238431035969390774039176113600326758938598312905961726761447479195236692754661127098476166335245118569319315163868742823661391978080155625395638363389335880296389371811509103078703583364479544504724117424456267398768483363594014016511039412147353322943732886624729667119668931889622044935822991901046638537981486137324641851248938171721925238794095980507451649422011021294020116758658798903892915685251627983627496145518772566258707836493016012354879299011651025514693262138104102713765715302120633524663935787265638025681461758686836356777160007235880219089378478714987895528233499888588134943176336612314910896457649467880092378885848765474948336418203366356857880128284792653134100961580205274724342493185974704960927765508980506809171289317650392381155261841525346094897909282358464631129565142466841251641574182477290680783110373339041696933558390263892986185187988896102175806358089155531818651838775580994959917250173754629890300524280224596458984449283141274434578618610753309471105156475116451614745170121602666465090430931564872929117390734021763304624273646435586790080907671369751246596652914201599305562484432951782931086073027568703037735327284365677, 472554661) ciphertext = 190987504276417030459995870118018106411927956775759012847742153271115853081408559439515500090420659778337774251322924763583703744945725548117826596107116645542242417390155411579632955292564528520440614260557243094399833823703776825260174109620647075222266930807489850145653178950535314869608224045341462372136686325390890689054405086686001100811443562979660892626976910848883193606213100173930615655868314435984441387498754642165766151061008739536079031140840087582367396856029192985567585098853421231849021423950166776436360731699210565052814347301305136231030452336673072044401519429834369139140245097717477442207591860572819484092848769895526302884706675965820142765147054286070702591314107210105634638529040955739525959665452187152373744418055109385189923937410612814332368059055442697514476224539572446022119292246216864736507911101687770449399470300111493467761898288339606268218461414713869261621265548926431739969658851060588469847933207757035870820118151506632080848622808949107266876446402143532885158806752022647196657389362551812094658375646137420717912004993731588408266942954086191081329114054376690515702418030563123621308538946327414923689799905388809280810108810572604423052944060166210108864637349960969813576226954947569269001567594538036335239515820446049796338189866087489579415290966515988794972617897613114169306902686552315662681234085741908135003796792983996537217079533422533672875702933249385450293644264481727769868049295596687776551250104869253909976864238705319499867029873108947287715051353048589899005756254898493157435715455584382285421252226592815717633100684130833535313398285854135049104416584931630961649612263799668626605766084592830857431301960508118967957132590949622478565095552894302156456587375827654576193163705593838932559456550980547713264158180558179573064749914083291869665313434519298805872794848445531668240282892429504465717077102142829322223537966050798014877242907116850396358948946563266157495445976661243015703150210392054301115412770660862765408166194109344334156035055331784788156175540722143596029916953303656978173674438529512674377683439887526966586680024643214529230521291448281299492022962381836977335458591380009655069999490948962732861301906043829089176993890552623525778739163797525576145126381504772928706462746770945831728396867697460511548895998660335284720579047966498756660763368794251021798470067833203405996009675602949792544182705941386274781263007295426151053568079918978166706088381712821903 pubkey = (631704658316107316476631662851232513167305743724051186158554607216138665758651383999780489278091838560489032372900267377736237142312800325510839644655041019350454746285608148076069877827331570306531360928735706136940744879296188814218221415268468882601401290453513620058967937490229879350100210840273601673434791156967887168489949398909636232265730565157705645074778099335973868420591684971700842192135737822163092719010899899900906950920588813409920740847058646752828785385873772281705505151082567637301753513073178877382222686947884464356503084436710964721728934103667575388962027500496785366512559779503975171067515648474317451743950311102788378592650584074924518502042800806374634257689006701099537082929839880680716644107887107277545440883202850169389561038503505611543517665847099355309543791726704508828412748648083667615253805811065493087765182890641394941547224007410230582635739282572999784818993426524660322506552777173684682345617903709438634566739636646813598805189824096257101005511591646200477114782395355594700543654172045449061307743391984162366457405661384570894282509109440702579925256407640046816406501144647037050778323528329913821976003677989099891054333950811501262124243258915504259130280580230299912657442669541457718378886950829044993718306207245034570466513477929865019679408238431035969390774039176113600326758938598312905961726761447479195236692754661127098476166335245118569319315163868742823661391978080155625395638363389335880296389371811509103078703583364479544504724117424456267398768483363594014016511039412147353322943732886624729667119668931889622044935822991901046638537981486137324641851248938171721925238794095980507451649422011021294020116758658798903892915685251627983627496145518772566258707836493016012354879299011651025514693262138104102713765715302120633524663935787265638025681461758686836356777160007235880219089378478714987895528233499888588134943176336612314910896457649467880092378885848765474948336418203366356857880128284792653134100961580205274724342493185974704960927765508980506809171289317650392381155261841525346094897909282358464631129565142466841251641574182477290680783110373339041696933558390263892986185187988896102175806358089155531818651838775580994959917250173754629890300524280224596458984449283141274434578618610753309471105156475116451614745170121602666465090430931564872929117390734021763304624273646435586790080907671369751246596652914201599305562484432951782931086073027568703037735327284365677, 512060519) ciphertext = 118105806757364864954099740578039575095067736310062562032293775737146734292611491109686416485919016851405784908499094267565612303208935666612372955592240502275304246975609627506123058353391372656409432910534157579594786467732926369572526172564718924601625672422241852492488550283148235537506268392245305690156723219564226402432576938782454753759983137914472704648591878027847262615725429446005016635025420868133866811373289327645413411453859339757836991093908071638328453514104881336701917644665804786789489323672785875877061237766568407039151396946704985496018147569926911261898580756098479100237007941318401021279795364728719207372661460410387690657138651731327964723514386572694325652597994434813931414394101200087900718036550266207104274280840585258295937618660007576916346971377563537978904909890356241631994402505853975554712900758886256393960997065883072603649541752328064420102794034716350179526975824164679514497545031932376505630561041528122534350326851355630277189536132079819347591965123978267329957678172531541870774152820885892748994104282993783130986435408443990102761662449293721684054746590737624241714144192554974418174740935392026309752818843371184788181135723934755921015195135100434571963047279241020959200031451732709183509226119313388765957669702752972765899086633745040942547050498490884353694399849142077796452902507813258263359599139001375752871961305870647115285853030278057230051592204611282860281668566134180445475472981874013691475514350039449881223501881564079522206136571985922976022429024806580161050812111546949423979614963273484255330194797143216964745972075353014043464318808527670570025723913145381743890479373651559112882154125825193684319648524540319399295496316455910887675719072214746078300659747824900422025873021264607615059776370887811316751386521720353564213575161113649210936024834236497270467247374376806151520458934834474873512780450459065406794893079375072143242760903847107206702819919541243590083307963659134589118157841441127260628026207634262496423960483763853574351631049111656076943501743107444844944097456043724623057099318681823470304041478338060550105843257247135981311666581587388804168534632878003367114935690158903476684427898910282066938176875785040879979309200489444338815528259008540300389580292768148738299179013875917009766599802284812113802699460093538336768415249967785549217725394898178950705893233820694790774211856222175935024768782962788732209486972454385313819695038224886978798800124937584338 '''

BattleCTF-Blind-最终分值：100 Crypto分类下的一道Misc &?g}-PN(9}P5MAm&?h7^PPOlbIq>h1&?hiR&?i)xPP!xdZ2CY{&?h.0PTrZKO-lrJ&?i*vPR*.wG5SCP&?h>4PQB/jXz<fx&?hE]PTrZKKk=*:&?hE]PT:0OQt?&1&?j0APQB/jG5SD3&?hE]PT:0OO-lrH&?i*vPR*.wM/sWz&?g[.PN#f@G5SC^&?i*vPN#f@O-lrp&?i:tPQjVhRq!e8&?i:tPN#f@WbN:H&?i2] CyperChef上先BASE85(CyperChef会自动分析出)再解盲文，在厨子(他们都这么叫CyperChef)上盲文叫braille / 最后需要把flag的壳改为battleCTF即可 / Sahara 看起来很复杂但实际上只是一道简单RSA from cryptography.hazmat.primitives.asymmetric import rsa, padding from cryptography.hazmat.primitives import serialization from cryptography.hazmat.backends import default_backend from base64 import b64encode, b64decode FLAG = open("flag.txt").read() def load_public_key(): with open('pub.pem', 'rb') as pubf: pubkey = serialization.load_pem_public_key(pubf.read(), backend=default_backend()) return pubkey def encrypt(pubkey:rsa.RSAPublicKey, ptxt:str) -> str: enc = pubkey.encrypt(ptxt.encode(), padding.PKCS1v15()) return b64encode(enc).decode() def get_pem(key:rsa.RSAPrivateKey|rsa.RSAPublicKey): if isinstance(key, rsa.RSAPublicKey): pem = key.public_bytes(encoding=serialization.Encoding.PEM, format=serialization.PublicFormat.SubjectPublicKeyInfo) else: pem = key.private_bytes(encoding=serialization.Encoding.PEM, format=serialization.PrivateFormat.PKCS8, encryption_algorithm=serialization.NoEncryption()) return pem if __name__ == '__main__': pub_key = load_public_key() pub_key_pem = get_pem(pub_key).decode() enc_flag = encrypt(pub_key, FLAG) with open('flag.enc', 'w') as f: f.write(enc_flag) exp n = 17729028558979019485846420034614601781855286885772116033115998289130663218793249135103097941406615594783564487056148202535602218241261076180277862184340050681277512936764254998557657989633659561175844653871375735119626199870178796372816549333367076487655787617921785826120525919291798195591267544750350222858119219959311035913906885739352404726672836723117136379411134589884489391116922923390687958161705756705708668649262568471831705504852664779788943978721769038284989250803324876493071615384204553854811020877754034576798208169454695001947778015807032019651748938505463608871771494765303144219873993106068807291321 e = 65537 enc = 'QrjGSaOn4vUMNLAWdKif3s0pTi3vjDupP764AqUV13FtO+0MVO5m848H1THn33Lorn5vhDOtr5x3kJBHP8lfPbgvoiw7n/FdhjjyclAlB4JLANUgLIjvurvMfFshuvsg3ljXnpNu+oVET/AgDev1hJp9CrbQ+8Axx9ki4ZRldqC/eUbzypqeun2jjKjMi98GamW6ufnZSxtJwajWLK6dHB72Dcx4sn38iHnqikRixOaUeJ6jR2yhdIYhQr4nU5tggHoxsLjnia8x4qTc4lWYAYz6vJiw1zRs0JwK//sZdEtx09c59Mj0WNrmkD8gP98f22LjHNPIxAHl3OyWY+PfcA==' from gmpy2 import iroot from Crypto.Util.number import * from base64 import * p = iroot(n,2)[0] # 拿着n去factordb.com试试, 发现n=p^2, 于是直接开根号得到p d = inverse_mod(e, p*(p-1)) # phi = p*(p-1)而不是(p-1)*(p-1) 因为??? m = pow(bytes_to_long(b64decode(enc)),d,n) print(long_to_bytes(m)[long_to_bytes(m).find(b'battle'):]) #battleCTF{Sm4!!_RSA_k3y_in_The_Sahara} SEA

CrazyTreat 题目源码 from Crypto.Util.number import * from random import randint from secret import flag def TrickPrime(bits): p = getPrime(bits) q = getPrime(bits) cut = randint(1,256) temp = p*q print('clown =',temp) game = (p&(2**bits-1)) >>cut<<cut #p高位需要给出 print("trick =",game) return p,q def CrazyPrime(nbits): p = getPrime(nbits) q = getPrime(nbits) r = getPrime(nbits) n = p * q * r print("n =", n) m = getPrime(256) P = pow(m, p, n) Q = pow(m, q, n) R = pow(m, r, n) print("P =", P) print("Q =", Q) print("R =", R) return m P,Q = TrickPrime(512) R = CrazyPrime(512) N =P*Q*R phi = (P-1)*(Q-1)*(R-1) e = 65537 d = inverse(e,phi) m = bytes_to_long(flag) c = pow(m,e,N) print("c = ",c) ''' clown = 128259792862716016839189459678072057136816726330154776961595353705839428880480571473066446384217522987161777524953373380960754160008765782711874445778198828395697797884436326877471408867745183652189648661444125231444711655242478825995283559948683891100547458186394738621410655721556196774451473359271887941209 trick = 13053422630763887754872929794631414002868675984142851995620494432706465523574529389771830464455212126838976863742628716168391373019631629866746550551576576 n = 924936528644761261915490226270682878749572154775391302241867565751616615723850084742168094776229761548826664906020127037598880909798055174894996273670320006942669796769794827782190025101253693980249267932225152093301291975335342891074711919668098647971235568200490825183676601392038486178409517985098598981313504275523679007669267428032655295176395420598988902864122270470643591017567271923728446920345242491655440745259071163984046349191793076143578695363467259 P = 569152976869063146023072907832518894975041333927991456910198999345700391220835009080679006115013808845384796762879536272124713177039235766835540634080670611913370463720348843789609330086898067623866793724806787825941048552075917807777474750280276411568158631295041513060119750713892787573668959642318994049493233526305607509996778047209856407800405714104373282610244944206314614906974275396096712817649817035559000245832673082730407216670764400076473183825246052 Q = 600870923560313304359037202752076267074889238956345564584928427345594724253036201151726541881494799597966727749590645445697106549304014936202421316051605075583257261728145977582815350958084624689934980044727977015857381612608005101395808233778123605070134652480191762937123526142746130586645592869974342105683948971928881939489687280641660044194168473162316423173595720804934988042177232172212359550196783303829050288001473419477265817928976860640234279193511499 R = 502270534450244040624190876542726461324819207575774341876202226485302007962848054723546499916482657212105671666772860609835378197021454344356764800459114299720311023006792483917490176845781998844884874288253284234081278890537021944687301051482181456494678641606747907823086751080399593576505166871905600539035162902145778102290387464751040045505938896117306913887015838631862800918222056118527252590990688099219298296427609455224159445193596547855684004680284030 c = 10585127810518527980133202456076703601165893288538440737356392760427497657052118442676827132296111066880565679230142991175837099225733564144475217546829625689104025101922826124473967963669155549692317699759445354198622516852708572517609971149808872997711252940293211572610905564225770385218093601905012939143618159265562064340937330846997881816650140361013457891488134685547458725678949 ''' exp(在tl2cents师傅的exp基础上加了些笔记) # sagemath 10.0 # sagemath 10.0 clown = 128259792862716016839189459678072057136816726330154776961595353705839428880480571473066446384217522987161777524953373380960754160008765782711874445778198828395697797884436326877471408867745183652189648661444125231444711655242478825995283559948683891100547458186394738621410655721556196774451473359271887941209 trick = 13053422630763887754872929794631414002868675984142851995620494432706465523574529389771830464455212126838976863742628716168391373019631629866746550551576576 print(hex(trick)) # 0xf93bccfd5550cb15211bdc316f1b15cdfbc1f3e54a7745b9c4835f5346fa7f1d9560784892728000000000000000000000000000000000000000000000000000 # 求其hex长度: trick2hex去除尾部所有0再减去1(最后一位因为bit2hex位数不够会补0,所以这一位可能不是真实的p中的部分(仅对于hex的呈现),所以要减去1) cache = len(hex(trick).rstrip('0')) - 2 -1 # rstrip('0')去除尾部所有0, -2 是`0x`格式 print(f'cache = {cache}\n泄漏bit位长: bitLens = {cache*4}') # 泄漏p高位 bitLen > 300, 因此可以 coppersmith 分解 clown(n) 得到 P, Q cut = 512 - cache*4 print(f'{cut = }') n = 924936528644761261915490226270682878749572154775391302241867565751616615723850084742168094776229761548826664906020127037598880909798055174894996273670320006942669796769794827782190025101253693980249267932225152093301291975335342891074711919668098647971235568200490825183676601392038486178409517985098598981313504275523679007669267428032655295176395420598988902864122270470643591017567271923728446920345242491655440745259071163984046349191793076143578695363467259 P = 569152976869063146023072907832518894975041333927991456910198999345700391220835009080679006115013808845384796762879536272124713177039235766835540634080670611913370463720348843789609330086898067623866793724806787825941048552075917807777474750280276411568158631295041513060119750713892787573668959642318994049493233526305607509996778047209856407800405714104373282610244944206314614906974275396096712817649817035559000245832673082730407216670764400076473183825246052 Q = 600870923560313304359037202752076267074889238956345564584928427345594724253036201151726541881494799597966727749590645445697106549304014936202421316051605075583257261728145977582815350958084624689934980044727977015857381612608005101395808233778123605070134652480191762937123526142746130586645592869974342105683948971928881939489687280641660044194168473162316423173595720804934988042177232172212359550196783303829050288001473419477265817928976860640234279193511499 R = 502270534450244040624190876542726461324819207575774341876202226485302007962848054723546499916482657212105671666772860609835378197021454344356764800459114299720311023006792483917490176845781998844884874288253284234081278890537021944687301051482181456494678641606747907823086751080399593576505166871905600539035162902145778102290387464751040045505938896117306913887015838631862800918222056118527252590990688099219298296427609455224159445193596547855684004680284030 c = 10585127810518527980133202456076703601165893288538440737356392760427497657052118442676827132296111066880565679230142991175837099225733564144475217546829625689104025101922826124473967963669155549692317699759445354198622516852708572517609971149808872997711252940293211572610905564225770385218093601905012939143618159265562064340937330846997881816650140361013457891488134685547458725678949 PR.<x> = PolynomialRing(Zmod(clown)) # 定义多项式环, Zmod(n)是模n的多项式环 f = trick + x # 定义多项式f p_low = f.small_roots(X = 2**cut, beta=0.45)[0] print(f'{hex(p_low) = }') print(f'{p_low = }') # p_low = 76347864203588455868161824448305083084387260376528823546715135 print(f'p_low的二进制位长: {len(bin(p_low))-2}') # -2是因为bin()返回的字符串前面有0b p = p_low + trick print(hex(p)) q = clown//int(p) assert p*q == clown # 确保p,q是clown的因子 # 计算R """ PR.<x> = PolynomialRing(Zmod(n)) r = (P-x)*(Q-x)*(R-x) rm = r.monic() # 用monic方法将r转化为首一多项式 _R = ZZ(rm.small_roots(X=2**256)[0]) # ZZ是整数环 N = ZZ(p)*ZZ(q)*ZZ(_R) e = 65537 phi = (p-1)*(q-1)*(_R-1) # 也可以不算R, 因为flag很小可以直接用p,q算得出的phi, 同时为了匹配p, q, 我们N也换成p*q即为clown """ N = clown phi = (p-1)*(q-1) d = int(inverse_mod(e,phi)) m = pow(c,d,N) from Crypto.Util.number import * print(long_to_bytes(int(m))) print(m) # Output: 0xf93bccfd5550cb15211bdc316f1b15cdfbc1f3e54a7745b9c4835f5346fa7f1d9560784892728000000000000000000000000000000000000000000000000000 cache = 76 泄漏bit位长: bitLens = 304 cut = 208 hex(p_low) = '0x2f82ea9f0e432e03c74e113f0f2d3ee868da63335cdc30a29bff' p_low = 76347864203588455868161824448305083084387260376528823546715135 p_low的二进制位长: 206 0xf93bccfd5550cb15211bdc316f1b15cdfbc1f3e54a7745b9c4835f5346fa7f1d956078489272af82ea9f0e432e03c74e113f0f2d3ee868da63335cdc30a29bff b'SYC{N0b0dy_Kn0vvs_CryPt0_be7t3r_7haN_Me}' 695436377443587187633900436650862817189253770609407637864965962513329890598866383949073658766717 solve~

生成时形如如下式子生成的密钥都有会受到ROCA攻击(CVE-2017-15361) [公式] 去Gitlab clone下 ROCA 攻击的源码 (neca) 接着 cd 进入刚刚 clone 项目的目录进行类似下面的操作 lov3@txt:~/tools/Crypto/neca$ ls CMakeLists.txt LICENSE README build cmake src lov3@txt:~/tools/Crypto/neca$ rm build/ rm: cannot remove 'build/': Is a directory lov3@txt:~/tools/Crypto/neca$ rm -rf build/ lov3@txt:~/tools/Crypto/neca$ ls CMakeLists.txt LICENSE README cmake src lov3@txt:~/tools/Crypto/neca$ mkdir build lov3@txt:~/tools/Crypto/neca$ cd build/ lov3@txt:~/tools/Crypto/neca/build$ cmake .. -- The C compiler identification is GNU 11.3.0 -- The CXX compiler identification is GNU 11.3.0 -- Detecting C compiler ABI info -- Detecting C compiler ABI info - done -- Check for working C compiler: /usr/bin/cc - skipped -- Detecting C compile features -- Detecting C compile features - done -- Detecting CXX compiler ABI info -- Detecting CXX compiler ABI info - done -- Check for working CXX compiler: /usr/bin/c++ - skipped -- Detecting CXX compile features -- Detecting CXX compile features - done -- Found GMP: /usr/lib/aarch64-linux-gnu/libgmp.so -- Found OpenMP_C: -fopenmp (found version "4.5") -- Found OpenMP_CXX: -fopenmp (found version "4.5") -- Found OpenMP: TRUE (found version "4.5") -- Configuring done -- Generating done -- Build files have been written to: /home/lov3/tools/Crypto/neca/build lov3@txt:~/tools/Crypto/neca/build$ ls CMakeCache.txt CMakeFiles Makefile cmake_install.cmake lov3@txt:~/tools/Crypto/neca/build$ make [ 50%] Building CXX object CMakeFiles/neca.dir/src/main.cpp.o [100%] Linking CXX executable neca [100%] Built target neca lov3@txt:~/tools/Crypto/neca/build$ ls CMakeCache.txt CMakeFiles Makefile cmake_install.cmake neca lov3@txt:~/tools/Crypto/neca/build$ ./neca NECA - Not Even Coppersmith's Attack ROCA weak RSA key attack by Jannis Harder ([email protected]) *** Currently only 512-bit keys are supported *** *** OpenMP support enabled *** Usage: neca <N> lov3@txt:~/tools/Crypto/neca/build$ 工具安装完成，用这道题(BattleCTF-rockyou) 试试工具 from Crypto.Util.number import bytes_to_long FLAG = bytes_to_long(open("flag.txt").read().encode()) n = 14558732569295568217680262946946350946269492093750369718350618000766298342508431492935822827678025952146979183716519987777790434353113812051439651306232101 e = 65537 c = pow(FLAG, e, n) print(f"c = {c}") # c = 10924637845512114669339598787759482373871484619074241479073765261738618851409833137908272858354441670603598700617114497065118363300675413269144392865493504 **lov3@txt**:**~/tools/Crypto/neca/build**$ ./neca 14558732569295568217680262946946350946269492093750369718350618000766298342508431492935822827678025952146979183716519987777790434353113812051439651306232101 NECA - Not Even Coppersmith's Attack ROCA weak RSA key attack by Jannis Harder ([email protected]) *** Currently only 512-bit keys are supported *** *** OpenMP support enabled *** N = 14558732569295568217680262946946350946269492093750369718350618000766298342508431492935822827678025952146979183716519987777790434353113812051439651306232101 Factoring... [=============== ] 62.14% elapsed: 175s left: 106.63s total: 281.64s Factorization found: N = 127801155916875524149457561567678575565270601000365665873572024750823913157383 * 113917064871970833547038329106470040388258358281464605006613652518914797349747 拿到p，q 写个程序解出m q = 127801155916875524149457561567678575565270601000365665873572024750823913157383 p = 113917064871970833547038329106470040388258358281464605006613652518914797349747 c = 10924637845512114669339598787759482373871484619074241479073765261738618851409833137908272858354441670603598700617114497065118363300675413269144392865493504 e = 65537 n = p * q d = inverse_mod(e, (p - 1) * (q - 1)) pt = pow(c, d, n) from Crypto.Util.number import long_to_bytes print(long_to_bytes(pt)) # Output: # b'battleCTF{ROCA_shork_me_0x0x0x}\n' solve~ 存一下sage解ROCA的代码 fllename: sage_functions.py #sage_functions.py from sage.all_cmdline import * def coppersmith_howgrave_univariate(pol, modulus, beta, mm, tt, XX): """ Taken from https://github.com/mimoo/RSA-and-LLL-attacks/blob/master/coppersmith.sage Coppersmith revisited by Howgrave-Graham finds a solution if: * b|modulus, b >= modulus^beta , 0 < beta <= 1 * |x| < XX More tunable than sage's builtin coppersmith method, pol.small_roots() """ # # init # dd = pol.degree() nn = dd * mm + tt # # checks # if not 0 < beta <= 1: raise ValueError("beta should belongs in [0, 1]") if not pol.is_monic(): raise ArithmeticError("Polynomial must be monic.") # # calculate bounds and display them # """ * we want to find g(x) such that ||g(xX)|| <= b^m / sqrt(n) * we know LLL will give us a short vector v such that: ||v|| <= 2^((n - 1)/4) * det(L)^(1/n) * we will use that vector as a coefficient vector for our g(x) * so we want to satisfy: 2^((n - 1)/4) * det(L)^(1/n) < N^(beta*m) / sqrt(n) so we can obtain ||v|| < N^(beta*m) / sqrt(n) <= b^m / sqrt(n) (it's important to use N because we might not know b) """ # # Coppersmith revisited algo for univariate # # change ring of pol and x polZ = pol.change_ring(ZZ) x = polZ.parent().gen() # compute polynomials gg = [] for ii in range(mm): for jj in range(dd): gg.append((x * XX) ** jj * modulus ** (mm - ii) * polZ(x * XX) ** ii) for ii in range(tt): gg.append((x * XX) ** ii * polZ(x * XX) ** mm) # construct lattice B BB = Matrix(ZZ, nn) for ii in range(nn): for jj in range(ii + 1): BB[ii, jj] = gg[ii][jj] BB = BB.LLL() # transform shortest vector in polynomial new_pol = 0 for ii in range(nn): new_pol += x ** ii * BB[0, ii] / XX ** ii # factor polynomial potential_roots = new_pol.roots() # test roots roots = [] for root in potential_roots: if root[0].is_integer(): result = polZ(ZZ(root[0])) if gcd(modulus, result) >= modulus ** beta: roots.append(ZZ(root[0])) return roots 替换入自己的 $n$ fllename: ROCA_attack.py from sage.all import * from tqdm import tqdm def solve(M, n, a, m): # I need to import it in the function otherwise multiprocessing doesn't find it in its context from sage_functions import coppersmith_howgrave_univariate base = int(65537) # the known part of p: 65537^a * M^-1 (mod N) known = int(pow(base, a, M) * inverse_mod(M, n)) # Create the polynom f(x) F = PolynomialRing(Zmod(n), implementation='NTL', names=('x',)) (x,) = F._first_ngens(1) pol = x + known beta = 0.1 t = m+1 # Upper bound for the small root x0 XX = floor(2 * n**0.5 / M) # Find a small root (x0 = k) using Coppersmith's algorithm roots = coppersmith_howgrave_univariate(pol, n, beta, m, t, XX) # There will be no roots for an incorrect guess of a. for k in roots: # reconstruct p from the recovered k p = int(k*M + pow(base, a, M)) if n%p == 0: return p, n//p def roca(n): keySize = n.bit_length() if keySize <= 960: M_prime = 0x1b3e6c9433a7735fa5fc479ffe4027e13bea m = 5 elif 992 <= keySize <= 1952: M_prime = 0x24683144f41188c2b1d6a217f81f12888e4e6513c43f3f60e72af8bd9728807483425d1e m = 4 print("Have you several days/months to spend on this ?") elif 1984 <= keySize <= 3936: M_prime = 0x16928dc3e47b44daf289a60e80e1fc6bd7648d7ef60d1890f3e0a9455efe0abdb7a748131413cebd2e36a76a355c1b664be462e115ac330f9c13344f8f3d1034a02c23396e6 m = 7 print("You'll change computer before this scripts ends...") elif 3968 <= keySize <= 4096: print("Just no.") return None else: print("Invalid key size: {}".format(keySize)) return None a3 = Zmod(M_prime)(n).log(65537) order = Zmod(M_prime)(65537).multiplicative_order() inf = a3 // 2 sup = (a3 + order) // 2 # Search 10 000 values at a time, using multiprocess # too big chunks is slower, too small chunks also chunk_size = 10000 for inf_a in tqdm(range(inf, sup, chunk_size)): # create an array with the parameter for the solve function inputs = [((M_prime, n, a, m), {}) for a in range(inf_a, inf_a+chunk_size)] # the sage builtin multiprocessing stuff from sage.parallel.multiprocessing_sage import parallel_iter from multiprocessing import cpu_count for k, val in parallel_iter(cpu_count(), solve, inputs): if val: p = val[0] q = val[1] print("found factorization:\np={}\nq={}".format(p, q)) return val if __name__ == "__main__": # Normal values #p = 88311034938730298582578660387891056695070863074513276159180199367175300923113 #q = 122706669547814628745942441166902931145718723658826773278715872626636030375109 #a = 551658, interval = [475706, 1076306] # won't find if beta=0.5 # p = 80688738291820833650844741016523373313635060001251156496219948915457811770063 # q = 69288134094572876629045028069371975574660226148748274586674507084213286357069 # #a = 176170, interval = [171312, 771912] # n = p*q n = 14558732569295568217680262946946350946269492093750369718350618000766298342508431492935822827678025952146979183716519987777790434353113812051439651306232101 # For the test values chosen, a is quite close to the minimal value so the search is not too long roca(n) 利用 两个代码放在同一个目录下，被引用的代码名必须为 sage_functions.py sage ROCA_attack.py 即可得到 $p, q$ 但是 ARM macOS make 的时候就会出现很多问题, 如下, 有大佬看见知道怎么就觉请评论告知 lov3@Cryptoer ~/D/C/T/n/build> cmake --build . master! [ 50%] Building CXX object CMakeFiles/neca.dir/src/main.cpp.o clang: warning: argument unused during compilation: '-Xclang -fopenmp -I/opt/homebrew/Cellar/libomp/16.0.6/include' [-Wunused-command-line-argument] In file included from /Users/lov3/Documents/Code/Tools/neca/src/main.cpp:12: /Users/lov3/Documents/Code/Tools/neca/src/arith.h:28:24: error: cannot initialize a variable of type 'const ulimb_t *' (aka 'const unsigned long long *') with an rvalue of type 'mp_srcptr' (aka 'const unsigned long *') ulimb_t const *value_limbs = mpz_limbs_read(value.get_mpz_t()); ^ ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ /Users/lov3/Documents/Code/Tools/neca/src/arith.h:59:18: error: cannot initialize a variable of type 'ulimb_t *' (aka 'unsigned long long *') with an rvalue of type 'mp_ptr' (aka 'unsigned long *') ulimb_t *value_limbs = mpz_limbs_write(value.get_mpz_t(), W); ^ ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 2 errors generated. make[2]: *** [CMakeFiles/neca.dir/src/main.cpp.o] Error 1 make[1]: *** [CMakeFiles/neca.dir/all] Error 2 make: *** [all] Error 2 lov3@Cryptoer ~/D/C/T/n/build> 2 master!

学习动机 国赛有道题可以随机生成一组pq试试运气，而且队友确实跑出来了（2023CISCN初赛-badkey） 于是就来学一下多线程，这样比赛需要爆k的时候也比较快 multiprocessing — 基于进程的并行 概述 from multiprocessing import Pool def f(x): return x*x if __name__ == '__main__': # Pool()创建进程池 https://docs.python.org/zh-cn/3/library/multiprocessing.html#multiprocessing.pool.Pool with Pool(5) as p: # 5个进程， with语句会自动调用close()和join()方法 , print(p.map(f, [1, 2, 3])) # map()会将第二个参数的每个元素作为第一个参数的参数，返回一个列表 # Output: # [1],[4],[9] Process 类 在 multiprocessing 中，通过创建一个 Process 对象然后调用它的 start() 方法来生成进程。 Process 和 threading.Thread API 相同。 一个简单的多进程程序示例是: