Trao đổi khóa Diffie-Hellman

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.

Mô tả giao thức

Sau đây là mô tả khái quát của giao thức.

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 mgᵃᵇ.

Giải mã

Để giải mã thông điệp m, gửi dưới dạng mgᵃᵇ, Bob (hoặc Alice) phải tính được giá trị (gᵃᵇ)⁻¹. Giá trị (gᵃᵇ)⁻¹ được tính như sau:
Vì Bob biết |G|, b, và gᵃ, 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 (gᵃ)|G|-b = g = ga|G|-ab = ga|G|g⁻ᵃᵇ = (g|G|)ᵃg⁻ᵃᵇ=1ᵃg⁻ᵃᵇ=g⁻ᵃᵇ=(gᵃᵇ)⁻¹.
Việc giải mã bây giờ trở nên dễ dàng: Bob sử dụng (gᵃᵇ)⁻¹ đã tính và phục hồi thông điệp nguyên thủy bằng cách tính: mgᵃᵇ(gᵃᵇ)⁻¹ = 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ả}

Giao thức cho nhóm nhiều hơn hai người

Giao thức Diffie-Hellman không giới hạn việc thỏa thuận khóa chỉ cho hai bên tham gia. Bất kỳ số lượng người sử dụng nào cũng có thể tham gia vào giao thức để tạo khóa bí mật chung bằng cách thực hiện  lặp lại các bước trao đổi thông tin và tính toán trong giao thức.

Phương pháp vòng tròn

Các nguyên tắc trên cho phép thực hiện theo bất kỳ thứ tự nào giữa những người tham gia. Cách đơn giản và dễ hiểu nhất có lẽ là sắp xếp  người tham gia theo vòng tròn và chuyển  khóa theo vòng tròn cho tới khi mỗi khóa được chuyển tới tất cả  người tham gia (kết thúc với người sở hữu khóa đó) và  mỗi người đã đóng góp phần của mình trong  khóa đó (kết thúc với khóa của riêng mỗi người). Cách này yêu cầu mỗi người thực hiện  phép tính modulo lũy thừa.

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ᵃᵇ.  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 gᵃ 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.

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.