# Lý thuyết mật mã trên Elliptic Curve
## 1. Các đường cong Ellip
- Đường cong Ellip thực:

- Đường cong Ellip được định nghĩa bởi phương trình với 2 biến $x,y$ và hệ số thực
- Xét đường cong Ellip bậc 3 có dạng:

- $y^{2} = x^{3} + ax + b$; trong đó $x,y,a,b$ là các số thực và định nghĩa thêm điểm $O$
- Có phép cộng đối với đường cong Ellip

- Về hình học tổng của $P$ và $Q$ là điểm đối xứng của giao điểm $R$
- Điểm $O$ đóng vai trò là đơn vị đối với phép cộng và nó là điểm vô cực


- Đường cong Ellip hữu hạn:

- Mã đường cong Ellip sử dụng đường cong Ellip mà các biến số và hệ số là hữu hạn
- Có hai họ đường cong nói chung:

- Đường cong nguyên tố **$E_{p}(a,b)$** được xác định trên $Z_{p}$

- Sử dụng các số nguyên modulo số nguyên tố
- Tốt nhất trong phần mềm

- Đường cong nhị phân **$E_{2^{n}}(a,b)$** xác định trên $GF(2^{n})$

- Sử dụng đa thức với hệ số nhị phân
- Tốt nhất trong phần cứng

## 2. Đường cong Elliptic(Elliptic Curve)
- Định nghĩa:

- Cho $p>3$ là số nguyên tố, đường cong Elliptic $y^{2}=x^{2}+ax+b \pmod p$, trong đó $a,b \in Z_{p}$ là các hằng số thỏa mãn $4a^{3}+27b^{2}\neq0\pmod p$ cùng với điểm đặc biệt $O$ gọi là điểm vô cực.

- Phép cộng 2 điểm trên Elliptic Curve:

- Giả sử $P = (x_1,y_1), Q = (x_2,y_2)$ là 2 điểm thuộc $E_p(a,b)$, phép cộng được định nghĩa như sau:

- Nếu $x_2=x_1,y_2=-y_1$ thì $P+Q=O$
- Ngược lại $P+Q=(x_3,y_3)$ thì:

- $x_3=\lambda^2-x_1-x_2$
- $y_3=\lambda(x_1-x_3)-y_1$
- $\lambda =
\begin{cases}
\frac{y_2-y_1}{x_2-x_1} & \quad \text{if } P \neq Q
\\\frac{3x_1^2 +a}{2y_1} & \quad \text{if } P = Q
\end{cases}$

- Tính chất của phép cộng trên $E$:

- $P+O=O+P=P$, $\forall P \in E$
- $P+(-P)=O$, $\forall P \in E$
- $(P+Q)+R=P+(Q+R)$, $\forall P,Q,R \in E$
- $P+Q=Q+P$, $\forall P,Q \in E$
- Nghịch đảo của $P$: $-P=-(x_1,y_1) = (x_1,-y_1)$, trường hợp $E$ được xác định trên $Z_p$ thì $-P=(x_1,p-y_1)$
$\implies$ Tập hợp các điểm thuộc $E$ tạo thành 1 nhóm giao hoán (abelian group)

- Khi cho $E$ là đường cong Elliptic: $y^2=x^3+ax+b$ trên $Z_p$ ta cần xác định các điểm trên $E$

- Với mỗi $x_0\in Z_p$, ta xác định được $z=y_0^2=x_0^3+ax_0+b \pmod p$
- Kiểm tra xem $z$ có phải là thặng dư bậc 2 trên $Z_p$ không
- Nếu $z$ là thặng dư bậc 2 trên $Z_p$ thì căn bậc 2 của $z$ trên $Z_p$, đó chính là các giá trị của $y_0$ tương ứng với $x_0$