Elliptic Curve trên Trường Hữu Hạn

Bạn có thể xem lại bài viết về Elliptic Curve cơ bản trên trường số thực ở bài viết trước của mình.

Đường cong elliptic trên trường hữu hạn là một phần quan trọng trong mật mã học hiện đại. Khác với đường cong elliptic trên trường số thực (trên miền liên tục), đường cong elliptic trong mật mã học được định nghĩa trên các trường hữu hạn số nguyên tố.

Trường hữu hạn thường là:

• Trường nguyên tố $\mathbb F_p$

• Trường nhị phân $\mathbb F_{2^m}$

Trong bài viết này ta tập trung vào trường nguyên tố $\mathbb F_p$.

💡 Về mặt tính toán, đường cong elliptic trên trường hữu hạn vẫn giữ nguyên phương pháp như ở trên đường cong elliptic trên trường số thực và bao gồm hay phép tính: phép cộng hai điểm và phép nhân scalar.

Định nghĩa Elliptic Curve trên $\mathbb F_p$

Cho $p$ là số nguyên tố $p \gt 3$. Một Elliptic curve trên $\mathbb F_p$ được định nghĩa là

với $a,b \in \mathbb F_p$ và thỏa điều kiện $4a^3 + 27b^2 \not \equiv 0 \pmod p$ để đảm bảo đường cong không có điểm kỳ dị.

Tập điểm của đường cong là:

Trong đó $O$ là điểm ở vô cực, tổng số điểm trên đường cong ($n$) kể cả điểm vô cực gọi là bậc của đường cong (curve order). Lưu ý rằng bậc của đường cong không phải là giá trị $p$. Theo định lý Hasse, ta có $|n-(p+1)| \le 2\sqrt p$, điều này cho thấy rằng số điểm của đường cong chỉ gần bằng với $p$.

Hình dạng của elliptic curve trên trường hữu hạn

Khác với trường số thực, ở đây các điểm của đường cong:

• $x,y$ chỉ nhận giá trị rời rạc

• Đồ thị không còn là đường cong liên tục

Ví dụ: Với $p=17$, đường cong $y^2 \equiv x^3 + 2x+2 \pmod {17}$ chỉ có một tập hữu hạn các điểm như: $(5,1),(5,16),(6,3),(6,14),\dots$ Vì thế nếu biểu diễn trên mặt phẳng ta sẽ chỉ thấy các chấm rời rạc mà không phải là một đường cong.

Phép cộng điểm

Điều thú vị là các công thức cộng điểm vẫn giống hệt trường số thực.

Giả sử $P=(x_1,y_1), Q=(x_2,y_2)$. Ta tính:

Khi đó:

Điểm khác biệt duy nhất là mọi phép toán đều thực hiện modulo $p$.

Phép nhân vô hướng

Sau khi đã định nghĩa phép cộng điểm trên elliptic curve, chúng ta có thể mở rộng phép toán này bằng cách cộng một điểm nhiều lần, cũng giống hệt như cách ta định nghĩa cho đường cong trên trường số thực.

Cho một điểm $P$ trên elliptic curve $E(\mathbb{F}_p)$ và một số nguyên $k$. Ta định nghĩa:

Chu kỳ của các điểm trên elliptic curve

Vì tập điểm của elliptic curve trên $\mathbb{F}_p$​ là hữu hạn, nên khi ta liên tục cộng điểm $P$ với chính nó:

thì dãy này không thể tăng mãi mà cuối cùng sẽ quay lại điểm đặc biệt $O$.

Nói cách khác, tồn tại một số nguyên dương $n$ sao cho:

Trong đó $O$ là điểm ở vô cực, đóng vai trò phần tử trung tính của phép cộng điểm.

Bậc của một điểm

Số nguyên dương nhỏ nhất $n$ thỏa mãn:

được gọi là bậc (order) của điểm $P$. Khi đó ta có:

và dãy các điểm bắt đầu lặp lại theo chu kỳ.

Cấu trúc nhóm

Nhờ các tính chất của phép cộng điểm, tập điểm của elliptic curve $E(\mathbb F_p)$ cùng với phép cộng tạo thành một nhóm abelian hữu hạn.

Các tính chất của nhóm bao gồm:

1. Closure
   Nếu $P,Q \in E(\mathbb{F}_p)$ thì $P+Q \in E(\mathbb{F}_p)$

2. Associativity
   Kết hợp $(P+Q)+R=P+(Q+R)$

3. Identity element
   Tồn tại điểm $O$ sao cho $P + O = P$

4. Inverse element

   Với mỗi điểm $P=(x,y)$ tồn tại điểm $−P=(x,−y)$ sao cho $P+(−P)=O$

5. Commutativity

   Giao hoán $P+Q=Q+P$

Xây dựng mật mã từ Elliptic Curve

Trong các hệ mật mã elliptic curve, chúng ta không sử dụng toàn bộ tập điểm của đường cong một cách tùy ý. Thay vào đó, người ta chọn một điểm đặc biệt gọi là điểm sinh.

Giả sử $E(\mathbb{F}_p)$ là tập các điểm trên elliptic curve và $G$là một điểm trên đường cong đó.

Điểm $G$ được gọi là điểm sinh (generator point) nếu bằng cách thực hiện phép nhân vô hướng, ta có thể tạo ra nhiều điểm khác trong nhóm:

Sau một số bước nhất định, dãy này sẽ quay lại điểm đơn vị:

Trong đó $O$ là điểm ở vô cực (phần tử trung tính của phép cộng).

Số $n$ nhỏ nhất thỏa mãn điều kiện trên được gọi là bậc của điểm $G$.

Tập các điểm:

tạo thành một nhóm con cyclic sinh ra bởi $G$ của elliptic curve. Trong các hệ mật mã elliptic curve, điểm sinh $G$ được công bố công khai cùng với các tham số của đường cong.

Người dùng chọn một số bí mật $k$ (private key) và tính:

Trong đó:

• $k$ là khóa bí mật

• $Q$là khóa công khai

Để ý rằng việc tính $Q$ từ $k$ và $G$ tương đối dễ vì chỉ cần thực hiện phép nhân vô hướng. Tuy nhiên nếu chỉ biết $G$ và $Q$, việc tìm lại $k$ là một bài toán rất khó về mặt tính toán. Bài toán này được gọi là Elliptic Curve Discrete Logarithm Problem. Chính độ khó của bài toán này tạo nên độ an toàn của các hệ mật mã elliptic curve.

Demo