Cơ sở mật mã học - Chương 9: Các sơ đồ định danh

o nó nhanh hơn.
9.4 Sơ đồ định danh Guillou - quisquater.
	Trong phần này sẽ mô tả một sơ đồ định danh khác do Guillou và Quisquater đưa ra dựa trên RSA.
	Việc thiết lập sơ đồ như sau: TA chọn 2 số nguyên tố p và q và lập tích n =pq. Giá trị của p và q được giữ bí mật trong khi n công khai. Giống như trước đây, p và q nên chọn đủ lớn để việc phân tích n không thể thực hiện được. Cũng như vậy, TA chọn số nguyên tố đủ lớn b giữ chức năng tham số mật như số mũ mật trong RSA. Giả thiết b là số nguyên tố dài 40 bít. Cuối cùng TA chọn sơ đồ chữ kí và hàm hash.
Hình 9.6: Phát dấu xác nhận cho Alice
TA thiết lập định danh cho Alice và phát chuỗi định danh ID(Alice).
Alice chọn bí mật một số nguyên u, trong đó 0 £ u £ n -1. Alice tính:
v = (u-1)b mod n
	và đưa u cho TA
TA tạo ra chữ kí:
s = sigTA(I,v)
	Dấu xác nhận:
	C(Alice) = (ID(Alice), v, s)
	và đưa cho Alice
	Dấu xác nhận do TA phát cho Alice được xây dựng như mô tả trong hình 9.6. Khi Alice muốn chứng minh danh tính của cô cho Bob, cô thực hiện giao thức hình 9.7. Ta sẽ chứng minh rằng, sơ đồ Guillou - Quisquater là đúng đắn và đầy đủ. Tuy nhiên, sơ đồ không được chứng minh là an toàn (mặc dù giả thiết hệ thống mã RSA là an toàn).
Ví dụ 9.6:
	Giả sử TA chọn p = 467, q = 479, vì thế n = 223693. Giả sử b = 503 và số nguyên mật của Alice u = 101576. Khi đó cô tính:
	v = (u-1)b mod n
	 = (101576-1)503 mod 223693
	 = 24412.
Hình 9.7: Sơ đồ định danh Guillou - Quisquater.
Alice chọn số ngẫu nhiên k, trong đó 0 £ k £ n -1 và tính:
g = kb mod n
Alice đưa cho Bob dấu xác nhận của cô C(Alice) = (ID(Alice), v, s) và g.
Bob xác minh chữ kí của TA bằng cách kiểm tra xem có thoả mãn hay không đồng dư thức:
ver(ID(Alice), v, s) = true.
Bob chọn số ngẫu nhiên r, 0 £ r £ b -1 và đưa nó cho Alice.
Alice tính:
y = k u’ mod n
và đưa y cho Bob
Bob xác minh rằng
g º vryb (mod n)
Giả sử Bob trả lời bằng yêu cầu r = 375. Khi đó Alice sẽ tính
	y = ku’ mod n
	 = 187485 ´ 101576375 mod 223693
	 = 93725
và đưa nó cho Bob. Bob xác minh thấy:
	24412 º 8988837593725503(mod 223693)
vì thế Bob chấp nhận bằng chứng về danh tính của Alice. …
Giống như trường hợp tổng quát, việc chứng minh tính đầy đủ rất đơn giản:
	vryb º (u-b)r(kur)b(mod n)
	 º u-brkbubr (mod n)
	 º kb (mod n)
	 º g (mod n)
Bây giờ ta xét đến tính đúng đắn. Ta sẽ chứng minh sơ đồ là đúng đắn miễn là không dễ dàng tính được u từ v. Vì v được lập từ u bằng phép mã RSA nên đây là giả thiết có vẻ hợp lý.
Định lí 9.4
	Giảsử Olga biết giá trị g nhờ nó cô có xác suất thành công trong việc giả danh Alice là e > 1/b trong giao thức xác minh. Khi đó Olga có thể tính u trong thời gian đa thức.
Chứng minh
	Với g nào đó, Olga có thể tính giá trị y1, y2, r1, r2 với r1 ¹ r2 sao cho:
g º 
không mất tính tổng quát, giả sử rằng r1 > r2. Khi đó ta có:
vì 0 < r1- r2 <b và b là số nguyên tố nên t = (r1 - r2)-1 mod b tồn tại và Olga có thể tính nó trong thời gian đa thức bằng thuật toán Euclidean. Vì thế ta có:
xét thấy,	(r1- r2)t = lb +1
với số nguyên dương l nào đó, vì thế:
	vlb +1 º (y2/y1)bt(mod n)
hay tương đương,
	v º (y2/y1)bt(v-1)lb(mod n).
Nâng cả hai vế lên luỹ thừa b-1 mod f(n) ta có:
	u-1º (y2/y1)t(v-1)l(mod n).
cuối cùng tính modulo đảo của cả hai vế của đồng dư thức này, ta nhận được công thức sau cho u:
	u = (y2/y1)tvl mod n
Olga có thể dùng công thức này để tính u trong thời gian đa thức. …
Ví dụ 9.7
	Giống như ví dụ trước, giả sử rằng n = 223963, b = 503, u = 101576 và v = 89888. Giả thiết Olga nghiên cứu thấy rằng:
	v401103386b º v37593725b (mod n)
Trước tiên cô tính:
	t = (r1- r2)-1 mod b
	 = (401 - 375)-1mod 503
	 = 445
Tiếp theo cô tính:
	l = ((r1- r2)t - 1)/b
	 = ((401 - 375)445 -1)/503 = 23
Cuối cùng cô có thể nhận được giá trị u mật như sau:
u = (y1/y2)tvl mod n
 = (103386/93725)4458988823 mod 233693
 = 101576
và như vậy, số mũ mật của Alice đã bị lộ. …
 9.4.1Sơ đồ định danh dựa trên tính đồng nhất.
	Sơ đồ định danh Guillou - Quisquater có thể chuyển thành sơ đồ định danh dựa trên tính đồng nhất. Điều này có nghĩa là không cần các dấu xác nhận. Thay vào đó, TA tính giá trị của u như một hàm của chuỗi ID của Alice bằng cách dùng một hàm hash công khai h trong phạm vi Zn như chỉ ra trên hình 9.8. Giao thức định danh lúc này làm việc như mô tả trong hình 9.9. Giá trị v được tính từ chuỗi ID của Alice thông qua hàm hash công khai. Để tiến hành giao thức định danh, Alice cần biết giá trị u, giá trị này chỉ TA là có thể tính được (giả thiết hệ thống mã khoá công khai RSA là an toàn). Nếu Olga cố tự xưng mình là Alice cô sẽ không thành công nếu không biết u.
Hình 9.8: Phát giá trị u cho Alice
Thiết lập danh tính của Alice và phát chuỗi định danh ID(Alice):
TA tính 
u = (h(ID(Alice)-1)a mod n
và đưa u cho Alice
Hình 9.9: Sơ đồ định danh dựa trên tính đồng nhất Guillou - Quisquater.
Alice chọn một số ngẫu nhiên k, 0 £ k £ n -1 và tính:
g = kb mod n
Alice đưa ID(Alice) và g cho Bob
Bob tính:
v = h(ID(Alice))
Bob chọn số ngẫu nhiên r, 0 £ r £ b-1 và đưa nó cho Alice.
Alice tính:
y = kur mod n
và đưa y cho Bob
Bob xác minh xem có thoả mãn hay không điều kiện dưới đây:
g = vryb(mod n)
9.5 Chuyến sơ đồ định danh thành sơ đồ chữ kí.
	Có một phương pháp chuẩn để chuyển sơ đồ định danh thành sơ đồ chữ kí. ý tưởng cơ bản là thay thế người xác minh (Bob) bằng hàm hash công khai h. Trong sơ đồ chữ kí thực hiện theo phương pháp này, thông báo không bị chặt ra (băm) trước khi được kí: Quá trình băm được tích hợp thành thuật toán kí.
	Sau đây sẽ minh hoạ biện pháp này bằng việc chuyển sơ đồ Schnorr thành sơ đồ chữ kí (hình 9.10). Thực tế, có khả năng đưa hàm hash h vào SHS và làm giảm được modulo q. Do SHS tạo ra xâu bit có độ dài 160 và q là số nguyên tố 160 bit, nên việc giảm được modulo q chỉ cần thiết khi bản tóm lược của thông báo do SHS tạo ra vượt quá q. Thậm chí trong trường hợp này, chỉ cần trừ q khỏi kết quả.
	Trong quá trình chuyển từ sơ đồ định danh thành sơ đồ chữ kí, ta đã thay yêu cầu 40 bit bằng bản tóm lược thông báo 160 bit, 40 bit là đủ đối với một yêu cầu (challenge) vì kẻ mạo danh cần có khả năng phỏng đoán yêu cầu để tính trước câu trả lời (mà sẽ được chấp nhận). Song trong phạm vi của sơ đồ chữ kí, ta cần cac bản tóm lược thông báo có kích thước lớn hơn nhiều để ngăn chặc sự tấn công thông qua việc tìm kiếm các va chạm trong hàm hash.
Hình 9.10: Sơ đồ chữ kí Schnorr.
	Cho p là số nguyên tố 512 bít sao cho bài toán logarithm rời rạc trong ZP là không giải được; cho q là số nguyên tố 160 bít chia hết cho p-1. Giả sử aÎlà căn bậc q của 1modulo p. Cho h là hàm hash trong phạm vi . Định nghĩa P=.A = ´ ZP và định nghĩa:
	K = {(p, q, a, a, v) : v º a-a(mod p)}
	Các giá trị p, q, a và v là công khai còn a mật.
Với K = (p, q, a, a, v) và với số ngẫu nhiên k mật Î, ta định nghĩa:
	sigK(x,k) = (g,y)
trong đó 
	g = ak mod p
và 
	y = k + ah(x,g) mod q.
với x,g Îvà yÎZP, định nghĩa
	ver(x, g, y) = true Û g º ayvh(x,y)(mod p)
9.6 Các chú giải và tài liệu tham khảo
Sơ đồ	định danh Schnorr nêu trong tài liệu [Sc91], sơ đồ Okamoto được đưa ra trong [OK93] còn sơ đồ Guillou - quisquater có thể tìm thấy trong [GQ88]. Một sơ đồ khác chứng minh sự an toàn dưới giả thiết tính toán hợp lý là của Brickell và McCurley [BM92].
Các sơ đồ định danh phổ biến khác chứa đựng trong sơ đồ Fiege - Fiat - Shamir [FFS88] và sơ đồ nhân hoán vị [SH90]. Sơ đồ Fiege - Fiat - Shamir được chứng minh là an toàn nhờ dùng kĩ thuật tri thức không.
Phương pháp xây dựng sơ đồ chữ kí từ các sơ đồ định danh là do Fiat và Shamir đưa ra [FS87]. Chúng cũng được mô tả và phiên bản dựa trên tính đồng nhất của sơ đồ định danh của chính họ.
Các tổng quan về các sơ đồ định danh này đã được công bố trong công trình của Burmester, Desmedt và Beth [BDB92] và công trình của Waleffe và Quisquater [DWQ93].
Các bài tập
9.1. Xét sơ đồ định danh sau đây: Alice sở hữu khoá mật n = pq, p và q là những số nguyên tố và p º q º 3 (mod 4). Các giá trị n và ID(Alice) đều do TA kí như thường lệ và lưu trên dấu xác nhận của Alice. Khi Alice muốn tự xưng danh với Bob, Bob sẽ đưa cho Alice một thặng dư bình phương theo modulo n gọi là x. Sau đó Alice sẽ tính căn bình phương y của x và đưa nó cho Bob. Khi đó Bob xác minh xem y2 có º x(mod n) hay không. Hãy giải thích tại sao sơ đồ này không an toàn.
9.2. Giả sử Alice đang dùng sơ đồ Schnorr với q = 1201, p =122503, t = 10 còn a= 11538.
	a/ Hãy kiểm tra xem a có bậc q trên không.
	b/ Giả thiết số mũ mật của Alice là a = 357, hãy tính v.
	c/ Giả sử k = 868, hãy tính g.
	d/ Giả sử Bob đưa ra yêu cầu r = 501, hãy tính câu trả lời y của Alice.
	e/ Thực hiện các tính toán của Bob khi xác minh y
9.3. Giả thiết, Alice dùng sơ đồ Schnorr với p, q, t như trong bài tập 9.2. v=51131 và giả sử Olga có thể nghiên cứu thấy rằng:
	a3v148 º a151v1077 (mod p)
Hãy chỉ ra cách Olga có thể tính số mũ mật a của Alice.
9.4. Giả sử Alice đang dùng sơ đồ Okamoto với q = 1201, p = 122503, t= 10, a1=60497 và a2 = 17163
	a/ Giả sử các số mũ mật của Alice a1=432, a2 = 423, hãy tính v.
	b/ Giả sử k1 = 389, k2 = 191, tính g
c/ Giả thiết Bob đưa ra yêu cầu r = 21. Hãy tính câu trả lời y1 và y2 của Alice
d/ Thực hiện các tính toan của Bob để xác minh y1và y2.
9.5/ Cũng giả thiết rằng Alice dùng sơ đồ Okamoto với p, q, t, a1và a2 như trong bài tập 9.4, và v = 119504.
	a/ Hãy kiểm tra xem phương trình sau có thoả mãn không:
	b/ Dùng thông tin trên để tính b1 và b2 sao cho:
	.
	c/ Giả sử rằng Alice để lộ a1=484 và a2 =935. Hãy chỉ ra cách Alice và Olga cùng nhau tính . 
9.6. Giả sử rằng, Alice đang dùng sơ đồ Quisquater với p = 503, q = 379 và b= 509.
a/ Giả sử giá trị u mật của Alice = 155863 tính v.
b/ Giả sử k = 123845, hãy tính g.
c/ Giả thiết Bob đưa ra yêu cầu r = 487. Hãy tính câu trả lời y của Alice
d/ Thực hiện các tính toán của Bob để xác minh y
9.7. Giả sử Alice đang dùng sơ đồ Quisquater với n = 199543, b = 523 và v=146152. Giả thiết Olga đã khám phá ra rằng
	v456101360b = v25736056b(mod n)
Hãy nêu cách Olga có thể tính u.