Khám phá cặp đường cong elip

Tác giả: Vitalik Buterin

Tiêu đề gốc: 《Khám Phá Các Đối Tượng Đường Elliptic》

Thời gian xuất bản: Ngày 14 tháng 1 năm 2017

Nhiều cơ sở hạ tầng trong mật mã, chẳng hạn như "chữ ký ngưỡng xác định" (deterministic threshold signature, tạm dịch), zk-SNARKs và các hình thức chứng minh không biết khác đơn giản hơn, một trong những mô hình nguyên thủy quan trọng là các đối tượng đường elliptic. Đường elliptic đã được sử dụng rộng rãi trong hơn ba mươi năm qua trong các ứng dụng mật mã như mã hóa, chữ ký số, v.v., "các đối tượng đường elliptic (EC pairings)" (hoặc ánh xạ song tuyến tính) là một thứ mới gần đây dựa trên nó, nó đã giới thiệu phép nhân mật mã, làm tăng đáng kể những gì có thể thực hiện dựa trên các thỏa thuận đường elliptic. Bài viết này sẽ giới thiệu chi tiết về các đối tượng đường elliptic và giải thích ngắn gọn cách thức hoạt động của nó.

Bởi vì khái niệm này thực sự không dễ hiểu, không mong đợi bạn sẽ hoàn toàn hiểu ngay từ lần đọc đầu tiên hoặc thậm chí là lần thứ mười, nhưng hy vọng bài viết này có thể ít nhất cho bạn biết một số điều thú vị.

Đường elliptic bản thân đã là một chủ đề không dễ hiểu, nhưng bài viết này phần lớn sẽ giả định rằng bạn có một số hiểu biết về nguyên lý hoạt động của nó, nếu bạn không có khái niệm cơ bản, tôi sẽ giới thiệu bài viết này như một điểm khởi đầu. Nói chung, đường elliptic xử lý một số đối tượng toán học được gọi là "điểm (points)", nói một cách đơn giản là các điểm trên mặt phẳng hai chiều (x, y), cũng như một số công thức đặc biệt cho phép cộng và trừ (ví dụ tính R = P + Q), bạn cũng có thể nhân điểm với một số nguyên (ví dụ P * n = P + P + … + P, mặc dù khi n rất lớn có một thuật toán nhanh hơn nhiều).

Đây là hình ảnh của phép cộng điểm trên đồ thị

Ngoài ra còn có một điểm đặc biệt gọi là "điểm vô cùng xa" (O), trong quy tắc toán học của các điểm như là phần tử không, tức là đối với tất cả các điểm đều có P + O = P. Một đường cong còn có một đặc tính gọi là "bậc (order)", tức là tồn tại một số nguyên dương n, đối với tất cả P đều có P * n = O (tất nhiên P * (n + 1) = P, P * ((7*n) + 5) = P * 5, và cứ như vậy). Còn có một "điểm sinh (generator point) G" đã được thỏa thuận trước, tức là điểm được chọn để làm phần tử đơn vị của phép cộng, đại diện cho số 1. Về lý thuyết, bất kỳ điểm nào trên đường cong đều có thể được coi là phần tử sinh, điều quan trọng là G được chọn thống nhất.

Các đối tượng cho phép bạn xác minh một loại phương trình phức tạp hơn: ví dụ, nếu P = G * p, Q = G * q, R = G * r, khi bạn muốn kiểm tra p * q = r có đúng hay không, bạn chỉ cần có tọa độ của ba điểm P, Q, R làm đầu vào. Điều này có thể trông giống như bảo đảm an toàn cơ bản nhất của đường elliptic đã bị phá vỡ, vì nhìn thoáng qua, nếu biết tọa độ của điểm P thì đã tiết lộ giá trị p. Nhưng thực tế, rủi ro bị rò rỉ như vậy là rất hạn chế - chính xác mà nói, vấn đề Diffie-Hellman quyết định rất dễ dàng, nhưng phiên bản tính toán vẫn là "không khả thi về mặt tính toán (computationally infeasible)". Ít nhất độ khó cũng giống như không biết giá trị này.

Cách hiểu thứ ba về "các đối tượng", có lẽ là cách có tính gợi mở nhất trong hầu hết các tình huống sử dụng mà chúng ta đang thảo luận, là nếu bạn coi các điểm trên đường elliptic như một hàm mã hóa một chiều (có nghĩa là encrypt(p) = p * G = P), thì so với nguyên lý toán học truyền thống của đường elliptic cho phép bạn kiểm tra các ràng buộc tuyến tính giữa các biến (ví dụ P = G * p, Q = G * q, R = G * r, kiểm tra 5 * P + 7 * Q = 11 * R thực sự là kiểm tra 5 * p + 7 * q = 11 * r), các đối tượng đường elliptic cho phép bạn kiểm tra các ràng buộc bậc hai giữa các biến (kiểm tra e(P, Q) * e(G, G * 5) = 1 thực sự là kiểm tra p * q + 5 = 0). Có thể làm được bậc hai thì đủ để chúng ta thực hiện những ứng dụng thú vị như chữ ký ngưỡng xác định, QAP (chương trình số học bậc hai, một loại chứng minh không biết) v.v.

Bây giờ câu hỏi là toán tử e(P, Q) mà chúng ta đã giới thiệu ở trên thực sự là gì? Đó là một tập hợp "các đối tượng". Các nhà toán học đôi khi cũng gọi nó là "ánh xạ song tuyến tính", "song tuyến tính" ở đây cơ bản có nghĩa là nó thỏa mãn các điều kiện sau:

e(P, Q + R) = e(P, Q) * e(P, R)
e(P + S, Q) = e(P, Q) * e(S, Q)

Lưu ý rằng ở đây dấu + và * có thể là bất kỳ toán tử nào; khi bạn tạo ra một loại đối tượng toán học mới, đại số trừu tượng không quan tâm đến cách + và * được "định nghĩa", chỉ cần chúng nhất quán với các phép toán mà chúng ta quen thuộc, như a + b = b + a, (a * b) * c = a * (b * c), (a * c) + (b * c) = (a + b) * c.

Giả sử bây giờ P, Q, R, S chỉ là các số, thì hàm đối tượng rất dễ xây dựng: chúng ta có thể định nghĩa e(x, y) = 2^(xy). Vậy chúng ta sẽ thấy:

e(3, 4 + 5) = 2^(3 * 9) = 2²⁷
e(3, 4) * e(3, 5) = 2^(3 * 4) * 2^(3 * 5) = 2¹² * 2¹⁵ = 2²⁷

Nó thực sự là song tuyến tính!

Tuy nhiên, các đối tượng đơn giản như vậy không phù hợp để sử dụng trong mật mã, vì việc phân tích các đối tượng toán học hoạt động đơn giản trên số nguyên là rất dễ dàng; tính chất của số nguyên khiến cho nhiều phép toán như chia, logarit trở nên dễ dàng. Số nguyên cũng không có khái niệm "khóa công khai" hay "hàm một chiều". Hơn nữa, các đối tượng được mô tả ở trên là có thể đảo ngược: biết x, biết e(x, y), thực hiện phép chia và logarit có thể tính được y. Cấu trúc toán học mà chúng ta muốn là gần như "hộp đen": bạn có thể thực hiện một số phép cộng, trừ, nhân, chia, nhưng chỉ có thể như vậy. Lúc này, đường elliptic và các đối tượng đường elliptic sẽ phát huy tác dụng.

Người ta phát hiện ra rằng thực sự có thể thiết kế ánh xạ song tuyến tính trên các điểm của đường elliptic - tức là khi đầu vào là hai điểm P và Q trên đường elliptic, xây dựng một hàm e(P, Q) ánh xạ đến một phần tử F_p¹² (ít nhất trong trường hợp cụ thể này là đủ, và quy chuẩn này sẽ khác nhau tùy thuộc vào chi tiết của đường cong, sẽ được đề cập sau), nhưng việc thực hiện điều này dưới nền tảng toán học thực sự rất phức tạp.

Đầu tiên, chúng ta sẽ giới thiệu về trường số nguyên tố (prime fields) và trường mở rộng (extension fields). Đường cong được vẽ trong hình trên mặc dù đẹp, nhưng đó là khi bạn giả định rằng phương trình của đường cong được định nghĩa trên các số thực thông thường. Nếu chúng ta thực sự sử dụng số thực trong mật mã, thì bạn có thể "quay ngược lại" bằng logarit, và mọi thứ sẽ trở nên vô dụng, chưa kể đến không gian cần thiết để lưu trữ số thực có thể vô tận. Vì vậy, chúng ta sử dụng các số trên trường số nguyên tố.

Một trường số nguyên tố được cấu thành từ tập hợp các số 0, 1, 2, …, (p−1), trong đó p là một số nguyên tố, và các phép toán được định nghĩa như sau:

a + b: (a + b) % p
a * b: (a * b) % p
a - b: (a - b) % p
a / b: (a * b^(p-2)) % p

Về cơ bản, tất cả các phép toán đều được thực hiện theo modulo p (đây là giới thiệu về phép toán modulo). Phép chia là một trường hợp đặc biệt. Nói chung, 3/2 không phải là số nguyên, nhưng chúng ta muốn chỉ xử lý số nguyên, vì vậy chúng ta chuyển sang tìm số nguyên x sao cho x * 2 = 3, và ở đây * tất nhiên là phép nhân modulo được định nghĩa ở trên. May mắn thay, có định lý nhỏ của Fermat, định nghĩa lũy thừa của phép chia có thể thỏa mãn yêu cầu, nhưng còn có một cách nhanh hơn, đó là sử dụng thuật toán Euclid mở rộng. Giả sử p = 7, dưới đây là một số ví dụ:

2 + 3 = 5 % 7 = 5
4 + 6 = 10 % 7 = 3
2 - 5 = -3 % 7 = 4
6 * 3 = 18 % 7 = 4
3 / 2 = (3 * 2^5) % 7 = 5
5 * 2 = 10 % 7 = 3

Nếu bạn thử thực hiện các phép toán như vậy, bạn sẽ thấy nó nhất quán và thỏa mãn tất cả các quy tắc thông thường. Hai ví dụ cuối cùng cho thấy (a / b) * b = a, bạn cũng có thể nhận thấy (a + b) + c = a + (b + c), (a + b) * c = a * c + b * c, và nhiều phương trình đại số khác mà bạn đã biết và yêu thích từ trung học vẫn sẽ hoạt động. Các đường cong elliptic thực tế được sử dụng, các điểm và phương trình thường được thực hiện trên trường số nguyên tố.

Bây giờ chúng ta hãy nói về trường mở rộng. Bạn có thể đã thấy trường mở rộng trước đây, ví dụ thường gặp nhất trong sách giáo khoa toán học là trường số phức - được mở rộng từ trường số thực bằng cách thêm phần tử mới sqrt(-1) = i. Nói một cách đơn giản, trường mở rộng là "phát minh" một phần tử mới trên một trường đã có sẵn, và định nghĩa mối quan hệ giữa phần tử mới này với các phần tử hiện có (trong ví dụ vừa rồi là i² + 1 = 0); mối quan hệ này không thể được thỏa mãn bởi các số hiện có, do đó tập hợp được tạo ra từ phần tử mới cộng với "tất cả các tổ hợp tuyến tính của các phần tử cũ" sẽ là tập hợp được xây dựng.

Chúng ta cũng có thể mở rộng trường số nguyên tố; ví dụ, trong trường số nguyên tố modulo 7, thêm phần tử i mà chúng ta vừa nói, thì chúng ta có

(2 + 3i) + (4 + 2i) = 6 + 5i
(5 + 2i) + 3 = 1 + 2i
(6 + 2i) * 2 = 5 + 4i
4i * (2 + i) = 3 + i

Phương trình cuối cùng có thể khó hiểu hơn; thực tế, bước đầu tiên của phương trình đó là thực hiện phép phân phối bên trái thành 4i * 2 + 4i * i, dẫn đến 8i - 4. Bởi vì chúng ta đang thực hiện phép toán trong môi trường modulo 7, số này trở thành i + 3. Còn về phần phép chia thì:

a / b : (a * b^(p²-2)) % p

Ở đây, lũy thừa của định lý nhỏ của Fermat đã chuyển từ p thành p², và tất nhiên cũng có thể sử dụng thuật toán Euclid mở rộng để tính toán hiệu quả hơn. Bởi vì đối với bất kỳ phần tử nào x trong trường, sẽ có x^(p² − 1) = 1, nên chúng ta gọi (p² − 1) là "bậc của nhóm nhân trong trường".

Đối với trường số thực, định lý cơ bản của đại số đảm bảo rằng trường mở rộng bậc hai của nó (quadratic extension): trường số phức, là hoàn chỉnh (người dịch chú thích: nên là đại số đóng, trường số thực cũng có tính hoàn chỉnh nhưng có thể mở rộng) - trường này không thể mở rộng thêm nữa, vì tất cả các phần tử mới có thể có j và các số phức hiện có nên thỏa mãn mối quan hệ toán học (nói chính xác là mối quan hệ toán học được định nghĩa bằng đa thức), đã có một phần tử trong trường đã thỏa mãn. Nhưng trong trường số nguyên tố, không có vấn đề này, chúng ta có thể thực hiện mở rộng bậc ba (cubic extension) (phần tử mới w và mối quan hệ với các phần tử hiện có là một đa thức bậc ba, do đó 1, w, w² là độc lập tuyến tính), mở rộng bậc cao hơn, thậm chí mở rộng nhiều lần nữa. Các đường cong elliptic được xây dựng trên các số phức của các phép toán modulo này.

Nếu bạn quan tâm đến cách thực hiện những toán học này thành mã, đây là một số ví dụ về việc thực hiện trường số nguyên tố và trường mở rộng.

Quay lại với các đối tượng đường elliptic. Các đối tượng đường elliptic (các đối tượng mà chúng tôi đang thảo luận chỉ là một trong số đó, nhưng logic của các đối tượng là tương tự) là một ánh xạ G2 × G1 → Gt, trong đó:

• G1 là một đường elliptic, các điểm trên đó thỏa mãn phương trình có dạng y² = x³ + b, và tọa độ x, y của điểm đều là phần tử của F_p (có nghĩa là chúng chỉ là các số bình thường, nhưng phép toán số học sẽ được thực hiện theo modulo một số nguyên tố nào đó).
• G2 cũng là một đường elliptic, cũng thỏa mãn đường cong G1, nhưng tọa độ x, y của các phần tử trong G2 là phần tử của F_p¹² (đây là những số phức mà chúng ta vừa đề cập; chúng ta định nghĩa một số kỳ diệu w, thỏa mãn một đa thức bậc 12 w¹² − 18 w⁶ + 82 = 0)
• Gt là tập hợp các kết quả của phép toán trên đường elliptic. Trong các đường cong mà chúng ta đang thảo luận, Gt là F_p¹² (sử dụng cùng những số phức như G2)

Điều chính mà nó phải thỏa mãn là tính song tuyến tính, trong bối cảnh này được đại diện như sau:

e(P, Q + R) = e(P, Q) * e(P, R)
e(P + Q, R) = e(P, R) * e(Q, R)

(người dịch chú thích: ở đây tính song tuyến tính chính xác mà nói là "song tuyến tính trên các số nguyên (bilinearity over ℤ)", chỉ vì các điểm trên đường elliptic đang được thảo luận đều là các điểm số nguyên, và định nghĩa của phép nhân và phép cộng là phép toán số nguyên sau đó lấy modulo, tự nhiên đã thỏa mãn một số tính chất tuyến tính)

Việc chọn hàm đối tượng còn có hai tiêu chí quan trọng:

• Phép toán phải đủ hiệu quả (ví dụ chúng ta có thể trực tiếp lấy logarit rời rạc của tất cả các điểm rồi nhân tất cả lại, như một phương pháp đối tượng đơn giản, nhưng chi phí tính toán cần thiết cho điều này cũng khó khăn như việc phá vỡ mật mã đường elliptic, vì vậy điều này không tính)
• Không suy giảm (bạn chắc chắn có thể đơn giản định nghĩa e(P, Q) = 1, nhưng nó không phải là một đối tượng đặc biệt hữu ích)

Vậy chúng ta nên làm thế nào để thực hiện điều này?

Toán học đứng sau việc cho phép hàm đối tượng hoạt động rất khó khăn, và cần một số đại số nâng cao, vượt quá những gì chúng ta đã thấy cho đến nay, nhưng tôi sẽ giải thích một cách tổng quát. Đầu tiên, chúng ta cần định nghĩa khái niệm "phân số (divisor)", về cơ bản là một cách khác để biểu diễn các hàm hoạt động trên các điểm của đường elliptic. Một phân số của một hàm cơ bản tính toán số lượng điểm mà hàm có bao nhiêu điểm không và bao nhiêu điểm có giá trị vô hạn. Để hiểu rõ hơn, chúng ta hãy xem một vài ví dụ. Giả sử chúng ta chọn một điểm P = (Px, Py), sau đó xem xét hàm sau:

f(x, y) = x − P_x

Phân số của nó là [P] + [−P] − 2 * [O] (ở đây dấu ngoặc vuông được sử dụng để biểu thị một điểm xuất hiện trong tập hợp các điểm không và các điểm có giá trị vô hạn của hàm, chứ không phải chính điểm đó; [P] + [Q] và [P + Q] không giống nhau). Lý do như sau:

• Hàm này có giá trị bằng không tại điểm P, vì x nhận giá trị Px, vì vậy x − Px = 0
• Hàm này cũng có giá trị bằng không tại điểm −P, vì −P và P có cùng tọa độ x
• Hàm này có giá trị vô hạn khi x tiến tới vô cùng, vì vậy chúng ta nói rằng hàm này có giá trị vô hạn tại điểm O. Tính toán điểm vô cùng này cần tính hai lần, vì vậy O cần nhân với hệ số -2 (dấu âm là vì nó là điểm vô cùng khác với điểm không, 2 là vì nó cần được tính hai lần).

Lý do tính toán khoảng như sau: vì phương trình của đường cong này là x³ = y² + b, khi x tăng lên, để y² đạt được quy mô tương ứng, tốc độ tăng của y cần khoảng gấp 1.5 lần x. Do đó, nếu một hàm tuyến tính chỉ chứa x, thì hệ số vô hạn của nó là 2, nhưng nếu nó chứa y, thì hệ số đó phải là 3.

Bây giờ hãy xem xét một hàm của một đường thẳng:

ax + by + c = 0

Trong đó a, b, c được chọn để đường thẳng này đi qua điểm P và điểm Q. Theo cách hoạt động của phép cộng trên đường elliptic, nó cũng sẽ đi qua điểm −P−Q. Bởi vì nó tiến tới vô cùng sẽ phụ thuộc vào cả x và y, nên phân số là [P]+ [Q] + [−P−Q] − 3 * [O].

Chúng ta biết rằng tất cả "hàm hữu tỷ" (có nghĩa là các hàm được định nghĩa thông qua một số phép cộng, trừ, nhân, chia hữu hạn trên tọa độ điểm) tương ứng duy nhất với một phân số, tối đa chỉ là nhân với một hằng số (có nghĩa là nếu hai hàm F và G có cùng một phân số, thì chắc chắn tồn tại một hằng số k sao cho F = G * k).

Đối với bất kỳ hai hàm nào F và G, phân số của (F * G) bằng tổng của phân số của F và G (trong sách giáo khoa toán học bạn sẽ thấy (F * G) = (F) + (G)), vì vậy ví dụ f(x, y) = P_x − x, thì (f³) = 3 * [P] + 3 * [−P] − 6 * [O]; P và −P được tính ba lần vì trong một ý nghĩa toán học cụ thể, f³ sẽ "tiến gần 0 nhanh gấp ba lần".

Lưu ý rằng có một định lý nói rằng nếu bạn bỏ dấu ngoặc vuông của một phân số nào đó, thì kết quả của các phép toán điểm đó chắc chắn sẽ là O (thực hiện theo quy tắc [P] + [Q] + [−P−Q] − 3 * [O] sẽ cho ra P + Q − P − Q − 3 * O = O), và bất kỳ phân số nào có tính chất này sẽ là phân số của hàm đó.

Bây giờ chúng ta có thể bắt đầu xem xét các đối tượng Tate. Hãy xem xét các hàm được định nghĩa bằng phân số sau:

• (F_P) = n * [P] − n * [O], trong đó n là bậc của G1, tức là đối với tất cả P, n * P = O
• (F_Q) = n * [Q] − n * [O]
• (g) = [P + Q] − [P] − [Q] + [O]

Bây giờ, hãy xem xét tích FP * FQ * g^n. Phân số của nó là:

n * [P] − n * [O] + n * [Q] − n * [O] + n * [P + Q] − n * [P] − n * [Q] + n * [O]

Rút gọn sẽ cho ra:

n * [P + Q] − n * [O]

Lưu ý rằng định dạng của phân số này tương ứng với phân số của FP và FQ. Do đó, có FP * FQ * g^n = F_(P + Q).

Bây giờ thực hiện thêm một thao tác gọi là "lũy thừa cuối cùng (final exponentiation)", lấy kết quả của phép toán trước đó (FP, FQ, v.v.) nâng lên lũy thừa z = (p¹² − 1) / n, trong đó p¹² − 1 là bậc của nhóm nhân trong Fp¹² (nói cách khác, đối với tất cả x ϵ Fp¹², x^(p¹² − 1) = 1). Lưu ý rằng nếu bạn áp dụng lũy thừa này lên bất kỳ kết quả nào đã là n lần lũy thừa, bạn sẽ nhận được một phần tử có lũy thừa (p¹² − 1), kết quả sẽ trở thành 1. Do đó, sau bước lũy thừa cuối cùng, g^n sẽ bị loại bỏ, và chúng ta sẽ có FP^z * FQ^z = F_(P + Q)^z. Như vậy, một phần của tính chất song tuyến tính đã được thiết lập.

Bây giờ nếu bạn muốn xây dựng một hàm mà sẽ song tuyến tính trên cả hai tham số, bạn cần toán học phức tạp hơn, vì vậy những gì cần làm không chỉ là tính FP, mà còn phải tính phân số của FP, và tiếp tục như vậy sẽ dẫn đến đối tượng Tate hoàn chỉnh. Để chứng minh nhiều kết luận hơn, bạn cần hiểu một số khái niệm như "tương đương tuyến tính (linear equivalence)" và Weil reciprocity. Những khái niệm chi tiết này có thể được tìm thấy tại đây và tại đây.

Và đây là một phiên bản sửa đổi của đối tượng Tate - Optimal Ate Pairing. Mã này cũng thực hiện việc tính toán F_p bằng thuật toán Miller.

Thực tế, việc sử dụng các đối tượng như vậy giống như cầm một thanh kiếm hai lưỡi: một mặt, điều này có nghĩa là chúng ta có thể sử dụng các đối tượng này để thực hiện các thỏa thuận khác nhau, đồng thời cũng có nghĩa là chúng ta phải đặc biệt cẩn thận khi chọn đường elliptic nào để sử dụng.

Mỗi đường elliptic đều có một giá trị gọi là bậc nhúng (embedding degree) - số nguyên dương nhỏ nhất k sao cho p^k − 1 là bội số của n (p là số nguyên tố được sử dụng trong trường, và n là bậc của đường cong). Trong các trường đã đề cập ở trên, k = 12, trong mật mã đường elliptic truyền thống (không quan tâm đến các đối tượng) thường sử dụng các trường có bậc nhúng rất lớn, lớn đến mức việc tính toán các đối tượng trở nên không khả thi về mặt tính toán. Tuy nhiên, khi chúng ta không chú ý, rất có thể chúng ta sẽ xây dựng các trường có k = 4 hoặc thậm chí k = 1.

Khi k = 1, "vấn đề logarit rời rạc" trên đường elliptic (trong trường hợp chỉ biết điểm P = G * p, tính giá trị p; tức là vấn đề bạn cần giải quyết khi "bẻ khóa" khóa riêng của đường elliptic) có thể suy giảm thành một vấn đề tương đối đơn giản trên F_p (phương pháp này được gọi là tấn công MOV); việc sử dụng một đường elliptic có bậc nhúng lớn hơn hoặc bằng 12 sẽ đảm bảo rằng sự suy giảm này không khả thi, hoặc vấn đề suy giảm trở nên phức tạp ít nhất cũng khó khăn như việc tính toán khóa riêng từ khóa công khai bằng phương pháp "bình thường". Hiện tại, tất cả các tham số đường cong tiêu chuẩn đã được kiểm tra cẩn thận, không bị ảnh hưởng bởi vấn đề này.