# RSA
- Tìm hiểu RSA:
### Giới thiệu :

-Mật mã RSA là mật mã khóa bất đối xứng được phát minh bởi Ron Rivest, Adi Shamir, and Len Adleman. Ngày nay RSA được triển khai trong nhiều hệ thống thương mại và được cho là đảm bảo an toàn với điều kiện độ dài khóa đủ lớn.

-Thuật toán RSA có hai khóa, đó là khóa công khai và khóa bí mật. Hai khóa này là những số cố định sử dụng để mã hóa và giải mã. Khóa công khai được công khai cho mọi người biết để mã hóa. Nhưng chỉ người biết khóa bí mật mới có thể giải mã được.
##### Quá trình hoạt động của RSA:
- Quá trình sinh khóa :

B1: Ta chọn hai số nguyên tố p ,q

B2: Tính số nguyên dương n (modulus) là sản phẩm của hai số nguyên tố p,q :

n=p*q

B3: Tính giá trị hàm số Euler của n :

( tham khảo hàm số Euler [https://vi.wikipedia.org/wiki/Hàm_phi_Euler](https://vi.wikipedia.org/wiki/H%C3%A0m_phi_Euler) )

Φ(n) =(p-1)*(q-1)

B4: Chọn số tự nhiên e sao cho **gcd(Φ(n),e)=1** và **1<e<Φ(n)**

B5: Bây giờ ta có khóa công khai là cặp {e,n}. Và ta tính khóa bí mật d sao cho: `d☰e^-1 (mod Φ(n)). `

- Quá trình mã hóa và giải mã:

- Giả sử ta có bản rõ m (plaintext) {m<n} .

- A muốn gửi cho B bản tin là M thì A sẽ sử dụng khóa công khai của B là e và n để
mã hóa theo công thức: c(ciphertext)=m^e mod n

- Khi B nhận được bản mã do A gửi đến thì B sẽ giải mã bằng khóa riêng của B là theo công thức m=c^d mod n

Ví dụ:

Chọn p=17 và q=11 ; n = p*q = 17*11= 187 ; Φ(n)=16*10=160

Giả sử B chọn e=7 , gcd(160,e)=1

Tính d = 23. Giả sử A muốn mã hóa bản tin m=88 thì ta tính : c=88^7 mod 187 =11.

B nhận đc bản mã c=11 và giải mã nó: m= 11^23 mod 187 =88

### Các loại tấn công thường gặp
#### Factoring Large Intege:
- Cuộc tấn công đầu tiên vào khóa công khai RSA để xem xét là bao gồm mô đun N. Do hệ số của N, kẻ tấn công có thể dễ dàng xây dựng Φ(n), từ đó có thể tìm thấy số mũ giải mã d = e^-1 mod Φ(n) và từ đó giải mã.
- Nếu n rất lớn thì ta có thể dùng tool http://factordb.com/ để tìm p,q
- Ví dụ:

n=882564595536224140639625987659416029426239230804614613279163
thì p=857504083339712752489993810777
    q=1029224947942998075080348647219

#### Elementary At:

##### 1.Common modulus:
- Bởi vì tránh tạo ra nhiều modulus khác nhau, người ta muốn sửa *n* một lần và cho tất cả để tất cả đều sử dụng một *n* (modulus).
Ví dụ mình là người muốn xem trộm tin nhắn của A gửi cho B1 và B2, và mình giữ C1, C2. Mình sẽ giải mã nó để đọc tin nhắn
c1= (m^e1) mod n
c2= (m^e2) mod n
Do **gcd(e1,e2) =1** , thì sẽ tồn tại hai số x và y thỏa:
`e1 * x + e2 * y =1`
=> m= ((c1^x) * (c2^y)) mod n
mà c1= m^e1; c2= m^e2 nên:
=> m= (((m^e1))^x) * ((m^e2)^y)) mod n
=> m= m^((e1 * x)+(e2 * y))= m^1 = m mod n

##### 2.Blinding
- Giả sử A có một cặp public key (N,e) và private key ( N,d). Giả sử B muốn A ký vào một tin nhắn m. Nhưng A không phải kẻ ngốc và không ký chữ ký vào tin nhắn m. Sau đó B chọn một số ngẫu nhiên *r* và m'=r^e mod n và yêu cầu A ký vào m' , A đã ký s' vào m'.
- Nhưng S' = ( M' )^d mod N và bây giờ Marvin chỉ cần tính S = S'/r mod N và lấy được chữ ký S của Bob trên M ban đầu.
- Kỹ thuật này gọi là làm mù cho phép B có được chữ ký hợp lệ khi bằng cách lừa anh ấy ký vào một tin nhắn làm mù ngẫu nhiên.
#### Low Private Exponent
- Để 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 chứ không phải là một ngẫu nhiên d.
- Vì lũy thừa mô-đun mất 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à 10 lần (đối với mô-đun 1024 bit). Thật không may, một người thông minh cuộc tấn công của M. Wiener 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ã.
- Định lí 2 (M. Wiener) : Cho N = p * q với q<p<2q. Cho d < 1/3 N^(1/4) . Cho (N,e) với e * d=1 (mod N) , kẻ tấn công có thể khôi phục được d.
Đối với dạng này mình có thể tìm d khi biết N và e , với mình thì mình tải tool RShack để tìm d https://github.com/zweisamkeit/RSHack
#### Low Public Exponent
- Để giảm thời gian mã hóa hoặc xác minh chữ ký, thông thường sử dụng một số mũ công khai nhỏ e .
- Giá trị nhỏ nhất có thể có của e là 3, nhưng để đánh bại một số cuộc tấn công nhất định, giá trị e = 2^16 + 1 = 65537 là thường thấy nhất.Các cuộc tấn công áp dụng khi một e nhỏ được sử dụng còn lâu mới bị phá vỡ hoàn toàn.
- Và khi e quá nhỏ cụ thể bằng 3 thì m sẽ nhỏ, các mô đun sẽ không hoạt động.
`c=m^3 mod n mà m^3 < n => c=m^3`
- Vì vậy khi e nhỏ (e=3) thì ta có thể tấn công lấy m dễ dàng.
- Ví dụ:
Cho c=068158860859ac022ab027ce6787f08a87775effe0623ee237499bffa8f3b69a139a24e0c79e94e9a8184ca4bfd16582ba3dd44242515b04c050382af187a0ee73fd91c9b7a9379435d9006bec1f1707c3bd4534cdfc393e396e1fb764a7b44bd5007f839ebe327465
e=3
- Mình sẽ giải như sau

from gmpy2 import *
c=int("068158860859ac022ab027ce6787f08a87775effe0623ee237499bffa8f3b69a139a24e0c79e94e9a8184ca4bfd16582ba3dd44242515b04c050382af187a0ee73fd91c9b7a9379435d9006bec1f1707c3bd4534cdfc393e396e1fb764a7b44bd5007f839ebe327465",16)
print(long_to_bytes(iroot(c,3)[0]))

#### 𝗛𝗮𝘀𝘁𝗮𝗱’𝘀 𝗯𝗿𝗼𝗮𝗱𝗰𝗮𝘀𝘁 𝗮𝘁𝘁𝗮𝗰𝗸
Giả sử A muốn gửi m cho 3 người bạn của A, mỗi người sẽ nhận được c1 ≡ m^3 mod n1, c2≡ m^3 n2, c3 ≡m^3 mod n3
Tiếp đó mình là một hacker muốn đọc tin nhắn của A gửi cho bạn thì mình sẽ đoán m bằng định lý thặng dư Trung Hoa
ta có:
m^3≡c1 mod n1
m^3≡c2 mod n2
m^3≡c3 mod n3
từ đó mình có thể tính m^3 (mod n1.n2.n3) ; và tính bằng căn bậc 3 của (mod n1.n2.n3)
### Challenge RSA
#### 1. RSA Starter 1
Find the solution to 101^17 mod 22663
- solve:

print(pow(101, 17, 22663))
#19906

#### 2. RSA Starter 2
Cho:
pt= 12
e=65537
p=17
q=23
Tìm ct=?
- solve:
Ta tính n =p * q
ct= pt^e mod n
và ta có

print(pow(12, 65537, (17*23)))
#301

#### 3. RSA Starter 3
Cho
p = 857504083339712752489993810777
q = 1029224947942998075080348647219
và tính totient của n
- solve:
Ta tính theo công thức phi(n) = (p-1) * (q-1)
- code:

p = 857504083339712752489993810777
q =1029224947942998075080348647219
phi = (p-1) * (q-1)
print(phi)
#882564595536224140639625987657529300394956519977044270821168

#### 4. RSA Starter 4
Cho:
p = 857504083339712752489993810777
q = 1029224947942998075080348647219
e = 65537
Yêu cầu tính private key d= ?
- solve:
- code

from Crypto.Util.number import inverse

p = 857504083339712752489993810777
q = 1029224947942998075080348647219
e= 65537 
d= inverse(e, (p-1)*(q-1))
print(d)
#121832886702415731577073962957377780195510499965398469843281

#### 5. RSA Starter 5
Cho:
N=882564595536224140639625987659416029426239230804614613279163
e = 65537
c= 77578995801157823671636298847186723593814843845525223303932
Yêu cầu giải mã tìm m.
- solve:
Bài này mình sẽ sử dụng tool http://factordb.com/ để tìm p và q và giải mã
- code

from Crypto.Util.number import *

N = 882564595536224140639625987659416029426239230804614613279163
e = 65537
c = 77578995801157823671636298847186723593814843845525223303932
p= 857504083339712752489993810777  # factordb để tìm p,q 
q= 1029224947942998075080348647219
phi = (p-1) *(q-1)
d= inverse(e, phi)
m= pow(c,d,N)
print(m)
#13371337

#### 6. RSA Starter 6
Cho:
N = 15216583654836731327639981224133918855895948374072384050848479908982286890731769486609085918857664046075375253168955058743185664390273058074450390236774324903305663479046566232967297765731625328029814055635316002591227570271271445226094919864475407884459980489638001092788574811554149774028950310695112688723853763743238753349782508121985338746755237819373178699343135091783992299561827389745132880022259873387524273298850340648779897909381979714026837172003953221052431217940632552930880000919436507245150726543040714721553361063311954285289857582079880295199632757829525723874753306371990452491305564061051059885803
d = 11175901210643014262548222473449533091378848269490518850474399681690547281665059317155831692300453197335735728459259392366823302405685389586883670043744683993709123180805154631088513521456979317628012721881537154107239389466063136007337120599915456659758559300673444689263854921332185562706707573660658164991098457874495054854491474065039621922972671588299315846306069845169959451250821044417886630346229021305410340100401530146135418806544340908355106582089082980533651095594192031411679866134256418292249592135441145384466261279428795408721990564658703903787956958168449841491667690491585550160457893350536334242689
flag: crypto{Immut4ble_m3ssag1ng}
Yêu cầu mã hóa flag sử dụng khóa riêng và hàm băm SHA256
- solve:
- code

from Crypto.Util.number import *
from hashlib import sha256
N = 15216583654836731327639981224133918855895948374072384050848479908982286890731769486609085918857664046075375253168955058743185664390273058074450390236774324903305663479046566232967297765731625328029814055635316002591227570271271445226094919864475407884459980489638001092788574811554149774028950310695112688723853763743238753349782508121985338746755237819373178699343135091783992299561827389745132880022259873387524273298850340648779897909381979714026837172003953221052431217940632552930880000919436507245150726543040714721553361063311954285289857582079880295199632757829525723874753306371990452491305564061051059885803
d = 11175901210643014262548222473449533091378848269490518850474399681690547281665059317155831692300453197335735728459259392366823302405685389586883670043744683993709123180805154631088513521456979317628012721881537154107239389466063136007337120599915456659758559300673444689263854921332185562706707573660658164991098457874495054854491474065039621922972671588299315846306069845169959451250821044417886630346229021305410340100401530146135418806544340908355106582089082980533651095594192031411679866134256418292249592135441145384466261279428795408721990564658703903787956958168449841491667690491585550160457893350536334242689
flag= b"crypto{Immut4ble_m3ssag1ng}"

H=(sha256(flag).hexdigest())
c=pow(int(H,16), d ,N)
print(c)
#13480738404590090803339831649238454376183189744970683129909766078877706583282422686710545217275797376709672358894231550335007974983458408620258478729775647818876610072903021235573923300070103666940534047644900475773318682585772698155617451477448441198150710420818995347235921111812068656782998168064960965451719491072569057636701190429760047193261886092862024118487826452766513533860734724124228305158914225250488399673645732882077575252662461860972889771112594906884441454355959482925283992539925713424132009768721389828848907099772040836383856524605008942907083490383109757406940540866978237471686296661685839083475

#### 7. Factoring
Cho số nguyên tố : 510143758735509025530880200653196460532653147
tìm số nhỏ hơn trong p or q
- solve:
Để tìm p,q mình dùng http://factordb.com/
Kết quả : 19704762736204164635843
#### 8. Inferius Prime
Cho
n=742449129124467073921545687640895127535705902454369756401331
e = 3
ct =39207274348578481322317340648475596807303160111338236677373
Yêu cầu giải mã tìm pt=?
- solve:
Tìm p,q bằng factordb http://factordb.com/

- code:

from Crypto.Util.number import *

n = 742449129124467073921545687640895127535705902454369756401331
e = 3
ct = 39207274348578481322317340648475596807303160111338236677373
p=752708788837165590355094155871
q=986369682585281993933185289261
phi = (p - 1) * (q - 1)
d = inverse(e, phi)
print(long_to_bytes(pow(ct,d,n)))
#crypto{N33d_b1g_pR1m35}

#### 9. Monoprime
Cho
n = 171731371218065444125482536302245915415603318380280392385291836472299752747934607246477508507827284075763910264995326010251268493630501989810855418416643352631102434317900028697993224868629935657273062472544675693365930943308086634291936846505861203914449338007760990051788980485462592823446469606824421932591
e = 65537
ct = 161367550346730604451454756189028938964941280347662098798775466019463375610700074840105776873791605070092554650190486030367121011578171525759600774739890458414593857709994072516290998135846956596662071379067305011746842247628316996977338024343628757374524136260758515864509435302781735938531030576289086798942
- solve:
Mình sẽ đi tìm p bằng factordb
Ở đây mình thấy hai số giống nhau đó là p
- code:

from Crypto.Util.number import *

n = 171731371218065444125482536302245915415603318380280392385291836472299752747934607246477508507827284075763910264995326010251268493630501989810855418416643352631102434317900028697993224868629935657273062472544675693365930943308086634291936846505861203914449338007760990051788980485462592823446469606824421932591                                                                  
e = 65537
ct = 161367550346730604451454756189028938964941280347662098798775466019463375610700074840105776873791605070092554650190486030367121011578171525759600774739890458414593857709994072516290998135846956596662071379067305011746842247628316996977338024343628757374524136260758515864509435302781735938531030576289086798942  
p= 171731371218065444125482536302245915415603318380280392385291836472299752747934607246477508507827284075763910264995326010251268493630501989810855418416643352631102434317900028697993224868629935657273062472544675693365930943308086634291936846505861203914449338007760990051788980485462592823446469606824421932591
q= 171731371218065444125482536302245915415603318380280392385291836472299752747934607246477508507827284075763910264995326010251268493630501989810855418416643352631102434317900028697993224868629935657273062472544675693365930943308086634291936846505861203914449338007760990051788980485462592823446469606824421932591
phi = (p-1)*(q-1)
d= inverse(e, phi)
m= pow(ct,d,n)
print(long_to_bytes(m))
#crypto{0n3_pr1m3_41n7_pr1m3_l0l}

#### 10. Square Eyes
n = 535860808044009550029177135708168016201451343147313565371014459027743491739422885443084705720731409713775527993719682583669164873806842043288439828071789970694759080842162253955259590552283047728782812946845160334801782088068154453021936721710269050985805054692096738777321796153384024897615594493453068138341203673749514094546000253631902991617197847584519694152122765406982133526594928685232381934742152195861380221224370858128736975959176861651044370378539093990198336298572944512738570839396588590096813217791191895941380464803377602779240663133834952329316862399581950590588006371221334128215409197603236942597674756728212232134056562716399155080108881105952768189193728827484667349378091100068224404684701674782399200373192433062767622841264055426035349769018117299620554803902490432339600566432246795818167460916180647394169157647245603555692735630862148715428791242764799469896924753470539857080767170052783918273180304835318388177089674231640910337743789750979216202573226794240332797892868276309400253925932223895530714169648116569013581643192341931800785254715083294526325980247219218364118877864892068185905587410977152737936310734712276956663192182487672474651103240004173381041237906849437490609652395748868434296753449
e = 65537
ct = 222502885974182429500948389840563415291534726891354573907329512556439632810921927905220486727807436668035929302442754225952786602492250448020341217733646472982286222338860566076161977786095675944552232391481278782019346283900959677167026636830252067048759720251671811058647569724495547940966885025629807079171218371644528053562232396674283745310132242492367274184667845174514466834132589971388067076980563188513333661165819462428837210575342101036356974189393390097403614434491507672459254969638032776897417674577487775755539964915035731988499983726435005007850876000232292458554577437739427313453671492956668188219600633325930981748162455965093222648173134777571527681591366164711307355510889316052064146089646772869610726671696699221157985834325663661400034831442431209123478778078255846830522226390964119818784903330200488705212765569163495571851459355520398928214206285080883954881888668509262455490889283862560453598662919522224935145694435885396500780651530829377030371611921181207362217397805303962112100190783763061909945889717878397740711340114311597934724670601992737526668932871436226135393872881664511222789565256059138002651403875484920711316522536260604255269532161594824301047729082877262812899724246757871448545439896
Yêu cầu tìm flag?
- solve:
Mình dùng factordb để tìm p,
p=23148667521998097720857168827790771337662483716348435477360567409355026169165934446949809664595523770853897203103759106983985113264049057416908191166720008503275951625738975666019029172377653170602440373579593292576530667773951407647222757756437867216095193174201323278896027294517792607881861855264600525772460745259440301156930943255240915685718552334192230264780355799179037816026330705422484000086542362084006958158550346395941862383925942033730030004606360308379776255436206440529441711859246811586652746028418496020145441513037535475380962562108920699929022900677901988508936509354385660735694568216631382653107
Đề bài nói chỉ sử dụng một cho hai và gợi ý công thức tổng quát của totient của n nên mình tìm được công thức tổng quát là 
- code:

from Crypto.Util.number import *

n = 535860808044009550029177135708168016201451343147313565371014459027743491739422885443084705720731409713775527993719682583669164873806842043288439828071789970694759080842162253955259590552283047728782812946845160334801782088068154453021936721710269050985805054692096738777321796153384024897615594493453068138341203673749514094546000253631902991617197847584519694152122765406982133526594928685232381934742152195861380221224370858128736975959176861651044370378539093990198336298572944512738570839396588590096813217791191895941380464803377602779240663133834952329316862399581950590588006371221334128215409197603236942597674756728212232134056562716399155080108881105952768189193728827484667349378091100068224404684701674782399200373192433062767622841264055426035349769018117299620554803902490432339600566432246795818167460916180647394169157647245603555692735630862148715428791242764799469896924753470539857080767170052783918273180304835318388177089674231640910337743789750979216202573226794240332797892868276309400253925932223895530714169648116569013581643192341931800785254715083294526325980247219218364118877864892068185905587410977152737936310734712276956663192182487672474651103240004173381041237906849437490609652395748868434296753449
e = 65537
ct = 222502885974182429500948389840563415291534726891354573907329512556439632810921927905220486727807436668035929302442754225952786602492250448020341217733646472982286222338860566076161977786095675944552232391481278782019346283900959677167026636830252067048759720251671811058647569724495547940966885025629807079171218371644528053562232396674283745310132242492367274184667845174514466834132589971388067076980563188513333661165819462428837210575342101036356974189393390097403614434491507672459254969638032776897417674577487775755539964915035731988499983726435005007850876000232292458554577437739427313453671492956668188219600633325930981748162455965093222648173134777571527681591366164711307355510889316052064146089646772869610726671696699221157985834325663661400034831442431209123478778078255846830522226390964119818784903330200488705212765569163495571851459355520398928214206285080883954881888668509262455490889283862560453598662919522224935145694435885396500780651530829377030371611921181207362217397805303962112100190783763061909945889717878397740711340114311597934724670601992737526668932871436226135393872881664511222789565256059138002651403875484920711316522536260604255269532161594824301047729082877262812899724246757871448545439896

p= (23148667521998097720857168827790771337662483716348435477360567409355026169165934446949809664595523770853897203103759106983985113264049057416908191166720008503275951625738975666019029172377653170602440373579593292576530667773951407647222757756437867216095193174201323278896027294517792607881861855264600525772460745259440301156930943255240915685718552334192230264780355799179037816026330705422484000086542362084006958158550346395941862383925942033730030004606360308379776255436206440529441711859246811586652746028418496020145441513037535475380962562108920699929022900677901988508936509354385660735694568216631382653107)
phi = (p**2)*(p-1)*(p**2)*(p-1)
d=inverse(e, phi)
print(long_to_bytes(pow(ct,d,n)))
#crypto{squar3_r00t_i5_f4st3r_th4n_f4ct0r1ng!}

#### 11. Manyprime
Cho
n = 580642391898843192929563856870897799650883152718761762932292482252152591279871421569162037190419036435041797739880389529593674485555792234900969402019055601781662044515999210032698275981631376651117318677368742867687180140048715627160641771118040372573575479330830092989800730105573700557717146251860588802509310534792310748898504394966263819959963273509119791037525504422606634640173277598774814099540555569257179715908642917355365791447508751401889724095964924513196281345665480688029639999472649549163147599540142367575413885729653166517595719991872223011969856259344396899748662101941230745601719730556631637
e = 65537
ct = 320721490534624434149993723527322977960556510750628354856260732098109692581338409999983376131354918370047625150454728718467998870322344980985635149656977787964380651868131740312053755501594999166365821315043312308622388016666802478485476059625888033017198083472976011719998333985531756978678758897472845358167730221506573817798467100023754709109274265835201757369829744113233607359526441007577850111228850004361838028842815813724076511058179239339760639518034583306154826603816927757236549096339501503316601078891287408682099750164720032975016814187899399273719181407940397071512493967454225665490162619270814464
- solve:
Tiếp tục factordb tìm p , lần này thì ta thu được rất nhiều p
Copy hết vào tính phi như công thức tổng quát.
- code:

from Crypto.Util.number import *

n = 580642391898843192929563856870897799650883152718761762932292482252152591279871421569162037190419036435041797739880389529593674485555792234900969402019055601781662044515999210032698275981631376651117318677368742867687180140048715627160641771118040372573575479330830092989800730105573700557717146251860588802509310534792310748898504394966263819959963273509119791037525504422606634640173277598774814099540555569257179715908642917355365791447508751401889724095964924513196281345665480688029639999472649549163147599540142367575413885729653166517595719991872223011969856259344396899748662101941230745601719730556631637
e = 65537
ct = 320721490534624434149993723527322977960556510750628354856260732098109692581338409999983376131354918370047625150454728718467998870322344980985635149656977787964380651868131740312053755501594999166365821315043312308622388016666802478485476059625888033017198083472976011719998333985531756978678758897472845358167730221506573817798467100023754709109274265835201757369829744113233607359526441007577850111228850004361838028842815813724076511058179239339760639518034583306154826603816927757236549096339501503316601078891287408682099750164720032975016814187899399273719181407940397071512493967454225665490162619270814464
phi=1
fac=[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 fac:
    phi=phi*(i-1)
d=inverse(e, phi)
m=pow(ct,d,n)
print(long_to_bytes(m))
#crypto{700_m4ny_5m4ll_f4c70r5}

#### 12. Salty
Cho
n = 110581795715958566206600392161360212579669637391437097703685154237017351570464767725324182051199901920318211290404777259728923614917211291562555864753005179326101890427669819834642007924406862482343614488768256951616086287044725034412802176312273081322195866046098595306261781788276570920467840172004530873767
e = 1
ct = 44981230718212183604274785925793145442655465025264554046028251311164494127485
- solve:
Dạng bài này sử dụng e rất nhỏ nên mình nghĩ ngay là pt=ct luôn
- code:

from Crypto.Util.number import *

n = 110581795715958566206600392161360212579669637391437097703685154237017351570464767725324182051199901920318211290404777259728923614917211291562555864753005179326101890427669819834642007924406862482343614488768256951616086287044725034412802176312273081322195866046098595306261781788276570920467840172004530873767                                                                  
e = 1
ct = 44981230718212183604274785925793145442655465025264554046028251311164494127485

print(long_to_bytes(ct))
#crypto{saltstack_fell_for_this!}

#### 13. Modulus Inutilis
Cho
n = 17258212916191948536348548470938004244269544560039009244721959293554822498047075403658429865201816363311805874117705688359853941515579440852166618074161313773416434156467811969628473425365608002907061241714688204565170146117869742910273064909154666642642308154422770994836108669814632309362483307560217924183202838588431342622551598499747369771295105890359290073146330677383341121242366368309126850094371525078749496850520075015636716490087482193603562501577348571256210991732071282478547626856068209192987351212490642903450263288650415552403935705444809043563866466823492258216747445926536608548665086042098252335883
e = 3
ct = 243251053617903760309941844835411292373350655973075480264001352919865180151222189820473358411037759381328642957324889519192337152355302808400638052620580409813222660643570085177957
- solve:
Đề bài cho e= 3 nên pt^3 < n
Vì vậy pt = căn bậc 3 của ct
Mình dùng function iroot để tính căn bậc 3 của một số nguyên tố lớn
- code:

from Crypto.Util.number import *
from gmpy2 import *
n = 17258212916191948536348548470938004244269544560039009244721959293554822498047075403658429865201816363311805874117705688359853941515579440852166618074161313773416434156467811969628473425365608002907061241714688204565170146117869742910273064909154666642642308154422770994836108669814632309362483307560217924183202838588431342622551598499747369771295105890359290073146330677383341121242366368309126850094371525078749496850520075015636716490087482193603562501577348571256210991732071282478547626856068209192987351212490642903450263288650415552403935705444809043563866466823492258216747445926536608548665086042098252335883
e = 3
ct = 243251053617903760309941844835411292373350655973075480264001352919865180151222189820473358411037759381328642957324889519192337152355302808400638052620580409813222660643570085177957

print(long_to_bytes(iroot(ct, e)[0]))   
#crypto{N33d_m04R_p4dd1ng}

#### 14. Everything is Big
Cho:
N = 0xb8af3d3afb893a602de4afe2a29d7615075d1e570f8bad8ebbe9b5b9076594cf06b6e7b30905b6420e950043380ea746f0a14dae34469aa723e946e484a58bcd92d1039105871ffd63ffe64534b7d7f8d84b4a569723f7a833e6daf5e182d658655f739a4e37bd9f4a44aff6ca0255cda5313c3048f56eed5b21dc8d88bf5a8f8379eac83d8523e484fa6ae8dbcb239e65d3777829a6903d779cd2498b255fcf275e5f49471f35992435ee7cade98c8e82a8beb5ce1749349caa16759afc4e799edb12d299374d748a9e3c82e1cc983cdf9daec0a2739dadcc0982c1e7e492139cbff18c5d44529407edfd8e75743d2f51ce2b58573fea6fbd4fe25154b9964d
e = 0x9ab58dbc8049b574c361573955f08ea69f97ecf37400f9626d8f5ac55ca087165ce5e1f459ef6fa5f158cc8e75cb400a7473e89dd38922ead221b33bc33d6d716fb0e4e127b0fc18a197daf856a7062b49fba7a86e3a138956af04f481b7a7d481994aeebc2672e500f3f6d8c581268c2cfad4845158f79c2ef28f242f4fa8f6e573b8723a752d96169c9d885ada59cdeb6dbe932de86a019a7e8fc8aeb07748cfb272bd36d94fe83351252187c2e0bc58bb7a0a0af154b63397e6c68af4314601e29b07caed301b6831cf34caa579eb42a8c8bf69898d04b495174b5d7de0f20cf2b8fc55ed35c6ad157d3e7009f16d6b61786ee40583850e67af13e9d25be3
c = 0x3f984ff5244f1836ed69361f29905ca1ae6b3dcf249133c398d7762f5e277919174694293989144c9d25e940d2f66058b2289c75d1b8d0729f9a7c4564404a5fd4313675f85f31b47156068878e236c5635156b0fa21e24346c2041ae42423078577a1413f41375a4d49296ab17910ae214b45155c4570f95ca874ccae9fa80433a1ab453cbb28d780c2f1f4dc7071c93aff3924d76c5b4068a0371dff82531313f281a8acadaa2bd5078d3ddcefcb981f37ff9b8b14c7d9bf1accffe7857160982a2c7d9ee01d3e82265eec9c7401ecc7f02581fd0d912684f42d1b71df87a1ca51515aab4e58fab4da96e154ea6cdfb573a71d81b2ea4a080a1066e1bc3474
- solve:
Lần này mình thấy số e rất lớn, sau đó mình tìm hiểu được đây là dạng Wiener attack. https://en.wikipedia.org/wiki/Wiener%27s_attack
Mình lên mạng và tải tool RShack về để tìm ra d
Và mình tìm được:
d=79434351637397000170240219617391501050474168352481334243649813782018808904459
Vì N,e,c đang ở dạng hex nên mình đổi về dạng int để tính.
- code:

from Crypto.Util.number import *

N = int(0xb8af3d3afb893a602de4afe2a29d7615075d1e570f8bad8ebbe9b5b9076594cf06b6e7b30905b6420e950043380ea746f0a14dae34469aa723e946e484a58bcd92d1039105871ffd63ffe64534b7d7f8d84b4a569723f7a833e6daf5e182d658655f739a4e37bd9f4a44aff6ca0255cda5313c3048f56eed5b21dc8d88bf5a8f8379eac83d8523e484fa6ae8dbcb239e65d3777829a6903d779cd2498b255fcf275e5f49471f35992435ee7cade98c8e82a8beb5ce1749349caa16759afc4e799edb12d299374d748a9e3c82e1cc983cdf9daec0a2739dadcc0982c1e7e492139cbff18c5d44529407edfd8e75743d2f51ce2b58573fea6fbd4fe25154b9964d)
e = int(0x9ab58dbc8049b574c361573955f08ea69f97ecf37400f9626d8f5ac55ca087165ce5e1f459ef6fa5f158cc8e75cb400a7473e89dd38922ead221b33bc33d6d716fb0e4e127b0fc18a197daf856a7062b49fba7a86e3a138956af04f481b7a7d481994aeebc2672e500f3f6d8c581268c2cfad4845158f79c2ef28f242f4fa8f6e573b8723a752d96169c9d885ada59cdeb6dbe932de86a019a7e8fc8aeb07748cfb272bd36d94fe83351252187c2e0bc58bb7a0a0af154b63397e6c68af4314601e29b07caed301b6831cf34caa579eb42a8c8bf69898d04b495174b5d7de0f20cf2b8fc55ed35c6ad157d3e7009f16d6b61786ee40583850e67af13e9d25be3)
c = int(0x3f984ff5244f1836ed69361f29905ca1ae6b3dcf249133c398d7762f5e277919174694293989144c9d25e940d2f66058b2289c75d1b8d0729f9a7c4564404a5fd4313675f85f31b47156068878e236c5635156b0fa21e24346c2041ae42423078577a1413f41375a4d49296ab17910ae214b45155c4570f95ca874ccae9fa80433a1ab453cbb28d780c2f1f4dc7071c93aff3924d76c5b4068a0371dff82531313f281a8acadaa2bd5078d3ddcefcb981f37ff9b8b14c7d9bf1accffe7857160982a2c7d9ee01d3e82265eec9c7401ecc7f02581fd0d912684f42d1b71df87a1ca51515aab4e58fab4da96e154ea6cdfb573a71d81b2ea4a080a1066e1bc3474)

d=79434351637397000170240219617391501050474168352481334243649813782018808904459

m= pow(c,d,N)
print(long_to_bytes(m))
#crypto{s0m3th1ng5_c4n_b3_t00_b1g}