Xây dựng các thuật toán mật mã khóa công khai 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 - Nguyễn Vĩnh Thái

Công nghệ thông tin N. V. Thái, L. H. Dũng, “Xây dựng các thuật toán mật mã và phân tích số/khai căn.” 24 XÂY DỰNG CÁC THUẬT TOÁN MẬT MÃ KHÓA CÔNG KHAI 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 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 thuật toán mật mã khóa công khai 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. 02 thuật toán mới đề xuất đảm bảo mức độ an toàn trước các tấn công: làm lộ khóa bí mật, thám mã bản tin. Đồng thời xác thực nguồn gốc văn bản điện tử, cũng như đảm bảo việc xác thực người gửi. Từ khóa: Logarit rời rạc; Phân tích số; Khai căn; Thuật toán khóa mật mã; Hệ thống mã khóa khóa công khai. 1. ĐẶT VẤN ĐỀ Hiện tại, RSA [1] vẫn đang được sử dụng trong các giao dịch điện tử (Chính phủ điện tử, thương mại điện tử...) do tính mềm dẻo và độ an toàn của nó. Tuy nhiên, thuật toán hệ mật này cũng có một nhược điểm căn bản so với các hệ mật được xây dựng trên bài toán logarit rời rạc (ElGamal, DSA, GOST R34.10-94...) [3] đó là các thực thể đầu cuối không được phép dùng chung modulo n với nhau. Nói cách khác: mỗi thực thể đầu cuối phải sở hữu một cặp tham số (, ) nguyên tố riêng biệt. Hơn nữa, cặp tham số này phải được giữ bí mật tuyệt đối. Trên thực tế, việc tạo ra các số nguyên tố lớn và mạnh theo các tiêu chuẩn an toàn (FIPS 186 - 4) [2] và giữ bí mật tuyệt đối cho chúng là không đơn giản, nên nhược điểm trên đã ảnh hưởng không nhỏ đến khả năng ứng dụng rộng rãi của hệ mật này (RSA) trong thực tế. Nâng cao độ an toàn cho các thuật toán mật mã khóa công khai dựa trên tính khó của việc giải đồng thời 2 bài toán khó là một hướng tiếp cận đang nhận được nhiều sự quan tâm của các nhà nghiên cứu [4 - 9]. Cũng với mục đích nâng cao độ an toàn cho thuật toán trước một số dạng tấn công trong thực tế, nhóm tác giả bài báo này đề xuất xây dựng 02 thuật toán: mật mã khóa công khai; mã hóa - xác thực 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 phép nhiều người dùng (thực thể cuối) sử dụng chung một , nghĩa là chỉ cần tạo ra một cặp tham số (, ) duy nhất cho tất cả các thực thể cuối. Ngoài ra, các tham số này không cần phải được giữ bí mật như ở hệ RSA mà vẫn có thể chống lại các dạng tấn công đã biết trong thực tế, đảm bảo độ an toàn của hệ thống. 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ố. 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 25 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, 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 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 (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: Công nghệ thông tin N. V. Thái, L. H. Dũng, “Xây dựng các thuật toán mật mã và phân tích số/khai căn.” 26 = DLP(,)() Bài toán DLP(,) là cơ sở để xây dựng nên hệ mật ElGamal. Hiện tại chưa có giải thuật hiệu quả 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 THUẬT TOÁN MẬT MÃ KHÓA CÔNG KHAI 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 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 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) 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. Thuật toán mật mã khóa công khai Thuật toán mật mã được đề xuất ở đây bao gồm thuật toán mã hóa (Thuật toán MTA 01.19-02) và giải mã (Thuật toán MTA 01.19-03) với các tham số hệ thống được hình thành theo (1) và khóa hình thành theo (2). Giả thiết người gửi/mã hóa là A, người nhận/giải mã là B và B có cặp khóa bí mật/công khai tương ứng là 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 27 (, , ), trong đó: được chọn ngẫu nhiên trong khoảng (1, ), còn (, ) được tính theo (1) và (2) như sau: = , = () () (3) a) Thuật toán mã hóa (MTA 01.19 - 02) Input: p, q , g, , , M. Output: , . Bước 1. Biểu diễn bản tin cần mã hóa M thành một giá trị m tương ứng trong khoảng [1, − 1], chọn ngẫu nhiên một giá trị trong khoảng (1, ) rồi tính thành phần thứ nhất của bản mã: = × () (4) Bước 2. Tính thành phần thứ 2 của bản mã: = ( ) (5) Bước 3. Gửi bản mã (, ) cho B. b) Thuật toán giải mã (MTA 01.19 - 03) Input: p, q , g, , , , (C, R). Output: . Bước 1. B sử dụng khóa bí mật thứ hai để tính theo: = () (6) Bước 2. Người nhận sử dụng khóa bí mật thứ nhất của mình để giải mã bản tin nhận được: = × () (7) Bước 3. Chuyển giá trị thành bản tin M. c) Tính đúng đắn của thuật toán Điều cần chứng minh ở đây là: Cho p, q, , là các số nguyên tố thỏa mãn: |(p − 1), n = p × q, > , 1 < < , = , 1 < < , = , = () (), 1 < < , 0 ≤ ≤ − 1, = × () , = ( ) Nếu: = () , = × () thì = Chứng minh: Từ (3), (5) và (6) ta có: = () = (( ) ) = . = (8) Nên từ (3), (4), (7) và (8) ta có điều cần chứng minh: = × () = × × ( ) = × . × . = 3.3. Độ an toàn của thuật toán MTA 01.19 - 02; MTA 01.19 - 03 a) Tấn công khóa bí mật Công nghệ thông tin N. V. Thái, L. H. Dũng, “Xây dựng các thuật toán mật mã và phân tích số/khai căn.” 28 Ở thuật toán mới đề xuất, tính an toàn của lược đồ sẽ bị phá vỡ khi cặp khóa , có thể tính được bởi một hay các đối tượng không mong muốn. Từ Thuật toán 2 cho thấy, để tìm được cần phải giải được (), còn để tính được cần phải giải được DLP(,). Nói một cách khác, độ an toàn về khóa của thuật toán được đảm bảo bằng độ khó của việc giải đồng thời 2 bài toán () và DLP(,). b) Tấn công thám mã bản tin Để giải mã bản tin có thể thực hiện tấn công vào thuật toán mã hóa hoặc giải mã như sau: - Tấn công thuật toán mã hóa Có thể giải mã bản tin nếu tính được trong (4) theo 2 cách: Cách thứ nhất: giải được bài toán RSAP(,) để tìm X = RSAP(,)(), sau đó phải giải tiếp bài toán DLP(,) để tìm k = DLP(,)(). Cách thứ hai: giải bài toán () để tìm để tìm X = () , sau đó giải tiếp DLP(,) để tìm k như cách thứ nhất. Như vậy, để giải mã bản tin bằng cách tấn công trực tiếp vào thuật toán mã hóa, kẻ tấn công cần phải giải được đồng thời hai bài toán RSAP(,) và DLP(,) hoặc () và DLP(,) đã chỉ ra ở trên. Nên độ an toàn của thuật toán trước dạng tấn công này được quyết định bằng độ 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 khai căn, hoặc: bài toán logarit rời rạc và bài toán phân tích số. - Tấn công thuật toán giải mã Để giải mã bản tin bằng cách tấn công vào thuật toán giải mã, kẻ tấn công cần phải tính được các khóa bí mật của người nhận B, nghĩa là phải giải được đồng thời hai bài toán bài toán () và DLP(,). Hay, độ an toàn của thuật toán trước dạng tấn công này được quyết định bằng độ khó của việc giải đồng thời 2 bài toán phân tích số và bài toán logarit rời rạc trên Zp. 3.4. Thuật toán mã hóa - xác thực Thuật toán mã hóa - xác thực được đề xuất ở đây thực hiện đồng thời chức năng bảo mật thông tin và xác thực nguồn gốc cũng như tính toàn vẹn của bản tin được mã hóa, thuật toán được đề xuất bao gồm thuật toán mã hóa (Thuật toán MTA 01.19 - 04) và giải mã (Thuật toán MTA 01.19 - 05), với 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 người gửi/mã hóa là A, người nhận/giải mã là 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, ), (, ) và (, ) được tính theo (1) và (2) như sau: = , = () () (9) = , = () () a) Thuật toán mã hóa (MTA 01.19 - 04) Input: p, q , g, , , , , M. 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 29 Output: , , . Bước 1. Biểu diễn bản tin cần mã hóa M thành một giá trị m tương ứng trong khoảng [1, − 1], chọn ngẫu nhiên một giá trị trong khoảng (1, ) rồi tính thành phần thứ nhất của bản mã: = ( × () ) (10) Bước 2. Tính giá trị: = (11) Bước 3. Tính thành phần thứ hai của bản mã: = (‖) (12) Bước 4. Tính thành phần thứ ba của bản mã: = () × ( + 2 (13) Bước 5. Gửi bản mã (, , ) cho B. b) Thuật toán giải mã (MTA 01.19 - 05) Input: p, q , g, , , , , , , (, , ). Output: , (, ) = /. Bước 1. Người nhận sử dụng khóa bí mật thứ hai để tính ̅ theo: = (14) Bước 2. Tính giá trị: = () (15) và = () × () (16) Bước 3. Từ , giải mã bản tin nhận được: = × () (17) Bước 4. Chuyển giá trị thành bản tin và tính: = (18) Bước 5. Nếu = thì = và khẳng định người gửi chính xác là A. c) Tính đúng đắn của thuật toán MTA 01.19 - 04; MTA 01.19 - 05 Điều cần chứng minh ở đây là: Cho p, q, , là các số nguyên tố thỏa mãn: |(p − 1), n = p × q, > , 1 < < , = , 1 < , < , = , = , = () (), 1 < < , = () (), 0 ≤ ≤ − 1, = , : {0,1}∗ → với |q| ≤ |h| < ||, = (‖) , = × (( + × ) ) () Nếu = , = () , = () × () , = × () , = thì = và = Chứng minh: Từ (9), (10) và (14) ta có: = = (( × () ) ) = × . (19) Công nghệ thông tin N. V. Thái, L. H. Dũng, “Xây dựng các thuật toán mật mã và phân tích số/khai căn.” 30 = ( × ) = × . Từ (9), (13) và (15) ta lại có: = () = (() × ( + ) )) ) (20) = (() × ( + ) )). = () × ( + ) Thay (9) và (20) vào (16) ta được: = () × () = ( )() .() × () = .() .() × = ( × × ) (21) = = Từ (9), (19) và (21) ta suy ra điều cần chứng minh thứ nhất: = × () = × . × ( ) = ( × . × .) = (22) Từ (17), (18), (21) và (22) ta suy ra điều cần chứng minh thứ hai: = = (‖) = 3.5. Độ an toàn của thuật toán MTA 01.19 - 04; MTA 01.19 - 05 Thuật toán mã hóa - xác thực được đề xuất ở đây thực chất là sự kết hợp giữa thuật toán mật mã ở mục 3.2 của bài báo này với thuật toán chữ ký số, nhằm cung cấp tính năng bảo mật nội dung của bản tin và xác thực nguồn gốc cùng với tính toàn vẹn của bản tin được thực hiện một cách đồng thời. Nhờ đó, thuật toán này cho phép chống lại các dạng tấn công giả mạo rất hiệu quả. Có một điểm cần lưu ý là dạng tấn công giả mạo ở đây cần được hiểu theo nghĩa một kẻ thứ 3 (T) muốn mạo danh A để gửi cho B bản tin M hoặc là T gửi một bản tin không phải M cho B trong khi B hiểu rằng A đã gửi bản tin M cho mình. Từ thuật toán kiểm tra cho thấy, điều kiện để B nhận biết chính xác bản tin M được A gửi đến khi nhận được 1 cặp (C,E,S) là: (23) Kẻ tấn công giả mạo có thể thực hiện được (23) nếu thực hiện được các bước tính toán sau: - Chọn giá trị ∗ và tính: = × () ∗ ; 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 31 - Giải bài toán DLP(,) để tìm ∗ từ: () ∗ ≡ ∗ × - Giải bài toán RSAP(,) hoặc () để tìm từ: ∗ = () Tuy nhiên, để thực hiện được các bước tính toán như trên, kẻ tấn công cũng buộc phải giải được đồng thời 2 bài toán toán DLP(,)và RSAP(,) hoặc DLP(,)và (). Như vậy, độ an toàn của thuật toán trước kiểu tấn công giả mạo chữ ký cũng được đảm bảo bằng độ khó của việc giải đồng thời 2 bài toán. Bên cạnh đó nếu (. ) được chọn là hàm băm có tính kháng va chạm cao (SHA 256/512,...) thì việc tạo ngẫu nhiên được cặp (C,E,S) thỏa mãn điều kiện của thuật toán kiểm tra là không khả thi trong các ứng dụng thực tế. 4. KẾT LUẬN Bài báo đề xuất xây dựng thuật toán mã hóa khóa công khai, thuật toán mã hóa - xác thực dựa trên độ khó giải của 2 bài toán khó, các thuật toán được thiết kế để các thực thể cuối trong cùng một hệ thống có thể sử dụng chung một bộ tham số. Qua phân tích đánh giá cho thấy các thuật toán 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 số 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 các thuật toán 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 đó thuật toán mới (MTA 01.19 - 02; 03; 04; 05) đề 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]. 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 [2]. National Institute of Standards and Technology, NIST FIPS PUB 186-4. Digital Signature Standard, U.S. Department of Commerce, 2013. [3]. 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. [4]. Eddie Shahrie Ismail, Tahat N.M.F., Rokiah. R. Ahmad, “A New Digital Signature Scheme Based on Factoring and Discrete Logarithms”, Journal of Mathematics and Statistics, 04/2008; 12(3). [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. Công nghệ thông tin N. V. Thái, L. H. Dũng, “Xây dựng các thuật toán mật mã và phân tích số/khai căn.” 32 [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. ABSTRACT A NEW PUBLIC - KEY CRYPTOGRAPHY ALGORITHM BASED ON TWO HARD PROBLEMS The paper proposes to build a new Public - Key Cryptography algorithm based on two hard problems: Discrete Logarithm and Factorization/Root problems. 02 new algorithms proposed to ensure the level of security against attacks: reveal the secret key, decrypting messages. At the same time verify the origin of documents, as well as ensure the sender authentication. Keywords: Discrete Logarithm; Factorization; Root Problems; Public - Key Cryptography Algorithm; Public - Key CryptoSystem. Nhận bài ngày 19 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: nguyenvinhthai@gmail.com.