# Một số khái niệm
## The $j$-invariant
Dựa vào $j$-invariant ta có thể dễ dàng xác định được hai đường cong thực sự "giống nhau" trong các hệ tọa độ khác nhau, tức là khi chúng là đẳng cấu **(isomorphic)**
$j$-invariant được tính bằng công thức:
- Đối với các Weierstraß Curves dạng ngắn:
$$j = 1728*\frac{4a^3}{4a^3 + 27b^2}$$
- Các đường cong dạng Montgomery:
$E_a: y^2 = x^3 +ax^2+x$ có $j$-invariant $j(E_a) = \frac{256(a^2-e)^3}{(a^2-4)}$.
Hai đường cong elliptic là đẳng cấu (trong trường hợp đóng đại số) nếu và chỉ nếu chúng có cùng $j$-invariant.
## Supersingularity
Đường cong $E$ được xác định trên trường hữu hạn $\mathbb{F}_q$ với đặc số $p$ là supersingular nếu và chỉ nếu $p$ chia hết $\#E(\mathbb{F}_q) - q - 1$, trong đó:
- $\#E(\mathbb{F}_q)$: Số điểm trên đường cong E trong trường $\mathbb{F}_q$
- $q$: Lũy thừa của số nguyên tố $p$(tức $q = p^k$, $k \ge 1$)
#### Trường hợp đặc biệt khi $q=p$
Khi $p=q$ (với $p \ge 5$), định nghĩa trên trở nên đơn giản nhờ Định lý Hasse:
- Định lý Hasse: $|\#E(\mathbb{F}_p) - p -1| \le 2 \sqrt{p}$
- Với $p \ge 5$, $2\sqrt{p} < p$. Do đó, nếu $p$ chia hết $|\#E(\mathbb{F}_p) - p -1|$, thì duy nhất khả năng là:
$$\#E(\mathbb{F}_p) = p+1$$
$\Rightarrow$ Supersingular curves khi p = q có số điểm chính xác là $p+1$
:::warning
"Supersingular" không liên quan đến singularities (điểm kỳ dị). Tất cả đường cong elliptic đều không kỳ dị (non-singular) theo định nghĩa.
Từ "supersingular" mang nghĩa "rất đặc biệt", ám chỉ tính hiếm và tính chất toán học độc đáo của chúng.
:::
## Isogenies of elliptic curves
### Definition & examples
**Isogeny** là một ánh xạ giữa 2 đường cong elliptic, vừa bảo toàn cấu trúc đại số(dạng phương trình) vừa bảo toàn cấu trúc nhóm(phép cộng điểm). Nó được biểu diễn bằng các hàm hữu tỉ(phân thức đa thức) và không đồng nhất(non-zero).
- Ví dụ: Ánh xạ
$$\phi : (x,y) \longmapsto (\frac{x^3 - 4x^2 + 30x - 12}{(x-2)^2}, y \cdot \frac{x^3 - 6x^2 - 14x + 35}{(x-2)^3})$$
là một isogeny từ đường cong $E: y^2 = x^3 +x$ sang $E': y^2 = x^3-3x + 3$ trên trường $\mathbb{F}_{71}$.
### Công thức tổng quát
Mọi isogeny giữa hai đường cong Weierstrass $E$ và $E'$ đều có dạng:
$$(x, y) \mapsto (f(x, y), g(x, y))$$
trong đó $f, g$ là các trên trường cơ sở $k$.
- Degree: Độ phức tạp đại dố của isogeny, bằng bậc nhỏ nhất của hàm hữu tỉ biểu diễn nó
- Tính nhân bậc: Nếu $\phi$ và $\psi$ là hai isogeny, thì $\text{deg}(\phi \circ \psi) = \text{deg}(\phi) \cdot \text{deg}(\psi)$
### Phân loại isogeny
- Isomorphism (Đẳng cấu): Isogeny bậc 1, tương ứng với phép đổi biến tọa độ đơn giản.
- Endomorphism (Tự đồng cấu): Isogeny từ $E$ đến chính nó (bao gồm phép nhân vô hướng)
- Automorphism (Tự đẳng cấu): Endomorphism khả nghịch, ví dụ: phép đổi dấu $(x, y) \longmapsto (x, -y)$
## Dual Isogeny
- **Định nghĩa:** Mỗi isogeny $\phi: E \to E'$ đều tồn tại một isogeny đối ngẫu duy nhất $\hat{\phi}: E' \to E,$ thỏa mãn:
$$\hat{\phi} \circ \phi = [\text{deg}(\phi)] \text{ và } \phi \circ \hat{\phi} = [\text{deg}(\phi)]$$
trong đó $[\text{deg}(\phi)]$ là phép nhân vô hướng với hệ số $\text{deg}(\phi)$.
- Dual Isogeny đóng vai trò như "nghịch đảo gần đúng" của isogeny, nhưng được điều chỉnh theo bậc của isogeny.
- Quan hệ isogeny trở thành quan hệ tương đương: Nếu $E$ isogeny với $E'$, thì $E'$ cũng isogeny với $E$ qua đối ngẫu.
## Isogeny from Kernel
### Định nghĩa Kernel
- Kernel của isogeny $\phi: E \mapsto E'$ là tập hợp các điểm $P$ trên đường cong $E$ sao cho $\phi(P) = \infty$.
- Kernal là một tập hợp hữu hạn và là một nhóm con của nhóm các điểm trên đường cong elliptic $E$, vì isogeny là một đồng cấu nhóm.
### Ví dụ
Xét isogeny $\phi$ ví dụ:
$$\phi : (x,y) \longmapsto (\frac{x^3 - 4x^2 + 30x - 12}{(x-2)^2}, y \cdot \frac{x^3 - 6x^2 - 14x + 35}{(x-2)^3})$$
Kernel của isogeny này là tập hợp các điểm mà mẫu số bằng 0, tức là $x=2$
$$\text{Kernel} = \{\infty, (2, 9), (2, 62)\}$$
### Ý nghĩa
- Kernel xác định gần như duy nhất một isogeny. Sự khác biệt đến từ các isogeny purely inseparable, vì chúng có kernel tầm thường nhưng không phải đẳng cấu.
- Nếu hai isogeny $\phi : E \to E'$ và $\psi: E \to E''$ có cùng kernel, thì $\psi = \alpha \circ \phi$ với $\alpha$ là một isogeny purely inseparable (thường là một đẳng cấu).
#### Định lý chính
- Định lý: Có một sự tương ứng 1-1 giữa các nhóm con hữu hạn của một đường cong elliptic và các isogeny tách được từ đường cong đó, sai khác một đẳng cấu.
- Isogeny tương ứng với nhóm con $H$ thường được ký hiệu là $\phi_H$ và đường cong đích (codomain) được ký hiệu là $E/H$, tương tự như khái niệm thương trong lý thuyết nhóm.
- Bậc của isogeny $\phi_H$ bằng kích thước của nhóm $H:\text{deg} \phi_H = |H|$
Ví dụ:
Nếu $H$ là một nhóm con hữu hạn của đường cong elliptic $E$, thì tồn tại một isogeny $\phi_H: E \to E/H$ với kernel $H$. Ví dụ:
- Nếu $H$ có 3 điểm bao gồm $\infty$, thì $\text{deg}\phi_H = 3$
- Nếu $H$ có 5 điểm, thì $\text{deg}\phi_H = 5$
## *$l$-torsion*
Cho $E$ là một đường cong elliptic và $l$ là một số nguyên dương. Tập hợp các điểm **$l$-torsion** của $E$, ký hiệu là $E[l]$, là tập hợp các điểm $P$ trên $E$ sao cho:
$$
[l]P = O,
$$
trong đó $[l]P$ là phép nhân điểm $P$ với $l$, và $O$ là điểm vô cực (phần tử trung hòa của nhóm đường cong elliptic).
Nói cách khác, $E[l]$ là **kernel** của ánh xạ nhân với $l$, tức là:
$$
E[l] = \text{ker}([l]).
$$
## **Công thức của Vélu**
Công thức của Vélu cho phép chúng ta xây dựng isogeny $\phi: E \to E'$ từ một kernel $G$ trên đường cong elliptic $E$. Cụ thể, công thức này tính toán tọa độ $x$ và $y$ của các điểm trên đường cong đích $E'$ từ tọa độ $x$ và $y$ của các điểm trên đường cong ban đầu $E$.
#### **Công thức tổng quát**
Giả sử $E$ là một đường cong elliptic và $G$ là một nhóm con hữu hạn của $E$. Công thức của Vélu cho isogeny $\phi: E \to E'$ với kernel $G$ như sau:
1. **Tọa độ $x$**:
$$
\phi(x) = x + \sum_{P \in G \setminus \{O\}} \left( \frac{x(P)}{x - x(P)} - \frac{x(P)}{x(P)} \right),
$$
trong đó:
- $x(P)$ là tọa độ $x$ của điểm $P$ trong kernel $G$.
- $O$ là điểm vô cực.
2. **Tọa độ $y$**:
$$
\phi(y) = y \cdot \prod_{P \in G \setminus \{O\}} \left( 1 - \frac{y(P)}{y} \right),
$$
trong đó:
- $y(P)$ là tọa độ $y$ của điểm $P$ trong kernel $G$.
# SIDH protocol
## The set of supersingular $j$-inavariants
SIDH hoạt động trong phần mở rộng bậc hai của trường nguyên tố lớn $\mathbb{F}_p$ với $p \equiv 3 \pmod 4$, trong đó ta thường chọn cách biểu diễn thuận tiện nhất là $\mathbb{F}_{p^2} = \mathbb{F}_p(i)$ với $i^2 +1 = 0$; khi đó, các phần tử có dạng $u+vi$ với $u, v \in \mathbb{F}_p$.
Trong số $p^2$ phần tử trong $\mathbb{F}_{p^2}$, tập hợp các supersingular $j$-invariants trong $\mathbb{F}_{p^2}$ có kích thuớc $[p/12] + z$, với $z \in \{0, 1, 2\}$. Khi p tăng theo cấp số nhân thì tập này cũng tăng theo.
Để viết ra đầy đủ tập hợp này và để có thể thực hiện minh họa một giao thức SIDH thu nhỏ ta sẽ sử dụng $p=431$
Trong trường hợp này, có $[p/12] + 2 = 37$ supersingular $j$-invariants trong $\mathbb{F}_{p^2}$
Lấy $a_1 = 208i+161$ và $a_2 = 172i + 162$ thì $j(E_{a_1}) = j(E_{a_1}) = 364i +304$, do đó:
$E_{a_1}: y^2 = x^3 + (208i + 161)x^2 + x$ và $E_{a_2}: y^2 = x^3 + (172i + 162)x^2 + x$ isomorphic.
The isomorphisms là:
$\psi: E_{a_1} \rightarrow E_{a_2}, (x, y) \mapsto \left( (66i + 182)x + (300i + 109), (122i + 159)y \right),$
và
$\psi^{-1}: E_{a_2} \rightarrow E_{a_1}, (x, y) \mapsto \left( (156i + 40)x + (304i + 202), (419i + 270)y \right).$
Gọi $O_1$ và $O_2$ là phần tử đơn vị(tức là điểm ở vô cùng) trên $E_{a_1}$ và $E_{a_2}$. Lưu ý rằng $\psi(O_1) = O_2$ và $\psi^{-1} (O_2) = O_1$ vì các ánh xạ trên không có mẫu số, chúng được xác định rõ cho tất cả các điểm (affine) khác trong $E_{a_1}(\mathbb{F}_{p^2})$ và $E_{a_2}(\mathbb{F}_{p^2})$. Tổ hợp của 2 ánh xạ này là ánh xạ đơn vị trên $E_{a_1}$ và $E_{a_2}$.
SIDH in a Nutshell
## Isogenies
Lý do chính khiến các đường cong elliptic dạng Montgomery thường được ưa chuộng trong cả ECC truyền thống và mật mã dựa trên isogeny là chúng tạo điều kiện cho phép tính toán rất hiệu quả chỉ với tọa độ $x$, tức là các ánh xạ mà hoàn toàn bỏ qua tọa độ $y$. Đơn giản viết các ánh xạ dưới dạng:
$$x \mapsto f(x)$$
ánh xạ đầy đủ sẽ có dạng như sau:
$$(x, y) \mapsto (f(x), c \cdot yf'(x))$$
Xét ánh xạ nhân với 2 (hoặc ánh xạ gấp đôi điểm) trên một đường cong cố định $E_a: y^2 = x^3 + ax^2+x$, được viết là:
$$[2]: E_a \rightarrow E_a, \quad x \mapsto \frac{(x^2 - 1)^2}{4x(x^2 + ax + 1)}\quad(1)$$
Lưu ý rằng: Ánh xạ gấp đôi có mẫu số sẽ tạo ra các điểm đặc biệt. Xem xét phương trình đường cong, chúng ta thấy rằng đây là ba điểm với $y=0$, cụ thể là $(0, 0), (\alpha, 0)$ và $(1/\alpha, 0)$, trong đó $\alpha^2 + a\alpha +1 = 0$. Thực tế, đây là ba điểm có bậc 2 trên $E_a$, và cùng với phần tử trung hòa $O$, chúng tạo nên kernel của ánh xạ gấp đôi. Kernel là một tiểu nhóm của các điểm trong $E_a$, với cấu trúc nhóm:
$$\text{ker}([2]) \approxeq \mathbb{Z}_2 \times \mathbb{Z}_2$$
tức là, 2-torsion chính xác là ba tiểu nhóm tuần hoàn có bậc 2. Mỗi tiểu nhóm có một trong ba điểm có bậc chính xác là 2, cùng với phần tử trung hòa $O$. Điều này được mô tả trong hình 2.
Phép nhân với 3 hay còn gọi là tripling:
$$[3]: E_a \rightarrow E_a, \quad x \mapsto \frac{x(x^4 -6x^2 -4ax^3-4)^2}{(3x^4 + 4ax^3 + 6x^2-1)^2}\quad (2)$$
Tương tự với $\text{ker}[3] \approxeq \mathbb{Z}_3 \times \mathbb{Z}_3$
Hình 3:
Tập hợp các điểm trong $l$-torsion tạo thành $l+1$ tiểu nhóm tuần hoàn có bậc $l$ khi $l$ là số nguyên tố.
Cả hai ánh xạ gấp đôi và gấp ba ở trên đều là những trường hợp đặc biệt của các ánh xạ tổng quát hơn giữa các đường cong elliptic mà chúng ta gọi là isogenies. Trong cả hai trường hợp này, thật trùng hợp khi domain và codomain của chúng cùng là một đường cong elliptic.
Quay lại Hình 2, giả sử chúng ta đặt $G = \{O, (\alpha, 0), (1/\alpha, 0), (0, 0)\}$ và đưa nó vào các công thức của Vélu, cùng với đường cong $E_a$. Kết quả sẽ là ánh xạ duy nhất có kernel $G$, tức là ánh xạ gấp đôi trong (1), cùng với $E_a$.
Giả sử chúng ta chọn kernel là một trong các tiểu nhóm có bậc 2, ví dụ đặt $G = \{O, (\alpha, 0)\}$, áp dụng công thức của Vélu ánh xạ mà chúng ta nhận được là:
$$\phi: E_a \rightarrow E_{a'} , \quad x \mapsto \frac{x(\alpha x - 1)}{x - \alpha}, \quad (3)$$
với
$$a' = 2(1 - 2\alpha^2)$$
Ánh xạ này có thể được sử dụng để tính toán các isogeny 2 trên bất kỳ đường cong Montgomery nào. Ví dụ:
$$E_a: y^2 = x^3 + (208i + 161)x^2 + x, \text{ với } j(E_a) = 364i + 304.$$
Điểm $(\alpha, 0) \in E_a$ với $\alpha = 350i + 68$ có bậc 2. Áp dụng (3) cho ra đường cong hình ảnh
$$ E_{a'} : y^2 = x^3 + (102i + 423)x^2 + x, \text{ với } j(E_{a'}) = 344i + 190, $$
và ánh xạ
$$\phi: x \mapsto \frac{x((350i + 68)x - 1)}{x - (350i + 68)} \quad (4)$$
sẽ đưa (tọa độ $x$ của) bất kỳ điểm nào không thuộc $\{O, (\alpha, 0)\}$ đến (tọa độ $x$ của) điểm tương ứng trên $E_{a'}$.
Bây giờ giả sử chúng ta đặt kernel là một trong các tiểu nhóm có bậc 3 trong Hình 3, ví dụ $G = \{O, (\beta, \gamma), (\beta, -\gamma)\}$. Áp dụng công thức của Vélu:
$$ \phi: E_a \rightarrow E_{a'} , \quad x \mapsto \frac{x(\beta x - 1)^2}{(x - \beta)^2}, \quad (5)$$
với
$$ a' = (a\beta - 6\beta^2 + 6)\beta. $$
Điểm $(\beta, \gamma) = (321i + 56, 303i + 174)$ có bậc 3 trên $E_a: y^2 = x^3 + (208i + 161)x^2 + x$. Áp dụng (5) cho ra đường cong hình ảnh
$$ E_{a'}: y^2 = x^3 + 415x^2 + x, \text{ với } j(E_{a'}) = 189, $$
và ánh xạ
$$ \phi: x \mapsto \frac{x((321i + 56)x - 1)^2}{(x - (321i + 56))^2} $$
sẽ di chuyển các điểm từ $E_a$ đến $E_{a'}$.
Các isogeny trong phần này tạo ra các đường cong hình ảnh với các j-invariant khác nhau; trong trường hợp này, các đường cong không còn là đồng cấu, mà được gọi là isogenous. Bậc của một isogeny tách biệt khác 0 là số lượng phần tử trong kernel của nó và nó cũng là bậc của isogeny như một ánh xạ tỷ lệ. Có thể thấy từ bất kỳ ví dụ nào ở trên rằng số lượng phần tử trong kernel khớp với bậc của ánh xạ tương ứng.
Các đồng cấu thực ra là một trường hợp đặc biệt của isogeny trong đó kernel là tầm thường, tức là kernel chỉ là $\{O\}$, vì vậy chúng là các isogeny có bậc 1. Theo định nghĩa, việc kết hợp một đồng cấu với đồng cấu nghịch đảo của nó cho ra ánh xạ đơn vị. Nếu $\phi: E \rightarrow E'$ là một isogeny có bậc $d$, thì dual isogeny $\hat{\phi}$ có đặc điểm rằng tổ hợp $(\hat{\phi} \circ \phi) = [d]$, tức là ánh xạ nhân với $d$ trên $E$, và tổ hợp $(\phi \circ \hat{\phi})$ là ánh xạ nhân với $d$ trên $E'$. Giống như các đồng cấu nghịch đảo, tổ hợp của các dual isogeny đưa chúng ta trở lại cùng một đường cong; sự khác biệt là kernel của tổ hợp này trở thành $d$-torsion nói chung (mà không tầm thường khi $d > 1$). Là một ví dụ, việc kết hợp isogeny bậc 2 $$ \phi: E_a \rightarrow E_{a'} $$ trong (3) với dual isogeny bậc 2 $\hat{\phi}: E_{a'} \rightarrow E_a$ cho ra ánh xạ gấp đôi bậc 4 trong (1) (có kernel trong Hình 2).
Nhưng các isogeny cũng là đại số ở chỗ chúng là các đồng cấu nhóm: một isogeny $\phi: E \rightarrow E'$ thỏa mãn
$$\phi(P + Q) = \phi(P) + \phi(Q)$$
cho tất cả $P, Q \in E$; tổng ở bên trái tương ứng với quy luật nhóm trên đường cong elliptic $E$, trong khi tổng ở bên phải là quy luật nhóm trên $E'$.
Trong bối cảnh SIDH, có thể thấy rõ đồng cấu này với một số ví dụ. Quay lại isogeny 2 trong (4) từ
$$ E_a: y^2 = x^3 + (208i + 161)x^2 + x $$
đến
$$ E_{a'}: y^2 = x^3 + (102i + 423)x^2 + x, $$
kernel của $\phi$ là $\{O, (\alpha, 0)\}$ với $\alpha = 350i + 68$.
Với các điểm khác nhau trên $E$ khi chúng di chuyển qua $\phi$, tạm thời trở lại với cả hai tọa độ dưới ánh xạ $\phi: (x, y) \mapsto (f(x), c \cdot y f'(x))$, với $f(x)$ như ở trên và với hằng số $c$ thỏa mãn $c^2 = \alpha$.
Các điểm:
$$P = (390i + 23, 104i + 7) \quad \text{and} \quad Q = (151i + 140, 110i + 136) $$
cả hai đều có bậc 8 trên $E_a$, nhưng khi $\phi$ là 2-isogeny ở trên, thì các điểm
$$ \phi(P) = (23i + 231, 309i + 61) \quad \text{and} \quad \phi(Q) = (80i + 261, 192i + 259) $$
có bậc 4 và 8 trên $E_{a'}$, tương ứng. Lý do mà bậc của $P$ giảm là vì nó nằm trên một phần tử không tầm thường trong kernel: $$[4]P = (\alpha, 0) \in \text{ker}(\phi)$$, do đó $$ \phi([4]P) = O $$ trên $E_{a'}$, và vì $\phi$ là một đồng cấu, $\phi([4]P) = [4]\phi(P);$ vì $[2]P \notin \text{ker}(\phi)$, nên $\phi(P)$ phải có bậc 4. Lý luận tương tự cho thấy rằng, nói chung, một isogeny bậc $d$ sẽ giảm bậc của bất kỳ điểm nào nằm trên kernel một hệ số $d$. Ngược lại, các điểm khác sẽ bảo toàn bậc của chúng khi di chuyển qua các isogeny, như chúng ta đã thấy ở trên đối với điểm $Q$. Là một ví dụ khác, hình ảnh của điểm: $$R = (\beta, \gamma) = (321i + 56, 303i + 174) $$ có bậc 3 trên $E_a$ là điểm $$ \phi(R) = (102i + 238, 346i + 193) $$ có bậc 3 trên $E_{a'}$. Nói chung, việc đánh giá một isogeny bậc $d$ tại một điểm có bậc $\ell$ sẽ bảo tồn bậc này nếu $d$ và $\ell$ là nguyên tố cùng nhau;
Các cài đặt hiện đại của SIDH (bao gồm cả trong SIKE) luôn cố định các số nguyên tố $p$ có dạng
$$
p = 2^{e_A} 3^{e_B} - 1,
$$
trong đó $e_A$ và $e_B$ sao cho $2^{e_A} \approx 3^{e_B}$. Thực tế, SIDH cho phép linh hoạt hơn bằng cho phép các số nguyên tố có dạng
$$
p = f \cdot 2^{e_A} 3^{e_B} - 1,
$$
Chúng ta làm việc với đường cong supersingular, trong đó nhóm đường cong elliptic $E(F_{p^2})$ là toàn bộ $(p + 1)$-torsion, tức là nhóm đó đồng cấu với $\mathbb{Z}^{p + 1} \times \mathbb{Z}^{p + 1}$. Do đó, với lựa chọn số nguyên tố của chúng ta, nhóm đường cong elliptic là
$$
E(F_{p^2}) \sim \mathbb{Z}^{(2^{e_A} 3^{e_B})} \times \mathbb{Z}^{(2^{e_A} 3^{e_B})}.
$$
Nói cách khác, hai điểm $P$ và $Q$, cả hai đều có bậc $2^{e_A} 3^{e_B}$, là một cơ sở cho toàn bộ nhóm đường cong elliptic $E(F_{p^2})$. Hơn nữa, các tổ hợp tuyến tính
$$
[\alpha]P + [\beta]Q \quad \text{với } \alpha, \beta \in \mathbb{Z}^{(2^{e_A} 3^{e_B})}
$$
có thể được sử dụng để tạo ra tất cả các điểm có bậc là bất kỳ ước số nào của $2^{e_A} 3^{e_B}$. Đặc biệt, mỗi điểm có bậc $2^{e_A}$ hoặc có bậc $3^{e_B}$ đều nằm trong $E(F_{p^2})$. Chúng ta sẽ thấy ở đầu phần tiếp theo rằng đây chính xác là những điểm được sử dụng làm các generator bí mật của các tiểu nhóm (tức là các isogeny) trong khung SIDH, vì vậy việc chọn các số nguyên tố theo cách trên cuối cùng có nghĩa là Alice và Bob chỉ phải làm việc với các điểm bên trong $E(F_{p^2})$.
## SIDH
### Tổng quan
SIDH thường lấy $p = 2^{e_A} 3^{e_B} - 1$ với $2^{e_A} \approx 3^{e_B}$. Quy trình bắt đầu trên một đường cong supersingular ban đầu $E$.
Bí mật của Alice sẽ là các isogeny có bậc $2^{e_A}$, và bí mật của Bob sẽ là các isogeny có bậc $3^{e_B}$. $\ell$-torsion là hai chiều, vì vậy Alice sẽ tính toán các generator của các subgroup bí mật bằng cách tính các tổ hợp tuyến tính bí mật của hai điểm cơ sở công khai:
$$
\langle P_A, Q_A \rangle = E[2^{e_A}] \sim \mathbb{Z}^{2^{e_A}} \times \mathbb{Z}^{2^{e_A}}.
$$
Tương tự, Bob sẽ tính toán các generator bí mật của mình như các tổ hợp tuyến tính bí mật của hai điểm công khai, $P_B$ và $Q_B$, nơi
$$
\langle P_B, Q_B \rangle = E[3^{e_B}] \sim \mathbb{Z}^{3^{e_B}} \times \mathbb{Z}^{3^{e_B}}.
$$
Điều này có nghĩa là $P_A$ và $Q_A$ đều có bậc $2^{e_A}$ và $P_B$ và $Q_B$ đều có bậc $3^{e_B}$. Trong thực tế, họ thường chọn các điểm generator bí mật của mình, $S_A$ và $S_B$, bằng cách đơn giản lấy:
$$
S_A = P_A + [k_A]Q_A \quad \text{với } k_A \in [0, 2^{e_A}),
$$
$$
S_B = P_B + [k_B]Q_B \quad \text{với } k_B \in [0, 3^{e_B}).
$$
#### 1. **Các điểm cơ sở và bậc của chúng**
- **Alice** làm việc với các điểm có bậc $2^{e_A}$:
- $P_A$ và $Q_A$ là hai điểm cơ sở công khai trên đường cong $E$, và chúng có bậc $2^{e_A}$. Điều này có nghĩa là:
$$
[2^{e_A}]P_A = O \quad \text{và} \quad [2^{e_A}]Q_A = O,
$$
trong đó $O$ là điểm vô cực.
- **Bob** làm việc với các điểm có bậc $3^{e_B}$:
- $P_B$ và $Q_B$ là hai điểm cơ sở công khai trên đường cong $E$, và chúng có bậc $3^{e_B}$. Điều này có nghĩa là:
$$
[3^{e_B}]P_B = O \quad \text{và} \quad [3^{e_B}]Q_B = O.
$$
---
#### 2. **Tính toán điểm sinh bí mật**
- **Alice** chọn một số nguyên ngẫu nhiên $k_A$ trong khoảng $[0, 2^{e_A})$ và tính toán điểm sinh bí mật $S_A$:
$$
S_A = P_A + [k_A]Q_A.
$$
- Điểm $S_A$ có bậc $2^{e_A}$ và được sử dụng để xây dựng isogeny bí mật của Alice.
- **Bob** chọn một số nguyên ngẫu nhiên $k_B$ trong khoảng $[0, 3^{e_B})$ và tính toán điểm sinh bí mật $S_B$:
$$
S_B = P_B + [k_B]Q_B.
$$
- Điểm $S_B$ có bậc $3^{e_B}$ và được sử dụng để xây dựng isogeny bí mật của Bob.
---
#### 3. **Tính toán isogeny bí mật**
- **Alice** xây dựng isogeny bí mật $\phi_A: E \to E_A$, trong đó $E_A = E / \langle S_A \rangle$:
- Isogeny $\phi_A$ có bậc $2^{e_A}$ và được xây dựng bằng cách kết hợp $e_A$ isogeny bậc 2. (tức là tại mỗi bước, Alice chọn một điểm có bậc 2 trên đường cong hiện tại và xây dựng một isogeny bậc 2 từ điểm đó. Quá trình này được lặp lại $e_A$ lần để thu được isogeny $\phi_A$có bậc $2^{e_A}$)
- Khóa công khai của Alice là:
$$
PK_A = (E_A, P_B^0, Q_B^0) = (\phi_A(E), \phi_A(P_B), \phi_A(Q_B)).
$$
- $E_A$ là đường cong hình ảnh sau khi áp dụng isogeny $\phi_A$.
- $P_B^0$ và $Q_B^0$ là hình ảnh của các điểm cơ sở công khai của Bob dưới ánh xạ $\phi_A$.
- **Bob** xây dựng isogeny bí mật $\phi_B: E \to E_B$, trong đó $E_B = E / \langle S_B \rangle$:
- Isogeny $\phi_B$ có bậc $3^{e_B}$ và được xây dựng bằng cách kết hợp $e_B$ isogeny bậc 3.
- Khóa công khai của Bob là:
$$
PK_B = (E_B, P_A^0, Q_A^0) = (\phi_B(E), \phi_B(P_A), \phi_B(Q_A)).
$$
- $E_B$ là đường cong hình ảnh sau khi áp dụng isogeny $\phi_B$.
- $P_A^0$ và $Q_A^0$ là hình ảnh của các điểm cơ sở công khai của Alice dưới ánh xạ $\phi_B$.
---
#### 4.**Tính toán khóa bí mật chung**
- **Alice** sử dụng khóa công khai của Bob $PK_B = (E_B, P_A^0, Q_A^0)$ để tính toán khóa bí mật chung:
1. Tính toán điểm sinh bí mật trên $E_B$:
$$
S_A^0 = P_A^0 + [k_A]Q_A^0.
$$
2. Xây dựng isogeny bí mật $\phi_A^0: E_B \to E_{AB}$, trong đó $E_{AB} = E_B / \langle S_A^0 \rangle$.
3. Tính toán j-invariant của đường cong $E_{AB}$:
$$
j_{AB} = j(E_{AB}).
$$
- $j_{AB}$ là khóa bí mật chung mà Alice tính toán.
- **Bob** sử dụng khóa công khai của Alice $PK_A = (E_A, P_B^0, Q_B^0)$ để tính toán khóa bí mật chung:
1. Tính toán điểm sinh bí mật trên $E_A$:
$$
S_B^0 = P_B^0 + [k_B]Q_B^0.
$$
2. Xây dựng isogeny bí mật $\phi_B^0: E_A \to E_{BA}$, trong đó $E_{BA} = E_A / \langle S_B^0 \rangle$.
3. Tính toán j-invariant của đường cong $E_{BA}$:
$$
j_{BA} = j(E_{BA}).
$$
- $j_{BA}$ là khóa bí mật chung mà Bob tính toán.
### Public parameters
Tiếp tục với ví dụ của $p = 2^43^{3} - 1$ và lấy đường cong bắt đầu công khai là
$$
E_{a0}: y^2 = x^3 + a_0 x^2 + x,
$$
với $a_0 = 329i + 423$ và $j(E_{a0}) = 87i + 190$. Chúng ta có thể chọn bất kỳ bốn điểm cơ sở công khai nào trên $E_{a0}$, miễn là $E[2^4] = \langle P_A, Q_A \rangle$ và $E[3^3] = \langle P_B, Q_B \rangle$. Chúng ta cố định
$$
P_A := (100i + 248, 304i + 199) \quad \text{và} \quad Q_A := (426i + 394, 51i + 79),
$$
cùng với
$$
P_B := (358i + 275, 410i + 104) \quad \text{và} \quad Q_B := (20i + 185, 281i + 239).
$$
#### **Alice’s public key generation**
Giả sử Alice chọn bí mật $k_A := 11$ từ $\{0, 1, \ldots, 15\}$. Bước đầu tiên của cô là tính toán generator bí mật tương ứng với $k_A$:
$$
S_A = P_A + [k_A]Q_A = (100i + 248, 304i + 199) + [11](426i + 394, 51i + 79) = (271i + 79, 153i + 430),
$$
điều này tạo thành một điểm có bậc $16$ trên đường cong bắt đầu $E_{a0}$. Alice tiếp tục tính toán khóa công khai của mình chỉ bằng cách sử dụng phép nhân đôi và phép isogeny bậc $2$.
– **Tính toán $\phi_0$**: Khởi tạo $S^0_A = S_A = (271i + 79, 153i + 430)$. Ba lần ứng dụng phép nhân đôi trong (1) tạo ra điểm
$$
R^0_A = [8]S^0_A = (18i + 37, 0),
$$
điểm này có bậc $2$ trên $E_{a0}$. Thay $R^0_A$ vào (3) cho $\phi_0: E_{a0} \to E_{a1}$, với $a_1 = 275i + 132$ và $j(E_{a1}) = 107$. Ánh xạ:
$$
\phi_0: x \mapsto x((18i + 37)x - 1) / (x - (18i + 37)),
$$
được sử dụng để cập nhật
$$
P_B^0 = \phi_0(P_B) = (118i + 85, 274i + 150),
$$
$$
Q_B^0 = \phi_0(Q_B) = (62i + 124, 64i + 269),
$$
$$
S_A^0 = \phi_0(S_A) = (36i + 111, 175i + 67).
$$
bậc của $P_B^0$ và $Q_B^0$ trên $E_{a1}$ không thay đổi, nhưng bậc của $S_A^0$ đã giảm từ $16$ xuống $8$.
– **Tính toán $\phi_1$**: Hai lần ứng dụng phép nhân đôi trong (1) tạo ra điểm
$$
R^0_A = [4]S^0_A = (7i + 49, 0),
$$
điểm này có bậc $2$ trên $E_{a1}$. Thay $R_A^0$ vào (3) cho
$$
\phi_1: E_{a1} \to E_{a2}, \quad a_2 = 273i + 76 \quad \text{và} \quad j(E_{a2}) = 344i + 190.
$$
Ánh xạ:
$$
\phi_1: x \mapsto x((7i + 49)x - 1) / (x - (7i + 49)),
$$
được sử dụng để cập nhật
$$
P_B^0 = \phi_1(P_B^0) = (274i + 251, 316i + 59),
$$
$$
Q_B^0 = \phi_1(Q_B^0) = (214i + 94, 354i + 193),
$$
$$
S_A^0 = \phi_1(S_A^0) = (274i + 374, 84i + 77).
$$
bậc của điểm $S_A^0$ đã giảm từ $8$ xuống $4$.
– **Tính toán $\phi_2$**: Một lần nhân đôi thông qua (1) tạo ra điểm
$$
R^0_A = [2]S^0_A = (245i + 27, 0),
$$
tọa độ này có bậc $2$ trên $E_{a2}$. Thay $R_A^0$ vào (3) cho
$$
\phi_2: E_{a2} \to E_{a3}, \quad a_3 = 93i + 136 \quad \text{và} \quad j(E_{a3}) = 350i + 65.
$$
Ánh xạ
$$
\phi_2: x \mapsto x((245i + 27)x - 1) / (x - (245i + 27)),
$$
được sử dụng để cập nhật
$$
P_B^0 = \phi_2(P_B^0) = (77i + 209, 75i + 79),
$$
$$
Q_B^0 = \phi_2(Q_B^0) = (339i + 356, 12i + 419),
$$
$$
S_A^0 = \phi_2(S_A^0) = (227i + 150, 0).
$$
Bậc của $S_A^0$ đã giảm từ $4$ xuống $2$.
– **Tính toán $\phi_3$**: $S_A^0 = (227i + 150, 0)$ đã có bậc $2$ trên $E_{a3}$, vì vậy không cần nhân với số. Thay $S_A^0$ vào (3) cho
$$
\phi_3: E_{a3} \to E_{a4}, \quad a_4 = 423i + 179 \quad \text{và} \quad j(E_{a4}) = 222i + 118.
$$
Ánh xạ:
$$
\phi_3: x \mapsto x((227i + 150)x - 1) / (x - (227i + 150)),
$$
được sử dụng để cập nhật
$$
P_B^0 = \phi_3(P_B^0) = (142i + 183, 119i + 360),
$$
$$
Q_B^0 = \phi_3(Q_B^0) = (220i + 314, 289i + 10);
$$
điểm $S_A^0$ nằm trong kernel và không được đưa qua.
Khóa isogeny bí mật của Alice là sự hợp nhất của bốn isogeny $2$ đã nêu ở trên, tức là
$$
\phi_A: E_{a0} \to E_{a4}, \quad Q \mapsto \phi_A(Q), \quad \text{với } \phi_A = (\phi_3 \circ \phi_2 \circ \phi_1 \circ \phi_0).
$$
Khóa công khai của cô là
$$
PK_A = (\phi_A(E_{a0}), \phi_A(P_B), \phi_A(Q_B)).
$$
Thay vì gửi j-invariant $j(E_{a4}) \in F_{p^2}$ như là giá trị xác định đường cong, Alice có thể đơn giản gửi $a_4 \in F_p^4$, và Bob cũng sẽ làm như vậy. Hàm j chỉ được sử dụng trong quá trình tính toán bí mật chia sẻ để đảm bảo rằng Alice và Bob đến cùng một giá trị.
#### **Bob’s public key generation**
Giả sử Bob chọn bí mật $k_B := 2$ từ $\{0, 1, \ldots, 26\}$. Bước đầu tiên của anh là tính toán generator bí mật tương ứng với $k_B$:
Các bước làm tương tự Alice
$$
S_B = P_B + [k_B]Q_B = (358i + 275, 410i + 104) + [2](20i + 185, 281i + 239) = (122i + 309, 291i + 374),
$$
điều này tạo thành một điểm có bậc $27$ trên $E_{a0}$. Bob tiếp tục tính toán khóa công khai của mình chỉ bằng cách sử dụng phép tripling và phép isogeny bậc $3$. Dưới đây, chúng ta sẽ sử dụng cùng một quy ước như đã làm với Alice.
– **Tính toán $\phi_0$**: Khởi tạo $S^0_B = S_B = (122i + 309, 291i + 374)$. Hai lần ứng dụng phép tripling trong (2) tạo ra điểm
$$
R^0_B = [9]S^0_B = (23i + 37, 4i + 302),
$$
điểm này có bậc $3$ trên $E_{a0}$. Nhập $R_B^0$ vào (5) cho
$$
\phi_0: E_{a0} \to E_{a1}, \quad a_1 = 134i + 2 \quad \text{và} \quad j(E_{a1}) = 106i + 379.
$$
Ánh xạ:
$$
\phi_0: x \mapsto \frac{x((23i + 37)x - 1)^2}{(x - (23i + 37))^2},
$$
được sử dụng để cập nhật
$$
P_A^0 = \phi_0(P_A) = (418i + 155, 288i + 331),
$$
$$
Q_A^0 = \phi_0(Q_A) = (159i + 242, 310i + 425),
$$
$$
S_B^0 = \phi_0(S_B) = (295i + 256, 253i + 64).
$$
Bậc của $P_A^0$ và $Q_A^0$ trên $E_{a1}$ không thay đổi, nhưng bậc của điểm mới $S_B^0$ đã giảm từ $27$ xuống $9$.
– **Tính toán $\phi_1$**: Một lần tripling thông qua (2) tạo ra điểm
$$
R^0_B = [3]S^0_B = ((98i + 36, 56i + 155)),
$$
điểm này có bậc $3$ trên $E_{a1}$. Nhập $R_B^0$ vào (5) cho
$$
\phi_1: E_{a1} \to E_{a2}, \quad a_2 = 117i + 54 \quad \text{và} \quad j(E_{a2}) = 325i + 379.
$$
Ánh xạ:
$$
\phi_1: x \mapsto \frac{x((98i + 36)x - 1)^2}{(x - (98i + 36))^2},
$$
được sử dụng để cập nhật
$$
P_A^0 = \phi_1(P_A^0) = (252i + 425, 315i + 19),
$$
$$
Q_A^0 = \phi_1(Q_A^0) = (412i + 81, 111i + 172),
$$
$$
S_B^0 = \phi_1(S_B^0) = (102i + 405, 375i + 313).
$$
bậc của điểm mới $S_B^0$ đã giảm từ $9$ xuống $3$.
– **Tính toán $\phi_2$**: $S_B^0 = (102i + 405, 375i + 313)$ đã có bậc $3$ trên $E_{a2}$, vì vậy không cần nhân với số. Nhập $R_B^0$ vào (5) cho
$$
\phi_2: E_{a2} \to E_{a3}, \quad a_3 = 273i + 76 \quad \text{và} \quad j(E_{a3}) = 344i + 190.
$$
Ánh xạ:
$$
\phi_2: x \mapsto \frac{x((98i + 36)x - 1)^2}{(x - (98i + 36))^2},
$$
được sử dụng để cập nhật
$$
P_A^0 = \phi_2(P_A^0) = (187i + 226, 43i + 360),
$$
$$
Q_A^0 = \phi_2(Q_A^0) = (325i + 415, 322i + 254),
$$
$$
S_B^0 = \phi_2(S_B^0) = (102i + 405, 375i + 313);
$$
điểm $S_B^0$ nằm trong kernel và không được đưa qua.
Khóa isogeny bí mật của Bob là sự hợp nhất của ba isogeny $3$ đã nêu ở trên, tức là
$$
\phi_B: E_{a0} \to E_{a3}, \quad Q \mapsto \phi_B(Q), \quad \text{với } \phi_B = (\phi_2 \circ \phi_1 \circ \phi_0).
$$
Khóa công khai của Bob là
$$
PK_B = (\phi_B(E_{a0}), \phi_B(P_A), \phi_B(Q_A)).
$$
#### **Alice’s shared secret computation**
Alice bắt đầu từ đường cong trong khóa công khai của Bob, lấy đường cong bắt đầu mới $E_{a0}$ với $a_0 = 273i + 76$. Bước đầu tiên của cô là tính toán generator bí mật trên $E_{a0}$ tương ứng với bí mật $k_A$:
$$
S_A = \phi_B(P_A) + [k_A] \phi_B(Q_A) = (187i + 226, 43i + 360) + [11](325i + 415, 322i + 254) = (125i + 357, 415i + 249).
$$
Cô tiếp tục thực hiện quy trình tương tự như trước, thực hiện một chuỗi phép toán tương tự như trong quá trình tạo khóa. Sự khác biệt duy nhất là cô không cần di chuyển các điểm cơ sở qua isogeny, tiết kiệm một số phép toán vì chỉ cần đến đường cong đích.
Các phép toán isogeny 2 được tóm tắt như sau:
$$
\phi_0: E_{a0} \to E_{a1}, \quad a_1 = 289i + 341 \quad \text{và} \quad j(E_{a1}) = 364i + 304;
$$
$$
\phi_1: E_{a1} \to E_{a2}, \quad a_2 = 414i + 428 \quad \text{và} \quad j(E_{a2}) = 67;
$$
$$
\phi_2: E_{a2} \to E_{a3}, \quad a_3 = 246 \quad \text{và} \quad j(E_{a3}) = 242;
$$
$$
\phi_3: E_{a3} \to E_{a4}, \quad a_4 = 230 \quad \text{và} \quad j(E_{a4}) = 234.
$$
Hình minh họa quy trình tính toán bí mật chia sẻ của Alice.
#### Bob’s shared secret computation
Bob bắt đầu từ đường cong trong khóa công khai của Alice trong (6), lấy đường cong bắt đầu mới $E_{a0}$ với $a_0 = 423i + 179$. Bước đầu tiên của anh là tính toán generator bí mật trên $E_{a0}$ tương ứng với bí mật $k_A$:
$$
S_B = \phi_A(P_B) + [k_B] \phi_A(Q_B) = (142i + 183, 119i + 360) + [2](220i + 314, 289i + 10) = (393i + 124, 187i + 380).
$$
Bob tiếp tục thực hiện quy trình tương tự như trước, với sự khác biệt là không di chuyển các điểm cơ sở của Alice qua isogeny. Các phép toán isogeny $3$ được tóm tắt như sau:
$$
\phi_0: E_{a0} \to E_{a1}, \quad a_1 = 183i + 177 \quad \text{và} \quad j(E_{a1}) = 299i + 315;
$$
$$
\phi_1: E_{a1} \to E_{a2}, \quad a_2 = 31 \quad \text{và} \quad j(E_{a2}) = 61;
$$
$$
\phi_2: E_{a2} \to E_{a3}, \quad a_3 = 230 \quad \text{và} \quad j(E_{a3}) = 234.
$$
Hình minh họa quy trình tính toán bí mật chia sẻ của Bob.
Chúng ta thấy rằng Alice và Bob đã thực sự đạt được cùng một giá trị chia sẻ.
-----
Script:
```python=
p = 431
assert p == 2^4*3^3 - 1 and is_prime(p)
F.<i> = GF(p^2, modulus=x^2+1)
def E_a(a):
"""Returns a curve given by Montgomery form y² = x³ + a*x² + x."""
return EllipticCurve(F, [0, a, 0, 1, 0])
E = E_a(329*i + 423)
P_A = E(100*i + 248, 304*i + 199)
Q_A = E(426*i + 394, 51*i + 79)
P_B = E(358*i + 275, 410*i + 104)
Q_B = E(20*i + 185, 281*i + 239)
def computeIsogenies(E, S, l, e):
"""Returns a list of e l-isogenies making up the target isogeny."""
S_tmp = S
E_tmp = E
ϕs = []
for k in range(e):
# Generate a point in the l-torsion via repeated
# doubling (l=2) or tripling (l=3) starting from S_tmp.
R_tmp = S_tmp
for _ in range(e-k-1):
R_tmp = l*R_tmp
assert R_tmp.order() == l
# Generate an l-isogeny to take a step in the graph.
ϕ_k = E_tmp.isogeny(R_tmp)
assert ϕ_k.degree() == l
S_tmp = ϕ_k(S_tmp)
# Each S_tmp lies above a point in the l-isogeny's kernel,
# so its order decreases by a factor of l per step.
assert S_tmp.order() == l^(e-k-1)
E_tmp = ϕ_k.codomain()
ϕs.append(ϕ_k)
return ϕs
k_A = 11
S_A = P_A + k_A*Q_A
assert S_A.order() == 2^4 # S_A remains in E[2^4]
ϕs_A = computeIsogenies(E, S_A, 2, 4)
# Check that we took the expected path.
assert [ ϕ.codomain().j_invariant() for ϕ in ϕs_A ] == \
[ 107, 344*i + 190, 350*i + 65, 222*i + 118 ]
ϕ_A = ϕs_A[3] * ϕs_A[2] * ϕs_A[1] * ϕs_A[0]
Alice = (ϕ_A.codomain(), ϕ_A(P_B), ϕ_A(Q_B))
k_B = 2
S_B = P_B + k_B*Q_B
assert S_B.order() == 3^3
ϕs_B = computeIsogenies(E, S_B, 3, 3)
assert [ ϕ.codomain().j_invariant() for ϕ in ϕs_B ] == \
[ 106*i + 379, 325*i + 379, 344*i + 190 ]
ϕ_B = ϕs_B[2] * ϕs_B[1] * ϕs_B[0]
Bob = (ϕ_B.codomain(), ϕ_B(P_A), ϕ_B(Q_A))
# Alice
(E_B, B_P_A, B_Q_A) = Bob
B_S_A = B_P_A + k_A*B_Q_A
ϕs_A = computeIsogenies(E_B, B_S_A, 2, 4)
assert [ ϕ.codomain().j_invariant() for ϕ in ϕs_A ] == \
[ 364*i + 304, 67, 242, 234 ]
jAlice = ϕs_A[-1].codomain().j_invariant()
# Bob
(E_A, A_P_B, A_Q_B) = Alice
A_S_B = A_P_B + k_B*A_Q_B
ϕs_B = computeIsogenies(E_A, A_S_B, 3, 3)
assert [ ϕ.codomain().j_invariant() for ϕ in ϕs_B ] == \
[ 299*i + 315, 61, 234 ]
jBob = ϕs_B[-1].codomain().j_invariant()
assert jAlice == jBob == 234 #Success
```
### SIDH in practice
Có 4 primes được dùng trong SIKE có form giống như ta phân tích ở trên là $p = 2^{e_Ae_B} - 1$
- $e_A = 216 \quad \text{and} e_B = 137 \quad \text{in SIKE434}$
- $e_A = 250 \quad \text{and} e_B = 159 \quad \text{in SIKE503}$
- $e_A = 305 \quad \text{and} e_B = 192 \quad \text{in SIKE610}$
- $e_A = 372 \quad \text{and} e_B = 239 \quad \text{in SIKE751}$
Dưới đây là ` SIKEp434` với các parameters được cho trước
```python=
p = 2^216*3^137 - 1
F.<i> = GF(p^2, modulus=x^2+1)
E = EllipticCurve(F, [0, 6, 0, 1, 0])
xQ20=0x000C7461738340EFCF09CE388F666EB38F7F3AFD42DC0B664D9F461F31AA2EDC6B4AB71BD42F4D7C058E13F64B237EF7DDD2ABC0DEB0C6C
xQ21=0x00025DE37157F50D75D320DD0682AB4A67E471586FBC2D31AA32E6957FA2B2614C4CD40A1E27283EAAF4272AE517847197432E2D61C85F5
yQ20=0x001D407B70B01E4AEE172EDF491F4EF32144F03F5E054CEF9FDE5A35EFA3642A11817905ED0D4F193F31124264924A5F64EFE14B6EC97E5
yQ21=0x000E7DEC8C32F50A4E735A839DCDB89FE0763A184C525F7B7D0EBC0E84E9D83E9AC53A572A25D19E1464B509D97272AE761657B4765B3D6
xP20=0x0003CCFC5E1F050030363E6920A0F7A4C6C71E63DE63A0E6475AF621995705F7C84500CB2BB61E950E19EAB8661D25C4A50ED279646CB48
xP21=0x001AD1C1CAE7840EDDA6D8A924520F60E573D3B9DFAC6D189941CB22326D284A8816CC4249410FE80D68047D823C97D705246F869E3EA50
yP20=0x001AB066B84949582E3F66688452B9255E72A017C45B148D719D9A63CDB7BE6F48C812E33B68161D5AB3A0A36906F04A6A6957E6F4FB2E0
yP21=0x000FD87F67EA576CE97FF65BF9F4F7688C4C752DCE9F8BD2B36AD66E04249AAF8337C01E6E4E1A844267BA1A1887B433729E1DD90C7DD2F
xQ30=0x0012E84D7652558E694BF84C1FBDAAF99B83B4266C32EC65B10457BCAF94C63EB063681E8B1E7398C0B241C19B9665FDB9E1406DA3D3846
xQ31=0x0000000
yQ30=0x0000000
yQ31=0x000EBAAA6C731271673BEECE467FD5ED9CC29AB564BDED7BDEAA86DD1E0FDDF399EDCC9B49C829EF53C7D7A35C3A0745D73C424FB4A5FD2
xP30=0x0008664865EA7D816F03B31E223C26D406A2C6CD0C3D667466056AAE85895EC37368BFC009DFAFCB3D97E639F65E9E45F46573B0637B7A9
xP31=0x0000000
yP30=0x0006AE515593E73976091978DFBD70BDA0DD6BCAEEBFDD4FB1E748DDD9ED3FDCF679726C67A3B2CC12B39805B32B612E058A4280764443B
yP31=0x0000000
Q_A = E(xQ20 + xQ21*i, yQ20 + yQ21*i)
P_A = E(xP20 + xP21*i, yP20 + yP21*i)
Q_B = E(xQ30 + xQ31*i, yQ30 + yQ31*i)
P_B = E(xP30 + xP31*i, yP30 + yP31*i)
def computeIsogeny(E, S, l, e):
S_tmp = S
E_tmp = E
ϕ = None
for k in range(e):
R_tmp = S_tmp
for _ in range(e-k-1):
R_tmp = l*R_tmp
ϕ_k = E_tmp.isogeny(R_tmp)
S_tmp = ϕ_k(S_tmp)
E_tmp = ϕ_k.codomain()
if ϕ is None:
ϕ = ϕ_k
else:
ϕ = ϕ_k * ϕ
return ϕ
# Alice generates public information
k_A = randint(0, 2^216-1)
S_A = P_A + k_A*Q_A
ϕ_A = computeIsogeny(E, S_A, 2, 216)
Alice = (ϕ_A.codomain(), ϕ_A(P_B), ϕ_A(Q_B))
# Bob
k_B = randint(0, 3^137-1)
S_B = P_B + k_B*Q_B
ϕ_B = computeIsogeny(E, S_B, 3, 137)
Bob = (ϕ_B.codomain(), ϕ_B(P_A), ϕ_B(Q_A))
# Alice computes shared secret
(E_B, B_P_A, B_Q_A) = Bob
B_S_A = B_P_A + k_A*B_Q_A
jAlice = computeIsogeny(E_B, B_S_A, 2, 216).codomain().j_invariant()
# Bob
(E_A, A_P_B, A_Q_B) = Alice
A_S_B = A_P_B + k_B*A_Q_B
jBob = computeIsogeny(E_A, A_S_B, 3, 137).codomain().j_invariant()
assert jAlice == jBob
```
## Security
**SIDH (Supersingular Isogeny Diffie-Hellman)** ban đầu dễ bị tấn công nếu khóa bí mật tĩnh (static secret key) bị rò rỉ. Nếu Alice sử dụng lại khóa bí mật $k_A$ của mình cho nhiều lần trao đổi khóa, một Bob độc hại có thể dần dần rò rỉ khóa này từng bit một bằng cách gửi $\log_2(k_A)$ yêu cầu được thiết kế đặc biệt.
Ý tưởng là chúng ta có thể sử dụng việc trao đổi khóa thành công hay thất bại như một "oracle" (một cơ chế trả lời có/không) để xác định xem Alice có khôi phục được đường cong đúng $E_{AB} = E / \langle S_A, S_B \rangle$ hay không. Từ ánh xạ đẳng cấu-nhóm con (isogeny-subgroup bijection), chúng ta biết rằng Alice sẽ làm điều này nếu và chỉ nếu cô ấy tính toán một isogeny từ $E_B = E / \langle S_B \rangle$ với nhóm con chính xác $\langle _BS_A \rangle = \langle \phi_B(P_A) + [k_A]\phi_B(Q_A) \rangle$ làm kernel. Tuy nhiên, các điểm đường cong $\phi_B(P_A)$ và $\phi_B(Q_A)$ được gửi bởi Bob, không có cách nào để Alice xác minh một cách đáng tin cậy liệu chúng có hợp lệ hay không. Do đó, Bob có thể thao túng chúng cho mục đích xấu.
Đặt $R \triangleq \phi_B(P_A)$ và $S \triangleq \phi_B(Q_A)$. Khóa riêng của Alice là $\alpha \triangleq k_A$, và số mũ bậc của nhóm con của cô ấy là $n \triangleq e_A$. Chúng ta có thể biểu diễn khóa dưới dạng nhị phân:
$$
\alpha = \alpha_0 + 2^1\alpha_1 + 2^2\alpha_2 + \ldots + 2^{n-1}\alpha_{n-1}.
$$
Giả sử chúng ta đã rò rỉ được $i$ bit đầu tiên và ký hiệu phần đó của khóa là $K_i$. Ban đầu, chúng ta không biết gì, nên $K_0 = 0$. Khi chúng ta quan tâm đến bit thứ $i$, chúng ta viết khóa dưới dạng:
$$
\alpha = K_i + 2^i\alpha_i + 2^{i+1}\alpha',
$$
trong đó $\alpha'$ đại diện cho tất cả các bit cao hơn.
Bây giờ, hãy xem xét điều gì xảy ra khi Bob gửi các điểm sau:
$$
(R - [2^{n-i-1}K_i]S, [1 + 2^{n-i-1}]S).
$$
Nghĩ rằng đây là cơ sở của cô ấy trên $E_B$, Alice sẽ xây dựng nhóm con:
$$
\langle R - [2^{n-i-1}K_i]S + [\alpha][1 + 2^{n-i-1}]S \rangle.
$$
Sau một số biến đổi, chúng ta có:
$$
\langle R + [\alpha]S + [(\alpha - K_i)2^{n-i-1}]S \rangle.
$$
Thay $\alpha = K_i + 2^i\alpha_i + 2^{i+1}\alpha'$, chúng ta được:
$$
\langle R + [\alpha]S + [2^{n-1}\alpha_i]S + [2^n\alpha']S \rangle.
$$
Vì $S$ thuộc nhóm $2^n$-torsion, nên $[2^n\alpha']S = O$ (điểm vô cực). Do đó, biểu thức trở thành:
$$
\langle R + [\alpha]S + [2^{n-1}\alpha_i]S \rangle.
$$
Biểu thức này bằng $\langle R + [\alpha]S \rangle$ nếu và chỉ nếu $\alpha_i = 0$.
- Nếu bit $\alpha_i = 0$, trao đổi khóa sẽ thành công, và chúng ta nhận được cùng một $j$-invariant.
- Nếu bit $\alpha_i = 1$, trao đổi khóa sẽ thất bại.
Bằng cách gửi cấu trúc này cho tất cả $i \in [0, n)$, chúng ta có thể khôi phục toàn bộ khóa. Để tránh bị phát hiện, Bob có thể brute-force (thử nghiệm) hai bit cuối cùng.
```python=
def simulateAlice(E_B, B_P_A, B_Q_A):
"""Pretends to be Alice computing an isogeny from a subgroup
on E_B and returning the resulting j-invariant."""
B_S_A = B_P_A + k_A*B_Q_A
return computeIsogeny(E_B, B_S_A, 2, 216).codomain().j_invariant()
(E_B, R, S) = Bob
Ki = 0
n = 216
bitsToLeak = 11
for i in range(bitsToLeak):
b = -Ki*2^(n-i-1)
d = 1 + 2^(n-i-1)
EvilBob = (E_B, R + b*S, d*S)
if simulateAlice(*EvilBob) != jBob:
Ki += 2^i
print(f"{i}:")
print(f"k_A = {bin(k_A)[-bitsToLeak:]}")
print(f"Ki = {bin(Ki)[2:].rjust(bitsToLeak,'0')}")
assert Ki & (2^bitsToLeak - 1) == k_A & (2^bitsToLeak -1)
```
## Tham khảo
- Elliptic curves and isogenies: The good bits: https://yx7.cc/docs/misc/isog_bristol_notes.pdf
- Supersingular isogeny key exchange for beginners: https://eprint.iacr.org/2019/1321.pdf
- On the Security of Supersingular Isogeny Cryptosystems: https://eprint.iacr.org/2016/859
Sign in with Wallet
Connect another wallet