Phân phối khóa và thỏa thuận khóa

Hệ phân phối khoá Diffie-Hellman

Hệ phân phối khoá Diffie-Hellman không đòi hỏi TA phải biết và chuyển bất kỳ thông tin bí mật nào về khoá của các người tham gia trong mạng để họ thiết lập được khoá chung bí mật cho việc truyền tin với nhau.

Trong một hệ phân phối khoá Diffie-Hellman, TA chỉ việc chọn một số nguyên tố lớn p và một phần tử nguyên thuỷ α size 12{α} {} theo mod p, sao cho bài toán tính log_{α size 12{α} {}} trong p Z_p^* là rất khó. Các số p và α size 12{α} {} được công bố công khai cho mọi người tham gia trong mạng. Ngoài ra, TA có một sơ đồ chữ ký với thuật toán ký (bí mật) sig_TA và thuật toán kiểm chứng (công khai) ver_TA.

Một thành viên bất kỳ A với danh tính ID(A) tuỳ ý chọn một số aA0≤aA≤p−2 size 12{a rSub { size 8{A} } left (0 <= a rSub { size 8{A} } <= p - 2 right )} {} và tính bA=αaAmodp size 12{b rSub { size 8{A} } =α rSup { size 8{a rSub { size 6{A} } } } "mod"p} {}. A giữ bí mật aA size 12{a rSub { size 8{A} } } {} và đăng ký các thông tin (ID(A), bA size 12{b rSub { size 8{A} } } {}) với TA. TA cấp cho A chứng chỉ:

C(A) = (ID(A), bA size 12{b rSub { size 8{A} } } {}, sig_TA(ID(A), bA size 12{b rSub { size 8{A} } } {})).

Các chứng chỉ của các thành viên trong mạng có thể được lưu giữ trong một cơ sở dữ liệu công khai hoặc uỷ thác cho TA lưu giữ và cung cấp công khai cho các thành viên mỗi khi cần đến.

Khi hai thành viên A và B trong mạng cần có một khoá bí mật chung để truyền tin bảo mật cho nhau thì A dùng thông tin công khai bB size 12{b rSub { size 8{B} } } {} có trong C(B) kết hợp với số bí mật của mình là aA size 12{a rSub { size 8{A} } } {} để tạo nên khoá:

Khoá chung đó B cũng tạo ra được từ các thông tin công khai bA size 12{b rSub { size 8{A} } } {}của A và số bí mật của mình:

Để bảo đảm được các thông tin về và bB size 12{b rSub { size 8{B} } } {} và bA size 12{b rSub { size 8{A} } } {} là chính xác, A và B có thể dùng thuật toán ver_TA để kiểm chứng chữ ký xác thực của TA trong các chứng chỉ C(B) và C(A) tương ứng.

Độ an toàn của hệ phân phối khoá Diffie-Hellman được bảo đảm bởi yếu tố sau đây: Biết bA size 12{b rSub { size 8{A} } } {} và bB size 12{b rSub { size 8{B} } } {} để tính K_A,B chính là bài toán Diffie-Hellman tương đương: biết αamodp size 12{α rSup { size 8{a} } "mod"p} {} và αbmodp size 12{α rSup { size 8{b} } "mod"p} {}, tính αabmodp size 12{α rSup { size 8{ ital "ab"} } "mod"p} {}. Đây là một bài toán khó tương đương bài toán tính lôgarit rời rạc hay bài toán phá mật mã ElGamal.

Giao thức trao đổi khoá Diffie-Hellman

Hệ phân phối khoá Diffie-Hellman nói trong mục trước có thể dễ dàng biến đổi thành một giao thức trao đổi (hay thoả thuận) khoá trực tiếp giữa những người sử dụng mà không cần có sự can thiệp của một TA làm nhiệm vụ điều hành hoặc phân phối khoá. Một nhóm bất kỳ người sử dụng có thể thoả thuận cùng dùng chung một số nguyên tố lớn p và một phần tử nguyên thuỷ α size 12{α} {} theo mod p, hai người bất kỳ trong nhóm A và B mỗi khi muốn truyền tin bảo mật cho nhau có thể cùng thực hiện giao thức sau đây để trao đổi khoá:

1. A chọn ngẫu nhiên số a_A (0 size 12{ <= {}} {} a_A size 12{ <= {}} {} p -2), giữ bí mật a_A, tính bA=αaAmodp size 12{b rSub { size 8{A} } =α rSup { size 8{a rSub { size 6{A} } } } "mod"p} {}

và gửi b_A cho B.

2. Tương tự, B chọn ngẫu nhiên số aB (0 size 12{ <= {}} {} a_B size 12{ <= {}} {} p -2), giữ bí mật a_B, tính bB=αaBmodp size 12{b rSub { size 8{B} } =α rSup { size 8{a rSub { size 6{B} } } } "mod"p} {} và gửi b_B cho A.

3. A và B cùng tính được khoá chung:

Giao thức trao đổi khoá Diffie-Hellman có các tính chất sau:

1. Giao thức là an toàn đối với việc tấn công thụ động, nghĩa là một người thứ ba, dù biết b_A và b_B sẽ khó mà biết được K_A,B.

Ta biết rằng bài toán “biết b_A và b_B tìm K_A,B” chính là bài toán Diffie-Hellman và trong mục 7.2.1 ta có nói rằng bài toán đó tương đương với bài toán phá mật mã El Gamal. Bây giờ ta chứng minh điều này. Phép mật mã El Gamal với khoá K = p,α,a,β size 12{ left (p,α,a,β right )} {}, trong đó β=αamodp size 12{β=α rSup { size 8{a} } "mod"p} {}, cho ta từ một bản rõ x và một số ngẫu nhiên k∈Zp−1 size 12{k in Z rSub { size 8{p - 1} } } {}1 lập được mật mã:

Trong đó: y1=αkmodp,y2=xβkmodp size 12{y rSub { size 8{1} } =α rSup { size 8{k} } "mod"p,y rSub { size 8{2} } =xβ rSup { size 8{k} } "mod"p} {}

Và phép giải mã được cho bởi:

Giả sử ta có thuật toán A giải bài toán Diffie-Hellman. Ta sẽ dùng A để phá mã El Gamal như sau: Cho mật mã (y1,y2) size 12{ ( y rSub { size 8{1} } ,y rSub { size 8{2} } ) } {}. Trước hết, dùng A cho y1=αkmodp size 12{y rSub { size 8{1} } =α rSup { size 8{k} } "mod"p} {} và β=αamodp size 12{β=α rSup { size 8{a} } "mod"p} {}, ta được:

A(y₁, β size 12{β} {}) = αka=βkmodp size 12{α rSup { size 8{ ital "ka"} } =β rSup { size 8{k} } "mod"p} {}

và sau đó ta thu được bản rõ x từ βk size 12{β rSup { size 8{k} } } {} và y₂ như sau:

Ngược lại, giả sử có thuật toán B phá mã El Gamal, tức là:

B p,α,a,β,y1,y2=x=y2(y1a)−1modp size 12{ left (p,α,a,β,y rSub { size 8{1} } ,y rSub { size 8{2} } right )=x=y rSub { size 8{2} } ( y rSub { size 8{1} } rSup { size 8{a} } ) rSup { size 8{ - 1} } "mod"p} {}

Áp dụng B cho β=bA,y1=bB,y2=1 size 12{β=b rSub { size 8{A} } ,y rSub { size 8{1} } =b rSub { size 8{B} } ,y rSub { size 8{2} } =1} {}, ta được

B p,α,bA,bB,1−1=(1.(bBaA)−1)−1=αaAaBmodp size 12{ left (p,α,b rSub { size 8{A} } ,b rSub { size 8{B} } ,1 right ) rSup { size 8{ - 1} } = ( 1 "." ( b rSub { size 8{B} } rSup { size 8{a rSub { size 6{A} } } } ) rSup { - 1} size 12{ ) rSup { - 1} } size 12{ {}=α rSup {a rSub { size 6{A} } a rSub { size 6{B} } } } size 12{"mod"p}} {} tức là giải được bài toán Diffie-Hellman.

2. Giao thức là không an toàn đối với việc tấn công chủ động bằng cách đánh tráo giữa đường, nghĩa là một người thứ ba C có thể đánh tráo các thông tin trao đổi giữa A và B, chẳng hạn, C thay αaA size 12{α rSup { size 8{a rSub { size 6{A} } } } } {}mà A định gửi cho B bởi αa'A size 12{α rSup { size 8{a rSup { size 6{'} rSub { size 6{A} } } } } } {},và thay αaB size 12{α rSup { size 8{a rSub { size 6{B} } } } } {}mà B định gửi cho A bởi αa'B size 12{α rSup { size 8{a rSup { size 6{'} rSub { size 6{B} } } } } } {}, như vậy, sau khi thực hiện giao thức trao đổi khoá, A đã lập một khoá chung αaAa'B size 12{α rSup { size 8{a rSub { size 6{A} } a rSup { size 6{'} rSub { size 6{B} } } } } } {} với C mà vẫn tưởng là với B, đồng thời B đã lập một khoá chung αa'AaB size 12{α rSup { size 8{a rSup { size 6{'} rSub { size 6{A} } } a rSub { size 6{B} } } } } {}với C mà vẫn tưởng là với A; C có thể giải mã mọi thông báo mà A tưởng nhầm là mình gửi đến B, cũng như mọi thông báo mà B tưởng nhầm là mình gửi đến A!

Một cách khắc phục kiểu tấn công chủ động nói trên là làm sao để A và B có thể kiểm chứng để xác thực tính đúng đắn của các khoá công khai b_A và b_B. Đưa vào giao thức trao đổi khoá Diffie-Hellman thêm vai trò điều phối của một TA để được một hệ phân phối khoá Diffie-Hellman như ở mục 7.2.1 là một cách khắc phục như vậy. Trong hệ phân phối khoá Diffie-Hellman, sự can thiệp của TA là rất yếu, thực ra TA chỉ làm mỗi một việc là cấp chứng chỉ xác nhực khoá công khai cho từng người dùng chứ không đòi hỏi biết thêm bất cứ một bí mật nào của người dùng. Tuy nhiên, nếu chưa thoả mãn với vai trò hạn chế đó của TA, thì có thể cho TA một vai trò xác nhận yếu hơn, không liên quan gì đến khoá, chẳng hạn như xác nhận thuật toán kiểm thử chữ ký của người dùng, còn bản thân các thông tin về khoá (cả bí mật và công khai) thì do những người dùng trao đổi trực tiếp với nhau. Với cách khắc phục có vai trò rất hạn chế đó của TA, ta có được giao thức ở phần sau.

Giao thức trao đổi khoá D-H có chứng chỉ xác thực

Mỗi người dùng A có một danh tính ID(A) và một sơ đồ chữ ký với thuật toán ký sig_A và thuật toán kiểm chứng ver_A. TA cũng có một vai trò xác thực, nhưng không phải xác thực bất kỳ thông tin nào liên quan đến việc tạo khoá mật mã của người dùng (dù là khoá bí mật hay là khoá công khai), mà chỉ là xác thực một thông tin ít quan hệ khác như thuật toán kiểm chứng chữ ký của người dùng. Còn bản thân các thông tin liên quan đến việc tạo khoá mật mã thì các người dùng sẽ trao đổi trực tiếp với nhau. TA cũng có một sơ đồ chữ ký của mình, gồm một thuật toán ký sig_TA và một thuật toán kiểm chứng (công khai) ver_TA. Chứng chỉ mà TA cấp cho mỗi người dùng A sẽ là:

C(A) = (ID(A), ver_A , sig_TA(ID(A), ver_A)).

Rõ ràng trong chứng chỉ đó TA không xác thực bất kỳ điều gì liên quan đến việc tạo khoá của A cả. Việc trao đổi khoá giữa hai người dùng A và B được thực hiện theo giao thức sau đây:

1. A chọn ngẫu nhiên số a_A (0 size 12{ <= {}} {} a_A size 12{ <= {}} {} p -2), tính bA=αaAmodp size 12{b rSub { size 8{A} } =α rSup { size 8{a rSub { size 6{A} } } } "mod"p} {}

và gửi b_A cho B.

2. B chọn ngẫu nhiên số aB (0 size 12{ <= {}} {} a_B size 12{ <= {}} {} p -2), giữ bí mật a_B, tính bB=αaBmodp size 12{b rSub { size 8{B} } =α rSup { size 8{a rSub { size 6{B} } } } "mod"p} {}, tính tiếp

yB=sigB(bB,bA) size 12{y rSub { size 8{B} } = ital "sig" rSub { size 8{B} } ( b rSub { size 8{B} } ,b rSub { size 8{A} } ) } {} và gửi (C(B), b_B, y_B) cho A.

3. A tính: K=bBaBmodp size 12{K=b rSub { size 8{B} } rSup { size 8{a rSub { size 6{B} } } } "mod"p} {} dùng ver_B để kiểm chứng y_B, dùng ver_TA để kiểm chứng C(B), sau đó tính yA=sigA(bA,bB) size 12{y rSub { size 8{A} } = ital "sig" rSub { size 8{A} } ( b rSub { size 8{A} } ,b rSub { size 8{B} } ) } {}, và gửi (C(A), y_A) cho B.

4. B dùng ver_A để kiểm chứng y_A ,và dùng ver_TA để kiểm chứng C(A).

Nếu tất cả các bước đó được thực hiện và các phép kiểm chứng đều cho kết quả đúng đắn, thì giao thức kết thúc, cả A và B đều có được khoá chung K. Do việc dùng các thuật toán kiểm chứng nên A biết chắc giá trị b_B là của B và B biết chắc giá trị b_A là của A, loại trừ khả năng một người C nào khác đánh tráo các giá trị đó giữa đường.