Giáo trình Lý thuyết mật mã - Chương 8: Phân phối và thoả thuận về khóa - Nguyễn Hoàng Cương

Nội dung text: Giáo trình Lý thuyết mật mã - Chương 8: Phân phối và thoả thuận về khóa - Nguyễn Hoàng Cương

1. Vietebooks Nguyễn Hoàng Cương ch−ơng 8 phân phối và thoả thuận về khoá 8.1 Giới thiệu: Chúng ta đã thấy rằng, hệ thống mã khoá công khai có −u điểm hơn hệ thống mã khoá riêng ở chỗ không cần có kênh an toàn để trao đổi khoá mật. Tuy nhiên, đáng tiếc là hầu hết các hệ thống mã khoá công khai đều chậm hơn hệ mã khoá riêng, chẳng hạn nh− DES. Vì thế thực tế các hệ mã khoá riêng th−ờng đ−ợc dùng để mã các bức điện dài. Nh−ng khi đó chúng ta lại trở về vấn đề trao đổi khoá mật. Trong ch−ơng này, chúng ta sẽ thảo luận vài biện pháp thiết lập các khoá mật. Ta phân biệt giữa phân phối khoá và thoả thuận vể khoá. Phân phối khoá đ−ợc định nghĩa là cơ chế một nhóm chọn khoá mật và sau đó truyền nó đến các nhóm khác. Còn thoả thuận khoá là giao thức để hai nhóm (hoặc nhiều hơn) liên kết với nhau cùng thiết lập một khoá mật bằng cách liên lạc trên kênh công khai. Trong sơ đồ thoả thuận khoá, giá trị khoá đ−ợc xác định nh− hàm của các đầu vào do cả hai nhóm cung cấp. Giả sử, ta có một mạng không an toàn gồm n ng−ời sử dụng. Trong một số sơ đồ, ta có ng−ời uỷ quyền đ−ợc tín nhiệm (TA) để đáp ứng những việc nh− xác minh danh tính của ng−ời sử dụng, chọn và gửi khoá đến ng−ời sử dụng Do mạng không an toàn nên cần đ−ợc bảo vệ tr−ớc các đối ph−ơng. Đối ph−ơng (Oscar) có thể là ng−ời bị động, có nghĩa là hành động của anh ta chỉ hạn chế ở mức nghe trộm bức điện truyền trên kênh. Song mặt khác, anh ta có thể là ng−ời chủ động. Một đối ph−ơng chủ động có thể làm nhiều hành vi xấu chẳng hạn: 1. Thay đổi bức điện mà anh ta nhận thấy là đang đ−ợc truyền trên mạng. 2. Cất bức điện để dùng lại sau này. 3. Cố gắng giả dạng làm những ng−ời sử dụng khác nhau trên mạng. Mục tiêu của đối ph−ơng chủ động có thể là một trong những cái nêu sau đây: 1. Lừa U và V chấp nhận khoá “không hợp lê” nh− khoá hợp lệ (khoá không hợp lệ có thể là khoá cũ đã hết hạn sử dụng, hoặc khoá do đối ph−ơng chọn). 2. Làm U hoặc V tin rằng, họ có thể trao đổi khoá với ng−ời kia khi họ không có khoá. Mục tiêu của phân phối khoá và giao thức thoả thuận khoá là, tại thời điểm kết thúc thủ tục, hai nhóm đều có cùng khoá K song không nhóm khác nào biết đ−ợc (trừ khả năng TA). Chắc chắn, việc thiết kế giao thức có kiểu an toàn này khó khăn hơn nhiều tr−ớc đối ph−ơng chủ động. Tr−ớc hết ta xem xét ý t−ởng về sự phân phối khoá tr−ớc trong mục 8.2. Với mỗi cặp ng−ời sử dụng {U,V}, TA chọn một khoá ngẫu nhiên KU,V=KV,U và truyền “ngoài dải” đến U và V trên kênh an toàn. (Nghĩa là, việc truyền khoá không xảy ra trên mạng do mạng không an toàn ). Biện pháp này gọi là an toàn không điều kiện song nó đòi hỏi một kênh an toàn giữa TA và những ng−ời sử Trang 1
2. Vietebooks Nguyễn Hoàng Cương dụng trên mạng. Tuy nhiên điều quan trọng hơn là mỗi ng−ời phải l−u n -1 khoá n và TA cần truyền tổng cộng (2 )khoá một cách an toàn (đôi khi bài toán này đ−ợc gọi là bài toán n2). Thậm chí với một số mạng t−ơng đối nhỏ, giá để giải quyết vấn đề này là khá đắt và nh− vậy giải pháp hoàn toàn không thực tế. Trong phần 8.2.1, chúng ta thảo luận một sơ đồ phân phối tr−ớc khoá an toàn không điều kiện khá thú vị do Blom đ−a ra. Sơ đồ cho phép giảm l−ợng thông tin mật mà ng−ời sử dụng cần cất giữ trên mạng. Mục 8.2.2 cũng đ−a ra một sơ đồ phân phối tr−ớc khoá an toàn về mặt tính toán dựa trên bài toán logarithm rời rạc. Một biện pháp thực tế hơn là TA phân phối khoá trực tiếp. Trong sơ đò nh− vậy, TA làm việc nh− một ng−ời chủ khoá (key server). TA chia khoá mật KU cho mỗi ng−ời sử dụng U trên mạng. Khi U muốn liên lạc với V, cô ta yêu cầu TA cung cấp khoá cho phiên làm việc (session key). TA tạo ra khoá session K và gửi nó d−ới dạng mã hoá cho U và V để giải mã. Hệ thống mã Kerboros mô tả trong mục 8.3 là dựa trên biện pháp này. Nếu nh− cảm thấy vấn đề phân phối khoá thông qua TA không thực tế hoặc không mong muốn thì biện pháp chung là dùng giao thức thoả thuận khoá. Trong giao thức thoả thuận khoá, U và V kết hợp chọn một khoá bằng cách liên lạc với nhau trên kênh công khai. ý t−ởng đáng chú ý này do Martin và Diffie đ−a ra độc lập với Merkle. ở đây mô tả vài giao th−c thoả thuận khoá phổ thông hơn. Giao thức đầu tiên của Diffie và Hellman đ−ợc cải tiến để ứng phó với các đối ph−ơng tích cực đ−ợc nêu trong phần 8.4.1. Hai giao thức đáng quan tâm nữa cũng đ−ợc xem xét: sơ đồ MTI nên trong 8.4.2 và sơ đồ Girault nêu trong mục 8.4.3 8.2 Phân phối khoá tr−ớc ⎛n⎞ theo ph−ơng pháp cơ bản, TA tạo ra ⎜ ⎟ khoá và đ−a mỗi khoa cho duy ⎝2⎠ nhất một cặp ng−ời sử dụng trong mạng có n ng−ời sử dụng. Nh− đã nêu ở trên, ta cần một kênh an toàn giữa TA và mỗi ng−ời sử dụng để truyền đi các khoá ⎛n⎞ này. Đây là một cải tiến quan trọng vì số kênh an toàn cần thiết giảm từ ⎜ ⎟ ⎝2⎠ xuống còn n. Song nếu n lớn, giải pháp này cũng không thực tế cả về l−ợng thông tin cần truyền đi an toàn lẫn l−ợng thông tin mà mỗi ng−ời sử dụng phải cất giữ an toàn (nghĩa là các khoá mật của n-1 ng−ời sử dụng khác). nh− vậy, điều cần quan tâm là cố gắng giảm đ−ợc l−ợng thông tin cần truyền đi và cất giữ trong khi vẫn cho phép mỗi cặp ng−ời sử dụng U và V có khả năng tính toán khoá mật KU,V. Một sơ đồ −u việt hơn thoả mãn yêu cầu này là sơ đồ phân phối khoá tr−ớc của Blom. 8.2.1 Sơ đồ Blom. Trang 2
3. Vietebooks Nguyễn Hoàng Cương Nh− trên, giả thiết rằng có một mạng gôm n ng−ời sử dụng. Để thuận tiện, giả sử rằng các khoá đ−ợc chọn trên tr−ờng số hữu hạn ZP, p ≥ n là số nguyên tố. Cho k là số nguyên, 1 < k < n -2. Giá trị k để hạn chế kích th−ớc lớn nhất mà sơ đồ vẫn duy trì đ−ợc mật độ. Trong sơ đồ Blom, TA sẽ truyền đi k +1 phần tử của ZP cho mỗi ng−ời sử dụng trên kênh an toàn (so với n -1 trong sơ đồ phân phối tr−ớc cơ bản). Mỗi cặp ng−ời sử dụng U và V sẽ có khả năng tính khoá KU,V = KV,U nh− tr−ớc đây. Điều kiện an toàn nh− sau: tập bất kì gồm nhiều nhất k ng−ời sử dụng không liên kết từ {U, V} phải không có khả năng xác định bất kì thông tin nào về KU,V. (chú ý rằng, ta đang xét sự an toàn không điều kiện). Tr−ớc hết, xét tr−ờng hợp đặc biệt của sơ đồ Blom khi k =1. ở đây TA sẽ truyền đi 2 phần tử của ZP cho mỗi ng−ời sử dụng trên kênh an toàn và ng−ời sử dụng riêng W sẽ không thể xác định đ−ợc bất kì thông tin nào về KU,V nếu W≠U,V. Sơ đồ Blom đ−ợc đ−a ra trong hình 8.1. Ta sẽ minh hoạ sơ đồ Blom với k = 1 trong ví dụ sau: Hình 8.1: Sơ đồ phân phối khoá của Blom (k =1) 1. Số nguyên tố p công khai, còn với mỗi ng−ời sử dụng U, phần tử rU ∈ ZP là công khai. Phần tử rU phải khác biệt. 2. Ta chọn 3 phần tử ngẫu nhiên a, b, c ∈ ZP (không cần khác biệt) và thiết lập đa thức Trang 3
4. Vietebooks Nguyễn Hoàng Cương 8.3.Kerboros trong các ph−ơng pháp phân phối tr−ớc khoá xem xét trong các phần tr−ớc đó, mỗi cặp ng−ời sử dụng cần tính một khoá cố định. Nếu dùng cùng một khoá trong một thời gian dài sẽ dễ bị tổn th−ơng, vì thế ng−ời ta th−ờng thích dùng ph−ơng pháp trực tiếp trong đó khoá của phiên lamà việc mới chỉ đ−ợc tạo ra mỗi khi hai ng−ới sử dụng muốn liên lạc với nhau (gọi là tính t−ơi mới của khoá). Nếu dùng phân phối khoá trực tiếp thì ng−ời sử dụng mạng không cần phải l−u các khoá khi muốn liên lạc với những ng−ời sử dụng khác (Tuy nhiên mỗi ng−ời đều đ−ợc chia sẻ khoá với TA). Khoá của phiên làm việc (khóa session) sẽ đ−ợc truyền đi theo yêu cầu của TA. Đó là sự đáp ứng của TA để đảm bảo khoá t−ơi. Korobos là hệ thống dịch vụ khóa phổ cập dựa trên mã khoá riêng. Trong phần này sẽ đ−a ra một tổng quan về giao thức phát hành khoá session trong Korobos. Mỗi ng−ời sử dụng U sẽ chia sẻ khoá DES mật KU cho TA. Trong phiên bản gần đây nhất của Korobos (version 5), mọi thông báo cần truyền đ−ợc mã hoá theo chế độ xích khối (CBC) nh− mô tả trong 3.4.1 Nh− trong mục 8.2.2, ID(U) chỉ thông tin định danh công khai cho U. Khi có yêu cầu khoá session gửi đến TA, TA sẽ tạo ra một khoá session mới ngẫu nhiên K. Cũng vậy, TA sẽ ghi lại thời gian khi có yêu cầu T và chỉ ra thời gian (thời gian tồn tại) L để K có hiệu lực. Điều đó có nghĩa là khoá K chỉ có hiệu lực từ T đến T+L. Tất cả thông tin này đều đ−ợc mã hoá và đ−ợc truyênông dân đến U và V. Tr−ớc khi đi đến các chi tiết hơn nữa, ta sẽ đ−a ra giao thức trong hình 8.4. thông tin đ−ợc truyền đi trong giao thức đ−ợc minh hoạ nh− sau: Hình 8.4: Truyền khoá session trong Korobos. 1. Ta sẽ giải thích điều sắp sửa xảy ra trong các b−ớc của giao thức. Mặc dù không có chứng minh hình thức rằng Kerobos là an toàn tr−ớc đối thủ tích cực, song ít nhất ta cũng có thể đ−a ra lí do nào đó về các đặc điểm của giao thức. Nh− nêu ở trên, TA tạo ra K, T và L trong b−ớc 2. Trong b−ớc 3, thông tin này cùng với ID(V) đ−ợc mã hoá bằng khoá KU (đ−ợc U và TA chia sẻ) để tạo lập m1. Cả hai bức điện đã mã hoá này đ−ợc gửi đến U. U có thể dùng khoá của mình giải mã m1, nhận đ−ợc K, T và L. Cô sẽ xác minh xem thời gian hiện tại có nằm trong khoảng T đến T + L hay không. Cô cũng kiểm tra khoá session K đ−ợc phát ra cho liên lạc giữa cô và V bằng cách xác minh thông tin ID(V) đã giải mã từ m2. Tiếp theo, U sẽ làm trễ thời gian m2 và m3 đến V. Cũng nh− vậy, U sẽ dùng khoá session K mới để mã T và ID(U) và gửi kết quả m3 đến V. Khi V nhận đ−ợc m3 và m3 từ U, V giải mã m2 thu đ−ợc T, K, L và ID(U). Khi đó, anh ta sẽ dùng khoá session mới K để giải mã m3 và xác minh xem T và Trang 4
5. Vietebooks Nguyễn Hoàng Cương ID(U) nhận đ−ợc từ m2 và m3 có nh− nhau không. Điều này đảm bảo cho V rằng khoá session đ−ợc mã bằng m2 cũng là khoá đã dùng để mã m3. Khi đó V dùng K để mã T+1 và gửi kết quả m4 trở về U. Khi U nhận đ−ợc m4, cô dùng K giải mã nó và xác minh xem kết quả có bằng T+1 không. Công đoạn này đảm bảo cho U rằng khoá session K đã đ−ợc truyền thành công đến V vì K đã đ−ợc dùng để tạo ra m4. Điều quan trọng cần l−u ý là các chức năng khác nhau của các thông báo dùng trong giao thức, m1 và m2 dùng để bảo đảm an toàn trong việc truyền khoá session. Còn m3 và m4 dùng để khẳng định khoá, nghĩa là cho phép U và V có thể thuyết phục nhau rằng họ sở hữu cùng một khoá session K. Trong hầu hết các sơ đồ phân phối khoá, sự khẳng định khoá đựoc coi nh− một đặc tính. Th−ờng thì nó đ−ợc thực hiện t−ơng tự kiểu Kerobos, U dùng K để mã ID(U) và T dùng để mã trong m2. T−ơng tự, V dùng K để mã T+1. Mục đích của thời gian hệ thống T và thời hạn L để ngăn đối ph−ơng tích cực khỏi “l−u” thông báo cũ nhằm tái truyền lại sau này (đây đ−ợc gọi là tấn công kiểu chơi lại - relay attack). Ph−ơng pháp này hiệu quả vì các khoá không đ−ợc chấp nhận là hợp lệ một khi chúng quá hạn. Một trong hạn chế của Kerobos là mọi ng−ời sử dụng trong mạng đều phải có đồng hồ đồng bộ với nhau vì cần có thời gian hiện tại để xác định khoá session K cho tr−ớc là hợp lệ. Thực tế, rất khó có đ−ợc sự đồng bộ hoàn hảo nên phải cho phép có khoảng thay đổi nào đó về thời gian. Hình 8.5: Trao đổi khoá Diffie - Hellman 8.4 Trao đổi khoá Diffie - Hellman Nếu ta không muốn dùng dịch vụ khoá trực tiếp thì buộc phải dùng giao thức thoả thuận khoá để trao đôỉ khoá mật. Tr−ớc hết, giao thức thoả thuận khoá nổi tiếng nhất là giao thức trao đổi khoá Diffie - Hellman. Giả sử rằng, p là số nguyên tố, α là phần tử nguyên thuỷ của ZP và chúng đều là những tham số công khai. Giao thức trao đổi khoá Diffie - Hellman đ−ợc đ−a ra trong mục 8.5. Cuối giao thức, U và V tính ra cùng một khoá: Giao thức này cũng t−ơng tự với sơ đồ phân phối khoá tr−ớc của Diffie - Hellman đã mô tả tr−ớc đây. Sự khác nhau ở chỗ các số mũ aU, aV của U và V đều đ−ợc chọn lại mỗi lần thực hiện giao thức thay vì cố định. Cũng nh− vậy, trong giao thức này, cả U lẫn V đều đ−ợc đảm bảo khoá t−ơi vì khoá session phụ thuộc vào cả hai số mũ ngẫu nhiên aU và aV. 8.4.1 Giao thức trạm tới trạm. Trao đổi khoá Diffie - Hellman đ−ợc đề xuất nh− sơ đồ sau: Trang 5
6. Vietebooks Nguyễn Hoàng Cương (Sơ đồ) Đáng tiếc là giao thức dễ bị tổn th−ơng tr−ớc đối ph−ơng tích cực - những ng−ời sử dụng tấn công “kẻ xâm nhập vào giữa cuộc” (Intuder - in -middle - attack). Đó là tình tiết của vở “The Lucy show”, trong đó nhân vật Vivian Vance đang dùng bữa tối với ng−ời bạn, còn Lucille Ball đang trốn d−ới bàn. Vivian và ng−ời bạn của cô nắm tay nhau d−ới bàn. Lucy cố tránh bị phát hiện đã nắm tay của cả hai ng−ời, còn hai ng−ời vẫn nghĩ rằng họ đang nắm tay nhau. Cuộc tấn công kiểu “kẻ xâm nhập giữa cuộc” trên giao thức trao đổi khoá Diffie - Hellman cũng nh− vậy. W sẽ chặn bắt đ−ợc các bức điện trao đổi giữa U và V và thay thế bằng các bức điện của anh ta nh− sơ đồ d−ới đây: (sơ đồ) ' Tại thời điểm cuối của giao thức, U thiết lập thực sự khoá mật α aU aV cùng ' với W, còn V thiết lập khoá mật α aU aV với W. Khi U cố giải mã bức điện để gửi cho V, W cũng có khả năng giải mã nó song V không thể, (t−ơng tự tình huống nắm tay nhau nếu V gửi bức điện cho U). Rõ ràng, điều cơ bản đối với U và V là bảo đảm rằng, họ đang trao đổi khoá với nhau mà không có W. Tr−ớc khi trao đổi khoá, U và V có thể thực hiện những giao th−c tách bạch để thiết lập danh tính cho nhau, ví dụ, nhờ dùng một trong các sơ đồ định danh mô tả trong ch−ơng 9. Tuy nhiên, điều này có thể đ−a đến việc không bảo vệ đ−ợc tr−ớc tấn công kẻ xâm nhập giữa cuộc nếu W vẫn duy trì một cách đơn giản sự tấn công thụ động cho đến khi U và V đã chứng minh danh tính của họ cho nhau. Vì thế giao thức thoả thuận khoá tự nó cần xác thực đ−ợc các danh tính của những ng−ời tham gia cùng lúc khoá đ−ợc thiết lập. Giao thức nh− vậy đ−ợc gọi là giao thức thoả thuận khoá đã xác thực. Ta sẽ mô tả một giao thức thoả thuận khoá là cải tiến của sơ đồ trao đổi khoá Diffie - Hellman. Giao thức giả thiết số nguyên tố p và phần tử nguyên thuỷ α là công khai và nó dùng với các dấu xác nhận. Mỗi ng−ời sử dụng U sẽ có một sơ đồ chữ kí với thuận toán xác minh verU. TA cũng có sơ đồ chữ kí với thuật toán xác minh công khai verTA. Mỗi ng−ời sử dụng U có dấu xác nhận: C(U) = (ID(U), verU, sigTA(ID(U), verU)) Trong đó ID(U) là thông tin định danh cho U Hình 8.6 Giao thức trạm tới trạm đơn giản. Thoả thuận khoá đã xác thực do Diffie - Hellman, van Oorschot và Viener đ−a ra đ−ợc gọi là giao thức trạm đến trạm (viết tắt là STS). Giao thức đ−a ra trên hình 8.6 đơn giản hơn một chút: nó có thể đ−ợc dùng để có thể phù hợp với các giao thức của ISO 9798-3. Thông tin đ−ợc trao đổi trong sơ đồ STS đã đơn giản hoá (gồm cả các dấu xác nhận) đ−ợc minh hoạ nh− sau: Trang 6
7. Vietebooks Nguyễn Hoàng Cương (sơ đồ) Ta hãy xem cách bảo vệ này tr−ớc tấn công kẻ xâm nhập giữa cuộc. Nh− tr−ớc đây, W sẽ chặn bắt α aU và thay nó bằng 8.4.2. Các giao thức thoả thuận khoá MTI Matsumoto, Takashima và Imai đã xây dựng vài giao thức thoả thuận khoá đáng chú ý bằng cách biến đổi giao thức trao đổi khoá của Diffie - Hellman. Các giao thức này đ−ợc gọi là MTI. Giao thức này không đòi hỏi U và V phải tính bất kì chữ kí nào. Chúng là các giao thức hai lần vì chỉ có hai lần truyền thông tin riêng biệt (một từ U đến V và một từ V đến U). Trái lại, giao thức STS đ−ợc gọi là giao 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ỷ α 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, α = 5. Giả sử U chọn aU = 21131: sau đó cô ta tính: 21131 bU = 5 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: 17555 bV =5 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ị: 169 sU = 5 mod 27803 = 6268. Trang 7
8. Vietebooks Nguyễn Hoàng Cương đến V. Lúc đó giả sử V chọn rV = 23456, sau đó anh ta gửi giá trị: 23456 sU = 5 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 α là phân tử có Trang 8
9. Vietebooks Nguyễn Hoàng Cương * bậc 2p1q1. Khi đó nhóm cyclic của Zn do α 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à α 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 φ(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: e bU = pU + ID(U) mod n Hình 8.8: Nhận khoá tự xác nhận từ TA 1. U chọn số mũ mật aU và tính: bU = 2. U đ−a aU và bU cho TA 3. TA tính: d pU = (bU - ID(U)) mod n 4. 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: rU ID(U), pU, α mod n U r V V ID(V), pV,α mod n Cuối giao thức, U và V tính khoá: K = α rU aV +rV aU mod n 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à φ(n) = 722356. Phần tử α=5 có bậc 2p1q1 = φ(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 1. U chọn rU ngẫu nhiên và tính su = 2. U gửi ID(U), pU và sU cho V. 3. V chọn rV ngẫu nhiên và tính Trang 9
10. Vietebooks Nguyễn Hoàng Cương rV sV =α mod n 4. V gửi ID(V), pV và sV cho U 5. U tính: aU e rU K = sV ( pV + ID(V )) mod n Và V tính: aV e rv K =sU ( pU + ID(U )) mod n 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: ' ' aU bU = α mod n Đây là cách anh ta có thể xác định khoá công khai t−ơng ứng ’ ’ d pU =(b U - ID(U)) mod n W sẽ tính: ’ ’ pW = 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 ’ ’ d pW =(b W - ID(W)) (mod n) cho W. Nhờ dùng yếu tố: ’ ’ bW - ID(W) ≡ b U - ID(U) (mod n) ’ ’ có thể suy ra rằng: p W = p U. 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: ' ru ’ rU ID(U), pU, α mod n ID(U), p U, α mod n rv ’ rv U ID(V), p V, α modn V ID(V), p V, α mod n W Trang 10
11. Vietebooks Nguyễn Hoàng Cương Xét thấy V sẽ tính khoá: ' ' K ' = α rU av +rvaU mod n trong khi U sẽ tính khoá K = α rU av +rvaU mod n W có thể tính K’ nh− sau: ' ' ' aU e rU K = sv ( pV + ID(V )) mod n 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: 2 gU(x) = 15 + 15x + 2x Trang 11
12. Vietebooks Nguyễn Hoàng Cương 2 gV(x) = 95 + 77x + 83x 2 gW(x) = 88 + 32x + 18x 2 gX(x) = 62 + 91x + 59x 2 gY(x) = 10 + 82x + 52x 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, α, β, γ, δ, ε) trong đó p là số nguyên tố, α ∈ Z P là phần tử * nguyên thuỷ còn β, γ, δ, ε ∈Z P Mục tiêu: Tính β logα γ δ logα ε mod p 8.3. Giả thiết U và V tiến hành trao đổi khoá theo sơ đồ Diffie - Hellman với p = 27001 và α = 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, α = 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ử α = 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ọ. Trang 12