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ì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ó.” 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.