RSA - HackMD

--- title: RSA --- # RSA - RSA (Rivest–Shamir–Adleman) là một trong những thuật toán mật mã khóa công khai nổi tiếng và được sử dụng rộng rãi nhất hiện nay. Thuật toán được xây dựng dựa trên độ khó của bài toán phân tích một số nguyên lớn thành thừa số nguyên tố. Nguyên lý hoạt động của RSA gồm ba bước chính: sinh khóa, mã hóa và giải mã. Với một cặp khóa công khai và khóa bí mật, RSA cho phép người dùng vừa bảo mật thông tin, vừa xác thực danh tính thông qua chữ ký số. ![RSA](https://hackmd.io/_uploads/r1LzwRxTgl.png) - Nguyên lý hoạt động của RSA: - 1. Khởi tạo: - Sinh ngẫu nhiên 2 số nguyên tố p và q. - Tạo modulus n : $n = p \cdot q$ - 2. Tạo khóa - Ta có hàm Euler: $\varphi(n) = (p - 1)(q - 1)$ - Chọn số mũ công khai e sao cho: $\gcd(e,\varphi(n)) = 1$ (thường dùng e = 65537 ). - Tính khóa bí mật d : $d = e^{-1} \pmod{\varphi(n)}$ - Lúc này ta có cặp khóa: + **Khóa công khai**: e + **Khóa bí mật**: d - 3. Mã hóa: - Với plaintext M, ta sẽ tính được ciphertext C theo công thức : $$C = M^e \pmod{n}$$ - 4. Giải mã: Với ciphertext C, ta tính ngược lại plaintext M bằng công thức: $$M = C^d \pmod{n}$$ - Chứng minh: $C^d \pmod{n} = (M^e)^d \pmod{n} = M^{ed} \pmod{n}$. - Ta có: $d = e^{-1} \pmod{\varphi(n)}$ <=> $d .e = 1 \pmod{\varphi(n)}$ <=> $d.e = 1 + k .\varphi(n)$ - Nên: $M^{ed} \pmod{n}$ = $M^{1 + k. \varphi(n)} \pmod{n} = M . (M^{k})^{\varphi(n)} \pmod{n}$ (*) - Mà ta có định lý Euler: $a^{\varphi(n)} \equiv 1 \pmod{n}$ nên phương trình (*) trở thành $C^d = M \pmod{n}$ --- # RSA ATTACK ## Factorization - Độ mạnh yếu của RSA phụ thuộc vào N lớn hay nhỏ, vì nếu N nhỏ ta có thể phân tích thừa số nguyên tố của N từ đó tính được $\varphi(N)$ dễ dàng - Ta có thể dùng hàm `factorint()` của thư viện sympy hoặc dùng sage, [factordb](https://factordb.com/index.php) ## Common modulus attack ### As an external attacker - Đây là kiểu tấn công khi bạn là người bên ngoài của tổ chức, bạn thu thập được $N$, $C_i$, $e_i$ của từng người thì ta sẽ có thể tìm được plaintext bằng cách: - Tính $gcd(e_i, e_j)$ - Theo định lý Euclid mở rộng ta có: $u.e_i + v.e_j = gcd(e_i, e_j) = 1$. Mà $C_i \equiv M^{e_i} \pmod N, C_j \equiv M^{e_j} \pmod N$, lấy $C_i^u.C_j^v = M^{e_i.u + e_j.v} = M$. Vậy là nhờ u, v ta đã tìm được M. ### As an internal attacker - Đây là kiểu tấn công khi chính bạn là người nằm bên trong tổ chức, bạn có $N, d_1, e_1$ của mình và muốn tấn công người có cặp $N, e_2, d_2$. Vậy lúc này chỉ cần tìm được $d_2$ là ta có thể tấn công được rồi, nhưng muốn tìm được $d_2$ thì ta phải tính được $\varphi(N)$, nhưng giả sử N rất lớn thì ta không thể factor được mà phải brute-force tìm $\varphi(N)$ như sau: - Ta có $d.e \equiv 1 \pmod {\varphi(N)}$ <=> $d.e - 1 = k.\varphi(N)$ => $k =\frac{e.d - 1} {\varphi(n)}$. - Mà $N > \varphi(N)$ nên: - $k_1 = \frac{e \times d - 1} {N} < k_2 = \frac{e \times d - 1} {\varphi(N)}$. Vậy ta cứ brute-force k thì sẽ tìm được $\varphi(N)$ ```py= k = (e*d - 1) // n while True: phi = (e*d - 1) // k if k*phi == e*d - 1: break k += 1 ``` - Nếu $d < \varphi(N)$ thì $k < e$ - Chứng minh: - $$d < \varphi(N) <=> e.d < e.\varphi(N)$$ - $k =\frac{e.d - 1} {\varphi(N)} < \frac{e.\varphi(N) - 1} {\varphi(N)} = e - \frac{1} {\varphi(N)}$, mà $\frac{1} {\varphi(N)}$ sẽ rất nhỏ Nếu $N$ lớn => $k < e$ ## Power attack on small public exponent - Khi N quá lớn mà e quá nhỏ thì dẫn tới trường hợp $M^e \pmod N$ vẫn = $M^e$, tức là $C = M^e$ => $M = \sqrt[e]{C}$. - Ta còn có thể mở rộng ra với trường hợp $M^e$ lớn hơn N "một chút", lúc này ta có $M^e = C + k.N$, ta cứ tăng k đến khi nào ra căn đúng thì dừng (có thể dùng hàm `iroot()` để check) ## Hastad’s Broadcast Attack - Khi ta có nhiều Ciphertext được mã hóa bằng 1 e giống nhau (e phải đủ nhỏ), ta có thể thực hiện kiểu attack này, giả sử ta có 3 Ciphertext: $$\begin{cases} C_1 \equiv m^e \pmod{N1}\\ C_2 \equiv m^e \pmod{N2}\\ C_3 \equiv m^e \pmod{N3} \end{cases}$$ - Hoặc ta có thể viết lại là \begin{cases} m^e \equiv C_1 \pmod{N1}\\ m^e \equiv C_2 \pmod{N2}\\ m^e \equiv C_3 \pmod{N3} \end{cases} - Đây là dạng hệ phương trình đồng dư => ta có thể giải bằng CRT để thu được $m^e \equiv M \pmod N$ (với $N = N_1.N_2.N_3.N_i$), và vì e đủ nhỏ => $m^e < N$ nên ta chỉ cần lấy $m = \sqrt[e]{M}$ > Điều kiện để Hastad’s Broadcast Attack là $m^e < N$ vì chỉ khi đó ta lấy $m^e \pmod N$ mới ra $m^e$ ## Fermat’s attack - Khi chọn p, q quá gần nhau thì ta sẽ có thể dùng Fermat’s attack. - Điều kiện để có thể dùng Fermat's attack: $$p-q < \sqrt[4]{N}$$ - Ta biến đổi N: $$N = p.q = \left (\frac{p+q}{2}\right)^2 -\left (\frac{p-q}{2} \right)^{2} = x^2-y^2 = (x+y)(x-y)$$ - Vậy ta đã phân tích ra $p = x + y$, $q = x - y$. Ta chỉ cần tính $x, y$ sẽ tìm được $p, q$. Vì p, q gần nhau nên $\frac{p+q}{2} \approx \sqrt N$ mà $p = x + y, q = x - y$ => $\frac{p+q}{2} = \frac{x + y + x - y}{2} = x$ => $x \approx \sqrt N$ - Thuật toán: - Đặt $x = \left \lceil \sqrt{N} \right \rceil$, tính $y^2 = x^2 - N$. Nếu $y^2$ là số chính phương thì ta đã tìm được x, y. Nếu không thì tăng x lên ```py= def fermat_attack(n): x = math.isqrt(n) if x*x < n: x += 1 # đảm bảo x = ceil(sqrt(n)) while True: y2 = x*x - n if y2 >= 0: y = math.isqrt(y2) if y*y == y2: p = x + y q = x - y return p, q x += 1 ``` ## Wiener’s attack - Nếu $d$ quá nhỏ thì lúc này sẽ tạo ra lỗ hỏng, ta có thể dùng Wiener’s attack - Điều kiện để thực hiện (về mặt lý thuyết): $$d < \frac{1}{3} \sqrt[4]{N}$$ - Ta có $e.d = k.\varphi(N) + 1$, chia cả 2 vế cho $d.\varphi(N)$ ta có: $\frac {e} {\varphi(N)} =\frac {k}{d} + \frac{1}{d.\varphi(N)} \approx \frac {k}{d}$ (vì $\frac{1}{d.\varphi(N)}$ là một số rất nhỏ khi $\varphi(N)$ và $d$ lớn. Mà $\varphi(N) \approx N$ nên ta có thể viết $\frac{e}{N} \approx \frac{k}{d}$ - Phương trình trên cho thấy $\frac{e}{N}$ là một xấp xỉ rất tốt của N, lý thuyết liên phân số cho phép chúng ta tìm ra tất cả các phân số tối giản xấp xỉ tốt nhất cho một số cho trước. - Có thể dùng thư viện có sẵn để attack: ``` curl -O https://raw.githubusercontent.com/orisano/owiener/master/owiener.py ``` ## Blinding Attack - Đây là kiểu attack khi bạn muốn "qua mặt" sever để thu được flag. Ví dụ như sever kêu ta phải gửi đi một ciphertext nào đó để nó mã hóa (nhưng ta phải gửi đi 1 ciphertext nào đó mà khi được sever giải mã nó phải khác flag). - Ta biết ciphertext được mã hóa theo công thức $C \equiv M^e \pmod N$ - Lúc này ta chọn một số $r$ sao cho $gcd(N, r) = 1$, sau đó nhân $C$ với $r^e \pmod N$ thì ta thu được $C' \equiv C.r^e \pmod N$. - Sever sẽ tiến hành giải mã: $(C')^d \equiv C^d . r^{e.d} \pmod N = M.r$ - Vậy khi nhận được $M.r$ thì ta chỉ cần chia cho $r$ là thu được $M$ # CRYPTOHACK CHALLENGES ## Starter ### Modular Exponentiation ![Screenshot 2025-10-06 152113](https://hackmd.io/_uploads/Hy5M3lb6gx.png) - Mô tả: challenge giới thiệu cho ta về kiến thức toán học, đó là modular exponentiation (lũy thừa module) - Hướng dẫn: ta chỉ cần dùng hàm pow() trong python để tính $101^{17}$ mod 22663 - Source code giải: ```py= print(pow(101, 17, 222663)) ``` :::spoiler Flag 19906 ::: ### Public Keys ![Screenshot 2025-10-06 153225](https://hackmd.io/_uploads/HkajClb6lg.png) - Mô tả: challenge giới thiệu về cách RSA hoạt động - Hướng dẫn: ta đã được cung cấp 2 số nguyên tố p = 17, q = 23, M = 12. Dựa vào đây ta có thể tính module N = p*q, từ đó tính được ciphertext $C = M^e \pmod N$ - Source code giải: ```py= p, q = 17, 23 n = p * q e = 65537 m = 12 c = pow(m, e, n) print(c) ``` :::spoiler Flag 301 ::: ### Euler's Totient ![Screenshot 2025-10-06 154233](https://hackmd.io/_uploads/r1ifbZ-6ll.png) - Mô tả: challenge giới thiệu về phi hàm Euler, ta được cung cấp 2 số nguyên tố p, q. Nhiệm vụ của ta là tính $\varphi(N)$ với $N = p.q$ - Hướng dẫn: - Ta có tính chất của phi hàm Euler: - $\varphi(N) = \varphi(m).\varphi(n)$ với $N = m.n$ (1) - $\varphi(p) = p -1$ nếu p là số nguyên tố (2) - Từ (1), (2) ta có $\varphi(N) = \varphi(p) * \varphi(q) = (p-1)(q-1)$ - Source code giải: ```py= p = 857504083339712752489993810777 q = 1029224947942998075080348647219 phi = (p-1)*(q-1) print(phi) ``` :::spoiler Flag 882564595536224140639625987657529300394956519977044270821168 ::: ### Private Keys ![Screenshot 2025-10-06 155557](https://hackmd.io/_uploads/H1LB4ZW6ee.png) - Mô tả: challenge kêu ta tìm khóa bí mật d - Hướng dẫn: Dựa vào lý thuyết, ta có d là nghịch đảo của e trong module $\varphi(n)$ => ta có thể dùng hàm pow trong python để tính - Source code giải: ```python= p = 857504083339712752489993810777 q = 1029224947942998075080348647219 e = 65537 phi = (p-1)*(q-1) d = pow(e, -1, phi) print(d) ``` :::spoiler Flag 121832886702415731577073962957377780195510499965398469843281 ::: ### RSA Decryption ![Screenshot 2025-10-06 160223](https://hackmd.io/_uploads/S1G6r-b6le.png) - Mô tả: ta được cung cấp N, e, ciphertext, nhiệm vụ của ta là decrypt ciphertext bằng khóa d tìm được ở challenge trước: - Hướng dẫn: Vì đã có d nên ta dễ dàng tìm được plaintext (M) bằng công thức: $$M \equiv C^d \pmod{n}$$ - Source code giải: ```py= n = 882564595536224140639625987659416029426239230804614613279163 e = 65537 d = 121832886702415731577073962957377780195510499965398469843281 c = 77578995801157823671636298847186723593814843845525223303932 m = pow(c, d, n) print(m) ``` :::spoiler Flag 13371337 ::: ### RSA Signatures ![Screenshot 2025-10-06 160820](https://hackmd.io/_uploads/By7EdZ-axg.png) ![Screenshot 2025-10-06 160833](https://hackmd.io/_uploads/H1QEOWWTxg.png) - Mô tả: challenge yêu cầu ta kí thông điệp `crypto{Immut4ble_m3ssag1ng}` bằng hàm băm sha256. - Hướng dẫn: ta sử dụng hàm SHA256 trong để hash chuỗi `crypto{Immut4ble_m3ssag1ng}` sau đó ký thông điệp này bằng khóa d riêng của mình: - Source code giải: ```py= from Crypto.Util.number import bytes_to_long from Crypto.Hash import SHA256 N = 15216583654836731327639981224133918855895948374072384050848479908982286890731769486609085918857664046075375253168955058743185664390273058074450390236774324903305663479046566232967297765731625328029814055635316002591227570271271445226094919864475407884459980489638001092788574811554149774028950310695112688723853763743238753349782508121985338746755237819373178699343135091783992299561827389745132880022259873387524273298850340648779897909381979714026837172003953221052431217940632552930880000919436507245150726543040714721553361063311954285289857582079880295199632757829525723874753306371990452491305564061051059885803 d = 11175901210643014262548222473449533091378848269490518850474399681690547281665059317155831692300453197335735728459259392366823302405685389586883670043744683993709123180805154631088513521456979317628012721881537154107239389466063136007337120599915456659758559300673444689263854921332185562706707573660658164991098457874495054854491474065039621922972671588299315846306069845169959451250821044417886630346229021305410340100401530146135418806544340908355106582089082980533651095594192031411679866134256418292249592135441145384466261279428795408721990564658703903787956958168449841491667690491585550160457893350536334242689 m = b"crypto{Immut4ble_m3ssag1ng}" h = SHA256.new(m).digest() s = pow(bytes_to_long(h), d, N) print(s) ``` :::spoiler Flag 13480738404590090803339831649238454376183189744970683129909766078877706583282422686710545217275797376709672358894231550335007974983458408620258478729775647818876610072903021235573923300070103666940534047644900475773318682585772698155617451477448441198150710420818995347235921111812068656782998168064960965451719491072569057636701190429760047193261886092862024118487826452766513533860734724124228305158914225250488399673645732882077575252662461860972889771112594906884441454355959482925283992539925713424132009768721389828848907099772040836383856524605008942907083490383109757406940540866978237471686296661685839083475 ::: ## Primes Part 1 ### Factoring ![Screenshot 2025-10-07 140459](https://hackmd.io/_uploads/BylniEz6lg.png) - Mô tả: trong RSA thường phải chọn N lớn để tránh việc có thể phân tích thừa số nguyên tố của N (thường N được tạo thành từ 2 số nguyên tố 1024 bit). - Hướng dẫn: N ở đây chỉ có 150 bit nên có thể phân tích dễ dàng bằng tool [factordb](https://factordb.com/index.php) ![Screenshot 2025-10-07 142208](https://hackmd.io/_uploads/Hkx2kHGTlx.png) :::spoiler Flag 19704762736204164635843 ::: ### Inferius Prime ![Screenshot 2025-10-07 142735](https://hackmd.io/_uploads/S1YeZSz6lx.png) - Mô tả: challenge này nói rằng N là một số nguyên 1600 bit. - Hướng dẫn: ta mở file `inferius.py` và `output.txt` kiểm tra thử ```py= #!/usr/bin/env python3 from Crypto.Util.number import getPrime, inverse, bytes_to_long, long_to_bytes, GCD e = 0x10001 # n will be 8 * (100 + 100) = 1600 bits strong (I think?) which is pretty good p = getPrime(100) q = getPrime(100) phi = (p - 1) * (q - 1) d = inverse(e, phi) n = p * q FLAG = b"crypto{???????????????}" pt = bytes_to_long(FLAG) ct = pow(pt, e, n) print(f"n = {n}") print(f"e = {e}") print(f"ct = {ct}") pt = pow(ct, d, n) decrypted = long_to_bytes(pt) assert decrypted == FLAG ``` - Chú ý rằng hàm `getPrime(k)` sẽ trả về một số nguyên tố có k bit, mà hai số k bit nhân với nhau sẽ thu được số nguyên có 2k bit hoặc 2k - 1 bit, vì vậy N sẽ chỉ có tối đa 200 bit, việc phân tích thừa số nguyên tố của nó rất dễ. - Source code giải: ```py= from Crypto.Util.number import long_to_bytes n = 984994081290620368062168960884976209711107645166770780785733 e = 65537 ct = 948553474947320504624302879933619818331484350431616834086273 p = 848445505077945374527983649411 q = 1160939713152385063689030212503 phi = (p-1)*(q-1) d = pow(e, -1, phi) m = pow(ct, d, n) print(long_to_bytes(m)) ``` :::spoiler Flag crypto{N33d_b1g_pR1m35} ::: ### Monoprime ![Screenshot 2025-10-07 144352](https://hackmd.io/_uploads/rJC6Erzpee.png) - Mô tả: Mọi người đều sử dụng 2 số nguyên tố để tính N, tại sao không dùng 1? - Huớng dẫn: Nếu N chỉ được tạo thành từ 1 số nguyên tố, ta có thể dễ dàng tính $\varphi(n) = n - 1$. - Source code giải: ```py= from Crypto.Util.number import long_to_bytes n = 171731371218065444125482536302245915415603318380280392385291836472299752747934607246477508507827284075763910264995326010251268493630501989810855418416643352631102434317900028697993224868629935657273062472544675693365930943308086634291936846505861203914449338007760990051788980485462592823446469606824421932591 e = 65537 ct = 161367550346730604451454756189028938964941280347662098798775466019463375610700074840105776873791605070092554650190486030367121011578171525759600774739890458414593857709994072516290998135846956596662071379067305011746842247628316996977338024343628757374524136260758515864509435302781735938531030576289086798942 phi = n - 1 d = pow(e, -1, phi) m = pow(ct, d, n) print(long_to_bytes(m)) ``` :::spoiler Flag crypto{0n3_pr1m3_41n7_pr1m3_l0l} ::: ### Square Eyes ![Screenshot 2025-10-07 144908](https://hackmd.io/_uploads/r1DUUrMagx.png) - Mô tả: challenge tạo ra một số nguyên tố 1024 sau đó nhân chính nó để tính N. - Hướng dẫn: vì $N = p^{2}$ nên $\varphi(N) = N . (1 - 1/p) = p^2.(1-1/p) = p^2 - p.$ (có thể tính p bằng hàm iroot trong thư viện gmpy2) - Source code giải: ```py= from Crypto.Util.number import long_to_bytes from gmpy2 import iroot n = 535860808044009550029177135708168016201451343147313565371014459027743491739422885443084705720731409713775527993719682583669164873806842043288439828071789970694759080842162253955259590552283047728782812946845160334801782088068154453021936721710269050985805054692096738777321796153384024897615594493453068138341203673749514094546000253631902991617197847584519694152122765406982133526594928685232381934742152195861380221224370858128736975959176861651044370378539093990198336298572944512738570839396588590096813217791191895941380464803377602779240663133834952329316862399581950590588006371221334128215409197603236942597674756728212232134056562716399155080108881105952768189193728827484667349378091100068224404684701674782399200373192433062767622841264055426035349769018117299620554803902490432339600566432246795818167460916180647394169157647245603555692735630862148715428791242764799469896924753470539857080767170052783918273180304835318388177089674231640910337743789750979216202573226794240332797892868276309400253925932223895530714169648116569013581643192341931800785254715083294526325980247219218364118877864892068185905587410977152737936310734712276956663192182487672474651103240004173381041237906849437490609652395748868434296753449 e = 65537 ct = 222502885974182429500948389840563415291534726891354573907329512556439632810921927905220486727807436668035929302442754225952786602492250448020341217733646472982286222338860566076161977786095675944552232391481278782019346283900959677167026636830252067048759720251671811058647569724495547940966885025629807079171218371644528053562232396674283745310132242492367274184667845174514466834132589971388067076980563188513333661165819462428837210575342101036356974189393390097403614434491507672459254969638032776897417674577487775755539964915035731988499983726435005007850876000232292458554577437739427313453671492956668188219600633325930981748162455965093222648173134777571527681591366164711307355510889316052064146089646772869610726671696699221157985834325663661400034831442431209123478778078255846830522226390964119818784903330200488705212765569163495571851459355520398928214206285080883954881888668509262455490889283862560453598662919522224935145694435885396500780651530829377030371611921181207362217397805303962112100190783763061909945889717878397740711340114311597934724670601992737526668932871436226135393872881664511222789565256059138002651403875484920711316522536260604255269532161594824301047729082877262812899724246757871448545439896 p = iroot(n, 2)[0] phi = p**2 - p d = pow(e, -1, phi) m = pow(ct, d, n) print(long_to_bytes(m)) ``` :::spoiler Flag crypto{squar3_r00t_i5_f4st3r_th4n_f4ct0r1ng!} ::: ### Manyprime ![image](https://hackmd.io/_uploads/S1rEOSG6el.png) - Mô tả: N trong challenge này được tạo thành từ 30 số nguyên tố - Hướng dẫn: sử dụng hàm factor trong sage để phân tích N: ![Screenshot 2025-10-07 151423](https://hackmd.io/_uploads/B1foTSGaee.png) - Source code giải: ```py= from Crypto.Util.number import long_to_bytes n = 580642391898843192929563856870897799650883152718761762932292482252152591279871421569162037190419036435041797739880389529593674485555792234900969402019055601781662044515999210032698275981631376651117318677368742867687180140048715627160641771118040372573575479330830092989800730105573700557717146251860588802509310534792310748898504394966263819959963273509119791037525504422606634640173277598774814099540555569257179715908642917355365791447508751401889724095964924513196281345665480688029639999472649549163147599540142367575413885729653166517595719991872223011969856259344396899748662101941230745601719730556631637 e = 65537 ct = 320721490534624434149993723527322977960556510750628354856260732098109692581338409999983376131354918370047625150454728718467998870322344980985635149656977787964380651868131740312053755501594999166365821315043312308622388016666802478485476059625888033017198083472976011719998333985531756978678758897472845358167730221506573817798467100023754709109274265835201757369829744113233607359526441007577850111228850004361838028842815813724076511058179239339760639518034583306154826603816927757236549096339501503316601078891287408682099750164720032975016814187899399273719181407940397071512493967454225665490162619270814464 primes = [9282105380008121879, 9303850685953812323, 9389357739583927789, 10336650220878499841, 10638241655447339831, 11282698189561966721, 11328768673634243077, 11403460639036243901, 11473665579512371723, 11492065299277279799, 11530534813954192171, 11665347949879312361, 12132158321859677597, 12834461276877415051, 12955403765595949597, 12973972336777979701, 13099895578757581201, 13572286589428162097, 14100640260554622013, 14178869592193599187, 14278240802299816541, 14523070016044624039, 14963354250199553339, 15364597561881860737, 15669758663523555763, 15824122791679574573, 15998365463074268941, 16656402470578844539, 16898740504023346457, 17138336856793050757, 17174065872156629921, 17281246625998849649] phi = 1 for p in primes: phi *= p - 1 d = pow(e, -1, phi) m = pow(ct, d, n) print(long_to_bytes(m)) ``` :::spoiler Flag crypto{700_m4ny_5m4ll_f4c70r5} ::: ## Public exponent ### Salty ![image](https://hackmd.io/_uploads/SyKpRrf6ll.png) - Mô tả: chall sử dụng e nhỏ, ta có thể tìm ra lỗ hỏng từ đây - Hướng dẫn: xem file `salty.py` thì nhận thấy rằng e = 1 ```py= from Crypto.Util.number import getPrime, inverse, bytes_to_long, long_to_bytes e = 1 d = -1 while d == -1: p = getPrime(512) q = getPrime(512) phi = (p - 1) * (q - 1) d = inverse(e, phi) n = p * q flag = b"XXXXXXXXXXXXXXXXXXXXXXX" pt = bytes_to_long(flag) ct = pow(pt, e, n) print(f"n = {n}") print(f"e = {e}") print(f"ct = {ct}") pt = pow(ct, d, n) decrypted = long_to_bytes(pt) assert decrypted == flag print(d) ``` - Ta có $C \equiv M^e \pmod N$, e = 1 nên $C \equiv M \pmod N$. Mà C nhỏ hơn N nên C = M. - Source code giải: ```py= from Crypto.Util.number import long_to_bytes n = 110581795715958566206600392161360212579669637391437097703685154237017351570464767725324182051199901920318211290404777259728923614917211291562555864753005179326101890427669819834642007924406862482343614488768256951616086287044725034412802176312273081322195866046098595306261781788276570920467840172004530873767 e = 1 ct = 44981230718212183604274785925793145442655465025264554046028251311164494127485 pt = ct print(long_to_bytes(pt)) ``` :::spoiler Flag crypto{saltstack_fell_for_this!} ::: ### Modulus Inutilis ![image](https://hackmd.io/_uploads/SyfrU8M6xe.png) - Mô tả: chall dùng e khá nhỏ, ta có thể dùng dùng kiểu attack on small public exponent - Hướng dẫn: $C \equiv M^e \pmod N$, vì e nhỏ nên $M^e$ mod N vẫn = $M^e$ => $M = \sqrt[e]{C}$ - Source code giải: ```py= from Crypto.Util.number import long_to_bytes from gmpy2 import iroot n = 17258212916191948536348548470938004244269544560039009244721959293554822498047075403658429865201816363311805874117705688359853941515579440852166618074161313773416434156467811969628473425365608002907061241714688204565170146117869742910273064909154666642642308154422770994836108669814632309362483307560217924183202838588431342622551598499747369771295105890359290073146330677383341121242366368309126850094371525078749496850520075015636716490087482193603562501577348571256210991732071282478547626856068209192987351212490642903450263288650415552403935705444809043563866466823492258216747445926536608548665086042098252335883 e = 3 ct = 243251053617903760309941844835411292373350655973075480264001352919865180151222189820473358411037759381328642957324889519192337152355302808400638052620580409813222660643570085177957 print(long_to_bytes(iroot(ct, 3)[0])) ``` :::spoiler Flag crypto{N33d_m04R_p4dd1ng} ::: ### Everything is Big ![Screenshot 2025-10-07 160915](https://hackmd.io/_uploads/ByC4YIz6xx.png) ```py= #!/usr/bin/env python3 from Crypto.Util.number import getPrime, bytes_to_long FLAG = b"crypto{?????????????????????????}" m = bytes_to_long(FLAG) def get_huge_RSA(): p = getPrime(1024) q = getPrime(1024) N = p*q phi = (p-1)*(q-1) while True: d = getPrime(256) e = pow(d,-1,phi) if e.bit_length() == N.bit_length(): break return N,e N, e = get_huge_RSA() c = pow(m, e, N) print(f'N = {hex(N)}') print(f'e = {hex(e)}') print(f'c = {hex(c)}') ``` - Mô tả: chall dùng d khá nhỏ. Cụ thể $N = 2048$ bit, còn $d = 256$ bit, do đó thỏa điều kiện $d < \frac {N^{\frac{1}{4}}} {3}$. Đây là đặc trưng của Wiener’s attack - Hướng dẫn: mình sẽ sử dụng thư viện có sẵn để giải, có thể cài bằng lệnh `curl -O https://raw.githubusercontent.com/orisano/owiener/master/owiener.py` - Source code giải: ```py= import owiener from Crypto.Util.number import * N = 0xb8af3d3afb893a602de4afe2a29d7615075d1e570f8bad8ebbe9b5b9076594cf06b6e7b30905b6420e950043380ea746f0a14dae34469aa723e946e484a58bcd92d1039105871ffd63ffe64534b7d7f8d84b4a569723f7a833e6daf5e182d658655f739a4e37bd9f4a44aff6ca0255cda5313c3048f56eed5b21dc8d88bf5a8f8379eac83d8523e484fa6ae8dbcb239e65d3777829a6903d779cd2498b255fcf275e5f49471f35992435ee7cade98c8e82a8beb5ce1749349caa16759afc4e799edb12d299374d748a9e3c82e1cc983cdf9daec0a2739dadcc0982c1e7e492139cbff18c5d44529407edfd8e75743d2f51ce2b58573fea6fbd4fe25154b9964d e = 0x9ab58dbc8049b574c361573955f08ea69f97ecf37400f9626d8f5ac55ca087165ce5e1f459ef6fa5f158cc8e75cb400a7473e89dd38922ead221b33bc33d6d716fb0e4e127b0fc18a197daf856a7062b49fba7a86e3a138956af04f481b7a7d481994aeebc2672e500f3f6d8c581268c2cfad4845158f79c2ef28f242f4fa8f6e573b8723a752d96169c9d885ada59cdeb6dbe932de86a019a7e8fc8aeb07748cfb272bd36d94fe83351252187c2e0bc58bb7a0a0af154b63397e6c68af4314601e29b07caed301b6831cf34caa579eb42a8c8bf69898d04b495174b5d7de0f20cf2b8fc55ed35c6ad157d3e7009f16d6b61786ee40583850e67af13e9d25be3 c = 0x3f984ff5244f1836ed69361f29905ca1ae6b3dcf249133c398d7762f5e277919174694293989144c9d25e940d2f66058b2289c75d1b8d0729f9a7c4564404a5fd4313675f85f31b47156068878e236c5635156b0fa21e24346c2041ae42423078577a1413f41375a4d49296ab17910ae214b45155c4570f95ca874ccae9fa80433a1ab453cbb28d780c2f1f4dc7071c93aff3924d76c5b4068a0371dff82531313f281a8acadaa2bd5078d3ddcefcb981f37ff9b8b14c7d9bf1accffe7857160982a2c7d9ee01d3e82265eec9c7401ecc7f02581fd0d912684f42d1b71df87a1ca51515aab4e58fab4da96e154ea6cdfb573a71d81b2ea4a080a1066e1bc3474 d = owiener.attack(e, N) m = pow(c, d, N) print(long_to_bytes(m)) ``` :::spoiler Flag crypto{s0m3th1ng5_c4n_b3_t00_b1g} ::: ### Crossed Wires ![Screenshot 2025-10-07 163600](https://hackmd.io/_uploads/B1YrewMalg.png) - Mô tả: đơn giản là những người bạn của bạn thay vì dùng chung e với bạn thì mỗi người lại dùng mỗi e khác nhau - source: ```py= from Crypto.Util.number import getPrime, long_to_bytes, bytes_to_long, inverse import math from gmpy2 import next_prime FLAG = b"crypto{????????????????????????????????????????????????}" p = getPrime(1024) q = getPrime(1024) N = p*q phi = (p-1)*(q-1) e = 0x10001 d = inverse(e, phi) my_key = (N, d) friends = 5 friend_keys = [(N, getPrime(17)) for _ in range(friends)] cipher = bytes_to_long(FLAG) for key in friend_keys: cipher = pow(cipher, key[1], key[0]) print(f"My private key: {my_key}") print(f"My Friend's public keys: {friend_keys}") print(f"Encrypted flag: {cipher}") ``` - Hướng dẫn: ta thấy rằng $C_{1} \equiv Flag^{e_{1}} \pmod N$, $C_{2} \equiv C_{1}^{e_{2}} \pmod N$, $C_{3} \equiv C_{2}^{e_{3}} \pmod N$, $C_{4} \equiv C_{3}^{e_{4}} \pmod N$, $C_{5} \equiv C_{4}^{e_{5}} \pmod N$ nên $C_{5} \equiv Flag^{e_{1}e_{2}e_{3}e_{4}e_{5}} \pmod N$ - Ta đã có được các e, d, $C_{5}$ và N trong file `output.txt` ``` My private key: (21711308225346315542706844618441565741046498277716979943478360598053144971379956916575370343448988601905854572029635846626259487297950305231661109855854947494209135205589258643517961521594924368498672064293208230802441077390193682958095111922082677813175804775628884377724377647428385841831277059274172982280545237765559969228707506857561215268491024097063920337721783673060530181637161577401589126558556182546896783307370517275046522704047385786111489447064794210010802761708615907245523492585896286374996088089317826162798278528296206977900274431829829206103227171839270887476436899494428371323874689055690729986771, 2734411677251148030723138005716109733838866545375527602018255159319631026653190783670493107936401603981429171880504360560494771017246468702902647370954220312452541342858747590576273775107870450853533717116684326976263006435733382045807971890762018747729574021057430331778033982359184838159747331236538501849965329264774927607570410347019418407451937875684373454982306923178403161216817237890962651214718831954215200637651103907209347900857824722653217179548148145687181377220544864521808230122730967452981435355334932104265488075777638608041325256776275200067541533022527964743478554948792578057708522350812154888097) My Friend's public keys: [(21711308225346315542706844618441565741046498277716979943478360598053144971379956916575370343448988601905854572029635846626259487297950305231661109855854947494209135205589258643517961521594924368498672064293208230802441077390193682958095111922082677813175804775628884377724377647428385841831277059274172982280545237765559969228707506857561215268491024097063920337721783673060530181637161577401589126558556182546896783307370517275046522704047385786111489447064794210010802761708615907245523492585896286374996088089317826162798278528296206977900274431829829206103227171839270887476436899494428371323874689055690729986771, 106979), (21711308225346315542706844618441565741046498277716979943478360598053144971379956916575370343448988601905854572029635846626259487297950305231661109855854947494209135205589258643517961521594924368498672064293208230802441077390193682958095111922082677813175804775628884377724377647428385841831277059274172982280545237765559969228707506857561215268491024097063920337721783673060530181637161577401589126558556182546896783307370517275046522704047385786111489447064794210010802761708615907245523492585896286374996088089317826162798278528296206977900274431829829206103227171839270887476436899494428371323874689055690729986771, 108533), (21711308225346315542706844618441565741046498277716979943478360598053144971379956916575370343448988601905854572029635846626259487297950305231661109855854947494209135205589258643517961521594924368498672064293208230802441077390193682958095111922082677813175804775628884377724377647428385841831277059274172982280545237765559969228707506857561215268491024097063920337721783673060530181637161577401589126558556182546896783307370517275046522704047385786111489447064794210010802761708615907245523492585896286374996088089317826162798278528296206977900274431829829206103227171839270887476436899494428371323874689055690729986771, 69557), (21711308225346315542706844618441565741046498277716979943478360598053144971379956916575370343448988601905854572029635846626259487297950305231661109855854947494209135205589258643517961521594924368498672064293208230802441077390193682958095111922082677813175804775628884377724377647428385841831277059274172982280545237765559969228707506857561215268491024097063920337721783673060530181637161577401589126558556182546896783307370517275046522704047385786111489447064794210010802761708615907245523492585896286374996088089317826162798278528296206977900274431829829206103227171839270887476436899494428371323874689055690729986771, 97117), (21711308225346315542706844618441565741046498277716979943478360598053144971379956916575370343448988601905854572029635846626259487297950305231661109855854947494209135205589258643517961521594924368498672064293208230802441077390193682958095111922082677813175804775628884377724377647428385841831277059274172982280545237765559969228707506857561215268491024097063920337721783673060530181637161577401589126558556182546896783307370517275046522704047385786111489447064794210010802761708615907245523492585896286374996088089317826162798278528296206977900274431829829206103227171839270887476436899494428371323874689055690729986771, 103231)] Encrypted flag: 20304610279578186738172766224224793119885071262464464448863461184092225736054747976985179673905441502689126216282897704508745403799054734121583968853999791604281615154100736259131453424385364324630229671185343778172807262640709301838274824603101692485662726226902121105591137437331463201881264245562214012160875177167442010952439360623396658974413900469093836794752270399520074596329058725874834082188697377597949405779039139194196065364426213208345461407030771089787529200057105746584493554722790592530472869581310117300343461207750821737840042745530876391793484035024644475535353227851321505537398888106855012746117 ``` - Vậy ta chỉ cần tính $\varphi(N)$, Từ d, e ta sẽ brute-force tìm được $\varphi(N)$ bằng kiểu tấn công As an internal attacker - Source code giải: ```py= from gmpy2 import iroot from Crypto.Util.number import long_to_bytes n = 21711308225346315542706844618441565741046498277716979943478360598053144971379956916575370343448988601905854572029635846626259487297950305231661109855854947494209135205589258643517961521594924368498672064293208230802441077390193682958095111922082677813175804775628884377724377647428385841831277059274172982280545237765559969228707506857561215268491024097063920337721783673060530181637161577401589126558556182546896783307370517275046522704047385786111489447064794210010802761708615907245523492585896286374996088089317826162798278528296206977900274431829829206103227171839270887476436899494428371323874689055690729986771 e = 0x10001 d = 2734411677251148030723138005716109733838866545375527602018255159319631026653190783670493107936401603981429171880504360560494771017246468702902647370954220312452541342858747590576273775107870450853533717116684326976263006435733382045807971890762018747729574021057430331778033982359184838159747331236538501849965329264774927607570410347019418407451937875684373454982306923178403161216817237890962651214718831954215200637651103907209347900857824722653217179548148145687181377220544864521808230122730967452981435355334932104265488075777638608041325256776275200067541533022527964743478554948792578057708522350812154888097 public_keys = [106979, 108533, 69557, 97117, 103231] encrypted_flag = 20304610279578186738172766224224793119885071262464464448863461184092225736054747976985179673905441502689126216282897704508745403799054734121583968853999791604281615154100736259131453424385364324630229671185343778172807262640709301838274824603101692485662726226902121105591137437331463201881264245562214012160875177167442010952439360623396658974413900469093836794752270399520074596329058725874834082188697377597949405779039139194196065364426213208345461407030771089787529200057105746584493554722790592530472869581310117300343461207750821737840042745530876391793484035024644475535353227851321505537398888106855012746117 k = (e*d - 1) // n while True: phi = (e*d - 1) // k if k*phi == e*d - 1 : break k += 1 flag = encrypted_flag for i in range(len(public_keys)): secret_key_of_my_friends = pow(public_keys[i], -1, phi) flag = pow(flag, secret_key_of_my_friends, n) print(long_to_bytes(flag)) ``` :::spoiler Flag crypto{3ncrypt_y0ur_s3cr3t_w1th_y0ur_fr1end5_publ1c_k3y} ::: - Fun fact: bài này lúc mới làm thì mình không biết brute-force tìm $\varphi(N)$ như thế nào, cứ nghĩ đơn giản là $d.e \equiv 1 \pmod {\varphi(N)}$ thì $\varphi(N) = d.e - 1$, xong mình tính ra được flag luôn??? ```py= from gmpy2 import iroot from Crypto.Util.number import long_to_bytes n = 21711308225346315542706844618441565741046498277716979943478360598053144971379956916575370343448988601905854572029635846626259487297950305231661109855854947494209135205589258643517961521594924368498672064293208230802441077390193682958095111922082677813175804775628884377724377647428385841831277059274172982280545237765559969228707506857561215268491024097063920337721783673060530181637161577401589126558556182546896783307370517275046522704047385786111489447064794210010802761708615907245523492585896286374996088089317826162798278528296206977900274431829829206103227171839270887476436899494428371323874689055690729986771 e = 0x10001 d = 2734411677251148030723138005716109733838866545375527602018255159319631026653190783670493107936401603981429171880504360560494771017246468702902647370954220312452541342858747590576273775107870450853533717116684326976263006435733382045807971890762018747729574021057430331778033982359184838159747331236538501849965329264774927607570410347019418407451937875684373454982306923178403161216817237890962651214718831954215200637651103907209347900857824722653217179548148145687181377220544864521808230122730967452981435355334932104265488075777638608041325256776275200067541533022527964743478554948792578057708522350812154888097 public_keys = [106979, 108533, 69557, 97117, 103231] encrypted_flag = 20304610279578186738172766224224793119885071262464464448863461184092225736054747976985179673905441502689126216282897704508745403799054734121583968853999791604281615154100736259131453424385364324630229671185343778172807262640709301838274824603101692485662726226902121105591137437331463201881264245562214012160875177167442010952439360623396658974413900469093836794752270399520074596329058725874834082188697377597949405779039139194196065364426213208345461407030771089787529200057105746584493554722790592530472869581310117300343461207750821737840042745530876391793484035024644475535353227851321505537398888106855012746117 phi = e*d - 1 flag = encrypted_flag for i in range(len(public_keys)): secret_key_of_my_friends = pow(public_keys[i], -1, phi) flag = pow(flag, secret_key_of_my_friends, n) print(long_to_bytes(flag)) ``` - Qua challenge này mình nhận ra rằng việc tính $d$ bằng một bội số của $\varphi(N)$ vẫn hợp lệ - Chứng minh: giả sử $T$ là bội của $\varphi(N)$, => $T = j.\varphi(N)$, $d \equiv e^{-1} \pmod {T}$ <=> $d.e = 1 + k.T = 1 + k.j.\varphi(N)$. $M \equiv C^d \pmod N => M \equiv (M^e)^d \pmod N$. $(M^e)^d \pmod N$ = $M^{1 + k.j.\varphi(N)} \pmod N = M \pmod N$ (theo định lý Euler). ### Everything is Still Big ![image](https://hackmd.io/_uploads/S1n2l676le.png) - Mô tả: e trong challenge này vẫn rất lớn, mình nghĩ ngay đến Wiener's attack nhưng tác giả đã cẩn thận chọn d lớn. - Hướng dẫn: Về mặt lý thuyết, để Wiener's attack được thì $d < \frac{1}{3} \sqrt[4]{N}$. Nhưng trong file `source.py`: ```py= while True: d = getrandbits(512) if (3*d)**4 > N and gcd(d,phi) == 1: e = inverse(d, phi) break ``` - $(3d)^4 > N$ <=> $d > \frac{1}{3} \sqrt[4]{N}$. Có lẻ là không dùng Wiener's attack được. Nhưng mình vẫn thử tool được code sẵn và kết quả là vẫn dùng được - Source code giải: ```py= from Crypto.Util.number import long_to_bytes import owiener N = 0xb12746657c720a434861e9a4828b3c89a6b8d4a1bd921054e48d47124dbcc9cfcdcc39261c5e93817c167db818081613f57729e0039875c72a5ae1f0bc5ef7c933880c2ad528adbc9b1430003a491e460917b34c4590977df47772fab1ee0ab251f94065ab3004893fe1b2958008848b0124f22c4e75f60ed3889fb62e5ef4dcc247a3d6e23072641e62566cd96ee8114b227b8f498f9a578fc6f687d07acdbb523b6029c5bbeecd5efaf4c4d35304e5e6b5b95db0e89299529eb953f52ca3247d4cd03a15939e7d638b168fd00a1cb5b0cc5c2cc98175c1ad0b959c2ab2f17f917c0ccee8c3fe589b4cb441e817f75e575fc96a4fe7bfea897f57692b050d2b e = 0x9d0637faa46281b533e83cc37e1cf5626bd33f712cc1948622f10ec26f766fb37b9cd6c7a6e4b2c03bce0dd70d5a3a28b6b0c941d8792bc6a870568790ebcd30f40277af59e0fd3141e272c48f8e33592965997c7d93006c27bf3a2b8fb71831dfa939c0ba2c7569dd1b660efc6c8966e674fbe6e051811d92a802c789d895f356ceec9722d5a7b617d21b8aa42dd6a45de721953939a5a81b8dffc9490acd4f60b0c0475883ff7e2ab50b39b2deeedaefefffc52ae2e03f72756d9b4f7b6bd85b1a6764b31312bc375a2298b78b0263d492205d2a5aa7a227abaf41ab4ea8ce0e75728a5177fe90ace36fdc5dba53317bbf90e60a6f2311bb333bf55ba3245f c = 0xa3bce6e2e677d7855a1a7819eb1879779d1e1eefa21a1a6e205c8b46fdc020a2487fdd07dbae99274204fadda2ba69af73627bdddcb2c403118f507bca03cb0bad7a8cd03f70defc31fa904d71230aab98a10e155bf207da1b1cac1503f48cab3758024cc6e62afe99767e9e4c151b75f60d8f7989c152fdf4ff4b95ceed9a7065f38c68dee4dd0da503650d3246d463f504b36e1d6fafabb35d2390ecf0419b2bb67c4c647fb38511b34eb494d9289c872203fa70f4084d2fa2367a63a8881b74cc38730ad7584328de6a7d92e4ca18098a15119baee91237cea24975bdfc19bdbce7c1559899a88125935584cd37c8dd31f3f2b4517eefae84e7e588344fa5 d = owiener.attack(e, N) m = pow(c, d, N) flag = long_to_bytes(m) print(flag) ``` - Mình không hiểu tại sao, nên đã đi đọc cách họ code: ```py= """ The MIT License (MIT) Copyright (c) 2019 Nao Yonashiro Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions: The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software. THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. """ from typing import Tuple, Iterator, Iterable, Optional def isqrt(n: int) -> int: """ ref: https://en.wikipedia.org/wiki/Integer_square_root >>> isqrt(289) 17 >>> isqrt(2) 1 >>> isqrt(1000000 ** 2) 1000000 """ if n == 0: return 0 # ref: https://en.wikipedia.org/wiki/Methods_of_computing_square_roots#Rough_estimation x = 2 ** ((n.bit_length() + 1) // 2) while True: y = (x + n // x) // 2 if y >= x: return x x = y def is_perfect_square(n: int) -> bool: """ ref: https://hnw.hatenablog.com/entry/20140503 >>> is_perfect_square(100) True >>> is_perfect_square(2000000000000000000000000000 ** 2) True >>> is_perfect_square(2000000000000000000000000000 ** 2 + 1) False """ sq_mod256 = (1,1,0,0,1,0,0,0,0,1,0,0,0,0,0,0,1,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,1,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,1,1,0,0,1,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,1,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,1,0,0,0,0,1,0,0,0,0,0,0,1,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,1,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,1,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,1,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0) if sq_mod256[n & 0xff] == 0: return False mt = ( (9, (1,1,0,0,1,0,0,1,0)), (5, (1,1,0,0,1)), (7, (1,1,1,0,1,0,0)), (13, (1,1,0,1,1,0,0,0,0,1,1,0,1)), (17, (1,1,1,0,1,0,0,0,1,1,0,0,0,1,0,1,1)) ) a = n % (9 * 5 * 7 * 13 * 17) if any(t[a % m] == 0 for m, t in mt): return False return isqrt(n) ** 2 == n def rational_to_contfrac(x: int, y: int) -> Iterator[int]: """ ref: https://en.wikipedia.org/wiki/Euclidean_algorithm#Continued_fractions >>> list(rational_to_contfrac(4, 11)) [0, 2, 1, 3] """ while y: a = x // y yield a x, y = y, x - a * y def contfrac_to_rational_iter(contfrac: Iterable[int]) -> Iterator[Tuple[int, int]]: """ ref: https://www.cits.ruhr-uni-bochum.de/imperia/md/content/may/krypto2ss08/shortsecretexponents.pdf (6) """ n0, d0 = 0, 1 n1, d1 = 1, 0 for q in contfrac: n = q * n1 + n0 d = q * d1 + d0 yield n, d n0, d0 = n1, d1 n1, d1 = n, d def convergents_from_contfrac(contfrac: Iterable[int]) -> Iterator[Tuple[int, int]]: """ ref: https://www.cits.ruhr-uni-bochum.de/imperia/md/content/may/krypto2ss08/shortsecretexponents.pdf Section.3 """ n_, d_ = 1, 0 for i, (n, d) in enumerate(contfrac_to_rational_iter(contfrac)): if i % 2 == 0: yield n + n_, d + d_ else: yield n, d n_, d_ = n, d def attack(e: int, n: int) -> Optional[int]: """ ref: https://www.cits.ruhr-uni-bochum.de/imperia/md/content/may/krypto2ss08/shortsecretexponents.pdf Section.4 >>> attack(2621, 8927) 5 >>> attack(6792605526025, 9449868410449) 569 >>> attack(30749686305802061816334591167284030734478031427751495527922388099381921172620569310945418007467306454160014597828390709770861577479329793948103408489494025272834473555854835044153374978554414416305012267643957838998648651100705446875979573675767605387333733876537528353237076626094553367977134079292593746416875606876735717905892280664538346000950343671655257046364067221469807138232820446015769882472160551840052921930357988334306659120253114790638496480092361951536576427295789429197483597859657977832368912534761100269065509351345050758943674651053419982561094432258103614830448382949765459939698951824447818497599, 109966163992903243770643456296093759130737510333736483352345488643432614201030629970207047930115652268531222079508230987041869779760776072105738457123387124961036111210544028669181361694095594938869077306417325203381820822917059651429857093388618818437282624857927551285811542685269229705594166370426152128895901914709902037365652575730201897361139518816164746228733410283595236405985958414491372301878718635708605256444921222945267625853091126691358833453283744166617463257821375566155675868452032401961727814314481343467702299949407935602389342183536222842556906657001984320973035314726867840698884052182976760066141) 4221909016509078129201801236879446760697885220928506696150646938237440992746683409881141451831939190609743447676525325543963362353923989076199470515758399 """ f_ = rational_to_contfrac(e, n) for k, dg in convergents_from_contfrac(f_): edg = e * dg phi = edg // k x = n - phi + 1 if x % 2 == 0 and is_perfect_square((x // 2) ** 2 - n): g = edg - phi * k return dg // g return None ``` - Sau khi đọc [doc](https://www.cits.ruhr-uni-bochum.de/imperia/md/content/may/krypto2ss08/shortsecretexponents.pdf) mà họ đưa, mình đã nhận thấy rằng, cách họ triển khai tính toán convergents (mình không biết nghĩa tiếng việt của từ này là gì =))) của liên phân số $\frac{e}{N}$ rất tối ưu, cụ thể: ```py= def convergents_from_contfrac(contfrac: Iterable[int]) -> Iterator[Tuple[int, int]]: """ ref: https://www.cits.ruhr-uni-bochum.de/imperia/md/content/may/krypto2ss08/shortsecretexponents.pdf Section.3 """ n_, d_ = 1, 0 for i, (n, d) in enumerate(contfrac_to_rational_iter(contfrac)): if i % 2 == 0: yield n + n_, d + d_ else: yield n, d n_, d_ = n, d ``` - Vấn đề của challenge này là $d$ được chọn lớn hơn ngưỡng một chút, điều này có nghĩa là **không còn đảm bảo** rằng $\frac{k}{d}$ là một convergents chính nữa. Nhưng ta vẫn có thể tìm được bằng các intermediate convergents (mình tạm gọi là convergents trung gian). Nếu $\frac{p_{n-1}}{q_{n-1}}$ và $\frac{p_n}{q_n}$ là hai convergents chính liên tiếp, thì các convergents trung gian giữa chúng có dạng: $\frac{p_{n-1} + i \cdot p_n}{q_{n-1} + i \cdot q_n}$ với $i$ là một số nguyên nhỏ (`yield n + n_, d + d_` chính là tính trường hợp khi $i$ = 1). Mình không hiểu về bản chất toán học của điều này, chỉ hiểu nó là vậy thôi. ::: spoiler Flag crypto{bon3h5_4tt4ck_i5_sr0ng3r_th4n_w13n3r5} ::: ### Endless Emails ![Screenshot 2025-10-08 204032](https://hackmd.io/_uploads/S1pxqJEalx.png) - Mô tả: Poor Johan nhận được nhiều messages, trong số đó có flag ta cần tìm. - Source chall: ```py= from Crypto.Util.number import bytes_to_long, getPrime from secret import messages def RSA_encrypt(message): m = bytes_to_long(message) p = getPrime(1024) q = getPrime(1024) N = p * q e = 3 c = pow(m, e, N) return N, e, c for m in messages: N, e, c = RSA_encrypt(m) print(f"n = {N}") print(f"e = {e}") print(f"c = {c}") ``` - Hướng dẫn: vì có nhiều ciphertext dùng chung 1 e => nghĩ ngay đến Hastad's Broadcast attack. Nhưng có 1 vấn đề là ta không biết trong 7 message đó có bao nhiêu message chứa flag ta cần, nên ta phải duyệt qua từng bộ số. Mình sẽ dùng hàm combinations của thư viện itertools để sinh tổ hợp. - Source code giải: ```py= from Crypto.Util.number import * from gmpy2 import iroot import itertools def crt(remainders, mod): x = 0 N = 1 for n in mod: N *= n for a, n in zip(remainders, mod): x += a* inverse(N//n, n) *(N//n) return x % N n_list = [ 14528915758150659907677315938876872514853653132820394367681510019000469589767908107293777996420037715293478868775354645306536953789897501630398061779084810058931494642860729799059325051840331449914529594113593835549493208246333437945551639983056810855435396444978249093419290651847764073607607794045076386643023306458718171574989185213684263628336385268818202054811378810216623440644076846464902798568705083282619513191855087399010760232112434412274701034094429954231366422968991322244343038458681255035356984900384509158858007713047428143658924970374944616430311056440919114824023838380098825914755712289724493770021, 20463913454649855046677206889944639231694511458416906994298079596685813354570085475890888433776403011296145408951323816323011550738170573801417972453504044678801608709931200059967157605416809387753258251914788761202456830940944486915292626560515250805017229876565916349963923702612584484875113691057716315466239062005206014542088484387389725058070917118549621598629964819596412564094627030747720659155558690124005400257685883230881015636066183743516494701900125788836869358634031031172536767950943858472257519195392986989232477630794600444813136409000056443035171453870906346401936687214432176829528484662373633624123, 19402640770593345339726386104915705450969517850985511418263141255686982818547710008822417349818201858549321868878490314025136645036980129976820137486252202687238348587398336652955435182090722844668488842986318211649569593089444781595159045372322540131250208258093613844753021272389255069398553523848975530563989367082896404719544411946864594527708058887475595056033713361893808330341623804367785721774271084389159493974946320359512776328984487126583015777989991635428744050868653379191842998345721260216953918203248167079072442948732000084754225272238189439501737066178901505257566388862947536332343196537495085729147, 12005639978012754274325188681720834222130605634919280945697102906256738419912110187245315232437501890545637047506165123606573171374281507075652554737014979927883759915891863646221205835211640845714836927373844277878562666545230876640830141637371729405545509920889968046268135809999117856968692236742804637929866632908329522087977077849045608566911654234541526643235586433065170392920102840518192803854740398478305598092197183671292154743153130012885747243219372709669879863098708318993844005566984491622761795349455404952285937152423145150066181043576492305166964448141091092142224906843816547235826717179687198833961, 17795451956221451086587651307408104001363221003775928432650752466563818944480119932209305765249625841644339021308118433529490162294175590972336954199870002456682453215153111182451526643055812311071588382409549045943806869173323058059908678022558101041630272658592291327387549001621625757585079662873501990182250368909302040015518454068699267914137675644695523752851229148887052774845777699287718342916530122031495267122700912518207571821367123013164125109174399486158717604851125244356586369921144640969262427220828940652994276084225196272504355264547588369516271460361233556643313911651916709471353368924621122725823, 25252721057733555082592677470459355315816761410478159901637469821096129654501579313856822193168570733800370301193041607236223065376987811309968760580864569059669890823406084313841678888031103461972888346942160731039637326224716901940943571445217827960353637825523862324133203094843228068077462983941899571736153227764822122334838436875488289162659100652956252427378476004164698656662333892963348126931771536472674447932268282205545229907715893139346941832367885319597198474180888087658441880346681594927881517150425610145518942545293750127300041942766820911120196262215703079164895767115681864075574707999253396530263, 19833203629283018227011925157509157967003736370320129764863076831617271290326613531892600790037451229326924414757856123643351635022817441101879725227161178559229328259469472961665857650693413215087493448372860837806619850188734619829580286541292997729705909899738951228555834773273676515143550091710004139734080727392121405772911510746025807070635102249154615454505080376920778703360178295901552323611120184737429513669167641846902598281621408629883487079110172218735807477275590367110861255756289520114719860000347219161944020067099398239199863252349401303744451903546571864062825485984573414652422054433066179558897, ] e = 3 c_list = [ 6965891612987861726975066977377253961837139691220763821370036576350605576485706330714192837336331493653283305241193883593410988132245791554283874785871849223291134571366093850082919285063130119121338290718389659761443563666214229749009468327825320914097376664888912663806925746474243439550004354390822079954583102082178617110721589392875875474288168921403550415531707419931040583019529612270482482718035497554779733578411057633524971870399893851589345476307695799567919550426417015815455141863703835142223300228230547255523815097431420381177861163863791690147876158039619438793849367921927840731088518955045807722225, 5109363605089618816120178319361171115590171352048506021650539639521356666986308721062843132905170261025772850941702085683855336653472949146012700116070022531926476625467538166881085235022484711752960666438445574269179358850309578627747024264968893862296953506803423930414569834210215223172069261612934281834174103316403670168299182121939323001232617718327977313659290755318972603958579000300780685344728301503641583806648227416781898538367971983562236770576174308965929275267929379934367736694110684569576575266348020800723535121638175505282145714117112442582416208209171027273743686645470434557028336357172288865172, 5603386396458228314230975500760833991383866638504216400766044200173576179323437058101562931430558738148852367292802918725271632845889728711316688681080762762324367273332764959495900563756768440309595248691744845766607436966468714038018108912467618638117493367675937079141350328486149333053000366933205635396038539236203203489974033629281145427277222568989469994178084357460160310598260365030056631222346691527861696116334946201074529417984624304973747653407317290664224507485684421999527164122395674469650155851869651072847303136621932989550786722041915603539800197077294166881952724017065404825258494318993054344153, 1522280741383024774933280198410525846833410931417064479278161088248621390305797210285777845359812715909342595804742710152832168365433905718629465545306028275498667935929180318276445229415104842407145880223983428713335709038026249381363564625791656631137936935477777236936508600353416079028339774876425198789629900265348122040413865209592074731028757972968635601695468594123523892918747882221891834598896483393711851510479989203644477972694520237262271530260496342247355761992646827057846109181410462131875377404309983072358313960427035348425800940661373272947647516867525052504539561289941374722179778872627956360577, 8752507806125480063647081749506966428026005464325535765874589376572431101816084498482064083887400646438977437273700004934257274516197148448425455243811009944321764771392044345410680448204581679548854193081394891841223548418812679441816502910830861271884276608891963388657558218620911858230760629700918375750796354647493524576614017731938584618983084762612414591830024113057983483156974095503392359946722756364412399187910604029583464521617256125933111786441852765229820406911991809039519015434793656710199153380699319611499255869045311421603167606551250174746275803467549814529124250122560661739949229005127507540805, 23399624135645767243362438536844425089018405258626828336566973656156553220156563508607371562416462491581383453279478716239823054532476006642583363934314982675152824147243749715830794488268846671670287617324522740126594148159945137948643597981681529145611463534109482209520448640622103718682323158039797577387254265854218727476928164074249568031493984825273382959147078839665114417896463735635546290504843957780546550577300001452747760982468547756427137284830133305010038339400230477403836856663883956463830571934657200851598986174177386323915542033293658596818231793744261192870485152396793393026198817787033127061749, 15239683995712538665992887055453717247160229941400011601942125542239446512492703769284448009141905335544729440961349343533346436084176947090230267995060908954209742736573986319254695570265339469489948102562072983996668361864286444602534666284339466797477805372109723178841788198177337648499899079471221924276590042183382182326518312979109378616306364363630519677884849945606288881683625944365927809405420540525867173639222696027472336981838588256771671910217553150588878434061862840893045763456457939944572192848992333115479951110622066173007227047527992906364658618631373790704267650950755276227747600169403361509144, ] k = len(c_list) while k >= e: comb = itertools.combinations(range(7), k) for i in comb: r = [c_list[j] for j in i] mod = [n_list[j] for j in i] m_pow_e = crt(r, mod) if iroot(m_pow_e, e)[1] == True: print(long_to_bytes(iroot(m_pow_e, e)[0])) exit(0) k -= 1 ``` ::: spoiler Flag crypto{1f_y0u_d0nt_p4d_y0u_4r3_Vuln3rabl3} ::: ## Primes Part 2 ### Infinite Descent ![image](https://hackmd.io/_uploads/SygHOh4Tgl.png) - `descent.py`: ```py= import random from Crypto.Util.number import bytes_to_long, isPrime from gmpy2 import iroot FLAG = b"crypto{???????????????????}" def getPrimes(bitsize): r = random.getrandbits(bitsize) p, q = r, r while not isPrime(p): p += random.getrandbits(bitsize//4) while not isPrime(q): q += random.getrandbits(bitsize//8) return p, q m = bytes_to_long(FLAG) p, q = getPrimes(2048) print(p, q) n = p * q e = 0x10001 c = pow(m, e, n) print(f"n = {n}") print(f"e = {e}") print(f"c = {c}") print(abs(p - q) - iroot(n, 4)[0]) ``` - Mô tả: chall tự sinh ra 2 số nguyên tố có độ dài 2048 bit, nhưng lại không sinh random mà tự sinh bằng hàm `getPrimes()` - Hướng dẫn: tập trung vào hàm `getPrimes()`: ```py= def getPrimes(bitsize): r = random.getrandbits(bitsize) p, q = r, r while not isPrime(p): p += random.getrandbits(bitsize//4) while not isPrime(q): q += random.getrandbits(bitsize//8) return p, q ``` - p, q đều xuất phát từ `r`, và mỗi bước p đều tăng lên 1 khoảng = `random.getrandbits(bitsize//4)` tức là nó sẽ tự cộng vào bản thân nó 1 số có độ dài 2048/4 = 512 bit, còn `q` thì mỗi bước tăng lên 1 khoảng = 256 bit. Do đó `p` và `q` sẽ rất gần nhau vì nó đều xuất phát từ 1 số và chỉ tăng lên một khoảng rất nhỏ so với độ lớn của nó => nghĩ ngay đến Fermat attack vì lúc này `p, q` rất gần nhau - `solve.py`: ```py= import math from gmpy2 import iroot from Crypto.Util.number import long_to_bytes, inverse def fermat_attack(n): x = math.isqrt(n) y = x*x - n while y < 0 or iroot(y, 2)[1] == False: x += 1 y = x*x - n return x + math.isqrt(y), x - math.isqrt(y) n = 383347712330877040452238619329524841763392526146840572232926924642094891453979246383798913394114305368360426867021623649667024217266529000859703542590316063318592391925062014229671423777796679798747131250552455356061834719512365575593221216339005132464338847195248627639623487124025890693416305788160905762011825079336880567461033322240015771102929696350161937950387427696385850443727777996483584464610046380722736790790188061964311222153985614287276995741553706506834906746892708903948496564047090014307484054609862129530262108669567834726352078060081889712109412073731026030466300060341737504223822014714056413752165841749368159510588178604096191956750941078391415634472219765129561622344109769892244712668402761549412177892054051266761597330660545704317210567759828757156904778495608968785747998059857467440128156068391746919684258227682866083662345263659558066864109212457286114506228470930775092735385388316268663664139056183180238043386636254075940621543717531670995823417070666005930452836389812129462051771646048498397195157405386923446893886593048680984896989809135802276892911038588008701926729269812453226891776546037663583893625479252643042517196958990266376741676514631089466493864064316127648074609662749196545969926051 e = 65537 c = 98280456757136766244944891987028935843441533415613592591358482906016439563076150526116369842213103333480506705993633901994107281890187248495507270868621384652207697607019899166492132408348789252555196428608661320671877412710489782358282011364127799563335562917707783563681920786994453004763755404510541574502176243896756839917991848428091594919111448023948527766368304503100650379914153058191140072528095898576018893829830104362124927140555107994114143042266758709328068902664037870075742542194318059191313468675939426810988239079424823495317464035252325521917592045198152643533223015952702649249494753395100973534541766285551891859649320371178562200252228779395393974169736998523394598517174182142007480526603025578004665936854657294541338697513521007818552254811797566860763442604365744596444735991732790926343720102293453429936734206246109968817158815749927063561835274636195149702317415680401987150336994583752062565237605953153790371155918439941193401473271753038180560129784192800351649724465553733201451581525173536731674524145027931923204961274369826379325051601238308635192540223484055096203293400419816024111797903442864181965959247745006822690967920957905188441550106930799896292835287867403979631824085790047851383294389 p, q = fermat_attack(n) print(long_to_bytes(pow(c, inverse(e, (p-1)*(q-1)), n))) ``` :::spoiler Flag crypto{f3rm47_w45_4_g3n1u5} ::: ### Marin's Secrets ![image](https://hackmd.io/_uploads/r1s-JAVpge.png) - `marin.py`: ```py= #!/usr/bin/env python3 import random from Crypto.Util.number import bytes_to_long from secret import secrets, flag def get_prime(secret): prime = 1 for _ in range(secret): prime = prime << 1 return prime - 1 random.shuffle(secrets) m = bytes_to_long(flag) p = get_prime(secrets[0]) q = get_prime(secrets[1]) n = p * q e = 0x10001 c = pow(m, e, n) print(f"n = {n}") print(f"e = {e}") print(f"c = {c}") ``` - Mô tả: p, q trong challenge vẫn được tự sinh trong hàm `get_prime` - Hướng dẫn: quan sát hàm `get_prime`: ```py= def get_prime(secret): prime = 1 for _ in range(secret): prime = prime << 1 return prime - 1 ``` - prime khởi đầu bằng 1, sau đó prime = prime << 1. prime << 1 có nghĩa là dịch tất cả các bit của prime sang trái 1 lần. ví dụ xét số a = 7 = 0b111. a << 1 = 0b111 < 1 = 0b.1110 = 14 (mở rộng: a << b = $a . 2^b$). Vậy sau khi hàm kết thúc, ta sẽ được 1 số nguyên tố có dạng: $2^a - 1$. - `ouput.txt`: ``` n: 658416274830184544125027519921443515789888264156074733099244040126213682497714032798116399288176502462829255784525977722903018714434309698108208388664768262754316426220651576623731617882923164117579624827261244506084274371250277849351631679441171018418018498039996472549893150577189302871520311715179730714312181456245097848491669795997289830612988058523968384808822828370900198489249243399165125219244753790779764466236965135793576516193213175061401667388622228362042717054014679032953441034021506856017081062617572351195418505899388715709795992029559042119783423597324707100694064675909238717573058764118893225111602703838080618565401139902143069901117174204252871948846864436771808616432457102844534843857198735242005309073939051433790946726672234643259349535186268571629077937597838801337973092285608744209951533199868228040004432132597073390363357892379997655878857696334892216345070227646749851381208554044940444182864026513709449823489593439017366358869648168238735087593808344484365136284219725233811605331815007424582890821887260682886632543613109252862114326372077785369292570900594814481097443781269562647303671428895764224084402259605109600363098950091998891375812839523613295667253813978434879172781217285652895469194181218343078754501694746598738215243769747956572555989594598180639098344891175879455994652382137038240166358066403475457 e: 65537 c: 400280463088930432319280359115194977582517363610532464295210669530407870753439127455401384569705425621445943992963380983084917385428631223046908837804126399345875252917090184158440305503817193246288672986488987883177380307377025079266030262650932575205141853413302558460364242355531272967481409414783634558791175827816540767545944534238189079030192843288596934979693517964655661507346729751987928147021620165009965051933278913952899114253301044747587310830419190623282578931589587504555005361571572561916866063458812965314474160499067525067495140150092119620928363007467390920130717521169105167963364154636472055084012592138570354390246779276003156184676298710746583104700516466091034510765027167956117869051938116457370384737440965109619578227422049806566060571831017610877072484262724789571076529586427405780121096546942812322324807145137017942266863534989082115189065560011841150908380937354301243153206428896320576609904361937035263985348984794208198892615898907005955403529470847124269512316191753950203794578656029324506688293446571598506042198219080325747328636232040936761788558421528960279832802127562115852304946867628316502959562274485483867481731149338209009753229463924855930103271197831370982488703456463385914801246828662212622006947380115549529820197355738525329885232170215757585685484402344437894981555179129287164971002033759724456 ``` - n = $p.q$ = $(2^a - 1)(2^b -1)$. vậy tối đa $a = \log_2(n) + 1 = 4485$ => hoàn toàn có thể brute-force a tìm p,q. - `solve.py` ```py= import math from Crypto.Util.number import long_to_bytes, inverse, isPrime n = 658416274830184544125027519921443515789888264156074733099244040126213682497714032798116399288176502462829255784525977722903018714434309698108208388664768262754316426220651576623731617882923164117579624827261244506084274371250277849351631679441171018418018498039996472549893150577189302871520311715179730714312181456245097848491669795997289830612988058523968384808822828370900198489249243399165125219244753790779764466236965135793576516193213175061401667388622228362042717054014679032953441034021506856017081062617572351195418505899388715709795992029559042119783423597324707100694064675909238717573058764118893225111602703838080618565401139902143069901117174204252871948846864436771808616432457102844534843857198735242005309073939051433790946726672234643259349535186268571629077937597838801337973092285608744209951533199868228040004432132597073390363357892379997655878857696334892216345070227646749851381208554044940444182864026513709449823489593439017366358869648168238735087593808344484365136284219725233811605331815007424582890821887260682886632543613109252862114326372077785369292570900594814481097443781269562647303671428895764224084402259605109600363098950091998891375812839523613295667253813978434879172781217285652895469194181218343078754501694746598738215243769747956572555989594598180639098344891175879455994652382137038240166358066403475457 e = 65537 c = 400280463088930432319280359115194977582517363610532464295210669530407870753439127455401384569705425621445943992963380983084917385428631223046908837804126399345875252917090184158440305503817193246288672986488987883177380307377025079266030262650932575205141853413302558460364242355531272967481409414783634558791175827816540767545944534238189079030192843288596934979693517964655661507346729751987928147021620165009965051933278913952899114253301044747587310830419190623282578931589587504555005361571572561916866063458812965314474160499067525067495140150092119620928363007467390920130717521169105167963364154636472055084012592138570354390246779276003156184676298710746583104700516466091034510765027167956117869051938116457370384737440965109619578227422049806566060571831017610877072484262724789571076529586427405780121096546942812322324807145137017942266863534989082115189065560011841150908380937354301243153206428896320576609904361937035263985348984794208198892615898907005955403529470847124269512316191753950203794578656029324506688293446571598506042198219080325747328636232040936761788558421528960279832802127562115852304946867628316502959562274485483867481731149338209009753229463924855930103271197831370982488703456463385914801246828662212622006947380115549529820197355738525329885232170215757585685484402344437894981555179129287164971002033759724456 for a in range(1, int(math.log2(n)) + 2): if n % (2**a - 1) == 0: p = 2**a - 1 q = n // p if isPrime(p) and isPrime(q): break phi = (p-1)*(q-1) print(long_to_bytes(pow(c, inverse(e, phi), n))) ``` :::spoiler Flag crypto{Th3se_Pr1m3s_4r3_t00_r4r3} ::: ### Fast Prime ### Ron was Wrong, Whit is Right ![Screenshot 2025-10-09 133841](https://hackmd.io/_uploads/SkT5OAE6gg.png) - `exerpt.py`: ```py= from Crypto.Cipher import PKCS1_OAEP from Crypto.PublicKey import RSA msg = "???" with open('21.pem') as f: key = RSA.importKey(f.read()) cipher = PKCS1_OAEP.new(key) ciphertext = cipher.encrypt(msg) with open('21.ciphertext', 'w') as f: f.write(ciphertext.hex()) ``` - Mô tả: chall cung cấp cho ta 1 file zip gồm 50 cặp file pem và file ciphertext tương ứng của nó, ta cũng biết rằng flag được mã hóa bằng PKCS1_OAEP và giấu trong file 21.pem. - Hướng dẫn: ta được cung cấp [resources](https://sbseminar.wordpress.com/2012/02/16/the-recent-difficulties-with-rsa/) về việc RSA có thể bị tấn công bằng cách tìm M sao cho gcd(M, N) khác 1 và N, thì lúc này M chính là 1 trong 2 số nguyên tố tạo nên N (vì N là tích của p, q, nên chia hết cho 1, p, q, bội của p, q mà ước chung nhỏ nhất của nó trả về khác 1 thì đó chính là số nguyên tố nhỏ nhất trong p,q) - `solve.py` ```py= import zipfile from Crypto.PublicKey import RSA from Crypto.Cipher import PKCS1_OAEP from Crypto.Util.number import inverse from math import gcd zip_filename = "keys_and_messages.zip" target_key_id = "21.pem" c_hex = "c62d91677825632cb8ac9d2fbee7490fca70b3f067bd8d811fa446a21001de7943cacafc429b2513d3f20c3224d212ca2937a4a4ea10792a1c498b791e978e4b050b525576bc68421e40d9f420c0b8a07778daf69edf2095bf48222896bb2d6581288ce7a2e7aec15a88a440ff1a1e48beb56f68b4f860d1f64a6ec8cafed90846b7d893bc482df69c8478d5a0d6fc2d043cdd97178740a9eb59d2576b5136200c8ea77e648c88e6c5104ca5d0c6add2fc2c8569ce909f8461e7fa3d901fe67eaeff656399d4751fedba9973e246427e0c7a217f5bdc3edcb5033f17b5ef53419e340355a809eb46f48f538e880abd6f72212b02d3dbf2c4f633a503e648d1a835c4574b23e329e1c51078ea7cbb7533e771899498d4a5760bc0799b7e046f268f098fe0b57de47cd70ccf01ad3c9daec5027f306141bfe7a6c0bd29ee6caf94c7433c25e34ee974005e2360337cb6b3cec5eaf5d31d19f01435f4cdcaa455a18e78dee078395b8ad14b9c3a0d817dc1e3109c7b8af35ab3a5950bf47d5e621f9373ef421540052aac307ecea91f9c29c14bfd81b41d4c5a9b34a8ec2fa1ae06c3d881f39286c3d8dbb1849602fecc27bb135f7dd443e2598d247d1182d350b04be1ac0a734cb0e852a36902d88066ac375a35e279b126e413a97aaa35a0ba933f7b8d574c298332ce428c181464b240709a414af1b77103441b6ccfd0790eccea5926844054903c83f4cb415d600a6b7bc771c9e7a86394a2b427ebe8edec08b8095f561827716898e11caf6f0fe562af8a69f7b6469f0e86bdcc32f429f10821c763b34307efc5b2ae7fd524a07e5d0b762c096f025a3f240fb7bd3554582dcce32c175867d93970b0422e17870ec58f2a305545a3d284b3abb2d21a45ad8fd5faed0dc66312a5aa2f994606a51cd6682acd48ea3fb883f0611e1e5c2fb4047b5c80815ba5d3bcfefaf121bfde4d5c91ee27bb899ef0d29fa5c6dc4223ac2bfcff0217d08579a13e9b02dc97aa2622df62eeaaa38bb3bd087cdd209f03e8926a951e90eaa0f678a252a067ac66402a4c85865931689ed3b33f9f6de0c499f140ef508dfba6007a607a271dcbec18a61f7488bba34d143f93bc259310ffbf23f3391734d8d8811a4be8abf6382e55c2ccbfd80b1559d907fd8d46e0431cdbcd8fdb06d57973437f7b8ff5efc5a53c80d552e8fe622971f7376eeea35f4df9b32ada93e531a52b63ba13f6b7bf61ab337d6d93feb0e8c8a309dfa7e5f50e8cf9655b73ae64822b50db5312f35f4718b0668305065ea283ddf8f0a4e8f486ee9d119ebc584be1837b3d959a25ace208ffac2fb703390a72d3027b64fdd1955b513c0403f09232efa1794a277e0be3f4f9f3a6fd23c6e52101e723cef5db7a2a18a107cd522379adb40c5ed36b26cdf53a1000d7d576f1157b42aac3d3ee011275" c = bytes.fromhex(c_hex) keys = {} try: with zipfile.ZipFile(zip_filename, "r") as zf: for filename in zf.namelist(): if filename.endswith(".pem"): key_id = filename.split("/")[-1] keys[key_id] = RSA.import_key(zf.read(filename)) target_key = keys[target_key_id] for key_id, other_key in keys.items(): if key_id == target_key_id: p = gcd(target_key.n, other_key.n) if p != 1: q = target_key.n // p phi = (p - 1) * (q - 1) d = inverse(target_key.e, phi) private_key = RSA.construct((target_key.n, target_key.e, d, p, q)) cipher = PKCS1_OAEP.new(private_key) flag = cipher.decrypt(c) print(flag.decode()) break ``` :::spoiler Flag crypto{3ucl1d_w0uld_b3_pr0ud} ::: - Giải thích code: `key_id = filename.split("/")[-1]` dùng để trích xuất tên file ra, vì được lưu vào zip nên file name sẽ có dạng `"keys_and_messages.zip/keys_and_messages/1.pem"`, mà ta chỉ cần `"1.pem"`, nên phải spilt ở ký tự `"/"` rồi sau đỏ lấy phần tử cuối cùng là `"1.pem"`. Sau khi có được d, ta phải mã hóa bằng phương thức PKCS1_OAEP mới ra đúng flag. ### RSA Backdoor Viability ## Padding ### Bespoke Padding ![image](https://hackmd.io/_uploads/Sy-ENJrTeg.png) - Trừ bài Fast Prime và RSA Backdoor Viability ra thì đây là bài mình cảm thấy khó nhất trong mục này 🐧🐧 - `13386.py` ```py= from utils import listener from Crypto.Util.number import bytes_to_long, getPrime import random FLAG = b'crypto{???????????????????????????}' class Challenge(): def __init__(self): self.before_input = "Come back as much as you want! You'll never get my flag.\n" self.p = getPrime(1024) self.q = getPrime(1024) self.N = self.p * self.q self.e = 11 def pad(self, flag): m = bytes_to_long(flag) a = random.randint(2, self.N) b = random.randint(2, self.N) return (a, b), a*m+b def encrypt(self, flag): pad_var, pad_msg = self.pad(flag) encrypted = (pow(pad_msg, self.e, self.N), self.N) return pad_var, encrypted def challenge(self, your_input): if not 'option' in your_input: return {"error": "You must send an option to this server"} elif your_input['option'] == 'get_flag': pad_var, encrypted = self.encrypt(FLAG) return {"encrypted_flag": encrypted[0], "modulus": encrypted[1], "padding": pad_var} else: return {"error": "Invalid option"} import builtins; builtins.Challenge = Challenge # hack to enable challenge to be run locally, see https://cryptohack.org/faq/#listener """ When you connect, the 'challenge' function will be called on your JSON input. """ listener.start_server(port=13386) ``` - Mô tả: khi ta connect với JSON: `{"option":"get_flag"}` tới sever, ta sẽ nhận được c, N và phần padding: ![Screenshot 2025-10-09 144000](https://hackmd.io/_uploads/SyKev1HTxl.png) - Phân tích chall ta thấy: N, e sẽ không đổi, a và b là pad và được sinh ngẫu nhiên từ 2 đến N, m sau khi pad sẽ có dạng a*m + b. - Hướng dẫn: Sau khi mò mẫm thì mình biết đây là Franklin-Reiter attack vì sever mã hóa cùng thông điệp m, N nhiều lần. Nhưng mỗi lần lại sử dụng a, b khác nhau và e nhỏ => có thể dùng Franklin-Reiter attack - Hướng tấn công: - Chúng ta kết nối tới server hai lần và nhận được: - Lần 1: $(c_1, N, a_1, b_1)$ - Lần 2: $(c_2, N, a_2, b_2)$ ![Screenshot 2025-10-09 144448](https://hackmd.io/_uploads/Sy6oFkHpxe.png) - Từ đó, chúng ta có hai phương trình đồng dư: 1. $c_1 \equiv (a_1 m + b_1)^e \pmod{N}$ 2. $c_2 \equiv (a_2 m + b_2)^e \pmod{N}$ - Điều này có nghĩa là `m` là nghiệm chung của hai đa thức $P_1(x),P_2(x)$ trên vành $\mathbb{Z}_N[x]$: 1. $P_1(x) = (a_1 x + b_1)^e - c_1 \equiv 0 \pmod{N}$ 2. $P_2(x) = (a_2 x + b_2)^e - c_2 \equiv 0 \pmod{N}$ Vì $m$ là nghiệm chung của cả $P_1(x)$ và $P_2(x)$, nên đa thức bậc nhất $(x - m)$ phải là một nhân tử của cả hai đa thức này. Theo tính chất đại số cơ bản, nhân tử chung này chính là Ước chung lớn nhất (GCD) của hai đa thức. Ta có thể tìm nó dễ dàng bằng thuật toán Euclid:$$GCD(P_1(x), P_2(x)) = x - m \pmod N$$ - Cài đặt code: 1. Buid đa thức: - Chúng ta cần biểu diễn $P_1(x)$ và $P_2(x)$ dưới dạng mảng các hệ số. Ta sử dụng khai triển nhị thức Newton cho $(ax+b)^e$: $(ax+b)^e = \sum_{k=0}^{e} \binom{e}{k} (ax)^k b^{e-k} = \sum_{k=0}^{e} \left( \binom{e}{k} a^k b^{e-k} \right) x^k$ ```py= def build_polynomials(a, b, e, c): coefficients = [] for k in range(e, -1, -1): coeff = comb(e, k) * pow(a, k, n) * pow(b, e-k, n) % n coefficients.append(coeff) coefficients[-1] = (coefficients[-1] - c) % n return coefficients ``` - 2. Tiến hành chia đa thức: ```py= def polynomial_mod(f1, f2): f1 = normalize(f1[:]) f2 = normalize(f2[:]) deg_f1 = len(f1) - 1 deg_f2 = len(f2) - 1 if deg_f1 < deg_f2: return [0], f1 q = [0] * (deg_f1 - deg_f2 + 1) inverse = pow(f2[0], -1, n) # nghịch đảo module của hệ số bậc cao nhất của f2 for i in range(len(q)): f1 = normalize(f1) coeff = f1[i]*inverse % n q[i] = coeff if deg_f1 < deg_f2: break for j in range(len(f2)): f1[j] = (f1[j] - coeff*f2[j]) % n r = normalize(f1) q = normalize(q) return q, r ``` - Tất cả các phép tính trên hệ số đều được thực hiện theo module `N`.Ta phải tính nghịch đảo module của hệ số cao nhất vì trong số học module, phép chia không tồn tại, thay vào đó ta thực hiện phép nhân với nghịch đảo. - Khi code mình gặp phải 1 vấn đề là hệ số lớn nhất của đa thức = 0 ví dụ hàm $f$ = [0, 2, 3, 5], về mặt toán học thì nó vẫn là $2x^2 + 3x + 5$ nhưng khi tính thì gặp lỗi, nên mình đã code thêm hàm `normalize()` để xóa các xố 0 ở đầu ```py= def normalize(f): while len(f) > 1 and f[0] == 0: f.pop(0) return f ``` - Sau đó ta dùng thuật Euclid để tìm gcd của hai đa thức: ```py= def gcd_polynomial(f, g): f = normalize(f) g = normalize(g) while g != [0]: _, r = polynomial_mod(f, g) f, g = g, r inverse = pow(f[0], -1, n) f = [(c * inverse) % n for c in f] return f ``` - Ở bước cuối ta nhân các hệ số của f với nghịch đảo module của hệ số cao nhất để được 1 đa thức monic (đa thức có hệ số cao nhất = 1) - `solve.py` ```py= from Crypto.Util.number import long_to_bytes, bytes_to_long from math import comb n = 9211714991512323362090044250086274884157599209063027027219389768302178623757015690219872377273761461752422593421475092648630587674171928226739074008316529942076984353938452716639466062852195418319069637076804978072199856473352545092131012050779162863254646125643977276566093959324955443872555888570877959976124300028138917102126286195413271675122750581981518108152677760370024054021504465374716329886166533002591768220588621873363975062157214077916999803307384620947793431351349576189696188494465698337969317686186845380111547277813012313089517530018315069615147172405515510016082067848245269324988529592121314346077 a = 5998531808824752750536492597089456378632490585916481031840506432910525969319953575106651001553391846300237983416249785029654611496946930523573582552379640600457530287452540071910744446114621219221404690947657487616748831447799781418368672431030253836553441008915202461441162044156632201605672018997552703833812872731118820214712688264617866107005094718602894520074935380898540939779811919192661960943052619310950896305974156684623528455218904295643997066232077563922666746328202302205573836970446085868851625008475503939430649277319741750430287585404164902190609788048473253730090619160932154467877175481454072879705 b = 693558441417849036076994852406400496907445988771964896432363606854928059463676712062618267696160973645909949757580135909799739880696159508509960014581354628314164018914355812498722884035196158154907660157189320695220447401693818522538800165143586361530993392297085058885543253526215401478980183812399390217955105107235858130550198330589292065397534274952519445627590398859886518587485336627288000451186637354005202790327696249680120357828615223166469937058029419573627362461983689477554329729500565784185917212997624767100729069855321375915623941333655325552522951146177201544084292548459762915891021075518551492145 c = 2236187249635242076045320855706680716824570497121754269681949349271390712233886355375275009850702784362926589742007457631407877597014549145879199891608395619227754759364472900883983892490287904872642283710048755660115981809299900809310427148418524630861560850039738042453552189076073859274322653040514856985286284109464434138315347843190437619217077482258424020462579334066089395675405314676841537969527780111017832453882890260189495393692265140798994844294357507336343719634431376825013471967723552074859621410723640877886632010415858917477419215470553700181233885060073598191629844610913698665409661719299351540766 d = 7652372914758661986806250222052346926580808127927501511053964076782150086269071082730035753554285404879484754145682357375925994198576421966754833528156377370218951336279477118646315470604877720850447371048852067839924502737733807223553036286338983952098990083186050367036536525507311744742881626975100710532102755769832797449144944723712288138755644346289580078950017903449889704536669340668658374460719992301292950938915543356379512496934286500462817603252277912891295626054860941915130635457950593285699943210647185194880691576877136493426111986804029598977891212783034351263796358028534890850222995593654057188066 e = 11 c1 = 5150272865882905988720328868337551118193510149043306428600590125623710816910619603714250100376079020251612367610912635132721026333818978467671238325638109765787775134227333186818398720819354606269068940887413075107313815766347634104382034986658924462916644005906971667644050292394582012013268492727580026702291064922686114381599341707386020591880062716181357426010107478878743796998092339752563037918335277393826712620951062672126539198170604309131565198393733536413334372664982892995530152096582973911961997440611778602008000521477315444031968368138322981885670849672383521446766499548134053331585611097492404794293 c2 = 3897277964053232999326259003671947809680446535511188063265951958185763561226645445365156267304515690484426601747492076627361901709530512709577166754417913764431391407255491246692728805335347632634216579933819023302580356723499133030188454201085907884563149864667620556280797332724038372791597355944018272371100881953667189557138671733232771553724304592783764416705174739370642150113860427621169857544314567847810789021757810627011904387342080988898053333909528860154385800715236922593666766487705438617753871570018152678719470644290053776092443691276959206980072412409365939954390644067784735452447400808431756427751 def build_polynomials(a, b, e, c): coefficients = [] for k in range(e, -1, -1): coeff = comb(e, k) * pow(a, k, n) * pow(b, e-k, n) % n coefficients.append(coeff) coefficients[-1] = (coefficients[-1] - c) % n return coefficients f1 = build_polynomials(a, b, e, c1) f2 = build_polynomials(c, d, e, c2) def normalize(f): while len(f) > 1 and f[0] == 0: f.pop(0) return f # chia đa thức f1 cho f2 ( f1(x) = f2(x)q(x) + r(x) ) def polynomial_mod(f1, f2): f1 = normalize(f1[:]) f2 = normalize(f2[:]) deg_f1 = len(f1) - 1 deg_f2 = len(f2) - 1 if deg_f1 < deg_f2: return [0], f1 q = [0] * (deg_f1 - deg_f2 + 1) inverse = pow(f2[0], -1, n) # nghịch đảo module của hệ số bậc cao nhất của f2 for i in range(len(q)): f1 = normalize(f1) coeff = f1[i]*inverse % n q[i] = coeff if deg_f1 < deg_f2: break for j in range(len(f2)): f1[j] = (f1[j] - coeff*f2[j]) % n r = normalize(f1) q = normalize(q) return q, r def gcd_polynomial(f, g): f = normalize(f) g = normalize(g) while g != [0]: _, r = polynomial_mod(f, g) f, g = g, r inverse = pow(f[0], -1, n) f = [(c * inverse) % n for c in f] return f g = gcd_polynomial(f1, f2) # g(x) = x - M mod n print(long_to_bytes(-g[1] % n)) ``` :::spoiler Flag crypto{linear_padding_isnt_padding} ::: ### Null or Never ![image](https://hackmd.io/_uploads/Syb4r4rTex.png) - `pad_encrypt.py`: ```py= #!/usr/bin/env python3 from Crypto.PublicKey import RSA from Crypto.Util.number import bytes_to_long FLAG = b"crypto{???????????????????????????????????}" def pad100(msg): return msg + b'\x00' * (100 - len(msg)) key = RSA.generate(1024, e=3) n, e = key.n, key.e m = bytes_to_long(pad100(FLAG)) c = pow(m, e, n) print(f"n = {n}") print(f"e = {e}") print(f"c = {c}") ``` - Mô tả: flag được pad thêm các byte b'\x00' vào phía sau - Hướng dẫn: mỗi lần pad 1 byte b'\x00' vào flag, flag sẽ tăng lên 2^8 lần => $C \equiv (flag \times 2^{8 \times len(flag)})^e \pmod N$, mà format của flag có dạng `crypto{}` nên $8 \le len(flag) \le 100$, e = 3 nên ta có thể brute-force len(flag) sau đó brute-force k để tìm flag. - `solve.py`: ```py= from Crypto.Util.number import bytes_to_long, long_to_bytes from gmpy2 import iroot n = 95341235345618011251857577682324351171197688101180707030749869409235726634345899397258784261937590128088284421816891826202978052640992678267974129629670862991769812330793126662251062120518795878693122854189330426777286315442926939843468730196970939951374889986320771714519309125434348512571864406646232154103 e = 3 c = 63476139027102349822147098087901756023488558030079225358836870725611623045683759473454129221778690683914555720975250395929721681009556415292257804239149809875424000027362678341633901036035522299395660255954384685936351041718040558055860508481512479599089561391846007771856837130233678763953257086620228436828 for s in range(len(b"crypto{}"), 100): t = c * pow(pow(2**8, 100 - s), -3, n) % n k = 0 for k in range(2000): if iroot((n*k + t), e)[1] == True: print(long_to_bytes(iroot((n*k + t), e)[0])) exit() ``` :::spoiler Flag crypto{n0n_574nd4rd_p4d_c0n51d3r3d_h4rmful} :::