# Starter
---
## Modular Exponentiation:
### Description
- khá quen thuộc, bài nay thì tính nhanh ta dùng `pow()`
### Solution
```python=
pow(101,17,22663)
```
### Flag
```python=
pow(101,17,22663)
```
## Public Keys:
### Description
- Để mã hóa được số 12, ta cần chọn 1 giá trị m ( m < N), từ đó số 12 sẽ được mã hóa sang giá trị mới là:` encrypted value = 12^e mod n `
### Solution:
```python=
e=65537
p=17
q=23
N=p*q
encrypted_value = pow(12,e,N)
print(encrypted_value)
```
### Flag:
```python=
301
```
## Euler's Totient:
### Description
### Solution
- Euler's totient: `ФN = T = (p-1)*(q-1)` ( gọi tên khác là phi N)
### Flag
```python=
882564595536224140639625987657529300394956519977044270821168
```
## Private Keys:
### Description
### Solution:
- Theo như bài cho, giá trị của private key bằng nghịch đảo của e modulo ФN ( hoặc là T cho gọn )
```python=
p = 857504083339712752489993810777
q = 1029224947942998075080348647219
N= p*q
e= 65537
T= (p-1)*(q-1)
# private key là nghịch đảo modulo của e mod T
private_key= pow(e,-1,T)
print(private_key)
```
### Flag
```python=
121832886702415731577073962957377780195510499965398469843281
```
## RSA Decryption:
### Description
-Ở đây giá trị c đã bị encrypt thông qua public key{N,e}, từ private key tìm được ở bài 4, ta phải decrypt c để tìm ra flag
### Solution
```python=
p = 857504083339712752489993810777
q = 1029224947942998075080348647219
N= p*q
e= 65537
T= (p-1)*(q-1)
d=121832886702415731577073962957377780195510499965398469843281
encrypted_value= 77578995801157823671636298847186723593814843845525223303932
decrypted_value= pow(encrypted_value,d,N)
print(decrypted_value)
```
- `encrypted_value = c`
### Flag:
```python=
13371337
```
## RSA Signatures:
### Description
- **Việc sign cái 1 cái message ( gọi là m ) bao gồm 2 bước**:
1. hash cái message m -> H
2. encrypt H với private key: s = H^d mod N ( private key{d,N} )
- Bài yêu cầu chúng ta sign flag thông qua priavte key và hash function của SHA256. Ngoài ra đề cũng gợi ý về việc đầu ra là 1 số nên cần sử dụng hàm`bytes_to_long()`
### Solution 1:
```python=
from Crypto.Util.number import bytes_to_long
import hashlib
N = 15216583654836731327639981224133918855895948374072384050848479908982286890731769486609085918857664046075375253168955058743185664390273058074450390236774324903305663479046566232967297765731625328029814055635316002591227570271271445226094919864475407884459980489638001092788574811554149774028950310695112688723853763743238753349782508121985338746755237819373178699343135091783992299561827389745132880022259873387524273298850340648779897909381979714026837172003953221052431217940632552930880000919436507245150726543040714721553361063311954285289857582079880295199632757829525723874753306371990452491305564061051059885803
d = 11175901210643014262548222473449533091378848269490518850474399681690547281665059317155831692300453197335735728459259392366823302405685389586883670043744683993709123180805154631088513521456979317628012721881537154107239389466063136007337120599915456659758559300673444689263854921332185562706707573660658164991098457874495054854491474065039621922972671588299315846306069845169959451250821044417886630346229021305410340100401530146135418806544340908355106582089082980533651095594192031411679866134256418292249592135441145384466261279428795408721990564658703903787956958168449841491667690491585550160457893350536334242689
hash= hashlib.sha256()
hash.update(b'crypto{Immut4ble_m3ssag1ng}')
H= hash.digest()
s= pow(bytes_to_long(H),d,N)
print(s)
```
- Cùng phân tích 1 chút về đoạn code trên:
1. Để có thể hash được m mà đề cho thì chuyển m về dạng byte bằng cách thêm tiền tố `b'` và `import hashlib`
- tham khảo: https://www.geeksforgeeks.org/hashlib-module-in-python/ và https://docs.python.org/3/library/hashlib.html
2. `hash.digest()`: sẽ hash data chúng ta vừa update và trả về ở dạng bytes dài 256 bit
### Solution 2:
```python=
from Crypto.Hash import SHA256
from Crypto.Util.number import bytes_to_long
N = 15216583654836731327639981224133918855895948374072384050848479908982286890731769486609085918857664046075375253168955058743185664390273058074450390236774324903305663479046566232967297765731625328029814055635316002591227570271271445226094919864475407884459980489638001092788574811554149774028950310695112688723853763743238753349782508121985338746755237819373178699343135091783992299561827389745132880022259873387524273298850340648779897909381979714026837172003953221052431217940632552930880000919436507245150726543040714721553361063311954285289857582079880295199632757829525723874753306371990452491305564061051059885803
d = 11175901210643014262548222473449533091378848269490518850474399681690547281665059317155831692300453197335735728459259392366823302405685389586883670043744683993709123180805154631088513521456979317628012721881537154107239389466063136007337120599915456659758559300673444689263854921332185562706707573660658164991098457874495054854491474065039621922972671588299315846306069845169959451250821044417886630346229021305410340100401530146135418806544340908355106582089082980533651095594192031411679866134256418292249592135441145384466261279428795408721990564658703903787956958168449841491667690491585550160457893350536334242689
hash = SHA256.new(data=b'crypto{Immut4ble_m3ssag1ng}')
S = pow(bytes_to_long(hash.digest()), d, N)
print(hex(S)[2:])
```
# Primes part 1
## Factoring
### Description:
- Tách số 150 bit trên thành 2 phần tử nguyên tố
và phần tử bé hơn là đáp án
### Solution:
- ta có thể sử dụng: http://factordb.com/ để tách
### Flag:
`19704762736204164635843`
## Inferius prime
### Description:
- nghĩa là cái flag đã được mã hóa và bài cung cấp cho một số giá trị sau và đoạn code mã hóa:
```python=
n = 984994081290620368062168960884976209711107645166770780785733
e = 65537
ct = 948553474947320504624302879933619818331484350431616834086273
```
```python=
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
```
### Solution:
- Từ đoạn code trên, ta có thể thấy pt là flag được chuyển thành bytes và `ct` là flag đã được mã hóa -> theo bài ta cần tìm được flag, tức là `pt`
- Ở cuối đoạn code được cho, ta thấy được gợi ý về cách tìm flag, ta cần tìm được `d` để có thể giải mã `ct`
- Và do các giá trị đang ở dạng số mà kết quả lại là bytes nên cần dùng `long_to_bytes()` để chuyển đổi
```python=
from Crypto.Util.number import long_to_bytes
n = 984994081290620368062168960884976209711107645166770780785733
e = 65537
ct = 948553474947320504624302879933619818331484350431616834086273
p= 848445505077945374527983649411
q= 1160939713152385063689030212503
T= (p-1)*(q-1)
# từ công thức e.d mod T =1
d= pow(e,-1,T)
pt = pow(ct,d,n)
print(long_to_bytes(pt))
```
### Flag:
```python=
b'crypto{N33d_b1g_pR1m35}'
```
## Monoprime
### Description:
- Về câu hỏi ở đầu đề thì RSA vẫn sẽ hoạt động đối với N nhưng nó sẽ không có độ bảo mật tốt đối với giá trị N mà có thể tách thành các thừa số 1 cách dễ dàng. Vì khi như thế, người xấu có thể dễ dàng tìm ra private key thông qua công thức `e.d mod T = 1`. ( Nếu sử dụng giá trị N mà có nhiều hơn 2 thừa số, ít nhất 2 trong số các thừa số phải khó và lớn. Tuy nhiên ít người sử dụng đến cách này )
- Với n là 1 số nguyên tố, thì phi n sẽ bằng n-1 vì nó tính tất cả những số nguyên tố cùng nhau với n
### Solution:
```python=
from Crypto.Util.number import long_to_bytes
n = 171731371218065444125482536302245915415603318380280392385291836472299752747934607246477508507827284075763910264995326010251268493630501989810855418416643352631102434317900028697993224868629935657273062472544675693365930943308086634291936846505861203914449338007760990051788980485462592823446469606824421932591
e = 65537
ct = 161367550346730604451454756189028938964941280347662098798775466019463375610700074840105776873791605070092554650190486030367121011578171525759600774739890458414593857709994072516290998135846956596662071379067305011746842247628316996977338024343628757374524136260758515864509435302781735938531030576289086798942
T = n-1
d= pow(e,-1,T)
decrypted_value=pow(ct,d,n)
print(long_to_bytes(decrypted_value))
```
### Flag:
```python=
b'crypto{0n3_pr1m3_41n7_pr1m3_l0l}'
```
## Square eyes
### Description:
- Yêu cầu vẫn tương tự 2 bài trên, giải mã 1 flag bị mã hóa và có giá trị là ct
- Mối quan hệ giữa Фn và n:
->>> Do đó ta có `p = q = n^-2`, và k=2 >= 1, p là 1 số nguyên tố nên ta có thể tính `ФN=Фp^2` như sau:
### Solution:
```python=
from math import isqrt
from Crypto.Util.number import long_to_bytes
n = 535860808044009550029177135708168016201451343147313565371014459027743491739422885443084705720731409713775527993719682583669164873806842043288439828071789970694759080842162253955259590552283047728782812946845160334801782088068154453021936721710269050985805054692096738777321796153384024897615594493453068138341203673749514094546000253631902991617197847584519694152122765406982133526594928685232381934742152195861380221224370858128736975959176861651044370378539093990198336298572944512738570839396588590096813217791191895941380464803377602779240663133834952329316862399581950590588006371221334128215409197603236942597674756728212232134056562716399155080108881105952768189193728827484667349378091100068224404684701674782399200373192433062767622841264055426035349769018117299620554803902490432339600566432246795818167460916180647394169157647245603555692735630862148715428791242764799469896924753470539857080767170052783918273180304835318388177089674231640910337743789750979216202573226794240332797892868276309400253925932223895530714169648116569013581643192341931800785254715083294526325980247219218364118877864892068185905587410977152737936310734712276956663192182487672474651103240004173381041237906849437490609652395748868434296753449
e = 65537
ct = 222502885974182429500948389840563415291534726891354573907329512556439632810921927905220486727807436668035929302442754225952786602492250448020341217733646472982286222338860566076161977786095675944552232391481278782019346283900959677167026636830252067048759720251671811058647569724495547940966885025629807079171218371644528053562232396674283745310132242492367274184667845174514466834132589971388067076980563188513333661165819462428837210575342101036356974189393390097403614434491507672459254969638032776897417674577487775755539964915035731988499983726435005007850876000232292458554577437739427313453671492956668188219600633325930981748162455965093222648173134777571527681591366164711307355510889316052064146089646772869610726671696699221157985834325663661400034831442431209123478778078255846830522226390964119818784903330200488705212765569163495571851459355520398928214206285080883954881888668509262455490889283862560453598662919522224935145694435885396500780651530829377030371611921181207362217397805303962112100190783763061909945889717878397740711340114311597934724670601992737526668932871436226135393872881664511222789565256059138002651403875484920711316522536260604255269532161594824301047729082877262812899724246757871448545439896
p = q = isqrt(n)
T= (p-1)*p
d = pow(e,-1,T)
encrypted_value = pow(ct,d,n)
print(long_to_bytes(encrypted_value))
```
### Flag:
```python=
b'crypto{squar3_r00t_i5_f4st3r_th4n_f4ct0r1ng!}'
```
- Hàm `isqrt()`: phương thức này trong Python được sử dụng để lấy căn bậc hai của số nguyên không âm n đã cho. Phương thức này trả về giá trị sàn của căn bậc hai chính xác của n hoặc tương đương với số nguyên lớn nhất a sao cho a^2 <= n.
## Many prime
### Description:
```python=
n = 580642391898843192929563856870897799650883152718761762932292482252152591279871421569162037190419036435041797739880389529593674485555792234900969402019055601781662044515999210032698275981631376651117318677368742867687180140048715627160641771118040372573575479330830092989800730105573700557717146251860588802509310534792310748898504394966263819959963273509119791037525504422606634640173277598774814099540555569257179715908642917355365791447508751401889724095964924513196281345665480688029639999472649549163147599540142367575413885729653166517595719991872223011969856259344396899748662101941230745601719730556631637
e = 65537
ct = 320721490534624434149993723527322977960556510750628354856260732098109692581338409999983376131354918370047625150454728718467998870322344980985635149656977787964380651868131740312053755501594999166365821315043312308622388016666802478485476059625888033017198083472976011719998333985531756978678758897472845358167730221506573817798467100023754709109274265835201757369829744113233607359526441007577850111228850004361838028842815813724076511058179239339760639518034583306154826603816927757236549096339501503316601078891287408682099750164720032975016814187899399273719181407940397071512493967454225665490162619270814464
```
- Từ đề bài, vì sử dụng one prime factor để tạo nên N thì là không hiệu quả nên người ra đề đã sử dụng hơn 30 prime factors
- Sử dụng http://factordb.com/ để tách N thì được kết quả như sau
```python=
factors = [ 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,]
```
- Có factors,giá trị của p và q, thì giờ tính `ФN = (p-1)*(q-1)`
### Solution:
```python=
from Crypto.Util.number import long_to_bytes
n = 580642391898843192929563856870897799650883152718761762932292482252152591279871421569162037190419036435041797739880389529593674485555792234900969402019055601781662044515999210032698275981631376651117318677368742867687180140048715627160641771118040372573575479330830092989800730105573700557717146251860588802509310534792310748898504394966263819959963273509119791037525504422606634640173277598774814099540555569257179715908642917355365791447508751401889724095964924513196281345665480688029639999472649549163147599540142367575413885729653166517595719991872223011969856259344396899748662101941230745601719730556631637
e = 65537
ct = 320721490534624434149993723527322977960556510750628354856260732098109692581338409999983376131354918370047625150454728718467998870322344980985635149656977787964380651868131740312053755501594999166365821315043312308622388016666802478485476059625888033017198083472976011719998333985531756978678758897472845358167730221506573817798467100023754709109274265835201757369829744113233607359526441007577850111228850004361838028842815813724076511058179239339760639518034583306154826603816927757236549096339501503316601078891287408682099750164720032975016814187899399273719181407940397071512493967454225665490162619270814464
factors = [ 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,]
T=1
for i in factors:
T*=(i-1) # T = T*(i-1)
d= pow(e,-1,T)
decrypted_value=pow(ct,d,n)
print(long_to_bytes(decrypted_value))
```
### Flag:
```python=
b'crypto{700_m4ny_5m4ll_f4c70r5}'
```
# Public Exponent
> exponent: lũy thừa
## Salty
### Description:
-**Bài cho 2 dữ kiện**: chương trình đã mã hóa flag và giá trị của n,e,ct( flag sau khi bị mã hóa và chuyển từ bytes thành số )
```python=
n = 110581795715958566206600392161360212579669637391437097703685154237017351570464767725324182051199901920318211290404777259728923614917211291562555864753005179326101890427669819834642007924406862482343614488768256951616086287044725034412802176312273081322195866046098595306261781788276570920467840172004530873767
e = 1
ct = 44981230718212183604274785925793145442655465025264554046028251311164494127485
```
```python=
from Crypto.Util.number import getPrime, inverse, bytes_to_long, long_to_bytes
e = 1
d = -1
while d == -1:
p = getPrime(512)
q = getPrime(512)
phi = (p - 1) * (q - 1)
d = inverse(e, phi)
n = p * q
flag = b"XXXXXXXXXXXXXXXXXXXXXXX"
pt = bytes_to_long(flag)
ct = pow(pt, e, n)
print(f"n = {n}")
print(f"e = {e}")
print(f"ct = {ct}")
pt = pow(ct, d, n)
decrypted = long_to_bytes(pt)
assert decrypted == flag
```
- `getPrime()` : trả về giá trị là 1 số nguyên tố N bit, tham số nhận vào tương ứng với số bit và N phải lớn hơn 1
- Đoạn code cũng gợi ý về cách tìm flag ở cuối -> tìm được private key cũng như là p,q
- Do n là 1 số nguyên tố nên q,p={1,n}
### Solution:
```python=
from Crypto.Util.number import inverse,long_to_bytes
n = 110581795715958566206600392161360212579669637391437097703685154237017351570464767725324182051199901920318211290404777259728923614917211291562555864753005179326101890427669819834642007924406862482343614488768256951616086287044725034412802176312273081322195866046098595306261781788276570920467840172004530873767
e = 1
ct = 44981230718212183604274785925793145442655465025264554046028251311164494127485
p=n
q=1
phi =(p-1)*q
d= inverse(e,phi)
decrypted_value= pow(ct,d,n)
print(long_to_bytes(decrypted_value))
```
### Flag:
```python=
b'crypto{saltstack_fell_for_this!}'
```
#### Note:
- Có 1 cách khác là: `ct = pow(flag,e,n)` với **e = 1** nên ct chính là flag -> Cách tấn công RSA khi giá trị e nhỏ
## Modulus Inutilis
### Description:
```python=
n = 17258212916191948536348548470938004244269544560039009244721959293554822498047075403658429865201816363311805874117705688359853941515579440852166618074161313773416434156467811969628473425365608002907061241714688204565170146117869742910273064909154666642642308154422770994836108669814632309362483307560217924183202838588431342622551598499747369771295105890359290073146330677383341121242366368309126850094371525078749496850520075015636716490087482193603562501577348571256210991732071282478547626856068209192987351212490642903450263288650415552403935705444809043563866466823492258216747445926536608548665086042098252335883
e = 3
ct = 243251053617903760309941844835411292373350655973075480264001352919865180151222189820473358411037759381328642957324889519192337152355302808400638052620580409813222660643570085177957
```
- Do **e = 3** -> small e -> Flag = căn bậc 3 của ct
### Solution:
```python=
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))
```
### Flag:
```python=
b'crypto{N33d_m04R_p4dd1ng}'
```
## Everything is Big
### Description:
- Output đề cho:
```python=
N = 0xb8af3d3afb893a602de4afe2a29d7615075d1e570f8bad8ebbe9b5b9076594cf06b6e7b30905b6420e950043380ea746f0a14dae34469aa723e946e484a58bcd92d1039105871ffd63ffe64534b7d7f8d84b4a569723f7a833e6daf5e182d658655f739a4e37bd9f4a44aff6ca0255cda5313c3048f56eed5b21dc8d88bf5a8f8379eac83d8523e484fa6ae8dbcb239e65d3777829a6903d779cd2498b255fcf275e5f49471f35992435ee7cade98c8e82a8beb5ce1749349caa16759afc4e799edb12d299374d748a9e3c82e1cc983cdf9daec0a2739dadcc0982c1e7e492139cbff18c5d44529407edfd8e75743d2f51ce2b58573fea6fbd4fe25154b9964d
e = 0x9ab58dbc8049b574c361573955f08ea69f97ecf37400f9626d8f5ac55ca087165ce5e1f459ef6fa5f158cc8e75cb400a7473e89dd38922ead221b33bc33d6d716fb0e4e127b0fc18a197daf856a7062b49fba7a86e3a138956af04f481b7a7d481994aeebc2672e500f3f6d8c581268c2cfad4845158f79c2ef28f242f4fa8f6e573b8723a752d96169c9d885ada59cdeb6dbe932de86a019a7e8fc8aeb07748cfb272bd36d94fe83351252187c2e0bc58bb7a0a0af154b63397e6c68af4314601e29b07caed301b6831cf34caa579eb42a8c8bf69898d04b495174b5d7de0f20cf2b8fc55ed35c6ad157d3e7009f16d6b61786ee40583850e67af13e9d25be3
c = 0x3f984ff5244f1836ed69361f29905ca1ae6b3dcf249133c398d7762f5e277919174694293989144c9d25e940d2f66058b2289c75d1b8d0729f9a7c4564404a5fd4313675f85f31b47156068878e236c5635156b0fa21e24346c2041ae42423078577a1413f41375a4d49296ab17910ae214b45155c4570f95ca874ccae9fa80433a1ab453cbb28d780c2f1f4dc7071c93aff3924d76c5b4068a0371dff82531313f281a8acadaa2bd5078d3ddcefcb981f37ff9b8b14c7d9bf1accffe7857160982a2c7d9ee01d3e82265eec9c7401ecc7f02581fd0d912684f42d1b71df87a1ca51515aab4e58fab4da96e154ea6cdfb573a71d81b2ea4a080a1066e1bc3474
```
- Từ output và đoạn code đề bài cho, ta có thể thấy giá trị e và N đều rất lớn, suy ra giá trị d sẽ nhỏ nên bài này sử dụng Wiener Attack
https://cryptohack.gitbook.io/cryptobook/untitled/low-private-component-attacks/wieners-attack
https://hackmd.io/@an1/ByGpxb12A
### Solution:
```python=
N = 0xb8af3d3afb893a602de4afe2a29d7615075d1e570f8bad8ebbe9b5b9076594cf06b6e7b30905b6420e950043380ea746f0a14dae34469aa723e946e484a58bcd92d1039105871ffd63ffe64534b7d7f8d84b4a569723f7a833e6daf5e182d658655f739a4e37bd9f4a44aff6ca0255cda5313c3048f56eed5b21dc8d88bf5a8f8379eac83d8523e484fa6ae8dbcb239e65d3777829a6903d779cd2498b255fcf275e5f49471f35992435ee7cade98c8e82a8beb5ce1749349caa16759afc4e799edb12d299374d748a9e3c82e1cc983cdf9daec0a2739dadcc0982c1e7e492139cbff18c5d44529407edfd8e75743d2f51ce2b58573fea6fbd4fe25154b9964d
e = 0x9ab58dbc8049b574c361573955f08ea69f97ecf37400f9626d8f5ac55ca087165ce5e1f459ef6fa5f158cc8e75cb400a7473e89dd38922ead221b33bc33d6d716fb0e4e127b0fc18a197daf856a7062b49fba7a86e3a138956af04f481b7a7d481994aeebc2672e500f3f6d8c581268c2cfad4845158f79c2ef28f242f4fa8f6e573b8723a752d96169c9d885ada59cdeb6dbe932de86a019a7e8fc8aeb07748cfb272bd36d94fe83351252187c2e0bc58bb7a0a0af154b63397e6c68af4314601e29b07caed301b6831cf34caa579eb42a8c8bf69898d04b495174b5d7de0f20cf2b8fc55ed35c6ad157d3e7009f16d6b61786ee40583850e67af13e9d25be3
c = 0x3f984ff5244f1836ed69361f29905ca1ae6b3dcf249133c398d7762f5e277919174694293989144c9d25e940d2f66058b2289c75d1b8d0729f9a7c4564404a5fd4313675f85f31b47156068878e236c5635156b0fa21e24346c2041ae42423078577a1413f41375a4d49296ab17910ae214b45155c4570f95ca874ccae9fa80433a1ab453cbb28d780c2f1f4dc7071c93aff3924d76c5b4068a0371dff82531313f281a8acadaa2bd5078d3ddcefcb981f37ff9b8b14c7d9bf1accffe7857160982a2c7d9ee01d3e82265eec9c7401ecc7f02581fd0d912684f42d1b71df87a1ca51515aab4e58fab4da96e154ea6cdfb573a71d81b2ea4a080a1066e1bc3474
import owiener
from Crypto.Util.number import long_to_bytes
d = owiener.attack(e, N)
if d:
m = pow(c, d, N)
flag = long_to_bytes(m).decode()
print(flag)
else:
print("Wiener's Attack failed.")
```
### Flag:
```python=
crypto{s0m3th1ng5_c4n_b3_t00_b1g}
```
## Crossed Wires
### Description:
Output đề cho:
```python=
My private key: (21711308225346315542706844618441565741046498277716979943478360598053144971379956916575370343448988601905854572029635846626259487297950305231661109855854947494209135205589258643517961521594924368498672064293208230802441077390193682958095111922082677813175804775628884377724377647428385841831277059274172982280545237765559969228707506857561215268491024097063920337721783673060530181637161577401589126558556182546896783307370517275046522704047385786111489447064794210010802761708615907245523492585896286374996088089317826162798278528296206977900274431829829206103227171839270887476436899494428371323874689055690729986771, 2734411677251148030723138005716109733838866545375527602018255159319631026653190783670493107936401603981429171880504360560494771017246468702902647370954220312452541342858747590576273775107870450853533717116684326976263006435733382045807971890762018747729574021057430331778033982359184838159747331236538501849965329264774927607570410347019418407451937875684373454982306923178403161216817237890962651214718831954215200637651103907209347900857824722653217179548148145687181377220544864521808230122730967452981435355334932104265488075777638608041325256776275200067541533022527964743478554948792578057708522350812154888097)
My Friend's public keys: [(21711308225346315542706844618441565741046498277716979943478360598053144971379956916575370343448988601905854572029635846626259487297950305231661109855854947494209135205589258643517961521594924368498672064293208230802441077390193682958095111922082677813175804775628884377724377647428385841831277059274172982280545237765559969228707506857561215268491024097063920337721783673060530181637161577401589126558556182546896783307370517275046522704047385786111489447064794210010802761708615907245523492585896286374996088089317826162798278528296206977900274431829829206103227171839270887476436899494428371323874689055690729986771, 106979), (21711308225346315542706844618441565741046498277716979943478360598053144971379956916575370343448988601905854572029635846626259487297950305231661109855854947494209135205589258643517961521594924368498672064293208230802441077390193682958095111922082677813175804775628884377724377647428385841831277059274172982280545237765559969228707506857561215268491024097063920337721783673060530181637161577401589126558556182546896783307370517275046522704047385786111489447064794210010802761708615907245523492585896286374996088089317826162798278528296206977900274431829829206103227171839270887476436899494428371323874689055690729986771, 108533), (21711308225346315542706844618441565741046498277716979943478360598053144971379956916575370343448988601905854572029635846626259487297950305231661109855854947494209135205589258643517961521594924368498672064293208230802441077390193682958095111922082677813175804775628884377724377647428385841831277059274172982280545237765559969228707506857561215268491024097063920337721783673060530181637161577401589126558556182546896783307370517275046522704047385786111489447064794210010802761708615907245523492585896286374996088089317826162798278528296206977900274431829829206103227171839270887476436899494428371323874689055690729986771, 69557), (21711308225346315542706844618441565741046498277716979943478360598053144971379956916575370343448988601905854572029635846626259487297950305231661109855854947494209135205589258643517961521594924368498672064293208230802441077390193682958095111922082677813175804775628884377724377647428385841831277059274172982280545237765559969228707506857561215268491024097063920337721783673060530181637161577401589126558556182546896783307370517275046522704047385786111489447064794210010802761708615907245523492585896286374996088089317826162798278528296206977900274431829829206103227171839270887476436899494428371323874689055690729986771, 97117), (21711308225346315542706844618441565741046498277716979943478360598053144971379956916575370343448988601905854572029635846626259487297950305231661109855854947494209135205589258643517961521594924368498672064293208230802441077390193682958095111922082677813175804775628884377724377647428385841831277059274172982280545237765559969228707506857561215268491024097063920337721783673060530181637161577401589126558556182546896783307370517275046522704047385786111489447064794210010802761708615907245523492585896286374996088089317826162798278528296206977900274431829829206103227171839270887476436899494428371323874689055690729986771, 103231)]
Encrypted flag: 20304610279578186738172766224224793119885071262464464448863461184092225736054747976985179673905441502689126216282897704508745403799054734121583968853999791604281615154100736259131453424385364324630229671185343778172807262640709301838274824603101692485662726226902121105591137437331463201881264245562214012160875177167442010952439360623396658974413900469093836794752270399520074596329058725874834082188697377597949405779039139194196065364426213208345461407030771089787529200057105746584493554722790592530472869581310117300343461207750821737840042745530876391793484035024644475535353227851321505537398888106855012746117
```
- Từ output ta có được d,N và 5 giá trị e khác nhau của 5 người bạn, do đó ta có thể suy ra `ct = m^(e1*e2*e3*e4*e5) mod N` và ở đây `e1*e2*e3*e4*e5` là 1 giá trị e
- Thông qua factordb, ta tách được N thành p,q
### Solution:
```python=
from Crypto.Util.number import long_to_bytes
d=2734411677251148030723138005716109733838866545375527602018255159319631026653190783670493107936401603981429171880504360560494771017246468702902647370954220312452541342858747590576273775107870450853533717116684326976263006435733382045807971890762018747729574021057430331778033982359184838159747331236538501849965329264774927607570410347019418407451937875684373454982306923178403161216817237890962651214718831954215200637651103907209347900857824722653217179548148145687181377220544864521808230122730967452981435355334932104265488075777638608041325256776275200067541533022527964743478554948792578057708522350812154888097
N=21711308225346315542706844618441565741046498277716979943478360598053144971379956916575370343448988601905854572029635846626259487297950305231661109855854947494209135205589258643517961521594924368498672064293208230802441077390193682958095111922082677813175804775628884377724377647428385841831277059274172982280545237765559969228707506857561215268491024097063920337721783673060530181637161577401589126558556182546896783307370517275046522704047385786111489447064794210010802761708615907245523492585896286374996088089317826162798278528296206977900274431829829206103227171839270887476436899494428371323874689055690729986771
e5 =[106979, 108533,69557,97117,103231]
ct= 20304610279578186738172766224224793119885071262464464448863461184092225736054747976985179673905441502689126216282897704508745403799054734121583968853999791604281615154100736259131453424385364324630229671185343778172807262640709301838274824603101692485662726226902121105591137437331463201881264245562214012160875177167442010952439360623396658974413900469093836794752270399520074596329058725874834082188697377597949405779039139194196065364426213208345461407030771089787529200057105746584493554722790592530472869581310117300343461207750821737840042745530876391793484035024644475535353227851321505537398888106855012746117
p= 134460556242811604004061671529264401215233974442536870999694816691450423689575549530215841622090861571494882591368883283016107051686642467260643894947947473532769025695530343815260424314855023688439603651834585971233941772580950216838838690315383700689885536546289584980534945897919914730948196240662991266027
q= 161469718942256895682124261315253003309512855995894840701317251772156087404025170146631429756064534716206164807382734456438092732743677793224010769460318383691408352089793973150914149255603969984103815563896440419666191368964699279209687091969164697704779792586727943470780308857107052647197945528236341228473
fn=(p-1)*(q-1)
e =1
# tìm giá trị e = e1*e2*e3*e4*e5
for i in e5:
e *= i
d= pow(e,-1,fn)
flag= pow(ct,d,N)
print(long_to_bytes(flag))
```
### Flag:
```python=
b'crypto{3ncrypt_y0ur_s3cr3t_w1th_y0ur_fr1end5_publ1c_k3y}'
```
## Everything is still big
### Description:
- Output:
```python=
N = 0xb12746657c720a434861e9a4828b3c89a6b8d4a1bd921054e48d47124dbcc9cfcdcc39261c5e93817c167db818081613f57729e0039875c72a5ae1f0bc5ef7c933880c2ad528adbc9b1430003a491e460917b34c4590977df47772fab1ee0ab251f94065ab3004893fe1b2958008848b0124f22c4e75f60ed3889fb62e5ef4dcc247a3d6e23072641e62566cd96ee8114b227b8f498f9a578fc6f687d07acdbb523b6029c5bbeecd5efaf4c4d35304e5e6b5b95db0e89299529eb953f52ca3247d4cd03a15939e7d638b168fd00a1cb5b0cc5c2cc98175c1ad0b959c2ab2f17f917c0ccee8c3fe589b4cb441e817f75e575fc96a4fe7bfea897f57692b050d2b
e = 0x9d0637faa46281b533e83cc37e1cf5626bd33f712cc1948622f10ec26f766fb37b9cd6c7a6e4b2c03bce0dd70d5a3a28b6b0c941d8792bc6a870568790ebcd30f40277af59e0fd3141e272c48f8e33592965997c7d93006c27bf3a2b8fb71831dfa939c0ba2c7569dd1b660efc6c8966e674fbe6e051811d92a802c789d895f356ceec9722d5a7b617d21b8aa42dd6a45de721953939a5a81b8dffc9490acd4f60b0c0475883ff7e2ab50b39b2deeedaefefffc52ae2e03f72756d9b4f7b6bd85b1a6764b31312bc375a2298b78b0263d492205d2a5aa7a227abaf41ab4ea8ce0e75728a5177fe90ace36fdc5dba53317bbf90e60a6f2311bb333bf55ba3245f
c = 0xa3bce6e2e677d7855a1a7819eb1879779d1e1eefa21a1a6e205c8b46fdc020a2487fdd07dbae99274204fadda2ba69af73627bdddcb2c403118f507bca03cb0bad7a8cd03f70defc31fa904d71230aab98a10e155bf207da1b1cac1503f48cab3758024cc6e62afe99767e9e4c151b75f60d8f7989c152fdf4ff4b95ceed9a7065f38c68dee4dd0da503650d3246d463f504b36e1d6fafabb35d2390ecf0419b2bb67c4c647fb38511b34eb494d9289c872203fa70f4084d2fa2367a63a8881b74cc38730ad7584328de6a7d92e4ca18098a15119baee91237cea24975bdfc19bdbce7c1559899a88125935584cd37c8dd31f3f2b4517eefae84e7e588344fa5
```
- Đoạn code đề cho:
```python=
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)}')
```
- Có thể thấy bài này ta không thể sử dụng Wiener do : `(3*d)**4 > N`, ta sẽ sử dụng Boneh Durfee - một phiên bản cao cấp hơn so với Wiener
### Solution:
- Do chưa code được nên ở đây mình dùng code có sẵn để từ đó tìm ra private key d rồi tìm ra flag
```python=
from Crypto.Util.number import *
N = 0xb8af3d3afb893a602de4afe2a29d7615075d1e570f8bad8ebbe9b5b9076594cf06b6e7b30905b6420e950043380ea746f0a14dae34469aa723e946e484a58bcd92d1039105871ffd63ffe64534b7d7f8d84b4a569723f7a833e6daf5e182d658655f739a4e37bd9f4a44aff6ca0255cda5313c3048f56eed5b21dc8d88bf5a8f8379eac83d8523e484fa6ae8dbcb239e65d3777829a6903d779cd2498b255fcf275e5f49471f35992435ee7cade98c8e82a8beb5ce1749349caa16759afc4e799edb12d299374d748a9e3c82e1cc983cdf9daec0a2739dadcc0982c1e7e492139cbff18c5d44529407edfd8e75743d2f51ce2b58573fea6fbd4fe25154b9964d
e = 0x9ab58dbc8049b574c361573955f08ea69f97ecf37400f9626d8f5ac55ca087165ce5e1f459ef6fa5f158cc8e75cb400a7473e89dd38922ead221b33bc33d6d716fb0e4e127b0fc18a197daf856a7062b49fba7a86e3a138956af04f481b7a7d481994aeebc2672e500f3f6d8c581268c2cfad4845158f79c2ef28f242f4fa8f6e573b8723a752d96169c9d885ada59cdeb6dbe932de86a019a7e8fc8aeb07748cfb272bd36d94fe83351252187c2e0bc58bb7a0a0af154b63397e6c68af4314601e29b07caed301b6831cf34caa579eb42a8c8bf69898d04b495174b5d7de0f20cf2b8fc55ed35c6ad157d3e7009f16d6b61786ee40583850e67af13e9d25be3
c = 0x3f984ff5244f1836ed69361f29905ca1ae6b3dcf249133c398d7762f5e277919174694293989144c9d25e940d2f66058b2289c75d1b8d0729f9a7c4564404a5fd4313675f85f31b47156068878e236c5635156b0fa21e24346c2041ae42423078577a1413f41375a4d49296ab17910ae214b45155c4570f95ca874ccae9fa80433a1ab453cbb28d780c2f1f4dc7071c93aff3924d76c5b4068a0371dff82531313f281a8acadaa2bd5078d3ddcefcb981f37ff9b8b14c7d9bf1accffe7857160982a2c7d9ee01d3e82265eec9c7401ecc7f02581fd0d912684f42d1b71df87a1ca51515aab4e58fab4da96e154ea6cdfb573a71d81b2ea4a080a1066e1bc3474
d = 79434351637397000170240219617391501050474168352481334243649813782018808904459
flag = pow(c,d,N)
print(long_to_bytes(flag))
```
### Flag:
```python=
crypto{bon3h5_4tt4ck_i5_sr0ng3r_th4n_w13n3r5}
```
## Endless Emails
### Description:
- Output:
```p
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
```
### Solution:
- Nhìn vào đề, ta có thể thấy Johan gửi cùng một tin nhắn tới tất cả sinh viên và ta cũng có thể thấy các bộ 3 `(c,n,e)` với giá trị e giống nhau . Suy ra đây là **Hastad’s Broadcast Attack**.
- Với **Hastad’s Broadcast Attack**, ta sẽ sử dung CRT để giải. Do CRT cần ít nhất 3 cặp `(c,n)` nên ta sẽ chọn 3 cặp `(c,n)` bất kì từ 7 cặp trên và sử dụng `e = 3`.
```python=
from itertools import combinations
from Crypto.Util.number import inverse, long_to_bytes
from gmpy2 import iroot
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):
K = n[i]*n[j]*n[k]
M1 = K // n[i]
M2 = K // n[j]
M3 = K // n[k]
y1 = inverse(M1,n[i])
y2 = inverse(M2,n[j])
y3 = inverse(M3,n[k])
M = (c[i]*y1*M1 + c[j]*y2*M2 + c[k]*y3*M3) % K
flag = long_to_bytes(iroot(M, e)[0])
if b'crypto' in flag:
print(flag.decode())
```
- `iroot(a,n)`: trả về kết quả là một `tuple` gồm: integer root ( căn bậc n của a) và boolean ( True hoặc False ) - đảm bảo kết quả tính căn bậc n là chính xác
`long_to_bytes()` chỉ nhận tham số là `integer` nên khi tính `flag` ta chỉ lấy thằng đầu tiên trong `tuple`.
- `combinations(iterable,r)`: cho phép tạo ra các tổ hợp gồm `r` giá trị từ `iterable`.
VD: `combinations(range(7),3)` cho ra kết quả là các tổ hợp gồm 3 giá trị với các giá trị trong đoạn [1,7]
### Flag:
```python=
crypto{1f_y0u_d0nt_p4d_y0u_4r3_Vuln3rabl3}
```
# Primes part 2
## Infinite Descent
### Description:
Finding large primes is slow, so I've devised an optimisation.
- Source code:
```python=
import random
from Crypto.Util.number import bytes_to_long, isPrime
FLAG = b"crypto{???????????????????}"
def getPrimes(bitsize):
r = random.getrandbits(bitsize)
p, q = r, r
while not isPrime(p):
p += random.getrandbits(bitsize//4)
while not isPrime(q):
q += random.getrandbits(bitsize//8)
return p, q
m = bytes_to_long(FLAG)
p, q = getPrimes(2048)
n = p * q
e = 0x10001
c = pow(m, e, n)
print(f"n = {n}")
print(f"e = {e}")
print(f"c = {c}")
```
- Output:
```python=
n = 383347712330877040452238619329524841763392526146840572232926924642094891453979246383798913394114305368360426867021623649667024217266529000859703542590316063318592391925062014229671423777796679798747131250552455356061834719512365575593221216339005132464338847195248627639623487124025890693416305788160905762011825079336880567461033322240015771102929696350161937950387427696385850443727777996483584464610046380722736790790188061964311222153985614287276995741553706506834906746892708903948496564047090014307484054609862129530262108669567834726352078060081889712109412073731026030466300060341737504223822014714056413752165841749368159510588178604096191956750941078391415634472219765129561622344109769892244712668402761549412177892054051266761597330660545704317210567759828757156904778495608968785747998059857467440128156068391746919684258227682866083662345263659558066864109212457286114506228470930775092735385388316268663664139056183180238043386636254075940621543717531670995823417070666005930452836389812129462051771646048498397195157405386923446893886593048680984896989809135802276892911038588008701926729269812453226891776546037663583893625479252643042517196958990266376741676514631089466493864064316127648074609662749196545969926051
e = 65537
c = 98280456757136766244944891987028935843441533415613592591358482906016439563076150526116369842213103333480506705993633901994107281890187248495507270868621384652207697607019899166492132408348789252555196428608661320671877412710489782358282011364127799563335562917707783563681920786994453004763755404510541574502176243896756839917991848428091594919111448023948527766368304503100650379914153058191140072528095898576018893829830104362124927140555107994114143042266758709328068902664037870075742542194318059191313468675939426810988239079424823495317464035252325521917592045198152643533223015952702649249494753395100973534541766285551891859649320371178562200252228779395393974169736998523394598517174182142007480526603025578004665936854657294541338697513521007818552254811797566860763442604365744596444735991732790926343720102293453429936734206246109968817158815749927063561835274636195149702317415680401987150336994583752062565237605953153790371155918439941193401473271753038180560129784192800351649724465553733201451581525173536731674524145027931923204961274369826379325051601238308635192540223484055096203293400419816024111797903442864181965959247745006822690967920957905188441550106930799896292835287867403979631824085790047851383294389
```
### Solution:
- Có thể thấy giá trị p,q khá gần nhau và thoả mãn ( p – q ) < n¼, nên ở đây sẽ thử dùng Fermat attack để tìm flag.
- soucre code để có thể tách n và tìm p,q: https://github.com/truong92cdv/ctf_tool/blob/master/RsaCtfTool/fermat.py
```python=
from Crypto.Util.number import long_to_bytes, inverse
from math import isqrt
n = 383347712330877040452238619329524841763392526146840572232926924642094891453979246383798913394114305368360426867021623649667024217266529000859703542590316063318592391925062014229671423777796679798747131250552455356061834719512365575593221216339005132464338847195248627639623487124025890693416305788160905762011825079336880567461033322240015771102929696350161937950387427696385850443727777996483584464610046380722736790790188061964311222153985614287276995741553706506834906746892708903948496564047090014307484054609862129530262108669567834726352078060081889712109412073731026030466300060341737504223822014714056413752165841749368159510588178604096191956750941078391415634472219765129561622344109769892244712668402761549412177892054051266761597330660545704317210567759828757156904778495608968785747998059857467440128156068391746919684258227682866083662345263659558066864109212457286114506228470930775092735385388316268663664139056183180238043386636254075940621543717531670995823417070666005930452836389812129462051771646048498397195157405386923446893886593048680984896989809135802276892911038588008701926729269812453226891776546037663583893625479252643042517196958990266376741676514631089466493864064316127648074609662749196545969926051
e = 65537
c = 98280456757136766244944891987028935843441533415613592591358482906016439563076150526116369842213103333480506705993633901994107281890187248495507270868621384652207697607019899166492132408348789252555196428608661320671877412710489782358282011364127799563335562917707783563681920786994453004763755404510541574502176243896756839917991848428091594919111448023948527766368304503100650379914153058191140072528095898576018893829830104362124927140555107994114143042266758709328068902664037870075742542194318059191313468675939426810988239079424823495317464035252325521917592045198152643533223015952702649249494753395100973534541766285551891859649320371178562200252228779395393974169736998523394598517174182142007480526603025578004665936854657294541338697513521007818552254811797566860763442604365744596444735991732790926343720102293453429936734206246109968817158815749927063561835274636195149702317415680401987150336994583752062565237605953153790371155918439941193401473271753038180560129784192800351649724465553733201451581525173536731674524145027931923204961274369826379325051601238308635192540223484055096203293400419816024111797903442864181965959247745006822690967920957905188441550106930799896292835287867403979631824085790047851383294389
p = 195792674104747095987493147509542111706218625610062336124403520222867868823726191300716398241097835405645124290816741323
368119724045639570254650340257812064666317307845163372102913343563964717321687427397904641098810392194525044566115891543
494273038327899685022043003165855440800034236691201860951884784807611081682993703269281278887868193923724770695153181797
517029858090242101642434095446927086842150422269320810528310285700603089630932176221831116433356923610198974492654022905
400257905815899808678478842818622166035715362553822980353378658851533281696341783232790047499151972701203233404169650141
36429743252761521
q = 195792674104747095987493147509542111706218625610062336124403520222867868823726191300716398241097835405645124290816741323
368119724045639570254650340257812064666317307845163372102913343563964717321687427397904641098810392194525044566115891543
494273038327899685022043003165855440800034236691201860951884784807611081682993703269281278887868193923724770695153181797
517029858090242101642434095446927086842150422269320810528310285700603089630932176221831116433356923626352035828685261788
380189469867926568198852610698903155005508023036225510298210584591637027518937986764434156811444290969896644737058506197
92495553724950931
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
p, q = fermat(n)
phi = (p-1)*(q-1)
d = inverse(e,phi)
flag = pow(c,d,n)
print(long_to_bytes(flag))
```
### Flag:
```python=
crypto{f3rm47_w45_4_g3n1u5}
```
## Marin's secrets
### Description:
- marin.py
```python=
import random
from Crypto.Util.number import bytes_to_long
from secret import secrets, flag
def get_prime(secret):
prime = 1
for _ in range(secret):
prime = prime << 1
return prime - 1
random.shuffle(secrets)
m = bytes_to_long(flag)
p = get_prime(secrets[0])
q = get_prime(secrets[1])
n = p * q
e = 0x10001
c = pow(m, e, n)
print(f"n = {n}")
print(f"e = {e}")
print(f"c = {c}")
```
- output:
```python=
n: 658416274830184544125027519921443515789888264156074733099244040126213682497714032798116399288176502462829255784525977722903018714434309698108208388664768262754316426220651576623731617882923164117579624827261244506084274371250277849351631679441171018418018498039996472549893150577189302871520311715179730714312181456245097848491669795997289830612988058523968384808822828370900198489249243399165125219244753790779764466236965135793576516193213175061401667388622228362042717054014679032953441034021506856017081062617572351195418505899388715709795992029559042119783423597324707100694064675909238717573058764118893225111602703838080618565401139902143069901117174204252871948846864436771808616432457102844534843857198735242005309073939051433790946726672234643259349535186268571629077937597838801337973092285608744209951533199868228040004432132597073390363357892379997655878857696334892216345070227646749851381208554044940444182864026513709449823489593439017366358869648168238735087593808344484365136284219725233811605331815007424582890821887260682886632543613109252862114326372077785369292570900594814481097443781269562647303671428895764224084402259605109600363098950091998891375812839523613295667253813978434879172781217285652895469194181218343078754501694746598738215243769747956572555989594598180639098344891175879455994652382137038240166358066403475457
e: 65537
c: 400280463088930432319280359115194977582517363610532464295210669530407870753439127455401384569705425621445943992963380983084917385428631223046908837804126399345875252917090184158440305503817193246288672986488987883177380307377025079266030262650932575205141853413302558460364242355531272967481409414783634558791175827816540767545944534238189079030192843288596934979693517964655661507346729751987928147021620165009965051933278913952899114253301044747587310830419190623282578931589587504555005361571572561916866063458812965314474160499067525067495140150092119620928363007467390920130717521169105167963364154636472055084012592138570354390246779276003156184676298710746583104700516466091034510765027167956117869051938116457370384737440965109619578227422049806566060571831017610877072484262724789571076529586427405780121096546942812322324807145137017942266863534989082115189065560011841150908380937354301243153206428896320576609904361937035263985348984794208198892615898907005955403529470847124269512316191753950203794578656029324506688293446571598506042198219080325747328636232040936761788558421528960279832802127562115852304946867628316502959562274485483867481731149338209009753229463924855930103271197831370982488703456463385914801246828662212622006947380115549529820197355738525329885232170215757585685484402344437894981555179129287164971002033759724456
```
### Solution:
- Từ source code, có thể thấy` p = 2**a -1 `và `q = 2**b -1` với a,b là các số nguyên bất kì thuộc secrets.
- Từ đó ta có:
```python=
n = (2**a -1)*(2**b -1)
= (2**a * 2**b) - 2**a - 2**b +1
n-1 = (2**a * 2**b) - 2**a - 2**b
```
- Vậy n-1 là 1 số chia hết cho 2, ta cho chạy vòng lặp để tìm a.
```
from Crypto.Util.number import long_to_bytes , inverse
n = 658416274830184544125027519921443515789888264156074733099244040126213682497714032798116399288176502462829255784525977722903018714434309698108208388664768262754316426220651576623731617882923164117579624827261244506084274371250277849351631679441171018418018498039996472549893150577189302871520311715179730714312181456245097848491669795997289830612988058523968384808822828370900198489249243399165125219244753790779764466236965135793576516193213175061401667388622228362042717054014679032953441034021506856017081062617572351195418505899388715709795992029559042119783423597324707100694064675909238717573058764118893225111602703838080618565401139902143069901117174204252871948846864436771808616432457102844534843857198735242005309073939051433790946726672234643259349535186268571629077937597838801337973092285608744209951533199868228040004432132597073390363357892379997655878857696334892216345070227646749851381208554044940444182864026513709449823489593439017366358869648168238735087593808344484365136284219725233811605331815007424582890821887260682886632543613109252862114326372077785369292570900594814481097443781269562647303671428895764224084402259605109600363098950091998891375812839523613295667253813978434879172781217285652895469194181218343078754501694746598738215243769747956572555989594598180639098344891175879455994652382137038240166358066403475457
e = 65537
c = 400280463088930432319280359115194977582517363610532464295210669530407870753439127455401384569705425621445943992963380983084917385428631223046908837804126399345875252917090184158440305503817193246288672986488987883177380307377025079266030262650932575205141853413302558460364242355531272967481409414783634558791175827816540767545944534238189079030192843288596934979693517964655661507346729751987928147021620165009965051933278913952899114253301044747587310830419190623282578931589587504555005361571572561916866063458812965314474160499067525067495140150092119620928363007467390920130717521169105167963364154636472055084012592138570354390246779276003156184676298710746583104700516466091034510765027167956117869051938116457370384737440965109619578227422049806566060571831017610877072484262724789571076529586427405780121096546942812322324807145137017942266863534989082115189065560011841150908380937354301243153206428896320576609904361937035263985348984794208198892615898907005955403529470847124269512316191753950203794578656029324506688293446571598506042198219080325747328636232040936761788558421528960279832802127562115852304946867628316502959562274485483867481731149338209009753229463924855930103271197831370982488703456463385914801246828662212622006947380115549529820197355738525329885232170215757585685484402344437894981555179129287164971002033759724456
cc = n - 1
a = 0
while cc % 2 ==0:
cc //= 2
a += 1
p = 2**a -1
q = n // p
phi = (p-1)*(q-1)
d = inverse(e,phi)
flag = pow(c,d,n)
print(long_to_bytes(flag))
```
### Flag:
```python=
crypto{Th3se_Pr1m3s_4r3_t00_r4r3}
```
## Fast Primes
### Description:
- source code:
```python=
#!/usr/bin/env python3
import math
import random
from Crypto.Cipher import PKCS1_OAEP
from Crypto.PublicKey import RSA
from Crypto.Util.number import bytes_to_long, inverse
from gmpy2 import is_prime
FLAG = b"crypto{????????????}"
primes = []
def sieve(maximum=10000):
# In general Sieve of Sundaram, produces primes smaller
# than (2*x + 2) for a number given number x. Since
# we want primes smaller than maximum, we reduce maximum to half
# This array is used to separate numbers of the form
# i+j+2ij from others where 1 <= i <= j
marked = [False]*(int(maximum/2)+1)
# Main logic of Sundaram. Mark all numbers which
# do not generate prime number by doing 2*i+1
for i in range(1, int((math.sqrt(maximum)-1)/2)+1):
for j in range(((i*(i+1)) << 1), (int(maximum/2)+1), (2*i+1)):
marked[j] = True
# Since 2 is a prime number
primes.append(2)
# Print other primes. Remaining primes are of the
# form 2*i + 1 such that marked[i] is false.
for i in range(1, int(maximum/2)):
if (marked[i] == False):
primes.append(2*i + 1)
def get_primorial(n):
result = 1
for i in range(n):
result = result * primes[i]
return result
def get_fast_prime():
M = get_primorial(40)
while True:
k = random.randint(2**28, 2**29-1)
a = random.randint(2**20, 2**62-1)
p = k * M + pow(e, a, M)
if is_prime(p):
return p
sieve()
e = 0x10001
m = bytes_to_long(FLAG)
p = get_fast_prime()
q = get_fast_prime()
n = p * q
phi = (p - 1) * (q - 1)
d = inverse(e, phi)
key = RSA.construct((n, e, d))
cipher = PKCS1_OAEP.new(key)
ciphertext = cipher.encrypt(FLAG)
assert cipher.decrypt(ciphertext) == FLAG
exported = key.publickey().export_key()
with open("key.pem", 'wb') as f:
f.write(exported)
with open('ciphertext.txt', 'w') as f:
f.write(ciphertext.hex())
```
- key.pem
```
-----BEGIN PUBLIC KEY-----
MFswDQYJKoZIhvcNAQEBBQADSgAwRwJATKIe3jfj1qY7zuX5Eg0JifAUOq6RUwLz
Ruiru4QKcvtW0Uh1KMp1GVt4MmKDiQksTok/pKbJsBFCZugFsS3AjQIDAQAB
-----END PUBLIC KEY-----
```
- ciphertext
```
249d72cd1d287b1a15a3881f2bff5788bc4bf62c789f2df44d88aae805b54c9a94b8944c0ba798f70062b66160fee312b98879f1dd5d17b33095feb3c5830d28
```
### Solution:
## Ron was Wrong, Whit is Right
### Description:
- source code:
```python=
from Crypto.Cipher import PKCS1_OAEP
from Crypto.PublicKey import RSA
msg = "???"
with open('21.pem') as f:
key = RSA.importKey(f.read())
cipher = PKCS1_OAEP.new(key)
ciphertext = cipher.encrypt(msg)
with open('21.ciphertext', 'w') as f:
f.write(ciphertext.hex())
```
Từ source code, ta có thể thấy trình tự mã hoá như sau: `tạo ra public key -> mã hoá message -> ghi vào ciphertext`
Nên ta có thể giải mã theo các bước sau: `đọc ciphertext -> tạo key -> giải mã`
- `ciphertext `ở đây là `msg` đã được encrypt
### Solution:
```python=
from Crypto.Cipher import PKCS1_OAEP
from Crypto.PublicKey.RSA import import_key, construct
from Crypto.Util.number import long_to_bytes, inverse
key = open('21.pem','rb').read()
keypub = import_key(key)
n, e = keypub.n, keypub.e
ciphertext = int(open('21.ciphertext', 'r').read(), 16)
# từ đây ta có giá trị của n,e -> suy ra p,q
p = 919031168254299342928662994540730760042229248845820491699169870943314884504551963184014786520812939038906152950817942941469675496074887272906954399256046690838233813273902630076899906873722574023918253104149453601408405078374008695616160025877687382663027910687942091698042309812910101246025081363544171351624307177908410700904833438480012985928358897861427063761678614898919524867442676631453135379994570031284289815099294504127712924001149921480778993635917803466637717023744788311275545126346774536416864472035644211758788016642401235014385037912224180351022196262011724157012443048941426178651665266181311662824205620324073087330858064769424755443807165558567191049013947419763315902476674266627953223373671797370373786249718677582213173537848582863398367624397247597103174897140005790273296171101569756006898658668311846034013183862374297777882433967015111727139360441681664840944403450472574336901043555319067050153928231938431298082827397506406624964952344826628463723499263165279281720105570577138817805451223334196017505528543229067732013216932022575286870744622250293712218581458417969597311485156075637589299870500738770767213366940656708757081771498126771190548298648709527029056697749965377697006723247968508680596118923
q = 991430390905926023965735525726256769345153760248048478891327804533279477721590201738061124861790305326884541900044434890157058142414306020739922709698601329762087825767461256626800629782378634339618941488765491437487541851308806651586976069659042714378353883168031522106709494592827914376213512564492771821921367377484213072867988877925314809325159382342584541006645302760204539354879391605736604946702073863673524002591877977949645618863730441482821840664748508050205004505250025193611888170440612737112479006348533153568103452396596042639466753099280111709882461562564978070397786887446291916733276692400981917025361391646188802038772976331121474570242334921390569285834250256522656433623912544555266998750630136756355560927237594975904642791712318215315246754105993145827690531584325461597482035600919501967088106457091199733024323755210212616553447076697617349235377466327471959683763796707566328536834402308887105044128592177681553611608618850780128709949316259039664054913946726480968288231015999572777436469163437066403964134928735809253108394078092917006632332098357725950865697047565284013456253933234017983509582245874130968218422573483012858388392588302838940565560162598810462310034964473576147200222580784694005333482381
phi = (p-1)*(q-1)
d = inverse(e,phi)
prv_key = construct((n,e,d))
cipher = PKCS1_OAEP.new(prv_key)
flag = cipher.decrypt(long_to_bytes(ciphertext))
print(flag)
```
- Tham số của `decrypt()` phải ở dạng `bytes/bytearray/memoryview` nên phải chuyển từ int về bytes. (có trong link về pkcs1_oaep)
- Do tham số của `decrypt()` là ở dạng bytes mà thằng `ciphertext` đang ở dạng hex (thập lục phân) nên ép về int rồi chuyển về bytes bằng `long_to_bytes` (số 16 được sử dụng mà không phải số khác vì ciphertext đang ở dạng hex, nếu nó ở dạng khác như nhị phân thì sẽ là 2)
### Flag:
```python=
crypto{3ucl1d_w0uld_b3_pr0ud}
```
### Note:
- Ngoài ra, để encrypt hay decrypt thì đều cần construct public key hoặc private ket từ n,e,d
https://stackoverflow.com/questions/33337904/rsa-generate-private-key-from-data-with-python
- pkcs1_oaep: https://pycryptodome.readthedocs.io/en/latest/src/cipher/oaep.html
- rsa.construct: https://pycryptodome.readthedocs.io/en/latest/src/public_key/rsa.html
## 16. RSA Backdoor Viability
### Description:
```python=
import random
from Crypto.Util.number import bytes_to_long, getPrime, isPrime
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}")
```
```python=
n = 709872443186761582125747585668724501268558458558798673014673483766300964836479167241315660053878650421761726639872089885502004902487471946410918420927682586362111137364814638033425428214041019139158018673749256694555341525164012369589067354955298579131735466795918522816127398340465761406719060284098094643289390016311668316687808837563589124091867773655044913003668590954899705366787080923717270827184222673706856184434629431186284270269532605221507485774898673802583974291853116198037970076073697225047098901414637433392658500670740996008799860530032515716031449787089371403485205810795880416920642186451022374989891611943906891139047764042051071647203057520104267427832746020858026150611650447823314079076243582616371718150121483335889885277291312834083234087660399534665835291621232056473843224515909023120834377664505788329527517932160909013410933312572810208043849529655209420055180680775718614088521014772491776654380478948591063486615023605584483338460667397264724871221133652955371027085804223956104532604113969119716485142424996255737376464834315527822566017923598626634438066724763559943441023574575168924010274261376863202598353430010875182947485101076308406061724505065886990350185188453776162319552566614214624361251463
e = 65537
c = 608484617316138126443275660524263025508135383745665175433229598517433030003704261658172582370543758277685547533834085899541036156595489206369279739210904154716464595657421948607569920498815631503197235702333017824993576326860166652845334617579798536442066184953550975487031721085105757667800838172225947001224495126390587950346822978519677673568121595427827980195332464747031577431925937314209391433407684845797171187006586455012364702160988147108989822392986966689057906884691499234298351003666019957528738094330389775054485731448274595330322976886875528525229337512909952391041280006426003300720547721072725168500104651961970292771382390647751450445892361311332074663895375544959193148114635476827855327421812307562742481487812965210406231507524830889375419045542057858679609265389869332331811218601440373121797461318931976890674336807528107115423915152709265237590358348348716543683900084640921475797266390455366908727400038393697480363793285799860812451995497444221674390372255599514578194487523882038234487872223540513004734039135243849551315065297737535112525440094171393039622992561519170849962891645196111307537341194621689797282496281302297026025131743423205544193536699103338587843100187637572006174858230467771942700918388
```
### Solution:
- Bài cho n nên mình sẽ thử xem có thể tìm p,q thông qua https://factordb.com/ và mình đã tìm ra được nên có thể giải bài toán 1 cách dễ dàng =))).
```python=
from Crypto.Util.number import inverse, long_to_bytes
n = 709872443186761582125747585668724501268558458558798673014673483766300964836479167241315660053878650421761726639872089885502004902487471946410918420927682586362111137364814638033425428214041019139158018673749256694555341525164012369589067354955298579131735466795918522816127398340465761406719060284098094643289390016311668316687808837563589124091867773655044913003668590954899705366787080923717270827184222673706856184434629431186284270269532605221507485774898673802583974291853116198037970076073697225047098901414637433392658500670740996008799860530032515716031449787089371403485205810795880416920642186451022374989891611943906891139047764042051071647203057520104267427832746020858026150611650447823314079076243582616371718150121483335889885277291312834083234087660399534665835291621232056473843224515909023120834377664505788329527517932160909013410933312572810208043849529655209420055180680775718614088521014772491776654380478948591063486615023605584483338460667397264724871221133652955371027085804223956104532604113969119716485142424996255737376464834315527822566017923598626634438066724763559943441023574575168924010274261376863202598353430010875182947485101076308406061724505065886990350185188453776162319552566614214624361251463
e = 65537
c = 608484617316138126443275660524263025508135383745665175433229598517433030003704261658172582370543758277685547533834085899541036156595489206369279739210904154716464595657421948607569920498815631503197235702333017824993576326860166652845334617579798536442066184953550975487031721085105757667800838172225947001224495126390587950346822978519677673568121595427827980195332464747031577431925937314209391433407684845797171187006586455012364702160988147108989822392986966689057906884691499234298351003666019957528738094330389775054485731448274595330322976886875528525229337512909952391041280006426003300720547721072725168500104651961970292771382390647751450445892361311332074663895375544959193148114635476827855327421812307562742481487812965210406231507524830889375419045542057858679609265389869332331811218601440373121797461318931976890674336807528107115423915152709265237590358348348716543683900084640921475797266390455366908727400038393697480363793285799860812451995497444221674390372255599514578194487523882038234487872223540513004734039135243849551315065297737535112525440094171393039622992561519170849962891645196111307537341194621689797282496281302297026025131743423205544193536699103338587843100187637572006174858230467771942700918388
p = 20365029276121374486239093637518056591173153560816088704974934225137631026021006278728172263067093375127799517021642683026453941892085549596415559632837140072587743305574479218628388191587060262263170430315761890303990233871576860551166162110565575088243122411840875491614571931769789173216896527668318434571140231043841883246745997474500176671926153616168779152400306313362477888262997093036136582318881633235376026276416829652885223234411339116362732590314731391770942433625992710475394021675572575027445852371400736509772725581130537614203735350104770971283827769016324589620678432160581245381480093375303381611323
q = 34857423162121791604235470898471761566115159084585269586007822559458774716277164882510358869476293939176287610274899509786736824461740603618598549945273029479825290459062370424657446151623905653632181678065975472968242822859926902463043730644958467921837687772906975274812905594211460094944271575698004920372905721798856429806040099698831471709774099003441111568843449452407542799327467944685630258748028875103444760152587493543799185646692684032460858150960790495575921455423185709811342689185127936111993248778962219413451258545863084403721135633428491046474540472029592613134125767864006495572504245538373207974181
phi = (p-1)*(q-1)
d = inverse(e,phi)
flag = pow(c,d,n)
print(long_to_bytes(flag))
```
### Flag:
```
crypto{I_want_to_Break_Square-free_4p-1}
```
---
# Padding
## Bespoke Padding
### Description:
- source code:
```
from utils import listener
from Crypto.Util.number import bytes_to_long, getPrime
import random
FLAG = b'crypto{???????????????????????????}'
class Challenge():
def __init__(self):
self.before_input = "Come back as much as you want! You'll never get my flag.\n"
self.p = getPrime(1024)
self.q = getPrime(1024)
self.N = self.p * self.q
self.e = 11
def pad(self, flag):
m = bytes_to_long(flag)
a = random.randint(2, self.N)
b = random.randint(2, self.N)
return (a, b), a*m+b
def encrypt(self, flag):
pad_var, pad_msg = self.pad(flag)
encrypted = (pow(pad_msg, self.e, self.N), self.N)
return pad_var, encrypted
def challenge(self, your_input):
if not 'option' in your_input:
return {"error": "You must send an option to this server"}
elif your_input['option'] == 'get_flag':
pad_var, encrypted = self.encrypt(FLAG)
return {"encrypted_flag": encrypted[0], "modulus": encrypted[1], "padding": pad_var}
else:
return {"error": "Invalid option"}
import builtins; builtins.Challenge = Challenge # hack to enable challenge to be run locally, see https://cryptohack.org/faq/#listener
"""
When you connect, the 'challenge' function will be called on your JSON
input.
"""
listener.start_server(port=13386)
```
- Connect at **socket.cryptohack.org 13386**
### Solution:
-
## Null Or Never
### Description:
**Challenge code**
```python=
#!/usr/bin/env python3
from Crypto.PublicKey import RSA
from Crypto.Util.number import bytes_to_long
FLAG = b"crypto{???????????????????????????????????}"
def pad100(msg):
return msg + b'\x00' * (100 - len(msg))
key = RSA.generate(1024, e=3)
n, e = key.n, key.e
m = bytes_to_long(pad100(FLAG))
c = pow(m, e, n)
print(f"n = {n}")
print(f"e = {e}")
print(f"c = {c}")
```
**Output**
```python=
n = 95341235345618011251857577682324351171197688101180707030749869409235726634345899397258784261937590128088284421816891826202978052640992678267974129629670862991769812330793126662251062120518795878693122854189330426777286315442926939843468730196970939951374889986320771714519309125434348512571864406646232154103
e = 3
c = 63476139027102349822147098087901756023488558030079225358836870725611623045683759473454129221778690683914555720975250395929721681009556415292257804239149809875424000027362678341633901036035522299395660255954384685936351041718040558055860508481512479599089561391846007771856837130233678763953257086620228436828
```
### Solution
Hàm `pad100` sẽ pad thêm vào sau `msg` k lần các byté `b'\x00'` sao cho `msg` của ta có độ dài là $100$. Việc padding như này sẽ làm tăng giá trị của `msg` thêm $256^k$ lần.
Có thể thấy flag ban đầu có độ dài là $43$, do đó ta có thể biết được là số bytes được padding thêm có độ dài là $57$. Do đó ta có $m = flag.256^{57}$.
Khi đó ta có:
$$
c = m^e \mod n = (flag.256^{57})^e \mod n
$$
$$
const = flag^e = c * (256^57)^-e \mod n
$$
Tuy nhiên do $const$ có bit length lớn hơn so với $n$ nên nếu ta chỉ căn bậc $e$ không thì sẽ không ra được flag mà ta sẽ phải bù thêm $k.n$
```python=
from Crypto.Util.number import long_to_bytes, inverse
from sympy import integer_nthroot
from tqdm import tqdm
n = 95341235345618011251857577682324351171197688101180707030749869409235726634345899397258784261937590128088284421816891826202978052640992678267974129629670862991769812330793126662251062120518795878693122854189330426777286315442926939843468730196970939951374889986320771714519309125434348512571864406646232154103
e = 3
c = 63476139027102349822147098087901756023488558030079225358836870725611623045683759473454129221778690683914555720975250395929721681009556415292257804239149809875424000027362678341633901036035522299395660255954384685936351041718040558055860508481512479599089561391846007771856837130233678763953257086620228436828
L = 43
B = 256**(100 - L)
inv_Be = inverse(pow(B, e, n), n)
c1 = (c * inv_Be) % n
for k in tqdm(range(100)):
y = c1 + k * n
root, is_exact = integer_nthroot(y, 3) # nếu root nguyên thì is_exact = True -> có thể root là flag
if is_exact:
flag = long_to_bytes(root)
if b'crypto{' in flag:
print(k)
print(flag.decode())
break
else:
print("Not found")
```
### Flag
```python=
crypto{n0n_574nd4rd_p4d_c0n51d3r3d_h4rmful}
```
# Signatures Part 1
## Signing Server
### Description:
My boss has so many emails he's set up a server to just sign everything automatically. He also stores encrypted messages to himself for easy access. I wonder what he's been saying.
Connect at socket.cryptohack.org 13374
- Source code:
```python=
from Crypto.Util.number import bytes_to_long, long_to_bytes
from utils import listener
class Challenge():
def __init__(self):
self.before_input = "Welcome to my signing server. You can get_pubkey, get_secret, or sign.\n"
def challenge(self, your_input):
if not 'option' in your_input:
return {"error": "You must send an option to this server"}
elif your_input['option'] == 'get_pubkey':
return {"N": hex(N), "e": hex(E) }
elif your_input['option'] == 'get_secret':
secret = bytes_to_long(SECRET_MESSAGE)
return {"secret": hex(pow(secret, E, N)) }
elif your_input['option'] == 'sign':
msg = int(your_input['msg'], 16)
return {"signature": hex(pow(msg, D, N)) }
else:
return {"error": "Invalid option"}
```
### Solution:
```python=
from pwn import *
from json import *
def send(hsh):
return r.sendline(dumps(hsh))
r = remote('socket.cryptohack.org', 13374)
r.recv()
option = {"option":"get_secret"}
send(option)
secret_msg = loads(r.recv())["secret"]
option = {"option":"sign", "msg":secret_msg}
send(option)
get = loads(r.recv())["signature"]
message = bytes.fromhex(get[2:])
print(message)
```
Cùng phân tích đoạn code 1 chút:
- `def send(hsh)`: tạo ra 1 function cho phép nhận 1 dict và chuyển nó về JSON string thông qua `dumps` và gửi đến máy chủ thông qua `sendline`.
- 2 dòng tiếp theo là kết nối đến server và `r.recv()` sẽ nhận thông tin từ server.
- `loads()` sẽ chuyển dữ liệu từ JSON string về Python dict nên cần thêm mục như `["secret"] `hay `["signature"]` để truy cập vào đúng dict để lấy dữ liệu.
- `get[2:]` sẽ loại bỏ tiền tố 0x của `get` để có thể chuyển từ dạng hex về bytes.
### Flag:
```python=
crypto{d0n7_516n_ju57_4ny7h1n6}
```
## Let's Decrypt
### Description:
If you can prove you own CryptoHack.org, then you get access to one of our secrets.
Connect at socket.cryptohack.org 13391
- source code:
```python=
import re
from Crypto.Hash import SHA256
from Crypto.Util.number import bytes_to_long, long_to_bytes
from utils import listener
from pkcs1 import emsa_pkcs1_v15
# from params import N, E, D
FLAG = "crypto{?????????????????????????????????}"
MSG = 'We are hyperreality and Jack and we own CryptoHack.org'
DIGEST = emsa_pkcs1_v15.encode(MSG.encode(), 256)
SIGNATURE = pow(bytes_to_long(DIGEST), D, N)
class Challenge():
def __init__(self):
self.before_input = "This server validates domain ownership with RSA signatures. Present your message and public key, and if the signature matches ours, you must own the domain.\n"
def challenge(self, your_input):
if not 'option' in your_input:
return {"error": "You must send an option to this server"}
elif your_input['option'] == 'get_signature':
return {
"N": hex(N),
"e": hex(E),
"signature": hex(SIGNATURE)
}
elif your_input['option'] == 'verify':
msg = your_input['msg']
n = int(your_input['N'], 16)
e = int(your_input['e'], 16)
digest = emsa_pkcs1_v15.encode(msg.encode(), 256)
calculated_digest = pow(SIGNATURE, e, n)
if bytes_to_long(digest) == calculated_digest:
r = re.match(r'^I am Mallory.*own CryptoHack.org$', msg)
if r:
return {"msg": f"Congratulations, here's a secret: {FLAG}"}
else:
return {"msg": f"Ownership verified."}
else:
return {"error": "Invalid signature"}
else:
return {"error": "Invalid option"}
import builtins; builtins.Challenge = Challenge # hack to enable challenge to be run locally, see https://cryptohack.org/faq/#listener
listener.start_server(port=13391)
```
### Solution:
Để tìm được flag thì ta cần tìm n,e và msg phù hợp.
```python=
elif your_input['option'] == 'verify':
msg = your_input['msg']
n = int(your_input['N'], 16)
e = int(your_input['e'], 16)
digest = emsa_pkcs1_v15.encode(msg.encode(), 256)
calculated_digest = pow(SIGNATURE, e, n)
if bytes_to_long(digest) == calculated_digest:
r = re.match(r'^I am Mallory.*own CryptoHack.org$', msg)
if r:
return {"msg": f"Congratulations, here's a secret: {FLAG}"}
else:
return {"msg": f"Ownership verified."}
else:
return {"error": "Invalid signature"}
```
Từ đoạn code trên thì ta có thể hiểu rằng cần tìm `msg` đúng để nhận được flag.
--> Do đó msg cần tìm ở đây chính là `"I am Mallory.*own CryptoHack.org"`.
Có được msg rồi thì ta làm như sau:
```
msg = "I am Mallory.*own CryptoHack.org"
digest = emsa_pkcs1_v15.encode(msg.encode(), 256)
a = bytes_to_long(digest)
```
Nếu msg đúng với msg để lấy flag thì `bytes_to_long(digest) == calculated_digest` nên ta có thể suy ra là `a ≡ sig^e mod n`. Để dễ hơn thì chọn e = 1, ta sẽ có `a ≡ sig mod n` -> `sig - a = n*k` do `sig > a`, lấy `k=1` -> giá trị`n` cần tìm.
```python=
from pwn import *
from json import *
from pkcs1 import emsa_pkcs1_v15
from Crypto.Util.number import bytes_to_long
def send(hsh):
return r.sendline(dumps(hsh))
r = remote('socket.cryptohack.org', 13391)
r.recv()
option = {"option":"get_signature"}
send(option)
var = loads(r.recv())
sig = var["signature"]
sig = int(sig,16)
msg = 'I am Mallory, own CryptoHack.org'
digest = emsa_pkcs1_v15.encode(msg.encode(), 256)
a = bytes_to_long(digest)
e = 1
n = sig - a
assert sig%n == a%n
option = {"option":"verify", "msg":msg, "N":hex(n), "e":hex(e)}
send(option)
get = loads(r.recv())
flag = get['msg']
print(flag)
```
### Flag:
```python=
crypto{dupl1c4t3_s1gn4tur3_k3y_s3l3ct10n}
```
---
# Signature part 2
## Vote for Pedro
### Description:
>If you want my flag, you better vote for Pedro! Can you sign your vote to the server as Alice?
Connect at socket.cryptohack.org 13375
```python=
from Crypto.Util.number import bytes_to_long, long_to_bytes
from utils import listener
FLAG = "crypto{????????????????????}"
class Challenge():
def __init__(self):
self.before_input = "Place your vote. Pedro offers a reward to anyone who votes for him!\n"
def challenge(self, your_input):
if 'option' not in your_input:
return {"error": "You must send an option to this server"}
elif your_input['option'] == 'vote':
vote = int(your_input['vote'], 16)
verified_vote = long_to_bytes(pow(vote, ALICE_E, ALICE_N))
# remove padding
vote = verified_vote.split(b'\00')[-1]
if vote == b'VOTE FOR PEDRO':
return {"flag": FLAG}
else:
return {"error": "You should have voted for Pedro"}
else:
return {"error": "Invalid option"}
import builtins; builtins.Challenge = Challenge # hack to enable challenge to be run locally, see https://cryptohack.org/faq/#listener
listener.start_server(port=13375)
```
- file alice.key:
```python=
N = 22266616657574989868109324252160663470925207690694094953312891282341426880506924648525181014287214350136557941201445475540830225059514652125310445352175047408966028497316806142156338927162621004774769949534239479839334209147097793526879762417526445739552772039876568156469224491682030314994880247983332964121759307658270083947005466578077153185206199759569902810832114058818478518470715726064960617482910172035743003538122402440142861494899725720505181663738931151677884218457824676140190841393217857683627886497104915390385283364971133316672332846071665082777884028170668140862010444247560019193505999704028222347577
e = 3
```
### Solution:
- Từ source code, có thể thấy ta sẽ nhận được flag khi `vote == b'VOTE FOR PEDRO`.
```
vote = ?
msg = b'VOTE FOR PEDRO' = long_to_bytes(pow(vote,ALICE_E,ALICE_N)).split(b'\00')[-1]
-->> bytes_to_long(prefix + b'\00' + msg) = vote^e mod N
-->> left ≡ vote^3 mod N
```
- Từ đây suy ra được phương trình sau:
vote^3^ = prefix.256^len(msg)^ + msg
- Lấy modulo 256^15^ 2 vế của phương trình:
-> vote^3^ ≡ msg mod 256^15^
- Từ đây ta tính được giá trị của vote thông qua sagemath:
```
from Crypto.Util.number import bytes_to_long
msg = b'VOTE FOR PEDRO'
msg = bytes_to_long(msg)
vote = int(mod(msg, 256^15).nth_root(3))
print(vote)
```
- `mod(msg,n).nth_root(3)`: cho phép tính căn bậc 3 theo modulo 256^15^
```
vote = 855520592299350692515886317752220783
```
- Còn lại là giải bài như thường:
```python=
from pwn import *
from json import *
from Crypto.Util.number import bytes_to_long
ALICE_N = 22266616657574989868109324252160663470925207690694094953312891282341426880506924648525181014287214350136557941201445475540830225059514652125310445352175047408966028497316806142156338927162621004774769949534239479839334209147097793526879762417526445739552772039876568156469224491682030314994880247983332964121759307658270083947005466578077153185206199759569902810832114058818478518470715726064960617482910172035743003538122402440142861494899725720505181663738931151677884218457824676140190841393217857683627886497104915390385283364971133316672332846071665082777884028170668140862010444247560019193505999704028222347577
ALICE_E = 3
r = remote('socket.cryptohack.org',13375)
r.recv()
def send(hsh):
return r.sendline(dumps(hsh))
vote = 855520592299350692515886317752220783
option = {'option':'vote', 'vote':hex(vote)}
send(option)
get = loads(r.recv())
flag = get['flag']
print(flag)
```
### Flag:
```python=
crypto{y0ur_v0t3_i5_my_v0t3}
```
Sign in with Wallet
Connect another wallet