Đề 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

Bài viết đề 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.
Nội dung trích xuất từ tài liệu:
Đề 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ử ĐỀ 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: ax  b mod n (1) với a, b, n là các tham số nguyên, trong đó n  2 Để giải phương trình (1) ta áp dụng các định lý sau: 2.1. Định lý 1 Gọi gcd  a, n   d  1 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 ( n  2) , khi đó, a là khả đảo theo mod n nếu và chỉ nếu gcd (a, n)  1 , 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 , d  1 và có tồn tại một b  (0, 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 a  a1d ; n  n1d ; trong đó, a1 và n1 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 ba1d  1  kn1d với k là số nguyên nào đó (3) Từ (3) suy ra ba1d  kn1d  1 hay d (ba1  kn1 )  1 1 Phương trình đồng dư dạng ax  b(mod 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. x0 là một nghiệm của phương trình khi và chỉ khi ax0  b(mod m) . Nếu x0 là một nghiệm của phương trình thì các phần tử thuộc lớp x0 cũng là nghiệm [4]. 106 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.” Nghiên cứu khoa học công nghệ Điều này là không xảy ra nếu d  1 , nó chỉ xảy ra khi và chỉ khi d  1 vì (ba1  kn1 ) 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: a1dx  b1d mod n1d (4) với a1 , b1 , n1 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: a1 x  b1 mod n1 (5) Do gcd ( a1 , n1 )  1 (vì gcd (a, n)  d ) nên theo bổ đề 1 có tồn tại a11 mod n1 , mà x0  a11 mod n1 là nghiệm duy nhất của phương trình (5) với 0  x0  n1 Vì d  1  1  ..  1 nên phương trình (1) có d nghiệm phân biệt là:  d d   d   x j  ( b ) x  j ( n )  mod n , với x  a mod n  a11 mod n d Như vậy ta có d giá trị của x với x  x0  jn1 mod n ; ( j  0,1, 2,.., d  1 ) 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  xn  , n  0 sao cho chu kỳ của dãy là lớn nhất có thể, tức là  xn  là m dãy. Ta có dãy xn 1  ( axn  b) mod m , trong đó x0 , a, b, m cho trước sao cho m  max  x0 , a, b . Rõ ràng dãy { }, ≥0 phụ thuộc vào 4 tham số a, b, x0 , 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à x0 . Mục tiêu của bài toán là hãy xác định các tham số a, b và x0 để 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)  b, m   1 ; Tạp chí Nghiên cứu KH&CN quân sự, Số 55, 06 - 2018 107  Kỹ thuật đi ...