<h1 style="text-align:center;">Đại Số Trừu Tượng</h1>
## Phép toán hai ngôi
### Phép toán hai ngôi (Binary operation)
<img style="display: block; margin: auto;" width="400" src="https://hackmd.io/_uploads/rJ75vbHk1l.png"/>
- **Định nghĩa:** Một **phép toán hai ngôi (Binary operation)** là một phép toán sử dụng **hai biến** đầu vào và cho ra **một kết quả** với các biến và kết quả đều thuộc **một tập hợp**.
- Hay nói cách khác, một phép toán hai ngôi trên tập hợp $S$ là một ánh xạ **tích Descartes** $S \times S$ vào $S$:
$$f: S \times S \rightarrow S$$
- **Phép toán hai ngôi** được ký hiệu là $f(a,b)$, $a*b$, $a+b$, $a.b$ hoặc $ab$ luôn cho gọn.
- **Ví dụ** và **Tính chất:**
- Tên tập số thực $\mathbb{R}$, $f(a, b) = a + b$ là một phép toán hai ngôi vì tổng của hai số thực luôn là số thực.
- Tên tập số thực $\mathbb{R}$ thì $f(a, b) = a \times b$ cũng là phép toán hai ngôi.
- Cho tập số nguyên $\mathbb{Z}$, ta có phép cộng là $f(f(a+b)+c) = (a+b)+c$ $\Leftrightarrow$ $f(a+f(b+c)) = a + (b+c)$.
- Trên tập số nguyên $\mathbb{Z}$, $f(a, b) = a \times b$ cũng chính là $f(b, a) = b \times a$.
- Những ví dụ trên là đại diện cho hai tính chất của phép toán hai ngôi là **tính kết hợp** (associative) và **tính giao hoán** (commutative):
- Tính kết hợp: ${\forall a,b,c \in S,(a*b)*c=a*(b*c)}$.
- Tính giao hoán: ${\forall a,b \in S,a*b=b*a}$.
> Ngoài tính kết hợp và giao hoán thì phép toán hai ngôi còn có **Phần tử trung hòa/ Phần tử đơn vị** (identity elements) và **phần tử nghịch đảo** (inverse elements).
- Có phần tử trung hòa (phần tử đơn vị) $\theta$ thuộc $S$ nếu: ${\forall a \in S,\hspace{1mm} \theta *a=a*\theta=a}$.
- Có phần tử nghịch đảo $b$ thuộc $S$ nếu: ${\forall a,b,e \in S, \hspace{1mm} a * b = b * a = e}$ với $e$ là phần tử trung hòa (hoặc phần tử đơn vị). Mỗi $a$ tồn tại một $b$ độc nhất. Giá trị $b$ được gọi là nghịch đảo của $a$ và được ký hiệu là $a^{-1}$.
- Nhưng không phải lúc nào những tính chất trên cũng thỏa mãn. Ví dụ:
- Trên tập số thực $\mathbb{R}$ thì phép mũ $f(a, b) = a^{b}$ sẽ không có tính **giao hoán** bởi vì $a^{b} \neq b^{a}$.
- Phép mũ cũng không có tính kết hợp vì $f(f(a,b), c) \neq f(a, f(b,c))$. Ví dụ $a = 2, b = 3, c = 2$ thì $f(f(2,3), 2) = f(8,2) = 64$, nhưng $f(2, (3,2)) = f(2, 9) = 512$.
- Tương tự với phép trừ bởi vì $a - b \neq b - a$. Phép trừ cũng không có tính kết hợp do $a - (b-c) \neq (a-b) - c$.
## Nhóm
### Nhóm (Group)
- **Định nghĩa:** Cho $G$ là một tập khác rỗng cùng với phép toán hai ngôi ($*$) trong $G$. Khi đó $G$ được gọi là một **nhóm** nếu thỏa mãn ba tính chất sau:
- **Tính kết hợp** (Associativity): $$\begin{equation}
\forall x, y, z \in G, (x * y) * z = x * (y * z)
\end{equation}$$
- **Phần tử trung hòa / Phần tử đơn vị** (Identity element): $$\begin{equation}
\forall x,e \in G, x * e = e * x = x
\end{equation}$$
- **Phần tử nghịch đảo** (Inverse element): $$\begin{equation}
\forall x,y,e \in G, x * y = y * x = e
\end{equation}$$
- **Ví dụ:**
- Nhóm số nguyên với phép cộng $(\mathbb{Z}, +)$ thỏa mã các tính chất sau:
- Tính kết hợp: $a+(b+c) = (a+b)+c$.
- Phần tử trung hòa: là số $0$, vì $0+a = a+0 = a$.
- Phần tử nghịch đảo: với mọi số nguyên $a$ thì phần tử nghịch đảo của nó là $-a$, vì $a+(-a) = 0$.
- Nhóm các số thực khác $0$ với phép nhân $(\mathbb{R^{*}}, \times)$:
- Tính kết hợp: $(a×b)×c=a×(b×c)$.
- Phần tử đơn vị: Số $1$, vì $1×a=a×1=a$.
- Phần tử nghịch đảo: với mọi số thực khác $0$, nghịch đảo của $a$ là $\frac{1}{a}$ vì $a \times \frac{1}{a} = 1$.
### Nhóm con (Subgroup)
- **Định nghĩa:** Cho một nhóm $G$ với phép toán hai ngôi $(*)$, và tập con $H$ của $G$. Khi đó $H$ được gọi là nhóm con của $G$ nếu chính $H$ là một nhóm với phép toán $(*)$ của $G$. Thường được ký hiệu là $H < G$.
- **Ví dụ:**
- Tập hợp số nguyên chẵn $2 \mathbb{Z} = \left\{..., -2, 0, 2, 4, ... \right\}$ là một nhóm con của nhóm $\mathbb{Z}$ với phép cộng.
- Tập $2 \mathbb{Z}$ thỏa tính chất đóng vì tổng của hai số chẵn luôn là số chẵn.
- Phần tử trung hòa là $0$, vẫn nằm trong tập $2 \mathbb{Z}$.
- Phần tử nghịch đảo của mỗi số $2a$ trong tập $2 \mathbb{Z}$ là $-2a$, cũng là một số chẵn.
- Tập hợp số nguyên $\mathbb{Z}$ là một nhóm con của $\mathbb{R}$ dưới phép cộng vì nó thỏa mãn các tính chất sau:
- Đóng: Tổng của hai số nguyên là một số nguyên.
- Phần tử trung hòa: Số $0$.
- Phần tử nghịch đảo: Với mỗi số nguyên $a$, nghịch đảo của nó là $-a$ cũng là một số nguyên và thuộc $\mathbb{R}$.
### Nhóm Cylic (Cyclic group)
- **Định nghĩa:** Một nhóm $G$ khác rỗng được gọi là nhóm **Cyclic** nếu trong $G$ tồn tại một phần tử $g$ mà ở đó người ta có thể tạo ra một tập con là tập hợp tất cả các lũy thừa của phần tử $g$. Hay tất cả các phần tử có thể được biểu diễn như là lũy thừa của một phần tử duy nhất, phần tử đó gọi là **phần tử sinh** của nhóm.
$$ ⟨g⟩ = \left\{ g^{k} \hspace{2mm}|\hspace{2mm} k \in \mathbb{Z} \right\}$$
- **Ví dụ:**
- Nếu $G = \left\{e = g^{0}, g^{1}, g^{2}, g^{3}, g^{4}, g^{5}... \right\}$ thì $G$ là nhóm Cyclic với $g$ là phần tử sinh.
- Nhóm $\mathbb{Z}_{7}^{*} = \left\{1,2,3,4,5,6\right\}$ với phép nhân modulo $7$ là một nhóm xyclic vì nó tồn tại phần tử $g$ mà có thể tạo ra được tất cả các phần tử trong nhóm, đó là số $3$ vì:
- $3^{1} \equiv 3 \pmod p$
- $3^{2} \equiv 2 \pmod p$
- $3^{3} \equiv 6 \pmod p$
- $3^{4} \equiv 4 \pmod p$
- $3^{5} \equiv 5 \pmod p$
- $3^{6} \equiv 1 \pmod p$
$\Rightarrow \mathbb{Z}_{7}^{*}= \left< 3\right>$
- Nhóm $\mathbb{Z}_{n} = \left\{0,1,2, ...n-1\right\}$ với phép cộng modulo $n$ là một nhóm cyclic vì nó có phần tử sinh là $1$ và mọi phần tử của $\mathbb{Z}_{n}$ đều có thể được biểu diễn dưới dạng $1 \times k\pmod n$ với $k \in \left\{0, 1, 2,... n-1\right\}$. Ví dụ nếu $n=5$:
- $\mathbb{Z}_{5} = \left\{0,1,2,3,4\right\}$ với phần tử sinh là $1$, ta có
- $1+1 \equiv 2 \pmod 5$
- $1+1+1 \equiv 3 \pmod 5$
- $1+1+1+1 \equiv 4 \pmod 5$
- $1+1+1+1+1 \equiv 0 \pmod 5$
$\Rightarrow \mathbb{Z}_{7}= \left< 1\right>$
>Nhóm $\mathbb{Z}_{n}$là tập hợp các số nguyên từ 0 đến n−1 với phép toán là phép **cộng modulo**. Còn nhóm $\mathbb{Z}_{n}^{*}$ là tập hợp các số nguyên dương nhỏ hơn n và nguyên tố cùng với n với phép toán là phép **nhân modulo**.
### Bậc của một nhóm (Order)
- **Định nghĩa:** order của một nhóm (hay còn gọi là bậc của nhóm) là số lượng phần tử trong nhóm đó. Nếu một nhóm $G$ có $n$ phần tử, thì ta nói nhóm $G$ có bậc $n$, ký hiệu là $|G| = n$.
- Nếu $|G| = \infty$ thì $G$ có vô số phần tử, gọi là nhóm vô hạn.
- Ngược lại nếu $|G| = n$ thì $G$ có $n$ phần tử, gọi là nhóm hữu hạn.
- Bên cạnh bậc của một nhóm, ta có định nghĩa về bậc của một phần tử như sau: Bậc của một phần tử $g \in G$ là một số nguyên dương $n$ nhỏ nhất sao cho $g^{n} = e$ với $e$ là phần tử đơn vị (hoặc phần tử trung hòa) của nhóm.
- **Ví dụ:**
- Tìm cấp của các phần tử trong $\mathbb{Z}_{20}^{*}$ với phép toán $modulo(n)$:
- Ta có $\mathbb{Z}_{20}^{*} = \left\{ 1,3,7,9,11,13,17,19\right\}$
- Ví dụ cấp của $7$ sẽ là $4$ vì: $7^{4} \equiv 1 \hspace{2mm} (mod \hspace{2mm} 20)$
- Làm theo cách trên ta lập được bảng sau:
|a|1|3|7|9|11|13|17|19|
|:--|:----:|:----:|:----:|:----:|:----:|:----:|:----:|---:|
|**ord(a)**|1|4|4|2|2|4|4|2
>Fun fact: cho $\alpha \in \mathbb{Z}_{n}^{*}$. Nếu $ord(\alpha) = \phi(n)$ thì $\alpha$ là phần tử sinh của $\mathbb{Z}_{n}^{*}$ và khi này $\mathbb{Z}_{n}^{*}$ được gọi là nhóm Cyclic. Vậy ở ví dụ trên $\mathbb{Z}_{20}^{*}$ sẽ không có phần tử sinh vì $\phi(20) = 8$ nhưng không có phần tử nào mà có $ord$ bằng $8$.
## Vành và Trường
### Vành (Ring)
- **Định nghĩa:** Một tập hợp khác rỗng $R$ được gọi là **Vành** nếu trên đó có hai phép toán hai ngôi là **phép cộng** (addition) và **phép nhân** (multiplication) thỏa các tính chất sau:
- $R$ là một nhóm giao hoán đối với phép cộng, nghĩa là:
- Tính kết hợp: $\forall x,y,z \in \mathbb{R}: (x+y)+z = x+(y+z)$
- Tính giao hoán: $\forall x,y \in \mathbb{R}: x+y=y+x$
- Phần tử trung hòa: $\exists 0 \in \mathbb{R}: 0+x=x+0=x$
- Mọi phần tử của $R$ có phần tử nghịch đảo: $\forall x \in \mathbb{R}, \exists x{'} :x+x{'} = x^{'}+x=0$
- Phép nhân có tính phân phối với phép cộng, nghĩa là:
- $\forall x,y,z \in \mathbb{R}: x \times (y+z) = x\times y+x \times z$ (phân phối phải)
- $\forall x,y,z \in \mathbb{R}: (x +y) \times z = x\times z+y \times z$ (phân phối trái)
- Phép nhân có tính kết hợp, nghĩa là: $\forall x,y,z \in \mathbb{R}: (x\times y)\times z = x \times (y \times z)$
- Phép nhân có phần tử đơn vị, nghĩa là: $\exists 1, \forall x \in \mathbb{R}: 1\times x = x \times 1 = x$
- Vành $R$ được gọi là **vành có đơn vị** nếu phép nhân có phần tử đơn vị khác $0$:
- Vành số nguyên $\mathbb{Z}$ có phần tử đơn vị là $1$: $a \times 1 = 1 \times a = a$
- Vành ma trận $2\times2$ có phần tử đơn vị là:
$$\begin{pmatrix}
1 &0 \\
0&1 \\
\end{pmatrix}$$
- Vành số chẵn $2 \mathbb{Z}$ *không phải* là một vành có đơn vị vì không tồn tại phần tử đơn vị cho phép nhân. Không thể tìm được số chẵn $x$ nào sao cho $2 \times x = 2$.
- Vành $R$ được gọi là **vành giao hoán** nếu phép nhân có tính giao hoán.
- Vành số nguyên $\mathbb{Z}$ là một ví dụ điển hình của vành giao hoán vì $\forall x,y \in \mathbb{Z}: a\times b = b \times a$, tương tự với vành số thực $\mathbb{R}$.
- Vành đa thức $\mathbb{R}[x]$: Tập hợp các đa thức với hệ số thực và phép cộng, phép nhân đa thức là một vành giao hoán. Ví dụ, với hai đa thức $p(x) = 2x+3$ và $q(x) = x^{2} + 1$, ta có $p(x) \times q(x) = q(x) \times p(x) = 2x^{3} + 3x^{2} +2x + 3$
- Nhưng vành ma trận $2\times2$ không phải là một vành giao hoán, ví dụ:
$$A = \begin{pmatrix}
1 &2 \\
0 &1 \\
\end{pmatrix},
B = \begin{pmatrix}
0 &1 \\
1 &0 \\
\end{pmatrix}$$
thì $A \times B \neq B \times A$
### Trường (Field)
- **Định nghĩa:** Vành $A$ được gọi là trường nếu $A$ là một vành giao hoán có phần tử đơn vị khác $0$ và **với mọi** phần tử khác $0$ của $A$ đều có phần tử nghịch đảo với phép nhân tức $\forall x \neq 0 \in A ,\exists \hspace{1mm} x^{-1}: x \times x^{-1} = 1$.
- **Ví dụ:**
- Trường số hữu tỉ $\mathbb{Q}$, số thực $\mathbb{R}$ và số phức $\mathbb{C}$ thỏa mãn các tính chất sau:
- Tính kết hợp: $(x + y) + z = x + (y + z) \hspace{2mm} \forall x, y, z \in \mathbb{Z}$
- Tính giao hoán: $x+y = y + x, \forall x,y \in \mathbb{Z}$
- Phần tử trung hòa: số $0$
- Phần tử đối xứng: $x + (-x) = 0$
- Phần tử đơn vị: số $1$
- Phần từ nghịch đảo: $\forall x \neq0, \exists \hspace{1mm} x^{-1}: x \times x^{-1} = 1$.
- Tính phân phối: $x.(y+z) = x.y + x.z, \hspace{1mm} z.(x+y)= z.x + z.y$
- Nhưng tập số nguyên $\mathbb{Z}$ không phải là một trường vì với mọi phần tử $x$ khác $0$ của tập không tồn tại phần tử nghịch đảo là $\frac{1}{x} \in \mathbb{Z}$. Nên nó chỉ là một vành giao hoán có đơn vị.
<h1 style="text-align:center;">DIFFIE-HELLMAN</h1>
<img style="display: block; margin: auto;" width="500" src="https://hackmd.io/_uploads/Sytt5Or2A.png"/>
- **Diffie-Hellman** là một giao thức mật mã cho phép hai bên trao đổi khóa bí mật một cách an toàn qua một kênh không an toàn. Được *Whitfield Diffie* và *Martin Hellman* giới thiệu vào năm 1976, đây là một trong những phương pháp đầu tiên cho phép chia sẻ khóa bí mật mà không cần phải trao đổi trực tiếp hoặc thông qua một kênh an toàn nào.
- **Tóm tắt thuật toán:**
- **Bước 1:** Chọn một số nguyên tố lớn (gọi là $p$) và phần tử sinh của $\mathbb{Z}^{*}_{p}$ gọi là $g$. Hai số $p$ & $g$ đã được hai người $A$ và $B$ thỏa thuận từ trước và chúng sẽ được gửi công khai.
- **Bước 2:** $A$ và $B$ sẽ tự tạo cho mình một **khóa bí mật** gọi là $a$ và $b$
- **Bước 3:** Bây giờ mỗi người sẽ tự tạo **khóa công khai** cho mình (gọi là $C_{A}$ hoặc $C_{B}$) và gửi đi cho người còn lại, công thức như sau:
- $C_{A} \equiv g^{a} \pmod p$
- $C_{B} \equiv g^{b} \pmod p$
- **Bước 4:** Khi $A$ nhận được $C_{B}$ và $B$ nhận được $C_{A}$ thì cả hai sẽ tạo được **khóa chung** bằng cách lấy `khóa công khai` **mũ** lên `khóa bí mật` lần rồi lấy **modulo p**, dựa theo công thức sau:
- $K_{A} \equiv {C_{B}}^{a} \pmod p \equiv {[g^{b} \pmod p]}^{a} \equiv g^{a\times b} \pmod p$
- $K_{B} \equiv {C_{A}}^{b} \pmod p \equiv {[g^{a} \pmod p]}^{b} \equiv g^{a\times b} \pmod p$
- Như ta thấy thì $K_{A} = K_{B}$ nên cả $A$ và $B$ đã gửi thành công khóa bí mật $K$ cho nhau mà không cần phải đưa nó qua bất cứ bên thứ hai nào.
- **Ví dụ:** $Bob$ và $Alice$ muốn gửi khóa chung cho nhau, họ thống nhất rằng sẽ chọn số nguyên tố $p = 23$ và $g = 5$. Alice chọn cho mình khóa bí mật $a = 6$ và Bob chọn $b = 15$.
- Đầu tiên Alice tính khóa công khai: $C_{A} \equiv 5^{6} \pmod {23} = 8$. Khóa công khai của Bob cũng tương tự, sẽ bằng: $C_{B} \equiv 5^{15} \pmod {23} = 19$.
- Khi Alice nhận được $C_{B}$ cô sẽ tính khóa chung băng công thức sau: $K \equiv {C_{B}}^{a} \equiv 19^{6} \pmod {23} = 2$.
- Bob cũng tính tương tự: $K \equiv {C_{A}}^{b} \equiv 8^{15} \pmod {23} = 2$.
$\Rightarrow$ Vậy cả hai đã chia sẽ thành công khóa chung cho nhau, đó là $K = 2$
<h1 style="text-align:center;">CryptoHack</h1>
Bài báo năm 1976 của *Whitfield Diffie* và *Martin Hellman* có tựa đề *"**New Directions in Cryptography**"* đã đánh dấu một bước tiến lớn cho lĩnh vực mật mã học. Bài báo này đã định nghĩa các khái niệm như **khóa công khai**, **hàm một chiều**, **chữ ký số**... Đồng thời mô tả một phương pháp trao đổi khóa bí mật một cách an toàn qua một kênh không an toàn. Đó là phương pháp trao đổi khóa **Diffie-Hellman**.
**Diffie-Hellman (DH)** dựa trên giả định rằng bài toán **logarit rời rạc (DLP)** rất khó giải. Tuy nhiên, trong thực tế, các tham số cần phải được chọn một cách cẩn thận, nếu không logarit rời rạc có thể dễ dàng bị phá vỡ, chúng ta sẽ học cách để làm quen với chúng qua những challenge bên dưới. Hơn nữa, phiên bản cơ bản nhất của giao thức này rất dễ bị tấn công bởi kiểu tấn công **man-in-the-middle**, cho thấy rằng **DH** đòi hỏi bạn phải xác thực cẩn thận đối với những đối tượng mà bạn đang giao tiếp.
## STARTER
### Working with Fields
- **Mô tả:** Challenge này cho ta một cái nhìn thoáng qua về định nghĩa của **vành, trường** và yêu cầu ta tìm **phần tử nghịch đảo** của một phần tử thuộc một trường hữu hạn.
- Cho một tập hợp số nguyên dưới phép toán modulo $N$ cùng với hai phép toán hai ngôi là phép cộng và phép nhân tạo thành một **vành** $\mathbb{Z}/\mathbb{NZ}$. Về cơ bản, vành nghĩa là khi ta thực hiện phép cộng hoặc phép nhân của bất kì hai phần tử nào thuộc một tập hợp thì sẽ luôn trả về một kết quả thuộc tập hợp đó.
- Khi $N = p$ là một số nguyên tố, thì chắc chắn rằng mọi phần tử trong vành sẽ có phần tử nghịch đảo, khi này vành của ta sẽ được gọi là một **trường**, kí hiệu là $\mathbb{F}_{p}$.
- Quay lại với bài toán, đề yêu cầu ta tìm *nghịch đảo* của $g = 200$ trong modulo $p=991$ hay tìm $d = g^{-1}$ sao cho $g.d \equiv 1$ $mod$ $p$.
- Bài toán khá đơn giản, chỉ cần dùng hàm **pow()** là xong.
- Đoạn code như sau:
```python
print(pow(200, -1, 991))
```
:::spoiler Flag
**441**
:::
### Generators of Groups
- **Mô tả:** Challenge này giới thiệu cho chúng ta về phần tử nguyên thủy hay phần tử sinh và yêu cầu tìm phần tử nguyên thủy trong một trường hữu hạn cho trước.
- Mỗi phần tử của một trường hữu hạn $\mathbb{F}_{p}$ có thể được dùng để tạo nên một nhóm con $\mathbb{H}$ bằng cách thực hiện phép nhân lặp lại một cách liên tục. Hay nói cách khác, cho một phần tử $g \in \mathbb{F}_{p}$, nhóm con $\mathbb{H}$ được tạo ra từ $g$ là:
$$\mathbb{H} = \left< g\right> = \left\{g, g^{2}, g^{3}...\right\}$$
- Một phần tử nguyên thủy $g$ của $\mathbb{F}_{p}$ sẽ là một phần tử có nhóm con là $\mathbb{H} = \mathbb{F}_{p}^{*}$. Tức tập con sinh ra bởi các lũy thừa của nó ($g^{n}$) bao trùm toàn bộ $\mathbb{F}_{p}^{*}$. Nghĩa là tất cả các phần tử khác $0$ của trường $\mathbb{F}_{p}$ đều có thể viết dưới dạng:
$$g^{n} \mod p \hspace{2mm} | \hspace{2mm} n \in \mathbb{Z}$$
- **Quay trở lại với challenge:** đề cho ta một trường hữu hạn với $p = 28151$ và yêu cầu ta tìm phần tử $g$ nhỏ nhất sao cho nó là phần tử nguyên thủy của $\mathbb{F}_{p}$
- **Cách 1**: Từ định lý **Lagrange**, ta sẽ sử dụng tính chất sau. Nếu $g$ là phần tử nguyên thủy, thì với mỗi thừa số nguyên tố $q$ của $p-1$, ta có $g^{(\frac{p-1}{q})} \not\equiv 1 \pmod p$.
- Từ định lý trên, ta tìm phần tử sinh $g$ như sau:
```python
p = 28151
p_minus_1 = p - 1
# Factorize p-1
factors = [2, 5, 563]
def is_primitive_element(g, p, factors):
for q in factors:
if pow(g, p_minus_1 // q, p) == 1:
return False
return True
primitive_root = None
for g in range(2, p):
if is_primitive_element(g, p, factors):
primitive_root = g
print(g)
break
```
- **Cách 2:** sử dụng phương thức **primitive_element()** trong thư viện **sage**:
:::spoiler Flag
**7**
:::
### Computing Public Values
- **Mô tả:** Challenge này hướng dẫn ta cách tạo khóa công khai từ những giá trị cho trước và yêu cầu ta tạo một khóa công khai như vậy.
- Giao thức **Diffie-Hellman** được sử dụng vởi vì bài toán **Logarit rời rạc** được cho là rất khó để giải nếu như chọn các tham số một cách cẩn thận.
- Bước đầu tiên là tạo một số nguyên tố $p$ đủ lớn và tìm một phần tử sinh của trường, gọi là $g$. Hai số trên phải được chọn lựa kỹ càng nếu không bài toán logarit rời rạc có thể bị bẻ gãy. Ví dụ, một số nguyên tố $p$ an toàn sẽ có dạng là $p = 2.q+1$ vì khi $p-1$ được phân tích thành thừa số nguyên tố là $\left\{2,q\right\}$ mà $q$ lại là một số nguyên tố lớn khác. Điều này bảo vệ **DH** khỏi kiểu tấn công **Pohlig–Hellman algorithm**.
- Sau đó người gửi chọn cho mình một số nguyên bí mật $a<p-1$ và tính toán giá trị $A \equiv g^{a} \pmod p$. Giá trị $A$ sau đó sẽ được gửi qua một môi trường mạng không đảm bảo nên giá trị $a$ của ta phải được đảm bảo là không thể giải ra bằng logarit rời rạc được.
- Challenge yêu cầu ta tính khóa công khai thông qua những giá trị mà đề cho là $g,p$ và $a$. Công thức sẽ là:
$$g^{a} \mod p$$
- Đoạn code như sau:
```python
g = 2
p = 2410312426921032588552076022197566074856950548502459942654116941958108831682612228890093858261341614673227141477904012196503648957050582631942730706805009223062734745341073406696246014589361659774041027169249453200378729434170325843778659198143763193776859869524088940195577346119843545301547043747207749969763750084308926339295559968882457872412993810129130294592999947926365264059284647209730384947211681434464714438488520940127459844288859336526896320919633919
a = 972107443837033796245864316200458246846904598488981605856765890478853088246897345487328491037710219222038930943365848626194109830309179393018216763327572120124760140018038673999837643377590434413866611132403979547150659053897355593394492586978400044375465657296027592948349589216415363722668361328689588996541370097559090335137676411595949335857341797148926151694299575970292809805314431447043469447485957669949989090202320234337890323293401862304986599884732815
print(pow(g,a,p))
```
:::spoiler Flag
**1806857697840726523322586721820911358489420128129248078673933653533930681676181753849411715714173604352323556558783759252661061186320274214883104886050164368129191719707402291577330485499513522368289395359523901406138025022522412429238971591272160519144672389532393673832265070057319485399793101182682177465364396277424717543434017666343807276970864475830391776403957550678362368319776566025118492062196941451265638054400177248572271342548616103967411990437357924**
:::
### Computing Shared Secrets
- **Mô tả:** Challenge này yêu cầu ta tính **khóa chung** từ những dữ liệu là đề cho trước.
- Có được những thông tin là: $g, p, A$, ta trong vai người $B$ sẽ sử dụng công thức: $$K \equiv A^{b} \pmod p$$
- Đoạn code như sau:
```python
g = 2
p = 2410312426921032588552076022197566074856950548502459942654116941958108831682612228890093858261341614673227141477904012196503648957050582631942730706805009223062734745341073406696246014589361659774041027169249453200378729434170325843778659198143763193776859869524088940195577346119843545301547043747207749969763750084308926339295559968882457872412993810129130294592999947926365264059284647209730384947211681434464714438488520940127459844288859336526896320919633919
b = 12019233252903990344598522535774963020395770409445296724034378433497976840167805970589960962221948290951873387728102115996831454482299243226839490999713763440412177965861508773420532266484619126710566414914227560103715336696193210379850575047730388378348266180934946139100479831339835896583443691529372703954589071507717917136906770122077739814262298488662138085608736103418601750861698417340264213867753834679359191427098195887112064503104510489610448294420720
A = 70249943217595468278554541264975482909289174351516133994495821400710625291840101960595720462672604202133493023241393916394629829526272643847352371534839862030410331485087487331809285533195024369287293217083414424096866925845838641840923193480821332056735592483730921055532222505605661664236182285229504265881752580410194731633895345823963910901731715743835775619780738974844840425579683385344491015955892106904647602049559477279345982530488299847663103078045601
print(pow(A,b,p))
```
:::spoiler Flag
**1174130740413820656533832746034841985877302086316388380165984436672307692443711310285014138545204369495478725102882673427892104539120952393788961051992901649694063179853598311473820341215879965343136351436410522850717408445802043003164658348006577408558693502220285700893404674592567626297571222027902631157072143330043118418467094237965591198440803970726604537807146703763571606861448354607502654664700390453794493176794678917352634029713320615865940720837909466**
:::
### Deriving Symmetric Keys
- **Mô tả:** Challenge này cho ta biết cách ứng dụng Diffie-Hellman vào việc trao đổi khóa bí mật của **AES** và cung cấp hai file: `source.py` là cách mà đề mã hóa thông điệp và file `decrypt.py` là file mà ta sẽ dùng để giải mã Ciphertext.
- Đọc hàm **encrypt_flag()** ta thấy **Key** của AES được tính bằng cách băm **khóa chung** của cả hai qua đoạn code sau:
```python
# Derive AES key from shared secret
sha1 = hashlib.sha1()
sha1.update(str(shared_secret).encode('ascii'))
key = sha1.digest()[:16]
```
- Vì thế, để có **key** thì ta phải đi tính **khóa chung**, cách tính sẽ tương tự như bài trước, sau khi có được khóa chung thì ta sẽ truyền ba tham số trên vào hàm **decrypt_flag** trong file `decrypt.py` để giải mã Ciphertext.
- Tính **shared_secret**:
```python
g = 2
p = 2410312426921032588552076022197566074856950548502459942654116941958108831682612228890093858261341614673227141477904012196503648957050582631942730706805009223062734745341073406696246014589361659774041027169249453200378729434170325843778659198143763193776859869524088940195577346119843545301547043747207749969763750084308926339295559968882457872412993810129130294592999947926365264059284647209730384947211681434464714438488520940127459844288859336526896320919633919
A = 112218739139542908880564359534373424013016249772931962692237907571990334483528877513809272625610512061159061737608547288558662879685086684299624481742865016924065000555267977830144740364467977206555914781236397216033805882207640219686011643468275165718132888489024688846101943642459655423609111976363316080620471928236879737944217503462265615774774318986375878440978819238346077908864116156831874695817477772477121232820827728424890845769152726027520772901423784
b = 197395083814907028991785772714920885908249341925650951555219049411298436217190605190824934787336279228785809783531814507661385111220639329358048196339626065676869119737979175531770768861808581110311903548567424039264485661330995221907803300824165469977099494284722831845653985392791480264712091293580274947132480402319812110462641143884577706335859190668240694680261160210609506891842793868297672619625924001403035676872189455767944077542198064499486164431451944
print(pow(A,b,p))
#kết quả: 1547922466740669851136899009270554812141325611574971428561894811681012510829813498961168330963719034921137405736161582760628870855358912091728546731744381382987669929718448423076919613463237884695314172139247244360699127770351428964026451292014069829877638774839374984158095336977179683450837507011404610904412301992397725594661037513152497857482717626617522302677408930050472100106931529654955968569601928777990379536458959945351084885704041496571582522945310187
```
- Truyển ba tham số trên vào hàm **decrypt_flag** để giải mã $Flag$. Đoạn code như sau:
```python
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad, unpad
import hashlib
def is_pkcs7_padded(message):
padding = message[-message[-1]:]
return all(padding[i] == len(padding) for i in range(0, len(padding)))
def decrypt_flag(shared_secret: int, iv: str, ciphertext: str):
# Derive AES key from shared secret
sha1 = hashlib.sha1()
sha1.update(str(shared_secret).encode('ascii'))
key = sha1.digest()[:16]
# Decrypt flag
ciphertext = bytes.fromhex(ciphertext)
iv = bytes.fromhex(iv)
cipher = AES.new(key, AES.MODE_CBC, iv)
plaintext = cipher.decrypt(ciphertext)
if is_pkcs7_padded(plaintext):
return unpad(plaintext, 16).decode('ascii')
else:
return plaintext.decode('ascii')
shared_secret = 1547922466740669851136899009270554812141325611574971428561894811681012510829813498961168330963719034921137405736161582760628870855358912091728546731744381382987669929718448423076919613463237884695314172139247244360699127770351428964026451292014069829877638774839374984158095336977179683450837507011404610904412301992397725594661037513152497857482717626617522302677408930050472100106931529654955968569601928777990379536458959945351084885704041496571582522945310187
iv = "737561146ff8194f45290f5766ed6aba"
ciphertext = "39c99bf2f0c14678d6a5416faef954b5893c316fc3c48622ba1fd6a9fe85f3dc72a29c394cf4bc8aff6a7b21cae8e12c"
print(decrypt_flag(shared_secret, iv, ciphertext))
```
:::spoiler Flag
**crypto{sh4r1ng_s3cret5_w1th_fr13nd5}**
:::
## MAN IN THE MIDDLE
### Parameter Injection
**nc socket.cryptohack.org 13371**
- **Mô tả:** Challenge này ta sẽ nhập vai vào hacker, chặn được tin nhắn được gửi từ hai bên và còn có thể chỉnh sửa chúng. Bạn sẽ suy nghĩ xem nên sửa tin nhắn như thế nào để có thể đọc được tin nhắn bị mã hóa bằng AES đây?
- **Tóm tắt:** $Alice$ gửi cho $Bob$ $g,p$ và khóa công khai của cô, Bob sau khi nhận được thì cũng gửi ngược lại $B$ của mình. Cô sau khi nhận được $B$ thì tiến hành tính **Khóa chung** và dùng nó để làm **Key** mã hóa AES. Sau đó Alice gửi cho Bob $IV$ và văn bản đã được mã hóa. Mỗi lần gửi qua gửi lại như vậy thì ta đều có thể chặn và sửa đổi được.
- Khi ta kết nối tới server thì nhận được tin nhắn sau:
> Khi này ta là người thứ ba và bắt được đoạn tin nhắn trên. Nó bao gồm $p,g$ và $A$. Ta sẽ không can thiệp vào mà gửi nguyên văn cho Bob.
- Sau khi gửi tin nhắn của Alice cho Bob thì cậu ta sẽ gửi ngược lại cho Alice khóa công khai của mình là $B$:
- Nhớ rằng Alice sẽ sử dụng khóa công khai của Bob là $B$ để tính khóa chung bằng công thức $K \equiv B^{a} \pmod p$. Nên ta sẽ gửi cho Alice $B = 1$ để khi cô đem $B$ mũ lên $a$ lần thì nó vẫn là $1$
- Ta sẽ gửi cho Alice đoạn tin nhắn sau: **{"B" = 0x01}**.
- Alice sau khi nhận được $B$ thì tiến hành tính khóa chung và dĩ nhiên thì nó bằng $1$, giờ thì ta chỉ cần chờ cô gửi $IV$ và văn bản bị mã hóa rồi dùng khóa chung là $1$ để giải.
- Ta có những dữ kiện:
```python
shared_secret = 1
iv = "0e0239fe9baab8e129434979585fd0c8"
ciphertext = "6263f82bc6a2167d274d20cff20f584f84ae4cb3cbd2633b60733e2a6a8e77af"
```
- Ta sẽ bỏ $3$ tham số trên vào hàm **Decrypt_flag** ở challenge trước để giải mã, đoạn code như sau:
```python
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad, unpad
import hashlib
def is_pkcs7_padded(message):
padding = message[-message[-1]:]
return all(padding[i] == len(padding) for i in range(0, len(padding)))
def decrypt_flag(shared_secret: int, iv: str, ciphertext: str):
# Derive AES key from shared secret
sha1 = hashlib.sha1()
sha1.update(str(shared_secret).encode('ascii'))
key = sha1.digest()[:16]
# Decrypt flag
ciphertext = bytes.fromhex(ciphertext)
iv = bytes.fromhex(iv)
cipher = AES.new(key, AES.MODE_CBC, iv)
plaintext = cipher.decrypt(ciphertext)
if is_pkcs7_padded(plaintext):
return unpad(plaintext, 16).decode('ascii')
else:
return plaintext.decode('ascii')
shared_secret = 1
iv = "0e0239fe9baab8e129434979585fd0c8"
ciphertext = "6263f82bc6a2167d274d20cff20f584f84ae4cb3cbd2633b60733e2a6a8e77af"
print(decrypt_flag(shared_secret, iv, ciphertext))
```
:::spoiler Flag
**crypto{n1c3_0n3_m4ll0ry!!!!!!!!}**
:::
### Export-grade
**nc socket.cryptohack.org 13379**
- **Mô tả:** Challenge này chúng ta cũng làm hacker ngăn chặn tin nhắn gửi từ hai bên như challenge trước nhưng lần này ta sẽ không mạnh bằng vì không thể chỉnh sửa toàn bộ tin nhắn để gửi đi. Mặc dù vậy thì challenge này cũng tạo ra lỗ hổng khác để ta khai thác.
- **Tóm tắt:** $Alice$ muốn gửi tin nhắn cho $Bob$ nhưng trước khi gửi thì cô muốn xác nhận rằng Bob muốn cô dùng kiểu *sinh khóa Diffie-Hellman* nào để mã hóa tin nhắn. Sau khi Bob chọn thì Alice sẽ tiến hành gửi $p,g,A$ theo kiểu sinh khóa đó. Anh cũng gửi lại $B$ rồi nhận được $IV$ và **encrypted_flag** từ cô. Mỗi lần gửi qua gửi lại như vậy thì chúng ta có thể xem được và chỉnh sửa được một số thứ.
- Khi kết nối tới server thì ta nhận được tin nhắn là tệp **Json** sau:
- **Alice** muốn **Bob** chọn kiểu sinh khóa nào mà anh muốn, chính là độ dài của modulus $p$, cô sẽ mã hóa theo độ dài đó. Alice nói rằng cô hỗ trợ mã hóa $p$ dài $1536$ bits, $1024$ bits, $512$ bits, $256$ bits, $128$ bits và $64$ bits.
- Ta sẽ thay đổi đoạn tin nhắn trên, chỉ gửi cho Bob **{"supported": ["DH64"]}** là kiểu có độ dài $p$ ngắn nhất, vì nó ngắn nên chắc chắn sẽ dễ bị tấn công.
- Vì ta chỉ gửi cho Bob đúng một kiểu nên anh không thể chọn kiểu khác được mà bắt buộc phải chọn **DH-64**, sau đó ta sẽ gửi cho Alice kiểu mà Bob đã chọn:
- Sau khi xác định được độ dài khóa mà Bob chọn thì Alice tiến hành gửi $p,g$ và tính khóa công khai $A$, sau đó gửi qua cho Bob, anh cũng gửi lại $B$ và nhận lại $IV$ và **encrypted_flag** (quá trình trên ta không thể can thiệp để chỉnh sửa).
- Bây giờ có trong tay những dữ kiện sau, bạn sẽ làm gì để giải mã ra **encrypted_flag**:
```python
p = 0xde26ab651b92a129
g = 0x02
A = 0xb3d610a9ea07bad0
B = 0x1b6d84351d043a81
IV = "b9d98bb5d65cc1ebba464c02900429a2"
ciphertext = "a25bf854668a9615d034bc8abdf15b7eba9ae67427c75a4f8754e458189c5577"
```
- Nhớ rằng $Flag$ được mã hóa AES nên ta phải tìm được $key$ thì mới có hy vọng giải được. Mà **Key** được tính từ **khóa chung** $K$ của Alice và Bob nên ta phải tìm cách để tính được nó.
$$K \equiv g^{a\times b} \pmod p$$
- Nếu tìm được tích $a$ và $b$ thì sẽ dễ dàng tình được $K$, nhưng ta sẽ phải giải phương trình Logarit rời rạc (DLP), thứ được cho là rất khó để giải nếu như các tham số được chọn một cách cẩn thận.
$\Rightarrow$ Thế nên Challenge đã tạo lỗ hổng cho ta khai thác đó là cho $p$ có độ dài thấp để ta có thể giải được phương trình Logarit rời rạc trên.
- **Hướng giải:**
- Để tìm được tích $a \times b$, đầu tiên ta tìm $a$ bằng cách giải phương trình Logarit rời rạc sau:
$$A \equiv g^{a} \pmod p$$
- Có $a$ thì ta chỉ cần thế vào phương trình tìm $K$ của Alice là có được $K$:
$$K \equiv B^{a}\pmod p$$
- Có $K, IV,$ **decrypted_flag** thì chỉ cần bỏ vào hàm `decrypted` ở bài trước là sẽ giải mã thành công $Flag$.
- Cách giải phương trình $A \equiv g^{a} \pmod p$ và tính $K$:
- Biến đổi phương trình trên thành: $a \equiv log_{g}A$ $mod$ $p$.
- Sử dụng hàm **discrete_log()** từ thư viện $Sage$ để tìm $a$.
- Câu lệnh:
- `discrete_log(A, g)`.
- $A$ là là số bạn muốn tìm logarit đem $mod$ cho $p$.
- $g$ là cơ số đem $mod$ cho $p$.
- Đoạn code như sau:
```python
#sage
p = 0xde26ab651b92a129
A = Mod(0xb3d610a9ea07bad0, p)
g = Mod(0x02, p)
a = discrete_log(A, g)
show(a) #4367044532041757184
```
- Sau khi có $a$ thì ta tính $K$ theo đoạn code sau:
```python
#sage
p = 0xde26ab651b92a129
B = 0x1b6d84351d043a81
a = 4367044532041757184
K = pow(B, a, p)
show(K) #7353727325691585831
```
- Khi có được $K, IV,$ **decrypted_flag** thì ta truyền vào hàm `decrypted` ở bài trước để giải mã ra $Flag$. Đoạn code như sau:
```python
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad, unpad
import hashlib
def is_pkcs7_padded(message):
padding = message[-message[-1]:]
return all(padding[i] == len(padding) for i in range(0, len(padding)))
def decrypt_flag(shared_secret: int, iv: str, ciphertext: str):
# Derive AES key from shared secret
sha1 = hashlib.sha1()
sha1.update(str(shared_secret).encode('ascii'))
key = sha1.digest()[:16]
# Decrypt flag
ciphertext = bytes.fromhex(ciphertext)
iv = bytes.fromhex(iv)
cipher = AES.new(key, AES.MODE_CBC, iv)
plaintext = cipher.decrypt(ciphertext)
if is_pkcs7_padded(plaintext):
return unpad(plaintext, 16).decode('ascii')
else:
return plaintext.decode('ascii')
shared_secret = 7353727325691585831
iv = "b9d98bb5d65cc1ebba464c02900429a2"
ciphertext = "a25bf854668a9615d034bc8abdf15b7eba9ae67427c75a4f8754e458189c5577"
print(decrypt_flag(shared_secret, iv, ciphertext))
```
:::spoiler Flag
**crypto{d0wn6r4d35_4r3_d4n63r0u5}**
:::
### Static Client
**nc socket.cryptohack.org 13373**
- **Mô tả:** Ở challenge này ta sẽ xem được tin nhắn mà Alice và Bob gửi qua lại cho nhau, sau khi hai người trao đổi thành công $Flag$ thì ta sẽ giả mạo thành Alice để khai thác thêm thông tin từ Bob.
- **Tóm tắt:** $Bob$ và $Alice$ sẽ trao đổi những thông cơ bản là $p,g,A,B,IV$ và **encrypted_flag** như những challenge trước, nhưng quá trình trao đổi trên ta chỉ có thể xem chứ không thể can thiệp vào để sửa đổi. Sau khi quá trình trên kết thúc thì ta sẽ được quyền giả mạo thành **Alice**, lúc này ta sẽ gửi những thông tin giả qua cho Bob để anh tự làm lộ thông tin và từ đó giải mã được **encrypted_flag**.
- Khi kết nối tới server ta nhận được những tin nhắn sau:
- Đó là cuộc hội thoại của **Alice** và **Bob** khi họ đang trao đổi thông tin cho nhau, bao gồm $p,g,A,B,IV$ và **encrypted_flag**.
- Sau đó chúng ta can thiệp vào, giả mạo thành **Alice** nói chuyện với Bob thông qua dòng `Bob connects to you, send him some parameters:`
- Để nói chuyện với **Bob** thì ta phải gửi những thông số cần để tính khóa chung qua, bao gồm $p,g$ và $A$, sau đó anh sẽ gửi lại $B, IV$ và **encrypted_message**. Ta sẽ lợi dụng điều trên, gửi cho Bob những thông tin sai để tính được $K$ từ đó giải mã được $Flag$.
- **Hướng giải:**
- Ta biết $K$ được tính từ công thức $K \equiv A^{b}\pmod p$ mà $B$ lại được tính từ $B \equiv g^{b}\pmod p$.
- Vì vậy khi gửi $g$ sang cho **Bob**, ta sẽ tráo giá trị $g$ thành $A$ còn $A$ muốn đặt là gì cũng được.
- Anh Bob khi tính giá trị của $B$ sẽ vô tình tính luôn giá trị của $K$ vì $g$ đã bị tráo thành $A$.
- Có những dữ kiện sau:
```python
p = 0xffffffffffffffffc90fdaa22168c234c4c6628b80dc1cd129024e088a67cc74020bbea63b139b22514a08798e3404ddef9519b3cd3a431b302b0a6df25f14374fe1356d6d51c245e485b576625e7ec6f44c42e9a637ed6b0bff5cb6f406b7edee386bfb5a899fa5ae9f24117c4b1fe649286651ece45b3dc2007cb8a163bf0598da48361c55d39a69163fa8fd24cf5f83655d23dca3ad961c62f356208552bb9ed529077096966d670c354e4abc9804f1746c08ca237327ffffffffffffffff
g = 0x02
A = 0x6576da4fc85bda7b79ed7af264890d2ef6316029620197af364348ddc4c6f8cda505b5c80ba131d2073d1e95244f3fd6c70ecf217a6cf727e5006c40540834da8ae4928eddd59da16b7dc4c9958b7a2f513018fe584357de47e5d14b0c38c86e16bd06fd20f4bbcfc4e2028cb0becb8736449de5658d48263cf8d4e3cbb336f6becf41ee0c053f8a1ee1a3513d82da0e50bde6fc606efcd5360fec98220c9617e85b436498d5b721888e71820d48a295eecd1edd7d8fabc102781ef7975cee46
B = 0x8d79b69390f639501d81bdce911ec9defb0e93d421c02958c8c8dd4e245e61ae861ef9d32aa85dfec628d4046c403199297d6e17f0c9555137b5e8555eb941e8dcfd2fe5e68eecffeb66c6b0de91eb8cf2fd0c0f3f47e0c89779276fa7138e138793020c6b8f834be20a16237900c108f23f872a5f693ca3f93c3fd5a853dfd69518eb4bab9ac2a004d3a11fb21307149e8f2e1d8e1d7c85d604aa0bee335eade60f191f74ee165cd4baa067b96385aa89cbc7722e7426522381fc94ebfa8ef0
IV = 0xf9f96db8acc1146609aed6cee3b0d968
encrypted = 0xfe02adae03d8c5f5726658b4566ca8173a7caf2a126d00f4f9b3cfdae2a21a92
```
- Ta sẽ gửi cho Bob: $p$ ở trên; $g$ bị tráo thành $A$ và $A$ giá trị nào cũng được, mình sẽ đặt là $1$. Tệp **Json** sẽ như sau:
:::spoiler Json
{"p":"0xffffffffffffffffc90fdaa22168c234c4c6628b80dc1cd129024e088a67cc74020bbea63b139b22514a08798e3404ddef9519b3cd3a431b302b0a6df25f14374fe1356d6d51c245e485b576625e7ec6f44c42e9a637ed6b0bff5cb6f406b7edee386bfb5a899fa5ae9f24117c4b1fe649286651ece45b3dc2007cb8a163bf0598da48361c55d39a69163fa8fd24cf5f83655d23dca3ad961c62f356208552bb9ed529077096966d670c354e4abc9804f1746c08ca237327ffffffffffffffff", "g":"0x6576da4fc85bda7b79ed7af264890d2ef6316029620197af364348ddc4c6f8cda505b5c80ba131d2073d1e95244f3fd6c70ecf217a6cf727e5006c40540834da8ae4928eddd59da16b7dc4c9958b7a2f513018fe584357de47e5d14b0c38c86e16bd06fd20f4bbcfc4e2028cb0becb8736449de5658d48263cf8d4e3cbb336f6becf41ee0c053f8a1ee1a3513d82da0e50bde6fc606efcd5360fec98220c9617e85b436498d5b721888e71820d48a295eecd1edd7d8fabc102781ef7975cee46", "A":"0x01"}
:::
- **Bob** sẽ trả lời lại chúng ta **encrypted** kèm theo đó là $B$ và $IV$. Khi này $B$ sẽ là $K$ vì nó được tính bằng $A^{b}\pmod p$ chứ không phải $g^{b}\pmod p$. Giờ chuyển $B$ từ `Hex` sang `int` thì ta có được $K$.
- Có được $K, IV$ và **encrypted_flag** thì ta sẽ truyền $3$ tham số trên vào hàm `decrypt` ở challenge trước để giải mã ra $Flag$. Đoạn code như sau:
```python
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad, unpad
import hashlib
def is_pkcs7_padded(message):
padding = message[-message[-1]:]
return all(padding[i] == len(padding) for i in range(0, len(padding)))
def decrypt_flag(shared_secret: int, iv: str, ciphertext: str):
# Derive AES key from shared secret
sha1 = hashlib.sha1()
sha1.update(str(shared_secret).encode('ascii'))
key = sha1.digest()[:16]
# Decrypt flag
ciphertext = bytes.fromhex(ciphertext)
iv = bytes.fromhex(iv)
cipher = AES.new(key, AES.MODE_CBC, iv)
plaintext = cipher.decrypt(ciphertext)
if is_pkcs7_padded(plaintext):
return unpad(plaintext, 16).decode('ascii')
else:
return plaintext.decode('ascii')
shared_secret = 2397583543557066191433753530017246622976728427347660612800286592367555037611481763631080628037887342716906654685739668198828000160358760796714640410690816149072235349678321460680183458040531578758571412561831954487048014266252305697261933771280800129182461507280646720689781400539066574155949351662846391646566899374303072787950549610786908019898154601673346270777952233823642731561557306661321794180955286848826170133789687207607806441760051235900431980273799276
iv = "f9f96db8acc1146609aed6cee3b0d968"
ciphertext = "fe02adae03d8c5f5726658b4566ca8173a7caf2a126d00f4f9b3cfdae2a21a92"
print(decrypt_flag(shared_secret, iv, ciphertext))
```
:::spoiler Flag
**crypto{n07_3ph3m3r4l_3n0u6h}**
:::
- **Fun fact:** còn một thứ Bob gửi qua đó là **encrypted**. Nó thì không liên quan đến Flag nhưng mà là một *easter egg* khá thú vị:
- Khi ta giải mã với $K = 1$ cùng với $IV$ mà Bob đưa thì ta được dòng tin nhắn dưới đây:
- **"Hey, what's up. I got bored generating random numbers did you see?"**
## GROUP THEORY
### Additive
**nc socket.cryptohack.org 13380**
- **Mô tả:** Ở challenge này $Alice$ và $Bob$ vẫn trao đổi thông tin cho nhau như những challenge trên nhưng thay vì tính $A,B,K$ trên **nhóm nhân Modulo**(multiplicative group) thì hai người quyết định thực hiện trên **nhóm cộng Modulo**(additive group), điều này đồng nghĩa với việc tìm hai khóa bí mật $a$ và $b$ là vô cùng đơn giản.
- Khi kết nối tới server thì ta được những thông tin về $p,g,A,B, IV$ và **encrypted_flag** như sau:
- Vì các phép tính được thực hiện trên nhóm **cộng Modulo** nên ta có công thức tính $A,B$ và $K$ như sau:
$$A \equiv g \times a \pmod p \Leftrightarrow a \equiv A \times g^{-1} \pmod p$$
$$B \equiv g \times b \pmod p \Leftrightarrow b \equiv B \times g^{-1} \pmod p$$
$$K \equiv g \times a \times b\pmod p$$
- Đoạn code để tìm $a,b$ và $K$ như sau:
```python
#sage
p = 0xffffffffffffffffc90fdaa22168c234c4c6628b80dc1cd129024e088a67cc74020bbea63b139b22514a08798e3404ddef9519b3cd3a431b302b0a6df25f14374fe1356d6d51c245e485b576625e7ec6f44c42e9a637ed6b0bff5cb6f406b7edee386bfb5a899fa5ae9f24117c4b1fe649286651ece45b3dc2007cb8a163bf0598da48361c55d39a69163fa8fd24cf5f83655d23dca3ad961c62f356208552bb9ed529077096966d670c354e4abc9804f1746c08ca237327ffffffffffffffff
g = 0x02
A = 0x7c0a16229c5e369a500b71aac1ffffbdf47872c1a4cbd7be6ce4492605dfc6d18f1a8f574fea2ea388ab342202ccc2620c2e8ea701dc14bef4ff8c062963b4fdec60604a6aec4afbea5c0acc73d9da91b85e45a29f163ac5317acbf0782580232b0dbd74c6b0a4f0115c25d9e7dd5f0ff1bd8d494a50345bded554c05da418d134a7ca0e41bf02cbcfd78e3ed3c2fec75f3792c6bc857e1861735f9ac308577f4fa8afa122ae723ec1003f49fa30745da9ab6e534ef58d36f8f8b8ec9ed92300
B = 0xaa8cf2af5a8737ab9d0bb468f9b8acc2128418cdb8c7fac590bd0fd64fac9fcb5bc51084f4d18ac35d0e9db2e60758260748a100227abc8ee3e285cd6382fe0438ad7dfbc5004014d01e98094bb998b72545362f8431d2eee66f86f4fd3bc0430d901223aca3ee2a8f9204aa5dc8b1f3844d6fa3d29c6af795c90463e7ad8828a38b9517cf8d5148d7998342a78d6b4fb760dad0e5d791cd88d09f771575db690ebd2e4003fd760d153c295f12061b4236d8239f44e812b43311936de6fce296
inv_g = pow(g, -1, p)
a = Mod(inv_g*A, p)
b = Mod(inv_g*B, p)
K = Mod(A*b, p)
show(K)
#113580855317733185105402060009437963648431323828455716460953499347433806759304486681684438720900164036456208685387812858806208439309937233617408546730459593623005344123416944103996610386753662771348742842953804323597914071005983480330211153523825695478265276106387349700089998490674954158887949224113894424296481582301055918329568701822014990205489468109671029874665990031435543029232179824586920111113527151588041254160962878303190833221956911289134
```
- Có được $K, IV$ và **encrypted_flag** thì ta truyền $3$ tham số này vào hàm **decrypted** ở challenge trước để giải ra $Flag$. Đoạn code như sau:
```python
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad, unpad
import hashlib
def is_pkcs7_padded(message):
padding = message[-message[-1]:]
return all(padding[i] == len(padding) for i in range(0, len(padding)))
def decrypt_flag(shared_secret: int, iv: str, ciphertext: str):
# Derive AES key from shared secret
sha1 = hashlib.sha1()
sha1.update(str(shared_secret).encode('ascii'))
key = sha1.digest()[:16]
# Decrypt flag
ciphertext = bytes.fromhex(ciphertext)
iv = bytes.fromhex(iv)
cipher = AES.new(key, AES.MODE_CBC, iv)
plaintext = cipher.decrypt(ciphertext)
if is_pkcs7_padded(plaintext):
return unpad(plaintext, 16).decode('ascii')
else:
return plaintext.decode('ascii')
shared_secret = 1135808553177331851054020600094379636484313238284557164609534993474338067593044866816844387209001640364562086853878128588062084393099372336174085467304595936230053441234169441039966103867536627713487428429538043235979140710059834803302111535238256954782652761063873497000899984906749541588879492241138944242964815823010559183295687018220149902054894681096710298746659900314355430292321798245869201111135271515880412541609628783031908332219569112891345485286121739
iv = "90e1ca13f8a952ecd47903ea37ce581e"
ciphertext = "e79bca91c4e6c3e68f64ef009be506015f430923e54ad788977fc0d0971956f6fcbc13bbf72c3436ada49ec405af0f6c"
print(decrypt_flag(shared_secret, iv, ciphertext))
```
:::spoiler Flag
**crypto{cycl1c_6r0up_und3r_4dd1710n?}**
:::
### Static Client 2
**nc socket.cryptohack.org 13378**
- Challenge này được xây dựng từ challenge cùng tên là **Static Client** nên nó cũng kế thừa ý tưởng từ challenge đó. Nhưng ở challenge này thì độ khó đã được nâng lên khi anh Bob giờ đã biết kiểm tra thông tin mà ta gửi qua. Nếu có những thông số không đủ an toàn thì anh sẽ từ chối trao đổi thông tin.
- Sau một hồi thử khá là nhiều thứ nhưng không có kết quả thì mình đã tìm được hướng giải đó là phương trình **Logarit rời rạc (DLP)** sẽ được giải nhanh hơn khi số $p$ thuộc trường hợp đặc biệt.
- **Cụ thể:** Ta sẽ giải được phương trình Logarit rời rạc một cách nhanh chóng khi $\phi(p)$là một [**Smooth number**](https://en.wikipedia.org/wiki/Smooth_number). Nên hướng giải của ta sẽ là gửi một số $p$ là **Smooth number + 1** cho Bob, anh sẽ dùng $p$ đó để tính $B$, từ đó ta sẽ giải phương trình $B \equiv g^{b} \pmod p$ để tìm $b$ rồi tính được $K$.
- Khi kết nối đến server thì ta được những thông tin sau:
- Ta sẽ tính $p$ là **Smooth number + 1** sau đó gửi $p, g, A$ cho Bob để anh tính $B$, sau đó dùng $B$ đó để tính $b$.
- Ta nấu được đoạn code để tìm **Smooth number + 1** như sau:
```python
from gmpy2 import *
from Crypto.Util.number import *
p = int("ffffffffffffffffc90fdaa22168c234c4c6628b80dc1cd129024e088a67cc74020bbea63b139b22514a08798e3404ddef9519b3cd3a431b302b0a6df25f14374fe1356d6d51c245e485b576625e7ec6f44c42e9a637ed6b0bff5cb6f406b7edee386bfb5a899fa5ae9f24117c4b1fe649286651ece45b3dc2007cb8a163bf0598da48361c55d39a69163fa8fd24cf5f83655d23dca3ad961c62f356208552bb9ed529077096966d670c354e4abc9804f1746c08ca237327ffffffffffffffff", 16)
def get_smooth_prime(p):
smooth_number = 0
while not is_prime(smooth_number + 1):
smooth_number = 2
while smooth_number.bit_length() < p.bit_length():
prime = getPrime(32)
smooth_number *= prime
return smooth_number + 1
print(hex(get_smooth_prime(p)))
#0x171c53605a7fa6558b16d65aa1f9a33e89497df575333671038acf57e4175db07d4f30cf37c21a4ada15cb353ab47f4f32bccc97ace4603d18fe19810fe21a7263c64e52f4716694d2f000584618570ba47633fa9e43da3d0b8ef1b0fd20ea2347a53f2363d3ffcb21d8bef667c5356cc25fc97902278573bdc4b7ac57811ad81fe24110f5f5dfd538dc73f1ecd41592f118bb72e456dd85c734cdb7d1e64b00e40c919491ec580dc8295fa44060202eeabf528a0f78ee8361b48498aab723ea2017
```
- Khi có được một số $p$ đẹp, ta sẽ tính $b$ bằng cách giải phương trình logarit rời rạc $b \equiv log_{g}{B} \pmod p$. Khi này $\phi(p)$ là *smooth number* nên việc giải phương trình trên là khả thi. Đoạn code như sau:
```python
#sage
p = 0x171c53605a7fa6558b16d65aa1f9a33e89497df575333671038acf57e4175db07d4f30cf37c21a4ada15cb353ab47f4f32bccc97ace4603d18fe19810fe21a7263c64e52f4716694d2f000584618570ba47633fa9e43da3d0b8ef1b0fd20ea2347a53f2363d3ffcb21d8bef667c5356cc25fc97902278573bdc4b7ac57811ad81fe24110f5f5dfd538dc73f1ecd41592f118bb72e456dd85c734cdb7d1e64b00e40c919491ec580dc8295fa44060202eeabf528a0f78ee8361b48498aab723ea2017
B = Mod(0x24cb418c74e42cb5e689edb7b91df4ca753393c591824fd33b1f9ff6dac81b07a00133d230738a9ed4d9958df0ac32c636991791ec9d43455fbe0f04e5d22a679315820f16f821b39b9ffbb8b24e8f44933c00ea0069b84408cd1472775f5c7e606407a85fdac65f530c57b19824b76c82c97b5c4e958b009ccc05bb2e9e840bcc30d64a8e96ef94dec0b0e7d7a8f390464fef1760f222f6009bfbe76a5247e15979f622086a3f397b3c8e99f089f56b90b7a53170b80f33f0b85c57e6e62ee1d2f, p)
g = Mod(0x02, p)
b = discrete_log(B, g)
show(b)
#1919572943691512325783103720167834163677411292709378502535498859989993544026380143919501049584589675317643993465536543895780854808442293000014297210200227069779643763121704810281976733978781152126062646602812482025293137787739116693980988513420732289020477701182639042794562638875881378349771734410919106042203493166198706573467903966100368713572415175654342828296086659529676015616513470105470901979846373335352656586302787870238998914215908919919219987614105175
```
- Khi có $b$, ta chỉ cần thế vào phương trình $K \equiv A^{b} \pmod p$ là có $K$, lưu ý phải dùng $A$ và $p$ của **Alice** chứ không dùng $A$ và $p$ mà chúng ta tạo ra để gửi qua **Bob**. Đoạn code như sau:
```python
#sage
p = 0xffffffffffffffffc90fdaa22168c234c4c6628b80dc1cd129024e088a67cc74020bbea63b139b22514a08798e3404ddef9519b3cd3a431b302b0a6df25f14374fe1356d6d51c245e485b576625e7ec6f44c42e9a637ed6b0bff5cb6f406b7edee386bfb5a899fa5ae9f24117c4b1fe649286651ece45b3dc2007cb8a163bf0598da48361c55d39a69163fa8fd24cf5f83655d23dca3ad961c62f356208552bb9ed529077096966d670c354e4abc9804f1746c08ca237327ffffffffffffffff
A = 0x16b0a9159d1157972a5fd9e848023e547af7fc95250bc670d88a15b2d25391bd3f7bdaaec9cb65ffff279ceb1f993b7af24ce4f94a21387ba60872251bb3b1aecd29d5fb4034db4c8b196cf405f557c190b88966ca60c63dc08dc0f740eb8f7dd13174a4859252134cc3425ad58e03e53d5640180cbde7d02f08ce789ab8f2659b779f4144a54c68ffdeab4090467c9fd34f3f23948272d8abf36caa10f3d4d84799dbc291b4fc31f421ef004788d29a418d7047ba654aa403b56d6c46592071
b = 1919572943691512325783103720167834163677411292709378502535498859989993544026380143919501049584589675317643993465536543895780854808442293000014297210200227069779643763121704810281976733978781152126062646602812482025293137787739116693980988513420732289020477701182639042794562638875881378349771734410919106042203493166198706573467903966100368713572415175654342828296086659529676015616513470105470901979846373335352656586302787870238998914215908919919219987614105175
K = pow(A, b, p)
show(K)
#K = 119916590500302892619307190780211288654127940628621497103823404912829895427425264762639110634211663918813704959859882537507499173219921582966831786289905962484178963423182288615127289574987191584030586339637970163914493784124695762604798868656003062106946319693673195228890727607152595620680565261357188719440743529858725421993295861376332423110638438176963378249552717037577640936358727763533711111460177136306125794943117423023148377592749041415886
```
- Có $3$ tham số $K, IV$ và **encrypted_flag** thì ta sẽ truyền vào hàm **decrypt** ở challenge trước để giải mã ra $Flag$. Đoạn code như sau:
```python
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad, unpad
import hashlib
def is_pkcs7_padded(message):
padding = message[-message[-1]:]
return all(padding[i] == len(padding) for i in range(0, len(padding)))
def decrypt_flag(shared_secret: int, iv: str, ciphertext: str):
# Derive AES key from shared secret
sha1 = hashlib.sha1()
sha1.update(str(shared_secret).encode('ascii'))
key = sha1.digest()[:16]
# Decrypt flag
ciphertext = bytes.fromhex(ciphertext)
iv = bytes.fromhex(iv)
cipher = AES.new(key, AES.MODE_CBC, iv)
plaintext = cipher.decrypt(ciphertext)
if is_pkcs7_padded(plaintext):
return unpad(plaintext, 16).decode('ascii')
else:
return plaintext.decode('ascii')
shared_secret = 1199165905003028926193071907802112886541279406286214971038234049128298954274252647626391106342116639188137049598598825375074991732199215829668317862899059624841789634231822886151272895749871915840305863396379701639144937841246957626047988686560030621069463196936731952288907276071525956206805652613571887194407435298587254219932958613763324231106384381769633782495527170375776409363587277635337111114601771363061257949431174230231483775927490414158868070941959653
iv = "0b338fde5a7a257c108777e3736c1d20"
ciphertext = "5a21acecf06203842a7aeb7696e5a05f53136c9be7db9a36cf1b56118f1e79725981ab984374f095ff3fe433878d4ac1"
print(decrypt_flag(shared_secret, iv, ciphertext))
```
:::spoiler Flag
**crypto{uns4f3_pr1m3_sm4ll_oRd3r}**
:::
<h2 style="text-align:center;">END</h2>
Sign in with Wallet
Connect another wallet