3. Đường cong elliptic

Đường cong elliptic (elliptic curve) rất nổi tiếng trong toán học. Đây là công cụ giúp các nhà toán học giải quyết bài toán lớn Định lý cuối cùng của Fermat.

Trong mật mã học, đường cong elliptic là một trong những tiêu chuẩn bảo mật về mã hóa và chữ ký điện tử. Chương này khảo sát những đặc trưng cơ bản đường cong elliptic và ứng dụng trong mật mã học.

3.1. Mở đầu về đường cong elliptic

Đường cong elliptic là tập hợp các điểm \((x, y)\) trên mặt phẳng \(Oxy\) thỏa mãn phương trình

\[y^2 = x^3 + ax + b,\]

với \(a, b \in \mathbb{R}\) và \(4a^3 + 27b^2 \neq 0\).

Ví dụ với phương trình \(y^2 = x^3 + 8\), đồ thị được biểu diễn ở hình 3.20.

Ta thấy rằng, đường cong elliptic đối xứng qua trục hoành.

Hình 3.20 Elliptic \(y^2 = x^3 + 8\)

Ví dụ với phương trình \(y^2 = x^3 - x\), đồ thị được biểu diễn ở hình 3.21.

Hình 3.21 Elliptic \(y^2 = x^3 - x\)

Hoặc đối với phương trình \(y^2 = x^3 - 3x + 3\) thì đồ thị được biểu diễn ở hình 3.22.

Hình 3.22 Elliptic \(y^2 = x^3 - 3x + 3\)

3.2. Phép cộng các điểm trên elliptic

Phương trình và đồ thị của đường cong elliptic đã được trình bày ở trên. Tuy nhiên chúng ta quan tâm tới mối liên hệ giữa các điểm trên elliptic, cụ thể là phép cộng hai điểm.

Ta thêm một điểm trừu tượng vào tập hợp các điểm trên đường cong elliptic và gọi là điểm vô cực. Điểm vô cực được kí hiệu là \(\mathcal{O}\). Khi đó mọi điểm \(P\) thuộc đường cong elliptic sẽ có tính chất

\[P + \mathcal{O} = \mathcal{O} + P = P.\]

Khi đó, với điểm \(P=(x, y)\) bất kì trên elliptic, điểm đối xứng của nó qua trục hoàng là \(P' = (x, -y)\), và ta định nghĩa \(P + P' = \mathcal{O}\).

Tiếp theo ta định nghĩa phép cộng hai điểm.

Giả sử \(P = (x_P, y_P)\) và \(Q = (x_Q, y_Q)\) là hai điểm trên elliptic. Ta có hai trường hợp:

1. Nếu \(P \neq Q\), ta vẽ đường thẳng đi qua \(P\) và \(Q\). Đường thẳng này cắt elliptic tại điểm thứ ba là \(S\). Ta lấy \(R\) đối xứng với \(S\) qua trục hoành. Khi đó \(R\) cũng nằm trên elliptic và \(P + Q = R\);

2. Nếu \(P \equiv Q\), ta vẽ tiếp tuyến với elliptic tại điểm \(P\). Tiếp tuyến này cắt elliptic tại điểm thứ hai là \(S\). Tương tự ta lấy \(R\) đối xứng với \(S\) qua trục hoành. Khi đó \(P + Q = 2P = R\).

Khi đó, tập hợp các điểm trên elliptic cùng với điểm vô cực, và phép cộng hai điểm được định nghĩa như trên tạo thành một nhóm.

Để chứng minh đây là nhóm, ta cần chuyển các khái niệm hình học kia sang đại số để tính toán và chứng minh.

3.2.1. Phép cộng hai điểm khác nhau

Đầu tiên ta thiết lập công thức phép cộng giữa hai điểm cho trường hợp \(P \neq Q\). Giả sử \(P = (x_P, y_P)\) và \(Q = (x_Q, y_Q)\).

Phương trình đường thẳng đi qua \(P\) và \(Q\) là

(3.6)\[y = \frac{y_Q - y_P}{x_Q - x_P} (x - x_P) + y_P.\]

Thay \(y\) vào phương trình đường cong elliptic ta có

(3.7)\[\left[\frac{y_Q - y_P}{x_Q - x_P} (x - x_P) + y_P\right]^2 = x^3 + ax + b\]

Đặt \(k = \dfrac{y_Q - y_P}{x_Q - x_P}\). Khi đó phương trình tương đương với

\[(k x - k x_P + y_P)^2 = x^3 + ax + b.\]

Khai triển và chuyển vế ta có

\[x^3 - k^2 x^2 + \ldots = 0.\]

Ta chỉ cần quan tâm hệ số trước \(x^2\). Bởi vì ta biết rằng đường thẳng \(PQ\) cắt elliptic tại ba điểm \(P\), \(Q\), \(S\), nên phương trình bậc 3 này có 3 nghiệm phân biệt là \(x_P\), \(x_Q\) và \(x_S\). Theo theo định lý Viete ta có

\[x_P + x_Q + x_S = k^2.\]

Như vậy ta có hoành độ điểm \(S\)

\[x_S = k^2 - x_P - x_Q,\]

thay \(x_S\) vào (3.6), ta có tung độ điểm \(S\)

\[y_S = k(x_S - x_P) + y_P,\]

mà \(R\) đối xứng với \(S\) qua trục hoành, như vậy \(x_R = x_S\) và \(y_R = -y_S\).

Như vậy kết quả của phép cộng là

\[\begin{split}x_R & = k^2 - x_P - x_Q \\ y_R & = k(x_P - x_R) - y_P\end{split}\]

với \(k = \dfrac{y_Q - y_P}{x_Q - x_P}\).

3.2.2. Phép cộng hai điểm giống nhau

Trong trường hợp hai điểm giống nhau, ta vẽ tiếp tuyến tiếp xúc với elliptic đi qua điểm đó.

Giả sử ta muốn vẽ tiếp tuyến tại điểm \(P = (x_P, y_P)\), khi đó từ phương trình elliptic \(y^2 = x^3 + ax + b\) ta vi phân hai vế thu được

\[2y \,dy = (3x^2 + a) \, dx.\]

Ta biết rằng hệ số góc của đường tiếp tuyến là đạo hàm hàm số tại điểm đó, hay nói cách khác là \(dy/dx\). Như vậy hệ số góc tiếp tuyến tại điểm \(P\) là

\[k = \frac{dy}{dx} = \frac{3 x_P^2 + a}{2y_P}\]

và như vậy phương trình đường tiếp tuyến là

\[y = k(x-x_P) + y_P.\]

Thực hiện tương tự như bên trên, ta có đường tiếp tuyến cắt elliptic tại hai điểm phân biệt, trong đó có một điểm tiếp xúc nên trong phương trình hoành độ giao điểm điểm tiếp xúc là nghiệm bội hai. Nói cách khác, theo định lý Viete thì

\[x_P + x_P + x_S = k^2,\]

suy ra hoành độ điểm \(S\) là

\[x_S = k^2 - 2 x_P,\]

và tung độ điểm \(S\) là

\[y_S = k(x_S - x_P) + y_P\]

Cuối cùng, tọa độ điểm \(R = P + P\) là

\[x_R = k^2 - 2 x_P, \quad y_R = k(x_P - x_S) - y_P.\]

3.2.3. Tổng kết

Để cộng hai điểm \(P=(x_P, y_P)\) và \(Q = (x_Q, y_Q)\) ta có ba trường hợp sau:

1. Nếu \(x_Q = x_P\) và \(y_Q = -y_P\), nói cách khác là đối xứng qua trục hoành, thì ta có \(P + Q = \mathcal{O}\).

2. Nếu \(x_P \neq x_Q\), đặt \(k = \dfrac{y_Q - y_P}{x_Q - x_P}\) thì tọa độ điểm \(R = P + Q\) là

\[x_R = k^2 - x_P - x_Q, \quad y_R = k(x_P - x_R) - y_P.\]

3. Nếu \(x_P = x_Q\) và \(y_P = y_Q\), khi hai điểm trùng nhau, đặt \(k = \dfrac{3x_P^2 + a}{2y_P}\), thì tọa độ điểm \(R = 2P\) là

\[x_R = k^2 - 2x_P, \quad y_R = k(x_P - x_R) - y_P.\]

3.3. Đường cong elliptic trên trường hữu hạn \(\mathbb{F}_p\)

Trong mật mã học đường cong elliptic được sử dụng nhiều nhất là trên trường hữu hạn \(\mathbb{F}_p\) với \(p\) là số nguyên tố.

Đường cong ellipitc lúc này là điểm vô cực \(\mathcal{O}\) và tập hợp các điểm \((x, y) \in \mathbb{F}_p^2\) thỏa mãn

\[y^2 \equiv x^3 + ax + b \bmod p,.\]

với \(4 a^3 + 27 b^2 \neq 0 \bmod p\).

Việc thực hiện phép cộng hai điểm cũng tương tự như trên \(\mathbb{R}\) ở phần trên nhưng các phép tính được thực hiện trong modulo \(p\).

Như vậy để cộng hai điểm \(P = (x_P, y_P)\) và \(Q = (x_Q, y_Q)\) thì:

1. Nếu \(x_Q \equiv x_P \pmod p\) và \(y_Q \equiv -y_P \pmod p\) thì \(P + Q = \mathcal{O}\).

2. Nếu \(x_Q \not\equiv x_P \pmod p\), đặt \(k \equiv \dfrac{y_Q - y_P}{x_Q - x_P} \pmod p\) thì tọa độ điểm \(R = P + Q\) là

\[x_R \equiv k^2 - x_P - x_Q \pmod p, \quad y_R = k(x_P - x_R) - y_P \pmod p.\]

3. Nếu \(x_Q \equiv x_P\) và \(y_Q \equiv y_P\), nói cách khác là hai điểm trùng nhau, đặt \(k = \dfrac{3x_P^2 + a}{2y_P} \pmod p\) thì tọa độ điểm \(R = 2 P\) là

\[x_R = k^2 - 2x_P \pmod p, \quad y_R = k(x_P - x_R) - y_P \pmod p.\]

Một điểm đáng chú ý là \(\mathbb{F}_p\) có hữu hạn phần tử, do đó số phần tử của đường cong elliptic với tọa độ trong \(\mathbb{F}_p\) cũng là hữu hạn. Do tính chất này mà mật mã học có thể sử dụng đường cong elliptic.

3.4. Dạng Weierstrass tổng quát

Ở công thức cộng hai điểm giống nhau xuất hiện hai hằng số là \(2\) và \(3\). Một vấn đề đặt ra là nếu trường có đặc số bằng \(2\), nghĩa là \(2 \equiv 0\), khi đó hàm hai biến

\[f(x, y) = y^2 - x^3 - ax - b\]

sẽ có đạo hàm theo \(y\) luôn bằng \(0\) vì \(f_y = 2y \equiv 0\). Ta không thể tính tiếp tuyến như trên \(\mathbb{R}\) để đưa ra công thức cho phép cộng hai điểm giống nhau. Tương tự đối với trường có đặc số bằng \(3\).

Trong trường hợp các trường \(K\) có đặc số bằng \(2\) thì chúng ta sử dụng dạng Weierstrass tổng quát (generalized Weierstrass) là

\[y^2 + a_1 xy + a_3 y = x^3 + a_2 x^2 + a_4 x + a_6,\]

với \(a_1, a_2, a_3, a_4, a_6 \in K\).

[TODO] Phép cộng hai điểm trên đường cong elliptic dạng Weierstrass tổng quát.