Trao đổi khóa Diffie-Hellman

Trao đổi khóa Diffie–Hellman (D-H) là một phương pháp cổ điển trong mật mã học, cho phép hai bên thiết lập một khóa bí mật chung để mã hóa dữ liệu qua kênh không an toàn mà không cần trao đổi khóa trước. Khóa bí mật này sẽ được dùng cho mã hóa đối xứng.

Giao thức này lần đầu tiên được Whitfield Diffie và Martin Hellman công bố vào năm 1976. Trước đó, một nhóm tại GCHQ gồm James H. Ellis, Clifford Cocks và Malcolm J. Williamson đã phát minh ra nó nhưng giữ bí mật. Vào năm 2002, Hellman đã đề xuất bổ sung tên Diffie–Hellman–Merkle để ghi nhận công lao của Ralph Merkle trong việc phát triển mật mã công khai (Hellman, 2002).

Mặc dù bản thân giao thức Diffie–Hellman không có khả năng xác thực và chỉ cung cấp ẩn danh, nó đã đặt nền móng cho nhiều giao thức xác thực và đóng góp vào việc thiết lập bí mật chuyển tiếp hoàn hảo trong giao thức Transport Layer Security (EDH hoặc DHE tùy thuộc vào bộ mã hóa).

Phương pháp này sau đó đã được ứng dụng vào thuật toán mã hóa RSA.

Vào năm 2002, Martin Hellman đã viết:

Hệ thống này hiện được gọi là Trao đổi khóa Diffie–Hellman. Khi hệ thống được giới thiệu trong bài báo của Diffie và tôi, nó là một phương pháp phân phối khóa công khai, một khái niệm do Merkle nêu ra. Do đó, nó nên được gọi là Trao đổi khóa 'Diffie–Hellman–Merkle' nếu cần một tên chính thức. Tôi hy vọng rằng phần ghi chú nhỏ của tôi sẽ giúp ghi nhận công lao của Merkle trong sự phát triển của mật mã công khai. [1] Lưu trữ 2005-01-18 tại Wayback Machine

Bằng sáng chế Hoa Kỳ số 4,200,770 mô tả thuật toán này từ năm 1977, đã hết hạn bản quyền và ghi nhận Hellman, Diffie, và Merkle là những người phát minh.

Mô tả

Diffie–Hellman thiết lập một khóa bí mật chung cho việc trao đổi dữ liệu an toàn qua kênh truyền thông công cộng không bảo mật. Sơ đồ dưới đây minh họa ý tưởng cơ bản của trao đổi khóa bằng ví dụ về màu sơn.

Khái niệm cơ bản

Ý tưởng chính là Alice và Bob trao đổi màu sơn bí mật qua một hỗn hợp sơn.

• Đầu tiên, Alice và Bob kết hợp màu chung đã biết (màu vàng) với màu bí mật riêng của họ.
• Tiếp theo, mỗi người gửi hỗn hợp của mình cho người kia qua kênh công cộng.
• Khi nhận được hỗn hợp từ đối phương, mỗi người sẽ trộn thêm với màu bí mật của mình để có được hỗn hợp cuối cùng.

Hỗn hợp cuối cùng sẽ hoàn toàn giống nhau cho cả hai người và chỉ họ mới biết. Điều quan trọng là rất khó cho bên ngoài (về mặt tính toán) để xác định bí mật chung của Alice và Bob (tức là hỗn hợp cuối cùng). Alice và Bob sẽ sử dụng bí mật này để mã hóa và giải mã dữ liệu trên kênh công cộng. Màu sơn đầu tiên (màu vàng) có thể được chọn tùy ý nhưng cần được thỏa thuận trước. Màu sơn này có thể được coi là không bí mật đối với bên thứ ba mà không ảnh hưởng đến bí mật chung của Alice và Bob.

Giao thức được mô tả theo dạng toán học như sau:

Giao thức sử dụng nhóm số nguyên modulo p, với p là số nguyên tố, và g là căn nguyên thủy modulo p. Trong ví dụ dưới đây, giá trị công khai được viết bằng màu xanh, và giá trị bí mật được viết bằng màu đỏ:

1. Alice và Bob đồng ý sử dụng số nguyên tố p=23 và căn nguyên thủy g=5.
2. Alice chọn số bí mật a=6, và gửi cho Bob giá trị A = g mod p
   • A = 5 mod 23
   • A = 15,625 mod 23
   • A = 8
3. Bob chọn số bí mật b=15, và gửi cho Alice giá trị B = g mod p
   • B = 5 mod 23
   • B = 30,517,578,125 mod 23
   • B = 19
4. Alice tính toán s = B mod p
   • s = 19 mod 23
   • s = 47,045,881 mod 23
   • s = 2
5. Bob tính toán s = A mod p
   • s = 8 mod 23
   • s = 35,184,372,088,832 mod 23
   • s = 2
6. Do đó, Alice và Bob đều có bí mật chung là số 2, vì 615 bằng 156.

Cả Alice và Bob đều nhận được giá trị chung cuối cùng vì (g) = (g) mod p. Chỉ có a, b và g = g mod p là được giữ bí mật. Tất cả các giá trị khác như p, g, g mod p và g mod p được công khai. Sau khi có được bí mật chung, Alice và Bob có thể sử dụng nó làm khóa mã hóa chung chỉ họ biết để gửi dữ liệu qua kênh truyền thông mở.

Trong thực tế, để đảm bảo an toàn cho giao thức, người ta sử dụng giá trị lớn hơn nhiều cho a, b, và p. Trong ví dụ trên, có chỉ 23 kết quả khác nhau cho n mod 23 (do đó, kẻ tấn công chỉ cần thử hết 23 trường hợp để tìm ra khóa bí mật). Nếu số nguyên tố p có ít nhất 300 chữ số, và a và b có ít nhất 100 chữ số, thì ngay cả những máy tính hiện đại cũng không thể xác định a chỉ với g, p, g mod p và g mod p. Bài toán này, gọi là bài toán Logarit rời rạc, hiện chưa có cách giải hiệu quả bằng máy tính (do đó được dùng để tạo khóa công khai).

Lưu ý rằng g không nhất thiết phải là một căn nguyên thủy có giá trị cao. Thực tế, thường sử dụng các giá trị như 2, 3 hoặc 5.

Miêu tả giao thức

Dưới đây là mô tả tổng quan về giao thức.

1. Alice và Bob đồng ý sử dụng chung một nhóm cyclic hữu hạn G và một phần tử sinh g thuộc G. Phần tử sinh g là công khai với mọi người, bao gồm cả kẻ tấn công. Chúng ta giả định nhóm G là nhóm nhân.
2. Alice chọn một số ngẫu nhiên a và gửi g mod p cho Bob.
3. Bob chọn một số ngẫu nhiên b và gửi g mod p cho Alice.
4. Alice tính toán (g) mod p.
5. Bob tính toán (g) mod p.

Vì giá trị của (g) và (g) là như nhau (do tính chất kết hợp của nhóm G), cả Alice và Bob đều có thể tính ra giá trị g và sử dụng nó làm khóa bí mật chung.

Trước khi gửi, thông điệp m của Alice (hoặc Bob) sẽ được mã hóa thành mg.

Để giải mã thông điệp m đã được mã hóa thành mg, Bob (hoặc Alice) cần tính giá trị (g). Giá trị (g) được tính như sau: Vì Bob biết |G|, b, và g, theo định lý Lagrange trong lý thuyết nhóm, ta có x = 1 với mọi x thuộc G, Bob có thể tính được (g) = g = g = gg = (g)g=1g=g=(g).

Giải mã trở nên đơn giản hơn: Bob dùng giá trị (g) đã tính để phục hồi thông điệp gốc bằng cách tính: mg(g) = m(1) = m.

Chương trình C đơn giản

#include 
#include 
#include 
#include 
#include 

int prime(int num) {
 int i;
 for (i = 2; ii <= num; ++i)
 if (num % i == 0)
 return 0;
 return 1;
}

int mod(int base, int expo, int num) {
 int res = 1;
 int i;
 for (i = 1; i 
  

    
  
  <= expo; ++i)
 res = (res  base) % num;
 return res;
}

int main() {
 int p, g, a, b, i, j, r1, r2, k1, k2, k3;
 srand(time(NULL));
 p:
 printf('
Nhập p và g: (hoặc comment dòng này để tạo giá trị ngẫu nhiên)');
 scanf('%d %d', &p, &g);

 if (!prime(p) || !prime(g)) {
 printf('
Các giá trị nhập không phải nguyên tố... Vui lòng nhập lại...');
 goto p;
 } else {
 srand(time(NULL));
 a = rand() % 50;
 b = rand() % 50;
 printf('
Số ngẫu nhiên: %d %d', a, b);
 r1 = mod(g, a, p); // g^a mod p
 r2 = mod(g, b, p); // g^b mod p
 printf('
R1 = %d
R2 = %d
', r1, r2);
 k1 = mod(r2, a, p); // r2^a mod p
 k2 = mod(r1, b, p); // r1^b mod p
 printf('
Khóa bí mật chung tính bởi Alice: %d', k1);
 printf('
Khóa bí mật chung tính bởi Bob: %d', k2);
 k3 = mod(g, a  b, p); // g^ab mod p
 printf('
Kiểm tra Khóa bí mật chung: %d', k3); // phải giống k1 và k2
 }
getch(); // Dừng màn hình để xem kết quả
}

Đề đồ

Trong giao thức này, Alice và Bob là hai bên trao đổi khóa. Kẻ nghe lén Eve có thể theo dõi thông tin giữa Alice và Bob nhưng không thể thay đổi nội dung của nó (tấn công bị động). Sơ đồ dưới đây mô tả rõ những thông tin mà mỗi bên biết trong mô hình giao thức.

• Đặt s là khóa bí mật chung. Trong trường hợp này, s = 2
• Đặt g là căn nguyên công khai. Giá trị của g là 5
• Đặt p là số nguyên tố công khai. Trong trường hợp này, p = 23
• Đặt a là khóa riêng của Alice. Giá trị của a là 6
• Đặt A là khóa công khai của Alice. Tính toán được là g mod p = 8
• Đặt b là khóa riêng của Bob. Giá trị của b là 15
• Đặt B là khóa công khai của Bob. Kết quả tính được là g mod p = 19

Chú ý: Việc giải mã khóa riêng của Alice hoặc Bob có thể rất khó khăn. Nếu Alice dễ dàng tìm được khóa riêng của Bob (hoặc ngược lại), thì Eve có thể giả mạo khóa bí mật chung bằng cách thay thế cặp khóa công khai/riêng tư, gắn khóa công khai của Bob vào khóa riêng của mình, và tính toán khóa bí mật chia sẻ giả. Sau đó, Eve có thể giải mã khóa riêng của Bob và tìm khóa bí mật chung giữa Bob và Alice. Eve cũng có thể chọn cặp khóa công khai/riêng tư sao cho việc giải mã khóa riêng của Bob trở nên đơn giản hơn.

Xem một ví dụ về giao thức Diffie-Hellman (với các số nhỏ) tại đây Lưu trữ ngày 12-08-2011 trên Wayback Machine

.

Có thể nhận thấy rằng trong quá trình tính toán, các khóa có thể bị lặp lại giữa các bên tham gia. Một thứ tự hợp lý hơn có thể giúp giảm số lượng phép tính lũy thừa modulo mà mỗi người tham gia phải thực hiện. Cụ thể, số phép tính lũy thừa có thể giảm xuống còn ${\log }_2<!--\; \; -->\left(N\right)+1$ bằng cách áp dụng phương pháp chia để trị. Ví dụ dưới đây minh họa phương pháp này cho 8 người.

1. Mỗi người A, B, C, và D thực hiện phép toán lũy thừa để tính $g^{abcd}\mathrm{mod}p$; kết quả được gửi cho E, F, G, và H. Ngược lại, A, B, C, và D nhận $g^{efgh}\mathrm{mod}p$.
2. A và B mỗi người thực hiện một phép toán lũy thừa để tính $g^{efghab}\mathrm{mod}p$, rồi gửi cho C và D. C và D cũng thực hiện tương tự để tính $g^{efghcd}\mathrm{mod}p$ và gửi cho A và B.
3. A thực hiện phép toán lũy thừa cuối cùng để tính bí mật $g^{efghcda}\mathrm{mod}p$, và gửi cho B. Tương tự, B thực hiện phép toán để tính và gửi $g^{efghcdb}\mathrm{mod}p$ cho A. Tương tự, C và D cũng thực hiện các phép toán này.
4. A thực hiện phép toán lũy thừa cuối cùng để có bí mật $g^{efghcdba}=g^{abcdefgh}\mathrm{mod}p$, trong khi B cũng tính và nhận được $g^{efghcdab}\mathrm{mod}p=g^{abcdefgh}\mathrm{mod}p$. Tương tự, C và D cũng sẽ tìm ra bí mật chung này.

Sau khi hoàn tất các bước trên, tất cả các tham gia đều có bí mật chung là $g^{abcdefgh}\mathrm{mod}p$, với mỗi người chỉ cần thực hiện 4 phép toán lũy thừa thay vì 8 như trong trường hợp sử dụng thứ tự vòng tròn.

Bảo mật

Giao thức này được cho là bảo vệ thông tin chống lại kẻ nghe lén, nếu như G và g được chọn chính xác. Kẻ nghe lén Eve cần giải bài toán Diffie–Hellman để tìm được g. Hiện tại, bài toán này được coi là rất khó đối với các máy tính hiện đại. Các thuật toán giải quyết bài toán lôgarit rời rạc có thể dễ dàng tính được a hoặc b và giải bài toán Diffie–Hellman, qua đó làm hệ thống mã hóa này và các hệ thống mã hóa công khai khác trở nên không an toàn.

Để ngăn ngừa việc áp dụng thuật toán Pohlig–Hellman để tìm số bí mật a hoặc b, cấp của G nên là một số nguyên tố hoặc có chứa các thừa số nguyên tố lớn. Do đó, số nguyên tố Sophie Germain q thường được chọn để tính số nguyên tố an toàn p=2q+1, vì cấp của G chỉ có hai thừa số nguyên tố là 2 và q. Đôi khi, giá trị g được chọn để tạo ra nhóm con cấp q của G, thay vì G chính, giúp ngăn chặn việc sử dụng ký hiệu Legendre của g để lộ bit thấp của a.

Nếu bộ sinh số ngẫu nhiên của Alice và Bob tạo ra số không hoàn toàn ngẫu nhiên hoặc có thể dự đoán, việc giải mã của Eve sẽ trở nên dễ dàng hơn nhiều.

Các số bí mật a và b sẽ bị xóa sau khi hoàn tất phiên truyền dữ liệu, do đó, trao đổi khóa Diffie–Hellman đạt được tính bảo mật chuyển tiếp hoàn hảo vì không có thông tin dài hạn nào bị rò rỉ.

Trong mô tả gốc, phương thức trao đổi Diffie–Hellman không cung cấp khả năng xác thực cho các bên, làm cho nó dễ bị tấn công kiểu người đứng giữa. Eve có thể thiết lập hai giao thức trao đổi với Alice và Bob, cho phép Eve giả danh Alice khi giao tiếp với Bob và ngược lại, từ đó có thể giải mã và mã hóa lại thông điệp giữa Alice và Bob mà không bị phát hiện. Eve phải luôn luôn đứng giữa để chuyển tiếp thông điệp đã mã hóa lại, nếu không Alice và Bob sẽ phát hiện ra sự can thiệp của Eve.

Để phòng ngừa các tấn công kiểu người đứng giữa, cần có phương pháp xác thực các bên tham gia. Các biến thể của Diffie-Hellman như STS có thể được áp dụng để bảo vệ chống lại các cuộc tấn công như vậy.

Các ứng dụng khác

Thỏa thuận khóa qua xác thực mật khẩu

Để chia sẻ mật khẩu, Alice và Bob có thể áp dụng phương pháp trao đổi khóa qua xác thực mật khẩu (PAKE) dựa trên giao thức Diffie–Hellman nhằm ngăn chặn tấn công người đứng giữa. Một phương pháp đơn giản là sử dụng phần tử sinh g làm mật khẩu. Với cách này, kẻ tấn công chỉ có thể thử một mật khẩu mỗi lần giao tiếp với một bên, giúp hệ thống vẫn bảo mật tốt dù mật khẩu tương đối yếu. Giải pháp này được mô tả trong tiêu chuẩn X.1035 của ITU-T và được áp dụng trong chuẩn mạng máy tính G.hn.

Khóa công khai

Diffie–Hellman cũng có thể được sử dụng như một phần của hạ tầng khóa công khai. Cụ thể, khóa công khai của Alice có thể được định nghĩa là . Để gửi một thông điệp đến Alice, Bob chọn một số ngẫu nhiên b và gửi Alice (không mã hóa) và thông điệp đã được mã hóa bằng khóa đối xứng . Chỉ Alice mới có thể giải mã thông điệp vì cô ấy có khóa riêng a. Để phòng ngừa tấn công người đứng giữa, có thể sử dụng một khóa công khai đã được chia sẻ trước.

Trên thực tế, Diffie–Hellman không được áp dụng phổ biến như RSA, thuật toán mã hóa khóa công khai chủ yếu được sử dụng. Nguyên nhân chính là do yếu tố lịch sử và thương mại, đặc biệt là sự đóng góp của công ty bảo mật RSA, nhà cung cấp chứng thực số nổi tiếng và sau này trở thành Verisign. Diffie–Hellman không phù hợp cho việc ký chứng thực, mặc dù thuật toán ElGamal và DSA có liên quan toán học đến chữ ký số. Các phương pháp như MQV, STS, và thành phần IKE trong giao thức IPsec cũng được dùng để bảo vệ thông tin trong giao thức Internet.

• Trao đổi khóa
• Đồng dư
• Elliptic curve Diffie–Hellman
• Mật mã hóa khóa công khai
• Mã hóa ElGamal
• Bài toán Diffie–Hellman
• MQV
• Trao đổi khóa qua xác thực mật khẩu
• Giao thức SRP

Chú thích

1. ^ Các thuật ngữ liên quan đến Trao đổi khóa Diffie–Hellman bao gồm:
   • Thỏa thuận khóa Diffie–Hellman
   • Thiết lập khóa Diffie–Hellman
   • Thương lượng khóa Diffie–Hellman
   • Trao đổi khóa lũy thừa
   • Giao thức Diffie–Hellman
   • Phương thức bắt tay Diffie–Hellman

• Dieter Gollmann (2006). Bảo mật Máy tính Ấn bản Thứ Hai West Sussex, England: John Wiley & Sons, Ltd.
• Có thể tham khảo tài liệu về mã hóa số không bí mật Lưu trữ 2014-10-30 tại Wayback Machine J. H. Ellis, tháng 1 năm 1970.
• Mã hóa không bí mật sử dụng trường hữu hạn Lưu trữ 2012-09-05 tại Wayback Machine MJ Williamson, ngày 21 tháng 1 năm 1974.
• Suy nghĩ về mã hóa không bí mật giá rẻ MJ Williamson, ngày 10 tháng 8 năm 1976.
• doi:10.1109/TIT.1976.1055638
  
• Thiết bị và phương pháp mật mã Martin E. Hellman, Bailey W. Diffie, và Ralph C. Merkle, Bằng sáng chế Mỹ #4,200,770, ngày 29 tháng 4 năm 1980
• Lịch sử của mã hóa không bí mật Lưu trữ 2014-10-30 tại Wayback Machine JH Ellis 1987 (28K PDF file) (Phiên bản HTML Lưu trữ 2010-11-27 tại Wayback Machine)
• Những năm đầu của mã hóa khóa công khai Whitfield Diffie, Proceedings of the IEEE, vol. 76, no. 5, tháng 5 năm 1988, pp: 560–577 (1.9MB PDF file)
• Menezes, Alfred; van Oorschot, Paul; Vanstone, Scott (1997). Sổ tay Mật mã học Ứng dụng Boca Raton, Florida: CRC Press. ISBN 0-8493-8523-7. (Có sẵn trực tuyến)
• Singh, Simon (1999) Sách Mã: sự phát triển của bí mật từ Mary Queen of Scots đến mã hóa lượng tử New York: Doubleday ISBN 0-385-49531-5
• Tổng quan về Mã hóa khóa công khai Martin E. Hellman, IEEE Communications Magazine, tháng 5 năm 2002, pp:42–49. (123kB PDF file)

Các liên kết hữu ích

• Giải thích trao đổi khóa Diffie-Hellman trong 5 phút
• Phỏng vấn lịch sử miệng với Martin Hellman, Charles Babbage Institute, Đại học Minnesota. Nhà nghiên cứu mật mã hàng đầu Martin Hellman thảo luận về hoàn cảnh và những hiểu biết cơ bản của việc phát minh ra mã hóa khóa công khai cùng với các cộng sự Whitfield Diffie và Ralph Merkle tại Đại học Stanford vào giữa những năm 1970.
• RFC 2631 – Phương pháp Thoả thuận Khóa Diffie–Hellman E. Rescorla tháng 6 năm 1999.
• Tóm tắt ANSI X9.42: Thoả thuận Khóa Đối xứng Sử dụng Mật mã Logarit Rời rạc (64K PDF file) (Mô tả về tiêu chuẩn ANSI 9 Lưu trữ 2004-08-16 tại Wayback Machine)
• Trao đổi Khóa Diffie–Hellman – Giải thích không toán học của Keith Palmgren
• Crypt::DH Module Perl từ CPAN
• Trình diễn thực tế về Diffie–Hellman
• Triển khai C sử dụng GNU Multiple Precision Arithmetic Library Lưu trữ 2008-06-27 tại Wayback Machine
• Diffie Hellman trong 2 dòng mã Perl (sử dụng dc)
• Quản lý Tài khoản Thông minh (SAcct) (sử dụng trao đổi khóa DH để rút ra khóa phiên)
• Bài nói chuyện của Martin Hellman năm 2007, video Google Lưu trữ 2011-12-15 tại Wayback Machine