# Lý thuyết
## Introduction
* Định nghĩa: RSA(Rivest–Shamir–Adleman) là một thuật toán mã hóa bất đối xứng dùng để mã hóa và giải mã message. RSA dùng 2 khóa khác nhau là public key(dùng cho mã hóa) và private key(dùng để giải mã)
* **public key = { e, n }**
* **private key = { d, n }**
* **Quá trình sinh khóa**:
* Chọn 2 số nguyên tố p và q có độ dài bit tương đương nhau, modul $N=p\cdot q$, nên $\phi(N) = (p-1)(q-1)$
* Chọn một số nguyên $e$ sao cho $1 < e < \phi(N)$ và $gcd(e, \phi(N))=1$ ($e$ thường được chọn là 65537), lấy d sao cho $e.d \equiv 1\bmod \phi(N)$
* <n, e> là cặp public key: $c = m^e \bmod n$
* <n, d> là cặp private key: $m =c^d \bmod n$
## Factoring large intergers (Phân tích thừa số số nguyên lớn)
Nếu biết được các ước nguyên tố của N(p và q), có thể tính được $\phi(N)$ và d cũng bị lộ. Việc phân tích modulo này là duyệt trâu trong RSA. Thuật toán phân tích nhanh nhất hiện tại là `General Number Field Sieve` với runtime là $$exp((c+o(1))n^{1/3}log^{2/3}n)$$ với $c \sim 1.923$. Nhưng với RSA-2048, cũng mất tỷ tỷ năm mới có thể phá khóa $\Rightarrow$ Độ an toàn của RSA
Với một số trường hợp có p-1 là tích của các thừa số nhỏ hơn B, p có thể được phân tích bằng pollard's p-1 với thời gian ít hơn $B^3$
* **Open problem 1:** Cho N, e thỏa mãn $gcd(e,\varphi(N))=1$, xác định hàm số $f_{e,N}: \mathbb{Z}_{N}^{*}\rightarrow\mathbb{Z}_{N}^{*}$ với $f_{e,N}(x)=x^{1/e}$ mod N. Có tồn tại một thuật toán A nào có thể phân tích thừa số của N khi được cho N và quyền truy cập vào một $f_{e,N}(x)$ với một số e nào đó hay không?
* **Fact 1:** Nếu biết được d, thì có thể phân tích được N từ d. Vì:
$e.d \equiv 1\bmod \phi(N)$, suy ra $e.d - 1$ chia hết cho $\phi(N)$ mà $\phi(N)$ là số chẵn, nên $e.d -1 = 2^t.r$ (r lẻ). Chọn số g bất kì $1<g<Z_{N}^{*}$, tìm $x=g^r$ sao cho:
* $x \neq 1$
$x \neq -1$
$x^2 \equiv 1 \pmod N$.
* Khi tìm được x, $p=gcd(x-1, N)$, nếu không tìm được x, tiếp tục thử với g khác trong các g thỏa mãn $1<g<Z_{N}^{*}$. Độ phức tạp: $O(n^3)$
## Elementary Attacks
### Common Modulus
* Phần này đưa ra một ý tưởng: cung cấp N chung cho tất cả mọi người trong một nội bộ và cho mỗi người một e, d riêng. Ý tưởng này có vẻ tiện nhưng tính bảo mật không cao, vì dựa vào fact 1 phía trên, từ e và d có thể suy ra p,q, từ đó 1 người dùng có thể suy ra tất cả d, e của mọi người khác.
Code ví dụ:
```=python
from math import gcd
N = 882564595536224140639625987659416029426239230804614613279163
d = 121832886702415731577073962957377780195510499965398469843281
e = 65537
k = e*d-1
s = 0
r = k
while r % 2 == 0:
r //= 2
s += 1
p=q=0
for g in range(2, 100):
if gcd(g,N)!= 1: continue
x=pow(g, r, N)
if x==1 or x==N-1: continue
for i in range(s):
y = pow(x, 2, N)
if y == 1:
p = gcd(x - 1, N)
if 1 < p < N:
q = N // p
break
else:
break
x = y
if p!=0: break
print(p)
print(q)
```
### Blinding
* Blinding là thuật toán bẫy bằng cách đánh tráo các message cần phải ký. Ví dụ, với message M, thay vì đưa trực tiếp M cho người ký, thì người ta sẽ tạo ra một message tương tự là M'=r^e.M, để tránh bị nghi ngờ, chữ ký sau khi kí cho M' được ký hiệu là S'=(M') ^d mod N. S' có thể được viết như sau:
$S’ = (M’)^d \bmod N = (r^e M)^d \bmod N = r M^d \bmod N$
Nhưng sau đó attacker có thể từ M có thể suy ra S bằng cách $S=S'/r = M^d (mod N)$.
* Trong thực tế, Blinding không nguy hiểm vì hầu hết hệ thống chữ ký RSA băm thông điệp trước khi ký, đồng thời Blinding còn là tính năng hữu ích trong các hệ thống tiền điện tử ẩn danh.
## Low private exponent
* Để giảm thời gian giải mã hoặc tạo chữ ký, người ta có thể chọn khóa bí mật $d$ nhỏ thay vì chọn $d$ ngẫu nhiên, vì thời gian tính lũy thừa modulo tỷ lệ với $log_2d$ với $d$ nhỏ, hiệu suất có thể tăng ít nhất 10 lần đối với mô-đun 1024 bit. Tuy nhiên, người ta đã chỉ ra rằng việc dùng $d$ quá nhỏ dẫn đến nguy cơ hệ RSA bị phá hoàn toàn, làm mất an toàn của toàn bộ hệ thống.
- Định lý 2 (M. Wiener): Cho $N = p.q$ với điều kiện $q < p < 2q$. Nếu khóa bí mật $d$ thỏa mãn: $d < \frac{1}{3}N^{1/4}$, thì khi biết khóa công khai $(N, e)$ với $ed \equiv 1 \pmod{\phi(N)}$, người ta có thể khôi phục $d$ một cách hiệu quả.
* Theo định nghĩa của RSA, ta có phương trình đồng dư:
$ed \equiv 1 \pmod{\phi(N)}$ $\rightarrow$ tồn tại một số nguyên $k$ sao cho: $ed - k\phi(N) = 1$
Chia cả hai vế cho $d\phi(N)$, ta có:
$$\frac{e}{\phi(N)} - \frac{k}{d} = \frac{1}{d\phi(N)}$$
$\Rightarrow$
$$\left|\frac{e}{\phi(N)} - \frac{k}{d}\right| = \frac{1}{d\phi(N)}$$
* Ta có $\phi(N) = (p-1)(q-1) = N - p - q + 1$. Vì $p$ và $q$ là các số nguyên tố lớn xấp xỉ $\sqrt{N}$, nên chênh lệch giữa $N$ và $\phi(N)$ sẽ nhỏ:
$$|N - \phi(N)| < 3\sqrt{N}$$
* Thay $\phi(N)$ bằng $N$, ta có:
$$\left|\frac{e}{N} - \frac{k}{d}\right| = \left|\frac{ed - kN}{Nd}\right| = \left|\frac{1 + k\phi(N) - kN}{Nd}\right| = \left|\frac{1 - k(N - \phi(N))}{Nd}\right|$$
Sử dụng bất đẳng thức $|N - \phi(N)| < 3\sqrt{N}$, ta có chặn trên:
$$\le \left|\frac{3k\sqrt{N}}{Nd}\right| = \frac{3k}{d\sqrt{N}}$$
* Theo giả thuyết, ta có $d < \frac{1}{3}N^{1/4}$.
Vì $k < d$ (do $e < \phi(N)$), ta suy ra:
$$\left|\frac{e}{N} - \frac{k}{d}\right| \le \frac{1}{dN^{1/4}} < \frac{1}{2d^2}$$
Sau đó áp dụng định lý về dãy hội tụ liên phân số, ta tìm trong dãy hội tụ của khai triển liên phân số $\frac{e}{N}$ sẽ tìm được $\frac{k}{d}$. Bằng cách thử từng cặp $\frac{k}{d}$ này, ta tính $\phi(N)=\frac{e.d-1}{k}$. Lúc này ta có:
$p+q = n - \phi(n)+1$ và $p.q = n$
Dùng Vi-et đảo ta tính được p, q.Thử lại xem nếu $p.q=N$ thì đó là cặp p, q cần tìm. Tìm được p, q sẽ tính được d
- Để tránh tấn công này, các phương pháp an toàn gồm:
+ Chọn $e$ lớn để $k$ lớn ($k = \frac{ed - 1}{\varphi(N)}$)
+ Dùng CRT với các giá trị $d_p= d \mod(p-1)$ và $d_p = d \mod (q-1)$ nhỏ để tăng tốc độ giải mã mà vẫn giữ $d$ lớn .
- Cải tiến sau này bởi Boneh và Durfee chỉ ra rằng cuộc tấn công vẫn khả thi nếu $d< N^{0.292}$ .
- **Open Problem 2:** Giả sử $N = pq$ và $d < N^{0.5}$ . Nếu Marvin được cho khoá công khai $(N,e)$ với điều kiện $ed\equiv 1\ (\mod\phi(N))$ và $e< \phi(N)$, thì liệu Marvin có thể khôi phục $d$ một cách hiệu quả không ?
* Có vẻ câu trả lời là có, nhưng đây vẫn còn là một vấn đề mở
## Hastad's broadcast attack
- **Tình huống:** Giả sử Bob muốn gửi cùng một bức thư $M$ cho một nhóm người.Mỗi người nhận có một N riêng: $N_1, N_2, N_3$, nhưng lại dùng chung một e nhỏ, ví dụ $e = 3$ .Bob mã hóa tin nhắn $M$ cho từng người và gửi đi $C_1, C_2, C_3$:$$C_1 \equiv M^3 \pmod{N_1}$$$$C_2 \equiv M^3 \pmod{N_2}$$$$C_3 \equiv M^3 \pmod{N_3}$$
- Marvin thu thập $k$ bản mã $C_i$ của cùng một tin nhắn $M$ được gửi đến $k$ người dùng khác nhau, mỗi người dùng có khóa $\langle N_i, e \rangle$ riêng, với số mũ công khai $e$ nhỏ và chung cho tất cả (ví dụ, $e=3$).
Vì các mô‑đun $N_i$ đôi một nguyên tố cùng nhau, nên Marvin có thể dùng CRT(định lý phần dư Trung Hoa) gộp các bản mã thành một giá trị $C'$ sao cho $C'\equiv M^3\ (\mod\ N_1 N_2 N_3)$ .
+ Do $M$ nhỏ hơn tất cả các $N_i$, ta có $M^3 < N_1 N_2 N_3$ hay $C'= M^3$.
+ Từ đó Marvin chỉ cần lấy căn bậc 3 của $C'$ để thu được $M$ .
* **Theorem 6 (Hastad):** Cho $N_1, N_2, ..., N_k$ là các số nguyên tố cùng nhau từng đôi một và $N_{min} = min_i (N_i)$(số nhỏ nhất trong các modulo N). Tiếp tục cho $g_i \in \mathbb{Z}_{N_i}[x]$ là $k$ đa thức khác nhau, mỗi đa thức nằm trong vành số nguyên modulo $N_i$. $d$ là bậc lớn nhất trong các đa thức $g_i$. Giả sử tồn tại $M < N_{min}$ thõa mãn $g_i(M) \equiv 0 \pmod{N_i}$ với mọi $i$ sao cho $1 \leq i \leq k$. Với điều kiện $k>d$, có thể tìm lại $M$ một cách hiệu quả nếu được cho $\langle N_i, g_i \rangle_{i=1}^k$.
* **Proof:**
* Gọi $\bar{N}$ là tích của $N_1, N_2, \dots , N_k$, giả sử tất cả các đa thức $g_i(x)$ đều là monic(có hệ số cao nhất là 1) (Nếu ở đây, hệ số cao nhất của $g_i$ không khả nghịch($gcd(hệ số, N_i) > 1$), có thể tìm được trực tiếp thừa số của $N_i$ luôn.)
* Nhân thêm x cào vác đa thức có bậc thấp hơn để đảm bảo tất cả các $g_i(x)$ đều có bậc là $d$
* Các đa thức được xây dựng như sau: $$g(x) = \sum_{i=1}^{k} T_i \cdot g_i(x)$$
Trong đó: $T_i \equiv 1 \pmod{N_i}$ (với mọi $j = i$) và $T_i \equiv 0 \pmod{N_j}$ (với mọi $j \neq i$)
Ta có: M là nghiệm của từng phương trình $g_i(M) \equiv 0 \bmod{N_i}$, suy ra $g(M) \equiv 0 \pmod{\bar{N}}$
Người ta chứng minh được là có thể tìm được $M$ hiệu quả nếu $|M| < \bar{N}^{1/d}$. Mà theo như giả thuyết ban đầu, $M < N_{min}$, mà $N_{min} \le \bar{N}^{1/k}$ \rightarrow $M \le \bar{N}^{1/k}$. Tiếp tục giả thuyết có $k > d$, nên: $M < \bar{N}^{1/d}$
* Cách phòng thủ:
* Không dùng fixed pad.
* Dùng Randomized Pad.
## Franklin-Reiter Related Message Attack
Ngược lại với Hastad, Franklin-Reiter Related Message Attack tấn công vào việc gửi hai message có liên quan cho cùng 1 người (dùng chung N). Đặt N, e là public key của Alice, Bob muốn gửi cho Alice 2 message là $M_1$ và $M_2$ sao cho $M_1 = f(M_2) \bmod N$ (quan hệ tuyến tính). Marvin là attacker có được 2 bản mã $C_1 \equiv M_1^e \pmod N$ và $C_2 \equiv M_2^e \pmod N$.
Marvin muốn tìm nghiệm chung của 2 đa thức, Marvin xây dụng 2 phương trình mà $M_2$ là nghiệm.
Từ $C_2$, có $C_2 = M_2^e$.$\rightarrow M_2$ là nghiệm của đa thức:$g_2(x) = x^e - C_2 \pmod N$
Từ $C_1$: có $C_1 = M_1^e$, mà $M_1 = f(M_2)$.Thay vào ta có $C_1 = (f(M_2))^e$.$\rightarrow M_2$ cũng là nghiệm của đa thức:$g_1(x) = (f(x))^e - C_1 \pmod N$
Do $x = M_2$ là nghiệm chung của $g_1(x)$ và $g_2(x)$ $\Leftrightarrow x-M_2$ là nghiệm chung của $g_1(x)$ và $g_2(x)$
Vậy, Marvin chỉ cần tính $gcd(g_1(x), g_2(x))= x-M_2$ => M2 => M1
## Bleichenbacher's Attack on PKCS 1
Đây là cách tấn công khác nhất trong toàn bộ file, vì nó không tấn công vào các dạng toán học của RSA, mà tấn công vào cách cài đặt và padding.
Trước khi mã hóa RSA, $M$ thường được đệm thêm các byte ngẫu nhiên để đủ độ dài bằng độ dài của modulus $N$
Cấu trúc được quy định theo chuẩn PKCS 1 như sau:
| 02 | Random | 00 | $M$ |
| :--- | :--- | :--- | :--- |
Hai byte đầu tiên laf`00` và `02` là bắt buột. Mỗi khi giải mã, server sẽ kiểm tra xem kết quả có bắt đầu bằng `00 02` hay không. Bleichenbacher phát hiện ra rằng cách server phản hồi khi giải mã tạo ra một lỗ hổng có thể lợi dụng để tìm ra $M$. Cụ thể,khi Marvin gửi một bản mã rác $C'$ đến server:
* Server giải mã $C'$ ra $M'$.
* Server kiểm tra 2 byte đầu của $M'$.
* Trường hợp 1: Nếu $M'$ không bắt đầu bằng `00 02`, máy chủ trả về thông báo lỗi: "Invalid Ciphertext".
* Trường hợp 2: Nếu $M'$ bắt đầu bằng `00 02`, máy chủ tiếp tục xử lý.
* $\rightarrow$ Kết luận: Máy chủ vô tình trở thành mộtphương tiện cho Marvin biết một bản mã bất kỳ sau khi giải mã có bắt đầu bằng `00 02` hay không.
Giả sử Marvin có được bản mã C, nhưng không có d. Marvin có thể dùng Oracle để đoán ra $M$.
Đầu tiên, chọn 1 số ngẫu nhiên $r$, tạo ra $C'$ bằng cách nhân C với r. Sau đó gửi C' cho server. Nếu kết quả trả về là không lỗi, có nghĩa là C' có 16 bit đầu tiên là `00 02`. Marvin sẽ lặp lại quá trình này hàng triệu lần với các r khác nhau, càng nhiều phản hồi hợp lệ, khoảng giá trị của $M$ sẽ được thu hẹp dần, đến khi chỉ còn lại 1 giá trị, đó là $M$. Cách bleichenbacher hoạt động tương tự như binary search nhưng phức tạp hơn, vì hiệu quả còn tùy thuộc vào chất lượng của s.
# Thực hành
## STARTER
### Modular Exponentiation
Challange giới thiệu phép lũy thừa modulo và hàm pow(base, exponent, modulus) trong python. Để giải challange, cần tính $101^{17} \bmod 22663$
code như sau:
```=python
print(pow(101,17,22663))
```
được flag là `19906`
### Public Keys
Challange giới thiệu quá trình encrypt trong RSA yêu cầu encrypt messange là 12 với e=65537, p=17 và q=23.
Code như sau
```=python
print(pow(12,65537,17*23))
```
được flag là `301`
### Euler's Totient
Dựa vào hàm phi Euler, do p và q là số nguyên tố, nên $N=p.q$ thì $\phi(N)=(p-1)(q-1)$
Flag: `882564595536224140639625987657529300394956519977044270821168`
### Private Keys
Challange yêu cầu tìm nghịch đảo modul của e, nên ta dùng hàm pow trong python, code như sau:
```=python
p = 857504083339712752489993810777
q = 1029224947942998075080348647219
e= 65537
phi = (p-1)*(q-1)
print(pow(e,-1,phi))
```
được flag là `121832886702415731577073962957377780195510499965398469843281`
### RSA Decryption
Challange cho biết đã encrypt message và yêu cầu dùng private key của challange trước để decrypt ciphertext đề cung cấp thành message.
Code như sau:
```=python
p = 857504083339712752489993810777
q = 1029224947942998075080348647219
e= 65537
phi = (p-1)*(q-1)
d = (pow(e,-1,phi))
N = 882564595536224140639625987659416029426239230804614613279163
c = 77578995801157823671636298847186723593814843845525223303932
m = pow(c,d,N)
print(m)
```
flag: `13371337`
### RSA Signatures
Challange đặt ra tình huống cần phải sign message bằng crypto. Để sign message, cần băm message thành chuỗi hash SHA256 bằng cách dùng hàm SHA256 mà đề cho, sau đó chuyển chuỗi byte thành số nguyên lớn bằng hàm `bytes_to_long()`, cuối cùng tính $S = H(m)^{d} \bmod N$
code như sau:
```=python
from Crypto.Hash import SHA256
from Crypto.Util.number import bytes_to_long
N = 15216583654836731327639981224133918855895948374072384050848479908982286890731769486609085918857664046075375253168955058743185664390273058074450390236774324903305663479046566232967297765731625328029814055635316002591227570271271445226094919864475407884459980489638001092788574811554149774028950310695112688723853763743238753349782508121985338746755237819373178699343135091783992299561827389745132880022259873387524273298850340648779897909381979714026837172003953221052431217940632552930880000919436507245150726543040714721553361063311954285289857582079880295199632757829525723874753306371990452491305564061051059885803
d = 11175901210643014262548222473449533091378848269490518850474399681690547281665059317155831692300453197335735728459259392366823302405685389586883670043744683993709123180805154631088513521456979317628012721881537154107239389466063136007337120599915456659758559300673444689263854921332185562706707573660658164991098457874495054854491474065039621922972671588299315846306069845169959451250821044417886630346229021305410340100401530146135418806544340908355106582089082980533651095594192031411679866134256418292249592135441145384466261279428795408721990564658703903787956958168449841491667690491585550160457893350536334242689
m = b"crypto{Immut4ble_m3ssag1ng}"
Hm = (bytes_to_long(SHA256.new(m).digest()))
s = pow(Hm,d,N)
print(s)
```
flag: `13480738404590090803339831649238454376183189744970683129909766078877706583282422686710545217275797376709672358894231550335007974983458408620258478729775647818876610072903021235573923300070103666940534047644900475773318682585772698155617451477448441198150710420818995347235921111812068656782998168064960965451719491072569057636701190429760047193261886092862024118487826452766513533860734724124228305158914225250488399673645732882077575252662461860972889771112594906884441454355959482925283992539925713424132009768721389828848907099772040836383856524605008942907083490383109757406940540866978237471686296661685839083475`
## Primes Part 1
### Factoring
Đề bài giới thiệu tầm quan trọng của kích thước khóa trong RSA. Ngày nay, việc sử dụng các số nguyên tố có độ dài ít nhất 1024 bit được khuyến nghị. RSA với một mô-đun 2048-bit được gọi là RSA-2048.
Challge yêu cầu factorise `510143758735509025530880200653196460532653147` thành 2 số nguyên tố.
Do `510143758735509025530880200653196460532653147` quá lớn, mình dùng https://sagecell.sagemath.org/ để chạy. Kết quả trả về 2 số nguyên, số nhỏ hơn trong 2 số là`19704762736204164635843`
Flag: `19704762736204164635843`
code:
```=python
factor(510143758735509025530880200653196460532653147)
```
### Inferius Prime
Do n vẫn nằm trong khoảng có thể tách được bằng factor, nên ta sẽ dùng factor để lấy p và q, sau đó thính phi, d, và kết quả cuối cùng. Dùng `.to_bytes()` để lấy flag có dạng crypto{...}
```
n = 984994081290620368062168960884976209711107645166770780785733
e = 65537
ct = 948553474947320504624302879933619818331484350431616834086273
fac = factor(n)
phi = ((fac[0][0]-1)*(fac[1][0]-1))
d=pow(e,-1,phi)
k = pow(ct,d,n)
k.to_bytes((k.bit_length() + 7) // 8).decode()
```
flag: `crypto{N33d_b1g_pR1m35}`
### Monoprime
Challange này nói về lý do tại sao không nên chỉ dùng một số nguyên tố cho cả hệ thống RSA $(p=q=N)$. Vì nếu N là số nguyên tố thì $\phi(N)=N-1$, và attacker sẽ dễ dàng tìm ra được message. Challange này giải tương tự các bài trước
Code như sau:
```=python
from Crypto.Util.number import inverse, bytes_to_long, long_to_bytes
e = 0x10001
n = 171731371218065444125482536302245915415603318380280392385291836472299752747934607246477508507827284075763910264995326010251268493630501989810855418416643352631102434317900028697993224868629935657273062472544675693365930943308086634291936846505861203914449338007760990051788980485462592823446469606824421932591
phi = (n - 1)
d = inverse(e, phi)
ct = 161367550346730604451454756189028938964941280347662098798775466019463375610700074840105776873791605070092554650190486030367121011578171525759600774739890458414593857709994072516290998135846956596662071379067305011746842247628316996977338024343628757374524136260758515864509435302781735938531030576289086798942
pt = pow(ct, d, n)
res = long_to_bytes(pt).decode()
print(res)
```
ta được flag: `crypto{0n3_pr1m3_41n7_pr1m3_l0l}`
### Square Eyes
Challange này giải tương tự các bài trước, n được cho là một số chính phương, nên $q=\sqrt{N}$, dùng `math.isqrt()` để tìm q, sau đó tính phi bằng công thức $\phi(N)=p.(p-1)$
Code như sau:
```=python
from Crypto.Util.number import inverse, bytes_to_long, long_to_bytes
import math
n = 535860808044009550029177135708168016201451343147313565371014459027743491739422885443084705720731409713775527993719682583669164873806842043288439828071789970694759080842162253955259590552283047728782812946845160334801782088068154453021936721710269050985805054692096738777321796153384024897615594493453068138341203673749514094546000253631902991617197847584519694152122765406982133526594928685232381934742152195861380221224370858128736975959176861651044370378539093990198336298572944512738570839396588590096813217791191895941380464803377602779240663133834952329316862399581950590588006371221334128215409197603236942597674756728212232134056562716399155080108881105952768189193728827484667349378091100068224404684701674782399200373192433062767622841264055426035349769018117299620554803902490432339600566432246795818167460916180647394169157647245603555692735630862148715428791242764799469896924753470539857080767170052783918273180304835318388177089674231640910337743789750979216202573226794240332797892868276309400253925932223895530714169648116569013581643192341931800785254715083294526325980247219218364118877864892068185905587410977152737936310734712276956663192182487672474651103240004173381041237906849437490609652395748868434296753449
e = 65537
ct = 222502885974182429500948389840563415291534726891354573907329512556439632810921927905220486727807436668035929302442754225952786602492250448020341217733646472982286222338860566076161977786095675944552232391481278782019346283900959677167026636830252067048759720251671811058647569724495547940966885025629807079171218371644528053562232396674283745310132242492367274184667845174514466834132589971388067076980563188513333661165819462428837210575342101036356974189393390097403614434491507672459254969638032776897417674577487775755539964915035731988499983726435005007850876000232292458554577437739427313453671492956668188219600633325930981748162455965093222648173134777571527681591366164711307355510889316052064146089646772869610726671696699221157985834325663661400034831442431209123478778078255846830522226390964119818784903330200488705212765569163495571851459355520398928214206285080883954881888668509262455490889283862560453598662919522224935145694435885396500780651530829377030371611921181207362217397805303962112100190783763061909945889717878397740711340114311597934724670601992737526668932871436226135393872881664511222789565256059138002651403875484920711316522536260604255269532161594824301047729082877262812899724246757871448545439896
p = math.isqrt(n)
phi = p*(p-1)
d = inverse(e, phi)
pt = pow(ct, d, n)
decrypted = long_to_bytes(pt)
print(decrypted.decode())
```
Flag nhận được là: `crypto{squar3_r00t_i5_f4st3r_th4n_f4ct0r1ng!}`
### Manyprime
Dùng ecm.factor(n) trong sage sẽ có được mảng các nhân tử của n, từ đó tính được phi bằng công thức $\phi(N) = (p_1-1).(p_2-1).(p_3-1). ... .(p_n-1)$, $d = e^{-1} \bmod \phi(N)$. Từ đó tính được $M=ct^d \bmod N$
```=python
from Crypto.Util.number import long_to_bytes
n = 580642391898843192929563856870897799650883152718761762932292482252152591279871421569162037190419036435041797739880389529593674485555792234900969402019055601781662044515999210032698275981631376651117318677368742867687180140048715627160641771118040372573575479330830092989800730105573700557717146251860588802509310534792310748898504394966263819959963273509119791037525504422606634640173277598774814099540555569257179715908642917355365791447508751401889724095964924513196281345665480688029639999472649549163147599540142367575413885729653166517595719991872223011969856259344396899748662101941230745601719730556631637
e = 65537
ct = 320721490534624434149993723527322977960556510750628354856260732098109692581338409999983376131354918370047625150454728718467998870322344980985635149656977787964380651868131740312053755501594999166365821315043312308622388016666802478485476059625888033017198083472976011719998333985531756978678758897472845358167730221506573817798467100023754709109274265835201757369829744113233607359526441007577850111228850004361838028842815813724076511058179239339760639518034583306154826603816927757236549096339501503316601078891287408682099750164720032975016814187899399273719181407940397071512493967454225665490162619270814464
factor=[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]
phi=1
for i in factor:
phi*=i-1
d=pow(e,-1,phi)
cgt=long_to_bytes(pow(ct, d, n)).decode()
print(cgt)
```
và ta nhận được flag là: `crypto{700_m4ny_5m4ll_f4c70r5}`
## PUBLIC EXPONENT
### Salty
Ở challange này, ta thấy $e=1$, vậy suy ra $d$ cũng bằng 1, vậy $M=ct \bmod n$, mà ct đề cho xấp xỉ $10^{77}$ nhỏ hơn nhiều với n (xấp xỉ $10^{309}$). Vậy nên, có thể kết luận $M=ct$, việc ta cần làm chỉ là chuyển ct từ long về byte và decode. Có thể code như sau:
``` =python
from Crypto.Util.number import long_to_bytes
ct = 44981230718212183604274785925793145442655465025264554046028251311164494127485
decrypted = long_to_bytes(ct).decode()
print(decrypted)
```
và nhận được flag: `crypto{saltstack_fell_for_this!}`
### Modulus Inutilis
mở file output đề cho thì ta được
```c
n = 17258212916191948536348548470938004244269544560039009244721959293554822498047075403658429865201816363311805874117705688359853941515579440852166618074161313773416434156467811969628473425365608002907061241714688204565170146117869742910273064909154666642642308154422770994836108669814632309362483307560217924183202838588431342622551598499747369771295105890359290073146330677383341121242366368309126850094371525078749496850520075015636716490087482193603562501577348571256210991732071282478547626856068209192987351212490642903450263288650415552403935705444809043563866466823492258216747445926536608548665086042098252335883
e = 3
ct = 243251053617903760309941844835411292373350655973075480264001352919865180151222189820473358411037759381328642957324889519192337152355302808400638052620580409813222660643570085177957
```
Do e = 3 và ct lại quá nhỏ so với n, nên $ct^e \bmod N = ct^e$, việc cần làm là lấy căn bậc 3 của ct, sau đó chuyển từ long thành byte để lấy flag. Vì ct quá lớn, không thể lấy căn theo cách thông thường nên mình sẽ viết một hàm binary search tìm căn bậc 3 của ct.
```=python
from Crypto.Util.number import long_to_bytes
import gmpy2
ct = 243251053617903760309941844835411292373350655973075480264001352919865180151222189820473358411037759381328642957324889519192337152355302808400638052620580409813222660643570085177957
r, e = gmpy2.iroot(ct,3)
m = long_to_bytes(r).decode()
print(m)
```
ta được flag cần tìm là: `crypto{N33d_m04R_p4dd1ng}`
### Everything is Big
File output có nội dung như sau:
```c
N = 0xb8af3d3afb893a602de4afe2a29d7615075d1e570f8bad8ebbe9b5b9076594cf06b6e7b30905b6420e950043380ea746f0a14dae34469aa723e946e484a58bcd92d1039105871ffd63ffe64534b7d7f8d84b4a569723f7a833e6daf5e182d658655f739a4e37bd9f4a44aff6ca0255cda5313c3048f56eed5b21dc8d88bf5a8f8379eac83d8523e484fa6ae8dbcb239e65d3777829a6903d779cd2498b255fcf275e5f49471f35992435ee7cade98c8e82a8beb5ce1749349caa16759afc4e799edb12d299374d748a9e3c82e1cc983cdf9daec0a2739dadcc0982c1e7e492139cbff18c5d44529407edfd8e75743d2f51ce2b58573fea6fbd4fe25154b9964d
e = 0x9ab58dbc8049b574c361573955f08ea69f97ecf37400f9626d8f5ac55ca087165ce5e1f459ef6fa5f158cc8e75cb400a7473e89dd38922ead221b33bc33d6d716fb0e4e127b0fc18a197daf856a7062b49fba7a86e3a138956af04f481b7a7d481994aeebc2672e500f3f6d8c581268c2cfad4845158f79c2ef28f242f4fa8f6e573b8723a752d96169c9d885ada59cdeb6dbe932de86a019a7e8fc8aeb07748cfb272bd36d94fe83351252187c2e0bc58bb7a0a0af154b63397e6c68af4314601e29b07caed301b6831cf34caa579eb42a8c8bf69898d04b495174b5d7de0f20cf2b8fc55ed35c6ad157d3e7009f16d6b61786ee40583850e67af13e9d25be3
c = 0x3f984ff5244f1836ed69361f29905ca1ae6b3dcf249133c398d7762f5e277919174694293989144c9d25e940d2f66058b2289c75d1b8d0729f9a7c4564404a5fd4313675f85f31b47156068878e236c5635156b0fa21e24346c2041ae42423078577a1413f41375a4d49296ab17910ae214b45155c4570f95ca874ccae9fa80433a1ab453cbb28d780c2f1f4dc7071c93aff3924d76c5b4068a0371dff82531313f281a8acadaa2bd5078d3ddcefcb981f37ff9b8b14c7d9bf1accffe7857160982a2c7d9ee01d3e82265eec9c7401ecc7f02581fd0d912684f42d1b71df87a1ca51515aab4e58fab4da96e154ea6cdfb573a71d81b2ea4a080a1066e1bc3474
```
Đọc file output đề cho, ta nhận thấy giá trị của e khá lớn, xấp xỉ N và c, do $e.d = 1 \bmod \phi(N)$, nên suy ra giá trị của d khá nhỏ. Dựa vào điều này, có thể nghĩ đến dùng wiener's attack để giải bài này tìm d => M. Gemini đã gợi ý dùng thư viện `owiener` để đơn giản hóa code. Nhập giá trị tương ứng của N, e, c vào, code như sau:
```=python
from Crypto.Util.number import long_to_bytes
import owiener
N = 0x8da7d2ec7bf9b322a539afb9962d4d2ebeb3e3d449d709b80a51dc680a14c87ffa863edfc7b5a2a542a0fa610febe2d967b58ae714c46a6eccb44cd5c90d1cf5e271224aa3367e5a13305f2744e2e56059b17bf520c95d521d34fdad3b0c12e7821a3169aa900c711e6923ca1a26c71fc5ac8a9ff8c878164e2434c724b68b508a030f86211c1307b6f90c0cd489a27fdc5e6190f6193447e0441a49edde165cf6074994ea260a21ea1fc7e2dfb038df437f02b9ddb7b5244a9620c8eca858865e83bab3413135e76a54ee718f4e431c29d3cb6e353a75d74f831bed2cc7bdce553f25b617b3bdd9ef901e249e43545c91b0cd8798b27804d61926e317a2b745
e = 0x86d357db4e1b60a2e9f9f25e2db15204c820b6e8d8d04d29db168c890bc8a6c1e31b9316c9680174e128515a00256b775a1a8ccca9c6936f1b4c2298c03032cda4dd8eca1145828d31466bf56bfcf0c6a8b4a1b2fb27de7a57fae7430048d7590734b2f05b6443ad60d89606802409d2fa4c6767ad42bffae01a8ef1364418362e133fa7b2770af64a68ad50ad8d2bd5cebb99ceb13368fb31a6e7503e753f8638e21a96af1b6498c18578ba89b98d70fa482ad137d28fe701b4b77baa25d5e84c81b26ee9bddf8cbb51a071c60dd57714de379cd4bc14932809ba18524a0a18e4133665cfc46e2c4fcfbc28e0a0957e5513a7307c422b87a6182d0b6a074b4d
c = 0x6a2f2e401a54eeb5dab1e6d5d80e92a6ca189049e22844c825012b8f0578f95b269b19644c7c8af3d544840d380ed75fdf86844aa8976622fa0501eaec0e5a1a5ab09d3d1037e55501c4e270060470c9f4019ced6c4e67673843daf2fd71c64f3dd8939ae322f2b79d283b3382052d076ebe9bb50b0042f1f7dd7beadf0f5686926ade9fc8370283ead781a21896e7a878d99e77c3bb1f470401062c0e0327fd85da1cf12901635f1df310e8f8c7d87aff5a01dbbecd739cd8f36462060d0eb237af8d613e2d9cebb67d612bcfc353ef2cd44b7ac85e471287eb04ae9b388b66ea8eb32429ae96dba5da8206894fa8c58a7440a127fceb5717a2eaa3c29f25f7
d = owiener.attack(e, N)
print(long_to_bytes(pow(c, d, N)).decode())
```
và ta được flag: `crypto{s0m3th1ng5_c4n_b3_t00_b1g}`
### Crossed Wires
File output đề cho có nội dung như sau:
```
My private key: (21711308225346315542706844618441565741046498277716979943478360598053144971379956916575370343448988601905854572029635846626259487297950305231661109855854947494209135205589258643517961521594924368498672064293208230802441077390193682958095111922082677813175804775628884377724377647428385841831277059274172982280545237765559969228707506857561215268491024097063920337721783673060530181637161577401589126558556182546896783307370517275046522704047385786111489447064794210010802761708615907245523492585896286374996088089317826162798278528296206977900274431829829206103227171839270887476436899494428371323874689055690729986771, 2734411677251148030723138005716109733838866545375527602018255159319631026653190783670493107936401603981429171880504360560494771017246468702902647370954220312452541342858747590576273775107870450853533717116684326976263006435733382045807971890762018747729574021057430331778033982359184838159747331236538501849965329264774927607570410347019418407451937875684373454982306923178403161216817237890962651214718831954215200637651103907209347900857824722653217179548148145687181377220544864521808230122730967452981435355334932104265488075777638608041325256776275200067541533022527964743478554948792578057708522350812154888097)
My Friend's public keys: [(21711308225346315542706844618441565741046498277716979943478360598053144971379956916575370343448988601905854572029635846626259487297950305231661109855854947494209135205589258643517961521594924368498672064293208230802441077390193682958095111922082677813175804775628884377724377647428385841831277059274172982280545237765559969228707506857561215268491024097063920337721783673060530181637161577401589126558556182546896783307370517275046522704047385786111489447064794210010802761708615907245523492585896286374996088089317826162798278528296206977900274431829829206103227171839270887476436899494428371323874689055690729986771, 106979), (21711308225346315542706844618441565741046498277716979943478360598053144971379956916575370343448988601905854572029635846626259487297950305231661109855854947494209135205589258643517961521594924368498672064293208230802441077390193682958095111922082677813175804775628884377724377647428385841831277059274172982280545237765559969228707506857561215268491024097063920337721783673060530181637161577401589126558556182546896783307370517275046522704047385786111489447064794210010802761708615907245523492585896286374996088089317826162798278528296206977900274431829829206103227171839270887476436899494428371323874689055690729986771, 108533), (21711308225346315542706844618441565741046498277716979943478360598053144971379956916575370343448988601905854572029635846626259487297950305231661109855854947494209135205589258643517961521594924368498672064293208230802441077390193682958095111922082677813175804775628884377724377647428385841831277059274172982280545237765559969228707506857561215268491024097063920337721783673060530181637161577401589126558556182546896783307370517275046522704047385786111489447064794210010802761708615907245523492585896286374996088089317826162798278528296206977900274431829829206103227171839270887476436899494428371323874689055690729986771, 69557), (21711308225346315542706844618441565741046498277716979943478360598053144971379956916575370343448988601905854572029635846626259487297950305231661109855854947494209135205589258643517961521594924368498672064293208230802441077390193682958095111922082677813175804775628884377724377647428385841831277059274172982280545237765559969228707506857561215268491024097063920337721783673060530181637161577401589126558556182546896783307370517275046522704047385786111489447064794210010802761708615907245523492585896286374996088089317826162798278528296206977900274431829829206103227171839270887476436899494428371323874689055690729986771, 97117), (21711308225346315542706844618441565741046498277716979943478360598053144971379956916575370343448988601905854572029635846626259487297950305231661109855854947494209135205589258643517961521594924368498672064293208230802441077390193682958095111922082677813175804775628884377724377647428385841831277059274172982280545237765559969228707506857561215268491024097063920337721783673060530181637161577401589126558556182546896783307370517275046522704047385786111489447064794210010802761708615907245523492585896286374996088089317826162798278528296206977900274431829829206103227171839270887476436899494428371323874689055690729986771, 103231)]
Encrypted flag: 20304610279578186738172766224224793119885071262464464448863461184092225736054747976985179673905441502689126216282897704508745403799054734121583968853999791604281615154100736259131453424385364324630229671185343778172807262640709301838274824603101692485662726226902121105591137437331463201881264245562214012160875177167442010952439360623396658974413900469093836794752270399520074596329058725874834082188697377597949405779039139194196065364426213208345461407030771089787529200057105746584493554722790592530472869581310117300343461207750821737840042745530876391793484035024644475535353227851321505537398888106855012746117
```
Bài này đề cho một cặp N, d và 5 cặp khóa N, e nhưng tất cả đều dùng chung một modulo N, nên có thể dự đoán hướng giải của bài này sẽ sử dụng Common modul. Dựa vào fact 1 và phần proof của fact 1 trong file tài liệu, code như sau
```=python
from math import gcd
from Crypto.Util.number import long_to_bytes
N = 21711308225346315542706844618441565741046498277716979943478360598053144971379956916575370343448988601905854572029635846626259487297950305231661109855854947494209135205589258643517961521594924368498672064293208230802441077390193682958095111922082677813175804775628884377724377647428385841831277059274172982280545237765559969228707506857561215268491024097063920337721783673060530181637161577401589126558556182546896783307370517275046522704047385786111489447064794210010802761708615907245523492585896286374996088089317826162798278528296206977900274431829829206103227171839270887476436899494428371323874689055690729986771
d = 2734411677251148030723138005716109733838866545375527602018255159319631026653190783670493107936401603981429171880504360560494771017246468702902647370954220312452541342858747590576273775107870450853533717116684326976263006435733382045807971890762018747729574021057430331778033982359184838159747331236538501849965329264774927607570410347019418407451937875684373454982306923178403161216817237890962651214718831954215200637651103907209347900857824722653217179548148145687181377220544864521808230122730967452981435355334932104265488075777638608041325256776275200067541533022527964743478554948792578057708522350812154888097
e = [106979, 108533, 69557, 97117, 103231]
c = 20304610279578186738172766224224793119885071262464464448863461184092225736054747976985179673905441502689126216282897704508745403799054734121583968853999791604281615154100736259131453424385364324630229671185343778172807262640709301838274824603101692485662726226902121105591137437331463201881264245562214012160875177167442010952439360623396658974413900469093836794752270399520074596329058725874834082188697377597949405779039139194196065364426213208345461407030771089787529200057105746584493554722790592530472869581310117300343461207750821737840042745530876391793484035024644475535353227851321505537398888106855012746117
et = 65537
k = et*d - 1
g=2
p=0
q=0
for i in range(5):
x = pow(g, k//pow(2, i), N)
y = gcd(x - 1, N)
if x != 1 and y != 1:
p = y
q = N // y
break
phi = (p - 1) * (q - 1)
dt = []
for i in range(5):
dt.append(pow(e[i], -1, phi))
m = pow(c, dt[4], N)
for i in range(4):
m = pow(m, dt[3 - i], N)
print(long_to_bytes(m).decode())
```
và ta được flag: `crypto{3ncrypt_y0ur_s3cr3t_w1th_y0ur_fr1end5_publ1c_k3y}`
### Everything is Still Big
Nội dung file output:
```
N = 0xb12746657c720a434861e9a4828b3c89a6b8d4a1bd921054e48d47124dbcc9cfcdcc39261c5e93817c167db818081613f57729e0039875c72a5ae1f0bc5ef7c933880c2ad528adbc9b1430003a491e460917b34c4590977df47772fab1ee0ab251f94065ab3004893fe1b2958008848b0124f22c4e75f60ed3889fb62e5ef4dcc247a3d6e23072641e62566cd96ee8114b227b8f498f9a578fc6f687d07acdbb523b6029c5bbeecd5efaf4c4d35304e5e6b5b95db0e89299529eb953f52ca3247d4cd03a15939e7d638b168fd00a1cb5b0cc5c2cc98175c1ad0b959c2ab2f17f917c0ccee8c3fe589b4cb441e817f75e575fc96a4fe7bfea897f57692b050d2b
e = 0x9d0637faa46281b533e83cc37e1cf5626bd33f712cc1948622f10ec26f766fb37b9cd6c7a6e4b2c03bce0dd70d5a3a28b6b0c941d8792bc6a870568790ebcd30f40277af59e0fd3141e272c48f8e33592965997c7d93006c27bf3a2b8fb71831dfa939c0ba2c7569dd1b660efc6c8966e674fbe6e051811d92a802c789d895f356ceec9722d5a7b617d21b8aa42dd6a45de721953939a5a81b8dffc9490acd4f60b0c0475883ff7e2ab50b39b2deeedaefefffc52ae2e03f72756d9b4f7b6bd85b1a6764b31312bc375a2298b78b0263d492205d2a5aa7a227abaf41ab4ea8ce0e75728a5177fe90ace36fdc5dba53317bbf90e60a6f2311bb333bf55ba3245f
c = 0xa3bce6e2e677d7855a1a7819eb1879779d1e1eefa21a1a6e205c8b46fdc020a2487fdd07dbae99274204fadda2ba69af73627bdddcb2c403118f507bca03cb0bad7a8cd03f70defc31fa904d71230aab98a10e155bf207da1b1cac1503f48cab3758024cc6e62afe99767e9e4c151b75f60d8f7989c152fdf4ff4b95ceed9a7065f38c68dee4dd0da503650d3246d463f504b36e1d6fafabb35d2390ecf0419b2bb67c4c647fb38511b34eb494d9289c872203fa70f4084d2fa2367a63a8881b74cc38730ad7584328de6a7d92e4ca18098a15119baee91237cea24975bdfc19bdbce7c1559899a88125935584cd37c8dd31f3f2b4517eefae84e7e588344fa5
```
Đề bài lần này tiếp tục là một e lớn, thử dùng wiener's attack một lần nữa:
```
import owiener
from Crypto.Util.number import long_to_bytes
N = 0xb12746657c720a434861e9a4828b3c89a6b8d4a1bd921054e48d47124dbcc9cfcdcc39261c5e93817c167db818081613f57729e0039875c72a5ae1f0bc5ef7c933880c2ad528adbc9b1430003a491e460917b34c4590977df47772fab1ee0ab251f94065ab3004893fe1b2958008848b0124f22c4e75f60ed3889fb62e5ef4dcc247a3d6e23072641e62566cd96ee8114b227b8f498f9a578fc6f687d07acdbb523b6029c5bbeecd5efaf4c4d35304e5e6b5b95db0e89299529eb953f52ca3247d4cd03a15939e7d638b168fd00a1cb5b0cc5c2cc98175c1ad0b959c2ab2f17f917c0ccee8c3fe589b4cb441e817f75e575fc96a4fe7bfea897f57692b050d2b
e = 0x9d0637faa46281b533e83cc37e1cf5626bd33f712cc1948622f10ec26f766fb37b9cd6c7a6e4b2c03bce0dd70d5a3a28b6b0c941d8792bc6a870568790ebcd30f40277af59e0fd3141e272c48f8e33592965997c7d93006c27bf3a2b8fb71831dfa939c0ba2c7569dd1b660efc6c8966e674fbe6e051811d92a802c789d895f356ceec9722d5a7b617d21b8aa42dd6a45de721953939a5a81b8dffc9490acd4f60b0c0475883ff7e2ab50b39b2deeedaefefffc52ae2e03f72756d9b4f7b6bd85b1a6764b31312bc375a2298b78b0263d492205d2a5aa7a227abaf41ab4ea8ce0e75728a5177fe90ace36fdc5dba53317bbf90e60a6f2311bb333bf55ba3245f
c = 0xa3bce6e2e677d7855a1a7819eb1879779d1e1eefa21a1a6e205c8b46fdc020a2487fdd07dbae99274204fadda2ba69af73627bdddcb2c403118f507bca03cb0bad7a8cd03f70defc31fa904d71230aab98a10e155bf207da1b1cac1503f48cab3758024cc6e62afe99767e9e4c151b75f60d8f7989c152fdf4ff4b95ceed9a7065f38c68dee4dd0da503650d3246d463f504b36e1d6fafabb35d2390ecf0419b2bb67c4c647fb38511b34eb494d9289c872203fa70f4084d2fa2367a63a8881b74cc38730ad7584328de6a7d92e4ca18098a15119baee91237cea24975bdfc19bdbce7c1559899a88125935584cd37c8dd31f3f2b4517eefae84e7e588344fa5
d = owiener.attack(e, N)
print(long_to_bytes(pow(c, d, N)).decode())import owiener
```
ta được flag là : `crypto{bon3h5_4tt4ck_i5_sr0ng3r_th4n_w13n3r5}`
### Endless Emails
File output:
```
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
```
Ta có thể thấy đề cho 7 N, e, c nhưng chung 1 giá trị e là 3, mình sẽ nghĩ ngay đến dùng hastad và CRT để giải bài này.
```=python
import libnum
from gmpy2 import iroot
from Crypto.Util.number import long_to_bytes
n1 = 14528915758150659907677315938876872514853653132820394367681510019000469589767908107293777996420037715293478868775354645306536953789897501630398061779084810058931494642860729799059325051840331449914529594113593835549493208246333437945551639983056810855435396444978249093419290651847764073607607794045076386643023306458718171574989185213684263628336385268818202054811378810216623440644076846464902798568705083282619513191855087399010760232112434412274701034094429954231366422968991322244343038458681255035356984900384509158858007713047428143658924970374944616430311056440919114824023838380098825914755712289724493770021
c1 = 6965891612987861726975066977377253961837139691220763821370036576350605576485706330714192837336331493653283305241193883593410988132245791554283874785871849223291134571366093850082919285063130119121338290718389659761443563666214229749009468327825320914097376664888912663806925746474243439550004354390822079954583102082178617110721589392875875474288168921403550415531707419931040583019529612270482482718035497554779733578411057633524971870399893851589345476307695799567919550426417015815455141863703835142223300228230547255523815097431420381177861163863791690147876158039619438793849367921927840731088518955045807722225
n2 = 20463913454649855046677206889944639231694511458416906994298079596685813354570085475890888433776403011296145408951323816323011550738170573801417972453504044678801608709931200059967157605416809387753258251914788761202456830940944486915292626560515250805017229876565916349963923702612584484875113691057716315466239062005206014542088484387389725058070917118549621598629964819596412564094627030747720659155558690124005400257685883230881015636066183743516494701900125788836869358634031031172536767950943858472257519195392986989232477630794600444813136409000056443035171453870906346401936687214432176829528484662373633624123
c2 = 5109363605089618816120178319361171115590171352048506021650539639521356666986308721062843132905170261025772850941702085683855336653472949146012700116070022531926476625467538166881085235022484711752960666438445574269179358850309578627747024264968893862296953506803423930414569834210215223172069261612934281834174103316403670168299182121939323001232617718327977313659290755318972603958579000300780685344728301503641583806648227416781898538367971983562236770576174308965929275267929379934367736694110684569576575266348020800723535121638175505282145714117112442582416208209171027273743686645470434557028336357172288865172
n3 = 19402640770593345339726386104915705450969517850985511418263141255686982818547710008822417349818201858549321868878490314025136645036980129976820137486252202687238348587398336652955435182090722844668488842986318211649569593089444781595159045372322540131250208258093613844753021272389255069398553523848975530563989367082896404719544411946864594527708058887475595056033713361893808330341623804367785721774271084389159493974946320359512776328984487126583015777989991635428744050868653379191842998345721260216953918203248167079072442948732000084754225272238189439501737066178901505257566388862947536332343196537495085729147
c3 = 5603386396458228314230975500760833991383866638504216400766044200173576179323437058101562931430558738148852367292802918725271632845889728711316688681080762762324367273332764959495900563756768440309595248691744845766607436966468714038018108912467618638117493367675937079141350328486149333053000366933205635396038539236203203489974033629281145427277222568989469994178084357460160310598260365030056631222346691527861696116334946201074529417984624304973747653407317290664224507485684421999527164122395674469650155851869651072847303136621932989550786722041915603539800197077294166881952724017065404825258494318993054344153
n4 = 12005639978012754274325188681720834222130605634919280945697102906256738419912110187245315232437501890545637047506165123606573171374281507075652554737014979927883759915891863646221205835211640845714836927373844277878562666545230876640830141637371729405545509920889968046268135809999117856968692236742804637929866632908329522087977077849045608566911654234541526643235586433065170392920102840518192803854740398478305598092197183671292154743153130012885747243219372709669879863098708318993844005566984491622761795349455404952285937152423145150066181043576492305166964448141091092142224906843816547235826717179687198833961
c4 = 1522280741383024774933280198410525846833410931417064479278161088248621390305797210285777845359812715909342595804742710152832168365433905718629465545306028275498667935929180318276445229415104842407145880223983428713335709038026249381363564625791656631137936935477777236936508600353416079028339774876425198789629900265348122040413865209592074731028757972968635601695468594123523892918747882221891834598896483393711851510479989203644477972694520237262271530260496342247355761992646827057846109181410462131875377404309983072358313960427035348425800940661373272947647516867525052504539561289941374722179778872627956360577
n5 = 17795451956221451086587651307408104001363221003775928432650752466563818944480119932209305765249625841644339021308118433529490162294175590972336954199870002456682453215153111182451526643055812311071588382409549045943806869173323058059908678022558101041630272658592291327387549001621625757585079662873501990182250368909302040015518454068699267914137675644695523752851229148887052774845777699287718342916530122031495267122700912518207571821367123013164125109174399486158717604851125244356586369921144640969262427220828940652994276084225196272504355264547588369516271460361233556643313911651916709471353368924621122725823
c5 = 8752507806125480063647081749506966428026005464325535765874589376572431101816084498482064083887400646438977437273700004934257274516197148448425455243811009944321764771392044345410680448204581679548854193081394891841223548418812679441816502910830861271884276608891963388657558218620911858230760629700918375750796354647493524576614017731938584618983084762612414591830024113057983483156974095503392359946722756364412399187910604029583464521617256125933111786441852765229820406911991809039519015434793656710199153380699319611499255869045311421603167606551250174746275803467549814529124250122560661739949229005127507540805
n6 = 25252721057733555082592677470459355315816761410478159901637469821096129654501579313856822193168570733800370301193041607236223065376987811309968760580864569059669890823406084313841678888031103461972888346942160731039637326224716901940943571445217827960353637825523862324133203094843228068077462983941899571736153227764822122334838436875488289162659100652956252427378476004164698656662333892963348126931771536472674447932268282205545229907715893139346941832367885319597198474180888087658441880346681594927881517150425610145518942545293750127300041942766820911120196262215703079164895767115681864075574707999253396530263
c6 = 23399624135645767243362438536844425089018405258626828336566973656156553220156563508607371562416462491581383453279478716239823054532476006642583363934314982675152824147243749715830794488268846671670287617324522740126594148159945137948643597981681529145611463534109482209520448640622103718682323158039797577387254265854218727476928164074249568031493984825273382959147078839665114417896463735635546290504843957780546550577300001452747760982468547756427137284830133305010038339400230477403836856663883956463830571934657200851598986174177386323915542033293658596818231793744261192870485152396793393026198817787033127061749
n7 = 19833203629283018227011925157509157967003736370320129764863076831617271290326613531892600790037451229326924414757856123643351635022817441101879725227161178559229328259469472961665857650693413215087493448372860837806619850188734619829580286541292997729705909899738951228555834773273676515143550091710004139734080727392121405772911510746025807070635102249154615454505080376920778703360178295901552323611120184737429513669167641846902598281621408629883487079110172218735807477275590367110861255756289520114719860000347219161944020067099398239199863252349401303744451903546571864062825485984573414652422054433066179558897
c7 = 15239683995712538665992887055453717247160229941400011601942125542239446512492703769284448009141905335544729440961349343533346436084176947090230267995060908954209742736573986319254695570265339469489948102562072983996668361864286444602534666284339466797477805372109723178841788198177337648499899079471221924276590042183382182326518312979109378616306364363630519677884849945606288881683625944365927809405420540525867173639222696027472336981838588256771671910217553150588878434061862840893045763456457939944572192848992333115479951110622066173007227047527992906364658618631373790704267650950755276227747600169403361509144
N = [n1, n2, n3, n4, n5, n6, n7]
C = [c1, c2, c3, c4, c5, c6, c7]
res = libnum.solve_crt(C, N)
m, mu = iroot(res, 3)
print(long_to_bytes(m))
```
khi run code này thì kết quả là
```
b'\x01-*\x10\x9fq\x80ON\xffR\x0fP\xe0\x17\x95\x17\xa6\tg\xb9|\xf2\\\x1b\x87\xf9)\xe3\xb8D\x878\xf1aI\xbe\x1b\xcf#\x0b5\x81\x06\x91sE\xc4A\x93:\xeb\x89\xf9\x87\x9a\xfa\x18\x930\xbf\xc1wE\xcd\x187?\xf4^\x0b\xc3\xffB\x93\x80\x94\xc1L\xcf2V\xc8\x92\x8b\xfc\xcc\x17\x8a\xdd\xf1\xb2\x85\xc5k\xb2\xf2\x98J\xcf\xc4ci)\x9a\xf9%\xf7\xaa\xf1\xba\xc7\xde\n\xc8\x1c\xfez\x03H\xc8l\x8b\x07\x85\x1dO2\xc1\x87\x878\x1b2\xa3]\x81r\xe1\xc4\x98\xf4S\x1a\xc5D\xc9\x01p&\xba\xecfzX&)u\x92\xf4\x9b~NX\xcc\xa9\x88\x18|e\xe7a\xfb\x00\xa21\x9ex\x87\xf4"\xe9\x19\xc2u5\xc5\xc76|\x1c$/\xac,\x15\xc22\xe8\xad\xbe\xc9\x8b\xb7\xaeaA\x12\x0bl7\xcc\xed7\x85B\x80j\xbfD\xc4\'\x19+\xc6\xcd\x86\x8a\x16\x932\xbcm\xa1\x03M\x13\xd4$\x88UQ\x00\xf0z\xfe\xbf\xe6\x96\x16\xc7^~a\xd8+K\xd6.\xdd\xef\xbe\xcePw\xe1\xbaa\x1a\xd2\xf0b\x8d\x7f~\x8bA6\xd0\xe1rlh\xfa\xfb\xd8G\x92\xa4\xf7u\xf3j\x9e9\xbb\xd3\x85zT\x82\xe56\xb8rG\xd8\xdbH%\xe3OJ\xec\xdb\x0b\x82\xed\xfe\x07\xd7\xe6@\xbf\\W\xe8i\x8d\x89\xe0\x15\x846\xb5/)O\xd0\xb4\xa9\x02\xce\xf1Y\xb6\x10\xaf\x84\x14\x03\xad\xe2\xd6/\xa9M\x9e\xf8\xf5\x80\x16\x15,QJ\x8c@.,}y\xd9\x93\xa4[\x0b{p\xf5l\xe2\n1>\xfd\x91\xc5\xd9\xc1\xf7\x7f25n\xbb\x9a\xf5\xeb;\xb2\x83D\xbat]\xec\xce#\x01\x96\xab\x93O\xd9{W\xe7\x84\x93\\q\x00\x18\x8f\xd8\xef\xcb\xf6R\x06\xf8\xe8Z\xba\xd0\'\xf3\xd3\xf5lL\x04\x15\xc6\xde\xcc\x18\xcb\xa3\x90\xa6\xa7\xf0\xcer\xf9[-R3\xadf\xe3\xff BUAG$\xc3\xd8\xa6\x8f\xef\xa7\x88\\Nk\xa3;\x12\x90\x00:\xe6+\xce\xe4,\x18\x8f\xb0\xd9\xd2\xfd\x7f\xf3\xb8]\x89\x12\xfe\x94[\xa2\x16gG\xca\x14=}<L\xf4\x90#\x06~m\x1bGJ<\x13j\xb93\x9e\x1f\xab\x1c\xa0\xc5\x8e\xd01\x00\xd2]\xc0=\xe90\x9cj\x0e^)\xf3\xfc"\x81S\xb6t\x8b\xe8\x02)\x8fQ\xa6%s1y\x82\xff\xe7V\x14\xc4\xea\x02\xe7c\xf5v\x7f\xf9\xf4\xfb\x13s\xf3\xf9\x96a\xdd-\xbb\xb8\x1a\xde
```
Đây không phải là format đúng của flag, nên đã có gì đó sai trong bài này, mình thử lại bằng cách lấy crt từng bộ ba phương trình, vì chỉ có 7 phương trình nên mình sẽ duyệt 3 vòng for, code lại như sau:
```=python
import libnum
from gmpy2 import iroot
from Crypto.Util.number import long_to_bytes
n1 = 14528915758150659907677315938876872514853653132820394367681510019000469589767908107293777996420037715293478868775354645306536953789897501630398061779084810058931494642860729799059325051840331449914529594113593835549493208246333437945551639983056810855435396444978249093419290651847764073607607794045076386643023306458718171574989185213684263628336385268818202054811378810216623440644076846464902798568705083282619513191855087399010760232112434412274701034094429954231366422968991322244343038458681255035356984900384509158858007713047428143658924970374944616430311056440919114824023838380098825914755712289724493770021
c1 = 6965891612987861726975066977377253961837139691220763821370036576350605576485706330714192837336331493653283305241193883593410988132245791554283874785871849223291134571366093850082919285063130119121338290718389659761443563666214229749009468327825320914097376664888912663806925746474243439550004354390822079954583102082178617110721589392875875474288168921403550415531707419931040583019529612270482482718035497554779733578411057633524971870399893851589345476307695799567919550426417015815455141863703835142223300228230547255523815097431420381177861163863791690147876158039619438793849367921927840731088518955045807722225
n2 = 20463913454649855046677206889944639231694511458416906994298079596685813354570085475890888433776403011296145408951323816323011550738170573801417972453504044678801608709931200059967157605416809387753258251914788761202456830940944486915292626560515250805017229876565916349963923702612584484875113691057716315466239062005206014542088484387389725058070917118549621598629964819596412564094627030747720659155558690124005400257685883230881015636066183743516494701900125788836869358634031031172536767950943858472257519195392986989232477630794600444813136409000056443035171453870906346401936687214432176829528484662373633624123
c2 = 5109363605089618816120178319361171115590171352048506021650539639521356666986308721062843132905170261025772850941702085683855336653472949146012700116070022531926476625467538166881085235022484711752960666438445574269179358850309578627747024264968893862296953506803423930414569834210215223172069261612934281834174103316403670168299182121939323001232617718327977313659290755318972603958579000300780685344728301503641583806648227416781898538367971983562236770576174308965929275267929379934367736694110684569576575266348020800723535121638175505282145714117112442582416208209171027273743686645470434557028336357172288865172
n3 = 19402640770593345339726386104915705450969517850985511418263141255686982818547710008822417349818201858549321868878490314025136645036980129976820137486252202687238348587398336652955435182090722844668488842986318211649569593089444781595159045372322540131250208258093613844753021272389255069398553523848975530563989367082896404719544411946864594527708058887475595056033713361893808330341623804367785721774271084389159493974946320359512776328984487126583015777989991635428744050868653379191842998345721260216953918203248167079072442948732000084754225272238189439501737066178901505257566388862947536332343196537495085729147
c3 = 5603386396458228314230975500760833991383866638504216400766044200173576179323437058101562931430558738148852367292802918725271632845889728711316688681080762762324367273332764959495900563756768440309595248691744845766607436966468714038018108912467618638117493367675937079141350328486149333053000366933205635396038539236203203489974033629281145427277222568989469994178084357460160310598260365030056631222346691527861696116334946201074529417984624304973747653407317290664224507485684421999527164122395674469650155851869651072847303136621932989550786722041915603539800197077294166881952724017065404825258494318993054344153
n4 = 12005639978012754274325188681720834222130605634919280945697102906256738419912110187245315232437501890545637047506165123606573171374281507075652554737014979927883759915891863646221205835211640845714836927373844277878562666545230876640830141637371729405545509920889968046268135809999117856968692236742804637929866632908329522087977077849045608566911654234541526643235586433065170392920102840518192803854740398478305598092197183671292154743153130012885747243219372709669879863098708318993844005566984491622761795349455404952285937152423145150066181043576492305166964448141091092142224906843816547235826717179687198833961
c4 = 1522280741383024774933280198410525846833410931417064479278161088248621390305797210285777845359812715909342595804742710152832168365433905718629465545306028275498667935929180318276445229415104842407145880223983428713335709038026249381363564625791656631137936935477777236936508600353416079028339774876425198789629900265348122040413865209592074731028757972968635601695468594123523892918747882221891834598896483393711851510479989203644477972694520237262271530260496342247355761992646827057846109181410462131875377404309983072358313960427035348425800940661373272947647516867525052504539561289941374722179778872627956360577
n5 = 17795451956221451086587651307408104001363221003775928432650752466563818944480119932209305765249625841644339021308118433529490162294175590972336954199870002456682453215153111182451526643055812311071588382409549045943806869173323058059908678022558101041630272658592291327387549001621625757585079662873501990182250368909302040015518454068699267914137675644695523752851229148887052774845777699287718342916530122031495267122700912518207571821367123013164125109174399486158717604851125244356586369921144640969262427220828940652994276084225196272504355264547588369516271460361233556643313911651916709471353368924621122725823
c5 = 8752507806125480063647081749506966428026005464325535765874589376572431101816084498482064083887400646438977437273700004934257274516197148448425455243811009944321764771392044345410680448204581679548854193081394891841223548418812679441816502910830861271884276608891963388657558218620911858230760629700918375750796354647493524576614017731938584618983084762612414591830024113057983483156974095503392359946722756364412399187910604029583464521617256125933111786441852765229820406911991809039519015434793656710199153380699319611499255869045311421603167606551250174746275803467549814529124250122560661739949229005127507540805
n6 = 25252721057733555082592677470459355315816761410478159901637469821096129654501579313856822193168570733800370301193041607236223065376987811309968760580864569059669890823406084313841678888031103461972888346942160731039637326224716901940943571445217827960353637825523862324133203094843228068077462983941899571736153227764822122334838436875488289162659100652956252427378476004164698656662333892963348126931771536472674447932268282205545229907715893139346941832367885319597198474180888087658441880346681594927881517150425610145518942545293750127300041942766820911120196262215703079164895767115681864075574707999253396530263
c6 = 23399624135645767243362438536844425089018405258626828336566973656156553220156563508607371562416462491581383453279478716239823054532476006642583363934314982675152824147243749715830794488268846671670287617324522740126594148159945137948643597981681529145611463534109482209520448640622103718682323158039797577387254265854218727476928164074249568031493984825273382959147078839665114417896463735635546290504843957780546550577300001452747760982468547756427137284830133305010038339400230477403836856663883956463830571934657200851598986174177386323915542033293658596818231793744261192870485152396793393026198817787033127061749
n7 = 19833203629283018227011925157509157967003736370320129764863076831617271290326613531892600790037451229326924414757856123643351635022817441101879725227161178559229328259469472961665857650693413215087493448372860837806619850188734619829580286541292997729705909899738951228555834773273676515143550091710004139734080727392121405772911510746025807070635102249154615454505080376920778703360178295901552323611120184737429513669167641846902598281621408629883487079110172218735807477275590367110861255756289520114719860000347219161944020067099398239199863252349401303744451903546571864062825485984573414652422054433066179558897
c7 = 15239683995712538665992887055453717247160229941400011601942125542239446512492703769284448009141905335544729440961349343533346436084176947090230267995060908954209742736573986319254695570265339469489948102562072983996668361864286444602534666284339466797477805372109723178841788198177337648499899079471221924276590042183382182326518312979109378616306364363630519677884849945606288881683625944365927809405420540525867173639222696027472336981838588256771671910217553150588878434061862840893045763456457939944572192848992333115479951110622066173007227047527992906364658618631373790704267650950755276227747600169403361509144
N = [n1, n2, n3, n4, n5, n6, n7]
C = [c1, c2, c3, c4, c5, c6, c7]
for i in range(5):
for j in range(i + 1, 6):
for k in range(j + 1, 7):
n1 = [N[i], N[j], N[k]]
c1 = [C[i], C[j], C[k]]
res = libnum.solve_crt(c1, n1)
m, is_exact = iroot(res, 3)
if is_exact:
print(long_to_bytes(m).decode())
```
Run code được kết quả là:
> 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}
Vậy, ta có flag: `crypto{1f_y0u_d0nt_p4d_y0u_4r3_Vuln3rabl3}`
## Primes Part 2
### Infinite Descent
File output của đề bài có nội dung như sau:
```
n = 383347712330877040452238619329524841763392526146840572232926924642094891453979246383798913394114305368360426867021623649667024217266529000859703542590316063318592391925062014229671423777796679798747131250552455356061834719512365575593221216339005132464338847195248627639623487124025890693416305788160905762011825079336880567461033322240015771102929696350161937950387427696385850443727777996483584464610046380722736790790188061964311222153985614287276995741553706506834906746892708903948496564047090014307484054609862129530262108669567834726352078060081889712109412073731026030466300060341737504223822014714056413752165841749368159510588178604096191956750941078391415634472219765129561622344109769892244712668402761549412177892054051266761597330660545704317210567759828757156904778495608968785747998059857467440128156068391746919684258227682866083662345263659558066864109212457286114506228470930775092735385388316268663664139056183180238043386636254075940621543717531670995823417070666005930452836389812129462051771646048498397195157405386923446893886593048680984896989809135802276892911038588008701926729269812453226891776546037663583893625479252643042517196958990266376741676514631089466493864064316127648074609662749196545969926051
e = 65537
c = 98280456757136766244944891987028935843441533415613592591358482906016439563076150526116369842213103333480506705993633901994107281890187248495507270868621384652207697607019899166492132408348789252555196428608661320671877412710489782358282011364127799563335562917707783563681920786994453004763755404510541574502176243896756839917991848428091594919111448023948527766368304503100650379914153058191140072528095898576018893829830104362124927140555107994114143042266758709328068902664037870075742542194318059191313468675939426810988239079424823495317464035252325521917592045198152643533223015952702649249494753395100973534541766285551891859649320371178562200252228779395393974169736998523394598517174182142007480526603025578004665936854657294541338697513521007818552254811797566860763442604365744596444735991732790926343720102293453429936734206246109968817158815749927063561835274636195149702317415680401987150336994583752062565237605953153790371155918439941193401473271753038180560129784192800351649724465553733201451581525173536731674524145027931923204961274369826379325051601238308635192540223484055096203293400419816024111797903442864181965959247745006822690967920957905188441550106930799896292835287867403979631824085790047851383294389
```
Bài này sử dụng e là 65537 nên không có gì để khai thác. N quá lớn không thể dùng factor như bình thường, có khả năng bài này sẽ được khai thác từ N. Thử dùng Fermat’s attack để giải
```=python
from Crypto.Util.number import long_to_bytes
import gmpy2
n = 383347712330877040452238619329524841763392526146840572232926924642094891453979246383798913394114305368360426867021623649667024217266529000859703542590316063318592391925062014229671423777796679798747131250552455356061834719512365575593221216339005132464338847195248627639623487124025890693416305788160905762011825079336880567461033322240015771102929696350161937950387427696385850443727777996483584464610046380722736790790188061964311222153985614287276995741553706506834906746892708903948496564047090014307484054609862129530262108669567834726352078060081889712109412073731026030466300060341737504223822014714056413752165841749368159510588178604096191956750941078391415634472219765129561622344109769892244712668402761549412177892054051266761597330660545704317210567759828757156904778495608968785747998059857467440128156068391746919684258227682866083662345263659558066864109212457286114506228470930775092735385388316268663664139056183180238043386636254075940621543717531670995823417070666005930452836389812129462051771646048498397195157405386923446893886593048680984896989809135802276892911038588008701926729269812453226891776546037663583893625479252643042517196958990266376741676514631089466493864064316127648074609662749196545969926051
e = 65537
c = 98280456757136766244944891987028935843441533415613592591358482906016439563076150526116369842213103333480506705993633901994107281890187248495507270868621384652207697607019899166492132408348789252555196428608661320671877412710489782358282011364127799563335562917707783563681920786994453004763755404510541574502176243896756839917991848428091594919111448023948527766368304503100650379914153058191140072528095898576018893829830104362124927140555107994114143042266758709328068902664037870075742542194318059191313468675939426810988239079424823495317464035252325521917592045198152643533223015952702649249494753395100973534541766285551891859649320371178562200252228779395393974169736998523394598517174182142007480526603025578004665936854657294541338697513521007818552254811797566860763442604365744596444735991732790926343720102293453429936734206246109968817158815749927063561835274636195149702317415680401987150336994583752062565237605953153790371155918439941193401473271753038180560129784192800351649724465553733201451581525173536731674524145027931923204961274369826379325051601238308635192540223484055096203293400419816024111797903442864181965959247745006822690967920957905188441550106930799896292835287867403979631824085790047851383294389
x = 2 * gmpy2.isqrt(n + 2 * gmpy2.isqrt(n))
y = gmpy2.isqrt(x*x - 4*n)
p = (x + y) // 2
q = (x - y) // 2
phi = (p-1)*(q-1)
d = pow(e, -1, phi)
m = pow(c, d, n)
print(long_to_bytes(m).decode())
```
Ta tìm được flag: `crypto{f3rm47_w45_4_g3n1u5}`
### Marin's Secrets
Trong file `marin.py`:
```=python
#!/usr/bin/env python3
import random
from Crypto.Util.number import bytes_to_long, inverse
from secret import secrets, flag
def get_prime(secret):
prime = 1
for _ in range(secret):
prime = prime << 1
return prime - 1
random.shuffle(secrets)
m = bytes_to_long(flag)
p = get_prime(secrets[0])
q = get_prime(secrets[1])
n = p * q
e = 0x10001
c = pow(m, e, n)
print(f"n = {n}")
print(f"e = {e}")
print(f"c = {c}")
```
Ta thấy 2 số nguyên tố p và q được tạo từ hàm get_prime và được dịch bit nên 2 số p và q sẽ có dạng là $2^x-1$, từ đó ta sẽ có $n = (2^a-1)(2^b-1)$ Vậy ta sẽ cho a chạy đến khi nào n chia hết cho $(2^a-1)$, từ đó tìm ra a,b => tìm ra p, q. Sau đó giải như bình thường
```=python
from Crypto.Util.number import long_to_bytes
n = 658416274830184544125027519921443515789888264156074733099244040126213682497714032798116399288176502462829255784525977722903018714434309698108208388664768262754316426220651576623731617882923164117579624827261244506084274371250277849351631679441171018418018498039996472549893150577189302871520311715179730714312181456245097848491669795997289830612988058523968384808822828370900198489249243399165125219244753790779764466236965135793576516193213175061401667388622228362042717054014679032953441034021506856017081062617572351195418505899388715709795992029559042119783423597324707100694064675909238717573058764118893225111602703838080618565401139902143069901117174204252871948846864436771808616432457102844534843857198735242005309073939051433790946726672234643259349535186268571629077937597838801337973092285608744209951533199868228040004432132597073390363357892379997655878857696334892216345070227646749851381208554044940444182864026513709449823489593439017366358869648168238735087593808344484365136284219725233811605331815007424582890821887260682886632543613109252862114326372077785369292570900594814481097443781269562647303671428895764224084402259605109600363098950091998891375812839523613295667253813978434879172781217285652895469194181218343078754501694746598738215243769747956572555989594598180639098344891175879455994652382137038240166358066403475457
e = 65537
c = 400280463088930432319280359115194977582517363610532464295210669530407870753439127455401384569705425621445943992963380983084917385428631223046908837804126399345875252917090184158440305503817193246288672986488987883177380307377025079266030262650932575205141853413302558460364242355531272967481409414783634558791175827816540767545944534238189079030192843288596934979693517964655661507346729751987928147021620165009965051933278913952899114253301044747587310830419190623282578931589587504555005361571572561916866063458812965314474160499067525067495140150092119620928363007467390920130717521169105167963364154636472055084012592138570354390246779276003156184676298710746583104700516466091034510765027167956117869051938116457370384737440965109619578227422049806566060571831017610877072484262724789571076529586427405780121096546942812322324807145137017942266863534989082115189065560011841150908380937354301243153206428896320576609904361937035263985348984794208198892615898907005955403529470847124269512316191753950203794578656029324506688293446571598506042198219080325747328636232040936761788558421528960279832802127562115852304946867628316502959562274485483867481731149338209009753229463924855930103271197831370982488703456463385914801246828662212622006947380115549529820197355738525329885232170215757585685484402344437894981555179129287164971002033759724456
a = 2
while True:
if n % (2**a - 1) == 0:
break
a = a + 1
p = 2**a - 1
q = n//p
phi = (p - 1)*(q - 1)
d = pow(e, -1, phi)
print(long_to_bytes(pow(c, d, n)).decode())
```
ta được flag: `crypto{Th3se_Pr1m3s_4r3_t00_r4r3}`
### Ron was Wrong, Whit is Right
Đề bài cho file `excerpt.py` có nội dung như sau:
```=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())
```
Ta thấy trong file, key được giấy trong file `21.pem`, nhưng mở file zip đề cho thì có tận 50 file pem, 50 file ciphertext. Mà trong resources đề cho có đề cập đến nhiều N có dùng chung thừa số nguyên tố, nên ta sẽ duyệt qua tất cả các file pem, sau đó tìm gcd thì ra được p, từ p tìm được q. N, e được giấu trong file `21.pem`.
Sau khi chuyển đuôi pem của `21.pem` thành ciphertext (21.ciphertext) thì file có nội dung sau:
```
-----BEGIN PUBLIC KEY-----
MIIEIjANBgkqhkiG9w0BAQEFAAOCBA8AMIIECgKCBAEA1dlvn9lQ5f+ZsWc1iPw6
HVY487KX7ASSJhZ4VMUGGkD+YVQnhTXLS7NWyL6qHu9tbx5pzyyC4jT65CjEeRaV
XTswGdH/kicZBLjBKUh0iayUfzASs4rYe3G62noWTDAtHs3+VBDMxGid+/TsgoxK
Qo/eTG7Evci9MdDUAgHhXAqQfM4Ot/HWlxogwikAs7SDyaZLNkxZFEKcqrS81udT
Nm0lsUceoNXBxb662iqFJN8Q7S4XYjYaDnScZdWc8HwhDnqStBJ1ATvVIXM9+AB3
rNlJ+GVG3kE7Azh59+1kKqdVRf9Zl0Ch65JUMLEpTKRQuBJxLzY2MbmbcxIv5bbB
EPz6a3iTQtquE49nqx07fEcxNoL1vCBa//MS4fBXYwTIT3W1irM8HQxB76MUlzp4
mSZnxHNWbLuA4kP79qwIzcxh1aUDYRYMp3mGlnJzLlUqhQJenFr5piNq03l1lRix
dCIjtso6eFgNv+MD1ndYsqL2ktFC0u6kvOVbyL4roW1m1STXcis5/BWTtnxe/o3m
TFClvzfvi6BWdK5m7vJ7Pp6bE8FEei81SBTGNX0B+K6W3DiaDOzwTr9amTaRzbSA
LtpXUBHbFEpKYlbBgCvX8uIB6L8IS5XQPtnPu+3dKXczLXu/hIRzJf6KQqwbL/xT
d6sSeXV/4t96dvtGoXh/fMR2CpHfSH5j3Akij9uQapvHwNyiL4t7Bd2+J3tYd0aX
94pg3wWtHhzXK5YEukLifyCh1Wf+T1EPD5d0sNKvCuFpzHHHPf6gGT2riWmgUv+Z
/eBrUJOSjEp7SD36JXML22T+rUT3ZGh76fzgjMpB1TUeY39OsmTPpNVEaymefxR8
8hxkpEed6PJTL58mj3ACFP+ZAX0DZMap6hReBqkZ+Y2KUbKmAeCDCMHwUGIekWZg
lRAKj0oqCyFpIv0abBc2SrEK1J9v5J2q/X4nk+uffHA+YhIt3q4r9kRryvzXc6+t
Qm1uggdgkrEM3zTtSPRhBsbqw2zjzTvy2naCUaFVKHoy/3clgR47zQUnYWp1epQg
cpPwjgQIipyA4d9gQx4eJq4pv/bal0zoDLFVwOMZINVl8S37lnffqjSmsmLMv6fa
pnPkcyXvxFWjtl8ltf7fzWPWGpJYdohtqxDr3Y1eXza53iSAnGUApQ/uwTPgTKhJ
DlF8M5lSLrUC2faYP229ySm/mf+u9XPudAZ26qW93aAQ8Seg9WCHWuCYXQapBiV6
wI1V6eU0TPXMKIElFe5qlBLrbuSm+i12qaMXuWC53yX4jLD/NILdrpvzELeM+426
BMUhR4Dvy+U64DjH+f9DjG9eI52ldA5lGLHS169mbQx+Zc108dyEc5MjRinPkXJu
jwIDAQAB
-----END PUBLIC KEY-----
```
Vậy ta sẽ tìm public key bằng cách chuyển nội dung trong file từ hex sang byte, sau đó tìm được flag. Code như sau:
```=python
from Crypto.Cipher import PKCS1_OAEP
from Crypto.PublicKey import RSA
from Crypto.Util.number import inverse, long_to_bytes
from gmpy2 import gcd
keys_and_messages = r"D:\\python\\TASK_2\\keys_and_messages"
keys = []
for i in range(1,51):
fn = f'{keys_and_messages}\\{i}.pem'
with open(fn, "rb") as f:
data = RSA.import_key(f.read())
keys.append(data.n)
with open(f'{keys_and_messages}\\{21}.pem', "rb") as f:
k = RSA.import_key(f.read())
n=k.n
e=k.e
p=0
for i in range(1,49):
for j in range(i+1,50):
t=gcd(keys[i], keys[j])
if t != 1:
p=t
break
q=n//p
phi = (p-1)*(q-1)
d = inverse(e, phi)
private_key = RSA.construct((int(n), int(e), int(d)))
cipher = PKCS1_OAEP.new(private_key)
cipherPath = f'{keys_and_messages}\\{21}.pem'.replace(".pem", ".ciphertext")
with open(cipherPath, "r") as f:
ciphertext = bytes.fromhex(f.read())
cgt = cipher.decrypt(ciphertext)
print(cgt.decode())
```
Run code ta được: `crypto{3ucl1d_w0uld_b3_pr0ud} If you haven't already, check out https://eprint.iacr.org/2012/064.pdf0` vậy flag là : `crypto{3ucl1d_w0uld_b3_pr0ud}`
## Padding
### Bespoke Padding
Đề bài cho file `13386.py` có nội dung như sau:
```=python
#!/usr/bin/env python3
from utils import listener
from Crypto.Util.number import bytes_to_long, getPrime
import random
FLAG = b'crypto{???????????????????????????}'
class Challenge():
def __init__(self):
self.before_input = "Come back as much as you want! You'll never get my flag.\n"
self.p = getPrime(1024)
self.q = getPrime(1024)
self.N = self.p * self.q
self.e = 11
def pad(self, flag):
m = bytes_to_long(flag)
a = random.randint(2, self.N)
b = random.randint(2, self.N)
return (a, b), a*m+b
def encrypt(self, flag):
pad_var, pad_msg = self.pad(flag)
encrypted = (pow(pad_msg, self.e, self.N), self.N)
return pad_var, encrypted
def challenge(self, your_input):
if not 'option' in your_input:
return {"error": "You must send an option to this server"}
elif your_input['option'] == 'get_flag':
pad_var, encrypted = self.encrypt(FLAG)
return {"encrypted_flag": encrypted[0], "modulus": encrypted[1], "padding": pad_var}
else:
return {"error": "Invalid option"}
"""
When you connect, the 'challenge' function will be called on your JSON
input.
"""
listener.start_server(port=13386)
```
Đọc source code trên thì thấy server tạo N=p*q với p, q 1024 bit, e=11. Khi gọi getflag thì server sinh ngẫu nhiên a,b, từ đó padding ngẫu nhiên $c = (a*m+b)^{11} \bmod N$.
$c = (a*m+b)^{11} = Σ C(11, i) . a^{11-i} . b^i . m^{11-i}$
$C(11, i)$ là hệ số gồm các số 1,11,55,165,330,462,462,330,165,55,11
Vậy, mỗi lần gọi server cho ta 1 đa thức bậc 11 theo m.
$c – b^{11} ≡ k_0.m^{11} + k_1.m^{10} + k_2.m^{9} + ... + k_{10}.m$
trong đó: $k_i = C(11, i) . a^(11-i) . b^i \bmod N$
Mỗi lần gọi server được 1 phương trình có dạng:
$k_0.m^{11} + k_1.m^{10} + ... + k_{10}.m = val \pmod N$
Ghép phương trình theo từng cặp:
$Eq1: k_0.m^{11} + k_1.m^{10} + ... + k_{10}.m = v1$
$Eq2: k_0.m^{11} + k_1.m^{10} + ... + k_{10}.m = v2$
Nhân Eq1 bởi l0, Eq2 bởi k0, rồi trừ:
$(k_0*l_0 - l_0*k_0)*m^{11} + ... → m^{11}$ bị triệt tiêu
Do cần triệt tiêu về còn 1 phương trình cuối cùng, mà e=11, nên ta phải gọi server 1024 lần.
Sau đó tìm m và long to byte để ra flag.
Code:
```=python
from pwn import *
import json
import sys
import ast
from Crypto.Util.number import inverse, long_to_bytes
data1 = []
N = None
r = remote('socket.cryptohack.org', 13386)
r.recvline()
for i in range(1024):
r.sendline('{"option":"get_flag"}')
item_dict = json.loads(r.recvline())
N = item_dict['modulus']
data1.append([item_dict['padding'], item_dict['encrypted_flag']])
print('recv', i, file=sys.stderr)
with open('datas-1.txt', 'w') as f:
print(data1, file=f)
with open('datas-2.txt', 'w') as f:
print(N, file=f)
with open('datas-1.txt') as f1, open('datas-2.txt') as f2:
data1 = ast.literal_eval(f1.read())
N = ast.literal_eval(f2.read())
heso = [1, 11, 55, 165, 330, 462, 462, 330, 165, 55, 11]
data2 = []
for item in data1:
(a, b), val = item
tmp = []
for i in range(11):
tmp.append((pow(a, 11 - i, N) * pow(b, i, N) * heso[i]) % N)
val = (val - pow(b, 11, N)) % N
data2.append([tmp, val])
while len(data2) > 1:
prev = data2
data2 = []
for i in range(0, len(prev), 2):
c0 = prev[i][0][0]
c1 = prev[i+1][0][0]
new_v = (prev[i][1] * c1 - prev[i+1][1] * c0) % N
new_c = []
for j in range(1, len(prev[i][0])):
new_c.append((prev[i][0][j] * c1 - prev[i+1][0][j] * c0) % N)
data2.append([new_c, new_v])
c, val = data2[0][0][0], data2[0][1]
flag = (val * inverse(c, N)) % N
print(long_to_bytes(flag).decode())
```
Ta được flag: `crypto{linear_padding_isnt_padding}`
### Null or never
Đề bài cho file `pad_encrypt.py` có nội dung như sau:
```=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}")
```
Vậy là ta đã biết độ dài thực tế của flag, đề bài nói rằng Flag sẽ được đệm thêm byte null (b'\x00') vào cuối cho đến khi độ dài đủ 100.
Giả sử $M$ ban đầu là $(M_{\text{thực}})$, sau khi bị padding bằng (k) byte null ở cuối thì $M = M_{\text{thực}} \cdot 2^{8k}$
Với $e=3$:
$$C \equiv M^3 \equiv (M_{\text{thực}} \cdot 2^{8k})^3 \equiv M_{\text{thực}}^3 \cdot 2^{24k} \pmod{N}$$
Suy ra:
$$C \equiv M_{\text{thực}}^3 \cdot 2^{24k} \pmod N$$
hay
$$C' \equiv C \cdot (2^{24k})^{-1} \pmod N$$
Khi đó:
$$C' \equiv M_{\text{thực}}^3 \pmod N$$
Vậy
$$M_{\text{thực}} = \sqrt[3]{C'}$$
Code như sau:
```=python
import gmpy2
from Crypto.Util.number import inverse
n = 95341235345618011251857577682324351171197688101180707030749869409235726634345899397258784261937590128088284421816891826202978052640992678267974129629670862991769812330793126662251062120518795878693122854189330426777286315442926939843468730196970939951374889986320771714519309125434348512571864406646232154103
e = 3
c = 63476139027102349822147098087901756023488558030079225358836870725611623045683759473454129221778690683914555720975250395929721681009556415292257804239149809875424000027362678341633901036035522299395660255954384685936351041718040558055860508481512479599089561391846007771856837130233678763953257086620228436828
FLAG = b"crypto{???????????????????????????????????}"
p = 8*(100 - len(FLAG))
a = inverse(2, n)
inv = pow(a, p * e, n)
rsa_enc = c * inv % n
for i in range(100):
ans = gmpy2.iroot(rsa_enc + i * n, 3)
m = long_to_bytes(ans[0])
if b"crypto{" in m:
print(m.decode())
break
```
Ta được flag: `crypto{n0n_574nd4rd_p4d_c0n51d3r3d_h4rmful}`
Sign in with Wallet
Connect another wallet