<h1 style="text-align:center;">Elliptic Curve In Cryptography</h1>
## Lý thuyết Đường Cong Elliptic
### Định nghĩa
- **Định nghĩa:** Đường cong elliptic là một loại đường cong đại số đặc biệt, thường được biểu diễn dưới phương trình:
<span style="font-size:2em; text-align:center">$$Y^2 = X^3 + aX + b$$</span>
với điều kiện:
<span style="font-size:2em">$$4a^3+ 27b^2 \neq 0$$</span>
- **Đồ thị:** đường cong Elliptic được biểu diễn như sau:
- Ở trên là không gian **hai chiều**, còn ở không gian **ba chiều** thì đường cong Elliptic được biểu diễn như sau:
- Đường cong Elliptic không chỉ được định nghĩa trên trường số thực, mà còn có thể định nghĩa trên các trường khác như trường hữu tỷ, trường số phức, và cả trường hữu hạn.
<img style="display: block; margin: auto;" width="500" src="https://hackmd.io/_uploads/r174fzEpA.png"/>
<p style="text-align:center;">Trường Hữu Hạn</p>
<img style="display: block; margin: auto;" width="500" src="https://hackmd.io/_uploads/B1eTmGN60.png"/>
<p style="text-align:center;">Trường Số Phức</p>
### Phép Cộng Hai Điểm Trên Đường Cong Elliptic.
- **Quy ước:**
- Đường cong này có điểm đặc biệt gọi là điểm **"vô cùng"** và được ký hiệu là $O$. Điểm $O$ cũng được xem là phần tử đơn vị của phép cộng, nghĩa là: $$\forall P \in E, P + O = O +P = P$$
- Phần tử nghịch đảo của điểm $P$ trong phép cộng được ký hiệu $– P$, là điểm đối xứng với $P$ qua trục hoành.
<img style="display: block; margin: auto;" width="400" src="https://hackmd.io/_uploads/H1_eIzNTA.gif"/>
- **Về phương diện hình học** thì phép cộng hai điểm $P$ và $Q$ nằm trên đường cong diễn ra như sau:
- Kẻ đường thẳng $A$ đi qua hai điểm $P$ và $Q$.
- Đường thẳng $A$ cắt đường cong Elliptic tại điểm $-R = -(P + Q)$.
- Lấy đối xứng $-R$ qua trục $Ox$ ta được điểm $R = (P + Q)$ là tổng của $P$ và $Q$.
<img style="display: block; margin: auto;" width="400" src="https://hackmd.io/_uploads/rk4r5fNaA.png"/>
- Trường hợp khi hai điểm $P$ và $Q$ trùng nhau thì lúc này phép tính $R = P + Q = 2P$ diễn ra như sau:
- Kẻ đường thẳng $A$ là **đường tiếp tuyến** với đường cong tại điểm $P$.
- Tiếp tuyến $A$ sẽ cắt đường cong tại điểm $R = -2P$.
- Lấy đối xứng giao điểm qua trục $Ox$ thì ta sẽ có được điểm $R = 2P$.
<img style="display: block; margin: auto;" width="400" src="https://hackmd.io/_uploads/rk-McGV60.png"/>
- **Về mặt đại số** thì phép cộng hai điểm $P(x_1, y_1)$ và $Q(x_2, y_2)$ trên đường cong $E(K)$ trong đó $P \neq -Q$ diễn ra như sau:
- Đầu tiên tính độ dốc của đường thẳng $A$ đi qua $P$ và $Q$:
<span style="font-size:1.5em; text-align:center">$$m = \frac{y_q - y_p}{x_q - x_p}$$</span>
- Tính tọa độ $(x_R, y_R)$:
<span style="font-size:1.5em; text-align:center">$$x_R = m^2 - x_p - x_q$$</span>
<span style="font-size:1.5em; text-align:center">$$y_R = m(x_p - x_R) - y_p$$</span>
- Trong trường hợp $P = Q$ thì ta tìm tọa độ $(x_R, y_R)$ của $R$ như sau:
- Tính giá trị đạo hàm $m$ của đường cong tại $P$:
<span style="font-size:1.5em; text-align:center">$$m = \frac{3x_p^2 + a}{2y_p}$$</span>
- Tính tọa độ $(x_R, y_R)$ của $R$:
<span style="font-size:1.5em; text-align:center">$$x_R = m^2 - 2x_p$$</span>
<span style="font-size:1.5em; text-align:center">$$y_R = m(x_p - x_R) - y_p$$</span>
- Trong trường hợp $P$ và $Q$ đối xứng qua trục hoành, hay nói cách khác $Q = -P$ thì đường thẳng $A$ nối $P, Q$ sẽ cắt đường cong Elliptic tại vô cực, hay $P + ( -P ) = O$.
### Phép Nhân Vô Hướng Trên Đường Cong Elliptic
- **Lưu ý:** Không tồn tại phép nhân hai điểm $P$ và $Q$ trên đường cong Elliptic và cũng tương tự không tồn tại phép chia một điểm $Q$ cho một điểm $P$.
> Phép chia một điểm $Q$ cho một số **n** hoàn toàn tồn tại nếu ta biết **n**.
- Trên đường cong Elliptic, việc **nhân** một điểm với một **hằng số** không đơn thuần chỉ là lấy từng toạ độ rồi nhân là xong.
- Phép nhân ở đây vẫn là phép cộng, nhưng thực hiện **nhiều lần** mà thôi.
- Ví dụ trong phép toán tính $3P$:
- Đầu tiên ta sẽ tính $2P$ bằng cách tính $P+P$
- Theo cách cộng ở bên trên, ta vẽ đường tiếp tuyến của đường cong tại $P$, nó cắt đường cong tại điểm $-2P$, lấy đối xứng qua trục hoành ta có $2P$.
- Tiếp tục vẽ đường thẳng nối giữa $2P$ và $P$, cắt đường cong tại $-3P$, lấy đối xứng ta có $3P$.
<img style="display: block; margin: auto;" width="300" src="https://hackmd.io/_uploads/HJZ5qQ4pR.png"/>
## Đường Cong Elliptic Trong Trường Hữu Hạn (Fp)
### Lý Thuyết
- Đường cong elliptic trong trường hữu hạn là một phần quan trọng trong toán học và mật mã học hiện đại. Cụ thể, phép toán trên điểm của đường cong Elliptic có tính chất khó làm ngược lại, tạo ra một cơ chế bảo mật mạnh để sử dụng trong các giao thức mật mã học như mã hóa khóa công khai, trao đổi khóa **Diffie-Hellman** (ECDH) và tạo **chữ ký số**.
- Một đường cong elliptic trong một trường hữu hạn $\mathbb{F}_p$ được định nghĩa bởi một **phương trình** dạng:
<span style="font-size:1.7em; text-align:center">$$y^2 \equiv x^3 + Ax + B \hspace{2mm} (mod \hspace{2mm}p)$$</span>
- Điều kiện để phương trình này tạo thành một đường cong elliptic hợp lệ là: $4A^3+ 27B^2 \not\equiv 0\hspace{2mm} (mod \hspace{2mm}p)$. Điều kiện này đảm bảo rằng đường cong không có các điểm kỳ dị (điểm mà tiếp tuyến không xác định).
<img style="display: block; margin: auto;" width="600" src="https://hackmd.io/_uploads/Sk3syqNaR.png"/>
<p style="text-align:center;font-size:0.9em">Đường cong elliptic y^2 = x^3 − x trong trường hữu hạn F61.</p>
#### Phép cộng trên trường hữu hạn
- Cũng giống trong trường số thực, ở trường hữu hạn thì ta vẫn sử dụng những công thức cũ, ta chỉ thêm vào phép tính $Modulo$ $p$ để đảm bảo rằng mọi phần tử đều nằm trong trường hữu hạn.
- Cho đường cong $y^2 = x^3 +2x +2$ trong trường hữu hạn $\mathbb{F}_{17}$ và điểm $P = (5,1)$, ta sẽ thực hiện phép tính $P+P$ trong ***sagemath*** như sau:
```python
#sage
#tạo đường cong Elliptic y^2 = x^3 + 2x + 2 trong trường hữu hạn Fp = 17
E = EllipticCurve(GF(17),[2,2])
#tạo điểm P (5,1) trên đường cong
P = E(5,1)
#tính điểm Q = 2P
Q = P + P
show(Q)
#(6 : 3 : 1)
```
- Để kiểm tra một điểm có thuộc đường cong hay không thì ta sử dụng hàm `.is_on_curve(x,y)`. Đoạn code trên ***sagemath*** như sau:
```python
#sage
E = EllipticCurve(GF(17),[2,2])
R = (6,3)
#kiểm tra điểm R có nằm trên đường cong hay không
print(E.is_on_curve(6,3))
#True
```
#### Phép nhân trên trường hữu hạn
- Cho đường cong $E: y^2 \equiv x^3 + 2x + 2 \pmod{17}$ và điểm $P = (5,1)$. Ta sẽ thực hiện phép nhân trong ***sagemath*** như sau:
```python
#sage
E = EllipticCurve(GF(17),[2,2])
P = E(5,1)
for i in range(1, 20):
M = i*P
print(f"{i} * P =", M)
```
- Ta sẽ được kết quả sau:
```python
1 * P = (5 : 1 : 1)
2 * P = (6 : 3 : 1)
3 * P = (10 : 6 : 1)
4 * P = (3 : 1 : 1)
5 * P = (9 : 16 : 1)
6 * P = (16 : 13 : 1)
7 * P = (0 : 6 : 1)
8 * P = (13 : 7 : 1)
9 * P = (7 : 6 : 1)
10 * P = (7 : 11 : 1)
11 * P = (13 : 10 : 1)
12 * P = (0 : 11 : 1)
13 * P = (16 : 4 : 1)
14 * P = (9 : 1 : 1)
15 * P = (3 : 16 : 1)
16 * P = (10 : 11 : 1)
17 * P = (6 : 14 : 1)
18 * P = (5 : 16 : 1)
19 * P = (0 : 1 : 0)
```
- Ở kết quả $19 \times P = (0,1)$ thì $(0,1)$ chính là điểm vô cùng $O$.
- Ta thấy rằng **order** của $P = (5,1)$ sẽ là $19$ vì $19$ là số nhỏ nhất sao cho $19 \times P = O$.
- Để tính **order** của đường cong $E$ hoặc một điểm thuộc đường cong $E$ thì ta sử dụng phương thức `.order()` như sau:
```python
#sage
E = EllipticCurve(GF(17),[2,2])
P = E(16,13)
print("order of E =", E.order())
print("order of P =", P.order())
#order of E = 19
#order of P = 19
```
### Đường Cong Elliptic Trong Trường Hữu Hạn Fp Là Một Nhóm Abel
- Đường cong Elliptic trên trường hữu hạn $\mathbb{F}_p$ tạo thành một **nhóm Abel** vì chúng thỏa mãn các tính chất cơ bản của một nhóm Abel: tính đóng, tính kết hợp, phần tử đơn vị, phần tử nghịch đảo, và tính giao hoán:
1. **Tính đóng**
- Khi cộng hai điểm $P$ và $Q$ trên đường cong elliptic luôn cho ra kết quả $R = P +Q$ là một điểm khác thuộc đường cong.
2. **Tính kết hợp**
- Với mọi điểm $P,Q,R$ trên đường cong, ta luôn có:
$$(P + Q) + R = P + (Q + R) \hspace{2mm} $$
3. **Phần tử đơn vị**
- Điểm vô cực $O$ đóng vai trò là phần tử đơn vị trong phép cộng trên đường cong elliptic. Với mọi điểm $P$ trên đường cong, ta luôn có:
$$P + O = O + P = P $$
4. **Phần tử nghịch đảo**
- Với mọi điểm $P = (x,y)$ trên đường cong elliptic, tồn tại một phần tử nghịch đảo là $-P = (x,-y)$ thuộc đường cong sao cho:
$$P + (-P) = O$$
5. **Tính giao hoán**
- Phép cộng trên đường cong elliptic có tính chất giao hoán, nghĩa là với mọi điểm $P,Q$ trên đường cong, ta luôn có:
$$P + Q = Q + P$$
### Order Của Đường Cong Elliptic Xrong Trường Fp
- **Order** (bậc) của đường cong elliptic trong trường hữu hạn $\mathbb{F}_p$ là số lượng các điểm trên đường cong elliptic, bao gồm cả điểm vô cực $O$, được ký hiệu là $\#E(\mathbb{F}_p)$.
<span style="font-size:1.3em; text-align:center">$$\#E(F_p) \in [1, 2\times p + 1]$$</span>
- **Định lý Hasse** về bậc của đường cong Elliptic:
- Số lượng điểm trên đường cong elliptic $E$ trong trường hữu hạn $\mathbb{F}_p$ không phải lúc nào cũng bằng $p$ (số phần tử của trường $\mathbb{F}_p$). Theo định lý Hasse, bậc của đường cong $E$ thỏa mãn:
<span style="font-size:1.3em; text-align:center">$$p + 1 - 2 \sqrt{p} \leq \#E(F_p) \leq p + 1 + 2 \sqrt{p}$$</span>
- Khoảng $[p + 1 - 2 \sqrt{p}, p + 1 + 2 \sqrt{p}]$ được gọi là khoảng Hasse.
- **Ví dụ:** Ta có đường cong $E: y^2 = x^3 + 3x + 8 \pmod{13}$. Ta sẽ sử dụng **định lý Hasse** để ước chừng số phần tử của đường cong trên.
$$p + 1 - 2\sqrt{p} \leq \#E(\mathbb{F}_p) \leq p + 1 + 2\sqrt{p}$$
$$\Leftrightarrow 8 \leq \#E(\mathbb{F}_p) \leq 20$$
- Liệt kê ra thì ta có các điểm sau: $E(\mathbb{F}_{13}) = \{ O, (1,5), (1,8), (2,3), (2,10), (9,6), (9,7), (12,2), (12,11) \}$
- Vì $E(\mathbb{F}_{13})$ có $9$ điểm nên ta nói bậc của $E(\mathbb{F}_{13}) = 9$ hay $\#E(\mathbb{F}_p) = 9$
- Mỗi điểm $P$ trên đường cong elliptic cũng có một **order** riêng. Order của một điểm $P$ là số nhỏ nhất $n$ sao cho:
$$nP = P+P+P+...+P = O$$
- Order của một điểm $P$ phải là một **ước** số của order của đường cong elliptic $\#E(\mathbb{F}_p)$ (theo định lý Lagrange trong lý thuyết nhóm).
- **Ví dụ:** $E: y^2 \equiv x^3 + 2x + 3 \pmod{97}$ và điểm $P = (3,6)$. Khi này **order** của $E$ và order của $P$ sẽ là:
```python
#sage
E = EllipticCurve(GF(97),[2,3])
P = E(3,6)
print("order of E =", E.order())
print("order of P =", P.order())
#order of E = 100
#order of P = 5
```
<img style="display: block; margin: auto;" width="400" src="https://hackmd.io/_uploads/rJoJwsEa0.png
"/>
### Bài Toán Logarit Rời Rạc
- **Bài toán Logarit rời rạc** trên đường cong elliptic (Elliptic Curve Discrete Logarithm Problem - **ECDLP**) là một bài toán rất khó, tạo nền tảng cho tính bảo mật của hệ thống mật mã đường cong elliptic. Đây là bài toán cơ bản quyết định độ an toàn của hầu hết các ứng dụng mật mã liên quan đến đường cong elliptic.
- **Mô tả bài toán:** Cho hai điểm $P$ và $Q$ thuộc đường cong $E$, trong đó $P$ là điểm ban đầu và $Q = k \times P$ (với $k$ là một số nguyên dương).
:question: **Yêu cầu:** Tìm $k$ khi biết $P$ và $Q$ ?
- **Không tồn tại** phép chia hai điểm trên đường cong Elliptic, nên với $Q = k \times P$, khi cho chúng ta điểm $Q$ và một điểm khởi đầu $P$, cách để tìm ra số $k$ thường là thử lần lượt các giá trị của $k$ trong một khoảng nào đó đến khi tìm được kết quả $Q = k \times P$.
- Đối với các trường hữu hạn lớn (ví dụ $\mathbb{F}_{256}$, thì số lượng giá trị cần thử sẽ rất lớn ($\sqrt{2^{256}}$ khả năng), khiến việc thử từng giá trị $k$ trở nên bất khả thi.
- Ta có một số thuật toán dùng để giải bài toán Logarit rời rạc, nhưng độ phức tạp của chúng vẫn tăng rất nhanh theo kích thước của order đường cong:
- **Thuật toán Baby-step Giant-step:** Cần khoảng $O(\sqrt{n})$ phép tính với $n$ là bậc của đường cong elliptic. Đây là thuật toán rất đơn giản và dễ hiểu.
- **Thuật toán Pollard's Rho:** Đây là một thuật toán khác có độ phức tạp tính toán tương đương $O(\sqrt{n})$, nhưng sử dụng ít bộ nhớ hơn. Độ phức tạp của phương pháp này phụ thuộc vào việc lựa chọn hàm băm.
- **Phương pháp Pohlig-Hellman:** Phương pháp này sử dụng việc phân tích order đường cong thành thừa số nguyên tố để tìm logarit rời rạc. Độ phức tạp của phương pháp này phụ thuộc vào các ước số nguyên tố của bậc của đường cong. Nếu order của đường cong là số nguyên tố lớn thì phương pháp này vô dụng.
>Tính khó giải của bài toán ECDLP đến từ việc không có thuật toán nào hiện tại có thể giải nó một cách hiệu quả, ngoại trừ phương pháp brute force và một số thuật toán khác có độ phức tạp tính toán rất cao. Đây chính là nền tảng cho độ an toàn của đường cong elliptic (ECC).
## Ứng Dụng Trong Mật Mã Học
### Elliptic Curve Diffie–Hellman Key Exchange (ECDH)
- Hai ứng dụng chính của **ECC** là **chữ ký số** (Digital Signatures) và **trao đổi khóa Diffie-hellman** (Key Exchange). **ECDH** tương tự thuật toán Diffie-Hellman truyền thống, khác ở chỗ nó sử dụng phép toán trên đường cong elliptic để tăng cường tính bảo mật.
- **Tóm tắt thuật toán:**
- **Bước 1:** Hai bên tham gia là $A$ và $B$ chọn cho mình một đường cong Elliptic chung và một điểm cơ sở $G(x_G,y_G)$ trên đường cong đó.
- **Bước 2:** Hai bên tạo cho mình khóa bí mật là $d_a$ cho $A$ và $d_b$ cho $B$.
- **Bước 3:** $A$ và $B$ tiến hành tính toán khóa công khai cho mình (gọi là $Q$) và gửi cho người còn lại:
$$Q_A = d_a \times G$$
$$Q_B = d_b \times G$$
- **Bước 4:** Khi $A$ nhận được $Q_{B}$ và $B$ nhận được $Q_{A}$ thì cả hai sẽ tạo được **khóa chung** bằng cách nhân `khóa công khai` với `khóa bí mật`theo công thức sau:
$$S_{A} = {Q_{B}}\times {d_a} = d_b \times G \times d_a$$
$$S_{B} = {Q_{A}}\times {d_b} = d_a \times B \times d_b$$
- Ta thấy rằng $S_A$ và $S_B$ sẽ bằng nhau vì chúng đều được tính từ công thức $S = d_a \times d_b \times G = (x_S, y_S)$. Khi này cả hai có thể dùng $x_S$ để làm khóa cho quá trình mã hóa tin nhắn.
- **Ví dụ:** cho đường cong $E: y^2 \equiv x^3 + 324x + 1287 \pmod{3851}$, Điểm cơ sở $G$ (điểm sinh), khóa bí mật $a = 1194$, $b = 1759$. Tính khóa chung $S$ ?
- Để tìm điểm sinh $G$, ta sử dụng phương thức ``.gens()``
```python
#sage
E = EllipticCurve(GF(3851),[324,1287])
print(E.gens())
# Trả về hai điểm sinh là ((1583 : 2701 : 1), (1256 : 1338 : 1))
```
- Ta sẽ sử dụng $G = (1583,2701)$ làm điểm cơ sở, đoạn code tìm **khóa chung** như sau:
```python
#sage
E = EllipticCurve(GF(3851),[324,1287])
G = E(1583, 2701)
#khóa bí mật
a = 1194
b = 1759
#khóa công khai
qa = a*G
pb = b*G
#khóa chung
sa = pb * a
sb = qa * b
print(sa)
print(sb)
#(3714 : 3618 : 1)
#(3714 : 3618 : 1)
```
- Sau đó cả hai sẽ sử dụng tọa độ $x = 3618$ để làm khóa chung, thường thì sẽ băm nó ra để làm khóa cho mã hóa đối xứng.
### Elliptic Curve Digital Signature (ECDSA)
- **ECDSA Sign** là một phần quan trọng trong đường cong Elliptic. Được sử dụng để xác thực tính toàn vẹn và nguồn gốc của dữ liệu. Đây cũng là một dạng chữ ký số phổ biến hiện nay. **ECDSA** được sử dụng trong nhiều giao thức bảo mật, chẳng hạn như *SSL/TLS, blockchain (Bitcoin, Ethereum)* và các ứng dụng bảo mật khác.
- $Alice$ sẽ tạo một cặp khóa $(r,s)$ gọi là **Chữ ký**, và để ký tin nhắn $M$ thì Alice thực hiện những bước dưới đây:
- Đầu tiên cô sẽ phải chọn ra một số ngẫu nhiên $k$ (khác với private key).
- Sau đó nhân $k$ với điểm sinh $G$ giống như phép toán dùng để tạo ra khóa công khai:
$$P \equiv k \times G \mod(p)= (x_P,y_P)$$
- Khi này giá trị $r$ sẽ là $x_P$, để tìm $s$ thì ta sẽ đi tính **hash** của $M$ , gọi là $z$ rồi áp dụng vào công thức dưới đây, với $d_A$ là khóa bí mật của $Alice$:
$$s \equiv k^{-1} \times (z + d_A \times r)\mod(p) $$
- $Alice$ sau khi tính được cặp khóa $(r,s)$ làm chữ ký thì cô sẽ gửi cho $Bob$ chữ ký cùng thông điệp $M$ đã được mã hóa bằng khóa chung hai người đã trao đổi từ trước. Khi Bob nhận được thông điệp và chữ ký thì anh sẽ tiến hành xác minh như sau:
- Đầu tiên anh tính **hash** của $M$ để có $z$.
- Chỉ cần sử dụng $Q_A$ mà Alice gửi từ trước, Bob sẽ tính $P$ như sau:
$$P = s^{-1} \times z \times G + s^{-1} \times r \times Q_A \mod(p)$$
- Nếu tọa độ $x_P = r$ thì chứng tỏ rằng chữ ký là hợp lệ và tin nhắn $M$ gửi qua là chính xác.
- Ta có thể chứng mình công thức trên như sau:
<img style="display: block; margin: auto;" width="500" src="https://hackmd.io/_uploads/ByyaiaI60.png
"/>
>Nếu chữ ký **(r,s)** hoặc thông điệp **M** bị thay đổi trong quá trình truyền, giá trị **P** tính toán trong quá trình xác minh cũng sẽ thay đổi. Điều này làm cho chữ ký **không hợp lệ**, giúp Bob phát hiện được sự thay đổi hoặc giả mạo thông tin. Đây chính là cơ chế bảo vệ tính toàn vẹn và xác thực của ECDSA.
# CryptoHack
Việc sử dụng **đường cong Elliptic** (Elliptic Curve) trong mã hóa công khai được đề xuất lần đầu vào năm **1985**. Sau nhiều thập kỷ chống chọi với các cuộc tấn công, đường cong Elliptic bắt đầu được sử dụng rồng rãi từ năm **2005**, đem lại lợi ích vượt trội so với kiểu mã hóa công khai được sử dụng trước đó là **RSA**.
Dù **chiều dài khóa** của đường cong Elliptic **ngắn hơn** so với RSA nhưng nó mang lại hiệu quả hơn rất nhiều so với RSA có cùng hoặc dài hơn về chiều dài khóa. Một khóa ECC dài **256 bit** có tính bảo mật ngang với một khóa RSA dài **3072 bit**. Hơn thế nữa, một vài thao tác sử dụng khóa của ECC có thể hiệu quả hơn về cả thời gian và bộ nhớ so với RSA. Cuối cùng, vì ECC phức tạp hơn nên nó khuyến khích các nhà phát triển nên sử dụng các thư viện ECC cài đặt sẵn thay vì tự chế ra một hệ mã ECC riêng.
Những Challenge dưới đây giúp ta có một cái nhìn trực quan về **hàm trapdoor** (trapdoor function) đằng sau ECC; thử nghiệm các cấu trúc toán học cơ bản của nó; và giúp bạn phá vỡ các cơ chế ECC phổ biến như **ECDSA**.
## Background
### Background Reading 5 pts · 4316 Solves
- **Mô tả:** Challenge này giới thiệu sơ lược cho chúng ta về **Đường Cong Elliptic** và yêu cầu trả lời câu hỏi đề đưa để nhận $Flag$.
- **Elliptic Curve Cryptography (ECC)** là một giao thức mã hóa bất đối xứng, giống như *RSA* và *Diffie-Hellman (DH)*, dựa trên *hàm trapdoor (trapdoor function)*. Các hàm trapdoor cho phép mã hóa thông tin bằng cách thực hiện một phép toán khi làm xuôi thì dễ thực hiện, nhưng để làm ngược lại thì rất khó hoặc không thể.
- Đối với RSA, hàm trapdoor dựa trên độ khó của việc phân tích thừa số nguyên tố các số lớn. Với Diffie-Hellman, nó dựa trên độ khó của bài toán Logarit rời rạc trong một trường hữu hạn. Các phép toán trên đều quen thuộc với chúng ta vì các phép nhân hay lấy lũy thừa đều là những thứ đã được dạy tại trường. Còn **ECC** đặc biệt hơn vì nó không tự dưng xuất hiện trong cuộc sống của bạn trừ khi bạn chủ động tìm hiểu về nó.
- Đường cong Elliptic có một đặc điểm thú vị: Ta có thể định nghĩa một phép tính mà chúng ta sẽ gọi là phép **"cộng điểm"**. Phép tính này nhận hai điểm trên đường cong và tạo ra một điểm thứ ba khác cũng thuộc đường cong. Phép cộng điểm này định nghĩa tập hợp các điểm trên một đường cong Elliptic là một **nhóm Abel** vì nó thỏa mãn các tính chất của một nhóm Abel.
- Trên đường cong Ellipic tồn tại một phép tính gọi là phép **"Nhân vô hướng"**, có thể hiểu nhân vô hướng chính là thực hiện phép **cộng điểm** nhiều lần trên chính điểm đó. Ví dụ $Q = [2]P = P + P$, điều này quan trọng vì phép nhân vô hướng là một **hàm trapdoor**!. Độ khó của ECC chính là việc tìm một số $n$ sao cho $Q = [n]P$ khi được cho trước $Q$ và $P$.
:question: **Vậy phép cộng điểm là như thế nào?**
- Về mặt hình học, khi ta thực hiện phép cộng hai điểm $P$ và $Q$, ta sẽ kẻ một đường thẳng đi qua hai điểm đó. Kẻ đến khi nào nó cắt đường cong $E$ tại một điểm $R$. Sau đó lấy đối xứng $R$ qua $Ox$ để có được $R^{'} = R(x,-y)$. Và kết quả cuối cùng của phép tính sẽ là $P+Q = R^{'}$.
- Vậy nếu chúng ta muốn thực hiện phép cộng điểm trên một điểm giống nhau, ví dụ như $P+P$ thì sao? Ta vẫn sẽ kẻ một đường thẳng đi qua $P$ nhưng lần này sẽ kẻ đường tiếp tuyến qua điểm $P$, tiếp tục kẻ đến khi nào nó cắt đường cong $E$ tại điểm $R$. Lấy đối xứng $R$ qua trục $Ox$ là ta đã có kết quả của phép tính rồi: $P+P = R^{'} = R(x,-y)$.
- Nhưng nếu đường thẳng đi qua $P$ và $Q$ hay đường tiếp tuyến tại $P$ không cắt đường cong $E$ thì sao? Lần này ta nói đường thẳng đi qua $P,Q$ cắt đường cong $E$ tại điểm $O$ (điểm vô cùng), là điểm nằm ở tận cùng của trục tung.
> Như vậy phép cộng điểm trên đường cong Elliptic được định nghĩa trong không gian hai chiều kèm với một điểm bổ sung nằm ở vô cực.
<img style="display: block; margin: auto;" width="600" src="https://hackmd.io/_uploads/SyygQfPp0.png
"/>
- Điểm vô cùng $O$ thực hiện chứng năng như một phần tử đơn vị trong một nhóm.
$$P + O = P$$
$$P + (-P) = O$$
:pencil2: **Những điều trên dẫn ta trở lại với định nghĩa của Đường cong Elliptic**
- **Định nghĩa:** Một đường cong Elliptic $\mathbb{E}$ là tập hợp nghiệm của **phương trình Weierstrass** (Weierstrass equation).
<span style="font-size:1.3em; text-align:center">$$\mathbb{E}: Y^2 = X^3 +aX+b$$</span>
- Cùng với điểm vô cùng $O$, các hằng số $a,b$ phải thỏa mãn mối quan hệ sau để đảm bảo rằng không tồn tại bất kỳ điểm kỳ dị nào trên đường cong.
<span style="font-size:1.3em; text-align:center">$$\mathbb{E}: 4a^3 + 27b^2 \neq 0$$</span>
<img style="display: block; margin: auto;" width="300" src="https://hackmd.io/_uploads/S1ZeN1up0.png
"/>
<p style="text-align:center;font-size:0.9em">Đường cong elliptic y^2 = x^3 − 3x +2 tồn tại một điểm kỳ dị tại x = 1</p>
- Phép cộng điểm trên đường cong $E$ thỏa mãn các tính chất sau: **phần tử trung hòa**, **phần tử nghịch đảo**, **kết hợp** và **giao hoán**.
$$P + O = O +P = P$$
$$P + (-P) = O$$
$$(P+Q)+R = P +(Q+R)$$
$$P + Q = Q +P$$
- Khi học **ECC** chúng ta sẽ nghiên cứu nó trên trường hữu hạn $\mathbb{F}_p$. Điều này có nghĩa là đường cong Elliptic thẳng tắp ban đầu khi bị đặt trong trường hữu hạn sẽ chỉ còn là những điểm rời rạc với tọa độ $(x,y)$ là những số nguyên trong $\mathbb{F}_p$.
- **Quay trở lại với Challenge**: Đề yêu cầu ta trả lời câu hỏi sau: tính chất $P + Q = Q +P$ cho thấy rằng phép cộng điểm trên đường con Elliptic có tính chất giao hoán. Vậy một nhóm mà có tính chất giao hoán được gọi là nhóm gì?
:::spoiler Flag
Đáp án là **nhóm Abel** (Abelian)
**crypto{Abelian}**
:::
## Starter
### Point Negation 10 pts · 3484 Solves
- **Mô tả:** Challenge này cho chúng ta biết rằng chúng ta sẽ làm việc với đường cong Elliptic trên một trường hữu hạn chứ không phải tập số thực nữa và yêu cầu ta tìm phần tử nghịch đảo của một điểm $P$ trên một trường hữu hạn để có $Flag$.
- Ở challenge trước, chúng ta có thể hiểu cơ bản rằng phép cộng điểm trên đường cong Elliptic là một phép tính trên nhóm Abel. Về mặt hình học thì ta cho phép tọa độ các điểm trên đường cong là bất kỳ số thực nào. Còn để áp dụng được ECC thì chúng ta phải nghiên cứu tọa độ của chúng trên một trường hữu hạn $\mathbb{F}_p$.
- Ta vẫn sẽ xem xét đường cong Elliptic trong công thức: $E: Y^2 = X^3 +aX+ b$ với $a,b \in \mathbb{F}_p$ và $4a^3+27b^2 \neq 0$. Tuy nhiên, sẽ không làm việc với một đường cong liên tục từ đầu tới đuôi mà sẽ là tập hợp các điểm được định nghĩa như sau:
$$E(\mathbb{F}_p) = \left\{(x,y):x,y \in \mathbb{F}_p | \hspace{2mm} y^2 = x^3 + ax+b \right\} \cup O$$
> :pencil2: Dù làm việc ở trong một trường hữu hạn nhưng những tính chất ta được học trước đây đều được giữ nguyên. Điểm vô cùng $O$, phép cộng điểm vẫn không thay đổi. Khi cho hai điểm thuộc $\mathbb{F}_p$, thì phép cộng điểm vẫn cho ra một điểm khác $\in \mathbb{F}_p$.
- **Quay trở lại với Challenge:** Toàn bộ challenge trong phần $STARER$ sẽ làm việc với đường cong sau:
$$E: Y^2 = X^3 + 487X + 1768 \mod(9739)$$
:question: Hãy sử dụng đường cong trên, và điểm $P(8045,6936)$. hãy tìm điểm $Q(x,y)$ sao cho $P + Q = O$ (điểm vô cùng).
- **Hướng giải:** Để cho kết quả là phần tử đơn vị của đường cong ($O$) thì ta sẽ cộng $P$ với phần tử nghịch đảo của nó là $(-P)$ theo tính chất:
$$P + (-P) = O$$
:exclamation: **Lưu ý:** theo quy ước thì phần tử nghịch đảo của $P = (x,y)$ sẽ là điểm $(-P)$ có tọa độ $(x, -y)$ chứ không phải $(-x,-y)$. Vì phần tử nghịch đảo là phần tử được lấy đối xứng qua trục $Ox$ nên tọa độ $y$ sẽ bị đổi dấu.
$\Rightarrow$ Vậy điểm $Q$ mà ta cần tìm chính là $(-P) = (x,-y)$.
:exclamation: **Lưu ý:** Ta đang làm việc trên một trường hữu hạn nên hãy chú ý những **số âm**.
:::spoiler Flag
(-P) = (8045, -6936) mod p = (8045, 2803)
**crypto{8045, 2803}**
:::
### Point Addition 30 pts · 3043 Solves
- **Mô tả:** Challenge này giới thiệu cho ta thuật toán để thực hiện phép cộng điểm trên hai điểm $P,Q$ và yêu cầu ta sử dụng thuật toán đó để tìm tọa độ của phép tính $S$ mà đề cho. Tọa độ của điểm $S$ sẽ là $Flag$.
- Khi làm việc với **đường cong Elliptic** thì ta cần thực hiện phép cộng điểm rất nhiều lần. Ở những challenge trước thì ta đã biết được phép cộng điểm diễn ra như thế nào thông qua khía cạnh hình học. Nhưng có một thuật toán rất hiệu quả để tính phép cộng điểm trên một đường cong Elliptic mà nó sẽ trả lại kết quả là tọa độ của điểm mới do hai điểm kia tạo ra.
- Thuật toán cộng hai điểm $P$ và $Q$ như sau:
<img style="display: block; margin: auto;" width="400" src="https://hackmd.io/_uploads/ryUKK-da0.png
"/>
> :pencil2: Ta đang làm việc với một trường hữu hạn nên những phép tính ở trên cần phải thực hiện thêm phép **modulo** $p$ ở cuối, và quan trọng là khi tính toán mà gặp dấu **"/"** thì chúng ta không **"chia"**, thay vào đó là nhân cho nghịch đảo modulo của **số chia**.
- **Quay trở lại Challenge:** Sử dụng đường cong $E$ ở challenge trước. Cho các điểm $P=(493,5564),Q=(1539,4742),R=(4403,5202)$, tìm điểm $S(x,y) = P + P + Q + R$ bằng cách thực hiện thuật toán ở trên. $Flag$ sẽ là tọa độ của $S$.
- **Đoạn code** làm cái thuật toán bên trên do mình nấu như sau:
```python
def addition(a, A, B, p):
if A == [0, 1]:
return B
elif B == [0, 1]:
return A
elif A[0] == B[0] and A[1] == -B[1] % p:
return [0, 1]
if A[0] != B[0]:
lam = ((B[1] - A[1]) * pow(B[0] - A[0], -1, p)) % p
elif A == B and A[1] != 0:
lam = ((3 * A[0]**2 + a) * pow(2 * A[1], -1, p)) % p
else:
return [0, 1]
x = (lam**2 - A[0] - B[0]) % p
y = (lam * (A[0] - x) - A[1]) % p
return [x, y]
```
- Có được hàm **Addition** thì ta chỉ cần truyền các giá trị vào để tính $S = P + P + Q + R$ thôi, đoạn **code** như sau:
```python
def addition(a, A, B, p):
if A == [0, 1]:
return B
elif B == [0, 1]:
return A
elif A[0] == B[0] and A[1] == -B[1] % p:
return [0, 1]
if A[0] != B[0]:
lam = ((B[1] - A[1]) * pow(B[0] - A[0], -1, p)) % p
elif A == B and A[1] != 0:
lam = ((3 * A[0]**2 + a) * pow(2 * A[1], -1, p)) % p
else:
return [0, 1]
x = (lam**2 - A[0] - B[0]) % p
y = (lam * (A[0] - x) - A[1]) % p
return [x, y]
P=(493,5564)
Q=(1539,4742)
R=(4403,5202)
a = 497
b = 1768
p = 9739
P2 = addition(a, P, P, p)
P2Q = addition(a, P2, Q, p)
P2QR = addition(a, P2Q, R, p)
print(P2QR)
```
:::spoiler Flag
**crypto{4215,2162}**
:::
### Scalar Multiplication 35 pts · 2883 Solves
- **Mô tả:** Challenge này định nghĩa phép nhân vô hướng là gì, thuật toán để tính phép nhân vô hướng và yêu cầu ta dùng thuật toán đó để tính phép tính $Q$ mà đề cho để nhận $Flag$.
- Phép **Nhân vô hướng** một điểm với một số $[n]$ là việc thực hiện phép cộng điểm đó với chính nó $[n]$ lần: $[3]P = P+P+P$. Không tồn tại phép nhân hai điểm $P,Q$ riêng biệt.
- Dưới đây là thuật toán **Double and Add** dùng để tính tích vô hướng của một điểm cho một số $[n]$. Nó thì không phải thuật toán hiệu quả nhất nhưng mà là dễ hiểu nhất cho chúng ta.
<img style="display: block; margin: auto;" width="400" src="https://hackmd.io/_uploads/SJ9HFZ_6R.png
"/>
- **Quay trở lại Challenge**: Sử dụng đường cong $E$ ở challenge trước, cùng điểm $P=(2339,2213)$. Tìm điểm $Q(x,y) = [7863]P$ bằng cách dùng thuật toán bên trên.
- **Đoạn code** thực hiện thuận toán tìm tích vô hướng như sau:
```python
def scalar(a, P, n, p):
Q = P
R = [0, 1]
while n > 0:
if n % 2 == 1:
R = addition(a, R, Q, p)
Q = addition(a, Q, Q, p)
n = n // 2
return R
```
- Giờ chỉ cần truyền các tham số vào để giải ra $Q$ thôi, đoạn code như sau:
```python
def addition(a, A, B, p):
if A == [0, 1]:
return B
elif B == [0, 1]:
return A
elif A[0] == B[0] and A[1] == -B[1] % p:
return [0, 1]
if A[0] != B[0]:
lam = ((B[1] - A[1]) * pow(B[0] - A[0], -1, p)) % p
elif A == B and A[1] != 0:
lam = ((3 * A[0]**2 + a) * pow(2 * A[1], -1, p)) % p
else:
return [0, 1]
x = (lam**2 - A[0] - B[0]) % p
y = (lam * (A[0] - x) - A[1]) % p
return [x, y]
def scalar(a, P, n, p):
Q = P
R = [0, 1]
while n > 0:
if n % 2 == 1:
R = addition(a, R, Q, p)
Q = addition(a, Q, Q, p)
n = n // 2
return R
a = 497
b = 1768
p = 9739
P = [2339,2213]
k = 7863
print(scalar(a, P, k, p))
```
:::spoiler Flag
**crypto{9467,2742}**
:::
### Curves and Logs 40 pts · 2750 Solves
- **Mô tả:** Challenge cho ta thấy cách mà hai bên là **Alice** và **Bob** trao đổi khóa chung, và yêu cầu ta tính toán khóa chung từ những dữ kiện mà đề cho để có $Flag$.
- Bài toán Logarit rời rạc trên đường cong Elliptic (ECDLP) là bài toán tìm $[n]$ sao cho $Q = [n]P$.
- Cũng giống như bài toán **Logarit rời rạc (DLP)** mà ta gặp trước đây thì phép nhân vô hướng của một điểm trên $\mathbb{E}(\mathbb{F}_p)$ cũng là một bài toán rất khó để làm ngược lại bởi vì thuật toán hiệu quả nhất cũng phải mất $q^{1/2}$ thời gian với $q$ là cấp của nhóm con của $P$.
**Bây giờ Alice và Bob muốn trao đổi tin nhắn nhắn cho nhau thì hai người sẽ thực hiện theo những bước sau:**
- Đầu tiên hai người sẽ thỏa thuận dùng chung một đường cong $\mathbb{E}$, một số nguyên tố $p$ và một phần tử sinh $G$ sao cho nó có thể tạo ra được một nhóm con $H = \left< G\right>$ có bậc bằng $q$ là một số nguyên tố.
> Như chúng ta đã biết thì **order** của một phần tử $P$ là một số $n$ nào đó sao cho $n \times P = O$ (phần tử vô cùng). Và trong hệ mã ECC thì **order** của phần tử sinh $G$ phải là một số nguyên tố để chống các kiểu tấn công **Pollard's Rho** và **Pohlig-Hellman**.
- Quá trình trao đổi khóa Diffie-Hellman **(ECHD)** trên đường con Elliptic diễn ra như sau:
- $Alice$ tạo một số nguyên ngẫu nhiên $n_A$ và tính $Q_A = [n_A]G$
- $Bob$ cũng làm tương tự tạo cho mình $n_B$ và tính $Q_B = [n_B]G$
- Sau đó Alice gửi cho Bob $Q_A$ còn Bob gửi ngược lại cô $Q_B$. Bời vì bài toán **ECDLP** là rất khó giải nên người nghe lén là $Eve$ không thể tính được $n_A$ hay $n_B$.
- Để tính khóa chung $S$ thì Alice tính theo công thức $[n_A]Q_B$ còn Bob thì công thức $[n_B]Q_A$.
- Bởi vì phép nhân vô hướng có tính giao hoán nên: $$S = [n_A]Q_B=[n_B]Q_A$$
- Giờ thì Alice và Bob có thể dùng $S$ để làm khóa chung rồi.
- **Quay trở lại với Challenge:** Sử dụng đường cong $E$ từ challenge trước, ta có khóa bí mật là $n_B = 1829$ và nhận được khóa công khai của Alice là $Q_A = (815,3190)$. Đề yêu cầu ta tính khóa cung $S$ rồi tính **SHA1 hash** của $x_S$ để có $Flag$.
- Ta tính $S$ theo công thức $S = [n_B]Q_A = 1829 \times (815,3190) = (7929, 707)$
- Với $x_S = 7929$ ta chuyển sang **String** rồi đưa vào **SHA1 hash** để có $Flag$.
```python
import hashlib
data = "7929"
hashed = hashlib.sha1(data.encode()).hexdigest()
print(hashed)
```
:::spoiler Flag
**crypto{80e5212754a824d3a4aed185ace4f9cac0f908bf}**
:::
### Efficient Exchange 50 pts · 2490 Solves
- $Alice$ và $Bob$ khi nhìn vào bài toán **Logarit rời rạc** trên đường cong Elliptic thì họ thấy rằng khi gửi cho nhau khóa công khai thì việc gửi cả $x$ và $y$ là không cần thiết. Chỉ cần gửi đi $x$ là đủ.
- Miễn Alice và Bob sử dụng đúng các tham số, thì một giá trị $x$ sẽ chỉ có hai giá trị là $y$ và $-y$ mà thôi. Lúc này muốn chọn giá trị nào làm $y$ để tính khóa chung cũng được. Chỉ hơi cực khi phải đi tính $y$ của khóa công khai một lần nữa.
- Thật vậy, dù ghép $x$ với bất kỳ giá trị $y$ nào mà ta tính ra được thì sau cùng giá trị $x$ của **khóa chung** vẫn sẽ giống nhau?? :exploding_head: Vì sao nhỉ? Ở ví dụ bên dưới ta có hai điểm có tọa độ là $(x,y)$ và $(x,-y)$, khi ta nhân chúng cho bất kỳ giá trị $n$ nào thì giá trị $x$ của cả hai kết quả sẽ luôn giống nhau, chỉ khác nhau giá trị của $y$.
```python
#sage
E = EllipticCurve(GF(9739),[497,1768])
e1 = E(7936, 1985)
e2 = E(7936, 7754)
for n in range(2,7):
print("n =", n)
print(e1*n, e2*n)
```
:::spoiler
n = 2
(4944 : 752 : 1) (4944 : 8987 : 1)
n = 3
(2709 : 3551 : 1) (2709 : 6188 : 1)
n = 4
(5981 : 2255 : 1) (5981 : 7484 : 1)
n = 5
(9402 : 4295 : 1) (9402 : 5444 : 1)
n = 6
(9687 : 1474 : 1) (9687 : 8265 : 1)
:::
- **Quay trở lại Challenge:** Vẫn sử dụng đường cong $E$ và điểm sinh $G$ ở challenge trước, đề cho ta tọa độ $x$ từ khóa công khai của **Alice** là $x(Q_A) = 4726$, và khóa bí mật của ta là $n_B = 6534$. Yêu cầu hãy tính tọa độ $x_S$ làm **shared_secret** để giải mã thông điệp được mã hóa bằng **AES-CBC**. Challenge đã cung cấp file `decrypt.py` giúp ta có thể truyền $3$ tham số là **shared_secret**, **IV** và **ciphertext** vào để giải mã ra **plaintext**.
- Được gợi ý ở trên rằng ta có thể chọn giá trị $y$ nào cho $x$ cũng được, sau cùng $x_S$ của cả hai sẽ luôn giống nhau. Vì thế bước đầu của ta chính là đi tính tọa độ $y$ của $x(Q_A) = 4726$.
- Để tìm được $y$ thì ta sẽ giải phương trình bậc hai Modulo sau:
$$y^2 \equiv x^3 + 497x + 1768 \pmod{9739}$$
>với x = 4726, thay vào phương trình ta được:
$$y^2 \equiv 4726^3 + 497\times 4726 + 1768 \pmod{9739}$$
$$\Leftrightarrow y^2 \equiv 5507 \pmod{9739}$$
- Để giải phương trình trên thì ta phải đi tính căn bậc hai Modulo $p$ của $5507$. Nhưng với điều kiện $5507$ phải là một **thặng dư bậc hai** (quadratic residue) tức là phải tồn tại $y$ sao cho $y^2 \equiv 5507 \pmod{9739}$.
:bulb: Đề có gợi ý như sau:
- Tức $p$ của chúng ta thuộc dạng $p \equiv 3 \pmod 4$. Mà khi $p \equiv 3 \pmod 4$ hoặc $p \equiv 1 \pmod 4$ thì khi này chắc chắn tồn tại thặng dư bậc hai. Ta sẽ sử dụng công thức $\sqrt{a} \equiv a^{p+1 \over 4 }\pmod{p}$ để tìm căn bậc hai Modulo $p$ của $5507$.
- Hoặc có thể dùng phương thức `.sqrt()` trong **sagemath** để tìm cũng được nếu bạn lười như mình :3
- Đoạn code tìm tọa độ $y$ của $x(Q_A) = 4726$ như sau:
```python
#sage
F = GF(9739)
xQ_A = F(5669) # Tạo phần tử trong trường hữu hạn
y1Q_A = xQ_A.sqrt() # căn bậc hai Modulo
y2Q_A = -y1Q_A % 9739 # nghiệm 2 sẽ là giá trị âm của nghiệm 1
print(y1Q_A, y2Q_A)
#3452 6287
```
- Với $x = 4726$ thì tồn tại hai giá trị $y$ là $3452$ và $6287$, ta sẽ chọn cặp $(x,y) = (4726,3452)$ làm khóa công khai của $Alice$.
- Khi có khóa công khai của **Alice**, ta sẽ dễ dàng tính được khóa chung qua công thức $S = Q_A \times n_B$, đoạn code như sau:
```python
#sage
E = EllipticCurve(GF(9739),[497,1768])
Q_A = E(4726, 3452)
n_B = 6534
print(Q_A * n_B)
#(1791 : 7558 : 1)
```
- Có trong tay $3$ tham số **shared_secret = 1791**, **IV** và **ciphertext**, ta sẽ truyền chúng vào hàm **decrypt** để 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 = 1791
iv = "cd9da9f1c60925922377ea952afc212c"
ciphertext = "febcbe3a3414a730b125931dccf912d2239f3e969c4334d95ed0ec86f6449ad8"
print(decrypt_flag(shared_secret, iv, ciphertext))
```
:::spoiler Flag
**crypto{3ff1c1ent_k3y_3xch4ng3}**
:::
## Parameter Choice
### Smooth Criminal 60 pts · 1621 Solves
- **Mô tả:** Challenge cung cấp cho ta hai file là `source.py` và `output.py`. File `source.py` là đoạn code mã hóa **ECC** do tác giả tự chế ra để mã hóa thông điệp gửi đi cho **Bob** và file `output.py` là thông điệp bị mã hóa. Vì đây là **ECC** tự chế nên nó có những lổ hổng nghiêm trọng, ta sẽ khai thác nó để tìm được thông tin hữu ích.
- Khi làm Challenge **Curves and Logs** thì tác giả có nói rằng: "Order của điểm sinh $G$ cần phải là một số nguyên tố, việc xây dựng nên một hệ mã ECC là vô cùng phức tạp, nên nó khuyến khích chúng ta nên sử dụng đường cong, số nguyên tố, và điểm sinh $G$ có sẵn do các nhà toán học xây dựng chứ không nên tự chế".
- Challenge này có một lỗ hổng đó là **order** của điểm sinh $G$ không phải là một số nguyên tố, mà nó là một **[smooth number](https://en.wikipedia.org/wiki/Smooth_number)**. Điều này khiến nó có thể bị phân tích thành nhiều thừa số nguyên tố, tạo tiền đề cho kiểu tấn công **Pohlig-Hellman**.
- Ta sẽ sử dụng phương thức `.factor()` để phân tích thừa số nguyên tố của $ord(G)$, đoạn code như sau:
```python
#sage
p = 310717010502520989590157367261876774703
a = 2
b = 3
E = EllipticCurve(GF(p), [a, b])
G = E(179210853392303317793440285562762725654, 105268671499942631758568591033409611165)
ord_G = G.order()
# ord_G = 155358505251260494795103074529582338902
print(ord_G.factor())
#2 * 3^7 * 139 * 165229 * 31850531 * 270778799 * 179317983307
```
- Vì $ord(G)$ là một **smooth number** nên bài toán Logarit rời rạc (DLP) đã có thể giải nhanh hơn nhờ thuật toán **Pohlig-Hellman**. Ta sẽ giải phương trình DLP $Q_A = n_A \times G$ bằng thuật toán Pohlig-Hellman để tìm ra được $n_A$:
```python
from sage.all import*
p = 310717010502520989590157367261876774703
a = 2
b = 3
E = EllipticCurve(GF(p), [a, b])
G = E(179210853392303317793440285562762725654, 105268671499942631758568591033409611165)
Q_A = E(280810182131414898730378982766101210916, 291506490768054478159835604632710368904)
n = G.order()
factors = n.factor()
#Pohlig-Hellman
d = []
subgroup = []
for p, e in factors:
G0 = (n // p ** e) * G
Q_A0 = (n // p ** e) * Q_A
x = discrete_log(Q_A0, G0, operation='+')
d.append(x)
subgroup.append(p ** e)
secret = crt(d, subgroup)
print(secret)
#47836431801801373761601790722388100620
```
- Có $n_B$ thì chỉ cần thay vào công thức $S = n_A \times Q_B$ để có khóa chung:
```python
p = 310717010502520989590157367261876774703
a = 2
b = 3
E = EllipticCurve(GF(p), [a, b])
G = E(179210853392303317793440285562762725654, 105268671499942631758568591033409611165)
Q_B = E(272640099140026426377756188075937988094, 51062462309521034358726608268084433317)
n_A = 47836431801801373761601790722388100620
print(Q_B * n_A)
#(171172176587165701252669133307091694084 : 188106434727500221954651940996276684440 : 1)
```
- Có $x_S$ làm **shared_secret**, **IV** và **Ciphertext**, giờ ta sẽ truyền $3$ tham số trên vào hàm `decrypt` để giải ra $Flag$.
```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 = 171172176587165701252669133307091694084
iv = "07e2628b590095a5e332d397b8a59aa7"
ciphertext = "8220b7c47b36777a737f5ef9caa2814cf20c1c1ef496ec21a9b4833da24a008d0870d3ac3a6ad80065c138a2ed6136af"
print(decrypt_flag(shared_secret, iv, ciphertext))
```
:::spoiler Flag
**crypto{n07_4ll_curv3s_4r3_s4f3_curv3s}**
:::
### Exceptional Curves 100 pts · 945 Solves
- **Mô tả:** Ở Challenge trước ta có $ord(G)$ có thể bị phân tích thành nhiều thừa số nguyên tố khiến bài toán ECDLP bị giải nhanh chóng thì ở Challenge này $ord(G)$ to bằng cả Modulus $p$ của trường hữu hạn luôn :flushed: Chắc là không tạo ra lỗ hổng nào đâu?
- Có! khi $\#E(Fp) = p$ thì nó sẽ tạo tiền đề cho kiểu tấn công **Smart Attack**. Kiểu tấn công trên sẽ giúp ta giải bài toán Logarit rời rạc (ECDLP) một cách nhanh chóng.
- Hàm để thực hiện kiểu tấn công **SmartAttack** như bên dưới, nó sẽ giúp ta giải phương trình Logarit rời rạc $P \equiv G \times n \pmod{p}$ để ra được $n$:
```python
def SmartAttack(P,Q,p):
E = P.curve()
Eqp = EllipticCurve(Qp(p, 2), [ ZZ(t) + randint(0,p)*p for t in E.a_invariants() ])
P_Qps = Eqp.lift_x(ZZ(P.xy()[0]), all=True)
for P_Qp in P_Qps:
if GF(p)(P_Qp.xy()[1]) == P.xy()[1]:
break
Q_Qps = Eqp.lift_x(ZZ(Q.xy()[0]), all=True)
for Q_Qp in Q_Qps:
if GF(p)(Q_Qp.xy()[1]) == Q.xy()[1]:
break
p_times_P = p*P_Qp
p_times_Q = p*Q_Qp
x_P,y_P = p_times_P.xy()
x_Q,y_Q = p_times_Q.xy()
phi_P = -(x_P/y_P)
phi_Q = -(x_Q/y_Q)
k = phi_Q/phi_P
return ZZ(k)
```
- Đoạn code tìm $n_A$ như sau:
```python
from sage.all import *
def SmartAttack(P,Q,p):
E = P.curve()
Eqp = EllipticCurve(Qp(p, 2), [ ZZ(t) + randint(0,p)*p for t in E.a_invariants() ])
P_Qps = Eqp.lift_x(ZZ(P.xy()[0]), all=True)
for P_Qp in P_Qps:
if GF(p)(P_Qp.xy()[1]) == P.xy()[1]:
break
Q_Qps = Eqp.lift_x(ZZ(Q.xy()[0]), all=True)
for Q_Qp in Q_Qps:
if GF(p)(Q_Qp.xy()[1]) == Q.xy()[1]:
break
p_times_P = p*P_Qp
p_times_Q = p*Q_Qp
x_P,y_P = p_times_P.xy()
x_Q,y_Q = p_times_Q.xy()
phi_P = -(x_P/y_P)
phi_Q = -(x_Q/y_Q)
k = phi_Q/phi_P
return ZZ(k)
# Curve params
p = 0xa15c4fb663a578d8b2496d3151a946119ee42695e18e13e90600192b1d0abdbb6f787f90c8d102ff88e284dd4526f5f6b6c980bf88f1d0490714b67e8a2a2b77
a = 0x5e009506fcc7eff573bc960d88638fe25e76a9b6c7caeea072a27dcd1fa46abb15b7b6210cf90caba982893ee2779669bac06e267013486b22ff3e24abae2d42
b = 0x2ce7d1ca4493b0977f088f6d30d9241f8048fdea112cc385b793bce953998caae680864a7d3aa437ea3ffd1441ca3fb352b0b710bb3f053e980e503be9a7fece
# Define curve
E = EllipticCurve(GF(p), [a, b])
G = E(3034712809375537908102988750113382444008758539448972750581525810900634243392172703684905257490982543775233630011707375189041302436945106395617312498769005, 4986645098582616415690074082237817624424333339074969364527548107042876175480894132576399611027847402879885574130125050842710052291870268101817275410204850)
Q_A = E(4748198372895404866752111766626421927481971519483471383813044005699388317650395315193922226704604937454742608233124831870493636003725200307683939875286865, 2421873309002279841021791369884483308051497215798017509805302041102468310636822060707350789776065212606890489706597369526562336256272258544226688832663757)
n_A = SmartAttack(G,Q_A,p)
print(n_A)
#2200911270816846838022388357422161552282496835763864725672800875786994850585872907705630132325051034876291845289429009837283760741160188885749171857285407
```
- Có $n_A$ thì ta dễ dàng tín được khóa chúng từ công thức: $S = n_A \times Q_B$:
```python
#sage
p = 0xa15c4fb663a578d8b2496d3151a946119ee42695e18e13e90600192b1d0abdbb6f787f90c8d102ff88e284dd4526f5f6b6c980bf88f1d0490714b67e8a2a2b77
a = 0x5e009506fcc7eff573bc960d88638fe25e76a9b6c7caeea072a27dcd1fa46abb15b7b6210cf90caba982893ee2779669bac06e267013486b22ff3e24abae2d42
b = 0x2ce7d1ca4493b0977f088f6d30d9241f8048fdea112cc385b793bce953998caae680864a7d3aa437ea3ffd1441ca3fb352b0b710bb3f053e980e503be9a7fece
E = EllipticCurve(GF(p), [a, b])
Q_B = E(0x7f0489e4efe6905f039476db54f9b6eac654c780342169155344abc5ac90167adc6b8dabacec643cbe420abffe9760cbc3e8a2b508d24779461c19b20e242a38, 0xdd04134e747354e5b9618d8cb3f60e03a74a709d4956641b234daa8a65d43df34e18d00a59c070801178d198e8905ef670118c15b0906d3a00a662d3a2736bf)
n_A = 2200911270816846838022388357422161552282496835763864725672800875786994850585872907705630132325051034876291845289429009837283760741160188885749171857285407
S = (Q_B * n_A)
print(S)
#(8216782777192629016736082577047876662181587556895841333932300215083185803392455455078234452846594885807223123796905544359993306809106491336354148716965075 : 148242255193707745238490492470982569663420403534103630669750159547273939511000254936452583511650128798498874821400341065904433354709622703123910071981138 : 1)
```
- Có $x_S$ làm **shared_secret**, **IV** và **Ciphertext**, giờ ta sẽ truyền $3$ tham số trên vào hàm `decrypt` để giải ra $Flag$.
```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 = 8216782777192629016736082577047876662181587556895841333932300215083185803392455455078234452846594885807223123796905544359993306809106491336354148716965075
iv = "719700b2470525781cc844db1febd994"
ciphertext = "335470f413c225b705db2e930b9d460d3947b3836059fb890b044e46cbb343f0"
print(decrypt_flag(shared_secret, iv, ciphertext))
```
:::spoiler Flag
**crypto{H3ns3l_lift3d_my_fl4g!}**
:::
### Micro Transmissions 120 pts · 670 Solves
- **Mô tả:** Challenge này gần giống với Challenge **Smooth Criminal** vì $Ord(G)$ của cả hai không phải một số nguyên tố, nhưng ở Challenge này thì thừa số nguyên tố của $Ord(G)$ cũng rất lớn nên đề đã tạo thêm lỗ hổng để ta có thể sử dụng **Pohlig-Hellman Attack** .
- Challenge này cho ta giá trị $x$ từ khóa công khai của $Alice$ và $Bob$, ta sẽ tìm lại giá trị $y$ bằng cách sử dụng hàm `lift_x()` thay vì đi tính thủ công như những challenge trước.
- Dùng phương thức `.factor()` ta phân tích được **G.order()** như sau:
```python
from sage.all import*
p = 99061670249353652702595159229088680425828208953931838069069584252923270946291
E = EllipticCurve(GF(p), [1,4])
G = E(43190960452218023575787899214023014938926631792651638044680168600989609069200, 20971936269255296908588589778128791635639992476076894152303569022736123671173)
order = G.order()
print(order.factor())
#7 * 11 * 17 * 191 * 317 * 331 * 5221385621 * 5397618469 * 210071842937040101 * 637807437018177170959577732683
```
- Vì $ord(G)$ có thể phân tích thành nhiều ước như vậy, ta sẽ nghĩ đến kiểu tấn công **Pohlig-Hellman**, nhưng nếu chỉ chạy thuật toán Pohlig-Hellman như bình thường thì sẽ rất là lâu vì **hai** ước cuối cùng của $ord(G$) rất là to. Để giảm thời gian chờ, ta chú vào hàm **gen_key_pair()**:
```python
def gen_key_pair(G, nbits):
n = random.getrandbits(nbits)
P = n*G
return P.xy()[0], n
```
- Thuật toán **Pohlig-Hellman** hoạt động kiểu: nó chia cái $order(G)$ của chúng ta thành nhiều nhóm con có **order** là $p_1^{e2,}p_2^{e2},p_3^{e3}...$ rồi nó tính Logarit rời rạc trên từng nhóm con đó. Sau cùng sẽ dùng thặng dư trung hoa (CRT) để gộp lại thành nghiệm $x$ của phương trình Logarit rời rạc ban đầu.
- Mà nhìn vào đoạn code ở trên thì ta thấy rằng $n_A$ và $n_B$ khá là nhỏ, chỉ $64$ bit (**18446744073709551615**) nhỏ hơn so với hai ước cuối của `order.factor()`. Vì vậy khi chạy thuật toán Pohlig-Hellman thì ta sẽ bỏ đi hai ước cuối đi vì chúng quá to so với khóa bí mật của ta.
- Đoạn code đi tìm $n_A$ như sau:
```python
from sage.all import*
p = 99061670249353652702595159229088680425828208953931838069069584252923270946291
a = 1
b = 4
E = EllipticCurve(GF(p), [a,b])
G = E(43190960452218023575787899214023014938926631792651638044680168600989609069200, 20971936269255296908588589778128791635639992476076894152303569022736123671173)
n = G.order()
factors = n.factor()[:-2] #bỏ đi hai ước cuối
xQA = 87360200456784002948566700858113190957688355783112995047798140117594305287669
Q_A = E.lift_x(ZZ(xQA)) #sử dụng .lift_x để tìm y, dùng ZZ() để chuyển sang int
#Pohlig-Hellman
d = []
subgroup = []
for p, e in factors:
G0 = (n // p ** e) * G
Q_A0 = (n // p ** e) * Q_A
x = discrete_log(Q_A0, G0, operation='+')
d.append(x)
subgroup.append(p ** e)
secret = crt(d, subgroup)
print(secret)
# 15423694994465574149
```
- Có được $n_A$ thì ta đi tính khóa chung thôi:
```python
from sage.all import*
p = 99061670249353652702595159229088680425828208953931838069069584252923270946291
a = 1
b = 4
E = EllipticCurve(GF(p), [a,b])
xQB = 6082896373499126624029343293750138460137531774473450341235217699497602895121
Q_B = E.lift_x(ZZ(xQB))
n_A = 15423694994465574149
S = Q_B * n_A
print(S)
#(92209717447332837440641806732517921920015580446111641942522142444036785043977 : 75091479522943693128989947826298830741418388855527893529216575952811663232944 : 1)
```
- Có $x_S$ làm **shared_secret**, **IV** và **Ciphertext**, giờ ta sẽ truyền $3$ tham số trên vào hàm `decrypt` để giải ra $Flag$.
```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 = 92209717447332837440641806732517921920015580446111641942522142444036785043977
iv = "ceb34a8c174d77136455971f08641cc5"
ciphertext = "b503bf04df71cfbd3f464aec2083e9b79c825803a4d4a43697889ad29eb75453"
print(decrypt_flag(shared_secret, iv, ciphertext))
```
:::spoiler Flag
**crypto{d0nt_l3t_n_b3_t00_sm4ll}**
:::
<h2 style="text-align:center;">END</h2>
Sign in with Wallet
Connect another wallet