Cơ sở mật mã học - Chương 6: Các sơ đồ chữ kí số

 a = Zq´ Zq. khoá có dạng:
	K =(g1, g2, a1, a2, b1, b2)
trong đó a1, a2, b1, b2Î Zq 
	g1= aa1ba2 mod p
còn	g2= ab1bb2 mod p
Với K =(g1, g2, a1, a2, b1, b2) và x ÎZp*, ta định nghĩa 
	sigk(x) =(y1, y2) 
trong đó 
	y1= a1+xb1mod q
còn 	y2= a2+xb2mod q
Với y =(y1, y2) Î Zq´ Zq ta có:
Xác minh ver(x,y) = true Û g1g2x º ay1by2(mod p)
Bây giờ giả sử ta xác minh y bằng cách dùng K’
	ay1by2 º aa’1+ xb’1ba’ + xb’2 (mod p)
	 º aa’1ba’2 (ab’1bb’2 )x (mod p)
	 º g1g2x mod p
Như vậy, y cũng sẽ được xác minh bằng K’.
Bổ đề 6.5
Giả sử K là khoá còn y = sigK’(x). Khi đó tồn tại đúng q khoá K’ tương đương với K sao cho y= sigK’(x).
Chứng minh 
Giả sử g1và g2là các thành phần công khai của K. Ta muốn xác định số bội 4 (a1, a2, b1, b2)sao cho các đồng dư thức sau đây được thoả mãn.
 g1º aa1ba2 (mod p)
	g2º ab1bb2 (mod p)
	y1º a1+xb1(mod q)
 	y2º a2+xb2(mod q).
Vì a sinh ra G nên tồn tại các số mũ duy nhất c1, c2, a0 Î Zq sao cho
g1º ac1 (mod p)
	g2º ac2 (mod p)
và b º aa0 (mod p)
vì thế nó điều kiện cần và đủ để hệ các đồng dư thức sau đây được thoả mãn:
	c1º a1+a0a2(mod q)
 	c2º b1+a0b2(mod q)
	y1º a1+ xb1(mod q)
 	y2º a2+ xb2(mod q)
Hệ thống này có thể viết dưới dạng phương trình ma trận trong Zq như sau:
	 =	 
có thể thấy ma trận hệ thống số của phương trình có hạng là 3( hạng của một ma trận là số cực đậi của các hàng độc lập tuyến tính mà nó có). Rõ ràng, hạng ít nhất bằng 3 vì các hàng 1, 2 và 4 là độc lập tuyến tính trên Zp. còn hạng nhiều nhất cũng bằng 3 vì:
	r1 +x r2-r3-a0r4= (0,0,0,0).
Với r1 chỉ hàng thứ i của ma trận. 
 	Hệ phương trình này có ít nhâts một nghiệm nhận được bằng cách dùng khoá K.Vì hàng của ma trận hệ số bằng 3 nên suy ra rằng chiều của không gian nghiệm là 4-3=1 và có chính xác q nghiệm. 
 Tương tự như vậy ta có thể chứng minh được kết qủa sau:
Bổ đề 6.6
 Giả sử K là khoá y=sigK(x) còn verK (x’,y’)=true, trong đó x’ # x. Khi đó tồn tại ít nhất một khoá K’ tương đương với K sao cho y=sigK’(x) và y’= sigK’(x’)
 Ta hãy làm sáng tỏ hai bổ đề trên về độ mật của sơ đồ. Khi cho trước y là chữ kí hợp lệ của x, sẽ tồn tại q khoá có thể để x sẽ được kí bằng y. Song với bức điện bất kì x’¹ x, q khoá này sẽ tạo ra q khoá khác nhau trên x’. Điều đó dẫn đến định lí sau đây:
Định lí 6.7:
 Nếu cho trước sigK(x)=y và x’¹ x. Oscar có thể tính sig K(x’) với xác suất là 1/q.
 Chú ý rằng, định lí này không phụ thuộc vào khả năng tính toán của Oscar: Mức an toàn qui định đạt được vì Oscar không thể nói về q khoá có thể mà Bob đang dùng. Như vậy độ an toàn ở đây là vô điều kiện.
Tiếp tục xem xét về khái niệm Fail- Stop. Khi cho trước chữ ký y trên bức điện x. Oscar không thể tính ra được chữ ký y’ của Bob trên bức điện x’ khác. Điều này cũng có thể hiểu rằng, Oscar có thể tính được chữ ký giả mạo y’’ = sigK(x’)(sẽ được chứng minh ). Tuy nhiên, nếu đưa cho Bob một chữ ký giả mạo hợp lệ, thì anh ta có thể tạo ra “một bằng chứng về sự giả mạo ” với xác suất 1-1/q. Bằng chứng về sự giả mạo là giá trị a0=loga b (chỉ người có thẩm quyền trung tâm biết ).
 Giả sử Bob sở hữu cặp (x’,y’’) sao cho ver(x’,y’’)= true và y’’¹sigK(x’).
 Nghĩa là:
 g1g2x’ º ay”1by”2(mod p)
trong đó :y’’=(y’’1,y’’2). Bây giờ Bob có thể tính chữ ký của mình trên x’ là y’ = (y’1,y2’). Khi đó :
 	g1g2x’ º ay’1by’2(mod p)
vì thế ay”1by”2 º ay’1by’2(mod p)
Nếu viết b = aa0mod p, ta có :
 ay”1+ a0 y”2 º ay’1+ a0 y’2(mod p)
hay:
 y”+a0y”2 º y’1+a0y’(mod q)
hoặc:
 y’’1- y1’ º a0(y’2-y”2’)(mod q)
Xét thấy y’1º y’’2(mod q) vì y’ là giả mạo. Vì thế (y’2-y’’2)-1 mod q tồn tại và
 a0 =loga b = (y’’1-y’1) (y’2-y’’2)-1 mod q
Dĩ nhiên, bằng việc chấp nhận bằng chứng về sự giả mạo như vậy,ta giả thiết Bob không thểt ự tính được logarithm rời rạc loga b. Đây là gải thiết về mặt tính toán. 
 	Cuối cùng, chú ý rằng,sơ đồ chữ kí là một lần vì khóa k của Bob có thể tính dễ dàng nếu hai bức điện đều dùng K để ký. Dưới đây là ví dụ minh hoạ cách Bob tạo một bằng chứng về sự giả mạo.
Vi dụ 6.7
 Cho p=4367=2.1733+1. Phần tử a =4 có bậc là 1733 trong Z3467*
Giả sử ao =1567, ta có:
 b = 41567 mod 346=514
(Bob biết a và b song không biết a0). Giả sử Bob tập khoá bằng cách dùng a1 = 888, a2 = 1042, b1 = 786, b2 = 999. Khi đó 
 g 1=48885141024 mod 3476=3405
và g 2=4786 514999 mod 3476=2281
Tiếp theo, giả sử Bob nhận được chữ kí giả mạo (822,55) trênê bức điện 3383. Đây là chữ ký hơp lệ vì thoả mãn điều kiện xác minh.
 3405 ´ 22813384º 2282 (mod 3476) 
và 482251455º 2282(mod 3476) 
Mặt khác đây không phải là chữ kí đã được Bob xây dựng. Bob có thể tíng chữ kí của mình như sau:
(888+3383´786 mod 1733.1024+3383´999 mod 1733 )=(1504.1291)
Sau đó anh ta tính tiếp log rời rạc bí mật 
 a0 =(822-1504)(1291-55)-1 mod 1733 =1567.
Đây là bằng chứng về sự giả mạo.
6.7 các chú giải về tài liệu dẫn
 Mitchell, Piper và Wild [MPW 92] đã đưa ra một tổng quan đầy đủ về các sơ đồ chữ kí. Bài này cũng có hai phương pháp giả mạo chữ kí của Elgamal mà ta đã đưa ra trong 6.2.
Sơ đồ chữ kí Elgamal đã được nêu trong [EL 85], tiêu chuẩn chữ kí số được công bố đầu tiên vào 8/1991 bởi NIST và được chấp nhận làm tiêu chuẩn vào 12/94 [NBS 94]. Một cuộc thoả luận dài về DSS và những cuộc tranh cãi xung quanh nó vào 7/1992 được đăng trên Communication of the ACM.
Sơ đồ Lamport được mô tả trong bài báo của Diffie_Hellman [DH 76] năm 1976. Bản cải tiến củaBob và Chaum được nêu trong [BC 93]. Sơ đồ chữ kí không chối nêu trong mục 6.5 do Chaum và Van Antwerpen đưa ra trong [CVA 90]. Sơ đồ chữ kí Fail-Stop trong mục 6.6 là của Van Heyst và Pederson [VHP 93].
Một số ví dụ về các sơ đồ chữ kí “phá được ”gồm các sơ đồ của ông Schorss- Sshamir[OSS 85](cũng bị phá bởi Estes EAKMM 86) và sơ đồ hoán vị Birational của Shamir [SH94] (bị Coppessnuth, Steru và Vandeney CSV 94). Cuối cùng ESIGN là sơ đồ chữ kí của Fujioka.Okamoto và Meyaguchi [FOM 91]. Một số phiên bản của sơ đồ này đã bị phá. Song một sửa đổi trong [FOM 91] lại không bị phá.
 bài tập
6.1. Giả thiết Bob đang dùng sơ dồ Elgamal, anh ta kí hai bức điện x1 và x2 bằng chữ kí (g, d 1) và (g, d 2) tương ứng (giá trị này của g giống nhau trong cả hai chữ kí ). Cũng giả sử UCLN (g 1-g 2,p-1)=1.
a) Hãy cho biết cách tính k hiệu quả khi biết thông tin này 
Hãy mô tả cách sơ đồ chữ kí có thể bị phá.
c) Giả sử p=31847, a =5, và b =25703. Tính k và a khi cho trước chữ kí (2397 2,31396 ) vói bức điện x=8990 và chữ kí (23972, 20481 trên bứ c điện x=31415)
6.2. Giả sử I thực hiên sơ đò Elgamal với p=31847, a =5,và b =26379. Hãy viết phương trìng thực hiện công việc sau:
 a) Xác minh chữ kí (20679,11082 ) trên bức điện x=20543
 b) Xác định số mũ mật a bằng cách dùng thuật toán tối ưu hoá thời gian - bộ nhớ của Shark, sau dó xác định giá trị k ngẫu nhiên dùng trong việc kí lên bức điện x.
Giả sử Bob dùng sơ đố chữ kí Elgamal như trong ví dụ 6.1:p=467,a =2 b=132.Giả sử Bob kí lên bức điện x=100 bằng chữ kí (29,51).Hãy tính chữ kí giả mạo mà Oscar có thể lập bằng cách dùng h=100,i=45 và j =293.Hãy kiểm tra xem chữ ký vừa nhận được có thoả mãn điều kiện xác minh không. 
Chứng minh rằng phương pháp giả mạo thứ hai trên sơ đồ Elgamal (mô tả trong mục 6.2) cũng tạo ra chữ kí thoả mãn điều kiện xác minh.
Sau đây là phương án của sơ đồ Elgamal :Khoá được xây dựng tương tự theo mghĩa như trước đây:Bob chọn a Î Zp* là phần tử nguyên thuỷ. a là số mũ mật (0 £ a £ p-2) sao cho UCLN (a,p-1) =1 và a a mod p. Khoá K = (a, a, b ), ở đây a và b công khai còn a mật. Cho xÎ Z p là bức điện được kí. Bob tính chữ kí sig (x)=(g, d ), trong đó:
 g =a k mod p 
còn d =(x-k g)a-1 mod (p-1).
Sự khác nhau duy nhất so với sơ đồ Elgamal ban đầu là ở cách tính d. Hãy trả lời các câu hỏi sau liên quan đến sơ đồ cải tiến này:
a) Mô tả cách xác minh một chữ kí (g, d ) trên bức điện x bằng cách dùng công khai khoá của Bob.
b) Mô tả ưu điểm về mặt tính toán của sơ đồ cải tiến.
So sánh tóm tắt độ an toàn của sơ đồ cải tiến và sơ đồ ban đầu. 
Giả sử Bob dùng DSS với q = 101, p = 7879, a = 170, a = 75 còn b = 4567 như trong ví dụ 6.3. Xác định chữ kí của Bob trên bức điện x=5011, bằng cách dùng giá trị ngẫu nhiên k =49 và chỉ ra cách xác minh chữ kí nhận được.
Trong sơ đồ Lamport,giả sử rằng hai bức điện x và x’ bội k (k-tuple) đều do Bob kí. Cho l = d(x,x’) là toạ độ trên đó x và x ‘ khác nhau. Hãy chỉ ra cách Oscar có thể kí 2l -2 bức điện mới.
Trong sơ đồ Bob-Chaum với k = 6, n = 4, giả sử rằng các bức điện x = (0, 1,0,0,1,1) và x’ = (1,1,0,1,1) đều được kí. Xác định bức điện mới được Oscar kí khi biết chữ kí trên x và x’.
Trong sơ đồ Bob- Chaum, giả sử rằng hia bức điện x và x’ là các bội k đều do Bob kí Cho l =½f(x)Èf(x’)½. Hãy chỉ ra cách Oscar có thể kí 	 -2
 bức điện mới. 
Giă sử Bob đang dùng chữ kí không chối được của Chaum –Van Antwerpen như trong ví dụ 6.5. Nghĩa là p = 467, a = 4, a = 101, b = 449. Giả sử Bob được trình chữ kí y = 25 trên bức điện x =157 và anh ta muốn chứng minh rằng nó giả mạo. Giả sử số ngẫu nhiên của Alice là e1 = 46, e2 = 123, f1 =198, f2 =11 trong thủ tục từ chối. Hãy tính các yêu cầu c, d, của Alice và các câu trả lời C, D của Bob; chỉ ra rằng phép kiểm tra tính phù hợp của Alice sẽ thành công.
Chứng minh rằng, mỗi lớp tương đương các khoá trong sơ đồ chữ kí Fail-Stop của Pedersen-Van Hðyt chứa q2 khoá. 
Giả sử Bob đang dùng sơ đồ chữ kí Fail-Stop của Pedersen-Van Heyst với p = 3467, a =4, a 0=1567 và b =514 (dĩ nhiên Bob không biết giá trị a0).
a) Dùng yếu tố a0 =1567, xác định tất cả các khoá có thể :
K = (g1, g2, a1, a2, b1, b2) 
 sao cho sig K(42) =(1118,1449)
Gái sử sigK(42) =(1118,1449) và sigK(969) =(899,471). Không cần dùng điều kịên a0 =1567. Hãy xác định K (điều này sẽ chứng tỏ sơ đồ là dùng một lần).
 Gải sử Bob dùng sơ đồ Fail-Stop của Pedersen-Van Heyst vơi p =5087, a =25, b =1866. Giả sử K =(5065, 5067,144,874,1873,2345) và Bob tìm chữ kí (2219,458) được giả mạo trên bức điện 4785
a) Chứng minh rằng, chữ kí giả mạo này thoả mãn điều kiện xác minh nên nó là chữ kí hợp lệ. 
b) Chỉ ra cách Bob tính “ bằng chứng giả mạo a0 khi cho trước chữ kí giả mạo này. ”