Cơ sở mật mã học - Chương 8: Phân phối và thỏa thuận về khóa

 thức ba lần.
Hình 8.7: Giao thức thoả thuận khoá MTI.
Ta đã đưa ra một trong các giao thức MIT. Việc thiết lập chúng giống như giao thức phân phối khoá trước Diffie – Hellman. Giả thiết số nguyên tố p và phần tử nguyên thuỷ a là công khai. Mỗi người sử dụng U đều có chuỗi ID(U), số mũ mật aU (0 £ aU £ p-2) và giá trị công khai tương ứng:
TA có sơ đồ chữ kí với thuật toán xác minh (công khai) verTA và thuật toán kí mật sigTA.
Mỗi người sử dụng U sẽ có dấu xác nhận:
	C(U) = (ID(U), bU, sigTA(ID(U), bU)).
Trong đó bU được thiết lập như trên.
Giao thức thoả thuận khoá MTI được đưa ra trên hình 8.7. Cuối giao thức U và V đều tính cùng một khoá:
	K =
Dưới đây là ví dụ minh hoạ giao thức này:
Ví dụ 8.3.
Giả sử p = 27803, a = 5. Giả sử U chọn aU = 21131: sau đó cô ta tính:
	bU = 521131 mod 27803 = 21420.
được đóng trên giấy xác nhận của cô. Cũng như vậy, V chọn aV = 17555. Sau đó anh ta sẽ tính:
	bV =517555 mod 27803 = 17100.
được dặt trên giấy xác nhận của anh.
Bây giờ giả sử rằng U chọn rU =169, sau đó cô gửi giá trị:
	sU = 5169 mod 27803 = 6268.
đến V. Lúc đó giả sử V chọn rV = 23456, sau đó anh ta gửi giá trị:
	sU = 523456 mod 27803 = 26759
đến U.
Bây giờ U tính khoá:
	KU,V =
	 = 626817555 2142023456 mod 27803
	 = 21600.
Như vậy, U và V đã tính cùng một khóa. …
Thông tin được truyền trong giao thức được miêu tả như sau:
(sơ đồ)
Hãy xét độ mật của sơ đồ. Không khó khăn nhận thấy rằng, độ mật của giao thức MTI trước tấn công thụ động đúng bằng bài toán Diffie – Hellman. Cũng như nhiều giao thức, việc chứng minh tính an toàn trước tấn công chủ động không phải đơn giản, chúng ta sẽ không thử chứng minh bất cứ điều gì về điều này và tự hạn chế đến một số đối số không hình thức.
Đây là một mối nguy hiểm có thể xem xét: Khi không dùng chữ kí trong suốt quá trình thực hiện giao thức, có thể xuất hiện tình huống không có sự bảo vệ nào trước tấn công xâm nhập vào điểm giữa. Quả thực, có khả năng W có thể chọn các giá trị mà U và V gửi cho nhau. Dưới đây mô tả một tình huống quan trọng có thể xuất hiện:
(sơ đồ)
Trong trường hợp này, U và V sẽ tính các khoá khác nhau: U tính
	K =
Trong khi đó V tính:
	K =
Tuy nhiên, W không thể tính toán ra khoá của U và V vì chúng đòi hỏi phải biết số mũ mật aU và aV tương ứng. Thậm chí ngay cả khi U và V tính ra các khoá khác nhau (mà dĩ nhiên là không dùng chúng) thì W cũng không thể tính được khoá nào trong chúng. Nói cách khác, cả U lẫn V đều được bảo đảm rằng, người sử dụng khác trên mạng chỉ có thể tính được khoá mà họ tính được. Tính chất này đôi khi được gọi là xác thực khoá ẩn (implicit key authentication)
8.4.3 Thoả thuận khoá dùng các khoá tự xác nhận
	Trong phần này, ta mô tả một phương pháp thoả thuận khoá do chính Girault đưa ra không cần dấu xác nhận. Giá trị của khoá công khai và danh tính người sở hữu nó sẽ ngầm xác thực lẫn nhau.
	Sơ đồ Girault kết hợp các tính chất của RSA và các logarithm rời rạc. Giả sử n = pq, p =p1+1, q = 2ql+1, còn p, q, p1và q1 đều là các số nguyên tố lớn. Nhóm nhân Zn* là đẳng cấu với Zp*´Zq*. Bậc cực đại của phần tử bất kì trong Zn* bởi vậy là bội chung nhỏ nhất của p - 1 và q - 1, hoặc 2p1q1. Cho a là phân tử có bậc 2p1q1. Khi đó nhóm cyclic của Zn* do a tạo ra là thiết lập thích hợp của bài toán logarithm rời rạc.
	Trong sơ đồ Girault, chỉ TA biết được phân tích nhân tử của n. Các giá trị n và a là công khai, song p, q, p1 và q1 đều là mật. TA chọn số mũ mã công khai RSA, kí hiệu là e. Số mũ giải mã tương ứng bí mật là d (nhớ rằn d = e-1mod f(n)).
	Mỗi người sử dụng U có một chuỗi ID(U) như trong các sơ đồ trước đây. U nhận được khoá tự xác nhận công khai pU từ TA như nêu trên hình 8.8. Nhận xét rằng, U cần TA giúp đỡ để tạo pU. Cũng chú ý rằng:
	bU = pUe + ID(U) mod n
Hình 8.8: Nhận khoá tự xác nhận từ TA
U chọn số mũ mật aU và tính:
bU =
U đưa aU và bU cho TA
TA tính:
pU = (bU - ID(U))d mod n
TA đưa pU cho U
Có thể tính từ pU và ID(U) bằng thông tin công khai có sẵn.
Giao thức thoả thuận khoá Girault được đưa ra trên hình 8.9. Thông tin truyền đi trong giao thức như sau:
ID(U), pU, 
ID(V), pV,
	U	V
Cuối giao thức, U và V tính khoá:
Dưới đây là một ví dụ về trao đổi khoá trong sơ đồ Girault.
Ví dụ 8.4:
	Giả sử p =839, q = 863. Khi đó n = 724057 và f(n) = 722356. Phần tử a=5 có bậc 2p1q1 = f(n)/2. Giả sử TA chọn d = 125777 làm số mũ giải mã RSA, khi đó e = 84453.
	Giả sử U có ID(U) = 500021 và aU = 111899. Khi đó bU = 488889 và pU =650704. Cũng giả thiết rằng V có ID(V) = 500022 và aU = 123456. Khi đó bV = 111692 và pV = 683556.
	Bây giờ U và V muốn trao đổi khoá. Giả sử U chọn rU =56381, nghĩa là sU=171007. Tiếp theo, giả sử V chọn rV = 356935, nghĩa là sV =320688.
Khi đó cả U lẫn V sẽ tính cùng một khoá K = 42869. …
Hình 8.9: Giao thức thoả thuận khoá của Girault
U chọn rU ngẫu nhiên và tính
su =
U gửi ID(U), pU và sU cho V.
V chọn rV ngẫu nhiên và tính
sV =
V gửi ID(V), pV và sV cho U
U tính:
K = 
	Và V tính:
	K =
Xét cách các khoá tự xác thực bảo vệ chống lại một kiểu tấn công. Vì các giá trị bU, pU và ID(U) không được TA kí nên không có cách nào để ai đó xác minh trực tiếp tính xác thực của chúng. Giả thiết thông tin này bị W - người muốn giả danh U - giả mạo (tức là không hợp tác với TA để tạo ra nó). Nếu W bắt đầu bằng ID(U) và giá trị giả b’U. Khi đó không có cách nào để cô ta tính được số mũ a’U tương ứng với b’U nếu bài toán logarithm rời rạc khó giải. Không có a’U, W không thể tính được khoá.
	Tình huống tương tự nếu W hoạt động như kẻ xâm nhập giữa cuộc. W sẽ có thể ngăn được U và V tính ra khoá chung, song W không thể đồng thời thực hiện các tính toán của U và V. Như vậy, sơ đồ cho khả năng xác thực ngầm như giao thức MTI.
	Bạn đọc có thể tự hỏi tại sao U được yêu cầu cung cấp các giá trị aU cho TA. Quả thực, TA có thể tính pU trực tiếp từ bU mà không cần biết aU song điều quan trọng ở đây là TA sẽ được thuyết phục rằng, U biết aU trước khi TA tính pU cho U.
	Điểm này được minh hoạ bằng cách chỉ ra sơ đồ có thể bị tấn tông nếu TA phát bừa bãi các khoá công khai pU cho những người sử dụng mà không kiểm tra trước hết xem họ có sở hữu các aU tương ứng với các bU của họ hay không. Giả sử W chọn một giá trị giả a’U và tính giá trị tương ứng:
Đây là cách anh ta có thể xác định khoá công khai tương ứng
	p’U =(b’U - ID(U))d mod n
W sẽ tính:
	p’W = b’W - ID(U) + ID(W)
và sau đó đưa b’W và ID(W) cho TA. Giả sử TA phát ra khoá công khai
	p’W =(b’W - ID(W))d (mod n)
cho W. Nhờ dùng yếu tố:
	b’W - ID(W) º b’U - ID(U) (mod n)
có thể suy ra rằng: p’W = p’U.
ID(U), pU, 
ID(V), pV, 
ID(U), p’U, 
ID(V), p’V, 
	Cuối cùng, giả sử U và V thực hiện giao thức còn W thay thế thông tin như sau:
U	 V	W
Xét thấy V sẽ tính khoá:
trong khi U sẽ tính khoá
W có thể tính K’ như sau:
Như vậy, W và V chia sẻ nhau một khoá, song V nghĩ anh ta đang chia khoá với U. Như vậy, W sẽ có thể giải mã được bức điện mà V gửi cho U.
8.5 Các chú ý và tài liệu tham khảo.
	Blom đã đưa ra sơ đồ phân phối khoá của ông trong [BL85]. Các bài báo có tính chất tổng quát hoá cũng có trong một số bài báo khác của ông [BDSHKVY93] và của Beimel và Chor [BC94].
	Diffie và Hellman đưa ra thuật toán trao đổi khoá của họ trong [DH76]. ý tưởng về trao đổi khoá cũng được Merkle đưa ra độc lập trong [ME78]. Những ý kiến về trao đổi khoá xác thực được lấy từ Diffie, Van Oorschot và Wiener [DVW92].
	Phiên bản thứ 5 về Kerobos được mô tả trong [KN93]. Còn bài báo gần đây nhất về Kerobos xem trong [SC94] của Schiller.
	Các giao thức của Matsumoto, Takashima và Imai có thể tìm thấy trong [MTI86]. Phân phối khoá tự xác nhận được giới thiệu trong Girault [GIR91]. Sơ đồ mà ông đưa ra thực sự là sơ đồ phân phối khoá trước: Bản cải tiến sơ đồ thoả thuận khoá dựa trên [RV94].
	Hai tổng quan gần đây về phân phối khoá và thoả thuận khoá là của Rueppel và Van Oorschot [RV94] và Van Tilburg [VT93].
Bài tập
8.1 Giả sử sơ đồ Blom với k =1 được thực hiện cho tập 4 người sử dụng, U, V, W và X. Giả thiết p = 7873, rU = 2365, rV =6648, rW = 1837 còn rX = 2186. Các đa thức mật g như sau:
	gU(x) = 6018 + 6351x
	gV(x) = 3749 + 7121x
	gW(x) = 7601 + 7802x
	gX(x) = 635 + 6828x
a/ Tính khoá cho mỗi cặp người sử dụng, xác minh rằng mỗi cặp nhận được một khoá chung (nghĩa là KU,V = KV,U v.v...)
b/ Chỉ ra cách W và X cùng nhau tính khoá KV,U
8.2 Giả thiết sơ đồ Blom với k = 2 được thực hiện cho tập 5 người sử dụng U, V, W, X và Y. Giả thiết p = 97, rU = 14, rV = 38, rW = 92, rX =69 còn rY = 70. Các đa thức mật g như sau:
	gU(x) = 15 + 15x + 2x2
	gV(x) = 95 + 77x + 83x2 
	gW(x) = 88 + 32x + 18x2
	gX(x) = 62 + 91x + 59x2
	gY(x) = 10 + 82x + 52x2
a/ Chỉ ra cách U và V tính khoá KU,V = KV,U
b/ Chỉ ra cách W, X và Y cùng nhau tính khoá KU,V
Hình 8.10: Bài toán MTI
Bài toán: I =(p, a, b, g, d, e) trong đó p là số nguyên tố, a Î Z*P là phần tử nguyên thuỷ còn b, g, d, e ÎZ*P
Mục tiêu: Tính 
8.3. Giả thiết U và V tiến hành trao đổi khoá theo sơ đồ Diffie - Hellman với p = 27001 và a = 101. Giả sử U chọn aU = 21768 và V chọn aV = 9898. Hãy chỉ ra các tính toán mà U và V thực hiện và xác định khoá mà họ tính được.
8.4. Giả thiết U và V tiến hành giao thức MTI với p = 30113, a = 52. Giả sử U có aU = 12385. Hãy chỉ ra các tính toán mà cả U và V thực hiện và xác định khoá mà họ tính được.
8.5. Nếu đối phương thụ động cố gắng tính K do U và V xây dựng bằng giao thưc MTI (hình 8.10), khi đó anh ta phải đối mặt với bài toán MTI. Chứng minh rằng thuật toán bất kì giải được bài toán MTI thì cũng có thể giải được bài toán Diffie - Hellman và ngược lại.
8.6. Xét sơ đồ định danh Girault trong đó p = 167, q = 179 và vì thế n = 29893. Giả sử a = 2 và e = 11101.
a/ Tính d.
b/ Cho trước ID(U) = 10021 và aU = 9843, tính bU và pU. Cho trước ID(V) = 10022 và aV = 7692, hãy tính bV và pV
c/ Chỉ ta cách có thể tính bU từ pU và ID(V) bằng cách dùng số mũ công khai e. Tương tự, chỉ ra cách tính bV từ pV và ID(V).
d/ Giả sử U chọn ra rU = 15556 và V chọn ra rV = 6420. Hãy tính sU và sV và chỉ ra cách U và V tính khoá chung của họ.