Logo Zephyrnet

[Gương] Khám phá các cặp đường cong Elliptic

Ngày:

Vitalik Buterin thông qua Blog Vitalik Buterin

Đây là sự phản ánh của bài viết tại https://medium.com/@VitalikButerin/khám phá-elliptic-curve-pairings-c73c1864e627

Cảnh báo kích hoạt: math.

Một trong những nguyên tắc mã hóa quan trọng đằng sau các cấu trúc khác nhau, bao gồm chữ ký ngưỡng xác định, zk-SNARK và các dạng chứng minh không có kiến ​​thức đơn giản khác là ghép nối đường cong elip. Các cặp đường cong elip (hoặc “bản đồ song tuyến tính”) là sự bổ sung gần đây cho lịch sử 30 năm sử dụng đường cong elip cho các ứng dụng mật mã bao gồm mã hóa và chữ ký số; các cặp đôi giới thiệu một dạng “phép nhân được mã hóa”, mở rộng đáng kể những gì các giao thức dựa trên đường cong elip có thể thực hiện. Mục đích của bài viết này là đi sâu vào các cặp đường cong elip một cách chi tiết và giải thích phác thảo chung về cách chúng hoạt động.

Bạn không thể hiểu mọi thứ ở đây ngay lần đầu đọc nó, hoặc thậm chí là lần thứ mười; thứ này thực sự khó khăn. Nhưng hy vọng bài viết này sẽ cung cấp cho bạn ít nhất một chút ý tưởng về những gì đang diễn ra.

Bản thân các đường cong elip là một chủ đề không hề đơn giản để hiểu và bài viết này thường cho rằng bạn biết chúng hoạt động như thế nào; nếu không, tôi giới thiệu bài viết này ở đây như một phần mở đầu: https://blog.cloudflare.com/a-relatively-easy-to-understand-primer-on-elliptic-curve-cryptography/. Tóm tắt nhanh, mật mã đường cong elip liên quan đến các đối tượng toán học được gọi là “điểm” (đây là các điểm hai chiều theo nghĩa đen có tọa độ (�,�), với các công thức đặc biệt để cộng và trừ chúng (tức là để tính tọa độ của �= �+�) và bạn cũng có thể nhân một điểm với một số nguyên (ví dụ: �⋅�=�+�+…+�, mặc dù có cách tính nhanh hơn nhiều nếu � lớn).

Đây là cách cộng điểm trông như thế nào về mặt đồ họa.

Tồn tại một điểm đặc biệt gọi là “điểm ở vô cực” (�), tương đương với số 0 trong số học điểm; luôn luôn xảy ra trường hợp �+�=�. Ngoài ra, một đường cong có một “gọi món“; tồn tại một số � sao cho �⋅�=� với mọi � (và tất nhiên, �⋅(�+1)=�,�⋅(7⋅�+5)=�⋅5, v.v.). Ngoài ra còn có một số “điểm tạo” � được mọi người đồng ý, được hiểu là đại diện cho số 1 theo một nghĩa nào đó. Về mặt lý thuyết, bất kỳ điểm nào trên đường cong (ngoại trừ �) đều có thể là �; tất cả những gì quan trọng là � đã được chuẩn hóa.

Các cặp đôi tiến một bước xa hơn ở chỗ chúng cho phép bạn kiểm tra một số loại phương trình phức tạp hơn trên các điểm trên đường cong elip — ví dụ: nếu �=�⋅�,�=�⋅� và �=�⋅�, bạn có thể kiểm tra xem hoặc không phải �⋅�=�, chỉ có �,� và � làm đầu vào. Điều này có vẻ như sự đảm bảo an ninh cơ bản của các đường cong elip đang bị phá vỡ, vì thông tin về � bị rò rỉ khi chỉ biết P, nhưng hóa ra là sự rò rỉ được kiểm soát chặt chẽ - cụ thể là, bài toán quyết định Diffie Hellman thì dễ, nhưng bài toán Diffie Hellman tính toán (biết � và � trong ví dụ trên, máy tính �=�⋅�⋅�) và vấn đề logarit rời rạc (khôi phục � từ �) vẫn không khả thi về mặt tính toán (ít nhất, nếu như trước đó).

Cách thứ ba để xem tác dụng của các cặp, và cách có lẽ rõ ràng nhất đối với hầu hết các trường hợp sử dụng mà chúng ta đang đề cập, đó là nếu bạn xem các điểm trên đường cong elip dưới dạng số được mã hóa một chiều (nghĩa là ���� ���(�)=�⋅�=�), thì trong khi phép toán đường cong elip truyền thống cho phép bạn kiểm tra tuyến tính các ràng buộc về các số (ví dụ: nếu �=�⋅�,�=�⋅� và �=�⋅�, kiểm tra 5⋅�+7⋅�=11⋅� là có thật không kiểm tra 5⋅�+7⋅�=11⋅�), việc ghép đôi cho phép bạn kiểm tra bậc hai các ràng buộc (ví dụ: kiểm tra �(�,�)⋅�(�,�⋅5)=1 là có thật không kiểm tra xem �⋅�+5=0). Và đi lên bậc hai là đủ để chúng ta làm việc với các dấu hiệu ngưỡng xác định, các chương trình số học bậc hai và tất cả những thứ hay ho khác.

Bây giờ, toán tử �(�,�) thú vị mà chúng tôi đã giới thiệu ở trên là gì? Đây là sự ghép đôi. Các nhà toán học đôi khi còn gọi nó là bản đồ song tuyến; từ “song tuyến” ở đây về cơ bản có nghĩa là nó thỏa mãn các ràng buộc:

�(�,�+�)=�(�,�)⋅�(�,�)

�(�+�,�)=�(�,�)⋅�(�,�)

Lưu ý rằng + và ⋅ có thể là toán tử tùy ý; khi bạn đang tạo ra những loại đối tượng toán học mới lạ mắt, đại số trừu tượng không quan tâm đến + và ⋅ như thế nào xác định, miễn là chúng nhất quán theo những cách thông thường, vd. �+�=�+�,(�⋅�)⋅�=�⋅(�⋅�) và (�⋅�)+(�⋅�)=(�+�)⋅�.

Nếu �, �, � và � đơn giản số, thì việc ghép nối đơn giản thật dễ dàng: chúng ta có thể thực hiện �(�,�)=2��. Sau đó, chúng ta có thể thấy:

�(3,4+5)=23⋅9=227

�(3,4)⋅�(3,5)=23⋅4⋅23⋅5=212⋅215=227

Đó là song tuyến tính!

Tuy nhiên, các cặp đơn giản như vậy không phù hợp với mật mã vì đối tượng mà chúng hoạt động là các số nguyên đơn giản và quá dễ phân tích; số nguyên giúp dễ dàng chia, tính logarit và thực hiện nhiều phép tính khác; các số nguyên đơn giản không có khái niệm về “khóa chung” hay “hàm một chiều”. Ngoài ra, với cách ghép nối được mô tả ở trên, bạn có thể quay ngược lại – biết � và biết �(�,�), bạn có thể chỉ cần tính phép chia và logarit để xác định �. Chúng tôi muốn các đối tượng toán học càng gần với “hộp đen” càng tốt, nơi bạn có thể cộng, trừ, nhân và chia, nhưng không làm gì khác. Đây là nơi các đường cong elip và các cặp đường cong elip xuất hiện.

Hóa ra là có thể tạo một bản đồ song tuyến tính trên các điểm của đường cong elip - nghĩa là đưa ra một hàm �(�,�) trong đó đầu vào � và � là các điểm của đường cong elip, và trong đó đầu ra là cái được gọi là (��)12 phần tử (ít nhất là trong trường hợp cụ thể mà chúng tôi sẽ đề cập ở đây; các chi tiết cụ thể khác nhau tùy thuộc vào chi tiết của đường cong, sẽ nói thêm về điều này sau), nhưng phép toán đằng sau cách làm này khá phức tạp.

Đầu tiên, hãy bao gồm các trường chính và trường mở rộng. Đường cong elip đẹp trong hình trước đó trong bài đăng này chỉ trông giống như vậy nếu bạn giả sử rằng phương trình đường cong được xác định bằng cách sử dụng các số thực thông thường. Tuy nhiên, nếu chúng ta thực sự sử dụng số thực thông thường trong mật mã, thì bạn có thể sử dụng logarit để “ngược lại” và mọi thứ sẽ hỏng; Ngoài ra, lượng không gian cần thiết để thực sự lưu trữ và biểu diễn các con số có thể tăng tùy ý. Do đó, thay vào đó chúng tôi sử dụng số trong một trường nguyên tố.

Trường nguyên tố bao gồm tập hợp các số 0,1,2…�−1, trong đó � là số nguyên tố và các phép toán khác nhau được định nghĩa như sau:

�+�:(�+�) % �

�⋅�:(�⋅�) % �

�−�:(�−�) % �

�/�:(�⋅��−2) % �

Về cơ bản, mọi phép toán đều được thực hiện theo modulo � (xem tại đây để giới thiệu về toán học mô-đun). Phép chia là trường hợp đặc biệt; thông thường, 32 không phải là số nguyên và ở đây chúng tôi chỉ muốn xử lý số nguyên, vì vậy thay vào đó chúng tôi cố gắng tìm số � sao cho �⋅2=3, trong đó ⋅ tất nhiên đề cập đến phép nhân mô-đun như được định nghĩa ở trên. Nhờ vào Định lý nhỏ Fermat, thủ thuật lũy thừa trình bày ở trên thực hiện được công việc đó, nhưng cũng có một cách nhanh hơn để thực hiện việc đó là sử dụng Thuật toán Euclid mở rộng. Giả sử �=7; Dưới đây là một vài 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⋅25) % 7=5

5⋅2=10 % 7=3

Nếu bạn thử nghiệm loại toán này, bạn sẽ nhận thấy rằng nó hoàn toàn nhất quán và đáp ứng tất cả các quy tắc thông thường. Hai ví dụ cuối ở trên cho thấy (�/�)⋅�=�; bạn cũng có thể thấy rằng (�+�)+�=�+(�+�),(�+�)⋅�=�⋅�+�⋅�, và tất cả các đẳng thức đại số trung học khác mà bạn biết và yêu thích vẫn tiếp tục cũng đúng. Trong các đường cong elip trong thực tế, các điểm và phương trình thường được tính trong trường nguyên tố.

Bây giờ, hãy nói về trường mở rộng. Có thể bạn đã từng thấy trường mở rộng trước đây; Ví dụ phổ biến nhất mà bạn gặp trong sách giáo khoa toán là trường số phức, trong đó trường số thực được “mở rộng” với phần tử bổ sung −1=�. Về cơ bản, các trường mở rộng hoạt động bằng cách lấy một trường hiện có, sau đó “phát minh” ra một phần tử mới và xác định mối quan hệ giữa phần tử đó và các phần tử hiện có (trong trường hợp này là �2+1=0), đảm bảo rằng phương trình này không đúng đối với bất kỳ số nào nằm trong trường ban đầu và xem xét tập hợp tất cả các kết hợp tuyến tính của các phần tử của trường ban đầu và phần tử mới mà bạn vừa tạo.

Chúng ta cũng có thể mở rộng các trường nguyên tố; ví dụ: chúng ta có thể mở rộng trường nguyên tố mod7 mà chúng ta đã mô tả ở trên bằng �, và sau đó chúng ta có thể thực hiện:

(2+3�)+(4+2�)=6+5�

(5+2�)+3=1+2�

(6+2�)⋅2=5+4�

4�⋅(2+�)=3+�

Kết quả cuối cùng đó có thể hơi khó tìm ra; điều đã xảy ra là trước tiên chúng ta phân tích tích thành 4�⋅2+4�⋅�, được 8�−4, và sau đó vì chúng ta đang làm phép toán mod7 nên nó trở thành �+3. Để chia ta làm:

�/�:(�⋅�(�2−2)) % �

Lưu ý rằng số mũ của định lý nhỏ Fermat bây giờ là �2 thay vì �, mặc dù một lần nữa nếu muốn hiệu quả hơn, chúng ta cũng có thể mở rộng Thuật toán Euclide Mở rộng để thực hiện công việc này. Lưu ý rằng ��2−1=1 với bất kỳ � nào trong trường này, vì vậy chúng ta gọi �2−1 là “thứ tự của nhóm nhân trong trường”.

Với số thực thì Định lý cơ bản của đại số đảm bảo rằng phần mở rộng bậc hai mà chúng ta gọi là số phức là “hoàn chỉnh” — bạn không thể mở rộng nó thêm nữa, bởi vì đối với bất kỳ mối quan hệ toán học nào (ít nhất, bất kỳ mối quan hệ toán học nào được xác định bởi một công thức đại số) mà bạn có thể nghĩ ra giữa một số phần tử mới � và các số phức hiện có, có thể tìm ra ít nhất một số phức thỏa mãn mối quan hệ đó. Tuy nhiên, với các trường nguyên tố, chúng tôi không gặp phải vấn đề này và vì vậy chúng tôi có thể tiến xa hơn và tạo các phần mở rộng bậc ba (trong đó mối quan hệ toán học giữa một số phần tử mới � và các phần tử trường hiện có là một phương trình bậc ba, vì vậy 1,� và �2 là tất cả đều độc lập tuyến tính với nhau), phần mở rộng bậc cao hơn, phần mở rộng của phần mở rộng, v.v. Và chính những loại số phức mô-đun tăng áp này mà các cặp đường cong elip được xây dựng trên đó.

Đối với những người muốn xem phép toán chính xác liên quan đến việc thực hiện tất cả các hoạt động này được viết bằng mã, các trường nguyên tố và phần mở rộng trường được triển khai tại đây: https://github.com/ethereum/py_pairing/blob/master/py_ecc/bn128/bn128_field_elements.py

Bây giờ, chuyển sang ghép cặp đường cong elip. Ghép nối đường cong elip (hay đúng hơn là dạng ghép nối cụ thể mà chúng ta sẽ khám phá ở đây; cũng có các loại ghép nối khác, mặc dù logic của chúng khá giống nhau) là bản đồ �2×�1→��, trong đó:

  • �1 là một đường cong elip, trong đó các điểm thỏa mãn phương trình có dạng �2=�3+� và cả hai tọa độ đều là phần tử của �� (tức là chúng là các số đơn giản, ngoại trừ số học được thực hiện theo modulo một số nguyên tố)
  • �2 là một đường cong elip, trong đó các điểm thỏa mãn phương trình giống như �1, ngoại trừ trường hợp tọa độ là các phần tử của (��)12 (tức là chúng là các số phức siêu nạp mà chúng ta đã nói ở trên; chúng ta định nghĩa một “số ma thuật” mới ” �, được xác định bởi đa thức bậc 12 như �12−18⋅�6+82=0)
  • �� là loại đối tượng mà kết quả của đường cong elip đi vào. Trong các đường cong mà chúng ta đang xem xét, �� là (��)12 (cùng số phức siêu nạp như được sử dụng trong �2)

Thuộc tính chính mà nó phải thỏa mãn là tính song tuyến, trong ngữ cảnh này có nghĩa là:

  • �(�,�+�)=�(�,�)⋅�(�,�)
  • �(�+�,�)=�(�,�)⋅�(�,�)

Có hai tiêu chí quan trọng khác:

  • Khả năng tính toán hiệu quả (ví dụ: chúng ta có thể thực hiện ghép nối dễ dàng bằng cách lấy logarit rời rạc của tất cả các điểm và nhân chúng với nhau, nhưng điều này khó về mặt tính toán như việc phá vỡ mật mã đường cong elip ngay từ đầu, vì vậy nó không được tính)
  • Không thoái hóa (chắc chắn, bạn chỉ có thể xác định �(�,�)=1, nhưng đó không phải là một cặp đôi đặc biệt hữu ích)

Vì vậy, làm thế nào để chúng tôi làm điều này?

Bài toán đằng sau lý do tại sao các hàm ghép đôi hoạt động khá phức tạp và liên quan đến khá nhiều đại số nâng cao thậm chí còn vượt xa những gì chúng ta đã thấy cho đến nay, nhưng tôi sẽ cung cấp một bản tóm tắt. Trước hết chúng ta cần xác định khái niệm dải phân cách, về cơ bản là một cách khác để biểu diễn hàm số trên các điểm trên đường cong elip. Ước số của một hàm về cơ bản là đếm các số 0 và các số vô cực của hàm. Để biết điều này có nghĩa gì, chúng ta hãy xem qua một vài ví dụ. Chúng ta hãy sửa một số điểm �=(��,��), và xét hàm số sau:

�(�,�)=�−��

Ước số là [�]+[−�]−2⋅[�] (dấu ngoặc vuông được dùng để biểu thị thực tế mà chúng ta đang đề cập đến sự có mặt của điểm � trong tập các số 0 và vô cực của hàm số, không phải bản thân điểm P; [�]+[�] là không tương tự như [�+�]). Lý do là như sau:

  • Hàm số bằng 0 tại �, vì � is ��, vậy �−��=0
  • Hàm số bằng 0 tại −�, vì −� và � có cùng tọa độ �
  • Hàm số tiến tới vô cùng khi � tiến tới vô cùng, vì vậy ta nói hàm số này bằng vô cùng tại �. Có một lý do kỹ thuật tại sao số vô cực này cần được tính hai lần, vì vậy � được cộng với “bội số” là −2 (âm vì nó là số vô cực chứ không phải số XNUMX, hai vì cách tính kép này).

Lý do kỹ thuật đại khái là thế này: vì phương trình của đường cong là �3=�2+�,� tiến tới vô cực “nhanh hơn 1.5 lần” so với � để �2 theo kịp �3; do đó, nếu một hàm tuyến tính chỉ bao gồm � thì nó được biểu diễn dưới dạng vô cực của bội số 2, nhưng nếu nó bao gồm � thì nó được biểu diễn dưới dạng vô cực của bội số 3.

Bây giờ, hãy xem xét một “hàm đường”:

��+��+�=0

Trong đó �, � và � được chọn cẩn thận sao cho đường thẳng đi qua các điểm � và �. Bởi vì cách thức hoạt động của phép cộng đường cong elip (xem sơ đồ ở trên cùng), điều này cũng có nghĩa là nó đi qua −�−�. Và nó tiến tới vô cùng phụ thuộc vào cả � và �, nên số chia trở thành [�]+[�]+[−�−�]−3⋅[�].

Chúng ta biết rằng mọi “hàm số hữu tỉ” (tức là một hàm chỉ được xác định bằng cách sử dụng một số hữu hạn các phép toán +,−,⋅ và / trên tọa độ của điểm) tương ứng duy nhất với một số ước số, cho đến phép nhân với một hằng số (tức là. nếu hai hàm � và � có cùng ước số thì �=�⋅� với một hằng số � nào đó).

Với hai hàm số � và � bất kỳ, ước số của �⋅� bằng ước số của � cộng với ước số của � (trong sách giáo khoa toán, bạn sẽ thấy (�⋅�)=(�)+(�)), vì vậy, ví dụ nếu �(�,�)=��−�, thì (�3)=3⋅[�]+3⋅[−�]−6⋅[�]; � và −� được "đếm ba lần" để giải thích thực tế là �3 tiến tới 0 tại những điểm đó "nhanh gấp ba lần" theo một nghĩa toán học nhất định.

Lưu ý rằng có một định lý phát biểu rằng nếu bạn “bỏ dấu ngoặc vuông” khỏi ước số của một hàm, thì tổng các điểm phải bằng �([�]+[�]+[−�−�]−3⋅[ �] rõ ràng phù hợp, vì �+�−�−�−3⋅�=�), và bất kỳ ước số nào có tính chất này đều là ước số của một hàm số.

Bây giờ, chúng ta đã sẵn sàng xem xét các cặp Tate. Hãy xem xét các hàm sau, được xác định thông qua ước số của chúng:

  • (��)=�⋅[�]−�⋅[�], trong đó � là cấp của �1, tức là. �⋅�=� với mọi �
  • (��)=�⋅[�]−�⋅[�]
  • (�)=[�+�]−[�]−[�]+[�]

Bây giờ chúng ta cùng xem sản phẩm ��⋅��⋅��. Số chia là:

�⋅[�]−�⋅[�]+�⋅[�]−�⋅[�]+�⋅[�+�]−�⋅[�]−�⋅[�]+�⋅[�]

Điều này đơn giản hóa gọn gàng để:

�⋅[�+�]−�⋅[�]

Lưu ý rằng ước số này có cùng định dạng với ước số cho �� và �� ở trên. Do đó, ��⋅��⋅��=��+�.

Bây giờ, chúng tôi giới thiệu một quy trình được gọi là bước “lũy thừa cuối cùng”, trong đó chúng tôi lấy kết quả của các hàm trên (��,��, v.v.) và nâng nó lên lũy thừa �=(�12−1)/�, trong đó �12−1 là bậc của nhóm nhân trong (��)12 (tức là với bất kì �∈(��)12,�(�12−1)=1). Lưu ý rằng nếu bạn áp dụng phép lũy thừa này cho bất kỳ kết quả nào có Đã được nâng lên lũy thừa của �, bạn nhận được lũy thừa theo lũy thừa của �12−1, do đó kết quả chuyển thành 1. Do đó, sau khi lũy thừa cuối cùng, �� hủy bỏ và chúng ta nhận được ���⋅���=( ��+�)�. Có một số tính song tuyến đối với bạn.

Bây giờ, nếu bạn muốn tạo một hàm song tuyến tính ở cả hai đối số, bạn cần đi vào phép toán phức tạp hơn, trong đó thay vì lấy trực tiếp �� của một giá trị, bạn lấy �� của một dải phân cách, và đó là nơi bắt nguồn của “ghép nối Tate” đầy đủ. Để chứng minh thêm một số kết quả, bạn phải xử lý các khái niệm như “sự tương đương tuyến tính” và “sự tương hỗ của Weil”, và hố thỏ tiếp tục từ đó. Bạn có thể tìm thêm tài liệu đọc về tất cả những điều này tại đâytại đây.

Để triển khai phiên bản sửa đổi của ghép nối Tate, được gọi là ghép nối Ate tối ưu, xem tại đây. Mã thực hiện Thuật toán Miller, cần thiết để tính ��.

Lưu ý rằng thực tế việc ghép đôi như thế này có thể xảy ra phần nào là một điều may mắn lẫn lộn: một mặt, điều đó có nghĩa là tất cả các giao thức mà chúng ta có thể thực hiện với việc ghép nối đều có thể thực hiện được, nhưng cũng có nghĩa là chúng ta phải cẩn thận hơn về những đường cong elip nào chúng tôi sử dụng.

Mỗi đường cong elip đều có một giá trị gọi là mức độ nhúng; về cơ bản, � nhỏ ​​nhất sao cho ��−1 là bội số của � (trong đó � là số nguyên tố được sử dụng cho trường và � là thứ tự đường cong). Trong các trường ở trên, �=12 và trong các trường được sử dụng cho ECC truyền thống (tức là nơi chúng tôi không quan tâm đến việc ghép nối), mức độ nhúng thường cực kỳ lớn, đến mức không thể tính toán được các cặp ghép; tuy nhiên, nếu không cẩn thận thì chúng ta có thể tạo ra các trường có �=4 hoặc thậm chí 1.

Nếu �=1 thì bài toán “logarit rời rạc” đối với đường cong elip (về cơ bản là khôi phục � chỉ biết điểm �=�⋅�, bài toán mà bạn phải giải để “bẻ khóa” khóa riêng của đường cong elip) có thể được giảm bớt thành một bài toán tương tự trên ��, trong đó bài toán trở nên dễ hơn nhiều (đây được gọi là Cuộc tấn công MOV); sử dụng các đường cong có mức độ nhúng từ 12 trở lên đảm bảo rằng mức giảm này không khả dụng hoặc việc giải quyết vấn đề nhật ký rời rạc qua kết quả ghép nối ít nhất cũng khó như việc khôi phục khóa riêng từ khóa chung “theo cách thông thường” (tức là. không thể tính toán được). Đừng lo; tất cả các thông số đường cong tiêu chuẩn đã được kiểm tra kỹ lưỡng về vấn đề này.

Hãy theo dõi lời giải thích toán học về cách hoạt động của zk-SNARK, sắp ra mắt.

Đặc biệt cảm ơn Christian Reitwiessner, Ariel Gabizon (từ Zcash) và Alfred Menezes vì ​​đã xem xét và sửa chữa.

tại chỗ_img

Tin tức mới nhất

tại chỗ_img