<h1 style="text-align:center;">Isogeny Based Cryptography</h1>

Hệ mã dựa trên Isogeny (**Isogeny-based cryptography**) là một mảng khá mới trong mật mã học, xuất hiện vào đầu những năm 2000 dưới sự nghiên cứu của **Couveignes**, **Rostovtsev** và **Stolbunov**. Do tính phức tạp về toán học, lĩnh vực này có thể khiến nhiều nhà nghiên cứu trẻ cảm thấy e ngại, nhưng sự phong phú về mặt toán học cũng là một khía cạnh hấp dẫn, đã thu hút rất nhiều sự chú ý nghiên cứu trong suốt hai thập kỷ qua.

Thứ mà các nhà mật mã học đặc biệt quan tâm chính là các đường cong Elliptic siêu kỳ dị (**supersingular elliptic curves**). Xét một đồ thị chứa các điểm là các đường cong siêu kỳ dị thì các **cạnh** nối các điểm sẽ là các **Isogeny** (có thể hiểu là ánh xạ) giữa các đường cong. Các đồ thị isogeny này có những tính chất toán học vô cùng đặc biệt, khiến chúng trở nên hấp dẫn trong việc thiết kế các hệ mã **bất đối xứng**, trong đó giá trị công khai sẽ là điểm đầu và điểm cuối, giá trị bí mật sẽ là các đường đi (isogeny) giữa chúng.

Vào năm 2022, hệ mã dựa trên Isogeny trải qua một đợt cải tiến quan trọng vì cơ chế trao đổi khóa dựa trên Isogeny trước đó là **SIDH** (Supersingular isogeny Diffie–Hellman) bị phá vỡ trong thời gian đa thức dựa trên bài nghiên cứu của **Kani** được xuất bản năm 1996. Nhưng nhờ vào sự phá vỡ đó mà các cơ chế trao đổi khóa bằng Isogeny đã được tích cực nghiên cứu hơn, biến chúng trở thành một trong các ứng viên cho dự án chống lượng tử sau này. Trong blog này, chúng ta sẽ tìm hiểu qua về lí thuyết cơ sở của Isogeny, cơ chế trao đổi khóa dựa trên Isogeny **SIDH** và **CSIDH**. Cuối cùng là làm một vài Challenge [**Cryptohack**](https://cryptohack.org/challenges/isogenies/) mảng Isogeny để nắm rõ hơn lí thuyết đã học.


---

# Lí Thuyết
## Cấu trúc đại số
### Các phép ánh xạ (mappings)

Ta cần nắm rõ và phân biệt được ba phép ánh xạ phổ biến là Injective, Surjective và Bijective.
++**Injective**++ (đơn ánh): Đây là phép ánh xạ **1-1**, tức **một** giá trị từ tập $A$ chỉ có **một** điểm ảnh ở $B$ mà thôi. Nếu số lượng phần tử của $A < B$ thì sẽ có một vài phần tử của $B$ không có điểm nào của $A$ ánh xạ tới.

++**Surjective**++ (toàn ánh): Từ "**toàn**" ở đây nghĩa là toàn bộ các phần tử của tập $B$ đều là ảnh của ít nhất **một** phần tử từ tập $A$. Nói cách khác, ảnh của $A$ phủ hết toàn bộ $B$.

++**Bijective**++ (song ánh): Đây là phép ánh xạ kết hợp giữa phép đơn ánh và toàn ánh, tức mỗi phần tử của $A$ và $B$ đều được ghép đôi một cách **duy nhất** với nhau, không có phần tử nào bị bỏ lại ở cả hai tập.

---

### Các phép biến hình (Morphism)
Ta cần hiểu các phép Morphism sau: Homomorphism, Isomorphism và Endomorphism.

++**Homomorphism**++ (Phép đồng cấu): là một phép ánh xạ bảo toàn cấu trúc giữa hai cấu trúc đại số cùng **loại**.

Cho hai nhóm $(G, \star)$ và $(H, \circ)$, gọi $\phi:G\rightarrow H$ là ánh xạ từ $G$ sang $H$ thì $\forall x,y \in G$, ánh xạ $\phi$ là phép đồng cấu nhóm nếu: $$\phi(x\star y) = \phi(x) \circ \phi(y)$$

++**Isomorphism**++ (Phép đẳng cấu): là một phép đồng cấu đặc biệt, một ánh xạ $\phi:G\rightarrow H$ được gọi là phép đẳng cấu nếu thỏa mãn các điều kiện sau:
- $\phi$ là *homomorphism*.
- $\phi$ là song ánh (*Bijective*).
- Tồn tại ánh xạ nghịch đảo $\phi^{-1}:H \rightarrow G$ sao cho $\phi^{-1}(\phi(x)) = x$ và $\phi^{-1}(\phi(y)) = y$.

> Ta ký hiệu hai nhóm $G$ và $H$ đẳng cấu với nhau là $G \cong H$.

++**Endomorphism**++ (Phép tự đồng cấu): là một Homomorphism từ một cấu trúc đại số về chính nó:
$$f:G\rightarrow G$$

Cho một cấu trúc đại số $A$, tập tất cả các endomorphism từ $A\rightarrow A$ được ký hiệu là: $\text{End}(A)$

Nếu ta định nghĩa hai phép toán:
- Cộng: $(f+g)(x) = f(x) + g(x)$
- Nhân (phép hợp hàm): $(f\circ g)(x) = f(g(x))$

thì $\text{End}(A)$ trở thành một vành (ring), và ta gọi đó là $\text{Endomorphism ring of } A$.

> Endomorphism không cần phải là song ánh.

## Elliptic Curve
### Đường cong dạng Weierstrass và Montgomery
Công thức **tổng quát** của đường cong Elliptic là:
$$E:y^2 + a_1xy + a_3y = x^3 + a_2x^2 + a_4x + a_6$$

++Ví dụ:++ Ta có thể xây dựng $E: y^2 = x^3 + 3x^2+5x+6$ trong sagemath như sau:

E = EllipticCurve(ZZ, [0, 3, 0, 5, 6]) # <= truyền a1, a2, a3, a4, a6
print(E)
# Elliptic Curve defined by y^2 = x^3 + 3*x^2 + 5*x + 6 over Integer Ring

Đường cong **Weierstrass** (dạng ngắn) là đường cong Elliptic mà ta đã làm quen trước đây, biểu diễn bằng công thức:
$$E:y^2 = x^3 + Ax + B$$

> Điều kiện để đường cong là đường cong hợp lệ là $4a^3 + 27b^2 \ne 0$.

---

Đường cong **Montgomery** là đường cong được biểu diễn bằng công thức:
$$E: By^2 = x^3 + Ax^2 + x$$

> Đường cong này mang lại hiệu suất rất tốt vì nó sử dụng thuật toán Montgomery Ladder để tính toán và nó cũng chống lại side-channel attack nữa.

Ta có thể chuyển từ đường cong Weierstrass → Montgomery bằng phương thức `.montgomery_model()` trong sagemath như sau:

E = EllipticCurve(GF(419), [269, 82])
print(E)
# Elliptic Curve defined by y^2 = x^3 + 269*x + 82 over Finite Field of size 419
EM = E.montgomery_model()
print(EM)
# Elliptic Curve defined by y^2 = x^3 + 199*x^2 + x over Finite Field of size 419

Để lấy hệ số `[a1,a2,a3,a4,a6]` của đường cong, ta dùng phương thức `.a_invariants()`:

E = EllipticCurve(GF(419), [269, 82])
print(E.a_invariants())
# (0, 0, 0, 269, 82)

---

### Đường cong Elliptic siêu kỳ dị (Supersingular Curve)
> Tránh nhầm lẫn với đường cong kỳ dị (Singular Curve), về mặt toán học thì từ siêu kỳ dị ở đây chỉ tính chất đặc biệt và độc đáo của đường cong chứ không phải ám chỉ đường cong có nhiều điểm kỳ dị (singularity). Tính chất đặc biệt của nó là nó có endomorphism ring lớn hơn so với đường cong elliptic thông thường.

**++Định nghĩa++**: Cho một đường cong Elliptic $E \in \mathbb{F}_q$ với $q=p^k$, thì $E$ là đường cong siêu kỳ dị (Supersingular) nếu và chỉ nếu số điểm trên đường cong $E$ thỏa mãn công thức sau:

$$\#E = q+1 - t$$

> Với một giá trị $t<2\sqrt{q}$ nào đó mà $t\equiv0\mod p$.

---

Với trường hợp đơn giản nhất là $q=p$ và $p>3$ thì khi này giá trị $t$ duy nhất thỏa mãn $t<2\sqrt{p}$ và $t\equiv0 \pmod p$ là $t=0$ mà thôi, suy ra số điểm trên đường cong $E$ khi này là:
$$\#E = p+1$$

Thêm vào đó nếu $\#E(\mathbb{F}_p)=p+1$ và $p>3$ thì số điểm của $E$ trên $\mathbb{F}_{p^2}$ sẽ thuộc tập giá trị sau:

$$\#E(\mathbb{F}_{p^2}) \in \left\{(p+1)^2, (p-1)^2, p^2+1 \right\}$$

Ta hoàn toàn có thể tính được **số lượng** đường cong Supersingular nằm trên $\mathbb{F}_p$ bằng công thức:
$$\left \lfloor \frac{p}{12}\right \rfloor + z$$

> $z \in \left\{0, 1, 2\right\}$ phụ thuộc vào giá trị $p\mod12$.

Để kiểm tra một đường cong có phải đường cong supersingular hay không, ta có thể sử dụng phương thức `.is_supersingular()` trong sagemath như sau:

E = EllipticCurve(GF(2**127-1), [0, 170141183460469230846243588177825628225, 0, 1, 0])
print(E.is_supersingular())
# True

---

### Phép đẳng cấu giữa hai đường cong (Isomorphisms)
Hai đường cong Elliptic $E_1$ và $E_2$ được gọi là đẳng cấu (isomorphic) trên một không gian $K$ nếu tồn tại một phép đẳng cấu $\phi: E_1 \rightarrow E_2$ giữa hai đường cong.

Tức là $\phi$ là một ánh xạ thỏa mãn các yếu tố:
- Là một song ánh (*bijection*).
- Là một hàm *hữu tỉ* khả nghịch.
- Bảo toàn cấu trúc nhóm, tức nếu ta có ba điểm $P,Q, R$ thỏa mãn $P+Q = R$ trên $E_1$ ta có thể tính tương tự trên $E_2$ bằng công thức: $\phi(P) + \phi(Q) = \phi(R)$.
- $\phi(k\cdot P) = k \cdot \phi(P)$, tức có thể đưa phép nhân ra ngoài.
- Cuối cùng $\phi(\mathcal{O}_{E_1}) = \mathcal{O}_{E_2}$.
> Ta ký hiệu hai đường cong đẳng cấu với nhau là $E_1 \cong E_2$.

---

Dạng chuẩn của isomorphism giữa hai elliptic curve dạng ngắn:

Giả sử $E_1 : y^2 = x^3+ax+b\cong E_2:y^2=x^3+a'x+b'$ thì mỗi phép đẳng cấu giữa hai đường cong đều có dạng:

$$\phi(x,y) = (u^2.x+r, \hspace{3mm} u^3.y+s.u^2.x+t)$$

Với $u \neq 0$, thì hệ số $a',b'$ của đường cong $E_2$ có thể được tính như sau:
$$a'=\frac{u^4}{a},\hspace{5mm}b'=\frac{u^6}{b}$$

Trong sagemath, để kiểm tra hai đường cong có đẳng cấu với nhau không, ta sử dụng phương thức `.is_isomorphic()`.

Và để xem phép đẳng cấu giữa chúng, ta dùng `.isomorphism_to()`, nó sẽ trả về các hệ số `(u, r, s, t)` của ánh xạ `(x,y)→(u^2.x + r, u^3.y + s.u^2.x + t)`.

F = GF(101)
u = F(-2)
a = F(2)
b = F(3)
E1 = EllipticCurve(F, [a, b])
E2 = EllipticCurve(F, [a/u^4, b/u^6])

print(E1.is_isomorphic(E2))
print(E1.order() == E2.order())
print(E1.isomorphism_to(E2))

# True
# True
# Elliptic-curve morphism:
#   From: Elliptic Curve defined by y^2 = x^3 + 2*x + 3 over Finite Field of size 101
#   To:   Elliptic Curve defined by y^2 = x^3 + 38*x + 90 over Finite Field of size 101
#   Via:  (u,r,s,t) = (99, 0, 0, 0)

---

++**Hệ quả:**++ Nếu $E_1 \cong E_2$ trên $K$ thì cả hai sẽ có cùng cấu trúc nhóm, tức là cùng số điểm, cùng kiểu Abelian và đặc biệt là cả hai sẽ có cùng giá trị **J_invariant**.

Ta có thể hiểu **J_invariant** là một bất biến quan trọng, nó giúp ta biết được liệu hai đường cong đang xét có đẳng cấu với nhau không, công thức tính j_invariant của $E$ dạng **ngắn** (weierstrass) là:
$$j(E) = 1728 \cdot \frac{4a^3}{4a^3 + 27b^2}$$

> Với đường cong dạng ngắn, nếu hệ số $a = 0$ thì sẽ cho ra `j_invariant = 0`, còn nếu $b = 0$ thì sẽ cho ra `j_invariant = 1728`.

Đối với đường cong **Montgomery**, ta có công thức tính của j_invariant là:
$$j(E) = \frac{256(a^2-e)^3}{(a^2-4)}$$

Để tính `j_invariant` của hai đường cong, ta sử dụng phương thức `.j_invariant()`.

F = GF(101)
E1 = EllipticCurve(F, [2, 3])
E2 = EllipticCurve(F, [50, 72])

assert E1.is_isomorphic(E2)
print(E1.j_invariant()) #74
print(E2.j_invariant()) #74

> **Fun fact:** Nếu $E_1 \cong E_2$ trên trường $\mathbb{F}_p$ thì bài toán logarit rời rạc (DLP) trên $E_1(\mathbb{F}_p)$ sẽ tương ứng với DLP trên $E_2(\mathbb{F}_p)$, và cả hai sẽ có chung mức độ bảo mật.
>Nhưng Nếu $E_1 \cong E_2$ trên trường mở rộng $\mathbb{F}_{p^k}$ thì khi này độ bảo mật sẽ không còn giống nhau nữa, nên sẽ xảy ra trường hợp ta ánh xạ một đường cong mà khó giải DLP sang một đường cong khác dễ giải DLP hơn.

>Ta có một tính chất khá hay đó là các đường cong **supersingular** trong trường hữu hạn $\mathbb{F}_p$ sẽ không đẳng cấu với nhau, nhưng chúng sẽ đẳng cấu với nhau trên trường mở rộng $\mathbb{F}_{p^k}$ với một giá trị $k$ nào đó.
---

### Twist và Quadratic Twist của một đường cong

**++Định nghĩa++** (Twist): Cho $E(\mathbb{F}_{p})$ là một đường cong Elliptic trên trường hữu hạn $\mathbb{F}_p$. Một **Twist** của $E$ là một đường cong $\widetilde{E}(\mathbb{F}_{p})$ cũng trên $\mathbb{F}_p$ sao cho cả hai **không** đẳng cấu trên $\mathbb{F}_p$ nhưng lại đẳng cấu trên $\mathbb{F}_{p^k}$, tức tồn tại một phép đẳng cấu $\phi:E \rightarrow \widetilde{E}$ sao cho: $$E(\mathbb{F}_{p^k}) \cong \widetilde{E}(\mathbb{F}_{p^k})$$

với $k \geq 2$

Hai Twist $\widetilde{E}_1$ và $\widetilde{E}_2$ của $E$ được gọi là **tương đương** (equivalent) nếu chúng đẳng cấu với nhau trên $\mathbb{F}_p$.

Một Twist $\widetilde{E}$ của $E$ được gọi là Twist **tầm thường** (trivial) nếu $\widetilde{E}_1$ đẳng cấu với $E$ trên $\mathbb{F}_p$.

>Ký hiệu $\text{Twist}(E)$ là tập các **lớp** Twist của $E$. Tức là $\text{Twist}(E)$ sẽ gồm lớp trivial và non-trivial.

++**Công thức**:++
Đặt $\mathbb{F}$ là một trường sao cho $\text{char}(\mathbb{F}) \neq 2$ (đặc cố ≠ 2). Đặt $E: y^2 = x^3 + a_4x + a_6$ là một đường cong trên $\mathbb{F}$ và một số $d \in \mathbb{F}^*$, ta có công thức Twist của $E$ là: $$E^{(d)} : y^2 = d^2.a_4x + d^3.a_6$$

Phép đẳng cấu giữa hai đường cong là:
$$\phi(x, y) = (dx, d^{3/2}y)$$

> **Note:** Nếu $\sqrt{d} \in \mathbb{F}^*$ thì $E^{(d)}$ là một Twist tầm thường.

Trong sagemath, ta có thể xem được `Trivial Twist` và `Non-trivial Twist` của một đường cong bằng phương thức `twists()`. Ở đây nó chỉ lấy đại diện một curve trong từng class chứ không liệt kê hết vì các curve trong cùng class đều đẳng cấu với nhau hết.

F = GF(101)
E1 = EllipticCurve(F, [2, 3])
for i in E1.twists():
    print(i)
# Elliptic Curve defined by y^2 = x^3 + 2*x + 3 over Finite Field of size 101
# Elliptic Curve defined by y^2 = x^3 + 44*x + 36 over Finite Field of size 101

**++Định nghĩa++** (Quadratic Twist): Đây là một trường hợp của Twist khi mà $E$ và $E^{(d)}$ không đẳng cấu trên $\mathbb{F}_p$ nhưng lại đẳng cấu trên $\mathbb{F}_{p^2}$, với điều kiện $\sqrt{d} \notin \mathbb{F}^*_p$.

Để xây dựng một **quadratic twist** trong sagemath, ta sử dụng phương thức `.quadratic_twist(d)` với `d` là một số không có căn bậc hai trong không gian đó.

F = GF(101)
d = F(2)
a, b = 2, 3

assert not is_square(d)

E = EllipticCurve(F, [a, b])
Ed = E.quadratic_twist(d)

# cả hai sẽ không đẳng cấu trên Fp
print(E.is_isomorphic(Ed)) # False

# nhưng sẽ đẳng cấu trên Fp^2
F2 = GF((101, 2), "k")
E = E.change_ring(F2)
Ed = Ed.change_ring(F2)
print(E.is_isomorphic(Ed)) #True

Ta có một số tính chất như sau:

- Nếu $E:y^2 = x^3+a_4x+a_6$ trên $\mathbb{F}_q$ có order là $q+1-t$ thì quadratic twist $E^{(d)}$ trên $\mathbb{F}_q$ có order là $q+1+t$.

- Nếu $d_1$ và $d_2$ là hai số `non-square` trên $\mathbb{F}_p$ thì $E^{(d_1)} \cong E^{(d_2)}$ trên $\mathbb{F}_p$.

- Cho $E$ là một đường cong trên trường $\mathbb{F}_p$ với $\text{char}(\mathbb{F}) \neq2,3$ và $j(E) \neq0,1728$ thì $\#\text{Twist}(E)$ chỉ là $2$ mà thôi, bao gồm một class trivial và một class quadratic twist.

- Một đường cong có $j(E)=1728$ sẽ có số lượng Twist là $2$ khi nằm trên $\mathbb{F}_{p}$, nhưng khi nó nằm trên $\mathbb{F}_{p^2}$ thì $\#\text{Twist}(E)$ sẽ là $4$.

    F = GF(101)
    E1 = EllipticCurve(F, [1, 0])
    E1 = E1.change_ring(GF((101, 2), "k"))
    print(len(E1.twists())) #4

- Ngược lại nếu một đường cong $E$ nằm trên $\mathbb{F}_{p^2}$ có $j(E)=0$ thì $\#\text{Twist}(E)=6$.

    F = GF(101)
    E1 = EllipticCurve(F, [0, 100])
    E1 = E1.change_ring(GF((101, 2), "k"))

    print(E1.j_invariant()) #0
    print(len(E1.twists())) #6

---

## Isogeny và tính chất
Giờ ta đến với món chính của phần này, hiểu rõ được định nghĩa của Isogeny sẽ giúp ta học các phần sau dễ dàng hơn. Nếu hiểu được những gì mình nói ở trước thì phần này chắc cũng không khó hiểu lắm đâu.
### Isogeny
++**Định nghĩa**++ (Isogeny): Cho hai đường cong Elliptic $E_1$ và $E_2$ định nghĩa trên trường hữu hạn $\mathbb{F}$, một Isogeny $\phi:E_1\rightarrow E_2$ là một **ánh xạ** từ $E_1$ sang $E_2$ thỏa mãn các điều kiện sau:
- $\phi$ là một phép đồng cấu (**homomorphism**), tức nó bảo toàn cấu trúc nhóm của $E_1$ bên $E_2$, và đảm bảo tính chất:
$$\phi(P+Q) = \phi(P) + \phi(Q)$$

$$\phi(\mathcal{O}_{E_1}) = \mathcal{O}_{E_2}$$

- $\phi$ là một ánh xạ hữu tỉ, tức nó sẽ có dạng:
$$\phi(x,y) = (f(x), \hspace{3mm} y.g(x))$$

Trong đó $f(x) = \frac{P(x)}{Q(x)}$ và $g(x) = \frac{R(x)}{S(x)}$ với $P,Q,R,S$ là các đa thức và $P$ không chia hết cho $Q; R$ không chia hết cho $S$.

> Nếu tồn tại một Isogeny giữa hai đường cong như vậy, thì ta gọi hai đường cong đó **isogenous** với nhau.

++**Ví Dụ**++: Cho hai đường cong $E_1:y^2=x^3+2x+3$ và $E_2: y^2 = x^3 + 78x+38$ định nghĩa trên $\mathbb{F}_{101}$ thì Isogeny $\phi:E_1\rightarrow E_2$ là:
$$\phi(x,y)= \left (\frac{(x^2 + x + 5)}{(x + 1)}, y\cdot \frac{(x^2 + 2x - 4)}{(x^2 + 2x + 1)}\right)$$

> Không có cách nào để từ hai đường cong $E_1$ và $E_2$ mà ta có thể tính được Isogeny giữa chúng đâu, đó là lý do mà bài toàn tìm Isogeny là vô cùng khó kể cả đối với máy tính lượng tử, ở ví dụ trên thì Isogeny đó được mình xây dựng từ Kernel của $\phi$ và dùng công thức vélu để xây dựng.

++**Định nghĩa**++ (Kernel): Cho hai đường cong $E_1,E_2$ định nghĩa trên trường $\mathbb{F}$ và một Isogeny $\phi: E_1\rightarrow E_2$ thì Kernel của Isogeny $\phi$, ký hiệu $\text{Ker}(\phi)$ là tập các điểm trên $E_1$ mà được ánh xạ sang điểm vô cực ($\mathcal{O}$) trên $E_2$, tức:
$$\text{Ker}(\phi) = \left\{P \in E_1(\mathbb{F})\hspace{2mm} |\hspace{2mm} \phi(P) = \mathcal{O}_{E_2} \right\}
$$

++**Định lý**++: Nếu $H \leq E$ là một nhóm con hữu hạn, thì tồn tại **một** Isogeny thỏa mãn $\phi:E_1\rightarrow E_2$ với $\text{Ker}(\phi) = H$.

Đôi lúc có thể bắt gặp ký hiệu này: $\phi: E_1 \rightarrow E_2 = E_1/\left<H \right>$, nó cho ta biết rằng đường cong $E_2$ isogenous với $E_1$ thông qua Isogeny $\phi$ có Kernel là subgroup $H$.

> Kernel xác định hoàn toàn một Isogeny, tức một Kernel sẽ tạo ra duy nhất một Isogeny mà thôi. Nên nó vô cùng quan trọng và không được tiết lộ.

Vì Ta làm việc với các Isogeny seperable nên bậc của các Isogeny sẽ bằng với số lượng phần tử trong Kernel hay:
$$\text{deg}(\phi) = \#\text{Ker}(\phi)$$

> Khi ai đó dùng ký hiệu $d$-isogeny, tức là họ đang nói đến tập hợp các Isogeny bậc $d$.

---

❓ Ta đã hiểu Kernel là gì, vậy làm sao để xây dựng lại Isogeny từ Kernel?

Ta sẽ sử dụng công thức **Vélu** để làm điều đó, công thức này khá là phức tạp và được tích hợp sẵn nên mình sẽ không trình bày chi tiết mà sẽ demo cho mọi người xem cách để xây dựng một Isogeny trong sagemath luôn.

++**Ví dụ**++: Cho đường cong $E: y^2 = x^3 + 34x+12$ trong không gian $\mathbb{F}_{22739}$ và điểm $P = (12908, 10072)$ có order bằng $5$, yêu cầu sử dụng điểm $P$ đó như điểm sinh của một subgroup $H$, tạo một Isogeny $\phi: E\rightarrow E'=E/H$ và tìm đường cong $E'$ mà $\phi$ đang ánh xạ đến.

Để tạo một Isogeny ta sử dụng phương thức `.isogeny(kernel, algorithm...)` với `kernel` là điểm sinh của một subgroup hoặc là một list các phần tử của subgroup.

Còn với `algorithm`, sẽ có các giá trị là:
- `traditional`: tính toán isogeny với thuật toán vélu truyền thống, độ phức tạp là cực cao nếu Kernel có order lớn.
- `factored`: sử dụng khi order của Kernel là một smooth number, với **SIDH** thì order của kernel thường là $2^m$ hoặc $3^m$ để tăng tốc độ tính toán.
- `velusqrt`: sử dụng khi order của kernel là một số nguyên tố lớn.

Ta thực hiện trong sagemath như sau:

p = 22739
F = GF(p)
E = EllipticCurve(F, [34, 12])

P = E(12908, 10072)
assert P.order() == 5

phi = E.isogeny(P) # vì số nhỏ nên không cần truyền algorith
print(phi)

Được kết quả là một isogeny giữa hai đường cong $E$ và $E'$:

Isogeny of degree 5 from Elliptic Curve defined by y^2 = x^3 + 34*x + 12 over Finite Field of size 22739 to Elliptic Curve defined by y^2 = x^3 + 13012*x + 21022 over Finite Field of size 22739

Để xem công thức của $\phi$, ta sử dụng phương thức `.rational_maps()`:

phi = E.isogeny(P)
print(phi.rational_maps())

# ((x^5 - 344*x^4 + 3970*x^3 - 9300*x^2 + 8615*x - 9553) / (x^4 - 344*x^3 - 2530*x^2 - 1969*x - 10272), 
# (x^6*y - 516*x^5*y + 11342*x^4*y + 10054*x^3*y - 6986*x^2*y + 2653*x*y + 1205*y) / (x^6 - 516*x^5 - 4897*x^4 - 819*x^3 - 333*x^2 + 2165*x - 11202))

Cuối cùng, để in ra đường cong $E'$, ta sử dụng `.codomain()` với $\phi$:

phi = E.isogeny(P)
print(phi.codomain())
# Elliptic Curve defined by y^2 = x^3 + 13012*x + 21022 over Finite Field of size 22739

---

### Dual isogeny
++**Định nghĩa**++: Đặt $\phi: E\rightarrow E'$ là một Isogeny có $\text{deg}(\phi) = d$, tồn tại độc nhất một Isogeny $$\hat{\phi}: E'\rightarrow E$$

sao cho $\hat{\phi}$ thỏa mãn:
$$\hat{\phi} \circ \phi(Q) = \hat{\phi}(\phi(Q)) = Q\times d$$

với một điểm $Q \in E$ bất kỳ.
> Có thể tưởng tượng dual Isogeny giống như phép nghịch đảo của Isogeny vậy, chỉ khác là phải nhân thêm degree của Isogeny vào kết quả nữa.

++**Tính chất**++:
- $\text{deg}(\hat{\phi})=\text{deg}(\phi)=d$.
- $\hat{\hat{\phi}}=\phi$.
- $\widehat{\phi \circ \psi} = \hat{\phi} \circ \hat{\psi}$

Trong sagemath, ta có thể sử dụng phương thức `.dual()` để tìm dual isogeny của một isogeny:

p = 22739
F = GF(p)
E = EllipticCurve(F, [34, 12])

P = E(12908, 10072)
assert P.order() == 5 #degree của isogeny là 5

phi = E.isogeny(P)
phi_hat = phi.dual() # sử dụng .dual() để tính dual isogeny

Q = E.random_element()
print(phi_hat(phi(Q)) == Q * 5) # True

---

## Weil Pairing
**++Định nghĩa++**: Cho một đường cong $E/k$ trên trường $k$ và một số nguyên dương $m$ nguyên tố với đặc số của $k$, ta ký hiệu $\mu_n \subset \overline{k}$ là một nhóm con căn bậc $m$ (m-th roots of unity) của trường $k$, thì **Weil pairing** là một ánh xạ song tuyến tính:
$$e_m: E[m] \times E[m] \rightarrow \mu_m$$

thỏa mãn các tính chất sau:
**++Tính chất++**:
- $e(aP, Q) = e(P, aQ) = e(P, Q)^a$
- $e(aP, bQ) = e(bP, aQ) = e(P, Q)^{a.b}$
- $e(P + P', Q) = e(P, Q) + e(P', Q)$
- $e(P, Q+Q') = e(P, Q) + e(P, Q')$

- $e(P, P) = 1$

Weil Pairing cũng có quan hệ mật thiết với Isogeny qua định lý sau:
**++Định lý++**: Cho $E, E'$ là hai đường cong Elliptic, đặt $\phi:E\rightarrow E'$ là một Isogeny từ $E\rightarrow E'$ và $\hat{\phi}: E'\rightarrow E$ là dual Isogeny của $\phi$, cho $m$ là một số nguyên dương và hai điểm $P \in E[m], Q \in E'[m]$, ta có tính chất:
$$e'_m(\phi(P), Q) = e_m(P, \hat{\phi}(Q))$$

Từ đó ta có hệ quả sau:

**++Hệ quả++**: Với $\phi:E\rightarrow E'$ là một Isogeny bậc $d$, ta có:
$$e'_m(\phi(P), \phi(Q)) = e_m(P, Q)^d$$

Trong sagemath, để tính Weil pairing giữa hai điểm $P, Q$ bậc $m$, ta sử dụng phương thức `.weil_paring()` như sau:

F = GF((101, 2), "i")
E = EllipticCurve(F, [2, 3])
P, Q = E.gens()
assert P.order() == Q.order()
m = P.order()
print(P.weil_pairing(Q, m))
# 47*i + 58

> **Weil pairing** rất quan trọng đối với Isogeny nên đây là phần không thể bỏ qua được
---

# SIDH
SIDH (Supersingular Isogeny Diffie–Hellman) là một giao thức trao đổi khóa công khai dựa trên cấu trúc toán học của các đường cong elliptic supersingular. Thay vì dựa vào phép lũy thừa modulo như trong Diffie–Hellman cổ điển, SIDH tận dụng các phép ánh xạ gọi là isogeny giữa các đường cong để thiết lập khóa chung. Giao thức hoạt động trên trường mở rộng $\mathbb{F}_{p^2}$ và mức độ bảo mật dựa trên độ khó của bài toán tìm một Isogeny giữa hai đường cong supersingular với nhau, điều này mang lại tính bảo mật cao trước cả máy tính lượng tử. Cao siêu là vậy nhưng giao thức này được cho là không an toàn và có thể bị tấn công bằng rất nhiều kiểu tấn công khác nhau, ở phần này chúng ta sẽ nghiên cứu về giao thức SIDH cũng như một vài cách tấn công đơn giản.

## Thuật toán

**++Ý tưởng++**: Khi chỉ biết hai đường cong $E$ và $E'$ thì việc tìm ra Isogeny giữa hai đường cong là vô cùng khó, ngay cả với máy tính lượng tử.

++**Giá trị khởi đầu**++ (Public): Giả sử Alice và Bob đang cố gắng trao đổi khóa bí mật bằng thuật toán SIDH, đầu tiên họ phải thống nhất với nhau các giá trị sau.
- Modulus là số nguyên tố $p = 2^m \times 3^n-1$.

- Đường cong supersingular $E/\mathbb{F}_{p^2}$ với $\text{Ord}(E) = (p+1)^2$.
- Alice chọn cho mình hai giá trị $(P,Q)$ sao cho $(P, Q)$ là điểm sinh của torsion $E[2^n]$ (có thể hiểu torsion $E[2^n]$ là tập hợp các điểm có order là $2^n$ trên đường cong supersingular).
- Bob cũng chọn cho mình hai điểm $(R,S)$ là điểm sinh của torsion $E[3^n]$.

**++Trao đổi khóa++**: Ở bước này, chỉ có những thứ được gửi đi là công khai, còn lại đều là bí mật:
- Alice chọn cho mình một giá trị bí mật $k_A \in (0, 2^m-1)$.
- Bob cũng chọn số bí mật $k_B \in (0, 3^n-1)$.
- Sau đó Alice tự tính cho mình một Isogeny $\phi_A:E\rightarrow E/A$ với kernel $A$ được tính theo công thức:
$$A = P + k_A.Q$$

- Bob cũng tính Isogeny $\phi_B:E\rightarrow E/B$ với công thức của kernel $B$ là:
$$B = R + k_B.S$$

- Bắt đầu bước trao đổi khóa, Alice sẽ gửi cho Bob những giá trị công khai là $E/A$ và cặp điểm sinh $(P, Q)$.
- Bob làm tương tự, anh gửi cho Alice $E/B$ và $(R, S)$.

- Sau khi có $E/B$ và $(R, S)$, Alice sử dụng $\phi_A$ của mình để tính $\phi_A(R), \phi_A(S)$.
- Bob có $E/A$ và cặp điểm sinh $(P, Q)$ nên cũng tính được $\phi_B(P), \phi_B(Q)$.

- Sau đó cả hai gửi ảnh của điểm sinh cho đối phương, tức Alice sẽ gửi $\phi_A(R), \phi_A(S)$, còn Bob sẽ gửi cho Alice $\phi_B(P), \phi_B(Q)$.

> Từ giờ cả hai sẽ không gửi gì cho nhau nữa mà sẽ tiến hành tính khoá chung.

- Alice tiến hành tính Kernel $A'$ bằng công thức:
$$A' = \phi_B(P) + k_A.\phi_B(Q)$$

sau đó dùng $A'$ tạo một Isogeny $\phi_{AB}: E_B\rightarrow E_{AB} = (E/B)/A'$.

- Bob cũng tiến hành tính Kernel $B'$ như sau:
$$B' = \phi_A(R) + k_B.\phi_A(S)$$

Từ $B'$ tính được Isogeny $\phi_{BA}: E_A \rightarrow E_{BA} = (E/A)/B'$.

- Khi này đường cong $E_{AB}$ sẽ đẳng cấu với đường cong $E_{BA}$ nên chúng sẽ có chung $j(E_{AB})$, Alice và Bob tiến hành băm $j(E_{AB})$ để làm khóa chung.

> Vậy là thành công trao đổi khóa chung là $j(E_{AB})$ rồi 😉

## Minh họa
Mình sẽ minh họa cách trao đổi khóa chung giữa Alice và Bob bằng giao thức **SIDH** trong sagemath với các giá trị khởi đầu sau:
- Đường cong Supersingular $E_0/\mathbb{F}_{p^2}: y^2 = x^3+x$ với mô đun $i^2+1=0$.
- Modulus là số nguyên tố $p = 2^{110}*3^{67} - 1$.

Đầu tiên ta cần khởi tạo đường cong $E_0$, cặp $(P,Q)$ cho Alice và $(R, S)$ cho Bob như sau:

ea, eb = 110, 67
p = 2**ea*3**eb - 1
F = GF(p**2, modulus=[1,0,1], name = "i")
i = F.gen()
E0 = EllipticCurve(F, [1,0])

# Torsion base points
G1, G2 = E0.gens()
P, Q = G1 * 3^eb, G2 * 3^eb
R, S = G1 * 2^ea, G1 * 2^ea

assert P.order() == Q.order() == 2^ea
assert R.order() == S.order() == 3^eb

Khởi tạo hai khóa bí mật $k_A, k_B$ và tính Isogeny $\phi_A$ và $\phi_B$ như sau:

sA = randint(0, 2^ea-1)
sB = randint(0, 3^eb-1)

def gen_phi(E, P, Q, s): 
    K = P + s*Q
    phi = E.isogeny(K, algorithm = "factored")
    codomain = phi.codomain()
    return phi, codomain

phiA, EA = gen_phi(E0, P, Q, sA)
phiB, EB = gen_phi(E0, R, S, sB)

Ta tiến hành tính ảnh của $(P, Q)$ qua $\phi_B$ và ảnh của $(R, S)$ qua $\phi_A$ như sau:

def evaluate(phi, P, Q):
    return phi(P), phi(Q)

imgP2, impQ2 = evaluate(phiB, P, Q)
imgP3, impQ3 = evaluate(phiA, R, S)

Có $(\phi_A(R), \phi_A(S))$ và $(\phi_B(P), \phi_B(Q))$ ta tiến hành tính khóa chung thôi:

def gen_shared_secret(E, imgP, imgQ, s):
    Ksa = imgP + s*imgQ
    phi = E.isogeny(Ksa, algorithm = "factored")
    Esa = phi.codomain()
    return Esa.j_invariant()

skey_Alice =  gen_shared_secret(EB, imgP2, impQ2, sA)
skey_Bob =  gen_shared_secret(EA, imgP3, impQ3, sB)

Kiểm tra kết quả:

print(skey_Alice == skey_Bob)
# True

:::spoiler Script

# Public parameter
ea, eb = 110, 67
p = 2**ea*3**eb - 1
F = GF(p**2, modulus=[1,0,1], name = "i")
i = F.gen()
E0 = EllipticCurve(F, [1,0])

# Torsion base points
G1, G2 = E0.gens()
P, Q = G1 * 3^eb, G2 * 3^eb
R, S = G1 * 2^ea, G1 * 2^ea

assert P.order() == Q.order() == 2^ea
assert R.order() == S.order() == 3^eb

# Secret Keys
sA = randint(0, 2^ea-1)
sB = randint(0, 3^eb-1)

def gen_phi(E, P, Q, s): 
    K = P + s*Q
    phi = E.isogeny(K, algorithm = "factored")
    codomain = phi.codomain()
    return phi, codomain

def evaluate(phi, P, Q):
    return phi(P), phi(Q)

def gen_shared_secret(E, imgP, imgQ, s):
    Ksa = imgP + s*imgQ
    phi = E.isogeny(Ksa, algorithm = "factored")
    Esa = phi.codomain()
    return Esa.j_invariant()

phiA, EA = gen_phi(E0, P, Q, sA)
phiB, EB = gen_phi(E0, R, S, sB)

imgP2, impQ2 = evaluate(phiB, P, Q)
imgP3, impQ3 = evaluate(phiA, R, S)

skey_Alice =  gen_shared_secret(EB, imgP2, impQ2, sA)
skey_Bob =  gen_shared_secret(EA, imgP3, impQ3, sB)

print(skey_Alice == skey_Bob)
# True

:::

## SIDH Attack
Có rất nhiều cách để tấn công SIDH từ dễ đến khó, điều đó khiến cho **SIDH** vừa phức tạp để thực hiện còn chứa nhiều lỗ hổng, khiến nó không còn đáng tin cậy nữa, sau đây chúng ta sẽ tìm hiểu cơ bản một số kiểu tấn công đối với SIDH, bao gồm **meet-in-the-middle attack, Castryck-Decru attack** và **keys reused attack**.
### Meet-in-the-middle

Đây là kiểu tấn công có thể tính được Isogeny $\phi:E\rightarrow E$ bậc $2^n$ từ đường cong $E$ đến $E'$ bằng cách liệt kê toàn bộ các Isogeny bậc $2^{n/2}$ của $E$ và toàn bộ Isogeny bậc $2^{n/2}$ của $E'$ và kiểm tra xem Isogeny nào là giao của hai List trên.

Điều đó giúp ta thay vì brute force $2^n$ Isogeny với độ phức tạp $O(2^n)$ thì giờ ta chỉ cần brute force $2. 2^{n/2}$ Isogeny và với độ phức tạp $O(2^{n/2})$ mà thôi.

Nhưng vì độ phức tạp là $O(2^{n/2})$ nên nó không thể áp dụng đối với các Isogeny có degree lớn được và hoàn toàn vô dụng với SIDH sử dụng tham số chuẩn.

> Có thể tham khảo bài giảng [**này**](https://affine.group/slides/2022_SIKE_MitM.pdf) và Link [**Github**](https://github.com/LearningToSQI/SQISign-SageMath/blob/main/mitm.py) này để hiểu rõ và mô phỏng lại mitm attack nhé, muốn thực hành thì có thể làm Challenge **Meet me in the Claw** trong mục Isogeny Challenges (Cryptohack).

### Keys reused
❓Nếu trong quá trình trao đổi khóa chung, Alice sử dụng lại khóa bí mật $k_A$ nhiều lần thì có sao không?

Điều này được chứng minh là vô cùng nguy hiểm nếu như Bob của chúng ta là người xấu vì hắn có thể gửi các khóa công khai nhìn có vẻ bình thường nhưng lại vô cùng nguy hiểm cho Alice nhằm khôi phục khóa bí mật $k_A$, ta có thể chứng minh như [**sau**](https://eprint.iacr.org/2016/859.pdf).

Đặt $(P,Q)$ của Alice là cặp điểm sinh của $E[2^n]$ và $(R,S)$ của Bob là của $E[3^m]$.

Khóa bí mật $k_A$ dưới dạng nhị phân là:
$$k_A = \alpha_0 + 2^1\alpha_1 + 2^2\alpha_2 + \ldots + 2^{n-1}\alpha_{n-1}.$$

Theo như giao thức SIDH đúng, trong quá trình trao đổi khóa, Bob sẽ gửi cho Alice giá trị của $P'=\phi_B(P)$ và $Q'=\phi_B(Q)$ để cô tiến hành tính Kernel $A' = \phi_B(P) + k_A.\phi_B(Q)$ và cô có thể giải mã tin nhắn một cách bình thường.

Nhưng bây giờ trong vai Bob độc ác ta sẽ tìm cách khôi phục lại $k_A$. Đầu tiên ta đặt: $$k_A = K_i + 2^i\alpha_i + 2^{i+1}\alpha'$$

- Với $K_i$ là các bit đã biết của $k_A$, nếu chưa biết thì đặt $K_i=0$.
- $\alpha_i$ là bit ta đang cần khôi phục.
- $\alpha'$ là các bit cao hơn.

Đặt $P'=\phi_B(P)$ và $Q'=\phi_B(Q)$, ta sẽ gửi cho Alice:
$$
\left\{\begin{matrix}
P'' = P' - (2^{n-i-1}K_i).Q' \\
Q''=(1 + 2^{n-i-1}).Q'
\end{matrix}\right.
$$

Khi này Alice sẽ tính Kernel $A'$ như sau:
$$A' = P'' + k_A.Q''$$

$$\Leftrightarrow A' = P' - (2^{n-i-1}K_i).Q' + k_A.(1 + 2^{n-i-1}).Q'$$

$$\Leftrightarrow A'= P' - (2^{n-i-1}K_i).Q' + k_A.Q' + k_A.2^{n-i-1}.Q'$$

$$\Leftrightarrow A' = P' + (k_A - K_i)2^{n-i-1}.Q' + k_A.Q' \hspace{5mm} (*)$$

Thay $k_A = K_i + 2^i\alpha_i + 2^{i+1}\alpha'$ vào $(*)$ ta được:
$$A' = P' + (2^i.a_i + 2^{i+1}a').2^{n-i-1}.Q' + k_A.Q'$$

$$\Leftrightarrow A' = P' + 2^{n-1}.a_i.Q' + 2^n.a'.Q' + k_A.Q'
$$

Vì $Q' \in E[2^n]$ nên $2^n.a'.Q' = \mathcal{O}$, phương trình trên trở thành:
$$A' = P' + 2^{n-1}.a_i.Q' + k_A.Q' \hspace{5mm} (**)$$

Từ giờ sẽ xảy ra hai trường hợp:
++**TH1**++: Nếu $a_i$ là bit $0$, $(**)$ trở thành:
$$A' = P' + k_A.Q'$$

Khi này $A'$ là Kernel chính xác và Alice có thể dùng nó để giải mã ciphertext được.

++**TH2**++: Nếu $a_i$ là bit $1$, thì $(**)$ vẫn giữ nguyên như cũ.
Khi này $A'$ không được tính đúng theo công thức nên quá trình trao đổi khóa thất bại, Alice sẽ trả về thông báo giải mã thất bại.

> Vậy nhờ vào từng thông báo mà Alice trả lời lại, ta có thể tính được từng bit $\alpha_i$ của $k_A$, gửi $n$ lần $P'',Q''$ là ta có thể khôi phục được $k_A$ rồi.

### Castryck-Decru attack
Đây là kiểu tấn công đã khiến cho SIDH bị loại khỏi ứng viên cho NIST post-quantum finalist. Nó có thể tấn công SIDH phiên bản tiêu chuẩn mà không cần nhờ đến bất kì lỗi nào. Chỉ cần máy tính xách tay, trong vòng 1 tiếng nó đã phá hoàn toàn scheme SIDH với mức bảo mật 128-bit.

Có thể tham khảo link [**Github**](https://github.com/GiacomoPope/Castryck-Decru-SageMath/tree/main) này để biết cách thực hiện Castryck-Decru attack. Muốn thực hành thì có thể làm thử Challenge **Breaking SIDH** (Cryptohack).

# CSIDH

CSIDH (Commutative Supersingular Isogeny Diffie–Hellman) là một biến thể của SIDH được thiết kế để đơn giản hóa và cải thiện hiệu năng. Thay vì trao đổi ảnh của các điểm sinh qua Isogeny như SIDH, CSIDH dựa vào một nhóm isogeny có tính giao hoán và chỉ làm việc trên trường $\mathbb{F}_p$ thay vì trường mở rộng, giúp tiết kiệm tài nguyên tính toán và bộ nhớ. Trong CSIDH, các bên trao đổi khóa bằng cách áp dụng một chuỗi isogeny bí mật lên một đường cong ban đầu. Do tính chất giao hoán, cả hai bên đều đến được cùng một kết quả và lấy được khóa chung từ đó. Nhờ sự tối ưu về hiệu năng và tính đơn giản, CSIDH được xem là ứng viên tiềm năng cho mật mã hậu lượng tử.

## Thuật toán

++**Ý tưởng**++:
Bởi vì SIDH bị tấn công bằng Castryck-Decru attack, nên khi thiết kế hệ mã này, người ta đã cố gắng sao cho không gửi bất kỳ điểm ảnh nào như SIDH mà sẽ cố gắng sử dụng thật **nhiều lần** Isogeny lên đường con ban đầu để đến được một đường cong khác, sao cho Attacker dù có biết đường cong đầu và cuối cũng không biết được nó đã đi qua bao nhiêu Isogeny. Có thể hiểu như hình bên dưới, từ $E$ và $a*E$, Attacker không thể tìm ra $a$ được.

Trước khi đi vào CSIDH, ta có một tính chất quan trọng sau của Isogeny:
Cho $\phi:E\rightarrow E'$ là một Isogeny bậc $l$ từ $E\rightarrow E'$, nếu từ $E'$ ta áp dụng thêm $e$ lần $\phi$ nữa thì nó sẽ quay trở về đường cong $E$ ban đầu, tức mỗi $1$ lần áp dụng $\phi$, ta sẽ di chuyển ngược chiều kim đồng hồ một lần, có thể biểu diễn bằng hình này:

> Isogeny $\phi$ sẽ là các cạnh màu xanh nước biển.

Và nếu tốn tại thêm các Isogeny $\phi', \phi''$ thì chúng vẫn có tính chất tương tự như trên.

> Các cạnh màu xanh là Isogeny $\phi'$

> Các cạnh màu đỏ là Isogeny $\phi''$

Và khi kết hợp các Đồ thị Isogeny trên ta sẽ có được đồ thị hoàn chỉnh là:

> Tóm lại ta có thể xem các Isogeny $\phi, \phi', \phi''$ như các bước đi, ta có thể đi ngược chiều hoặc cùng chiều kim đồng hồ bao nhiêu tùy thích và độ khó của CSIDH nằm ở chỗ, nếu biết điểm đầu và điểm cuối, ta không biết được nó đã sử dụng bao nhiêu bước đi và đi mỗi bước như thế nào.

> Giờ ta sẽ bắt đầu với giao thức **CSIDH**

++**Giá trị khởi đầu**++ (Public): Đầu tiên Alice và Bob cần thống nhất các giá trị sau:
- Chọn một List các số nguyên tố lẻ $l = [l_0,l_1,l_2,...,l_n]$.
- Tạo Modulus là số nguyên tố $p = 4\cdot l_0\cdot l_1\cdot l_2\cdot ...\cdot l_n - 1$.
- Đường cong supersingular $E:y^2=x^3+x$ với $\text{Ord}(E) = p+1$.
- Khi này trên đường cong sẽ tồn tại các Isogeny bậc $l_0,l_1,l_2,...,l_n$.

++**Trao đổi khóa**++: Đầu tiên Alice và Bob chọn cho mình hai vector bí mật: $e_a = [a_0, a_1, a_2,...,a_n]$ và $e_b = [b_0,b_1,b_2,...,b_n]$.

Ta cần đảm bảo rằng $\text{Len}(l) =\text{Len}(a)=\text{Len}(b)$

Ta đặt $a$ là List các Isogeny dạng $l^{e_a}$ và $b$ là các Isogeny dạng $l^{e_b}$:
$$a = [l_0^{a_0}, l_1^{a_1},l_2^{a_2},...,l_n^{a_n}]$$

$$b = [l_0^{b_0}, l_1^{b_1},l_2^{b_2},...,l_n^{b_n}]$$

Từ đường cong $E$, Alice sẽ áp dụng các Isogeny trong $a$ và được đường cong mới là $E_A = a*E$. Có thể tưởng tượng như sau: Alice từ điểm ban đầu di chuyển $a_0$ bước dài $l_0$, $a_1$ bước $l_1$,... đến bước cuối là $a_n$ bước $l_n$. Nếu đi nhiều bước thì Attacker không thể nào xác định số bước Alice đã đi.

Khi này Bob cũng làm tương tự, anh áp dụng các Isogeny $l_0^{b_0}, l_1^{b_1}, l_2^{b_2},...,l_n^{b_n}$ với đường cong $E$ và được đường cong mới là $E_B = b*E$.

Bắt đầu quá trình trao đổi khóa:
Đầu tiên Bob gửi cho Alice đường cong $E_B$ còn Alice gửi cho Bob $E_A$.
Có $E_A$, Bob tiến hành tính như trên, anh lấy $E_A*b$ và được đường cong $E_{AB} = E*a*b$.
Alice cũng làm tương tự, cô tính $E_{BA}$ từ đường cong $E_B$ của Bob theo công thức: $E_{BA} = E_B*a = E*a*b$

Khi này $E_{AB} \cong E_{BA}$ nên chúng sẽ có cùng **j_invariant**, Alice và Bob của thể sử dụng $J(E_{AB})$ để làm khóa chung.

> Vậy là thành công trao đổi khóa chung rồi 😉

> **Lưu ý**: Nếu giá trị của $a_i$ trong vector $e_a$ hoặc $b_i$ trong $e_b$ là số âm thì ta phải bước lùi đúng không? Vậy ta bước lùi như thế nào?
Ta sẽ chuyển sang đường cong Twist, đi $a_i$ bước rồi quay trở lại đường cong ban đầu, khi này ta sẽ đi ngược lại $a_i$ bước ở đường cong gốc.
## Minh họa
**++Ví dụ 1++**: Cho đường cong supersingular $E/\mathbb{F}_{419}:y^2=x^3+x$, với $\text{Order}(E) = 4.3.5.7$, Ta sẽ làm việc với các Isogeny bậc $3,5,7$, cho vector bí mật $e_a = [2, 3, 4]$, yêu cầu tìm **j_invariant** của $E$ sau khi áp dụng $2$ lần $3$-Isogeny, $3$ lần $5$-Isogeny và $4$ lần $7$-Isogeny với đường cong $E$.

Ta thực hiện trong sagemath như sau:

p = 419
F = GF(p)
E = EllipticCurve(F, [1, 0])

assert E.is_supersingular()

l = [3,5,7]
e = [2,3,4]

def do_isogenies(E, l, e):
    for _ in range(e):
        # tìm điểm có order l
        while True:
            P = E.random_element()
            if (P * l == E(0, 1, 0)) and (P != E(0, 1, 0)):
                break
        E = E.isogeny(P).codomain()
    return E

for li, ei in zip(l, e):
    E = do_isogenies(E, li, ei)
    
print(E.j_invariant())
# 48

**++Ví dụ 2++**: Sử dụng đường cong cũ, yêu cầu tìm **j_invariant** của $E$ sau khi áp dụng $-1$ lần $3$-Isogeny, tức là đi lùi một lần Isogeny bậc $3$, ta sẽ sử dụng đường cong Twist như sau:

p = 419
Fp = GF(p)
E = EllipticCurve(Fp, (1, 0))
E = E.quadratic_twist()

# tìm điểm K có order là 3
K = E.gen(0)
K *= (p+1)//3

phi = E.isogeny(K)
E = phi.codomain()

E = E.quadratic_twist()
print(E.j_invariant())
# 356

**++Ví dụ 3++**: Giờ ta sẽ đi thực hành cách trao đổi khóa giữa hai bên là Alice và Bob.
Cả hai bắt đầu với các tham số sau:
- List $l$ và modulus $p$ là:

# CSIDH-512 prime
l = [3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 
        71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 
        149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 
        227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293,
        307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 587]
p = 4 * prod(l) - 1

- Đường cong $E_0:y^2=x^3+x$

E0 = EllipticCurve(F, [1, 0])

- Khóa bí mật của Alice là:

e_a = [-1, -2, -3, -3, -2, -3, -3, 0, 2, -1, 2, -1, -2, -3, 1, 2, 1, 2, 0, 0, 1, -1, 0, 2, -1, 0, 0, 0, 1, -1, -3, 1, -1, -3, -3, 2, 2, 1, -1, -1, 1, 0, 1, 1, 1, -2, 2, 2, -2, -2, 0, 0, 2, 0, -1, -3, -2, -2, 0, -1, -3, -1, -2, -3, -2, 2, 1, 1, -2, 0, 1, -1, -3, 2]

- Khóa bí mật của Bob:

e_b = [-1, -1, 0, 1, 2, 0, 2, -1, -3, 1, 0, -2, -2, 2, -1, -2, -3, -3, -3, 2, 2, 2, -2, -1, 1, -2, 0, -3, -1, 1, -1, -1, -3, -1, -2, 1, -1, -2, -3, 1, 0, -1, 1, 2, 2, 0, 0, -1, -2, -2, 1, -1, 1, 1, 1, 1, 0, 0, 0, -3, -2, -1, 2, 0, -3, -2, 1, 1, -2, -1, -1, 2, 0, 1]

- Để tính $e$ lần Isogeny bậc $l$, ta xây dựng một hàm như sau:

def do_isogenies(E, l, e):
    if e >= 0:
        for _ in range(e):
            
            # Tìm điểm G có order là l
            G = ((p + 1) // l) * E.random_point()
            inf = E((0, 1, 0))
            while G == inf: 
                G = ((p + 1) // l) * E.random_point()
            
            # E = E.isogeny(G, algorithm = 'factored').codomain()
            E = isogeny_codomain_from_kernel(E, G) # dùng cái này chạy nhanh hơn
    else:
        e *= -1
        for _ in range(e):
            E = E.quadratic_twist()
            
            # Tìm điểm G có order là l
            G = ((p + 1) // l) * E.random_point()
            inf = E((0, 1, 0))
            while G == inf: 
                G = ((p + 1) // l) * E.random_point()
            
            # E = E.isogeny(G, algorithm = 'factored').codomain()
            E = E = isogeny_codomain_from_kernel(E, G)
            E = E.quadratic_twist()
    
    return E

- Đầu tiên Alice tính giá trị công khai của cô là $E_A$ như sau:

# Alice tính khóa công khai
EA = E0
for li, ei in tqdm(zip(l, e_a)):
    EA = do_isogenies(EA, li, ei)

- Bob cũng làm tương tự, anh tính $E_B$ như sau:

# Bob tính khóa công khai
EB = E0
for li, ei in tqdm(zip(l, e_b)):
    EB = do_isogenies(EB, li, ei)

- Sau đó Alice gửi cho Bob $E_A$, còn Bob gửi cho cô $E_B$. Sau khi có $E_B$, Alice tiến hành tính $E_{AB} = E_B*a$ như sau:

# Alice tính EB*a
EAB = EB
for li, ei in tqdm(zip(l, e_a)):
    EAB = do_isogenies(EAB, li, ei)
ssA = EAB.j_invariant()

- Bob cũng làm tương tự với $E_A$ và anh có $E_{AB}$ là:

# Bob tính EA*b
EAB = EA
for li, ei in tqdm(zip(l, e_b)):
    EAB = do_isogenies(EAB, li, ei)
ssB = EAB.j_invariant()

- Giờ thì đảm bảo cả hai đều đến chung một đường cong và có chung $j(E_{AB})$.

print(ssA == ssB)
# True

:::spoiler Script

# CSIDH-512 prime
l = [3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 
        71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 
        149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 
        227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293,
        307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 587]
p = 4 * prod(l) - 1
F = GF(p)
E0 = EllipticCurve(F, [1, 0])

e_a = [-1, -2, -3, -3, -2, -3, -3, 0, 2, -1, 2, -1, -2, -3, 1, 2, 1, 2, 0, 0, 1, -1, 0, 2, -1, 0, 0, 0, 1, -1, -3, 1, -1, -3, -3, 2, 2, 1, -1, -1, 1, 0, 1, 1, 1, -2, 2, 2, -2, -2, 0, 0, 2, 0, -1, -3, -2, -2, 0, -1, -3, -1, -2, -3, -2, 2, 1, 1, -2, 0, 1, -1, -3, 2]
e_b = [-1, -1, 0, 1, 2, 0, 2, -1, -3, 1, 0, -2, -2, 2, -1, -2, -3, -3, -3, 2, 2, 2, -2, -1, 1, -2, 0, -3, -1, 1, -1, -1, -3, -1, -2, 1, -1, -2, -3, 1, 0, -1, 1, 2, 2, 0, 0, -1, -2, -2, 1, -1, 1, 1, 1, 1, 0, 0, 0, -3, -2, -1, 2, 0, -3, -2, 1, 1, -2, -1, -1, 2, 0, 1]

assert len(l) == len(e_a) == len(e_b)

def do_isogenies(E, l, e):
    if e >= 0:
        for _ in range(e):
            
            # Tìm điểm G có order là l
            G = ((p + 1) // l) * E.random_point()
            inf = E((0, 1, 0))
            while G == inf: 
                G = ((p + 1) // l) * E.random_point()
            
            # E = E.isogeny(G, algorithm = 'factored').codomain()
            E = isogeny_codomain_from_kernel(E, G) # dùng cái này chạy nhanh hơn
    else:
        e *= -1
        for _ in range(e):
            E = E.quadratic_twist()
            
            # Tìm điểm G có order là l
            G = ((p + 1) // l) * E.random_point()
            inf = E((0, 1, 0))
            while G == inf: 
                G = ((p + 1) // l) * E.random_point()
            
            # E = E.isogeny(G, algorithm = 'factored').codomain()
            E = E = isogeny_codomain_from_kernel(E, G)
            E = E.quadratic_twist()
    
    return E

from tqdm import tqdm
# Alice và Bob tính khóa công khai nè
EA = E0
for li, ei in tqdm(zip(l, e_a)):
    EA = do_isogenies(EA, li, ei)
  
EB = E0
for li, ei in tqdm(zip(l, e_b)):
    EB = do_isogenies(EB, li, ei)

# Alice tính EB*a
EAB = EB
for li, ei in tqdm(zip(l, e_a)):
    EAB = do_isogenies(EAB, li, ei)
ssA = EAB.j_invariant()

# Bob tính EA*b
EAB = EA
for li, ei in tqdm(zip(l, e_b)):
    EAB = do_isogenies(EAB, li, ei)
ssB = EAB.j_invariant()

print(ssA == ssB)
#74it [00:02, 35.63it/s]
#74it [00:00, 105.73it/s]
#74it [00:00, 100.90it/s]
#74it [00:00, 104.59it/s]
#True

:::
# Challenge Cryptohack

## Introduction
### Introduction to Isogenies (10 pts)
> Trước khi bắt tay vào làm các Challenge **Isogeny** thì chúng ta cần hoàn thành một số Challenge phần **Elliptic Curve** đã vì Isogeny cần rất nhiều kiến thức Elliptic Curve.

Nếu đã có đủ kiến thức ECC, chúng ta sẽ tiến hành tìm hiểu về Isogeny thông qua các Challenge Cryptohack ở phần này.

Isogeny giữa hai đường cong Elliptic là gì? Đầu tiên, chúng là các ánh xạ hữu tỉ (**rational maps**) giữa hai đường cong Elliptic, chúng không chỉ ánh xạ các điểm từ đường cong này sang đường cong kia mà còn bảo toàn cấu trúc nhóm nữa. Điều đó có nghĩa Isogeny là một phép đồng cấu nhóm (**group homomorphism**). Ta ký hiệu Isogeny là $\phi:E\rightarrow E'$ với đường cong đầu là $E$ (domain) và đường cong được ánh xạ tới là $E'$ (codomain).

Ta sẽ làm việc chủ yếu với các **Seperable Isogeny** - là các Isogeny có $\text{Degree}$ bằng chính xác với order của $\text{Kernel}$ (tập các điểm thuộc đường cong $E$ được ánh xạ sang điểm vô cực $\mathcal{O}$ trên $E'$). Bản chất của Isogeny rất khó hiểu, nhưng có hai thứ ta cần phải làm được. Đầu tiên, phải xây dựng được một Isogeny từ Kernel $H$ với $H$ là một subgroup của $E$. Thứ hai, phải biết cách ánh xạ một điểm từ $E$ sang $E'$. Làm được hai thứ trên là ta có thể hiểu và xây dựng lại được hấu hết các hệ mã dựa trên Isogeny rồi.

Quay trở lại với Challenge, Challenge yêu cầu ta tính kích thước Kernel của một separable isogeny có **degree = 65537**.

Như lý thuyết đã học ở trên thì ta có:
$$\text{Ker}(\phi) = \text{Deg} = 65537$$

## Starter
### The j-invariant (20 pts)
Cũng giống như số học modulo, nơi mà ta làm việc với các số đồng dư modulo $N$, thì ở các hệ mã dựa trên Isogeny, ta sẽ làm việc với các đường cong đẳng cấu với nhau. Giả sử trong một giao thức, ta không có đủ điều kiện để so sánh hai phương trình đường cong liệu chúng có giống nhau hay không, nhưng ta hoàn toàn có thể kiểm tra liệu hai đường cong đó có đẳng cấu không.

Có một cách để xác định liệu hai đường cong có đẳng cấu với nhau không đó là kiểm tra bất biến của chúng. Đối với đường cong Elliptic thì ta sử dụng **j_invariant**, ký hiệu là $j(E)$.

> **Lưu ý:** Nếu hai đường cong đẳng cấu với nhau, chúng sẽ có chung j_invariant, nhưng nếu hai đường cong có chung j_invariant, chúng có thể không đẳng cấu trên trường cơ sở, mà đẳng cấu trên một trường mở rộng nào đó.

Quay lại với Challenge, Challenge yếu cầu ta tính $j(E)$ của đường cong:
$$E: y^2 \equiv x^3 + 145x + 45 \pmod{163}$$

Như đã tìm hiểu ở trước thì ta có công thức của $j(E)$ là:
$$j(E) = 1728\cdot \frac{4a^3}{4a^3+27b^2} = 127$$

Trong sagemath, ta có thể dùng phương thức `j_invariant()`:

E = EllipticCurve(GF(163), [145, 49])
print(E.j_invariant())
# 127

### Where's the Supersingular Curve (25 pts)
Từ phần này trở đi, chúng ta sẽ tập trung vào tính toán Isogeny với các đường cong supersingular hơn. Lý do chúng ta quan tâm đến chúng là vì một Isogeny bậc $l$ của một đường cong supersingluar có thể nối tới $(l+1)$ đường cong supersingular khác, tức đồ thị của ta sẽ vô cùng phức tạp, và nếu cho bạn biết điểm bắt đầu và điểm kết thúc, cũng không thể tìm ra được đường đi.

Ở Challenge này, ta được cho một list các đường cong Montgomery $(y^2=x^3+Ax^2+x)$, làm sao để tìm ra đường cong nào là đường cong supersinglar? **Flag** của ta sẽ là hệ số $A$ của đường cong ta tìm thấy.

Theo như tính chất của đường cong supersingular mà ta đã tìm hiểu trước đây, nếu như modulus $q=p$ thì số điểm hay order của đường cong sẽ là:
$$\#E(\mathbb{F}_p) = p+1$$

Vì vậy ta sẽ tính order của từng đường cong, cái nào có order là $p+1$ thì nhận, lấy hệ số A của nó làm Flag.

from sage.all import *

p = 2**127 - 1
F = GF(p)

# copy từ source code bỏ qua nhé
A_coefficients = [...]

for i, A in enumerate(A_coefficients):
    curve = EllipticCurve(F, [0, A, 0, 1, 0])
    if curve.order() == p + 1:
        print(A_coefficients[i])
        break

Ngoài cách kiểm tra order như trên thì bạn có thể dùng phương thức `.is_supersingular()` để kiểm tra đường cong nào là supersingular cũng được:

from sage.all import *

p = 2**127 - 1
F = GF(p)

# copy từ source code bỏ qua nhé
A_coefficients = [...]
for A in A_coefficients:
    E = EllipticCurve(F, [0, A, 0, 1, 0])
    if E.is_supersingular():
        print(A)
        break

### Image Point Arithmetic (30 pts)
Như đã đề cập ở phần Introduction, một Isogeny không chỉ là một ánh xạ hữu tỉ giữa hai đường cong mà nó còn bảo toàn cấu trúc nhóm của đường cong ban đầu. Nghĩa là nếu ta **không biết** Isogeny $\phi: E\rightarrow E'$, nhưng nếu biết $\phi(P)$ và $\phi(Q)$, ta có thể biết được kết quả của $\phi(P+Q)$.

Quay trở lại với Challenge, Challenge yêu cầu ta tính giá trị $x$ của điểm $\phi(P+Q)$ từ điểm $\phi(P) = (48622,27709), \phi(Q) = (9460,13819)$ và modulus $p = 63079$.

Bởi vì Isogeny là homomorphism nên ta có:
$$\phi(P+Q) = \phi(P) + \phi(Q)$$

Giờ ta chỉ cần thực hiện phép cộng điểm trong Elliptic Curve thôi. Nếu không tìm đường cong của $E'$ thì có thể cộng thủ công.

# sage
p = 63079
F = GF(p)
xP, yP = F(48622), F(27709)
xQ, yQ = F(9460), F(13819)

lamda = (yQ-yP)/(xQ-xP)
x = lamda^2 - xP - xQ
print(x)

### Montgomery Curves (30 pts)
Challenge yêu cầu ta chuyển đổi từ đường cong dạng Weierstrass sang đường cong Montgomery, **Flag** sẽ là hệ số $A$ của đường cong Montgomery. Đường cong Weierstrass Challenge cung cấp là:
$$E:y^2 = x^3 + 312589632 x+654443578 \pmod {1912812599}$$

Theo wiki, ta có thể chuyển đổi từ đường cong Weierstrass → Montgomery bằng công thức [sau](https://en.wikipedia.org/wiki/Montgomery_curve#Equivalence_with_twisted_Edwards_curves):

Thực hiện trong sagemath như sau:

p = 1912812599
A = 312589632
B = 654443578

F = GF(p)
E = EllipticCurve(F, [A, B])
assert E.order() % 4 == 0

# tính alpha
z = PolynomialRing(F, "z").gen()
f = z^3 + A*z + B
alpha = f.roots()[0][0]

tmp = 3*alpha^2 + A
assert is_square(tmp)

s = tmp.sqrt()^(-1)

# tính A
A = 3*alpha*s
print(f"{A = }")

Hoặc có thể dùng phương thức `.montgomery_model()` cho nhanh cũng được.

p = 1912812599
A = 312589632
B = 654443578

F = GF(p)
E = EllipticCurve(F, [A, B])

EM = E.montgomery_model()
print(EM.a2())

### DLOG on the Surface (40 pts)
++**Mô tả:**++ Challenge định nghĩa một đường cong supersingular trên không gian $\mathbb{F}_{p^2}$ với $P,Q$ là hai điểm sinh, sau đó thực hiện tính toán hai điểm sau:
$$
\left\{\begin{matrix}
R = a.P + b.Q \hspace{5mm}(1) \\
S = c.P + d.Q \hspace{5mm}(2)
\end{matrix}\right.
$$

Với $a,b,c,d$ là các số nguyên $\approx127$ bit.
Sau đó tiến hành băm $4$ giá trị $a,b,c,d$ trên để làm khóa cho AES, vậy mục tiêu của ta là tìm lại 4 giá trị đó.

Các thuật toán trao đổi khóa dựa trên Isogeny sử dụng order rất smooth nên bài toán DLP có thể giải rất nhanh, giờ ta phải nghĩ cách để có thể DLP tìm lại các giá trị bí mật trên.

Nhưng $R$ và $S$ có đến hai ẩn, ta chưa thể DLP ngay được, mà phải nghĩ cách triệt tiêu bớt đi một ẩn.

Trick đó là nếu $Q$ là điểm sinh của kernel của Isogeny $\phi_Q$, thì ta có tính chất:
$$\phi_Q(Q) = \mathcal{O}$$

Tiến hành tính $\phi_Q$ từ kernel $Q$, sau đó đưa điểm $R$ qua $\phi_Q$ và ta được ảnh là:
$$\phi_Q(R) = \phi_Q(a.P) + \phi_Q(b.Q)$$

$$\Leftrightarrow \phi_Q(R) = a.\phi_Q(P) + b.\mathcal{O}$$

$$\Rightarrow \phi_Q(R) = a.\phi_Q(P)$$

Đã triệt tiêu được biến $b$ rồi, giờ ta chỉ cần Logarit là có được $a$ rồi.

phiQ = E.isogeny(Q, algorithm = "factored") # lưu ý và phải thêm algorithm = "factored" vào
a = discrete_log(phiQ(R), phiQ(P), operation = "+")
print(f"{a = }")
# a = 8989068744398147088210219398915291813

Làm tương tự với các giá trị $b,c,d$ còn lại, ta có được các phương trình sau:
$$
\left\{\begin{matrix}
\phi_P(R)=b.\phi_P(Q) \\
\phi_Q(S)=c.\phi_Q(P)\\
\phi_P(S)=d.\phi_P(Q)\\
\end{matrix}\right.
$$

Logarit từng phương trình là ta có được $4$ giá trị bí mật rồi, đem băm để làm khóa giải mã AES là có được **Flag**.

## Road to SIDH
### Two Isogenies (30 pts)
> Từ Challenge này trở đi, ta sẽ làm việc trên trường hữu hạn $\mathbb{F}_{p^2}$ với $p \equiv 3 \pmod 4$. Chúng ta sẽ dùng modulus $i^2+1$ nên mọi phần tử trong trường sẽ có dạng $x=a+i.b$.

Ở Challenge này, mục tiêu của ta là tính một Isogeny bậc hai với đường cong $E$ và Kernel $K$ như sau:
$$E:y^2 = x^3+x, \hspace{5mm} K = (i, 0),\hspace{5mm} p = 2^{18}\cdot 3^{13}-1$$

**Flag** của Challenge này sẽ là $j(E')$ với $E'$ là codomian của Isogeny $\phi_2:E\rightarrow E'$.

Mình nghĩ nếu đã quen cách xây dựng trong Isogeny trong sagemath thì bài này không có gì khó, ta làm như sau:

p = 2^18 * 3^13 - 1
F = GF(p**2, names="i", modulus=[1,0,1])
i = F.gen()
E = EllipticCurve(F, [1, 0])
K = E(i, 0)

phi = E.isogeny(K)
E_ = phi.codomain()

print(E_.j_invariant())

### Three Isogenies (35 pts)
Challenge này khá giống Challenge trước, chỉ khác là bây giờ Isogeny của ta là Isogeny bậc $3$, bởi vì order điểm sinh của Kernel là bằng $3$.

Sử dụng các dữ kiện sau:
$$E:y^2 = x^3+x, \hspace{5mm} K = (483728976,174842350631),\hspace{5mm} p = 2^{18}\cdot 3^{13}-1$$

Yêu cầu của Challenge là tính $j(E')$ của $E'$ là codomain của Isogeny $\phi_3:E\rightarrow E'$.

Vẫn thực hiện tương tự Challenge trước:

p = 2^18 * 3^13 - 1
F = GF(p**2, names="i", modulus=[1,0,1])
i = F.gen()
E = EllipticCurve(F, [1, 0])
K = E(483728976,174842350631)

phi = E.isogeny(K)
E_ = phi.codomain()

print(E_.j_invariant())

### Composite Isogenies (60 pts)
Qua hai Challenge trên, ta có thể để ý hai thứ sau. Đầu tiên, thuật toán mà ta sử dụng để tính một Isogeny bậc $n$ có độ phức tạp phụ thuộc vào order của Kernel. Thứ hai đó là tất cả các Isogeny sẽ có bậc là ước của $2^{18}.3^{13}$, tức có order rất smooth.

Bởi vì độ phức tạp của thuật toán Vélu là tuyến tính theo order của Kernel, nên với order có dạng $n = p_0^{e_0} \cdot p_1^{e_1} \cdot ...\cdot p_k^{e_k}$, thay vì dùng vélu để tính thẳng Isogeny bậc $n$ thì chúng ta chia nhỏ order ra và gộp $e_0$ Isogeny bậc $p_0$, $e_1$ Isogeny bậc $p_1$ và cứ gộp đến khi nào hết order $n$ thì thôi. Gộp ở đây nghĩa là phép hợp hàm:
$$\phi_{P_0} \circ... \circ \phi_{P_0} = \phi_{P_0}(\phi_{P_0}(...))$$

Challenge yêu cầu ta tính một Isogeny $\phi$ bậc $3^{13}$ và **Flag** là $j(E')$ với $E'$ là codomain của $\phi$.

Như đã đề cập từ trước thì nếu bậc của Isogeny là smooth number, ta cần phải truyền vào `.isogeny()` tham số `algorithm = factored` nữa, nhanh gấp nhiều lần với `traditional`.

p = 2^18 * 3^13 - 1
F = GF(p**2, names="i", modulus=[1,0,1])
i = F.gen()
E = EllipticCurve(F, [1, 0])

K = E(357834818388*i+53943911829, 46334220304*i+267017462655)
phi = E.isogeny(K, algorithm = "factored")
print(phi.codomain().j_invariant())

### SIDH Key Exchange (80 pts)
Ở Challenge này, ta sẽ tự xây dựng cho mình một thuật toán **SIDH** và dùng khóa chung để decrypt ciphertext.

++**Thuật toán SIDH**++

Giá trị khởi đầu của cả hai là một đường cong $E_0$ và hai tập gồm một cặp điểm sinh, Alice sẽ chọn $(P_2, Q_2)$ và Bob chọn tập $(P_3, Q_3)$:
$$E[2^{e_A}] = (P_2, Q_2), \hspace{3mm} E[3^{e_B}] = (P_3, Q_3)$$

> Đây là giá trị khởi đầu nên nó sẽ được công khai

Quá trình trao đổi khóa diễn ra như sau:
Đầu tiên Alice tính Isogeny $\phi_A:E_0\rightarrow E_A$ từ kernel sinh bằng điểm $K_A = P_2 + s_A.Q_2$ có order là $2^{e_A}$.
Bob cũng làm tương tự, anh tính $\phi_B:E_0\rightarrow E_B$ bằng điểm $K_B = P_3 + s_B.Q_3$ có order là $3^{e_B}$.
> Khóa bí mật của cả hai là $s_A$ và $s_B$.

Sau đó cả hai gửi cho nhau cặp điểm sinh và của mình, tức Bob nhận được cặp $(P_2, Q_2)$ còn Alice thì nhận được $(P_3, Q_3)$ từ Bob.

Alice sau khi nhận được $(P_3, Q_3)$, cô tiến hành tính ảnh của $(P_3, Q_3)$ qua Isogeny $\phi_A$ của cô, được cặp $(\phi_A(P_3), \phi_A(Q_3))$.
Bob cũng làm tương tự với cặp $(P_2, Q_2)$ của Alice và được $(\phi_B(P_2), \phi_B(Q_2))$.

Sau đó cả hai tiến hành gửi đường cong (sinh từ isogeny của mình) và ảnh của điểm sinh đối phương cho nhau.
Tức Alice sẽ gửi cho Bob $E_A$ và $(\phi_A(P_3), \phi_A(Q_3))$.
Còn Bob sẽ gửi cho cô $E_B$ và $(\phi_B(P_2), \phi_B(Q_2))$.

Sau có đủ thông tin, cả hai tiến hành tính khóa chung như sau.
Alice tính Kernel $K_{SA} = \phi_B(P_2) + s_A.\phi_B(Q_2)$ rồi sử dụng nó để tạo nên Isogeny $\phi_{SA}: E_B \rightarrow E_{SA}$.
Bob làm tương tự, anh tính Isogeny $\phi_{SB}: E_A \rightarrow E_{SB}$ từ Kernel $K_{SB} = \phi_A(P_3) + s_B.\phi_A(Q_3)$.

Khóa chung của cả hai sẽ là:
$$\text{shared secret} = j(E_{SA}) = j(E_{SB})$$

> Những giá trị được gửi đi mới được xem là công khai, sẽ có tổng cộng hai lần gửi giá trị công khai.

## Road to CSIDH
### Special Isogenies (30 pts)
++**Mô tả**++: Challenge yêu cầu ta tìm codomain của một Isogeny $\phi: E\rightarrow E'$ bậc $5$ với Kernel là một điểm bậc $5$ bất kỳ, domain của Isogeny là đường cong:
$$E/\mathbb{F}_{419}: y^2 = x^3+x$$

**Flag** sẽ là hệ số $A$ của $E'$ ở dạng Montgomery.

### Prime Power Isogenies (50 pts)
Cho đường cong $E/\mathbb{F}_{419}: y^2 = x^3+x$.
Câu hỏi của Challenge là tìm số lần ($n$) mà một Isogeny bậc $7$ cần lặp lại để từ đường cong trên sau $n$ phép lặp Isogeny bậc $7$ thì trở về chính nó.

### Secret Exponents (60 pts)
Trong giao thức CSIDH thì khóa bí mật của ta sẽ là **list** các số nguyên sao cho len của nó là ước của $(p+1)$. List này đại diện cho các giá trị lũy thừa $[e_1, e_2, ..., e_n]$ dùng để xác định đường đi bí mật (Isogeny) của Alice và Bob.

Challenge yêu cầu ta sử dụng khóa bí mật $[2,3,4]$ và từ đường cong:
$$E_0: y^2 = x^3+x \mod 4129$$

Với order là $3.5.7$ tính codomain của Isogeny có **degree** là $2^3.3^5.4^7$. Flag sẽ là hệ số $A$ của đường cong codomain dạng Montgomery.

### Twisted CSIDH Isogenies (70 pts)
Tưởng tượng giao thức CSIDH giống như một chiếc đồng hồ, điểm bắt đầu của ta nằm ở vị trí 12 giờ, giả sử ta áp dụng **một** lần Isogeny bậc $l$ thì ta sẽ di chuyển ngược chiều kim đồng hồ **một** giờ, thì khi thực hiện Isogeny này thêm $11$ lần nữa (hay một Isogeny bậc $l^{11}$) thì ta sẽ quay trở lại vị trí ban đầu là vị trí 12 giờ.

Vậy nếu ta đang đứng ở vị trí **10** giờ, nhưng muốn quay ngược lại vị trí **11** giờ thì sao? Không thể di chuyển ngược chiều kim đồng hồ thêm **11** lần nữa vì nó sẽ tốn thời gian, vậy thì phải làm sao?

Ta sẽ sử dụng đường cong **Twist**, bằng cách chuyển đường cong $E$ thành $E^t$, sau đó thực hiện Isogeny bậc $l$ trên đường cong đó và sau đó untwist (tức chuyển đường cong $E^t$ thành đường cong $E$) là ta đã di chuyển thuận chiều kim đồng hồ **1** giờ rồi.

Quay trở lại với Challenge, Challenge yêu cầu ta thực hiện một lần Isogeny bậc $3^{-1}$, Flag sẽ là hệ số $A$ của đường cong codomain dưới dạng Montgomery.

### CSIDH Key Exchange (90 pts)

**++Mô tả++**: Ở Challenge này ta sẽ tự tay tạo cho mình một giao thức trao đổi khóa CSIDH, khóa chung sẽ được dùng để giải mã **Flag**.

++**Giao thức CSIDH**++
CSIDH khác với SIDH ở chỗ các supersingular không cần phải làm việc trên trường mở rộng $\mathbb{F}_{p^2}$ mà chỉ cần ở trên trường $\mathbb{F}_{p}$ mà thôi. Modulus của ta có dạng $p \equiv 3 \pmod 4$ và order của $E$ được chọn rất smooth nên ta có thể biểu diễn order $E$ như sau:

$$\text{Order}(E) = 4 \times l_1\times l_2\times...\times l_k$$

Cả hai sẽ bắt đầu với chung đường cong $E_0$, đặt $L$ là list của các giá trị $[l_1, l_2,...,l_k]$. Alice chọn cho mình một vector bí mật $e = [e_1,e_2,...,e_k]$ và Bob chọn cho mình vector bí mật $f = [f_1,f_2,...,f_k]$.

Đầu tiên Alice tính codomain của $(e*E_0)$ tức thực hiện Isogeny bậc $l_1^{e_1}.l_2^{e_2},...,l_k^{e_k}$ trên đường cong $E_0$ để được đường cong mới là $E_A$. Bob cũng làm tương tự bằng cách tính codomain của $(f*E_0)$ được $E_B$.

Bây giờ cả hai trao đổi đường cong cho nhau, Alice sẽ gửi cho Bob $E_A$, còn Bob gửi cho Alice $E_B$.

Alice sau khi có $E_B$, cô sẽ tính $E_{AB} = a*E_B = a*b*E_0$.
Còn Bob khi có $E_A$ sẽ tính $E_{AB} =b*E_A = b*a*E_0$.

Nhờ vào tính chất giao hoán nên khi này cả hai sẽ có chung đường cong $E_{AB}$, giờ thì tính $j(E_{AB})$ để làm khóa chung thôi.
$$\text{shared secret} = j(E_{AB})$$

Ta thực hiện Challenge như sau:

## Isogeny Challenges
### What's My Kernel (70 pts)
**++Mô tả++**: Challenge này thực hiện tính toán khóa công khai của thuật toán **SIDH**, bao gồm:
$$E'=E/R, \hspace{5mm} \phi_R(P_B),\hspace{5mm} \phi_R(Q_B) $$

Ta có $R$ là kernel của $\phi_R$ và được tính theo công thức: $$R = P_A+n.Q_A \hspace{5mm} (*)$$

Với $n$ là giá trị của **Flag**, $(P_A, Q_A)$ là cặp điểm sinh của Alice và $(P_B, Q_B)$ là của Bob.

Nhưng challenge này mắc một lỗi nghiêm trọng, ở đoạn:

# Cofactors
c_a = l_b ^ e_b
c_b = l_b ^ e_b
# Compute generators of E[l_a^e_a] and E[l_b^e_b]
P, Q = E.gens()
P_a, Q_a = c_a * P, c_a * Q
P_b, Q_b = c_a * P, c_a * Q

Ta thấy rằng $(P_A, P_B)$ là giống nhau, $(Q_A, Q_B)$ cũng giống nhau, suy ra ta có:
$$\phi_R(P_B) = \phi_R(P_A), \hspace{5mm} \phi_R(Q_B) = \phi_R(Q_A)$$

Vì $R$ là kernel của $\phi_R$, nên từ $(*)$ ta có được:
$$\phi_R(R) = \phi_R(P_A) + n.\phi_R(Q_A)$$

$$\Leftrightarrow \mathcal{O} - \phi_R(P_A) = n.\phi_R(Q_A)$$

> Vì order của $\phi_R(Q_A)$ rất smooth ($2^{216}$) nên ta có thể dùng `discrete_log` để tìm lại $n$ được và có Flag.

### André Encoding (80 pts)
**++Mô tả++**: Cho $(P,Q)$ là hai điểm sinh cố định cho trước, Challenge tính $52$ cặp giá trị $(\phi_{R_i}(P), \phi_{R_i}(Q))$ với, với Kernel $R_i$ được tính từ công thức:

$$R_i = \left(\frac{p+1}{2^{64}. b_i} \right) \cdot (P+s_i.Q)$$

Trong đó: $b_i$ là $52$ ký tự của Flag, $s_i$ là một số random trong khoảng $(0, 2^{64}. b_i)$, mục tiêu của ta sẽ là tìm lại $52$ giá trị $b_i$.

Challenge này có hai hướng giải, hướng thứ nhất là làm tương tự bài **What's My Kernel**, cách thứ hai là sử dụng **Weil pairing**.

**++Cách 1++**: Đặt $t = \frac{p+1}{2^{64}. b_i}$ Ta biến đổi công thức của $R_i$ như sau:
$$R_i = t_i \cdot (P+s_i.Q)$$

$$\Leftrightarrow \phi_{R_i}(R_i) = t_i \cdot \phi_{R_i}(P+s_i.Q)$$

$$\Leftrightarrow \mathcal{O} = t_i \cdot \phi_{R_i}(P) + s_i.\phi_{R_i}(Q)$$

$$\Leftrightarrow - t_i \cdot \phi_{R_i}(P) = s_i.\phi_{R_i}(Q) \hspace{5mm} (*)$$

Ta sẽ brute force $b$ để thử từng giá trị $t_i$, và nếu ta có thể `discrete_log` được phương trình $(*)$ để có $s_i$ thì ta tìm được giá trị $b$ phù hợp.

**++Cách 2++**: Sử dụng hệ quả của Weil Pairing, ta có:
$$e'_m(\phi_{R_i}(P), \phi_{R_i}(Q)) = e_m(P, Q)^{d_i}$$

Với $d_i = 2^{64}.b_i$ là degree của $\phi_{R_i}$, ta sẽ dùng `.discrete_log()` để có được $d_i$, sau đó lấy $d_i$ chia $2^{64}$ là có $b_i$, làm tương tự như vậy $52$ lần là ta sẽ có được Flag hoàn chỉnh.

### Better than Linear (85 pts)
**++Mô tả++**: Ở những Challenge trước, ta đã quen với việc tính Isogeny có degree là một smooth number, ví dụ $2^m, 3^n$. Nhưng sẽ có đôi lúc ta phải làm việc với những Isogeny có order là một số nguyên tố lớn, ta không thể sử dụng cách chia nhỏ Isogeny ra như trước mà phải sử dụng thuật toán gọi là [Square‑root Vélu](https://doc.sagemath.org/html/en/reference/arithmetic_curves/sage/schemes/elliptic_curves/hom_velusqrt.html), ta có thể sử dụng thuật toán này trong sagemath bằng cách truyền tham số `algorithm = "velusqrt"` vào phương thức `.isogeny()`.

Challenge yêu cầu ta tính **j-invariant** của codomain của đường cong $E$ sau với kernel $K$ và modulus $p$:
$$E/ \mathbb{F}_{p^2}: y^2 = x^3 + x, \hspace{5mm} p=92935740571$$

$$K = (11428792286i+6312697112,78608501229i+30552079595)$$

### Abelian SIDH (90 pts)
**++Mô tả++**: Challenge này giúp ta làm quen với dual isogeny của một isogeny, dual isogeny của isogeny $\phi: E\rightarrow E'$ là một Isogeny $\hat{\phi}: E'\rightarrow E$ sao cho:
$$\hat{\phi} \circ \phi(P) = P \times \text{Deg}(\phi)$$

Ở challenge này, Flag của ta được mã hóa bằng AES với key $(k)$ là:
$$k = \hat{\phi} \circ \phi(G_B) = G_B \times \text{Deg}(\phi) =G_B \times l_a^{e_a} $$

Đã có $G_B$ và $l_a, e_a$, ta hoàn toàn có thể khôi phục được Flag, một điểm cần chú ý là ta cần phải xét hai trường hợp dấu của điểm $G_B$.

<h1 style="text-align:center;">END</h1>

> [time=Tue, Jun 10, 2025 2:14 PM]
:::spoiler
:::