# RSA
- **Mô tả sợ lược**:
- RSA là một thuật toán mật mã hóa khóa công khai. Đây là thuật toán đầu tiên phù hợp với việc tạo ra chữ ký điện tử đồng thời với việc mã hóa.
- Thuật toán RSA có hai khóa: **khóa công khai** (hay khóa công cộng) và **khóa bí mật** (hay khóa cá nhân). Mỗi khóa là những số cố định sử dụng trong quá trình mã hóa và giải mã. Khóa công khai được công bố rộng rãi cho mọi người và được dùng để mã hóa. Những thông tin được mã hóa bằng khóa công khai chỉ có thể được giải mã bằng khóa bí mật tương ứng. Nói cách khác, mọi người đều có thể mã hóa nhưng chỉ có người biết khóa cá nhân (bí mật) mới có thể giải mã được.
- **TẠO KHOÁ**:
- Chọn 2 số nguyên tố lớn $p$ và $q$, $p\neq q$.
- Tính $n = p.q$
- Tính $\phi(n) = (p-1).(q-1)$
- Chọn một số **e** sao cho: $1<e<\phi(n)$ và $gcd(e,\phi(n))=1$.
- Tìm d sao cho: $d.e \equiv 1 \pmod {\phi(n)}$
- **Khoá công khai: (n,e)**
- **Khoá bí mật: (n,d)**
- **MÃ HOÁ**:
- Giả sử Bình muốn gửi đoạn thông tin **M** cho An. Đầu tiên Bình chuyển **M** thành một số **m** theo một hàm có thể đảo ngược (từ **m** có thể xác định lại **M**) được thỏa thuận trước.
- Tiếp theo, Bình dùng cặp khoá công khai của An để chuyển **m** thành **c** theo công thức:
$$c \equiv m^e \pmod n$$
- **GIẢI MÃ:**
- An nhận **c** từ Bình và dùng khoá bí mật **d** của mình để tìm **m** theo công thức sau:
$$m \equiv c^d \pmod n$$
# Các kiểu tấn công RSA thường gặp
## Factorizing the public key
- Sức mạnh của RSA dựa trên việc phân tích **n** thành 2 thừa số nguyên tố p và q để tìm $\phi(n)$ theo công thức: $\phi(n) = (p-1).(q-1)$, có được $\phi(n)$ ta sẽ tìm được **d** một cách dễ dàng với công thức: $d \equiv e^{-1} \pmod {\phi(n)}$. Từ đó, thông qua phép tính: $m \equiv c^d \pmod n$ thông điệp sẽ nằm trong tay.
- Đây là cách tấn công đơn giản nhất và chỉ thực hiện được khi **n** rất nhỏ. Vì vậy để an toàn, **n** nên có độ dài ít nhất 2048 bit.
- Ta dùng hàm **factorint()** trong thư viện **sympy** để phân tích **n**:
```python
from sympy import*
a = 510143758735509025530880200653196460532653147
print(factorint(a))
```
## Common modulus
### As an external attacker
- Giả sử có nhiều người liên lạc với nhau, vì không muốn tạo ra cho mỗi người 1 modulo khác nhau thế nên họ dùng chung $N$, nghĩa là mỗi người sẽ có cặp khoá bí mật $(N,d_i$) và cặp khoá công khai $(N,e_i)$ riêng.
- Bạn biết được họ đang trao đổi thông điệp **m**, bằng cách nào đó bạn can thiệp và có được 2 ciphertext khác nhau là $C_A$ và $C_B$ từ 2 người A và B. Vậy làm thế nào để đọc được nó?
- Đầu tiên, ta tính được $gcd(e_A,e_B)$, thường kết quả sẽ bằng 1. Như đã biết, tồn tại 2 số $u,v$ thoả pt: $e_A.u + e_B.v = gcd(e_A,e_B) = 1$ (tính được bằng thuật toán Euclide mở rộng).
- Ta có: $C_A = M^{e_A} \pmod N$ và $C_B = M^{e_B} \pmod N$ $\Rightarrow C_A^{u} = M^{e_A.u} \pmod N$ và $C_B^{v} = M^{e_B.v} \pmod N$.
- Vậy nên: $M^{e_A.u} . M^{e_B.v} = M^{e_A.u+e_B.v} = M^{gcd(e_A,e_B)} = M^{1} = M$
>[!Note]
Có thể dùng hàm **gcdext($e_A,e_B$)** của thư viện **gmpy2** để tìm $u,v$.
>Hàm trả về 3 giá trị lần lượt là: $gcd(e_A,e_B), u, v$.
>Kết quả $u,v$ tính từ hàm **gcdext($e_A,e_B$)** có thể là số âm, khi đó ta tính $C_A^{u}$ như sau: Đặt $u = -a$ $\Rightarrow$ $C_A^{u} = C_A^{-a} = (C_A^{-1})^{a} = (C_A^{-1})^{-u}$
### As an internal attacker
- Giả sử bạn là thành viên của một nhóm và có cặp $(N,e)$ và $(N,d)$ của riêng mình, bạn có thể giải mã mọi tin nhắn của nhóm bằng cách tìm được $\phi(n)$ như sau:
- Vì $d.e \equiv 1 \pmod {\phi(n)}$ nên ta viết thành: $d.e - 1 = k.\phi(n)$.
- Khi $n$ rất lớn thì $\phi(n)$ và $n$ khá gần nhau $\Rightarrow k = \frac{d.e-1}{\phi(n)} \approx \frac{d.e-1}{n}$ $\Rightarrow \phi(n) = \frac{d.e-1}{k}$.
- Nếu kết quả $\phi(n)$ không là số nguyên, ta tăng $k$ đến khi nào $\phi(n)$ nguyên thì dừng.
> Sở dĩ tăng dần $k$ chứ không phải giảm dần là do $n$ luôn lớn hơn $\phi(n)$, vì vậy $k$ tìm được từ $n$ sẽ luôn bé hơn hoặc bằng $k$ cần tìm.
- Có được $\phi(n)$, dùng công thức $d_{victim} = e_{victim}^{-1} \pmod {\phi(n)}$ tìm ra khoá bí mật của người bạn muốn tấn công và giải mã thông điệp.
- Ví dụ:
```python
from Crypto.Util.number import*
n = 1249110767794010895540410194153
e_victim = 3
e = 66537
d = 205119704640110252892051812353
k = (e * d - 1) // n
while True:
phi = (e * d - 1) // k
if k * phi == (e * d - 1):
print(f"{k = }")
print(f"{phi = }")
break
else:
k = k + 1
d = inverse(e_victim,phi)
print(f'{d = }')
#k = 128477
#phi = 106229518027654879057562454280
#d = 70819678685103252705041636187
```
## Decipher oracle
- Đôi khi bạn sẽ gặp các dịch vụ đặc biệt cung cấp giải mã bất kỳ văn bản mã hóa nào bạn cung cấp cho họ, ngoại trừ một văn bản mã hóa cụ thể (thường là *flag*). Các dịch vụ như vậy được gọi là Oracle.
- Sau đây là cách bạn có thể tạo ra văn bản mã hoá để đánh lừa nó trao cờ cho mình.
- Bạn biết rằng: $m = c^d \pmod n$ với $c = m^e \pmod n$. Mẹo ở đây là ta nhân $c$ với một số $c_2$ với $c_2 = a^e \pmod n$, $a$ là số bất kỳ.
- Đến đây, ta được $C = c.c_2 = (a.m)^e \pmod n$.
- Server sẽ giải mã ra kết quả $a.m$, khi đó ta chỉ cần đem chia cho $a$ là ra $m$.
## Small public exponent
- Bạn muốn gửi một tin nhắn $m$ mã hoá bằng RSA, bạn chọn cho mình một số $n$ khá lớn nhưng $e$ lại quá nhỏ, nhỏ đến mức $c = m^e <n$. Điều đó làm cho phép tính modulo trở nên vô nghĩa. Khi đó, chỉ cần tính $\sqrt[e]c$ là tìm ra $m$ ngay.
- Dùng hàm **iroot()** trong thư viện **gmpy2** để tìm $\sqrt[e]c$.
```python
from gmpy2 import iroot
print(iroot(27,3)[0])
#3
```
>[!Note] Hàm **iroot(n,k)**:
>Trả về 2 giá trị, một là `root`: phần nguyên kết quả phép tính $\sqrt[k] n$; hai là `giá trị boolean`(True/False) để xem $root^k = n$ đúng không.
>Ta có thể truy xuất chúng thông qua chỉ số.
## Hastard's Broadcast Attack
- Cách tấn công này dựa trên cơ sở của Small public exponent ($e$ nhỏ) nhưng lần này là một đoạn tin nhắn dài hơn nên không thể dùng cách tương tự ở trên. Tuy nhiên, nạn nhân gửi cho nhiều người cùng một tin nhắn và sử dụng $e$ như nhau.
- Với tin nhắn cần mã hoá là $m$, đặt $M=m^e$, ta có hệ các pt:
- $M \equiv C_1 \pmod {N_1}$
$M \equiv C_2 \pmod {N_2}$
$M \equiv C_3 \pmod {N_3}$
- Dùng **định lí phần dư trung hoa** để giải hệ tìm $M$.
- Tính căn bậc $e$ để tìm $m$ với $m^e<N_1.N_2.N_3$.
- Thuật toán CRT:
```python
def crt(modulo,remainder):
N = 1
for m in modulo:
N *= m
result = 0
for m,r in zip(modulo,remainder):
n = N // m
result += r * pow(n,-1,m) * n
return result % N
```
- Có thể dùng hàm **crt()** trong thư viện **sympy** để giải hệ phương trình đồng dư. Cú pháp: **crt(list_m,list_r)**, trong đó:
- *list_m*: danh sách các số modulo $N_1,N_2,N_3,...$
- *list_r*: danh sách các số dư $C_1,C_2,C_3,...$
- Hàm trả về 2 giá trị:
- Số dư $M$
- Modulo $N$ là tích các modulo $N_1,N_2,N_3,...$
- Trường hợp các modulo không nguyên tố cùng nhau, hàm trả về `None`.
>[!Note]
>Ta không thể import trực tiếp từ thư viện **sympy** mà dùng dòng lệnh: `from sympy.ntheory.modular import crt`.
## Fermat's attack
- Khi chọn $p$ và $q$ dù lớn nhưng quá gần nhau cũng rất dễ bị tấn công.
- Điều kiện để thực hiện Fermat's attack: $p-q<n^{\frac{1}{4}}$; khi đó ta phân tích $n$ như sau:
$$n = p.q = {(\frac{p-q}{2}})^2 - {(\frac{p+q}{2}})^2 = x^2 - y^2 = (x-y).(x+y)$$
- Trong đó: $x=\frac{p-q}{2}$ và $y=\frac{p+q}{2}$.
- Thuật toán Fermat:
- Đặt $x = [\sqrt n]$
- Tính $y^2 = x^2 - N$ và kiểm tra $y^2$ là một số chính phương chưa, nếu chưa ta tăng $x$ đến khi nó là số chính phương thì dừng.
- Tìm $p$ và $q$ với: $p=x-y$ và $q=x+y$.
- Thuật toán Fermat trong python:
```python
def fermat(n):
a = iroot(n, 2)[0] #a=x; b=y^2
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 = }")
```
## Wiener's attack
- Khi $e$ quá lớn so với modulo dẫn đến $d$ quá nhỏ: $d<\frac{1}{3}.\sqrt[4] n$, điều này tạo lỗ hổng để dùng Wiener's attack.
- Do công thức: $e.d-k.\phi(n)=1$ ($k$ là số nguyên dương), khi đó: $\frac{e}{\phi(n)} \approx \frac{k}{d}$. Từ đó ta có cách tấn công như sau:
- Để tìm các cặp $(k,d)$, ta tìm các phân số bằng nhau liên tục của $\frac{e}{n}$.
- Kiểm tra từng cặp $(k,d)$ xem có đúng không như sau:
- Tính $\phi(n) = \frac{e.d-1}{k}$
- Dùng $\phi(n)$ vừa tìm được giải pt: $x^2-(n-\phi(n)+1).x+n=0$
- Nghiệm pt ứng với 2 số $p$ và $q$, khi đó ta lấy tích của chúng. Nếu kết quả trùng với $n$ ban đầu nghĩa là cặp $(k,d)$ đó chính xác.
- Trong python, hàm **attack()** hoạt động dựa trên nguyên lý ở trên tìm $d$ một cách nhanh chóng:
```python
from owiener import attack
d = attack(e,N)
```
# CRYPTOHACK RSA
## STARTER
### Modular Exponentiation
- **Mô tả**: thử thách này giới thiệu về **phép luỹ thừa modulo**, nghĩa là luỹ thừa một số sau đó đem chia lấy dư một số.
- Trong RSA, phép lũy thừa modulo và bài toán phân tích thừa số nguyên tố, giúp chúng ta xây dựng một *"hàm bẫy"*. Đây là một hàm dễ tính theo một hướng nhưng khó thực hiện ngược lại.
- Trong python, hàm ***pow(base, exponent, modulus)*** được dùng để tính luỹ thừa modulo.
- **Cách giải**:
- Ta cần tính kết quả phép toán: $101^{17} \pmod {22663}$
- Code:
```python
print(pow(101,17,22663))
```
:::spoiler Flag
*19906*
:::
### Public keys
- **Mô tả**: thử thách này giới thiệu về cặp khoá công khai $(N,e)$ trong mã hoá RSA.
- Giá trị $e$ phổ biến là **65537**.
- Giá trị $N$ thường là **tích 2 số nguyên tố p,q**.
- **Cách giải**:
- Đề yêu cầu mã hoá số `12` với các giá trị cho trước: $e = 65537$, $p = 17$, $q = 23$.
- Ta áp dụng công thức: $c = m^{e}\pmod N$. Trong đó:
- $m = 12$
- $N = p.q$
- Code:
```python
e = 65537
p,q = 17,23
N = p*q
print(pow(12,e,N))
```
:::spoiler Flag
*301*
:::
### Euler's Toitent
- **Mô tả**: thử thách này giới thiệu về hàm phi Euler $\phi(n)$.
- $\phi(n)$ là số phần tử lớn hơn 0, bé hơn $n$ và nguyên tố cùng nhau với $n$.
- Công thức tổng quát: $$\phi(n)=n.(1-\frac{1}{p_1}).(1-\frac{1}{p_2}) ...(1-\frac{1}{p_k})$$
- Với $p_1$,$p_2$...,$p_k$ là các thừa số nguyên tố của $n$.
>[!Note]
>Nếu $n$ là số nguyên tố $\Rightarrow \phi(n)=n-1$
>Nếu $n = p.q$ và $gcd(p,q)=1$ $\Rightarrow \phi(n) = \phi(p).\phi(q)$
- **Cách giải**:
- Đề cho 2 số nguyên tố p,q và $N=p.q$, ta áp dụng công thức trên để tìm $\phi(N)$.
- Code:
```python
p = 857504083339712752489993810777
q = 1029224947942998075080348647219
print((p-1)*(q-1))
```
:::spoiler Flag
*882564595536224140639625987657529300394956519977044270821168*
:::
### Private keys
- **Mô tả**: thử thách này giới thiệu cho ta khoá bí mật ***d*** dùng để giải mã ciphertext đã được mã hoá bằng khoá công khai ***e*** trước đó.
- Công thức tính d: $d\equiv e^{-1}$ mod $\phi(N)$
- **Cách giải**:
- Đề cho 2 số nguyên tố $p,q$ và $e$, yêu cầu tính $d$.
- Ta sẽ tìm $\phi(N)$ trước, sau đó tìm $d$ bằng thuật toán Euclide mở rộng hoặc dùng hàm **inverse()** hay **pow()**.
- Code:
```python
def extended_euclide(a,b):
x2 = 1; x1 = 0
y2 = 0; y1 = 1
while (b>0):
q = a//b
r = a - q*b
x = x2 - q*x1
y = y2 - q*y1
a = b; b = r
x2 = x1; x1 = x
y2 = y1; y1 = y
d = a; x = x2; y = y2
return (d,x,y)
p = 857504083339712752489993810777
q = 1029224947942998075080348647219
phi = (p-1)*(q-1)
e = 65537
print(pow(e,-1,phi))
#print(inverse(e,phi)) ->thêm dòng from Crypto.Util.number import inverse
#print(extended_euclide(e,phi))
```
:::spoiler Flag
*121832886702415731577073962957377780195510499965398469843281*
:::
### RSA Decryption
- **Mô tả**: thử thách này cho ta **N**, **e** và yêu cầu giải mã ciphertext là **c** dựa vào khoá bí mật **d** ở bài trước.
- **Cách giải**:
- Dùng công thức: $m=c^{d} \pmod N$
- Code:
```python
e = 65537
N = 882564595536224140639625987659416029426239230804614613279163
d = 121832886702415731577073962957377780195510499965398469843281
c = 77578995801157823671636298847186723593814843845525223303932
print(pow(c,d,N))
```
:::spoiler Flag
*13371337*
:::
### RSA Signatures
- **Mô tả**: thử thách này giới thiệu về **chữ ký số** RSA.
- Chữ ký số dùng để đảm bảo thông điệp gửi đi chính xác, không bị thay đổi và do đúng người gửi ban đầu.
- Ở đây, vai trò của khoá bí mật $d$ và khoá công khai $e$ bị thay đổi một chút, cụ thể như sau:
- Đầu tiên, người gửi mã hoá tin nhắn cần gửi **m** dựa vào khoá công khai $N_0$, $e_0$ của người nhận theo công thức: $c = m^{e_0}$ mod $N_0$
- Tiếp theo, người gửi sẽ dùng 1 hàm băm để băm tin nhắn **m** thành **H(m)**, sau đó dùng khoá bí mật **d** của mình để mã hoá thành **S** theo công thức: $S = H(m)^{d_1} \pmod {N_1}$.
- Nhiệm vụ của người nhận là giải mã $c$ thành $m$ bằng khoá bí mật của mình, sau đó giải mã $S$ thành $H(m)$ bằng khoá công khai $N_1$, $e_1$ của người gửi: $H(m) = S^{e_1} \pmod{N_1}$. So sánh 2 kết quả.
- Thử thách này yêu cầu ta kí một *flag* cho trước, dùng hàm băm SHA256 và khoá bí mật trong file đính kèm.
- **Cách giải**:
- Ta dùng hàm băm **SHA256** trong thư viện **hashlib**, có 2 phương thức trả về giá trị băm:
- **.hexdigest()**: trả về giá trị băm dạng chuỗi hex
- **.digest()**: trả về giá trị băm dạng bytes.
- Sau đó mã hoá tiếp bằng khoá bí mật.
- Code:
```python
from Crypto.Util.number import*
import hashlib
flag = b"crypto{Immut4ble_m3ssag1ng}"
N = 15216583654836731327639981224133918855895948374072384050848479908982286890731769486609085918857664046075375253168955058743185664390273058074450390236774324903305663479046566232967297765731625328029814055635316002591227570271271445226094919864475407884459980489638001092788574811554149774028950310695112688723853763743238753349782508121985338746755237819373178699343135091783992299561827389745132880022259873387524273298850340648779897909381979714026837172003953221052431217940632552930880000919436507245150726543040714721553361063311954285289857582079880295199632757829525723874753306371990452491305564061051059885803
d = 11175901210643014262548222473449533091378848269490518850474399681690547281665059317155831692300453197335735728459259392366823302405685389586883670043744683993709123180805154631088513521456979317628012721881537154107239389466063136007337120599915456659758559300673444689263854921332185562706707573660658164991098457874495054854491474065039621922972671588299315846306069845169959451250821044417886630346229021305410340100401530146135418806544340908355106582089082980533651095594192031411679866134256418292249592135441145384466261279428795408721990564658703903787956958168449841491667690491585550160457893350536334242689
hash = bytes_to_long(hashlib.sha256(flag).digest())
print(pow(hash,d,N))
```
:::spoiler Flag
*13480738404590090803339831649238454376183189744970683129909766078877706583282422686710545217275797376709672358894231550335007974983458408620258478729775647818876610072903021235573923300070103666940534047644900475773318682585772698155617451477448441198150710420818995347235921111812068656782998168064960965451719491072569057636701190429760047193261886092862024118487826452766513533860734724124228305158914225250488399673645732882077575252662461860972889771112594906884441454355959482925283992539925713424132009768721389828848907099772040836383856524605008942907083490383109757406940540866978237471686296661685839083475*
:::
## PRIMES PART 1
### Factoring
- **Mô tả**: thử thách này đề cập đến việc có thể phân tích $N$ thành 2 số nguyên tố $p,q$ khá dễ dàng nếu $p,q$ nhỏ. Vì vậy, nên sử dụng 2 số nguyên tố dài ít nhất 1024 bit, khi nhân lại sẽ được một số có thể dài tối đa 2048 bit, gọi là **RSA-2048**.
- Đề bài yêu cầu ta phân tích 1 số dài 150 bit thành 2 số nguyên tố, chọn số nhỏ hơn.
- **Cách giải**:
- Dùng hàm **factorint()** trong thư viện **sympy**.
- Code:
```python
from sympy import*
a = 510143758735509025530880200653196460532653147
print(factorint(a))
```
:::spoiler Flag
*19704762736204164635843*
:::
### Inferius prime
- **Mô tả**: thử thách này yêu cầu ta giải mã thông điệp **ct** ra *flag* với các dữ kiện như sau:
```python
n = 984994081290620368062168960884976209711107645166770780785733
e = 65537
ct = 948553474947320504624302879933619818331484350431616834086273
```
- **Cách giải**:
- Do cần phải có $d$ mới giải mã được nên đầu tiên ta cần tìm $\phi(n)$, để tìm được $\phi(n)$ cần biết được $p$ và $q$ $\to$ ta sẽ dùng hàm **factorint()** phân tích $n$ thành tích $p$ và $q$:
```python
n = 984994081290620368062168960884976209711107645166770780785733
e = 65537
ct = 948553474947320504624302879933619818331484350431616834086273
print(factorint(n))
#{mpz(1160939713152385063689030212503): 1, 848445505077945374527983649411: 1}
```
- Sau khi có được $\phi(n)=(p-1).(q-1)$, ta tiếp tục tìm $d$ là nghịch đảo modulo của $e$ mod $n$, từ đó tìm được *flag*.
- Code:
```python
from sympy import*
from Crypto.Util.number import*
n = 984994081290620368062168960884976209711107645166770780785733
e = 65537
ct = 948553474947320504624302879933619818331484350431616834086273
p, q = factorint(n)
phi = (p-1)*(q-1)
d = inverse(e,phi)
flag = long_to_bytes(pow(ct,d,n)).decode()
print(flag)
```
:::spoiler Flag
*crypto{N33d_b1g_pR1m35}*
:::
### Monoprime
- **Mô tả**: thử thách này cho ta biết tại sao nên dùng tích của 2 số nguyên tố mà không phải là 1.
- Đề yêu cầu ta giải mã **ct** ra *flag* với dữ kiện như sau:
```python
n = 171731371218065444125482536302245915415603318380280392385291836472299752747934607246477508507827284075763910264995326010251268493630501989810855418416643352631102434317900028697993224868629935657273062472544675693365930943308086634291936846505861203914449338007760990051788980485462592823446469606824421932591
e = 65537
ct = 161367550346730604451454756189028938964941280347662098798775466019463375610700074840105776873791605070092554650190486030367121011578171525759600774739890458414593857709994072516290998135846956596662071379067305011746842247628316996977338024343628757374524136260758515864509435302781735938531030576289086798942
```
- **Cách giải**:
- Tương tự như bài trên nhưng ở đây thay vì $n$ tạo bởi tích 2 số nguyên tố thì bài này lại cho $n$ là một số nguyên tố. Vậy ta sẽ suy ra được $\phi(n) = n-1$, tiếp tục tìm $d$ và giải mã.
- Code:
```python
from sympy import*
from Crypto.Util.number import*
n = 171731371218065444125482536302245915415603318380280392385291836472299752747934607246477508507827284075763910264995326010251268493630501989810855418416643352631102434317900028697993224868629935657273062472544675693365930943308086634291936846505861203914449338007760990051788980485462592823446469606824421932591
e = 65537
ct = 161367550346730604451454756189028938964941280347662098798775466019463375610700074840105776873791605070092554650190486030367121011578171525759600774739890458414593857709994072516290998135846956596662071379067305011746842247628316996977338024343628757374524136260758515864509435302781735938531030576289086798942
phi = n-1
d = inverse(e,phi)
flag = long_to_bytes(pow(ct,d,n)).decode()
print(flag)
```
:::spoiler Flag
*crypto{0n3_pr1m3_41n7_pr1m3_l0l}*
:::
### Square eyes
- **Mô tả**: thử thách này cũng tương tự như 2 bài trên nhưng ở đây, $n$ là một số chính phương, dữ kiện như sau:
```python
n = 535860808044009550029177135708168016201451343147313565371014459027743491739422885443084705720731409713775527993719682583669164873806842043288439828071789970694759080842162253955259590552283047728782812946845160334801782088068154453021936721710269050985805054692096738777321796153384024897615594493453068138341203673749514094546000253631902991617197847584519694152122765406982133526594928685232381934742152195861380221224370858128736975959176861651044370378539093990198336298572944512738570839396588590096813217791191895941380464803377602779240663133834952329316862399581950590588006371221334128215409197603236942597674756728212232134056562716399155080108881105952768189193728827484667349378091100068224404684701674782399200373192433062767622841264055426035349769018117299620554803902490432339600566432246795818167460916180647394169157647245603555692735630862148715428791242764799469896924753470539857080767170052783918273180304835318388177089674231640910337743789750979216202573226794240332797892868276309400253925932223895530714169648116569013581643192341931800785254715083294526325980247219218364118877864892068185905587410977152737936310734712276956663192182487672474651103240004173381041237906849437490609652395748868434296753449
e = 65537
ct = 222502885974182429500948389840563415291534726891354573907329512556439632810921927905220486727807436668035929302442754225952786602492250448020341217733646472982286222338860566076161977786095675944552232391481278782019346283900959677167026636830252067048759720251671811058647569724495547940966885025629807079171218371644528053562232396674283745310132242492367274184667845174514466834132589971388067076980563188513333661165819462428837210575342101036356974189393390097403614434491507672459254969638032776897417674577487775755539964915035731988499983726435005007850876000232292458554577437739427313453671492956668188219600633325930981748162455965093222648173134777571527681591366164711307355510889316052064146089646772869610726671696699221157985834325663661400034831442431209123478778078255846830522226390964119818784903330200488705212765569163495571851459355520398928214206285080883954881888668509262455490889283862560453598662919522224935145694435885396500780651530829377030371611921181207362217397805303962112100190783763061909945889717878397740711340114311597934724670601992737526668932871436226135393872881664511222789565256059138002651403875484920711316522536260604255269532161594824301047729082877262812899724246757871448545439896
```
- **Cách giải**:
- Ta sẽ tìm $\phi(n)$ bằng công thức tổng quát (đã đề cập ở challenge Euler's Toitent):
- Do $n = p^2$, ta biến đổi một tí như sau: $$\phi(n) = n.(1-\frac{1}{p}) = p^2.(1-\frac{1}{p}) = p.(p-1)$$
- Dùng hàm **isqrt()** trong thư viện math hoặc hàm **iroot()** trong thư viện gmpy2 để tìm $p = \sqrt n$.
- Code:
```python
import gmpy2, math
from Crypto.Util.number import*
n = 535860808044009550029177135708168016201451343147313565371014459027743491739422885443084705720731409713775527993719682583669164873806842043288439828071789970694759080842162253955259590552283047728782812946845160334801782088068154453021936721710269050985805054692096738777321796153384024897615594493453068138341203673749514094546000253631902991617197847584519694152122765406982133526594928685232381934742152195861380221224370858128736975959176861651044370378539093990198336298572944512738570839396588590096813217791191895941380464803377602779240663133834952329316862399581950590588006371221334128215409197603236942597674756728212232134056562716399155080108881105952768189193728827484667349378091100068224404684701674782399200373192433062767622841264055426035349769018117299620554803902490432339600566432246795818167460916180647394169157647245603555692735630862148715428791242764799469896924753470539857080767170052783918273180304835318388177089674231640910337743789750979216202573226794240332797892868276309400253925932223895530714169648116569013581643192341931800785254715083294526325980247219218364118877864892068185905587410977152737936310734712276956663192182487672474651103240004173381041237906849437490609652395748868434296753449
e = 65537
ct = 222502885974182429500948389840563415291534726891354573907329512556439632810921927905220486727807436668035929302442754225952786602492250448020341217733646472982286222338860566076161977786095675944552232391481278782019346283900959677167026636830252067048759720251671811058647569724495547940966885025629807079171218371644528053562232396674283745310132242492367274184667845174514466834132589971388067076980563188513333661165819462428837210575342101036356974189393390097403614434491507672459254969638032776897417674577487775755539964915035731988499983726435005007850876000232292458554577437739427313453671492956668188219600633325930981748162455965093222648173134777571527681591366164711307355510889316052064146089646772869610726671696699221157985834325663661400034831442431209123478778078255846830522226390964119818784903330200488705212765569163495571851459355520398928214206285080883954881888668509262455490889283862560453598662919522224935145694435885396500780651530829377030371611921181207362217397805303962112100190783763061909945889717878397740711340114311597934724670601992737526668932871436226135393872881664511222789565256059138002651403875484920711316522536260604255269532161594824301047729082877262812899724246757871448545439896
#p = gmpy2.iroot(n, 2)[0]
p = math.isqrt(n)
phi = p * (p-1)
d = inverse(e,phi)
print(long_to_bytes(pow(ct, d, n)).decode())
```
:::spoiler Flag
*crypto{squar3_r00t_i5_f4st3r_th4n_f4ct0r1ng!}*
:::
### ManyPrime
- **Mô tả**: thử thách này cũng tương tự như các bài trên nhưng $n$ được tạo bởi hơn 30 số nguyên tố với các dữ kiện:
```python
n = 580642391898843192929563856870897799650883152718761762932292482252152591279871421569162037190419036435041797739880389529593674485555792234900969402019055601781662044515999210032698275981631376651117318677368742867687180140048715627160641771118040372573575479330830092989800730105573700557717146251860588802509310534792310748898504394966263819959963273509119791037525504422606634640173277598774814099540555569257179715908642917355365791447508751401889724095964924513196281345665480688029639999472649549163147599540142367575413885729653166517595719991872223011969856259344396899748662101941230745601719730556631637
e = 65537
ct = 320721490534624434149993723527322977960556510750628354856260732098109692581338409999983376131354918370047625150454728718467998870322344980985635149656977787964380651868131740312053755501594999166365821315043312308622388016666802478485476059625888033017198083472976011719998333985531756978678758897472845358167730221506573817798467100023754709109274265835201757369829744113233607359526441007577850111228850004361838028842815813724076511058179239339760639518034583306154826603816927757236549096339501503316601078891287408682099750164720032975016814187899399273719181407940397071512493967454225665490162619270814464
```
- **Cách giải**: ta chỉ cần dùng hàm **factor()** trong thư viện sagemath phân tích ra các thừa số nguyên tố để tìm $\phi(n)$.
>[!Tip]
>Có thể dùng trang web http://factordb.com/index.php để phân tích nhanh hơn.
- Do $n$ gồm tích các số nguyên tố mũ 1 nên ta có thể biến đổi công thức tổng quát tìm $\phi(n)$ thành:
$$\phi(n) = (p_1-1).(p_2-2)...(p_k-1)$$
- Code:
```python
from Crypto.Util.number import*
import sagemath, sympy
n = 580642391898843192929563856870897799650883152718761762932292482252152591279871421569162037190419036435041797739880389529593674485555792234900969402019055601781662044515999210032698275981631376651117318677368742867687180140048715627160641771118040372573575479330830092989800730105573700557717146251860588802509310534792310748898504394966263819959963273509119791037525504422606634640173277598774814099540555569257179715908642917355365791447508751401889724095964924513196281345665480688029639999472649549163147599540142367575413885729653166517595719991872223011969856259344396899748662101941230745601719730556631637
e = 65537
ct = 320721490534624434149993723527322977960556510750628354856260732098109692581338409999983376131354918370047625150454728718467998870322344980985635149656977787964380651868131740312053755501594999166365821315043312308622388016666802478485476059625888033017198083472976011719998333985531756978678758897472845358167730221506573817798467100023754709109274265835201757369829744113233607359526441007577850111228850004361838028842815813724076511058179239339760639518034583306154826603816927757236549096339501503316601078891287408682099750164720032975016814187899399273719181407940397071512493967454225665490162619270814464
phi = 1
lst_prime = [9282105380008121879,9303850685953812323,9389357739583927789,10336650220878499841,10638241655447339831,11282698189561966721,11328768673634243077,11403460639036243901,11473665579512371723,11492065299277279799,11530534813954192171,11665347949879312361,12132158321859677597,12834461276877415051,12955403765595949597,12973972336777979701,13099895578757581201,13572286589428162097,14100640260554622013,14178869592193599187,14278240802299816541,14523070016044624039,14963354250199553339,15364597561881860737,15669758663523555763,15824122791679574573,15998365463074268941,16656402470578844539,16898740504023346457,17138336856793050757,17174065872156629921,17281246625998849649]
for i in lst_prime:
phi = phi*(i-1)
d = inverse(e,phi)
flag = long_to_bytes(pow(ct,d,n)).decode()
print(flag)
```
:::spoiler Flag
*crypto{700_m4ny_5m4ll_f4c70r5}*
:::
## PUBLIC EXPONENT
### Salty
- **Mô tả**:
- File output.txt:
```python
n = 110581795715958566206600392161360212579669637391437097703685154237017351570464767725324182051199901920318211290404777259728923614917211291562555864753005179326101890427669819834642007924406862482343614488768256951616086287044725034412802176312273081322195866046098595306261781788276570920467840172004530873767
e = 1
ct = 44981230718212183604274785925793145442655465025264554046028251311164494127485
```
- Có thể thấy một điều đặc biệt là $e=1$, đồng thời $n$ là một số lớn hơn nhiều so với $ct$ $\Rightarrow$ $ct$ chính là thông điệp ban đầu khi chưa mã hoá.
- **Cách giải**:
- Ta chỉ cần chuyển số sang dạng bytes.
- Code:
```python
from Crypto.Util.number import*
n = 110581795715958566206600392161360212579669637391437097703685154237017351570464767725324182051199901920318211290404777259728923614917211291562555864753005179326101890427669819834642007924406862482343614488768256951616086287044725034412802176312273081322195866046098595306261781788276570920467840172004530873767
e = 1
ct = 44981230718212183604274785925793145442655465025264554046028251311164494127485
flag = long_to_bytes(ct).decode()
print(flag)
```
:::spoiler Flag
*crypto{saltstack_fell_for_this!}*
:::
### Modulus Inutilis
- **Mô tả**:
- File output.txt:
```python
n = 17258212916191948536348548470938004244269544560039009244721959293554822498047075403658429865201816363311805874117705688359853941515579440852166618074161313773416434156467811969628473425365608002907061241714688204565170146117869742910273064909154666642642308154422770994836108669814632309362483307560217924183202838588431342622551598499747369771295105890359290073146330677383341121242366368309126850094371525078749496850520075015636716490087482193603562501577348571256210991732071282478547626856068209192987351212490642903450263288650415552403935705444809043563866466823492258216747445926536608548665086042098252335883
e = 3
ct = 243251053617903760309941844835411292373350655973075480264001352919865180151222189820473358411037759381328642957324889519192337152355302808400638052620580409813222660643570085177957
```
- Ở thử thách này, $e$ là một số nhỏ và $n$ cực lớn, điều này làm ta liên tưởng đến ****Small public exponent****.
- **Cách giải**:
- Ta chỉ cần tìm $\sqrt[e] {ct} = \sqrt[3] {ct}$ rồi đổi sang dạng bytes là xong.
- Code:
```python
from Crypto.Util.number import*
import gmpy2
n = 17258212916191948536348548470938004244269544560039009244721959293554822498047075403658429865201816363311805874117705688359853941515579440852166618074161313773416434156467811969628473425365608002907061241714688204565170146117869742910273064909154666642642308154422770994836108669814632309362483307560217924183202838588431342622551598499747369771295105890359290073146330677383341121242366368309126850094371525078749496850520075015636716490087482193603562501577348571256210991732071282478547626856068209192987351212490642903450263288650415552403935705444809043563866466823492258216747445926536608548665086042098252335883
e = 3
ct = 243251053617903760309941844835411292373350655973075480264001352919865180151222189820473358411037759381328642957324889519192337152355302808400638052620580409813222660643570085177957
flag = long_to_bytes(gmpy2.iroot(ct,e)[0]).decode()
print(flag)
```
:::spoiler Flag
*crypto{N33d_m04R_p4dd1ng}*
:::
### Everything is Big
- **Mô tả**:
- File output.txt:
```python
from Crypto.Util.number import*
import owiener
N = 0xb8af3d3afb893a602de4afe2a29d7615075d1e570f8bad8ebbe9b5b9076594cf06b6e7b30905b6420e950043380ea746f0a14dae34469aa723e946e484a58bcd92d1039105871ffd63ffe64534b7d7f8d84b4a569723f7a833e6daf5e182d658655f739a4e37bd9f4a44aff6ca0255cda5313c3048f56eed5b21dc8d88bf5a8f8379eac83d8523e484fa6ae8dbcb239e65d3777829a6903d779cd2498b255fcf275e5f49471f35992435ee7cade98c8e82a8beb5ce1749349caa16759afc4e799edb12d299374d748a9e3c82e1cc983cdf9daec0a2739dadcc0982c1e7e492139cbff18c5d44529407edfd8e75743d2f51ce2b58573fea6fbd4fe25154b9964d
e = 0x9ab58dbc8049b574c361573955f08ea69f97ecf37400f9626d8f5ac55ca087165ce5e1f459ef6fa5f158cc8e75cb400a7473e89dd38922ead221b33bc33d6d716fb0e4e127b0fc18a197daf856a7062b49fba7a86e3a138956af04f481b7a7d481994aeebc2672e500f3f6d8c581268c2cfad4845158f79c2ef28f242f4fa8f6e573b8723a752d96169c9d885ada59cdeb6dbe932de86a019a7e8fc8aeb07748cfb272bd36d94fe83351252187c2e0bc58bb7a0a0af154b63397e6c68af4314601e29b07caed301b6831cf34caa579eb42a8c8bf69898d04b495174b5d7de0f20cf2b8fc55ed35c6ad157d3e7009f16d6b61786ee40583850e67af13e9d25be3
c = 0x3f984ff5244f1836ed69361f29905ca1ae6b3dcf249133c398d7762f5e277919174694293989144c9d25e940d2f66058b2289c75d1b8d0729f9a7c4564404a5fd4313675f85f31b47156068878e236c5635156b0fa21e24346c2041ae42423078577a1413f41375a4d49296ab17910ae214b45155c4570f95ca874ccae9fa80433a1ab453cbb28d780c2f1f4dc7071c93aff3924d76c5b4068a0371dff82531313f281a8acadaa2bd5078d3ddcefcb981f37ff9b8b14c7d9bf1accffe7857160982a2c7d9ee01d3e82265eec9c7401ecc7f02581fd0d912684f42d1b71df87a1ca51515aab4e58fab4da96e154ea6cdfb573a71d81b2ea4a080a1066e1bc3474
```
- Ta có thể thấy $e$ là một số vô cùng lớn xấp xỉ $N$, điều này khiến $d$ nhỏ lại $\Rightarrow$ dùng kiểu tấn công wiener mà ta từng đề cập ở trên.
- **Cách giải**:
- Dùng hàm **attack()** trong thư viện owiener để tìm $d$ $\Rightarrow$ *flag*.
- Code:
```python
from Crypto.Util.number import*
import owiener
N = 0xb8af3d3afb893a602de4afe2a29d7615075d1e570f8bad8ebbe9b5b9076594cf06b6e7b30905b6420e950043380ea746f0a14dae34469aa723e946e484a58bcd92d1039105871ffd63ffe64534b7d7f8d84b4a569723f7a833e6daf5e182d658655f739a4e37bd9f4a44aff6ca0255cda5313c3048f56eed5b21dc8d88bf5a8f8379eac83d8523e484fa6ae8dbcb239e65d3777829a6903d779cd2498b255fcf275e5f49471f35992435ee7cade98c8e82a8beb5ce1749349caa16759afc4e799edb12d299374d748a9e3c82e1cc983cdf9daec0a2739dadcc0982c1e7e492139cbff18c5d44529407edfd8e75743d2f51ce2b58573fea6fbd4fe25154b9964d
e = 0x9ab58dbc8049b574c361573955f08ea69f97ecf37400f9626d8f5ac55ca087165ce5e1f459ef6fa5f158cc8e75cb400a7473e89dd38922ead221b33bc33d6d716fb0e4e127b0fc18a197daf856a7062b49fba7a86e3a138956af04f481b7a7d481994aeebc2672e500f3f6d8c581268c2cfad4845158f79c2ef28f242f4fa8f6e573b8723a752d96169c9d885ada59cdeb6dbe932de86a019a7e8fc8aeb07748cfb272bd36d94fe83351252187c2e0bc58bb7a0a0af154b63397e6c68af4314601e29b07caed301b6831cf34caa579eb42a8c8bf69898d04b495174b5d7de0f20cf2b8fc55ed35c6ad157d3e7009f16d6b61786ee40583850e67af13e9d25be3
c = 0x3f984ff5244f1836ed69361f29905ca1ae6b3dcf249133c398d7762f5e277919174694293989144c9d25e940d2f66058b2289c75d1b8d0729f9a7c4564404a5fd4313675f85f31b47156068878e236c5635156b0fa21e24346c2041ae42423078577a1413f41375a4d49296ab17910ae214b45155c4570f95ca874ccae9fa80433a1ab453cbb28d780c2f1f4dc7071c93aff3924d76c5b4068a0371dff82531313f281a8acadaa2bd5078d3ddcefcb981f37ff9b8b14c7d9bf1accffe7857160982a2c7d9ee01d3e82265eec9c7401ecc7f02581fd0d912684f42d1b71df87a1ca51515aab4e58fab4da96e154ea6cdfb573a71d81b2ea4a080a1066e1bc3474
d = owiener.attack(e,N)
flag = long_to_bytes(pow(c,d,N)).decode()
print(flag)
```
:::spoiler Flag
*crypto{s0m3th1ng5_c4n_b3_t00_b1g}*
:::
### Crossed Wires
- **Mô tả**:
- File source:
```python
from Crypto.Util.number import getPrime, long_to_bytes, bytes_to_long, inverse
import math
from gmpy2 import next_prime
FLAG = b"crypto{????????????????????????????????????????????????} "
p = getPrime(1024)
q = getPrime(1024)
N = p*q
phi = (p-1)*(q-1)
e = 0x10001
d = inverse(e, phi)
my_key = (N, d)
friends = 5
friend_keys = [(N, getPrime(17)) for _ in range(friends)]
cipher = bytes_to_long(FLAG)
for key in friend_keys:
cipher = pow(cipher, key[1], key[0])
print(f"My private key: {my_key}")
print(f"My Friend's public keys: {friend_keys}")
print(f"Encrypted flag: {cipher}")
```
- Thử thách này bạn sẽ là người nhận ciphertext được mã hoá từ nhóm bạn. Từ file source ta thấy *cipher* được đem mũ $e$ mod $n$ lần lượt theo từng cặp $(n,e_i)$, nghĩa là sử dụng $e$ là tích các public key 5 người như sau:
$$C \equiv m^{e_1.e_2.e_3.e_4.e_5} \pmod n$$
- File output.txt:
```python
n = 21711308225346315542706844618441565741046498277716979943478360598053144971379956916575370343448988601905854572029635846626259487297950305231661109855854947494209135205589258643517961521594924368498672064293208230802441077390193682958095111922082677813175804775628884377724377647428385841831277059274172982280545237765559969228707506857561215268491024097063920337721783673060530181637161577401589126558556182546896783307370517275046522704047385786111489447064794210010802761708615907245523492585896286374996088089317826162798278528296206977900274431829829206103227171839270887476436899494428371323874689055690729986771
d = 2734411677251148030723138005716109733838866545375527602018255159319631026653190783670493107936401603981429171880504360560494771017246468702902647370954220312452541342858747590576273775107870450853533717116684326976263006435733382045807971890762018747729574021057430331778033982359184838159747331236538501849965329264774927607570410347019418407451937875684373454982306923178403161216817237890962651214718831954215200637651103907209347900857824722653217179548148145687181377220544864521808230122730967452981435355334932104265488075777638608041325256776275200067541533022527964743478554948792578057708522350812154888097
lst_e = [106979,108533,69557,97117,103231]
ct = 20304610279578186738172766224224793119885071262464464448863461184092225736054747976985179673905441502689126216282897704508745403799054734121583968853999791604281615154100736259131453424385364324630229671185343778172807262640709301838274824603101692485662726226902121105591137437331463201881264245562214012160875177167442010952439360623396658974413900469093836794752270399520074596329058725874834082188697377597949405779039139194196065364426213208345461407030771089787529200057105746584493554722790592530472869581310117300343461207750821737840042745530876391793484035024644475535353227851321505537398888106855012746117
```
- Đề cho bộ 3 $(n,d,e)$ của mình và $e$ của 5 người bạn $\Rightarrow$ **Common modulus (Internal attacker)**.
- **Cách giải**:
- Muốn giải mã được *flag* ta cần có $d$ tính theo công thức: $d \equiv e^{-1} \mod \phi(n)$ với $e=e_1.e_2.e_3.e_4.e_5$, nhưng đề chưa cho $\phi(n)$. Vậy nên ta sẽ tìm $\phi(n)$ dựa theo phương pháp tấn công trên.
- Sau khi tìm được $\phi(n)$, ta tiến hành tìm $d$ và giải mã ra **flag**.
- Code:
```python
from Crypto.Util.number import*
n = 21711308225346315542706844618441565741046498277716979943478360598053144971379956916575370343448988601905854572029635846626259487297950305231661109855854947494209135205589258643517961521594924368498672064293208230802441077390193682958095111922082677813175804775628884377724377647428385841831277059274172982280545237765559969228707506857561215268491024097063920337721783673060530181637161577401589126558556182546896783307370517275046522704047385786111489447064794210010802761708615907245523492585896286374996088089317826162798278528296206977900274431829829206103227171839270887476436899494428371323874689055690729986771
d = 2734411677251148030723138005716109733838866545375527602018255159319631026653190783670493107936401603981429171880504360560494771017246468702902647370954220312452541342858747590576273775107870450853533717116684326976263006435733382045807971890762018747729574021057430331778033982359184838159747331236538501849965329264774927607570410347019418407451937875684373454982306923178403161216817237890962651214718831954215200637651103907209347900857824722653217179548148145687181377220544864521808230122730967452981435355334932104265488075777638608041325256776275200067541533022527964743478554948792578057708522350812154888097
lst_e = [106979,108533,69557,97117,103231]
ct = 20304610279578186738172766224224793119885071262464464448863461184092225736054747976985179673905441502689126216282897704508745403799054734121583968853999791604281615154100736259131453424385364324630229671185343778172807262640709301838274824603101692485662726226902121105591137437331463201881264245562214012160875177167442010952439360623396658974413900469093836794752270399520074596329058725874834082188697377597949405779039139194196065364426213208345461407030771089787529200057105746584493554722790592530472869581310117300343461207750821737840042745530876391793484035024644475535353227851321505537398888106855012746117
e = 0x10001
k = (d*e-1)//n
while True:
phi = (d*e-1)//k
if (phi*k) == d*e-1:
print(f'{phi = }')
print(f'{k = }')
break
else:
k += 1
E = 1
for i in lst_e:
E *= i
D = inverse(E,phi)
flag = long_to_bytes(pow(ct,D,n)).decode()
print(flag)
```
>Hoặc ta có thể tính từng $d_i$ ứng với mỗi $e_i$, sau đó lấy tích các $d$ vừa tìm được.
:::spoiler Flag
*crypto{3ncrypt_y0ur_s3cr3t_w1th_y0ur_fr1end5_publ1c_k3y}*
:::
### Everything is still Big
- **Mô tả**:
- File source:
```python
from Crypto.Util.number import getPrime, bytes_to_long, inverse
from random import getrandbits
from math import gcd
FLAG = b"crypto{?????????????????????????????????????}"
m = bytes_to_long(FLAG)
def get_huge_RSA():
p = getPrime(1024)
q = getPrime(1024)
N = p*q
phi = (p-1)*(q-1)
while True:
d = getrandbits(512)
if (3*d)**4 > N and gcd(d,phi) == 1:
e = inverse(d, phi)
break
return N,e
N, e = get_huge_RSA()
c = pow(m, e, N)
print(f'N = {hex(N)}')
print(f'e = {hex(e)}')
print(f'c = {hex(c)}')
```
- File output:
```python
N = 0xb12746657c720a434861e9a4828b3c89a6b8d4a1bd921054e48d47124dbcc9cfcdcc39261c5e93817c167db818081613f57729e0039875c72a5ae1f0bc5ef7c933880c2ad528adbc9b1430003a491e460917b34c4590977df47772fab1ee0ab251f94065ab3004893fe1b2958008848b0124f22c4e75f60ed3889fb62e5ef4dcc247a3d6e23072641e62566cd96ee8114b227b8f498f9a578fc6f687d07acdbb523b6029c5bbeecd5efaf4c4d35304e5e6b5b95db0e89299529eb953f52ca3247d4cd03a15939e7d638b168fd00a1cb5b0cc5c2cc98175c1ad0b959c2ab2f17f917c0ccee8c3fe589b4cb441e817f75e575fc96a4fe7bfea897f57692b050d2b
e = 0x9d0637faa46281b533e83cc37e1cf5626bd33f712cc1948622f10ec26f766fb37b9cd6c7a6e4b2c03bce0dd70d5a3a28b6b0c941d8792bc6a870568790ebcd30f40277af59e0fd3141e272c48f8e33592965997c7d93006c27bf3a2b8fb71831dfa939c0ba2c7569dd1b660efc6c8966e674fbe6e051811d92a802c789d895f356ceec9722d5a7b617d21b8aa42dd6a45de721953939a5a81b8dffc9490acd4f60b0c0475883ff7e2ab50b39b2deeedaefefffc52ae2e03f72756d9b4f7b6bd85b1a6764b31312bc375a2298b78b0263d492205d2a5aa7a227abaf41ab4ea8ce0e75728a5177fe90ace36fdc5dba53317bbf90e60a6f2311bb333bf55ba3245f
c = 0xa3bce6e2e677d7855a1a7819eb1879779d1e1eefa21a1a6e205c8b46fdc020a2487fdd07dbae99274204fadda2ba69af73627bdddcb2c403118f507bca03cb0bad7a8cd03f70defc31fa904d71230aab98a10e155bf207da1b1cac1503f48cab3758024cc6e62afe99767e9e4c151b75f60d8f7989c152fdf4ff4b95ceed9a7065f38c68dee4dd0da503650d3246d463f504b36e1d6fafabb35d2390ecf0419b2bb67c4c647fb38511b34eb494d9289c872203fa70f4084d2fa2367a63a8881b74cc38730ad7584328de6a7d92e4ca18098a15119baee91237cea24975bdfc19bdbce7c1559899a88125935584cd37c8dd31f3f2b4517eefae84e7e588344fa5
```
- Đề cho $e$ và $N$ đều lớn mình có thể nghĩ ngay đến wiener's attack để tìm $d$, nhưng từ file source ta có điều kiện: $(3.d)^4>N$. Vì thế ta không thể áp dụng wiener's attack được.
- **Cách giải**:
- Đối với bài này mình sẽ dùng tool **buneh_durfee** để tìm $d$ như sau:
- Đầu tiên tải file *buneh_durfee.sage*: https://github.com/mimoo/RSA-and-LLL-attacks/blob/master/boneh_durfee.sage
- Ngay hàm `example()` thay $n$ và $e$ của bài toán và chạy file bằng dòng lệnh: `sage boneh_durfee.sage`; hàm sẽ trả về giá trị private key $d$.
- Code:
```python
from Crypto.Util.number import long_to_bytes, inverse
N = 0xb12746657c720a434861e9a4828b3c89a6b8d4a1bd921054e48d47124dbcc9cfcdcc39261c5e93817c167db818081613f57729e0039875c72a5ae1f0bc5ef7c933880c2ad528adbc9b1430003a491e460917b34c4590977df47772fab1ee0ab251f94065ab3004893fe1b2958008848b0124f22c4e75f60ed3889fb62e5ef4dcc247a3d6e23072641e62566cd96ee8114b227b8f498f9a578fc6f687d07acdbb523b6029c5bbeecd5efaf4c4d35304e5e6b5b95db0e89299529eb953f52ca3247d4cd03a15939e7d638b168fd00a1cb5b0cc5c2cc98175c1ad0b959c2ab2f17f917c0ccee8c3fe589b4cb441e817f75e575fc96a4fe7bfea897f57692b050d2b
e = 0x9d0637faa46281b533e83cc37e1cf5626bd33f712cc1948622f10ec26f766fb37b9cd6c7a6e4b2c03bce0dd70d5a3a28b6b0c941d8792bc6a870568790ebcd30f40277af59e0fd3141e272c48f8e33592965997c7d93006c27bf3a2b8fb71831dfa939c0ba2c7569dd1b660efc6c8966e674fbe6e051811d92a802c789d895f356ceec9722d5a7b617d21b8aa42dd6a45de721953939a5a81b8dffc9490acd4f60b0c0475883ff7e2ab50b39b2deeedaefefffc52ae2e03f72756d9b4f7b6bd85b1a6764b31312bc375a2298b78b0263d492205d2a5aa7a227abaf41ab4ea8ce0e75728a5177fe90ace36fdc5dba53317bbf90e60a6f2311bb333bf55ba3245f
c = 0xa3bce6e2e677d7855a1a7819eb1879779d1e1eefa21a1a6e205c8b46fdc020a2487fdd07dbae99274204fadda2ba69af73627bdddcb2c403118f507bca03cb0bad7a8cd03f70defc31fa904d71230aab98a10e155bf207da1b1cac1503f48cab3758024cc6e62afe99767e9e4c151b75f60d8f7989c152fdf4ff4b95ceed9a7065f38c68dee4dd0da503650d3246d463f504b36e1d6fafabb35d2390ecf0419b2bb67c4c647fb38511b34eb494d9289c872203fa70f4084d2fa2367a63a8881b74cc38730ad7584328de6a7d92e4ca18098a15119baee91237cea24975bdfc19bdbce7c1559899a88125935584cd37c8dd31f3f2b4517eefae84e7e588344fa5
d = 4405001203086303853525638270840706181413309101774712363141310824943602913458674670435988275467396881342752245170076677567586495166847569659096584522419007
flag = long_to_bytes(pow(c,d,N)).decode()
print(flag)
```
:::spoiler Flag
*crypto{bon3h5_4tt4ck_i5_sr0ng3r_th4n_w13n3r5}*
:::
### Endless Emails
- **Mô tả**:
- File johan:
```python
from Crypto.Util.number import bytes_to_long, getPrime
from secret import messages
def RSA_encrypt(message):
m = bytes_to_long(message)
p = getPrime(1024)
q = getPrime(1024)
N = p * q
e = 3
c = pow(m, e, N)
return N, e, c
for m in messages:
N, e, c = RSA_encrypt(m)
print(f"n = {N}")
print(f"e = {e}")
print(f"c = {c}")
```
- File output:
```python
n = 14528915758150659907677315938876872514853653132820394367681510019000469589767908107293777996420037715293478868775354645306536953789897501630398061779084810058931494642860729799059325051840331449914529594113593835549493208246333437945551639983056810855435396444978249093419290651847764073607607794045076386643023306458718171574989185213684263628336385268818202054811378810216623440644076846464902798568705083282619513191855087399010760232112434412274701034094429954231366422968991322244343038458681255035356984900384509158858007713047428143658924970374944616430311056440919114824023838380098825914755712289724493770021
e = 3
c = 6965891612987861726975066977377253961837139691220763821370036576350605576485706330714192837336331493653283305241193883593410988132245791554283874785871849223291134571366093850082919285063130119121338290718389659761443563666214229749009468327825320914097376664888912663806925746474243439550004354390822079954583102082178617110721589392875875474288168921403550415531707419931040583019529612270482482718035497554779733578411057633524971870399893851589345476307695799567919550426417015815455141863703835142223300228230547255523815097431420381177861163863791690147876158039619438793849367921927840731088518955045807722225
n = 20463913454649855046677206889944639231694511458416906994298079596685813354570085475890888433776403011296145408951323816323011550738170573801417972453504044678801608709931200059967157605416809387753258251914788761202456830940944486915292626560515250805017229876565916349963923702612584484875113691057716315466239062005206014542088484387389725058070917118549621598629964819596412564094627030747720659155558690124005400257685883230881015636066183743516494701900125788836869358634031031172536767950943858472257519195392986989232477630794600444813136409000056443035171453870906346401936687214432176829528484662373633624123
e = 3
c = 5109363605089618816120178319361171115590171352048506021650539639521356666986308721062843132905170261025772850941702085683855336653472949146012700116070022531926476625467538166881085235022484711752960666438445574269179358850309578627747024264968893862296953506803423930414569834210215223172069261612934281834174103316403670168299182121939323001232617718327977313659290755318972603958579000300780685344728301503641583806648227416781898538367971983562236770576174308965929275267929379934367736694110684569576575266348020800723535121638175505282145714117112442582416208209171027273743686645470434557028336357172288865172
n = 19402640770593345339726386104915705450969517850985511418263141255686982818547710008822417349818201858549321868878490314025136645036980129976820137486252202687238348587398336652955435182090722844668488842986318211649569593089444781595159045372322540131250208258093613844753021272389255069398553523848975530563989367082896404719544411946864594527708058887475595056033713361893808330341623804367785721774271084389159493974946320359512776328984487126583015777989991635428744050868653379191842998345721260216953918203248167079072442948732000084754225272238189439501737066178901505257566388862947536332343196537495085729147
e = 3
c = 5603386396458228314230975500760833991383866638504216400766044200173576179323437058101562931430558738148852367292802918725271632845889728711316688681080762762324367273332764959495900563756768440309595248691744845766607436966468714038018108912467618638117493367675937079141350328486149333053000366933205635396038539236203203489974033629281145427277222568989469994178084357460160310598260365030056631222346691527861696116334946201074529417984624304973747653407317290664224507485684421999527164122395674469650155851869651072847303136621932989550786722041915603539800197077294166881952724017065404825258494318993054344153
n = 12005639978012754274325188681720834222130605634919280945697102906256738419912110187245315232437501890545637047506165123606573171374281507075652554737014979927883759915891863646221205835211640845714836927373844277878562666545230876640830141637371729405545509920889968046268135809999117856968692236742804637929866632908329522087977077849045608566911654234541526643235586433065170392920102840518192803854740398478305598092197183671292154743153130012885747243219372709669879863098708318993844005566984491622761795349455404952285937152423145150066181043576492305166964448141091092142224906843816547235826717179687198833961
e = 3
c = 1522280741383024774933280198410525846833410931417064479278161088248621390305797210285777845359812715909342595804742710152832168365433905718629465545306028275498667935929180318276445229415104842407145880223983428713335709038026249381363564625791656631137936935477777236936508600353416079028339774876425198789629900265348122040413865209592074731028757972968635601695468594123523892918747882221891834598896483393711851510479989203644477972694520237262271530260496342247355761992646827057846109181410462131875377404309983072358313960427035348425800940661373272947647516867525052504539561289941374722179778872627956360577
n = 17795451956221451086587651307408104001363221003775928432650752466563818944480119932209305765249625841644339021308118433529490162294175590972336954199870002456682453215153111182451526643055812311071588382409549045943806869173323058059908678022558101041630272658592291327387549001621625757585079662873501990182250368909302040015518454068699267914137675644695523752851229148887052774845777699287718342916530122031495267122700912518207571821367123013164125109174399486158717604851125244356586369921144640969262427220828940652994276084225196272504355264547588369516271460361233556643313911651916709471353368924621122725823
e = 3
c = 8752507806125480063647081749506966428026005464325535765874589376572431101816084498482064083887400646438977437273700004934257274516197148448425455243811009944321764771392044345410680448204581679548854193081394891841223548418812679441816502910830861271884276608891963388657558218620911858230760629700918375750796354647493524576614017731938584618983084762612414591830024113057983483156974095503392359946722756364412399187910604029583464521617256125933111786441852765229820406911991809039519015434793656710199153380699319611499255869045311421603167606551250174746275803467549814529124250122560661739949229005127507540805
n = 25252721057733555082592677470459355315816761410478159901637469821096129654501579313856822193168570733800370301193041607236223065376987811309968760580864569059669890823406084313841678888031103461972888346942160731039637326224716901940943571445217827960353637825523862324133203094843228068077462983941899571736153227764822122334838436875488289162659100652956252427378476004164698656662333892963348126931771536472674447932268282205545229907715893139346941832367885319597198474180888087658441880346681594927881517150425610145518942545293750127300041942766820911120196262215703079164895767115681864075574707999253396530263
e = 3
c = 23399624135645767243362438536844425089018405258626828336566973656156553220156563508607371562416462491581383453279478716239823054532476006642583363934314982675152824147243749715830794488268846671670287617324522740126594148159945137948643597981681529145611463534109482209520448640622103718682323158039797577387254265854218727476928164074249568031493984825273382959147078839665114417896463735635546290504843957780546550577300001452747760982468547756427137284830133305010038339400230477403836856663883956463830571934657200851598986174177386323915542033293658596818231793744261192870485152396793393026198817787033127061749
n = 19833203629283018227011925157509157967003736370320129764863076831617271290326613531892600790037451229326924414757856123643351635022817441101879725227161178559229328259469472961665857650693413215087493448372860837806619850188734619829580286541292997729705909899738951228555834773273676515143550091710004139734080727392121405772911510746025807070635102249154615454505080376920778703360178295901552323611120184737429513669167641846902598281621408629883487079110172218735807477275590367110861255756289520114719860000347219161944020067099398239199863252349401303744451903546571864062825485984573414652422054433066179558897
e = 3
c = 15239683995712538665992887055453717247160229941400011601942125542239446512492703769284448009141905335544729440961349343533346436084176947090230267995060908954209742736573986319254695570265339469489948102562072983996668361864286444602534666284339466797477805372109723178841788198177337648499899079471221924276590042183382182326518312979109378616306364363630519677884849945606288881683625944365927809405420540525867173639222696027472336981838588256771671910217553150588878434061862840893045763456457939944572192848992333115479951110622066173007227047527992906364658618631373790704267650950755276227747600169403361509144
```
- Từ file johan có thể thấy *messages* là một danh sách các tin nhắn cần mã hóa, Flag sẽ là một trong các tin nhắn đó.
- Mỗi tin nhắn được mã hóa bởi cặp $(N_{i},e)$, nhưng sẽ có những tin nhắn trùng nhau và dùng chung $e=3$ khá nhỏ nên ta sẽ áp dụng **Hastard's Broadcast Attack**.
- **Cách giải**:
- Dùng định lí phần dư trung hoa để giải các hệ 3 phương trình chọn từ cặp $(n_i,c_i)$ bất kì từ file output, sau đó lấy căn bậc $e$ của kết quả vừa tìm được.
- Nếu chọn đúng 3 cặp $(n,c)$ trong 7 cặp được dùng để mã hóa cùng một tin nhắn là Flag thì thành công.
- Hàm **combinations()** trong module `itertools` được dùng để tạo tất cả các tổ hợp không lặp của một tập hợp phần tử, với độ dài cho trước. Cú pháp:
```python
from itertools import combinations
combinations(iterable, r)
```
- Trong đó:
- iterable: một chuỗi, danh sách, tuple,...
- r: số lượng phần tử trong mỗi tổ hợp
- Code:
```python
from Crypto.Util.number import*
from sympy.ntheory.modular import crt
from gmpy2 import iroot
from itertools import combinations
n0 = 14528915758150659907677315938876872514853653132820394367681510019000469589767908107293777996420037715293478868775354645306536953789897501630398061779084810058931494642860729799059325051840331449914529594113593835549493208246333437945551639983056810855435396444978249093419290651847764073607607794045076386643023306458718171574989185213684263628336385268818202054811378810216623440644076846464902798568705083282619513191855087399010760232112434412274701034094429954231366422968991322244343038458681255035356984900384509158858007713047428143658924970374944616430311056440919114824023838380098825914755712289724493770021
c0 = 6965891612987861726975066977377253961837139691220763821370036576350605576485706330714192837336331493653283305241193883593410988132245791554283874785871849223291134571366093850082919285063130119121338290718389659761443563666214229749009468327825320914097376664888912663806925746474243439550004354390822079954583102082178617110721589392875875474288168921403550415531707419931040583019529612270482482718035497554779733578411057633524971870399893851589345476307695799567919550426417015815455141863703835142223300228230547255523815097431420381177861163863791690147876158039619438793849367921927840731088518955045807722225
n1 = 20463913454649855046677206889944639231694511458416906994298079596685813354570085475890888433776403011296145408951323816323011550738170573801417972453504044678801608709931200059967157605416809387753258251914788761202456830940944486915292626560515250805017229876565916349963923702612584484875113691057716315466239062005206014542088484387389725058070917118549621598629964819596412564094627030747720659155558690124005400257685883230881015636066183743516494701900125788836869358634031031172536767950943858472257519195392986989232477630794600444813136409000056443035171453870906346401936687214432176829528484662373633624123
c1 = 5109363605089618816120178319361171115590171352048506021650539639521356666986308721062843132905170261025772850941702085683855336653472949146012700116070022531926476625467538166881085235022484711752960666438445574269179358850309578627747024264968893862296953506803423930414569834210215223172069261612934281834174103316403670168299182121939323001232617718327977313659290755318972603958579000300780685344728301503641583806648227416781898538367971983562236770576174308965929275267929379934367736694110684569576575266348020800723535121638175505282145714117112442582416208209171027273743686645470434557028336357172288865172
n2 = 19402640770593345339726386104915705450969517850985511418263141255686982818547710008822417349818201858549321868878490314025136645036980129976820137486252202687238348587398336652955435182090722844668488842986318211649569593089444781595159045372322540131250208258093613844753021272389255069398553523848975530563989367082896404719544411946864594527708058887475595056033713361893808330341623804367785721774271084389159493974946320359512776328984487126583015777989991635428744050868653379191842998345721260216953918203248167079072442948732000084754225272238189439501737066178901505257566388862947536332343196537495085729147
c2 = 5603386396458228314230975500760833991383866638504216400766044200173576179323437058101562931430558738148852367292802918725271632845889728711316688681080762762324367273332764959495900563756768440309595248691744845766607436966468714038018108912467618638117493367675937079141350328486149333053000366933205635396038539236203203489974033629281145427277222568989469994178084357460160310598260365030056631222346691527861696116334946201074529417984624304973747653407317290664224507485684421999527164122395674469650155851869651072847303136621932989550786722041915603539800197077294166881952724017065404825258494318993054344153
n3 = 12005639978012754274325188681720834222130605634919280945697102906256738419912110187245315232437501890545637047506165123606573171374281507075652554737014979927883759915891863646221205835211640845714836927373844277878562666545230876640830141637371729405545509920889968046268135809999117856968692236742804637929866632908329522087977077849045608566911654234541526643235586433065170392920102840518192803854740398478305598092197183671292154743153130012885747243219372709669879863098708318993844005566984491622761795349455404952285937152423145150066181043576492305166964448141091092142224906843816547235826717179687198833961
c3 = 1522280741383024774933280198410525846833410931417064479278161088248621390305797210285777845359812715909342595804742710152832168365433905718629465545306028275498667935929180318276445229415104842407145880223983428713335709038026249381363564625791656631137936935477777236936508600353416079028339774876425198789629900265348122040413865209592074731028757972968635601695468594123523892918747882221891834598896483393711851510479989203644477972694520237262271530260496342247355761992646827057846109181410462131875377404309983072358313960427035348425800940661373272947647516867525052504539561289941374722179778872627956360577
n4 = 17795451956221451086587651307408104001363221003775928432650752466563818944480119932209305765249625841644339021308118433529490162294175590972336954199870002456682453215153111182451526643055812311071588382409549045943806869173323058059908678022558101041630272658592291327387549001621625757585079662873501990182250368909302040015518454068699267914137675644695523752851229148887052774845777699287718342916530122031495267122700912518207571821367123013164125109174399486158717604851125244356586369921144640969262427220828940652994276084225196272504355264547588369516271460361233556643313911651916709471353368924621122725823
c4 = 8752507806125480063647081749506966428026005464325535765874589376572431101816084498482064083887400646438977437273700004934257274516197148448425455243811009944321764771392044345410680448204581679548854193081394891841223548418812679441816502910830861271884276608891963388657558218620911858230760629700918375750796354647493524576614017731938584618983084762612414591830024113057983483156974095503392359946722756364412399187910604029583464521617256125933111786441852765229820406911991809039519015434793656710199153380699319611499255869045311421603167606551250174746275803467549814529124250122560661739949229005127507540805
n5 = 25252721057733555082592677470459355315816761410478159901637469821096129654501579313856822193168570733800370301193041607236223065376987811309968760580864569059669890823406084313841678888031103461972888346942160731039637326224716901940943571445217827960353637825523862324133203094843228068077462983941899571736153227764822122334838436875488289162659100652956252427378476004164698656662333892963348126931771536472674447932268282205545229907715893139346941832367885319597198474180888087658441880346681594927881517150425610145518942545293750127300041942766820911120196262215703079164895767115681864075574707999253396530263
c5 = 23399624135645767243362438536844425089018405258626828336566973656156553220156563508607371562416462491581383453279478716239823054532476006642583363934314982675152824147243749715830794488268846671670287617324522740126594148159945137948643597981681529145611463534109482209520448640622103718682323158039797577387254265854218727476928164074249568031493984825273382959147078839665114417896463735635546290504843957780546550577300001452747760982468547756427137284830133305010038339400230477403836856663883956463830571934657200851598986174177386323915542033293658596818231793744261192870485152396793393026198817787033127061749
n6 = 19833203629283018227011925157509157967003736370320129764863076831617271290326613531892600790037451229326924414757856123643351635022817441101879725227161178559229328259469472961665857650693413215087493448372860837806619850188734619829580286541292997729705909899738951228555834773273676515143550091710004139734080727392121405772911510746025807070635102249154615454505080376920778703360178295901552323611120184737429513669167641846902598281621408629883487079110172218735807477275590367110861255756289520114719860000347219161944020067099398239199863252349401303744451903546571864062825485984573414652422054433066179558897
c6 = 15239683995712538665992887055453717247160229941400011601942125542239446512492703769284448009141905335544729440961349343533346436084176947090230267995060908954209742736573986319254695570265339469489948102562072983996668361864286444602534666284339466797477805372109723178841788198177337648499899079471221924276590042183382182326518312979109378616306364363630519677884849945606288881683625944365927809405420540525867173639222696027472336981838588256771671910217553150588878434061862840893045763456457939944572192848992333115479951110622066173007227047527992906364658618631373790704267650950755276227747600169403361509144
e = 3
lst_n = [n1,n2,n3,n4,n5,n6,n0]
lst_c = [c1,c2,c3,c4,c5,c6,c0]
equation = [(x, y) for x, y in zip(lst_n, lst_c)] #tạo 1 list gồm các cặp (n,c)
three_equations = list(combinations(equation, 3)) #tạo 1 list gồm các phần tử là các tổ hợp 3 cặp (n,c)
for i in three_equations:
n = [x[0] for x in i]
c = [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())
break
```
:::spoiler Flag
*crypto{1f_y0u_d0nt_p4d_y0u_4r3_Vuln3rabl3}*
:::
## PRIMES PART 2
### Infinite Descent
- **Mô tả**:
- Source:
```python
import random
from Crypto.Util.number import bytes_to_long, isPrime
FLAG = b"crypto{???????????????????}"
def getPrimes(bitsize):
r = random.getrandbits(bitsize)
p, q = r, r
while not isPrime(p):
p += random.getrandbits(bitsize//4)
while not isPrime(q):
q += random.getrandbits(bitsize//8)
return p, q
m = bytes_to_long(FLAG)
p, q = getPrimes(2048)
n = p * q
e = 0x10001
c = pow(m, e, n)
print(f"n = {n}")
print(f"e = {e}")
print(f"c = {c}")
```
- Từ file source cho thấy **n** được tạo bởi $p$ và $q$ khá gần nhau $\Rightarrow$ dùng Fermat's attack.
- **Cách giải**:
- Thông qua Fermat's attack, ta tìm được $p$ và $q$; sau đó tìm $\phi(n)$ và $d$ như bình thường.
- **Code:**
```python
from gmpy2 import iroot
from Crypto.Util.number import*
n = 383347712330877040452238619329524841763392526146840572232926924642094891453979246383798913394114305368360426867021623649667024217266529000859703542590316063318592391925062014229671423777796679798747131250552455356061834719512365575593221216339005132464338847195248627639623487124025890693416305788160905762011825079336880567461033322240015771102929696350161937950387427696385850443727777996483584464610046380722736790790188061964311222153985614287276995741553706506834906746892708903948496564047090014307484054609862129530262108669567834726352078060081889712109412073731026030466300060341737504223822014714056413752165841749368159510588178604096191956750941078391415634472219765129561622344109769892244712668402761549412177892054051266761597330660545704317210567759828757156904778495608968785747998059857467440128156068391746919684258227682866083662345263659558066864109212457286114506228470930775092735385388316268663664139056183180238043386636254075940621543717531670995823417070666005930452836389812129462051771646048498397195157405386923446893886593048680984896989809135802276892911038588008701926729269812453226891776546037663583893625479252643042517196958990266376741676514631089466493864064316127648074609662749196545969926051
e = 65537
c = 98280456757136766244944891987028935843441533415613592591358482906016439563076150526116369842213103333480506705993633901994107281890187248495507270868621384652207697607019899166492132408348789252555196428608661320671877412710489782358282011364127799563335562917707783563681920786994453004763755404510541574502176243896756839917991848428091594919111448023948527766368304503100650379914153058191140072528095898576018893829830104362124927140555107994114143042266758709328068902664037870075742542194318059191313468675939426810988239079424823495317464035252325521917592045198152643533223015952702649249494753395100973534541766285551891859649320371178562200252228779395393974169736998523394598517174182142007480526603025578004665936854657294541338697513521007818552254811797566860763442604365744596444735991732790926343720102293453429936734206246109968817158815749927063561835274636195149702317415680401987150336994583752062565237605953153790371155918439941193401473271753038180560129784192800351649724465553733201451581525173536731674524145027931923204961274369826379325051601238308635192540223484055096203293400419816024111797903442864181965959247745006822690967920957905188441550106930799896292835287867403979631824085790047851383294389
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
phi = (p-1)*(q-1)
d = inverse(e,phi)
print(long_to_bytes(pow(c,d,n)).decode())
```
:::spoiler Flag
*crypto{f3rm47_w45_4_g3n1u5}*
:::
### Marin's Secrets
- **Mô tả**: từ file marin có thể thấy $N$ được tạo bởi 2 **số nguyên tố Mersenne**.
- Số nguyên tố Mersenne là số có giá trị bằng $2^p -1$ với $p$ cũng là một số nguyên tố. Ví dụ: 31 là số nguyên tố Mersenne vì $31 = 2^5-1$ có $5$ là số nguyên tố.
- Tính đến nay đã có 52 số nguyên tố Mersenne $2^p -1$ tương ứng 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.
```
- File output:
```python
n = 658416274830184544125027519921443515789888264156074733099244040126213682497714032798116399288176502462829255784525977722903018714434309698108208388664768262754316426220651576623731617882923164117579624827261244506084274371250277849351631679441171018418018498039996472549893150577189302871520311715179730714312181456245097848491669795997289830612988058523968384808822828370900198489249243399165125219244753790779764466236965135793576516193213175061401667388622228362042717054014679032953441034021506856017081062617572351195418505899388715709795992029559042119783423597324707100694064675909238717573058764118893225111602703838080618565401139902143069901117174204252871948846864436771808616432457102844534843857198735242005309073939051433790946726672234643259349535186268571629077937597838801337973092285608744209951533199868228040004432132597073390363357892379997655878857696334892216345070227646749851381208554044940444182864026513709449823489593439017366358869648168238735087593808344484365136284219725233811605331815007424582890821887260682886632543613109252862114326372077785369292570900594814481097443781269562647303671428895764224084402259605109600363098950091998891375812839523613295667253813978434879172781217285652895469194181218343078754501694746598738215243769747956572555989594598180639098344891175879455994652382137038240166358066403475457
e = 65537
c = 400280463088930432319280359115194977582517363610532464295210669530407870753439127455401384569705425621445943992963380983084917385428631223046908837804126399345875252917090184158440305503817193246288672986488987883177380307377025079266030262650932575205141853413302558460364242355531272967481409414783634558791175827816540767545944534238189079030192843288596934979693517964655661507346729751987928147021620165009965051933278913952899114253301044747587310830419190623282578931589587504555005361571572561916866063458812965314474160499067525067495140150092119620928363007467390920130717521169105167963364154636472055084012592138570354390246779276003156184676298710746583104700516466091034510765027167956117869051938116457370384737440965109619578227422049806566060571831017610877072484262724789571076529586427405780121096546942812322324807145137017942266863534989082115189065560011841150908380937354301243153206428896320576609904361937035263985348984794208198892615898907005955403529470847124269512316191753950203794578656029324506688293446571598506042198219080325747328636232040936761788558421528960279832802127562115852304946867628316502959562274485483867481731149338209009753229463924855930103271197831370982488703456463385914801246828662212622006947380115549529820197355738525329885232170215757585685484402344437894981555179129287164971002033759724456
```
- **Cách giải**:
- Do $n = (2^p-1).(2^q-1)$ nên ta có thể dùng vòng lặp tìm $p,q$ rồi tìm $\phi(n)$ và $d$ như bình thường.
- **Code:**
```python
from Crypto.Util.number import*
n = 658416274830184544125027519921443515789888264156074733099244040126213682497714032798116399288176502462829255784525977722903018714434309698108208388664768262754316426220651576623731617882923164117579624827261244506084274371250277849351631679441171018418018498039996472549893150577189302871520311715179730714312181456245097848491669795997289830612988058523968384808822828370900198489249243399165125219244753790779764466236965135793576516193213175061401667388622228362042717054014679032953441034021506856017081062617572351195418505899388715709795992029559042119783423597324707100694064675909238717573058764118893225111602703838080618565401139902143069901117174204252871948846864436771808616432457102844534843857198735242005309073939051433790946726672234643259349535186268571629077937597838801337973092285608744209951533199868228040004432132597073390363357892379997655878857696334892216345070227646749851381208554044940444182864026513709449823489593439017366358869648168238735087593808344484365136284219725233811605331815007424582890821887260682886632543613109252862114326372077785369292570900594814481097443781269562647303671428895764224084402259605109600363098950091998891375812839523613295667253813978434879172781217285652895469194181218343078754501694746598738215243769747956572555989594598180639098344891175879455994652382137038240166358066403475457
e = 65537
c = 400280463088930432319280359115194977582517363610532464295210669530407870753439127455401384569705425621445943992963380983084917385428631223046908837804126399345875252917090184158440305503817193246288672986488987883177380307377025079266030262650932575205141853413302558460364242355531272967481409414783634558791175827816540767545944534238189079030192843288596934979693517964655661507346729751987928147021620165009965051933278913952899114253301044747587310830419190623282578931589587504555005361571572561916866063458812965314474160499067525067495140150092119620928363007467390920130717521169105167963364154636472055084012592138570354390246779276003156184676298710746583104700516466091034510765027167956117869051938116457370384737440965109619578227422049806566060571831017610877072484262724789571076529586427405780121096546942812322324807145137017942266863534989082115189065560011841150908380937354301243153206428896320576609904361937035263985348984794208198892615898907005955403529470847124269512316191753950203794578656029324506688293446571598506042198219080325747328636232040936761788558421528960279832802127562115852304946867628316502959562274485483867481731149338209009753229463924855930103271197831370982488703456463385914801246828662212622006947380115549529820197355738525329885232170215757585685484402344437894981555179129287164971002033759724456
lst_p = [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]
for i in lst_p:
p = 2**i-1
if n%p == 0:
q = n//p
break
#p,q = 2**2203-1, 2**2281-1
phi = (p-1)*(q-1)
d = inverse(e,phi)
flag = long_to_bytes(pow(c,d,n)).decode()
print(flag)
```
:::spoiler Flag
*crypto{Th3se_Pr1m3s_4r3_t00_r4r3}*
:::
### Fast Primes
- **Mô tả**:
- File fast_primes:
```python
import math
import random
from Crypto.Cipher import PKCS1_OAEP
from Crypto.PublicKey import RSA
from Crypto.Util.number import bytes_to_long, inverse
from gmpy2 import is_prime
FLAG = b"crypto{????????????}"
primes = []
def sieve(maximum=10000):
# In general Sieve of Sundaram, produces primes smaller
# than (2*x + 2) for a number given number x. Since
# we want primes smaller than maximum, we reduce maximum to half
# This array is used to separate numbers of the form
# i+j+2ij from others where 1 <= i <= j
marked = [False]*(int(maximum/2)+1)
# Main logic of Sundaram. Mark all numbers which
# do not generate prime number by doing 2*i+1
for i in range(1, int((math.sqrt(maximum)-1)/2)+1):
for j in range(((i*(i+1)) << 1), (int(maximum/2)+1), (2*i+1)):
marked[j] = True
# Since 2 is a prime number
primes.append(2)
# Print other primes. Remaining primes are of the
# form 2*i + 1 such that marked[i] is false.
for i in range(1, int(maximum/2)):
if (marked[i] == False):
primes.append(2*i + 1)
def get_primorial(n):
result = 1
for i in range(n):
result = result * primes[i]
return result
def get_fast_prime():
M = get_primorial(40)
while True:
k = random.randint(2**28, 2**29-1)
a = random.randint(2**20, 2**62-1)
p = k * M + pow(e, a, M)
if is_prime(p):
return p
sieve()
e = 0x10001
m = bytes_to_long(FLAG)
p = get_fast_prime()
q = get_fast_prime()
n = p * q
phi = (p - 1) * (q - 1)
d = inverse(e, phi)
key = RSA.construct((n, e, d))
cipher = PKCS1_OAEP.new(key)
ciphertext = cipher.encrypt(FLAG)
assert cipher.decrypt(ciphertext) == FLAG
exported = key.publickey().export_key()
with open("key.pem", 'wb') as f:
f.write(exported)
with open('ciphertext.txt', 'w') as f:
f.write(ciphertext.hex())
```
- File key:
```python
-----BEGIN PUBLIC KEY-----
MFswDQYJKoZIhvcNAQEBBQADSgAwRwJATKIe3jfj1qY7zuX5Eg0JifAUOq6RUwLz
Ruiru4QKcvtW0Uh1KMp1GVt4MmKDiQksTok/pKbJsBFCZugFsS3AjQIDAQAB
-----END PUBLIC KEY-----
```
- Giới thiệu sơ về **sàng Sundaram** (hàm sieve()):
- Sàng Sundaram là một thuật toán ít phổ biến hơn so với sàng Eratosthenes, cũng dùng để tìm các số nguyên tố nhỏ hơn một số nguyên $max$ cho trước.
- Ý tưởng: loại bỏ các số có dạng $i+j+2ij$, với $1 \le i \le j$ và $i+j+2ij \le n$ với $n=[\frac{max-1}{2}]$. Sau khi loại bỏ, các số còn lại sẽ được tính theo công thức $2n+1$ cho ra các số nguyên tố lẻ nhỏ hơn $max$.
- Sở dĩ loại bỏ các số dạng $i+j+2ij$ vì:
- Số nguyên lẻ được biểu diễn: $p = 2n+1$
- Đặt $s=i+j+2ij$ ta có: $2s+1=2.(i+j+2ij)+1=(2i+1).(2j+1)$ là tích của 2 số nguyên lẻ $\Rightarrow$ không là SNT.
- Ở thử thách này, $p$ và $q$ được tạo bởi công thức:
$$p=k.M+ (65537^{a}\bmod M)$$
- $M$ là tích các số nguyên tố nhỏ hơn số nguyên cho trước.
- $a,K$ được tạo ngẫu nhiên.
- Vì thuật toán sinh số nguyên tố để tạo khóa RSA có cấu trúc đặc biệt nên tạo ra một lỗ hổng tên là **Roca** (Return of Coppersmith’s Attack). Roca bị khai thác bởi phương pháp Coppersmith: tìm $k$ nhỏ trong miền modulo $n$, từ đó tìm được $p$.
- **Cách làm:**
- Dùng tool https://github.com/FlorianPicca/ROCA/blob/master/roca_attack.py để phân tích $n$ thành 2 số nguyên tố $p,q$.
- Đọc file pem để có được $n,e$ và tính $d$.
- Tạo lần lượt khóa RSA và đối tượng OAEP rồi tiến hành giải mã.
- **Code:**
```python
from Crypto.Util.number import*
from Crypto.PublicKey import RSA
from Crypto.Cipher import PKCS1_OAEP
c = 0x249d72cd1d287b1a15a3881f2bff5788bc4bf62c789f2df44d88aae805b54c9a94b8944c0ba798f70062b66160fee312b98879f1dd5d17b33095feb3c5830d28
p = 77342270837753916396402614215980760127245056504361515489809293852222206596161
q = 51894141255108267693828471848483688186015845988173648228318286999011443419469
with open ("key_fastprime.pem", "r") as f:
key = RSA.import_key(f.read())
n = key.n
e = key.e
d = inverse(e,(p-1)*(q-1))
key = RSA.construct((n,e,d))
cipher = PKCS1_OAEP.new(key)
print(cipher.decrypt(long_to_bytes(c)))
```
:::spoiler Flag
crypto{p00R_3570n14}
:::
### Ron was wrong, Whit is Right
- **Mô tả**:
- File excerpt:
```python
from Crypto.Cipher import PKCS1_OAEP
from Crypto.PublicKey import RSA
msg = "???"
with open('21.pem') as f:
key = RSA.importKey(f.read())
cipher = PKCS1_OAEP.new(key)
ciphertext = cipher.encrypt(msg)
with open('21.ciphertext', 'w') as f:
f.write(ciphertext.hex())
```
- Từ file này ta thấy **key** được lưu ở file *21.pem*, **ciphertext** được lưu ở file *21.ciphertext*.
- Vì **msg** được mã hóa bằng PKCS1_OAEP nên đầu tiên, ta phải tạo một **key**-đối tượng khóa RSA (cơ bản gồm $n,e,d$), sau đó tạo một **cipher**-đối tượng OAEP dựa trên **key**, cuối cùng dùng phương thức **.decrypt()** của cipher để giải mã.
- Hàm **RSA.construct()** dùng để tạo một đối tượng khóa RSA từ các tham số đã biết như $n,e,d$ hoặc mở rộng hơn là thêm $p,q,...$
- Tạo đối tượng OAEP:
- Cú pháp:`cipher = PKCS1_OAEP.new(key)` với *key* phải là một khóa RSA đầy đủ.
- Trả về 2 phương thức: `cipher.encrypt(message)` và `cipher.decrypt(ciphertext)`.
- **Cách giải**:
- Đọc file để có được $n$ và $e$, sau đó lần lượt tìm $p,q$ và tính như bình thường như sau:
- Có 50 file lưu 50 $n$ khác nhau, ta sẽ tính ***gcd*** của $n$ lấy ở file *21.pem* với từng $n$ của 49 file còn lại, nếu kết quả ở file nào khác 1 nghĩa là $p$ chính là thừa số nguyên tố chung của 2 số $n$ đó.
- Sau đó tìm $q = n//p$ rồi đến $\phi(n)$ và $d$.
- Sau khi có $d$, tạo lần lượt $key$ và $cipher$.
- Dùng phương thức **.decrypt()** để giải mã.
- **Code**:
```python
from Crypto.Util.number import*
from Crypto.PublicKey import RSA
from gmpy2 import gcdext
from Crypto.Cipher import PKCS1_OAEP
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 i in n_all:
print(gcdext(n21,i)[0])
p = 919031168254299342928662994540730760042229248845820491699169870943314884504551963184014786520812939038906152950817942941469675496074887272906954399256046690838233813273902630076899906873722574023918253104149453601408405078374008695616160025877687382663027910687942091698042309812910101246025081363544171351624307177908410700904833438480012985928358897861427063761678614898919524867442676631453135379994570031284289815099294504127712924001149921480778993635917803466637717023744788311275545126346774536416864472035644211758788016642401235014385037912224180351022196262011724157012443048941426178651665266181311662824205620324073087330858064769424755443807165558567191049013947419763315902476674266627953223373671797370373786249718677582213173537848582863398367624397247597103174897140005790273296171101569756006898658668311846034013183862374297777882433967015111727139360441681664840944403450472574336901043555319067050153928231938431298082827397506406624964952344826628463723499263165279281720105570577138817805451223334196017505528543229067732013216932022575286870744622250293712218581458417969597311485156075637589299870500738770767213366940656708757081771498126771190548298648709527029056697749965377697006723247968508680596118923
q = n21//p
c = 0xc62d91677825632cb8ac9d2fbee7490fca70b3f067bd8d811fa446a21001de7943cacafc429b2513d3f20c3224d212ca2937a4a4ea10792a1c498b791e978e4b050b525576bc68421e40d9f420c0b8a07778daf69edf2095bf48222896bb2d6581288ce7a2e7aec15a88a440ff1a1e48beb56f68b4f860d1f64a6ec8cafed90846b7d893bc482df69c8478d5a0d6fc2d043cdd97178740a9eb59d2576b5136200c8ea77e648c88e6c5104ca5d0c6add2fc2c8569ce909f8461e7fa3d901fe67eaeff656399d4751fedba9973e246427e0c7a217f5bdc3edcb5033f17b5ef53419e340355a809eb46f48f538e880abd6f72212b02d3dbf2c4f633a503e648d1a835c4574b23e329e1c51078ea7cbb7533e771899498d4a5760bc0799b7e046f268f098fe0b57de47cd70ccf01ad3c9daec5027f306141bfe7a6c0bd29ee6caf94c7433c25e34ee974005e2360337cb6b3cec5eaf5d31d19f01435f4cdcaa455a18e78dee078395b8ad14b9c3a0d817dc1e3109c7b8af35ab3a5950bf47d5e621f9373ef421540052aac307ecea91f9c29c14bfd81b41d4c5a9b34a8ec2fa1ae06c3d881f39286c3d8dbb1849602fecc27bb135f7dd443e2598d247d1182d350b04be1ac0a734cb0e852a36902d88066ac375a35e279b126e413a97aaa35a0ba933f7b8d574c298332ce428c181464b240709a414af1b77103441b6ccfd0790eccea5926844054903c83f4cb415d600a6b7bc771c9e7a86394a2b427ebe8edec08b8095f561827716898e11caf6f0fe562af8a69f7b6469f0e86bdcc32f429f10821c763b34307efc5b2ae7fd524a07e5d0b762c096f025a3f240fb7bd3554582dcce32c175867d93970b0422e17870ec58f2a305545a3d284b3abb2d21a45ad8fd5faed0dc66312a5aa2f994606a51cd6682acd48ea3fb883f0611e1e5c2fb4047b5c80815ba5d3bcfefaf121bfde4d5c91ee27bb899ef0d29fa5c6dc4223ac2bfcff0217d08579a13e9b02dc97aa2622df62eeaaa38bb3bd087cdd209f03e8926a951e90eaa0f678a252a067ac66402a4c85865931689ed3b33f9f6de0c499f140ef508dfba6007a607a271dcbec18a61f7488bba34d143f93bc259310ffbf23f3391734d8d8811a4be8abf6382e55c2ccbfd80b1559d907fd8d46e0431cdbcd8fdb06d57973437f7b8ff5efc5a53c80d552e8fe622971f7376eeea35f4df9b32ada93e531a52b63ba13f6b7bf61ab337d6d93feb0e8c8a309dfa7e5f50e8cf9655b73ae64822b50db5312f35f4718b0668305065ea283ddf8f0a4e8f486ee9d119ebc584be1837b3d959a25ace208ffac2fb703390a72d3027b64fdd1955b513c0403f09232efa1794a277e0be3f4f9f3a6fd23c6e52101e723cef5db7a2a18a107cd522379adb40c5ed36b26cdf53a1000d7d576f1157b42aac3d3ee011275
d = inverse(e21,(p-1)*(q-1))
key = RSA.construct((n21,e21,d))
cipher = PKCS1_OAEP.new(key)
print(cipher.decrypt(bytes.fromhex(hex(c)[2:])).decode())
#print(cipher.decrypt(long_to_bytes(c)).decode())
```
:::spoiler Flag
*crypto{3ucl1d_w0uld_b3_pr0ud}*
:::
Sign in with Wallet
Connect another wallet