Xem mã nguồn của Trao đổi khóa Diffie-Hellman

{{no footnotes|date=September 2013}}
'''Trao đổi khóa Diffie&ndash;Hellman''' ('''D-H''')<ref group="nb">Các thuật ngữ tương tự cho Trao đổi khóa Diffie&ndash;Hellman bao gồm:
*'''Thỏa thuận khóa Diffie&ndash;Hellman'''
*'''Thiết lập khóa Diffie&ndash;Hellman'''
*'''Thương lượng khóa Diffie&ndash;Hellman'''
*'''Trao đổi khóa lũy thừa'''
*'''Giao thức Diffie&ndash;Hellman'''
*'''Phương thức bắt tay Diffie;Hellman'''</ref> là một phương pháp trao đổi [[khóa (mật mã học)|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&ndash;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)|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&ndash;Hellman&ndash;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&ndash;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: 
<blockquote>Hệ thống này cho tới nay được biết đến với tên gọi Trao đổi khóa Diffie&ndash;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&ndash;Hellman&ndash;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. [http://www.comsoc.org/livepubs/ci1/public/anniv/pdfs/hellman.pdf] {{Webarchive|url=https://web.archive.org/web/20050118031258/http://www.comsoc.org/livepubs/ci1/public/anniv/pdfs/hellman.pdf |date=2005-01-18 }}</blockquote>

{{US patent|4,200,770}} 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&ndash;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.

[[Tập tin:Diffie-Hellman Key Exchange.svg|giữa|380px|Minh họa Trao đổi khóa Diffie-Hellman]]

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 các số nguyên modulo n|nhóm nhân số nguyên modulo]] ''p'', trong đó ''p'' [[số nguyên tố]], và ''g'' là [[Căn nguyên thủy modulo n|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 <span style="color:blue">xanh</span>, và giá trị bí mật viết bằng màu '''<span style="color:red"> đỏ</span>''':
{| cellspacing="1" cellpadding="4" border="0"
|-
|
{| class="wikitable"
|-
! colspan="3" | Alice
| <br>
| align="center" colspan="3" | '''Bob'''<br>
|-
| bgcolor="#d0d0d0" align="center" style="font-size: 90%;" | Bí mật
| bgcolor="#d0d0d0" align="center" style="font-size: 90%;" | Công khai
| bgcolor="#d0d0d0" align="center" style="font-size: 90%;" | Tính
| bgcolor="#d0d0d0" align="center" style="font-size: 90%;" | Gửi<br>
| bgcolor="#d0d0d0" align="center" style="font-size: 90%;" | Tính<br>
| bgcolor="#d0d0d0" align="center" style="font-size: 90%;" | Công khai<br>
| bgcolor="#d0d0d0" align="center" style="font-size: 90%;" | Bí mật<br>
|-
| align="center" | a<br>
| align="center" | p, g
| align="center" | <br>
| align="center" | p,g'''<math>\rightarrow</math>'''
| align="center" | <br>
| align="center" | <br>
| align="center" | b<br>
|-
| bgcolor="#e0e0e0" align="center" | a<br>
| bgcolor="#e0e0e0" align="center" | p, g, A<br>
| bgcolor="#e0e0e0" align="center" | g<sup>a</sup> mod p = A
| bgcolor="#e0e0e0" align="center" | A'''<math>\rightarrow</math>'''
| bgcolor="#e0e0e0" align="center" | <br>
| bgcolor="#e0e0e0" align="center" | p, g<br>
| bgcolor="#e0e0e0" align="center" | b<br>
|-
| align="center" | a<br>
| align="center" | p, g, A<br>
| align="center" | <br>
| align="center" | '''<math>\leftarrow</math>''' B<br>
| align="center" | g<sup>b</sup> mod p = B<br>
| align="center" | p, g, A, B<br>
| align="center" | b<br>
|-
| bgcolor="#e0e0e0" align="center" | a, '''s'''
| bgcolor="#e0e0e0" align="center" | p, g, A, B<br>
| bgcolor="#e0e0e0" align="center" | B<sup>a</sup> mod p = s<br>
| bgcolor="#e0e0e0" align="center" | <br>
| bgcolor="#e0e0e0" align="center" | A<sup>b</sup> mod p = s<br>
| bgcolor="#e0e0e0" align="center" | p, g, A, B<br>
| bgcolor="#e0e0e0" align="center" | b, '''s'''<br>
|}
| valign="bottom" |
|
|}
# Alice và Bob thỏa thuận sử dụng chung một số nguyên tố ''<span style="color:blue">p</span>''=<span style="color:blue">23</span> và căn nguyên thủy ''<span style="color:blue">g</span>''=<span style="color:blue">5</span>.
# Alice chọn một số nguyên bí mật '''''<span style="color:red">a</span>'''''='''<span style="color:red">6</span>''', và gửi cho Bob giá trị <span style="color:blue">A</span> = ''<span style="color:blue">g</span><sup>'''<span style="color:red">a</span>'''</sup>'' mod ''<span style="color:blue">p</span>''
#* <span style="color:blue">A</span> = <span style="color:blue">5</span><sup>'''<span style="color:red">6</span>'''</sup> mod <span style="color:blue">23</span>
#* <span style="color:blue">A</span> = '''<span style="color:red">15,625</span>''' mod <span style="color:blue">23</span>
#* <span style="color:blue">A</span> = <span style="color:blue">8</span>
# Bob chọn một số nguyên bí mật '''''<span style="color:red">b</span>'''''='''<span style="color:red">15</span>''', và gửi cho Alice giá trị <span style="color:blue">B</span> = ''<span style="color:blue">g</span><sup>'''<span style="color:red">b</span>'''</sup>'' mod ''<span style="color:blue">p</span>''
#* <span style="color:blue">B</span> = <span style="color:blue">5</span><sup>'''<span style="color:red">15</span>'''</sup> mod <span style="color:blue">23</span>
#* <span style="color:blue">B</span> = '''<span style="color:red">30,517,578,125</span>''' mod <span style="color:blue">23</span>
#* <span style="color:blue">B</span> = <span style="color:blue">19</span>
# Alice tính '''<span style="color:red">s</span>''' = ''<span style="color:blue">B</span>'' ''<sup>'''<span style="color:red">a</span>'''</sup>'' mod ''<span style="color:blue">p</span>''
#* '''<span style="color:red">s</span>''' = <span style="color:blue">19</span><sup>'''<span style="color:red">6</span>'''</sup> mod <span style="color:blue">23</span>
#* '''<span style="color:red">s</span>''' = '''<span style="color:red">47,045,881</span>''' mod <span style="color:blue">23</span>
#* '''<span style="color:red">s</span>''' = '''<span style="color:red">2</span>'''
# Bob tính '''<span style="color:red">s</span>''' = ''<span style="color:blue">A</span>'' ''<sup>'''<span style="color:red">b</span>'''</sup>'' mod ''<span style="color:blue">p</span>''
#* '''<span style="color:red">s</span>''' = <span style="color:blue">8</span><sup>'''<span style="color:red">15</span>'''</sup> mod <span style="color:blue">23</span>
#* '''<span style="color:red">s</span>''' = '''<span style="color:red">35,184,372,088,832</span>''' mod <span style="color:blue">23</span>
#* '''<span style="color:red">s</span>''' = '''<span style="color:red">2</span>'''
# Như vậy Alice và Bob cùng chia sẻ bí mật chung là số '''<span style="color:red">2</span>''' vì <span style="color:red">6</span>*<span style="color:red">15</span> cũng bằng <span style="color:red">15</span>*<span style="color:red">6</span>.

Cả Alice và Bob đều có được giá trị chung cuối cùng vì (''g<sup>a</sup>'')''<sup>b</sup>'' = (''g<sup>b</sup>'')''<sup>a</sup>'' mod ''p''.  Lưu ý rằng chỉ có ''a'', ''b'' và ''g<sup>ab</sup> = g<sup>ba</sup>'' mod ''p'' là được giữ bí mật.  Tất cả các giá trị khác như ''p'', ''g'', ''g<sup>a</sup> mod p'' và ''g<sup>b</sup> 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'', ''g<sup>b</sup>'' mod ''p'' và ''g<sup>a</sup>'' 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 ''g<sup>a</sup>'' mod p cho Bob.
# Bob chọn một số tự nhiên ngẫu nhiên ''b'' và gửi ''g<sup>b</sup>'' mod p cho Alice.
# Alice tính (''g<sup>b</sup>'')''<sup>a</sup>'' mod p.
# Bob tính (''g<sup>a</sup>'')''<sup>b</sup>'' mod p.

Vì giá trị (''g<sup>b</sup>'')''<sup>a</sup>'' và (''g<sup>a</sup>'')''<sup>b</sup>'' 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ị ''g<sup>ab</sup>'' 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 ''mg<sup>ab</sup>''.

==== Giải mã ====
Để giải mã thông điệp ''m'', gửi dưới dạng ''mg<sup>ab</sup>'', Bob (hoặc Alice) phải tính được giá trị ''(g<sup>ab</sup>)<sup>-1</sup>''. Giá trị ''(g<sup>ab</sup>)<sup>-1</sup>'' được tính như sau:
Vì Bob biết ''|G|, b,'' và ''g<sup>a</sup>'', mặt khác theo [[Định lý Lagrange (lý thuyết nhóm)|định lý Lagrange]] trong [[lý thuyết nhóm]] ta có ''x<sup>|G|</sup> = 1'' với mọi ''x'' thuộc ''G'',
nên Bob tính được ''(g<sup>a</sup>)<sup>|G|-b</sup> = g<sup>a(|G|-b)</sup> = g<sup>a|G|-ab</sup> = g<sup>a|G|</sup>g<sup>-ab</sup> = (g<sup>|G|</sup>)<sup>a</sup>g<sup>-ab</sup>=1<sup>a</sup>g<sup>-ab</sup>=g<sup>-ab</sup>=(g<sup>ab</sup>)<sup>-1</sup>.''

Việc giải mã bây giờ trở nên dễ dàng: Bob sử dụng ''(g<sup>ab</sup>)<sup>-1</sup>'' đã tính và phục hồi thông điệp nguyên thủy bằng cách tính: ''mg<sup>ab</sup>(g<sup>ab</sup>)<sup>-1</sup> = m(1) = m.''

==Chương trình C đơn giản==
<syntaxhighlight lang="c">
#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ả
}
</syntaxhighlight>

==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 '''<span style="color:red">s</span>''' = khóa bí mật được chia sẻ. '''<span style="color:red">s</span>''' = '''<span style="color:red">2</span>'''
* Đặt <span style="color:blue">g</span> = căn nguyên thủy công khai. <span style="color:blue">g</span> = <span style="color:blue">5</span>
* Đặt <span style="color:blue">p</span> = số nguyên tố công khai. <span style="color:blue">p</span> = <span style="color:blue">23</span>
* Đặt '''<span style="color:red">a</span>''' = khóa riêng tư của Alice. '''<span style="color:red">a</span>''' = '''<span style="color:red">6</span>'''
* Đặt <span style="color:blue">A</span> = khóa công khai của Alice. <span style="color:blue">A</span> = <span style="color:blue">g</span><sup>'''<span style="color:red">a</span>'''</sup> mod <span style="color:blue">p</span> = <span style="color:blue">8</span>
* Đặt '''<span style="color:red">b</span>''' = khóa riêng tư của Bob. '''<span style="color:red">b</span>''' = '''<span style="color:red">15</span>'''
* Đặt <span style="color:blue">B</span> = khóa công khai của Bob. <span style="color:blue">B</span> = <span style="color:blue">g</span><sup>'''<span style="color:red">b</span>'''</sup> mod <span style="color:blue">p</span> = <span style="color:blue">19</span>

{| border="0" cellspacing="0" cellpadding="2"
| valign="top" |
{| class="wikitable"
! colspan="2" | Alice
|-
| align="center" | biết 
| align="center" | không biết
|-
| <span style="color:blue">p</span> = <span style="color:blue">23</span>
| '''<span style="color:red">b</span>''' = '''<span style="color:red">?</span>'''
|-
| base <span style="color:blue">g</span> = <span style="color:blue">5</span>
|
|-
| '''<span style="color:red">a</span>''' = '''<span style="color:red">6</span>'''
| 
|-
| <span style="color:blue">A</span> = <span style="color:blue">5</span><sup>'''<span style="color:red">6</span>'''</sup> mod <span style="color:blue">23</span> = <span style="color:blue">8</span>
|
|-
| <span style="color:blue">B</span> = <span style="color:blue">5</span><sup>'''<span style="color:red">b</span>'''</sup> mod <span style="color:blue">23</span> = <span style="color:blue">19</span>
|
|-
| '''<span style="color:red">s</span>''' =  <span style="color:blue">19</span><sup>'''<span style="color:red">6</span>'''</sup> mod <span style="color:blue">23</span> = '''<span style="color:red">2</span>'''
|
|-
| '''<span style="color:red">s</span>''' = <span style="color:blue">8</span><sup>'''<span style="color:red">b</span>'''</sup> mod <span style="color:blue">23</span> = '''<span style="color:red">2</span>'''
|
|-
| '''<span style="color:red">s</span>''' = <span style="color:blue">19</span><sup>'''<span style="color:red">6</span>'''</sup> mod <span style="color:blue">23</span> = <span style="color:blue">8</span><sup>'''<span style="color:red">b</span>'''</sup> mod <span style="color:blue">23</span>
|
|-
| '''<span style="color:red">s</span>''' = '''<span style="color:red">2</span>'''
|
|}
| valign="top" | 
{| class="wikitable"
! colspan="2" | Bob
|-
| align="center" | biết 
| align="center" | không biết
|-
| <span style="color:blue">p</span> = <span style="color:blue">23</span>
| '''<span style="color:red">a</span>''' = '''<span style="color:red">?</span>'''
|-
| base <span style="color:blue">g</span> = <span style="color:blue">5</span>
|
|-
| '''<span style="color:red">b</span>''' = '''<span style="color:red">15</span>'''
| 
|-
| <span style="color:blue">B</span> = <span style="color:blue">5</span><sup>'''<span style="color:red">15</span>'''</sup> mod <span style="color:blue">23</span> = <span style="color:blue">19</span>
|
|-
| <span style="color:blue">A</span> = <span style="color:blue">5</span><sup>'''<span style="color:red">a</span>'''</sup> mod <span style="color:blue">23</span> = <span style="color:blue">8</span>
|
|-
| '''<span style="color:red">s</span>''' = <span style="color:blue">8</span><sup>'''<span style="color:red">15</span>'''</sup> mod <span style="color:blue">23</span> = '''<span style="color:red">2</span>'''
|
|-
| '''<span style="color:red">s</span>''' = <span style="color:blue">19</span><sup>'''<span style="color:red">a</span>'''</sup> mod <span style="color:blue">23</span> = '''<span style="color:red">2</span>'''
|
|-
| '''<span style="color:red">s</span>''' = <span style="color:blue">8</span><sup>'''<span style="color:red">15</span>'''</sup> mod <span style="color:blue">23</span> = <span style="color:blue">19</span><sup>'''<span style="color:red">a</span>'''</sup> mod <span style="color:blue">23</span>
|
|-
| '''<span style="color:red">s</span>''' = '''<span style="color:red">2</span>'''
|
|}
| valign="top" | 
{| class="wikitable"
! colspan="2" | Eve
|-
| align="center" | biết 
| align="center" | không biết
|-
| <span style="color:blue">p</span> = <span style="color:blue">23</span>
| '''<span style="color:red">a</span>''' = '''<span style="color:red">?</span>'''
|-
| base <span style="color:blue">g</span> = <span style="color:blue">5</span>
| '''<span style="color:red">b</span>''' = '''<span style="color:red">?</span>'''
|-
| 
| '''<span style="color:red">s</span>''' = '''<span style="color:red">?</span>'''
|-
| <span style="color:blue">A</span> = <span style="color:blue">5</span><sup>'''<span style="color:red">a</span>'''</sup> mod <span style="color:blue">23</span> = <span style="color:blue">8</span>
| 
|-
| <span style="color:blue">B</span> = <span style="color:blue">5</span><sup>'''<span style="color:red">b</span>'''</sup> mod <span style="color:blue">23</span> = <span style="color:blue">19</span>
|
|-
| '''<span style="color:red">s</span>''' = <span style="color:blue">19</span><sup>'''<span style="color:red">a</span>'''</sup> mod <span style="color:blue">23</span>
|
|-
| '''<span style="color:red">s</span>''' = <span style="color:blue">8</span><sup>'''<span style="color:red">b</span>'''</sup> mod <span style="color:blue">23</span>
|
|-
| '''<span style="color:red">s</span>''' = <span style="color:blue">19</span><sup>'''<span style="color:red">a</span>'''</sup> mod <span style="color:blue">23</span> = <span style="color:blue">8</span><sup>'''<span style="color:red">b</span>'''</sup> mod <span style="color:blue">23</span>
|
|}
|}

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ỏ) [http://buchananweb.co.uk/security02.aspx ở đây] {{Webarchive|url=https://web.archive.org/web/20110812224735/http://buchananweb.co.uk/security02.aspx |date=2011-08-12 }}

.

==== 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 <math>\log_2 (N) + 1</math> bằng cách sử dụng kiểu phương pháp [[Thuật toán chia để trị|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 <math>g^{abcd} \mod p</math>; giá trị này được gửi đến E, F, G, và H. Ngược lại A, B, C, và D nhận <math>g^{efgh}\mod p</math>.
# A và B mỗi người thực hiện một phép tính lũy thừa để tính <math>g^{efghab} \mod p</math>, rồi gửi cho C và D. Ngược lại C và D làm tương tự để tính <math>g^{efghcd} \mod p</math> và gửi cho A và B.
# A thực hiện một phép tính lũy thừa để tính <math>g^{efghcda} \mod p</math>, sau đó gửi cho B. Tương tự, B tính và gửi <math>g^{efghcdb} \mod p</math> 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 <math>g^{efghcdba} = g^{abcdefgh} \mod p</math>, trong khi đó B cũng tính tương tự để có <math>g^{efghcdab} \mod p = g^{abcdefgh} \mod p</math>. 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 <math>g^{abcd} \mod p</math> 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 <math>g^{abcdefgh} \mod p</math>, 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&ndash;Hellman]] để có thể tìm ra ''g''<sup>''ab''</sup>.  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ả [[lôgarit rời rạc|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&ndash;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 (lý thuyết nhóm)|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&ndash;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<sup>a</sup>'' 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&ndash;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&ndash;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ư [[Giao thức Station-to-Station|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&ndash;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&ndash;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à <math>(g^a \bmod{p}, g, p)</math>.  Để 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 <math>g^b \bmod p</math> (không mã hóa) cùng với thông điệp được mã hóa với khóa đối xứng <math>(g^a)^b \bmod{p}</math>.  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&ndash;Hellman không được sử dụng theo cách này vì thực ra [[RSA (mã hóa)|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à [[RSA (công ty bảo mật)|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&ndash;Hellman không thể dùng để ký chứng thực. Tuy nhiên, thuật toán [[mã hóa ElGamal|ElGamal]] và [[Giải thuật ký số|DSA]] có mối liên hệ toán học với chữ ký số, cũng như là [[MQV]], [[Giao thức Station-to-Station|STS]] và thành phần [[Trao đổi khóa Internet|IKE]] của bộ giao thức [[Ipsec|IPsec]] dùng để đảm bảo [[an toàn thông tin]] cho [[IP|giao thức Internet]].

==Xem thêm==
* [[Trao đổi khóa]]
* [[Đồng dư]]
* [[Elliptic curve Diffie&ndash;Hellman]]
* [[Mật mã hóa khóa công khai]]
* [[Mã hóa ElGamal]]
* [[Bài toán Diffie&ndash;Hellman]]
* [[MQV]]
* [[Trao đổi khóa bằng xác thực mật khẩu]]
* [[Giao thức SRP]]

== Chú thích ==
<references group="nb" />

==Tham khảo==
{{Tham khảo}}
* Dieter Gollmann (2006). ''Computer Security Second Edition'' West Sussex, England: [[Wiley (nhà xuất bản)|John Wiley & Sons]], Ltd.
* [http://cryptocellar.web.cern.ch/cryptocellar/cesg/possnse.pdf The possibility of Non-Secret digital encryption] {{Webarchive|url=https://web.archive.org/web/20141030210530/https://cryptocellar.web.cern.ch/cryptocellar/cesg/possnse.pdf |date=2014-10-30 }} J. H. Ellis, January 1970.
* [http://www.cesg.gov.uk/publications/Documents/secenc.pdf Non-Secret Encryption Using a Finite Field] {{Webarchive|url=https://web.archive.org/web/20120905025956/http://www.cesg.gov.uk/publications/Documents/secenc.pdf |date=2012-09-05 }} MJ Williamson, ngày 21 tháng 1 năm 1974.
* [http://www.fi.muni.cz/usr/matyas/lecture/paper3.pdf Thoughts on Cheaper Non-Secret Encryption] MJ Williamson, ngày 10 tháng 8 năm 1976.
* {{chú thích DOI|10.1109/TIT.1976.1055638}}
* {{US patent|4200770|Cryptographic apparatus and method}} 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
* [http://cryptocellar.web.cern.ch/cryptocellar/cesg/ellis.pdf The History of Non-Secret Encryption] {{Webarchive|url=https://web.archive.org/web/20141030210520/https://cryptocellar.web.cern.ch/cryptocellar/cesg/ellis.pdf |date=2014-10-30 }} [[James H. Ellis|JH Ellis]] 1987 (28K [[PDF]] file) ([http://www.jya.com/ellisdoc.htm HTML version] {{Webarchive|url=https://web.archive.org/web/20101127035626/http://jya.com/ellisdoc.htm |date=2010-11-27 }})
* [http://cr.yp.to/bib/1988/diffie.pdf The First Ten Years of Public-Key Cryptography] Whitfield Diffie, Proceedings of the IEEE, vol. 76, no. 5, May 1988, pp: 560&ndash;577 (1.9MB PDF file)
* [[Alfred Menezes|Menezes, Alfred]]; [[Paul van Oorschot|van Oorschot, Paul]]; [[Scott Vanstone|Vanstone, Scott]] (1997).  ''Handbook of Applied Cryptography'' Boca Raton, Florida: CRC Press. ISBN 0-8493-8523-7. ([http://www.cacr.math.uwaterloo.ca/hac/ Available online])
* [[Simon Singh|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
* [http://dx.doi.org/10.1109/MCOM.2002.1006971 An Overview of Public Key Cryptography] Martin E. Hellman, IEEE Communications Magazine, May 2002, pp:42&ndash;49. (123kB PDF file)

==Liên kết ngoài==
*[http://www.youtube.com/watch?v=3QnD2c4Xovk Diffie-Hellman key exchange explained in 5 minutes]
*[http://purl.umn.edu/107353 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 &ndash; ''Diffie&ndash;Hellman Key Agreement Method'' E. Rescorla June 1999.
* [http://csrc.nist.gov/encryption/kms/summary-x9-42.pdf ''Summary of ANSI X9.42: Agreement of Symmetric Keys Using Discrete Logarithm Cryptography'']{{Dead link|date=November 2009}} (64K PDF file) ([http://www.rsasecurity.com/rsalabs/node.asp?id=2306 Description of ANSI 9 Standards] {{Webarchive|url=https://web.archive.org/web/20040816210145/http://www.rsasecurity.com/rsalabs/node.asp?id=2306 |date=2004-08-16 }})
* [http://docs.google.com/viewer?a=v&pid=sites&srcid=bmV0aXAuY29tfGhvbWV8Z3g6NTA2NTM0YmNhZjRhZDYzZQ Diffie&ndash;Hellman Key Exchange – A Non-Mathematician’s Explanation] by Keith Palmgren
* [https://metacpan.org/module/Crypt::DH Crypt::DH] [[Perl]] module from [[CPAN]]
* [http://ds9a.nl/tmp/dh.html Hands-on Diffie&ndash;Hellman demonstration]
* [http://oldpiewiki.yoonkn.com/cgi-bin/moin.cgi/DiffieHellmanKeyExchange C implementation using GNU Multiple Precision Arithmetic Library] {{Webarchive|url=https://web.archive.org/web/20080627113318/http://oldpiewiki.yoonkn.com/cgi-bin/moin.cgi/DiffieHellmanKeyExchange |date=2008-06-27 }}
* [http://www.cypherspace.org/adam/rsa/perl-dh.html Diffie Hellman in 2 lines of Perl] (using [[dc (computer program)|dc]])
* [http://code.google.com/p/sacct/ Smart Account Management (SAcct)] (using DH key exchange to derive session key)
* [http://video.google.com/videoplay?docid=8991737124862867507 Talk by Martin Hellman in 2007, Google video] {{Webarchive|url=https://web.archive.org/web/20111215041349/http://video.google.com/videoplay?docid=8991737124862867507 |date=2011-12-15 }}

{{Mật mã học|Khóa công khai}}

{{DEFAULTSORT:Trao đổi khóa Diffie-Hellman}}
[[Thể loại:Giao thức thỏa thuận khóa]]