Xây dựng giao thức trao đổi khóa an toàn dựa trên tính khó của việc giải đồng thời 2 bài toán logarit rời rạc và phân tích số/khai căn cho các hệ mật khóa đối xứng - Nguyễn Vĩnh Thái

Công nghệ thông tin N. V. Thái, L. H. Dũng, “Xây dựng giao thức trao đổi khóa các hệ mật khóa đối xứng.” 8 XÂY DỰNG GIAO THỨC TRAO ĐỔI KHÓA AN TOÀN DỰA TRÊN TÍNH KHÓ CỦA VIỆC GIẢI ĐỒNG THỜI 2 BÀI TOÁN LOGARIT RỜI RẠC VÀ PHÂN TÍCH SỐ/KHAI CĂN CHO CÁC HỆ MẬT KHÓA ĐỐI XỨNG Nguyễn Vĩnh Thái1, Lưu Hồng Dũng2* Tóm tắt: Bài báo đề xuất xây dựng giao thức trao đổi khóa an toàn cho các hệ mã hóa khóa đối xứng từ mức độ khó của việc giải đồng thời 2 bài toán: bài toán logarit rời rạc trên Zp và bài toán phân tích một số nguyên lớn ra các thừa số nguyên tố, hoặc: bài toán logarit rời rạc trên Zp và bài toán khai căn trên vành Zn. Giao thức mới đề xuất đảm bảo các tính chất của một giao thức trao đổi khóa an toàn, đồng thời khóa bí mật chia sẻ tạo ra được xác thực về nguồn gốc nên có thể chống lại các kiểu tấn công khóa giả mạo, khóa bí mật chia sẻ rất hiệu quả. Từ khóa: Logarit rời rạc; Phân tích số; Khai căn; Xác nhận khóa; Giao thức xác nhận khóa; Giao thức trao đổi khóa; Giao thức chuyển khóa. 1. ĐẶT VẤN ĐỀ Trong các hệ mã khóa bí mật (Secret - Key Cryptosystems), việc thiết lập một khóa bí mật chung (Key Establishment) cho cả bên gửi/mã hóa và bên nhận/giải mã là một vấn đề rất quan trọng và phức tạp, được thực hiện bằng các giao thức thỏa thuận khóa (Key Agreement Protocols) hay chuyển khóa (Key Transport Protocols). Chuyển khóa được thực hiện bằng việc tạo trước khóa bí mật dùng chung bởi 1 trong 2 bên, rồi sử dụng các thuật toán mật mã khóa công khai như RSA, ElGamal,... để chuyển cho bên kia qua các kênh không an toàn. Sử dụng thuật toán mã khóa công khai để chuyển khóa không bảo đảm được một số tính chất an toàn như: Xác thực thực thể (entity authentication), xác thực khóa hiện (explicit key authentication), tính bí mật về phía trước (forward secrecy),... Vì vậy, việc chuyển khóa chỉ được thực hiện khi yêu cầu về các tính chất an toàn như thế không được đặt ra trong các ứng dụng thực tế. Khác với chuyển khóa, thỏa thuận khóa được thực hiện theo cách mà ở đó mỗi bên tham gia sẽ tạo ra thông tin để thỏa thuận cho việc thiết lập 1 khóa bí mật dùng chung, rồi trao đổi các thông tin này cho nhau. Từ thông tin thỏa thuận nhận được mỗi bên sẽ tạo ra khóa bí mật chung hay còn gọi là khóa bí mật chia sẻ. Do có việc trao đổi thông tin thỏa thuận khóa trong quá trình thiết lập 1 khóa chung giữa 2 bên, các giao thức loại này còn được gọi là giao thức trao đổi khóa (Key Exchange Protocols). Giao thức thỏa thuận khóa đầu tiên được đề xuất bởi W. Diffie và M. Hellman vào năm 1976 (DHKE) [1]. Với giao thức HDKE, không một kẻ thứ 3 nào có thể tính được khóa bí mật của 2 đối tượng tham gia trao đổi khóa nếu không giải được bài toán logarit rời rạc DLP (Discrete Logarithm Problem) [2]. Tuy nhiên, DHKE có thể dễ dàng bị một kẻ thứ 3 không mong muốn mạo danh một trong 2 đối tượng để thiết lập 1 khóa bí mật chung với đối tượng kia [3]. Một hướng nghiên cứu nhằm khắc phục nhược điểm trên đây của DHKE là tích hợp giao thức này với các thuật toán chữ ký số, hoặc giao thức trao đổi khóa an toàn dựa trên hai bài toán khó và đã có một số kết quả về hướng nghiên cứu này được công bố [4 - 10]. 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, 04 - 2019 9 Trong phần tiếp theo của bài báo, nhóm tác giả đề xuất xây dựng giao thức trao đổi khóa an toàn cho các hệ mật khóa đối xứng dựa trên tính khó của việc giải đồng thời 2 bài toán logarit rời rạc và phân tích số/khai căn. Khác với các giao thức trong [4] tới [10], giao thức mới đề xuất ở đây sử dụng mật mã khóa công khai mà không phải chữ ký số để cung cấp tính năng xác thực khóa bí mật chia sẻ, từ đó có thể chống lại các dạng tấn công giả mạo đã biết trong thực tế. Giao thức trao đổi khóa cho các hệ mật khóa đối xứng này được thiết kế để các thực thể cuối (người sử dụng) trong cùng một hệ thống có thể sử dụng chung một bộ tham số (tham số miền) do nhà cung cấp dịch vụ chứng thực số tạo ra. 2. MỘT SỐ BÀI TOÁN KHÓ ỨNG DỤNG TRONG MẬT MÃ 2.1. Bài toán phân tích số Bài toán phân tích số được phát biểu như sau: Cho số ∈ ℕ, hãy tìm biểu diễn: = Π với: ≥ 1 ( = 1, , ) nguyên dương; ≥ 1 ( = 1, , ) nguyên tố. Một trường hợp riêng của bài toán phân tích số được ứng dụng để xây dựng hệ mật RSA mà ở đó là tích của hai số nguyên tố và . Khi đó, bài toán phân tích số hay còn gọi là bài toán () được phát biểu như sau: Với mỗi số nguyên dương , hãy tìm số nguyên tố hoặc thỏa mãn phương trình sau: × = Giải thuật cho bài toán () có thể được viết như một thuật toán tính hàm (.) với biến đầu vào là , còn giá trị hàm là hoặc của phương trình sau: = () hoặc: = () Trong hệ mật RSA [12], bài toán phân tích số được sử dụng trong việc hình thành cặp khóa công khai/bí mật cho mỗi thực thể ký. Với việc giữ bí mật các tham số (, ) thì việc tính được khóa bí mật () từ khóa công khai () và () là một bài toán khó nếu , được chọn đủ lớn và mạnh. Hiện tại bài toán trên vẫn được coi là bài toán khó do chưa có giải thuật thời gian đa thức hay đa thức xác suất cho nó và hệ mật RSA là một minh chứng thực tế cho tính khó giải của bài toán này. Trong thực tế, các tham số , có thể chọn theo FIPS 186 - 4 [11] của Hoa Kỳ cho hệ mật RSA. 2.2. Bài toán khai căn trên Cho cặp số nguyên dương (, ) với là tích 2 số nguyên tố và sao cho bài toán phân tích số là khó giải trên Z, còn là một giá trị thỏa mãn: 1 < < () và: gcd, () = 1, ở đây: () = ( − 1). ( − 1). Khi đó, bài toán khai căn trên Z hay còn gọi là RSAP(,) được phát biểu như sau: Với mỗi số nguyên dương ∈ ℤ ∗ , hãy tìm thỏa mãn phương trình sau: = Bài toán RSAP(,) cũng là một cơ sở quan trọng để xây dựng nên hệ mật RSA. Ở hệ mật RSA nếu giải được RSAP(,), kẻ thám mã có thể tìm được bản rõ (M) từ bản mã (C) và các tham số công khai (, ), hoặc dễ dàng tạo được chữ ký giả mạo Công nghệ thông tin N. V. Thái, L. H. Dũng, “Xây dựng giao thức trao đổi khóa các hệ mật khóa đối xứng.” 10 (S) cho một bản tin bất kỳ (M) mà không cần biết khóa bí mật (d) của đối tượng ký (bị mạo danh). Tuy nhiên, hiện tại vẫn chưa có giải thuật thời gian đa thức cho bài toán này và do đó việc tấn công hệ mật RSA bằng việc giải RSAP(,) là vẫn chưa khả thi. 2.3. Bài toán logarit rời rạc trên Cho cặp số nguyên dương (, ) với là số nguyên tố, còn là một phần tử của nhóm ∗ . Khi đó, bài toán logarit rời rạc trên Z hay còn gọi là bài toán DLP(,) được phát biểu như sau: Với mỗi số nguyên dương ∈ ℤ ∗ , hãy tìm thỏa mãn phương trình sau: = Giải thuật cho bài toán DLP(,) có thể được viết như một thuật toán tính hàm DLP(,)(. ) với biến đầu vào là , còn giá trị hàm là của phương trình sau: = DLP(,)() Bài toán DLP(,) là cơ sở để xây dựng nên hệ mật ElGamal [2]. Hiện tại chưa có giải thuật hiệu quả (thời gian đa thức hay đa thức xác suất) cho DLP(,) và độ an toàn của thuật toán DSA trong chuẩn chữ ký số DSS của Hoa Kỳ là một minh chứng thực tế cho tính khó giải của bài toán này. 3. XÂY DỰNG GIAO THỨC TRAO ĐỔI KHÓA CHO CÁC HỆ MẬT KHÓA ĐỐI XỨNG 3.1. Thuật toán hình thành tham số và khóa Các tham số hệ thống hay tham số miền được nhà cung cấp dịch vụ chứng thực số hình thành bằng thuật toán như sau: a) Thuật toán 3.1. Hình thành các tham số hệ thống Input: , - độ dài (tính theo bit) của các số nguyên tố , . Output: , , . Bước 1. Chọn cặp số , nguyên tố với: () = , () = sao cho |( − 1) Bước 2. Chọn là phần tử sinh của nhóm ∗ theo: = , với ∈ (1, ) Chú thích: (. ): hàm tính độ dài (theo bit) của một số. Mỗi thực thể cuối/người sử dụng trong hệ thống hình thành khóa của mình bằng thuật toán như sau: b) Thuật toán 3.2. Hình thành khóa Input: , , , , - độ dài (tính theo bit) của các số nguyên tố , . Output: , , (), . Bước 1. Chọn cặp số , là các nguyên tố với: () = , () = Bước 2. Tính = . , nếu ≤ thì thực hiện lại Bước 1. Bước 3. Tính () = ( − 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, 04 - 2019 11 Bước 4. Chọn khóa bí mật thứ nhất trong khoảng (1, ) Bước 5. Tính khóa công khai theo: = (1) Kiểm tra nếu: ≥ () hoặc: gcd (, ()) ≠ 1 thì thực hiện lại từ bước 4. Bước 6. Tính khóa bí mật thứ hai theo: = () (2) Bước 7. Chọn hàm băm : {0,1}∗ → với < ℎ < 3.2. Giao thức trao đổi khóa Giả thiết rằng 2 đối tượng tham gia truyền thông ở đây là A và B sử dụng một thuật toán mật mã khóa đối xứng (DES, AES,...) để mã hóa dữ liệu cần trao đổi với nhau, khi đó giao thức trao đổi khóa đề xuất ở đây (ký hiệu: MTA 01.19 - 01) được sử dụng để thiết lập một khóa bí mật chung/chia sẻ giữa A và B. Các tham số hệ thống cũng được hình thành theo Thuật toán (1) và khóa hình thành theo Thuật toán (2). Giả thiết A, B có cặp khóa bí mật/công khai tương ứng là (, , ) và (, , ) trong đó (, ) được chọn ngẫu nhiên trong khoảng (1, ), còn (, ) và (, ) được tính theo (1), (2) như sau: = , = () () (3) = , = () () a) Giao thức trao đổi khóa (MTA 01.19 - 01) Input: p, q , g, , , , , , , , . Output: , . Bảng 1 được sử dụng để mô tả thiết lập một khóa bí mật chung/chia sẻ giữa A và B như sau: Bảng 1. Các bước của giao thức MTA 01.19 - 01. A B Bước 1 - Chọn ngẫu nhiên một giá trị : 0 < < = (4) - Tính thành phần theo: = () (5) - Tính thành phần theo: = ‖ (6) , - Chọn ngẫu nhiên một giá trị : 0 < < = (7) - Tính thành phần theo: = () (8) - Tính thành phần theo: = ‖ (9) , Bước 2 Công nghệ thông tin N. V. Thái, L. H. Dũng, “Xây dựng giao thức trao đổi khóa các hệ mật khóa đối xứng.” 12 A B - Tính : =‖() (10) - Kiểm tra nếu = thì thực hiện tiếp, nếu ≠ thì dừng. - Tính khóa bí mật chia sẻ với B theo: = (() ) (11) - Tính thành phần theo: = ‖ (12) - Tính : =‖() (13) - Kiểm tra nếu = thì thực hiện tiếp, nếu ≠ thì dừng. - Tính khóa bí mật chia sẻ với A theo: = (() ) (14) - Tính thành phần theo: = ‖ (15) Bước 3 - Tính : =‖() (16) - Kiểm tra nếu = thì A khẳng định đối tượng tham gia trao đổi khóa là B và B đã thiết lập được khóa bí mật chia sẻ với A, sau đó A có thể dùng khóa này để trao đổi thông tin mật với B bằng 1 thuật toán mật mã khóa đối xứng, Nếu ≠ thì khẳng định đối tượng tham gia trao đổi khóa là giả mạo và hủy khóa đã được tạo ra. - Tính : =‖() (17) - Kiểm tra nếu = thì B khẳng định đối tượng tham gia trao đổi khóa là A và A đã thiết lập được khóa bí mật chia sẻ với B, sau đó B có thể dùng khóa này để trao đổi thông tin mật với A bằng 1 thuật toán mật mã khóa đối xứng, Nếu ≠ thì khẳng định đối tượng tham gia trao đổi khóa là giả mạo và hủy khóa đã được tạo ra. b) Tính đúng đắn của giao thức Điều cần chứng minh ở đây là: Cho p, q , p, q là các số nguyên tố thỏa mãn: |(p − 1), n = p × q, > , 1 < < , = , 1 < , < , = , = , = () (), = () (), 1 < < , = , 1 < < , = , = () , = ‖ , = () , = ‖ , = (() ) , = (() ) , = ‖ , = (‖‖ ) Nếu: = ‖() , = ‖() , = ‖() , = ‖() thì: =, =, =, =, = Chứng minh: 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, 04 - 2019 13 Từ (7), (11) ta có: = (() ) = (( ). ) =( ) =. (18) Từ (4), (14) ta có: = (() ) = (( ). ) =( ) =. (19) Từ (18), (19) ta có: = (20) Từ (3) và (5) ta có: = () = ( ) = . (21) Từ (3) và (8) ta có: = () = ( ) = . (22) Từ (21), (22) ta có: = (23) Từ (6), (13) và (23) suy ra: = ‖() = ‖ = Từ (9), (10), và (23) suy ra: = ‖() = ‖ = Từ (12), (17), (18) và (23) suy ra: = ‖() = ‖ = Từ (15), (16), (18) và (23) suy ra: = ‖() = ‖ = c) Độ an toàn của giao thức Giao thức MTA 01.19 - 01 được đề xuất bảo đảm các tính chất an toàn của một giao thức trao đổi khóa: - Xác thực thực thể: ở giao thức này việc kiểm tra điều kiện = và = cho phép các đối tượng tham gia trao đổi khóa hoàn toàn có thể xác thực được danh tính của nhau. - Xác thực khóa hiện: bằng việc kiểm tra điều kiện = , A hoàn toàn có thể khẳng định B đã tạo được khóa bí mật chia sẻ với mình và B cũng có thể khẳng định được điều tương tự như thế với A khi điều kiện: = thỏa mãn. - Tính an toàn khóa đã biết: việc biết một hoặc một số khóa chia sẻ giữa A và B cũng không cho phép một đối tượng thứ 3 nào đó có thể tính được các khóa khác cũng được thiết lập bởi A và B. - Tính bí mật về phía trước: việc tính các khóa bí mật chia sẻ đã được thiết lập trước đó bởi A và B là không thể thực hiện được, dù các khóa bí mật của A và B (, , , ) bị lộ. Các tính chất an toàn nói trên của thuật toán thực chất được đảm bảo bởi mức độ an toàn của nó trước các dạng tấn công: - Tấn công khóa bí mật chia sẻ: Công nghệ thông tin N. V. Thái, L. H. Dũng, “Xây dựng giao thức trao đổi khóa các hệ mật khóa đối xứng.” 14 Để tính được khóa , từ (11) cho thấy kẻ tấn công cần phải tính được và . Để tính cần phải giải được (), còn để tính từ (3) trước tiên cần phải giải được bài toán phân tích số () rồi tính: = () hoặc phải giải được bài toán khai căn RSAP(,) để tìm: = (,)(). Sau đó phải giải tiếp bài toán logarit rời rạc DLP(,) để tìm : = (,)(). Việc tính từ (14) cũng phải được thực hiện các bước tương tự như thế. Như vậy, độ an toàn của thuật toán trước dạng tấn công khóa bí mật chia sẻ luôn được đảm bảo bằng tính khó của việc giải đồng thời 2 bài toán: DLP(,)và (); DLP(,) và RSAP(,). - Tấn công giả mạo: Một kẻ giả mạo T muốn mạo danh A để tạo khóa bí mật chia sẻ với B hoặc mạo danh B để chia sẻ khóa bí mật với A thì cần phải tính được: , , , . Tuy nhiên, từ (6) cho thấy để tính được thì kẻ giả mạo cần phải giải được bài toán loagrit rời rạc: = (,)() rồi tính và bài toán khai căn để tìm: = (,)() hoặc bài toán phân tích số để tìm khóa bí mật rồi tính: = () . Để tính từ (9) hay , từ (12) và (15) thì T cũng phải thực hiện các bước tính toán tương tự. Như vậy, để có thể giả mạo thành công A hoặc B nhằm tạo khóa bí mật chia sẻ với đối tượng còn lại thì T cần phải giải được đồng thời 2 bài toán: DLP(,) và () hoặc DLP(,) và RSAP(,). Nghĩa là độ an toàn trước dạng tấn công giả mạo của giao thức được đảm bảo bằng độ khó của việc giải đồng thời 2 bài toán DLP(,) và () hoặc DLP(,) và RSAP(,). 4. KẾT LUẬN Bài báo đề xuất xây dựng một giao thức trao đổi khóa an toàn cho các hệ mật khóa đối xứng. Qua phân tích đánh giá cho thấy các thuật toán của giao thức mới đề xuất có độ an toàn được đảm bảo bằng mức độ khó của việc giải đồng thời 2 bài toán: bài toán logarit rời rạc và bài toán phân tích một số nguyên lớn ra các thừa số nguyên tố, hoặc: bài toán logarit rời rạc và bài toán khai căn. Hoàn toàn có thể khẳng định rằng không có bất kỳ kiểu tấn công nào vào giao thức thành công được mà không phải giải được đồng thời 2 bài toán khó nêu trên, do đó giao thức trao đổi khóa an toàn MTA 01.19 - 01 mới đề xuất có thể phù hợp với các ứng dụng yêu cầu cao về độ an toàn trong thực tế. TÀI LIỆU THAM KHẢO [1]. W. Diffie & M. Hellman, “New Directions in Cryptography”, IEEE Trans. On Info. Theory, IT-22(6):644-654, 1976. [2]. T. ElGamal, “A public key cryptosystem and a signature scheme based on discrete logarithms”, IEEE Transactions on Information Theory 1985, Vol. IT-31, No. 4. pp.469–472. [3]. Mark Stamp, Richard M. Low,“Applied cryptanalysis: Breaking Ciphers in the Real World”, John Wiley & Sons, Inc., ISBN 978-0-470-1. [4]. Eddie Shahrie Ismail, Tahat N.M.F., Rokiah. R. Ahmad, “A New Digital Signature Scheme Based on Factoring and Discrete Logarithms”, Journal of 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, 04 - 2019 15 Mathematics and Statistics, 04/2008; 12(3). DOI: 10.3844/jmssp.2008.222.225 Source:DOAJ. [5]. Qin Yanlin, Wu Xiaoping,“New Digital Signature Scheme Based on both ECDLP and IFP”, Computer Science and Information Technology, 2009. ICCSIT 2009. 2nd IEEE International Conference on, 8-11 Aug. 2009, E- ISBN : 978-1-4244-4520-2, pp 348 - 351. [6]. Swati Verma1, Birendra Kumar Sharma, “A New Digital Signature Scheme Based on Two Hard Problems”, International Journal of Pure and Applied Sciences and Technology, ISSN 2229 – 6107, Int. J. Pure Appl. Sci. Technol., 5(2) (2011), pp. 55-59. [7]. Sushila Vishnoi, Vishal Shrivastava, “A new Digital Signature Algorithm based on Factorization and Discrete Logarithm problem”, International Journal of Computer Trends and Technology, volume 3, Issue 4, 2012. [8]. A.N. Berezin, N.A. Moldovyan, V.A. Shcherbacov, “Cryptoschemes Based on Difficulty of Simultaneous Solving Two Different Difficult Problems”, Computer Science Journal of Moldova, vol.21, no.2(62), 2013. [9]. Lưu Hồng Dũng, Trần Trung Dũng, Tống Minh Đức, “Nghiên cứu xây dựng hệ tích hợp mật mã khóa công khai - chữ ký số”, Tạp chí Khoa học và Kỹ thuật (Học viện KTQS), số 149 (08-2012). ISSN: 1859 - 0209., 01/08/2012. [10]. 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 (08/2017), trang 147 - 152 . ISSN: 1859 - 1043. [11]. National Institute of Standards and Technology, NIST FIPS PUB 186-4. Digital Signature Standard, U.S. Department of Commerce, 2013. [12]. R. L. Rivest, A. Shamir, and L. M. Adleman, “A Method for Obtaining Digital Signatures and Public Key Cryptosystems”, Commun. of the ACM, Vol. 21, No. 2, 1978, pp. 120-126. ABSTRACT THE KEY EXCHANGE PROTOCOL BASED ON TWO HARD PROBLEMS FOR SECRET - KEY CRYPTOSYSTEMS The paper proposes to build a protocol for exchanging security keys for symmetric key encryption systems from the difficulty level of solving two problems simultaneously: Discrete Logarithm and Factorization/Root problems. The new protocol proposes to ensure the properties of a secure key exchange protocol, and the shared secret key is authenticated to the origin, so it can withstand fake key attacks, secret keys-share is works effectively. Keywords: Discrete Logarithm; Factorization; Root Problems; Key Establishment; Key Agreement Protocols; Key Exchange Protocol; Key Transport Protocols. Nhận bài ngày 04 tháng 12 năm 2018 Hoàn thiện ngày 10 tháng 3 năm 2019 Chấp nhận đăng ngày 25 tháng 3 năm 2019 Địa chỉ: 1 Viện CNTT, Viện KH và CNQS; 2 Khoa CNTT, Học viện KTQS. * Email: luuhongdung@gmail.com.