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<br /> <br /> PHÁT TRIỂN GIAO THỨC TRAO ĐỔI KHÓA AN TOÀN<br /> DỰA TRÊN HAI BÀI TOÁN KHÓ<br /> Đỗ Việt Bình1*, Nguyễn Hiếu Minh2<br /> 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ý<br /> 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<br /> 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 đề<br /> 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<br /> khóa mới dựa trên biến thể này.<br /> <br /> Từ khóa: Xác thực; Bài toán khó; Trao đổi khóa; giao thức; Chữ ký số.<br /> <br /> <br /> 1. TỔNG QUAN<br /> Giao thức trao đổi khóa Diffie-Hellman (DH) không cung cấp khả năng xác<br /> thực giữa các bên tham gia [3]. Do đó, nhiều giao thức đã được đưa ra nhằm khắc<br /> 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<br /> những hạn chế và chỉ dựa trên một bài toán khó [5-7].<br /> Trong công bố trước đây [4], chúng tôi đã đề xuất việc kết hợp hai lược đồ chữ<br /> ký số RSA và Schnorr, đồng thời xây dựng giao thức trao đổi khóa an toàn DH–<br /> 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. Để<br /> 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–<br /> 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<br /> mới này.<br /> Trong bài báo này, phần 2 phân tích lược đồ chữ ký số RSA–Schnorr trong<br /> 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.<br /> 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<br /> 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<br /> tắt các kết quả của bài báo.<br /> 2. LƯỢC ĐỒ CHỮ KÝ SỐ RSA–SCHNORR<br /> Ở 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<br /> 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<br /> số nguyên tố mạnh , ’ và một số nguyên tố = 2 + 1 với = ’. Lược đồ<br /> được thực hiện như Bảng 1:<br /> Bảng 1. Lược đồ chữ ký số RSA-Schnorr.<br /> <br /> Tạo - Tính f( ) = ( − 1)( − 1).<br /> khóa - Chọn ∈ ∗ sao cho là phần tử có cấp bằng trong ∗<br /> thỏa<br /> mãn ≡ 1 .<br /> <br /> <br /> <br /> 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ó.”<br /> Nghiên cứu khoa học công nghệ<br /> <br /> ∗<br /> - Chọn số bí mật ∈ , ∈ [1, − 1] và tính = .<br /> - Chọn số nguyên ∈ thỏa mãn: , f( ) = 1.<br /> - Tính sao cho: ∗ = 1 f( ).<br /> - Khóa công khai là ( , , ), khóa bí mật là ( , ).<br /> <br /> Ký - Chọn ngẫu nhiên số bí mật với 1 < < .<br /> - Tính = .<br /> - Tính = ( || ).<br /> - Tính =( − ) .<br /> - Chữ ký là ( , ).<br /> <br /> ∗<br /> Xác - Tính = .<br /> thực ∗ ∗<br /> - Tính = .<br /> ∗ ∗<br /> - Tính = ( || ).<br /> ∗<br /> - Nếu = chữ ký hợp lệ.<br /> ∗<br /> - Ngược lại nếu ≠ chữ ký không hợp lệ.<br /> <br /> <br /> 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<br /> cao khả năng bảo mật. Lược đồ này được mô tả như trong Bảng 2:<br /> Bảng 2. Biến thể lược đồ chữ ký số RSA-Schnorr.<br /> Tạo - Chọn hai số nguyên tố mạnh và ’.<br /> khóa - Tính = ’ và = 2 + 1 thỏa mãn là số nguyên tố.<br /> - Tính f( ) = ( − 1)( − 1).<br /> - Chọn , ∈ ∗ sao cho , là các phần tử có cấp bằng trong ∗<br /> <br /> thỏa mãn ≡ 1 và ≡ 1 .<br /> ∗<br /> - Chọn hai số bí mật , ∈ với , ∈ [1, − 1].<br /> - Tính = .<br /> - Chọn số nguyên ∈ thỏa mãn: , f( ) = 1.<br /> - Tính sao cho: ∗ = 1 f( ).<br /> - Khóa công khai là ( , , ), khóa bí mật là ( , , ).<br /> Ký - Chọn ngẫu nhiên hai số , bí mật với 1 < , < .<br /> - Tính = .<br /> <br /> <br /> <br /> Tạp chí Nghiên cứu KH&CN quân sự, Số Đặc san CNTT, 11 - 2018 157<br />  Công nghệ thông tin<br /> <br /> - Tính = ( || ).<br /> - Tính =( − ) .<br /> - Tính =( − ) .<br /> - Chữ ký là ( , , ).<br /> ∗<br /> Xác - Tính = .<br /> thực - Tính ∗<br /> = .<br /> ∗ ∗<br /> ∗<br /> - Tính = .<br /> ∗ ∗<br /> - Tính = ( || ).<br /> ∗<br /> - Nếu = chữ ký hợp lệ.<br /> ∗<br /> - Ngược lại nếu ≠ chữ ký không hợp lệ.<br /> <br /> <br /> Tính đúng đắn của giao thức:<br /> ∗ ∗ ∗ ∗<br /> ∗<br /> Ta có: = = =<br /> = = =<br /> ∗ ∗)<br /> => = ( || = ( || ) = .<br /> Với việc sử dụng hai phần tử , , khóa bí mật ( , , ) và hai thành phần ngẫu<br /> 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<br /> giải bài toán logarithm rời rạc.<br /> 3. GIAO THỨC DH–MM–KE1<br /> 3.1. Mô tả giao thức<br /> Dựa trên biến thể của lược đồ chữ ký số RSA–Schnorr, chúng tôi đề xuất giao<br /> 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<br /> hoạt động như sau:<br /> 1) Chọn tham số:<br /> Các tham số của hai bên A và B được tính như biến thể lược đồ RSA–Schnorr<br /> trình bày trong phần 2.<br /> Với người gửi A: = 2 + 1, trong đó = , và là các số<br /> 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:<br /> Khóa công khai ( , ) và khóa bí mật ( , ).<br /> Với người nhận B: = 2 + 1, trong đó = , và là các số<br /> 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:<br /> Khóa công khai ( , ) và khóa bí mật ( , ).<br /> Ký hiệu { } = {0, 1, … , − 1} và { } = {0, 1, … , − 1}.<br /> <br /> <br /> 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ó.”<br /> Nghiên cứu khoa học công nghệ<br /> <br /> Tìm tập = ∩ . Tính = ( , ).<br /> ∗ ∗<br /> Tìm , là phần tử có cấp bằng trong và có cấp bằng trong thỏa<br /> mãn ≡ 1 ; ≡ 1 và ≡ 1 ; ≡ 1 .<br /> A tính = ; B tính = và đăng ký các giá<br /> trị này với nhà cung cấp dịch vụ.<br /> 2) A thực hiện như sau:<br /> - Lựa chọn , ∈ [2, − 1].<br /> - Tính = và = <br /> - Gửi ( , ) cho B.<br /> 3) B thực hiện như sau:<br /> - Chọn ∈ [1, − 1] và tính = <br /> - Chọn , ∈ [2, − 1].<br /> - Tính = = .<br /> - Tính toán khóa bí mật được chia sẻ = ( || )<br /> - Tính = và = <br /> - Tính = ( || || || || || )<br /> - Tính =( − ) <br /> - Tính =( − ) <br /> - Gửi lại các giá trị ( , , , , , ) cho người A.<br /> 4) A sau đó tiếp tục thực hiện như sau:<br /> - Tính = <br /> - Tính = = <br /> - Tính khóa bí mật chia sẻ = ( || )<br /> - Xác thực ( , , )<br /> - Tính = ( || || || || || )<br /> - Tính =( − ) <br /> - Tính =( − ) <br /> - Gửi ( , , ) cho B.<br /> 5) B thực hiện:<br /> - Xác thực ( , , ).<br /> Giao thức DH–MM–KE1 được mô tả như trong hình Hình 1.<br /> <br /> <br /> <br /> Tạp chí Nghiên cứu KH&CN quân sự, Số Đặc san CNTT, 11 - 2018 159<br />  Công ngh<br /> nghệệ thông tin<br /> <br /> <br /> <br /> <br /> Hình 1. Giao th<br /> thức<br /> ức DH<br /> DH–MM<br /> MM KE1.<br /> MM–KE1<br /> KE1<br /> Tính đúng đ<br /> đắn<br /> ắn của giao thức:<br /> Ta có: = = =<br /> => = ( ||| ) = ( || | )=<br /> 3.2. Đ<br /> Độ<br /> ộ an to<br /> toàn<br /> àn của<br /> của giao thức<br /> chất 2.1: Giao th<br /> Tính chất thức<br /> ức DH–MM<br /> DH MM MM–KE1 KE1 đđảm ảm bảo tính chất an to toàn<br /> àn đầy<br /> đầy đủ về phía<br /> trước (Perfect Forward Secrecy).<br /> trước<br /> Ch ứng minh: Ta ccần<br /> hứng ần chứng minh nếu khóa bí mật ddài ài hhạn<br /> ạn của A vvàà B bbịị lộ th<br /> thìì các<br /> khóa phiên và đư ợc tạo ra tr<br /> được trước<br /> ớc đó vẫn không bị ảnh hhư ưởng.<br /> ởng.<br /> Khóa phiên theo hư hướng<br /> ớng từ A tớitới B đđược<br /> ợc A tính nh như<br /> ư sau:<br /> = ( || ) = ( ||| ) (3.1)<br /> Còn B tính nh<br /> nhưư sau:<br /> = ( || ) = ( ||| ) (3.2)<br /> và<br /> và phụ<br /> phụ thuộc vvào ào giá tr<br /> trịị ngẫu nhi<br /> nhiên<br /> ên và<br /> Do đó, khi m một<br /> ột khóa ddài hạn ( , ), ( , ) ccủa<br /> ài hạn ủa A vvàà B bịbị lộ, ng<br /> ngưườiời tấn<br /> công không th<br /> thểể tính bất kỳ khóa phi phiên<br /> ên đđãã ssử<br /> ử dụng và bằng<br /> ằng (3.1) v vàà (3.2).<br /> Do đó, giao th<br /> thức<br /> ức này<br /> này đđảm<br /> ảm bảo tính an to toàn<br /> àn đầy<br /> đầy đủ về phía tr trư<br /> ước.<br /> ớc.<br /> <br /> <br /> 160 Đ. V. Bình,<br /> Bình, N. H. Minh, “Phát tri<br /> triển<br /> ển giao thức trao đổi khóa … dựa tr<br /> trên khó.””<br /> ên hai bài toán khó.<br /> Nghiên cứu khoa học công nghệ<br /> <br /> 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.<br /> Chứng minh: Trong giao thức DH–MM–KE1, A và B tính khóa phiên và<br /> 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<br /> khóa bí mật ( , ) và số ngẫu nhiên ( , ). Điều này có nghĩa là các khóa<br /> phiên được tính độc lập.<br /> Tính chất 2.3: Giao thức DH–MM–KE1 an toàn với tấn công SSR<br /> 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<br /> trung gian trong quá trình thực hiện giao thức cũng không thể tính được khóa bí<br /> mật chia sẻ.<br /> Theo công thức (3.1) và (3.2), khóa phiên và phụ thuộc vào khóa bí<br /> mật ( , ) của A và B.<br /> Do đó, khi các số ngẫu nhiên và hoặc các thành phần trung gian khác bị<br /> 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<br /> ( ).<br /> Do đó, giao thức DH–MM–KE1 an toàn với tấn công SSR.<br /> 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<br /> thuận (key compromise impersonation – KCI).<br /> 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.<br /> 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<br /> thời biết về và ( , ) hoặc và ( , ).<br /> 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ử<br /> 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<br /> của B ( ), vì khóa phiên là = ( || ) và người tấn<br /> 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ể<br /> tính được .<br /> Do đó, giao thức DH–MM–KE1 an toàn trước tấn công giả mạo khóa thỏa<br /> thuận KCI.<br /> 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<br /> chia sẻ (unknown key-share).<br /> 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<br /> 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<br /> này cùng với ( , , , , ). Vì khóa bí mật chia sẻ là một hàm băm<br /> 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<br /> 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ự<br /> với giống như A.<br /> 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ó.<br /> Chứng minh: Ta cần chứng minh để phá giải giao thức DH–MM–KE1, người tấn<br /> công phải giải quyết đồng thời hai bài toán khó.<br /> <br /> <br /> <br /> Tạp chí Nghiên cứu KH&CN quân sự, Số Đặc san CNTT, 11 - 2018 161<br />  Công nghệ thông tin<br /> <br /> Trong giao thức DH–MM–KE1, A và B tính khóa chia sẻ và theo công<br /> thức (3.1) và (3.2).<br /> Các giá trị này phụ thuộc vào ( , hoặc ).<br /> Để 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<br /> 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<br /> tích thành thừa số nguyên tố.<br /> Để tính (hoặc ) người tấn công phải tính được giá trị của ( , ) hoặc<br /> ( , ).<br /> Ta có: ( = và = ) và ( =<br /> và = ).<br /> Do đó, để tính được ( , ) hoặc ( , ), người tấn công phải giải bài<br /> toán logarithm rời rạc.<br /> Như vậy, giao thức DH–MM–KE1 an toàn dựa trên hai bài toán khó.<br /> 3.3. Đánh giá hiệu quả thuật toán<br /> Độ phức tạp thời gian của giao thức DH–MM–KE1 được trình bày trong Bảng 3.<br /> Bảng 3. Độ phức tạp thời gian của giao thức DH–MM–KE1.<br /> Giai đoạn Độ phức tạp thời gian<br /> 1 3 +2<br /> 2 7 +5 +2<br /> 3 9 +3 +3<br /> 4 5 +2 +<br /> Tổng 24 + 12 +6<br /> <br /> 4. KẾT LUẬN<br /> 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<br /> 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<br /> 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<br /> thức trước đây.<br /> TÀI LIỆU THAM KHẢO<br /> [1]. Arazi B. (1993), “Integrating a key distribution procedure into the digital<br /> signature standard”. Electronics Letters; 29: 966-967.<br /> [2]. Brown D, Menezes A. (2001), “A Small Subgroup Attack on Arazi's Key<br /> Agreement Protocol”. Bulletin of the ICA;37: 45-50.<br /> [3]. Diffie W, Hellman M. (1976), “New Directions in Cryptography.IEEE<br /> Transactions on Information Theory”; 22: 644-654.<br /> [4]. Do Viet Binh, Authenticated key exchange protocol based on two hard<br /> problems, Tạp chí nghiên cứu khoa học và công nghệ quân sự, số 50, tháng<br /> <br /> <br /> 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ó.”<br /> Nghiên cứu khoa học công nghệ<br /> <br /> 08-2017, trang 147-152.<br /> [5]. Harn L, Mehta M, Hsin WJ. (2004), “Integrating Diffie-Hellman key<br /> exchange into the digital signature algorithm (DSA)”. IEEE<br /> Communications Letters; 8: 198-200.<br /> [6]. Jeong IR, Kwon JO, Lee DH. (2007), “Strong Diffie-Hellman DSA Key<br /> Exchange”. IEEE Communications Letters; 11: 432-433.<br /> [7]. Liu J, Li J. (2010), “A Better Improvement on the Integrated Diffie-Hellman<br /> - DSA Key Agreement Protocol”. IEEE Com. Letters; 11: 114-117.<br /> [8]. Nyberg K, Rueppel R. (1994), “Weaknesses in some recent key agreement<br /> protocols”. Electronics Letters; 30: 26-27.<br /> <br /> ABSTRACT<br /> DEVELOP A SECURE KEY EXCHANGE PROTOCOL<br /> BASED ON TWO DIFFICULT MATH PROBLEMS<br /> In previous researches, we have proposed a solution of combination<br /> between digital signature and key exchange protocol to increase the security<br /> and achieve the necessary properties of secure key exchange protocols. In<br /> this paper, we propose a variant of previous digital signature scheme and<br /> develop a new secured key exchange protocol which is based on this variant.<br /> Keywords: Authentication; Hard problem; Key exchange; Protocol; Digital signature.<br /> <br /> <br /> Nhận bài ngày 28 tháng 06 năm 2018<br /> Hoàn thiện ngày 09 tháng 10 năm 2018<br /> Chấp nhận đăng ngày 05 tháng 11 năm 2018<br /> <br /> <br /> <br /> 1<br /> Địa chỉ: Viện CNTT – Viện KH&CN quân sự;<br /> 2<br /> Học viện Kỹ thuật mật mã.<br /> *<br /> Email: binhdv@gmail.com.<br /> <br /> <br /> <br /> <br /> Tạp chí Nghiên cứu KH&CN quân sự, Số Đặc san CNTT, 11 - 2018 163<br />