Cơ sở mật mã học - Chương 5: Các hệ mật khóa công khai thác

o các ví dụ về các nhóm cyclic trong đó bài toán DL có thể được nghiên cứu.
	Thực tế các trường hữu hạn GF(2n) đã được nghiên cứu khá kĩ. Cả hai thuật toán logarithm rời rạc Shanks và Pohlig-Hellman đều làm việc trên các trường GF(2n). Phương pháp tính toán chỉ số có thể sửa đổi để làm việc trên các trương này. Thời gian tiền tính toán của thuật toán tính toán chỉ số khoảng
còn thời gian để tìm một giá trị logarithm rời rạc riêng khoảng 
Tuy nhiên, với các giá trị n lớn (n > 800), bài toán DL trong GF(2n) được coi là khó cỡ 2n phải có ít nhất một thừa số nguyên tố "lớn" ( để gây khó khăn cho cách tấn công Pohlig - Hellman).
Các đương cong Elliptic
Ta bắt đầu bằng việc định nghĩa khái niệm đường cong elliptic.
Định nghĩa 5.3
	Cho p >3 là số nguyên tố. Đường cong elliptic y2 = x3+ax+b trên Zp là một tập các cặp (x,y)ÎZp´Zp thoả mãn đồng dư thức
y2 º x3+ax+b (mod p) (5.1)
trong đó a, bÎZp là các hằng số sao cho 4a3+27b2 º 0 ( mod p) cùng với một điểm đặc biệt O được gọi là điểm vô cực.
	[Phương trình (5.1) có thể dùng để xác định một đường cong elliptic trên một trường bất kì GF(pn) với p - là số nguyên tố lớn hơn 3. Đường cong elliptic trên GF(2n) hoặc GF(3n) được xác định bằng một phương trình khác đôi chút)].
	Đường cong elliptic E có thể tạo thành một nhóm Aben bằng cách xác định một phép toán thích hợp trên các điểm của nó. Phép toán này là phép cộng và được xác định như sau ( ở đây mọi phép toán số học được thực hiện trên Zp).
Giả sử
P = (x1,y1) và Q = (x2,y2)
là các điểm trên E. Nếu x2=x1 và y2=-y1 thì P+Q = O; ngược lại P+Q = (x3,y3) trong đó:
x3 = l2-x1-x2
và	 (y2-y1)/(x2-x1) nếu P ¹ Q
	l = 
	 (3x12+a)/2y1 nếu P = Q
y3 = l(x1-x3)-y1
Cuối cùng ta xác định
P+O = O+P = P
đối với mọi P Î E. Với định nghĩa phép cộng như vậy, có thể chỉ ra rằng, E là một nhóm Aben với phần tử đơn vị O. ( phần lớn các phép kiểm tra đều khá đơn giản song việc chứng minh tính kết hợp lại rất khó).
	Cần để ý là các phần tử ngược (nghịch đảo) rất dễ tính toán. Phần tử nghịch đảo của (x,y) là (x,-y) với mọi (x,y) Î E ( ta kí hiệu phần tử này là -(x,y) do phép nhóm là phép cộng)
	Xét ví dụ sau.
Ví dụ 5.7
	Giả sử E là một đường cong elliptic y2 = x3+x+6 trên Z11. Trước tiên ta xác định các điểm trên E. Để làm điều đó, xét mỗi giá trị có thể x Î Z11, tính x3+x+6 mod 11 và thử giải phương trình (5.1) đối với y. Với giá trị x cho trước, ta có thể kiểm tra xem liệu z = x3+x+6 mod 11 có phải là một thặng dư bình phương hay không bằng cách áp dụng tiêu chuẩn Euler. Ta đã có một công thức tường minh để tính các căn bậc hai của các thặng dư bình phương theo modulo p với các số nguyên tố p º 3 (mod 4). áp dụng công thức này, ta có các căn bậc hai của một thặng dư bình phương z là:
z(11+1)/4 mod 11 = z3 mod 11
Kết quả của các phép tính này được nêu trên bảng 5.2
	Như vậy, E có tất cả 13 điểm. Với một nhóm bất kì cấp nguyên tố đều là nhóm cyclic nên dẫn đến E đẳng cấu với Z13 và một điểm bất kì ( không phải điểm vô cực) đều là phần tử sinh của nhóm E. Giả sử ta lấy phần tử sinh là (2,7) = a. Khi đó ta có thể tính các "luỹ thừa" của a ( chính là các bội của a vì phép nhóm là phép cộng). Để tính 2a = (2,7) + (2,7), trước hết ta tính:
l = (3´22+1)(2´7)-1 mod 11 
 = 2´3-1 mod 11
 = 2´4 mod 11
 = 8
Sau đó ta có: 	x3 = 82-2-2 mod 11
	 = 5
và	y3 = (8(2-5)-7) mod 11
	 = 2
Bởi vậy 2a = (5,2)
Bảng 5.2 Các điểm trên đường cong elliptic y2 = x3+x+6 trên Z11
x
x3+x+6 mod 11
Có trong QR(11)?
y
0
1
2
3
4
5
6
7
8
9
10
6
8
5
3
8
4
8
4
9
7
4
Không
Không
Có
Có
Không
Có
Không
Có
Có
Không
Có
4,7
5,6
2,9
2,9
3,8
2,9
	Bội tiếp theo là 3a = 2a+a = (5,2) + (2,7). Ta lại bắt đầu bằng viẹc tính l.
l = (7-2)(2-5)-1 mod 11
 = 5´8-1 mod 11
 = 5´7 mod 11
 = 2
Khi đó ta có x3 = 22-5-2 mod 11
	 = 8
và	y3 = 2(5-8) - 2 mod 11
	 = 3
Bởi vậy 3a = (8,3)
	Tiếp tục theo cách tương tự, có thể tính được các bội còn lại như sau:
a = (2,7) 2a = (5,2) 3a = (8,3)
4a = (10,2) 5a = (3,6) 6a = (7,9)
7a = (7,2) 8a = (3,5) 9a = (10,9)
10a = (8,8) 11a = (5,9) 12a = (2,4)
Do đó a = (2,7) thực sự là phần tử nguyên thuỷ.
	Một đường cong elliptic xác định trên Zp (p là số nguyên tố >3) sẽ có khoảng p điểm. Chính xác hơn, theo một định lý nổi tiếng của Hasse, số các điểm trên E ( kí hiệu là #E) thảo mãn bất đẳng thức sau:
	Việc tính toán chính xác giá trị của #E có khó hơn nhưng đã có một thuật toán hữu hiệu do Schoof đưa ra giúp tính toán dễ dàn hơn.( Nghĩa hữu hiệu ở đây được hiểu là thời gian chạy của thuật toán là thời gian đa thức theo log p. Thuật toán Schoof có thời gian chạy khoảng O((log p)8) phép tính trên bít và có thể thực hiện đối với các số nguyên tố p có vài trăm chữ số).
	Bây giờ giả sử có thể tính được #E. Vấn đề tiếp theo là phải tìm một nhóm con cyclic trong E sao cho bài toán DL trong nó là khó. Bởi vậy ta phải biết một vài điều về cấu trúc của nhóm E. Định lý sau đây cung cấp một thông tin đáng kể về cấu trúc nhóm của E.
Định lý 5.1
	Cho E là một đường cong elliptic trên Zp, p là số nguyên tố > 3. Khi đó, tồn tại các số nguyên n1 và n2 sao cho E là đẳng cấu với Zn1´Zn2. Ngoài ra n2 | n1 và n2 | (p-1).
	Bởi vậy nếu có thể tính được các số n1 và n2 thì ta sẽ biết rằng E có một nhóm con cyclic đẳng cấu với Zn1 và có thể dùng E để thiết lập một hẹe mật Elgamal.
Chú ý là nếu n2 = 1 thì E là một nhóm cyclic. Cũng vậy, nếu #E là một số nguyên tố hoặc là tích của các số nguyên tố khác nhau thì E là nhóm cyclic có chỉ số nhóm cyclic.
Các thuật toán Shanks và Pohlig - Hellman có thể áp dụng cho bài toán rời rạc trên đường cong Elliptic song tới nay vẫn chưa có một thuật toán thích hợp cho phương pháp tính chỉ số đối với các đường cong Elliptic.Tuy nhiên, đã có một phương pháp khai thác đẳng cấu một cách tường minh giữa các đường cong Elliptic trong trường hữu hạn. Phương pháp này dẫn đến các thuật toán hữu hiệu đối với một số lớp các đường cong Elliptic. Kỹ thuật này do Menezes, Okamoto và Vanstone đưa ra và có thể áp dụng cho một số trường hợp riêng trong một lớp đặc biệt các đường cong Elliptic (được gọi là các đường cong siêu biến, chúng đã được kiến nghị sử dụng trong các hệ thống mật mã). Tuy nhiên, nếu tránh các đường cong siêu biến thì lại xuất hiện một đường cong Elliptic có một nhóm con cyclic cỡ 2160 , đường cong này sẽ cho phép thiết lập an toàn một hệ mật miễn là bậc của nhóm con phải là bội của ít nhất một thừa số nguyên tố lớn ( nhằm bảo vệ hệ mật khỏi phương pháp tấn công của Pohlig - Hellman).
	Xét một ví dụ về phép mã Elgamal sử dụng đường cong elliptic nêu trên ví dụ 5.7.
Ví dụ 5.8.
	Giả sử a = (2,7) và số mũ mật của Bob là a = 7. Bởi vậy:
b = 7a = (7,2)
Phép mã hoá thực hiện như sau
eK(x,k) = (k(2,7),x+k(7,2))
trong đó xÎE và 0 £ k £ 12 còn phép giải mã thực hiện như sau:
dK(y1,y2) = y2-7y1
	Giả sử Alice muốn mã bản tin x = (10,9) ( là một điểm trên E). Nếu cô chọn giá trị ngẫu nhiên k=3 thì cô tính
y1 = 3(2,7)
 = (8,3)
và 	y2 = (10,9) + 3(7,2)
 = (10,9) + (3,5)
 = (10,2)
	Bởi vậy, y = ((8,3),(10,2)). Bây giờ nếu Bob nhận được bản mã y thì anh ta giải mã như sau:
x = (10,2) - 7(8,3)
 = (10,2) - (3,5)
 = (10,2) + (3,6)
 = (10,9)
Đây chính là bản rõ đúng.
Trên thực tế có một số khó khăn khi áp dụng hệ mật Elgamal trên đường cong Elliptic. Hệ thống này được áp dụng trong Zp ( hoặc trong GF(pn) với n > 1) sẽ có hệ số mở rộng bản tin là 2. Việc áp dụng đường cong Elliptic sẽ có thừa số mở rộng khoảng 4 lần. Điều này là do có xấp xỉ p bản rõ, nhưng mỗi bản mã lại gổm bốn phần tử của trường. Một trở ngại là không gian bản rõ chứa các điểm trên đường cong E và không có phương pháp nào xác định tường minh các điểm trên E
Menezes và Vanstone đã tìm ra một phương án hiệu quả hơn. theo phương án này đường cong Elliptic dùng để "che dấu", còn các bản rõ và bản mã hợp lệ là các cặp được sắp tùy ý các phần tử khác không của trường( tức là chúng không đòi hỏi phải là các điểm trên E). Điều này sẽ tạo hệ số mở rộng bản tin là 2 giống như trong hệ mật Elgamal ban đầu. Hệ mật Menezes - Vanstone được mô tả trên hình 5.10.
	Nếu trở lại đường cong y2 = x3 + x + 6 trên Z11 ta sẽ thấy rằng hệ mật Menezes - Vanstone có 10´10 = 100 bản rõ, trong khi đó hệ mật ban đầu chỉ có 13 bản rõ. Ta sẽ minh hoạ phép mã và giải mã trong hệ mật này bằng cách sử dụng đường cong trên.
Hình 3.6 Hệ mật trên đường cong Elliptic của Menezes - Vanstone
Giả sử E là một đường cong Elliptic trên Zp (p là số nguyên tố > 3) sao cho E chứa một nhóm con cyclic H, trong đó bài toán DL là bài toán khó.
Giả sử P = Zp* ´ Zp* , C = E ´ Zp* ´ Zp* ,ta định nghĩa:
	K = { (E,a,a,b) : b = a a }
trong đó aÎE. Các giá trị a và b được công khai, còn a được giữ kín.
Đối với K = (E,a,a,b), với số ngẫu nhiên bí mật k Î Z| H | 
và x = (x1,x2) Î Zp*´ Zp*, ta xác định:
	 eK (x,k) = (y0,y1,y2)
	y0 = k a
	(c1,c2) = k b
	y1 = c1x1 mod p
	và	y2 = c2y2 mod p
Với bản mã y = (y0,y1,y2), ta định nghĩa
	dK (y) = (y1c1-1 mod p, y2c2-1 mod p)
 trong đó	a y0 = (c1,c2)
Ví dụ 5.9
	Cũng như ví dụ trước, giả sử a = (2,7) và số mũ mật của Bob là 7. Khi đó
b = 7a = (7,2)
Giả sử Alice muốn mã hoá bản rõ sau:
x = (x1,x2) = (9,1)
(Cần chú ý là x không phải là một điểm trên E) và cô chọn giá trị ngẫu nhiên k = 6. Đầu tiên cô tính:
y0 = ka = 6(2,7) = (7,9)
và 	kb = 6(7,2) = (8,3)
Như vậy, c1 = 8 còn c2 = 3.
	Tiếp theo Alice tính:
y1 = c1x1 mod p = 8´9 mod 11 = 6
và 	y2 = c2x2 mod p = 3´1 mod 11 = 3
Bản mã mà cô giửi cho Bob là:
y = (y0,y1,y2) = ((7,9), 6, 3)
Khi Bob nhận được bản mã này, Trước tiên anh ta tính:
(c1,c2) = (a y0) = 7(7,9) = (8,3)
và sau đó tính:
x = (y1c1-1 mod p, y2c2-1 mod p)
 = ((6´8-1 mod 11, 3´3-1 mod 11)
 = (6´7 mod 11, 3´4 mod 11)
 = (9,1).
Đặc trưng của bài toán: I = (s1, s2, . . . ,sn, T) trong đó s1, . . ., sn và T là các số nguyên dương. Các si được gọi là các cỡ, T được gọi là tổng đích.
Vấn đề: Liệu có một véc tơ nhị phân x = (x1, . . . , xn) sao cho:
Hình 5.11. Bài toán tổng các tập con
Đây chính là bản rõ đúng.
5.3. Hệ mật xêp ba lô merkle - Hellman