题目附件 from Crypto.Util.number import * from secret import flag def genKey(nbits): p = getPrime(nbits) q = getPrime(nbits) N = p*p*q d = inverse(N, (p-1)*(q-1)//GCD(p-1, q-1)) return N,d def encrypt(message,N): m = bytes_to_long(flag) c = pow(m, N, N) return c nbits = 1024 m = bytes_to_long(flag) N,d = genKey(nbits) c = encrypt(m,N) print('c =', c) print('N =', N) print('d =', d) """ c = 29897791365314067508830838449733707533227957127276785142837008063510003132596050393885548439564070678838696563164574990811756434599732001622138564176327233154381380717648392357672642893142367607369679906940371540867456654151408884171467638060523066406441697453971996011548195499549200103123841556085936672833238264876038160712793697159776332101536779874757463509294968879216810485825310481778472384531442206034564488532399171243463881900578407746982324779260941957792455217641883334131366614310644607114128868153897806362954456585661855569432513785225453501792356175649676419772626548071916379318631677869452985829916084336045071072493567871623113923140668031380684940109024609167449291380675124701557542736834722898328082888430566229322840781411336263268594978558564310744076581639469210462567543585251718744340216155557606004995449505782302864725856877289388008819135023371948017425832082773421030256964953984562211638060 N = 3231913372897424708803097969843687520868057190788284975066875241636436021279559026753076528399891936983240045179193386905918743759145596242896507856007669217275515235051689758768735530529408948098860529277921046146065473333357110158008648799207873976745048714516868561754202543130629713461365314627535982379718931633528922076268531363809414255082933615667770491818402126891370106045838695484124212397783571579791558324350069782623908757815983802849109451590357380624488436968737140312471089662428308113246310588336044438265822574558816510054763215983649467009345458480077882624118620789015758507736272402998721366662352794082495441303895025585316667229865533166614969641012195668280586477033200418153345241668242651407009849656745509386158276185301334443855737552801531617549980843398648751032649895403939319648954908487619711555700124294191702406981128355348449748466449951568451135718146828444185238617155432417897711198169 d = 220908195398117048628110042133057032501548264225985823161565460390793825899523662424732910718579350524590368287207857059670558852106434615134645183432670023784725430385048028248108677670095524205518013647694485975996499747580966911259433184798952372110628624294686853944766950244209186984164963987120416687012811346656498861438432610431705868541829977481875385468143747334359481673214618931159403123892213161430602430294790913847722073762999311674428134241956293914716183107414340330449465142849402354034926378025006749405210014879947411570380433942279355488861684317611066949685697268714760755591128598654573304969 """ 思路 定义模数 $N$ 和 解密指数 $d$ 之间的关系 [公式] 解密指数 $d$ 的计算公式

Reference 基础 What is modular arithmetic? (article) | Khan Academy 中国剩余定理 - OI Wiki 视频/会议 论文 1111.4877.pdf 题目 hackergame2019-writeups/official/十次方根 at master · ustclug/hackergame2019-writeups · GitHub Intended Solution to Crypto Problems in NCTF 2019 | Soreat_u’s Blog 进阶 Using the CRT with RSA 代码 Python2 RSA/rth-root extraction at master · mad-jcbx/RSA · GitHub 拓展 Elements of Z/nZ - Finite Rings AMM 算法详解与应用 AMM算法简要理解（Adleman-Mander-Miller Method） 工具 factordb 讨论 Improved nth root for finite fields and integer_mods · Issue #7931 · sagemath/sage · GitHub sage/src/sage/rings/finite_rings/integer_mod.pyx at 3dd953c3aa6b5143071b6c39208199cf128c8080 · sagemath/sage · GitHub 导言 在一般情况的RSA中，求出 $\phi(N)$ 就已经接近解出明文了。这个时候我们往往只需要通过 $ed\equiv1 \pmod {\phi (N)}$ 即可求出私钥 $d$，从而求出明文。但是要直接求逆元 $d$，需要满足 $gcd(e,\phi(N))=1$，也就是 $e$ 和 $\phi(N)$ 互质的情况。如果不满足，则会大大提高难度。

Reference 怎么样用c语言求1000的阶乘？ - 知乎 SpeedUp 题意: 提交 'flag' + {{ $\text{SHA256}\left(\sum_{{i=0}}^{{\lfloor \log_{10} (2^{27}!) \rfloor}} \left( \left\lfloor \frac{{2^{27}!}}{{10^i}} \right\rfloor \mod 10 \right)\right)$ }} + '}' / 上面这个式子让 GPT 写的 (图一乐，而且这么求 number length 慢的要死(慢过 str(number).__len__()，而实际上是可以 log 巴拉巴拉求的，忘了复杂度了，总之是可以更快，而且实际上也不用求长度，见最后的代码))

因为一些事情得重新拾起算法了 / Reference(Aka thanks)(可能"Reference"在这里的用法不太对，欢迎提醒我来纠正) Wiki 时间复杂度 - 维基百科，自由的百科全书 快速幂 - OI Wiki 基础 [[Binary Exponentiation]] [[Linear Algebra|矩阵乘法]] 视频 509 Luogu P3390【模板】矩阵快速幂 bilibili 题目 P1226 【模板】快速幂 - 洛谷 | 计算机科学教育新生态 P3390 【模板】矩阵快速幂 - 洛谷 | 计算机科学教育新生态 讨论(想法) 似乎还可以通过剪枝优化，下次() 关于快速幂的名字笔者并无好感，更喜欢称其为“二进制求幂”，非常直观 把基础拿出来讲 – 矩阵乘法 矩阵乘法:

2023年四川网信人才技能大赛（网络安全管理员赛项）决赛 / 题目附件 from Crypto.Util.number import * from secret import flag from sympy import nextprime flag=b'' r = getRandomNBitInteger(64) p = r**5 + r**4 - r**3 + r**2 - r + 2023 q = r**5 - r**4 + r**3 - r**2 + r + 2023 p =nextprime(p) q =nextprime(q) n = p*q def enc(flag, n): m = bytes_to_long(flag) return pow(m, 65537, n) c = enc(flag, n) print(n) print(c) # 25066797992811602609904442429968244207814135173233823574561146780193277243588729282392464721760638040595480284865294238118778099149754637586361909432730412493061503054820202744474632665791457 # 18808483076270941157829928736000549389727451019027515249724024369421942132354537978233676261769285858813983730966871222263698559152437016666829640339912308636169767041243411900882395764607422 Exploit Sage / P.<r> = PolynomialRing(QQ) fp = r**5 + r**4 - r**3 + r**2 - r + 2023 fq = r**5 - r**4 + r**3 - r**2 + r + 2023 print(f'{latex((fp * fq))}') # n的最大项只有r^8，所以对n开十次过后基本就等于r r_max = (1 << 64) - 1 # 接着还可以减一个小值来模拟随机, 或者用题目的r生成方式, 会发现对最后的结果没有影响 p = fp(r = r_max) q = fq(r = r_max) P = Primes() p = P.next(Integer(p)) q = P.next(Integer(q)) n = p * q Diff = int(real_nth_root(n, 10)) - r_max print(f'{Diff = }') # 于是 换上题目数据 n = 25066797992811602609904442429968244207814135173233823574561146780193277243588729282392464721760638040595480284865294238118778099149754637586361909432730412493061503054820202744474632665791457 r = int(real_nth_root(n, 10)) - Diff p = fp(r = r) q = fq(r = r) p = P.next(Integer(p)) q = P.next(Integer(q)) assert p * q == n phi = (p - 1) * (q - 1) e = 0x10001 c = 18808483076270941157829928736000549389727451019027515249724024369421942132354537978233676261769285858813983730966871222263698559152437016666829640339912308636169767041243411900882395764607422 d = inverse_mod(e, phi) m = power_mod(c, d, n) from Crypto.Util.number import long_to_bytes print(long_to_bytes(m)) Output

一年一度的密码盛宴, 看春哥队和 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$

安利大佬的博客, 讲了 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 '''

生成时形如如下式子生成的密钥都有会受到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!

密码1-基于国密SM2算法的密钥密文分发 按照附件写exp # 自动发包 import requests import json import base64 import binascii import urllib.parse as parse from gmssl import sm2, func from gmssl.sm4 import CryptSM4, SM4_ENCRYPT, SM4_DECRYPT # curl -d "name=%E5%93%88%E5%93%88&school=%E5%AE%89%E5%BE%BD%E5%A4%A7%E5%AD%A6&phone=15958198820" http://192.168.31.153:3000/api/login url = 'http://39.105.187.49:16435' data = { 'name': '1', 'school': '1', 'phone': '1' } # 对data进行url编码 data = parse.urlencode(data) # import urllib.parse as parse # print(data) 接口 = '/api/login' res = requests.post(url + 接口, data=data) json_data = json.loads(res.text) data = json_data['data'] # print(data) id = data['id'] print(id) # 1，登录选手信息获取唯一id # 把id发给 /api/allkey 接口 = '/api/allkey' res = requests.post(url + 接口, data={'id': id}) # print(res.text) json_data = json.loads(res.text) data = json_data['data'] publicKey = data['publicKey'] # 选手SM2公钥 privateKey = data['privateKey'] # 选手SM2私钥 randomString = data['randomString'] # print('publicKey\n', publicKey) # print('privateKey\n', privateKey) # print('randomString\n', randomString) # 将公钥传回 接口 = '/api/allkey' # 2，发送选手SM2公钥到服务端，并获取服务端加密后的随机数密文、私钥密文和公钥明文 # 服务器使用国密SM2算法生成密钥对B(公钥B_Public_Key、私钥B_Private_Key)、使用量子随机数发生器产生16字节随机数C；服务器首先使用16字节随机数C对私钥B_Private_Key采用SM4ECB算法加密得到私钥B_Private_Key密文，然后使用A_Public_Key对16字节随机数C进行SM2加密得到随机数C密文； res = requests.post(url + 接口, data={'id': id, 'publicKey': publicKey}) # print(res.text) B公钥明文 = json.loads(res.text)['data']['publicKey'] 随机数C对私钥B_Private_Key采用SM4ECB算法加密得到私钥B_Private_Key密文 = json.loads(res.text)[ 'data']['privateKey'] 量子随机数发生器产生16字节随机数C密文 = json.loads(res.text)['data']['randomString'] # print('serverPublicKey\n', serverPublicKey) # 用户使用私钥A_Private_Key，对随机数C密文进行SM2解密，获取16字节随机数C明文； sm2_crypt = sm2.CryptSM2( public_key=publicKey, private_key=privateKey) print('sm4密文_\n', 量子随机数发生器产生16字节随机数C密文) # print(' # AttributeError: 'str' object has no attribute 'hex' 量子随机数发生器产生16字节随机数C密文 = binascii.a2b_hex(量子随机数发生器产生16字节随机数C密文) 量子随机数发生器产生16字节随机数C明文 = sm2_crypt.decrypt(量子随机数发生器产生16字节随机数C密文) # 量子随机数发生器产生16字节随机数C明文 转为字节 量子随机数发生器产生16字节随机数C明文 = binascii.b2a_hex(量子随机数发生器产生16字节随机数C明文) # 用户使用16字节随机数C明文，对私钥B_Private_Key密文，采用SM4ECB算法解密，得到私钥B_Private_Key明文； print('量子c\n', 量子随机数发生器产生16字节随机数C明文) sm4_crypt = CryptSM4() sm4_crypt.set_key(量子随机数发生器产生16字节随机数C明文, SM4_DECRYPT) 私钥B_Private_Key明文 = sm4_crypt.crypt_ecb( 随机数C对私钥B_Private_Key采用SM4ECB算法加密得到私钥B_Private_Key密文.encode('utf-8')) 私钥B_Private = binascii.b2a_hex(私钥B_Private_Key明文) print('私钥B_Private\n', 私钥B_Private) # 这里发现解出的私钥有问题 有可能为空 猜想是否解密错误 # 用户向服务器请求密钥，服务器使用公钥B_Public_Key明文，对密钥D(16字节)采用SM2算法加密，将密钥D密文传输给用户； check接口 = '/api/check' # 不过在这里check的时候发现一直check错误。。。 # 尝试找漏洞 后面有的注释是第一次按文件写的时候写的 接口 = '/api/quantum' res = requests.post(url + 接口, data={'id': id}) # print(res.text) quantumString = json.loads(res.text)['data']['quantumString'] res = requests.post(url + check接口, data={'id': id, 'quantumString': quantumString}) # print('quantumString\n', quantumString) # 用户使用私钥B_Private_Key明文，对密钥D密文进行解密，得到密钥D明文； sm2_crypt2 = sm2.CryptSM2( public_key=B公钥明文, private_key=私钥B_Private) quantumString = binascii.a2b_hex(quantumString) quantumString = sm2_crypt2.decrypt(quantumString) quantumString = binascii.b2a_hex(quantumString) print('quantumString\n', quantumString) # 用户将密钥D明文，上报至服务器进行验证，服务器返回参赛结果；用户可向服务器查询个人信息及参赛结果。 # 尝试非预期 quantumString = quantumString.decode('utf-8') res = requests.post(url + 接口, data={'id': id, 'quantumString': quantumString}) print(res.text) res = requests.post(url + 接口, data={'id': id, 'quantumString': quantumString}) print(res.text) 接口 = '/api/search' res = requests.post(url + 接口, data={'id': id}) print(res.text) quantumStringServer = json.loads(res.text)['data']['quantumStringServer'] print('quantumStringServer\n', quantumStringServer) res = requests.post(url + check接口, data={'id': id, 'quantumString': quantumStringServer}) res = requests.post(url + 接口, data={'id': id}) print(res.text) 密码2-可信度量 在根目录下递归搜索包含字符串"flag"的文件，并将结果输出到标准输出，并过滤掉无权访问的行 grep -ra "flag" / 2>&1 | grep -v "Permission denied" | grep -v "denied$" --line-buffered 密码3-Sign_in_passwd 文件后缀改txt后(方便查阅) url解码第二行信息后base64换表 第一行作为密文 第二行作为表来解 密码4-badkey1 题面 from Crypto.Util.number import * from Crypto.PublicKey import RSA from hashlib import sha256 import random, os, signal, string def proof_of_work(): random.seed(os.urandom(8)) proof = ''.join([random.choice(string.ascii_letters+string.digits) for _ in range(20)]) _hexdigest = sha256(proof.encode()).hexdigest() print(f"sha256(XXXX+{proof[4:]}) == {_hexdigest}") print('Give me XXXX: ') x = input() if len(x) != 4 or sha256(x.encode()+proof[4:].encode()).hexdigest() != _hexdigest: print('Wrong PoW') return False return True if not proof_of_work(): exit(1) signal.alarm(10) print("Give me a bad RSA keypair.") try: p = int(input('p = ')) q = int(input('q = ')) assert p > 0 assert q > 0 assert p != q assert p.bit_length() == 512 assert q.bit_length() == 512 assert isPrime(p) assert isPrime(q) n = p * q e = 65537 assert p % e != 1 assert q % e != 1 d = inverse(e, (p-1)*(q-1)) except: print("Invalid params") exit(2) try: key = RSA.construct([n,e,d,p,q]) print("This is not a bad RSA keypair.") exit(3) except KeyboardInterrupt: print("Hacker detected.") exit(4) except ValueError: print("How could this happen?") from secret import flag print(flag) 按照 brealid 师傅的推导过程自己推了一遍 工作量证明 模板 import hashlib import string import itertools from tqdm import tqdm from pwn import * # 遍历所有的XXXX，找到符合条件的XXXX b = string.digits + string.ascii_letters + string.punctuation strL = itertools.product(b, repeat=4) ip = '47.93.187.243' port = 39092 io = remote(ip, port, level='debug') data = io.recvline() # print(data) # b'sha256(XXXX+2ywKnEOsDsVMJXvP) == f8ffb979f1819dba9905c67b9b85874c681807f6e3cb2953901785764f5e8db8\n' 残缺的sha = data.split(b'+')[1].split(b')')[0] sha256后的值 = data.split(b'== ')[1].strip() hash_object = hashlib.sha256() for i in strL: a = i[0] + i[1] + i[2] + i[3] sha = a + 残缺的sha.decode() # print(sha) hash_object.update(sha.encode()) digest = hash_object.digest() hex_digest = digest.hex() if hex_digest == sha256后的值.decode(): print(a) io.sendline(a.encode()) break io.interactive() 推导