TRƯỜNG ĐẠI HỌC CÔNG NGHIỆP HÀ NỘI
KHOA CÔNG NGHỆ THÔNG TIN
Bài tập lớn
An toàn bảo mật thông tin
Đề tài
Giao thức thỏa thuận khóa Diffie - Hellman
Giáo viên hướng dẫn: Th.S Trần Phương Nhung
Nhóm sinh viên: 1. Phạm Thị Yến
2. Nguyễn Thị Nhâm
3. Nguyễn Đình Triệu
4. Lê Thanh Nghị
Hà Nội, Tháng 11/2012
Giao thức thỏa thuận khóa Diffie Hellman
Mục Lục
Phân công công việc
Stt Mã SV Tên SV Nội dung Trang-
trang
Nhận xét
1
0541060168 Nguyễn Thị Nhâm
Tìm hiểu về
giao thức thỏa
thuận khóa
Diffie -
Hellman + Ví
dụ bằng số
4 - 10
Tích cực
hoạt động,
và nghiên
cứu.Hoàn

thành tốt
nhiệm vụ
2
Nhóm 7 : ĐHKHMT2-K5
Giao thức thỏa thuận khóa Diffie Hellman
minh họa
2
0541060137 Lê Thanh Nghị
Viết chương
trình thực hiện
giao thức Diffie
- Hellman
Tích cực
nghiên cứu.
Hoàn thành
tốt nhiệm vụ
3
0541060129 Nguyễn Đình Triệu
Tìm hiểu các
đặc điểm đặc
trưng của giao
thức thỏa thuận
khóa Diffie -
Hellman
10 - 14
Tích cực
nghiên cứu.
Hoàn thàn
tốt nhiệm vụ
4

0541060165 Phạm Thị Yến
Tìm hiểu về
giao thức thỏa
thuận khóa
Diffie -
Hellman + Ví
dụ bằng số min
họa
4 - 10
Tích cực
nghiên cứu.
Hoàn thành
tốt nhiệm
vụ.
Lời mở đầu
Trao đổi thông tin luôn là nhu cầu cần thiết của con người, đặc biệt là trong cuộc
sống hiện đại ngày nay khi mà mạng máy tính và Internet phát triển một cách
mạnh mẽ và giữ vai trò quan trọng trong mọi lĩnh vực của đời sống xã hội như:
3
Nhóm 7 : ĐHKHMT2-K5
Giao thức thỏa thuận khóa Diffie Hellman
chính trị, quân sự, học tập, mua sắm, kinh doanh,… Tất cả những thông tin liên
quan đến những công việc này đều được máy vi tính quản lý và truyền đi trên hệ
thống mạng. Đối với những thông tin bình thường thì không ai chú đến, nhưng đối
với những thông tin mang tính chất sống còn đối với một cá nhân hay một tổ chức
thì vấn đề bảo mật thông tin là rất quan trọng và được đặt lên hàng đầu. Chính vì
vậy nên rất nhiều tổ chức, cá nhân đã nghiên cứu, tìm kiếm và đưa ra rất nhiều giải
pháp bảo mật thông tin. Trong đó giao thức Diffie - Hellman rất thích hợp trong
truyền thông tin giữ liệu và có tính bảo mật khá cao. Báo cáo này do nhóm biên
soạn dựa trên những kiến thức lĩnh hội được từ cô giáo Th.S. Trần Phương Nhung,

và thông qua sự tìm hiểu, nghiên cứu tích cực của các thành viên trong nhóm.Báo
cáo của nhóm đi sâu về đi sâu vào trình bày giao thức thỏa thuận khóa Diffie -
Hellman với nội dung 3 chương được chia thành các chủ đề khác nhau, từ việc giới
thiệu sơ bộ, trình bày khái niệm, cách thiết lập, sơ đồ và các ví dụ minh họa cụ thể
về giao thức thỏa thuận khóa. Mặc dù nhóm đã rất cố gắng song vẫn không tránh
khỏi một số thiếu sót mong thầy cô và bạn bè đóng góp ý kiến để nhóm hoàn thiện
hơn báo cáo này.
Xin chân thành cảm ơn tới bạn bè, người thân đã góp ý, giúp đỡ nhóm. Đặc biệt
cảm ơn cô giáo Th.S. Trần Phương Nhung người đã hướng dẫn nhóm hoàn thành
báo của mình!
Chương I: Giới thiệu về giao thức Diffie - Hellman
Năm 1976, một sự đột phá đã thay đổi nền tảng cơ bản trong cách làm việc
của các hệ thống mật mã hóa. Đó chính là việc công bố của bài viết phương hướng
mới trong mật mã học (New Directions in Cryptography) của Whitfield Diffie và
Martin Hellman. Bài viết giới thiệu một phương pháp hoàn toàn mới về cách thức
4
Nhóm 7 : ĐHKHMT2-K5
Giao thức thỏa thuận khóa Diffie Hellman
phân phối các khóa mật mã. Là hệ thống đầu tiên sử dụng "public-key" hoặc các
khóa mật mã "không đối xứng", và nó được gọi là trao đổi khóa Diffie-Hellman
(Diffie-Hellman key exchange). Bài viết còn kích thích sự phát triển gần như tức
thời của một lớp các thuật toán mật mã hóa mới, các thuật toán chìa khóa bất đối
xứng (asymmetric key algorithms).
Trao đổi khóa Diffie-Hellman bị cáo buộc rằng nó đã được phát minh ra một
cách độc lập một vài năm trước đó trong Trụ sở Truyền Thông Chính phủ Anh
(GCHQ) bởi Malcolm J. Williamson). Vào năm 2002, Hellman đã đưa ra thuật
toán được gọi chung là trao đổi khóa Diffie–Hellman–Merkle công nhận sự đóng
góp của cả Ralph Merkle, người đã phát minh ra thuật toán mã hóa công khai.
Trước thời kỳ này, hầu hết các thuật toán mật mã hóa hiện đại đều là những
thuật toán khóa đối xứng (symmetric key algorithms), trong đó cả người gửi và

người nhận phải dùng chung một khóa, tức khóa dùng trong thuật toán mật mã, và
cả hai người đều phải giữ bí mật về khóa này. Tất cả các máy điện cơ dùng trong
thế chiến II, kể cả mã Caesar và mã Atbash, và về bản chất mà nói, kể cả hầu hết
các hệ thống mã được dùng trong suốt quá trình lịch sử nữa đều thuộc về loại này.
Đương nhiên, khóa của một mã chính là sách mã (codebook), và là cái cũng phải
được phân phối và giữ gìn một cách bí mật tương tự.
Do nhu cầu an ninh, khóa cho mỗi một hệ thống như vậy nhất thiết phải
được trao đổi giữa các bên giao thông liên lạc bằng một phương thức an toàn nào
đấy, trước khi họ sử dụng hệ thống (thuật ngữ thường được dùng là 'thông qua một
kênh an toàn'), ví dụ như bằng việc sử dụng một người đưa thư đáng tin cậy với
một cặp tài liệu được khóa vào cổ tay bằng một cặp khóa tay, hoặc bằng cuộc gặp
gỡ mặt đối mặt, hay bằng một con chim bồ câu đưa thư trung thành Vấn đề này
chưa bao giờ được xem là dễ thực hiện, và nó nhanh chóng trở nên một việc gần
như không thể quản lý được khi số lượng người tham gia tăng lên, hay khi người ta
không còn các kênh an toàn để trao đổi khóa nữa, hoặc lúc họ phải liên tục thay đổi
các chìa khóa-một thói quen nên thực hiện trong khi làm việc với mật mã. Cụ thể
là mỗi một cặp truyền thông cần phải có một khóa riêng nếu, theo như thiết kế của
hệ thống mật mã, không một người thứ ba nào, kể cả khi người ấy là một người
dùng, được phép giải mã các thông điệp. Một hệ thống thuộc loại này được gọi là
một hệ thống dùng chìa khóa mật, hoặc một hệ thống mật mã hóa dùng khóa đối
xứng. Hệ thống trao đổi khóa Diffie-Hellman (cùng những phiên bản được nâng
cấp kế tiếp hay các biến thể của nó) tạo điều kiện cho các hoạt động này trong các
hệ thống trở nên dễ dàng hơn rất nhiều, đồng thời cũng an toàn hơn, hơn tất cả
những gì có thể làm trước đây.
5
Nhóm 7 : ĐHKHMT2-K5
Giao thức thỏa thuận khóa Diffie Hellman
Mặc dù, bản thân thuật toán là một giao thức chọn khóa nặc danh (không cần thông
qua xác thực) nhưng nó đã cung cấp ra một cơ sở cho các giao thức xác thực khác
nhau khá hoàn hảo.

Phương thức tiếp nối ngay sau Diffie – Hellman là RSA, một thể hiện của mã khóa
công khai sử dụng thuật toán bất đối xứng.
Chương II: Giao thức thỏa thuận khóa Diffie - Hellman
1. Khái niệm thỏa thuận khóa.
Thoả thuận khoá: việc trao đổi khoá giữa các chủ thể trong một cộng đồng nào đó
có thể được thiết lập một cách tự do giữa bất cứ hai người nào khi có nhu cầu trao
đổi thông tin.
2. Giao thức thỏa thuận khóa Diffie - Hellman.
6
Nhóm 7 : ĐHKHMT2-K5
Giao thức thỏa thuận khóa Diffie Hellman
- Trao đổi khóa Diffie – Hellman là thiết lập một khóa chia sẻ bí mật được sử dụng
cho thông tin liên lạc bí mật bằng cách trao đổi dữ liệu thông qua mạng công cộng.
Đây mà một trong số nhiều phương thức dùng để trao đổi khóa trong ngành mật
mã học.
- Phương pháp này không cần có sự can thiệp của một TA ( cơ quan ủy thác) làm
nhiệm vụ điều hành hoặc phân phối khóa.
- Phương pháp này cho phép những người sử dụng có thể cùng nhau tạo ra một khóa
bí mật thông qua một kênh truyền thông không đảm bảo về độ bảo mật. Khóa bí
mật này sẽ được dùng để người sử dụng trao đổi thông tin với nhau.
2.1. Cách thiết lập giao thức thỏa thuận khóa Diffie - Hellman.
• Tình huống:
+ Alice và Bob muốn chia sẻ thông tin bảo mật cho nhau nhưng phương tiện truyền
thông duy nhất của họ là không an toàn. Tất cả các thông tin mà họ trao đổi được
quan sát bởi Eve kẻ thù của họ.
+ Làm thế nào để Alice và Bob chia sẻ thông tin bảo mật cho nhau mà không làm
cho Eve biết được?
+ Thoạt nhìn ta thấy Alice và Bob phải đối mặt với một nhiệm vụ không thể.
• Giải quyết tình huống trên:
+ Alice và Bob đồng ý dùng chung về một nhóm cyclic hữu hạn G và một yếu

tố tạo ra g trong G. (Điều này thường được thực hiện rất lâu trước khi phần còn lại
của giao thức, g được giả định là được biết đến bởi tất cả các kẻ tấn công)
+ Khi Alice và Bob muốn truyền thông tin bảo mật cho nhau có thể cùng thực hiện
theo giao thức sau để trao đổi:
1. Alice chọn ngẫu nhiên số a
A
(0 ≤ a
A
≤ p-2) bí mật, tính
pgb
A
a
A
mod
=
và gửi b
A
cho Bob .
2. Tương tự, Bob chọn ngẫu nhiên số a
B
(0 ≤ a
B
≤ p-2) bí mật, tính

pgb
B
a
B
mod
=

và gửi b
B
cho Alice.
3. Alice tính được khóa:
pbK
A
a
BA
mod
=
4. Bob tính được khóa:
pbK
B
a
AB
mod
=
+ Bây giờ Alice và Bob có cùng khóa chung là:

pgKK
BA
aa
BA
mod
==
+ Mô tả giao thức Diffie - Hellman bằng bảng sau:
Alice Bob
Bí mật
Công khai Tính toán Gửi Tính toán Công khai Bí mật
7

Nhóm 7 : ĐHKHMT2-K5
Giao thức thỏa thuận khóa Diffie Hellman
a
A
p, g → a
B
a
A
p, g, b
A
pgb
A
a
A
mod
=
b
A
→ p, g a
B
a
A
←b
B
pgb
B
a
B
mod
=

p, g, b
B
a
B
a
A,
K
A
p, g, b
A,
b
B
p, g, b
A,
b
B
a
B,
K
B
• Chú ý là chỉ có a
A,
a
B
và K
A,
K
B
là được giữ bí mật. Tất cả các giá trị còn lại như p,
g, b

A
, b
B
đều công khai. Một khi Alice và Bob tính được khóa bí mật dùng chung,
họ có thể dùng nó làm khóa mã hóa chỉ họ biết để gửi các thông điệp qua cùng
kênh giao tiếp mở. Đương nhiên, để đảm bảo an toàn, các giá trị a
A
, a
B
và p cần
được lấy lớn hơn, g không cần lấy giá trị quá lớn. Thực tế thì g thường lấy giá trị 2
hoặc 5
2.2. Sơ đồ giao thức thỏa thuận khóa Diffie - Hellman.
Sơ đồ dưới đây minh họa phần nào ý tưởng chung.
Đầu tiên, Alice và Bob đã thống nhất về màu sơn chung (màu vàng), Alice và Bob
trao đổi màu sắc đã được trộn của họ. Cuối cùng, điều này tạo ra một màu bí mật
giống hệt nhau mà kẻ khác không có khả năng tạo được ra giống vậy. Kể từ đây,
Alice và Bob sẽ trao đổi bằng cách mã hóa và giải mã sử dụng khóa bí mật đó (thể
hiện bằng màu sơn bí mật cuối cùng).
8
Nhóm 7 : ĐHKHMT2-K5
Giao thức thỏa thuận khóa Diffie Hellman
Hình 1: Sơ đồ giao thức thỏa thuận khóa Diffie - Hellman
2.3. Ví dụ bằng số minh họa.
1. Alice và Bob thống nhất với nhau chọn số nguyên tố p = 37 và g = 5.
2. Alice chọn một giá trị ngẫu nhiên bất kỳ a
A
= 7 và bí mật a
A.


Alice tính b
A
= 5
7
mod 37 = 18.
Sau đó Alice gửi b
A
= 18 cho Bob.
Bob chọn một giá trị ngẫu nhiên bất kỳ a
B
= 5 và bí mật a
B
Bob tính b
B
= 5
5
mod 37 = 17.
Sau đó Bob gửi b
B
= 17 cho Alice.
4. Bob nhận được b
A
= 18 và tính khóa chung: K
B
= 18
4
mod 37=15, và bí mật K
B

5. Alice nhận được b

B
=17 và tính khóa chung: K
A
= 17
7
mod 37=15, và bí mật K
A
9
Nhóm 7 : ĐHKHMT2-K5
Giao thức thỏa thuận khóa Diffie Hellman
2.4. Mở rộng bài toán cho nhiều bên
Thỏa thuận khóa Diffie-Hellman không chỉ giới hạn để thương lượng một khóa
dùng chung giữa hai bên. Bất cứ một số lượng người dùng nào cũng có thể tham
gia vào một thỏa thuận như thế bằng cách lặp các giao thức thỏa thuận và trao đổi
dữ liệu trung gian. Ví dụ, Alice, Bob và Carol có thể tham gia vào một thỏa thuận
Diffie-Hellman như sau (với tất cả phép toán đều lấy mod p):
1. Các bên đồng ý với các tham số của giải thuật là p và g.
2. Các bên tự sinh khóa bí mật, đặt tên là a
A
, a
B
và a
c
.
3. Alice tính
A
a
g
và gửi nó cho Bob.
4. Bob tính

BA
aa
g )(
=
BA
aa
g
và gửi nó cho Carol.
5. Carol tính
CBA
a
aa
g )(
=
CBA
aaa
g
và dùng nó làm khóa bí mật.
6. Bob tính
B
a
g
và gửi nó cho Carol.
7. Carol tính
C
B
a
a
g )(
=

CB
aa
g
và gửi nó cho Alice.
8. Alice tính
A
CB
a
aa
g )(
=
ACB
aaa
g
=
CBA
aaa
g
và dùng nó làm khóa bí mật.
9. Carol tính
C
a
g
và gửi nó cho Alice.
10. Alice tính
A
C
a
a
g )(

=
CA
aa
g
và gửi nó cho Bob.
11. Bob tính
BAC
aaa
g
=
BAC
aaa
g
=
CBA
aaa
g
và dùng nó làm khóa bí mật.
Một kẻ nghe trộm có thể biết
A
a
g
,
B
a
g
,
C
a
g

,
BA
aa
g
,
CB
aa
g
,
AC
aa
g
nhưng không thể nào
kết hợp chúng để sinh lại
CBA
aaa
g
. Để mở rộng cơ chế này cho các nhóm lớn hơn cần
phải tuân thủ 2 nguyên tắc cơ bản sau:
• Bắt đầu với một khóa “rỗng” chỉ gồm có g, khóa bí mật được tạo ra bằng cách
tăng giá trị hiện tại theo số mũ bí mật của những bên tham gia một lần, theo thứ tự
bất kỳ.
• Bất kỳ giá trị trung gian nào (số mũ sẽ lên tới tích N-1 số mũ, trong đó N là số
bên tham gia vào nhóm) đều có thể bị công khai, nhưng giá trị cuối cùng (khi cả N
số mũ đều được dùng) sẽ tạo thành khóa bí mật dùng chung và do đó phải tránh bị
công khai. Vì vậy, mỗi người dùng cần thu về bản sao của khóa mật bằng cách sử
dụng khóa mật của chính họ lúc cuối cùng (mặt khác, không có cách nào để bên
tham gia cuối cùng trao khóa cuối cho bên nhận của nó, vì bên này phải giữ bí mật
khóa)
10

Nhóm 7 : ĐHKHMT2-K5
Giao thức thỏa thuận khóa Diffie Hellman
Những nguyên tắc này mở ra rất nhiều tùy chọn để sắp xếp các bên tham gia đóng
góp tạo khóa. Phương pháp đơn giản và rõ ràng nhất là sắp N bên tham gia vào
một vòng tròn và có N khóa quay quanh vòng tròn này, cho tới khi mỗi khóa đều
đã được N bên đóng góp xây dựng (kết thúc với chính bên sở hữu nó) và mỗi bên
tham gia đều đã đóng góp vào N khóa (kết thúc với khóa của họ). Tuy nhiên, điều
này yêu cầu mỗi bên phải tính N số mũ thành phần.
Bằng cách chọn một thứ tự tối ưu hơn, phụ thuộc vào thực tế là các khóa có thể
trùng lặp, chúng ta có thể giảm khối lượng tính toán số mũ của mỗi bên là log
2
(N)
+ 1 sử dụng phương pháp Chia để trị, được đề xuất sau đây đối với 8 bên:
1. Các bên A, B, C và D mỗi bên thực hiện tính toán
DCBA
aaaa
g
, giá trị này được
gửi cho E, F, G, H. Ngược lại, họ cũng nhận được
HGFE
aaaa
g
.
2. Các bên A và B mỗi bên tính
BAHGFE
aaaaaa
g
, gửi cho C và D, khi đó C và D
cũng làm việc tương tự là gửi
DCHGFE

aaaaaa
g
cho A và B.
3. Bên A tính toán
ADCHGFE
aaaaaaa
g
và gửi cho B, tương tự, B gửi lại
BCDHGFE
aaaaaaa
g

cho A. C và D cũng làm việc tương tự.
4. Bên A tính số mũ cuối thu được
ABDCHGFE
aaaaaaaa
g
=
HGFEDCBA
aaaaaaaa
g
, trong khi B
làm điều tương tự để nhận được
BADCHGFE
aaaaaaaa
g
=
HGFEDCBA
aaaaaaaa
g

. C và D cũng
làm điều tương tự.
5. Các bên từ E qua H đồng thời thực hiện tính toán sử dụng gabcd làm điểm
khởi đầu.
Sau khi hoàn thành thuật toán, tất cả các bên tham gia đều đã sở hữu khóa mật
HGFEDCBA
aaaaaaaa
g
, nhưng mỗi bên chỉ phải tính toán 4 lần số mũ thành phần, thay vì
phải tính 8 lần như trong sắp xếp vòng tròn đơn giản.
2.5. Các đặc điểm đặc trưng của giao thức thảo thuận khóa Diffie - Hellman.
2.5.1. Giao thức là an toàn đối với việc tấn công thụ động.
• Giao thức là an toàn đối với việc tấn công thụ động, nghĩa là một người thứ ba dù
biết b
A
và b
B
sẽ khó mà biết được K
A,B
.
• Xét ví dụ:
1. Alice và Bob thống nhất với nhau chọn số nguyên tố p = 17 và g = 2.
2. Alice chọn một giá trị ngẫu nhiên bất kỳ a
A
= 6 và bí mật a
A
.
Alice tính b
A
= 2

6
mod 17 = 13.
Sau đó Alice gửi b
A
= 13 cho Bob.
3. Bob chọn một giá trị ngẫu nhiên bất kỳ a
B
= 9 và bí mật a
B

Bob tính b
B
= 2
9
mod 17 = 2.
Sau đó Bob gửi b
B
= 2 cho Alice.
4. Bob nhận được b
A
= 13 và tính khóa chung: K
B
= 13
9
mod 17=13, và bí mật K
B
11
Nhóm 7 : ĐHKHMT2-K5
Giao thức thỏa thuận khóa Diffie Hellman
5. Alice nhận được b

B
= 2 và tính khóa chung: K
A
= 2
6
mod 17=13, và bí mật K
A
Eve là một kẻ nghe trộm – cô ta theo dõi những gì Alice và Bob gửi cho nhau
nhưng không thể thay đổi nội dung các cuộc liên lạc.
Eve muốn tái thiết lại những thông tin bảo mật mà Alice và Bob chia sẻ cho nhau.
 Eve sẽ phải đối mặt với một nhiệm vụ thực sự khó khăn.
 Dưới đây là các biểu đồ giúp xác định ai biết được giá trị nào. (Eve là một kẻ nghe
trộm.)
Alice
Biết
Không biết
p = 17
a
B
= ?
g = 5
a
A
= 6
b
A
= 2
6
mod 17 = 13
217mod2

==
B
a
B
b
K
A
= 2
6
mod 17=13
1317mod13
==
B
a
B
K
17mod1317mod2
6
,
B
a
BA
K ==
K
A,B
= 13
Bob
Biết
Không biết
p = 17

a
A
=?
g = 2
a
B
= 9
b
B
= 2
9
mod 17 = 2
1317mod2
==
A
a
A
b
K
B
= 13
9
mod 17=13
1317mod2
==
A
a
A
K
12

Nhóm 7 : ĐHKHMT2-K5
Giao thức thỏa thuận khóa Diffie Hellman
17mod1317mod2
9
,
==
A
a
BA
K
K
A,B
= 13
Eve
Biết
Không biết
p = 17
a
A
= ?
g = 2
a
B
=?
1317mod2
==
A
a
A
b

K
A,B
= ?
217mod2
==
B
a
B
b
17mod2
A
a
A
K
=
17mod13
B
a
B
K
=
17mod1317mod2
,
BA
aa
BA
K ==
13
Nhóm 7 : ĐHKHMT2-K5
Giao thức thỏa thuận khóa Diffie Hellman

• Ta thấy Eve rơi vào tình thế tiến thoái lưỡng nam. Cô ấy biết được giá trị của b
A
, b
B
vì vậy cô ấy biết được
A
a
g
,
B
a
g
. Cô ấy cũng biết những giá trị của g và p, nhưng lại
không biết được các giá trị của a
A,
a
B
và K
A, B
 Đây chính là bài toán Diffie - Hellman mà khi biết b
A,
b
B
tìm K
A,B,
bài toán này
tương đương với bài toán phá mã ElGammal. Bây giờ ta đi chứng minh điều này.
- Phép mật mã ElGammal với khoá K = (p, g, a, β), trong đó β = g
a
mod p cho ta từ

một bản rõ x và một số ngẫu nhiên k ∈ Z
p-1
lập được mật mã e
K
(x, k) = (y
1
, y
2
) với
y
1
= g
k
mod p, y
2
= xβ
k
mod p . Và phép giải mã được cho bởi y
1
= g
k
mod p. Giả sử
ta có thuật toán A giải bài toán Diffie-Hellman. Ta sẽ dùng A để phá mã
ElGammal như sau:
• Cho mật mã (y
1
, y
2
). Trước tiên, dung A cho y
1

= g
k
mod p và β=g
a
mod p ta
được A(y
1
,B) = g
ka
=β
k
mod p . Sau đó, ta thu được bản rõ x từ β
k
và y
2
như
sau:
x = y
2
(β
k
)
-1
mod p.
• Ngược lại, giả sử có một thuật toán khác là B dùng để phá mã ElGammal,
tức là B (p, g, β, y
1
, y
2
) = x = y

2
(y
1
a
)
-1
mod p . Áp dụng B cho β=b
A
,
y
1
= b
B
, y
2
=1, ta được
pbbbpB
BAA
aaa
BBA
mod)).(1()1,,,,(
111
αα
==
−−−
tức giải
được bài toán Diffie-Hellman.
• Trên thực tế các giá trị của p, a
A,
a

B
là rất lớn. Nếu p là số nguyên tố có ít nhất 300
chữ số, a
A
và a
B
có ít nhất 100 chữ số thì thậm chí ngay cả thuật toán tốt nhất được
biết đến hiện nay cũng không thể giải được nếu chỉ biết g, p, b
A
, b
B
kể cả khi sử
dụng tất cả khả năng tính toán của nhân loại. Bài toán này còn được biết đến với
tên gọi bài toán logarit rời rạc. Bài toán logarit rời rạc vẫn còn đang gây rất nhiều
tranh cãi và chưa có thuật giải cụ thể nào.
2.5.2. Giao thức là không an toàn đối với việc tấn công chủ động.
• Giao thức là không an toàn đối với việc tấn công chủ động bằng cách đánh tráo
giữa đường. Nghĩa là một người thứ ba Eve có thể đánh tráo các thông tin trao đổi
giữa Alice và Bob.
• Chẳng hạn, Eve thay
A
a
g
mà Alice định gửi cho Bob bởi
A
a
g
'
và thay
B

a
g
mà Bob
định gửi cho Alice bởi
B
a
g
'
. Như vậy, sau khi thực hiện giao thức trao đổi khoá,
Alice đã lập một khoá chung
BA
aa
g
'
với Eve mà vẫn tưởng là với Bob; đồng thời Bob
14
Nhóm 7 : ĐHKHMT2-K5
Giao thức thỏa thuận khóa Diffie Hellman
cũng lập một khoá chung
BA
aa
g
'
với Eve mà vẫn tưởng là với Alice. Eve có thể giải
mã mọi thông báo mà Alice tưởng nhầm là mình gửi đến Bob cũng như mọi thông
báo mà Bob tưởng nhầm là mình gửi đến Alice.
• Một cách khắc phục kiểu tấn công này là làm sao để Alice và Bob có kiểm thử để
xác nhận tính đúng đắn của các khoá công khai b
A
và b

B
. Người ta đưa vào giao
thức trao đổi khoá Diffie-Hellman thêm vai trò điều phối của một TA để được một
hệ phân phối khoá Diffie-Hellman như một cách khắc phục nhược điểm này. Trong
hệ phân phối khoá Diffie-Hellman, sự can thiệp của TA là rất yếu, thực ra TA chỉ
làm mỗi việc là cấp chứng chỉ xác nhận khoá công khai cho từng người dùng chứ
không đòi hỏi biết thêm bất cứ một bí mật nào của người dùng. Tuy nhiên, nếu
chưa thoả mãn với vai trò hạn chế đó của TA thì có thể cho TA một vai trò xác
nhận yếu hơn, không liên quan gì đến khoá, chẳng hạn như xác nhận thuật toán
kiểm thử chữ ký của người dùng, còn bản thân các thông tin về khoá (cả bí mật
lẫn công khai) thì do các người dùng trao đổi trực tiếp với nhau. Với cách khắc
phục có vai trò hết sức hạn chế đó của TA, ta được giao thức sau đây:
2.6. Giao thức thỏa thuận khóa Diffie - Hellman có chứng chỉ xác nhận.
• Mỗi người dùng A có một danh tính ID(A) và một sơ đồ chữ ký với thuật toán ký
sig
A
và thuật toán kiểm thử ver
A
. TA cũng có một vai trò xác nhận, nhưng không
phải xác nhận bất kỳ thông tin nào liên quan đến việc tạo khoá mật mã của người
dùng (dù là khoá bí mật hay khoá công khai), mà chỉ là xác nhận một thông tin ít
quan hệ khác như thuật toán kiểm thử chữ ký của người dùng. Còn bản thân các
thông tin liên quan đến việc tạo khoá mật mã thì các người dùng sẽ trao đổi trực
tiếp với nhau. TA cũng có một sơ đồ chữ ký của mình, gồm một thuật toán ký sig
TA
và một thuật toán kiểm thử công khai ver
TA
. Chứng chỉ mà TA cấp cho mỗi người
A sẽ là:
C(A) = (ID(A), ver

A
, sig
TA
(ID(A), ver
A
)).
Rõ ràng trong chứng chỉ đó TA không xác nhận bất kỳ điều gì liên quan đến việc
tạo khoá của A cả.
• Cơ chế giao thức thỏa thuận khóa Diffie - Hellman có chứng chỉ xác nhận
Việc trao đổi khoá giữa hai người dùng A và B được thực hiện theo giao thức sau
đây:
1. A chọn ngẫu nhiên số a
A
(0 ≤ a
A
(≤ p-2), tính
pgb
A
a
A
mod
=
và gửi b
A
cho B.
15
Nhóm 7 : ĐHKHMT2-K5
Giao thức thỏa thuận khóa Diffie Hellman
2. B chọn ngẫu nhiên số a
B

(0 ≤ a
B
≤ p-2), tính
pgb
B
a
B
mod
=
, tính tiếp
pbK
B
a
A
mod
=
,
),(
BABB
bbsigy
=
và gửi (C(Alice), b
B
, y
B
) cho A.
3. A tính
pbK
A
a

B
mod
=
dùng ver
B
để kiểm thử y
B
, dùng ver
TA
để kiểm thử C(B),
sau đó tính y
A
= sigA(b
A
, b
B
) và gửi (C(A), y
A
) cho B.
4. B dùng ver
A
để kiểm thử y
A
và dùng ver
TA
để kiểm thử C(A).
Nếu tất cả các bước đó được thực hiện và các phép kiểm thử đều cho kết quả đúng
đắn thì giao thức được kết thúc, và cả A và B đều có được khoá chung K. Do việc
dùng các thuật toán kiểm thử nên A biết chắc giá trị b
B

là của B và B biết chắc giá
trị b
A
của A, loại trừ khả năng một người C nào khác đánh tráo các giá trị đó giữa
đường.
16
Nhóm 7 : ĐHKHMT2-K5
Giao thức thỏa thuận khóa Diffie Hellman
Tài liệu tham khảo
1. Giáo trình an toàn và bảo mật thông tin – Trường ĐH Hàng Hải
2. Giáo trình an toàn bảo mật thông tin – Trường ĐH Giao Thông Vân Tải
3. Whitfield Diffie, Martin E. Hellman, “ New Directions in Cryptography”, IEEE
transactions on information theory, Vol. IT-22, No.6, November 1976.
4. A Review of the Diffie-Hellman Algorithm and its Use in Secure Internet Protocols
- David A. Carts
5. Diffie-Hellman Key Exchange – A Non-Mathematician’s Explanation
/>exchange-a-non-mathematicians-explanation
6. Discrete Logarithms and Diffie - Hellman.
7.
8.
9.
10. />11. />12.
%A7y_modulo_n
13. />primitive-root- modulo-p-in-the-diffie-hellman?rq=1
14. Cryptography in C and C++ - Michael Welschenbach 2
nd
Edition (2005)
15. Primitive Roots - David Savtt
16. The Primitive Root Theorem - Philadelphia University
17. New Directions in Cryptography - Invited Paper - Whitfield Diffie and Martin E.

Hellman
18. A Review of the Diffie-Hellman Algorithm and its Use in Secure Internet
Protocols - David A. Carts
19. Video:
Public Key Cryptography- Diffie-Hellman Key Exchange
Primitive Root Calculator
20. Và một số tài liệu và các trang web khác.
17
Nhóm 7 : ĐHKHMT2-K5