Xem mẫu
- Công nghệ thông tin
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 - Tính f( ) = ( − 1)( − 1).
khóa - Chọn ∈ ∗ sao cho là phần tử có cấp bằng trong ∗
thỏa
mãn ≡ 1 .
156 Đ. 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ó.”
- Nghiên cứu khoa học công nghệ
∗
- 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 - Tính = .
thực ∗ ∗
- 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 - Chọn hai số nguyên tố mạnh và ’.
khóa - 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 = .
Tạp chí Nghiên cứu KH&CN quân sự, Số Đặc san CNTT, 11 - 2018 157
- Công nghệ thông tin
- Tính = ( || ).
- Tính =( − ) .
- Tính =( − ) .
- Chữ ký là ( , , ).
∗
Xác - Tính = .
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ệ.
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}.
158 Đ. 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ó.”
- Nghiên cứu khoa học công nghệ
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.
Tạp chí Nghiên cứu KH&CN quân sự, Số Đặc san CNTT, 11 - 2018 159
- Công ngh
nghệệ thông tin
Hình 1. Giao th
thức
ức DH
DH–MM
MM KE1.
MM–KE1
KE1
Tính đúng đ
đắn
ắn của giao thức:
Ta có: = = =
=> = ( ||| ) = ( || | )=
3.2. Đ
Độ
ộ an to
toàn
àn của
của giao thức
chất 2.1: Giao th
Tính chất thức
ức DH–MM
DH MM MM–KE1 KE1 đđảm ảm bảo tính chất an to toàn
àn đầy
đầy đủ về phía
trước (Perfect Forward Secrecy).
trước
Ch ứng minh: Ta ccần
hứng ần chứng minh nếu khóa bí mật ddài ài hhạn
ạn của A vvàà B bbịị lộ th
thìì các
khóa phiên và đư ợc tạo ra tr
được trước
ớc đó vẫn không bị ảnh hhư ưởng.
ởng.
Khóa phiên theo hư hướng
ớng từ A tớitới B đđược
ợc A tính nh như
ư sau:
= ( || ) = ( ||| ) (3.1)
Còn B tính nh
nhưư sau:
= ( || ) = ( ||| ) (3.2)
và
và phụ
phụ thuộc vvào ào giá tr
trịị ngẫu nhi
nhiên
ên và
Do đó, khi m một
ột khóa ddài hạn ( , ), ( , ) ccủa
ài hạn ủa A vvàà B bịbị lộ, ng
ngưườiời tấn
công không th
thểể tính bất kỳ khóa phi phiên
ên đđãã ssử
ử dụng và bằng
ằng (3.1) v vàà (3.2).
Do đó, giao th
thức
ức này
này đđảm
ảm bảo tính an to toàn
àn đầy
đầy đủ về phía tr trư
ước.
ớc.
160 Đ. V. Bình,
Bình, N. H. Minh, “Phát tri
triển
ển giao thức trao đổi khóa … dựa tr
trên khó.””
ên hai bài toán khó.
- Nghiên cứu khoa học công nghệ
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ó.
Tạp chí Nghiên cứu KH&CN quân sự, Số Đặc san CNTT, 11 - 2018 161
- Công nghệ thông tin
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
162 Đ. 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ó.”
- Nghiên cứu khoa học công nghệ
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
1
Địa chỉ: Viện CNTT – Viện KH&CN quân sự;
2
Học viện Kỹ thuật mật mã.
*
Email: binhdv@gmail.com.
Tạp chí Nghiên cứu KH&CN quân sự, Số Đặc san CNTT, 11 - 2018 163
nguon tai.lieu . vn