Phép cộng đường cong elip Python
|
Phần này cung cấp ví dụ tính toán đại số cộng hai điểm phân biệt trên một đường cong elip Bây giờ chúng ta có các công thức đại số để tính toán phép toán cộng trên các đường cong elip. Hãy thử chúng với một số ví dụ Ví dụ đầu tiên là cộng 2 điểm phân biệt với nhau, lấy từ "Elliptic Curve Cryptography. một lời giới thiệu nhẹ nhàng" của Andrea Corbellini tại andrea. corbellini. name/2015/05/17 /elliptic-curve-cryptography-a-gentle-introduction/ Phần này cung cấp một ví dụ hướng dẫn về cách thực hiện thao tác cộng điểm trên một đường cong elip cho trước bằng thư viện tinyec Python Nếu bạn muốn thực hiện thao tác cộng điểm trên đường cong elip với thư viện tinyec Python, bạn phải thực hiện theo ba bước 1. Tạo đường cong elip. Ví dụ >>> import tinyec.ec as ec >>> s = ec.SubGroup(p=97,g=(0,0),n=1,h=1) >>> c = ec.Curve(a=2,b=3,field=s,name='p97a2b3') 2. Tạo sinh thái. Chỉ các đối tượng có tọa độ x và y của chúng một ec. đối tượng đường cong. Ví dụ >>> p = ec.Point(curve=c,x=3,y=6) >>> q = ec.Point(curve=c,x=80,y=10) >>> print(p) (3, 6) on "p97a2b3" => y^2 = x^3 + 2x + 3 (mod 97) >>> print(q) (80, 10) on "p97a2b3" => y^2 = x^3 + 2x + 3 (mod 97) 3. Thực hiện phép cộng điểm với toán tử "+". Ví dụ >>> r = p + q >>> print(r) (80, 87) on "p97a2b3" => y^2 = x^3 + 2x + 3 (mod 97) Vâng. Việc cộng điểm được thực hiện chính xác, bạn có thể xác minh thủ công Nếu bạn tạo một ec. Điểm đối tượng có điểm đường cong không hợp lệ, tinyec sẽ cho bạn biết điểm nằm ngoài đường cong Lần trước chúng ta đã thấy phiên bản hình học của thuật toán cộng điểm trên đường cong elip. Chúng tôi đã đi khá sâu vào cài đặt chính thức cho nó (không gian xạ ảnh $ \mathbb{P}^2$), và chúng tôi đã dành nhiều thời gian để nói về cách xác định đúng đối tượng “không” trong đường cong elip sao cho Với sự hiểu biết đó, giờ đây cuối cùng chúng ta cũng chuyển sang viết mã và viết các lớp cho các đường cong và điểm và triển khai thuật toán cộng. Như thường lệ, tất cả mã chúng tôi đã viết trong bài đăng này đều có sẵn trên trang Github của blog này Điểm và đường congMọi sinh viên lập trình nhập môn có lẽ đã viết chương trình sau bằng một số ngôn ngữ cho một lớp đại diện cho một điểm class Point(object):
def __init__(self, x, y):
self.x = x
self.y = y
Đó là lớp không cần thiết đơn giản nhất có thể. một giá trị x và y được khởi tạo bởi hàm tạo (và trong Python tất cả các biến thành viên đều công khai) Chúng tôi muốn lớp này biểu diễn một điểm trên đường cong elip và làm quá tải các toán tử cộng và phủ định để chúng tôi có thể làm những việc như thế này p1 = Point(3,7) p2 = Point(4,4) p3 = p1 + p2 Nhưng như chúng ta đã thảo luận khá lâu, các toán tử cộng phụ thuộc vào các đặc điểm của đường cong elip mà chúng đang chạy (chúng ta phải vẽ các đường và cắt nó với đường cong). Có một số cách chúng ta có thể làm điều này xảy ra, nhưng để làm cho mã sử dụng các lớp này đơn giản nhất có thể, chúng ta sẽ có mỗi điểm chứa một tham chiếu đến đường cong mà chúng xuất phát. Vì vậy, chúng ta cần một lớp đường cong Thực ra, nó khá đơn giản vì lớp chỉ là một trình giữ chỗ cho các hệ số của phương trình xác định. Chúng ta giả sử rằng phương trình đã ở dạng chuẩn tắc Weierstrass, nhưng nếu không, người ta có thể thực hiện cả đống phép tính đại số để đưa nó về dạng đó (và bạn có thể thấy quy trình phức tạp như thế nào trong báo cáo ngắn này hoặc trang 115 ( . 21) của cuốn sách này). Để an toàn, chúng tôi sẽ thêm một số kiểm tra bổ sung để đảm bảo đường cong trơn tru class EllipticCurve(object):
def __init__(self, a, b):
# assume we're already in the Weierstrass form
self.a = a
self.b = b
self.discriminant = -16 * (4 * a*a*a + 27 * b * b)
if not self.isSmooth():
raise Exception("The curve %s is not smooth!" % self)
def isSmooth(self):
return self.discriminant != 0
def testPoint(self, x, y):
return y*y == x*x*x + self.a * x + self.b
def __str__(self):
return 'y^2 = x^3 + %Gx + %G' % (self.a, self.b)
def __eq__(self, other):
return (self.a, self.b) == (other.a, other.b)
Và đây là một số ví dụ về tạo đường cong >>> EllipticCurve(a=17, b=1) y^2 = x^3 + 17x + 1 >>> EllipticCurve(a=0, b=0) Traceback (most recent call last): [...] Exception: The curve y^2 = x^3 + 0x + 0 is not smooth! Vì vậy, chúng tôi đã có nó. Bây giờ khi chúng ta dựng một Điểm, chúng ta thêm đường cong làm đối số bổ sung và kiểm tra an toàn để đảm bảo rằng điểm đang được dựng nằm trên đường cong elip đã cho class Point(object):
def __init__(self, curve, x, y):
self.curve = curve # the curve containing this point
self.x = x
self.y = y
if not curve.testPoint(x,y):
raise Exception("The point %s is not on the given curve %s" % (self, curve))
Lưu ý rằng lần kiểm tra cuối cùng này sẽ phục vụ như một bài kiểm tra đơn vị thô cho tất cả các ví dụ của chúng tôi. Nếu chúng ta làm sai thì nhiều khả năng điểm “đã thêm” sẽ không nằm trên đường cong. Tất nhiên, cần phải kiểm tra chính xác hơn để chống đạn, nhưng chúng tôi để lại các bài kiểm tra rõ ràng cho người đọc như một cái cớ để họ làm quen với các phương trình Vài ví dụ ________số 8Trước khi tiếp tục và thực hiện phép cộng và các hàm liên quan, chúng ta cần quyết định cách chúng ta muốn biểu diễn điểm lý tưởng $ [0. 1. 0]$. Chúng tôi có hai lựa chọn. Đầu tiên là làm mọi thứ trong tọa độ xạ ảnh và xác định toàn bộ hệ thống để thực hiện đại số xạ ảnh. Xem xét chúng ta chỉ có một điểm để lo lắng, điều này có vẻ như quá mức cần thiết (nhưng có thể thú vị). Tùy chọn thứ hai và tùy chọn chúng tôi sẽ chọn là có một lớp con đặc biệt của Điểm đại diện cho điểm lý tưởng class Ideal(Point):
def __init__(self, curve):
self.curve = curve
def __str__(self):
return "Ideal"
Lưu ý thừa kế được biểu thị bằng dấu ngoặc đơn (Điểm) trong dòng đầu tiên. Mỗi chức năng chúng tôi xác định trên một Điểm sẽ yêu cầu chức năng ghi đè 1-2 dòng trong phân lớp này, vì vậy chúng tôi sẽ chỉ cần thêm một lượng nhỏ sổ sách kế toán. Ví dụ, phủ định là khá dễ dàng >>> p = ec.Point(curve=c,x=3,y=6) >>> q = ec.Point(curve=c,x=80,y=10) >>> print(p) (3, 6) on "p97a2b3" => y^2 = x^3 + 2x + 3 (mod 97) >>> print(q) (80, 10) on "p97a2b3" => y^2 = x^3 + 2x + 3 (mod 97)0 Lưu ý rằng Python cho phép một người ghi đè thao tác trừ tiền tố bằng cách xác định __neg__ trên một đối tượng tùy chỉnh. Có các hàm tương tự để cộng ( __add__ ), phép trừ và gần như mọi thao tác được tích hợp sẵn trong python. Và tất nhiên bổ sung là nơi mọi thứ trở nên thú vị hơn. Đối với điểm lý tưởng, nó tầm thường. >>> p = ec.Point(curve=c,x=3,y=6) >>> q = ec.Point(curve=c,x=80,y=10) >>> print(p) (3, 6) on "p97a2b3" => y^2 = x^3 + 2x + 3 (mod 97) >>> print(q) (80, 10) on "p97a2b3" => y^2 = x^3 + 2x + 3 (mod 97)1 Tại sao điều này có ý nghĩa? . Vì vậy, theo tất cả các phân tích của chúng tôi, $ P + 0 = 0 + P = P$ và mã ngắn thỏa mãn Đối với các điểm khác biệt, chúng tôi phải tuân theo thuật toán mà chúng tôi đã sử dụng lần trước. Hãy nhớ rằng thủ thuật là tạo thành đường thẳng $L(x)$ đi qua hai điểm được thêm vào, thay đường thẳng đó cho $y$ trong đường cong elip, rồi tìm ra hệ số của $x^2$ trong kết quả . Sau đó, sử dụng hai điểm hiện có, chúng ta có thể giải quyết căn bậc ba của đa thức bằng cách sử dụng công thức của Vieta Để làm được điều đó, chúng ta cần giải tích hệ số của số hạng $ x^2$ của phương trình $ L(x)^2 = x^3 + ax + b$. Thật tẻ nhạt, nhưng đơn giản. Đầu tiên, viết $ \displaystyle L(x) = \left ( \frac{y_2 – y_1}{x_2 – x_1} \right ) (x – x_1) + y_1$ Bước đầu tiên của việc mở rộng $ L(x)^2$ mang lại cho chúng ta $ \displaystyle L(x)^2 = y_1^2 + 2y_1 \left ( \frac{y_2 – y_1}{x_2 – x_1} \right ) (x – x_1) + \left [ \left (\frac{y_2 – Và chúng tôi nhận thấy rằng số hạng duy nhất chứa phần $x^2$ là số hạng cuối cùng. Mở rộng điều đó mang lại cho chúng ta $ \displaystyle \left ( \frac{y_2 – y_1}{x_2 – x_1} \right )^2 (x^2 – 2xx_1 + x_1^2)$ Và một lần nữa chúng ta có thể loại bỏ những phần không liên quan đến $x^2$. Nói cách khác, nếu chúng ta viết lại $ L(x)^2 = x^3 + ax + b$ dưới dạng $ 0 = x^3 – L(x)^2 + ax + b$, chúng ta sẽ mở rộng tất cả $ \displaystyle 0 = x^3 – \left ( \frac{y_2 – y_1}{x_2 – x_1} \right )^2 x^2 + C_1x + C_2$ trong đó $C_1, C_2$ là một số hằng số mà chúng tôi không cần. Bây giờ, sử dụng công thức của Vieta và gọi $x_3$ là căn thứ ba mà chúng tôi tìm kiếm, chúng tôi biết rằng $ \displaystyle x_1 + x_2 + x_3 = \left ( \frac{y_2 – y_1}{x_2 – x_1} \right )^2$ Điều đó có nghĩa là $ x_3 = \left ( \frac{y_2 – y_1}{x_2 – x_1} \right )^2 – x_2 – x_1$. Khi chúng ta có $ x_3$, chúng ta có thể nhận được $ y_3$ từ phương trình của đường thẳng $ y_3 = L(x_3)$ Lưu ý rằng điều này chỉ hoạt động nếu hai điểm chúng tôi đang cố thêm khác nhau. Hai trường hợp còn lại là nếu các điểm giống nhau hoặc nằm trên một đường thẳng đứng. Các gotcha này sẽ tự biểu hiện dưới dạng các nhánh có điều kiện của hàm add của chúng ta >>> p = ec.Point(curve=c,x=3,y=6) >>> q = ec.Point(curve=c,x=80,y=10) >>> print(p) (3, 6) on "p97a2b3" => y^2 = x^3 + 2x + 3 (mod 97) >>> print(q) (80, 10) on "p97a2b3" => y^2 = x^3 + 2x + 3 (mod 97)2 Đầu tiên, chúng tôi kiểm tra xem hai điểm có giống nhau không, trong trường hợp đó chúng tôi sử dụng phương pháp tiếp tuyến (chúng tôi sẽ thực hiện tiếp theo). Giả sử các điểm khác nhau, nếu giá trị $x$ của chúng bằng nhau thì đường thẳng là đường thẳng đứng và điểm thứ ba là điểm lý tưởng. Mặt khác, chúng tôi sử dụng công thức chúng tôi đã xác định ở trên. Lưu ý dấu trừ tinh tế và quan trọng ở cuối. Điểm $(x_3, y_3)$ là giao điểm thứ ba nhưng ta vẫn phải thực hiện phép đối để có tổng hai điểm Bây giờ đối với trường hợp khi các điểm $P, Q$ thực sự giống nhau. Chúng tôi sẽ gọi nó là $P = (x_1, y_1)$ và chúng tôi đang cố gắng tìm $2P = P+P$. Theo thuật toán của chúng tôi, chúng tôi tính toán đường tiếp tuyến $J(x)$ tại $P$. Để làm được điều này, chúng ta chỉ cần một chút phép tính. Để tìm hệ số góc của tiếp tuyến, ta ngầm phân biệt phương trình $ y^2 = x^3 + ax + b$ và nhận được $ \displaystyle \frac{dy}{dx} = \frac{3x^2 + a}{2y}$ Lần duy nhất chúng tôi nhận được một đường thẳng đứng là khi mẫu số bằng 0 (bạn có thể xác minh điều này bằng cách lấy giới hạn nếu muốn), và do đó $ y=0$ ngụ ý rằng $ P+P = 0$ và chúng ta đã hoàn thành. Thực tế là điều này có thể xảy ra đối với $ P$ khác không sẽ gây ngạc nhiên cho bất kỳ độc giả nào không quen thuộc với các nhóm. Nhưng nếu không đi sâu vào một cuộc trò chuyện sâu sắc về các loại cấu trúc nhóm khác nhau ngoài kia, chúng ta sẽ phải giải quyết những bất ngờ thú vị như vậy Trong trường hợp khác $ y \neq 0$, chúng ta cắm các giá trị $ x,y$ vào đạo hàm và đọc hệ số góc $ m$ là $ (3x_1^2 + a)/(2y_1)$. Sau đó, sử dụng cùng một công thức độ dốc điểm cho một đường thẳng, chúng tôi nhận được $ J(x) = m(x-x_1) + y_1$ và chúng tôi có thể sử dụng cùng một kỹ thuật (và cùng một mã. ) từ trường hợp đầu tiên đến kết thúc Chỉ có một nếp nhăn nhỏ chúng ta cần làm phẳng. chúng ta có thể chắc chắn rằng công thức của Vieta hoạt động không? . làm thế nào để chúng ta biết rằng $ x_1$ là căn bậc hai của lập phương? . Có rất nhiều hình học đại số kỹ thuật (và một khái niệm rất thú vị nhưng phức tạp về kích thước) ẩn sau bức màn ở đây. Nhưng với mục đích của chúng ta, nó nói rằng tiếp tuyến của chúng ta cắt đường cong elip với bội số 2, và điều này mang lại cho chúng ta một căn bậc hai của phương trình bậc ba tương ứng. Và vì vậy, trong chức năng bổ sung, tất cả những gì chúng ta cần làm là thay đổi độ dốc mà chúng ta đang sử dụng. Điều này mang lại cho chúng tôi một triển khai tốt đẹp và ngắn gọn p1 = Point(3,7) p2 = Point(4,4) p3 = p1 + p20 Điều thú vị là dữ liệu của đường cong được đưa vào bức tranh ít như thế nào. Không có gì phụ thuộc vào $b$, và chỉ một trong hai trường hợp phụ thuộc vào $a$. Đây là một lý do khiến dạng chuẩn Weierstrass rất hữu ích và nó có thể cắn vào mông chúng ta sau này trong một vài trường hợp chúng ta không có nó (đối với các trường số đặc biệt) Dưới đây là một số ví dụ p1 = Point(3,7) p2 = Point(4,4) p3 = p1 + p21 Và vì vậy, chúng tôi lao đầu vào vấn đề số học dấu chấm động đầu tiên của mình. Chúng tôi sẽ đánh bại con quái vật này lâu dài hơn trong phần sau của loạt bài này (trên thực tế, chúng tôi sẽ loại bỏ hoàn toàn nó và xác định hệ thống số của riêng mình. ), nhưng bây giờ đây là cách khắc phục nhanh p1 = Point(3,7) p2 = Point(4,4) p3 = p1 + p22 Bây giờ chúng ta đã có phép cộng và phủ định, phần còn lại của lớp chỉ là thay đồ. Ví dụ: chúng tôi muốn có thể sử dụng ký hiệu phép trừ và vì vậy chúng tôi cần triển khai __sub__ p1 = Point(3,7) p2 = Point(4,4) p3 = p1 + p23 Lưu ý rằng vì Điểm lý tưởng là một lớp con của điểm nên nó kế thừa tất cả các chức năng đặc biệt này trong khi chỉ cần ghi đè __add__ và . Cảm ơn bạn, đa hình. Hàm cuối cùng mà chúng tôi muốn là một hàm chia tỷ lệ, giúp cộng một điểm vào chính nó một cách hiệu quả $ n$ lần. __neg__. Thank you, polymorphism! The last function we want is a scaling function, which efficiently adds a point to itself $ n$ times. p1 = Point(3,7) p2 = Point(4,4) p3 = p1 + p24 Hàm chia tỷ lệ cho phép chúng ta tính nhanh $nP = P + P + \dots + P$ ($n$ lần). Thật vậy, thực tế là chúng ta có thể làm điều này hiệu quả hơn so với việc thực hiện phép cộng $n$ là điều làm cho mật mã đường cong elliptic hoạt động. Chúng ta sẽ xem xét kỹ hơn vấn đề này trong bài đăng tiếp theo, nhưng bây giờ chúng ta hãy nói xem thuật toán đang làm gì Cho một số được viết dưới dạng nhị phân $n = b_kb_{k-1}\dots b_1b_0$, chúng ta có thể viết $nP$ dưới dạng $ \displaystyle b_0 P + b_1 2P + b_2 4P + \dots + b_k 2^k P$ Ưu điểm của điều này là chúng ta có thể tính toán lặp đi lặp lại từng $P, 2P, 4P, \dots, 2^kP$ chỉ bằng cách sử dụng phép cộng $k$ bằng cách nhân với 2 (thêm một số thứ vào chính nó) $k$ lần. Vì số bit trong $n$ là $k= \log(n)$, nên chúng tôi đang nhận được một cải tiến lớn so với các lần bổ sung $n$ Thuật toán được đưa ra ở trên trong mã, nhưng đó là một thủ thuật dịch chuyển bit đơn giản. Chỉ cần có $ i$ là một lũy thừa của hai, được dịch chuyển một ở cuối mỗi vòng lặp. Sau đó, bắt đầu với $Q_0$ là $P$, và thay thế $Q_{j+1} = Q_j + Q_j$, và theo kiểu lập trình điển hình, chúng tôi loại bỏ các chỉ số và ghi đè lên biến ràng buộc ở mỗi bước (Q = Q+Q). Cuối cùng, chúng ta có một biến $R$ mà $Q_j$ được thêm vào khi bit thứ $j$ của $n$ là 1 (và bị bỏ qua khi nó là 0). Phần còn lại là sổ sách kế toán Lưu ý rằng __mul__ chỉ cho phép chúng tôi viết một cái gì đó như P * n, but the standard notation for scaling is n * P. This is what __rmul__ cho phép chúng tôi thực hiện. Chúng ta có thể thêm nhiều hàm trợ giúp khác, chẳng hạn như các hàm cho phép chúng ta xử lý các điểm như thể chúng là các danh sách, kiểm tra sự bằng nhau của các điểm, các hàm so sánh để cho phép một người sắp xếp danh sách các điểm theo thứ tự từ vựng hoặc một hàm để biến đổi các điểm . Chúng tôi đã thực hiện một vài trong số này mà bạn có thể thấy nếu truy cập vào kho lưu trữ mã, nhưng chúng tôi sẽ để việc loại bỏ lớp này như một bài tập cho người đọc Vài ví dụ p1 = Point(3,7) p2 = Point(4,4) p3 = p1 + p25 Như mọi người có thể thấy, độ chính xác trở nên rất lớn rất nhanh. Một điều chúng ta sẽ làm để tránh những con số lớn như vậy (nhưng hy vọng không làm mất tính bảo mật) là làm việc trong các trường hữu hạn, phiên bản đơn giản nhất của nó là tính modulo một số nguyên tố. Vì vậy, bây giờ chúng ta đã hiểu cụ thể về thuật toán cộng điểm trên các đường cong elip và một chương trình Python đang hoạt động để thực hiện điều này cho các số hữu tỷ hoặc số dấu phẩy động (nếu chúng ta muốn xử lý các vấn đề về độ chính xác). Lần tới, chúng tôi sẽ tiếp tục dòng suy nghĩ này và nâng cấp chương trình của chúng tôi (với rất ít công việc. ) để làm việc trên các trường số đơn giản khác. Sau đó, chúng ta sẽ đi sâu vào các vấn đề mật mã và nói về cách người ta có thể mã hóa thông điệp trên một đường cong và sử dụng các phép toán đại số để mã hóa thông điệp của họ |
