7.1. Gi¶ sö h: X →Y lµ hµm hash. Víi y bÊt kú ∈Y, cho:
h
-1
(y) = { x: h(x) = y}
vµ ký hiÖu s
y
= | h
-1
(y)|.
§Þnh nghÜa N =
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. Nhng 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

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 K
U
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 thc 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
theo phơng pháp cơ bản, TA tạo ra







sử rằng các khoá đợc chọn trên trờng số hữu hạn Z
P
, 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 Z
P
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á K
U,V
= K
V,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ề K
U,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 Z
P
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ề K
U,V
nếu WU,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ử r

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á K
U
(đợc U và TA chia sẻ) để tạo lập m
1
. 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ã m
1
, 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ừ m
2
.
Tiếp theo, U sẽ làm trễ thời gian m
2
và m
3
đến V. Cũng nh vậy, U sẽ dùng