Phát triển giao thức trao đổi khóa an toàn dựa trên hai bài toán khó

Công nghệ thông tin 
Đ. V. Bình, N. H. Minh, “Phát triển giao thức trao đổi khóa  dựa trên hai bài toán khó.” 156 
PHÁT TRIỂN GIAO THỨC TRAO ĐỔI KHÓA AN TOÀN 
DỰA TRÊN HAI BÀI TOÁN KHÓ 
Đỗ Việt Bình1*, Nguyễn Hiếu Minh2 
Trong các nghiên cứu trước đây, chúng tôi đã công bố giải pháp kết hợp chữ ký 
số và giao thức trao đổi khóa để nâng cao khả năng bảo mật và đạt được những tính 
chất cần thiết của giao thức trao đổi khóa an toàn. Trong bài báo này, chúng tôi đề 
xuất một biến thể của lược đồ chữ ký số trước đây và xây dựng giao thức trao đổi 
khóa mới dựa trên biến thể này. 
Từ khóa: Xác thực; Bài toán khó; Trao đổi khóa; giao thức; Chữ ký số. 
1. TỔNG QUAN 
Giao thức trao đổi khóa Diffie-Hellman (DH) không cung cấp khả năng xác 
thực giữa các bên tham gia [3]. Do đó, nhiều giao thức đã được đưa ra nhằm khắc 
phục nhược điểm này [1] [2] [5] [8]. Tuy nhiên các lược đồ này vẫn còn tồn tại 
những hạn chế và chỉ dựa trên một bài toán khó [5-7]. 
Trong công bố trước đây [4], chúng tôi đã đề xuất việc kết hợp hai lược đồ chữ 
ký số RSA và Schnorr, đồng thời xây dựng giao thức trao đổi khóa an toàn DH–
MM–KE1 dựa trên lược đồ mới đề xuất này nhằm nâng cao khả năng bảo mật. Để 
nâng cao khả năng bảo mật, chúng tôi đề xuất một biến thể mới của lược đồ RSA–
Schnorr, đồng thời xây dựng các giao thức trao đổi khóa an toàn dựa trên giao thức 
mới này. 
Trong bài báo này, phần 2 phân tích lược đồ chữ ký số RSA–Schnorr trong 
công bố trước, đề xuất lược đồ cải tiến khắc phục nhược điểm của lược đồ này. 
Trên cơ sở đó, phần 3 đề xuất giao thức trao đổi khóa an toàn dựa trên hai bài toán 
khó (DH–MM–KE1) và trình bày khả năng bảo mật của giao thức này. Phần 4 tóm 
tắt các kết quả của bài báo. 
2. LƯỢC ĐỒ CHỮ KÝ SỐ RSA–SCHNORR 
Ở bài báo [4], chúng tôi đã đề xuất lược đồ chữ ký dựa trên hai bài toán khó dựa 
trên việc kết hợp hai lược đồ chữ ký số RSA và Schnorr. Lược đồ này sử dụng hai 
số nguyên tố mạnh , ’ và một số nguyên tố  = 2 + 1 với  = ’. Lược đồ 
được thực hiện như Bảng 1: 
Bảng 1. Lược đồ chữ ký số RSA-Schnorr. 
Tạo 
khóa 
- Tính f() = ( − 1)( − 1). 
- Chọn  ∈ 
∗ sao cho  là phần tử có cấp bằng  trong 
∗ thỏa 
mãn  ≡ 1		. 
Nghiên cứu khoa học công nghệ 
Tạp chí Nghiên cứu KH&CN quân sự, Số Đặc san CNTT, 11 - 2018 157
- Chọn số bí mật  ∈ 
∗ ,  ∈ [1,  − 1] và tính  = 
		. 
- Chọn số nguyên  ∈  thỏa mãn: , f() = 1. 
- Tính  sao cho:  ∗  = 1		f(). 
- Khóa công khai là (, , ), khóa bí mật là (, ). 
Ký - Chọn ngẫu nhiên số  bí mật với 1 <  < . 
- Tính  = 		. 
- Tính  = (||). 
- Tính  = ( − )		. 
- Chữ ký là (, ). 
Xác 
thực 
- Tính ∗ = 		. 
- Tính ∗ = 
∗
		. 
- Tính ∗ = (||∗). 
- Nếu  = ∗ chữ ký hợp lệ. 
- Ngược lại nếu  ≠ ∗ chữ ký không hợp lệ. 
Trong bài báo này, chúng tôi đề xuất một biến thể của lược đồ trên nhằm nâng 
cao khả năng bảo mật. Lược đồ này được mô tả như trong Bảng 2: 
Bảng 2. Biến thể lược đồ chữ ký số RSA-Schnorr. 
Tạo 
khóa 
- Chọn hai số nguyên tố mạnh  và ’. 
- Tính  = ’ và  = 2 + 1 thỏa mãn  là số nguyên tố. 
- Tính f() = ( − 1)( − 1). 
- Chọn ,  ∈ 
∗ sao cho ,  là các phần tử có cấp bằng  trong 
∗ 
thỏa mãn 
 ≡ 1		 và 
 ≡ 1		. 
- Chọn hai số bí mật ,  ∈ 
∗ với ,  ∈ [1,  − 1]. 
- Tính  = 

		. 
- Chọn số nguyên  ∈  thỏa mãn: , f() = 1. 
- Tính  sao cho:  ∗  = 1		f(). 
- Khóa công khai là (, , ), khóa bí mật là (, , ). 
Ký - Chọn ngẫu nhiên hai số ,  bí mật với 1 < ,  < . 
- Tính  = 

		. 
Công nghệ thông tin 
Đ. V. Bình, N. H. Minh, “Phát triển giao thức trao đổi khóa  dựa trên hai bài toán khó.” 158 
- Tính  = (||). 
- Tính  = ( − )
		. 
- Tính  = ( − )
		. 
- Chữ ký là (, , ). 
Xác 
thực 
- Tính 
∗ = 
		. 
- Tính 
∗ = 
		. 
- Tính ∗ = 

∗


∗
		. 
- Tính ∗ = (||∗). 
- Nếu  = ∗ chữ ký hợp lệ. 
- Ngược lại nếu  ≠ ∗ chữ ký không hợp lệ. 
Tính đúng đắn của giao thức: 
Ta có: ∗ = 

∗


∗
		 = 

∗


∗


		 = 
= 



 = 

 =  
=> ∗ = (||∗) = (||) = . 
Với việc sử dụng hai phần tử , , khóa bí mật (, , ) và hai thành phần ngẫu 
nhiên (, ), người tấn công không thể tìm được các thành phần bí mật bằng việc 
giải bài toán logarithm rời rạc. 
3. GIAO THỨC DH–MM–KE1 
3.1. Mô tả giao thức 
Dựa trên biến thể của lược đồ chữ ký số RSA–Schnorr, chúng tôi đề xuất giao 
thức trao đổi khóa an toàn dựa trên hai bài toán khó DH–MM–KE1. Giao thức này 
hoạt động như sau: 
1) Chọn tham số: 
Các tham số của hai bên A và B được tính như biến thể lược đồ RSA–Schnorr 
trình bày trong phần 2. 
Với người gửi A:  = 2 + 1, trong đó  = 
 , 
 và  là các số 
nguyên tố mạnh với kích thước ít nhất là 1024 bit. Các tham số khóa của người A: 
Khóa công khai (, ) và khóa bí mật (, ). 
Với người nhận B:  = 2 + 1, trong đó  = 
 , 
 và  là các số 
nguyên tố mạnh với kích thước ít nhất là 1024 bit. Các tham số khóa của người B: 
Khóa công khai (, ) và khóa bí mật (, ). 
Ký hiệu {} = {0, 1,  ,  − 1} và {} = {0, 1,  ,  − 1}. 
Nghiên cứu khoa học công nghệ 
Tạp chí Nghiên cứu KH&CN quân sự, Số Đặc san CNTT, 11 - 2018 159
Tìm tập  =  ∩ . Tính  = (, ). 
Tìm ,  là phần tử có cấp bằng  trong 
∗ và có cấp bằng  trong 
∗ thỏa 
mãn 
 ≡ 1		; 
 ≡ 1		 và 
 ≡ 1		; 
 ≡ 1		. 
A tính  = 

		; B tính  = 

		 và đăng ký các giá 
trị này với nhà cung cấp dịch vụ. 
2) A thực hiện như sau: 
- Lựa chọn ,  ∈ [2,  − 1]. 
- Tính	 = 

		 và  = 
		 
- Gửi (, ) cho B. 
3) B thực hiện như sau: 
- Chọn  ∈ [1,  − 1] và tính  = 
		 
- Chọn ,  ∈ [2,  − 1]. 
- Tính  = 
		 = 	
		. 
- Tính toán khóa bí mật được chia sẻ  = (||) 
- Tính  = 

		 và  = 
		 
- Tính  = (||||||||||) 
- Tính  = ( − )
		 
- Tính  = ( − )
		 
- Gửi lại các giá trị (, , , , , ) cho người A. 
4) A sau đó tiếp tục thực hiện như sau: 
- Tính	 = 		 
- Tính  = 
		 = 	
		 
- Tính khóa bí mật chia sẻ  = (||) 
- Xác thực (, , ) 
- Tính  = (||||||||||) 
- Tính  = ( − )
		 
- Tính  = ( − )
		 
- Gửi (, , ) cho B. 
5) B thực hiện: 
- Xác thực (, , ). 
Giao thức DH–MM–KE1 được mô tả như trong hình Hình 1. 
160
Tính đúng đ
3.2. Đ
Tính ch
trư
Ch
khóa phiên 

công không th
Do đó, giao th
Ta có: 
ớc (Perfect Forward Secrecy).
ứng minh:
Khóa phiên theo hư
Còn B tính nh
	và 
Do đó, khi m
Đ. V. B
ộ an to

ất 2.1:



ình, N. H. Minh, “Phát tri
 =



 ph
ắn của giao thức:

àn c
 Giao th
 Ta c
=
=
ụ thuộc v
ể tính bất kỳ khóa phi
ức n


ủa giao thức
và 

ư sau:

ột khóa d
ày đ

ần chứng minh nếu khóa bí mật d

(
(
	
=> 
ức DH
 đư
ớng từ A
||
||
ào giá tr
ảm bảo tính an to
Hình 

ợc tạo ra tr
)
)
ài h
	
=
=
=
1. 
=

–MM
 t
(
(
ị ngẫu nhi
ạn (
ển giao thức trao đổi khóa  dựa tr
Giao th
	 
(
ới B đ
||
||



||
–KE1 đ
ước đó vẫn không bị ảnh h





ên đ
ức DH

)
ược A tính nh


, 
ã s
àn đ

=
ảm bảo tính chất an to


ên 
), 
ử dụng 





(
ầy đủ về phía tr
–MM
	
(|


 và 
,

|
	
	


–KE1
	
)
ài h
ư sau:

) c

=
=
ạn của A v
	)
	)
ủa A v
 và 
. 



ư
 
ư
à B b
 
ớc.
Công ngh
ên hai bài toán khó.
àn đ
ởng.
bằng (3.1) v
à B b
ị lộ, ng
ầy đủ về phía 
ệ thông tin
ị lộ th
ư
à (3.2). 
ì các 
(3.1)
(3.2)
ời tấn 
”
Nghiên cứu khoa học công nghệ 
Tạp chí Nghiên cứu KH&CN quân sự, Số Đặc san CNTT, 11 - 2018 161
Tính chất 2.2: Giao thức DH–MM–KE1 thỏa mãn tính chất khóa độc lập. 
Chứng minh: Trong giao thức DH–MM–KE1, A và B tính khóa phiên  và 
 theo công thức (3.1) và (3.2). Có thể thấy, các khóa phiên đều phụ thuộc vào 
khóa bí mật (, ) và số ngẫu nhiên (, ). Điều này có nghĩa là các khóa 
phiên được tính độc lập. 
Tính chất 2.3: Giao thức DH–MM–KE1 an toàn với tấn công SSR 
Chứng minh: Ta cần chứng minh nếu người tấn công thu được các trạng thái 
trung gian trong quá trình thực hiện giao thức cũng không thể tính được khóa bí 
mật chia sẻ. 
Theo công thức (3.1) và (3.2), khóa phiên  và  phụ thuộc vào khóa bí 
mật (, ) của A và B. 
Do đó, khi các số ngẫu nhiên  và  hoặc các thành phần trung gian khác bị 
lộ, người tấn công cũng không thể tính được khóa phiên vì không tính được 
	(). 
Do đó, giao thức DH–MM–KE1 an toàn với tấn công SSR. 
Tính chất 2.4: Giao thức DH–MM–KE1 an toàn trước tấn công giả mạo khóa thỏa 
thuận (key compromise impersonation – KCI). 
Chứng minh: Giao thức này sử dụng một quá trình xác thực chung giữa A và B. 
Do đó, quá trình xác thực sẽ thất bại nếu người tấn công hoạt động và không đồng 
thời biết về  và (, ) hoặc  và (, ). 
Do đó, cách duy nhất của người tấn công là tính trực tiếp khóa phiên, giả sử 
người tấn công biết khóa bí mật dài hạn của A (, ) và khóa phiên tạm thời 
của B (), vì khóa phiên là  = (||
		) và người tấn 
công có thể tính . Tuy nhiên, trong trường hợp này, người tấn công vẫn không thể 
tính được 
. 
Do đó, giao thức DH–MM–KE1 an toàn trước tấn công giả mạo khóa thỏa 
thuận KCI. 
Tính chất 2.5: Giao thức DH–MM–KE1 an toàn trước tấn công không biết khóa 
chia sẻ (unknown key-share). 
Chứng minh: Việc xác nhận khóa có thể ngăn chặn tấn công không biết khóa chia 
sẻ. B xác nhận với A rằng đã nhận được khóa chia sẻ bí mật  bằng việc kí khóa 
này cùng với (, , , , ). Vì khóa bí mật chia sẻ  là một hàm băm 
một chiều của các số ngẫu nhiên (, ) của A, A tin rằng nội dung thông điệp 
không bị lặp và biết rằng nó thực sự là từ phía B. B cũng làm những điều tương tự 
với  giống như A. 
Tính chất 2.6: Giao thức DH–MM–KE1 an toàn dựa trên hai bài toán khó. 
Chứng minh: Ta cần chứng minh để phá giải giao thức DH–MM–KE1, người tấn 
công phải giải quyết đồng thời hai bài toán khó. 
Công nghệ thông tin 
Đ. V. Bình, N. H. Minh, “Phát triển giao thức trao đổi khóa  dựa trên hai bài toán khó.” 162 
Trong giao thức DH–MM–KE1, A và B tính khóa chia sẻ  và  theo công 
thức (3.1) và (3.2). 
Các giá trị này phụ thuộc vào (,  hoặc ). 
Để tính , người tấn công phải tính được , muốn tính được giá trị của  thì lại 
cần tìm được f() mà muốn tìm được f() thì lại cần phải giải tiếp bài toán phân 
tích  thành thừa số nguyên tố. 
Để tính  (hoặc ) người tấn công phải tính được giá trị của (, ) hoặc 
(, ). 
Ta có: ( = 
		 và  = 

		) và ( =

		 và  = 

		). 
Do đó, để tính được (, ) hoặc (, ), người tấn công phải giải bài 
toán logarithm rời rạc. 
Như vậy, giao thức DH–MM–KE1 an toàn dựa trên hai bài toán khó. 
3.3. Đánh giá hiệu quả thuật toán 
Độ phức tạp thời gian của giao thức DH–MM–KE1 được trình bày trong Bảng 3. 
Bảng 3. Độ phức tạp thời gian của giao thức DH–MM–KE1. 
Giai đoạn Độ phức tạp thời gian 
1 3 + 2 
2 7 + 5 + 2 
3 9 + 3 + 3 
4 5 + 2 +  
Tổng 24 + 12 + 6 
4. KẾT LUẬN 
Chúng tôi vừa đề xuất cải tiến lược đồ chữ ký số trước đây và một giao thức 
trao đổi khóa an toàn dựa trên lược đồ cải tiến này. Các giao thức này được xây 
dựng dựa trên hai bài toán khó, vì vậy, chúng có độ bảo mật cao hơn những giao 
thức trước đây. 
TÀI LIỆU THAM KHẢO 
[1]. Arazi B. (1993), “Integrating a key distribution procedure into the digital 
signature standard”. Electronics Letters; 29: 966-967. 
[2]. Brown D, Menezes A. (2001), “A Small Subgroup Attack on Arazi's Key 
Agreement Protocol”. Bulletin of the ICA;37: 45-50. 
[3]. Diffie W, Hellman M. (1976), “New Directions in Cryptography.IEEE 
Transactions on Information Theory”; 22: 644-654. 
[4]. Do Viet Binh, Authenticated key exchange protocol based on two hard 
problems, Tạp chí nghiên cứu khoa học và công nghệ quân sự, số 50, tháng 
Nghiên cứu khoa học công nghệ 
Tạp chí Nghiên cứu KH&CN quân sự, Số Đặc san CNTT, 11 - 2018 163
08-2017, trang 147-152. 
[5]. Harn L, Mehta M, Hsin WJ. (2004), “Integrating Diffie-Hellman key 
exchange into the digital signature algorithm (DSA)”. IEEE 
Communications Letters; 8: 198-200. 
[6]. Jeong IR, Kwon JO, Lee DH. (2007), “Strong Diffie-Hellman DSA Key 
Exchange”. IEEE Communications Letters; 11: 432-433. 
[7]. Liu J, Li J. (2010), “A Better Improvement on the Integrated Diffie-Hellman 
- DSA Key Agreement Protocol”. IEEE Com. Letters; 11: 114-117. 
[8]. Nyberg K, Rueppel R. (1994), “Weaknesses in some recent key agreement 
protocols”. Electronics Letters; 30: 26-27. 
ABSTRACT 
DEVELOP A SECURE KEY EXCHANGE PROTOCOL 
BASED ON TWO DIFFICULT MATH PROBLEMS 
In previous researches, we have proposed a solution of combination 
between digital signature and key exchange protocol to increase the security 
and achieve the necessary properties of secure key exchange protocols. In 
this paper, we propose a variant of previous digital signature scheme and 
develop a new secured key exchange protocol which is based on this variant. 
Keywords: Authentication; Hard problem; Key exchange; Protocol; Digital signature. 
Nhận bài ngày 28 tháng 06 năm 2018 
Hoàn thiện ngày 09 tháng 10 năm 2018 
Chấp nhận đăng ngày 05 tháng 11 năm 2018 
Địa chỉ: 1Viện CNTT – Viện KH&CN quân sự; 
 2Học viện Kỹ thuật mật mã. 
 *Email: binhdv@gmail.com.