Đồ án Hệ mật đường cong Elliptic và ứng dụng trong mạng điện thoại

p) ta thấy 4a3 + 27b2 = 4 + 432 = 436 22 (mod 23). Vì vậy, E thực sự là đường cong elliptic. Theo định lý Hasse, #E(F23) = 29, là một số nguyên tố nên E(F23) là cylic và bất kỳ điểm nào khác O đều là phần tử sinh của E(F23). Ví dụ, G = (0, 2) là phần tử sinh với các tập điểm của E(F23) như sau: k kG k kG k kG K kG k kG k kG 1 (0, 2) 6 (9, 11) 11 (10, 5) 16 (8, 8) 21 (14, 18) 26 (11, 14) 2 (13, 12) 7 (15, 6) 12 (17, 9) 17 (17, 14) 22 (15, 17) 27 (13, 11) 3 (11, 9) 8 (14, 5) 13 (8, 15) 18 (10, 18) 23 (9, 12) 28 (0, 21) 4 (1, 12) 9 (4, 7) 14 (18, 9) 19 (22, 18) 24 (7, 3) 29 O 5 (7, 20) 10 (22, 5) 15 (18, 14) 20 (4, 16) 25 (1, 11) Bảng 2.1. Các điểm trên E(Z23) CHƯƠNG 3: CÁC HỆ MẬT TRÊN ĐƯỜNG CONG ELLIPTIC 3.1. Lịch sử Năm 1976, Diffie và Hellman giới thiệu hệ mã hoá khoá công khai đầu tiên mà sự an toàn của nó dựa trên độ khó của bài toán DLP. Họ đưa ra khái niệm hàm cửa sập một chiều (TOF). Năm 1985, Lenstra thành công trong việc sử dụng các đường cong elliptic cho các số nguyên. Kết quả này mang lại khả năng áp dụng các đường cong elliptic trong các hệ mật mã khoá công khai. Miller và Kobliz giới thiệu những hệ mật mã elliptic đầu tiên. Họ không phát minh ra các thuật toán mới nhưng đã có đóng góp lớn là chỉ ra việc áp dụng đường cong Elliptic cho các hệ khoá công khai. Miller đề xuất một giao thức trao đổi khoá tựa như Diffie – Hellman vào năm 1985 (nhanh hơn 20% so với giao thức Diffie - Hellman). Kobliz đưa ra thuật toán mã hoá tương tự như hệ Elgamal và Massey – Omura vào năm 1987. Sơ đồ đầu tiên tương tự như sơ đồ RSA và 3 hàm một chiều (có cửa sập) mới dựa trên đường cong Elliptic được đưa ra năm 1991 bởi Koyama, Maurer, Okamoto và Vanstone ( thuật toán này tốc độ thực hiện nhanh gấp 6 lần so với RSA). Cùng thời điểm đó, Kaliski chứng minh rằng các hàm cửa sập một chiều đòi hỏi thời gian là hàm mũ để thực hiện phép tính nghịch đảo. Menezes, Okamoto và Vanstone đã đưa ra một phương pháp tấn công MOV để giải bài toán EDLP trong một số trường hợp riêng. Ngay sau đó, Miyaji đã tìm được các điều kiện để tránh khỏi tấn công MOV và đề xuất một ứng dụng thực tế của các đường cong elliptic cho các sơ đồ chữ ký và định danh trên Smart Card. Năm 1993, Demytko đưa ra một thuật toán mới tương tự như RSA cho các đường cong Elliptic trên vành Zn vượt qua các hạn chế của các phiên bản trước, và Menezes và Vanstone đã đưa ra phương pháp thực thi trên các thiết bị cứng có thể cài thiện các tính toán trên elliptic trên một trường hữu hạn. Những năm 1997, 1998 việc tìm ra các hệ mật mã trên các đường cong Elliptic ngày càng thu hút nhiều sự chú ý và một số thuật toán đã được đưa thành chuẩn trong các RFC. 3.2. Nhúng bản rõ vào các đường cong Elliptic Nhúng một bản rõ lên E là biểu diễn lại bản rõ đó như là các điểm trên E mà nhờ đó chúng ta có thể thực hiện được các tính toán trên E. Có một số phương pháp đế thực hiện việc này. Trong đó có 2 phương pháp chính là: imbeding, mask. 3.2.1. Imbeding Cách 1: Để nhúng m lên E(Zp) với p là số nguyên tố, chẳng hạn p 3 (mod 4). Giả sử E(Zp) được cho bởi phương trình (2.1) và giả sử m là số nguyên thỏa mãn . Thêm 3 chữ số vào m sẽ tạo ra x thỏa mãn . Chúng ta sẽ bổ sung các chữ số khác nhau cho đến khi tìm được x sao cho f(x) = x3 + ax + b là một số bình phương trong Zp và y (với f(x) = y2 mod p ) thỏa mãn . Điểm Pm được tạo thành khi nhúng m lên E là: Có thể dễ dàng khôi phục lại m từ bằng cách loại bỏ 3 chữ số cuối của tọa độ x của điểm Pm. Cách 2 Bước 1: Sử dụng bảng chữ cái gồm N ký tự. Chia bản rõ thành các khối có độ dài cố định l. Các ký tự được đánh số là 0,, N-1. Một khối văn bản w cùng với các số tạo thành một ánh xạ: Bước 2: Chọn một giá trị k thích hợp sao cho kNl < q. Với mỗi j là phần tử của Fq tính kxw + j. Lấy điểm Pw đầu tiên mà tọa độ x kxw , ví dụ Pw = (kxw + j, *) Bước 3: Khôi phục lại khối bản rõ từ Pw bằng cách tính 3.2.2. Mask Để biểu diễn lại các cặp phần tử (m1, m2) thành các điểm trên E có thể áp dụng phương pháp masking bằng cách nhân m1 và m2 với các tọa độ x, y của các điểm trên E. 3.3. Một số hệ mã hóa trên đường cong elliptic Hệ mã hóa đường cong elliptic (ECC) có thể được thực thi tương tự như các hệ mật mã khác trên trường số nguyên, thay vào đó là các điểm trên đường cong elliptic. 3.3.1. Hệ mã hóa “tựa” Elgamal. Hệ Elgamal làm việc với nhóm cyclic hữu hạn. Năm 1987, Koblitz đã đưa ra một hệ trên ECC dựa trên hệ Elgamal. Ta có trường số Zp và một đường cong elliptic E trên Zp là E(Zp) cùng một điểm cơ sở PE. Mỗi người dùng sẽ chọn một số aX làm khóa bí mật, và aXP là khóa công khai. Giả sử Alice cần gửi một thông điệp m cho Bob. Đầu tiên cô ấy nhúng văn bản m lên E, chẳng hạn m được thể hiện bằng một điểm PmE. Khi đó cô ta phải mã hóa Pm. Ký hiệu aB là khóa bí mật của Bob, vì vậy khóa công khai của Bob là aBP. Alice chọn một số ngẫu nhiên k và gửi cho Bob cặp điểm trên E: (C1, C2) = (kP, Pm + k(aBP)) Để giải mã, Bob tính: C2 – aB(C1) = Pm + k(aBP) – aB(kP) = Pm Chú ý rằng ở đây Pm là một điểm thuộc đường cong elliptic, quá trình mã hóa giải mã được thực hiện trên các điểm thuộc đường cong E. Trong thực tế, để sử dụng được người ta phải tương ứng một số với một điểm thuộc đường cong elliptic. Khi đó mỗi thông điệp cần mã hóa sẽ tương ứng với một dãy số. Mỗi số sẽ tương ứng với một điểm trên đường cong elliptic. Tính bảo mật Nếu kẻ tấn công giữa đường, Oscar, có thể giải bài toán EDLP thì anh ta có thể biết được khóa bí mật aB của Bob từ các thông tin công khai P và aBP, và có thể giải mã được thông điệp mà Alice gửi. Như vậy, độ an toàn (bảo mật) của thuật toán trên dựa vào độ an toàn của bài toán EDLP. Sơ đồ mã hóa trên có ưu điểm là không yêu cầu tính số điểm của E trên Fq (#E(Fq)). 3.3.2. Hệ mã hóa Menezes-Vanstone. Sự khác biệt của hệ này với hệ tựa Elgamal là Alice áp dụng kỹ thuật Masking thay vì Imbeding khi biểu diễn lại bản rõ thành các điểm trên E. E là một đường cong elliptic trên trường nguyên tố Zp (p > 3) sao cho E chứa một nhóm con cyclic H, mà trong đó bài toán EDLP là khó. Zp, E(Zp) và điểm PE là công khai. Mỗi người dùng chọn một số nguyên ngẫu nhiên aX làm khóa bí mật và công khai aXP. Giả sử rằng Alice cần gửi thông điệp M = (x1, x2) cho Bob. Giả sử aB là khóa bí mật của Bob. Alice chọn số ngẫu nhiên k và gửi: (y0, y1, y2) = (kP, c1x1 mod p, c2x2 mod p) với (c1, c2) = k(aBP) Để giải mã, Bob tính: (y1c1-1 mod p, y2c2-1 mod p) = (x1, x2) với aBy0 = (c1, c2) Việc giải mã là đúng đắn vì: y0 = kP, Bob có thể tính: aBy0 = aB(kP) = k(aBP) = (c1, c2) vì vậy: Ví dụ Xét đường cong E có phương trình dạng: y2 = x3 + x + 13 Trên trường nguyên tố Z31. Như vậy, E có đặc số 2, 3. Chọn điểm cơ sở G = (9, 10). #E(Z31) = 34 và P là phần tử bậc 34. Các điểm trên E được liệt kê như sau: Bảng 3.1. Các điểm trên E(Z31) k kG k kG k kG K kG k kG k kG 1 (9, 10) 7 (6, 24) 13 (27, 10) 19 (5, 22) 25 (16, 23) 31 (23, 12) 2 (18, 29) 8 (24, 29) 14 (26, 21) 20 (26, 10) 26 (24, 2) 32 (18, 2) 3 (23, 19) 9 (16, 8) 15 (5, 9) 21 (27, 21) 27 (6, 7) 33 (9, 21) 4 (4, 22) 10 (20, 2) 16 (19, 3) 22 (28, 18) 28 (17, 13) 34 O 5 (25, 16) 11 (22, 22) 17 (10, 0) 23 (22, 9) 29 (25, 15) 6 (17, 18) 12 (28, 13) 18 (19, 28) 24 (20, 29) 30 (4, 9) Chúng ta sử dụng phương pháp masking thay cho imbeding nên không gian bản rõ là Z34*xZ34*. Mỗi bản rõ (x1, x2) thể hiện 2 chữ cái trong đó “a” là 1, “b” là 2, , “z” là 26. Phép tính nghịch đảo modulo được thực hiện bằng thuật toán Euclid mở rộng. Phép tính kG sử dụng thuật toán nhân đôi và cộng. 3.4. Một số sơ đồ chữ ký trên đường cong elliptic 3.4.1. Sơ đồ chữ ký ECDSA. Sơ đồ chữ ký ECDSA được xây dựng tương tự như sơ đồ chữ ký Elgamal tuy nhiên các thuật toán ký và thuật toán kiểm thử được xây dựng dựa trên đường cong elliptic. Để thiết lập sơ đồ chữ ký ECDSA, cần xác định các tham số: lựa chọn đường cong E trên trường hữu hạn Fq với đặc số p sao cho phù hợp, điểm cơ sở G E(Fq). Một số khuyến nghị khi lựa chọn các tham số: Kích thước q của trường, hoặc q = p (p > 2) hoặc q = 2m. Hai phần tử a, b thuộc Fq xác định phương trình đường cong elliptic: y2 = x3 + ax + b (p>2) hoặc y2 + xy = x3 + ax2 + b (p =2) Hai phần tử xG và yG thuộc Fq xác định điểm cơ sở G = (xG, yG). Bậc n của điểm G với n > 2160 và Tham số phụ h = #E(Fq)/n. Sinh khóa Chọn số ngẫu nhiên d trong khoảng [1, n – 1] Tính Q = dG. Khóa công khai là Q, khóa bí mật là d Ký trên bản rõ m Chọn một số ngẫu nhiên k, Tính kG = (x1, y1). Tính r = x1 mod n. Nếu r = 0, quay lại bước 1. Tính k-1 mod n. Tính s = k-1 (m + dr) mod n. Nếu s = 0 quay lại bước 1. Chữ ký trên thông điệp m là (r, s) Kiểm tra chữ ký Kiểm tra r và s có là các số tự nhiên trong khoảng [2, n – 1] Tính w = s-1 mod n Tính u1 = mw mod n và u2 = rw mod n Tính X = u1G + u2Q Nếu X = O thì phủ nhận chữ ký. Ngược lại tính v = x1 mod n. Chữ ký chỉ được chấp nhận nếu v = r. Chứng minh: Nếu chữ ký (r, s) trên m là đúng thì s = k-1(m + dr) mod n. k s-1 (m + dr) s-1e + s-1 rd wm + wrd u1 + u2d (mod n). Vì vậy, u1G + u2Q = (u1 + u2d)G = kG, và vì vậy v = r. Độ an toàn của sơ đồ chữ ký ECDSA. Các hệ mã hoá đường cong elliptic đầu tiên được phát minh năm 1985 bởi Neal Kobliz và Victor Miller. Tuy nhiên sơ đồ chữ ký ECDSA do Scott Vanstone đưa ra năm 1992, được chấp nhận là chuẩn ISO vào năm 1998, là chuẩn ANSI vào năm 1999, và là chuẩn IEEE vào năm 2000. Độ an toàn của sơ đồ ký ECDSA dựa trên bài toán logarit rời rạc đường cong elliptic. Cho đến nay độ an toàn của các hệ mã hoá đường cong elliptic đã được chỉ ra là rất an toàn và hiệu quả. Đối với bài toán logarit rời rạc đường cong elliptic thì có nhiều thuật toán giải nó. Tuy nhiên chưa có thuật toán nào có độ phức tạp tính toán trong thời gian đa thức. Thuật toán giải bài toán logarit rời rạc đường cong elliptic tốt nhất hiện nay là thuật toán Pollard’s Rho, phiên bản thiết kế theo hướng tính toán song song. Theo đó với nhóm đường cong elliptic cấp n và có r máy tính cùng tính toán thì phải mật /2.r phép toán. Mặt khác người ta đã phân tích và chỉ ra rằng với hệ mã hoá dựa trên bài toán logarit rời rạc đường cong elliptic có cùng độ bảo mật với hệ mã hoá dựa trên bài toán phân tích số nguyên thành các thừa số nguyên tố (như RSA) thì độ dài khoá của hệ mã hoá dựa trên đường cong elliptic có chiều dài khoá ngắn hơn rất nhiều . Chẳng hạn với hệ mã hoá RSA có chiều dài khoá là 1024 bit thì hệ mã hoá bằng đường cong elliptic chỉ cần độ dài khoá 163 bit sẽ có độ bảo mật tương đương. Và do đó việc tính toán các tiến trình đối với các hệ mã hoá đường cong elliptic là nhanh hơn rất nhiều. 3.4.2. Sơ đồ chữ ký Nyberg – Rueppel. Giả sử E là một đường cong Elliptic trên trường Zp (p>3 và nguyên tố) sao cho E chứa một nhóm con cyclic H trong đó bài toán logarith rời rạc là “khó”. Với , , ta định nghĩa: với . Các giá trị và là công khai, a là bí mật. Với chọn một số ngẫu nhiên . Khi đó, với ta định nghĩa: Trong đó . Trong đó Tất cả các sơ đồ chữ ký đều yêu cầu phải băm văn bản trước khi ký. Chuẩn P1363 của IEEE khuyến nghị dùng SHA-1, được định nghĩa bởi NIST, hoặc RIPEMD-160, được định nghĩa bởi ISO-IEC. Lý do để sử dụng các hàm băm là việc chúng giúp khó tìm được 2 văn bản có cùng giá trị băm, hàm băm giúp chữ ký trên văn bản gốc gọn nhẹ hơn rất nhiều. 3.4.3. Sơ đồ chữ ký mù Harn trên EC. Chữ ký mù là chữ ký thực hiện trên một văn bản mà người ký hoàn toàn không biết nội dung. Điều này thực hiện được vì người trình ký đã sử dụng một phương pháp nào đó để che dấu nội dung của văn bản gốc để người ký không biết. Để người ký yên tâm, người xin cấp chữ ký phải chứng minh tính hợp lệ của nội dung đã bị che dấu. Sinh khóa Chọn các tham số cho đường cong Elliptic Chọn số nguyên tố p và số nguyên n. Giả sử f(x) là một hàm đa thức trên trường GF(p) bậc n tạo thành trường hữu hạn GF(pn) và a là một nghiệm của f(x) trong GF(pn). Với 2 phần tử a, b của GF(pn), xác định phương trình của E trên GF(pn) ( trong trường hợp p>3) với Với 2 phần tử xp và yp trong GF(pn) xác định một điểm P = (xp, yp) trên E(GF(pn)) (P O với O là điểm gốc). Giả sử điểm P có bậc q Hàm chuyển c(x) : được cho bởi: , , Việc sinh khóa bao gồm: Chọn một khóa bí mật d là số nguyên ngẫu nhiên trong [1, q – 1] Tính khóa công khai Q, là một diểm trên E sao cho Q = dP. Ký mù Giả sử Bob yêu cầu Alice ký lên một văn bản m0 mà m là đại diện của văn bản này (m = H(m0) với H là một hàm băm nào đó). Giao thức ký được thực hiện như sau: Alice sinh ra cặp khóa () theo cách sau: chọn ngẫu nhiên và tính . Sau đó tính : , trong đó , rồi gửi và cho Bob Bob chọn các tham số làm mù , tính R trên E sao cho R = a+ bP = (xk, yk) và tính r = c(xk) và . Sau đó gửi cho Alice ( là m sau khi đã bị làm mù). Alice tính , rồi gửi cho Bob. Bob nhận được , xóa mù để có được chữ ký s trên m bằng cách tính Cặp (r, s) là một chữ ký ECC trên m. 3.4.4. Sơ đồ “ blind multi-signature” của Harn trên EC Sinh khóa Việc chọn các tham số cho đường cong Elliptic tương tự như sơ đồ chữ ký Harn. Chúng ta giả sử rằng có t người ký là Ui, với . Việc sinh khóa được thực hiện qua các bước: Mỗi người ký Ui chọn ngẫu nhiên một khóa bí mật di là một số nguyên thuộc [1,q– 1] Khóa công khai của người ký Ui là điểm: Qi = diP = (), Khóa công khai cho tất cả người ký là: Q = Q1 ++ Qt = dP = (xd, yd) với d = d1 + + dt (mod q) Ký Người ký Ui sinh một lần cặp () bằng cách chọn ngẫu nhiên và tính . Ui tính các , i = 1,, t với rồi gửi và cho Ban thư ký. Ban thư ký chọn các tham số làm mù , tìm điểm R trên E sao cho trong đó và . Ban thư ký tính và . Sau đó, gửi và đến cho từng người ký Ui. Ui tính chữ ký , i=1,, t. Sau đó gửi tới Ban thư ký. Ban thư ký tính và kiểm tra , i=1,, t. Chữ ký mù nhóm ECC là cặp (r, s) trong đó: và Chứng minh Cặp (r, s) là một chữ ký do nhiều thành viên ký trên thông điệp m – nó cũng là một chữ ký nhóm mù. Việc xác minh tính hợp lệ của chữ ký nhóm (r, s) của thông điệp m được thực hiện như sau: Tìm một điểm trên E sao cho . Sử dụng hàm chuyển để tính c(xe) và kiểm tra . Nếu đúng thì (r, s) được chấp nhận. Dễ dàng để xác minh rằng Để chứng minh rằng giao thức ký trên tạo ra chữ ký nhóm có tính chất “mù” ta phải chỉ ra rằng với mỗi người ký tồn tại duy nhất cặp (a, b) là các tham số làm mù với . Với các và cặp chữ ký hợp lệ (r, s) của thông điệp m, chúng ta có: Ta phải chỉ ra rằng . Ta có 3.5. Một số thuật toán tấn công các hệ ECC 3.5.1. Phương pháp tấn công “baby-step giant - step”. Đây là phương pháp tấn công đầu tiên lên hệ mật mã ECC do Shanks đưa ra, và thực hiện với thời gian là hàm mũ. Nó giải bài toán DLP trong trường nguyên tố Zp được mở rộng cho bài toán EDLP. Bài toán Tìm k sao cho kP = Q trên E(Fq) với #E(Fq) = N, giả sử k tồn tại thực sự. Thuật toán Chọn số nguyên m > Tính mP Với i = 0 đến i = m-1 tính (và lưu lại) iP Với j = 0 đến j = m-1 tính (và lưu lại) Q – jmP Sắp xếp danh sách trong bước 3 và 4 theo một thứ tự nhất định So sánh các danh sách ở các bước 3 và 4 cho đến khi tìm được cặp i, j thỏa mãn iP = Q – jmP Kết quả trả lại là k i + jm (mod N) Chứng minh Vì chúng ta chọn m thỏa mãn m2 > N nên sẽ có k < m2. Đặt k0 k (mod m), . Đặt k1 = (k – k0) / m. Ta sẽ có: k = k0 + mk1, với Trong thuật toán trên ta thử tìm tất cả i thuộc khoảng của k0 và tất cả j trong khoảng của k1 cho đến khi tìm được i, j thoả mãn iP = Q – jmP (i + jm)P = Q hay k = i + jm. Vì k tồn tại nên k0, k1 tồn tại. Độ phức tạp thời gian Bước 1 cần O(log N). Bước 2 và bước 3 cần O(m+1) = O(). Bước 4 cần O(). Thuật toán sắp xếp trong bước 5 được thực hiện trong O(log()) thời gian. Bước 6 được thực hiện trong O() thời gian. Bước 7 cũng được thực hiện trong O() thời gian. Vì vậy, thời gian thực hiện của thuật toán là . Thuật toán này quá chậm vì thời gian là hàm mũ của độ dài dữ liệu vào N. 3.5.2. Phương pháp tấn công MOV Thuật toán tấn công MOV (tên của 3 nhà khoa học Menezes, Okamoto, và Vanstone) làm yếu bài toán logarit rời rạc trên đường cong elliptic E(Fq) thành bài toán logarith rời rạc trên trường với m nào đó. Khi đó có thể tấn công bằng tấn công chỉ số, nhất là khi m nhỏ. Chúng ta bắt đầu bằng định nghĩa cặp Weil cho các đường cong elliptic E(F). Xét đường cong elliptic E(F) và N là một số nguyên không là ước của đặc số của F. Đặt E[N] là tập hợp các điểm trên đường cong E.. Như vậy, là nhóm các nghiệm thứ N trong F. Vì đặc số của F không chia hết cho N, xN = 1 không có nghiệm kép, nghĩa là có N nghiệm phân biệt trong F. Định nghĩa: Một cặp Weil là một ánh xạ: thỏa mãn: eN là song tuyến tính với mọi biến eN là không suy biến với mọi biến. Nghĩa là, nếu eN(S, T) = 1 với mọi S, thì T = O, và nếu eN (S, T) = 1 với mọi T thì S = O. eN (T, T) = 1 eN(T, S) = eN(S, T)-1 S, T Nếu là một phần tử đặc biệt của F đóng vai trò là các hệ số của E, thì eN (S,T) = (eN(S, T)) S, T Nếu là một separable endomorphism của E thì eN((S), (T)) = eN(S, T)deg S, T Bài toán: Tìm k thỏa mãn kP = Q trên E(Fq) với #E(Fq) = N và giả sử k tồn tại. Sử dụng phép làm yếu bài toán logarith rời rạc trên đường cong E(Fq) thành bài toán logarith rời rạc trên Thuật toán Khi (d1, d2, ,dk) = N, thực hiện các bước sau, sau mỗi bước tăng i lên 1 Chọn một điểm ngẫu nhiên . Tính bậc Mi của Si Đặt di = gcd(Mi, N) và Ti = (Mi/di)Si. Đặt = eN(P, Ti), =eN(Q, Ti). Giải bài toán logarith rời rạc = trong trường và tìm được ki (mod di) Sử dụng các giá trị ki (mod di) để tìm k (mod N) với k ki (mod di) . Giá trị k chính là kết quả cần tìm. Chứng minh Ở bước 1 và 2, chúng ta chọn một điểm và tính bậc của nó. Bước 3 tìm Ti . Đặt với R là một điểm tùy ý trên E() Khi đó:, và vì rồi giải trong Đặt kP = Q, và định nghĩa li thỏa mãn k li (mod di). Ta có: eN(kP, Ti) = eN(Q, Ti) eN(P, Ti)k = eN(Q, Ti) Vì nên (mod di) li ki (mod di) và k phải bằng ki (mod di). Như vậy, việc tìm ki sẽ phục vụ việc tìm k. Độ phức tạp thời gian Khi có các ki việc tìm k là dễ dàng, vì vậy thời gian chạy của thuật toán phụ thuộc vào việc tìm ki. Thời gian tìm ki phụ thuộc vào độ lớn của trường . Nếu m càng lớn thì tính toán càng phức tạp. Không có một tiêu chuẩn chung để chọn m phù hợp cho tất cả các đường cong elliptic. Quay trở lại bài toán tính độ phức tạp, dựa trên đặc điểm E(F)với n1, n2 thỏa mãn n1|n2. B1, B2 là các điểm trên E(F) với các bậc n1 và n2. Bất kỳ điểm Si nào tìm được cũng có thể biểu diễn dưới dạng a1B1 + a2B2 với a1, a2 nào đó. Giả sử p là một số nguyên tố pe||N. Khi đó, pe|n2. Nếu p không nguyên tố cùng nhau với a2 thì pe|n2 pe|Mi với Mi là bậc của Si. Suy ra pe|di = gcd(Mi, N). Vì Si được chọn ngẫu nhiên nên a2 cho Si cũng ngẫu nhiên, do đó xác suất để p không nguyên tố cùng nhau với a2 là 1 – 1/p. Suy ra, xác suất để pe|di là 1 – 1/p với mọi i và với mọi pe||N. Xác suất này đủ thấp để chỉ có một vài di cần cho pe|lcm(d1, d2,, dk) đúng với mọi p. Vì vậy chúng ta không cần lặp các bước của thuật toán quá nhiều lần.MOV là thuật toán hàm mũ nhỏ đầu tiên để giải bài toán EDLP với k nhỏ. Nó dựa vào tính đẳng cấu giữa đường cong elliptic và trường hữu hạn khi gcd(#E(Fq), q) = 1. Vì vậy, tính hiệu quả của nó giới hạn trong một lớp các đường cong elliptic là lớp các đường cong supersingular vì tồn tại k 6 cho các đường cong này. Với các đường cong elliptic khác (các đường cong nonsupersingular), k quá lớn để áp dụng tấn công MOV. Miyaji chứng minh rằng phép làm yếu trên hiệu quả cho các đường cong elliptic trên trường . Còn các đường cong elliptic trên trường Fp (với p là số nguyên tố lớn) tránh được cách tấn công này. Hơn nữa, Miyaji đề xuất một cách xây dựng một đường cong elliptic để việc làm yếu EDLP về DLP là không thể. Bởi vậy, không phải mọi hệ mật mã trên đường cong elliptic đều có thể bị tấn công bởi phương pháp MOV. 3.5.3. Các thuật toán tấn công khác Nhiều thuật toán tấn công khác cũng đã được chứng minh là không hiệu quả với các hệ mật mã trên đường cong elliptic. Thuật toán tấn công chỉ số áp dụng hiệu quả để giải bài toán DLP nhưng không áp dụng được cho EDLP. Giao thức trao đổi khóa trên đường cong elliptic tương tự giao thức Diffie – Hellman cũng chống lại được tấn công của Western, Miller, và tấn công với thời gian là hàm mũ nhỏ của Adleman. Thuật toán tương tự RSA của Demytko cũng an toàn với các tấn công đẳng cấu. 3.6. Những chú ý để lựa chọn đường cong Elliptic phù hợp Việc chọn một đường cong elliptic thế nào ảnh hưởng đến tốc độ, tính hiệu quả, độ dài khóa và tính an toàn của hệ mật mã trên đường cong này. Dù E, K và điểm cơ sở P E cố định và công khai nhưng việc chọn các tham số này phù hợp là bước quan trọng nhất. 3.6.1. Trường K Trước hết chúng ta xem xét sự ảnh hưởng của trường K đến cấu trúc nhóm của E(K) và các hệ mật mã trên E(K). Một đường cong elliptic trên một trường hữu hạn tạo thành nhóm Abel được sử dụng trong mật mã học. Một ví dụ là việc chọn trường giúp thực hiện các phép tính nhanh và dễ dàng triển khai được trên các thiết bị cứng. Tuy nhiên, các đường cong trên trường có thể bị tấn công bởi MOV, trong khi các đường cong trên trường Fp (p là số nguyên tố lớn) lại chống lại được kiểu tấn công này. Rõ ràng, các đường cong elliptic trên trường nguyên tố Fp và trên trường có các tính chất giúp chúng có thể thực thi được trên các thiết bị mà vẫn đảm bảo an toàn. Một chú ý nữa là việc tính số điểm trên #E(K). Với #E(K) thích hợp có thể là điều kiện cho phép thực hiện tấn công Pohlig – Hellman. Có thể dùng thuật toán đơn định thời gian đa thức Schoof để tính #E trên trường hữu hạn Fq với đặc số khác 2, 3. Tốc độ của thuật toán Schoof phụ thuộc vào kích thước và đặc số của trường K. Ví dụ với r nhỏ, tính #E() có thể nhanh hơn một chút so với tính #E(Fp) với p lớn hơn đáng kể so với 2r, nhưng khi r tăng thì tính #E() mất nhiều thời gian hơn tính #E(Fp). 3.6.2. Dạng của đường cong elliptic Trước hết, chúng ta cần xem các dạng đường cong elliptic. Có 2 lớp đường cong elliptic được dùng trong các hệ mã hóa. Supersingular Curve Menezes và Vanstone đã tìm ra các ưu điểm của các đường cong elliptic supersingular cho các hệ mật mã, đặc biệt trên trường . Một đường cong elliptic trên trường hữu hạn có q phần tử được gọi là supersingular nếu t2 = 0, q, 2q, 3q, hoặc 4q với t được định nghĩa trong định lý Hasse, t = q + 1 - #E(Fq), |t| . Tuy nhiên, các đường cong supersingular có thể bị tấn công bằng MOV. Nonsupersingular Các đường cong nonsupersingular có bất biến j khác 0. Ưu điểm của các đường cong nonsupersingular là nó cung cấp độ bảo mật tương đương như các đường cong supersingular nhưng với các trường nhỏ hơn. Độ dài khóa ngắn giúp chúng có thể được triển khai trên các thiết bị như smart card. Hơn nữa, các đường cong nonsupersingular có thể chống lại tấn công MOV, ví dụ với nhóm con cyclic cỡ 2160. 3.6.3. Phương pháp lựa chọn Có một vài phương pháp để lựa chọn các đường cong elliptic. Phương pháp tự nhiên nhất là chọn ngẫu nhiên. Chọn ngẫu nhiên một đường cong elliptic E trên trường K và một điểm cơ sở PE. K được chọn và cố định trước. Phương pháp chọn ngẫu nhiên Koblitz cho các đường cong elliptic trên trường Fq (với q lớn ) như sau: Sơ đồ 3.6.3. Phương pháp chọn ngẫu nhiên Koblitz Chọn ngẫu nhiên 3 phần tử từ Fq là x, y, a Tính b = y2 – (x3 + ax) Kiểm tra để đảm bảo phương trình x3 + ax + b = 0 không có nghiệm kép Nếu điều kiện trên không thỏa mãn quay lại bước 1 Còn lại, đặt P = (x, y) và đường cong y2 = x3 + ax + b là đường cong cần chọn. Tuy nhiên phương pháp này có thể tạo ra các đường cong không đảm bảo một số yêu cầu định trước. Một kỹ thuật cải tiến là xây dựng các đường cong với các tính chất cho trước. Cũng có thể chọn những đường cong để tạo các hệ mã hóa không phụ thuộc vào bài toán EDLP, chẳng hạn các hệ elliptic dựa trên RSA. Các hệ mật mã elliptic làm việc với các nhóm con cylic của E với phần tử sinh là điểm P. Vì vậy, việc lựa chọn P phù hợp là rất quan trọng. 3.7. Các chuẩn cho hệ mật ECC Việc đưa ra một chuẩn chung cho các hệ thống mật mã, các giao thức, các giao diện là một việc quan trọng. Việc chuẩn hóa mang lại 3 lợi ích chính: Nó cho phép sự kết hợp giữa phần cứng và phần mềm của nhiều nhà cung cấp khác nhau. Nó đưa ra một cái nhìn chuẩn cho việc đảm bảo an toàn cho các hệ thống dưới khía cạnh mật mã học. Nó cho phép có các thiết kế chuẩn cho các môi trường ứng dụng khác nhau. Các đường cong Elliptic đã được xem xét và nghiên cứu kỹ lưỡng bởi cộng đồng các nhà toán học trong hơn 10 năm và đã được khảo sát kỹ bởi các tổ chức chuẩn hóa từ năm 1995. Điều này đảm bảo rằng tính tin cậy của nó đã được kiểm chứng. Nỗ lực để có thể chuẩn hóa các hệ mật mã khóa công khai được bắt đầu từ nhiều năm trước bởi Viện nghiên cứu điện và điện tử IEEE (Institute of the Electrical and Electronics Engineers) với phiên bản P1363. Nó đưa ra định dạng và thủ tục cho 3 hệ thống mã hóa khóa công khai khác nhau bao gồm xác thực, toàn vẹn và tin cậy. ISO/IEC SC27 cũng bắt đầu xem xét các chuẩn cho ECC. Trong ANSI X