Elliptic Curves over Real Numbers: A Geometric Intuition

Đường cong elliptic đóng vai trò cực kỳ quan trọng trong công nghệ mật mã hiện đại vì tính hiệu quả trong không gian lưu trữ và bảo mật vượt trội so với các công nghệ mã khóa công khai truyền thống như RSA. Hãy xem bảng so sánh bên dưới để thấy sự hiệu quả của mã hóa trên đường cong so với RSA:

Ở bài viết này, mình muốn giới thiệu một số phép toán được định nghĩa trên đường cong trên trường số thực để bạn đọc dễ hình dung. Tuy nhiên, trong công nghệ mật mã, người ta sử dụng đường cong elliptic trên trường hữu hạn các số nguyên tố, mình sẽ giới thiệu ở bài viết sau. Trong bài viết này chúng ta sẽ tìm hiểu:

Phương trình của elliptic curve
Hình dạng của đường cong
Quy tắc cộng hai điểm trên đường cong
Quy tắc nhân một điểm với một scalar

Phương trình của Elliptic Curve

Một elliptic curve trên trường số thực thường được định nghĩa bởi phương trình:

y^2 = x^3+ax+b

trong đó $a,b$ là các số thực. Một elliptic curve trên trường số thực thường được định nghĩa bởi phương trình:

4a^3 + 27b^2 \ne 0

Điều kiện này đảm bảo rằng đường cong không có điểm kỳ dị (singular point), chẳng hạn như điểm nhọn hoặc giao cắt với chính nó. Nếu điều kiện này được thỏa mãn, đường cong được gọi là non-singular elliptic curve. Về mặt đồ thị, đường cong có 2 dạng như bên dưới:

Lý do là vì phương trình có chưa $y^2$ nên nếu $(x,y)$ nằm trên đường cong thì $(x,-y)$ cũng nằm trên đường cong.

Điểm kỳ dị

Một điểm được gọi là singular nếu tại đó:

đường cong có góc nhọn (cusp), hoặc
hai nhánh của đường cong giao nhau (self-intersection).

Những điểm như vậy phá vỡ cấu trúc hình học của elliptic curve.

Tại sao cần điều kiện $4a^3 + 27b^2 \ne 0$ ?

Xét hàm $F(x,y)=y^2 - (x^3+ax+b)$ , một điểm trên đường cong là singular nếu cả hai đạo hàm riêng đều bằng $0$ . Nghĩa là:

\frac{\partial F}{\partial x} = 0, \frac{\partial F}{\partial y} = 0

Ta có: $\displaystyle \frac{\partial F}{\partial x} = -(3x^2+a)$ và $\displaystyle \frac{\partial F}{\partial y} = 2y$ . Khi cả hai đều bằng $0$ nghĩa là $y=0$ và $\displaystyle x^2 = -\frac a 3$ . Thay vào phương trình elliptic curve

x^3 + ax + b = 0

Sau khi rút gọn ta được điều kiện: $4a^3 + 27b^2 = 0$ nghĩa là nếu điều này xảy ra thì đường cong xuất hiện điểm kỳ dị. Vì vậy để tránh trường hợp này ta yêu cầu:

4a^3 + 27b^2 \ne 0

Vai trò của điều kiện này:

Đảm bảo có đường cong trơn
Không có singular point
Phép cộng điểm được định nghĩa hợp lệ (ta sẽ nói kỹ hơn về phép cộng điểm ở phần sau bài này)
Tập điểm trên đường cong tạo thành một nhóm abelian

Điểm vô cực

Để định nghĩa phép toán trên elliptic curve, người ta thêm một điểm đặc biệt gọi là điểm vô cực, ký hiệu là $O$ . Tập các điểm trên elliptic curve khi đó là:

E(\mathbb R) = \{(x,y) \in \mathbb R^2\} \cup \{O\}

Điểm $O$ đóng vai trò phần tử đơn vị trong phép cộng điểm. Nghĩa là với mọi điểm $P$ trên đường cong thì:

P+O=O+P=P

Phép cộng 2 điểm trên đường cong

Giả sử ta có hai điểm $P(x_1,y_1), Q(x_2,y_2)$ , ta định nghĩa phép cộng 2 điểm trên đường cong như sau:

Vẽ đường thẳng đi qua hai điểm $P$ và $Q$ .
Đường thẳng này sẽ cắt elliptic curve tại một điểm thứ ba.
Lấy điểm đối xứng qua trục hoành của điểm thứ ba đó.

Điểm thu được chính là $P+Q$ .

Một lưu ý là nếu hai điểm $P,Q$ đối xứng nhau qua trục hoành thì $P=-Q$ và lúc này:

P+Q=O

Với $O$ là phần tử đơn vị.

Phép nhân đôi điểm (Point Doubling)

Khi điểm $P=Q$ lúc này ta có $P+Q=P+P=2 \times P$ . Tuy nhiên lúc này ta không thể vẽ đường thẳng qua hai điểm khác nhau nữa. Thay vào đó ta:

Vẽ tiếp tuyến của đường cong tại điểm $P$
Tiếp tuyến này sẽ cắt đường cong tại một điểm thứ ba
Lấy điểm đối xứng của điểm đó qua trục hoành

Điểm kết quả chính là $2P$ . Phép toán này được gọi là point doubling. Từ công thức này ta suy ra được công thức nhân một điểm với một scalar bất kỳ

k \times P = \underbrace {P + P + \dots + P}_{\text{k times}}

Có một lưu ý rằng tồn tại một số điểm trên đường cong mà tiếp tuyến tại điểm đó không cắt đường cong. Ví dụ:

Rõ ràng tiếp tuyến tại $P$ sẽ song song với trục tung và không cắt đường cong. Theo quy ước của elliptic curve thì giao điểm được xem như ở vô cực $O$ . Do đó:

2P = O

Công thức đại số

Mặc dù cách giải thích bằng hình học rất trực quan, nhưng trong thực tế ta sử dụng công thức đại số.

Nếu $P \ne Q$ :

\lambda = \frac {y_2 - y_1} {x_2 - x_1} \\ x_3 = \lambda^2 - x_1 - x_2 \\ y_3 = \lambda(x_1-x_3)-y_1

Khi đó

P+Q = (x_3,y_3)

Nếu $P=Q$ :

\lambda = \frac {3x_1^2 + a}{2y_1}

Các công thức này cho phép máy tính thực hiện các phép toán trên elliptic curve.

Cấu trúc nhóm của Elliptic Curve

Một điều đáng ngạc nhiên là các điểm trên elliptic curve cùng với phép cộng vừa định nghĩa tạo thành một nhóm abelian. Cụ thể các tính chất sau đều được thỏa mãn:

Đóng (closure)
Kết hợp (associativity)
Có phần tử đơn vị $O$
Có phần tử nghịch đảo
Giao hoán (commutative)

Chính cấu trúc nhóm này làm cho elliptic curve trở nên cực kỳ hữu ích trong toán học và mật mã.

Elliptic curve trên trường số thực