Nghiên cứu, tìm hiểu và trình bày về chữ ký số trên đường cong elliptic, ứng dụng của đường cong elliptic trong hệ thống bỏ phiếu điện tử và hệ thống tiền điện tử

và v rF 2 .Khi đó rF2 được xem là không gian vector trên F2 với chiều r. Ký hiệu d là chiều của không gian vector này. Có thể thực hiện ánh xạ 1 – 1 giữa các phần tử trong không gian vector d chiều và các d-tuple của các phần tử trong F2. Vì vậy,có2d phần tử trong không gian vector này.Vì d = r, rF2 là không gian vector r chiều. mqF là một mở rộng của Fq. 2 phần tử mqF , là liên hợp trên Fq nếu  và  là các nghiệm của cùng một đa thức tối giản bậc m trên Fq. 12 ,...,,, mqqq  là các liên hợp của mqF với Fq. mqF là một mở rộng của Fq. Một cơ sở của mqF (không gian vector trên Fq) của { 12 ,...,,, mqqq  } gồm mqF và các liên hợp của nó với Fq , được gọi là cơ sở trực giao của mqF trên Fq. Mọi trường mở rộng bậc hữu hạn của một trường hữu hạn có một cơ sở trực giao. Không gian chiếu 21 Xét L = Kn+1 \{0} với K là một trường. Với A = (a0, a1, …, an), B = {b0, b1, …, bn} L, định nghĩa một quan hệ A ~ B gồm A, B và gốc O = (0, 0,…,0) là cộng tuyến, nghĩa là tồn tại K thỏa mãn : ii ba  , (i = 0, 1, …, n). Quan hệ ~ là quan hệ tương đương và định nghĩa một phân hoạch của L. Tập thương số là không gian chiếu ký hiệu là Pn(K). Mặt phẳng chiếu là tập các lớp tương đương của bộ ba (X, Y, Z) với ( ),,( ZYX  ) ~ (X, Y, Z) ( K ). Mỗi lớp tương đương (X, Y, Z) được gọi là một điểm chiếu trên mặt phẳng chiếu. Nếu một điểm chiếu có Z  0, thì (x, y, 1) là một thể hiện của lớp tương đương với x = Z X , y = Z Y . Mặt phẳng chiếu có thể được định nghĩa là tập tất cả các điểm(x, y)của mặt phẳngAffine cộng với các điểm Z = 0. 22 1.2.4. Không gian vector K là một trường và V là một nhóm cộng Abel. V được gọi là không gian vector trên trường K nếu một toán tử K x V  V được định nghĩa thỏa mãn các điều kiện sau: a(u + v) = au + av (a + b)u = au + bu a(bu) = (ab)u 1u = u Các phần tử của V được gọi là các vector và các phần tử của K được gọi là các vô hướng. V là một không gian vector trên trường K và các v1, …, vm V. Vector trong V có dạng c1v1 + c2v2 + …+ cmvm với ci K (i = 1, …, m) là một tổ hợp tuyến tính của v1, …, vm. Tập hợp tất cả các tổ hợp tuyến tính gọi là span của v1, …,vmvà ký hiệu là span(v1, …, vm). v1, …, vm được gọi là span nếu của V nếu V = span(v1, …, vm). V là không gian vector trên trường K. Các vector v1, …, vm V được gọi là độc lập tuyến tính trên K nếu không có các vô hướng c1,…, cm K thỏa mãn: c1v1 + c2v2 + …+ cmvm = 0 Tập S = {u1, u2,…,un} của các vector tạo thành cơ sở của V khi và chỉ khi u1, u2,…,un là độc lập tuyến tính là span của V. Nếu S là một cơ sở của V thì mọi phần tử của V được biểu diễn duy nhất dưới dạng tổ hợp tuyến tính của các phần tử của S. Nếu không gian vector V có cơ sở là một số hữu hạn các vector thì bất kỳ cơ sở nào của V cũng sẽ có cùng số phần tử. Khi đó nó chính là chiều của V trên K. Nếu F là một trường mở rộng của trường K thì F là một không gian vector trên K. Chiều của F trên K được gọi là bậc mở rộng của F trên K. 23 Chương 2. ĐƯỜNG CONG ELLIPTIC Hệ thống mã khóa khóa công khai dựa trên việc sử dụng các bài toán khó giải quyết. Vấn đề khó ở đây chính là việc số lượng phép tính cần thiết để tìm ra một lời giải cho bài toán là rất lớn. Trong lịch sử 20 năm của ngành mã hóa bất đối xứng đã có nhiều đề xuất khác nhau cho dạng bài toán như vậy, tuy nhiên chỉ có hai trong số các đề xuất đó còn tồn tại đến ngày nay. Hai bài toán đó bao gồm : bài toán logarit rời rạc (discrete logarithm problem) và bài toán phân tích thừa số của số nguyên. Cho đến năm 1985, hai nhà khoa học Neal Koblitz và Victor S.Miller đã độc lập nghiên cứu và đưa ra đề xuất ứng dụng lý thuyết toán học đường cong elliptic (elliptic curve ) trên trường hữu hạn. Đường cong elliptic cũng như đại số hình học- được nghiên cứu rộng rãi trong vòng 150 năm trở lại đây và đã đạt được một số kết quả lý thuyết có giá trị. Đường cong elliptic được phát hiện lần đầu tiên vào thế kỷ 17 dưới dạng công thức Diophantine : y2 – x3 = c với c Z Tính bảo mật của hệ thống mã hóa sử dụng đường cong elliptic dựa trên điểm mấu chốt là độ phức tạp của bài toán logarit rời rạc trong hệ thống đại số. Trong suốt 10 năm gần đây, bài toán này nhận được sự quan tâm chú ý rộng rãi của các nhà toán học hàng đầu trên thế giới. Không giống như bài toán logarit rời rạc trên trường hữu hạn hoặc bài toán phân tích thừa số của số nguyên, bài toán logarit rời rạc trên đường cong elliptic chưa có thuật toán nào có thời gian thực hiện nhỏ hơn cấp lũy thừa. Thuật toán tốt nhất được biết đến hôm nay tốn thời gian thực hiện cấp lũy thừa. 24 2.1. CÔNG THỨC WEIERSTRASSE VÀ ĐƯỜNG CONG ELLIPTIC Gọi K là trường hữu hạn hoặc vô hạn. Một đường cong elliptic được định nghĩa trên trường K bằng công thức Weierstrasse : y2 + a1xy + a3y = x3 + a2x2 + a4x + a6 (1) Trong đó a1 , a2 , a3 , a4 , a5 , a6 K Đường cong elliptic trên trường k được ký hiệu E(K). Số lượng các điểm nguyên trên E ký hiệu là #E(K) , có khi chỉ đơn giản là #E. Đối với từng trường khác nhau, công thức Weierstrasse có thể được biến đổi và đơn giản hóa thành các dạng khác nhau. Một đường cong elliptic là tập hợp các điểm thỏa mãn công thức trên. Hình 1: Một ví dụ về đường cong Elliptic 2.2. ĐƯỜNG CONG ELLIPTIC TRÊN TRƯỜNG R2 Đường cong elliptic E trên trường số thực R là tập hợp các điểm (x,y) thỏa mãn công thức: y2 = x3 + a4x + a6 với a4 , a6 R (2) cùng với một điểm đặc biệt O được gọi là điểm tại vô cực (cũng là phần tử identify). Cặp giá trị (x,y ) đại diện cho một điểm trên đường cong elliptic và tạo nên mặt phẳng tọa độ hai chiều (Affine) R x R . Đường cong elliptic E trên R2 25 được gọi là định nghĩa trên R , ký hiệu là E (R). Đường cong elliptic trên số thực có thể dùng để thể hiện một nhóm (E(R), +) bao gồm tập hợp các điểm (x ,y) thuộc R x R với phép công + trên E(R). 2.2.1. Phép cộng Hình 2: Điểm ở vô cực Phép cộng điểm (ESUM) được định nghĩa trên tập E(R) của các điểm (x, y). Điểm tại vô cực 0 là điểm cộng với bất kỳ điểm nào cũng sẽ ra chính điểm đó. Như vậy,    , ,P x y E R P O O P P          3 4 6, ,P x y E R y x a a     (3) Như vậy , tương ứng với một giá trị x ta sẽ có hai giá trị tọa độ y. Điểm (x , -y ) ký hiệu là –P E(R), được gọi là điểm đối của P với : P + (-P) = (x , y) + (x ,- y) = 0 (4) Phép cộng trên E(R) được định nghĩa theo phương diện hình học . Giả sử có hai điểm phân biệt P Và Q , P, Q E(R). Phép cộng trên nhóm đường cong elliptic là P +Q = R ,R E(R). 26 Hình 3: Phép cộng trên đường cong elliptic Để tìm ra điểm R , ta nối P và Q bằng đường thẳng L. Đường thảng L sẽ cắt E tại ba điểm P , Q và -R(x , y). Điểm R (x , -y) sẽ có tung độ là giá trị đối của y. Thể hiện đường cong elliptic dưới dạng đại số , ta có: P = (x1 , y1) Q = (x2 , y2) R= P + Q = (x3 , y3) (5) Trong đó P , Q , R E (R) và : x3 = θ2 – x1 – x2 y3 = θ(x1 + x3) – y1 (6) 2 1 2 1 y y x x     nếu P ≠ Q (7) Hoặc 2 1 4 1 3 2 x a y    nếu P = Q (8) 27 Thuật toán cộng trên đường cong elliptic Input: Đường cong elliptic E(R)với các tham số a4, a6 E(R) , Điểm P = (x1, y1) E(R) và Q = (x2, y2) E(R) Output: R = P + Q, R = (x3, y3) E(R) If P = O then R ← Q và trả về giá trị R If Q = O then R ← P và trả về giá trị R If x1 = x2 then If y1 = y2 then 2 1 4 1 3 2 x a y    else if y1 = −y2 then R ← O và trả về R, else 2 1 2 1 y y x x     end if x3 = θ2 – x1 – x2 y3 = θ(x1 + x3) – y1 Trả về (x3, y3) = R 28 2.2.2. Phép nhân đôi Hình 4: Phép nhân đôi trên đường cong elliptic Xét phép nhân đôi (EDBL): nếu cộng hai điểm P, Q E(R) với P = Q thì đường thẳng L sẽ là tiếp tuyến của đường cong elliptic tại điểm P. Trường hợp này điểm –R sẽ là giao điểm còn lại của L với E. Lúc đó R = 2P. 29 2.3. ĐƯỜNG CONG ELLIPTIC TRÊN TRƯỜNG HỮU HẠN Đường cong elliptic được xây dựng trên các trường hữu hạn. Có hai trường hữu hạn thường được sử dụng: trường hữu hạn Fq với q là số nguyên tố hoặc q là 2m (m là số nguyên). Tùy thuộc vào trường hữu hạn Fq, với mỗi bậc của q, tồn tại nhiều đường cong elliptic. Do đó, với một trường hữu hạn cố định có q phần tử và q lớn, có nhiều sự lựa chọn nhóm đường cong elliptic. 2.3.1. Đường cong elliptic trên trường Fp (p là số nguyên tố) Cho p là số nguyên tố (p>3), Cho a,b Fp sao cho 4a3 + 27b2 ≠ 0 trong trường Fp . Một đường cong elliptic E(Fp) trên Fp (được định nghĩa bởi các tham số a và b) là tập hợp các cặp giá trị (x ,y) (x, y Fp) thỏa công thức: y2 = x3 + ax + b (9) cùng với một điểm 0 – gọi là điểm tại vô cực. Số lượng điểm của E(Fp) là #E(Fp) thỏa định lý Hasse: 1 2 # ( ) 1 2pp p E F p p      (10) Các phép toán của đường cong elliptic trên Fp cũng tương tự với E(R). Tập hợp các điểm trên E(Fp) tạo thành một nhóm thỏa các tính chất sau:  Tính đóng: a, b G, a + b G.  Tính kết hợp: Các phép toán trong nhóm có tính kết hợp Do đó, (a + b) + c = a + (b + c).  Phần tử trung hòa: có một giá trị 0 G sao cho a + 0 = 0 + a = a, a G.  Phần tử đối: , a G , -a G gọi là số đối của a, sao cho -a + a = a + (-a) = 0 Bậc của một điểm A trên E(Fp) là một số nguyên dương r sao cho: .... 0 r A A A    (11) 30 2.3.2. Đường cong elliptic trên trường F2m Một đường cong elliptic E(F2m) trên F2m được đĩnh nghĩa bởi các tham số a , b F2m (với b ≠ 0 ) là tập các điểm (x,y) với các x F2m , y F2m thỏa công thức: y2 + xy = x3 + ax2 + b (12) cùng với điểm 0 là điểm tại vô cực . Số lượng các điểm thuộc E(F2m) ký hiệu # E(F2m) thỏa định lý Hasse : 1 2 # ( ) 1 2pp p E F p p      (13) Trong đó q = 2m . Ngoài ra # E(F2m) là số chẵn Tập hợp các điểm thuộc E(F2m) tạo thành một nhóm thỏa các tính chất sau:  0 + 0 = 0  (x , y) + 0 = (x , y) , (x ,y) E(F2m)  (x , y) + (x, x + y) = 0 , (x ,y) E(F2m) Khi đó (x, x + y) là điểm đối của (x , y) trên E(F2m)  Việc xử lý được thực hiện trên hai hệ tọa độ khác nhau: hệ tọa độ Affine và hệ tọa độ quy chiếu. Với các hệ tọa độ khác nhau, việc tính toán trên đường cong cũng khác nhau. 2.3.3. Các phép toán trên đường cong elliptic trong hệ tọa độ Affine Hệ mã hóa đường cong elliptic dựa trên bài toán logarit rời rạc trên E(F2m) và các tính toán cơ bản trên đường cong elliptic. Phép nhân được thể hiện là một dãy các phép cộng và phép nhân đôi các điểm của đường cong elliptic. Giống như các phép tính trên đường cong elliptic trên số thực, phép cộng và phép nhân đôi được định nghĩa trên hệ tọa độ. Xét đường cong elliptic E trên F2m trong hệ tọa độ Affine. Cho P = (x1 , y1) , Q = (x2 , y2) là hai điểm trên đường cong elliptic E(F2m) . Điểm đối của P là: –P = (x1 , y1+x1) E(F2m). 31 Nếu Q ≠ -P thì P +Q = R = (x3, y3) E(F2m) 32 Thuật toán cộng điểm trong hệ tọa độ Affine Input Đường cong elliptic E(F2m) với các tham số a2 , a6 F2m Điểm P = (x1, y1) E(F2m) và Q = (x2, y2) E(F2m) Output : R = P +Q ,R = (x3, y3) E(F2m) If P = O then R ← Q và trả về giá trị R If Q = O then R ← P và trả về giá trị R If x1 = x2 then If y1 = y2 then 1 1 1 y x x    và x3 ← θ2 + θ + a2 Else If y2 = x1 + y1 then R ← O và trả về R, Else If 1 2 1 2 y y x x     End If x3 ← θ2 + θ + x1 + x2 + a2 y3 ← (x1 + x3)θ + x3 + y1 Trả về (x1, y3) =R 2.3.4. Các phép toán trên đường cong elliptic trong hệ tọa độ chiếu Đường cong E(F2m) có thể được xem là tương đương với tập hợp các điểm E’(F2m) trên mặt phẳng chiếu P2(F2m) thỏa mãn công thức: y2z + xyz = x3 +a2x2z2 +a6z3 (16) Sử dụng hệ tọa độ chiếu , thao tác tính nghịch đảo cần cho phép cộng và phép nhân đôi điểm trong hệ Affine có thể được loại bỏ. 33 2.3.5. Chuyển đổi giữa hệ tọa độ Affine và hệ tọa độ chiếu Mọi điểm (a,b) E(F2m) trong hệ tọa độ Affine có thể được xem là bộ ba (x,y,z) trong E’(F2m) trong hệ tọa độ chiếu với x = a , y =b , z= 1. Hơn nữa , một điểm (tx , ty , tz) trong hệ tọa độ chiếu với t ≠ 0 được xem như trung với điểm (x,y,z). Như vậy , chuyển đổi giữa hệ aìffine và hệ tọa độ chiếu như sau : M(a,b) = M’(a,b,1) (17) '( , , ) , ,1 ,p q p qN p q r N N r r r r             (18) 2.3.6. Các phép toán đường cong trong hệ tọa độ chiếu Phương pháp trình bày công thức của phép cộng và nhân đôi trong hệ tọa chiếu tương tự với hệ tọa độ Affine. Cho P’ = (x1: y1: z1) E’(F2m) , Q’ = (x2: y2: z2) E’(F2m) và P’ ≠ -Q’ trong đó P’ , Q’ thuộc hệ tọa độ quy chiếu. Do P’ = (x1/z1: y1/z1:1), ta có thể áp dụng công thức cộng và nhân cho điểm P(x1/z1: y1/z1) và Q(x2,y2) cho E(F2m) trong hệ Affine để tìm P’ + Q’ = R’ (x’3: y’3:1). Từ đó ta có : 2 ' 3 22 1 B B Ax a A A z     (19) ' ' '1 1 3 3 3 1 1 ( )x yBy x x A z z     Trong đó A = (x2 z1+ x1) và A = (y2 z1+ y1). Đặt z3 = A3z1 và x3 = x’3z3 , y3 = y’3z3 ,nếu P + Q = (x3: y3: z3) thì : x3 = AD, y3 = CD + A2( Bx1 + Ay1) (20) z3 = A3z1 Với C = A + B và D = A2 ( A + a2z1) + z1BC Tương tự 2P = (x3: y3: z3) với x3 = AB , y3 = x14A + B(x12 +y1z1 + A) (21) z3 = A3 34 Trong đó A = x1z1 và B = a6z14 + x14 . Điểm kết quả có thể được chuyển trở lại sang hệ Affine bằng cách nhân với z3-1 . Như vậy sẽ không có thao tác tính nghịch đảo trọng hệ tọa độ chiếu. Do đó chỉ cần 1 phép nghịch đảo sau một dãy các phép cộng và nhân đôi để chuyển sang hệ Affine. So sánh số lượng cá thao tác đối với các phép toán trên đường cong elliptic trọng hệ tọa độ Affine và hệ tọa độ chiếu Tọa độ Affine Tọa độ chiếu Thao tác ESUM EDBL ESUM EDBL Nhân 2 2 13 7 Nghịch đảo 1 1 0 0 2.3.6. Phép nhân đường cong Thuật toán nhân điểm trong hệ tọa đội Affine Input : P E(F2m) và c F2m Output : Q = c x P   0 2 , 0,1 , 1 n i i i n i c b b b     Q ← P For i= n – 1 downto 0 Gán Q ← Q + Q (Affine EDBL) If bi = 1 then Gán Q ← Q + P (Affine ESUM) End if End for Trả về Q Phép nhân được định nghĩa như một dãy các phép cộng : ... c Q c P P P P      35 Thuật toán nhân điểm trong hệ tọa độ chiếu Input : P E(F2m) và c F2m Output : Q = c x P   0 2 , 0,1 , 1 n i i i n i c b b b     Biểu diễn P trong hệ tọa độ chiếu : P’ Gán Q’ ← P’ For i = n -1 downto 0 Q’ ← Q’ + Q’ (Projective EDBL) If bi = 1 then Q’ ← Q’ + P’ (Projective ESUM) End if End for Biểu diễn Q’ trong hệ tọa độ Affine ta được Q Trả về Q 36 2.4 BÀI TOÁN LOGARIT RỜI RẠC TRÊN ĐƯỜNG CONG ELLIPTIC Bài toán logarit rời rạc trên đường cong elliptic (ECDLP): Cho E là một đường cong elliptic và P E là một điểm có bậc n . Cho điểm Q E , tìm số nguyên dương m (2 ≤ m ≤ n-2) thỏa mãn công thức Q = m x P . Hiện nay chưa có thuật toán nào được xem là hiệu quả để giải quyết bài toán này. Để giải bài toán logarit rời rạc trên đường cong elliptic, cần phải kiểm tra tất cả các giá trị m [2...n-2]. Nếu điểm P được chọn lựa cẩn thận với n rất lớn thì việc giải bài toán ECDLP xem như không khả thi. Việc giải bài toán ECDLP khó khăn hơn việc giải quyết bài toán logarit rời rạc trên trường số nguyên thông thường. 37 Chương 3. CHỮ KÝ SỐ TRÊN ĐƯỜNG CONG ELLIPTC 3.1. CHỮ KÝ SỐ 3.1.1. Khái niệm chữ ký số Để chứng thực nguồn gốc hay hiệu lực của một tài liệu (ví dụ: đơn xin học, giấy báo nhập học, ... ), lâu nay người ta dùng chữ ký “tay”, ghi vào phía dưới của mỗi tài liệu. Như vậy người ký phải trực tiếp “ký tay“ vào tài liệu. Ngày nay các tài liệu được số hóa, người ta cũng có nhu cầu chứng thực nguồn gốc hay hiệu lực của các tài liệu này. Rõ ràng không thể “ký tay“ vào tài liệu, vì chúng không được in ấn trên giấy. Tài liệu “số” ( hay tài liệu “điện tử”) là một xâu các bit (0 hay 1), xâu bít có thể rất dài (nếu in trên giấy có thể hàng nghìn trang). “Chữ ký” để chứng thực một xâu bít tài liệu cũng không thể là một xâu bit nhỏ đặt phía dưới xâu bit tài liệu. Một “chữ ký” như vậy chắc chắn sẽ bị kẻ gian sao chép để đặt dưới một tài liệu khác bất hợp pháp. Những năm 80 của thế kỷ 20, các nhà khoa học đã phát minh ra “chữ ký số” để chứng thực một “tài liệu số”. Đó chính là “bản mã” của xâu bít tài liệu. Người ta tạo ra “chữ ký số” (chữ ký điện tử) trên “tài liệu số” giống như tạo ra “bản mã” của tài liệu với “khóa lập mã”. Như vậy “ký số” trên “tài liệu số” là “ký” trên từng bit tài liệu. Kẻ gian khó thể giả mạo “chữ ký số” nếu nó không biết “khóa lập mã”. Để kiểm tra một “chữ ký số” thuộc về một “tài liệu số”, người ta giải mã “chữ ký số” bằng “khóa giải mã”., và so sánh với tài liệu gốc. Ngoài ý nghĩa để chứng thực nguồn gốc hay hiệu lực của các tài liệu số hóa, mặt mạnh của “chữ ký số” hơn “chữ ký tay” là ở chỗ người ta có thể “ký” vào tài liệu từ rất xa trên mạng công khai. Hơn thế nữa, có thể “ký” bằng các thiết bị cầm tay (VD điện thoại di động) tại khắp mọi nơi (Ubikytous) và di động (Mobile),miễn là kết nối được vào mạng. Đỡ tốn bao thời gian, sức lực, chi phí, … “Ký số” thực hiện trên từng bit tài liệu, nên độ dài của “chữ ký số” ít nhất cũng bằng độ dài của tài liệu. Do đó thay vì ký trên tài liệu dài, người ta thường dùng “hàm băm” để tạo “đại diện” cho tài liệu, sau đó mới “Ký số” lên “đại diện” này. 38 Chữ ký thông thường Chữ ký số * Vấn đề ký một tài liệu: Chữ ký chỉ là một phần vật lý của tài liệu * Vấn đề về kiểm tra: Chữ ký được kiểm tra bằng cách so sánh nó với chữ ký xác thực khác. Tuy nhiên, đây không phải là một phương pháp an toàn vì nó dễ bị giả mạo * Vấn đề ký một tài liệu: Chữ ký số không gắn kiểu vật lý vào bức thông điệp nên thuật toán được dùng phải “ không nhìn thấy” theo một cách nào đó trên bức thông điệp. * Vấn đề về kiểm tra Chữ ký số có thể kiểm tra nhờ dùng một thuật toán kiểm tra công khai. Như vậy, bất kì ai cũng có thể kiểm tra được chữ ký số. Việc dùng chữ ký số an toàn có thể chặn được giả mạo 3.1.2. Sơ đồ chữ ký số Sơ đồ chữ ký là bộ năm (P, A, K, S, V ), trong đó: P là tập hữu hạn các văn bản có thể. A là tập hữu hạn các chữ ký có thể. K là tập hữu hạn các khoá có thể. S là tập các thuật toán ký. V là tập các thuật toán kiểm thử. Với mỗi khóa k  K, có thuật toán ký Sig k  S, Sig k : P A, có thuật toán kiểm tra chữ ký Ver k  V, Ver k : P  A đúng, sai, thoả mãn điều kiện sau với mọi x  P, y  A: Đúng, nếu y = Sig k (x) Ver k (x, y) = Sai, nếu y  Sig k (x) 39 Chú ý : Người ta thường dùng hệ mã hóa khóa công khai để lập “Sơ đồ chữ ký số”. Ở đây khóa bí mật a dùng làm khóa “ký”, khóa công khai b dùng làm khóa kiểm tra “chữ ký”. Ngược lại với việc mã hóa, dùng khóa công khai b để lập mã., dùng khóa bí mật a để giải mã. Điều này là hoàn toàn tự nhiên, vì “ký” cần giữ bí mật nên phải dùng khóa bí mật a để “ký”. Còn “chữ ký” là công khai cho mọi người biết, nên họ dùng khóa công khai b để kiểm tra. Ví dụ : Chữ ký số RSA (Đề xuất năm 1978) a. Sơ đồ chữ ký *Tạo cặp khóa (bí mật, công khai) (a, b) : Chọn bí mật số nguyên tố lớn p, q, tính n = p * q, công khai n, đặt P = C = Zn Tính bí mật (n) = (p-1).(q-1). Chọn khóa công khai b < (n), nguyên tố với (n). Khóa bí mật a là phần tử nghịch đảo của b theo mod (n): a*b  1 (mod (n). Tập cặp khóa (bí mật, công khai) K = (a, b)/ a, b  Zn , a*b  1 (mod (n)). * Ký số: Chữ ký trên x  P là y = Sig k (x) = x a (mod n), y  A. (R1) * Kiểm tra chữ ký: Verk (x, y) = đúng  x  y b (mod n). (R2) b. Chú ý: - So sánh giữa sơ đồ chữ ký RSA và sơ đồ mã hóa RSA ta thấy có sự tương ứng. - Việc ký chẳng qua là mã hoá, việc kiểm thử lại chính là việc giải mã: Việc “ký số” vào x tương ứng với việc “mã hoá” tài liệu x. Kiểm thử chữ ký chính là việc giải mã “chữ ký”, để kiểm tra xem tài liệu đã giải mã có đúng là tài liệu trước khi ký không. Thuật toán và khóa kiểm thử “chữ ký” là công khai, ai cũng có thể kiểm thử chữ ký được. 40 c. Ví dụ Chữ ký trên x = 2 *Tạo cặp khóa (bí mật, công khai) (a, b) : Chọn bí mật số nguyên tố p=3, q=5, tính n = p * q = 3*5 = 15, công khai n. Đặt P = C = Zn = Zn . Tính bí mật (n) = (p-1).(q-1) = 3 * 4 = 8. Chọn khóa công khai b = 3 < (n), nguyên tố với (n) = 8. Khóa bí mật a = 3, là phần tử nghịch đảo của b theo mod (n): a*b  1 (mod (n). * Ký số: Chữ ký trên x = 2  P là y = Sig k (x) = x a (mod n)= 2 3 (mod 15) = 8, y  A. * Kiểm tra chữ ký: Verk (x, y) = đúng  x  y b (mod n)  2  8 b (mod 15). 41 3.2. MỘT SỐ SƠ ĐỒ CHỮ KÝ SỐ TRÊN ĐƯỜNG CONG ELLIPTIC 3.2.1. Sơ đồ chữ ký ECDSA Để 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ố: 1. Kích thước q của trường, hoặc q = p (p > 2) hoặc q = 2m. 2. 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) 3. Hai phần tử xG và yG thuộc Fq xác định điểm cơ sở G = (xG, yG). 4. Bậc n của điểm G với n > 2160 và qn 4 Sinh khóa : 1. Chọn số ngẫu nhiên d trong khoảng [2, n – 1] làm khóa bí mật. 2. Tính Q = dG làm khóa công khai. Ký trên bản rõ m 1. Chọn một số ngẫu nhiên k, 12  nk 2. Tính kG = (x1, y1). 3. Tính r = x1 mod n. Nếu r = 0, quay lại bước 1. 4. Tính k-1 mod n. 5. Tính s = k-1 (m + dr) mod n. Nếu s = 0 quay lại bước 1. 6. Chữ ký trên thông điệp m là (r, s) Kiểm tra chữ ký 1. Kiểm tra r và s có là các số tự nhiên trong khoảng [2, n – 1] không. 2. Tính w = s-1 mod n 3. Tính u1 = mw mod n và u2 = rw mod n 4. Tính X = u1G + u2Q = (xX, yX) 5. Nếu X = O thì phủ nhận chữ ký. Ngược lại tính v = xX mod n. 6. Chữ ký chỉ được chấp nhận nếu v = r. 42 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. 43 3.2.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 ** pp xP  , ** pp xZExZC  , ta định nghĩa: }:),,,{(  aaEK  với E . Các giá trị  và  là công khai, a là bí mật. Với ),,,(  aEK  chọn một số ngẫu nhiên ||HZk  .Khi đó, với ** 21 ),( pp xZZxxx  ta định nghĩa ),,(),( dckxsig K  trong đó : kyy ),( 21 pxhashyc mod)(1  packd mod exhashtruedcxverK  )(),,(  cdyy ),( 21 pyce mod1 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. 44 3.2.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 1. 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). 2. 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) ( baxxy  32 trong trường hợp p>3) với 0274 23  ba 3. Với 2 phần tử xp và yp trong GF(pn) xác định một điểm G = (xG, yG) trên E(GF(pn)) (G  O với O là điểm gốc). 4. Giả sử điểm G có bậc q 5. Hàm chuyển c(x) : np n ZpGF )( được cho bởi:     1 0 )( n i i k pcxc npZ ,     1 0 n i i kcx  )( npGF , pci 0 Việc sinh khóa bao gồm: 1. Chọn một khóa bí mật d là số nguyên ngẫu nhiên trong [2, q – 1] 2. Tính khóa công khai Q, là một diểm trên E sao cho Q = dG. Ký mù Giả sử Jerry yêu cầu Tom 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: 1. Tom sinh ra cặp khóa ( Rk , ) theo cách sau: chọn ngẫu nhiên ]1,1[  qk và tính ),( kk yxGkR  . Sau đó tính r :     1 0 )( n i i kik pcxcr , trong đó     1 0 n i i kik cx  , pc ki 0 rồi gửi r và R cho Jerry 45 2. Jerry chọn các tham số làm mù ]1,1[,  qba , tính R trên E sao cho R = a R + bG = (xk, yk) và tính r = c(xk) và rarmm  1)( . Sau đó gửi m cho Tom ( m là m sau khi đã bị làm mù). 3. Tom tính )(mod)( qkrmds  , rồi gửi s cho Jerry. 4. Jerry nhận được s , xóa mù để có được chữ ký s trên m bằng cách tính bsas  Cặp (r, s) là một chữ ký ECC trên m. Chứng minh Cặp (r, s) là một chữ ký ECC Harn của thông điệp m và sơ đồ ký trên là một sơ đồ chữ ký mù trên ECC. Việc xác minh tính hợp lệ của chữ ký Harn được thực hiện như sau: 1. Tìm một điểm V trên E sao cho sG – (m + r)Q = (xv, yv). 2. Sử dụng hàm chuyển để tính c(xe) và kiểm tra ))(mod( ? qxcr v . Nếu đúng thì (r, s) được chấp nhận là chữ ký hợp lệ. Để chứng minh giao thức trên thực sự tạo ra chữ ký có tính chất “mù”, chúng ta chỉ ra rằng mỗi người ký có một cặp duy nhất (a, b) là tham số làm mù, với ]1,1[,  qba . Với smrkR ,,,, và một chữ ký hợp lệ (r, s) của m ta có: )(mod))(( 1 qrmrma  )(mod qsasb  Ta phải chứng minh: bGRaR  . Thực vậy, RQrmsGdrGdmGsG GradrarmadGsGkrdmdaGsGGkaGsasGGkabGRa    )( ))(()( 1 46 Ví dụ Xét việc tạo chữ ký mù Harn trên đường cong elliptic y2 = x3 + x + 13 trên trường nguyên tố Z31. Chọn điểm cơ sở G = (9, 10). #E(Z31) = 34 và G là phần tử bậc 34. Khi đó q = 34. Sinh chữ ký Khóa bí mật d = 11, khi đó khóa công khai Q = dG = 11G = (22, 22). Giả sử Jerry có thông điệp m0 với đại là m = 17 và cần Tom ký lên m sao cho Tom không biết nội dung m. 1. Khi nhận được yêu cầu ký từ Jerry, Tom chọn ngẫu nhiên ]1,2[  qk = 20 và tính GkR  = 20P = (26, 10), r = 26. Tom gửi r và R cho Jerry. 2. Jerry chọn các tham số làm mù ]1,1[,  qba với a = 5, b = 7. Tính R trên E với R = a R + bG = 5 R + 7G = 5G = (25, 16), r = 25. Jerry làm mù m thành m với rarmm  1)( = (17 + 25)5-1 – 26 (mod 34) = 30. Jerry gửi m = 30 cho Tom. 3. Tom tính )(mod)( qkrmds  = 11(30 + 26) + 20 (mod 34) = 24. Tom gửi s = 24 cho Jerry. 4. Jerry nhận được s , xóa mù để có được chữ ký s trên m bằng cách tính bsas  =5 x 24 + 7(mod 34)=25. Cặp (25, 25) là chữ ký của Tom trên m=17. Xác minh tính hợp lệ của chữ ký Jerry muốn chứng minh rằng anh ta có chữ ký của Tom trên m = 17 và chữ ký muốn chứng minh chữ ký đó là (25, 25). Các thao tác chứng minh diễn ra như sau: 1. Tìm một điểm V trên E sao cho sG – (m + r)Q = (xv, yv) = 25G – (17 + 25)Q = 25P – 8Q = 25G – 88G = 5G (mod 34) = (25, 16). 2. Kiểm tra r ?  xv. Nếu Jerry cung cấp một chữ ký giả (r’, s’)  (r, s) thì điều kiện kiểm tra r ?  xv không thỏa mãn nên chữ ký sẽ bị phủ nhận. 47 3.2.4. Sơ đồ đa chữ ký mù của Harn trên EC Đa chữ ký hiểu được hiểu là chữ ký được tạo thành bởi nhiều người ký. Có những văn bản cần được ký bởi một số người có thẩm quyền thay vì một người nhằm bảo đảm tính an toàn. Đa chữ ký mù những người ký không biết về nội dung văn bản ký. 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 ti ,.1 . Việc sinh khóa được thực hiện qua các bước: 1. 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] 2. Khóa công khai của người ký Ui là điểm: Qi = diG = ( ii dd yx , ), ti ,.1 3. Khóa công khai cho tất cả người ký là: Q = Q1 +…+ Qt = dG = (xd, yd) với d = d1 + …+ dt (mod q) Ký mù trên m 1. Người ký Ui sinh một lần cặp ( ii Rk , ) bằng cách chọn ngẫu nhiên ]1,2[  qki và tính ),( ii kkii yxGkR  . Ui tính các ir , i = 1,…, t với )( iki xcr  rồi gửi ir và iR cho Ban thư ký. 2. Ban thư ký chọn các tham số làm mù ]1,1[,  qba , tìm điểm R trên E sao cho ),( kk yxbQRaR  trong đó tRRR  1 và tQQQ  1 . Ban thư ký tính ))(mod( qxcr k và rabrmm  1)( . Sau đó, gửi m và r đến cho từng người ký Ui. 3. Ui tính chữ ký )(mod)( qkrmds iii  , i=1,…, t. Sau đó gửi is tới Ban thư ký. 4. Ban thư ký tính ),()( ii eeii yxQrmGs  và kiểm tra ))(mod( ? qxcr iei  , i=1,…, t. Chữ ký mù nhóm ECC là cặp (r, s) trong đó: )(mod...1 qsss t và )(mod qass  . 48 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à đa chữ ký mù. Việc xác minh tính hợp lệ của đa chữ ký (r, s) của thông điệp m được thực hiện như sau: 1. Tìm một điểm trên E sao cho ),()( ee yxQrmsG  . 2. Sử dụng hàm chuyển để tính c(xe) và kiểm tra ))(mod( ? qxcr e . Nếu đúng thì (r, s) được chấp nhận. Dễ dàng để xác minh rằng RQrmsG  )( Để chứng minh rằng giao thức ký trên tạo ra chữ ký 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 ]1,1[,  qba . Với các rmsrkR iiii ,,,,, và cặp chữ ký hợp lệ (r, s) của thông điệp m, chúng ta có: )(mod1 qssa  , )(mod)( qrmarmb  Ta phải chỉ ra rằng bQRaR  . Ta có: RQrmsG QrmGsaQrmQrmaQrmGsa QrmarmRRabQRa t i t i ii t        )( )()()()))(( ))()(()..( 1 1 1 49 3.3. MỘT SỐ PHƯƠNG PHÁP TẤN CÔNG HỆ ECC 3.3.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 kG = Q trên E(Fq) với #E(Fq) = N, giả sử k tồn tại thực sự. Thuật toán 1. Chọn số nguyên m > N 2. Tính mG 3. Với i = 0 đến i = m-1 tính (và lưu lại) iG 4. Với j = 0 đến j = m-1 tính (và lưu lại) Q – jmG 5. Sắp xếp danh sách trong bước 3 và 4 theo một thứ tự nhất định 6. 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 iG = Q – jmG 7. 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), mk  00 . Đặt k1 = (k – k0) / m. Ta sẽ có: k = k0 + mk1, với mk  10 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 iG = Q – jmG  (i + jm)G =Qhay 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( N ). Bước 4 cần O( N ). Thuật toán sắp xếp trong bước 5 được thực hiện trong O(log( N ) N ) thời gian. Bước 6 được thực hiện trong O( N ) thời gian. Bước 7 cũng được thực hiện trong O( N ) thời gian. Bỏ qua các yếu tố logarith rời rạc ( N đủ lớn để bài toán DLP là khó giải), thì thời gian thực hiện của thuật toán là hàm mũ của N . 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. 50 3.3.2. Phương pháp tấn công MOV Phương pháp 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 mqF 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.  1|  NN xFx . Như vậy, N 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ạ: ][][: NxENEeN  n thỏa mãn: 1. eN là song tuyến tính với mọi biến 2. 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. 3. eN (T, T) = 1 T 4. eN(T, S) = eN(S, T)-1  S, T 5. Nếu  à 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 6. 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 kG = 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 mqF 51 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 1. Chọn một điểm ngẫu nhiên )( mqi FES  . 2. Tính bậc Mi của Si 3. Đặt di = gcd(Mi, N) và Ti = (Mi/di)Si. 4. Đặt i1 = eN(G, Ti), i2 =eN(Q, Ti). 5. Giải bài toán logarith rời rạc iki1 = i2 trong trường mqF 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) i . 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 ),( iN TRe với R là một điểm tùy ý trên E( mqF ) Khi đó: 1),(),(),(),(  OReSMRedTReTRe NiiNiN d iN d , và vì 21 , mqd F  rồi giải ik ii 12   trong mqF Đặt kG = Q, và định nghĩa li thỏa mãn k  li (mod di). Ta có: eN(kG, Ti) = eN(Q, Ti)  eN(G, Ti)k = eN(Q, Ti)  iki 21   Vì 11 di nên i k ii 12   (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 mqF . 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. 52 Quay trở lại bài toán tính độ phức tạp, dựa trên đặc điểm E(F mq )  21 nn ZZ  với n1, n2 thỏa mãn n1|n2. B1, B2 là các điểm trên E(F mq ) 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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 rF2 . 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. 53 Chương 4 . ỨNG DỤNG CHỮ KÝ SỐ TRÊN ĐƯỜNG CONG ELLIPTIC Các hệ mật trên đường cong elliptic (ECC) có thể được sử dụng hiệu quả trong các thiết bị không dây như là Cell phone , PDA , Smart card... Vì ECC có thể hoạt động trên các thiết bị nhỏ (bộ nhớ nhỏ, bộ tính toán bé, số “cổng” ít, ít năng lượng). Mà vẫn đảm bảo độ mật cao. Với ECC chỉ cần sử dụng các khóa có độ dài nhỏ, nhưng vẫn hiệu quả như các hệ mật khác có độ dài gấp nhiều lần. Ví dụ hệ mật RSA dùng khóa có độ dài 1024 bit , nhưng ECC chỉ cần khóa 160 bit đã mang lại độ mật tương tự. Mặt khác, ECC còn tính nhanh hơn gấp 4 lần. Khóa RSA 1024bit có thể thỏa đáng giao dịch ngày nay, nhưng đến cuối thập kỷ này, để bảo đảm độ mật cần thiết, phải sử dụng khóa RSA 2048 bit. Trong khi đó, để có được độ mật tương tự , ECC chỉ cần khóa 203 bit. Hơn thế nữa thời gian tính toán chỉ bằng 1/10 , chưa kể đến việc ECC sinh khóa nhanh hơn RSA. Các hoạt động kinh tế xã hội (thanh toán, rút tiền, bỏ phiếu, đấu thầu , góp ý kiến) diễn ra mọi nơi mọi lúc. Các thiết bị cầm tay có kết nối an toàn từ xa (Smart card , E-token..). Chắc chắn sẽ được sử dụng nhiều để tiết kiệm thời gian và sức lực. Khi đó không thể quên công nghệ ECC. Hai ứng dụng là phổ biến trên thế giới có thể áp dụng ECC, đó là Bỏ phiếu điện tử và Hệ thống tiền điện tử. 54 4.1.ỨNG DỤNG TRONG BỎ PHIẾU ĐIỆN TỬ Theo phương thức bỏ phiếu điện tử , mỗi lá phiếu phải có Thông tin định danh. Nó có thể là một con số x nào đó và phải khác nhau. Trên mỗi lá phiếu phải có chữ ký trên số định danh x , thì lá phiếu mới mới có giá trị để bầu cử. Nếu cử tri chuyển ngay Số định danh x cho ban kiểm phiếu ký thì lập tức họ xác định mối liên hệ giữa cử tri và x (ví dụ qua địa chỉ Internet nơi người gửi ). Đó là điều cử tri không mong muốn gây rắc rồi sau này. Để tránh tình huống này, cử tri đổi x thành y trước khi đưa cho ban kiểm phiếu ký xác nhận. Ban kiểm phiếu ký vào y, mà không biết đó là số định danh x đã che dấu (làm mù). Họ trao chữ ký trên y là z cho cử tri. Cử tri xóa mù trên z sẽ được chữ ký ban kiểm phiếu trên số định danh x, như vậy cử tri có quyền bầu cử. Để phòng tránh sự gian lận thông đồng giữa một người nào đó trong ban kiểm phiếu với cử tri. Hệ thống dùng “Đa chữ ký mù” để bảo đảm sự nhất trí cao khi cấp quyền bỏ phiếu cho cử tri. 4.1.1. Quy trình bỏ phiếu điện tử Giai đoạn chuẩn bị Các thành phần kỹ thuật của hệ thống bỏ phiếu cũng như chuẩn bị cơ cấu tổ chức. Người kiểm phiếu và nhân viên bầu cử được chỉ định. Các nhân viên bầu cử thực hiện tất cả các bước trong quá trình bỏ phiếu như điều hành hệ thống máy tính, cung cấp dữ liệu cần thiết cho hệ thống. Người kiểm tra cuộc bầu cử sẽ điều khiển toàn bộ quá trình bầu cử bằng cách chỉ đạo các nhân viên bầu cử nhờ việc kiểm tra sự hoạt động của hệ thống máy tính. Hơn nữa, BKP cũng được chỉ định. Đây là người chịu trách nhiệm về kết quả bầu cử. Cuối cùng, danh sách các cử tri cũng được thiết lập. Trong bước này, quan trọng nhất là cơ chế định danh người gửi dùng để sử dụng trong quá trình bỏ phiếu của cử tri. Giai đoạn bỏ phiếu Giai đoạn các cử tri thực hiện bỏ phiếu. Các cử tri phải có một hình thức định danh tính hợp lệ của lá phiếu. Thêm vào đó, một vài kỹ thuật (mã hoá) cần được áp dụng để bảo đảm tính toàn vẹn của lá phiếu. Giai đoạn Kiểm phiếu và thông báo kết quả BKP sẽ tính toán kết quả dựa vào các lá phiếu đã bỏ, sau đó sẽ công bố kết quả. 55 4.1.2. Sử dụng ECC trong bỏ phiếu điện tử 1 .Cấp quyền bầu cử Khi đã được kiểm traCử tri cần BĐK ký trên bí danh của mình. BĐK sẽ sử dụng sơ đồ chữ ký mù Harn để ký như sau: Sơ đồ 4.4.1. Sơ đồ ký mù của BĐK khi cấp quyền bầu cử cho cử tri 1. Cử tri gửi ID m của mình đến BĐK để xin cấp chữ ký. 2. BĐK có cặp khóa công khai/ bí mật trên đường cong elliptic là (d, Q). Khi có yêu cầu ký, BĐK chọn ngẫu nhiên ]1,2[  qk và tính ),( kk yxGkR  . Tính     1 0 )( n i i kik pcxcr , trong đó     1 0 n i i kik cx  , pc ki 0 . Gửi r và R cho cử tri. 3. Cử tri chọn các tham số làm mù ]1,1[,  qba , tính R trên E sao cho R = a R +bG = (xk, yk) và tính r = c(xk) và rarmm  1)( . Sau đó gửi m cho BĐK (m là m sau khi đã bị làm mù). 4. BĐK ký mù (ký trên văn bản đã bị làm mù): )(mod)( qkrmds  , rồi gửi s cho cử tri.Jerry nhận được s , xóa mù để có được chữ ký s trên m bằng cách tính bsas  Cặp (r, s) là một chữ ký ECC trên định danh m của cử tri. Để tăng tính an toàn và công bằng của cuộc bầu cử nhằm tránh gian lận tại giai đoạn đăng ký (cấp quyền bầu cử cho những cử tri không hợp lệ), nên thiết lập BĐK gồm t thành viên (ít nhất là 2). Khi đó, để ký lên định danh của cử tri, t thành viên này có thể dùng giao thức đa chữ ký mù 3.2.4 của Harn để thực hiện việc ký. 2. Bỏ phiếu Sau khi đã đăng ký và được cấp quyền bầu cử, cử tri sẽ tiến hành bỏ phiếu và giả sử lá phiếu của cử tri thứ i là vi. Cử tri tiến hành các bước như sau: 56 1. Nhúng nội dung của lá phiếu lên E, khi đó vi được thể hiện thành một điểm (Pm)iE. Cử tri phải mã hóa Pm bằng khóa công khai của BKP. 2. Giả sử khóa bí mật của BKP là aT thì khóa công khai sẽ là aTG. Cử tri chọn ngẫu nhiên ri và Pm được mã hóa thành một cặp điểm trên E: Vi = (C1, C2) = (riG,( Pm)i + ri(aTG) 3. Cử tri gửi điểm Vi đến BKP. 3. Kiểm phiếu Khi các lá phiếu được chuyển về BKP, nó sẽ được trộn bằng một máy trộn ngẫu nhiên, nhằm ngăn chặn các tiêu cực trong quá trình bỏ phiếu. BKP nhận được các Vi = (C1, C2). Do tính chất đồng cấu của hệ mã ECC được sử dụng, BKP không cần giải mã từng lá phiếu mà có thể tính tổng các lá phiếu đã mã hóa rồi từ đó tính được kết quả cuối cùng của cuộc bỏ phiếu. Để giải mã từng lá phiếu, BKP tính: C2 – aT(C1) = Pm + k(aTG) – aT(kG) = Pm Tuy nhiên, không giải mã từng lá phiếu, BKP vẫn tính được kết quả cuộc bầu cử theo công thức:      N i iT N i N i im CaCP 1 1 1 1 2 57 4.2. ỨNG DỤNG TRONG HỆ THỐNG TIỀN ĐIỆN TỬ Một đồng tiền điện tử C có 2 thông tin quan trọng nhất : Số Seri và giá trị của đồng tiền. Cũng như đồng tiền thông thường(bằng giấy). Hệ thống phải bảo đảm các yêu cầu sau: Ngần hàng phát hành đồng tiền C “khó” nhận biết đồng tiền này(ví dụ : Số seri) của người mua hàng đã rút ra từ tài khoản của họ. Ngân hàng thu nạp đồng tiền C cũng khó thể biết đồng tiền C đã được nhận từ người bán. Mặt khác người bán hàng khó thể biết C được rút từ tài khoản nào. Để thực hiện yêu cầu trên, hiện nay người ta dùng “Chữ ký mù” để ký lên đồng tiền C. Như vậy tiền điện tử C không lưu lại dấu vết của những ai đã “tiêu” (Spending) nó. Trên thực tế đồng tiền C không chỉ do một ngân hàng phát hành, nó có thể là đồng tiền chung của nhiều ngân hàng. Vì vậy nó phải mang dấu ấn của các ngân hàng liên quan. Trong trường hợp này Tổ chức liên ngân hàng sẽ thống nhất một “Đa chữ ký mù” để ký lên đồng tiền C. Quá trình giao dịch sẽ chia thành bốn giai đoạn: 4.2.1. Tạo tiền ecash 1. Sau khi biết được số tiền cần phải thanh toán, phần mềm tại máy khách hàng sẽ sinh ra dãy số ngẫu nhiên, dãy số này được xem như là dãy số tiền tương trưng cho số tiền cần phải rút từ ngân hàng. Một thừa số mù sẽ được đưa vào dãy số, thừa số mù này sẽ khiến cho ngân hàng không thể lưu giữ danh sách dãy số tiền và không biết được nó được tiêu xài ở đâu. 2. Dãy số đã được làm mù này sẽ được gửi đến ngân hàng mà khách hàng đã có tài khỏan trước đấy. 3. Ngân hàng sẽ kiểm tra thông tin được gửi đến. Sau đó ngân hàng sẽ ký lên thông điệp(dãy số), vì dãy số đã được làm mù nên ngân hàng sẽ không biết nó là của ai, tại thời điểm đấy tài khoản của khách hàng sẽ bị trừ một khoảng tương ứng. 4. Ngân hàng gửi dãy số sau khi được ký đến khách hàng. 5. Khách hàng sẽ giải mù những dãy số này, như vậy dãy số cộng với chữ ký của ngân hàng đến lúc này thực sự trở thành những đồng tiền số có giá trị và giá trị của chúng được bảo đảm bởi ngân hàng, và những đồng tiền số này sẽ chứa trên máy tính của người sửa dụng. 58 4.2.2 Tiêu tiền ecash 1. Khách hàng gửi một yêu cầu mua sắm tới Người bán hàng. 2. Người bán hàng gửi một yêu cầu ngược đến cyberwallet software(số tiền cần thanh toán, thông tin về sản phẩm yêu cầu). 3. Khách hàng xác nhận giao dịch và đồng ý giao dịch thì phần mềm sẽ thu nhập những đồng tiền cần thiết đủ số tiền yêu cầu . 4. Chuyển tiền đến người bán hàng 4.2.3 Đổi tiền 1. Trước khi chấp nhận thanh toán này, Người bán hàng phải kiểm tra tính hợp lệ của những đồng tiền số bằng cách gửi chúng đến ngân hàng. 2. Ngân hàng kiểm tra tính hợp lệ của những đồng tiền số và đồng thời xem nó có được tiêu lần thứ hai không bằng cách dựa vào dữ liệu lưu trữ của ngân hàng. Nếu những đồng tiền là hợp lệ, Ngân hàng sẽ phá huỷ những đồng tiền số này, đồng thời lưu dãy số này vào dữ liệu của những tiền đã sử dụng. Và chuyển một lượng tiền đến tài khoản của người bán. 4.2.4 Kết thúc giao dịch Sau khi những đồng tiền đã được kiểm tra hợp lệ, người bán hàng gửi một biên nhận đến khách hàng và giao dịch tài chính được hoàn thành . 59 KẾT LUẬN Hệ thống mã hóa khóa công cộng ra đời đã giải quyết các hạn chế của mã hóa quy ước. Mã hóa khóa công cộng sử dụng một cặp khóa, một khóa (thông thường là khóa riêng) dùng để mã hóa và một khóa (khóa riêng) dùng để giải mã. Mã hóa khóa công cộng giúp tránh bị tấn công khi trao đổi khóa do khóa để giải mã (khóa riêng) không cần phải truyền hoặc chia sẻ với người khác. Ngoài ra,mỗi người chỉ cần sở hữu một cặp khóa công cộng – khóa riêng và người gởi thông tin chỉ cần giữ khóa công cộng của người nhận do đó số lượng khóa cần phải quản lý giảm khá nhiều. Mỗi người chỉ cần lưu trữ bảo mật một khóa riêng của chính mình. Tuy nhiên, do nhu cầu mã hóa và giải mã bằng hai khóa khác nhau trong cùng một cặp khóa nên để bảo mật, kích thước khóa công khai – khóa riêng lớn hơn rất nhiều so với khóa công khai. Do đó tốc độ mã hóa khóa công cộng chậm hơn tốc độ mã hóa khóa quy ước. Tốc độ mã hóa bằng phần mềm của thuật toán DES nhanh hơn khoảng 100 lần so với mã hóa RSA với cùng mức độ bảo mật. Mã hóa khóa công khai dựa trên hai vấn đề lớn của toán học là bài toán logarit rời rạc và bài toán phân tích thừa số của số nguyên. Phương pháp RSA dựa trên bài toán phân tích thừa số của số nguyên tố và đã được đưa ra từ cuối thập niên 70. Phương pháp ECC dựa trên bài toán logarit rời rạc trên trường số của đường elliptic curve (ECDLP) chỉ mới được đưa ra từ năm 1985. Một ưu điểm của ECC là khả năng bảo mật cao với kích thước khóa nhỏ dựa vào mức độ khó giải quyết của vấn đề ECDLP. Đây chính là một tính chất rất hữu ích đối với xu hướng ngày nay là tìm ra phương pháp tăng độ bảo mật của mã hóa khóa công cộng với kích thước khóa được rút gọn. Kích thước khóa nhỏ hơn giúp thu gọn được kích thước của chứng nhận giao dịch trên mạng và giảm kích thước tham số của hệ thống mã hóa. Kích thước khóa nhỏ giúp các hệ thống bảo mật dựa trên ECC giảm thời gian tạo khóa.Thời gian tạo khóa thường rất lớn ở hệ thống RSA. Do có kích thước khóa nhỏ và khả năng phát sinh khóa rất nhanh nên ECC rất được quan tâm để áp dụng cho các ứng dụng trên môi trường giới hạn về thông lượng truyền dữ liệu, giới hạn về khả năng tính toán, khả năng lưu trữ. ECC thích hợp với các thiết bị di động kỹ thuật số như handheld, PDA, điện thoại di động và thẻ thông minh (smart card). 60 Các hệ thống ECC đã và đang được một số công ty lớn về viễn thông và bảo mật trên thế giới quan tâm phát triển. Nổi bật trong số đó là Certicom (Canada) kết hợp với Đại học Waterloo đã nghiên cứu và xem ECC như là chiến lược phát triển bảo mật chính của công ty. Certicom cung cấp dịch vụ bảo mật dựa trên ECC. Ngoài ra, một số công ty khác như Siemens (Đức), Matsushita (Nhật), Thompson (Pháp) cũng nghiên cứu phát triển ECC. Mới đây, RSA Security Laboratory – phòng thí nghiệm chính của RSA – đã bắt đầu nghiên cứu và đưa ECC vào sản phẩm của mình. Tuy nhiên, ECC vẫn có một số hạn chế nhất định. Hạn chế lớn nhất hiện nay là việc chọn sử dụng các tham số đường cong và điểm quy ước chung như thế nào để thật sự đạt được độ bảo mật cần thiết. Hầu hết các đường cong được đưa ra đều thất bại khi áp dụng vào thực tiễn. Do đó hiện nay số lượng đường cong thật sự được sử dụng không được phong phú. NIST đề xuất một số đường cong elliptic curve đã được kiểm định là an toàn để đưa vào sử dụng thực tế trong tài liệu FIPS 186-2. Ngoài ra, đối với các tham số mang giá trị nhỏ, mức độ bảo mật của ECC không bằng RSA (khi e = 3). Đối với một số trường hợp RSA vẫn là lựa chọn tốt do RSA đã chứng minh được tính ổn định trong một khoảng thời gian khá dài. ECC vẫn còn non trẻ và cần được kiểm định trong tương lai tuy nhiên ECC cung cấp khả năng ứng dụng rất lớn trong lĩnh vực mã hóa khóa công cộng trên các thiết bị di động và smart card. Tương lai ECC sẽ được nghiên cứu đưa vào thực tiễn phổ biến hơn. Kết quả chính của khóa luận là : 1. Tìm hiểu , nghiên cứu tài liệu để hệ thống lại các vấn đề sau :  Khái niệm đường cong Elliptic  Chữ ký số trên đường cong Elliptic 2. Nghiên cứu tài liệu và thực tế để hiểu biết ứng dụng của chữ ký số trên ECC vào bỏ phiếu điện tử và dùng tiền điện tử. 61 TÀI LIỆU THAM KHẢO [1] PGS.TS Trịnh Nhật Tiến, 2008. Giáo trình An toàn dữ liệu. Trường Đại học công nghệ – ĐHQGHN. [2] ThS. Trương Thị Thu Hiền, 2006. Hệ mật đường cong elliptic và ứng dụng trong bỏ phiếu điện tử. Trường Đại học công nghệ – ĐHQGHN. [3] TS. Dương Anh Đức, 2005. Mã hóa và ứng dụng. Trường Đại học khoa học tự nhiên– Đại học Quốc gia thành phố Hồ Chí Minh. [4] PGS.TS Trịnh Nhật Tiến, ThS Trương Thị Thu Hiền, 2005. Chữ ký mù bội trên đường cong elliptic và ứng dụng. Trường Đại học công nghệ – ĐHQGHN. [5] Constantin Popescu, 1999, Blind Signature and Blind Multisignature Schemes using Elliptic Curves [6] Peter Landrock, 2005, Practical Electronic Voting Schemes, ECC conference, Copenhagen [7] Thomas Coffee, 2004, Elliptic Curves and Modern Cryptosystems. [8] Joe Hurd, course notes 2005, Elliptic Curve Cryptography – A case study in formalization using a higher order logic theorem prover, Oxford University. [9] [10] [11]