Trao đổi khóa Diffie-Hellman

Trao đổi khóa Diffie–Hellman (D-H) là một phương pháp trao đổi khóa được phát minh sớm nhất trong mật mã học. Phương pháp trao đổi khóa Diffie–Hellman cho phép hai bên (người, thực thể giao tiếp) thiết lập một khóa bí mật chung để mã hóa dữ liệu sử dụng trên kênh truyền thông không an toàn mà không cần có sự thỏa thuận trước về khóa bí mật giữa hai bên. Khóa bí mật tạo ra sẽ được sử dụng để mã hóa dữ liệu với phương pháp mã hóa khóa đối xứng.
Giao thức này được công bố đầu tiên bởi Whitfield Diffie và Martin Hellman vào năm 1976, dù rằng trước đó vài năm nó đã được phát minh một cách độc lập trong GCHQ, cơ quan tình báo Anh, bởi James H. Ellis, Clifford Cocks và Malcolm J. Williamson nhưng được giữ bí mật. Năm 2002, Hellman đề xuất thuật toán nên được gọi là trao đổi khóa Diffie–Hellman–Merkle để ghi nhận sự đóng góp của Ralph Merkle trong phát minh lĩnh vực mật mã hóa khóa công khai (Hellman, 2002).
Mặc dù giao thức trao đổi khóa Diffie–Hellman bản thân nó là giao thức trao đổi khóa "ẩn danh" (không "xác thực"), nó đã đưa ra một nền tảng cơ sở cho nhiều loại giao thức xác thực và được sử dụng để tạo nên bí mật chuyển tiếp hoàn hảo trong chế độ ngắn hạn của giao thức Transport Layer Security (EDH hoặc DHE tùy theo bộ mã hóa).
Phương pháp này được áp dụng sau đó cho thuật toán RSA (mã hóa)
Năm 2002, Martin Hellman viết: 
Hệ thống này cho tới nay được biết đến với tên gọi Trao đổi khóa Diffie–Hellman. Khi hệ thống lần đầu tiên được mô tả trong bài báo của Diffie và tôi, đó là một hệ thống phân phối khóa công khai, một khái niệm nêu ra bởi Merkle, vì vậy nó nên được gọi là Trao đổi khóa 'Diffie–Hellman–Merkle' nếu chúng ta cần một cái tên cho nó. Tôi hy vọng rằng chút lời mọn của tôi ở đây sẽ giúp mọi người ghi nhận sự đóng góp tương xứng của Merkle trong phát minh lĩnh vực mật mã hóa khóa công khai. 
 mô tả thuật toán này từ năm 1977, tới nay đã hết hạn bản quyền, đã ghi nhận Hellman, Diffie, và Merkle là tác giả phát minh.
Mô tả.
Diffie–Hellman thiết lập bí mật chung để sử dụng cho trao đổi dữ liệu an toàn trên một kênh truyền thông công cộng không an toàn. Sơ đồ sau đây minh họa ý tưởng cơ bản của việc trao đổi khóa thông qua ví dụ về màu sơn.
Ý tưởng cơ bản.
Điểm chủ chốt của ý tưởng này là Alice và Bob trao đổi màu sơn bí mật thông qua hỗn hợp sơn. 
Hỗn hợp sơn cuối cùng là hoàn toàn giống nhau cho cả hai người và chỉ có riêng hai người biết. Mấu chốt ở đây là đối với một người ngoài sẽ rất khó (về mặt tính toán) cho họ để tìm ra được bí mật chung của hai người (nghĩa là hỗn hợp cuối cùng). Alice và Bob sẽ sử dụng bí mật chung này để mã hóa và giải mã dữ liệu truyền trên kênh công cộng. Lưu ý, màu sơn đầu tiên (màu vàng) có thể tùy ý lựa chọn, nhưng được thỏa thuận trước giữa Alice và Bob. Màu sơn này cũng có thể được giả sử là không bí mật đối với người thứ ba mà không làm lộ bí mật chung cuối cùng của Alice và Bob.
Giao thức được diễn giải dưới dạng toán học như sau:
Giao thức sử dụng nhóm nhân số nguyên modulo "p", trong đó "p" số nguyên tố, và "g" là căn nguyên thủy mod "p". Trong ví dụ dưới đây, giá trị không bí mật được viết bằng màu xanh, và giá trị bí mật viết bằng màu đỏ:
Cả Alice và Bob đều có được giá trị chung cuối cùng vì ("ga")"b" = ("gb")"a" mod "p". Lưu ý rằng chỉ có "a", "b" và "gab = gba" mod "p" là được giữ bí mật. Tất cả các giá trị khác như "p", "g", "ga mod p" và "gb mod p" được truyền công khai. Sau khi Alice và Bob tính được bí mật chung, cả hai có thể sử dụng nó làm khóa mã hóa chung chỉ có hai người biết để gửi dữ liệu trên kênh truyền thông mở.
Trong thực tế để giao thức được an toàn, người ta sử dụng giá trị lớn hơn nhiều cho "a", "b", và "p", vì trong ví dụ trên chỉ có tổng cộng 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 là tìm ra khóa bí mật). Nếu số nguyên tố "p" có ít nhất 300 chữ số, còn "a" và "b" có ít nhất 100 chữ số, thì ngay cả những máy tính hiện đại nhất hiện nay cũng không thể tìm được "a" nếu chỉ biết "g", "p", "gb" mod "p" và "ga" mod "p". Bài toán này, gọi là bài toán Lôgarit rời rạc, hiện chưa có cách giải hiệu quả bằng máy tính (vì vậy được sử dụng để tạo khóa công khai).
Lưu ý, "g" không cần thiết là một căn nguyên thủy có giá trị lớn. Trong thực tế người ta hay sử dụng các giá trị 2, 3 hoặc 5.
Mô tả giao thức.
Sau đây là mô tả khái quát của giao thức.
Thiết lập khóa.
Vì giá trị ("gb")"a" và ("ga")"b" là bằng nhau (do nhóm "G" có tính kết hợp), cả Alice và Bob đều tính được giá trị "gab" và có thể sử dụng nó cho khóa bí mật chung.
Mã hóa.
Thông điệp "m" trước khi được gửi đi bởi Alice (hoặc Bob) sẽ được mã hóa thành "mgab".
Giải mã.
Để giải mã thông điệp "m", gửi dưới dạng "mgab", Bob (hoặc Alice) phải tính được giá trị "(gab)-1". Giá trị "(gab)-1" được tính như sau:
Vì Bob biết "|G|, b," và "ga", mặt khác theo định lý Lagrange trong lý thuyết nhóm ta có "x|G| = 1" với mọi "x" thuộc "G",
nên Bob tính được "(ga)|G|-b = ga(|G|-b) = ga|G|-ab = ga|G|g-ab = (g|G|)ag-ab=1ag-ab=g-ab=(gab)-1."
Việc giải mã bây giờ trở nên dễ dàng: Bob sử dụng "(gab)-1" đã tính và phục hồi thông điệp nguyên thủy bằng cách tính: "mgab(gab)-1 = m(1) = m."
Chương trình C đơn giản.
int prime(int num) {
 int i;
 for (i = 2; i*i &lt;= 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 &lt;= 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("\nNhập p và g: (hoặc comment dòng này để tạo giá trị ngẫu nhiên)");
 scanf("%d %d", &amp;p, &amp;g);
 if (!prime(p) || !prime(g)) {
 printf("\nCá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("\nSố tạo 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("\nR1 = %d\nR2 = %d\n", r1, r2);
 k1 = mod(r2, a, p); // r2^a mod p
 k2 = mod(r1, b, p); // r1^b mod p
 printf("\nKhóa bí mật chung tính được bởi Alice: %d", k1);
 printf("\nKhóa bí mật chung tính được bởi Bob: %d", k2);
 k3 = mod(g, a * b, p); // g^a*b mod p
 printf("\nKiể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ả
Sơ đồ.
Trong giao thức này, hai bên trao đổi khóa là Alice và Bob. Kẻ nghe lén Eve có thể quan sát được thông tin truyền giữa Alice và Bob nhưng không thay đổi nội dung thông tin (tấn công bị động). Sơ đồ sau đây tóm tắt mỗi người biết gì trong mô hình của giao thức.
Lưu ý: Việc Bob giải được khóa riêng tư của Alice, và Alice giải được khóa riêng tư của Bob phải là bài toán khó đối với cả hai. Nếu bài toán tìm khóa riêng tư của Bob không khó đối với Alice (hoặc ngược lại), thì Eve chỉ cần thay thế cặp khóa riêng tư / công khai của mình, gắn khóa công khai của Bob vào khóa riêng tư của mình, tạo ra khóa bí mật chia sẻ giả, và giải ra khóa riêng tư của Bob, sau đó sử dụng nó để tìm ra khóa bí mật chia sẻ giữa Bob và Alice. Eve cũng có thể tìm cách chọn cặp khóa công khai / riêng tư nào đó giúp Eve giải được khóa riêng tư của Bob một cách dễ dàng.
Có thể tham khảo một demo về giao thức Diffie-Hellman (sử dụng các số nhỏ) ở đây 
Phương pháp chia để trị.
Có thể thấy rằng trong quá trình tính toán các khóa có thể bị tính trùng lặp bởi các bên tham gia. Như vậy một thứ tự tốt khác có thể giúp ta giảm số lượng phép tính modulo lũy thừa tính bởi mỗi người tham gia xuống. Cụ thể, số lượng phép tính lũy thừa có thể giảm xuống còn formula_1 bằng cách sử dụng kiểu phương pháp chia để trị. Ví dụ sau minh họa phương pháp này cho 8 người:
Sau khi các bước này hoàn tất thì tất cả mọi người tham gia đều có bí mật formula_11, trong đó mỗi người chỉ thực hiện 4 phép tính lũy thừa so với 8 trong trường hợp thứ tự vòng tròn như trên.
Bảo mật.
Người ta cho rằng giao thức sẽ bảo vệ thông tin đối với kẻ nghe lén nếu như "G" và "g" được chọn đúng. Kẻ nghe lén Eve cần phải giải được bài toán Diffie–Hellman để có thể tìm ra "g""ab". Bài toán này hiện nay được xem là bài toán khó đối với các máy tính hiện đại ngày nay. Thuật toán nào có thể giải quyết một cách hiệu quả bài toán lôgarit rời rạc sẽ dễ dàng tính được "a" hoặc "b" và giải được bài toán Diffie–Hellman, qua đó biến hệ mã hóa này và cá hệ mã hóa công khai khác trở nên mất an toàn.
cấp của "G" phải là số nguyên tố hoặc có chứa thừa số nguyên tố lớn nhằm để tránh việc áp dụng thuật toán Pohlig–Hellman để tìm được "a" hoặc "b". Vì lý do này, số nguyên tố Sophie Germain "q" thỉnh thoảng được sử dụng để tính số nguyên tố an toàn "p=2q+1", bởi vì cấp của "G" khi đó chỉ có 2 thừa số nguyên tố là 2 và "q". Giá trị "g" thỉnh thoảng được chọn để sinh ra cấp "q" nhóm con của "G", hơn là "G", nhờ đó ký hiệu Legendre của "ga" không làm lộ bit thấp của "a".
Nếu bộ tạo số ngẫu nhiên sử dụng bởi Alice và Bob xuất ra số không hoàn toàn ngẫu nhiên hoặc số có thể đoán biết được một phần nào đó thì nhiệm vụ phá mã của Eve sẽ trở nên dễ dàng hơn nhiều.
Các số nguyên bí mật "a" và "b" sẽ bị loại bỏ ở cuối phiên truyền dữ liệu, do đó, trao đổi khóa Diffie–Hellman hiển nhiên đạt được tính bí mật chuyển tiếp hoàn hảo vì không có thông tin riêng tư dài hạn nào bị lộ ra.
Trong bản mô tả nguyên thủy của mình, phương thức trao đổi Diffie–Hellman bản thân nó không cung cấp khả năng xác thực cho các bên giao tiếp, và vì vậy trở nên không an toàn đối với hình thức tấn công người đứng giữa. Eve có thể thiết lập hai giao thức trao đổi, một với Alice và một với Bob, giúp cho Eve có thể giả dạng Alice đối với Bob và ngược lại một cách hiệu quả, từ đó có thể giải mã, rồi mã hóa lại thông điệp chuyển giữa Alice và Bob mà không bị phát hiện. Lưu ý rằng để 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) bất cứ khi nào Alice và Bob gửi. Nếu Eve ngưng chuyển tiếp, Alice và Bob sẽ phát hiện ra sự hiện diện của Eve và biết được rằng thông tin trao đổi riêng tư giữa hai người đã bị can thiệp và lộ ra với một người ngoài nào đó bất hợp pháp.
Một phương pháp để xác thực các bên tham gia với nhau là cần thiết để đề phòng các loại hình tấn công này. Những biến thể của Diffie-Hellman như STS có thể được áp dụng để tránh các cuộc tấn công kiểu này.
Các ứng dụng khác.
Thỏa thuận khóa bằng xác thực mật khẩu.
Để chia sẻ mật khẩu, Alice và Bob có thể sử dụng dạng trao đổi khóa bằng xác thực mật khẩu (PAKE) của giao thức Diffie–Hellman để đề phòng tấn công người đứng giữa. Một cách đơn giản là sử dụng phần tử sinh "g" làm mật khẩu. Đặc điểm của cách này là kẻ tấn công chỉ có thể thử một mật khẩu duy nhất trong mỗi lần tương tác với một bên, do đó hệ thống này có thể cung cấp khả năng bảo mật tốt ngay cả với một 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 sử dụng trong chuẩn mạng máy tính trong nhà G.hn.
Khóa công khai.
Người ta cũng có thể sử dụng Diffie–Hellman như là một phần của hạ tầng khóa công khai. Một cách đơn giản, khóa công khai của Alice được đặt là formula_12. Để gửi một thông điệp tới Alice, Bob chọn một số ngẫu nhiên "b" và gửi Alice formula_13 (không mã hóa) cùng với thông điệp được mã hóa với khóa đối xứng formula_14. Chỉ có Alice mới có thể giải mã thông điệp vì chỉ có cô mới có khóa riêng tư "a". Để chống tấn công người đứng giữa, người ta có thể sử dụng một khóa công khai được chia sẻ trước.
Trong thực tế, Diffie–Hellman không được sử dụng theo cách này vì thực ra RSA là thuật toán mã hóa khóa công khai được dùng phổ biến nhất. Lý do chính là do yếu tố lịch sử và thương mại, cụ thể là công ty bảo mật RSA tạo nên nhà cung cấp chứng thực số dùng cho chữ ký số, sau này trở thành Verisign. Diffie–Hellman không thể dùng để ký chứng thực. Tuy nhiên, thuật toán ElGamal và DSA có mối liên hệ toán học với chữ ký số, cũng như là MQV, STS và thành phần IKE của bộ giao thức IPsec dùng để đảm bảo an toàn thông tin cho giao thức Internet.