# ELLIPTIC CURVES IN CRYPTOGRAPHY # Đường cong elliptic Đường cong Elliptic là một đường cong trong hình học đại số, được xác định bởi phương trình đại số có dạng: y^2 = x^3 + ax + b Với a, b là các hằng số số thực và `4a^3 + 27b^2 # 0`. Phương trình trên được gọi là dạng chuẩn Weierstrass cho các đường cong elip. Đường cong này có điểm đặc biệt gọi là điểm "vô cùng" và được ký hiệu là O. Đường cong Elliptic có những tính chất đặc biệt, chẳng hạn như nó là một đường cong mượt (smooth curve), tức là không có đỉnh, cusp hoặc self-intersection points. Điều này cho phép nó được sử dụng trong nhiều lĩnh vực, từ mã hóa đến lý thuyết số và hình học. Một trong những tính chất quan trọng nhất của đường cong Elliptic là nó có một phép toán "cộng" trên các điểm trên đường cong, được gọi là phép toán toán học trên đường cong Elliptic. Phép toán này cung cấp cho đường cong Elliptic một cấu trúc nhóm đặc biệt, cho phép nó được sử dụng trong các ứng dụng mã hóa và xác thực bảo mật. (Sẽ được phân tích kĩ hơn ở bên dưới) ![//avinetworks.com/wp-content/uploads/2020/02/elliptic-curve-cryptography-diagram.png](//avinetworks.com/wp-content/uploads/2020/02/elliptic-curve-cryptography-diagram.png) ## Phép cộng 2 điểm trên đường cong Elliptic ![//images.viblo.asia/ee44171b-e4e2-400a-96dc-e84de7e0da77.gif](//images.viblo.asia/ee44171b-e4e2-400a-96dc-e84de7e0da77.gif) Trên phương diện hình học, phép cộng 2 điểm P và Q theo biểu thức P + Q = R trên đường cong Elliptic được thực hiện như sau: Qui ước: - Điểm O là phần tử đơn vị của phép cộng. Như vậy với P∈ E(a,b), P ≠ 0 thì P + 0 = 0+P=P - Phần tử nghịch đảo của điểm P trong phép cộng, ký hiệu – P, là điểm đối xứng với P qua trục hoành Kẻ đường thẳng d đi qua 2 điểm P và Q, đường thẳng sẽ cắt đường cong Elliptic tại điểm thứ 3 là -R. Phần tử nghịch đảo của -R là R chính là kết quả của phép cộng hai điểm P và Q trong đường cong Elliptic. Nếu P và Q trùng nhau thì đường thẳng d chính là tiếp tuyến của đường cong tại điểm P và thực hiện tương tự như trên. Trên phương diện số học, các bước thực hiện sẽ có chút phức tạp hơn - Nếu P = Q: - Tính đạo hàm của đường cong tại P: m = (3x_p^2 + a) / (2y_p) - Tính tọa độ của R: x_R = m^2 - 2x_p, y_R = m(x_p - x_R) - y_p - Nếu P ≠ Q: - Tính độ dốc của đường thẳng đi qua P và Q: m = (y_q - y_p) / (x_q - x_p) - Tính tọa độ của R: x_R = m^2 - x_p - x_q, y_R = m(x_p - x_R) - y_p Trong trường hợp P và Q đối xứng qua trục hoành, hay nói cách khác Q = -P thì đường thẳng nối P, Q sẽ cắt đường cong Elliptic tại vô cực, hay P + ( -P ) = 0 Các phép tính này có thể được áp dụng cho đường cong Elliptic trên một trường hữu hạn, nơi các toán tử cộng, trừ, nhân và chia được định nghĩa trên các phần tử của trường hữu hạn đó. Các tính chất của đường cong Elliptic đã làm cho nó trở thành một công cụ hữu ích trong các ứng dụng mã hóa và xác thực bảo mật. ## Phép nhân vô hướng trên đường cong Elliptic (**Scalar multiplication**) Ngoài phép cộng, chúng ta có thể định nghĩa một phép toán khác: phép nhân vô hướng, nghĩa là: ```jsx nP = P + P + P +...+ P (n time) ``` Đk: `n`là số tự nhiên Như vậy để thực hiện phép nhân vô hướng nP, ta phải cộng n lần các điểm P lại với nhau. Nếu n có k bit nhị phân thì độ phức tạp của phép toán sẽ là O(2^k), điều này không thực sự tốt. Nhưng ta có thể thực hiện một số phép toán tối ưu hơn với độ phức tạp giảm đáng kể như sau. Một trong số đó là thuật toán **double and add.** Nguyên tắc hoạt động của nó có thể được giải thích rõ hơn với một ví dụ: Chọn n = 151, dạng nhị phân của n như sau: 10010111. Biểu diễn nhị phân này có thể được chuyển thành tổng lũy thừa của hai: $151 = 2^7 + 2^4 + 2^2 + 2^1 + 2^0$ Theo cách thức này, ta có thể nhân P vào cả 2 vế, được biểu thức như sau: $151P = 2^7P + 2^4P + 2^2P + 2^1P + 2^0P$ Cuối cùng, thuật toán **double and add** được mô tả như sau: ``` Input: P in E and an integer n > 0 1. Set Q = P and R = O. 2. Loop while n > 0. 3. If n ≡ 1 mod 2, set R = R + Q. 4. Set Q = 2 Q and n = ⌊n/2⌋. 5. If n > 0, continue with loop at Step 2. 6. Return the point R, which equals nP. ``` # Đường cong Elliptic trong trường hữu hạn(Fp) và ứng dụng trong mật mã Bây giờ chúng ta sẽ giới hạn các đường cong elliptic của mình trong các trường hữu hạn, thay vì tập hợp các số thực và xem mọi thứ thay đổi như thế nào. ## Đường cong Elliptic trong trường hữu hạn(Fp) Đường cong elliptic trong trường hữu hạn Fp là một loại đường cong elliptic mà tất cả các điểm trên đường cong được định nghĩa trong một trường hữu hạn Fp, trong đó p là một số nguyên tố. Các điểm trên đường cong elliptic Fp được biểu diễn bởi các cặp số nguyên (x,y), trong đó x và y đều là các phần tử của trường hữu hạn Fp, và thỏa mãn phương trình đường cong elliptic: y^2 = x^3 + ax + b ⇒ y^2 = x^3 + ax + b (mod p) trong đó a và b là các hệ số trong trường hữu hạn Fp và thỏa mãn điều kiện 4a^3 + 27b^2 ≠ 0 để đảm bảo rằng đường cong không phải là một đường thẳng. Một trong những ứng dụng quan trọng của đường cong elliptic trong trường hữu hạn Fp là trong mật mã học. Cụ thể, phép toán trên điểm của đường cong elliptic Fp có tính chất khó tính ngược lại, tạo ra một cơ chế bảo mật mạnh để sử dụng trong các giao thức mật mã học như mã hóa khóa công khai và chữ ký số. ![//blog.cloudflare.com/content/images/image06.png](//blog.cloudflare.com/content/images/image06.png) Những gì trước đây là một đường cong liên tục bây giờ là một tập hợp các điểm rời rạc trong hệ tọa độ xy. Và ta có thể thấy sự đối xứng giữa các điểm. ## Luật nhóm của đường cong Elliptic trong trường hữu hạn Fp Đường cong Elliptic trên trường hữu hạn Fp là một nhóm Abelian vì nó thỏa mãn cả hai tính chất của nhóm và tính chất của nhóm Abelian. Cụ thể, như đã biết, đường cong Elliptic thỏa mãn các tính chất của nhóm bao gồm tính kết hợp, phần tử đơn vị, phần tử nghịch đảo và tính giao hoán. Trong khi đó, tính chất của nhóm Abelian là tính giao hoán và phép cộng là phép toán có tính chất giao hoán. Nghĩa là, phép cộng hai phần tử bất kỳ trên đường cong Elliptic có tính chất giao hoán. Điều này có nghĩa là phép cộng P + Q sẽ tương đương với phép cộng Q + P. Vì vậy, đường cong Elliptic trên trường hữu hạn Fp thỏa mãn cả tính chất của nhóm và tính chất của nhóm Abelian, do đó được gọi là một nhóm Abelian. ## Phép cộng ![$E : y^2 = x^3 - x + 3 (mod 127), P(16, 20) , Q (41, 120),P+Q=R$](//andrea.corbellini.name/images/point-addition-mod-p.png) $E : y^2 = x^3 - x + 3 (mod 127), P(16, 20) , Q (41, 120),P+Q=R$ Phép cộng hai điểm trên đường cong Elliptic trong trường hữu hạn Fp được thực hiện bằng cách sử dụng công thức cộng của đường cong Elliptic. Cho hai điểm P và Q trên đường cong Elliptic, ta cần tính toán tổng P + Q bằng cách sử dụng các tham số của đường cong Elliptic và phép toán trên trường hữu hạn Fp. Cụ thể, công thức để tính toán P + Q là: - Nếu P = O (phần tử đơn vị), tổng P + Q sẽ là Q. - Nếu Q = O (phần tử đơn vị), tổng P + Q sẽ là P. - Nếu P = -Q (nghĩa là hai điểm trên đường cong đối xứng qua trục hoành), tổng P + Q sẽ là phần tử đơn vị O. - Nếu P ≠ Q, công thức cộng sẽ là: - Tính độ dốc của đường thẳng đi qua P và Q (lưu ý, nếu P và Q trùng nhau thì đường thẳng này là tiếp tuyến của đường cong tại P). - Tìm điểm giao của đường thẳng và đường cong Elliptic. Điểm này sẽ được ký hiệu là R. - Điểm R sẽ được phản xạ qua trục hoành để tính toán kết quả P + Q. Công thức chi tiết để tính toán điểm phản xạ R qua trục hoành là: x_R = s^2 - x_P - x_Q y_R = -y_P + s * (x_P - x_R) trong đó: s = (y_P - y_Q) / (x_P - x_Q) Nếu P = Q, công thức cộng sẽ được thay thế bằng công thức nhân (tính đạo hàm tại điểm P và sử dụng phép cộng trên trường hữu hạn). Việc tính toán phép cộng trên đường cong Elliptic trong trường hữu hạn Fp rất quan trọng trong các ứng dụng mã hóa và bảo mật thông tin. ```python def add_point(p1, p2): if p1 == (0, 0): return p2 if p2 == (0,0): return p1 x1, y1 = p1 x2, y2 = p2 if x1 == x2 and y1 == -y2: return (0, 0) lamda = 0 if p1 == p2: lamda = ((3*pow(x1,2,p)+a) * inverse(2*y1, p)) else: lamda = ((y2-y1) * inverse(x2-x1, p)) x3 = (pow(lamda, 2) - x1 - x2) % p y3 = (lamda*(x1 - x3) - y1) % p return (x3, y3) ``` ## Phép nhân vô hướng Chúng ta sẽ sử dụng thuật toán **double and add** tương tự như đường cong Elliptic trong trường số thực kết hợp thêm phép (mod p) để đảm bảo kết quả sẽ là một điểm ở trong trường hữu hạn Fp. Phép nhân vô hướng nP với P là một điểm trên đường cong Elliptic trong trường hữu hạn Fp là phép tính nhân một điểm trên đường cong Elliptic với một số nguyên dương n. Công thức tính toán phép nhân vô hướng là: ``` Input: P in E(Fp) and an integer n > 0 1. Set Q = P and R = O. 2. Loop while n > 0. 3. If n ≡ 1 mod 2, set R = R + Q. 4. Set Q = 2 Q and n = ⌊n/2⌋. 5. If n > 0, continue with loop at Step 2. 6. Return the point R, which equals nP. ``` Việc tính toán phép nhân vô hướng này có thể được tối ưu bằng cách sử dụng các thuật toán như Montgomery ladder hay double-and-add. Các thuật toán này giúp giảm số lần tính toán trên đường cong Elliptic và tăng tốc độ tính toán. Việc tính toán phép nhân vô hướng trên đường cong Elliptic trong trường hữu hạn Fp cũng rất quan trọng trong các ứng dụng mã hóa và bảo mật thông tin. $VD: E: y^2 = x^3 + 2x + 3(mod 97), P (3,6)$ ![//andrea.corbellini.name/images/cyclic-subgroup.png](//andrea.corbellini.name/images/cyclic-subgroup.png) ```python def Scalar_Mul(P, n): Q = P R = (0, 0) while n > 0:
Các kiểu dữ liệu trong hệ mật mã hóa ecc năm 2024
Bài Viết Liên Quan
Toplist
Bài mới nhất
Chủ đề
Hỏi Đáp
Toplist
Địa Điểm Hay
Là gì
Mẹo Hay
mẹo hay
programming
Học Tốt
Nghĩa của từ
Cách
2023
Review
Cryto
Giá
Học
đánh giá
Bao nhiêu
là ai
bao nhieu
bao nhiêu
hướng dẫn
Máy
So Sánh
Bài tập
So sánh
Top List
Tiếng anh
Xây Đựng
Ngôn ngữ
Sản phẩm tốt
Top
topten
Nhà
Dịch
Ở đâu
Thế nào
Hướng dẫn
Đại học
Tại sao
Máy tính
Sách
Khoa Học
Vì sao
Hà Nội
Bao lâu
Là ai
Món Ngon
cách