# 1. Lí thuyết
## Các khái niệm cơ bản:
- **Cryptography** (Mật mã học) là ngành khoa học nghiên cứu và thực hành các phương pháp bảo mật thông tin bằng cách sử dụng thuật toán để mã hóa thông tin sang dạng không thể đọc hiểu được, nhằm đảm bảo tính bí mật của thông tin.
- Ví dụ: Mình có một đoạn thông tin là chuỗi: ```PHAT``` và mình muốn gửi đi cho bạn B nhưng không muốn ai biết, mình sử dụng thuật toán mã hóa Caesar với phép chuyển sang phải 3 vị trí thì sẽ được chuỗi ```SKDW```, bạn B thì biết key là **3** nên sẽ lùi 3 vị trí và thu được chuỗi ```PHAT```
- **Cryptanalysis**: còn gọi là thám mã, là quá trình nghiên cứu và phá vỡ các hệ thống mật mã để khôi phục thông tin đã được mã hóa thành thông tin ban đầu mà ta không biết **key**.
- Ví dụ: như ví dụ ở trên, nếu như có một cryptanalyst đánh cắp được chuỗi ```SKDW``` thì họ có thể sẽ tiến hành giải mã bằng phương pháp như brute-force (vét cạn tất cả trường hợp) họ thử key từ 1-26 và họ có thể sẽ tìm được key là **3** và giải mã được đoạn thông tin gốc là ```PHAT```.
- **Encode**: (Mã hóa) là quá trình chuyển đổi dữ liệu từ định dạng này sang định dạng khác, thường để xử lý, lưu trữ, nén, hoặc truyền tải hiệu quả hơn
- Ví dụ: ta có thông tin gốc là ```xinchao123``` thì sau khi endcode thành hệ hex ta được ```78696e6368616f313233```
- **Decode**: (Giải mã) ngược lại với encode. Là quá trình chuyển đổi dữ liệu từ một định dạng đã được mã hóa sang định dạng chuẩn hoặc "thân thiện" với con người hơn.
- Ví dụ: chuyển đổi mã nhị phân ```11111010111``` thành ```2007``` được gọi là quá trình decode.
- **Encrypt**, hay mã hóa: là quá trình chuyển đổi thông tin từ dạng có thể đọc được (văn bản thuần) sang dạng không thể đọc được (văn bản mã hóa) bằng cách sử dụng các thuật toán và khóa mật mã, nhằm mục đích bảo vệ tính bảo mật của dữ liệu khi lưu trữ hoặc truyền tải.
- Ví dụ: mình có thông điệp ```iLoveCrypto``` và muốn gửi đi một cách an toàn, mình có thể sử dụng AES (Advanced Encryption Standard), thì thông điệp sau khi mã hóa sẽ trở thành `53616c7465645f5f54a8d6773837caf3c9710637ccbf547992a134038b88ffd2`, sẽ không thể biết được thông điệp gốc nếu không có key.
- **Decrypt** : (giải mã) là quá trình đảo ngược của encrypt, chuyển đổi dữ liệu đã được mã hóa (ciphertext) trở lại dạng có thể đọc hiểu được ban đầu (plaintext). Quá trình này thường yêu cầu sử dụng một hoặc nhiều key bí mật để thực hiện việc giải mã.
- **Symmetric Cryptography**: (Mã hóa khóa đối xứng) là một phương pháp mã hóa sử dụng cùng một khóa bí mật cho cả quá trình mã hóa và giải mã dữ liệu.
- Ví dụ: AES (Advanced Encryption Standard) là một thuật toán mã hóa đối xứng, nghĩa là nó sử dụng một khóa bí mật chung cho cả việc mã hóa và giải mã dữ liệu,
- **Asymmetric Cryptography:** là mã hóa bất đối xứng, việc mã hóa và giải mã sẽ cần nhiều hơn một khóa, cụ thể là một khóa công khai (public key) để mã hóa và một khóa riêng tư (private key) để giải mã, hoặc ngược lại. Khóa công khai có thể chia sẻ rộng rãi, còn khóa riêng tư phải được giữ bí mật.
- Ví dụ: RSA (Rivest-Shamir-Adleman) là một thuật toán mã hóa bất đối xứng. Tính bảo mật của RSA phụ thuộc vào độ khó của việc phân tích các số lớn thành thừa số nguyên tố của chúng.
- **Block Cipher** (mã hóa khối) là thuật toán mã hóa đối xứng hoạt động trên các khối dữ liệu có độ dài cố định (thường là 64 hoặc 128 bit), sử dụng một khóa bí mật để biến đổi từng khối plain text thành khối bản mã (cipher text) theo một phương pháp xác định.
- Ví dụ: Các thuật phổ biến về mã hóa khối bao gồm DES (Data Encryption Standard), mã hóa dữ liệu theo khối 64 bit. Và AES (Advanced Encryption Standard), mã hóa dữ liệu theo khối cố định 128 bit, với các tùy chọn kích thước khóa là 128, 192 hoặc 256 bit.
- **Stream Cipher** (mã hóa dòng): là một dạng mật mã đối xứng, xử lý từng bit hoặc từng byte của dữ liệu gốc một cách liên tục bằng cách kết hợp chúng với một dòng khóa (keystream) được tạo ra từ một khóa bí mật chung. Dòng khóa này có độ dài tương đương với dữ liệu và không được tái sử dụng để mã hóa các plain text khác.
- Ví dụ: một số thuật toán mã hóa dòng phổ biến là RC4 và SEAL.
- Hash Function: là một thuật toán dùng để chuyển đổi bất kỳ dữ liệu đầu vào nào (chuỗi ký tự, số, v.v.) thành một giá trị đầu ra có độ dài cố định, được gọi là giá trị băm (hash value).
- Ví dụ: hàm băm MD5 sẽ băm chuỗi ```iwannajoinKCSC``` thành ```5f8b3e4b01915168c6bc0d8746ba54a7```.
## Một số kiến thức toán học
## Cấu trúc đại số
### Phép toán hai ngôi
- Phép toán hai ngôi: với hai phần tử $a, b \in \text{G}$ mà $a \circ b \in \text{G}$ thì $\circ$ là một toán tử hai ngôi
> Lưu ý: $\circ$ là toán tử đại diện cho các toán tử cộng, nhân, ...
- Ví dụ: trên tập số nguyên $\mathbb{Z}$, thì phép cộng, trừ, nhân là toán tử hai ngôi nhưng phép chia thì không, $1 + 3 = 4 \in \mathbb{Z}$, $9 - 10 = -1 \in \mathbb{Z}$, $2.3 = 6 \in \mathbb{Z}$, $1 \div 4 = 0.25 \notin \mathbb{Z}$.
### Nhóm (Group)
- **Định nghĩa**: Với tập hợp G đã cho và phép toán hai ngôi $\circ$ được gọi là nhóm $(\text{G}, \circ)$ nếu $\forall a,b,c \in G$ thoả mản các tính chất:
1. $(a \circ b) \circ c = a \circ (b \circ c)\hspace{3mm}$ (Tính kết hợp)
2. $a \circ b \in G$ (Tính đóng)
3. ∃e sao cho $a \circ e = e \circ a = a$ (Phần tử đơn vị)
4. $a^{-1} \circ a = a \circ a^{-1} = e$ (Có nghịch đảo)
- Ví dụ: Tập $\mathbb{R}$ là một nhóm với phép cộng vì:
- $(a+b) + c =a + (b+c)$ (Tính kết hợp)
- $a + b \in \mathbb{R}$ (Tính đóng)
- Tồn tại phần tử đơn vị e là 0 vì: $0 + a = a + 0 = a$
- $a + -a = -a + a = 0$ (Có nghịch đảo)
- **Nhóm Abel (hoặc nhóm giao hoán)**: Nhóm $(\text{G}, \circ)$ được gọi là nhóm Abel khi ($\circ$) có tính giao hoán, tức là $a \circ b = b \circ a$
### Cấp của nhóm, phần tử
- Cấp của nhóm G chính là số phần tử của G.
- Bậc của phần tử $a \in G$ là **số nguyên dương m nhỏ nhất** thỏa mãn: $a^{m} = e$ (e là phần tử đơn vị của G)
> Chú ý: Nếu m không tồn tại thì a là phần tử có bậc vô hạn.
- Ví dụ: Trong nhóm ($\mathbb{R}^*$)với phép nhân:
+ Tập này có phần tử đơn vị e = 1.
+ Phần tử $1$ có bậc là $1$ vì $1^1 = 1 = e$.
+ Phần tử $-1$ có bậc là 2 vì $(-1)^2 = 1 = e$.
+ Còn $\forall a \in \mathbb{R} \backslash \{1, -1\}$ sẽ có bậc vô hạn.
- Ký hiệu cấp của nhóm G là ord(G) hoặc |G|, bậc của phần tử a được ký hiệu là ord(a) hoặc |a|.
- $\forall a \in G$, luôn có $ord(a)|ord(G)$
- Ví dụ: Cho nhóm $\mathbb{Z}^*_{10}$ (nhóm modulo với phép nhân):
- Ta có: $\mathbb{Z}^*_{10}$ = {1, 3, 7, 9} và e = 1
- Ví dụ cấp của 3 là 4 vì: $3^{4} \equiv 1 \hspace{2mm} (mod \hspace{2mm} 10)$, tương tự với các phần tử còn lại:
| a | 1 | 3 | 7 | 9 |
| --- | -------- | -------- | -------- | --- |
| ord(a) | 1 | 4 | 4 | 2 |
- Ta nhận thấy rằng $|\mathbb{Z}^*_{10}|$ = 4, nên bậc của mọi phần tử a luôn là ước của 4.
- Ngoài ra nếu ord(a) = $|\mathbb{Z}^*_{n}|$ = $\phi(n)$ thì a là phần tử sinh của $\mathbb{Z}^*_{n}$ (trong ví dụ trên ta có 2 phần tử sinhh 3 và 7)
- Định lý Lagrange: Nếu $S$ là nhóm con của $G$ thì $ord(S)|ord(G)$, tức là số lượng phần tử của S là ước số của số lượng phần tử của G.
### Nhóm vòng (nhóm cyclic)
- $G$ được gọi là nhóm cyclic nếu nó chứa một phần tử a nào đó mà mọi phần tử của $G$ đều là một lũy thừa nguyên của a. Ta gọi $a$ là phần tử sinh của $G$, kí hiệu $G = ⟨a⟩$.
- Ví dụ: $\mathbb{Z}_{19}^{*} = \left\{1,2,3,4,5, 6, 7, 8, 9 ...,18\right\} = ⟨2⟩$ vì:
$$
\begin{aligned}
2^1 &\equiv 2 \pmod{19}\\
2^2 &\equiv 4 \pmod{19}\\
2^3 &\equiv 8 \pmod{19}\\
2^4 &\equiv 16 \pmod{19}\\
2^5 &\equiv 13 \pmod{19}\\
2^6 &\equiv 7 \pmod{19}\\
2^7 &\equiv 14 \pmod{19}\\
2^8 &\equiv 9 \pmod{19}\\
2^9 &\equiv 18 \pmod{19}\\
2^{10} &\equiv 17 \pmod{19}\\
2^{11} &\equiv 15 \pmod{19}\\
2^{12} &\equiv 11 \pmod{19}\\
2^{13} &\equiv 3 \pmod{19}\\
2^{14} &\equiv 6 \pmod{19}\\
2^{15} &\equiv 12 \pmod{19}\\
2^{16} &\equiv 5 \pmod{19}\\
2^{17} &\equiv 10 \pmod{19}\\
2^{18} &\equiv 1 \pmod{19}
\end{aligned}
$$
- Ta thấy từ 2 có thể sinh ra được tất cả các phần tử của tập $\mathbb{Z}_{19}^{*}$ nên 2 là phần tử sinh của tập này.
- Các tính chất:
- Giả sử $a$ là phần tử sinh của $\mathbb{Z}_{n}^{*}$, khi đó $b = a^{i} \mod n$ cũng là phần tử sinh nếu gcd(i, $\phi(n)$) = 1. Vậy ta rút ra được nhận xét nếu $\mathbb{Z}_{n}^{*}$ là nhóm cyclic thì số phần tử sinh của $\mathbb{Z}_{n}^{*}$ = $\phi(\phi(n))$.
- Bài tập: tìm các phần tử sinh của $\mathbb{Z}_{41}^{*}$
- Giải:
- Ta có $\phi(41) = 40$
- Các ước nguyên tố của 40: [2, 5]
- Tiến hành tìm phần tử sinh nhỏ nhất thỏa:
\begin{matrix}
x^{40/2} \not\equiv 1 \pmod {41} \\
x^{40/5} \not\equiv 1 \pmod {41} \\
\end{matrix}
- Xét x = 6 thỏa. Vậy 6 là phần tử sinh của $\mathbb{Z}_{41}^{*}$
- Các giá trị i thỏa gcd(i, $\phi(41)$) = 1 là: [1, 3, 7, 9, 11, 13, 17, 19, 21, 23, 27, 29, 31, 33, 37, 39].
- Ta lần lượt tính các giá trị $6^{i}$ mod 41 = [6, 7, 11, 12, 13, 15, 17, 19, 22, 24, 26, 28, 29, 30, 34, 35]
- Vậy ta đã tìm được tập các phần tử sinh của $\mathbb{Z}_{41}^{*}$ = [6, 7, 11, 12, 13, 15, 17, 19, 22, 24, 26, 28, 29, 30, 34, 35].
### Vành (Ring)
- Định nghĩa: cho tập hợp $R$, phép toán hai ngôi $(+, \times)$ được gọi là một vành nếu:
- Với phép cộng:
- $(\text{R}, +)$ là nhóm Abel.
- Với phép nhân, có:
- Tính kết hợp: $(a \times b) \times c = a \times (b \times c)$
- Tính phân phối với phép cộng: $a \times (b + c) = a \times b + a \times c$
- Ví dụ: Vành số nguyên $(\mathbb{Z}, +, \times)$ có phần tử đơn vị là 1 $a \times 1 = 1 \times a = a$
### Trường (Field)
- Trường là một tập hợp $F$ cùng 2 phép toán $(+, \times)$ thỏa mãn:
- $(F, +)$ là một nhóm Abel (với phần tử đơn vị là $0$)
- $(F \setminus \{0\}, \times)$ là một nhóm Abel (với phần tử đơn vị là 1)
- Phép nhân phân phối với phép cộng
- Ví dụ xét phần tử $x$ thuộc tập số thực $\mathbb{R}$ có phần tử nghịch đảo $\frac{1}{x} \in \mathbb{R}$ vì nó là 1 trường, nhưng tập số nguyên $\mathbb{Z}$ có phần tử nghịch đảo = $\frac{1}{x} \notin \mathbb{Z}$ nên nó chỉ là 1 vành.
## Số học modulo
- Phép chia: cho 2 số a, n thực hiện phép chia a cho n ta được:
$$a = n \times q + r \hspace{2mm} $$
- Trong đó:
q là thương, kí hiệu q = a div n
r là số dư, ký hiệu r = a mod n
- Định nghĩa đồng dư: $a \equiv b \pmod n$ khi và chỉ khi a và b có cùng số dư khi chia với n.
- Ví dụ: 8 mod 3 = 2, 11 mod 3 = 2 suy ra $8 \equiv 11 \pmod 3$
- Tập các đại diện số nguyên theo modulo n gồm n phần tử, ký hiệu: $Z_{n}$ = {0, 1, 2,..., n-1}
- Ví dụ: $Z_{5}$ = {0, 1, 2, 3, 4}
- Các phép tính với modulo:
$$(a + b) \mod n = (a \mod n + b \mod n) \mod n$$ (tương tự với phép trừ)
$$(a \times b) \mod n = (a \mod n \times b \mod n) \mod n$$
- Ví dụ: Tính giá trị của A:
$$
A = (2025^2 + 37 \cdot 2025 - 121) \pmod{19}
$$
- Ta có:
- 2025 mod 19 = 11
- 37 mod 19 = 18
- 121 mod 19 = 7
- Ta biến đổi A:
$A = (2025\cdot2025 + 37 \cdot 2025 - 121) \pmod{19}$
$A = (11^{2} + 18 \cdot11 - 7) \pmod{19}$
$A = (121 + 198 - 7) \pmod{19}$
(198 = 10.19 + 8)
$A = (7 + 8- 7) \pmod{19}$
$A = 8 \pmod{19}$
- Vậy A = 8
> Chú ý: $(a\times b) \equiv (a \times c) \pmod n = b\equiv c \pmod n$ khi và chỉ khi gcd(a, n) = 1
- Phần tử nghịch đảo theo modulo: Phần tử nghịch đảo của một số nguyên a theo modulo n là số nguyên b > 0 sao cho:
$a \times b \equiv 1 \pmod n$
>b chỉ tồn tại khi gcd(a, n) = 1
- Cách tìm b:
- Tiến hành khai triển $a \times b \equiv 1 \pmod n$ = $a \times b = q \times n + 1$ = $a \times b - q \times n = 1 \hspace{5mm}$ (đây chính là dạng phương trình ${\displaystyle ax+by=\gcd(a,b)}$, hoàn toàn có thể dùng thuật Euclid mở rộng để giải.
- Phi hàm Euler: Phi hàm Euler $\phi(n)$ là số số nguyên tố cùng nhau với N trong đoạn từ 1 tới N.
- Tính chất:
- $\phi(p) = p-1$ nếu p là số nguyên tố.
- $\phi(n) = n \times (1 - \frac{1}{p_1}) \times (1 - \frac{1}{p_2}) \times \dots \times (1 - \frac{1}{p_k})$ với ${p_1}, {p_2}, {p_k}$ là các ước nguyên tố của N (thu được bằng cách phân tích thừa số nguyên tố của N)
- Ví dụ:
- $\phi(29) = 29-1 = 28$
$\phi(6) = 6 \left(1 - \frac{1}{2}\right)\left(1 - \frac{1}{3}\right)
= 6 \cdot \frac{1}{2} \cdot \frac{2}{3}
= 2$
> $\phi(m \times n) = \phi(m) \times \phi(n)$ Nếu gcd(m,n) = 1
- Với nhóm nhân $Z_n$, ta có: $|Z^*_n| = \phi(n)$
- Định lý Euler: là mở rộng của định lý Fermat, phát biểu rằng:
- Với mọi cặp a, n mà gcd(a, n) = 1 thì:
$$a^{\phi(n)} \equiv 1 \pmod n$$
- Ví dụ: với a = 5, n = 6 ta có: $\phi(6)
= 2$, $5^{2} \mod 6 =1$.
- Định lý thặng dư Trung Hoa (Chinese remainder theorem): Cho hệ phương trình đồng dư: $$\left\{\begin{matrix}
x \equiv a_1 \pmod {n_1} \\
x \equiv a_2 \pmod {n_2} \\
\cdots \\
x \equiv a_k \pmod {n_k} \\
\end{matrix}\right.$$
- Với $gcd(n_{i}, n_{j}) = 1, \forall i \neq j$, khi đó áp dụng CRT ta tìm được x:
$$x = \sum_{i=1}^{k} (a_i N_i M_i) \mod N$$
- Trong đó:
- $N = n_1 \times n_2 \times \dots \times n_k$
- $N_{i} = N / n_{i}$
- $M_i \equiv N_i^{-1} \pmod {n_i}$
- Luyện tập:
$$
\begin{cases}
x \equiv 2 \pmod{3}\\[4pt]
x \equiv 3 \pmod{5}\\[4pt]
x \equiv 2 \pmod{7}.
\end{cases}
$$
- Ta tính $N = n_1 \times n_2 \times \dots \times n_3 = 3 \times 5 \times 7 = 105$
- $N_{1} = N / 3 = 35$, $N_{2} = N / 5 = 21$, $N_{3} = N / 7 = 15$
- $M_1 = N_1^{-1} \mod {n_1} = 2$, $M_2 = N_2^{-1} \mod {n_2} = 1$, $M_3 = 1$
- $x = 2 \times 35 \times 2 + 3 \times 21 \times 1 + 2 \times 15 \times 1 =233$
- Vậy:
$$
x \equiv 23 \pmod{105}.
$$
- Thặng dư bậc hai:
- Định nghĩa: Cho p là số nguyên tố lẻ, $g$ là phần tử sinh của $\mathbb{Z}_{p}^{*}$. Một phần tử $a$ $\in \mathbb{Z}_{n}^{*}$ được gọi là thặng dư bậc hai nếu $a \equiv g^{i} \pmod p$ với $i$ là số nguyên chẵn.
- Hệ quả: $|Q_n| = \frac{(p-1)(q-1)}{4};|\overline{Q}_n| = \frac{3\times(p-1)(q-1)}{4}$
- Ví dụ: Cho $3$ là phần tử sinh của $\mathbb{Z}_{17}^{*}$, tìm $Q_{17}$,$\overline{Q}_{17}$
- Giải:
- Theo định lý: thặng dư bậc hai là các lũy thừa có số mũ **chẵn**: $3^{2},3^{4},\dots,3^{16}$. Từ trên ta có:
$$
\begin{aligned}
3^2&\equiv9,\\
3^4&\equiv13,\\
3^6&\equiv15,\\
3^8&\equiv16,\\
3^{10}&\equiv8,\\
3^{12}&\equiv4,\\
3^{14}&\equiv2,\\
3^{16}&\equiv1.
\end{aligned}
$$
Vậy
$$
{Q_{17}=\{1,2,4,8,9,13,15,16\}.}
$$
- Tập phần tử không phải thặng dư (phần bù) là các phần tử còn lại trong $\{1,\dots,16\}$:
$$
\overline{Q}_{17}=\{3,5,6,7,10,11,12,14\}.
$$
- **Định lý.** Cho $n = p \cdot q$ với \(p, q\) là hai số nguyên tố phân biệt.
Khi đó $(a \in \mathbb{Z}_n^*)$ là thặng dư bậc hai theo modulo n khi và chỉ khi
$a\in Q_p$ và $a \in Q_q$
- Hệ quả:
$$
|Q_n| = \frac{(p-1)(q-1)}{4}, \qquad
|\overline{Q_n}| = \frac{3(p-1)(q-1)}{4}.
$$
- Giải thích:
* $|\mathbb{Z}_n^*|$ = $\phi(n)$ = $(p-1)(q-1)$.
* $|Q_n|$ = $\dfrac{(p-1)(q-1)}{4}$.
* Phần còn lại (không thặng dư):
$(p-1)(q-1) - \dfrac{(p-1)(q-1)}{4} = \dfrac{3(p-1)(q-1)}{4}$
- Định nghĩa căn bậc hai của một số theo modulo n: Cho $a \in Q_n$, $x \in Z^*_n$ và thỏa mản $x^2 \equiv a \pmod n$ thì $x$ gọi là căn bậc hai của $a \mod n$
- Định lý về số căn bậc hai:Cho $n = p^{e_1}_1 \times p^{e_2}_2 \times \dots \times p^{e_k}_k$ ($p_i$ là số nguyên tố lẻ và $e_i \geq 1$). Nếu $a \in Q_n$ thì có đúng $2^k$ căn bậc hai khác nhau theo modulo n.
- Định nghĩa (Ký hiệu Legendre):
- Cho \(p\) là số nguyên tố lẻ, \(a\) là số nguyên. Ký hiệu Legendre $\left(\frac{a}{p}\right)$ được định nghĩa như sau:
$$
\left(\frac{a}{p}\right) =
\begin{cases}
0, & \text{nếu } p \mid a, \\[4pt]
1, & \text{nếu } a \in Q_p \text{ (tức là $a$ là thặng dư bậc hai modulo $p$)}, \\[4pt]
-1, & \text{nếu } a \notin Q_p \text{ (tức là $a$ không là thặng dư bậc hai modulo $p$)}.
\end{cases}
$$
---
- Định nghĩa (Ký hiệu Jacobi) cho $n \geq 3$ là số nguyên lẻ $n = p^{e_1}_1 \times p^{e_2}_2 \times \dots \times p^{e_k}_k$,khi đó, ký hiệu **Jacobi**$\left(\frac{a}{n}\right)$ được định nghĩa là:
$$\left(\frac{a}{n}\right) = \left(\frac{a}{p_1}\right)^{e_1} \times \left(\frac{a}{p_2}\right)^{e_2} \times \dots \times \left(\frac{a}{p_k}\right)^{e_k}$$
---
- Tính chất:
- 1. Nếu $n$ là số nguyên lẻ và $m_1 \equiv m_2 \pmod{n}$ thì:
$$
\left(\frac{m_1}{n}\right) = \left(\frac{m_2}{n}\right)
$$
- 2. Nếu $n$ là số nguyên lẻ thì:$$
\left(\frac{2}{n}\right) =
\begin{cases}
1 & \text{nếu } n \equiv \pm 1 \pmod{8} \\
-1 & \text{nếu } n \equiv \pm 3 \pmod{8}
\end{cases}
$$
- 3. Nếu $n$ là số nguyên lẻ thì:
$$
\left(\frac{m_1 \cdot m_2}{n}\right) = \left(\frac{m_1}{n}\right) \left(\frac{m_2}{n}\right)
$$
- Đặc biệt, nếu $m = 2^k \cdot t \ (t \text{ là số lẻ})$ thì:
$$
\left(\frac{m}{n}\right) = \left(\frac{2}{n}\right)^k \cdot \left(\frac{t}{n}\right)
$$
- 4. Giả sử $m$ và $n$ là số nguyên lẻ thì:
$$
\left(\frac{m}{n}\right) \left(\frac{n}{m}\right) =
\begin{cases}
-1 & \text{nếu } m \equiv n \equiv 3 \pmod{4} \\
1 & \text{trường hợp còn lại}
\end{cases}
$$
- Bài tập: Tính ký hiệu Jacobi
$\left(\frac{7411}{9283}\right)
= -\left(\frac{9283}{7411}\right)
= -\left(\frac{1872}{7411}\right)
= -\left(\frac{117}{7411}\right)
= -\left(\frac{7411}{117}\right)
= -\left(\frac{40}{117}\right)
= -\left(\frac{2}{117}\right)^3 \left(\frac{5}{117}\right)
= -(-1)^3 \cdot (-1) = -1$
- Bài toán Lorarit rời rạc (DLP):
- Cho g là phần tử sinh của $\mathbb{Z}_n^*$, ta luôn tìm được $x$ thỏa $g^x \equiv a \pmod p$ <=> $x \equiv \log_ga \pmod p$
- Thuật toán baby step giant step:
- Tính $m =\left \lceil \sqrt{\text{ord}(a)} \right \rceil$
- Lập bảng $(j, \alpha^{j} \mod n)$ với $j = \overline{0 \rightarrow m-1}$
- Tính $\beta\cdot(\alpha^{-m})^i \mod n$ với $i = \overline{0 \rightarrow m-1}$
- Tìm $i, j$ thỏa: $\beta\cdot(\alpha^{-m})^i = \alpha^j$
- $\log_{\alpha}\beta = m \cdot i + j$
- Ví dụ luyện tập:
+ Cho a = 31 là phẩn tử sinh của $\mathbb{Z}_{61}^*$. Hãy tìm $\log_{31}{45}$
trên $\mathbb{Z}_{61}^*$.
- Giải:
- m = $\left \lceil \sqrt{\text{ord}(31)} \right \rceil$ = $\left \lceil \sqrt{\phi(61)} \right \rceil$ = $\left \lceil \sqrt{60} \right \rceil$ = 8.
- Lập bảng $(j, 31^{j} \mod 61)$ với $j = \overline{0 \rightarrow 7}$
| j | 0 | 1 | 2 | 3 |4 | 5 | 6 | 7 |
| --- | --- | --- | --- | --- | --- | -------- | -------- | -------- |
| $31^{j} \mod 61$ | 1 | 31 | 46 | 23 | 42 | 21 | 41 | 51 |
- Tính $45\cdot(31^{-8})^i \mod 61$ với $i = \overline{0 \rightarrow 7}$
- $31^{-1} \mod 61 =2$, $31^{-8} \mod 61 =2^{8} \mod 61 = 12$
| $i$ | 0 | 1 | 2 | 3 | 4 | 5 |6 | 7 |
| -------- | -------- | --- | --- | --- | --- | --- | --- | -------- |
| $45\cdot(12)^i \mod 61$ | 45 | 52 | 14 | 46 | 3 | 36 | 5 | 60 |
- $\beta\cdot(\alpha^{-m})^i = \alpha^j$ tại j = 2, i = 3. Vậy $\log_{31}45 \mod {61}$ = $m \cdot i + j = 8 \cdot 3 + 2 = 26$
---
- Cho $a = 17$ là phần tử sinh của $\mathbb{Z}_{97}^*$. Hãy tìm $\log_{17}{15}$ trên $\mathbb{Z}_{97}^*$.
- $m = \left\lceil \sqrt{\text{ord}(17)} \right\rceil = \left\lceil \sqrt{\varphi(97)} \right\rceil = \lceil \sqrt{96} \rceil = 10$
- Lập bảng $(j, 17^j \bmod 97)$ với $j = 0 \rightarrow 9$
\
\begin{array}{c|cccccccccc}
j & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\
\hline
17^j \bmod 97 & 1 & 17 & 95 & 63 & 4 & 68 & 89 & 58 & 16 & 78
\end{array}
- Tính $15 \cdot (17^{-10})^i \bmod 97$ với $i = 0 \rightarrow 9$
- $17^{-1} \bmod 97 = 40$, $17^{-10} \bmod 97 = (17^{-1})^{10} \equiv 40^{10} \equiv 3 \pmod{97}$
\
\begin{array}{c|cccccccccc}
i & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\
\hline
15 \cdot 3^i \bmod 97 & 15 & 45 & 38 & 17 & 51 & 56 & 71 & 19 & 57 & 74
\end{array}
- $\beta \cdot (\alpha^{-m})^i = \alpha^j$ tại $i = 3, j = 1$.
- Vậy $\log_{17}{15} \bmod 97 = m \cdot i + j = 10 \cdot 3 + 1 = 31$
# 2. Thực hành challenges CryptoHack
## Introduction
### Finding Flags
- Bài này là bài làm quen ta chỉ cần nhập flag đề cho là ```crypto{y0ur_f1rst_fl4g}``` thôi.
### Great Snakes
- 
- Bài này cho ta một file ```great_snakes.py```, ta thử tải: 
- run file ta được flag ```crypto{z3n_0f_pyth0n}```.
### Network Attacks
- Đây là một bài khá lạ với mình, mình chưa học về thao tác với sever nên sẽ làm trực tiếp trên source code, khi tải file ``` pwntools_example.py``` ta được đoạn code:
```python=
#!/usr/bin/env python3
from pwn import * # pip install pwntools
import json
HOST = "socket.cryptohack.org"
PORT = 11112
r = remote(HOST, PORT)
def json_recv():
line = r.readline()
return json.loads(line.decode())
def json_send(hsh):
request = json.dumps(hsh).encode()
r.sendline(request)
print(r.readline())
print(r.readline())
print(r.readline())
print(r.readline())
request = {
"buy": "clothes"
}
json_send(request)
response = json_recv()
print(response)
```
- Chạy thử thì không tìm được gì đặc biệt cả:
- 
- Chú ý rằng đề kêu "Send a JSON object with the key buy and value flag.".
```python=
request = {
"buy": "clothes"
}
json_send(request)
```
- Đây là một dict với key là "buy", value là "clothes" nó được chuyển thành JSON trong hàm json_send() với lệnh `request = json.dumps(hsh).encode()`, nên ta chỉ cần sửa value "clothes" thành "flag":
- Mình đã nhận được flag ```crypto{sh0pp1ng_f0r_fl4g5}```
## General
### ASCII
- Mô tả: Đề giới thiệu cho ta về hệ ASCII, và ta cần chuyển đổi mảng số nguyên đã cho thành ký tỵ thông qua bản mã ASCII
- Hướng dẫn: trong python, ta có hàm chr() giúp chuyển từ số nguyên thành thành ký tự và ngược lại, hàm ord() chuyển đổi ký tự thành số nguyên.
- source code:
```python
a = [99, 114, 121, 112, 116, 111, 123, 65, 83, 67, 73, 73, 95, 112, 114, 49, 110, 116, 52, 98, 108, 51, 125]
for i in a:
print(chr(i), end = "")
```
- Vậy mình đã tìm được flag là ```crypto{ASCII_pr1nt4bl3}```
### Hex
- Mô tả: challenge cho ta một dãy số nguyên ở dạng cơ số 16(hex), hệ được tạo thành từ việc chuyển đổi từng ký tự thành số nguyên thông qua bản mã ASCII sau đó chuyển sang cơ số 16.
- Hướng dẫn: 1 byte hệ cơ số 16 được tạo thành từ hai giá trị trong tập [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F] (A, B, C, D, E, F) tương ứng (10, 11, 12, 13, 14, 15). Ví dụ chuyển từ chữ ```Q``` sang hex: đầu tiên thông qua bản mã ASCII ta có ký tự ```Q``` = ```81```, lấy 81 div 16 = ```5```, 81 mod 16 = 1, lấy 1 div 16 = ```1```, nối 2 kết quả của 2 lần div lại ta được ```51```. Vậy `81 (dec) = 51 (hex)`. Trong python thì có hàm ```bytes.fromhex()``` giúp chuyển từ hex sang byte nhanh chóng, ta sẽ dùng hàm này.
- Source code:
```python=
a = "63727970746f7b596f755f77696c6c5f62655f776f726b696e675f776974685f6865785f737472696e67735f615f6c6f747d"
flag = bytes.fromhex(a)
print(flag)
```
- Vậy mình đã tìm được flag: ```crypto{You_will_be_working_with_hex_strings_a_lot}```
#### Base64
- Mô tả: challenge cho ta một chuỗi hex, ta phải chuyển nó sang bytes rồi sang base64.
- Hướng dẫn: mã base64 là một mã khá phổ biển, nó chuyển từ 6 bit sang một 1 ký tự base64, ta có bảng:
- Ví dụ ta có chuỗi ```dog``` biểu diễn ở mã nhị phân là ```011001000110111101100111```, ta chia nó thành 4 phần 6 bit: 011001 000110 111101 100111, ta chiếu 4 phần này lên bảng phía trên, thu được 4 ký tự: ```Z``` ```G``` ```9``` ```n```. Vậy từ chuỗi ```dog``` sẽ được mã hóa thành ```ZG9n``` thông qua hệ base64. Vấn đề đặt ra là nếu độ dài của chuỗi ở dạng không chia hết cho 6 thì sao?, ví dụ chuỗi ```hi``` = ```0110100001101001``` nếu chia chuỗi này sang các phần 6 bit: `011010 000110 1001`, 2 phần đầu đã đủ 6 bit nhưng phần cuối chỉ có 4 bit, lúc này ta tiến hành đệm (padding) các bit 0 vào chỗ thiếu, chuỗi sẽ trở thành ```011010 000110 100100```. và do đó ```hi``` sẽ trở thành ```aGk=```
>- Lưu ý: ta thêm 1 ký tự ```=``` nếu pad thêm ```00``` và ```==``` nếu pad thêm ```0000```
- Trở lại challenge, ta sẽ chuyển chuỗi hex đó thành byte ròi chuyển thành base64 thông qua hàm b64encode().
- Source code:
```python=
from base64 import b64encode
a = "72bca9b68fc16ac7beeb8f849dca1d8a783e8acf9679bf9269f7bf"
bytes = bytes.fromhex(a)
print(b64encode(bytes))
```
- Vậy ta đã tìm được flag: ```crypto/Base+64+Encoding+is+Web+Safe/```
### Bytes and Big Integers
- Mô tả: challenge này hướng dẫn cách ta chuyển đổi từ một message nào đó ở dạng ký tự sang một dãy số, vì sau này khi áp dụng các thuật toán, ta phải tính toán, làm việc với các con số.
- Hướng dẫn: Để chuyển chuỗi ký tự sang số nguyên, ta chuyển từng ký tự sang số theo mã ASCII, tiếp tục chuyển từng số sang base 16, nối từng byte lại với nhau và cuối cùng chuyển sang hệ thập phân. Các bạn có thể đọc ví dụ trên đề để hiểu rõ hơn.
- Đề đã cho ta một dãy số, ta sẽ sử dụng hàm `long_to_bytes()` trong thư viện PyCryptodome (các bạn có thể dùng pip để tải thư viện này), hàm `long_to_bytes()` sẽ chuyển từ số nguyên sang mã bytes(ngược lại với hàm `bytes_to_long()`).
- Source code:
```python=
from Crypto.Util.number import long_to_byte
n = 11515195063862318899931685488813747395775516287289682636499965282714637259206269
flag = long_to_bytes(n)
print(flag)
```
- Vậy mình đã có được flag: `crypto{3nc0d1n6_4ll_7h3_w4y_d0wn}`
### Encoding Challenge
- Mô tả: nếu ta giải mã 100 đoạn mã mà challenge gửi tới thì ta sẽ nhận được flag.
- Hướng dẫn: đề cho ta 2 file, file `13377.py` là source code giúp ta hiểu cách sever hoạt động
- Sever sẽ gửi chuỗi JSON có dạng ` {"type": encoding, "encoded": encoded}` (encoding gồm các dạng base64, hex, rot13, bigint, utf-8) ta giải đúng 100 lần sẽ nhận JSON dạng `{"flag": FLAG}`, `pwntools_example.py` là file hướng dẫn cách tương tác với server, mình sẽ giải challenge dựa theo file này:
```py=
from pwn import * # pip install pwntools
import json
r = remote('socket.cryptohack.org', 13377, level = 'debug')
def json_recv():
line = r.recvline()
return json.loads(line.decode())
def json_send(hsh):
request = json.dumps(hsh).encode()
r.sendline(request)
received = json_recv()
print("Received type: ")
print(received["type"])
print("Received encoded value: ")
print(received["encoded"])
to_send = {
"decoded": "changeme"
}
json_send(to_send)
json_recv()
```
- `json_recv()` là hàm nhận, `json_send()` là hàm gửi dict `to_send` đã được chuyển thành JSON bằng hàm `json.dumps`. Vậy mình cũng sẽ gọi hàm `json_recv()` và lưu vào biến `received`, sau đó tiến hành decode:
```py=
from pwn import *
import json, base64, codecs
from Crypto.Util.number import *
r = remote('socket.cryptohack.org', 13377)
def json_recv():
return json.loads(r.recvline().decode())
def json_send(hsh):
r.sendline(json.dumps(hsh).encode())
while True:
received = json_recv()
if "flag" in received:
print(received["flag"])
break
encoding, encoded = received["type"], received["encoded"]
if encoding == "base64":
decoded = base64.b64decode(encoded).decode()
elif encoding == "hex":
decoded = bytes.fromhex(encoded).decode()
elif encoding == "rot13":
decoded = codecs.decode(encoded, "rot13")
elif encoding == "bigint":
decoded = long_to_bytes(int(encoded, 16)).decode()
elif encoding == "utf-8":
decoded = "".join(chr(o) for o in encoded)
json_send({"decoded": decoded})
```
- Giải thích code
- Nhận encode từ sever và tiến hành decode, liên tục gửi JSON tới sever bằng lệnh `json_send({"decoded": decoded})`
```py=
while True:
received = json_recv()
if "flag" in received:
print(received["flag"])
break
```
- Dùng để kiểm tra nếu sever đã gửi flag thì in ra và tiến hành break khỏi while.
- Vậy mình đã nhận được flag: `crypto{3nc0d3_d3c0d3_3nc0d3}`.
### XOR Starter
- Mô tả: challenge giới thiệu về phép XOR, ta cần XOR chuỗi `label` với số `13` để thu được flag.
- Hướng dẫn: đầu tiên ta phải hiểu về phép XOR trước, XOR hai bit giống nhau sẽ được `0`, được `1` khi XOR hai bit khác nhau.
- Quay trở lại challenge, để XOR được 1 chuỗi với 1 số, ta phải chuyển từng kí tự trong chuỗi thành số nguyên (có thể dùng hàm `ord()`) sau đó XOR từng số với `13`.
- Source code:
```python=
str = "label"
n = 13
str = "label"
n = 13
for c in str:
print((chr(ord(c) ^ n)), end = "")
```
- Vậy mình đã thu được flag: `crypto{aloha}`.
### XOR Properties
- Mô tả: challenge này cho ta biết các tính chất thú vị của phép XOR, ta phải sử dụng các tính chất này để tìm được flag.
- Hướng dẫn: ta đã biết được KEY1 nhưng chưa biết KEY2, KEY3, FLAG. Để ý dòng cuối `FLAG ^ KEY1 ^ KEY3 ^ KEY2 = 04ee9855208a2cd59091d04767ae47963170d1660df7f56f5faf`. Vậy ta phải làm sao đó để biến `KEY1 ^ KEY3 ^ KEY2` thành `0` vì `FLAG ^ 0` sẽ = `FLAG`. Mà một phần tử XOR với chính nó sẽ ra `0` nên ta lấy `FLAG ^ KEY1 ^ KEY3 ^ KEY2` ^ `KEY1 ` ^ `KEY2 ^ KEY3` = `FLAG`
- Source code:
```py=
from pwn import *
key1 = bytes.fromhex("a6c8b6733c9b22de7bc0253266a3867df55acde8635e19c73313")
key2key3 = bytes.fromhex("c1545756687e7573db23aa1c3452a098b71a7fbf0fddddde5fc1")
flagkey1key2key3 = bytes.fromhex("04ee9855208a2cd59091d04767ae47963170d1660df7f56f5faf")
print((xor(xor(flagkey1key2key3, key1), key2key3).decode("utf-8")))
```
- Vậy mình đã thu được flag: `crypto{x0r_i5_ass0c1at1v3}`
### Favourite byte
- Mô tả: đề cho ta một chuỗi hex, ta cần XOR chuỗi này với một byte secret nào đó để tìm được flag.
- Hướng dẫn: Nhận thấy rằng 1 byte chỉ có có 256 giá trị (vì 1 byte = 8 bit, mà mỗi bit có 2 trạng thái nên tổng cộng có $2^{8} = 256$ trường hợp). Mình sẽ tiến hành brute-force từ 0 đến 255.
- Source code:
```python=
from pwn import *
string = bytes.fromhex("73626960647f6b206821204f21254f7d694f7624662065622127234f726927756d")
flag = ""
for i in range(256):
flag = xor(string, i)
if(b"crypto" in flag):
print(flag)
```
- Vậy mình đã tìm được flag: `crypto{0x10_15_my_f4v0ur173_by7e}`
### You either know, XOR you don't
- Mô tả: Đề cho ta chuỗi hex, ta phải tìm secret key sau đó XOR chuỗi này với secret key để tìm được flag.
- Hướng dẫn: vì bài này key không còn là 1 byte nên không thể brute-force được nữa. Đề cho hint là chú ý đến flag format, format của flag có dạng là `crypto{...}` nên ta sẽ thử tìm secret key dựa vào 7 kí tự đầu `crypto{` và ký tự `}` ở cuối.
- Lúc này ta có thể chắc chắn key = `myXORkey`
- Source code:
```python
from pwn import *
string = bytes.fromhex("0e0b213f26041e480b26217f27342e175d0e070a3c5b103e2526217f27342e175d0e077e263451150104")
key = b"myXORkey"
print(xor(string, key))
```
- Vậy mình đã tìm được flag: `crypto{1f_y0u_Kn0w_En0uGH_y0u_Kn0w_1t_4ll}`
### Lemur XOR
- Mô tả: challenge cho ta hai hình ảnh, ta phải XOR từng byte RBG giữa hai ảnh với nhau để tạo thành tấm ảnh mới chứa flag
- Hướng dẫn: mình sẽ dùng thư viện PIL và numpy để xử lý hình ảnh
- Sour code:
```py=
from PIL import Image
import numpy
img1 = Image.open("flag.png")
img2 = Image.open("lemur.png")
a1 = numpy.array(img1)
a2 = numpy.array(img2)
result = numpy.bitwise_xor(a1, a2)
out = Image.fromarray(result)
out.save("ans.png")
out.show()
```
- Giải thích code:
- Ta lưu 2 ảnh vào img1 và img2, sau đó chuyển ảnh thành numpy array bằng lệnh `numpy.array()` vì phép XOR hoạt động với số nguyên.
`numpy.bitwise_xor()` thực hiện XOR từng phần tử với nhau, sau đó chuyển từ array sang ảnh bằng hàm `Image.fromarray()`. Lệnh `out.show()` sẽ hiện ảnh ra màn hình:
- Vậy mình đã tìm được flag là `crypto{X0Rly_n0t!}`
### Greatest Common Divisor
- Mô tả: challenge giới thiệu cho ta về ước chung lớn nhất, ta cần tìm ước chung lớn nhất của 66528 và 52920.
- Hướng dẫn: Mình sẽ sử dụng thật toán Euclid để tìm ƯCLN (gcd), cách thuật Euclid hoạt động:
- Cho hai số nguyên dương $a$ và $b$ ($a \geq b$).
- Chia $a$ cho $b$, lấy thương và **phần dư** $r$.
$$
a = b \cdot q + r \quad (0 \leq r < b)
$$
- Nếu $r = 0$, thì $\gcd(a, b) = b$.
- Nếu $r \neq 0$, thay $a \leftarrow b$, $b \leftarrow r$, rồi lặp lại bước 2.
> Thuật toán kết thúc sau hữu hạn bước vì phần dư ngày càng nhỏ dần (tại bước cuối, $r_{N}$ sẽ = 0 => gcd(a,b) = $r_{N-1}$).
- Source code:
```py=
def gcd(a, b):
while(b != 0):
a, b = b, a%b
return a
a = 66528
b = 52920
print(gcd(a, b))
```
- Vậy mình đã tìm được flag = `1512`.
### Extended GCD
- Mô tả: challenge cho hai số nguyên tố p, q, ta cần tìm u, v thỏa mản:
$$p \times u + q \times v = gcd(p,q)$$
- Hướng dẫn: đây là bài toán áp dụng thuật toán Euclid mở rộng.
Giả sử chúng ta cần tìm $\gcd(a, b)$ với $a > b$.
- Ta đặt $r_0 = a$ và $r_1 = b$.
- Thuật toán Euclid cơ bản là một chuỗi các phép chia lấy dư: $r_0 = q_1 r_1 + r_2$$r_1 = q_2 r_2 + r_3$...$r_{i-1} = q_i r_i + r_{i+1}$
Từ phép chia ở bước $i$, ta có thể viết lại công thức truy hồi cho số dư:$$r_{i+1} = r_{i-1} - q_i r_i$$(với $q_i = \lfloor r_{i-1} / r_i \rfloor$)
Mục tiêu của chúng ta là tìm các hệ số $s_i$ và $t_i$ sao cho:$$r_i = s_i a + t_i b$$
Chúng ta sẽ chứng minh rằng nếu $r_{i-1}$ và $r_i$ có thể biểu diễn được, thì $r_{i+1}$ cũng vậy.
Trường hợp cơ sở:
- Tại $i=0$: $r_0 = a = (1) \times a + (0) \times b$$\implies$ $s_0 = 1, t_0 = 0$
- Tại $i=1$: $r_1 = b = (0) \times a + (1) \times b$$\implies$ $s_1 = 0, t_1 = 1$
Cả hai trường hợp cơ sở đều thỏa mãn.
Bước quy nạp:
- Giả sử tại bước $i-1$ và $i$, ta đã có các hệ số:$$r_{i-1} = s_{i-1} a + t_{i-1}b \hspace{5mm}(1)$$
$$r_i = s_i a + t_i b \hspace{5mm} (2)$$
Bây giờ, ta tìm các hệ số $s_{i+1}$ và $t_{i+1}$ cho $r_{i+1}$. Ta bắt đầu từ công thức truy hồi của số dư:$$r_{i+1} = r_{i-1} - q_i r_i$$
Thay thế $r_{i-1}$ và $r_i$ bằng phương trình (1) và (2) ở trên:$$r_{i+1} = (s_{i-1} a + t_{i-1} b) - q_i (s_i a + t_i b)$$
Nhóm các số hạng theo $a$ và $b$:$$r_{i+1} = (s_{i-1} - q_i s_i) a + (t_{i-1} - q_i t_i) b$$Chúng ta muốn $r_{i+1} = s_{i+1} a + t_{i+1} b$. Bằng cách đồng nhất hai vế, ta rút ra được các công thức truy hồi cho $s$ và $t$:$$s_{i+1} = s_{i-1} - q_i s_i$$
$$t_{i+1} = t_{i-1} - q_i t_i$$
Đây chính là điều phải chứng minh. Chúng ta cứ lặp lại công thức này cho đến khi $r_k = \gcd(a, b)$, và khi đó, các hệ số $s_k$ và $t_k$ tương ứng chính là $u$ và $v$ mà ta cần tìm.
- Source code:
```py=
def extended_gcd_recursive(a, b):
if b == 0:
return (a, 1, 0)
q = a // b
r = a % b
(gcd, s_next, t_next) = extended_gcd_recursive(b, r)
s = t_next
t = s_next - q * t_next
return (gcd, s, t)
a = 26513
b = 32321
print(extended_gcd_recursive(a,b))
```
> output = (1, 10245, -8404)
- Vậy mình đã tìm được flag = `-8404`
### Modular Arithmetic 1
- Mô tả: challenge giới thiệu về kiến thức đồng dư cơ bản, các bạn có thể đọc thêm ở phần lý thuyết mà mình đã giới thiệu.
- Source code:
```py=
print(min(11%6, 8146798528947%17))
```
- Vậy mình đã tìm được flag = `4`.
### Modular Arithmetic 2
- Mô tả: challenge giới thiệu về định lý Fermat nhỏ, ta cần áp dụng định lý này để tính $273246787654 ^ {65536}\hspace{1mm}mod\hspace{2mm} 65537$
- Hướng dẫn: Định lý Fermat nhỏ phát biểu rằng: nếu p là một số nguyên tố và a là một số nguyên bất kỳ thì:
$$a^{p}\equiv a\hspace{1mm}(mod\hspace{1mm}p)$$
- Chia hai vế cho $a$, ta có thể viết lại thành:
$$a^{p-1}\equiv 1\hspace{1mm}(mod\hspace{1mm}p)$$
- Đề đã khẳng định 65537 là số nguyên tố nên $273246787654 ^ {65536}\hspace{1mm}mod\hspace{2mm} 65537 = 1$
- Vậy mình đã tìm được flag là `1`.
### Modular Inverting
- Mô tả: challenge giới thiệu về nghịch đảo modulo.
- Hướng dẫn: trong trường $Fp$ = $(0,1,2,3,...,p-1).$ với mọi $g \in Fp$, nếu $gcd(g, p) = 1$ thì sẽ tồn tại $d$ sao cho $g \times d ≡ 1\hspace{1mm}(mod\hspace{1mm}p)$
- Quay trở lại bài toán, ta cần tìm d thỏa mãn:
$3 \times d ≡ 1\hspace{1mm}mod\hspace{2mm}13$, hoặc $d ≡ 3^{-1}\hspace{1mm}mod\hspace{2mm}13$
- Source code:
```py=
print(pow(3, -1, 13))
```
- Vậy mình đã tìm được flag là `9`.
### Privacy-Enhanced Mail?
- Mô tả: challenge giới thiệu cho ta về file pem, ta phải tìm ra được khóa d (khóa bí mật).
- Hướng dẫn: Ta thử tải file pem, vì là file private key nên chắc chắn sẽ chứa khóa e, n, d:
```
-----BEGIN RSA PRIVATE KEY-----
MIIEowIBAAKCAQEAzvKDt+EO+A6oE1LItSunkWJ8vN6Tgcu8Ck077joGDfG2NtxD
4vyQxGTQngr6jEKJuVz2MIwDcdXtFLIF+ISX9HfALQ3yiedNS80n/TR1BNcJSlzI
uqLmFxddmjmfUvHFuFLvxgXRga3mg3r7olTW+1fxOS0ZVeDJqFCaORRvoAYOgLgu
d2/E0aaaJi9cN7CjmdJ7Q3m6ryGuCwqEvZ1KgVWWa7fKcFopnl/fcsSecwbDV5hW
fmvxiAUJy1mNSPwkf5YhGQ+83g9N588RpLLMXmgt6KimtiWnJsqtDPRlY4Bjxdpu
V3QyUdo2ymqnquZnE/vlU/hn6/s8+ctdTqfSCwIDAQABAoIBAHw7HVNPKZtDwSYI
djA8CpW+F7+Rpd8vHKzafHWgI25PgeEhDSfAEm+zTYDyekGk1+SMp8Ww54h4sZ/Q
1sC/aDD7ikQBsW2TitVMTQs1aGIFbLBVTrKrg5CtGCWzHa+/L8BdGU84wvIkINMh
CtoCMCQmQMrgBeuFy8jcyhgl6nSW2bFwxcv+NU/hmmMQK4LzjV18JRc1IIuDpUJA
kn+JmEjBal/nDOlQ2v97+fS3G1mBAaUgSM0wwWy5lDMLEFktLJXU0OV59Sh/90qI
Jo0DiWmMj3ua6BPzkkaJPQJmHPCNnLzsn3Is920OlvHhdzfins6GdnZ8tuHfDb0t
cx7YSLECgYEA7ftHFeupO8TCy+cSyAgQJ8yGqNKNLHjJcg5t5vaAMeDjT/pe7w/R
0IWuScCoADiL9+6YqUp34RgeYDkks7O7nc6XuABi8oMMjxGYPfrdVfH5zlNimS4U
wl93bvfazutxnhz58vYvS6bQA95NQn7rWk2YFWRPzhJVkxvfK6N/x6cCgYEA3p21
w10lYvHNNiI0KBjHvroDMyB+39vD8mSObRQQuJFJdKWuMq+o5OrkC0KtpYZ+Gw4z
L9DQosip3hrb7b2B+bq0yP7Izj5mAVXizQTGkluT/YivvgXcxVKoNuNTqTEgmyOh
Pn6w+PqRnESsSFzjfWrahTCrVomcZmnUTFh0rv0CgYBETN68+tKqNbFWhe4M/Mtu
MLPhFfSwc8YU9vEx3UMzjYCPvqKqZ9bmyscXobRVw+Tf9llYFOhM8Pge06el74qE
IvvGMk4zncrn8LvJ5grKFNWGEsZ0ghYxJucHMRlaU5ZbM6PEyEUQqEKBKbbww65W
T3i7gvuof/iRbOljA9yzdwKBgQDT9Pc+Fu7k4XNRCon8b3OnnjYztMn4XKeZn7KY
GtW81eBJpwJQEj5OD3OnYQoyovZozkFgUoKDq2lJJuul1ZzuaJ1/Dk+lR3YZ6Wtz
ZwumCHnEmSMzWyOT4Rp2gEWEv1jbPbZl6XyY4wJG9n/OulqDbHy4+dj5ITb/r93J
/yLCBQKBgHa8XYMLzH63Ieh69VZF/7jO3d3lZ4LlMEYT0BF7synfe9q6x7s0ia9b
f6/QCkmOxPC868qhOMgSS48L+TMKmQNQSm9b9oy2ILlLA0KDsX5O/Foyiz1scwr7
nh6tZ+tVQCRvFviIEGkaXdEiBN4eTbcjfc5md/u9eA5N21Pzgd/G
-----END RSA PRIVATE KEY-----
```
- Mình sẽ dùng hàm `RSA.importKey()` của thư viện Crypto.PublicKey mà challenge gợi ý để đọc khóa d.
- Source code:
```py=
from Crypto.PublicKey import RSA
with open("privacy_enhanced_mail.pem", "rb") as f:
pem_data = f.read()
key = RSA.import_key(pem_data)
print(key.d)
```
- Vậy mình đã tìm được flag là `15682700288056331364787171045819973654991149949197959929860861228180021707316851924456205543665565810892674190059831330231436970914474774562714945620519144389785158908994181951348846017432506464163564960993784254153395406799101314760033445065193429592512349952020982932218524462341002102063435489318813316464511621736943938440710470694912336237680219746204595128959161800595216366237538296447335375818871952520026993102148328897083547184286493241191505953601668858941129790966909236941127851370202421135897091086763569884760099112291072056970636380417349019579768748054760104838790424708988260443926906673795975104689`
### CERTainly not
- Huớng dẫn: challenge giới thiệu về file DER, ta cần tìm khóa n của file này.
- Hướng dẫn: file DER cũng tương tượng file PEM, ta sẽ làm tương tự như challenge trước
- Source code:
```py=
from Crypto.PublicKey import RSA
with open("2048b-rsa-example-cert.der", "rb") as f:
der = f.read()
a = RSA.importKey(der)
print(a.n)
```
- Vậy mình đã tìm được flag là `22825373692019530804306212864609512775374171823993708516509897631547513634635856375624003737068034549047677999310941837454378829351398302382629658264078775456838626207507725494030600516872852306191255492926495965536379271875310457319107936020730050476235278671528265817571433919561175665096171189758406136453987966255236963782666066962654678464950075923060327358691356632908606498231755963567382339010985222623205586923466405809217426670333410014429905146941652293366212903733630083016398810887356019977409467374742266276267137547021576874204809506045914964491063393800499167416471949021995447722415959979785959569497`
### SSH Keys
- Mô tả: challenge giới thiệu về giao thức ssh, ta phải lấy được flag là khó n từ file pub.
- Hướng dẫn: SSH là một giao thức mạng cho phép bạn thiết lập kết nối an toàn và mã hóa giữa sever-client. Mục đích là cung cấp một kênh truyền dữ liệu bảo mật.
- Cách làm vẫn tương tự như các challenge trước, file pub lưu trữ khóa RSA nên ta có thể lấy được khóa n từ file này.
- Source code:
```py=
from Crypto.PublicKey import RSA
with open("bruce_rsa.pub", "rb") as f:
ssh = f.read()
a = RSA.import_key(ssh)
print(a.n)
```
- Vậy mình đã tìm được flag là `3931406272922523448436194599820093016241472658151801552845094518579507815990600459669259603645261532927611152984942840889898756532060894857045175300145765800633499005451738872081381267004069865557395638550041114206143085403607234109293286336393552756893984605214352988705258638979454736514997314223669075900783806715398880310695945945147755132919037973889075191785977797861557228678159538882153544717797100401096435062359474129755625453831882490603560134477043235433202708948615234536984715872113343812760102812323180391544496030163653046931414723851374554873036582282389904838597668286543337426581680817796038711228401443244655162199302352017964997866677317161014083116730535875521286631858102768961098851209400973899393964931605067856005410998631842673030901078008408649613538143799959803685041566964514489809211962984534322348394428010908984318940411698961150731204316670646676976361958828528229837610795843145048243492909`
### Transparency
- Mô tả: challenge giới thiệu về giao thức TSL và kêu mình tìm tên miền phụ của cryptohack.org để lấy flag.
- Hướng dẫn: mình sẽ sử dụng tool scan trên web https://pentest-tools.com/information-gathering/find-subdomains-of-domain
- Khi scan mình đã tìm được 1 subdomain có tên trùng với tên challenge:
- Truy cập vào đó mình nhận được flag:
- Vậy mình đã tìm được flag `crypto{thx_redpwn_for_inspiration}`.
Sign in with Wallet
Connect another wallet