# Task 1: RSA
* Để nắm được sơ lược RSA thì mình có tìm hiểu ở đây: https://vi.wikipedia.org/wiki/RSA_(m%C3%A3_h%C3%B3a)
https://www.youtube.com/watch?v=9KohZt8EFNc&t=225s
## RSA là gì ?
### Khái niệm
* RSA là một thuật toán mã hoá khóa công khai (public-key cryptography) được phát triển bởi Ron Rivest, Adi Shamir và Leonard Adleman vào năm 1977. Tên của thuật toán đến từ viết tắt của ba nhà nghiên cứu đầu tiên của nó. ( Điều này sơ sơ vậy thôi chứ ít ai quan tâm lắm xD ) :smile:
* Thuật toán RSA là thuật toán mã hóa công khai. Hoạt động dựa trên việc chọn ra 2 số nguyên tố lớn để tạo 2 cặp khóa là public key và private key.
* Public key : khóa công khai dùng để mã hóa.
* Private key : khóa bí mật dùng để giải mã.
* 

### Hoạt động
* **Tạo khóa**
1.Chọn ra 2 số nguyên tố khác nhau **p** và **q**
2.Tính **n= p * q.**
3.Tính hàm Euler : **$\varphi(n)$ = (p-1) * (q-1)**
4.Chọn 1 số nguyên tố **e** sao cho **1<e<$\varphi(n)$** và **e** nguyên tố cùng nhau với **$\varphi(n)$.**
5.Tính **d** sao cho **(d*e)%$\varphi(n)$=1**
#### Lúc này thì khóa công khai bao gồm (e,n), khóa bí mật gồm (d,n).

* **Mã hóa(encrypt)**
encrypt_msg=**$msg^e$** mod n.
* **Giải mã(decrypt)**
msg = encrypt_ms$g^d$ mod n.
* **Tính đúng đắn của thuật toán:**
* * Trước hết mình tham khảo định lí Euler :https://vi.wikipedia.org/wiki/%C4%90%E1%BB%8Bnh_l%C3%BD_Euler
* * Ta có: **msg = encrypt_ms$g^d$ mod n
= $(msg^e mod n)^d$ mod n
= msg^ed^ mod n
= msg^(1+k*phi_N)^ mod n
= (msg * msg^k*phi_N^)mod n
= msg mod n (Vì theo định lí Euler ở trên ta có msg^phi_N^ mod n = 1)**
### Ứng dụng
* Đương nhiên là để mã hóa và giải mã sao cho chỉ 2 bên biết mà người khác không biết rồi xD :smile_cat: Trên thực tế thì RSA dùng để chứng thực dữ liệu, truyền tải dữ liệu an toàn,chữ ký số/ chữ ký điện tử. https://itnavi.com.vn/blog/rsa-la-gi
* Để mình lấy 1 ví dụ nhỏ cho mọi người hình dung. Như sau:
* * Giả sử mình có người yêu rồi nhưng mình vẫn mập mờ với 1 cô gái khác 
( Ví dụ thôi chứ mình không thế xD)
* * Lo sợ rằng nhắn tin qua messenger không an toàn nên mình lựa chọn RSA :)
* * Cô gái kia sẽ tính toán các giá trị **p,q,n,e,d** rồi gửi cho mình khóa công khai **(e,n)**
* * Thay vì gửi tin nhắn **msg = "Anh se dua em di tron"**
thì mình gửi **enc_msg = (Anh se dua em di tron)^e^ mod n**
* * Đương nhiên nếu lỡ người yêu mình có đọc được tin nhắn này thì cũng chả biết **enc_msg** là cái gì.Còn nếu mà biết là mình dùng RSA thì có **d** đâu mà đòi giải mã xD :smirk:
* 
* Còn cô gái kia dùng **(d,n)** là có được thông điệp của mình. :crossed_fingers:
* 

### Code

import random
import math

def create_key(p,q):
  # Tính n
  n = p * q
  # Tính phi_N(Hàm Euler)
  phi_N = (p-1)*(q-1)
  # Chọn 1 số e bất kì là số nguyên tố nằm trong khoảng từ 1 tới phi_N
  e = random.randrange(1,phi_N)
  # kiểm tra e phải nguyên tố cùng nhau với phi_N(Nếu sai thì phải chọn lại e)
  while(math.gcd(e,phi_N)!=1):
     e = random.randrange(1,phi_N)
  # Tìm giá trị d sao cho (d*e)%phi_N=1
  d=pow(e,-1,phi_N)
  
  # trả về cặp khóa lần lượt là public và private
  return ((e,n),(d,n))


def encrypt(pk, plaintext):
  
  e, n = pk

  # Chuyển mỗi kí tự bản rõ sang kí tự dựa trên a^b mod m
  cipher = [pow(ord(char), e, n) for char in plaintext]

  # Trả về mảng bytes
  return cipher

def decrypt(pk, ciphertext):
  
  d, n = pk

  # Tạo bản rõ dựa trên bản mã và khóa sử dụng a^b mod m
  plain = [chr(pow(char, d, n)) for char in ciphertext]

  # Trả về mảng bytes dưới dạng chuỗi 
  return ''.join(plain)

p = 61
q = 53
public, private = create_key(p, q)
print("Public key is ", public)
print("Private key is ", private)

message = 'Crypto so difficult'
encrypted_message = encrypt(public, message)
print("Encrypted message is ", encrypted_message)

decrypted_message = decrypt(private, encrypted_message)
print("Decrypted message is ", decrypted_message)

* Kết quả:

Public key is  (3073, 3233)
Private key is  (2257, 3233)
Encrypted message is  [669, 756, 3171, 91, 307, 1270, 2411, 1226, 1270, 2411, 1022, 2649, 3163, 3163, 2649, 577, 2157, 1145, 307]
Decrypted message is  Crypto so difficult

## Tấn công hệ mật RSA
* Phần nội dung này sẽ đề cập tới các điểm yếu của RSA phục vụ cho CTF.
### Attack 1: small N
* Với $N=p*q$ nhỏ (<256 bit) thì ta hoàn toàn có thể brute-force hoặc factorize **N**.
* Chiều dài khuyến cáo của **N** là 1024 bit. Tuy nhiên nếu N vẫn có sẵn trong bộ dữ liệu của http://factordb.com/ hay https://www.alpertron.com.ar/ECM.HTM thì vẫn toi :smile: . Vậy nên hãy thử phân tích **N** từ các web này trước sau đó mới sử dụng .
### Attack 2: small e,small m
* Thông thường thì các bài CTF thường chọn N lớn để đảm bảo không bị **Attack 1** tấn công. Tuy nhiên nếu như **e,m** quá nhỏ thì sẽ dẫn tới 1 điểm yếu để khai thác.
* Ta biết : **c = m^e^modn**. Nhưng do **e,m** quá nhỏ dẫn tới **m^e^<n** dẫn tới quá trình **mod** không tác dụng gì. Giải mã ngược lại thì chỉ cần **m = c^1/e^**

### Attack 3: Fermat Attack
* Điểm yếu lần này là khi 2 số nguyên tố **p,q** quá gần nhau .
Dẫn tới **N** sẽ gần bằng **p^2^** và **q^2^**.
* Điều kiện cần : **| p - q | < n^1/4^**
* **N = p*q
= $(p+q)^2/4$ - $(p-q)^2/4$
= a^2^-b^2^**
* Để tìm được **p,q** thì ta chỉ cần cho **a = N^1/2^**, sau đó kiểm tra xem **a^2^-N** có là số chính phương không.
Nếu có thì từ **a,b** tìm ra **p,q**.
Còn không thì tăng **a** lên 1 đơn vị cho tới khi tìm được.

### Attack 4:Hastad Broadcast Attack (same e, small e)
* Trong 1 hệ thống mạng , mỗi máy tính có cặp khóa **($e_i,n_i$)** riêng biệt.Giả sử như người quản trị dùng **e=3** để tất cả máy tính sử dụng. Tức là $e_1=e_2=...=3$.
* Điểm yếu của việc này máy chủ gửi cùng 1 tin nhắn broadcast m (đã được mã hóa thành $c_1, c_2$, ...) cho nhiều máy tính trong mạng, và ta bắt được ít nhất e ciphertext ($c_1, c_2, ..., c_e$).
* Gom lại thành hệ phương trình đồng dư :
* * $m^3$ = $c_1$mod$n_1$
* $m^3$ = $c_2$mod$n_2$
* .......
* $m^3$ = $c_e$mod$n_e$
* Để giải hệ phương trình đồng dư này thì dùng :https://vi.wikipedia.org/wiki/%C4%90%E1%BB%8Bnh_l%C3%BD_s%E1%BB%91_d%C6%B0_Trung_Qu%E1%BB%91c
* Tìm được **m^3^** thì sẽ tìm được **m**
* 

### Attack 5:Common modulus (same n)
* Khác với **attack 4** là sử dụng chung **e** thì điểm yếu của **attack 5** là sử dụng chung **N**. Tức là mỗi máy tính trong hệ thống sẽ có cho mình các thông số là ($e_i,d_i,N$)
* :one: Nếu bạn là 1 thành viên trong đó thì bạn sẽ sở hữu cho mình 1 cặp ($e,d,N$)

$ed = 1 mod (\varphi(n))$
$<=>$ ed = 1 + k * $\varphi(n)$
$<=>$ $k = \frac{e*d-1}{\varphi(n)} > \frac{e*d-1}{n}$ với k là số tự nhiên.

Vậy ta brute_force k từ giá trị $\frac{e*d-1}{n}$ trở đi
Từ giá trị **k** đó thì ta tính ngược lại $\varphi(n)$
Nếu $\varphi(n)$ chưa nguyên thì **k = k + 1**
Còn nếu $\varphi(n)$ nguyên rồi thì ngon. Vì khi có $\varphi(n)$ ta sẽ tính được giá trị **d** của các máy khác: $d'=e'mod\varphi(n)$.

Ừm chắc xong rồi đấy. Có $d'$ thì ta sẽ biết các thông tin trao đổi ở máy kia thôi xD.
* :two: Còn nếu bạn là 1 attacker, không là thành viên trong hệ thống đó. Thì đương nhiên bạn không có giá trị **d**.Nhưng vô tình trong 1 lần có cùng 1 thông điệp **m** được gửi tới 2 máy A,B. Bạn nghe lén được 2 giá trị $c_A,c_B$ đó. Vậy là đủ rồi.
Đầu tiên ta dùng https://vi.wikipedia.org/wiki/Gi%E1%BA%A3i_thu%E1%BA%ADt_Euclid_m%E1%BB%9F_r%E1%BB%99ng để tìm 2 giá trị **u,v** của phương trình **u∗$e_A$+v∗$e_B$=UCLN($e_A,e_B$)=1**
Sau đó tính nốt : $c_A^u.c_B^v = (m^{e_A})^u.(m^{e_B})^v = m^{e_A.u}.m^{e_B.v} = m^{e_A.u+e_B.v} = m^1 = m$
* Vậy từ **attack 4** và **attack 5** thì rút ra 1 điều là mỗi cá nhân nên chọn cho mình **(e,N)** khác nhau chứ không nên dùng chung với người khác.
* 

### Attack 6: Wiener Attack (small d)
* Ta biết rằng mã hóa : $c = m^emodn$ và giải mã : $m = c^dmodn$.
* Tức là thời gian mã hóa phụ thuộc vào **e** và giải mã phụ thuộc vào **d**.
* Điều này dẫn tới rằng nếu 1 số máy tính yếu thì giải mã khó khăn. Họ lựa chọn
**e** lớn , **d** nhỏ để giảm thiểu thời gian giải mã. Tuy nhiên thì đó lại là điểm yếu
cho **Wiener Attack**.
* Điều kiện cần:
d < n^1/4^/3(1)
q < p < 2q(2)
e' < n^3/2^ với e' = e (mod n)hay Public Key không quá lớn(3)

* $ed≡1 mod(\varphi(n))$
$<=>ed=k\varphi(n)+1$
$<=>|ed-k\varphi(n)|=1$
$<=>\frac{1}{d*\varphi(n)}=|\frac{e}{\varphi(n)} - \frac{k}{d}|<|\frac{e}{n} - \frac{k}{d}|$
* ta có $\varphi(n) = (p-1).(q-1)= n - p -q +1 <=> n-p-q <\varphi(n)$ (4)
* Từ (2) $<=> n<p^2<2n$( Nhân p vào 2 vế)$<=> p<\sqrt{2n}<2\sqrt{n}$.
* Từ (2) $<=> q^2 <n$(Nhân q vào 2 vế) $<=>q<\sqrt{n}$. Vậy $p+q<3\sqrt(n)$. Kết hợp với (4) ta được : $n-\varphi(n) < 3.\sqrt{n}$ (5)
* Ta có : $|\frac{e}{n} - \frac{k}{d}| = |\frac{ed-kn}{nd}| = |\frac{ k\varphi(n)+1 -kn}{nd}| = |\frac{1-k(n-\varphi(n))}{nd}|= |\frac{k(n-\varphi(n))-1}{nd}|<|\frac{3k\sqrt{n}}{nd}|$
* Hiển nhiên:
$e < \varphi(n)$
$<=>ke < k\varphi(n)$ (Mà $k\varphi(n) = ed-1$)
Suy ra : $ke < ed-1<ed => ke<ed =>k<d<\frac{1}{3}*n^{1/4}$(Theo (1))
* Theo (1) $d<1/3*n^{1/4}$ hay $2d<n^{1/4}$
* Vậy $|\frac{e}{n} - \frac{k}{d}|<
|\frac{1}{d*n^{1/4}\sqrt{n}}|<|\frac{1}{d*n^{1/4}}|<|\frac{1}{2d^2}|$
* **Vận dụng**: Với (e,n) công khai thì bạn áp dụng định lý về dãy hội tụ liên phân số [https://vi.wikipedia.org/wiki/Li%C3%AAn_ph%C3%A2n_s%E1%BB%91] hoặc dùng công cụ [https://www.wolframalpha.com/] bằng cách nhập **convergents of e/n** và mục result là thứ bạn cần. Lấy từng phân số gán giá trị cho cặp k/d rồi tính $φ(n) = \frac{ed - 1}{k}$ . Giải phương trình $x^2 - ((n-\varphi(n))+1)x + n = 0$ và cặp (x1,x2) nguyên chính là giá trị p,q cần tìm.
* Ví dụ:(e,n)=(17993,90581)
* Sau khi lên [https://www.wolframalpha.com/] nhập **convergents of 17993/90581** thì thứ mình thu được:
{${0, \frac{1}{5}\,\frac {29}{146}, \frac{117}{589}, \frac{146}{735}, \frac{555}{2794}, \frac{1256}{6323}, \frac{5579}{28086}, \frac{17993}{90581}}$}
* Mình chọn $\frac{1}{5}$ và bắt đầu từ k=1;d=5
* $\varphi(n)=\frac{ed-1}{k}=\frac{17993.5-1}{1}=89964$
* Phương trình:
$x^2 - ((n-\varphi(n))+1)x + n = 0$
$<=>x^2 - 618x + 90581 = 0$
$<=> x_1=239$ và $x_2=379$
Đó chính là giá trị của p và q! ***Perfect***
Vậy p=239,q=379,d=5.

### Attack 7:Blinding Attack
* Giả sử mình muốn có được chữ kí S của A thông qua 1 tin nhắn M. Tuy nhiên vì biết đó là tin nhắn của mình nên A đương nhiên từ chối. Vậy mình sẽ gửi cho A 1 đoạn tin nhắn $M_0$ khác($M_0 = r^e.M(mod N)$). A không nhận ra đó là tin nhắn của mình nên ký vô chữ kí $S_0$. Ta có:
$S_0 = (M_0^d)mod N$
$= (r^e.M)^d mod N$
$= (r^{ed}modN).(M^dmodN)$
$=(r^{k.\varphi(n)+1}modN).(M^dmodN)$
$= (rmodN).(M^dmodN)$
$=>S_0/r=M^dmodN = S$
* Vậy ta đã có đc chữ kí *S* rồi xD 

# CHALLENGE
## STARTER
* Mục **starter** này các challenge chỉ là những thao tác cơ bản nhất của RSA thôi.
### RSA Starter 1
* 
* 
* **Flag:19906**
### RSA Starter 2
* 
* 
* **Flag:301**
### RSA Starter 3
* 
* 
* **Flag:882564595536224140639625987657529300394956519977044270821168**
### RSA Starter 4
* 
* 
* **Flag:121832886702415731577073962957377780195510499965398469843281**
### RSA Starter 5
* 
* 
* **Flag:13371337**
### RSA Starter 6
* 
* Private.key:

N = 15216583654836731327639981224133918855895948374072384050848479908982286890731769486609085918857664046075375253168955058743185664390273058074450390236774324903305663479046566232967297765731625328029814055635316002591227570271271445226094919864475407884459980489638001092788574811554149774028950310695112688723853763743238753349782508121985338746755237819373178699343135091783992299561827389745132880022259873387524273298850340648779897909381979714026837172003953221052431217940632552930880000919436507245150726543040714721553361063311954285289857582079880295199632757829525723874753306371990452491305564061051059885803
d = 11175901210643014262548222473449533091378848269490518850474399681690547281665059317155831692300453197335735728459259392366823302405685389586883670043744683993709123180805154631088513521456979317628012721881537154107239389466063136007337120599915456659758559300673444689263854921332185562706707573660658164991098457874495054854491474065039621922972671588299315846306069845169959451250821044417886630346229021305410340100401530146135418806544340908355106582089082980533651095594192031411679866134256418292249592135441145384466261279428795408721990564658703903787956958168449841491667690491585550160457893350536334242689

* 

Flag:13480738404590090803339831649238454376183189744970683129909766078877706583282422686710545217275797376709672358894231550335007974983458408620258478729775647818876610072903021235573923300070103666940534047644900475773318682585772698155617451477448441198150710420818995347235921111812068656782998168064960965451719491072569057636701190429760047193261886092862024118487826452766513533860734724124228305158914225250488399673645732882077575252662461860972889771112594906884441454355959482925283992539925713424132009768721389828848907099772040836383856524605008942907083490383109757406940540866978237471686296661685839083475**

## PRIMES PART 1
### Factoring
* 
* Bài này mình chỉ cần factor được **N** và gửi flag là số nhỏ hơn.
* 
* **Flag:19704762736204164635843**
### Inferius Prime
* 
* inferius.py:

#!/usr/bin/env python3

from Crypto.Util.number import getPrime, inverse, bytes_to_long, long_to_bytes, GCD

e = 3

# n will be 8 * (100 + 100) = 1600 bits strong which is pretty good
while True:
    p = getPrime(100)
    q = getPrime(100)
    phi = (p - 1) * (q - 1)
    d = inverse(e, phi)
    if d != -1 and GCD(e, phi) == 1:
        break

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

* output.txt:

n = 742449129124467073921545687640895127535705902454369756401331
e = 3
ct = 39207274348578481322317340648475596807303160111338236677373

* 
* **Flag:crypto{N33d_b1g_pR1m35}**
### Monoprime
* 
* Bài này thì **n=p**. Mình tính $\varphi(n)$:

* output.txt:

n = 171731371218065444125482536302245915415603318380280392385291836472299752747934607246477508507827284075763910264995326010251268493630501989810855418416643352631102434317900028697993224868629935657273062472544675693365930943308086634291936846505861203914449338007760990051788980485462592823446469606824421932591                                                                 
e = 65537
ct = 161367550346730604451454756189028938964941280347662098798775466019463375610700074840105776873791605070092554650190486030367121011578171525759600774739890458414593857709994072516290998135846956596662071379067305011746842247628316996977338024343628757374524136260758515864509435302781735938531030576289086798942  

* 
* **Flag:crypto{0n3_pr1m3_41n7_pr1m3_l0l}**
### Square Eyes
* 
* Lần này thì **n=p*p**.
* 
* 
* **Flag: crypto{squar3_r00t_i5_f4st3r_th4n_f4ct0r1ng!}**
### Manyprime
* 
* Lần này thì có khoảng 30 số nguyên tố tạo nên **n**
* 
* **Flag:crypto{700_m4ny_5m4ll_f4c70r5}**
## PUBLIC EXPONENT
### Salty
* 
* salty.py:

#!/usr/bin/env python3

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

* output.txt:

n = 110581795715958566206600392161360212579669637391437097703685154237017351570464767725324182051199901920318211290404777259728923614917211291562555864753005179326101890427669819834642007924406862482343614488768256951616086287044725034412802176312273081322195866046098595306261781788276570920467840172004530873767                                                             
e = 1
ct = 44981230718212183604274785925793145442655465025264554046028251311164494127485

* Nhìn thấy **e=1** thì mình dùng **Attack 2(small e,small m)**
* 
* **Flag:crypto{saltstack_fell_for_this!}**
### Modulus Inutilis
* 
* modulus_inutilis.py:

#!/usr/bin/env python3
from Crypto.Util.number import getPrime, inverse, bytes_to_long, long_to_bytes

e = 3
d = -1

while d == -1:
    p = getPrime(1024)
    q = getPrime(1024)
    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

* output.txt:

n = 17258212916191948536348548470938004244269544560039009244721959293554822498047075403658429865201816363311805874117705688359853941515579440852166618074161313773416434156467811969628473425365608002907061241714688204565170146117869742910273064909154666642642308154422770994836108669814632309362483307560217924183202838588431342622551598499747369771295105890359290073146330677383341121242366368309126850094371525078749496850520075015636716490087482193603562501577348571256210991732071282478547626856068209192987351212490642903450263288650415552403935705444809043563866466823492258216747445926536608548665086042098252335883
e = 3
ct = 243251053617903760309941844835411292373350655973075480264001352919865180151222189820473358411037759381328642957324889519192337152355302808400638052620580409813222660643570085177957

* N không factor được nên mình thử dùng **Attack 2(small e,small m)**. Cụ thể là cho **flag = ct^1/3^**
* 
* **Flag:crypto{N33d_m04R_p4dd1ng}**
### Everything is Big
* 
* source.py:

#!/usr/bin/env python3

from Crypto.Util.number import getPrime, bytes_to_long

FLAG = b"crypto{?????????????????????????}"

m = bytes_to_long(FLAG)

def get_huge_RSA():
    p = getPrime(1024)
    q = getPrime(1024)
    N = p*q
    phi = (p-1)*(q-1)
    while True:
        d = getPrime(256)
        e = pow(d,-1,phi)
        if e.bit_length() == N.bit_length():
            break
    return N,e


N, e = get_huge_RSA()
c = pow(m, e, N)

print(f'N = {hex(N)}')
print(f'e = {hex(e)}')
print(f'c = {hex(c)}')

* output.txt:

N = 0xb8af3d3afb893a602de4afe2a29d7615075d1e570f8bad8ebbe9b5b9076594cf06b6e7b30905b6420e950043380ea746f0a14dae34469aa723e946e484a58bcd92d1039105871ffd63ffe64534b7d7f8d84b4a569723f7a833e6daf5e182d658655f739a4e37bd9f4a44aff6ca0255cda5313c3048f56eed5b21dc8d88bf5a8f8379eac83d8523e484fa6ae8dbcb239e65d3777829a6903d779cd2498b255fcf275e5f49471f35992435ee7cade98c8e82a8beb5ce1749349caa16759afc4e799edb12d299374d748a9e3c82e1cc983cdf9daec0a2739dadcc0982c1e7e492139cbff18c5d44529407edfd8e75743d2f51ce2b58573fea6fbd4fe25154b9964d
e = 0x9ab58dbc8049b574c361573955f08ea69f97ecf37400f9626d8f5ac55ca087165ce5e1f459ef6fa5f158cc8e75cb400a7473e89dd38922ead221b33bc33d6d716fb0e4e127b0fc18a197daf856a7062b49fba7a86e3a138956af04f481b7a7d481994aeebc2672e500f3f6d8c581268c2cfad4845158f79c2ef28f242f4fa8f6e573b8723a752d96169c9d885ada59cdeb6dbe932de86a019a7e8fc8aeb07748cfb272bd36d94fe83351252187c2e0bc58bb7a0a0af154b63397e6c68af4314601e29b07caed301b6831cf34caa579eb42a8c8bf69898d04b495174b5d7de0f20cf2b8fc55ed35c6ad157d3e7009f16d6b61786ee40583850e67af13e9d25be3
c = 0x3f984ff5244f1836ed69361f29905ca1ae6b3dcf249133c398d7762f5e277919174694293989144c9d25e940d2f66058b2289c75d1b8d0729f9a7c4564404a5fd4313675f85f31b47156068878e236c5635156b0fa21e24346c2041ae42423078577a1413f41375a4d49296ab17910ae214b45155c4570f95ca874ccae9fa80433a1ab453cbb28d780c2f1f4dc7071c93aff3924d76c5b4068a0371dff82531313f281a8acadaa2bd5078d3ddcefcb981f37ff9b8b14c7d9bf1accffe7857160982a2c7d9ee01d3e82265eec9c7401ecc7f02581fd0d912684f42d1b71df87a1ca51515aab4e58fab4da96e154ea6cdfb573a71d81b2ea4a080a1066e1bc3474

* Bài này thì cứ chuyển output.txt sang số rồi factor n:
* 
* **Flag:crypto{s0m3th1ng5_c4n_b3_t00_b1g}**
### Crossed Wires
* 
* source.py:

from Crypto.Util.number import getPrime, long_to_bytes, bytes_to_long, inverse
import math
from gmpy2 import next_prime

FLAG = b"crypto{????????????????????????????????????????????????}"

p = getPrime(1024)
q = getPrime(1024)
N = p*q
phi = (p-1)*(q-1)
e = 0x10001
d = inverse(e, phi)

my_key = (N, d)

friends = 5
friend_keys = [(N, getPrime(17)) for _ in range(friends)]

cipher = bytes_to_long(FLAG)

for key in friend_keys:
    cipher = pow(cipher, key[1], key[0])

print(f"My private key: {my_key}")
print(f"My Friend's public keys: {friend_keys}")
print(f"Encrypted flag: {cipher}")

* output.txt:

My private key: (21711308225346315542706844618441565741046498277716979943478360598053144971379956916575370343448988601905854572029635846626259487297950305231661109855854947494209135205589258643517961521594924368498672064293208230802441077390193682958095111922082677813175804775628884377724377647428385841831277059274172982280545237765559969228707506857561215268491024097063920337721783673060530181637161577401589126558556182546896783307370517275046522704047385786111489447064794210010802761708615907245523492585896286374996088089317826162798278528296206977900274431829829206103227171839270887476436899494428371323874689055690729986771, 2734411677251148030723138005716109733838866545375527602018255159319631026653190783670493107936401603981429171880504360560494771017246468702902647370954220312452541342858747590576273775107870450853533717116684326976263006435733382045807971890762018747729574021057430331778033982359184838159747331236538501849965329264774927607570410347019418407451937875684373454982306923178403161216817237890962651214718831954215200637651103907209347900857824722653217179548148145687181377220544864521808230122730967452981435355334932104265488075777638608041325256776275200067541533022527964743478554948792578057708522350812154888097)
My Friend's public keys: [(21711308225346315542706844618441565741046498277716979943478360598053144971379956916575370343448988601905854572029635846626259487297950305231661109855854947494209135205589258643517961521594924368498672064293208230802441077390193682958095111922082677813175804775628884377724377647428385841831277059274172982280545237765559969228707506857561215268491024097063920337721783673060530181637161577401589126558556182546896783307370517275046522704047385786111489447064794210010802761708615907245523492585896286374996088089317826162798278528296206977900274431829829206103227171839270887476436899494428371323874689055690729986771, 106979), (21711308225346315542706844618441565741046498277716979943478360598053144971379956916575370343448988601905854572029635846626259487297950305231661109855854947494209135205589258643517961521594924368498672064293208230802441077390193682958095111922082677813175804775628884377724377647428385841831277059274172982280545237765559969228707506857561215268491024097063920337721783673060530181637161577401589126558556182546896783307370517275046522704047385786111489447064794210010802761708615907245523492585896286374996088089317826162798278528296206977900274431829829206103227171839270887476436899494428371323874689055690729986771, 108533), (21711308225346315542706844618441565741046498277716979943478360598053144971379956916575370343448988601905854572029635846626259487297950305231661109855854947494209135205589258643517961521594924368498672064293208230802441077390193682958095111922082677813175804775628884377724377647428385841831277059274172982280545237765559969228707506857561215268491024097063920337721783673060530181637161577401589126558556182546896783307370517275046522704047385786111489447064794210010802761708615907245523492585896286374996088089317826162798278528296206977900274431829829206103227171839270887476436899494428371323874689055690729986771, 69557), (21711308225346315542706844618441565741046498277716979943478360598053144971379956916575370343448988601905854572029635846626259487297950305231661109855854947494209135205589258643517961521594924368498672064293208230802441077390193682958095111922082677813175804775628884377724377647428385841831277059274172982280545237765559969228707506857561215268491024097063920337721783673060530181637161577401589126558556182546896783307370517275046522704047385786111489447064794210010802761708615907245523492585896286374996088089317826162798278528296206977900274431829829206103227171839270887476436899494428371323874689055690729986771, 97117), (21711308225346315542706844618441565741046498277716979943478360598053144971379956916575370343448988601905854572029635846626259487297950305231661109855854947494209135205589258643517961521594924368498672064293208230802441077390193682958095111922082677813175804775628884377724377647428385841831277059274172982280545237765559969228707506857561215268491024097063920337721783673060530181637161577401589126558556182546896783307370517275046522704047385786111489447064794210010802761708615907245523492585896286374996088089317826162798278528296206977900274431829829206103227171839270887476436899494428371323874689055690729986771, 103231)]
Encrypted flag: 20304610279578186738172766224224793119885071262464464448863461184092225736054747976985179673905441502689126216282897704508745403799054734121583968853999791604281615154100736259131453424385364324630229671185343778172807262640709301838274824603101692485662726226902121105591137437331463201881264245562214012160875177167442010952439360623396658974413900469093836794752270399520074596329058725874834082188697377597949405779039139194196065364426213208345461407030771089787529200057105746584493554722790592530472869581310117300343461207750821737840042745530876391793484035024644475535353227851321505537398888106855012746117

* Về ý tưởng bài này thì không có gì khó khăn cả. Chúng ta chỉ cần tìm khóa private của friends và giải mã ngược lại là xong.
* 
* **Flag:crypto{3ncrypt_y0ur_s3cr3t_w1th_y0ur_fr1end5_publ1c_k3y}**

### Everything is Still Big
* 
* source.py:

#!/usr/bin/env python3

from Crypto.Util.number import getPrime, bytes_to_long, inverse
from random import getrandbits
from math import gcd

FLAG = b"crypto{?????????????????????????????????????}"

m = bytes_to_long(FLAG)

def get_huge_RSA():
    p = getPrime(1024)
    q = getPrime(1024)
    N = p*q
    phi = (p-1)*(q-1)
    while True:
        d = getrandbits(512)
        if (3*d)**4 > N and gcd(d,phi) == 1:
            e = inverse(d, phi)
            break
    return N,e


N, e = get_huge_RSA()
c = pow(m, e, N)

print(f'N = {hex(N)}')
print(f'e = {hex(e)}')
print(f'c = {hex(c)}')

* output.txt:

N = 0xb12746657c720a434861e9a4828b3c89a6b8d4a1bd921054e48d47124dbcc9cfcdcc39261c5e93817c167db818081613f57729e0039875c72a5ae1f0bc5ef7c933880c2ad528adbc9b1430003a491e460917b34c4590977df47772fab1ee0ab251f94065ab3004893fe1b2958008848b0124f22c4e75f60ed3889fb62e5ef4dcc247a3d6e23072641e62566cd96ee8114b227b8f498f9a578fc6f687d07acdbb523b6029c5bbeecd5efaf4c4d35304e5e6b5b95db0e89299529eb953f52ca3247d4cd03a15939e7d638b168fd00a1cb5b0cc5c2cc98175c1ad0b959c2ab2f17f917c0ccee8c3fe589b4cb441e817f75e575fc96a4fe7bfea897f57692b050d2b
e = 0x9d0637faa46281b533e83cc37e1cf5626bd33f712cc1948622f10ec26f766fb37b9cd6c7a6e4b2c03bce0dd70d5a3a28b6b0c941d8792bc6a870568790ebcd30f40277af59e0fd3141e272c48f8e33592965997c7d93006c27bf3a2b8fb71831dfa939c0ba2c7569dd1b660efc6c8966e674fbe6e051811d92a802c789d895f356ceec9722d5a7b617d21b8aa42dd6a45de721953939a5a81b8dffc9490acd4f60b0c0475883ff7e2ab50b39b2deeedaefefffc52ae2e03f72756d9b4f7b6bd85b1a6764b31312bc375a2298b78b0263d492205d2a5aa7a227abaf41ab4ea8ce0e75728a5177fe90ace36fdc5dba53317bbf90e60a6f2311bb333bf55ba3245f
c = 0xa3bce6e2e677d7855a1a7819eb1879779d1e1eefa21a1a6e205c8b46fdc020a2487fdd07dbae99274204fadda2ba69af73627bdddcb2c403118f507bca03cb0bad7a8cd03f70defc31fa904d71230aab98a10e155bf207da1b1cac1503f48cab3758024cc6e62afe99767e9e4c151b75f60d8f7989c152fdf4ff4b95ceed9a7065f38c68dee4dd0da503650d3246d463f504b36e1d6fafabb35d2390ecf0419b2bb67c4c647fb38511b34eb494d9289c872203fa70f4084d2fa2367a63a8881b74cc38730ad7584328de6a7d92e4ca18098a15119baee91237cea24975bdfc19bdbce7c1559899a88125935584cd37c8dd31f3f2b4517eefae84e7e588344fa5

* Lại chuyển về hết số nguyên rồi factor **n** thôi.
* 
* **Flag:crypto{bon3h5_4tt4ck_i5_sr0ng3r_th4n_w13n3r5}**
### Endless Emails
* 
* johan.py:

#!/usr/bin/env python3

from Crypto.Util.number import bytes_to_long, getPrime
from secret import messages


def RSA_encrypt(message):
    m = bytes_to_long(message)
    p = getPrime(1024)
    q = getPrime(1024)
    N = p * q
    e = 3
    c = pow(m, e, N)
    return N, e, c


for m in messages:
    N, e, c = RSA_encrypt(m)
    print(f"n = {N}")
    print(f"e = {e}")
    print(f"c = {c}")

* output.txt:

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

* Bài này dùng **Attack 4:Hastad Broadcast Attack (same e, small e)**

from itertools import combinations
from Crypto.Util.number import *
from gmpy2 import iroot
 
def crt(remainders, mod):
    assert len(remainders)== len(mod)
    N  = 1
    for i in mod:
        N*=i
    Ni = []
    for i in range(len(mod)):
        Ni.append(N//mod[i])
    Y=[]
    for i in range(len(mod)):
        Y.append(pow(Ni[i],-1,mod[i]))
    res = 0
    for i in range(len(mod)):
        res+=remainders[i]*Ni[i]*Y[i]
    return res%N
 
n0 = 14528915758150659907677315938876872514853653132820394367681510019000469589767908107293777996420037715293478868775354645306536953789897501630398061779084810058931494642860729799059325051840331449914529594113593835549493208246333437945551639983056810855435396444978249093419290651847764073607607794045076386643023306458718171574989185213684263628336385268818202054811378810216623440644076846464902798568705083282619513191855087399010760232112434412274701034094429954231366422968991322244343038458681255035356984900384509158858007713047428143658924970374944616430311056440919114824023838380098825914755712289724493770021
e = 3
c0 = 6965891612987861726975066977377253961837139691220763821370036576350605576485706330714192837336331493653283305241193883593410988132245791554283874785871849223291134571366093850082919285063130119121338290718389659761443563666214229749009468327825320914097376664888912663806925746474243439550004354390822079954583102082178617110721589392875875474288168921403550415531707419931040583019529612270482482718035497554779733578411057633524971870399893851589345476307695799567919550426417015815455141863703835142223300228230547255523815097431420381177861163863791690147876158039619438793849367921927840731088518955045807722225
 
 
n1 = 20463913454649855046677206889944639231694511458416906994298079596685813354570085475890888433776403011296145408951323816323011550738170573801417972453504044678801608709931200059967157605416809387753258251914788761202456830940944486915292626560515250805017229876565916349963923702612584484875113691057716315466239062005206014542088484387389725058070917118549621598629964819596412564094627030747720659155558690124005400257685883230881015636066183743516494701900125788836869358634031031172536767950943858472257519195392986989232477630794600444813136409000056443035171453870906346401936687214432176829528484662373633624123
e = 3
c1 = 5109363605089618816120178319361171115590171352048506021650539639521356666986308721062843132905170261025772850941702085683855336653472949146012700116070022531926476625467538166881085235022484711752960666438445574269179358850309578627747024264968893862296953506803423930414569834210215223172069261612934281834174103316403670168299182121939323001232617718327977313659290755318972603958579000300780685344728301503641583806648227416781898538367971983562236770576174308965929275267929379934367736694110684569576575266348020800723535121638175505282145714117112442582416208209171027273743686645470434557028336357172288865172
 
 
n2 = 19402640770593345339726386104915705450969517850985511418263141255686982818547710008822417349818201858549321868878490314025136645036980129976820137486252202687238348587398336652955435182090722844668488842986318211649569593089444781595159045372322540131250208258093613844753021272389255069398553523848975530563989367082896404719544411946864594527708058887475595056033713361893808330341623804367785721774271084389159493974946320359512776328984487126583015777989991635428744050868653379191842998345721260216953918203248167079072442948732000084754225272238189439501737066178901505257566388862947536332343196537495085729147
e = 3
c2 = 5603386396458228314230975500760833991383866638504216400766044200173576179323437058101562931430558738148852367292802918725271632845889728711316688681080762762324367273332764959495900563756768440309595248691744845766607436966468714038018108912467618638117493367675937079141350328486149333053000366933205635396038539236203203489974033629281145427277222568989469994178084357460160310598260365030056631222346691527861696116334946201074529417984624304973747653407317290664224507485684421999527164122395674469650155851869651072847303136621932989550786722041915603539800197077294166881952724017065404825258494318993054344153
 
 
n3 = 12005639978012754274325188681720834222130605634919280945697102906256738419912110187245315232437501890545637047506165123606573171374281507075652554737014979927883759915891863646221205835211640845714836927373844277878562666545230876640830141637371729405545509920889968046268135809999117856968692236742804637929866632908329522087977077849045608566911654234541526643235586433065170392920102840518192803854740398478305598092197183671292154743153130012885747243219372709669879863098708318993844005566984491622761795349455404952285937152423145150066181043576492305166964448141091092142224906843816547235826717179687198833961
e = 3
c3 = 1522280741383024774933280198410525846833410931417064479278161088248621390305797210285777845359812715909342595804742710152832168365433905718629465545306028275498667935929180318276445229415104842407145880223983428713335709038026249381363564625791656631137936935477777236936508600353416079028339774876425198789629900265348122040413865209592074731028757972968635601695468594123523892918747882221891834598896483393711851510479989203644477972694520237262271530260496342247355761992646827057846109181410462131875377404309983072358313960427035348425800940661373272947647516867525052504539561289941374722179778872627956360577
 
 
n4 = 17795451956221451086587651307408104001363221003775928432650752466563818944480119932209305765249625841644339021308118433529490162294175590972336954199870002456682453215153111182451526643055812311071588382409549045943806869173323058059908678022558101041630272658592291327387549001621625757585079662873501990182250368909302040015518454068699267914137675644695523752851229148887052774845777699287718342916530122031495267122700912518207571821367123013164125109174399486158717604851125244356586369921144640969262427220828940652994276084225196272504355264547588369516271460361233556643313911651916709471353368924621122725823
e = 3
c4 = 8752507806125480063647081749506966428026005464325535765874589376572431101816084498482064083887400646438977437273700004934257274516197148448425455243811009944321764771392044345410680448204581679548854193081394891841223548418812679441816502910830861271884276608891963388657558218620911858230760629700918375750796354647493524576614017731938584618983084762612414591830024113057983483156974095503392359946722756364412399187910604029583464521617256125933111786441852765229820406911991809039519015434793656710199153380699319611499255869045311421603167606551250174746275803467549814529124250122560661739949229005127507540805
 
 
n5 = 25252721057733555082592677470459355315816761410478159901637469821096129654501579313856822193168570733800370301193041607236223065376987811309968760580864569059669890823406084313841678888031103461972888346942160731039637326224716901940943571445217827960353637825523862324133203094843228068077462983941899571736153227764822122334838436875488289162659100652956252427378476004164698656662333892963348126931771536472674447932268282205545229907715893139346941832367885319597198474180888087658441880346681594927881517150425610145518942545293750127300041942766820911120196262215703079164895767115681864075574707999253396530263
e = 3
c5 = 23399624135645767243362438536844425089018405258626828336566973656156553220156563508607371562416462491581383453279478716239823054532476006642583363934314982675152824147243749715830794488268846671670287617324522740126594148159945137948643597981681529145611463534109482209520448640622103718682323158039797577387254265854218727476928164074249568031493984825273382959147078839665114417896463735635546290504843957780546550577300001452747760982468547756427137284830133305010038339400230477403836856663883956463830571934657200851598986174177386323915542033293658596818231793744261192870485152396793393026198817787033127061749
 
 
n6 = 19833203629283018227011925157509157967003736370320129764863076831617271290326613531892600790037451229326924414757856123643351635022817441101879725227161178559229328259469472961665857650693413215087493448372860837806619850188734619829580286541292997729705909899738951228555834773273676515143550091710004139734080727392121405772911510746025807070635102249154615454505080376920778703360178295901552323611120184737429513669167641846902598281621408629883487079110172218735807477275590367110861255756289520114719860000347219161944020067099398239199863252349401303744451903546571864062825485984573414652422054433066179558897
e = 3
c6 = 15239683995712538665992887055453717247160229941400011601942125542239446512492703769284448009141905335544729440961349343533346436084176947090230267995060908954209742736573986319254695570265339469489948102562072983996668361864286444602534666284339466797477805372109723178841788198177337648499899079471221924276590042183382182326518312979109378616306364363630519677884849945606288881683625944365927809405420540525867173639222696027472336981838588256771671910217553150588878434061862840893045763456457939944572192848992333115479951110622066173007227047527992906364658618631373790704267650950755276227747600169403361509144
 
n=[n0,n1,n2,n3,n4,n5,n6]
c=[c0,c1,c2,c3,c4,c5,c6]
id=0
for i,j,k in combinations(range(len(n)),3):
    mod=[n[i],n[j],n[k]]
    remains =[c[i],c[j],c[k]]
    m =iroot(crt(remains,mod),3)
    flag = long_to_bytes(m[0])
    if b'crypto' in flag:
        print(flag)

* **Flag:crypto{1f_y0u_d0nt_p4d_y0u_4r3_Vuln3rabl3}**
## PRIMES PART 2
### Infinite Descent
* 
* descent.py:

#!/usr/bin/env python3

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.txt:`

    n = 383347712330877040452238619329524841763392526146840572232926924642094891453979246383798913394114305368360426867021623649667024217266529000859703542590316063318592391925062014229671423777796679798747131250552455356061834719512365575593221216339005132464338847195248627639623487124025890693416305788160905762011825079336880567461033322240015771102929696350161937950387427696385850443727777996483584464610046380722736790790188061964311222153985614287276995741553706506834906746892708903948496564047090014307484054609862129530262108669567834726352078060081889712109412073731026030466300060341737504223822014714056413752165841749368159510588178604096191956750941078391415634472219765129561622344109769892244712668402761549412177892054051266761597330660545704317210567759828757156904778495608968785747998059857467440128156068391746919684258227682866083662345263659558066864109212457286114506228470930775092735385388316268663664139056183180238043386636254075940621543717531670995823417070666005930452836389812129462051771646048498397195157405386923446893886593048680984896989809135802276892911038588008701926729269812453226891776546037663583893625479252643042517196958990266376741676514631089466493864064316127648074609662749196545969926051
    e = 65537
    c = 98280456757136766244944891987028935843441533415613592591358482906016439563076150526116369842213103333480506705993633901994107281890187248495507270868621384652207697607019899166492132408348789252555196428608661320671877412710489782358282011364127799563335562917707783563681920786994453004763755404510541574502176243896756839917991848428091594919111448023948527766368304503100650379914153058191140072528095898576018893829830104362124927140555107994114143042266758709328068902664037870075742542194318059191313468675939426810988239079424823495317464035252325521917592045198152643533223015952702649249494753395100973534541766285551891859649320371178562200252228779395393974169736998523394598517174182142007480526603025578004665936854657294541338697513521007818552254811797566860763442604365744596444735991732790926343720102293453429936734206246109968817158815749927063561835274636195149702317415680401987150336994583752062565237605953153790371155918439941193401473271753038180560129784192800351649724465553733201451581525173536731674524145027931923204961274369826379325051601238308635192540223484055096203293400419816024111797903442864181965959247745006822690967920957905188441550106930799896292835287867403979631824085790047851383294389

* Bài này mình dùng **Attack 3: Fermat Attack** để tìm p,q.
* 
* **Flag:crypto{f3rm47_w45_4_g3n1u5}**
### Marin's Secrets
* 
* marin.py:

#!/usr/bin/env python3

import random
from Crypto.Util.number import bytes_to_long, inverse
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.txt:

n: 658416274830184544125027519921443515789888264156074733099244040126213682497714032798116399288176502462829255784525977722903018714434309698108208388664768262754316426220651576623731617882923164117579624827261244506084274371250277849351631679441171018418018498039996472549893150577189302871520311715179730714312181456245097848491669795997289830612988058523968384808822828370900198489249243399165125219244753790779764466236965135793576516193213175061401667388622228362042717054014679032953441034021506856017081062617572351195418505899388715709795992029559042119783423597324707100694064675909238717573058764118893225111602703838080618565401139902143069901117174204252871948846864436771808616432457102844534843857198735242005309073939051433790946726672234643259349535186268571629077937597838801337973092285608744209951533199868228040004432132597073390363357892379997655878857696334892216345070227646749851381208554044940444182864026513709449823489593439017366358869648168238735087593808344484365136284219725233811605331815007424582890821887260682886632543613109252862114326372077785369292570900594814481097443781269562647303671428895764224084402259605109600363098950091998891375812839523613295667253813978434879172781217285652895469194181218343078754501694746598738215243769747956572555989594598180639098344891175879455994652382137038240166358066403475457 
e: 65537
c: 400280463088930432319280359115194977582517363610532464295210669530407870753439127455401384569705425621445943992963380983084917385428631223046908837804126399345875252917090184158440305503817193246288672986488987883177380307377025079266030262650932575205141853413302558460364242355531272967481409414783634558791175827816540767545944534238189079030192843288596934979693517964655661507346729751987928147021620165009965051933278913952899114253301044747587310830419190623282578931589587504555005361571572561916866063458812965314474160499067525067495140150092119620928363007467390920130717521169105167963364154636472055084012592138570354390246779276003156184676298710746583104700516466091034510765027167956117869051938116457370384737440965109619578227422049806566060571831017610877072484262724789571076529586427405780121096546942812322324807145137017942266863534989082115189065560011841150908380937354301243153206428896320576609904361937035263985348984794208198892615898907005955403529470847124269512316191753950203794578656029324506688293446571598506042198219080325747328636232040936761788558421528960279832802127562115852304946867628316502959562274485483867481731149338209009753229463924855930103271197831370982488703456463385914801246828662212622006947380115549529820197355738525329885232170215757585685484402344437894981555179129287164971002033759724456

* Mình có tìm thấy thứ này(https://vi.wikipedia.org/wiki/Danh_s%C3%A1ch_s%E1%BB%91_nguy%C3%AAn_t%E1%BB%91_Mersenne_v%C3%A0_s%E1%BB%91_ho%C3%A0n_h%E1%BA%A3o). Marin Mersenne là một nhà toán học người pháp nổi tiếng ở thế kỷ 17 được biết đến với việc nghiên cứu các số nguyên tố Mersenne với dạng **2^n^-1**.
* 
* **Flag:crypto{Th3se_Pr1m3s_4r3_t00_r4r3}**
### RSA Backdoor Viability
* 
* complex_primes.py:

#!/usr/bin/env python3

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}")

* output.txt:

n = 709872443186761582125747585668724501268558458558798673014673483766300964836479167241315660053878650421761726639872089885502004902487471946410918420927682586362111137364814638033425428214041019139158018673749256694555341525164012369589067354955298579131735466795918522816127398340465761406719060284098094643289390016311668316687808837563589124091867773655044913003668590954899705366787080923717270827184222673706856184434629431186284270269532605221507485774898673802583974291853116198037970076073697225047098901414637433392658500670740996008799860530032515716031449787089371403485205810795880416920642186451022374989891611943906891139047764042051071647203057520104267427832746020858026150611650447823314079076243582616371718150121483335889885277291312834083234087660399534665835291621232056473843224515909023120834377664505788329527517932160909013410933312572810208043849529655209420055180680775718614088521014772491776654380478948591063486615023605584483338460667397264724871221133652955371027085804223956104532604113969119716485142424996255737376464834315527822566017923598626634438066724763559943441023574575168924010274261376863202598353430010875182947485101076308406061724505065886990350185188453776162319552566614214624361251463
e = 65537
c = 608484617316138126443275660524263025508135383745665175433229598517433030003704261658172582370543758277685547533834085899541036156595489206369279739210904154716464595657421948607569920498815631503197235702333017824993576326860166652845334617579798536442066184953550975487031721085105757667800838172225947001224495126390587950346822978519677673568121595427827980195332464747031577431925937314209391433407684845797171187006586455012364702160988147108989822392986966689057906884691499234298351003666019957528738094330389775054485731448274595330322976886875528525229337512909952391041280006426003300720547721072725168500104651961970292771382390647751450445892361311332074663895375544959193148114635476827855327421812307562742481487812965210406231507524830889375419045542057858679609265389869332331811218601440373121797461318931976890674336807528107115423915152709265237590358348348716543683900084640921475797266390455366908727400038393697480363793285799860812451995497444221674390372255599514578194487523882038234487872223540513004734039135243849551315065297737535112525440094171393039622992561519170849962891645196111307537341194621689797282496281302297026025131743423205544193536699103338587843100187637572006174858230467771942700918388

* Ban đầu mình thử factor **n** thì ra **p,q** luôn .
* 
* **Flag:crypto{I_want_to_Break_Square-free_4p-1}**

### Ron was Wrong, Whit is Right
* **extract.py**:

from Crypto.Cipher import PKCS1_OAEP
from Crypto.PublicKey import RSA


msg = "???"

with open('21.pem') as f:
    key = RSA.importKey(f.read())

cipher = PKCS1_OAEP.new(key)
ciphertext = cipher.encrypt(msg)

with open('21.ciphertext', 'w') as f:
    f.write(ciphertext.hex())

* Bài này mình thấy các thao tác ghi key,cipher... tại tệp thứ 21.pem và 21.ciphertext. Mình đọc file ra thì thấy n factor được nên làm thôi.
* Về PKCS1_OAEP mình đọc qua ở đây https://pycryptodome.readthedocs.io/en/latest/src/cipher/oaep.html

from Crypto.Util.number import *
from Crypto.Cipher import PKCS1_OAEP
from Crypto.PublicKey import RSA

key = RSA.importKey(open("21.pem", "rb").read())
e = key.e
n = key.n
p = 919031168254299342928662994540730760042229248845820491699169870943314884504551963184014786520812939038906152950817942941469675496074887272906954399256046690838233813273902630076899906873722574023918253104149453601408405078374008695616160025877687382663027910687942091698042309812910101246025081363544171351624307177908410700904833438480012985928358897861427063761678614898919524867442676631453135379994570031284289815099294504127712924001149921480778993635917803466637717023744788311275545126346774536416864472035644211758788016642401235014385037912224180351022196262011724157012443048941426178651665266181311662824205620324073087330858064769424755443807165558567191049013947419763315902476674266627953223373671797370373786249718677582213173537848582863398367624397247597103174897140005790273296171101569756006898658668311846034013183862374297777882433967015111727139360441681664840944403450472574336901043555319067050153928231938431298082827397506406624964952344826628463723499263165279281720105570577138817805451223334196017505528543229067732013216932022575286870744622250293712218581458417969597311485156075637589299870500738770767213366940656708757081771498126771190548298648709527029056697749965377697006723247968508680596118923
q = 991430390905926023965735525726256769345153760248048478891327804533279477721590201738061124861790305326884541900044434890157058142414306020739922709698601329762087825767461256626800629782378634339618941488765491437487541851308806651586976069659042714378353883168031522106709494592827914376213512564492771821921367377484213072867988877925314809325159382342584541006645302760204539354879391605736604946702073863673524002591877977949645618863730441482821840664748508050205004505250025193611888170440612737112479006348533153568103452396596042639466753099280111709882461562564978070397786887446291916733276692400981917025361391646188802038772976331121474570242334921390569285834250256522656433623912544555266998750630136756355560927237594975904642791712318215315246754105993145827690531584325461597482035600919501967088106457091199733024323755210212616553447076697617349235377466327471959683763796707566328536834402308887105044128592177681553611608618850780128709949316259039664054913946726480968288231015999572777436469163437066403964134928735809253108394078092917006632332098357725950865697047565284013456253933234017983509582245874130968218422573483012858388392588302838940565560162598810462310034964473576147200222580784694005333482381
c = 0xc62d91677825632cb8ac9d2fbee7490fca70b3f067bd8d811fa446a21001de7943cacafc429b2513d3f20c3224d212ca2937a4a4ea10792a1c498b791e978e4b050b525576bc68421e40d9f420c0b8a07778daf69edf2095bf48222896bb2d6581288ce7a2e7aec15a88a440ff1a1e48beb56f68b4f860d1f64a6ec8cafed90846b7d893bc482df69c8478d5a0d6fc2d043cdd97178740a9eb59d2576b5136200c8ea77e648c88e6c5104ca5d0c6add2fc2c8569ce909f8461e7fa3d901fe67eaeff656399d4751fedba9973e246427e0c7a217f5bdc3edcb5033f17b5ef53419e340355a809eb46f48f538e880abd6f72212b02d3dbf2c4f633a503e648d1a835c4574b23e329e1c51078ea7cbb7533e771899498d4a5760bc0799b7e046f268f098fe0b57de47cd70ccf01ad3c9daec5027f306141bfe7a6c0bd29ee6caf94c7433c25e34ee974005e2360337cb6b3cec5eaf5d31d19f01435f4cdcaa455a18e78dee078395b8ad14b9c3a0d817dc1e3109c7b8af35ab3a5950bf47d5e621f9373ef421540052aac307ecea91f9c29c14bfd81b41d4c5a9b34a8ec2fa1ae06c3d881f39286c3d8dbb1849602fecc27bb135f7dd443e2598d247d1182d350b04be1ac0a734cb0e852a36902d88066ac375a35e279b126e413a97aaa35a0ba933f7b8d574c298332ce428c181464b240709a414af1b77103441b6ccfd0790eccea5926844054903c83f4cb415d600a6b7bc771c9e7a86394a2b427ebe8edec08b8095f561827716898e11caf6f0fe562af8a69f7b6469f0e86bdcc32f429f10821c763b34307efc5b2ae7fd524a07e5d0b762c096f025a3f240fb7bd3554582dcce32c175867d93970b0422e17870ec58f2a305545a3d284b3abb2d21a45ad8fd5faed0dc66312a5aa2f994606a51cd6682acd48ea3fb883f0611e1e5c2fb4047b5c80815ba5d3bcfefaf121bfde4d5c91ee27bb899ef0d29fa5c6dc4223ac2bfcff0217d08579a13e9b02dc97aa2622df62eeaaa38bb3bd087cdd209f03e8926a951e90eaa0f678a252a067ac66402a4c85865931689ed3b33f9f6de0c499f140ef508dfba6007a607a271dcbec18a61f7488bba34d143f93bc259310ffbf23f3391734d8d8811a4be8abf6382e55c2ccbfd80b1559d907fd8d46e0431cdbcd8fdb06d57973437f7b8ff5efc5a53c80d552e8fe622971f7376eeea35f4df9b32ada93e531a52b63ba13f6b7bf61ab337d6d93feb0e8c8a309dfa7e5f50e8cf9655b73ae64822b50db5312f35f4718b0668305065ea283ddf8f0a4e8f486ee9d119ebc584be1837b3d959a25ace208ffac2fb703390a72d3027b64fdd1955b513c0403f09232efa1794a277e0be3f4f9f3a6fd23c6e52101e723cef5db7a2a18a107cd522379adb40c5ed36b26cdf53a1000d7d576f1157b42aac3d3ee011275
phi_N = (p-1)*(q-1)
d = pow(e, -1, phi_N)
key = RSA.construct((n, e, d))
cipher = PKCS1_OAEP.new(key)

print(cipher.decrypt(bytes.fromhex(hex(c)[2:])).decode())

* **Flag:crypto{3ucl1d_w0uld_b3_pr0ud}**
## PADDING
### Bespoke Padding
* **13386.py**:

#!/usr/bin/env python3

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"}


"""
When you connect, the 'challenge' function will be called on your JSON
input.
"""
listener.start_server(port=13386)

* Mình ngó source code thì thấy rằng là $ct = (a*m+b)^emodn$
* Trước hết là mình cứ lấy thêm các số liệu.

from pwn import *
import requests
import json
from Crypto.Util.number import *


HOST = "socket.cryptohack.org"
PORT = 13386

r = remote(HOST,PORT)

def json_recv():
    line = r.readline()
    return json.loads(line.decode())

def json_send(hsh):
    request = json.dumps(hsh).encode()
    r.sendline(request)


print(r.readline())
requests = {"option":"get_flag"}

json_send(requests)

res = json_recv()

ct = res['encrypted_flag']
n = res['modulus']
pad = res['padding']
a = pad[0]
b = pad[1]

print(f'{ct = }')
print(f'{n = }')
print(f'{a = }')
print(f'{b = }')

* Mình thấy chall này phù hợp với cách giải quyết của https://en.wikipedia.org/wiki/Coppersmith%27s_attack. Nhưng kiểu $a*m+b$ thì là trường hợp https://en.wikipedia.org/wiki/Coppersmith%27s_attack#Franklin%E2%80%93Reiter_related-message_attack
* Vậy thì mình sẽ kết nối tới server để lấy thêm 1 bộ số $ct,n,a,b$ vì https://en.wikipedia.org/wiki/Coppersmith%27s_attack#Franklin%E2%80%93Reiter_related-message_attack
cần 2 bộ số khác nhau nhưng phải chung $n$.
* Sửa lại code pwntools kia 1 chút.

from pwn import *
import requests
import json
from Crypto.Util.number import *


HOST = "socket.cryptohack.org"
PORT = 13386

r = remote(HOST,PORT)

def json_recv():
    line = r.readline()
    return json.loads(line.decode())

def json_send(hsh):
    request = json.dumps(hsh).encode()
    r.sendline(request)


print(r.readline())
requests = {"option":"get_flag"}
json_send(requests)
res = json_recv()

n1 = res['modulus']
ct1 = res['encrypted_flag']
pad1 = res['padding']
a1 = pad1[0]
b1 = pad1[1]


while True:
    requests = {"option":"get_flag"}
    json_send(requests)
    res = json_recv()
    n2 = res['modulus']
    ct2 = res['encrypted_flag']
    pad2 = res['padding']
    a2 = pad2[0]
    b2 = pad2[1]
    if n1 == n2 and a1 != a2:
        break



n = n1
print(f'{n = }')
print(f'{ct1 = }')
print(f'{a1 = }')
print(f'{b1 = }')
print(f'{ct2 = }')
print(f'{a2 = }')
print(f'{b2 = }')

* Script lấy flag mình copy paste từ https://github.com/ashutosh1206/Crypton/blob/master/RSA-encryption/Attack-Franklin-Reiter/exploit.sage.

from sage.all import *
from Crypto.Util.number import *

e = 11
n = 22194831691821791704203828193266597327890972515513966625309967551716179880553022721038942514259104738217689644942700263130669490529695450220802697891198615867921188286357752275238072100652491987989113071965099210549244803254616983956314167540650389720442184104457066655049554043996826488710683600567646282085517208708589277144332517971585217739394776666403752422582716534295436877847250290203687145437886814361979720675132561563041469353702873391507326914385269503040407107716106302819896138572076791236579215634042003493877702817302634560357698660895394598711194654157997848913634617233149676259902177268403556620787
ct1 = 11208874911729329282284342222289477472007366146054759076026881983993601043460599235977362315295363992108256232335569584984927659596553353760397514480959898207368530833803791801998989363744250966481176339662639686437906801472146098299601034256343099068542016395973619515585994305510172179099883267420368359741928680217529331272640584734372495640028794182033156794074823809990615060346578911584868013914529419043167039691183463520147798768253187206788790453706531942725022177552326340740964248924918057045450592985179369889439033169616505399579989014380387654129021591784109461336359032630670627339335695822358528015923
a1 = 13617991514261329585632595727762435592955028356397992093771717342228763870580545642872390433352056800484833023556944227907608511706777473896900110150932871126759922474245944540717302305744362170378627177116357184772239287296429773474107805630068610301969826233639605331550863676988564068023514436405174117470240693689587197500674463636678906992472462620201475265478133200736114018845689730174477450419036177086648698631202169911035133504196136454910692582759380933385234080590585893210998100210429009524249982940147027579284980361942110205604414423864126278313418200630912553472951245700739669406769473448846223351620
b1 = 13080430320381912481781301705527028529886394415789256100463017646588297642468103324305004977447048080147701571434045466043223800812209978791421491329538553869903264552836404898179988412338556345762748141485053417775532436217471662700829800300101382934024247585680635125739391245311802676676881415572567548050665008633779924512766530828676629423697142580905569077463213041434381706890214618694698011178892730402129683174773861396860348790154298620920030602290999379906017504742280386380462173022189483078391933865972135567089686554527837144709018770432534447781621818859261993051957989416237308293838203399669808271897
ct2 = 2725824240985491310790119168998159182334015386135277910971937556919628949575479910233859349223232055050429291351532287759834808212057868824353621094273993252511872017891621658725196635175659083751433780080942560302379613928902192698106771489929594583415393561658534084759655934638988283217904687692284171433405789537106889051415206212307041473734511024872905605018876288529353076223785713032659236637217002540177736779139660107856849396785352735629388505548075247281533548991429871202508752978543926362334243221735063244375342259892345731506730743446658760483865122610948219027552035852864941271625361224653453019648
a2 = 10892344389255696192272792594477335166204112023406168185029411778663228700413002827891348318648737249637156039917182854604878583957147328153317813461902876432258317800424235021746742772473207090497172803874326285960751351710300130066239965008216964563088829761789760956254407969806694860380027451343744049413529763019519261560780259208589385946007999918493522500594970093979680156972117612670976877885116081531383573426200737591793142740467080240458786550997767363595794668275382273208170021516778372897735104535937837108390120262090427458914613509636158866995624627908322094994543820040206330119166416907986601166468
b2 = 16191968406404684702377720375515765521131909156055952093526779091065844152577032481460358371455825362861970306968997217008042035992745681808940096015218990255751755208333204825876522224134433049980638849627478159574923063686305685079199929912158099182004752522075904802287380762437268225652318976375188971645960482700640655141706991939804055350138806117151173384454571731657576491543219554514486393107067940731868683623178153144567881844387721058962357467106948038104135250257657438855792542070166717068166634993706340176649148291659340035917992168269821016770238180911382512457486114516031878929442131257722433423038


def gcd(a, b): 
    while b:
        a, b = b, a % b
    return a.monic()


P.<x> = PolynomialRing(Zmod(n))
g1 = (a1*x + b1)^e - ct1
g2 = (a2*x + b2)^e - ct2
m  = -gcd(g1, g2).coefficients()[0]
flag = long_to_bytes(int(m))
print(flag)

* **Flag:crypto{linear_padding_isnt_padding}**
### Null or Never
* **pad_encrypt.py**:

#!/usr/bin/env python3

from Crypto.PublicKey import RSA
from Crypto.Util.number import bytes_to_long

FLAG = b"crypto{???????????????????????????????????}"


def pad100(msg):
    return msg + b'\x00' * (100 - len(msg))


key = RSA.generate(1024, e=3)
n, e = key.n, key.e

m = bytes_to_long(pad100(FLAG))
c = pow(m, e, n)

print(f"n = {n}")
print(f"e = {e}")
print(f"c = {c}")

* output.txt

n = 95341235345618011251857577682324351171197688101180707030749869409235726634345899397258784261937590128088284421816891826202978052640992678267974129629670862991769812330793126662251062120518795878693122854189330426777286315442926939843468730196970939951374889986320771714519309125434348512571864406646232154103
e = 3
c = 63476139027102349822147098087901756023488558030079225358836870725611623045683759473454129221778690683914555720975250395929721681009556415292257804239149809875424000027362678341633901036035522299395660255954384685936351041718040558055860508481512479599089561391846007771856837130233678763953257086620228436828

* Khác với chall trên thì lần này $ct = (m + pad)^e mod n$.Do để bài đã cho rõ định dạng của flag nên mình biết dộ dài flag và độ dài padding.
* Vậy dùng https://en.wikipedia.org/wiki/Coppersmith%27s_attack#
* Full script:

from sage.all import *
from Crypto.Util.number import *

n = 95341235345618011251857577682324351171197688101180707030749869409235726634345899397258784261937590128088284421816891826202978052640992678267974129629670862991769812330793126662251062120518795878693122854189330426777286315442926939843468730196970939951374889986320771714519309125434348512571864406646232154103
e = 3
c = 63476139027102349822147098087901756023488558030079225358836870725611623045683759473454129221778690683914555720975250395929721681009556415292257804239149809875424000027362678341633901036035522299395660255954384685936351041718040558055860508481512479599089561391846007771856837130233678763953257086620228436828

P.<x> = PolynomialRing(Zmod(n))

flag_head = b'crypto{'
flag_tail = b'}'
pad = b'\x00'*57

flag_fake = flag_head + b'\x00'*35 + flag_tail + pad
flag_fake = bytes_to_long(flag_fake)

f = (flag_fake + x*256**(100-7-35))^e - c
f = f.monic()
res = f.small_roots(epsilon = 1/30)
flag_main = long_to_bytes(int(res[0]))
flag = flag_head + flag_main + flag_tail
print(flag)

* **FLag:crypto{n0n_574nd4rd_p4d_c0n51d3r3d_h4rmful}**

## SIGNATURES PART 1
### Signing Server
* **13374.py**:

#!/usr/bin/env python3

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"}


listener.start_server(port=13374)

* Chall này thì không có gì khó khăn cả. Mình chỉ cần lấy được secret bằng cách gửi

requests = {"option":"get_secret"}

* rồi gửi

requests = {"option":"sign","msg":ct}

* là xong.
* Full script:

from pwn import *
import requests
import json
from Crypto.Util.number import *


HOST = "socket.cryptohack.org"
PORT = 13374

r = remote(HOST,PORT)

def json_recv():
    line = r.readline()
    return json.loads(line.decode())

def json_send(hsh):
    request = json.dumps(hsh).encode()
    r.sendline(request)

print(r.readline())

requests = {"option":"get_secret"}
json_send(requests)
res = json_recv()
ct = res['secret']

requests = {"option":"sign","msg":ct}
json_send(requests)
res = json_recv()


flag = long_to_bytes(int(res['signature'],16))
print(flag)

* **Flag:crypto{d0n7_516n_ju57_4ny7h1n6}**
### Let's Decrypt
* 13391.py:

#!/usr/bin/env python3

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"}


listener.start_server(port=13391)

* Phân tính source 1 chút thì mình sẽ có flag nếu thỏa mãn :
* Chúng ta đã có 
* Và 
* Việc cần làm bây giờ của mình là tính toán digest sao cho 
* Thực tế là mình lấy giá trị $s = signature$ thôi chứ $n,e$ của server mình không quan tâm.
* Để có flag thì mình phải tính toán 3 giá trị 
rồi gửi lên server.
* Về phần msg, mình thấy rằng msg phải thỏa mãn:
* Nôm na là msg phải có phần đầu là $I am Mallory$ và phần đuôi là $own CryptoHack.org$. Lợi dụng điều đó mình sẽ gửi 1 msg khác có định dạng tương tự.
* Còn về tính $e$ với $n$ thì:
* Phương trình cần thỏa mãn:
* $s^e mod n = digest$
* Để đơn giản mình chọn $e = 1$. Còn $n$ thì tính theo:$n = s - digest$
* Full script:

from pwn import *
import requests
import json
from Crypto.Util.number import *
from pkcs1 import emsa_pkcs1_v15

HOST = "socket.cryptohack.org"
PORT = 13391

r = remote(HOST,PORT)

def json_recv():
    line = r.readline()
    return json.loads(line.decode())

def json_send(hsh):
    request = json.dumps(hsh).encode()
    r.sendline(request)

print(r.readline())

requests = {"option":"get_signature"}
json_send(requests)
res = json_recv()

s = int(res['signature'],16)

msg = "I am Mallory.(But my name is Giang. I am a hacker).own CryptoHack.org"
digest = emsa_pkcs1_v15.encode(msg.encode(), 256)
digest = bytes_to_long(digest)
e = 1
n = s - digest

requests =  {'option': 'verify','msg': msg,'N': hex(n),'e': hex(e)}

json_send(requests)
res = json_recv()
print(res)

* **Flag:crypto{dupl1c4t3_s1gn4tur3_k3y_s3l3ct10n}**
### Blinding Light
* 13376.py:

#!/usr/bin/env python3

from Crypto.Util.number import bytes_to_long, long_to_bytes
from utils import listener

FLAG = "crypto{?????????????????????????????}"
ADMIN_TOKEN = b"admin=True"


class Challenge():
    def __init__(self):
        self.before_input = "Watch out for the Blinding Light\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'] == 'get_pubkey':
            return {"N": hex(N), "e": hex(E) }

        elif your_input['option'] == 'sign':
            msg_b = bytes.fromhex(your_input['msg'])
            if ADMIN_TOKEN in msg_b:
                return {"error": "You cannot sign an admin token"}

            msg_i = bytes_to_long(msg_b)
            return {"msg": your_input['msg'], "signature": hex(pow(msg_i, D, N)) }

        elif your_input['option'] == 'verify':
            msg_b = bytes.fromhex(your_input['msg'])
            msg_i = bytes_to_long(msg_b)
            signature = int(your_input['signature'], 16)

            if msg_i < 0 or msg_i > N:
                # prevent attack where user submits admin token plus or minus N
                return {"error": "Invalid msg"}

            verified = pow(signature, E, N)
            if msg_i == verified:
                if long_to_bytes(msg_i) == ADMIN_TOKEN:
                    return {"response": FLAG}
                else:
                    return {"response": "Valid signature"}
            else:
                return {"response": "Invalid signature"}

        else:
            return {"error": "Invalid option"}


listener.start_server(port=13376)

* Nhìn tên chall thì mình đoán ngay là dùng **Attack 7:Blinding Attack**.Phân tích source thì có vẻ là như vậy.
* 
* Theo đúng lý thuyết thì bài này nếu mình gửi $M = ADMIN-TOKEN$ là chim lượn ngay XD.
* Mình sẽ tính toán và chọn $M_0 = 2^e* ADMIN-TOKEN$.Gửi giá trị này cho **option : sign** thì mình có được giá trị $signature=ADMIN-TOKEN ^ D mod N$. Vậy gửi nốt lên **option : verify** là có flag thôi.
* Full script:

from pwn import *
import requests
import json
from Crypto.Util.number import *
from pkcs1 import emsa_pkcs1_v15

HOST = "socket.cryptohack.org"
PORT = 13376

r = remote(HOST,PORT)

def json_recv():
    line = r.readline()
    return json.loads(line.decode())

def json_send(hsh):
    request = json.dumps(hsh).encode()
    r.sendline(request)

print(r.readline())

ADMIN_TOKEN = b"admin=True"

requests = {"option":"get_pubkey"}
json_send(requests)
res = json_recv()
n = int(res['N'],16)
e = int(res['e'],16)

msg_i = (pow(2, e) * bytes_to_long(ADMIN_TOKEN)) % n
msg_b = long_to_bytes(msg_i)


requests = {"option":"sign","msg":hex(msg_i)[2:]}
json_send(requests)
res = json_recv()

s = int(res['signature'],16)
signature = s//2
msg = bytes_to_long(ADMIN_TOKEN)

requests = {"option":"verify","msg":hex(msg)[2:],"signature":hex(signature)[2:]}
json_send(requests)
res = json_recv()

flag = res['response']
print(flag)

* **Flag:crypto{m4ll34b1l17y_c4n_b3_d4n63r0u5}**
## SIGNATURES PART 2
### Vote for Pedro
* 13375.py:

#!/usr/bin/env python3

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"}


listener.start_server(port=13375)

* alice.key:

N = 22266616657574989868109324252160663470925207690694094953312891282341426880506924648525181014287214350136557941201445475540830225059514652125310445352175047408966028497316806142156338927162621004774769949534239479839334209147097793526879762417526445739552772039876568156469224491682030314994880247983332964121759307658270083947005466578077153185206199759569902810832114058818478518470715726064960617482910172035743003538122402440142861494899725720505181663738931151677884218457824676140190841393217857683627886497104915390385283364971133316672332846071665082777884028170668140862010444247560019193505999704028222347577

e = 3

* Điều kiện để chúng ta có flag:
* Về :

vote = verified_vote.split(b'\00')[-1]

* Nôm na là giá trị **verified_vote** nó sẽ lấy cái chuỗi cuối cùng ở đằng sau byte $b'\00'$. Ví dụ :

b'\00\00giang' -> b'giang'

* Để có flag thì cần tính toán giá trị vote sao cho $vote^emodn$ đem đi split thì đúng bằng **b'VOTE FOR PEDRO'**.
* Do là tính toán trên các phép toán đồng dư nên là sẽ có rất nhiều trường hợp thõa mãn. Mình đương nhiên sẽ chọn trường hợp dễ nhất trước đó là $m^e<n$.
* Vậy thì mình có :

vote^3 = bytes_to_long(find + b'\00' + b'VOTE FOR PEDRO')

* hay là :

vote^3 = find_value * 256^15 + bytes_to_long(b'\00VOTE FOR PEDRO')
                               ``đặt cái này là vote_value``

* Mình giải phương trình đồng dư:

vote*3 = vote_value mod (256^15)

* Dùng sageMath là tìm được giá trị vote khi vote_value mình đã có rồi:

from sage.all import *
from Crypto.Util.number import *

vote = b'VOTE FOR PEDRO'
vote_value = bytes_to_long(vote)

m = var('m')
f = m^3 == vote_value
m = solve_mod(f, 256^15)

print(m)

* Mình tìm được vote = 855520592299350692515886317752220783
* Vậy thì gửi nốt lên sever là có flag thôi XD.
* Full script:

from pwn import *
import requests
import json
from Crypto.Util.number import *
import gmpy2

HOST = "socket.cryptohack.org"
PORT = 13375

r = remote(HOST,PORT)

def json_recv():
    line = r.readline()
    return json.loads(line.decode())

def json_send(hsh):
    request = json.dumps(hsh).encode()
    r.sendline(request)

print(r.readline())

vote = 855520592299350692515886317752220783
requests = {"option":"vote","vote":hex(vote)}
json_send(requests)
res = json_recv()
flag = res['flag']
print(flag)

* **Flag:crypto{y0ur_v0t3_i5_my_v0t3}**
### Let's Decrypt Again
* 13394.py

#!/usr/bin/env python3

import hashlib
import re
import secrets
from Crypto.Util.number import bytes_to_long, long_to_bytes, getPrime, inverse, isPrime
from pkcs1 import emsa_pkcs1_v15
from utils import listener
# from params import N, E, D

FLAG = b"crypto{????????????????????????????????????}"

BIT_LENGTH = 768

MSG = b'We are hyperreality and Jack and we own CryptoHack.org'
DIGEST = emsa_pkcs1_v15.encode(MSG, BIT_LENGTH // 8)
SIGNATURE = pow(bytes_to_long(DIGEST), D, N)
BTC_PAT = re.compile("^Please send all my money to ([1-9A-HJ-NP-Za-km-z]+)$")


def xor(a, b):
    assert len(a) == len(b)
    return bytes(x ^ y for x, y in zip(a, b))


def btc_check(msg):
    alpha = "123456789ABCDEFGHJKLMNPQRSTUVWXYZabcdefghijkmnopqrstuvwxyz"
    addr = BTC_PAT.match(msg)
    if not addr:
        return False
    addr = addr.group(1)
    raw = b"\0" * (len(addr) - len(addr.lstrip(alpha[0])))
    res = 0
    for c in addr:
        res *= 58
        res += alpha.index(c)
    raw += long_to_bytes(res)

    if len(raw) != 25:
        return False
    if raw[0] not in [0, 5]:
        return False
    return raw[-4:] == hashlib.sha256(hashlib.sha256(raw[:-4]).digest()).digest()[:4]


PATTERNS = [
    re.compile(r"^This is a test(.*)for a fake signature.$").match,
    re.compile(r"^My name is ([a-zA-Z\s]+) and I own CryptoHack.org$").match,
    btc_check
]


class Challenge():
    def __init__(self):
        self.shares = [secrets.token_bytes(len(FLAG))
                       for _ in range(len(PATTERNS) - 1)]
        last_share = FLAG
        for s in self.shares:
            last_share = xor(last_share, s)
        self.shares.append(last_share)

        self.pubkey = None
        self.suffix = None

        self.before_input = "This server validates statements we make for you. Present your messages and public key, and if the signature matches ours, you must undoubtably be us. Just do it multiple times to make sure...\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'] == 'set_pubkey':
            if self.pubkey is None:
                pubkey = int(your_input['pubkey'], 16)
                if isPrime(pubkey):
                    return {"error": "Everyone knows RSA keys are not primes..."}
                self.pubkey = pubkey
                self.suffix = secrets.token_hex(32)

                return {"status": "ok", "suffix": self.suffix}
            return {"error": "I already had one"}

        elif your_input['option'] == 'claim':
            if self.pubkey is None:
                return {"error": "I need your modulus first, please"}

            msg = your_input['msg']
            n = self.pubkey
            e = int(your_input['e'], 16)
            index = your_input['index']
            if not (0 <= index < len(PATTERNS)):
                return {"error": "invalid index"}

            if not msg.endswith(self.suffix):
                return {"error": "Invalid message"}

            digest = emsa_pkcs1_v15.encode(msg.encode(), BIT_LENGTH // 8)
            calculated_digest = pow(SIGNATURE, e, n)

            if bytes_to_long(digest) == calculated_digest:
                r = PATTERNS[index](msg[:-len(self.suffix)])
                if r:
                    return {"msg": "Congratulations, here's a secret", "secret": self.shares[index].hex()}
                else:
                    return {"msg": "Ownership verified."}
            else:
                return {"error": "Invalid signature"}

        else:
            return {"error": "Invalid option"}


listener.start_server(port=13394)

* Bài này thì khó hơn **Let's Decrypt** rồi.
* Shares sẽ chứa 2 chuỗi bytes đầu là random, chuỗi thứ 3 là kết quả phép xor giữa flag và 2 chuỗi đó. Vậy không còn cách nào khác để có flag buộc phải tìm được shares.
* Giống **Let's Decrypt** thì option này trả về $N,E,signature$ thôi.
* option này thì mình phải tính toán 1 giá trị $n$ mới . Sau đó thì server sẽ gửi lại 1 chuỗi hex được random tên là suffix.
* Muốn lấy lại được **shares** như mình nói ở trên thì:
* Gửi $e,index,msg$ tương ứng để có từng phần tử trong $shares$.
* Do giá trị $n$ mà mình gửi vào từ trước là sẽ cố định nên phải tính toán $n$ như nào để $e1,e2,e3$ dễ dàng tìm được.
* Còn về phần thao tác với $msg$ như nào thì xem lại **Let's Decrypt**.
* Mấu chốt lại là phải chọn $n$ là [Smooth number](https://en.wikipedia.org/wiki/Smooth_number)
* Mục đích của việc chọn $n$ là [Smooth number](https://en.wikipedia.org/wiki/Smooth_number) là để [Pohlig–Hellman](https://en.wikipedia.org/wiki/Pohlig%E2%80%93Hellman_algorithm) giải bài toán [Lôgarit rời rạc](https://vi.wikipedia.org/wiki/L%C3%B4garit_r%E1%BB%9Di_r%E1%BA%A1c) .
* Bởi vì tìm $e$ từ phương trình $ct = m^emodn$ là vô cùng khó khăn nếu n không là [Smooth number](https://en.wikipedia.org/wiki/Smooth_number)
* Chung quy lại bài này quan trọng nhất là chọn $n$ sao cho có thể $discrete-log$ để tìm lại```e```
* Với tìm hiểu trên kia của mình thì mình có 2 hướng cho việc tìm n:
* $n$ là tích 2 smooth number
* $n = p^k$ với $p$ cũng là smooth number
* Tuy nhiên chả hiểu sao mình phải mất 2 ngày mới có thể chọn được $n = 2010103^{50}$ (cái này cũng đi đọc nhiều blog mới , vì các giá trị $n$ trước đều bị fail.
* À còn lưu ý nốt 1 điều ở def $btc-check$ , ở đây msg của mình phải có 1 address bitcoin nên mình lấy 1 address ngẫu nhiên là ```1P5ZEDWTKTFGxQjZphgWPQUpe554WKDfHQ``` ở [đây](https://bitinfocharts.com/bitcoin/address/1P5ZEDWTKTFGxQjZphgWPQUpe554WKDfHQ)
* Full script:

from pwn import *
import requests
import json
from Crypto.Util.number import *
from pkcs1 import emsa_pkcs1_v15
from sympy.ntheory.residue_ntheory import discrete_log
from sage.all import *

HOST = 'socket.cryptohack.org'
PORT = 13394

r = remote(HOST,PORT)
BIT_LENGTH = 768

def json_recv():
    line = r.readline()
    return json.loads(line.decode())

def json_send(hsh):
    request = json.dumps(hsh).encode()
    r.sendline(request)

print(r.readline())

requests = {"option":"get_signature"}
json_send(requests)
res = json_recv()
s = int(res['signature'],16)

n = 2010103**50
requests = {"option":"set_pubkey","pubkey":hex(n)}
json_send(requests)
res = json_recv()
suffix = res['suffix']

msg1 = "This is a test for a fake signature."+suffix
m1 = msg1
msg2 = "My name is Giang and I own CryptoHack.org"+suffix
m2 = msg2
msg3 = "Please send all my money to 1P5ZEDWTKTFGxQjZphgWPQUpe554WKDfHQ"+suffix
m3 = msg3

msg1 = bytes_to_long(emsa_pkcs1_v15.encode(msg1.encode(), BIT_LENGTH // 8))
msg2 = bytes_to_long(emsa_pkcs1_v15.encode(msg2.encode(), BIT_LENGTH // 8))
msg3 = bytes_to_long(emsa_pkcs1_v15.encode(msg3.encode(), BIT_LENGTH // 8))

s = Mod(s,n)
msg1 = Mod(msg1,n)
msg2 = Mod(msg2,n)
msg3 = Mod(msg3,n)

e1 = discrete_log(msg1,s)
e2 = discrete_log(msg2,s)
e3 = discrete_log(msg3,s)

share = []
requests = {"option":"claim","msg":m1,"e":hex(e1),"index":int(0)}
json_send(requests)
res = json_recv()
secret = bytes.fromhex(res['secret'])
share.append(secret)

requests = {"option":"claim","msg":m2,"e":hex(e2),"index":int(1)}
json_send(requests)
res = json_recv()
secret = bytes.fromhex(res['secret'])
share.append(secret)

requests = {"option":"claim","msg":m3,"e":hex(e3),"index":int(2)}
json_send(requests)
res = json_recv()
secret = bytes.fromhex(res['secret'])
share.append(secret)


flag = xor(xor(share[0],share[1]),share[2])
print(flag)

* **Flag:crypto{let's_decrypt_w4s_t0o_ez_do_1t_ag41n}**

# **Reference:**
* https://crypto.stanford.edu/~dabo/pubs/papers/RSA-survey.pdf

* https://drx.home.blog/2019/03/01/crypto-rsa/?fbclid=IwAR0mpPBx3GCLOxdDT6DzyggUB8y79b4HytPcivBK_4KFwR-6-OVBHMiPIZw

* https://bitsdeep.com/posts/attacking-rsa-for-fun-and-ctf-points-part-1/