---
# System prepended metadata

title: RSA và Các Kiểu Tấn Công RSA

---

<h1 style="text-align:center;font-family:Algerian">RSA</h1>

![image](https://hackmd.io/_uploads/HJ9PVlQ00.png)

**RSA**, được mô tả lần đầu tiên vào năm 1977, là hệ thống mật mã **khóa công khai** nổi tiếng nhất. Nó có hai trường hợp sử dụng chính:
- **Mã hóa khóa công khai**: cho phép người dùng (**Alice**) tạo ra *một cặp khóa công khai* và đưa cặp khóa công khai đó cho người khác để họ dùng nó mã hóa tin nhắn gửi cho Alice. Sau khi nhận được tin nhắn được mã hóa thì Alice có thể dùng *cặp khóa bí mật* của mình để giải mã tin nhắn.
- **Tạo chữ ký số**: cho phép Alice sử dụng khóa riêng của mình để “**ký**” một tin nhắn. Bất kỳ ai cũng có thể sử dụng khóa công khai của Alice để xác minh rằng chữ ký được tạo bằng khóa riêng của cô ấy và tin nhắn không bị giả mạo.

Nguyên lý hoạt động của **RSA** dựa trên số học Modulo. Theo quá trình sau:
1) ***Sinh khóa***:
    - Đầu tiên ta cần tạo hai số nguyên tố $p$ và $q$ khác nhau.

    - Tính $n$ và $\phi(n)$ theo công thức:
    <span style="font-size:1.2em">$$ n = p \times q $$</span>

    <span style="font-size:1.2em">$$\phi(n) = (p-1) \times (q-1)$$</span>
    - Tiếp theo ta chọn một số $e$ nào đó thỏa mãn hai điều kiện sau: $1 < e <\phi(n)$ và $gcd(e,\hspace{1mm}\phi(n)) = 1$. Tức $\phi(n)$ và $e$ là hai số **nguyên tố cùng nhau**. Số $e$ được sử dụng phổ biến là: $e =65537$.
    
    - Lúc này cặp **khóa công khai** của ta sẽ là: <span style="font-size:1.2em">$$(n,\hspace{1mm}e)$$</span>
    - Khóa công khai có vai trò làm tham số để người khác mã hóa tin nhắn mà họ cần gửi cho bạn. Khi nhận được tin nhắn đã mã hóa thì bạn sẽ dùng khóa bí mật để giải mã tin nhắn ra bản rõ.
    - Để có được khóa bí mật thì ta sẽ tính $d$. Nó được dùng để giải mã thông điệp được mã hóa bằng khóa công khai $(e)$.
    - $d$ được tình bằng nghịch đảo của $e$ trong Modulo $\phi(n)$. Nghịch đảo Modulo của  $e$ là một số $d$ sao cho $e \times d \equiv 1 \pmod{\phi(n)}$ hay:
 <span style="font-size:1.3em">$$d \equiv e^{-1} \pmod{\phi(n)}$$</span>
 
    - **Ví dụ:** Nếu ta chọn $e = 3$ trong Modulo $\phi(n) = 17$ thì giá trị $d$ sẽ là $6$ vì $3 \times 6 = 18$ mà $18 \mod 17 = 1$.
    - Lúc này ta sẽ có được cặp **khóa bí mật** là: 
        <span style="font-size:1.2em">$$(n,\hspace{1mm}d)$$</span>

2) ***Mã hóa và giải mã***:
    - Giả sử có người muốn gửi một tin nhắn bí mật cho bạn.
    
    - Đầu tiên họ sẽ phải chuyển văn bản gốc sang số để có thể tính toán, gọi là $m$. 
    - Tiếp theo họ dùng **cặp khóa công khai** của bạn là $(n, e)$ để mã hóa $m$ thành $c$ bằng công thức: <span style="font-size:1.3em">$$c \equiv m^{e} \pmod n$$</span>
    - Khi gửi cho chúng ta thì chúng ta sẽ dùng **cặp khóa bí mật** để giải Ciphertext ra Plaintext theo công thức $t \equiv c ^ d \pmod n$, chứng mình như sau:
    <span style="font-size:1.3em">$$t \equiv c ^ d \pmod n$$</span>

        <span style="font-size:1.3em">$$\Leftrightarrow t \equiv m^{e \times d} \pmod n$$</span>

        <span style="font-size:1.3em">$$\Leftrightarrow t \equiv m^{1 + k\times \phi(n)} \pmod n \hspace{5mm} (*)$$</span> 
        
        <span style="font-size:1.3em">$$\Leftrightarrow t \equiv m^{1} \times m^{k\times \phi(n)} \pmod n$$</span>
        
        <span style="font-size:1.3em">$$\Leftrightarrow t \equiv m^{1} \times (m^k)^{\phi(n)} \pmod n \hspace{5mm} (**)$$</span>
        
        <span style="font-size:1.3em">$$\Leftrightarrow t \equiv m^{1} \times 1 \pmod n$$</span>
        
    <span style="font-size:1.3em">$$\Leftrightarrow t =m$$</span>
    - **Chú thích:** Ở bước $(*)$ ta có $d \equiv e^{-1} \pmod {\phi(n)}$ nên $e\times d \equiv 1 \pmod {\phi(n)}$ suy ra $e\times d = 1+ k\times \phi(n)$.
    
    - Ở bước $(**)$ ta có $(m^k)^{\phi(n)} \equiv 1 \pmod n$ vì $a^{\phi(n)}  \equiv 1 \pmod n$ với mọi số nguyên $a$, theo [**định lý Euler**](https://vi.wikipedia.org/wiki/Định_lý_Euler).
    
    - Sau các bước biến đổi ta chuyển $t$ sang chữ để có thể đọc được Plaintext. Vậy là hoàn thành quá trình trao đổi tin nhắn bí mật bằng **RSA** rồi.

**Ví dụ** minh họa:
- Bạn là $A$, người gửi tin nhắn cho bạn là anh $B$. Anh $B$ biết được kết quả xổ số của giải đặc biệt là **549742** nên muốn gửi số trên một cách bí mật cho bạn và không muốn ai biết.

- Thế thì trước tiên bạn phải tính cặp khóa công khai $(N,e)$ ($B$ sẽ sử dụng nó để gửi tin nhắn) và cặp khóa bí mật để giải mã tin nhắn của $B$.
- Đầu tiên ta tìm hai số nguyên tố là: `p = 11966168819543524997`,`q = 9974297842387296499` và chọn một số $e$ phổ biến là `e = 65537`.
- Sau đó ta tính $N$ và $\phi(N)$ theo công thức $N = p \times q$ và $\phi(N) = (p-1) \times (q-1)$ thì được hai giá trị là  `N = 119354131838415124092902326483457085503` và `φ(N) = 119354131838415124070961859821526264008`.
- Khi này ta sẽ gửi cho $B$ cặp khóa công khai $(N,e)$. Anh sẽ dùng nó để mã hóa tin nhắn theo công thức sau:
$$c \equiv m^e \pmod N$$
- $B$ gửi cho ta giá trị của $c$ là `c = 19714759499267620469749571111089170291`, chúng ta sẽ tiến hành giải mã như sau:
- Ta tính $d$ từ  $\phi(N)$ có được ở trên theo công thức:
$$d \equiv e^{-1} \pmod{\phi(n)}$$
- Giá trị $d$ là `d = 69577866043405249174223688214007521193`. Có trong tay $c,d$ và $N$ thì chỉ cần áp dụng công thức sau là có được tin nhắn gốc:
$$m \equiv c^d \pmod N$$
- Tính toán $m$ bằng **python** như sau:
    ```python
    e = 65537
    N = 119354131838415124092902326483457085503
    c = 19714759499267620469749571111089170291
    d = 69577866043405249174223688214007521193

    m = pow(c,d,N)
    print(f"{m = }")
    #m = 549742
    ```
>**Mã hóa RSA** được coi là một trong những phương pháp mã hóa khóa công khai an toàn nhất hiện nay, tuy nhiên nó không hoàn toàn miễn nhiễm trước các loại tấn công khác nhau.  Sau đây mình sẽ giới thiệu về một vài kiểu tấn công RSA phổ biến, nó sẽ dựa vào lỗi sai của người mã hóa, tạo lỗ hổng cho hacker lợi dụng. Nếu bạn chưa hiểu rõ về RSA thì có thể đọc phần **Cryptohack RSA** trước khi đọc phần **RSA ATTACK** vì mình sẽ giải thích chi tiết hơn về RSA phần đó :face_with_hand_over_mouth:
# RSA ATTACK
## Factorizing the public key
<img style="display: block; margin: auto;" width="400" src="https://hackmd.io/_uploads/SkDwLl7AC.png"/>

- Đúng như tên của nó thì **Factorizing the public key** tức là kẻ tấn công sẽ cố gắng phân tích cặp khóa công khai của ta thành tích của các thừa số nguyên tố, ở đây là tích của $p$ và $q$. Sức mạnh của **RSA** phụ thuộc vào độ khó của việc phân tích thừa số nguyên tố của $n$. Nên nếu kẻ xấu phân tích $n$ thành $p \times q$ thì việc mã hóa sẽ không còn ý nghĩa nào nữa.
-  Nhưng tại sao phải phân tích $n$ thành $p \times q$ ? Bởi vì có $p$ và $q$ là có tất cả, ta có thể dễ dàng tính được $\phi(n)$ bằng công thức $\phi(n) = (p - 1) \times (q - 1)$. Mà có được $\phi(n)$ thì ta hoàn toàn tính được $d$ qua công thức $d \equiv e^{-1} \pmod{\phi(n)}$, mà khi có được $d$ thì chỉ cần thay vào công thức $t \equiv c ^ d \pmod n$ là có được văn bản gốc.

- Đây là cách tấn công đơn giản nhất nên nó chỉ có tác dụng với $n$ kích thước nhỏ mà thôi, với các $N$ từ **256 bit** trở xuống thì ta có thể factor rất nhanh nhưng khi gặp $n$ lớn như $2048$ bit thì **Factorizing the public key** hoàn toàn vô dụng.

> **Vậy thực hiện Factorizing the public key như thế nào?**
- Hàm `factorint()` của thư viện **SymPy**:
    ```python
    from sympy import factorint
    n = 600851475143 
    factors = factorint(n)
    print(factors)
    # {71: 1, 839: 1, 1471: 1, 6857: 1}
    ```

- Hàm `factor()` của thư viện **Sagemath:**
    ```python
    from sage.all import *
    n = 600851475143
    factors = factor(n)
    print(factors)
    #71 * 839 * 1471 * 6857
    ```

:::info
:bulb: Nếu n được tạo thành từ nhiều số nguyên tố nhỏ hơn thì việc factorize sẽ diễn ra nhanh hơn rất nhiều so với $n$ được tạo từ chỉ hai số nguyên tố!
:::

- **Ví dụ** một đoạn code sử dụng hai số nguyên tố $p$ và $q$ nhỏ khiến cho $n$ không đủ an toàn, rất dễ bị tấn công *Factorizing the public key*.
    ```python
    from Crypto.Util.number import bytes_to_long, getPrime
    flag = b'Flag{???????????????????????}'
    m = bytes_to_long(flag)

    p,q = getPrime(128),getPrime(128)
    N = p*q
    assert m < N 
    print(f"N = {N}")
    #N = 60757841907558221465987265233393482388582365507883396610293678730517461812261

    e = 0x10001 #65537

    c = pow(m, e, N)

    print(f"ciphertext = {c}")
    #ciphertext = 15657874744941535788473801795744796562429674242622141710837810244754213789508
    ```
> Hãy thử sử dụng các hàm factorize mà mình nhắc ở trên factor thử $N$, xem nó lâu hay nhanh.
## Common modulus
### As an external attacker
- Giả sử đang có $3$ người đang liên lạc với nhau là *Alice*, *Bob* và *Canna*. Bạn biết rằng họ đang sử dụng **RSA** để liên lạc với nhau. Họ thống nhất với nhau rằng sẽ sử dụng chung một Modulo $n$ và mỗi người sẽ có một cặp khóa công khai riêng biệt là $(n, e_{i})$ và cặp khóa bí mật $(n, d_{i})$.

- Một hôm, *Alice* gửi một tin nhắn bí mật là $M$ cho hai người là *Bob* và *Canna*. Bạn đã can thiệp và lấy được $C_{b}$ và $C_{c}$ . Chúng sẽ khác nhau vì được mã hóa từ cặp khóa công khai của *Bob* và *Canna* từ công thức $C_{b} \equiv M ^{e_{b}} \pmod n$ và $C_{c} \equiv M ^ {e_{c}} \pmod n$. Chúng có điểm chung là đều được mã hóa từ văn bản gốc là $M$.
> **Bây giờ có trong tay $(n, e_b)$, $(n, e_c)$, $C_b$ và $C_c$ , bạn sẽ làm gì để tìm lại được $M$ ?**
- Đó chính là sử dụng tình chất của thuật toán **Euclid mở rộng (EGCD)**:
    - Đầu tiên ta tính $gcd(e_b, e_c)$, thường thì nó sẽ bằng **1**.
    
    - Như đã học ở phần **General** thì ta biết rằng tồn tại hai số $u$ và $v$ sao cho: <span style="font-size:1.2em">$$u \times e_b + v \times e_c =gcd(e_b, e_c) = 1$$</span>
    - Nên ta sẽ dùng thuật toán **Euclid mở rộng** để tìm $u$ và $v$. Khi có được $u$ và $v$ thì ta thực hiện các bước tiếp theo.
    - Ta biết $C_b = M ^ {e_b}$, ta có $C_b^{u}$ như sau:
     <span style="font-size:1.2em">$$C_b ^{\hspace{2mm}u} = (M ^ {e_b}) ^ u = M ^ {e_b \times u}$$</span>

    - Tương tự thì ta có: <span style="font-size:1.2em">$C_c^{v} =(M ^ {e_c}) ^ v = M ^ {e_c \times v}$</span>
    - Bây giờ ta lấy cả $C_b ^ {\hspace{2mm}u}$ và $C_c ^ {\hspace{2mm}v}$ nhân lại với nhau thì được:
 <span style="font-size:1.2em">$$C_b ^ {\hspace{2mm}u} \times C_c ^ {\hspace{2mm}v} = M ^ {e_b \times u + e_c \times v} = M ^ 1 = M$$</span>
    - Vậy là nhờ hai cặp số $u$ và $v$ của thuật toán Euclid mở rộng mà ta tìm được $M$ rồi.
>**Ta sẽ tìm cặp (u,v) như thế nào?**
- Sử dụng hàm `gcdext(a,b)` của thư viện **gmpy2**, nó sẽ trả về $3$ giá trị là ước chung lớn nhất của $(a,b)$ và giá trị $u,v$ của thuật toán Euclid mở rộng:
    ```python
    from gmpy2 import gcdext
    a = 190
    b = 103
    g, u, v = gcdext(a, b)
    print(f"{g = }")
    print(f"{u = }")
    print(f"{v = }")
    #g = mpz(1)
    #u = mpz(45)
    #v = mpz(-83)
    ```
- **Ví dụ** về cách tấn công trên:
    ```python
    from Crypto.Util.number import *
    flag = b'KCSC{??????????????????????}'

    # Parameters
    m = bytes_to_long(flag)
    p = getPrime(512)
    q = getPrime(512) 
    n = p*q
    e1 , e2 = getPrime(15) , getPrime(15)

    # Encrypt 
    c1 , c2 = pow(m,e1,n) , pow(m,e2,n)

    # Print
    print(f'{e1 = }')
    print(f'{e2 = }')
    print(f'{c1 = }')
    print(f'{c2 = }')
    print(f'{n = }')

    """
    e1 = 21341
    e2 = 25261
    c1 = 43946260278933165267431660993044179256450733940962448204621518943475853900082006280519072025814200897790997592340463936456190958275666594052429995580298318496180813719454334563715414909165832843522756119935976461092478885641955852178168496150011655624379719912171071289603245412892961948366155515278642890726
    c2 = 128310176397306858891446325231403610621098642187330349239489878341148171560057825931212023839177308332325958639449594866005405570172437515529356365161126570201717589561767400076906280689289461272183010707070634476880143832792975654032711035308135704921921241852756875248875673992949337763386726353743428471285
    n = 136973822933716552336015210410086061910624054358619578509115117334628335462050100007125608207863413129800784125730025310219736602623178611290649570777043217574184550605465181131198300470624226421519634791007102521649222963071618444042047066059200007171516431004284842846905028782392942642458999153116596453733 
    """
    ```
> Đúng như lý thuyết ta được học thì ở ví dụ trên một tin nhắn $m$ được mã hóa với hai số $e$ khác nhau nhau nhưng lại sử dụng chung Modulo $n$, nếu chung $e$ nhưng khác Modulo $n$ thì sẽ là kiểu tấn công khác mà ta sẽ học sau này :smile: 
- **Solve**
    ```python
    from Crypto.Util.number import long_to_bytes
    from gmpy2 import gcdext

    e1 = 21341
    e2 = 25261
    c1 = 43946260278933165267431660993044179256450733940962448204621518943475853900082006280519072025814200897790997592340463936456190958275666594052429995580298318496180813719454334563715414909165832843522756119935976461092478885641955852178168496150011655624379719912171071289603245412892961948366155515278642890726
    c2 = 128310176397306858891446325231403610621098642187330349239489878341148171560057825931212023839177308332325958639449594866005405570172437515529356365161126570201717589561767400076906280689289461272183010707070634476880143832792975654032711035308135704921921241852756875248875673992949337763386726353743428471285
    n = 136973822933716552336015210410086061910624054358619578509115117334628335462050100007125608207863413129800784125730025310219736602623178611290649570777043217574184550605465181131198300470624226421519634791007102521649222963071618444042047066059200007171516431004284842846905028782392942642458999153116596453733 

    g, u, v = gcdext(e1, e2)
    a = long_to_bytes((pow(c1, u, n) * pow(c2, v, n)) % n)
    print(a.decode())
    ```
:::spoiler Flag
**KCSC{3x73rn4l_4774ck_1n_r54}**
:::
### As an internal attacker
- Ở cách tấn công Common Modulus as an external attacker phần trước thì bạn là người bên ngoài, can thiệp vào để lấy cặp khóa công khai và các văn bản mã hóa của họ rồi sử dụng công thức toán học để giải mã ra Plaintext.

- Còn ở trường hợp này thì bạn sẽ là người **bên trong tổ chức**. Bạn và người bạn muốn tấn công có hai bộ khóa như sau $(n, e_1),(n, d_1)$ và $(n, e_2),(n, d_2)$. Vì cùng một tổ chức nên bạn và người đó sẽ có chung Modulo $n$. Bây giờ bạn phải tìm cách để từ bộ khóa của bạn mà suy ra được khóa bí mật $d$ của người bạn muốn tấn công. 
:::info
:bulb: Khi mà có được $d$ của người bạn muốn tấn công thì bất kỳ tin nhắn bí mật nào người khác gửi cho nạn nhân đều bị ta đọc được!
:::
- Để tìm được cặp khóa bí mật của nạn nhân thì ta bắt đầu bằng công thức này: $$d \equiv e ^ {-1} \pmod{\phi(n)}$$ 

    $$\Leftrightarrow e \times d \equiv 1 \pmod{\phi(n)}$$
- Biến đổi phương trình Modulo thành: $$e \times d - 1 = k \times \phi(n)$$ 

$$\Leftrightarrow k = \frac{e \times d  - 1} {\phi(n)}$$
- Ta biết rằng $n > \phi(n)$ nên: $$k_1 = \frac{e \times d - 1} {\phi(n)} > k_2 = \frac{e \times d - 1} {n}$$
- Vậy cách tấn công của ta sẽ là tính $k_2$ đầu tiên, sau đó tăng $k_2$ dần dần lên đến khi nào nó bằng $k_1$ thì dừng. Sở dĩ có thể làm như vậy vì giá trị của $\phi(n)$ khá gần với $n$ nên quá trình trên hoàn toàn có thể thực hiện được.
> **Khi có được $k_1$ rồi thì thay vào công thức $\phi(n)=$<span style="font-size:1.3em">$\frac{(e \times d - 1)}{k_1}$</span> là có được $\phi(n)$. Rồi tình $d \equiv e ^ {-1} \pmod{\phi(n)}$**.
- **Ví dụ** về kiểu tấn công trên:
    ```python
    from Crypto.Util.number import getPrime   
    p,q = getPrime(512), getPrime(512)

    N = p * q
    print(f"{N = }")

    phi = (p-1) * (q-1)

    e1 = 65537
    e2 = 25261
    print(f"{e1 = }")

    d1 = pow(e1, -1, N)
    d2 = pow(e2, -1, N)
    print(f"{d1 = }")

    #N = 117704067672883037376030830145700215357572435982701916566499889223000013519955331766548499616330205185281466326045375998482067680554871351096186175802407426623567339183089956168585674798584299942705999002628197040366578193734017048991401354035799191823625940444165646453369894762305964576694418965387598209207
    #e1 = 65537
    #d1 = 90403160815756604198542622735461892369787541962941295333801340066358372835809871977676507571106355313888763431158277709684504307008407530536607219512488826563985009767307262061155202811565059766483805572368172577687292368582563775852284641603155288152250413326785204996823580920021255671338179548068268969569
    ```
- Dù $N$ có số bit rất lớn (~$1024$) nhưng ta vẫn có thể tính được $\phi(n)$ từ lý thuyết mà ta đã học ở trên:
- **Solve**
    ```python
    N = 142112763922984882085217347048981250371723851319858048390352732637197297667408541541772373233253561976579006868188000153550812150368096943291281858387824563027425299379790142196062402785322235713848340509229988718954567745152782539743939378507197839047017522977706756942961398468982396951743989887951034999529
    e1 = 65537
    d1 = 16456257769069873051020254920956386607122881847908856512113567724852988266139179726879633496607432165650824467440968203691000708136525744276325404325880046520517121580072743475073890698961051723948228575072804437007281606084570039735061964134628139837463051129557602246671865556572736171426600840130924586286

    k = (e1 * d1 - 1) // N

    while True:
        phi = (e1 * d1 - 1) // k #nếu k sai thì phi sẽ sai 
        if k * phi == (e1 * d1 - 1): #phi sai thì cái này không đúng
            print(f"{k = }")
            print(f"{phi = }")
            break
        else:
            k = k + 1
    ```
:::spoiler output
**k =** 7589
**phi =**  142112763922984882085217347048981250371723851319858048390352732637197297667408541541772373233253561976579006868188000153550812150368096943291281858387824563027425299379790142196062402785322235713848340509229988718954567745152782539743939378507197839047017522977706756942961398468982396951743989887951034999529
:::
## Decipher oracle
- Thỉnh thoảng ta sẽ gặp một dạng bài đặc biệt yêu cầu ta gửi cho nó bất kỳ Ciphertext nào và nó sẽ giải mã thành Plaintext cho chúng ta, có lẽ ngoại trừ một vài văn bản đặc biệt như $Flag$ thì nó sẽ không trả lại. Những dạng bài như vậy sẽ được gọi là **Oracles** bởi vì nó cho ta thêm những thông tin và điều kiện đặc biệt mà ta phải thỏa mãn để có được $Flag$.

- Ví dụ có một Challenge yêu cầu ta phải gửi cho nó một Ciphertext để cho nó giải mã, nếu Plaintext chứa thông tin hay ký tự gì đó nằm trong $Flag$ thì nó sẽ không đưa $Flag$. Ta phải tìm cách qua mặt được cái chương trình này.
- Quay lại vấn đề chính thì cách tấn công này sẽ làm giả  Ciphertext để qua mắt ai đó hoặc chương trình nào đó rồi làm một vài thao tác để lấy lại Plaintext.
- **Ví dụ:** Bạn muốn gửi một tin nhắn $M$ cho $A$ là người bạn thích, nhưng để được gửi qua cho $A$ thì phải có sự đồng ý của $B$, mà $B$ thì rất khó. Bạn biết chắc chắn tin nhắn $M$ của mình sẽ không được $B$ chấp nhận nên giờ bạn phải biến đổi $M$ thành $M'$ là một tin nhắn vô nghĩa để cho $B$ không thể đọc được rồi gửi cho $A$. Sau đó $A$ sẽ biến đổi $M'$ lại ban đầu để có thể đọc được.

    - Đầu tiên ta mã hóa văn bản gốc theo khóa công khai của $B$ là: $$c \equiv M ^ e \pmod n$$ 
    - Sau đó ta nhân $c$ với một một thành phần khác là: $$r ^ e\hspace{1mm}mod\hspace{1mm}n$$
    - Lúc này ta được: $$M' \equiv [c \times (r ^ e)] \pmod n$$
    - Khi đưa cho $B$ giải mã ra thì $B$ sẽ dùng khóa bí mật để giải: $$(M') ^ d = c ^ d \times r ^ {e\times d} = M ^ {e\times d} \times r ^ 1 = M \times r$$
    - $B$ sẽ không đọc ra được văn bản $M$ vì bây giờ nó đã bị nhân với $r$.
    > **Vậy là qua mắt được $B$ rồi.**
    - Giờ để $A$ lấy được văn bản gốc thì $A$ chỉ đơn giản là lấy: $$\frac{M'}{r}$$

## Small public exponent
- Nhiều trường hợp chọn số $N$ **rất lớn** để tặng độ khó cho bài toán nhưng lại chọn số $e$ **nhỏ** để tính toán nhanh, đây là một lỗ hổng rất dễ bị khai thác nếu như tin nhắm $M$ cũng có chiều dài không đủ lớn.
- Khi ta có $N$ rất lớn nhưng số $e$ lại quá bé thì $M ^ e$ vẫn có khả năng bé hơn $N$. Vì $N > M^e$ nên: $$C \equiv M ^ e \pmod N = M ^ e$$
- Để lấy được $M$ thì ta lấy căn bậc $e$ của $C$ là xong: <span style="font-size:1.2em">$$M = C ^ {1 \over e} = \sqrt[e]{C}$$</span>

- Nếu $M^e$ lớn hơn $N$ một **tí**  thì ta không thể tính căn bậc $e$ trực tiếp như trên được, nhưng vẫn có thể tìm ngược lại $M$ như sau:
$$C \equiv M^e \pmod N$$ 

$$\Leftrightarrow M^e = C + k \times N$$

$$\Rightarrow M = \sqrt[e]{C+k \times N}$$
- Sau đó ta **Brute force** $k$ đến khi nào có thể căn ra được thì dừng. Nhưng chỉ khi $k$ nhỏ thôi nhé, nếu $k$ quá lớn thì ta sẽ không dùng kiểu tấn công này mà phải chuyển qua **CopperSmith's attack**.
## Hastad’s Broadcast Attack
- Kiếu tấn công này dựa trên **Small public exponent** như cách tấn công trước nhưng lần này thì tin nhắn dài hơn nên ta không thể lấy căn bậc $e$ được. Tuy nhiên thì  Ciphertext lại được gửi đi cho nhiều người khác với `chung một e` hoặc là `nhiều người` cùng gửi cho mình một tin nhắn có `nội dung giống nhau`, sử dụng cùng một $e$.

- Giả sử  tin nhắn gốc là $m$, ciphertext là $C_i \equiv m^e \pmod {N_i}$. Ta sẽ có hệ  phương trình Modulo như sau:
    $$\begin{cases}
 m^e \equiv C_1 \pmod{N1}\\
 m^e \equiv C_2 \pmod{N2}\\
 m^e \equiv C_3 \pmod{N3}
\end{cases}$$

- Để giải hệ trên, ta sẽ sử dụng thuật toán [**Chinese Remainder Theorem**](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#N%E1%BB%99i_dung) (CRT).  Sau khi CRT, ta sẽ được:
$$M \equiv m^e \pmod N$$

> Với $N=N_1.N_2.N_3...$ và $M$ là kết quả của CRT.

- Mà $m^e < N$ nên ta có thể bỏ đi phép modulo và được kết quả là:
$$M = m^e$$

- Giờ chỉ cần lấy căn bậc e là có được $m$:
$$m = \sqrt[e]{M}$$ 



> **Chú ý:** Để thực hiện **Hastad’s Broadcast Attack** được thì điều kiện của ta là: $m^e < N$ Với $N = N_1.N_2.N_3...$
Lý do là vì nếu $m^e>N$ thì khi CRT ta sẽ được $m^e\mod N$ chứ không phải $m^e$.


- Thuật toán **CRT** như sau:
    ```python
    def crt(remainders, mod):
        prod = 1
        for m in mod:
            prod *= m
        result = 0
        for r, m in zip(remainders, mod):
            p = prod // m
            result += r * pow(p,-1,m) * p
        return result % prod

    # ví dụ:
    # x ≡ 2 (mod 3)
    # x ≡ 3 (mod 5)

    remainders = [2,3]
    mod = [3,5]
    print(crt(remainders, mod)) #8
    ```
 
- **Ví dụ:** Ta can thiệp vào quá trình gửi tin nhắn của **Alice** cho `ba người khác` và được các dữ kiện sau: 
    ```python
    e1 = 3
    e2 = 3
    e3 = 3

    n1 = 95118357989037539883272168746004652872958890562445814301889866663072352421703264985997800660075311645555799745426868343365321502734736006248007902409628540578635925559742217480797487130202747020211452620743021097565113059392504472785227154824117231077844444672393221838192941390309312484066647007469668558141
    n2 = 98364165919251246243846667323542318022804234833677924161175733253689581393607346667895298253718184273532268982060905629399628154981918712070241451494491161470827737146176316011843738943427121602324208773653180782732999422869439588198318422451697920640563880777385577064913983202033744281727004289781821019463
    n3 = 68827940939353189613090392226898155021742772897822438483545021944215812146809318686510375724064888705296373853398955093076663323001380047857809774866390083434272781362447147441422207967577323769812896038816586757242130224524828935043187315579523412439309138816335569845470021720847405857361000537204746060031
    
    c1 = 29761034965151746948583154246855630752401551589793866662796146501825511364511870879442792482205328878203476750784328917805150321688330126618076317923432240182204777193089972121555535042984602904376413754480617409134274932850579091275413039129451341011198046896779072941730866017432331180882048582718551624340
    c2 = 26575757665496281468873262002511990141987650882219069193576119000821801989732911809335086924697501168937529609141457290787349629531782897390894171038169226633036338928103704553192140799610614385425886914455098159700590690594163495045233435752690357744938221252575309153004333570992284559353930522688482768177
    c3 = 42643020076877516972504379723085990495997764766643946085707250330923029265713980832386537940197751233476036196499242775111274192849253123912586669588654667607954357952152668755110585250372185025218292259231525547687180497640458279523069500931043105950830420054050096964268507866705743700763108396929123035619
     ```
- Vì tin nhắn gốc là giống nhau với 3 ciphertext nên ta sẽ sử dụng thuật toán **CRT** để giải:
    ```python
    from gmpy2 import iroot
    from Crypto.Util.number import long_to_bytes

    def crt(remainders, mod):
        prod = 1
        for m in mod:
            prod *= m
        result = 0
        for r, m in zip(remainders, mod):
            p = prod // m
            result += r * pow(p,-1,m) * p
        return result % prod

    remainders = [c1,c2,c3]
    mod = [n1,n2,n3]

    print(long_to_bytes(iroot(crt(remainders, mod), 3)[0]).decode()) #nhớ tính căn bậc 3
    ```
- Các thư viện toán học cũng cài đặt sẵn thuật toán **CRT** như thư viện **sagemath** và **sympy**, ta chỉ cần import rồi dùng thôi:
    ```python!
    from sympy.ntheory.modular import crt 
    #truyền modulo trước rồi remainders sau: crt(mod, remainders)

    from sage.all import crt 
    #truyền remainders trước rồi modulo sau: crt(remainders, mod)
    ```

## Fermat’s attack
- **Fermat's Attack** là một kiểu tấn công nhắm vào  trường hợp đặc biệt của **RSA** khi Modulus $N$ được tạo từ hai số nguyên tố không cân đối (quá gần nhau về giá trị).

- Điều kiện để thực hiện Fermat's attack:
$$p-q < \sqrt[4]{N}$$
- Đầu tiên ta biến đổi $N$ thành:
$$N = p \times q = \left (\frac{q-p}{2} \right)^{2}-\left (\frac{p+q}{2}\right)^2 = x^2-y^2  \hspace{6mm} (*)$$
- Với $x = \frac{q-p}{2}$ và $y = \frac{p+q}{2}$, ta biển đổi $N$ thành $N = (x+y)\times (x-y)$. Như bạn thấy thì khi này $N$ là tích của hai số là $x+y$ vả $x-y$, điều đó có nghĩa là $p$ sẽ bằng $x+y$ và $q = x-y$, ta sẽ đi tìm $x$ và $y$ để có được $p$ và $q$.
- Vì $p$ và $q$ có giá trị gần nhau nên $\frac{p+q}{2} \approx \sqrt N$, mà $p = x+y$, $q = x-y$ nên ta có $\frac{p+q}{2} = \frac{2x}{2} = x \approx \sqrt N$, vậy là ta đã ước chừng được giá trị ban đầu của $x$ rồi, sau đó thực hiện thuật toán như sau:
    - Đặt $x = \left \lceil \sqrt{N} \right \rceil$.
    - Từ $(*)$ ta tính $y^2 = x^2 - N$ và kiểm tra xem $y^2$ có phải một số chính phương hay không, nếu không thì ta tiếp tục tăng $x$ lên đến khi nào kết quả là một số chính phương thì dừng.
    - Sau khi có $y^2$ là số chính phương, ta tính căn để có được $y$ sau đó áp dụng công thức tính $p$ và $q$ ở trên:
    $$p = x+y$$

        $$q = x-y$$
- **Ví dụ:** Cho bạn $N = 10403$ hãy áp dụng thuật toán Fermat để tìm lại $p$ và $q$ biết $p$ và $q$ gần nhau:
    - Tính $\sqrt N \approx 102$, đặt là $x$.
    - Tính $y^2 = x^2 -N = 102^2 - 10403 = 10404 - 10403 = 1$ là một số chính phương nên ta không tìm $y^2$ nữa.
    - $y = \sqrt{y^{2}} = \sqrt1 = 1$.
    - $p = x+y = 102 + 1 = 103$.
    - $q = 102 - 1 = 101$.
    - Vậy $N = 103 \times 101 = 10403$.
- **Ví dụ:** Bạn có được một Modulus $N$ mà biết rằng nó là tích của hai số nguyên tố gần nhau:
    ```python
    n = 163325259729739139586456854939342071588766536976661696628405612100543978684304953042431845499808366612030757037530278155957389217094639917994417350499882225626580260012564702898468467277918937337494297292631474713546289580689715170963879872522418640251986734692138838546500522994170062961577034037699354013013
    ```
- Ta thực hiện thuật toán **Fermat’s factorizing** trong python như sau:
    ```python
    from gmpy2 import iroot

    n = ...
    a = iroot(n, 2)[0]
    b = pow(a, 2) - n

    while b < 0 or not iroot(b, 2)[1]:  
        a += 1
        b = pow(a, 2) - n
    b = iroot(b, 2)[0]
    p = a + b
    q = a - b
    print(f"{p = }") 
    print(f"{q = }") 
    ```
:::spoiler **Values of p and q**
**p =** mpz(12779877140635552275193974526927174906313992988726945426212616053383820179306398832891367199026816638983953765799977121840616466620283861630627224899027521)
**q =** mpz(12779877140635552275193974526927174906313992988726945426212616053383820179306398832891367199026816638983953765799977121840616466620283861630627224899026453)
:::
## Wiener’s attack
- Đôi khi ta sẽ gặp một số tình huống mà mã hóa RSA sử dụng số $e$ quá lớn, quá mức cần thiết. Nhưng điều đó chưa chắc là tốt, khi $e$ quá lớn thì sẽ tạo lỗ hổng cho kiểu tấn công **Wiener**. Tham khảo nguồn [**này**](https://cryptohack.gitbook.io/cryptobook/untitled/low-private-component-attacks/wieners-attack) để hiểu rõ hơn.
$$d < \frac{1}{3} \times \sqrt[4]{N}$$

> **Vậy tấn công như thế nào khi ta biết số $e$ là quá lớn?**
- Ta sẽ sử dụng **thư viện owiener** để tấn công, nó sẽ giúp ta tìm ra được $d$ từ $e$ và $n$ cho trước:
    - Cài thư viện owiener:
    ```python
    curl -O https://raw.githubusercontent.com/orisano/owiener/master/owiener.py
    ```
    - Sau khi cài xong thì chỉ cần khai báo là có thể sử dụng được. Ta tìm $d$ bằng câu lệnh sau:
        ```python
        import owiener
        d = owiener.attack(e,N)
        ```
- **Ví dụ:** bạn có những dữ kiện sau: 
    ```python
    N = 23314261774711635287199613322625299631998299531668574856054445891367514103118788671741746880773471358355043843424178957765687991051382738221889741391209910265414558275853987805928032540504091325882973089325788388764059748141908558032906355962434381133814683631259503022678117195972953901341152390082323332013081727028250772610795079682074032005674396787209080870144904438012362544373403906582078249640767748443695976768936365312724837274503878342188073955100351982119862045062809973110618490322000848950789796929040191128376295484446101182115221654618310291664010793027421046736723687597493681537019384653365187810893
    e = 19530226410043970810725557003435543135763530881424210248055253789146116962119210614869432985570865118752985919383689598525891574886387777910656552352995376444381466131799115118821582068507614159079491660471660498703856657100219432169415694357051026653501587627161359216917068611699460388404704994020658035113867704564864520447628130219204036115956229378374533904177298511420691232986523029437427813718184752726121102827577815324799236044788791890210324092921530775467785171769947364981150722141109135873933436026419757925700203197178661307541794973688656649796675223608169318604829628635422095313615753614708538760163
    c = 8028121224227573051828850229994462997334629895742133475980102822209497303556216779775942543561944932524150303356432654518807957178569209410177254952777287867269725600174363472416920972657180694221524823357993311941711660626697551627760577426753521788921114199242994421027253907973286593309748059366733997153548521855813763130272553602724942731498310511847885977497728649159363241087645689831666350800348400155464399327635456578067757425624251823026377947503169196936361131843633441040763103641837689196421514573226485717472879713606424296498797414793405914833918934223936424519120394289446392279412227764722289357940
    ```
- Ta có thể thấy rằng số $e$ là rất lớn, gần như là lớn bằng $N$. Ta sẽ khai báo thư viện **owiener** để tấn công.
- **Solve**
    ```python
    import owiener
    from Crypto.Util.number import long_to_bytes
    N = 23314261774711635287199613322625299631998299531668574856054445891367514103118788671741746880773471358355043843424178957765687991051382738221889741391209910265414558275853987805928032540504091325882973089325788388764059748141908558032906355962434381133814683631259503022678117195972953901341152390082323332013081727028250772610795079682074032005674396787209080870144904438012362544373403906582078249640767748443695976768936365312724837274503878342188073955100351982119862045062809973110618490322000848950789796929040191128376295484446101182115221654618310291664010793027421046736723687597493681537019384653365187810893
    e = 19530226410043970810725557003435543135763530881424210248055253789146116962119210614869432985570865118752985919383689598525891574886387777910656552352995376444381466131799115118821582068507614159079491660471660498703856657100219432169415694357051026653501587627161359216917068611699460388404704994020658035113867704564864520447628130219204036115956229378374533904177298511420691232986523029437427813718184752726121102827577815324799236044788791890210324092921530775467785171769947364981150722141109135873933436026419757925700203197178661307541794973688656649796675223608169318604829628635422095313615753614708538760163
    c = 8028121224227573051828850229994462997334629895742133475980102822209497303556216779775942543561944932524150303356432654518807957178569209410177254952777287867269725600174363472416920972657180694221524823357993311941711660626697551627760577426753521788921114199242994421027253907973286593309748059366733997153548521855813763130272553602724942731498310511847885977497728649159363241087645689831666350800348400155464399327635456578067757425624251823026377947503169196936361131843633441040763103641837689196421514573226485717472879713606424296498797414793405914833918934223936424519120394289446392279412227764722289357940
    d = owiener.attack(e,N)
    m = pow(c,d,N)
    print(long_to_bytes(m).decode())
    ```
:::spoiler **Flag**
**crypto{s0m3th1ng5_c4n_b3_t00_b1g}**
:::
# Cryptohack RSA
![image](https://hackmd.io/_uploads/rkF0TZrJyl.png)

## STARTER
### RSA Starter 1
![image](https://hackmd.io/_uploads/HJq6XYvQR.png)
- **Mô tả**: Challenge này giới thiệu cho chúng ta về **modular exponentiation**.

- *Modular exponentiation* hay tên tiếng việt là *lũy thừa modulo* được sử dụng rộng rãi trong RSA và thường được viết như thế này: $2^{10}\mod 17$.
- Có thể hiếu lũy thừa modulo là lấy một số nào đó lũy thừa lên rồi sau đó chia lấy dư cho *Modulus* là được. Trong python thì ta sử dụng hàm `pow()` để tính lũy thừa modulo với các tham số là **pow(Base,Exponent,Modulus)**.
- Trong $RSA$ lũy thừa modulo cùng với phép phân tích thừa số nguyên tố đã tạo nên một chức năng mã hóa khó có thể làm ngược lại gọi là **"trapdoor function"**. Nó cho phép chúng ta mã hóa thông tin mà chỉ người có **key** chính xác mới có thể làm ngược lại để có thông tin gốc.
<img style="display: block; margin: auto;" width="400" src="https://hackmd.io/_uploads/S1ExLFDXR.png"/>

- Hướng dẫn giải challenge:
    - Challenge này yêu cầu ta tính $101 ^ {17}\hspace{1mm}\mod22663$.
    - Ta chỉ cần dùng hàm `pow()` như sau:
        ```python
        print(pow(101, 17, 22663))
        ```
:::spoiler Flag
**19906**
:::

### RSA Starter 2
![image](https://hackmd.io/_uploads/HkmvDFP7R.png)
- **Mô tả**: Challenge này giới thiệu cho ta về $N$ và $e$, cách tính và giá trị của chúng.

- Mã hóa RSA là *lũy thừa modulo* với mũ số là $e$ và modulus là $N$. Trong đó $N$ được tính bằng công thức: $N = p \times q$ với $p$ và $q$ là hai số nguyên tố ta chọn lúc đầu.
- Mũ số $e$ thường có giá trị là **0x10001** hay **65537**.
- Hướng dẫn giải challenge:
    - Đề yêu cầu ta mã hóa số $12$ bằng số mũ $e = 65537$ và hai số nguyên tố là $p = 17$ và $q = 23$.
    - Ta sẽ đi tính $N$ rồi sử dụng công thức: $$c \equiv m ^ e \pmod N$$
    - Đoạn code như sau:
        ```python
        p = 17
        q = 23
        N = p * q
        m = 12
        e = 65537
        print(pow(m, e, n))
        ```
:::spoiler Flag
**301**
:::

### RSA Starter 3
![image](https://hackmd.io/_uploads/HkE6YtDmA.png)
- **Độ khó** của mã hóa $RSA$ phụ thuộc vào việc **phân tích thừa số nguyên tố** của $N$. Nếu $p$ và $q$ bị tìm thấy thì hacker sẽ tính được **hàm φ(n)** rồi sau đó giải mã được Ciphertext.

- Hướng dẫn giải challenge:
    - Challenge yêu cầu ta tìm $\phi(n)$ của $N$.
    - Nhớ lại kiến thức cũ, để tính được $\phi(n)$ thì có rất nhiều cách, ở đây đề đã cho ta hai số nguyên tố thì $\phi(n)$ sẽ được tính bằng công thức: $$\phi(n) = (p - 1) \times (q - 1)$$
    - Đoạn code sẽ như sau:
        ```python
        p = 857504083339712752489993810777
        q = 1029224947942998075080348647219
        print((p-1)*(q-1))
        ```
:::spoiler Flag
**882564595536224140639625987657529300394956519977044270821168**
:::

### RSA Starter 4
![image](https://hackmd.io/_uploads/rk21hFD70.png)
- **Mô tả**: Challenge này giới thiệu cho ta về **khóa bí mật d**, cách tính và tầm quan trọng của nó.

- Khóa $d$ được sử dụng để giải mã tin nhẵn được mã hóa và nó cũng được dùng để **ký** một tin nhắn, được ứng dụng trong **Chữ Ký Số**.

:::info
:bulb: Khóa $d$ sẽ giúp ta đảo ngược lại quá trình mã hóa để có được văn bản gốc. Nên nếu bạn muốn bẻ khóa RSA mà không có khóa $d$ thì có lẽ cách nhanh nhất là thử phân tích thừa số nguyên tố của $N$.
:::
- khóa bí mật $d$ được tính bằng **nghịch đảo modulo** của $e$ trong modulo $\phi(n)$, công thức như sau:
$$d \times e \equiv 1\pmod{\phi(n)}$$

$$\Leftrightarrow d \equiv e^{-1}\pmod{\phi(n)}$$
- Để tính $d$ trong python thì ta sẽ dùng hàm `pow()`: **d = pow(e,-1, phi)**
- Hướng dẫn giải challenge:
    - Challenge cho ta các dữ kiện sau và yêu cầu ta tìm khóa bí mật $d$:
        ```python
        p = 857504083339712752489993810777
        q = 1029224947942998075080348647219
        e = 65537
        ```
    - Ta sẽ đi tính $\phi(n)$ rồi thay vào `d = pow(e,-1,phi)` là xong:
        ```python
        p = 857504083339712752489993810777
        q = 1029224947942998075080348647219
        e = 65537
        phi = (p-1)*(q-1)
        print(pow(e, -1, phi))
        ```
:::spoiler Flag
**121832886702415731577073962957377780195510499965398469843281**
:::

### RSA Starter 5
![image](https://hackmd.io/_uploads/rJ-qy5vX0.png)
- **Mô tả**: Challenge này cho ta $N$, $e$, $d$, $c$ và yêu cầu ta hãy giải mã $c$ ra $Flag$.
- Ta có các dữ kiện sau:
    ```python
    N = 882564595536224140639625987659416029426239230804614613279163
    e = 65537
    d = 121832886702415731577073962957377780195510499965398469843281
    c = 77578995801157823671636298847186723593814843845525223303932
    ```
- Hướng dẫn giải:
    - Để giải mã RSA thì ta sử dụng công thức sau: $$t \equiv c ^ d \pmod n$$
    - Đoạn code:
        ```python
        N = 882564595536224140639625987659416029426239230804614613279163
        e = 65537
        d = 121832886702415731577073962957377780195510499965398469843281
        c = 77578995801157823671636298847186723593814843845525223303932
        print(pow(c, d, N))
        ```
:::spoiler Flag
**13371337**
:::

### RSA Starter 6
![image](https://hackmd.io/_uploads/ByIsPqDmC.png)
- **Mô tả**: Challenge này hướng dẫn ta cách **"ký"** một văn bản.

- Tưởng tượng bạn cần gửi một tin nhắn $M$ cho ai đó, bạn sẽ mã hóa nó bằng công thức: $C \equiv M ^ e \pmod N$ với $N$ và $e$ là cặp **khóa công khai** của họ. Nhưng mã hóa như trên thì không đảm bảo an toàn được, có thể có thế lực nào đó can thiệp vào để sửa đổi tin nhắn gốc, vì vậy ta cần phải ký nó để đảm bảo rằng người nhận sau khi giải mã ra sẽ biết đó là do bạn gửi.
- Để ký tin nhắn này thì bạn sẽ làm như sau: Đầu tiên gửi một văn bản mã hóa bằng công thức như trên là: $C \equiv M ^ e \pmod N$ với $N$ và $e$ là **cặp khóa công khai** của người bạn gửi đến, sau đó bạn làm thêm một **phiên bản** nữa nhưng lần này sẽ mã hóa khác đi. Bạn sẽ dùng **hàm băm** để băm văn bản gốc thành $H(M)$ rồi mã hóa nó bằng công thức: $S \equiv H(M) ^ d  \pmod N$ với $N$ và $d$ là cặp **khóa bí mật** của bạn.
- Sau khi nhận được hai văn bản là $C$ và $S$, người nhận sẽ dùng **khóa bí mật** của họ để giải mã $C$ ra $M$. Sau đó họ sẽ dùng **khóa công khai** của bạn để giải mã $S$ ra $H(M)$, lúc này $H(M)$ là giá trị **băm** của $M$ nên không thể đọc được. Sau khi có được $M$ và $H(M)$, người đó sẽ đối chiếu bằng cách lấy **hàm băm**, băm $M$ ra rồi đối chiếu với $H(M)$, lúc này cả hai đều là giá trị băm, một văn bản chỉ có duy nhất một giá trị băm, nên nếu cả hai giống nhau tức là $M$ chưa bị thay đổi trong quá trình chuyển đi.
- Quay lại với challenge thì đề yêu cầu ta băm văn bản gốc là **crypto{Immut4ble_m3ssag1ng}** bằng **hàm băm SHA256** rồi ký nó với khóa bí mật của đề bài:

- Hướng dẫn giải:
    - Để dùng hàm băm **SHA256** thì ta khai báo như sau:
        ```python
        from hashlib import sha256
        ```
    - Sau đó ta băm văn bản gốc như sau:
        ```python
        from hashlib import sha256
        message = b"crypto{Immut4ble_m3ssag1ng}"
        hash = sha256(message).hexdigest()
        #giá trị băm sẽ là b'99b4c7bb814cc630c4199e4814ffed85a835f64ffc82aadaa6388d9df9aeb2cb'
        ```
    - Sau đó ta tiến hành ký thì hàm `pow()`:
        ```python
        from hashlib import sha256
        from Crypto.Util.number import*
        N = 15216583654836731327639981224133918855895948374072384050848479908982286890731769486609085918857664046075375253168955058743185664390273058074450390236774324903305663479046566232967297765731625328029814055635316002591227570271271445226094919864475407884459980489638001092788574811554149774028950310695112688723853763743238753349782508121985338746755237819373178699343135091783992299561827389745132880022259873387524273298850340648779897909381979714026837172003953221052431217940632552930880000919436507245150726543040714721553361063311954285289857582079880295199632757829525723874753306371990452491305564061051059885803
        d = 11175901210643014262548222473449533091378848269490518850474399681690547281665059317155831692300453197335735728459259392366823302405685389586883670043744683993709123180805154631088513521456979317628012721881537154107239389466063136007337120599915456659758559300673444689263854921332185562706707573660658164991098457874495054854491474065039621922972671588299315846306069845169959451250821044417886630346229021305410340100401530146135418806544340908355106582089082980533651095594192031411679866134256418292249592135441145384466261279428795408721990564658703903787956958168449841491667690491585550160457893350536334242689
        message = b'crypto{Immut4ble_m3ssag1ng}'
        hash = bytes_to_long(sha256(message).digest())
        c = pow(hash,d,N)
        print(c)
        ```
:::spoiler Flag
**13480738404590090803339831649238454376183189744970683129909766078877706583282422686710545217275797376709672358894231550335007974983458408620258478729775647818876610072903021235573923300070103666940534047644900475773318682585772698155617451477448441198150710420818995347235921111812068656782998168064960965451719491072569057636701190429760047193261886092862024118487826452766513533860734724124228305158914225250488399673645732882077575252662461860972889771112594906884441454355959482925283992539925713424132009768721389828848907099772040836383856524605008942907083490383109757406940540866978237471686296661685839083475**
:::

## PRIMES PART 1
### Factoring
![image](https://hackmd.io/_uploads/HJNC7jPQR.png)
- **Mô tả**: Challenge này cho ta biết được tầm quan trọng của **độ dài của một số nguyên tố**. 
- RSA sử dụng cặp số nguyên tố phải dài ít nhất $1024$ bit. Sau khi nhân chúng lại thì ta có $N \approx 2048$ bit. Mã hóa RSA với $N$ bằng $2048$ bit thì được gọi là **RSA-2048**. $N$ mà càng lớn thì càng khó để phân tích thành thừa số nguyên tố, tạo nên độ khó cao cho RSA. Vì vậy ta phải chọn $p$ và $q$ chính xác để đảm bảo an toàn cho RSA.

- Challenge này yêu cầu ta phân tích một số dài $150$ bit thành tích của hai số nguyên tố, submit số nhỏ hơn để có điểm.
>**510143758735509025530880200653196460532653147** 
- Ta sẽ sử dụng hàm `factorint()` của thư viện **sympy** hoặc sử dụng hàm `factor()` của thư viện **Sagemath**, sử dụng như sau:
    ```python
    from sympy import factorint
    n = 510143758735509025530880200653196460532653147
    print(factorint(n))
    ```
- Số nhỏ hơn sẽ là $Flag$ của challenge này.
:::spoiler Flag
{mpz(19704762736204164635843): 1, 25889363174021185185929: 1}
**19704762736204164635843**
:::
### Inferius Prime
![image](https://hackmd.io/_uploads/HJNGDswmC.png)
- **Mô tả**: Challenge này cho ta làm quen với cách phân tích $N$ thành thừa số nguyên tố.
- Đề cho ta dữ kiện từ file `output.txt` như sau:
    ```python!
    n = 742449129124467073921545687640895127535705902454369756401331
    e = 3
    ct = 39207274348578481322317340648475596807303160111338236677373
    ```
- Ta có thể thấy rằng $n$ khá là nhỏ, hoàn toàn có thể tách nó ra được. Sử dụng hàm `factor()` của thư viện **Sagemath**:
    ```python
    from sage.all import factor
    n = 742449129124467073921545687640895127535705902454369756401331
    print(factor(n))
    #752708788837165590355094155871 * 986369682585281993933185289261
    ```
- Giờ ta đã có $p$ và $q$, giờ chỉ cần tính $d$ nữa là bài toán sẽ kết thúc:
    ```python!
    from Crypto.Util.number import*
    n = 742449129124467073921545687640895127535705902454369756401331
    p = 752708788837165590355094155871
    q = 986369682585281993933185289261
    e = 3
    ct = 39207274348578481322317340648475596807303160111338236677373

    phi = (p-1)*(q-1)
    d = pow(e, -1, phi)

    Flag = long_to_bytes(pow(ct, d, n)).decode()
    print(Flag)
    ```
:::spoiler Flag
**crypto{N33d_b1g_pR1m35}**
:::
### Monoprime
![image](https://hackmd.io/_uploads/rksOtjvX0.png)
- **Mô tả**: Challenge này cho ta biết rằng tại sao phải sử dụng **hai** số nguyên tố để tạo thành $N$ chứ không phải **một**.

- Giả sử ta chỉ sử dụng một số nguyên tố để tạo thành $N$, vậy giờ ta phải tính $\phi(n)$ như thế nào?
- Ôn lại bài cũ thì nếu $p$ là số nguyên tố thì $\phi(n)$ sẽ bằng $p-1$. Nếu ta dùng hai số nguyên tố là $p$ và $q$ thì lúc này $\phi(n)$ sẽ là $(p-1)\times(q-1)$. Vì vậy nếu ta chỉ dùng một số nguyên tố thì việc bảo mật sẽ hoàn toàn vô nghĩa vì bây giờ $\phi(n)$ sẽ bằng $N-1$.

- Quay lại đề bài thì bài cho ta những dữ kiện sau:
    ```python
    n = 171731371218065444125482536302245915415603318380280392385291836472299752747934607246477508507827284075763910264995326010251268493630501989810855418416643352631102434317900028697993224868629935657273062472544675693365930943308086634291936846505861203914449338007760990051788980485462592823446469606824421932591                                                               
    e = 65537
    ct = 161367550346730604451454756189028938964941280347662098798775466019463375610700074840105776873791605070092554650190486030367121011578171525759600774739890458414593857709994072516290998135846956596662071379067305011746842247628316996977338024343628757374524136260758515864509435302781735938531030576289086798942  
    ```
    - Đề nói rằng chỉ lấy một số nguyên tố nên suy ra $N$ cũng chính là số nguyên tố đó, bây giờ để tính $\phi(n)$ thì ta chỉ cần lấy $N-1$ là xong, có $\phi(n)$ rồi tính $d$ là kết thúc bài toán.
    - Đoạn code như sau:
        ```python
        from Crypto.Util.number import*

        n = 171731371218065444125482536302245915415603318380280392385291836472299752747934607246477508507827284075763910264995326010251268493630501989810855418416643352631102434317900028697993224868629935657273062472544675693365930943308086634291936846505861203914449338007760990051788980485462592823446469606824421932591                                                                  
        e = 65537
        ct = 161367550346730604451454756189028938964941280347662098798775466019463375610700074840105776873791605070092554650190486030367121011578171525759600774739890458414593857709994072516290998135846956596662071379067305011746842247628316996977338024343628757374524136260758515864509435302781735938531030576289086798942  

        phi = n - 1
        d = pow(e, -1, phi)

        Flag = long_to_bytes(pow(ct, d, n)).decode()
        print(Flag)
        ```
:::spoiler Flag
**crypto{0n3_pr1m3_41n7_pr1m3_l0l}**
:::
### Square Eyes
![image](https://hackmd.io/_uploads/r1vm2jw7A.png)
- **Mô tả**: Challenge này sáng tạo hơn challenge trước vì nó dùng hai số nguyên tố để tạo ra $N$ nhưng số nguyên tố nó dùng lại **giống nhau**. Tức là:
$$N=p^2$$

- Vì $N = p ^ 2$ nên công thức tính $\phi(n)$ bây giờ sẽ là: $$\phi(n) = N \times (1 - \frac{1}{p}) = p ^ 2 \times (\frac{p - 1}{p}) = p \times (p - 1)$$
- Giờ ta chỉ cần tính $\sqrt{N}$ là có được $p$
    - Dùng hàm `iroot()` của thư viện **gmpy2** để tìm căn bậc hai của số lớn:
        ```python!
        import gmpy2
        p = gmpy2.iroot(n, 2)[0]
        ```
- Đoạn code như sau:
    ```python
    import gmpy2
    from Crypto.Util.number import*
    n = 535860808044009550029177135708168016201451343147313565371014459027743491739422885443084705720731409713775527993719682583669164873806842043288439828071789970694759080842162253955259590552283047728782812946845160334801782088068154453021936721710269050985805054692096738777321796153384024897615594493453068138341203673749514094546000253631902991617197847584519694152122765406982133526594928685232381934742152195861380221224370858128736975959176861651044370378539093990198336298572944512738570839396588590096813217791191895941380464803377602779240663133834952329316862399581950590588006371221334128215409197603236942597674756728212232134056562716399155080108881105952768189193728827484667349378091100068224404684701674782399200373192433062767622841264055426035349769018117299620554803902490432339600566432246795818167460916180647394169157647245603555692735630862148715428791242764799469896924753470539857080767170052783918273180304835318388177089674231640910337743789750979216202573226794240332797892868276309400253925932223895530714169648116569013581643192341931800785254715083294526325980247219218364118877864892068185905587410977152737936310734712276956663192182487672474651103240004173381041237906849437490609652395748868434296753449
    e = 65537
    ct = 222502885974182429500948389840563415291534726891354573907329512556439632810921927905220486727807436668035929302442754225952786602492250448020341217733646472982286222338860566076161977786095675944552232391481278782019346283900959677167026636830252067048759720251671811058647569724495547940966885025629807079171218371644528053562232396674283745310132242492367274184667845174514466834132589971388067076980563188513333661165819462428837210575342101036356974189393390097403614434491507672459254969638032776897417674577487775755539964915035731988499983726435005007850876000232292458554577437739427313453671492956668188219600633325930981748162455965093222648173134777571527681591366164711307355510889316052064146089646772869610726671696699221157985834325663661400034831442431209123478778078255846830522226390964119818784903330200488705212765569163495571851459355520398928214206285080883954881888668509262455490889283862560453598662919522224935145694435885396500780651530829377030371611921181207362217397805303962112100190783763061909945889717878397740711340114311597934724670601992737526668932871436226135393872881664511222789565256059138002651403875484920711316522536260604255269532161594824301047729082877262812899724246757871448545439896

    p = gmpy2.iroot(n, 2)[0]

    phi = p * (p-1)
    d = pow(e, -1, phi)

    print(long_to_bytes(pow(ct, d, n)).decode())
    ```
:::spoiler Flag
**crypto{squar3_r00t_i5_f4st3r_th4n_f4ct0r1ng!}**
:::
### Manyprime
![image](https://hackmd.io/_uploads/S1Ho72vmC.png)
- **Mô tả**: Challenge này sử dụng **32 số nguyên tố** để tạo nên $N$, theo mình thì challenge này làm tay thì lâu thôi chứ không khó.
- Đề cho ta những dữ kiện sau:
    ```python
    n = 580642391898843192929563856870897799650883152718761762932292482252152591279871421569162037190419036435041797739880389529593674485555792234900969402019055601781662044515999210032698275981631376651117318677368742867687180140048715627160641771118040372573575479330830092989800730105573700557717146251860588802509310534792310748898504394966263819959963273509119791037525504422606634640173277598774814099540555569257179715908642917355365791447508751401889724095964924513196281345665480688029639999472649549163147599540142367575413885729653166517595719991872223011969856259344396899748662101941230745601719730556631637
    e = 65537
    ct = 320721490534624434149993723527322977960556510750628354856260732098109692581338409999983376131354918370047625150454728718467998870322344980985635149656977787964380651868131740312053755501594999166365821315043312308622388016666802478485476059625888033017198083472976011719998333985531756978678758897472845358167730221506573817798467100023754709109274265835201757369829744113233607359526441007577850111228850004361838028842815813724076511058179239339760639518034583306154826603816927757236549096339501503316601078891287408682099750164720032975016814187899399273719181407940397071512493967454225665490162619270814464
    ```
- Sử dụng hàm `factor()` của thư viện **Sagemath** để phân tích thừa số nguyên tố của $n$ trên:
    ```python!
    9282105380008121879 * 9303850685953812323 * 9389357739583927789 * 10336650220878499841 * 10638241655447339831 * 11282698189561966721 * 11328768673634243077 * 11403460639036243901 * 11473665579512371723 * 11492065299277279799 * 11530534813954192171 * 11665347949879312361 * 12132158321859677597 * 12834461276877415051 * 12955403765595949597 * 12973972336777979701 * 13099895578757581201 * 13572286589428162097 * 14100640260554622013 * 14178869592193599187 * 14278240802299816541 * 14523070016044624039 * 14963354250199553339 * 15364597561881860737 * 15669758663523555763 * 15824122791679574573 * 15998365463074268941 * 16656402470578844539 * 16898740504023346457 * 17138336856793050757 * 17174065872156629921 * 17281246625998849649
    ```
- Giờ thì ta sẽ cho hết các số nguyên tố này vào một **list** rồi dùng vòng lặp để tính thôi.
- Công thức tính $\phi(n)$ sẽ là $$\phi(n) = (p_1-1)\times(p_2-1)\times...\times(p_n-1)$$
- Đoạn code như sau:
    ```python
    from Crypto.Util.number import*
    N = 580642391898843192929563856870897799650883152718761762932292482252152591279871421569162037190419036435041797739880389529593674485555792234900969402019055601781662044515999210032698275981631376651117318677368742867687180140048715627160641771118040372573575479330830092989800730105573700557717146251860588802509310534792310748898504394966263819959963273509119791037525504422606634640173277598774814099540555569257179715908642917355365791447508751401889724095964924513196281345665480688029639999472649549163147599540142367575413885729653166517595719991872223011969856259344396899748662101941230745601719730556631637
    list_primes = [9282105380008121879, 9303850685953812323, 9389357739583927789, 10336650220878499841, 10638241655447339831, 11282698189561966721, 11328768673634243077, 11403460639036243901, 11473665579512371723, 11492065299277279799, 11530534813954192171, 11665347949879312361, 12132158321859677597, 12834461276877415051, 12955403765595949597, 12973972336777979701, 13099895578757581201, 13572286589428162097, 14100640260554622013, 14178869592193599187, 14278240802299816541, 14523070016044624039, 14963354250199553339, 15364597561881860737, 15669758663523555763, 15824122791679574573, 15998365463074268941, 16656402470578844539, 16898740504023346457, 17138336856793050757, 17174065872156629921, 17281246625998849649]
    e = 65537
    ciphertext = 320721490534624434149993723527322977960556510750628354856260732098109692581338409999983376131354918370047625150454728718467998870322344980985635149656977787964380651868131740312053755501594999166365821315043312308622388016666802478485476059625888033017198083472976011719998333985531756978678758897472845358167730221506573817798467100023754709109274265835201757369829744113233607359526441007577850111228850004361838028842815813724076511058179239339760639518034583306154826603816927757236549096339501503316601078891287408682099750164720032975016814187899399273719181407940397071512493967454225665490162619270814464
    phi = 1
    for i in list_primes:
        phi = (i-1)*phi
    d = pow(e, -1, phi)
    print(long_to_bytes(pow(ciphertext, d, N)).decode()) 
    ```
:::spoiler Flag
**crypto{700_m4ny_5m4ll_f4c70r5}**
:::

## PUBLIC EXPONENT
### Salty
![image](https://hackmd.io/_uploads/SyCpw3PmA.png)
- **Mô tả**: Challenge này cho lũy thừa $e$ siêu nhỏ và bằng $1$. Có lẽ... $e = 1$ thì sẽ tính nhanh hơn chăng?

- `output.txt` cho ta các dữ liệu:
    ```python
    n = 110581795715958566206600392161360212579669637391437097703685154237017351570464767725324182051199901920318211290404777259728923614917211291562555864753005179326101890427669819834642007924406862482343614488768256951616086287044725034412802176312273081322195866046098595306261781788276570920467840172004530873767                                                                  
    e = 1
    ct = 44981230718212183604274785925793145442655465025264554046028251311164494127485
    ```
- Ta biết rằng $N$ rất lớn, văn bản gốc dù có chuyển thành số thì cũng không lớn hơn được, đằng này $e = 1$ tức là văn bản gốc đem mũ $1$ thì nó vẫn như cũ.
- Suy ra $ct$ chính là văn bản gốc, ta chỉ cần chuyển nó sang chữ là được.
- Đoạn code như sau:
    ```python!
    from Crypto.Util.number import*
    ct = 44981230718212183604274785925793145442655465025264554046028251311164494127485
    print(long_to_bytes(ct).decode())
    ```
:::spoiler Flag
**crypto{saltstack_fell_for_this!}**
:::
### Modulus Inutilis
![image](https://hackmd.io/_uploads/B1AP5nv7R.png)
- **Mô tả**: Challenge này nhìn thì có vẻ *hoản hảo* nhưng nó mắc phải một lỗi đó là cho số $e$ quá bé, ta sẽ sử dụng cách tấn công **Small public exponent** để khai thác lỗ hổng này.

- Như đã đề cập ở phần **Small public exponent** thì số $N$ là **rất lớn**, mà ở đây $e$ lại **quá bé** nên dù có lấy văn bản gốc mũ lên $e$ lần thì nó vẫn bé hơn $N$. Bây giờ ta chỉ cần lấy $\sqrt[3]{ct}$ là xong.
- Sử dụng hàm `iroot()` từ thư viện **gmpy2**:
    ```python
    import gmpy2
    from Crypto.Util.number import*
    n = 17258212916191948536348548470938004244269544560039009244721959293554822498047075403658429865201816363311805874117705688359853941515579440852166618074161313773416434156467811969628473425365608002907061241714688204565170146117869742910273064909154666642642308154422770994836108669814632309362483307560217924183202838588431342622551598499747369771295105890359290073146330677383341121242366368309126850094371525078749496850520075015636716490087482193603562501577348571256210991732071282478547626856068209192987351212490642903450263288650415552403935705444809043563866466823492258216747445926536608548665086042098252335883
    e = 3
    d = 1
    ct = 243251053617903760309941844835411292373350655973075480264001352919865180151222189820473358411037759381328642957324889519192337152355302808400638052620580409813222660643570085177957
    pt = pow(ct, d, n)
    print(long_to_bytes(gmpy2.iroot(ct, e)[0]).decode())
    ```
:::spoiler Flag
**crypto{N33d_m04R_p4dd1ng}**
:::
### Everything is Big
![image](https://hackmd.io/_uploads/BJCWepPQ0.png)
- **Mô tả**: Challenge trước thì cho số $e$ siêu nhỏ còn challenge này cho số $e$ bự ngang với $N$. Điều này tạo điều kiện cho kiểu **tấn công wiener** mà mình đã đề cập ở phần **RSA Attack**.

- Ta có những dữ kiện sau:
    ```python
    N = 0xb8af3d3afb893a602de4afe2a29d7615075d1e570f8bad8ebbe9b5b9076594cf06b6e7b30905b6420e950043380ea746f0a14dae34469aa723e946e484a58bcd92d1039105871ffd63ffe64534b7d7f8d84b4a569723f7a833e6daf5e182d658655f739a4e37bd9f4a44aff6ca0255cda5313c3048f56eed5b21dc8d88bf5a8f8379eac83d8523e484fa6ae8dbcb239e65d3777829a6903d779cd2498b255fcf275e5f49471f35992435ee7cade98c8e82a8beb5ce1749349caa16759afc4e799edb12d299374d748a9e3c82e1cc983cdf9daec0a2739dadcc0982c1e7e492139cbff18c5d44529407edfd8e75743d2f51ce2b58573fea6fbd4fe25154b9964d
    e = 0x9ab58dbc8049b574c361573955f08ea69f97ecf37400f9626d8f5ac55ca087165ce5e1f459ef6fa5f158cc8e75cb400a7473e89dd38922ead221b33bc33d6d716fb0e4e127b0fc18a197daf856a7062b49fba7a86e3a138956af04f481b7a7d481994aeebc2672e500f3f6d8c581268c2cfad4845158f79c2ef28f242f4fa8f6e573b8723a752d96169c9d885ada59cdeb6dbe932de86a019a7e8fc8aeb07748cfb272bd36d94fe83351252187c2e0bc58bb7a0a0af154b63397e6c68af4314601e29b07caed301b6831cf34caa579eb42a8c8bf69898d04b495174b5d7de0f20cf2b8fc55ed35c6ad157d3e7009f16d6b61786ee40583850e67af13e9d25be3
    c = 0x3f984ff5244f1836ed69361f29905ca1ae6b3dcf249133c398d7762f5e277919174694293989144c9d25e940d2f66058b2289c75d1b8d0729f9a7c4564404a5fd4313675f85f31b47156068878e236c5635156b0fa21e24346c2041ae42423078577a1413f41375a4d49296ab17910ae214b45155c4570f95ca874ccae9fa80433a1ab453cbb28d780c2f1f4dc7071c93aff3924d76c5b4068a0371dff82531313f281a8acadaa2bd5078d3ddcefcb981f37ff9b8b14c7d9bf1accffe7857160982a2c7d9ee01d3e82265eec9c7401ecc7f02581fd0d912684f42d1b71df87a1ca51515aab4e58fab4da96e154ea6cdfb573a71d81b2ea4a080a1066e1bc3474
    ```
- Import thư viện **owiener** rồi tiến hành tìm $d$ thôi:
    ```python
    import owiener
    from Crypto.Util.number import long_to_bytes
    N = 
    e = 
    c = 
    d = owiener.attack(e,N)
    m = pow(c,d,N)
    print(long_to_bytes(m).decode())
    ```
:::spoiler Flag
**crypto{s0m3th1ng5_c4n_b3_t00_b1g}**
:::
### Crossed Wires
![image](https://hackmd.io/_uploads/r1-dXTvmA.png)
- **Mô tả:** bạn có $5$ thằng bạn, bạn kêu chúng nó mã hóa tin nhắn mật rồi gửi cho bạn. Nhưng thay vì dùng cặp khóa công khai của bạn để mã hóa thì chúng nó chỉ dùng $N$ của bạn, còn $e$ thì mỗi thằng một $e$ khác nhau. Kết quả là bạn nhận được cái tin nhắn mã hóa từ $5$ cái $e$ của chúng nó. Làm sao để lấy lại văn bản gốc?
<span style="font-size:1.6em; text-align:center">$$c \equiv m ^{e_1\times e_2\times e_3\times e_4\times e_5} \pmod N$$</span>

- `output.txt` cho ta dữ kiện sau:
    ```python
    list_e = [106979, 108533, 69557, 97117, 103231] #5 cái e của lũ bạn
    n = 21711308225346315542706844618441565741046498277716979943478360598053144971379956916575370343448988601905854572029635846626259487297950305231661109855854947494209135205589258643517961521594924368498672064293208230802441077390193682958095111922082677813175804775628884377724377647428385841831277059274172982280545237765559969228707506857561215268491024097063920337721783673060530181637161577401589126558556182546896783307370517275046522704047385786111489447064794210010802761708615907245523492585896286374996088089317826162798278528296206977900274431829829206103227171839270887476436899494428371323874689055690729986771
    d = 2734411677251148030723138005716109733838866545375527602018255159319631026653190783670493107936401603981429171880504360560494771017246468702902647370954220312452541342858747590576273775107870450853533717116684326976263006435733382045807971890762018747729574021057430331778033982359184838159747331236538501849965329264774927607570410347019418407451937875684373454982306923178403161216817237890962651214718831954215200637651103907209347900857824722653217179548148145687181377220544864521808230122730967452981435355334932104265488075777638608041325256776275200067541533022527964743478554948792578057708522350812154888097
    ct = 20304610279578186738172766224224793119885071262464464448863461184092225736054747976985179673905441502689126216282897704508745403799054734121583968853999791604281615154100736259131453424385364324630229671185343778172807262640709301838274824603101692485662726226902121105591137437331463201881264245562214012160875177167442010952439360623396658974413900469093836794752270399520074596329058725874834082188697377597949405779039139194196065364426213208345461407030771089787529200057105746584493554722790592530472869581310117300343461207750821737840042745530876391793484035024644475535353227851321505537398888106855012746117
    e = 0x10001
    ```
- Để triệt tiêu được $5$ cái $e$ kia thì ta phải tìm được $5$ cái $d$ tương ứng, nhưng để có được $d$ thì ta phải có $\phi(N)$, nhưng Challenge không cho $\phi(N)$.
- May mắn là ta có được cặp khóa bí mật là $(N,\hspace{1mm}d)$, hoàn toàn có thể suy ngược lại $\phi(n)$ bằng cách tấn công **Modulus common as internal attacker** đã đề cập ở trên:
    ```python!
    k = (e1 * d1 - 1) // N

    while True:
        phi = (e1 * d1 - 1) // k
        if k * phi == (e1 * d1 - 1):
            print(f"{k = }")
            print(f"{phi = }")
            break
        else:
            k = k + 1
    ```
    - Ta sẽ tính được $k$ và $\phi(N)$ như sau: 
    ```python
    k = 8254    
    phi = 21711308225346315542706844618441565741046498277716979943478360598053144971379956916575370343448988601905854572029635846626259487297950305231661109855854947494209135205589258643517961521594924368498672064293208230802441077390193682958095111922082677813175804775628884377724377647428385841831277059274172982280249307490374900729021320924716697863966277266625488626020771604596923670543560857724741855180400786259195735908618899535592322919617065525626834782656528352786625383923291590279348919015437292702452668873586799771898145386750557481851748649545280807708561842706253359025121644739401403945728547286791397492272
    ```
    - Sau khi có $\phi(n)$ thì ta hoàn toàn có thể tính được $5$ cái $d$ của lũ bạn rồi cho vào `pow(ct, d, N)` là giải mã được. Thực hiện như sau:
    ```python
    from Crypto.Util.number import*
    list_e = [106979, 108533, 69557, 97117, 103231]
    n = #bị giới hạn ký tự nên các bạn thêm vào giúp mình nha 😔
    d = 
    c = 
    e = 0x10001
    phi = 
    for i in list_e:
        new_d = inverse(i, phi)
        c = pow(c,new_d,n)
    print(long_to_bytes(c).decode())
    ```
:::spoiler Flag
**crypto{3ncrypt_y0ur_s3cr3t_w1th_y0ur_fr1end5_publ1c_k3y}**
:::
### Everything is Still Big
![image](https://hackmd.io/_uploads/rkBgiP6Qkx.png)
- **Mô tả:** Challenge này kế thừa ý tưởng từ challenge **Everything is Big** khi nó sử dụng số $e$ rất lớn, nhưng lần này thì Challenge không cho ta sử dụng **wiener attack** vì nó đặt ra điều kiện:
$$(3 \times d)^4 < N$$

- Ngoài **wiener attack** có thể tấn công khi số $d$ đủ nhỏ thì chúng ta cũng có một kiểu tấn công khác cũng có thể dụng khi $d$  nhỏ là **Boneh-Durfee attack**, áp dụng khi:
$$d < N^{0.292}$$

> Vì $d < N^{0.292}$ nên Boneh-Durfee mạnh hơn wiener
- Boneh-Durfee kết hợp **LLL** và **Coppersmith** nên thuật toán của nó khá phức tạp, mình chưa thể giải thích ở đây nhưng các bạn có thể sử dụng tool tấn công **Boneh-Durfee** có sẵn [**này**](https://github.com/mimoo/RSA-and-LLL-attacks/blob/master/boneh_durfee.sage) để thực hiện Challenge trên.

- Thay đổi $N$ và $e$ của hàm `example()` thành $N$ và $e$ mình cần tấn công:
![image](https://hackmd.io/_uploads/H1QITwpmke.png)
- Nếu thành công, thuật toán sẽ trả về khóa bí mật $d$ cho ta, khi có $d$ thì bài toán kết thúc:
![image](https://hackmd.io/_uploads/H1lWkxupQkl.png)


:::spoiler Flag
**crypto{bon3h5_4tt4ck_i5_sr0ng3r_th4n_w13n3r5}**
:::
### Endless Emails
![image](https://hackmd.io/_uploads/rkoHV1XRA.png)
- **Mô tả:** Một email giống nhau được ông **Johan** gửi cho vài người bằng cách sử dụng chung chung số $e = 3$ với Modulus $N$ của mỗi người là khác nhau. Vì sử dụng số $e$ khá nhỏ và được gửi đi cho nhiều người nên ta sẽ sử dụng kiểu tấn công **RSA Broadcast Attack**.

- Challenge này có $7$ Modulus $N$ và $7$ Ciphertext, như gợi ý từ Challenge thì sẽ có một vài email của ông là giống nhau, ta sẽ thử dùng **CRT** cho tổ hợp $3$ ciphertext trong $7$ ciphertext trên, nếu chọn trúng $3$ ciphertext được mã hóa từ chung tin nhắn thì ta sẽ giải ra được $Flag$
- Ta sẽ ghép cặp từng cặp $C$ và $N$ lại bằng hàm `zip()` để tạo thành một phương trình Modulo. Sau đó tạo tổ hợp $3$ thương trình từ $7$ phương trình mà đề cho tạo thành một hệ phương trình Modulo. Sau đó dùng **CRT** để giải hệ đó.
- Hàm `combinations()` của thư viện **itertools**  được sử dụng để tạo ra tất cả các tổ hợp (**Combination**) có độ dài xác định từ một danh sách hoặc chuỗi đầu vào mà không quan tâm đến thứ tự của các phần tử:
    ```python
    import itertools

    data = [1, 2, 3]
    comb = itertools.combinations(data, 2)
    for c in comb:
        print(c)
    #(1, 2)
    #(1, 3)
    #(2, 3)
    ```
- Thực hiện như sau:
    ```python!
    from gmpy2 import iroot
    from Crypto.Util.number import*
    from itertools import combinations
    from sympy.ntheory.modular import crt

    e = 3
    #sắp xếp c và n theo đúng thứ tự nhé, vì giới hạn ký tự của hackmd là 100000 nên mình phải lược bỏ các c và n 😔
    lst_n = [...]
    lst_c = [...]

    equation = [(x, y) for x, y in zip(lst_c, lst_n)]
    three_equations = list(combinations(equation, 3))

    for i in three_equations:
        c = [x[0] for x in i]
        n = [x[1] for x in i]

        flag = crt(n, c)[0]
        flag = long_to_bytes(iroot(flag,e)[0])

        if b"crypto{" in flag:
            print(flag.decode())
    ```
:::spoiler Flag
yes

---

Johan Hastad
Professor in Computer Science in the Theoretical Computer Science
Group at the School of Computer Science and Communication at KTH Royal Institute of Technology in Stockholm, Sweden.

**crypto{1f_y0u_d0nt_p4d_y0u_4r3_Vuln3rabl3}**
:::
## PRIMES PART 2
### Infinite Descent
![image](https://hackmd.io/_uploads/HJ8RL0D70.png)
- **Mô tả:** Challenge này cho hai số nguyên tố $p$ và $q$ khá gần nhau, mục đích là để ta sử dụng **Fermat's attack**.

- Ta sẽ sử dụng thuật toán Fermat's factorizing đã đề cập ở trên để tìm $p$ và $q$:
    ```python
    from gmpy2 import iroot

    n = int(input())
    a = iroot(n, 2)[0]
    b = pow(a, 2) - n

    while b < 0 or not iroot(b, 2)[1]:  
        a += 1
        b = pow(a, 2) - n
    b = iroot(b, 2)[0]
    p = a + b
    q = a - b
    print(f"{p = }") 
    print(f"{q = }") 
    ```
- Sau khi có được $p$ và $q$ thì giải như bình thường.
:::spoiler Flag
**crypto{f3rm47_w45_4_g3n1u5}**
:::
### Marin's Secrets
![image](https://hackmd.io/_uploads/SyhyjRvQ0.png)
- **Mô tả:** Challenge này khá là sáng tạo khi nó sử dụng **số nguyên tố Mersenne** để tạo thành $N$ mà không dùng hàm tạo số nguyên tố ngẫu nhiên như các challenge trước.

- Nói sơ qua thì **số nguyên tố Mersenne** là số nguyên tố có dạng $2^n − 1$. Đây là một số nguyên tố hiếm bởi vì tính đến nay chỉ có $52$ số nguyên tố Mersenne $2^p − 1$ được tìm thấy với số mũ $p$ dưới đây:
    ```python!
    2, 3, 5, 7, 13, 17, 19, 31, 61, 89, 107, 127, 521, 607, 1279, 2203, 2281, 3217, 4253, 4423, 9689, 9941, 11213, 19937, 21701, 23209, 44497, 86243, 110503, 132049, 216091, 756839, 859433, 1257787, 1398269, 2976221, 3021377, 6972593, 13466917, 20996011, 24036583, 25964951, 30402457, 32582657, 37156667, 42643801, 43112609, 57885161, 74207281, 77232917, 82589933, 136279841
    ```
> **Fun fact:** Số Mersenne thứ 52: $2^{136279841}-1$  là số nguyên tố lớn nhất mà con người từng tìm thấy

- Quay trở lại với Challenge, nhìn vào hàm `get_prime()`, ta thấy rằng $p,q$ được tính bằng cách lấy $2$ mũ **secret** lần với secret là một giá trị nào đó trong $52$ giá trị trên, chắc chắn là **secret** không thể quá lớn vì $N$ chỉ dài $4484$ bit.

- Ta sẽ tìm được hai giá trị secret thỏa mãn là $2203$ và $2281$ vì tổng của chúng đúng bằng $4484$ bit.

- Có được **secret** thì bài toán kết thúc:
    ```python
    from Crypto.Util.number import long_to_bytes, inverse

    n =  
    e = 65537
    c = 

    secrets = [2203, 2281]
    p = 2 ** secrets[0] - 1
    q = 2** secrets[1] - 1
    d = pow(e, -1, (p-1)*(q-1))

    print(long_to_bytes(pow(c,d,n)).decode())
    ```
:::spoiler Flag
****crypto{Th3se_Pr1m3s_4r3_t00_r4r3}****
:::
### Fast Primes
![image](https://hackmd.io/_uploads/B16r8F6myx.png)
- Đúng như cái tên thì Challenge này tạo Modulus $N$ bằng cái nhân hai **fast primes** cho nhau. Fast primes là số nguyên tố tạo ra nhằm đẩy nhanh quá trình tạo lượng lớn số nguyên tố ngẫu nhiên, giảm tiêu thụ bộ nhớ. Cấu trúc của nó như sau:
$$p = k \times M + (65537^a \mod M)$$

    - Với $M$ là tích của $n$ số nguyên tố đầu tiên, $a$ và $k$ được tạo ngẫu nhiên.
- Tuy nhiên thì hiện nay nó không còn được sử dụng nhiều nữa, vì cấu trúc của nó dễ đoán và không còn phù hợp với tiêu chuẩn mã hóa hiện nay nữa.
- Vì cấu trúc dễ đoán của nó nên nó tạo ra một lỗ hổng bảo mật gọi là [**ROCA**](https://en.wikipedia.org/wiki/ROCA_vulnerability) viết tắt cho  “Return of Coppersmith’s Attack” được phát hiện vào năm 2017.
- Các bạn có thể tham khảo đường [**link**](https://bitsdeep.com/posts/analysis-of-the-roca-vulnerability/) này để rõ hơn về lỗ hổng **ROCA**.
- Vấn đề này cũng khá phức tạp vì nó liên quan đến rất nhiều khái niệm như **Logarit rời rạc**, **Coppersmith-Howgrave**, **LLL**, mình cũng chưa nắm rõ hết nên không thể giải thích ngay ở đây được, nhưng các bạn có thể sử dụng tool tấn công **ROCA** sẵn ở [**đây**](https://github.com/FlorianPicca/ROCA/blob/master/sage_functions.py), tải hai file `roca_attack.py` và `sage_functions.py` sau đó chạy file `roca_attack.py` để tiến hành tấn công.

    ![image](https://hackmd.io/_uploads/r18uicp71g.png)
- Sau khi có $p,q$ thì ta tính được $d$ và dùng nó làm **key** cho **PKCS1_OAEP**, thực hiện như sau:
    ```python
    from Crypto.Cipher import PKCS1_OAEP
    from Crypto.PublicKey import RSA

    p = 
    q = 
    n = p*q
    c = bytes.fromhex(open("fast_primes.txt", "r").read())
    e = 0x10001
    d = pow(e,-1,(p-1)*(q-1))

    key = RSA.construct((n,e,d))
    cipher = PKCS1_OAEP.new(key)
    print(cipher.decrypt(c).decode())
    ```
:::spoiler Flag
**crypto{p00R_3570n14}**
:::
### Ron was Wrong, Whit is Right
![image](https://hackmd.io/_uploads/B11TkfpWkg.png)
- **Mô tả:** Challenge cung cấp $50$ cặp khóa công khai $(e,n)$ cùng với $50$ tin nhắn được mã hóa thông qua thuật toán **PKCS1_OAEP**. Biết rằng **Flag** được mã hóa bằng cặp khóa thứ $21$ thông qua file `excerpt.py`. Nhưng có vẻ là cặp khóa công khai thứ $21$ có vấn đề chăng?

- Vì **Flag** được mã hóa bằng **PKCS1_OAEP**, nên cách duy nhất để giải mã chính là tìm được $key$ của nó, mà key được tính từ $d$  → ta phải factor được $n$ ra $p\times q$ để có $d$.
- Nhưng mà $n$ dài đến $8192$ bit!! Đừng nghĩ đến chuyện factor nó bằng các tool thông thường (phải mất vài trăm triệu năm) :smile: Chắc chắn có cách nào đó để ta lợi dụng được $49$ cái $n$ còn lại.
- Sau một hồi thử khá nhiều cách thì mình quyết định đi tìm ước chung lớn nhất **(GCD)** của $n_{21}$ với các $n$ còn lại và nó đã thành công:
    ```python
    from Crypto.Util.number import *
    from itertools import *
    from gmpy2 import *
    from Crypto.PublicKey import RSA

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

    n_all = []
    for i in range(1,51):
        with open(f'{i}.pem') as f:
            key = RSA.importKey(f.read())
            n_all.append(key.n)

    for n in n_all:
        if gcd(n21, n) != 1:
            print(f"n thứ", n_all.index(n)+1)

    # n thứ 21
    # n thứ 34
    ```
    - Ta thấy $n_{34}$ có ước chung lớn nhất với $n_{21}$. Mà $n = p \times q$ nên khi ta biết được ước chung lớn nhất của $n_{21}$ và $n_{34}$ thì ta đã biết được $p$ hoặc $q$ của cả hai rồi, để tính giá trị còn lại thì ta lấy $n$ chia cho **GCD** là xong.
- Đoạn code hoàn chỉnh:
    ```python!
    from Crypto.Util.number import *
    from Crypto.Cipher import PKCS1_OAEP
    from itertools import *
    from gmpy2 import *
    from Crypto.PublicKey import RSA

    with open('21.pem') as f:
        key = RSA.importKey(f.read())
        n21 = key.n
    ct21 = bytes.fromhex(open('21.ciphertext', 'rb').read().decode())
    e = 65537

    n_all = []
    for i in range(1,51):
        with open(f'{i}.pem') as f:
            key = RSA.importKey(f.read())
            n_all.append(key.n)

    n_all.pop(20)

    for n in n_all:
        if gcd(n21, n) != 1:
            p = int(gcd(n21, n))
            q = n21 // p
            d = pow(65537,-1,(p-1)*(q-1))
            key = RSA.construct((n21,e,d))
            cipher = PKCS1_OAEP.new(key)
            print(cipher.decrypt(ct21).decode())
    ```
:::spoiler Flag
**crypto{3ucl1d_w0uld_b3_pr0ud} If you haven't already, check out https://eprint.iacr.org/2012/064.pdf**
:::
> **Fun fact:** biết được $p$ của cặp khóa thứ $34$ thì ta cũng có thể giải mã ciphertext thứ $34$ được, nó là: **"BA4DPD6O5DNL3CHIYRIW3Q48XJ2XMS8I02BYX7WNUJNGF1QLU66DT8RAU8B"**.

## PADDING
### Bespoke Padding
![image](https://hackmd.io/_uploads/rkGstkvG1l.png)
- **nc socket.cryptohack.org 13386**
- **source code:**
    ```python!
    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"}
    # nc socket.cryptohack.org 13386
    ```
- **Mô tả:** Challenge này **pad** Flag bằng công thức $m = (a \times Flag + b)$ rồi đem mã hóa RSA như bình thường. Khi ta yêu cầu `get_flag` thì server sẽ trả về cho ta $(a,b)$, $C$ và $N$, mỗi lần yêu cầu sẽ là cặp $(a,b)$ và $C$ khác nhau. Ta sẽ làm sao để từ những dữ kiện trên mà tìm ra **Flag**.

- Sau một hồi tìm tòi thì mình rút ra được kết luận nếu $Flag$ mà được biểu diễn dưới dạng đa thức **(polynomial)** thì nó sẽ dễ bị tấn công **Franklin Reiter's Attack on related messages** nếu tồn tại hai đa thức mà chúng có nghiệm chung là **Flag**.
- Challenge cho phép ta gửi yêu cầu bao nhiêu tùy thích nên ta sẽ gửi yêu cầu `get_flag` **hai** lần để có hai đa thức $g(x)$ như sau:
$$f_1(x) = (a_1 \times Flag + b_1)^e - C_1$$

    $$f_2(x) = (a_2 \times Flag + b_2)^e - C_2$$

- Sau đó ta dùng **GCD** để tìm nghiệm chung của hai đa thức, GCD sẽ được biểu diễn bằng đa thức $(x-F)$. Có thể hiểu như sau:
    - **Ví dụ:** $g_1(x) = (x-F) \times (x-m_1)$ và $g_2(x) = (x-F) \times (x-m_2)$ thì **GCD** của cả hai sẽ là $(x-F)$ chứ không phải $F$.
- Tương tự như ví dụ trên thì nghiệm chung của $f_1(x)$ và $f_2(x)$ cũng được biểu diễn dưới dạng $(x-F)$, sau đó ta sử dụng phương thức `.coefficients()` để liệt kê các hệ số của $(x-F)$, nó sẽ là $[-F, 1]$ (sắp xếp theo bậc tăng dần).
- Vậy để lấy được $F$ thì ta thêm dấu âm **""-""** vào hệ số đầu tiên:
    ```python!
    F = -gcd(f1, f2).coefficients()[0]
    ```
:::info
Chú ý là ta phải làm việc trên Zmod(N)
:::
- **Script:**
    ```python!
    from sage.all import *
    from Crypto.Util.number import  *
    # hai đa thức phải chung N nhé
    N = 
    e = 11

    a = 
    b = 
    c = 
    d = 

    (c1, c2) = ( , )
    R = PolynomialRing(Zmod(N), 'x')
    x = R.gen()

    f1 = (a * x + b)**e - c1
    f2 = (c * x + d)**e - c2

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

    result = -gcd(f1, f2).coefficients()[0]

    print(long_to_bytes(int(result)))
    ```
:::spoiler Flag
**crypto{linear_padding_isnt_padding}**
:::
### Null or Never
![image](https://hackmd.io/_uploads/BkeqFkPMkl.png)
- **source code:**
    ```python!
    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}")
    ```
- **Mô tả:** Challenge thực hiện **pad** Flag bằng cách thêm rất nhiều bytes **NULL** **(\x00)** vào phía sau Flag đến khi độ dài đủ $100$. Nhưng mà $e = 3$ khá khiêm tốn nên nó tạo ra lỗ hổng vô cùng nghiêm trọng.

- Việc thêm một bytes **\x00** vào phía sau $Flag$ tương đương với dịch một giá trị nhị phân đi $8$ bit sang bên trái vậy:
    - **Ví dụ:** Chữ `a` có giá trị nhị phân là `01100001 (97)`, khi thêm `\x00` và sau `a` thì ta có giá trị nhị phân mới là `01100001 00000000 (24832)`, điều đó khiến cho giá trị của `a` tăng lên đến $2^8$ lần.

:::info 
:bulb: Mỗi lần thêm $k$ bytes **\x00** vào phía sau thì điều đó tương ứng với dịch bytes sang bên trái $k$ lần, khiến giá trị của nó tăng lên $2^{8 \times k}$ lần.
:::
- Quay trở lại với Challenge, vì được dịch $100 - len(Flag) = 57$ bytes nên ta có thể biểu diễn lại $Flag$ như sau:
$$C \equiv (Flag \times 2^{8 \times 57})^e \pmod N$$

    $$C \equiv Flag^e \times (2^{8 \times 57})^e \pmod N$$

    $$Flag^e \equiv C \times (2^{8 \times 57})^{-e} \pmod N$$
- Để có được $Flag$ thì ta đi tính căn bậc $e$ của $C \times (2^{8 \times 57})^{-e}$ là kết thúc!
:::info
:bulb: Vì $Flag^e > N$ nên không thể trực tiếp căn ra được mà cần phải biến đổi lại một tí nhé!
:::
$$Flag^e \equiv const \pmod N$$

$$Flag^e = k \times N + const$$

$$Flag = \sqrt[e]{k \times N + const}$$

- **Script:**
    ```python!
    from Crypto.Util.number import *
    from gmpy2 import *
    n = 
    e = 3
    c = 
    const = (c * pow(2**(8*57), -e, n)) % n

    for k in range(100):
        if iroot(const + k*n , 3)[1]:
            print(f"{k = }")
            print(long_to_bytes(iroot(const + k*n , 3)[0]).decode())
    ```
:::spoiler Flag
k = 28
**crypto{n0n_574nd4rd_p4d_c0n51d3r3d_h4rmful}**
:::
## SIGNATURE PART 1
### Signing Server
![image](https://hackmd.io/_uploads/HJfat1vfkl.png)
- **nc socket.cryptohack.org 13374**
- **Source code:**
    ```python!
    from Crypto.Util.number import bytes_to_long, long_to_bytes

    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"}
    ```
- **Mô tả:** Server cho phép ta nhận được **Ciphertext** của Flag thông qua `{"option" : "get_secret"}` nhưng đồng thời cũng cho phép ta **ký** một tin nhắn **msg** bất kỳ thông qua `{"option" : "sign", "msg" : "..."}`. 

- Nhưng server không có các bước kiểm tra đầu vào hoặc bước băm tin nhắn trước khi ký, nên ta hoàn toàn có thể ký thẳng **Ciphertext** để  ra được $Flag$ luôn:
$$C \equiv M^e \pmod N$$

    $$C^d \equiv M^{e \times d} \pmod N$$

    $$M \equiv C^{d} \pmod N$$
- **Script:**
    ```python!
    from pwn import remote
    from json import loads
    from Crypto.Util.number import long_to_bytes
    # nc socket.cryptohack.org 13374
    io = remote("socket.cryptohack.org", 13374)

    io.recvuntil(b"Welcome to my signing server. You can get_pubkey, get_secret, or sign.\n")

    io.sendline(b'{"option" : "get_secret"}')
    secret = loads(io.recvline())
    msg = secret["secret"].encode()

    io.sendline(b'{"option" : "sign", "msg" : "' + msg + b'"}')
    flag = loads(io.recvline())

    print(long_to_bytes(int(flag["signature"], 16)).decode())
    ```
:::spoiler Flag
**TODO: audit signing server to make sure that meddling hacker doesn't get hold of my secret flag: crypto{d0n7_516n_ju57_4ny7h1n6}**
:::
### Let's Decrypt
![image](https://hackmd.io/_uploads/HymAFkwzJe.png)
- **nc socket.cryptohack.org 13391**

- **Source code:**
    ```python!
    import re
    from Crypto.Hash import SHA256
    from Crypto.Util.number import bytes_to_long, long_to_bytes
    from 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"}
    ```
- **Mô tả:** Challenge này sử dụng tin nhắn `'We are hyperreality and Jack and we own CryptoHack.org'` để tạo **SIGNATURE** nhưng lại yêu cầu **msg**  chúng ta gửi vào khi mã hóa bằng tiêu chuẩn **emsa_pkcs1_v15** phải bằng **pow(SIGNATURE, e, n)**?? Chắc chắn là ta không thể sử dụng lại tin nhắn của Challenge rồi, vì server yêu cầu **msg** của ta phải bắt đầu bằng `I am Mallory` và kết thúc bằng `own CryptoHack.org` :sweat_smile: 

- Vì **msg** phải tuân theo format của server, **SIGNATURE** không thể thay đổi được, thứ duy nhất có thể tùy biến theo mục đích của ta đó là $N$ và $e$, server cũng cho phép ta gửi hai giá trị này kèm với **option verify** nên nó là thứ duy nhất ta có thể khai thác. Mình đã không hề nghĩ đến việc phải thay đổi hai cái này luôn :sweat_smile: 
    ```python!
    elif your_input['option'] == 'verify':
        msg = your_input['msg']
        n = int(your_input['N'], 16)
        e = int(your_input['e'], 16)
    ```
- Gọi **digest** là $d$, **SIGNATURE** là $S$, Ta có:
$$d \equiv S^e \pmod N$$

$$S^e = k\times N+d$$
- Cho $e=1$, $k=1$, ta được:
$$N = S-d$$
- Vậy là ta có cặp $(e,N) = (1, S-d)$ thỏa mãn yêu cầu $d \equiv S^e \pmod N$ rồi. Ta sẽ chọn **msg** là `I am Mallory, I own CryptoHack.org`. Gửi chúng kèm theo `{"option" : "verify"}` là có được $Flag$.
- **Script:**
    ```python!
    from pwn import remote
    from json import loads
    from Crypto.Util.number import bytes_to_long
    from pkcs1 import emsa_pkcs1_v15

    # nc socket.cryptohack.org 13391

    io = remote("socket.cryptohack.org", 13391)
    io.recvuntil(b"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")
    io.sendline(b'{"option" : "get_signature"}')
    data = loads(io.recvline())

    SIGNATURE = int(data["signature"], 16)
    N = data["N"]
    e = data["e"]

    msg = b"I am Mallory, I own CryptoHack.org"
    e = hex(1)[2:]
    d = bytes_to_long(emsa_pkcs1_v15.encode(msg, 256))
    N = hex(SIGNATURE - d)[2:]

    verify = '{"option" : "verify", "msg" : "%s", "e" : "%s", "N" : "%s"}' % (msg.decode(), e, N)
    io.sendline(verify.encode())
    flag = loads(io.recvline())["msg"]
    print(flag)
    ```
:::spoiler Flag
**Congratulations, here's a secret: crypto{dupl1c4t3_s1gn4tur3_k3y_s3l3ct10n}**
:::
### Blinding Light
![image](https://hackmd.io/_uploads/rJTRYyDfkl.png)
- **nc socket.cryptohack.org 13376**

- **Source code:**
    ```python!
    from Crypto.Util.number import bytes_to_long, long_to_bytes

    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"}
    ```
- **Mô tả:** Yêu cầu của server rất đơn giản, nếu chữ ký mà ta gửi vào sau khi verify chứa **"admin=True"** thì server sẽ đưa $Flag$ cho. NHƯNG, khi ký tin nhắn thì tin nhắn được ký không chứa **"admin=True"** :sweat_smile: 

- Mình nghĩ qua mặt cái bước kiểm tra này cũng đơn giản thôi, vì nó yêu cầu khi ký không được chứa **ADMIN_TOKEN**, nhưng verify ra thì phải chứa **ADMIN_TOKEN** thì ta sẽ biến đổi sao cho khi ký nó không đọc được chữ `admin=True`, sau khi nó ký xong thì mình biến đổi sao cho nó chứa `admin=True` là được :smile: 

- **Hướng giải:** Ta sẽ nhân `admin=True` cho $2^e$, khi ký thì server sẽ không kiểm tra được từ `admin=True` vì khi này nó bị nhân với $2^e$, sau khi nó ký khóa $d$ xong thì $2^e$ chỉ còn lại $2$. Nên khi đem đi verify thì ta chia **signature** cho $2$ là ra từ `admin=True`.
- **Script:**
    ```python!
    from pwn import remote
    from json import loads
    from Crypto.Util.number import bytes_to_long
    # nc socket.cryptohack.org 13376

    io = remote("socket.cryptohack.org", 13376)

    io.recvuntil(b"Watch out for the Blinding Light\n", drop=True)
    io.sendline(b'{"option" : "get_pubkey"}')
    data = loads(io.recvline())
    N = int(data["N"], 16)
    e = int(data["e"], 16)

    admin = b"admin=True"
    modify_admin = hex((bytes_to_long(admin) * pow(2, e, N)) % N)[2:] #nhân admin với 2^e

    msg = '{"option" : "sign", "msg" : "%s"}' % (modify_admin) 
    msg = msg.encode()
    io.sendline(msg)

    signature = loads(io.recvline())["signature"]
    signature = hex((int(signature, 16) * pow(2, -1, N)) % N)[2:] #chia cho 2

    verify = '{"option" : "verify", "msg" : "%s", "signature" : "%s"}' % (admin.hex(), signature)
    verify = verify.encode()
    io.sendline(verify)

    flag = loads(io.recvline())["response"]
    print(flag)
    ```
:::spoiler Flag
**crypto{m4ll34b1l17y_c4n_b3_d4n63r0u5}**
:::
## SIGNATURE PART 2
### Vote for Pedro
![image](https://hackmd.io/_uploads/BJNfjKPfJe.png)
- **nc socket.cryptohack.org 13394**

- **Source code:** 
    ```python!
    from Crypto.Util.number import bytes_to_long, long_to_bytes

    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"}
    ```
- **Mô tả:** Challenge này làm mình nhớ tới bài **ezRSA** hồi thi **KMACTF 2024**, tóm tắt thì để nhận được $Flag$, **vote** của ta khi mũ $e$ lên phải có từ **"VOTE FOR PEDRO"** ở cuối, thông qua đoạn code:
    ```python!
    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}
    ```
- Challenge sử dụng $e = 3$, coi như có lòng trắc ẩn :pray:
- Lúc đầu ý tưởng của mình là tính căn bậc $e$ của **"VOTE FOR PEDRO"** bằng hàm `iroot()` rồi khi server mũ $e$ lên thì ra được từ gốc, nhưng mà không. Khi mình tính căn bậc $e$ thì kết quả bị làm tròn khiến cho mũ $e$ không thể ra được từ **"VOTE FOR PEDRO"**.

- Quay trở lại với Challenge thì mục tiêu của ta là tìm **vote** thỏa mãn điều kiện:
**prefix + \x00 + msg = pow(vote, e, N)**.
    - Gọi `prefix` là $P$, `msg` là $M$, `vote` là $V$, `len(M) = 14` ta biến đổi phương trình trên thành:
$$P + 00 + M \equiv V^e \pmod N$$
    - $P + 00 + M$ tương đương với việc dịch $P$ sang bên trái $15$ bytes, khiến giá trị $P$ tăng lên $2^{8 \times 15}$ lần, giả sử giá trị của $P$ là $k$ thì ta có $P$ mới là $P = k \times 2^{8 \times 15}$, phương trình mới là:
$$k \times 2^{8 \times 15} + M \equiv V^e \pmod N  $$
    - Với $k$ là giá trị bất kỳ, ta tiếp tục biến đổi phương trình trên:
$$k \times 2^{8 \times 15} + M \equiv V^e \pmod N  $$

    $$\Leftrightarrow V^e \equiv M +k \times 2^{8 \times 15} \pmod N$$

>[!Important] 
Điểm mấu chốt đó là ta hoàn toàn có thể bỏ đi phép $\mod N$ vì các phép tính của ta rất nhỏ, không thể nào vượt quá modulus $N$ được.

- Vậy ta thu được:
$$
\begin{align}
V^e &\equiv M +k \times 2^{8 \times 15}\\
\Leftrightarrow V^e &\equiv M \pmod {2^{8 \times 15}}\\
\Leftrightarrow V &\equiv \sqrt[e]{M} \pmod{2^{8 \times 15}} 
\end{align}
$$

- Vậy là bài toán ban đầu của ta trở thành bài toán tính căn bậc $e$ của $M$ trong modulus $2^{8 \times 15}$, sau một hồi tìm kiếm thì mình biết được rằng không ai dùng `iroot()` để tìm căn bậc $e$ modulo, mà họ sẽ dùng `.nth_root()` trong sagemath.

>[!Important]
Điều kiện để tính căn bậc $n$ modulo **nhanh** đó là phải phân tích được `thừa số nguyên tố` của modulus, ở đây ta có Modulus là $2^{8 \times 15}$, ta đã biết được phân tích thừa số nguyên tố của nó nên `.nth_root()` sẽ chạy siêu nhanh luôn.


- Tính được $V$ thì bài toán kết thúc, gửi nó kèm theo `{"option" : "vote"}` là có $Flag$.
- **Script:**
    ```python!
    from sage.all import *
    from pwn import remote
    from Crypto.Util.number import bytes_to_long
    from json import loads

    io = remote("socket.cryptohack.org", 13375)
    e = 3

    msg = bytes_to_long(b'VOTE FOR PEDRO')

    V = hex(int(mod(msg, 256**15).nth_root(e)))[2:]

    vote = '{"option" : "vote", "vote" : "%s"}' % (V)
    vote = vote.encode()

    io.recvuntil(b"Place your vote. Pedro offers a reward to anyone who votes for him!\n")
    io.sendline(vote)

    flag = loads(io.recvline())["flag"]
    print(flag)
    ```
:::spoiler Flag
**crypto{y0ur_v0t3_i5_my_v0t3}**
:::

