Đề xuất thuật toán sinh số giả ngẫu nhiên có chu kỳ cực đại bằng phương pháp đồng dư tuyến tính

Kỹ thuật điều khiển & Điện tử L. H. Triều, T. X. Ban, “Đề xuất thuật toán sinh số phương pháp đồng dư tuyến tính.” 106 ĐỀ XUẤT THUẬT TOÁN SINH SỐ GIẢ NGẪU NHIÊN CÓ CHU KỲ CỰC ĐẠI BẰNG PHƯƠNG PHÁP ĐỒNG DƯ TUYẾN TÍNH Lê Hải Triều1*, Trần Xuân Ban2 Tóm tắt: Bài báo đề xuất phương pháp sinh dãy số giả ngẫu nhiên có chu kỳ cực đại dựa trên phương pháp đồng dư tuyến tính. Mục đích là thỏa thuận khóa hiệu quả đơn giản, dùng trong liên lạc mật dựa trên phương pháp đồng dư tuyến tính. Khóa tạo ra có chu kỳ cực đại, không có chu kỳ con. Từ khóa: Sinh số giả ngẫu nhiên; Đồng dư tuyến tính. 1. MỞ ĐẦU Việc sinh số ngẫu nhiên có nhiều ý nghĩa trong thực tiễn, đặc biệt trong lĩnh vực bảo mật thông tin, chẳng hạn các khóa mã đòi hỏi phải được chọn một cách ngẫu nhiên, nhằm chống lại các tấn công vét cạn (brute force) [1, 2, 3]. Hiện nay, một hệ mật mã được cho là an toàn nếu không gian khóa là đủ lớn và việc chọn khóa trong đó phải là ngẫu nhiên theo nghĩa độc lập, đồng xác suất [5, 6, 7]. Tuy nhiên, việc sinh số hoàn toàn ngẫu nhiên bằng các thuật toán là rất khó khăn, tốn kém [8]. Bài báo này trình bày thuật toán sinh số giả ngẫu nhiên bằng phương pháp đồng dư tuyến tính, dãy số được tạo ra tuần hoàn, có chu kỳ cực đại và không tồn tại chu kỳ con trong khoảng chu kỳ cực đại đó. 2. ĐẶT BÀI TOÁN Xét phương trình đồng dư tuyến tính 1 có dạng sau: modax b n (1) với , ,a b n là các tham số nguyên, trong đó 2n  Để giải phương trình (1) ta áp dụng các định lý sau: 2.1. Định lý 1 Gọi gcd  , 1a n d  là hàm trả về ước số chung lớn nhất của a và n, khi đó: a) Phương trình (1) có d nghiệm phân biệt nếu b chia hết cho d (ký hiệu |d b ). b) Phương trình (1) vô nghiệm nếu b không chia hết cho d (ký hiệu ∤ b). Để chứng minh Định lý 1 ta áp dụng bổ đề sau: 2.1.1. Bổ đề: Cho trước 2 số nguyên không âm a và n ( 2)n  , khi đó, a là khả đảo theo mod n nếu và chỉ nếu gcd ( , ) 1a n  , tức là a và n nguyên tố cùng nhau. 2.1.2. Chứng minh bổ đề: Thật vậy, giả sử ngược lại rằng gcd ( , )a n d , 1d  và có tồn tại một (0, )b n sao cho ab mod n = 1 hay viết cách khác ab  1 mod n. Từ gcd ( , )a n d suy ra 1a a d ; 1n n d ; trong đó, 1a và 1n là hai số nguyên nào đó. Vậy (1) có thể viết thành các phương trình sau: a1db  1 mod n1d (2) hay 1 11ba d kn d  với k là số nguyên nào đó (3) Từ (3) suy ra 1 1 1ba d kn d  hay 1 1( ) 1d ba kn  1 Phương trình đồng dư dạng (mod )ax b m được gọi là phương trình đồng dư tuyến tính với , ,a b m là các số đã biết. 0x là một nghiệm của phương trình khi và chỉ khi 0 (mod )ax b m . Nếu 0x là một nghiệm của phương trình thì các phần tử thuộc lớp 0x cũng là nghiệm [4]. Nghiên cứu khoa học công nghệ Tạp chí Nghiên cứu KH&CN quân sự, Số 55, 06 - 2018 107 Điều này là không xảy ra nếu 1d  , nó chỉ xảy ra khi và chỉ khi 1d  vì 1 1( )ba kn là một số nguyên. Vậy Bổ đề 1 là đúng. 2.1.3. Chứng minh Định lý 1 * Trường hợp 1: gcd ( , )a n d nếu |b d . Khi đó phương trình (1) có thể viết như sau: 1 1 1moda dx b d n d (4) với 1 1 1, ,a b n là những số nguyên nào đó. Áp dụng tính chất (hệ quả) của phép toán đồng dư từ (4) ta suy ra phương trình: 1 1 1moda x b n (5) Do gcd 1 1( , ) 1a n  (vì gcd ( , )a n d ) nên theo bổ đề 1 có tồn tại 1 1 1moda n  , mà 1 0 1 1modx a n  là nghiệm duy nhất của phương trình (5) với 0 10 x n  Vì 1 1 .. 1d     nên phương trình (1) có d nghiệm phân biệt là: ( ) ( ) modj b nx x j n d d      , với     11mod moda nx a nd d    Như vậy ta có d giá trị của x với 0 1 modx x jn n  ; ( 0,1, 2,.., 1j d  ) là nghiệm của (1) và chúng khác nhau theo modulo n. Trường hợp 1 được giải quyết. * Trường hợp 2: b không chia hết cho d ( ∤ b) Theo Định lý 1 ta sẽ xây dựng dãy số giả ngẫu nhiên. Bài toán đặt ra hãy xây dựng dãy giả ngẫu nhiên  , 0nx n  sao cho chu kỳ của dãy là lớn nhất có thể, tức là  nx là m dãy. Ta có dãy 1 ( ) modn nx ax b m   , trong đó 0 , , ,x a b m cho trước sao cho  0max , ,m x a b . Rõ ràng dãy {}, ≥0 phụ thuộc vào 4 tham số 0, , ,a b x m . Dãy này tuần hoàn và cho chu kỳ R m , tùy thuộc vào việc chọn ,a b và 0x . Mục tiêu của bài toán là hãy xác định các tham số ,a b và 0x để R m . Chứng minh trường hợp 2 như sau: Theo trường hợp 1, nếu b chia hết cho d, thì có thể viết lại d = gcd (a,n). Do dó, giả thiết tồn tại một số nguyên x0 thỏa mãn phương trình (1). Vì gcd(a,n) = d >1, nên phương trình (1) có thể được viết như sau: a1dx0 ≡ b mod (n1d) Trong đó, a1, b1 là những số nguyên. Từ đó, ta suy ra: a1dx0 = b + kn1d với k là một số nguyên nào đó. Ta có: a1dx0 - kn1d = b, hay (a1x0 - kn1)d = b. Suy ra a1x0 - kn1= b/d là số nguyên. Tuy nhiên, do trường hợp 2 chúng ta đã chọn b không chia hết cho d nên b/d không phải là số nguyên, trong khi đó, theo chứng minh trên, a1x0 - kn1 là một số nguyên. Kết quả này mâu thuẫn với giả thiết trên. Vậy không tồn tại nghiệm nguyên x0 thỏa mãn phương trình đồng dư (1). Trường hợp thứ 2 được chứng minh. 2.2. Định lý 2 Để dãy {}, ≥0 được xác định trong (1) có chu kỳ R m phải thỏa mãn đồng thời 3 điều kiện sau: i)  , 1b m  ; Kỹ thuật điều khiển & Điện tử L. H. Triều, T. X. Ban, “Đề xuất thuật toán sinh số phương pháp đồng dư tuyến tính.” 108 ii) 1a  là bội của p với mọi ước nguyên tố p của m với 2p  , trong đó p là một ước của m ; iii) 1a  là bội của 4 nếu m là bội của 4. 2.2.1. Ví dụ Xét 0 3x  , 13a  , 7b  và 105m  . Ta có ( , ) (7,105) 1b m   ; 1 12a   là bội của 2,3, 4,6 (trường hợp này 2p  ); 1 12a   là bội của 4 ; nhưng 105m  không phải là bội của 4. 2.2.2. Chứng minh Định lý 2 Ta xét phương trình đồng dư tuyến tính có dạng: modx ax b m  (6) hay (a – 1)x  - b mod m (7) Từ điều kiện (ii) ta suy ra rằng: ( 1, ) 1a m p   Trong lúc đó, theo (i) ta có: ( , ) 1b m p  Từ đó (6) hoặc tương đương với (7) vô nghiệm với xn ≠ xn+1 trong khoảng (0,m). Tức là không tồn tại một 0n  sao cho: ( ) modn nx ax b m  đối với 1, 2,..,n m  3. VÍ DỤ Các định lý trên là cơ sở lý thuyết để chúng ta xây dựng dãy giả ngẫu nhiên với chu kỳ lớn tùy ý. Sau đây là hai ví dụ có tính chất thực hành. 3.1. Ví dụ 1 Cho y0 = 3; a = 7; b = 5; m = 27 Khi đó áp dụng công thức yn+1 = ayn + b mod m = 7yn + 5 mod 27 ta có: n yn ayn yn+1 = ayn + b mod m 0 3 21 26 1 26 182 25 2 25 175 18 3 18 126 23 4 23 161 4 5 4 28 6 6 6 42 20 7 20 140 10 8 10 70 21 9 21 147 17 10 17 119 16 11 16 112 9 12 9 63 14 13 14 98 22 14 22 154 24 15 24 168 11 16 11 77 1 Nghiên cứu khoa học công nghệ Tạp chí Nghiên cứu KH&CN quân sự, Số 55, 06 - 2018 109 17 1 7 12 18 12 84 8 19 8 56 7 20 7 49 0 21 0 0 5 22 5 35 13 23 13 91 15 24 15 105 2 25 2 14 19 26 19 133 3 27 3 21 26 Nếu đổi sang chữ cái với 0 = A, 1 = B,.., 25 = Z thì sẽ được dãy: ZSYEG UKVRQ JOWYL BMIHA FNPCT ( số 26 tương ứng với số 0 ) 3.2. Ví dụ 2 Cho y0 = 3; a = 3; b = 3; m = 1024 Rõ ràng các tham số y0, a, b, m thỏa mãn 3 điều kiện của Định lý 2 ở trên. Thật vậy: - Điều kiện (i): ( , ) (3,1024) 1b m   ; - Điều kiện (ii): 1 12 3.4a    , ở đây 2p  - Điều kiện (iii): 1 12 3.4a    là bội của 4 mà 1024 4.256m   là bội của 4. Khi đó áp dụng công thức yn+1 = ayn + b mod m ta có: n yn ayn yn+1 = ayn + b mod m 0 3 39 42 1 42 546 549 2 549 7137 996 3 996 12948 663 4 663 8619 430 5 430 5590 473 6 473 6149 8 7 8 104 107 8 107 1391 370 9 370 4810 717 10 717 9321 108 11 108 1404 383 12 383 4979 886 13 886 11518 257 14 257 3341 272 15 272 3536 467 16 467 6071 954 Kỹ thuật điều khiển & Điện tử L. H. Triều, T. X. Ban, “Đề xuất thuật toán sinh số phương pháp đồng dư tuyến tính.” 110 17 954 12402 117 18 117 1521 500 19 500 6500 359 20 359 4667 574 21 574 7462 297 22 297 3861 792 23 792 10296 59 24 59 767 770 25 770 10010 797 26 797 10361 124 27 124 1612 591 28 591 7683 518 29 518 6734 593 30 593 7709 544 31 544 7072 931 32 931 12103 842 33 842 10946 709 34 709 9217 4 Lấy các số đầu tiên của dãy ta được: 4, 5, 9, 6, 4, 4, 8, 1, 3, 7, 1, 3, 8, 2, 2, 4, 9, 1, 5, 3, 5, 2, 7, 5, 7, 7, 1, 5, 5, 5, 5, 9, 8, 7, 4. Chuyển sang dạng ký tự với bảng mã quy định như trong Ví dụ 1 ta được chuỗi: EFJGE EIBDH BDICC EJBFD FCHFH HBFFF FJIHE . 4. KẾT LUẬN 4.1. Kết luận 1 Từ công thức 1 modn nx ax b m   ta tìm công thức truy hồi như sau: 1 0 modx ax b m  2 1 0mod ( mod ) modx ax b m a ax b m b m     2 2 0 ( 1) modx a x a b m   2 3 2 0mod ( ( 1) mod ) modx ax b m a a x a b m b m      3 2 3 0 ( 1) modx a x a a b m    ... 1 2 1 1 0 ( .. 1) mod n n n nx a x a a a b m         (8) Như vậy việc trao đổi khóa bí mật, đơn thuần chỉ là trao đổi 4 tham số 0 , , ,x a b m . 4.2. Kết luận 2 Việc tạo dãy số giả ngẫu nhiên vừa được trình bày trong bài báo có một số ưu điểm như sau: - Chu kỳ R của dãy được kiểm soát nếu thực hiện đúng giả thiết của Định lý 2. Nghiên cứu khoa học công nghệ Tạp chí Nghiên cứu KH&CN quân sự, Số 55, 06 - 2018 111 - Việc trao đổi khóa rất đơn giản, chỉ là 4 tham số 0 , , ,x a b m . Tùy theo yêu cầu của ứng dụng để chọn số m cho phù hợp. Hơn nữa thuật toán sinh dãy giả ngẫu nhiên rất đơn giản chỉ áp dụng theo công thức (8). Đây là công thức truy hồi để tìm dãy {} với 2n  . - Trường hợp muốn chuyển sang dãy bit giả ngẫu nhiên, chúng ta chú ý đến số tự nhiên đầu tiên của các số trong dãy: số lẻ được gán cho số 1 và chẵn được gắn cho số 0. Ví dụ: 81, 15, 27, 31, 24, 01010 4.3. Kết luận 3 Nội dung nghiên cứu có ý nghĩa thực tiễn cho an ninh quốc phòng. Chủ yếu sử dụng cho bài toán trao đổi khóa mật mã, mà hiện nay vấn đề trao đổi khóa mật mã chủ yếu dựa trên các hệ mật mã khóa công khai. Trong lúc đó, cho đến nay chưa có một công bố nghiêm túc về độ an toàn thực tế của các Hệ mật mã khóa công khai. Mặt khác, việc sử dụng các Hệ mật mã khóa công khai để trao đổi khóa mật tỏ ra “cồng kềnh” và tốn nhiều bộ nhớ máy tính [9,10]. Trong quá trình nghiên cứu tiếp theo, nhằm đảm bảo an toàn, các tham số x0 , a, b, m trong thuật toán nêu trên chúng tôi sẽ cứng hóa và đưa vào thử nghiệm trên các hệ thống truyền ảnh kỹ thuật số thông qua kênh truyền online và trình bày trong nội dung nghiên cứu tiếp theo. TÀI LIỆU THAM KHẢO [1]. Alfred J. Menezes, Paul C. van Oorschot, Scott A. Vanstone, “Handbook of Applied Cryptography”, CRC Press: Boca Raton, New York, London, Tokyo, 1999. [2]. Andreas Klein, “Stream Ciphers”, Springer London Heidelberg, New York Dordrecht, 2013. [3]. D. L. Kreher and D.R. Stison, “Combinatorial Algorithms: Generation Enumeration and Search”, CRC Press, 1999. [4]. E. Bach, “Realistic Analysis of some Randomized Algorithms”, Journal of Computer and System Sciences, 2005. [5]. H. Fukumasa , R. Kohno and H. Imai, “Design of pseudonoise sequences with good odd and even correlation properties for DS/CDMA”, IEEE Journal on Selected Areas in Communications, Volume 12, Issue 5, Jun 1994. [6]. Daniel J. Bernstein. “The Salsa20 family of stream ciphers”. In Matthew Robshaw and Olivier Billet, editors, New Stream Cipher Designs, volume 4986 of Lecture Notes in Computer Science, pages 84–97. Springer Berlin Heidelberg, 2008. [7]. M. Blum and S. Micali, “How to generate cryptographycally strong sequences of pseudorandom bits”, SIAM Journal on Computing, Volume 13, Issue 4, pp. 850– 864, 2006. [8]. S. Micali , C. P. Schnorr, “Efficient, perfect polynomial random number generators”, Journal of Cryptology, v.3 n.3, p.157-172, January 1991. [9]. U. Baum, S. Blackburn, “Clock-controlled pseudorandom generators on finite groups”, pp 6–21, BPreneel, editor (LNSC 1008), Springer- Verlag, 1995. [10]. U. Maurer, J. L. Massey, “Local Randomness in Pseudorandom Sequences”, Journal of Cryptology: the journal of the International Association for Cryptologic Research Volume 4, Number 2, 1991. Kỹ thuật điều khiển & Điện tử L. H. Triều, T. X. Ban, “Đề xuất thuật toán sinh số phương pháp đồng dư tuyến tính.” 112 ABSTRACT PROPOSED ALGORITHM GENERATING PSEUDO-RANDOM NUMBER WITH MAXIMUM CYCLE BY USING LINEAR CONGURENCE METHOD In the paper, a algorithm for generating pseudo-random numbers with maximum cycles based on linear congruence method is proposesed. The goal is a simple, effective key agreement, used for confidential communications based on linear congruence method. The key has maximum cycles, with no cycles. Keywords: Pseudorandom number; Linear congruential equation. Nhận bài ngày 27 tháng 3 năm 2018 Hoàn thiện ngày 11 tháng 4 năm 2018 Chấp nhận đăng ngày 08 tháng 6 năm 2018 Địa chỉ: 1 Viện Kỹ thuật điện tử và cơ khí nghiệp vụ, Tổng cục 4, Bộ Công an; 2 Trường Đại học Kỹ thuật – Hậu cần, Bộ Công an. * Email: lht295@gmail.com.