Hiiiiii, writeup này sẽ là ghi chép của mình trong quá trình hoàn thiện các challenge về **RSA Cryptosystem** ở web Cryptohack nha.
> *Bài này mình sẽ vừa giải các bài ở trang web, vừa giải thích và thêm một số video hoặc tài liệu mình đã nghiên cứu để hoàn thiện các challenge.*
# Lesson 1: Modular Exponentiation (Phép toán modulo)
> Bài này sẽ nhắc lại về việc ứng dụng phép toán modulo trong việc sử dụng thuật toán RSA. Để có thể hiểu sâu các bài học, mình khuyến nghị các bạn hoàn thành course Modular Arithmetic trước khi đi sâu tìm hiểu các nội dung tiếp theo.
Nội dung cụ thể của bài học như sau:
Mình sẽ có một bài blog cụ thể hơn về RSA. Tuy nhiên tóm gọn lại là, trong bài này có 3 ý cần nắm rõ:
* Một là, trong thuật toán bảo mật RSA, các phép tính modulo sẽ được ứng dụng khá nhiều. Việc ứng dụng phép toán modulo để có thể tạo ra các "khóa cửa sập" với khả năng mã hóa ưu việt.
* Ngôn ngữ Python có function giúp thực hiện các phép toán modulo với cú pháp như sau: `pow(base, exponent, modulus)`.
Chốt lại là vẫn phải học toán, và đề bài là sử dụng hàm pow để giải quyết phép tính kia.
Là một bài toán đơn giản, vì thế mà cách giải quyết cũng sẽ đơn giản:
`print(101, 17, 22663)`
> Với 101 là cơ số (base), 17 là số mũ (exponent), 22663 là modulo .
# Lesson 2: Public Keys (Khóa công khai)
Mã hóa RSA được cấu thành từ phép modulo với số mũ **e** và một modulo **N** với N là kết quả của phép nhân hai số nguyên tố **N = p.q**.
Số mũ e và modulo N cùng nhau tạo nên một "khóa công khai" trong thuật toán mã hóa RSA.
Những thông tin này được giải thích trong đề bài sau:
Đề bài đi kèm yêu cầu: *mã hóa số 12 sử dụng số mũ **e = 65537** và các số nguyên tố **p = 17** và **q = 23***.
Trước tiên, mình sẽ đi tìm modulo bằng cách nhân 2 số p và q với nhau để có được cặp số mã hóa công khai (N,e). Và con số sau mã hóa (ciphertext) mà mình cần tìm thì ta sẽ sử dụng hàm pow() đã được đề cập ở bài trước. Đoạn code mình viết như sau:
```
#Nhập liệu
message = 12
exponent = 65537
p = 17
q = 23
#Thực hiện lần lượt các thao tác
#tính toán số N (modulus), phép toán đồng dư
#để tìm ra ciphertext.
modulus = p * q
ciphertext = pow(message, exponent, modulus)
#In kết quả
print(ciphertext)
```
Kết quả nhận về là con số 301.
# Lesson 3: Euler's Totient (Hàm phi Euler)
Như đã nhắc lại ở trên, RSA là thuật toán sử dụng phép toán modulo để mã hóa, vì thế độ phức tạp của mã hóa phụ thuộc vào độ khó của việc phân tích modulo **N**. Nếu N có thể bị phân tích thành các thừa số nguyên tố, chúng ta có thể tìm ra phi Euler của **N** và từ đó giải mã được đoạn mã.
Để có thể làm được bài này, thì ta cần đi sâu vào tìm hiểu về **Euler totient** hay hàm phi Euler.
> Hàm phi Euler, hay phi hàm Euler, được sử dụng để tìm số lượng số nguyên tố cùng nhau với một số n. Nội dung cụ thể của hàm phi Euler với số N được phân tích thành tích của các số nguyên tố p1, p2... p(n) cụ thể như sau:
> 
> Đó là nội dung cụ thể của phi hàm Euler. Bên cạnh đó còn đi kèm với 1 số tính chất sẽ được đào sâu ứng dụng trong những bài toán sau.
Phía trên là phần tóm tắt kiến thức, dưới đây sẽ là phần đề bài:
Cùng với phần kiến thức phía trên, ta đi đến phần giải quyết vấn đề được đưa ra bằng coding.
> Cho số nguyên N được tạo thành từ tích hai số nguyên tố p và q. Tìm phi Euler của N.
```
p = 857504083339712752489993810777
q = 1029224947942998075080348647219
euler = (p-1)*(q-1)
print(euler)
```
*Dựa vào phần kiến thức tổng quát, trường hợp được đưa ra giải quyết là trường hợp số nguyên là tích của chỉ 2 thừa số nguyên tố, nên mình quyết định chỉ đơn thuần áp dụng nguyên phần tính toán đơn giản cho 2 phần số này thay vì tạo 1 vòng lặp như với trường hợp nhiều thừa số.*
# Lesson 4: Private Keys (Khóa bí mật)
Ở trên chúng ta đã nói về **Khóa công khai (Public Keys)**, là 1 phần trong 2 khóa của hệ bảo mật RSA. **Khóa công khai** được bên gửi sử dụng để mã hóa thông tin cần được trao đổi, còn đôi với **Khóa bí mật** được sử dụng để giải mã trong hệ mã RSA. Đây cũng chính là "cơ chế cửa sập" (trapdoor) được nói đến khi nói về tính ưu việt của hệ mã RSA. Và khi nói đến **Khóa bí mật** trong hệ mã RSA, ta sẽ ứng dụng hàm phi Euler vừa được sử dụng ở bài trước.
Khóa bí mật **d** trong hệ mã RSA chính là ***nghịch đảo modulo*** (tìm hiểu trong course **Modular Arithmetic**) của số mũ **e** và modulo là hàm phi Euler của số **N**.
Phần kiến thức trên gói trong đề bài sau, kèm với đó là một bài toán liên quan:
Yay, kết hợp nghịch đảo modulo và phi hàm Euler:
```
p = 857504083339712752489993810777
q = 1029224947942998075080348647219
e = 65537
euler = (p-1)*(q-1)
print(pow(e, -1, euler))
```
Kết quả dài vai~ nên thôi không viết ra nhá =)))
# Lesson 5: RSA Decryption (Giải mã RSA)
Ứng dụng những gì đã biết ở trên thì ta sẽ thực hiện challenge về giải mã khóa RSA.
Đề bài cung cấp Khóa công khai và Khóa bảo mật, yêu cầu giải mã dãy cho sẵn. Khóa công khai đã được cho sẵn, khóa bảo mật được sử dụng từ bài trước (Lesson 4).
Mình sẽ tổng hợp dữ liệu mình đã có nhé:
```
#Khóa công khai được cho mới
N = 882564595536224140639625987659416029426239230804614613279163
c = 77578995801157823671636298847186723593814843845525223303932
#Khóa bảo mật đã cho ở bài trước:
d = 121832886702415731577073962957377780195510499965398469843281
```
Bắt đầu thôi. từ những dữ liệu ở trên, ta áp dụng vào công thức:
```
N = 882564595536224140639625987659416029426239230804614613279163
c = 77578995801157823671636298847186723593814843845525223303932
d = 121832886702415731577073962957377780195510499965398469843281
text = pow( c, d, N )
print(text)
```
Output sẽ là `13371337`.
# Lesson 6: RSA Signatures (Chữ kí số RSA)
Một trong những ứng dụng của RSA trong bảo mật chính là tạo ra các chữ kí số. Và chữ ký số trong RSA thực sự là "số". Đúng, nó là 1 con số được sử dụng để thành 1 "chữ ký", xác thực chính chủ người tạo ra thông tin hay tạo ra bản mã hóa.
Chữ kí số RSA sử dụng hàm băm (hash, trong challenge này sẽ là SHA256). Và trong thư viện Pycryptodome cũng đã có sẵn function để làm việc với hàm băm này. Vậy nên ta sẽ sử dụng nó.
```
#Import các chức năng cần thiết
from Crypto.Hash import SHA256
from Crypto.Util.number import bytes_to_long
#Các khóa RSA được cấp
n = 15216583654836731327639981224133918855895948374072384050848479908982286890731769486609085918857664046075375253168955058743185664390273058074450390236774324903305663479046566232967297765731625328029814055635316002591227570271271445226094919864475407884459980489638001092788574811554149774028950310695112688723853763743238753349782508121985338746755237819373178699343135091783992299561827389745132880022259873387524273298850340648779897909381979714026837172003953221052431217940632552930880000919436507245150726543040714721553361063311954285289857582079880295199632757829525723874753306371990452491305564061051059885803
d = 11175901210643014262548222473449533091378848269490518850474399681690547281665059317155831692300453197335735728459259392366823302405685389586883670043744683993709123180805154631088513521456979317628012721881537154107239389466063136007337120599915456659758559300673444689263854921332185562706707573660658164991098457874495054854491474065039621922972671588299315846306069845169959451250821044417886630346229021305410340100401530146135418806544340908355106582089082980533651095594192031411679866134256418292249592135441145384466261279428795408721990564658703903787956958168449841491667690491585550160457893350536334242689
#Thiết lập hàm băm
hash = SHA256.new(data=b'crypto{Immut4ble_m3ssag1ng}')
#Tạo chữ kí số
s = pow(bytes_to_long(hash.digest()), d, n)
#Chuyển định dạng dữ liệu sang HEX
h = hex(s)
print(int(h,16))
```
# Lesson 7: Factoring (Phân tích số)
Trong mã hóa RSA, ta cần sử dụng các số nguyên tố (Primes) trong việc mã hóa, giải mã. Khi công nghệ phát triển, các máy tính trở nên nhanh hơn, mạnh mẽ hơn, việc bảo mật yêu cầu trở nên phức tạp hơn để có thể phòng tránh nguy cơ bị giải mã quá dễ dàng với những công cụ ngày càng tinh vi và phức tạp. Vì thế, một phương pháp để tăng độ phức tạp cho mã khóa hay làm cho khóa trở nên "khó đoán, khó mò" hơn đó là sử dụng các số lớn hơn, dài hơn và phức tạp hơn.
Ngày nay, những con số được sử dụng trong mã hóa được khuyên dùng có độ dài 1024 bits, và nhân bản lên để có modulo 2048 bits. Những khóa RSA có số modulo 2048 bits được gọi là RSA-2048.
Challenge này yêu cầu phân tích một số khá lớn, chạy vòng lặp khá là khó khăn nên mình sẽ dùng tool. Tool mình sử dụng sẽ là `factordb.com`.
Số bé hơn mình nhận được sẽ là `19704762736204164635843`.
Hoặc một cách khác nữa đó là sử dụng Sagemath:
# Lesson 8: Monoprime
Vấn đề đặt ra là tại sao ta lại cần đến 2 số p và q để tạo ra khóa N?
Chal file được cho sẵn như sau:
```
n = 171731371218065444125482536302245915415603318380280392385291836472299752747934607246477508507827284075763910264995326010251268493630501989810855418416643352631102434317900028697993224868629935657273062472544675693365930943308086634291936846505861203914449338007760990051788980485462592823446469606824421932591
e = 65537
ct = 161367550346730604451454756189028938964941280347662098798775466019463375610700074840105776873791605070092554650190486030367121011578171525759600774739890458414593857709994072516290998135846956596662071379067305011746842247628316996977338024343628757374524136260758515864509435302781735938531030576289086798942
```
Có số `n`, có `e`, và thêm 1 tham số `ct`. Có vẻ tham số n được cho sẵn chính là số *N* trong vấn đề được đặt ra trong đề. Dùng công cụ được sử dụng ở bài trước để phân tích số n thì ta thấy n là số nguyên tố. Suy ra, `p = n` và `q = 1`.
Và có lẽ, bài này sẽ là giải mã để nhận flag từ tham số `ct` kia.
```
from Crypto.Util.number import long_to_bytes
n = 171731371218065444125482536302245915415603318380280392385291836472299752747934607246477508507827284075763910264995326010251268493630501989810855418416643352631102434317900028697993224868629935657273062472544675693365930943308086634291936846505861203914449338007760990051788980485462592823446469606824421932591
e = 65537
ct = 161367550346730604451454756189028938964941280347662098798775466019463375610700074840105776873791605070092554650190486030367121011578171525759600774739890458414593857709994072516290998135846956596662071379067305011746842247628316996977338024343628757374524136260758515864509435302781735938531030576289086798942
p = 1
q = n
phi = (q-1)
d = pow(e,-1,phi)
decrypt = pow(ct,d,n)
print(long_to_bytes(decrypt))
```
Và output ta nhận được là flag: `crypto{0n3_pr1m3_41n7_pr1m3_l0l}`
# Lesson 9: Manyprime
Câu hỏi ở bài trước đã được giải đáp, và đến đây là một câu hỏi khác: Nếu ta dùng trên 30 thừa số để tạo số N thì sao?
Độ khó bài này ở chỗ sử dụng tận 30 số.
Ban đầu mình đã định sử dụng sagemath để phân tích số N, tuy nhiên có một số vấn đề gì đó nên k ra được output (có lẽ do số quá lớn). Tiếp tục sử dụng factordb.com, tách số N để nhận được các thừa số nguyên tố, ta được kết quả:
*Trông kinh khủng vcl.*
Nhưng thôi, chúng ta sẽ lấy hết đống đấy, tuy nhiên sẽ cho hết vào 1 mảng để tiện cho việc quản lí.
Có đủ các thành phần, mình sẽ đi tính toán thôi.
```
from Crypto.Util.number import long_to_bytes
n = 580642391898843192929563856870897799650883152718761762932292482252152591279871421569162037190419036435041797739880389529593674485555792234900969402019055601781662044515999210032698275981631376651117318677368742867687180140048715627160641771118040372573575479330830092989800730105573700557717146251860588802509310534792310748898504394966263819959963273509119791037525504422606634640173277598774814099540555569257179715908642917355365791447508751401889724095964924513196281345665480688029639999472649549163147599540142367575413885729653166517595719991872223011969856259344396899748662101941230745601719730556631637
e = 65537
ct = 320721490534624434149993723527322977960556510750628354856260732098109692581338409999983376131354918370047625150454728718467998870322344980985635149656977787964380651868131740312053755501594999166365821315043312308622388016666802478485476059625888033017198083472976011719998333985531756978678758897472845358167730221506573817798467100023754709109274265835201757369829744113233607359526441007577850111228850004361838028842815813724076511058179239339760639518034583306154826603816927757236549096339501503316601078891287408682099750164720032975016814187899399273719181407940397071512493967454225665490162619270814464
euler = 1
factorize = [ 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,]
for i in factorize:
euler*=(i-1)
d = pow(e,-1,euler)
decrypt = pow(ct,d,n)
print(long_to_bytes(decrypt))
```
Output đẹp vai: `crypto{700_m4ny_5m4ll_f4c70r5}`
> *Nói chung là nhiều cũng không tốt*.
# Lesson 10: Inferious Prime:
Bài được đính kèm 2 file như sau:
```
#!/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
```
và một file txt:
```
n = 984994081290620368062168960884976209711107645166770780785733
e = 65537
ct = 948553474947320504624302879933619818331484350431616834086273
```
Chúng ta sẽ thử factor `n`, sẽ ra p và q:
Phân tích sơ qua file code được cho thì ta thấy quy trình mã hóa như sau:
Flag được chuyển hóa thành long với `bytes_to_long()`, được encrypt với khóa `(e,n)` tạo thành tham số `pt`. Sau đó tham số `pt` lại được mã hóa 1 lần nữa với khóa `(d,n)` với `d` được đảo từ `(e, phi)`.
Đến đây chiến được ròi, ta sẽ đảo ngược lại quá trình này, đi từ dưới lên trên:
```
from Crypto.Util.number import inverse, bytes_to_long, long_to_bytes
p, q = 752708788837165590355094155871, 986369682585281993933185289261
#Tìm các tham số cần thiết
n, phi = p * q, (p - 1) * (q - 1)
e = 3
d = inverse(e, phi)
ct = 39207274348578481322317340648475596807303160111338236677373
print(long_to_bytes(pow(ct, d, n)))
```
Output sẽ là: `crypto{N33d_b1g_pR1m35}`
# Lesson 11: Square Eyes
Vẫn sẽ là một file output.txt dài ngoằng:
```
n = 535860808044009550029177135708168016201451343147313565371014459027743491739422885443084705720731409713775527993719682583669164873806842043288439828071789970694759080842162253955259590552283047728782812946845160334801782088068154453021936721710269050985805054692096738777321796153384024897615594493453068138341203673749514094546000253631902991617197847584519694152122765406982133526594928685232381934742152195861380221224370858128736975959176861651044370378539093990198336298572944512738570839396588590096813217791191895941380464803377602779240663133834952329316862399581950590588006371221334128215409197603236942597674756728212232134056562716399155080108881105952768189193728827484667349378091100068224404684701674782399200373192433062767622841264055426035349769018117299620554803902490432339600566432246795818167460916180647394169157647245603555692735630862148715428791242764799469896924753470539857080767170052783918273180304835318388177089674231640910337743789750979216202573226794240332797892868276309400253925932223895530714169648116569013581643192341931800785254715083294526325980247219218364118877864892068185905587410977152737936310734712276956663192182487672474651103240004173381041237906849437490609652395748868434296753449
e = 65537
ct = 222502885974182429500948389840563415291534726891354573907329512556439632810921927905220486727807436668035929302442754225952786602492250448020341217733646472982286222338860566076161977786095675944552232391481278782019346283900959677167026636830252067048759720251671811058647569724495547940966885025629807079171218371644528053562232396674283745310132242492367274184667845174514466834132589971388067076980563188513333661165819462428837210575342101036356974189393390097403614434491507672459254969638032776897417674577487775755539964915035731988499983726435005007850876000232292458554577437739427313453671492956668188219600633325930981748162455965093222648173134777571527681591366164711307355510889316052064146089646772869610726671696699221157985834325663661400034831442431209123478778078255846830522226390964119818784903330200488705212765569163495571851459355520398928214206285080883954881888668509262455490889283862560453598662919522224935145694435885396500780651530829377030371611921181207362217397805303962112100190783763061909945889717878397740711340114311597934724670601992737526668932871436226135393872881664511222789565256059138002651403875484920711316522536260604255269532161594824301047729082877262812899724246757871448545439896
```
Đề bài có đi kèm gợi ý khi phải ứng dụng hàm phi Euler. Thử phân tích số n ra thì mình được kết quả như sau:
Có thể thấy `n = p^2`, ta nghĩ ngay đến *Square Root*. Khi ấy ta có giá trị của phi Euler N = `p(p-1)`
```
from Crypto.Util.number import *
n = 535860808044009550029177135708168016201451343147313565371014459027743491739422885443084705720731409713775527993719682583669164873806842043288439828071789970694759080842162253955259590552283047728782812946845160334801782088068154453021936721710269050985805054692096738777321796153384024897615594493453068138341203673749514094546000253631902991617197847584519694152122765406982133526594928685232381934742152195861380221224370858128736975959176861651044370378539093990198336298572944512738570839396588590096813217791191895941380464803377602779240663133834952329316862399581950590588006371221334128215409197603236942597674756728212232134056562716399155080108881105952768189193728827484667349378091100068224404684701674782399200373192433062767622841264055426035349769018117299620554803902490432339600566432246795818167460916180647394169157647245603555692735630862148715428791242764799469896924753470539857080767170052783918273180304835318388177089674231640910337743789750979216202573226794240332797892868276309400253925932223895530714169648116569013581643192341931800785254715083294526325980247219218364118877864892068185905587410977152737936310734712276956663192182487672474651103240004173381041237906849437490609652395748868434296753449
e = 65537
ct = 222502885974182429500948389840563415291534726891354573907329512556439632810921927905220486727807436668035929302442754225952786602492250448020341217733646472982286222338860566076161977786095675944552232391481278782019346283900959677167026636830252067048759720251671811058647569724495547940966885025629807079171218371644528053562232396674283745310132242492367274184667845174514466834132589971388067076980563188513333661165819462428837210575342101036356974189393390097403614434491507672459254969638032776897417674577487775755539964915035731988499983726435005007850876000232292458554577437739427313453671492956668188219600633325930981748162455965093222648173134777571527681591366164711307355510889316052064146089646772869610726671696699221157985834325663661400034831442431209123478778078255846830522226390964119818784903330200488705212765569163495571851459355520398928214206285080883954881888668509262455490889283862560453598662919522224935145694435885396500780651530829377030371611921181207362217397805303962112100190783763061909945889717878397740711340114311597934724670601992737526668932871436226135393872881664511222789565256059138002651403875484920711316522536260604255269532161594824301047729082877262812899724246757871448545439896
p = 23148667521998097720857168827790771337662483716348435477360567409355026169165934446949809664595523770853897203103759106983985113264049057416908191166720008503275951625738975666019029172377653170602440373579593292576530667773951407647222757756437867216095193174201323278896027294517792607881861855264600525772460745259440301156930943255240915685718552334192230264780355799179037816026330705422484000086542362084006958158550346395941862383925942033730030004606360308379776255436206440529441711859246811586652746028418496020145441513037535475380962562108920699929022900677901988508936509354385660735694568216631382653107
phi = p*(p-1)
d = inverse(e,phi)
m = pow(ct,d,n)
print(long_to_bytes(m))
```
Và đó, output của ta sẽ là:`crypto{squar3_r00t_i5_f4st3r_th4n_f4ct0r1ng!}`
# Lesson 12: Salty (Mặn!?)
Man no way, nghe cái đề bài k liên quan lắm.
Những thừa số nhỏ hơn thì code chạy nhanh hơn? Đúng, nhưng mà có lẽ không nên.
Vẫn cho file output với các số n, e, ct. Nhưng đã có thêm một file python nữa. Điều đặc biệt ở đây là `e = 1`.
```
n = 110581795715958566206600392161360212579669637391437097703685154237017351570464767725324182051199901920318211290404777259728923614917211291562555864753005179326101890427669819834642007924406862482343614488768256951616086287044725034412802176312273081322195866046098595306261781788276570920467840172004530873767
e = 1
ct = 44981230718212183604274785925793145442655465025264554046028251311164494127485
```
Không cần quan tâm lắm, chuyển `ct` sang bytes chắc chắn được flag (vì `e = 1`).
Và nó đúng thế thật :v
```
from Crypto.Util.number import long_to_bytes
n = 110581795715958566206600392161360212579669637391437097703685154237017351570464767725324182051199901920318211290404777259728923614917211291562555864753005179326101890427669819834642007924406862482343614488768256951616086287044725034412802176312273081322195866046098595306261781788276570920467840172004530873767
e = 1
ct = 44981230718212183604274785925793145442655465025264554046028251311164494127485
print(long_to_bytes(ct))
```
Output nè: `crypto{saltstack_fell_for_this!}`
# Lesson 13: Modulus Inutilis
Lần này thì e k còn bằng 1 nữa:
```
n = 17258212916191948536348548470938004244269544560039009244721959293554822498047075403658429865201816363311805874117705688359853941515579440852166618074161313773416434156467811969628473425365608002907061241714688204565170146117869742910273064909154666642642308154422770994836108669814632309362483307560217924183202838588431342622551598499747369771295105890359290073146330677383341121242366368309126850094371525078749496850520075015636716490087482193603562501577348571256210991732071282478547626856068209192987351212490642903450263288650415552403935705444809043563866466823492258216747445926536608548665086042098252335883
e = 3
ct = 243251053617903760309941844835411292373350655973075480264001352919865180151222189820473358411037759381328642957324889519192337152355302808400638052620580409813222660643570085177957
```
Với e = 3, flag sẽ chính là căn bậc 3 của `ct`, tương tự như bài trước. Ở đây mình sử dụng function cbrt (hàm tìm căn bậc 3).
```
from sympy import cbrt
from Crypto.Util.number import long_to_bytes
n = 17258212916191948536348548470938004244269544560039009244721959293554822498047075403658429865201816363311805874117705688359853941515579440852166618074161313773416434156467811969628473425365608002907061241714688204565170146117869742910273064909154666642642308154422770994836108669814632309362483307560217924183202838588431342622551598499747369771295105890359290073146330677383341121242366368309126850094371525078749496850520075015636716490087482193603562501577348571256210991732071282478547626856068209192987351212490642903450263288650415552403935705444809043563866466823492258216747445926536608548665086042098252335883
e = 3
ct = 243251053617903760309941844835411292373350655973075480264001352919865180151222189820473358411037759381328642957324889519192337152355302808400638052620580409813222660643570085177957
flag= cbrt(ct)
print(long_to_bytes(flag))
```
Output chính là `crypto{N33d_m04R_p4dd1ng}`.
# Lesson 14: Everything is big!
Vẫn cho file output, vẫn cho một file python. Phân tích kĩ file python để hiểu cách mã hóa, ta thấy số d sẽ nhỏ, vì thế ta sẽ sử dụng Wiener attack.
```
#!/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)}')
```
```
N = 0xb8af3d3afb893a602de4afe2a29d7615075d1e570f8bad8ebbe9b5b9076594cf06b6e7b30905b6420e950043380ea746f0a14dae34469aa723e946e484a58bcd92d1039105871ffd63ffe64534b7d7f8d84b4a569723f7a833e6daf5e182d658655f739a4e37bd9f4a44aff6ca0255cda5313c3048f56eed5b21dc8d88bf5a8f8379eac83d8523e484fa6ae8dbcb239e65d3777829a6903d779cd2498b255fcf275e5f49471f35992435ee7cade98c8e82a8beb5ce1749349caa16759afc4e799edb12d299374d748a9e3c82e1cc983cdf9daec0a2739dadcc0982c1e7e492139cbff18c5d44529407edfd8e75743d2f51ce2b58573fea6fbd4fe25154b9964d
e = 0x9ab58dbc8049b574c361573955f08ea69f97ecf37400f9626d8f5ac55ca087165ce5e1f459ef6fa5f158cc8e75cb400a7473e89dd38922ead221b33bc33d6d716fb0e4e127b0fc18a197daf856a7062b49fba7a86e3a138956af04f481b7a7d481994aeebc2672e500f3f6d8c581268c2cfad4845158f79c2ef28f242f4fa8f6e573b8723a752d96169c9d885ada59cdeb6dbe932de86a019a7e8fc8aeb07748cfb272bd36d94fe83351252187c2e0bc58bb7a0a0af154b63397e6c68af4314601e29b07caed301b6831cf34caa579eb42a8c8bf69898d04b495174b5d7de0f20cf2b8fc55ed35c6ad157d3e7009f16d6b61786ee40583850e67af13e9d25be3
c = 0x3f984ff5244f1836ed69361f29905ca1ae6b3dcf249133c398d7762f5e277919174694293989144c9d25e940d2f66058b2289c75d1b8d0729f9a7c4564404a5fd4313675f85f31b47156068878e236c5635156b0fa21e24346c2041ae42423078577a1413f41375a4d49296ab17910ae214b45155c4570f95ca874ccae9fa80433a1ab453cbb28d780c2f1f4dc7071c93aff3924d76c5b4068a0371dff82531313f281a8acadaa2bd5078d3ddcefcb981f37ff9b8b14c7d9bf1accffe7857160982a2c7d9ee01d3e82265eec9c7401ecc7f02581fd0d912684f42d1b71df87a1ca51515aab4e58fab4da96e154ea6cdfb573a71d81b2ea4a080a1066e1bc3474
```
> Wiener's attack là một loại tấn công mật mã nhằm vào hệ thống RSA, được đặt theo tên của nhà mật mã học Michael J. Wiener. Cách này sử dụng pp phân số liên tục (continuos fraction) để tìm ra khóa bí mật d khi giá trị d nhỏ. Lí do ta nên sử dụng phương pháp này ở bài này là vì giá trị của e khá lớn dẫn đến giá trị d sẽ nhỏ => phù hợp với phương pháp.
Để code lại thì khá phức tạp, vì thế ta sẽ sử dụng thư viện có sẵn:
```
import owiener
from Crypto.Util.number import long_to_bytes
N = int('0xb8af3d3afb893a602de4afe2a29d7615075d1e570f8bad8ebbe9b5b9076594cf06b6e7b30905b6420e950043380ea746f0a14dae34469aa723e946e484a58bcd92d1039105871ffd63ffe64534b7d7f8d84b4a569723f7a833e6daf5e182d658655f739a4e37bd9f4a44aff6ca0255cda5313c3048f56eed5b21dc8d88bf5a8f8379eac83d8523e484fa6ae8dbcb239e65d3777829a6903d779cd2498b255fcf275e5f49471f35992435ee7cade98c8e82a8beb5ce1749349caa16759afc4e799edb12d299374d748a9e3c82e1cc983cdf9daec0a2739dadcc0982c1e7e492139cbff18c5d44529407edfd8e75743d2f51ce2b58573fea6fbd4fe25154b9964d',16)
e = int('0x9ab58dbc8049b574c361573955f08ea69f97ecf37400f9626d8f5ac55ca087165ce5e1f459ef6fa5f158cc8e75cb400a7473e89dd38922ead221b33bc33d6d716fb0e4e127b0fc18a197daf856a7062b49fba7a86e3a138956af04f481b7a7d481994aeebc2672e500f3f6d8c581268c2cfad4845158f79c2ef28f242f4fa8f6e573b8723a752d96169c9d885ada59cdeb6dbe932de86a019a7e8fc8aeb07748cfb272bd36d94fe83351252187c2e0bc58bb7a0a0af154b63397e6c68af4314601e29b07caed301b6831cf34caa579eb42a8c8bf69898d04b495174b5d7de0f20cf2b8fc55ed35c6ad157d3e7009f16d6b61786ee40583850e67af13e9d25be3',16)
c = int('0x3f984ff5244f1836ed69361f29905ca1ae6b3dcf249133c398d7762f5e277919174694293989144c9d25e940d2f66058b2289c75d1b8d0729f9a7c4564404a5fd4313675f85f31b47156068878e236c5635156b0fa21e24346c2041ae42423078577a1413f41375a4d49296ab17910ae214b45155c4570f95ca874ccae9fa80433a1ab453cbb28d780c2f1f4dc7071c93aff3924d76c5b4068a0371dff82531313f281a8acadaa2bd5078d3ddcefcb981f37ff9b8b14c7d9bf1accffe7857160982a2c7d9ee01d3e82265eec9c7401ecc7f02581fd0d912684f42d1b71df87a1ca51515aab4e58fab4da96e154ea6cdfb573a71d81b2ea4a080a1066e1bc3474',16)
d = owiener.attack(e,N)
m = pow(c,d,N)
print(long_to_bytes(m))
```
Output: `crypto{s0m3th1ng5_c4n_b3_t00_b1g}`
# Lesson 15: Crossed Wires:
Một challenge khác, cũng gồm 1 file source và một file output:
```
My private key: (21711308225346315542706844618441565741046498277716979943478360598053144971379956916575370343448988601905854572029635846626259487297950305231661109855854947494209135205589258643517961521594924368498672064293208230802441077390193682958095111922082677813175804775628884377724377647428385841831277059274172982280545237765559969228707506857561215268491024097063920337721783673060530181637161577401589126558556182546896783307370517275046522704047385786111489447064794210010802761708615907245523492585896286374996088089317826162798278528296206977900274431829829206103227171839270887476436899494428371323874689055690729986771, 2734411677251148030723138005716109733838866545375527602018255159319631026653190783670493107936401603981429171880504360560494771017246468702902647370954220312452541342858747590576273775107870450853533717116684326976263006435733382045807971890762018747729574021057430331778033982359184838159747331236538501849965329264774927607570410347019418407451937875684373454982306923178403161216817237890962651214718831954215200637651103907209347900857824722653217179548148145687181377220544864521808230122730967452981435355334932104265488075777638608041325256776275200067541533022527964743478554948792578057708522350812154888097)
My Friend's public keys: [(21711308225346315542706844618441565741046498277716979943478360598053144971379956916575370343448988601905854572029635846626259487297950305231661109855854947494209135205589258643517961521594924368498672064293208230802441077390193682958095111922082677813175804775628884377724377647428385841831277059274172982280545237765559969228707506857561215268491024097063920337721783673060530181637161577401589126558556182546896783307370517275046522704047385786111489447064794210010802761708615907245523492585896286374996088089317826162798278528296206977900274431829829206103227171839270887476436899494428371323874689055690729986771, 106979), (21711308225346315542706844618441565741046498277716979943478360598053144971379956916575370343448988601905854572029635846626259487297950305231661109855854947494209135205589258643517961521594924368498672064293208230802441077390193682958095111922082677813175804775628884377724377647428385841831277059274172982280545237765559969228707506857561215268491024097063920337721783673060530181637161577401589126558556182546896783307370517275046522704047385786111489447064794210010802761708615907245523492585896286374996088089317826162798278528296206977900274431829829206103227171839270887476436899494428371323874689055690729986771, 108533), (21711308225346315542706844618441565741046498277716979943478360598053144971379956916575370343448988601905854572029635846626259487297950305231661109855854947494209135205589258643517961521594924368498672064293208230802441077390193682958095111922082677813175804775628884377724377647428385841831277059274172982280545237765559969228707506857561215268491024097063920337721783673060530181637161577401589126558556182546896783307370517275046522704047385786111489447064794210010802761708615907245523492585896286374996088089317826162798278528296206977900274431829829206103227171839270887476436899494428371323874689055690729986771, 69557), (21711308225346315542706844618441565741046498277716979943478360598053144971379956916575370343448988601905854572029635846626259487297950305231661109855854947494209135205589258643517961521594924368498672064293208230802441077390193682958095111922082677813175804775628884377724377647428385841831277059274172982280545237765559969228707506857561215268491024097063920337721783673060530181637161577401589126558556182546896783307370517275046522704047385786111489447064794210010802761708615907245523492585896286374996088089317826162798278528296206977900274431829829206103227171839270887476436899494428371323874689055690729986771, 97117), (21711308225346315542706844618441565741046498277716979943478360598053144971379956916575370343448988601905854572029635846626259487297950305231661109855854947494209135205589258643517961521594924368498672064293208230802441077390193682958095111922082677813175804775628884377724377647428385841831277059274172982280545237765559969228707506857561215268491024097063920337721783673060530181637161577401589126558556182546896783307370517275046522704047385786111489447064794210010802761708615907245523492585896286374996088089317826162798278528296206977900274431829829206103227171839270887476436899494428371323874689055690729986771, 103231)]
Encrypted flag: 20304610279578186738172766224224793119885071262464464448863461184092225736054747976985179673905441502689126216282897704508745403799054734121583968853999791604281615154100736259131453424385364324630229671185343778172807262640709301838274824603101692485662726226902121105591137437331463201881264245562214012160875177167442010952439360623396658974413900469093836794752270399520074596329058725874834082188697377597949405779039139194196065364426213208345461407030771089787529200057105746584493554722790592530472869581310117300343461207750821737840042745530876391793484035024644475535353227851321505537398888106855012746117
```
và file source code:
```
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}")
```
Output ta nhận được khóa bí mật của bản thân, khóa công khai với cùng số N từ 5 người bạn khác nhau. Nếu như ta mã hóa bản rõ m với các khóa này, ta sẽ nhận được bản mã `C = M^(e1.e2.e3.e4.e5) mod N`.
Bài có đính kèm một bài viết về việc phân tích ra p và q chỉ với e và d. Thử phân tích số N ra p và q. Đến đây thì bắt đầu đi vào giải quyết bằng code.
```
from Crypto.Util.number import long_to_bytes
d=2734411677251148030723138005716109733838866545375527602018255159319631026653190783670493107936401603981429171880504360560494771017246468702902647370954220312452541342858747590576273775107870450853533717116684326976263006435733382045807971890762018747729574021057430331778033982359184838159747331236538501849965329264774927607570410347019418407451937875684373454982306923178403161216817237890962651214718831954215200637651103907209347900857824722653217179548148145687181377220544864521808230122730967452981435355334932104265488075777638608041325256776275200067541533022527964743478554948792578057708522350812154888097
N=21711308225346315542706844618441565741046498277716979943478360598053144971379956916575370343448988601905854572029635846626259487297950305231661109855854947494209135205589258643517961521594924368498672064293208230802441077390193682958095111922082677813175804775628884377724377647428385841831277059274172982280545237765559969228707506857561215268491024097063920337721783673060530181637161577401589126558556182546896783307370517275046522704047385786111489447064794210010802761708615907245523492585896286374996088089317826162798278528296206977900274431829829206103227171839270887476436899494428371323874689055690729986771
e_list =[106979, 108533,69557,97117,103231]
e = 1
for k in e_list:
e *= k
cip= 20304610279578186738172766224224793119885071262464464448863461184092225736054747976985179673905441502689126216282897704508745403799054734121583968853999791604281615154100736259131453424385364324630229671185343778172807262640709301838274824603101692485662726226902121105591137437331463201881264245562214012160875177167442010952439360623396658974413900469093836794752270399520074596329058725874834082188697377597949405779039139194196065364426213208345461407030771089787529200057105746584493554722790592530472869581310117300343461207750821737840042745530876391793484035024644475535353227851321505537398888106855012746117
p= 134460556242811604004061671529264401215233974442536870999694816691450423689575549530215841622090861571494882591368883283016107051686642467260643894947947473532769025695530343815260424314855023688439603651834585971233941772580950216838838690315383700689885536546289584980534945897919914730948196240662991266027
q= 161469718942256895682124261315253003309512855995894840701317251772156087404025170146631429756064534716206164807382734456438092732743677793224010769460318383691408352089793973150914149255603969984103815563896440419666191368964699279209687091969164697704779792586727943470780308857107052647197945528236341228473
phi_N =(p-1)*(q-1)
d = pow(e,-1,phi_N)
ans = pow(cip,d,N)
print(long_to_bytes(ans))
```
Output: `crypto{3ncrypt_y0ur_s3cr3t_w1th_y0ur_fr1end5_publ1c_k3y}`
# Lesson 16: Everything is still big!
Lần này thì họ dùng những số cực lớn. Code được đính kèm bài như sau:
```
#!/usr/bin/env python3
from Crypto.Util.number import getPrime, bytes_to_long, inverse
from random import getrandbits
from math import gcd
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 = getrandbits(512)
if (3*d)**4 > N and gcd(d,phi) == 1:
e = inverse(d, phi)
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)}')
```
Kèm với đó là output từ code trên:
```
N = 0xb12746657c720a434861e9a4828b3c89a6b8d4a1bd921054e48d47124dbcc9cfcdcc39261c5e93817c167db818081613f57729e0039875c72a5ae1f0bc5ef7c933880c2ad528adbc9b1430003a491e460917b34c4590977df47772fab1ee0ab251f94065ab3004893fe1b2958008848b0124f22c4e75f60ed3889fb62e5ef4dcc247a3d6e23072641e62566cd96ee8114b227b8f498f9a578fc6f687d07acdbb523b6029c5bbeecd5efaf4c4d35304e5e6b5b95db0e89299529eb953f52ca3247d4cd03a15939e7d638b168fd00a1cb5b0cc5c2cc98175c1ad0b959c2ab2f17f917c0ccee8c3fe589b4cb441e817f75e575fc96a4fe7bfea897f57692b050d2b
e = 0x9d0637faa46281b533e83cc37e1cf5626bd33f712cc1948622f10ec26f766fb37b9cd6c7a6e4b2c03bce0dd70d5a3a28b6b0c941d8792bc6a870568790ebcd30f40277af59e0fd3141e272c48f8e33592965997c7d93006c27bf3a2b8fb71831dfa939c0ba2c7569dd1b660efc6c8966e674fbe6e051811d92a802c789d895f356ceec9722d5a7b617d21b8aa42dd6a45de721953939a5a81b8dffc9490acd4f60b0c0475883ff7e2ab50b39b2deeedaefefffc52ae2e03f72756d9b4f7b6bd85b1a6764b31312bc375a2298b78b0263d492205d2a5aa7a227abaf41ab4ea8ce0e75728a5177fe90ace36fdc5dba53317bbf90e60a6f2311bb333bf55ba3245f
c = 0xa3bce6e2e677d7855a1a7819eb1879779d1e1eefa21a1a6e205c8b46fdc020a2487fdd07dbae99274204fadda2ba69af73627bdddcb2c403118f507bca03cb0bad7a8cd03f70defc31fa904d71230aab98a10e155bf207da1b1cac1503f48cab3758024cc6e62afe99767e9e4c151b75f60d8f7989c152fdf4ff4b95ceed9a7065f38c68dee4dd0da503650d3246d463f504b36e1d6fafabb35d2390ecf0419b2bb67c4c647fb38511b34eb494d9289c872203fa70f4084d2fa2367a63a8881b74cc38730ad7584328de6a7d92e4ca18098a15119baee91237cea24975bdfc19bdbce7c1559899a88125935584cd37c8dd31f3f2b4517eefae84e7e588344fa5
```
Lần này thì việc sử dụng Wiener là không thể, bởi vì khi này `(3*d)**4 > N` tức d đã lớn hơn rất nhiều, không còn ở trường hợp "Low Private Exponent". Vì thế ta sẽ sử dụng Boneh-Durfee Attack (cực vjp).
Cực lười để code, vì thế ta sẽ sử dụng [tool](https://raw.githubusercontent.com/mimoo/RSA-and-LLL-attacks/master/boneh_durfee.sage) code sẵn, sử dụng Sagemath để khởi chạy. Đối với tool này, ta sẽ cung cấp số **N** và **e**, từ đó nhận về lại số **d** qua quá trình xử lí bới thuật toán.
Và đây là output sau khi chạy thuật toán:
Và ta đã tìm ra khóa bí mật **d**. Đến đây khi đã có đủ **N,e,d**, ta có thể đi tìm ra được flag.
```
from Crypto.Util.number import *
N = 0xb8af3d3afb893a602de4afe2a29d7615075d1e570f8bad8ebbe9b5b9076594cf06b6e7b30905b6420e950043380ea746f0a14dae34469aa723e946e484a58bcd92d1039105871ffd63ffe64534b7d7f8d84b4a569723f7a833e6daf5e182d658655f739a4e37bd9f4a44aff6ca0255cda5313c3048f56eed5b21dc8d88bf5a8f8379eac83d8523e484fa6ae8dbcb239e65d3777829a6903d779cd2498b255fcf275e5f49471f35992435ee7cade98c8e82a8beb5ce1749349caa16759afc4e799edb12d299374d748a9e3c82e1cc983cdf9daec0a2739dadcc0982c1e7e492139cbff18c5d44529407edfd8e75743d2f51ce2b58573fea6fbd4fe25154b9964d
e = 0x9ab58dbc8049b574c361573955f08ea69f97ecf37400f9626d8f5ac55ca087165ce5e1f459ef6fa5f158cc8e75cb400a7473e89dd38922ead221b33bc33d6d716fb0e4e127b0fc18a197daf856a7062b49fba7a86e3a138956af04f481b7a7d481994aeebc2672e500f3f6d8c581268c2cfad4845158f79c2ef28f242f4fa8f6e573b8723a752d96169c9d885ada59cdeb6dbe932de86a019a7e8fc8aeb07748cfb272bd36d94fe83351252187c2e0bc58bb7a0a0af154b63397e6c68af4314601e29b07caed301b6831cf34caa579eb42a8c8bf69898d04b495174b5d7de0f20cf2b8fc55ed35c6ad157d3e7009f16d6b61786ee40583850e67af13e9d25be3
c = 0x3f984ff5244f1836ed69361f29905ca1ae6b3dcf249133c398d7762f5e277919174694293989144c9d25e940d2f66058b2289c75d1b8d0729f9a7c4564404a5fd4313675f85f31b47156068878e236c5635156b0fa21e24346c2041ae42423078577a1413f41375a4d49296ab17910ae214b45155c4570f95ca874ccae9fa80433a1ab453cbb28d780c2f1f4dc7071c93aff3924d76c5b4068a0371dff82531313f281a8acadaa2bd5078d3ddcefcb981f37ff9b8b14c7d9bf1accffe7857160982a2c7d9ee01d3e82265eec9c7401ecc7f02581fd0d912684f42d1b71df87a1ca51515aab4e58fab4da96e154ea6cdfb573a71d81b2ea4a080a1066e1bc3474
d = 79434351637397000170240219617391501050474168352481334243649813782018808904459
m = pow(c, d, N)
print(long_to_bytes(m))
```
Flag: `crypto{s0m3th1ng5_c4n_b3_t00_b1g}`
# Lesson 17: Endless Emails
File johan.py đi kèm bài:
```
#!/usr/bin/env python3
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}")
```
và cùng với đó là một file output:
```
n = 14528915758150659907677315938876872514853653132820394367681510019000469589767908107293777996420037715293478868775354645306536953789897501630398061779084810058931494642860729799059325051840331449914529594113593835549493208246333437945551639983056810855435396444978249093419290651847764073607607794045076386643023306458718171574989185213684263628336385268818202054811378810216623440644076846464902798568705083282619513191855087399010760232112434412274701034094429954231366422968991322244343038458681255035356984900384509158858007713047428143658924970374944616430311056440919114824023838380098825914755712289724493770021
e = 3
c = 6965891612987861726975066977377253961837139691220763821370036576350605576485706330714192837336331493653283305241193883593410988132245791554283874785871849223291134571366093850082919285063130119121338290718389659761443563666214229749009468327825320914097376664888912663806925746474243439550004354390822079954583102082178617110721589392875875474288168921403550415531707419931040583019529612270482482718035497554779733578411057633524971870399893851589345476307695799567919550426417015815455141863703835142223300228230547255523815097431420381177861163863791690147876158039619438793849367921927840731088518955045807722225
n = 20463913454649855046677206889944639231694511458416906994298079596685813354570085475890888433776403011296145408951323816323011550738170573801417972453504044678801608709931200059967157605416809387753258251914788761202456830940944486915292626560515250805017229876565916349963923702612584484875113691057716315466239062005206014542088484387389725058070917118549621598629964819596412564094627030747720659155558690124005400257685883230881015636066183743516494701900125788836869358634031031172536767950943858472257519195392986989232477630794600444813136409000056443035171453870906346401936687214432176829528484662373633624123
e = 3
c = 5109363605089618816120178319361171115590171352048506021650539639521356666986308721062843132905170261025772850941702085683855336653472949146012700116070022531926476625467538166881085235022484711752960666438445574269179358850309578627747024264968893862296953506803423930414569834210215223172069261612934281834174103316403670168299182121939323001232617718327977313659290755318972603958579000300780685344728301503641583806648227416781898538367971983562236770576174308965929275267929379934367736694110684569576575266348020800723535121638175505282145714117112442582416208209171027273743686645470434557028336357172288865172
n = 19402640770593345339726386104915705450969517850985511418263141255686982818547710008822417349818201858549321868878490314025136645036980129976820137486252202687238348587398336652955435182090722844668488842986318211649569593089444781595159045372322540131250208258093613844753021272389255069398553523848975530563989367082896404719544411946864594527708058887475595056033713361893808330341623804367785721774271084389159493974946320359512776328984487126583015777989991635428744050868653379191842998345721260216953918203248167079072442948732000084754225272238189439501737066178901505257566388862947536332343196537495085729147
e = 3
c = 5603386396458228314230975500760833991383866638504216400766044200173576179323437058101562931430558738148852367292802918725271632845889728711316688681080762762324367273332764959495900563756768440309595248691744845766607436966468714038018108912467618638117493367675937079141350328486149333053000366933205635396038539236203203489974033629281145427277222568989469994178084357460160310598260365030056631222346691527861696116334946201074529417984624304973747653407317290664224507485684421999527164122395674469650155851869651072847303136621932989550786722041915603539800197077294166881952724017065404825258494318993054344153
n = 12005639978012754274325188681720834222130605634919280945697102906256738419912110187245315232437501890545637047506165123606573171374281507075652554737014979927883759915891863646221205835211640845714836927373844277878562666545230876640830141637371729405545509920889968046268135809999117856968692236742804637929866632908329522087977077849045608566911654234541526643235586433065170392920102840518192803854740398478305598092197183671292154743153130012885747243219372709669879863098708318993844005566984491622761795349455404952285937152423145150066181043576492305166964448141091092142224906843816547235826717179687198833961
e = 3
c = 1522280741383024774933280198410525846833410931417064479278161088248621390305797210285777845359812715909342595804742710152832168365433905718629465545306028275498667935929180318276445229415104842407145880223983428713335709038026249381363564625791656631137936935477777236936508600353416079028339774876425198789629900265348122040413865209592074731028757972968635601695468594123523892918747882221891834598896483393711851510479989203644477972694520237262271530260496342247355761992646827057846109181410462131875377404309983072358313960427035348425800940661373272947647516867525052504539561289941374722179778872627956360577
n = 17795451956221451086587651307408104001363221003775928432650752466563818944480119932209305765249625841644339021308118433529490162294175590972336954199870002456682453215153111182451526643055812311071588382409549045943806869173323058059908678022558101041630272658592291327387549001621625757585079662873501990182250368909302040015518454068699267914137675644695523752851229148887052774845777699287718342916530122031495267122700912518207571821367123013164125109174399486158717604851125244356586369921144640969262427220828940652994276084225196272504355264547588369516271460361233556643313911651916709471353368924621122725823
e = 3
c = 8752507806125480063647081749506966428026005464325535765874589376572431101816084498482064083887400646438977437273700004934257274516197148448425455243811009944321764771392044345410680448204581679548854193081394891841223548418812679441816502910830861271884276608891963388657558218620911858230760629700918375750796354647493524576614017731938584618983084762612414591830024113057983483156974095503392359946722756364412399187910604029583464521617256125933111786441852765229820406911991809039519015434793656710199153380699319611499255869045311421603167606551250174746275803467549814529124250122560661739949229005127507540805
n = 25252721057733555082592677470459355315816761410478159901637469821096129654501579313856822193168570733800370301193041607236223065376987811309968760580864569059669890823406084313841678888031103461972888346942160731039637326224716901940943571445217827960353637825523862324133203094843228068077462983941899571736153227764822122334838436875488289162659100652956252427378476004164698656662333892963348126931771536472674447932268282205545229907715893139346941832367885319597198474180888087658441880346681594927881517150425610145518942545293750127300041942766820911120196262215703079164895767115681864075574707999253396530263
e = 3
c = 23399624135645767243362438536844425089018405258626828336566973656156553220156563508607371562416462491581383453279478716239823054532476006642583363934314982675152824147243749715830794488268846671670287617324522740126594148159945137948643597981681529145611463534109482209520448640622103718682323158039797577387254265854218727476928164074249568031493984825273382959147078839665114417896463735635546290504843957780546550577300001452747760982468547756427137284830133305010038339400230477403836856663883956463830571934657200851598986174177386323915542033293658596818231793744261192870485152396793393026198817787033127061749
n = 19833203629283018227011925157509157967003736370320129764863076831617271290326613531892600790037451229326924414757856123643351635022817441101879725227161178559229328259469472961665857650693413215087493448372860837806619850188734619829580286541292997729705909899738951228555834773273676515143550091710004139734080727392121405772911510746025807070635102249154615454505080376920778703360178295901552323611120184737429513669167641846902598281621408629883487079110172218735807477275590367110861255756289520114719860000347219161944020067099398239199863252349401303744451903546571864062825485984573414652422054433066179558897
e = 3
c = 15239683995712538665992887055453717247160229941400011601942125542239446512492703769284448009141905335544729440961349343533346436084176947090230267995060908954209742736573986319254695570265339469489948102562072983996668361864286444602534666284339466797477805372109723178841788198177337648499899079471221924276590042183382182326518312979109378616306364363630519677884849945606288881683625944365927809405420540525867173639222696027472336981838588256771671910217553150588878434061862840893045763456457939944572192848992333115479951110622066173007227047527992906364658618631373790704267650950755276227747600169403361509144
```
Nghiên cứu tài liệu "Twenty Years of Attacks on the RSA Cryptosystem", ta thấy trường hợp này với `e = 3`, cùng với đó là nhiều cặp (N,e). Ta biết bản rõ M trong mọi tin nhắn này đều giống nhau, vì thế dùng phương thức tấn công Hastad's Broadcast Attack chắc chắn sẽ hiệu quả ở trường hợp này.
Phương thức tấn công này có sử dụng kết hợp với CRT, vì thế ta sẽ code lại thuật toán này.
Sign in with Wallet
Connect another wallet