CHƯƠNG I TỔNG QUAN VỀ HỆ MẬT ĐƯỜNG CONG ELLIPTIC 1. Các khái niệm cơ bản Với việc sử dụng ngày càng phổ biến của các dịch vụ đám mây và mạng xã hội, thông tin cá nhân được lưu trữ trên Internet phải đối mặt với nguy cơ bị rò rỉ. Mã hóa đường cong Elliptic trở thành phương pháp bảo vệ thông tin hữu hiệu và được sử dụng rộng rãi vì tính mạnh mẽ của nó. Mã hóa hiện đại được thành lập dựa trên ý tưởng rằng khóa sử dụng để mã hóa dữ liệu có thể được công bố trong khi khóa dùng cho hoạt động giải mã dữ liệu phải được giữ bí mật.
Vì vậy, các hệ thống náy được biết đến dưới tên hệ thống mã hóa khóa công khai. Nói chung, một hệ thống mã hóa khóa công khai có hai thành phần, một khóa công khai và một khóa riêng. Mã hóa là hoạt động chuyển đổi một khối thông tin ban đầu, được gọi là bản rõ, thành một khối thông tin phù hợp (khóa). Giải mã là chuyển đổi ngược từ bản mã thành bản rõ bằng khóa đúng.
Mã hóa với khóa công khai chỉ có thể được hoàn tác bằng cách giải mã với khóa riêng. Mật mã đường cong Elliptic là kỹ thuật mật mã khóa công khai dựa trên lý thuyết về đường cong Elliptic, giúp tạo mật mã nhanh hơn, nhỏ hơn và mạnh hơn. ECC tạo ra các mật mã thông qua thuộc tính của phương trình đường cong Elliptic thay cho phương pháp sử dụng những nguyên tố lớn truyền thống. Công nghệ này có thể sử dụng cùng với hầu hết những phương thức mã hóa công khai như RSA và Diffie – Hellman.
Hiện nay, hệ mật RSA là giải thuật khóa công khai được sử dụng nhiều nhất, nhưng hệ mật dựa trên đường cong Elliptic (ECC) có thể dần thay thế cho RSA bởi mức an toàn, tốc độ xử lý cao hơn. Theo một số nhà nghiên cứu, ECC đạt đến cấp độ bảo mật chỉ với 164 bit trong khi các hệ thống khác phải cần 1024 bit để đạt được cấp độ bảo mật tương tự. Vì ECC giúp thiết lập bảo mật với sức mạnh tính toán và nguồn pin sử dụng thấp nên nó được áp dụng rộng rãi. ECC dựa vào các thuộc tính của một loại phương trình cụ thể được tạo từ nhóm (tập hợp các phần tử cùng với phép toán hai ngôi kết hợp hai phần tử bất kỳ của tập hợp thành một phần tử thứ ba).
Đồ thị xuất phát từ các điểm nơi giao nhau giữa đường 4 cong và hai trục. Lấy điểm đó nhân với một số để tìm thêm điểm tiếp theo, nhưng rất khó để biết cần nhân với số nào cho dù kết quả và điểm tiếp theo đã được cho trước. Các phương trình của đường cong Elip có một đặc điểm là vô cùng giá trị cho mục đích mà hóa vì chúng dễ thực hiện nhưng lại vô cùng khó đảo ngược. Phương trình đồng dư bậc hai và thặng dư bậc hai.
Ta xét phương trình đồng dư bậc hai có dạng như sau: 𝑥 2 ≡ 𝑎 ( 𝑚𝑜𝑑 𝑛 ) (1.1) Trong đó n là số nguyên dương, a là số nguyên với gcd (𝑎, 𝑛) ≡ 1 và x là ẩn số. Phương trình trên không phải bao giờ cũng có nghiệm, khi nó có nghiệm thì ta gọi a là thặng dư bậc hai mod n. Tập các số nguyên tố với n được phân thành hai tập con: Tập 𝑄𝑛 các thặng dư bậc hai mod n, và tập các bất thặng dư bậc hai mod n. Tiêu chuẩn Euler: Khi p là số nguyên tố.
Định nghĩa Giả sử K là một trường có đặc số khác 2 và 3, ta xét đa thức 𝑋3 + 𝑎𝑋 + 𝑏 (với a, b K) Khi đường cong Elliptic trên trường K: 𝑌 2 = 𝑋 3 + 𝑎𝑋 + 𝑏 là tập hợp tất cả các điểm (x,y) với x, y K sao cho (1) không có các nghiệm bội, tức là 4𝑎3 + 27𝑏2 ≠ 0 mod p cùng với phần tử O – điểm O này được gọi là điểm vô hạn. Tức là đường cong Elliptic là tập hợp S: S = { (𝑥, 𝑦): 𝑦 2 = 𝑥 3 + 𝑎𝑥 + 𝑏, 𝑥, 𝑦 ∈ 𝐾} ∈ {𝑂}. Với a, b K cho trước sao cho 4𝑎3 + 27𝑏 2 ≠ 0 theo mod p. Nếu K là trường đặc số 2 thì ta định nghĩa: S = { (𝑥, 𝑦): 𝑦 2 + 𝑦 = 𝑥 3 + 𝑎𝑥 + 𝑏} ∪ {𝑂} Nếu K là trường đặc số 3 thì ta định nghĩa: S = { (𝑥, 𝑦): 𝑦 2 + 𝑦 = 𝑥 3 + 𝑎𝑥 + 𝑏 + 𝑐 } ∪ {𝑂 } 5 1.
Cơ sở toán học 1. Phương trình Weierstrass của đường cong Elliptic Giả sử p là một số nguyên tố >3. Người ta chứng minh được rằng bằng phép biến đổi tuyến tính, ta có thể quy phương trình đường cong Elliptic về dạng Weierstrass như sau: 𝒚𝟐 = 𝒙𝟑 + 𝑨𝒙 + 𝑩 (1.2) Trong đó A và B là các hằng số. Các giá trị của x, y, A, B thường là các giá trị trên một trường nào đó, ví dụ như R (số thực), Q (số hữu tỷ), C (số phức), hoặc trường hữu hạn Fq, với q = pn trong đó p là số nguyên tố với n ≥ 1.
Nếu K là một trường có a, b K, khi đó ta nói đường cong Elliptic được định nghĩa trên trường K. Điểm (x, y) trên đường cong Elliptic với (x, y) K được gọi là điểm K – hữu tỷ. Dạng tổng quát phương trình Weierstrass của đường cong Elliptic sẽ được biểu diễn dưới dạng: 𝒚𝟐 + 𝒂𝟏 𝒙𝒚 + 𝒂𝟑 𝒚 = 𝒙𝟑 + 𝒂𝟐 𝒙𝟐 + 𝒂𝟒 𝒙 + 𝒂𝟔 (1.3) Trong đó 𝑎1 , … … , 𝑎6 là các hằng số.3) thường được sử dụng với các trường K có đặc số chap(K) bằng 2 hoặc 3. Khi K có chap(K) khác 2 có thể biến đổi (1.3) thành dạng sau: 𝑎1𝑥 𝑎3 2 3 𝑎12 2 𝑎1 𝑎3 𝑎32 (𝑦 + + ) = 𝑥 + (𝑎2 ) 𝑥 + (𝑎4 + ) 𝑥 + ( + 𝑎6 ), 2 2 4 2 4 Có thể viết lại như sau: 𝑦12 = 𝑥 3 + 𝑎′2 𝑥 2 + 𝑎′4 𝑥 + 𝑎′6 , Với 𝑦1 = 𝑦 + 𝑎1 𝑥 ⁄2 + 𝑎3 ⁄2 và với các hằng số 𝑎′2 , 𝑎′4 , 𝑎′6.
Khi K có chap(K) khác 3 có thể dùng phép thế 𝑥1 = 𝑥 + 𝑎′2 ⁄3 và ta có: 𝑦12 = 𝑥13 + 𝐴𝑥 + 𝐵, Trong đó A, B là các hằng số bất kỳ. Đường cong này sẽ suy biến và không có đủ 3 nghiệm phân biệt khi ∆= 0, trong tài liệu này chúng ta chỉ xét các đường cong có ∆≠ 0. Cộng các điểm trên đường cong Elliptic 6 Xét hai điểm 𝑃1 = (𝑥1 , 𝑦1 ) và 𝑃2 = (𝑥2 , 𝑦2 ) trên đường cong Elliptic E: 𝑦 2 + 𝑎1 𝑥𝑦 + 𝑎3 𝑦 = 𝑥 3 + 𝑎2 𝑥 2 + 𝑎4 𝑥 + 𝑎6. Phép cộng giữa hai điểm trên đường cong E được định nghĩa như sau: 𝑷𝟑 (𝒙𝟑 , 𝒚𝟑 ) = 𝑷𝟏 (𝒙𝟏 , 𝒚𝟏 ) + 𝑷𝟐 (𝒙𝟐 , 𝒚𝟐 ) (1.4) Trong đó 𝑃3(𝑥3 , 𝑦3 ) = −𝑃′ 3 (𝑥3 , 𝑦 ′ 3) là giao điểm của đường cong E và đường thẳng đi qua P1 và P2.
Công thức để tính các giá trị (x3, y3) sẽ được chứng minh ở dưới đây. 1: Phép cộng trên đường cong Elliptic Đường thẳng đi qua 2 điểm P1 và P2 có phương trình là: y = x + (1.5) Trong đó là hệ số góc của đường thẳng đi qua P1, P2. Trường hợp 2 điểm không trùng nhau 𝑃1 ≠ 𝑃2 Từ (5) và (6) suy ra: 𝑦1 − 𝑦2 = (𝑥1 − 𝑥2 ), khi 𝑃1 ≠ 𝑃2 , nghĩa là 𝑥1 ≠ 𝑥2 , ta có công thức: 𝒚𝟏 − 𝒚𝟐 = (1.10) 𝒙𝟏 − 𝒙𝟐 𝒙𝟏 − 𝒙𝟐 Tiếp theo thay y ở (4) vào phương trình (2) ta có: (𝒙 + µ)𝟐 + (𝒂𝟏 𝒙 + 𝒂𝟑 )(𝒙 + µ) = 𝒙𝟑 + 𝒂𝟐 𝒙𝟐 + 𝒂𝟒 𝒙 + 𝒂𝟔 (1.11) Từ đó dẫn đến phương trình 𝑟(𝑥 ) = 0 với: r ( x) = x 3 + (a2 − 2 − a1 ) x 2 + (a4 − 2 − a3 − a1 ) x + a6 − 2 − a3 (1.13) = ( x 2 − ( x1 + x2 ) x + x1 x2 )( x − x3 ) = x3 − ( x1 + x2 ) x 2 + x1 x2 x − x3 x 2 + ( x1 + x2 ) x3 x − x1x2 x3 = x3 − ( x1 + x2 + x3 ) x 2 + ( x1 x2 + x1 x3 + x2 x3 ) x − x1x2 x3 Đồng nhất các hệ số x2 của 𝑟(𝑥) ở 2 phương trình (1.13) ta có: 𝑥1 + 𝑥2 + 𝑥3 = −(𝑎2 − 2 − 𝑎1 ) Từ đây có thể tính được 𝑥3 theo công thức sau: 𝒙𝟑 = 𝟐 + 𝒂𝟏 − 𝒂𝟐 − 𝒙𝟏 − 𝒙𝟐 (1.14) Đến đây cần phải tính tiếp giá trị 𝑦3 , lúc này 𝑥3 đã tính xong nên có thể coi là hằng số, có thể biết lại (2) thành dạng như sau: 8 𝒚𝟐 + (𝒂𝟏 𝒙𝟑 + 𝒂𝟑 )𝒚 − (𝒙𝟑𝟑 + 𝒂𝟐 𝒙𝟐𝟑 + 𝒂𝟒 𝒙𝟑 + 𝒂𝟔 ) = 𝟎 (1.15) Phương trình bậc 2 này có 2 nghiệm là: −(𝒂𝟏 𝒙𝟑 + 𝒂𝟑 ) ± √∆ (1.16) 𝒚𝟑 , 𝒚′𝟑 = 𝟐×𝟏 Cộng 2 nghiệm này ta sẽ có: 𝑦′3 + 𝑦3 = −𝑎1𝑥3 − 𝑎3 , mặt khác do 𝑦′3 nằm trên đường thẳng 𝑃1, 𝑃2 nên 𝑦′3 = 𝑥3 + µ. Từ đây có thể tính được 𝑦3 theo công thức như sau: 𝒚𝟑 = −𝒙𝟑 − µ − 𝒂𝟏 𝒙𝟑 − 𝒂𝟑 (1.
Trường hợp 2 điểm trùng nhau 𝑃1 = 𝑃2 Khi này 𝑥1 = 𝑥2 và 𝑦1 = 𝑦2 do đó công thức tính ở (9) không sử dụng được vì xuất hiện phép chia số 0. Trong trường hợp này chính là hệ số góc của đường thẳng tiếp tuyến đường cong E tại 𝑃1 hay 𝑃2.