RSA & RSA ATTACK

# 1. RSA và các cách tấn công thường gặp của RSA ## 1. RSA - Trong mật mã học, RSA là một thuật toán mật mã hóa khóa công khai. Đây là thuật toán đầu tiên phù hợp với việc tạo ra chữ ký điện tử đồng thời với việc mã hóa. Nó đánh dấu một sự tiến bộ vượt bậc của lĩnh vực mật mã học trong việc sử dụng khóa công cộng. RSA đang được sử dụng phổ biến trong thương mại điện tử và được cho là đảm bảo an toàn với điều kiện độ dài khóa đủ lớn. - RSA thuộc nhóm hệ mã khóa công khai, dựa vào độ khó của bài toán phân tích 1 số ra thừa số nguyên tố (factoring problem). Để tạo cặp khóa Public key và Private key, Alice cần: - Chọn 2 số nguyên tố lớn p, q với p ≠ q - Tính $$N = pq $$ - Tính giá trị hàm số Ơle $$ φ(N) = (p-1)(q-1) $$ - Chọn 1 số e sao cho $$1 < e < φ(N) \ và \ gcd(e,φ(N)) = 1 $$ - Tính $$d = e^{-1} (mod φ(N))$$, số d thỏa mãn $$ed ≡ 1 (mod φ(N))$$ - Public Key gồm: $$ N \text{ - mudulus} $$ $$ e \text{ - số mũ mã hóa} $$ - Private Key gồm: $$ N \text{ - mudulus, xuất hiện cả trong khóa công khai và bí mật} $$ $$ d \text{ - số mũ giải mã} $$ - Khi Bob muốn gửi một tin nhắn M cho Alice, Bob chuyển M thành một số m < n theo 1 cách thỏa thuận trước. Bob sẽ tính ra bản mã c từ bản rõ m theo công thức: $$ c = m ^ e (modN) $$ - Để giải mã, Alice dùng Private Key của mình để tính ngược lại: $$m = c ^ d (modN)$$ - Quá trình giải mã có thể thu được m ban đầu là do: $$c ^ d ≡ (m ^ e) ^ d ≡ m ^ ed (modN) ≡ m (modN) \ hay \ m = c ^ d (mod N)$$ - Độ mạnh của hệ mã RSA dựa trên việc bạn cần phân tích được n ra thừa số nguyên tố để tính d nếu muốn phá mã, và đến nay chưa có giải thuật nào hiệu quả trong thời gian đa thức giúp ta phân tích thừa số nguyên tố đối với các số lớn. - Hệ mã RSA nếu được thiết kế một cách đúng đắn với việc chọn các tham số n, p, q, e hợp lý thì sẽ rất an toàn, thế nhưng trong các bài CTF, các tham số này thường được chọn theo một cách nào đó khiến cho hệ mã yếu đi và dễ bị tấn công. Các điểm yếu thực thi của RSA sẽ được trình bày dưới đây. - ỨNG DỤNG - Mã hóa RSA có thể được sử dụng trong một số hệ thống khác nhau. Nó có thể vận hành trong OpenSSL, wolfCrypt, cryptlib và một số thư viện mật mã khác. - RSA cũng thường được sử dụng để tạo kết nối an toàn giữa VPN client và VPN server. Theo các giao thức như OpenVPN, TLS có thể sử dụng thuật toán RSA để trao đổi key và thiết lập một kênh an toàn. - Theo truyền thống, nó được sử dụng trong TLS và cũng là thuận toán ban đầu được sử dụng trong mã hóa PGP. RSA vẫn được nhìn thấy trong một loạt các trình duyệt web, email, VPN, chat và các kênh giao tiếp khác - Mã hóa RSA đóng vai trò quan trọng trong việc thiết lập kết nối an toàn SSL/TLS và bảo vệ dữ liệu truyền tải trên mạng. - RSA còn sử dụng để tạo chữ kí số, xác thực Certificate HTTPS. ## 2. Các cách tấn công thường gặp của RSA ### 1. Small n - Nếu n nhỏ (chiều dài n < 256 bit), ta có thể dễ dàng factorize n bằng cách brute-force số p. Chiều dài n được khuyến cáo là 1024 bit. - Kể cả khi n lớn, đôi khi factorize của n đã có sẵn trong các database online như [factordb](http://factordb.com/). Hoặc dễ dàng factorize bằng các công cụ online như [alpertron](https://www.alpertron.com/), trang web này sử dụng phương pháp Elliptic Curve Method để factorize. Vậy nên, việc đầu tiên bạn cần làm khi gặp các bài RSA là thử các trang web này trước. - Code minh họa: ```python! from Crypto.Util.number import inverse, long_to_bytes from factordb.factordb import FactorDB n = 742449129124467073921545687640895127535705902454369756401331 e = 3 ct = 39207274348578481322317340648475596807303160111338236677373 f = FactorDB(n) f.connect() [p, q] =(f.get_factor_list()) phi =(p-1)*(q-1) d = inverse(e,phi) decrypted = pow(ct,d,n) print(long_to_bytes(decrypted)) ``` ### 2. Small e - Giả sử Alice muốn chia sẻ một tin nhắn M nhỏ (một khóa đối xứng) qua một kênh không an toàn. Cô ấy mã hóa nó bằng RSA. n được chọn từ các số nguyên tố mạnh và khá lớn nhưng cô ấy đã chọn e = 3. - Sẽ không có vấn đề gì nếu cô ấy sử dụng đệm nhưng rõ ràng không phải vậy. Bạn chặn tin nhắn và suy ra từ khóa công khai rằng nó được tính toán như sau: $$C = M^3 [n]$$ - Nhưng vì nhỏ, M^3 < n vì M vậy nó không bị ảnh hưởng bởi modulo. Bạn chỉ cần tính căn bậc ba của C để có được thông điệp gốc. $$ C = M ^ 3 (modN) = M^3 $$ - Code minh họa: ```python3! from Crypto.Util.number import * import gmpy2 # flag = b"KCSC{?????????}" # flag = bytes_to_long(flag) # p = getPrime(1024) # q = getPrime(1024) # N = p*q # e = 3 # cipher = pow(flag, e, N) # print(f"{cipher = }") # print(f"{e = }") # print(f"{N = }") cipher = 59679191818359995370202204525552897661585191321589640897962553635418434415061564469248378765641028251799653 e = 3 N = 21401699041420490699637745290653047330524576101816966213499740906093256690308283336690577207977880719037835247336954929148296393929524033882366630989121744982271886727656590351375192671511041954445109921679571050637854777638154411655036815605211653508056048587389327700171761542697049935330646071362109506002780542377842459042871967183121240602112834334684604955288028352155338385864589982161253480083366373037953822327026444497238099073117736732812210603049033870379303953354052872102810601901739978207517492864547072321106856087371530785966468583425201265802677864617199183004080683426914054350947398717594514616183 print(long_to_bytes(gmpy2.iroot(cipher, e)[0])) # KCSC{123456789} ``` ### 3.Fermat Attack - Trong thực tế, ta cần chọn p, q có cùng độ dài bit để tạo được 1 mã RSA mạnh, tuy nhiên nếu p, q quá gần nhau thì lại tạo ra lỗ hổng bảo mật khi mà attacker có thể dễ dàng factorize n - rong thực tế nếu: p - q < n^(1/4) thì Fermat’s factoring algorithm có thể phân tích n 1 cách hiệu quả. - Ta có : - Với x = (p - q)/2 & y = (p + q)/2 n có thể được phân tích thừa số nguyên tố như sau: n = x^2 - y^2 = (x - y)(x + y) - Định lý Fermat giúp tìm p, q - Code minh họa: ```python3! def isqrt(n): x = n y = (x + n // x) // 2 while y < x: x = y y = (x + n // x) // 2 return x def fermat(n): a = isqrt(n) b2 = a*a - n b = isqrt(n) count = 0 while b*b != b2: a = a + 1 b2 = a*a - n b = isqrt(b2) count += 1 p = a+b q = a-b assert n == p * q return p, q def main(): n = 163325259729739139586456854939342071588766536976661696628405612100543978684304953042431845499808366612030757037530278155957389217094639917994417350499882225626580260012564702898468467277918937337494297292631474713546289580689715170963879872522418640251986734692138838546500522994170062961577034037699354013013 p, q = fermat(n) print(f"{p = }") print(f"{q = }") if __name__ == '__main__': main() ``` ### 4.Hastad Broadcast Attack - Đặt bối cảnh một mạng nội bộ sử dụng RSA làm phương thức bảo mật truyền tin. Mỗi máy tính trong mạng LAN sẽ có một bộ Public Key (ni, ei) riêng. Giả sử rằng, quản trị viên muốn sử dụng hệ thống mã hóa đơn giản nên anh ta chọn 1 số e nhỏ (e = 3) để dùng chung cho tất cả các máy trong mạng LAN, hay nói cách khác e1 = e2 = en = e = 3. - Kịch bản tấn công xảy ra nếu máy chủ gửi cùng 1 tin nhắn broadcast m (đã được mã hóa thành c1, c2, ... cho nhiều máy tính trong mạng, và ta bắt được ít nhất e ciphertext c1, c2, ..., ce. Lúc này, ta sẽ có thể khôi phục lại plaintext m không mấy khó khăn. - Giả sử e = 3, đặt M = m^3. Nhiệm vụ của ta là giải hệ phương trình đồng dư: ```sage! M ≡ c1[n1] M ≡ c2[n2] m ≡ c3[n3] ``` - Để tìm được M thì điều kiện cần có là GCD(ni, nj) = 1 - Ta có thể áp dụng [Chinese Remainder Theorem](https://en.wikipedia.org/wiki/Chinese_remainder_theorem#:~:text=In%20mathematics%2C%20the%20Chinese%20remainder,are%20pairwise%20coprime%20(no%20two)). Sau khi tính được M, ta sẽ tìm lại được m (vì m < ni nên M = m ^ 3 < N, ta chỉ cần tính căn bậc 3 của M). - Code minh họa: ```python3! from Crypto.Util.number import * import gmpy2 e = 17 c1 = 5281902984460481872302011044114495295234706883691270450730514347553367729238298595829480655414548578940224329381972042327440066670142366495280771989420757877500383415087347958655409229805727133604659164018942437897797502973158822281545452793162139435644545907400047562338947483265323747272064512895032117277125123806241924006024065776471160313966595545372454577848929238063734964580623425517430922461778531674407648652147793048655534309061064293141379907098205500027275675907609664817506677507430929046690025280013453016187259205326639860958728201747428903509610925019408056231238340322831006094356755532942788059845 n1 = 16930644133133585153982116446709052721672748348204781862085225308015958369430178426924538163682833765362822077349105004445448958262188377554881412690572248052350840173351221808492539562404392378070802786671280372543130448307383633438827466178723748896312100460675703702162271014860469664170242386651584282586901993638538797099854814661924313225993112751308504309349333978398784283221774291656840002217537988653138155296055099768818584462192204413162324165236392979907684140656757898307337905401896581249560678489854415726470019798795208823138650333827337983608326844617365113983298696064210393115154759291454195692373 c2 = 6162539726286592168394448349690174616346889109160236370611851880156690694712760329744074831228591055634518601693912353931368848316889426845015738676848439972254280732503854103853320110092491469914385988167410727536596346306843876822277027093518743294669965911466013487176645544303209199706511600822221896442247998987128724332167832065101628368630622196780631151950624374003738598234457262104177776394340556855566300326141831504301005520835753870827859262212652975658548934416777300952082762384420499635206417089278284976520806511553990747668508907624111161554742592764211574031473657602849178212391109386523736123225 n2 = 24517830966075068901143081428136123787052462312728921454664505259135368205967208384321697479280273940725987122343582634769573313694977955351008895829262278664950511633319526458471500717719183843537956381037748017055977477231213564700962749046423150919990089564077863308748604142838798184581851355965003040482172222846012964383746163017000648375552920723819402398890728926342009527890326964300454951835432280426955033831895830700954905020816313887830291466080919961631523098068933610444428612902610455365013948374770977767001367985317420877941833498437819340406382755518088589696697321340723109560066075801867816757243 c3 = 19908100167530216645294949759783346545029235701853013289113833267209207614808513713310237969750220599230702392524311814340229834745985200556448477263767965831011135495482388430411710703857335313563121388465470530848661415361605517365926771165709472561083643203337808374724449086723593596845700498749711885216543551227316982638103624172386677548005428618414955857762672903247827644153128066936494858165396265940016365364770664110861333303512475064549820159646008318554658964484061481333613199128577346633337396079262450825350654019895506969392774300773381808489530831368833223045245411050842234360325298418088989859161 n3 = 21404493333459773651833468889494854452146341909489290362795042422081025549394197696207194740465796006865793114554826965350325270688131352372790308281188594067594092027310514703330195829475266538616467239956851153498522500671756355728397676054553313625727693338831805978536697927429324389373252910725919888390839180105695354495463820979707332963584951628592768362598994748878184136661630763266935396207706143788599547556573680129113171095202415059427609744739187238102875459200266914230437205151399301939429262300637643779611482708303062671827115951463353597025183123730487168755528498188468405928192815431774026410657 N=n1*n2*n3 N1=N//n1 N2=N//n2 N3=N//n3 u1 = inverse(N1, n1) u2 = inverse(N2, n2) u3 = inverse(N3, n3) M = (c1*u1*N1 + c3*u3*N3 + c2*u2*N2) % N m = gmpy2.iroot(M,e)[0] print(long_to_bytes(m)) ``` ### 5.Wiener Attack - Để giảm thời gian giải mã (hoặc thời gian tạo chữ ký), người ta có thể muốn sử dụng một giá trị nhỏ của d hơn là một d ngẫu nhiên. Do lũy thừa mô-đun cần có thời gian tuyến tính trong log2 d, nên một d nhỏ có thể cải thiện hiệu suất ít nhất là hệ số 10 (đối với mô-đun 1024 bit). Thật không may, một cuộc tấn công thông minh của M. Wiener [19] cho thấy rằng một d nhỏ dẫn đến sự phá vỡ hoàn toàn hệ thống mật mã. - Đặt N= p*q với q < p < 2q . Đặt ![](https://hackmd.io/_uploads/Sy8w0eb5h.png). Cho trước (N,e) với ed = 1 mod phi(N), Marvin có thể phục hồi d một cách hiệu quả. - Bằng chứng dựa trên các xấp xỉ sử dụng các phân số liên tục. Vì ed = 1 mod phi(N), nên tồn tại k sao cho ed − kphi(N) = 1. Do đó, ![](https://hackmd.io/_uploads/HyEwtb-5h.png) - Do đó, k/d là một xấp xỉ của e/phi(N). Mặc dù Marvin không biết phi(N), anh ấy có thể sử dụng N để tính gần đúng nó. Thật vậy, vì phi(N) = N − p − q + 1 và p + q − 1 < 3sqrt(N), nên chúng ta có |N − phi(N)| < 3sqrt(N). Sử dụng N thay cho phi(N), chúng tôi thu được: ![](https://hackmd.io/_uploads/SkDUqWZ92.png) - Bây giờ, kphi(N) = ed − 1 < ed. Vì e < phi(N), chúng ta thấy rằng k < d < ![](https://hackmd.io/_uploads/HJ52cWbc3.png) . Do đó chúng tôi có được:![image](https://hackmd.io/_uploads/SkjBsRo_p.png) - Cuối cùng có được ![image](https://hackmd.io/_uploads/Sk3phCj_T.png) - Đây là một quan hệ xấp xỉ cổ điển. Các số lượng phân số k/d với d < N gần đúng với e/N bị giới hạn bởi log2 N. Thực tế, tất cả các phân số như vậy thu được dưới dạng các phần tử hội tụ của khai triển phân số liên tục của e/N . Tất cả người ta phải làm là tính log N hội tụ của phân số tiếp tục cho e/N. Một trong số này sẽ bằng k/d. Vì ed − kphi(N) = 1, nên ta có gcd(k, d) = 1, và do đó k/d là phân số rút gọn. Đây là một thuật toán thời gian tuyến tính để khôi phục khóa bí mật d. - Code minh họa: ```python3! from Crypto.Util.number import* import owiener N = 'b12746657c720a434861e9a4828b3c89a6b8d4a1bd921054e48d47124dbcc9cfcdcc39261c5e93817c167db818081613f57729e0039875c72a5ae1f0bc5ef7c933880c2ad528adbc9b1430003a491e460917b34c4590977df47772fab1ee0ab251f94065ab3004893fe1b2958008848b0124f22c4e75f60ed3889fb62e5ef4dcc247a3d6e23072641e62566cd96ee8114b227b8f498f9a578fc6f687d07acdbb523b6029c5bbeecd5efaf4c4d35304e5e6b5b95db0e89299529eb953f52ca3247d4cd03a15939e7d638b168fd00a1cb5b0cc5c2cc98175c1ad0b959c2ab2f17f917c0ccee8c3fe589b4cb441e817f75e575fc96a4fe7bfea897f57692b050d2b' E = '9d0637faa46281b533e83cc37e1cf5626bd33f712cc1948622f10ec26f766fb37b9cd6c7a6e4b2c03bce0dd70d5a3a28b6b0c941d8792bc6a870568790ebcd30f40277af59e0fd3141e272c48f8e33592965997c7d93006c27bf3a2b8fb71831dfa939c0ba2c7569dd1b660efc6c8966e674fbe6e051811d92a802c789d895f356ceec9722d5a7b617d21b8aa42dd6a45de721953939a5a81b8dffc9490acd4f60b0c0475883ff7e2ab50b39b2deeedaefefffc52ae2e03f72756d9b4f7b6bd85b1a6764b31312bc375a2298b78b0263d492205d2a5aa7a227abaf41ab4ea8ce0e75728a5177fe90ace36fdc5dba53317bbf90e60a6f2311bb333bf55ba3245f' C = 'a3bce6e2e677d7855a1a7819eb1879779d1e1eefa21a1a6e205c8b46fdc020a2487fdd07dbae99274204fadda2ba69af73627bdddcb2c403118f507bca03cb0bad7a8cd03f70defc31fa904d71230aab98a10e155bf207da1b1cac1503f48cab3758024cc6e62afe99767e9e4c151b75f60d8f7989c152fdf4ff4b95ceed9a7065f38c68dee4dd0da503650d3246d463f504b36e1d6fafabb35d2390ecf0419b2bb67c4c647fb38511b34eb494d9289c872203fa70f4084d2fa2367a63a8881b74cc38730ad7584328de6a7d92e4ca18098a15119baee91237cea24975bdfc19bdbce7c1559899a88125935584cd37c8dd31f3f2b4517eefae84e7e588344fa5' n = int(N,16) e = int(E,16) c = int(C,16) d = owiener.attack(e, n) if d is None: print("Failed") else: print('d = ' , d) #d = 4405001203086303853525638270840706181413309101774712363141310824943602913458674670435988275467396881342752245170076677567586495166847569659096584522419007 print(long_to_bytes(pow(c,d,n))) ``` ### 6. Common modulus #### 1.External attack - Cuộc tấn công mô đun phổ biến lợi dụng thực tế là nếu hai khóa công khai RSA chia sẻ cùng một mô đun (n), các bản mã được mã hóa bằng các khóa này cũng sẽ chia sẻ cùng một mô đun. Giả sử chúng ta có hai bản mã, C1 và C2, được mã hóa bằng các khóa công khai tương ứng (e1, n) và (e2, n). $$C1 = M^e1 (modN)$$ $$C2 = M^e2 (modN)$$ - Để thực hiện tấn công tìm m thì ta cần tìm u, v từ $$ GCD(e1, e2) = 1 <=> e1*u + e2*v = 1$$ ```! C1 = M^e1 C2 = M^e2 C1^u = M^e1*u c2^v = M^e2*v Khi đó C1^u*C2^v = M^e1*u * M^e2*v = M^(e1*u + e2*v) = M ``` - Từ đó ta sẽ khôi phục được bản mã. Code minh họa: bài RSA5 byuctf 2023 ```python3! from Crypto.Util.number import * from numpy import * n = 158307578375429142391814474806884486236362186916188452580137711655290101749246194796158132723192108831610021920979976831387798531310286521988621973910776725756124498277292094830880179737057636826926718870947402385998304759357604096043571760391265436342427330673679572532727716853811470803394787706010603830747 e1 = 65537 c1 = 147465654815005020063943150787541676244006907179548061733683379407115931956604160894199596187128857070739585522099795520030109295201146791378167977530770154086872347421667566213107792455663772279848013855378166127142983660396920011133029349489200452580907847840266595584254579298524777000061248118561875608240 e2 = 65521 c2 = 142713643080475406732653557020038566547302005567266455940547551173573770529850069157484999432568532977025654715928532390305041525635025949965799289602536953914794718670859158768092964083443092374251987427058692219234329521939404919423432910655508395090232621076454399975588453154238832799760275047924852124717 def egcd(a,b): u, u1 = 1, 0 v, v1 = 0, 1 while b: q = a // b u, u1 = u1, u - q * u1 v, v1 = v1, v - q * v1 a, b = b, a - q * b return u, v, a print(egcd(e1, e2)) u=-4095 v=4096 c1_inv = inverse(c1, n) m= (pow(c1_inv,-u) * pow(c2,v))%n print(long_to_bytes(m)) # flag: byuctf{NEVER_USE_SAME_MODULUS_WITH_DIFFERENT_e_VALUES} ``` #### 2.internal attacker - Giả định rằng bạn là một phần của nhóm và sở hữu khóa công khai và riêng tư với cùng mô đun với những người khác. - Ta có: $$e*d = 1 mod φ(n)$$ $$e*d = k * φ(n) + 1$$ $$k = (e*d - 1) / φ(n)$$ $$φ(n) = (e*d - 1) / k$$ - Nếu kết quả không phải là số nguyên, hãy tăng k dần cho đến khi thu được kết quả. - Bây giờ bạn đã biết φ(n) và e của nạn nhân, bạn có thể tính toán các khóa ``d(victim) = e(victim) ^ -1 mod φ(n)`` riêng tương ứng và giải mã các tin nhắn ### 7.Blinding Attack - Khi Marvin cố gắng gửi một tin nhắn tương tự như Alices, Bob nhận thấy rằng tin nhắn có một số thông điệp nguy hiểm trong đó và từ chối ký vào tin nhắn. Nhưng RSA vốn không có bất kỳ cơ chế kiểm tra nào, những ràng buộc này có thể được bỏ qua một cách dễ dàng. Đôi khi chỉ cần nhân thông điệp nguy hiểm với một số nguyên tố là đủ. Vì vậy, Marvin có thể thử một cuộc tấn công mù bằng cách sử dụng các bước sau: - 1. Chuẩn bị một bộ đệm r^e (r = số nguyên nhỏ và e = khóa công khai) và gửi tin nhắn nhân với bộ đệm. `` M' = ( r^e * M ) % N `` . Những bộ đệm này thường được gọi là các yếu tố làm mù. - 2. Vì Bob chỉ kiểm tra một số ký tự, chuỗi nhất định, tin nhắn của Marvin sẽ được chấp thuận vì theo quan điểm của Bob, Marvin đang gửi một tin nhắn ngẫu nhiên không chứa bất kỳ văn bản không mong muốn nào. Và bob trả về tin nhắn đã ký. `` S’ = (M’)^d (mod N) = (r^e M)^d (mod N) = r^ed * M^d (mod N) = r * M^d (mod N)`` - 3. Bây giờ tất cả những gì Marvin phải làm là giải mã tin nhắn và loại bỏ yếu tố gây mù. Chữ kí cho thông điệp M chính là : ``S'/r = M^d (modN)`` ### 8. Multi-prime RSA - Với n thông thường chúng ta thường factor ra 2 số nguyên tố nhưng ở trường hợp sau thì n factor ra nhiều số nguyên tố. - ![image](https://hackmd.io/_uploads/BylGS13_p.png) - Ở challenge ``Manyprime`` bên dưới thì chúng ta sẽ áp dụng cách tấn công này. ``` n = p1 * p2 * p3 * ... * pn phi(n) = (p1-1) * (p2-1) * (p3-1) * ... * (pn-1) ``` ```sage! >>> from Crypto.Util.number import * >>> p1 = 13 >>> p2 = 17 >>> p3 = 89 >>> p4 = 101 >>> n = p1 * p2 * p3 * p4 >>> e = 23 >>> phi = (p1-1) * (p2-1) * (p3-1) * (p4-1) >>> d = inverse(e,phi) >>> m = 1337 >>> c = pow(m,e,n) >>> m == pow(c, d, n) True ``` ### 9. Boneh Durfee Attack - [Boneh Durfee Attack](https://www.sciencedirect.com/science/article/pii/S0304397518305371) là sự mở rộng, nâng cao hơn so với Wiener Attack - Ở đây ``Boneh Durfee`` sẽ tấn công với điều kiện private key lớn hơn: $$d < N ^ {0.292}$$ - Chúng ta sử dụng tấn công Boneh Durfee để tìm lại d. ![image](https://hackmd.io/_uploads/BJuRbUhup.png) ``` φ(n) = (p-1) * (q-1) = p*q - p - q + 1 = N + 1 - p - q ed = 1 mod φ(n) => ed = k φ(n) + 1 => k φ(n) + 1 = 0 mod e => k (N + 1 - p - q) + 1 = 0 mod e => 2k [(N + 1)/2 + (-p -q)/2] + 1 = 0 mod e => f(x,y) = x *(A + y) + 1 ``` - Khi đó ta dựng lattices từ ``f(x,y) = x *(A + y) + 1 `` - Việc còn lại private key d được tìm kiếm với việc giải ra x, y. - Sau đây là ví dụ áp dụng ``boneh durfee`` trong bài ``Everything is Still Big`` - Ở đây matrix của nó rất to nên ta không thể lập bằng tay trên sage được ```python! import itertools from sage.all import * def small_roots(f, bounds, m=1, d=None): if not d: d = f.degree() if isinstance(f, Polynomial): x, = polygens(f.base_ring(), f.variable_name(), 1) f = f(x) R = f.base_ring() N = R.cardinality() f /= f.coefficients().pop(0) f = f.change_ring(ZZ) G = Sequence([], f.parent()) for i in range(m+1): base = N^(m-i) * f^i for shifts in itertools.product(range(d), repeat=f.nvariables()): g = base * prod(map(power, f.variables(), shifts)) G.append(g) B, monomials = G.coefficient_matrix() monomials = vector(monomials) factors = [monomial(*bounds) for monomial in monomials] for i, factor in enumerate(factors): B.rescale_col(i, factor) B = B.dense_matrix().LLL() B = B.change_ring(QQ); print(len(B.rows()), len(B.columns())); for i, factor in enumerate(factors): B.rescale_col(i, 1/factor) H = Sequence([], f.parent().change_ring(QQ)) for h in filter(None, B*monomials): H.append(h) I = H.ideal() if I.dimension() == -1: H.pop() elif I.dimension() == 0: roots = [] for root in I.variety(ring=ZZ): root = tuple(R(root[var]) for var in f.variables()) roots.append(root) return roots return [] def boneh_durfee(N, e): print('Boneh Durfee') bounds = (floor(N^.25), 2^1024) d = random_prime(bounds[0]) e = e R = Integers(e) P.<k, s> = PolynomialRing(R) f = 2*k*((N+1)//2 - s) + 1 print(small_roots(f, bounds, m=3, d=4)) if __name__ == '__main__': print('Generating primes') e = 19822480419274488251677307922322581373608204916680174673515561360377028968995622607105335755414698144839412875613842080380230300482081946559177683666445909117111224336011873134132068056373656982714080443846061013910593976113415924274483397122945817679487981728613001314822288629582438110592231444108617950478126633605615041008363059448762655342571466013321463018102191788621452554997775676351436919999398565010668785252540431172512816473968178117862553874600835604298639910296325807391721223375419556418763943323750839521188471388175040976788107840583526861438993050030109324607729519719906931135902316161956554417247 N = 22363547196442286210426096667664934311317202577331708826153312267732060185205433048808318440463775968421571822227366261954714323978290561533582199565520788429312336490136251056698920021717041035283985925620392112442824974178172021230849595039039306862922738621825885516779477934926848831948958100398352376077348421245571051324795910162119087349950756020138069248337386146521430971157062177977730152042384068692748838755054309828353321199177441035894790043246481449883627784291325743830605685598965856794606303061786664661856150516456672469573269821203622123914965529899157206838756880892870142776988576626372988177707 print(f"{N = }") print(f"{e = }") boneh_durfee(N, e) ``` ### 10. Bleichenbacher’s Attack ![image](https://hackmd.io/_uploads/r1taqQeYT.png) - Cuộc tấn công này có thể áp dụng khi trao đổi khóa diễn ra bằng thuật toán RSA và phần đệm được sử dụng là PKCS # 1 v1.5. - Cách thức hoạt động của Attack: - Lưu ý rằng trong quá trình thiết lập phiên TLS với trao đổi khóa RSA, máy khách chọn một số 48 bit ngẫu nhiên (2 byte phiên bản giao thức và 46 byte ngẫu nhiên), pad theo sơ đồ mã hóa PKCS để tạo cùng thứ tự modulo n. Toàn bộ sự việc sau đó được nâng lên số mũ công khai e modulo n. Về phía người nhận, sau khi giải mã, dữ liệu được xác minh để căn chỉnh đúng nếu không gói sẽ bị loại bỏ. Sau khi giải mã, người nhận kiểm tra xem dữ liệu văn bản thuần túy có bắt đầu bằng ``0x00 02 ``, nếu không nó bị loại bỏ, thì tất cả các byte sẽ bị bỏ qua cho đến khi tìm thấy 0x00. - dữ liệu đệm PKCS phải luôn bắt đầu bằng 0x00 0x02. - Giả sử kẻ tấn công nhận được văn bản mật mã C về cơ bản là $$ M = c^d (modN)$$ kẻ tấn công không biết về M (được đệm PKCS) nhưng anh ta biết về khóa công khai (e, n). $$ C = M^e(modN)$$ - Kẻ tấn công sau đó nhân giá trị mật mã này với một s đã chọn. Đối với tất cả các trường hợp lỗi, máy chủ sẽ báo lỗi. Kẻ tấn công tiếp tục thay đổi giá trị của s và đợi cho đến khi được máy chủ chấp nhận. $$C' = Cs^e (modN)$$ - Khi máy chủ chấp nhận C 'có nghĩa là C'sau khi giải mã bắt đầu bằng 0x00 0x02 và C' là mã hóa hợp lệ cho M * s với đệm PKCS. $$ M' = (Cs^e)^d (modN) = C^d s^{ed} (modN) = ms (modN) $$ - Chọn hằng số $$B = 2^8(k−2)$$ k là kích thước khóa tính bằng byte, giống như trong RSA chúng ta nói 2048 bit (256 byte). Vì 2 byte đầu tiên là 0x00 0x02 ,2⁸ được thực hiện để hiển thị thông điệp trong biểu diễn bit - Khi tin nhắn được máy chủ chấp nhận, điều đó có nghĩa là. $$ 2B < m*s (modN) < 3B$$ - Nếu thông điệp được chấp nhận, 2 byte đầu tiên được 0x00 02 và do đó thông điệp $$ m*s (modN) $$ hoàn toàn nhỏ hơn khi 2 byte đầu tiên được 0x00 03. Và giống như kẻ tấn công tiếp tục giảm ranh giới bằng cách thực hiện tìm kiếm nhị phân cho đến khi một giá trị duy nhất được tìm thấy. ### 11. Brute force attack on small secret CRT-Exponents - Giả sử tôi có: $$ d_p ≡ e^{-1} \ (mod(p-1))$$ $$ d_q ≡ e^{-1} \ (mod(q-1))$$ - Với dp ta có: $$ d_p * e ≡ 1 \ (mod(p-1))$$ $$ d_p * e ≡ 1 + k(p-1)$$ - Chọn một số m bất kì sao cho ``GCD(m, p) = 1`` - Khi đó: $$ m^{d_p*e} = m^{1+k(p-1)} = m * m^{(p-1)^k} $$ - Theo Fermat’s little theorem ta có: $$ m * m^{(p-1)^k}(modP) = m * 1^k(modP) = m (modP) $$ $$ m^{e*d_p} ≡ m(modP) \ hay \ m - m^{e*d_p} = k*p$$ - Và cuối cùng: $$ GCD(m-m^{e*d_p}, n) = GCD(k*p, p* q) = p $$ với ``m < n `` - Code minh họa: ```c! sage: from Crypto.Util.number import isPrime, GCD ....: ....:n=95580702933509662811256129990158655210667121276245053843875590334281563078868202152845967187641817281520364662600110239110410372520340630639373679599982371620736610194814723749147422221945978800055101110346161945811520158431287139909125886966214800526831490560384144156085296004816333892025839072729987354233 .... e=1817084480271067137841898198122075168542117135135738925285694555698012943264936112861815937200507849960517390660821911331068907250788900674614345400567411 ....: m = 7516789928765 # random number ....: for dp in range(1000000): ....: f = GCD(m-pow(m, e*dp, n), n) ....: if f > 1: ....: print(dp, f) ....: break ....: p = f ....: q = n // p ....: print(isPrime(p)) ....: print(isPrime(q)) ....: 187261 8275629468590614667884614599278593237258686111405345888268221129814081809682982742676180514534238891248302334619164139839173447495925780801832743975865311 True ``` # 2. Challenges RSA Cryptohack ### 1. RSA Starter 1 ![image](https://hackmd.io/_uploads/rJJcDrqOT.png) Với bài này thử thách tôi chỉ cần tính phép tính ``101^17 mod 22663`` ```sage! sage: pow(101,17,22663) 19906 ``` > FLAG : 19906 ### 2. RSA Starter 2 ![image](https://hackmd.io/_uploads/SJ5Kdr9Oa.png) Với bài này tôi chỉ cần mã hóa 12 với số mũ e = 65537 và 2 số nguyên tố p = 17, q = 23 ```sage! sage: pow(12, 65537, 17*23) 301 ``` > FLAG : 301 ### 3. RSA Starter 3 ![image](https://hackmd.io/_uploads/Sy37Frqda.png) - Bài này yêu cầu ta tính phi(n) dựa vào[Euler’s Totient Function](https://leimao.github.io/article/RSA-Algorithm/) ```python3! phiN = (p-1)* (q-1) print(phiN) ``` > FLAG : 882564595536224140639625987659416029426239230804614613279163 ### 4. RSA Starter 4 ![image](https://hackmd.io/_uploads/SJ3Etr5dT.png) - Bài này yêu cầu ta tính private key d ```python3! from Crypto.Util.number import* p = 857504083339712752489993810777 q = 1029224947942998075080348647219 e = 65537 d = pow(e,-1,(p-1)*(q-1)) print(d) ``` > FLAG : 121832886702415731577073962957377780195510499965398469843281 ### 5. RSA Starter 5 ![image](https://hackmd.io/_uploads/rkiLTSq_p.png) - Bài này tôi chỉ cần factor n từ đó tính phi(n) và private key rồi giải mã ciphertext để tìm ra flag. ```python3! from Crypto.Util.number import* from factordb.factordb import FactorDB n = 882564595536224140639625987659416029426239230804614613279163 c = 77578995801157823671636298847186723593814843845525223303932 e = 65537 f = FactorDB(n) f.connect() [p,q] = f.get_factor_list() d = inverse(e,(p-1)*(q-1)) flag = pow( c, d, n ) print(flag) ``` > FLAG : 13371337 ### 6. RSA Starter 6 - Challenge này yêu cầu ta kí flag bằng private key và băm nó ra với sha256 - ``To sign this message, you calculate the hash of the message: H(M) and "encrypt" this with your private key:`` $$S = H(M)^{d1} mod N1.$$ - H(M) = sha256(flag) ```python! from Crypto.Util.number import* import hashlib n = 15216583654836731327639981224133918855895948374072384050848479908982286890731769486609085918857664046075375253168955058743185664390273058074450390236774324903305663479046566232967297765731625328029814055635316002591227570271271445226094919864475407884459980489638001092788574811554149774028950310695112688723853763743238753349782508121985338746755237819373178699343135091783992299561827389745132880022259873387524273298850340648779897909381979714026837172003953221052431217940632552930880000919436507245150726543040714721553361063311954285289857582079880295199632757829525723874753306371990452491305564061051059885803 d = 11175901210643014262548222473449533091378848269490518850474399681690547281665059317155831692300453197335735728459259392366823302405685389586883670043744683993709123180805154631088513521456979317628012721881537154107239389466063136007337120599915456659758559300673444689263854921332185562706707573660658164991098457874495054854491474065039621922972671588299315846306069845169959451250821044417886630346229021305410340100401530146135418806544340908355106582089082980533651095594192031411679866134256418292249592135441145384466261279428795408721990564658703903787956958168449841491667690491585550160457893350536334242689 flag = b"crypto{Immut4ble_m3ssag1ng}" HM = hashlib.sha256(flag).hexdigest() HM = int(HM, 16) # print(HM) print(pow(HM, d, n)) ``` > FLAG : 13480738404590090803339831649238454376183189744970683129909766078877706583282422686710545217275797376709672358894231550335007974983458408620258478729775647818876610072903021235573923300070103666940534047644900475773318682585772698155617451477448441198150710420818995347235921111812068656782998168064960965451719491072569057636701190429760047193261886092862024118487826452766513533860734724124228305158914225250488399673645732882077575252662461860972889771112594906884441454355959482925283992539925713424132009768721389828848907099772040836383856524605008942907083490383109757406940540866978237471686296661685839083475 ### 7. Factoring ![image](https://hackmd.io/_uploads/Hyg2BZ8qdT.png) - Bài này tôi sẽ sử dụng [FactorDB](http://factordb.com/) của python để tách n và số nhỏ hơn sẽ là flag ```python3! from factordb.factordb import FactorDB n = 510143758735509025530880200653196460532653147 f = FactorDB(n) f.connect() [p,q] = f.get_factor_list() print(min(p,q)) ``` > FLAG: 19704762736204164635843 ### 8. Inferius Prime ![image](https://hackmd.io/_uploads/SkRBM8qd6.png) - Source [inferius.py](https://cryptohack.org/static/challenges/inferius_e85eea9b19cd68aa71ce850918302bad.py) [output.txt](https://cryptohack.org/static/challenges/output_4b843d94b6196df152219c3165b9347f.txt) - Bài này tôi làm tương tự RSA Started 5 ```python3! from Crypto.Util.number import * from factordb.factordb import FactorDB n = 742449129124467073921545687640895127535705902454369756401331 e = 3 ct = 39207274348578481322317340648475596807303160111338236677373 f = FactorDB(n) f.connect() [p,q] = f.get_factor_list() d = inverse(e,(p-1)*(q-1)) flag = pow(ct, d, n ) print(long_to_bytes(flag)) ``` > FLAG : crypto{N33d_b1g_pR1m35} ### 9. Monoprime ![image](https://hackmd.io/_uploads/rJ3oYTqua.png) - Bài này tôi kiểm tra n chỉ được cấu thành từ 1 số nguyên tố - ![image](https://hackmd.io/_uploads/ByEj-acup.png) => phi(n) = n - 1 => d = pow(e, -1, n-1) ```python! from Crypto.Util.number import* n = 171731371218065444125482536302245915415603318380280392385291836472299752747934607246477508507827284075763910264995326010251268493630501989810855418416643352631102434317900028697993224868629935657273062472544675693365930943308086634291936846505861203914449338007760990051788980485462592823446469606824421932591 e = 65537 ct = 161367550346730604451454756189028938964941280347662098798775466019463375610700074840105776873791605070092554650190486030367121011578171525759600774739890458414593857709994072516290998135846956596662071379067305011746842247628316996977338024343628757374524136260758515864509435302781735938531030576289086798942 print(long_to_bytes(pow(ct, inverse(e, n-1), n))) ``` > FLAG : crypto{0n3_pr1m3_41n7_pr1m3_l0l} ### 10. Square Eyes ![image](https://hackmd.io/_uploads/H1yvEUcup.png) - Với bài này mặc dù độ dài của n khá lớn nhưng tôi sử dụng [factor](http://factordb.com/) cho ra n = p^2 ![image](https://hackmd.io/_uploads/rJq2Dpqup.png) - Khi đó tôi sử dụng [Euler's totient]() - ![image](https://hackmd.io/_uploads/BJwrd6cdT.png) ```python! from Crypto.Util.number import* from factordb.factordb import FactorDB n = 535860808044009550029177135708168016201451343147313565371014459027743491739422885443084705720731409713775527993719682583669164873806842043288439828071789970694759080842162253955259590552283047728782812946845160334801782088068154453021936721710269050985805054692096738777321796153384024897615594493453068138341203673749514094546000253631902991617197847584519694152122765406982133526594928685232381934742152195861380221224370858128736975959176861651044370378539093990198336298572944512738570839396588590096813217791191895941380464803377602779240663133834952329316862399581950590588006371221334128215409197603236942597674756728212232134056562716399155080108881105952768189193728827484667349378091100068224404684701674782399200373192433062767622841264055426035349769018117299620554803902490432339600566432246795818167460916180647394169157647245603555692735630862148715428791242764799469896924753470539857080767170052783918273180304835318388177089674231640910337743789750979216202573226794240332797892868276309400253925932223895530714169648116569013581643192341931800785254715083294526325980247219218364118877864892068185905587410977152737936310734712276956663192182487672474651103240004173381041237906849437490609652395748868434296753449 e = 65537 ct = 222502885974182429500948389840563415291534726891354573907329512556439632810921927905220486727807436668035929302442754225952786602492250448020341217733646472982286222338860566076161977786095675944552232391481278782019346283900959677167026636830252067048759720251671811058647569724495547940966885025629807079171218371644528053562232396674283745310132242492367274184667845174514466834132589971388067076980563188513333661165819462428837210575342101036356974189393390097403614434491507672459254969638032776897417674577487775755539964915035731988499983726435005007850876000232292458554577437739427313453671492956668188219600633325930981748162455965093222648173134777571527681591366164711307355510889316052064146089646772869610726671696699221157985834325663661400034831442431209123478778078255846830522226390964119818784903330200488705212765569163495571851459355520398928214206285080883954881888668509262455490889283862560453598662919522224935145694435885396500780651530829377030371611921181207362217397805303962112100190783763061909945889717878397740711340114311597934724670601992737526668932871436226135393872881664511222789565256059138002651403875484920711316522536260604255269532161594824301047729082877262812899724246757871448545439896 f = FactorDB(n) f.connect() [p,q] = f.get_factor_list() phi = p * (p - 1) d = inverse(e, phi) print(long_to_bytes(pow(ct, d, n))) ``` > FLAG : crypto{squar3_r00t_i5_f4st3r_th4n_f4ct0r1ng!} ### 11. Manyprime ![image](https://hackmd.io/_uploads/rkFRYT5Oa.png) - Với bài này khi tôi [factor](http://factordb.com/index.php?query=580642391898843192929563856870897799650883152718761762932292482252152591279871421569162037190419036435041797739880389529593674485555792234900969402019055601781662044515999210032698275981631376651117318677368742867687180140048715627160641771118040372573575479330830092989800730105573700557717146251860588802509310534792310748898504394966263819959963273509119791037525504422606634640173277598774814099540555569257179715908642917355365791447508751401889724095964924513196281345665480688029639999472649549163147599540142367575413885729653166517595719991872223011969856259344396899748662101941230745601719730556631637) thì ra 30 số nguyên tố. ![image](https://hackmd.io/_uploads/SycBc6cu6.png) - n được cấu tạo từ nhiều số nguyên tố - n = p1 * p2 * p3 * ... * pn - phi = (p1-1) * (p2-1) * (p3-1) * ... * (pn-1) ```python3! from Crypto.Util.number import* from factordb.factordb import FactorDB n = 580642391898843192929563856870897799650883152718761762932292482252152591279871421569162037190419036435041797739880389529593674485555792234900969402019055601781662044515999210032698275981631376651117318677368742867687180140048715627160641771118040372573575479330830092989800730105573700557717146251860588802509310534792310748898504394966263819959963273509119791037525504422606634640173277598774814099540555569257179715908642917355365791447508751401889724095964924513196281345665480688029639999472649549163147599540142367575413885729653166517595719991872223011969856259344396899748662101941230745601719730556631637 e = 65537 ct = 320721490534624434149993723527322977960556510750628354856260732098109692581338409999983376131354918370047625150454728718467998870322344980985635149656977787964380651868131740312053755501594999166365821315043312308622388016666802478485476059625888033017198083472976011719998333985531756978678758897472845358167730221506573817798467100023754709109274265835201757369829744113233607359526441007577850111228850004361838028842815813724076511058179239339760639518034583306154826603816927757236549096339501503316601078891287408682099750164720032975016814187899399273719181407940397071512493967454225665490162619270814464 f = FactorDB(n) f.connect() p = f.get_factor_list() phi = 1 for i in p: phi*=(i-1) d = inverse(e, phi) print(long_to_bytes(pow(ct, d, n))) ``` > FLAG : crypto{700_m4ny_5m4ll_f4c70r5} ### 12. Salty ![image](https://hackmd.io/_uploads/HJrgaI5u6.png) - Source - [salty.py](https://cryptohack.org/static/challenges/salty_9854bdcadc3f8b8f58008a24d392c1bf.py) - [output.txt](https://cryptohack.org/static/challenges/output_95f558e889cc66920c24a961f1fb8181.txt) - Với chall này số mũ e = 1 khi mã khóa thì c = M^1 % n = M, không ảnh hưởng gì đến plaintext nên việc giải mã nó trở nên dễ dàng. ```python3! from Crypto.Util.number import* from factordb.factordb import FactorDB n = 110581795715958566206600392161360212579669637391437097703685154237017351570464767725324182051199901920318211290404777259728923614917211291562555864753005179326101890427669819834642007924406862482343614488768256951616086287044725034412802176312273081322195866046098595306261781788276570920467840172004530873767 e = 1 ct = 44981230718212183604274785925793145442655465025264554046028251311164494127485 print(long_to_bytes(ct)) ``` > FLAG : crypto{saltstack_fell_for_this!} ### 13. Modulus Inutilis ![image](https://hackmd.io/_uploads/Hy0Vtei_p.png) - Source - [modulus_inutilis.py](https://cryptohack.org/static/challenges/modulus_inutilis_d2e0022b0165d99403eafeb0bea01231.py) - [output.txt](https://cryptohack.org/static/challenges/output_30cff153b7432055fc947fc5abdb57d3.txt) - Bài này vì số e nhỏ và m^3 < n nên ta tấn công theo small e, tính căn bậc 3 của ciphertext ```sage! sage: from Crypto.Util.number import * sage: c = 24325105361790376030994184483541129237335065597307548026400135291986518015122218982047335841103775938132864295 ....: 7324889519192337152355302808400638052620580409813222660643570085177957 sage: flag = c.nth_root(3) sage: long_to_bytes(flag) b'crypto{N33d_m04R_p4dd1ng}' sage: ``` > FLAG : crypto{N33d_m04R_p4dd1ng} ### 14. Everything is Big ![image](https://hackmd.io/_uploads/BJ9rgZju6.png) - Source - [source.py](https://cryptohack.org/static/challenges/source_a9eaeb4b534011e36229bf45be4ea455.py) - [output.txt](https://cryptohack.org/static/challenges/output_1884d0ba92d19ad074549e174cdf5a70.txt) ```python! from Crypto.Util.number import long_to_bytes import RSA_owiener N = int("b8af3d3afb893a602de4afe2a29d7615075d1e570f8bad8ebbe9b5b9076594cf06b6e7b30905b6420e950043380ea746f0a14dae34469aa723e946e484a58bcd92d1039105871ffd63ffe64534b7d7f8d84b4a569723f7a833e6daf5e182d658655f739a4e37bd9f4a44aff6ca0255cda5313c3048f56eed5b21dc8d88bf5a8f8379eac83d8523e484fa6ae8dbcb239e65d3777829a6903d779cd2498b255fcf275e5f49471f35992435ee7cade98c8e82a8beb5ce1749349caa16759afc4e799edb12d299374d748a9e3c82e1cc983cdf9daec0a2739dadcc0982c1e7e492139cbff18c5d44529407edfd8e75743d2f51ce2b58573fea6fbd4fe25154b9964d", 16) e = int("9ab58dbc8049b574c361573955f08ea69f97ecf37400f9626d8f5ac55ca087165ce5e1f459ef6fa5f158cc8e75cb400a7473e89dd38922ead221b33bc33d6d716fb0e4e127b0fc18a197daf856a7062b49fba7a86e3a138956af04f481b7a7d481994aeebc2672e500f3f6d8c581268c2cfad4845158f79c2ef28f242f4fa8f6e573b8723a752d96169c9d885ada59cdeb6dbe932de86a019a7e8fc8aeb07748cfb272bd36d94fe83351252187c2e0bc58bb7a0a0af154b63397e6c68af4314601e29b07caed301b6831cf34caa579eb42a8c8bf69898d04b495174b5d7de0f20cf2b8fc55ed35c6ad157d3e7009f16d6b61786ee40583850e67af13e9d25be3", 16) c = int("3f984ff5244f1836ed69361f29905ca1ae6b3dcf249133c398d7762f5e277919174694293989144c9d25e940d2f66058b2289c75d1b8d0729f9a7c4564404a5fd4313675f85f31b47156068878e236c5635156b0fa21e24346c2041ae42423078577a1413f41375a4d49296ab17910ae214b45155c4570f95ca874ccae9fa80433a1ab453cbb28d780c2f1f4dc7071c93aff3924d76c5b4068a0371dff82531313f281a8acadaa2bd5078d3ddcefcb981f37ff9b8b14c7d9bf1accffe7857160982a2c7d9ee01d3e82265eec9c7401ecc7f02581fd0d912684f42d1b71df87a1ca51515aab4e58fab4da96e154ea6cdfb573a71d81b2ea4a080a1066e1bc3474", 16) d = RSA_owiener.attack(e, N) if d is None: exit() else: print(f"{d = }") flag=pow(c,d,N) print(long_to_bytes(flag)) ``` > FLAG : crypto{s0m3th1ng5_c4n_b3_t00_b1g} ### 15. Crossed Wires ![image](https://hackmd.io/_uploads/ryn8eWodp.png) - Source - [source.py](https://cryptohack.org/static/challenges/source_b3c3c786c649d363d27995545cf95dab.py) - [ouput.txt](https://cryptohack.org/static/challenges/output_434cbf2b937bac1177bed299b2049a92.txt) - Bài này tôi thấy flag bị mã hóa 5 lần với số mũ e khác nhau nhưng đều cung n - Giờ tôi chỉ cần đảo ngược lại là ra flag. ```python! from Crypto.Util.number import getPrime, long_to_bytes, bytes_to_long, inverse import math from gmpy2 import next_prime from factordb.factordb import * # 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}") my_key = (21711308225346315542706844618441565741046498277716979943478360598053144971379956916575370343448988601905854572029635846626259487297950305231661109855854947494209135205589258643517961521594924368498672064293208230802441077390193682958095111922082677813175804775628884377724377647428385841831277059274172982280545237765559969228707506857561215268491024097063920337721783673060530181637161577401589126558556182546896783307370517275046522704047385786111489447064794210010802761708615907245523492585896286374996088089317826162798278528296206977900274431829829206103227171839270887476436899494428371323874689055690729986771, 2734411677251148030723138005716109733838866545375527602018255159319631026653190783670493107936401603981429171880504360560494771017246468702902647370954220312452541342858747590576273775107870450853533717116684326976263006435733382045807971890762018747729574021057430331778033982359184838159747331236538501849965329264774927607570410347019418407451937875684373454982306923178403161216817237890962651214718831954215200637651103907209347900857824722653217179548148145687181377220544864521808230122730967452981435355334932104265488075777638608041325256776275200067541533022527964743478554948792578057708522350812154888097) friend_keys = [(21711308225346315542706844618441565741046498277716979943478360598053144971379956916575370343448988601905854572029635846626259487297950305231661109855854947494209135205589258643517961521594924368498672064293208230802441077390193682958095111922082677813175804775628884377724377647428385841831277059274172982280545237765559969228707506857561215268491024097063920337721783673060530181637161577401589126558556182546896783307370517275046522704047385786111489447064794210010802761708615907245523492585896286374996088089317826162798278528296206977900274431829829206103227171839270887476436899494428371323874689055690729986771, 106979), (21711308225346315542706844618441565741046498277716979943478360598053144971379956916575370343448988601905854572029635846626259487297950305231661109855854947494209135205589258643517961521594924368498672064293208230802441077390193682958095111922082677813175804775628884377724377647428385841831277059274172982280545237765559969228707506857561215268491024097063920337721783673060530181637161577401589126558556182546896783307370517275046522704047385786111489447064794210010802761708615907245523492585896286374996088089317826162798278528296206977900274431829829206103227171839270887476436899494428371323874689055690729986771, 108533), (21711308225346315542706844618441565741046498277716979943478360598053144971379956916575370343448988601905854572029635846626259487297950305231661109855854947494209135205589258643517961521594924368498672064293208230802441077390193682958095111922082677813175804775628884377724377647428385841831277059274172982280545237765559969228707506857561215268491024097063920337721783673060530181637161577401589126558556182546896783307370517275046522704047385786111489447064794210010802761708615907245523492585896286374996088089317826162798278528296206977900274431829829206103227171839270887476436899494428371323874689055690729986771, 69557), (21711308225346315542706844618441565741046498277716979943478360598053144971379956916575370343448988601905854572029635846626259487297950305231661109855854947494209135205589258643517961521594924368498672064293208230802441077390193682958095111922082677813175804775628884377724377647428385841831277059274172982280545237765559969228707506857561215268491024097063920337721783673060530181637161577401589126558556182546896783307370517275046522704047385786111489447064794210010802761708615907245523492585896286374996088089317826162798278528296206977900274431829829206103227171839270887476436899494428371323874689055690729986771, 97117), (21711308225346315542706844618441565741046498277716979943478360598053144971379956916575370343448988601905854572029635846626259487297950305231661109855854947494209135205589258643517961521594924368498672064293208230802441077390193682958095111922082677813175804775628884377724377647428385841831277059274172982280545237765559969228707506857561215268491024097063920337721783673060530181637161577401589126558556182546896783307370517275046522704047385786111489447064794210010802761708615907245523492585896286374996088089317826162798278528296206977900274431829829206103227171839270887476436899494428371323874689055690729986771, 103231)] cipher = 20304610279578186738172766224224793119885071262464464448863461184092225736054747976985179673905441502689126216282897704508745403799054734121583968853999791604281615154100736259131453424385364324630229671185343778172807262640709301838274824603101692485662726226902121105591137437331463201881264245562214012160875177167442010952439360623396658974413900469093836794752270399520074596329058725874834082188697377597949405779039139194196065364426213208345461407030771089787529200057105746584493554722790592530472869581310117300343461207750821737840042745530876391793484035024644475535353227851321505537398888106855012746117 f = FactorDB(my_key[0]) f.connect() [p, q] = f.get_factor_list() phi = (p-1)*(q-1) for e in friend_keys: d = pow(e[1], -1, phi) cipher = pow(cipher, d, my_key[0]) print(d) print(long_to_bytes(cipher)) ``` > FLAG : crypto{3ncrypt_y0ur_s3cr3t_w1th_y0ur_fr1end5_publ1c_k3y} ### 16. Everything is Still Big ![image](https://hackmd.io/_uploads/SyADeWoOa.png) - Với bài này mình nhận thấy số e lớn và làm tương tự bài ``Everything is Big`` thì ra flag. ```python! from Crypto.Util.number import long_to_bytes import RSA_owiener N = 0xb12746657c720a434861e9a4828b3c89a6b8d4a1bd921054e48d47124dbcc9cfcdcc39261c5e93817c167db818081613f57729e0039875c72a5ae1f0bc5ef7c933880c2ad528adbc9b1430003a491e460917b34c4590977df47772fab1ee0ab251f94065ab3004893fe1b2958008848b0124f22c4e75f60ed3889fb62e5ef4dcc247a3d6e23072641e62566cd96ee8114b227b8f498f9a578fc6f687d07acdbb523b6029c5bbeecd5efaf4c4d35304e5e6b5b95db0e89299529eb953f52ca3247d4cd03a15939e7d638b168fd00a1cb5b0cc5c2cc98175c1ad0b959c2ab2f17f917c0ccee8c3fe589b4cb441e817f75e575fc96a4fe7bfea897f57692b050d2b e = 0x9d0637faa46281b533e83cc37e1cf5626bd33f712cc1948622f10ec26f766fb37b9cd6c7a6e4b2c03bce0dd70d5a3a28b6b0c941d8792bc6a870568790ebcd30f40277af59e0fd3141e272c48f8e33592965997c7d93006c27bf3a2b8fb71831dfa939c0ba2c7569dd1b660efc6c8966e674fbe6e051811d92a802c789d895f356ceec9722d5a7b617d21b8aa42dd6a45de721953939a5a81b8dffc9490acd4f60b0c0475883ff7e2ab50b39b2deeedaefefffc52ae2e03f72756d9b4f7b6bd85b1a6764b31312bc375a2298b78b0263d492205d2a5aa7a227abaf41ab4ea8ce0e75728a5177fe90ace36fdc5dba53317bbf90e60a6f2311bb333bf55ba3245f c = 0xa3bce6e2e677d7855a1a7819eb1879779d1e1eefa21a1a6e205c8b46fdc020a2487fdd07dbae99274204fadda2ba69af73627bdddcb2c403118f507bca03cb0bad7a8cd03f70defc31fa904d71230aab98a10e155bf207da1b1cac1503f48cab3758024cc6e62afe99767e9e4c151b75f60d8f7989c152fdf4ff4b95ceed9a7065f38c68dee4dd0da503650d3246d463f504b36e1d6fafabb35d2390ecf0419b2bb67c4c647fb38511b34eb494d9289c872203fa70f4084d2fa2367a63a8881b74cc38730ad7584328de6a7d92e4ca18098a15119baee91237cea24975bdfc19bdbce7c1559899a88125935584cd37c8dd31f3f2b4517eefae84e7e588344fa5 N = int("b12746657c720a434861e9a4828b3c89a6b8d4a1bd921054e48d47124dbcc9cfcdcc39261c5e93817c167db818081613f57729e0039875c72a5ae1f0bc5ef7c933880c2ad528adbc9b1430003a491e460917b34c4590977df47772fab1ee0ab251f94065ab3004893fe1b2958008848b0124f22c4e75f60ed3889fb62e5ef4dcc247a3d6e23072641e62566cd96ee8114b227b8f498f9a578fc6f687d07acdbb523b6029c5bbeecd5efaf4c4d35304e5e6b5b95db0e89299529eb953f52ca3247d4cd03a15939e7d638b168fd00a1cb5b0cc5c2cc98175c1ad0b959c2ab2f17f917c0ccee8c3fe589b4cb441e817f75e575fc96a4fe7bfea897f57692b050d2b", 16) e = int("9d0637faa46281b533e83cc37e1cf5626bd33f712cc1948622f10ec26f766fb37b9cd6c7a6e4b2c03bce0dd70d5a3a28b6b0c941d8792bc6a870568790ebcd30f40277af59e0fd3141e272c48f8e33592965997c7d93006c27bf3a2b8fb71831dfa939c0ba2c7569dd1b660efc6c8966e674fbe6e051811d92a802c789d895f356ceec9722d5a7b617d21b8aa42dd6a45de721953939a5a81b8dffc9490acd4f60b0c0475883ff7e2ab50b39b2deeedaefefffc52ae2e03f72756d9b4f7b6bd85b1a6764b31312bc375a2298b78b0263d492205d2a5aa7a227abaf41ab4ea8ce0e75728a5177fe90ace36fdc5dba53317bbf90e60a6f2311bb333bf55ba3245f", 16) c = int("a3bce6e2e677d7855a1a7819eb1879779d1e1eefa21a1a6e205c8b46fdc020a2487fdd07dbae99274204fadda2ba69af73627bdddcb2c403118f507bca03cb0bad7a8cd03f70defc31fa904d71230aab98a10e155bf207da1b1cac1503f48cab3758024cc6e62afe99767e9e4c151b75f60d8f7989c152fdf4ff4b95ceed9a7065f38c68dee4dd0da503650d3246d463f504b36e1d6fafabb35d2390ecf0419b2bb67c4c647fb38511b34eb494d9289c872203fa70f4084d2fa2367a63a8881b74cc38730ad7584328de6a7d92e4ca18098a15119baee91237cea24975bdfc19bdbce7c1559899a88125935584cd37c8dd31f3f2b4517eefae84e7e588344fa5", 16) d = RSA_owiener.attack(e, N) if d is None: exit() else: print(f"{d = }") flag=pow(c,d,N) print(long_to_bytes(flag)) ``` - Với bài này tôi nghĩ là do N yếu nên có thể tấn công theo Wiener's attack còn 1 cách khác là ``boneh durfee attack``. Boneh durfee là sự mở rộng của cuộc tấn công Wiener. Pháp này sẽ tìm được khóa d(d< N ^ 0.292) lớn hơn so với Wiener(d < N ^ 0.25) - Dưới dây là 1 tool [X-RSA](https://github.com/X-Vector/X-RSA) có ``boneh durfee attack`` tôi đã sử dụng và ra flag - ![image](https://hackmd.io/_uploads/SJsIS5jup.png) > FLAG : crypto{bon3h5_4tt4ck_i5_sr0ng3r_th4n_w13n3r5} ### 17. Endless Emails ![image](https://hackmd.io/_uploads/r1pOlZiu6.png) - Với bài này tôi sử dụng ``Hastad Broadcast Attack`` để giải hệ phương trình thặng dư trung hoa. Bruce force cho đến khi xuất hiện format flag. ```python3! from Crypto.Util.number import* from itertools import combinations import gmpy2 n1 = 14528915758150659907677315938876872514853653132820394367681510019000469589767908107293777996420037715293478868775354645306536953789897501630398061779084810058931494642860729799059325051840331449914529594113593835549493208246333437945551639983056810855435396444978249093419290651847764073607607794045076386643023306458718171574989185213684263628336385268818202054811378810216623440644076846464902798568705083282619513191855087399010760232112434412274701034094429954231366422968991322244343038458681255035356984900384509158858007713047428143658924970374944616430311056440919114824023838380098825914755712289724493770021 e = 3 c1 = 6965891612987861726975066977377253961837139691220763821370036576350605576485706330714192837336331493653283305241193883593410988132245791554283874785871849223291134571366093850082919285063130119121338290718389659761443563666214229749009468327825320914097376664888912663806925746474243439550004354390822079954583102082178617110721589392875875474288168921403550415531707419931040583019529612270482482718035497554779733578411057633524971870399893851589345476307695799567919550426417015815455141863703835142223300228230547255523815097431420381177861163863791690147876158039619438793849367921927840731088518955045807722225 n2 = 20463913454649855046677206889944639231694511458416906994298079596685813354570085475890888433776403011296145408951323816323011550738170573801417972453504044678801608709931200059967157605416809387753258251914788761202456830940944486915292626560515250805017229876565916349963923702612584484875113691057716315466239062005206014542088484387389725058070917118549621598629964819596412564094627030747720659155558690124005400257685883230881015636066183743516494701900125788836869358634031031172536767950943858472257519195392986989232477630794600444813136409000056443035171453870906346401936687214432176829528484662373633624123 e = 3 c2 = 5109363605089618816120178319361171115590171352048506021650539639521356666986308721062843132905170261025772850941702085683855336653472949146012700116070022531926476625467538166881085235022484711752960666438445574269179358850309578627747024264968893862296953506803423930414569834210215223172069261612934281834174103316403670168299182121939323001232617718327977313659290755318972603958579000300780685344728301503641583806648227416781898538367971983562236770576174308965929275267929379934367736694110684569576575266348020800723535121638175505282145714117112442582416208209171027273743686645470434557028336357172288865172 n3 = 19402640770593345339726386104915705450969517850985511418263141255686982818547710008822417349818201858549321868878490314025136645036980129976820137486252202687238348587398336652955435182090722844668488842986318211649569593089444781595159045372322540131250208258093613844753021272389255069398553523848975530563989367082896404719544411946864594527708058887475595056033713361893808330341623804367785721774271084389159493974946320359512776328984487126583015777989991635428744050868653379191842998345721260216953918203248167079072442948732000084754225272238189439501737066178901505257566388862947536332343196537495085729147 e = 3 c3 = 5603386396458228314230975500760833991383866638504216400766044200173576179323437058101562931430558738148852367292802918725271632845889728711316688681080762762324367273332764959495900563756768440309595248691744845766607436966468714038018108912467618638117493367675937079141350328486149333053000366933205635396038539236203203489974033629281145427277222568989469994178084357460160310598260365030056631222346691527861696116334946201074529417984624304973747653407317290664224507485684421999527164122395674469650155851869651072847303136621932989550786722041915603539800197077294166881952724017065404825258494318993054344153 n4 = 12005639978012754274325188681720834222130605634919280945697102906256738419912110187245315232437501890545637047506165123606573171374281507075652554737014979927883759915891863646221205835211640845714836927373844277878562666545230876640830141637371729405545509920889968046268135809999117856968692236742804637929866632908329522087977077849045608566911654234541526643235586433065170392920102840518192803854740398478305598092197183671292154743153130012885747243219372709669879863098708318993844005566984491622761795349455404952285937152423145150066181043576492305166964448141091092142224906843816547235826717179687198833961 e = 3 c4 = 1522280741383024774933280198410525846833410931417064479278161088248621390305797210285777845359812715909342595804742710152832168365433905718629465545306028275498667935929180318276445229415104842407145880223983428713335709038026249381363564625791656631137936935477777236936508600353416079028339774876425198789629900265348122040413865209592074731028757972968635601695468594123523892918747882221891834598896483393711851510479989203644477972694520237262271530260496342247355761992646827057846109181410462131875377404309983072358313960427035348425800940661373272947647516867525052504539561289941374722179778872627956360577 n5 = 17795451956221451086587651307408104001363221003775928432650752466563818944480119932209305765249625841644339021308118433529490162294175590972336954199870002456682453215153111182451526643055812311071588382409549045943806869173323058059908678022558101041630272658592291327387549001621625757585079662873501990182250368909302040015518454068699267914137675644695523752851229148887052774845777699287718342916530122031495267122700912518207571821367123013164125109174399486158717604851125244356586369921144640969262427220828940652994276084225196272504355264547588369516271460361233556643313911651916709471353368924621122725823 e = 3 c5 = 8752507806125480063647081749506966428026005464325535765874589376572431101816084498482064083887400646438977437273700004934257274516197148448425455243811009944321764771392044345410680448204581679548854193081394891841223548418812679441816502910830861271884276608891963388657558218620911858230760629700918375750796354647493524576614017731938584618983084762612414591830024113057983483156974095503392359946722756364412399187910604029583464521617256125933111786441852765229820406911991809039519015434793656710199153380699319611499255869045311421603167606551250174746275803467549814529124250122560661739949229005127507540805 n6 = 25252721057733555082592677470459355315816761410478159901637469821096129654501579313856822193168570733800370301193041607236223065376987811309968760580864569059669890823406084313841678888031103461972888346942160731039637326224716901940943571445217827960353637825523862324133203094843228068077462983941899571736153227764822122334838436875488289162659100652956252427378476004164698656662333892963348126931771536472674447932268282205545229907715893139346941832367885319597198474180888087658441880346681594927881517150425610145518942545293750127300041942766820911120196262215703079164895767115681864075574707999253396530263 e = 3 c6 = 23399624135645767243362438536844425089018405258626828336566973656156553220156563508607371562416462491581383453279478716239823054532476006642583363934314982675152824147243749715830794488268846671670287617324522740126594148159945137948643597981681529145611463534109482209520448640622103718682323158039797577387254265854218727476928164074249568031493984825273382959147078839665114417896463735635546290504843957780546550577300001452747760982468547756427137284830133305010038339400230477403836856663883956463830571934657200851598986174177386323915542033293658596818231793744261192870485152396793393026198817787033127061749 n7 = 19833203629283018227011925157509157967003736370320129764863076831617271290326613531892600790037451229326924414757856123643351635022817441101879725227161178559229328259469472961665857650693413215087493448372860837806619850188734619829580286541292997729705909899738951228555834773273676515143550091710004139734080727392121405772911510746025807070635102249154615454505080376920778703360178295901552323611120184737429513669167641846902598281621408629883487079110172218735807477275590367110861255756289520114719860000347219161944020067099398239199863252349401303744451903546571864062825485984573414652422054433066179558897 e = 3 c7 = 15239683995712538665992887055453717247160229941400011601942125542239446512492703769284448009141905335544729440961349343533346436084176947090230267995060908954209742736573986319254695570265339469489948102562072983996668361864286444602534666284339466797477805372109723178841788198177337648499899079471221924276590042183382182326518312979109378616306364363630519677884849945606288881683625944365927809405420540525867173639222696027472336981838588256771671910217553150588878434061862840893045763456457939944572192848992333115479951110622066173007227047527992906364658618631373790704267650950755276227747600169403361509144 n = [n1, n2, n3, n4, n5, n6, n7] c = [c1 ,c2, c3, c4, c5, c6, c7] for i, j, k in combinations(range(7), 3): N=n[i]*n[j]*n[k] N1=N//n[i] N2=N//n[j] N3=N//n[k] u1 = inverse(N1, n[i]) u2 = inverse(N2, n[j]) u3 = inverse(N3, n[k]) M = (c[i]*u1*N1 + c[k]*u3*N3 + c[j]*u2*N2) % N m = long_to_bytes(gmpy2.iroot(M, e)[0]) if b'crypto{' in m: print(m.decode()) ``` > FLAG : crypto{1f_y0u_d0nt_p4d_y0u_4r3_Vuln3rabl3} ### 18. Infinite Descent ![image](https://hackmd.io/_uploads/Skk5x-i_a.png) - Source - [descent.py](https://cryptohack.org/static/challenges/descent_240fda375202c97a3cbaf3fdedbb8266.py) - [output.txt](https://cryptohack.org/static/challenges/output_14f82a67efe7b7edffb810dbb7ab5f27.txt) - Bài này đầu tiên tôi dùng [factordb]() và giải mã theo bài RSA5 thì ra flag ```python3 from Crypto.Util.number import getPrime, long_to_bytes, bytes_to_long, inverse from factordb.factordb import * n = 383347712330877040452238619329524841763392526146840572232926924642094891453979246383798913394114305368360426867021623649667024217266529000859703542590316063318592391925062014229671423777796679798747131250552455356061834719512365575593221216339005132464338847195248627639623487124025890693416305788160905762011825079336880567461033322240015771102929696350161937950387427696385850443727777996483584464610046380722736790790188061964311222153985614287276995741553706506834906746892708903948496564047090014307484054609862129530262108669567834726352078060081889712109412073731026030466300060341737504223822014714056413752165841749368159510588178604096191956750941078391415634472219765129561622344109769892244712668402761549412177892054051266761597330660545704317210567759828757156904778495608968785747998059857467440128156068391746919684258227682866083662345263659558066864109212457286114506228470930775092735385388316268663664139056183180238043386636254075940621543717531670995823417070666005930452836389812129462051771646048498397195157405386923446893886593048680984896989809135802276892911038588008701926729269812453226891776546037663583893625479252643042517196958990266376741676514631089466493864064316127648074609662749196545969926051 e = 65537 c = 98280456757136766244944891987028935843441533415613592591358482906016439563076150526116369842213103333480506705993633901994107281890187248495507270868621384652207697607019899166492132408348789252555196428608661320671877412710489782358282011364127799563335562917707783563681920786994453004763755404510541574502176243896756839917991848428091594919111448023948527766368304503100650379914153058191140072528095898576018893829830104362124927140555107994114143042266758709328068902664037870075742542194318059191313468675939426810988239079424823495317464035252325521917592045198152643533223015952702649249494753395100973534541766285551891859649320371178562200252228779395393974169736998523394598517174182142007480526603025578004665936854657294541338697513521007818552254811797566860763442604365744596444735991732790926343720102293453429936734206246109968817158815749927063561835274636195149702317415680401987150336994583752062565237605953153790371155918439941193401473271753038180560129784192800351649724465553733201451581525173536731674524145027931923204961274369826379325051601238308635192540223484055096203293400419816024111797903442864181965959247745006822690967920957905188441550106930799896292835287867403979631824085790047851383294389 f = FactorDB(n) f.connect() [p, q] = f.get_factor_list() d = inverse(e, (p-1)*(q-1)) print(long_to_bytes(pow(c, d, n))) ``` - Cách thứ 2 tôi nhìn vào hàm getPrimes() thì nhận thấy p, q là 2 số nguyên tố gần nhau => dùng ``Fermat Attack`` ![image](https://hackmd.io/_uploads/SJWA7sid6.png) ```python3! from Crypto.Util.number import getPrime, long_to_bytes, bytes_to_long, inverse from factordb.factordb import * from gmpy2 import isqrt def fermat(n): a = isqrt(n) b2 = a*a - n b = isqrt(n) count = 0 while b*b != b2: a = a + 1 b2 = a*a - n b = isqrt(b2) count += 1 p = a+b q = a-b assert n == p * q return p, q def main(): n = 383347712330877040452238619329524841763392526146840572232926924642094891453979246383798913394114305368360426867021623649667024217266529000859703542590316063318592391925062014229671423777796679798747131250552455356061834719512365575593221216339005132464338847195248627639623487124025890693416305788160905762011825079336880567461033322240015771102929696350161937950387427696385850443727777996483584464610046380722736790790188061964311222153985614287276995741553706506834906746892708903948496564047090014307484054609862129530262108669567834726352078060081889712109412073731026030466300060341737504223822014714056413752165841749368159510588178604096191956750941078391415634472219765129561622344109769892244712668402761549412177892054051266761597330660545704317210567759828757156904778495608968785747998059857467440128156068391746919684258227682866083662345263659558066864109212457286114506228470930775092735385388316268663664139056183180238043386636254075940621543717531670995823417070666005930452836389812129462051771646048498397195157405386923446893886593048680984896989809135802276892911038588008701926729269812453226891776546037663583893625479252643042517196958990266376741676514631089466493864064316127648074609662749196545969926051 e = 65537 c = 98280456757136766244944891987028935843441533415613592591358482906016439563076150526116369842213103333480506705993633901994107281890187248495507270868621384652207697607019899166492132408348789252555196428608661320671877412710489782358282011364127799563335562917707783563681920786994453004763755404510541574502176243896756839917991848428091594919111448023948527766368304503100650379914153058191140072528095898576018893829830104362124927140555107994114143042266758709328068902664037870075742542194318059191313468675939426810988239079424823495317464035252325521917592045198152643533223015952702649249494753395100973534541766285551891859649320371178562200252228779395393974169736998523394598517174182142007480526603025578004665936854657294541338697513521007818552254811797566860763442604365744596444735991732790926343720102293453429936734206246109968817158815749927063561835274636195149702317415680401987150336994583752062565237605953153790371155918439941193401473271753038180560129784192800351649724465553733201451581525173536731674524145027931923204961274369826379325051601238308635192540223484055096203293400419816024111797903442864181965959247745006822690967920957905188441550106930799896292835287867403979631824085790047851383294389 p, q = fermat(n) print(f"{p = }") print(f"{q = }") d = inverse(e, (p-1)*(q-1)) print(long_to_bytes(pow(c, d, n))) if __name__ == '__main__': main() ``` > FLAG : crypto{f3rm47_w45_4_g3n1u5} ### 19. Marin's Secrets ![image](https://hackmd.io/_uploads/ryaqlWidp.png) - Source - [marin.py](https://cryptohack.org/static/challenges/marin_15d882fcfd597e1fb7785379b2529875.py) - [output.txt](https://cryptohack.org/static/challenges/output_f194012343666ced1a6699d196c8adc5.txt) - Bài này tôi sử dụng [FactorDB](http://factordb.com/index.php?query=658416274830184544125027519921443515789888264156074733099244040126213682497714032798116399288176502462829255784525977722903018714434309698108208388664768262754316426220651576623731617882923164117579624827261244506084274371250277849351631679441171018418018498039996472549893150577189302871520311715179730714312181456245097848491669795997289830612988058523968384808822828370900198489249243399165125219244753790779764466236965135793576516193213175061401667388622228362042717054014679032953441034021506856017081062617572351195418505899388715709795992029559042119783423597324707100694064675909238717573058764118893225111602703838080618565401139902143069901117174204252871948846864436771808616432457102844534843857198735242005309073939051433790946726672234643259349535186268571629077937597838801337973092285608744209951533199868228040004432132597073390363357892379997655878857696334892216345070227646749851381208554044940444182864026513709449823489593439017366358869648168238735087593808344484365136284219725233811605331815007424582890821887260682886632543613109252862114326372077785369292570900594814481097443781269562647303671428895764224084402259605109600363098950091998891375812839523613295667253813978434879172781217285652895469194181218343078754501694746598738215243769747956572555989594598180639098344891175879455994652382137038240166358066403475457) là ra flag. ```python! from Crypto.Util.number import * from factordb.factordb import FactorDB n = 658416274830184544125027519921443515789888264156074733099244040126213682497714032798116399288176502462829255784525977722903018714434309698108208388664768262754316426220651576623731617882923164117579624827261244506084274371250277849351631679441171018418018498039996472549893150577189302871520311715179730714312181456245097848491669795997289830612988058523968384808822828370900198489249243399165125219244753790779764466236965135793576516193213175061401667388622228362042717054014679032953441034021506856017081062617572351195418505899388715709795992029559042119783423597324707100694064675909238717573058764118893225111602703838080618565401139902143069901117174204252871948846864436771808616432457102844534843857198735242005309073939051433790946726672234643259349535186268571629077937597838801337973092285608744209951533199868228040004432132597073390363357892379997655878857696334892216345070227646749851381208554044940444182864026513709449823489593439017366358869648168238735087593808344484365136284219725233811605331815007424582890821887260682886632543613109252862114326372077785369292570900594814481097443781269562647303671428895764224084402259605109600363098950091998891375812839523613295667253813978434879172781217285652895469194181218343078754501694746598738215243769747956572555989594598180639098344891175879455994652382137038240166358066403475457 e = 65537 c = 400280463088930432319280359115194977582517363610532464295210669530407870753439127455401384569705425621445943992963380983084917385428631223046908837804126399345875252917090184158440305503817193246288672986488987883177380307377025079266030262650932575205141853413302558460364242355531272967481409414783634558791175827816540767545944534238189079030192843288596934979693517964655661507346729751987928147021620165009965051933278913952899114253301044747587310830419190623282578931589587504555005361571572561916866063458812965314474160499067525067495140150092119620928363007467390920130717521169105167963364154636472055084012592138570354390246779276003156184676298710746583104700516466091034510765027167956117869051938116457370384737440965109619578227422049806566060571831017610877072484262724789571076529586427405780121096546942812322324807145137017942266863534989082115189065560011841150908380937354301243153206428896320576609904361937035263985348984794208198892615898907005955403529470847124269512316191753950203794578656029324506688293446571598506042198219080325747328636232040936761788558421528960279832802127562115852304946867628316502959562274485483867481731149338209009753229463924855930103271197831370982488703456463385914801246828662212622006947380115549529820197355738525329885232170215757585685484402344437894981555179129287164971002033759724456 f = FactorDB(n) f.connect() [p,q] = f.get_factor_list() d = inverse(e,(p-1)*(q-1)) flag = pow(c, d, n ) print(long_to_bytes(flag)) ``` > FLAG : crypto{Th3se_Pr1m3s_4r3_t00_r4r3} ### 20. Fast Primes ![image](https://hackmd.io/_uploads/rkqixZoua.png) - Chall này cho ta - [fast_primes.py](https://cryptohack.org/static/challenges/fast_primes_d50f598035bc3bedfa9fcff8cc08ece7.py) - [key.pem](https://cryptohack.org/static/challenges/key_17a08b7040db46308f8b9a19894f9f95.pem) - [ciphertext.txt](https://cryptohack.org/static/challenges/ciphertext_98a448b6bbcd080909d235e5da5e9d56.txt) - Từ key.pem tôi có thể xuất ra n, e - tiếp đó chú ý đến đoạn mã hóa bằng [PKSC1](https://en.wikipedia.org/wiki/PKCS_1) ![image](https://hackmd.io/_uploads/rJPY_ajOp.png) - Giờ ta chỉ cần tìm private key d và giải mã theo ``PKCS1`` là ra flag. ```python3! import math import random from Crypto.Cipher import PKCS1_OAEP from Crypto.PublicKey import RSA from Crypto.Util.number import* from gmpy2 import is_prime from factordb.factordb import FactorDB key = RSA.importKey(open("key.pem", "rb").read()) print(key.exportKey) n = key.n e = key.e ciphertext = bytes.fromhex("249d72cd1d287b1a15a3881f2bff5788bc4bf62c789f2df44d88aae805b54c9a94b8944c0ba798f70062b66160fee312b98879f1dd5d17b33095feb3c5830d28") f = FactorDB(n) f.connect() [p, q] = (f.get_factor_list()) d = inverse(e,(p-1)*(q-1)) key = RSA.construct((n, e, d)) cipher = PKCS1_OAEP.new(key) flag = cipher.decrypt(ciphertext) print(flag) ``` > FLAG : crypto{p00R_3570n14} ### 21.Ron was Wrong, Whit is Right - Source - [excerpt.py](https://cryptohack.org/static/challenges/excerpt_fde5288e8de326c341ced61e9fea92ba.py) - [keys_and_messages.zip](https://cryptohack.org/static/challenges/keys_and_messages_701dba5b1a84cb168547ec18227a7740.zip) - Ở bài này tôi sẽ brute force key.pem và cipher từ 1 -> 50 sao cho xuất hiện format ``crypto{`` trong decrypt PKCS1 và lụm flag. ```python3! from Crypto.Cipher import PKCS1_OAEP from Crypto.PublicKey import RSA from factordb.factordb import FactorDB from Crypto.Util.number import* #msg = "???" for i in range(1, 50): print("decode " , i) with open(f"{i}.pem", 'r') as f: key = RSA.importKey(f.read()) print(key.exportKey) with open(f"{i}.ciphertext", "r") as f: c = f.read() try: n = key.n e = key.e f = FactorDB(n) f.connect() [p, q] = (f.get_factor_list()) except: continue d = pow(e,-1,(p-1)*(q-1)) print(f"{c = }") print(f"{n = }") print(f"{e = }") c = bytes.fromhex(c) print(c) key = RSA.construct((n,e,d)) cipher = PKCS1_OAEP.new(key) ciphertext = cipher.decrypt(c) if b"crypto{" in ciphertext: print(ciphertext) break ``` ### 22. RSA Backdoor Viability ![image](https://hackmd.io/_uploads/S1zMDnkt6.png) - Source - [complex_primes.py](https://cryptohack.org/static/challenges/complex_primes_2d261cc3ab7fb63530d172e045861190.py) - [output.txt](https://cryptohack.org/static/challenges/output_57c296f30a4d023c3c29f9b311da7c85.txt) - Với bài này số n đã có trong database của [factordb](http://factordb.com/) nên việc giải mã trở nên đơn giản ```python! #!/usr/bin/env python3 import random from Crypto.Util.number import bytes_to_long, getPrime, isPrime, long_to_bytes from factordb.factordb import FactorDB ''' FLAG = b"crypto{????????????????????????????????}" def get_complex_prime(): D = 427 while True: s = random.randint(2 ** 1020, 2 ** 1021 - 1) tmp = D * s ** 2 + 1 if tmp % 4 == 0 and isPrime((tmp // 4)): return tmp // 4 m = bytes_to_long(FLAG) p = get_complex_prime() q = getPrime(2048) n = p * q e = 0x10001 c = pow(m, e, n) print(f"n = {n}") print(f"e = {e}") print(f"c = {c}") ''' n = 709872443186761582125747585668724501268558458558798673014673483766300964836479167241315660053878650421761726639872089885502004902487471946410918420927682586362111137364814638033425428214041019139158018673749256694555341525164012369589067354955298579131735466795918522816127398340465761406719060284098094643289390016311668316687808837563589124091867773655044913003668590954899705366787080923717270827184222673706856184434629431186284270269532605221507485774898673802583974291853116198037970076073697225047098901414637433392658500670740996008799860530032515716031449787089371403485205810795880416920642186451022374989891611943906891139047764042051071647203057520104267427832746020858026150611650447823314079076243582616371718150121483335889885277291312834083234087660399534665835291621232056473843224515909023120834377664505788329527517932160909013410933312572810208043849529655209420055180680775718614088521014772491776654380478948591063486615023605584483338460667397264724871221133652955371027085804223956104532604113969119716485142424996255737376464834315527822566017923598626634438066724763559943441023574575168924010274261376863202598353430010875182947485101076308406061724505065886990350185188453776162319552566614214624361251463 e = 65537 c = 608484617316138126443275660524263025508135383745665175433229598517433030003704261658172582370543758277685547533834085899541036156595489206369279739210904154716464595657421948607569920498815631503197235702333017824993576326860166652845334617579798536442066184953550975487031721085105757667800838172225947001224495126390587950346822978519677673568121595427827980195332464747031577431925937314209391433407684845797171187006586455012364702160988147108989822392986966689057906884691499234298351003666019957528738094330389775054485731448274595330322976886875528525229337512909952391041280006426003300720547721072725168500104651961970292771382390647751450445892361311332074663895375544959193148114635476827855327421812307562742481487812965210406231507524830889375419045542057858679609265389869332331811218601440373121797461318931976890674336807528107115423915152709265237590358348348716543683900084640921475797266390455366908727400038393697480363793285799860812451995497444221674390372255599514578194487523882038234487872223540513004734039135243849551315065297737535112525440094171393039622992561519170849962891645196111307537341194621689797282496281302297026025131743423205544193536699103338587843100187637572006174858230467771942700918388 f = FactorDB(n) f.connect() [p, q] = (f.get_factor_list()) d = pow(e,-1,(p-1)*(q-1)) print(long_to_bytes(pow(c,d,n))) ``` > FLAG : crypto{I_want_to_Break_Square-free_4p-1} ### 23. Signing Server ![image](https://hackmd.io/_uploads/ryhmbH3da.png) - Source - ``nc socket.cryptohack.org 13374`` - [13374.py](https://cryptohack.org/static/challenges/13374_1455e06ebe824637f7c31c94a9eb58fa.py) - Với bài này cách làm khá đơn giản. - ![image](https://hackmd.io/_uploads/HJR-fS2Oa.png) - Khi ta chọn option ``{'option': 'get_secret'}`` thì server sẽ trả mã hóa của flag : ``c = m ^ e (modN)`` - Khi ta gửi lại ciphertext cho server qua ``{'option': 'sign', 'msg': ciphertext}`` khi đó server sẽ giải mã luôn cho ta: ``flag = ciphertext ^ D (modN)`` - Như vậy bài này đã được giải quyết. ```python! from Crypto.Util.number import* from pwn import * import json f = connect("socket.cryptohack.org", 13374) f.recvline() f.sendline(json.dumps({'option': 'get_secret'})) recv = json.loads(f.recvline().decode()) ciphertext = recv['secret'][2:] f.sendline(json.dumps({'option': 'sign', 'msg': ciphertext}).encode()) recv = json.loads(f.recvline().decode()) flag = int(recv["signature"][2:], 16) print(long_to_bytes(flag)) f.close() ``` > FLAG : crypto{d0n7_516n_ju57_4ny7h1n6} ### 24. Blinding Light - ![image](https://hackmd.io/_uploads/rkB9kDpup.png) - Source - ``nc socket.cryptohack.org 13376`` - [13376.py](https://cryptohack.org/static/challenges/13376_f33b73edaadf6e553906fb0fc2b79385.py) - Với bài này tôi sử dụng ``blinding attack`` có viết ở trên. - Ở đây đầu tiên tôi chọn ``r=5`` sau đó tôi cho ``M' = ( r^e * M ) % N`` và gửi vào cho server kí. - Khi đó server sẽ trả về ``S’ = (M’)^d (mod N) = (r^e M)^d (mod N) = r^ed * M^d (mod N) = r * M^d (mod N)`` - Tiếp đó tôi sẽ chia nó cho ``r=5`` là sẽ có ``c = S'/r = m^d (modN)`` và ``verified = c^e (modN) = ADMIN_TOKEN`` và gửi lại vào server ![image](https://hackmd.io/_uploads/SyuqGDpdp.png) sẽ trả về flag. ```python! from Crypto.Util.number import * from pwn import * from json import * ADMIN_TOKEN = b"admin=True" f = connect('socket.cryptohack.org', 13376) f.recvline() f.sendline(dumps({"option": "get_pubkey"})) recv = loads(f.recvline()) N = int(recv["N"], 16) e = int(recv["e"], 16) m = bytes_to_long(ADMIN_TOKEN) # m = 459922107199558918501733 r = 5 m2 = (m* r**e) % N f.sendline(dumps({"option": "sign", "msg": hex(m2)[2:]})) recv = loads(f.recvline()) msg = int(recv["msg"], 16) signature = int(recv["signature"], 16)# s2 #s = (s2//r) % n s = signature * inverse(r,N) % N f.sendline(dumps({"option": "verify", "msg": hex(m)[2:],"signature": hex(s)[2:] })) print(f.recvline()) ``` > FLAG : crypto{m4ll34b1l17y_c4n_b3_d4n63r0u5} ### 25.Let's Decrypt - ![image](https://hackmd.io/_uploads/Syngu60Y6.png) - Source: [13391.py](https://cryptohack.org/static/challenges/13391_410b65ffd09d75b4c9fc4fe11bfdec46.py) - Với bài này tôi chỉ cần để ý tới chỗ này ![image](https://hackmd.io/_uploads/Sk_Wd6RtT.png) - Ta chỉ cần chọn số e và n phù hợp với yêu cầu đề bài. - ở đây tôi sẽ gửi ``msg = b"I am MalloryWe own CryptoHack.org"`` - Nhận thấy ``msg < signature`` - Khi đó tôi có$$signature \ mod \ (signature - m) \ = \ signature - (signature - m) = m$$ luôn đúng với ``GCD(signature, m) == 1`` hay $$(signature - m) = k*(signature - m)$$ - Tôi chọn e = 1, ta có$$ signature ≡ m ≡ m^1 \ (mod \ signature - m)$$ - Bây giờ tôi chỉ cần gửi - N = signature - m - e = 1 - Code ```python3! from pkcs1 import emsa_pkcs1_v15 from Crypto.Util.number import* from pwn import* import json r = connect("socket.cryptohack.org", 13391) r.recvline() msg = 'I am MalloryWe own CryptoHack.org' digest = bytes_to_long(emsa_pkcs1_v15.encode(msg.encode(), 256)) r.sendline(json.dumps({'option': 'get_signature'})) data = json.loads(r.recvline()) n = int(data["N"][2:], 16) e = int(data["e"][2:], 16) signature = int(data["signature"][2:], 16) print(GCD(bytes_to_long(b"I am MalloryWe own CryptoHack.org"), signature)) ## =1 thỏa điều kiện print(n) print(e) print(signature) send = {'option': 'verify', 'msg': msg, 'e': hex(1)[2:], 'N': hex(signature - digest)[2:]} send = json.dumps(send).encode() r.sendline(send) print(send) print(r.recvline()) r.close() ``` > FLAG : crypto{dupl1c4t3_s1gn4tur3_k3y_s3l3ct10n} ## Reference - https://bitsdeep.com/posts/attacking-rsa-for-fun-and-ctf-points-part-1/ (part-2, part-3, part-4) - https://crypto.stanford.edu/~dabo/pubs/papers/RSA-survey.pdf - https://en.wikipedia.org/wiki/RSA_(cryptosystem) - https://en.wikipedia.org/wiki/Chinese_remainder_theorem#:~:text=In%20mathematics%2C%20the%20Chinese%20remainder,are%20pairwise%20coprime%20(no%20two) - https://github.com/defund/coppersmith/tree/master - https://cr.yp.to/bib/2001/coppersmith.pdf