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