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. 
 Đầu tiên Alice và Bob trộn màu đã biết chung (màu vàng) với màu bí mật riêng của mỗi người.
 Sau đó, mỗi người chuyển hỗn hợp của mình tới người kia thông qua một kênh vận chuyển công cộng.
 Khi nhận được hỗn hợp của người kia, mỗi người sẽ trộn thêm với màu bí mật của riêng mình và nhận được hỗn hợp cuối cùng.

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  đỏ:
 Alice và Bob thỏa thuận sử dụng chung một số nguyên tố p=23 và căn nguyên thủy g=5.
 Alice chọn một số nguyên bí mật a=6, và gửi cho Bob giá trị A = ga mod p
 A = 56 mod 23
 A = 15,625 mod 23
 A = 8
 Bob chọn một số nguyên bí mật b=15, và gửi cho Alice giá trị B = gb mod p
 B = 515 mod 23
 B = 30,517,578,125 mod 23
 B = 19
 Alice tính s = B a mod p
 s = 196 mod 23
 s = 47,045,881 mod 23
 s = 2
 Bob tính s = A b mod p
 s = 815 mod 23
 s = 35,184,372,088,832 mod 23
 s = 2
 Như vậy Alice và Bob cùng chia sẻ bí mật chung là số 2 vì 6*15 cũng bằng 15*6.

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 

 Alice và Bob thỏa thuận sử dụng chung một nhóm cyclic hữu hạn G và một phần tử sinh g của G.  Phần tử sinh g công khai với tất cả mọi người, kể cả kẻ tấn công. Dưới đây chúng ta giả sử nhóm G là nhóm nhân.
 Alice chọn một số tự nhiên ngẫu nhiên a và gửi ga mod p cho Bob.
 Bob chọn một số tự nhiên ngẫu nhiên b và gửi gb mod p cho Alice.
 Alice tính (gb)a mod p.
 Bob tính (ga)b mod p.

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
#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#include <time.h>
#include <conio.h>

int prime(int num) {
    int i;
    for (i = 2; i*i <= 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("\nNhậ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("\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.

 Đặt s = khóa bí mật được chia sẻ. s = 2
 Đặt g = căn nguyên thủy công khai. g = 5
 Đặt p = số nguyên tố công khai. p = 23
 Đặt a = khóa riêng tư của Alice. a = 6
 Đặt A = khóa công khai của Alice. A = ga mod p = 8
 Đặt b = khóa riêng tư của Bob. b = 15
 Đặt B = khóa công khai của Bob. B = gb mod p = 19

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  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:

 Mỗi người A, B, C, và D thực hiện một phép tính lũy thừa để tính ; giá trị này được gửi đến E, F, G, và H. Ngược lại A, B, C, và D nhận .
 A và B mỗi người thực hiện một phép tính lũy thừa để tính , rồi gửi cho C và D. Ngược lại C và D làm tương tự để tính  và gửi cho A và B.
 A thực hiện một phép tính lũy thừa để tính , sau đó gửi cho B. Tương tự, B tính và gửi  cho A. Bên C và D cũng thực hiện tương tự.
 A thực hiện một phép tính lũy thừa cuối cùng để có được bí mật , trong khi đó B cũng tính tương tự để có . Và cũng như vậy, C và D cũng tìm được bí mật chia sẻ chung.
 Những người từ E đến H cũng cùng lúc thực hiện các bước như trên cho giá trị nhận được  từ phía nhóm kia và tính được bí mật chia sẻ chung.

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 , 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 gab.  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à .  Để 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  (không mã hóa) cùng với thông điệp được mã hóa với khóa đối xứng .  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.

Xem thêm
 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 bằng xác thực mật khẩu
 Giao thức SRP

Chú thích

Tham khảo

 Dieter Gollmann (2006). Computer Security Second Edition West Sussex, England: John Wiley & Sons, Ltd.
 The possibility of Non-Secret digital encryption  J. H. Ellis, January 1970.
 Non-Secret Encryption Using a Finite Field  MJ Williamson, ngày 21 tháng 1 năm 1974.
 Thoughts on Cheaper Non-Secret Encryption MJ Williamson, ngày 10 tháng 8 năm 1976.
 
  Martin E. Hellman, Bailey W. Diffie, and Ralph C. Merkle, U.S. Patent #4,200,770, ngày 29 tháng 4 năm 1980
 The History of Non-Secret Encryption  JH Ellis 1987 (28K PDF file) (HTML version )
 The First Ten Years of Public-Key Cryptography Whitfield Diffie, Proceedings of the IEEE, vol. 76, no. 5, May 1988, pp: 560–577 (1.9MB PDF file)
 Menezes, Alfred; van Oorschot, Paul; Vanstone, Scott (1997).  Handbook of Applied Cryptography Boca Raton, Florida: CRC Press. ISBN 0-8493-8523-7. (Available online)
 Singh, Simon (1999) The Code Book: the evolution of secrecy from Mary Queen of Scots to quantum cryptography New York: Doubleday ISBN 0-385-49531-5
 An Overview of Public Key Cryptography Martin E. Hellman, IEEE Communications Magazine, May 2002, pp:42–49. (123kB PDF file)

Liên kết ngoài
Diffie-Hellman key exchange explained in 5 minutes
Oral history interview with Martin Hellman, Charles Babbage Institute, University of Minnesota.  Leading cryptography scholar Martin Hellman discusses the circumstances and fundamental insights of his invention of public key cryptography with collaborators Whitfield Diffie và Ralph Merkle at Stanford University in the mid-1970s.
 RFC 2631 – Diffie–Hellman Key Agreement Method E. Rescorla June 1999.
 Summary of ANSI X9.42: Agreement of Symmetric Keys Using Discrete Logarithm Cryptography (64K PDF file) (Description of ANSI 9 Standards )
 Diffie–Hellman Key Exchange – A Non-Mathematician’s Explanation by Keith Palmgren
 Crypt::DH Perl module from CPAN
 Hands-on Diffie–Hellman demonstration
 C implementation using GNU Multiple Precision Arithmetic Library 
 Diffie Hellman in 2 lines of Perl (using dc)
 Smart Account Management (SAcct) (using DH key exchange to derive session key)
 Talk by Martin Hellman in 2007, Google video 

Giao thức thỏa thuận khóa