Phương pháp tạo dãy giả ngẫu nhiên để ứng dụng trong giao thức mật mã

Kỹ thuật điều khiển & Điện tử 
L. D. Cường, H. V. Canh, V. V. Tùng, “Phương pháp tạo dãy giả  giao thức mật mã.” 98 
PHƯƠNG PHÁP TẠO DÃY GIẢ NGẪU NHIÊN ĐỂ 
ỨNG DỤNG TRONG GIAO THỨC MẬT MÃ 
 Lê Danh Cường1*, Hồ Văn Canh2, Võ Văn Tùng1 
Tóm tắt: Bảo vệ thông tin bằng phương pháp mật mã là giải pháp hữu hiệu hiện 
nay, đặc biệt trong lĩnh vực Quốc phòng - An ninh. Đối với các hệ mật, độ mật phụ 
thuộc chủ yếu vào khóa mã. Bởi vậy vấn đề sinh khóa mã để đảm bảo an toàn cho hệ 
mật luôn mang tính thời sự và thực tiễn trong lĩnh vực bảo mật thông tin hiện nay. Có 
hai phương pháp sinh khóa cơ bản là sinh khóa ngẫu nhiên và phương pháp sinh 
khóa giả ngẫu nhiên. Tuy nhiên, hiện nay bài toán sinh khóa giả ngẫu nhiên đang 
được quan tâm nghiên cứu nhiều hơn. Nội dung bài báo sẽ trình bày phương pháp tạo 
dãy giả ngẫu nhiên mới, sử dụng thuật toán sinh các bit ngẫu nhiên dựa trên tổ hợp 
các thanh ghi dịch phản hồi tuyến tính (LFSR) đáp ứng yêu cầu nâng cao độ an toàn 
của khóa mã sử dụng trong các hệ mật mã đối với lĩnh vực ANQP. 
Từ khóa: Bit giả ngẫu nhiên, Thanh ghi dịch NFSR, Bộ tạo bit giả ngẫu nhiên, Mật mã, Thám mã; 
1. ĐẶT VẤN ĐỀ 
Khi sử dụng giải pháp bảo vệ thông tin bằng mật mã, một câu hỏi đặt ra là “độ an toàn 
của thông tin được khẳng định như thế nào khi ứng dụng kỹ thuật mật mã ?”. Ta biết rằng, 
sự an toàn của thông tin hoàn toàn phụ thuộc vào độ an toàn của hệ mật sử dụng, tức là 
phụ thuộc vào hai yếu tố là khóa mã và thuật toán mã hóa. Trong các giao dịch thương mại 
điện tử, thường các thuật toán mã hóa được công khai, bởi vật độ an toàn của thông tin 
hoàn toàn chỉ còn phụ thuộc vào độ an toàn của khóa mã. Đối với các hệ mật sử dụng khóa 
giả ngẫu nhiên, để tạo ra khóa mã cho mỗi phiên liên lạc người ta phải cung cấp một “số 
ngẫu nhiên ban đầu” cho thuật toán sinh khóa, trong quá trình mã hóa thuật toán mã hóa sẽ 
tạo ra khóa mã dịch cho phiên liên lạc đó. Số ngẫu nhiên ban đầu cung cấp cho hệ mật 
được gọi là “Mầm khóa” (Key Seed). Như vậy có thể nói, độ an toàn của hệ mật sẽ phụ 
thuộc vào mầm khóa và thuật toán sinh khóa. 
Giả sử trong trường hợp mã thám biết thuật toán sinh khóa, khi đó độ mật của hệ mật 
sẽ chỉ còn phụ thuộc vào mầm khóa. Do mầm khóa là dãy bit có độ dài hữu hạn, bởi vậy 
việc tấn công khai thác mầm khóa mã thám thường sử dụng tấn công vét cạn. Đối với tấn 
công vét cạn, thời gian tấn công sẽ phụ thuộc vào độ dài của mầm khóa. Để chống lại tấn 
công vét cạn người ta buộc phải nâng độ dài của mầm khóa. Điều này dẫn đến lực lượng 
của không gian cung cấp mầm khóa phải đủ lớn để chống lại tấn công. Để chống lại các 
tấn công vét cạn để tìm khóa đúng, không gian mầm khóa phải “đủ lớn” và việc chọn mầm 
khóa để sinh khóa phải hoàn toàn ngẫu nhiên. Tuy nhiên, không gian mầm khóa được thể 
hiện qua độ dài khóa, độ dài khóa càng dài thì không gian khóa càng lớn. Nếu độ dài mầm 
là k thì lực lượng không gian mầm sẽ là 2k khóa mầm. 
Một số ví dụ điển hình chứng minh điều nhận xét ở trên: 
- Đối với chuẩn mã hóa DES độ dài mầm khóa là 56 bit, không gian khóa của DES có 
lực lượng là 256. Khi mới ra đời, không gian khóa như vậy là đủ lớn để có thể chống lại tấn 
công vét cạn tìm khóa đúng. Tuy nhiên, do sự phát triển của công nghệ tính toán ngày nay, 
độ dài khóa như vậy chưa đủ để chống lại khả năng vét cạn của các cơ quan mã thám. 
- Hiện nay, thay vì DES, người ta sử dụng mật mã AES (Advance Encryption 
Standard) có độ dài mầm khóa đến 256 bit, tức là không gian khóa có lực lượng 2256=1664 
và người ta tin tưởng rằng việc tấn công vét cạn là khó khả thi trừ phi có sự phát triển tính 
toán tiềm năng của thế hệ máy tính mới. 
Nghiên cứu khoa học công nghệ 
Tạp chí Nghiên cứu KH&CN quân sự, Số 50, 08 - 2017 99
Đối với mã thám khi không khai thác được mầm khóa và thuật toán sinh khóa, họ sẽ 
tìm cách tấn công trực tiếp vào bản mã dựa trên thuật toán mã hóa. 
Một trong những ví dụ điển hình tấn công thuật toán mã hóa trên bản mã là thuật toán 
IDEA (International Data Encryption Algorithm), thuật toán này sử dụng độ dài mầm khóa 
128 bit, gọi là “đủ lớn” hiện nay, tương đương với không gian khóa là 2128 phần tử, tức là 
1632 phần tử. Tuy nhiên, do đây là thuật toán mã khối (block), với thông báo rõ được chia 
thành từng khối 8 ký tự, mỗi khối cùng một khóa mã cho trước. Thuật toán sẽ mã lần lượt 
khối đầu tiên cho đến khối cuối cùng. Nếu coi mỗi block gồm 8 ký tự là một thông báo thì 
thuật toán mã trùng khóa (khóa có lặp lại). Ở đây, có hai điểm mã thám sẽ sử dụng để tấn 
công bản mã. Đó là: 
- Khi viết dọc khối thứ nhất trên khối thứ hai; khối thứ hai trên khối thứ 3,.v.v. cho đến 
khối cuối cùng, sau đó tính tần số xuất hiện các ký tự theo cột (có 8 cột tất cả) sẽ phát hiện 
ra một số quy luật giúp cho tấn công. 
- Trong thuật toán mã hóa có sự tương ứng 1-1 giữa khối rõ với khối mã. Nhưng số các 
khối rõ gồm 8 ký tự có thể có đối với ngôn ngữ tiếng Anh là 268, do đó số các khối mã 
tương ứng nhiều nhất là 826 và không gian khóa thực tế nhiều nhất là 826 khóa có thể có. 
Từ đó, nếu có một thuật toán thực hiện phân hoạch không gian khóa 21 KKK  ; Trong 
đó,   21 KK thì khả năng tìm khóa đúng trong lớp gồm 
826 khóa (chẳng hạn K1) có 
thể khả thi. 
Qua các kết quả công bố trong và ngoài nước mà nhóm tác giả được tiếp cận, cũng như 
việc phân tích ở trên, có thể thấy rằng độ mật của hệ mật phụ thuộc vào độ an toàn của 
khóa mã dịch, hay nói một cách khác là phụ thuộc vào độ dài của mầm khóa và độ phức 
tạp của thuật toán sinh khóa. 
Do vậy, việc nghiên cứu sinh khóa giả ngẫu nhiên sử dụng trong mật mã đóng vai trò 
rất quan trọng. Bài báo đã tìm hiểu một số thuật toán tạo dãy giả ngẫu nhiên đã được công 
bố trong và ngoài nước, trên cơ sở nghiên cứu nhóm tác giả đưa ra một thuật toán tạo khóa 
giả ngẫu nhiên đáp ứng cho yêu cầu bảo mật Quốc phòng - An ninh hiện nay bằng mật mã. 
2. MỘT SỐ KHÁI NIỆM CƠ SỞ 
2.1. Một số định nghĩa 
Định nghĩa 1: Một thuật toán sinh bit giả ngẫu nhiên được gọi là tất định 
(deterministic) nếu cho trước một dãy nhị phân ngẫu nhiên có độ dài k thì đầu ra của nó là 
một dãy bit giả ngẫu nhiên độ dài kll . Dãy đầu vào k bit đó được gọi là mầm 
(seed). Còn đầu ra l bit của nó được gọi là dãy giả ngẫu nhiên. 
Định nghĩa 2: Một thuật toán sinh bit giả ngẫu nhiên được gọi là thuật toán sinh bit giả 
ngẫu nhiên an toàn cho mật mã nếu các dãy do thuật toán sinh ra qua được 5 tiêu chuẩn 
thống kê [1]. 
2.2. Một số thuật toán sinh bit giả ngẫu nhiên [4] 
2.2.1. Thuật toán tạo bit giả ngẫu nhiên bởi thuật toán RSA 
Cho hệ mật RSA: qpn với qp, là hai số nguyên tố khác nhau và đủ lớn. Đặt: 
 11)(  qpn (2.1) 
Lấy b là một số nguyên sao cho: 
 1)(,  nb (2.2) 
Ký hiệu: 1,:1* nxnxZn 
Kỹ thuật điều khiển & Điện tử 
L. D. Cường, H. V. Canh, V. V. Tùng, “Phương pháp tạo dãy giả  giao thức mật mã.” 100 
Lấy một số *nZr và tính: 
 rx 0 , )(mod1 nxx
b
ii ; ,..2,1,0 i (2.3) 
Khi đó định nghĩa: 
 2modii xZ với ,..2,1 i (2.4) 
Lúc đó, dãy 1: iZi được gọi là dãy bit giả ngẫu nhiên được tạo ra từ thuật toán 
RSA. 
2.2.2. Thuật toán tạo bit giả ngẫu nhiên BBS (Blum_Blum_Shub) 
Thuật toán: Chọn qpn , trong đó qp, là 2 số nguyên tố khác nhau sao cho 
 4mod3, qp . Ký hiệu )(nQ là tập các thặng dư bình phương theo mod n . Với mỗi 
)(nQr , xác định dãy số ,..,, 210 xxx như sau: 
1B : rx 0 
2B : Với ,..2,1,0 i tính 
 nxx ii mod
2
1  (2.5) 
3B : Đặt 2modii xZ với ,..2,1,0 i 
4B : Quay lại iZ ; ,..2,1 i là dãy bit giả ngẫu nhiên BBS 
2.2.3. Thuật toán tạo bit ngẫu nhiên dựa trên bài toán logarit rời rạc 
Cho p là một số nguyên tố đủ lớn, là một phần tử nguyên thủy trong *pZ , xác định 
dãy: rx 0 
 nxx ii mod
2
1  (2.6) 
1 mod
ix
ix p 
bây giờ đặt: 
1
2
0
2
i
i
i
p
ifx
Z
p
ifx
(2.7) 
1 2, ,..Z Z Z là dòng bit giả ngẫu nhiên được sinh ra từ bài toán logarit rời rạc. 
2.3. Nhận xét 
Các thuật toán sinh dãy bit giả ngẫu nhiên đã trình bày có ưu điểm là đơn giản và chất 
lượng của các dãy đó tuy chưa có đánh giá bằng 5 tiêu chuẩn thống kê điển hình nhất 
nhưng tính đồng xác suất được hiện rõ. Tuy nhiên, việc cứng hóa modul mật mã khi ứng 
dụng các thuật toán tạo dãy giả ngẫu nhiên này phức tạp và dãy bit đó rất dễ tuần hoàn có 
chu kỳ không đủ lớn. Bởi vậy, cùng với một số lý do khác, chẳng hạn việc xác định một 
phần tử là nguyên thủy *pZ là không đơn giản và nếu số không phải là nguyên thủy thì 
rõ ràng là không tốt vì chắc chắn dãy bit giả ngẫu nhiên do thuật toán logarit rời rạc sinh ra 
sẽ tuần hoàn với chu kỳ ngắn. 
3. ĐỀ XUẤT THUẬT TOÁN TẠO CHUỖI BIT GIẢ NGẪU NHIÊN 
ỨNG DỤNG CHO GIAO THỨC MẬT MÃ 
3.1. Khái niệm thanh ghi dịch có phản hồi 
Nghiên cứu khoa học công nghệ 
Tạp chí Nghiên cứu KH&CN quân sự, Số 50, 08 - 2017 101
3.1.1. Định nghĩa 
Định nghĩa 1: Thanh ghi dịch phản hồi tuyến tính (LFSR) độ dài L gồm L trạng thái (L 
ô) được đánh số từ 1,..,2,1,0 l ; mỗi ô chứa một bit 0/1 và có một đầu vào và một đầu ra. 
Đồng thời liên hệ với một đồng hồ nhằm điều khiển việc dịch chuyển dữ liệu của thanh R. 
 Định nghĩa 2: Thanh ghi dịch R được ký hiệu: 
 )(, xCLR (3.1) 
trong đó: 
 LLxCxCxC ...1)( 11 ])[2( xGF (3.2) 
là đa thức kết nối (connection polynomial). Thanh ghi dịch tuyến tính R được gọi là không 
suy biến (nonsingular) nếu bậc của C(x) là L, tức là CL=1. 
Giả sử nội dung của ô thứ i là si {0,1}, đối với mỗi 1,..,1,0 Li . Khi đó, dãy 
 011 ,,.., SSSL được gọi là trạng thái ban đầu (khởi tạo) của thanh LFSR. 
Định nghĩa 3: Cho: 
])[2()( xGFxC 
là đa thức nguyên thủy (primitive polynomial) bậc L. 
Khi đó, ))(,( xCL
được gọi là LFSR có độ dài cực đại (maximum length). 
Đầu ra của LFSR có độ dài cực đại với trạng thái ban đầu khác 0 được gọi là maximum 
sequence (m_sequence). Khi đó với mỗi một 12 
L
 trạng thái ban đầu khác 0 của một 
thanh ghi dịch phản hồi tuyến tính LFSR sẽ sinh ra một dãy giả ngẫu nhiên có chu kỳ cực 
đại là 12 L . 
Từ đó suy ra rằng để tạo thanh ghi dịch phản hồi tuyến tính có chu kỳ cực đại 12 L , 
điều kiện cần là độ dài thanh ghi dịch đó phải là số nguyên tố ( 12 
L
 là số nguyên tố 
mersenne). 
3.1.2. Các khẳng định 
Khẳng định 1: Nếu trạng thái ban đầu của LFSR là  011 ,,.., SSSL thì dãy đầu ra 
,.., 10 SSS được xác định một cách duy nhất bởi phép đệ quy (recursion) sau đây: 
 2mod..2211 LjLjjJ SCSCSCS (3.3) 
đối với Lj  . 
Khẳng định 2: Với mọi dãy đầu ra của một LFSR )(, xCL là tuần hoàn với chu kỳ 
12 L nếu và chỉ nếu đa thức )(xC là đa thức nguyên thủy có bậc (degree) đúng bằng L . 
Khẳng định 3: Cho đa thức ])[2()( xGFxC có bậc L . Khi đó: Nếu )(xC là bất khả 
quy trên trường )2(GF , thì mỗi một 12 L trạng thái ban đầu khác 0 của một LFSR 
không suy biến sẽ sinh ra dãy đầu ra tuần hoàn với chu kỳ bằng số nguyên dương nhỏ nhất 
N sao cho Nx 1 chia hết cho )(xC (có nghĩa là đa thức )(xC nguyên thủy trên trường 
)2(GF [15]. 
3.2. Thuật toán sinh dãy giả ngẫu nhiên được đề xuất 
3.2.1. Cấu tạo hệ thống các thanh ghi dịch phản hồi phi tuyến 
Việc xây dựng hệ thống các thanh ghi dịch với số lượng thanh, độ dài mỗi thanh và 
thuật toán của chúng cần có quy tắc nhất định. Theo trình bày trên, độ dài mỗi thanh ghi 
Kỹ thuật điều khiển & Điện tử 
L. D. Cường, H. V. Canh, V. V. Tùng, “Phương pháp tạo dãy giả  giao thức mật mã.” 102 
dịch phải là số nguyên tố; Nếu có nhiều thanh ghi dịch độ dài khác nhau thì các độ dài của 
chúng phải nguyên tố với nhau từng đôi một hoặc bằng nhau. Trong bài này, chúng tôi 
chọn 5 thanh ghi dịch với độ dài bằng nhau (bằng 31). 
Giả sử, ta có K thanh ghi dịch phản hồi tuyến tính, ký hiệu là 
KRRR ,.., 21 , mỗi thanh 
ghi dịch iR có độ dài KiLi ,..2,1; . Trong đó, các iL là những số nguyên tố. 
Lược đồ hoạt động của các thanh ghi dịch: 
3.2.2. Tạo mầm khóa 
Cho một hệ thống khóa gồm 2 khóa, mầm khóa được ký hiệu lần lượt là: 
2
1
..
..
212
211
m
m
dddK
bbbK
 (3.4) 
Để dễ hình dung, ta lấy 201 m , 102 m , trong đó, zcbadb ji ,..,,,, và 5 K , 
3154321 LLLLL . 
 Các chữ cái , : 1,20; 1,10i jb d i j được chuyển thành các vectơ nhị phân 5 hoặc 8 
thành phần. Trong thuật toán này, ta chuyển các ,i jb d thành các vectơ nhị phân 5 thành 
phần, được cho trong bảng 1 sau đây: 
Nghiên cứu khoa học công nghệ 
Tạp chí Nghiên cứu KH&CN quân sự, Số 50, 08 - 2017 103
Bảng 1. Bảng véc tơ nhị phân 5 thành phần. 
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z 3 4 8 9 + / 
1 1 0 1 1 1 0 0 0 1 1 0 0 0 0 0 1 0 1 0 1 0 1 1 1 1 0 0 1 0 1 0 
1 0 1 0 0 0 1 0 1 1 1 1 0 0 0 1 1 1 0 0 1 1 1 0 0 0 0 1 1 0 1 0 
0 0 1 0 0 1 0 1 1 0 1 0 1 1 0 1 1 0 1 0 1 1 0 1 1 0 0 0 1 1 0 0 
0 1 1 1 0 1 1 0 0 1 1 0 1 1 1 0 0 1 0 0 0 1 0 1 0 0 1 0 1 0 1 0 
0 1 0 0 0 0 1 1 0 0 0 1 1 0 1 1 1 0 0 1 0 1 1 1 1 1 0 0 1 0 1 0 
Bây giờ ta đặt: 

5
1
32
*
1
1
1 .2)(
j
j
j Zg 

5
1
32
*
16
1
2 .2)(
j
j
j Zg 
(3.5) 
Trong đó, 521 ,..,, là vectơ nhị phân tương ứng các chữ cái của bảng trên: 
Ta lập bảng 2 sau đây: 
Bảng 2. Bảng véc tơ chuyển đổi tương ứng. 
3.2.3. Lấp đầy các thanh ghi dịch (5 thanh ghi) 
Mầm khóa 1K , 2K lấp đầy các ô của 5 thanh ghi dịch thực hiện như sau: 
Ký hiệu: các vectơ nhị phân của khóa 1
K
 là 1 2 20, ,..,b b b , khóa 2
K
 là 1 2 10, ,..,d d d , với 
20,1);,..,,( )5()2()1( ibbbb iiit 
10,1);,..,,( )5()2()1( idddd iiit 
(3.6) 
Ký hiệu )( jiy là ô thứ i của thanh ghi jR với 1,2,..; 1,2,..,5i j 
Đặt: 
( ) 1 1,5jiy j  
( ) ( )
1 , 1,20, 1,5
j j
i iy b i j 
( ) ( )
21
j j
i iy c 
(3.7) 
với ( )jic là thành phần thứ j của vectơ nhị phân 
(1) (2) (3) (4) (5)( , , , , ), 1,10i i i i i ic c c c c c i 
và
2 1 10[g ( )-g ( )] mod32i i ic d b 
(3.8) 
Nói cách khác 1
2 ( )i ic g c
 , trong đó, 2 1 10[g ( )-g ( )] mod32i i ic d b 
Kỹ thuật điều khiển & Điện tử 
L. D. Cường, H. V. Canh, V. V. Tùng, “Phương pháp tạo dãy giả  giao thức mật mã.” 104 
Các hàm 1 (.)g , 2 (.)g được cho trong bảng 3.2, tức là 
5
1
1
1
2 mod 32j ji i
j
g b b 
 
5
1
2
1
2 mod32j b ii i
j
g b b 
  
(3.9) 
Như vậy, sau giai đoạn này cả 31 ô của cả 5 thanh ghi đã được lấp đầy thông tin nhờ hệ 
thống các mầm khóa cho trước 1K và 2K . 
3.2.4. Sự hoạt động của 5 thanh ghi R1,R2,..,R5 
Như vậy sau khi các thanh ghi dịch được nạp đủ trạng thái ban đầu (lấp đầy) và ký hiệu 
là ( ) ( ) ( )
1 2 31, ,..,
j j jy y y và 0,1jiy , 1,31; 1,5i j . 
Ta ký hiệu (1) (2) (5), ,..,t t t    là vectơ ngẫu nhiên được các thanh ghi tạo ra ở nhịp 
thứ t với 1, 2,3,..t Ta có: 
*) Bước 1: Với 1t , 
 (1) (2) (3) (4) (5)1 1 1 1 1, , , ,      (3.10) 
Trong đó, 
( ) ( )
1 27 , 1,5
j jy j 
*) Bước 2: Với 1,2,3,..i đặt 
( ) ( ) ( )
31 28
j J j
i i iy y y  , 1,5j (3.11) 
*) Bước 3: từ (3.10)(3.11), 2,3,...t tính (1) (2) (3) (4) (5), , , ,t t t t t      , trong đó 
)(
27),(
)( j
tj
j
t y  với 1,5j (3.12) 
Và hàm hai biến ( , )j t được định nghĩa là: 0)1,( j 
 ( , 1) ( , ) ( , ) 1j t j t j t  (3.13) 
đối với 1,5; 1,2,3,..j t 
Hàm ( , )j t được định nghĩa là: (1, ) 1t với 1,2,3,..t 
(1)
(1, ) 19(2, ) 1tt y   
( )
( , ) 19( 1, ) ( , ) 1
j
j tj t j t y     (3.14) 
với 2,3,4j 
Từ (3.12), (3.13), (3.14) ta có thể tạo ra được dãy bit giả ngẫu nhiên có độ dài tùy ý 
 t với 1t . 
3.2.5. Ví dụ 
*) Bước 1: Giả sử ta có: 
K1= JOMPC NXRJO MDHJX BVKFM (20 ký tự) 
K2= CPWKV EEBSN (10 ký tự) 
Khi đó ta lập bảng 3 đối với 1K và bảng 4 đối với 2K như sau: 
Nghiên cứu khoa học công nghệ 
Tạp chí Nghiên cứu KH&CN quân sự, Số 50, 08 - 2017 105
Bảng 3. Lập bảng cho K1. 
 CC 
Tt 
J O M P C N X R I O M D H J X B V K F M 
1 1 0 0 0 0 0 1 0 0 0 0 1 0 1 1 1 0 1 1 0 
2 1 0 0 1 1 0 0 1 1 0 0 0 0 1 0 0 1 1 0 0 
3 0 0 1 1 1 1 1 0 1 0 1 0 1 0 1 0 1 1 1 1 
4 1 1 1 0 1 1 1 1 0 1 1 1 0 1 1 1 1 1 1 1 
5 0 1 1 1 0 0 1 0 0 1 1 0 1 0 1 1 1 0 0 1 
Bảng 4. Lập bảng cho K2. 
 CC 
TT 
C P W K V E E B S N 
1 0 0 1 1 0 1 1 1 1 0 
2 1 1 1 1 1 0 0 0 0 0 
3 1 1 0 1 1 0 0 0 1 1 
4 1 0 0 1 1 0 0 1 0 1 
5 0 1 1 0 1 0 0 1 0 0 
*) Bước 2: Lập các trạng thái ban đầu cho 5 thanh ghi dịch 521 ,.., RRR Tính 
, 1,10iC i 
1 2 1 1 11 2 1( ) ( ) mod32 (01110) (00111) mod32 (14 28) mod32 18C g d g b g g 
2 2 2 1 12( ) ( ) (13 9) mod32 4C g d g b 
3 3 3 1 13( ) ( ) (25 20) mod 32 5C g d g b 
4 19C ; 5 18C ; 6 23C ; 7 18C ; 
8 4C ; 9 7C ; 10 10C 
Từ đó áp dụng bảng 3.2 ta có các kết quả: 
1 1
1 12 2( ) (18) 10010C g C g 
1 1
6 62 2( ) (23) 10111C g C g 
1 1
2 22 2( ) (4) 00100C g C g 
1 1
7 72 2( ) (18) 10010C g C g 
1 1
3 32 2( ) (5) 00101C g C g 
1 1
8 82 2( ) (4) 00100C g C g 
1 1
4 42 2( ) (19) 10011C g C g 
1 1
9 92 2( ) (7) 00111C g C g 
1 1
5 52 2( ) (18) 10010C g C g 
1 1
10 102 2( ) (10) 01010C g C g 
55 trạng thái đầu của các thanh ghi dịch phản hồi được thể hiện trong bảng 5: 
Bảng 5. 55 trạng thái của các thanh ghi dịch. 
 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 
1R 1 1 0 0 0 0 0 1 0 0 0 0 1 0 1 1 1 0 1 1 0 
2R 1 1 0 0 1 1 0 0 1 1 0 0 0 0 1 0 0 1 1 0 0 
3R 1 0 0 1 1 1 1 1 0 1 0 1 0 1 0 1 0 1 1 1 1 
4R 1 1 1 1 0 1 1 1 1 0 1 1 1 0 1 1 1 1 1 1 1 
5R 1 0 1 1 1 0 0 1 0 0 1 1 1 1 0 1 1 1 0 0 1 
Kỹ thuật điều khiển & Điện tử 
L. D. Cường, H. V. Canh, V. V. Tùng, “Phương pháp tạo dãy giả  giao thức mật mã.” 106 
 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 
1R 1 0 0 1 1 1 1 0 0 0 1 1 0 1 1 0 1 0 0 1 0 
2R 0 0 0 0 0 0 0 0 0 1 1 1 1 1 0 0 1 0 1 0 0 
3R 0 1 1 0 0 1 0 1 1 0 0 1 0 1 0 1 0 1 1 1 1 
4R 1 0 0 1 1 1 1 0 1 1 1 0 0 0 0 1 1 1 0 1 0 
5R 0 0 1 1 0 1 0 0 1 0 1 1 1 0 0 1 0 1 1 0 0 
 43 44 45 46 47 48 49 50 51 52 53 54 55  
1R 0 0 0 1 1 1 1 0 0 1 1 0 1  
2R 1 0 0 0 0 0 1 1 0 1 1 0 1  
3R 0 1 0 0 0 0 1 1 1 0 1 0 1  
4R 1 0 0 0 1 1 1 0 0 0 1 0 0  
5R 0 0 1 0 1 0 1 1 0 0 1 0 1  
*) Bước 3: Tạo dãy giả ngẫu nhiên 
Cho 1, 2,..,5; 1, 2,3,..j t 
i/ Theo (3.12), (3.13), (3.14) ta có: 
( ,1) 0; 1,5j j  
(1, ) 1; 1,2,3,..t t  
ii/ Cuối cùng ta có bảng 6 tương ứng 1,2,3,..t như sau: 
Bảng 6. Bảng dãy giả ngẫu nhiên tương ứng. 
t 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 
R 1 (1, )t 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 
(1, )t 0 2 4 6 8 10 12 14 16 18 20 22 24 26 28 
t 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 
R 2 (2, )t 0 1 1 0 0 1 1 0 0 1 1 0 1 1 0 
(2, )t 0 1 3 5 6 7 9 11 12 13 15 17 18 20 22 
t 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 
R 3 (3, )t 0 1 1 1 0 1 1 1 1 1 0 0 0 0 0 
(3, )t 0 1 3 5 7 8 10 12 14 16 18 19 20 21 22 
t 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 
R 4 (4, )t 0 1 1 0 0 1 0 0 1 1 1 0 1 1 0 
(4, )t 0 1 3 5 6 7 9 10 11 13 15 17 18 20 22 
t 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 
R 5 (5, )t 0 1 1 1 0 1 0 1 0 1 0 0 0 0 0 
(5, )t 0 1 3 5 7 8 10 11 13 14 16 17 18 19 20 
Nghiên cứu khoa học công nghệ 
Tạp chí Nghiên cứu KH&CN quân sự, Số 50, 08 - 2017 107
iii/ Tạo dãy bit giả ngẫu nhiên 
Áp dụng công thức 
( ) ( )
( , ) 27 ; 1,5; 1,2,..,15,..
j j
t j ty j t  
ta nhận được dãy giả ngẫu nhiên sau: 
 = 10111 00010 00111 11011 11001 01100 00101 11110 00111 01000 
 10000 10000 00001 10010 11111  
iv/ Nhận xét 
+ Từ kết quả trên, chu kỳ của dãy giả ngẫu nhiên vừa đươc tạo ra là 31 5(2 1) . Để chứng 
minh, xem [16] bằng cách sử dụng các định nghĩa 1, 2, 3 và định lý sau: 
Định lý: Một thiết bị sinh tuyến tính của một bộ nhớ với kích cỡ cho trước tạo ra một 
dãy các phần tử từ trường )( pGF với chu kỳ cực đại nếu và chỉ nếu đa thức đặc trưng của 
chúng nguyên thủy. Khi đó, chu kỳ của chúng là: 
i
i
k
i
L
p
p
p
p
p
LN
)1(
1
)1(
)(
1

 (3.15) 
Trong đó, ip là những nhân tử nguyên tố của 1 
Lp 
Đặc biệt, nếu thiết bị sinh có k thanh ghi dịch phản hồi tuyến tính có độ dài bằng nhau 
và bằng L thì kLp pLN )1()( (3.16) 
+ Kết quả thực nghiệm theo một số tiêu chuẩn NIS 
Lấy ngẫu nhiên mẫu cần test  độ dài đủ lớn n bit (theo một số khuyến cáo 
chọn 000.10 n ) từ  : 
000.10321 ,..,,,  với  nii ..1,1,0  
Kiểm tra kết quả test 5 tiêu chuẩn của NIS [1], ta thu được P_giá trị )_( gtP . Sau đó, 
so sánh với mức được NIS chọn  01,0;001,0 (tương ứng với xác suất sai lầm loại 1). 
Kết quả đạt được thỏa mãn 5 tiêu chuẩn của NIS. 
Phép test Tiêu chuẩn Kết quả So sánh Kết 
luận 
The 
Frequency 
test 
1_ gtP : ngẫu nhiên hoàn hảo; 
0_ gtP : hoàn toàn không ngẫu 
nhiên; 
 gtP _ : ngẫu nhiên; 
 gtP _ : không ngẫu nhiên. 
gtP _ = 
0,109599 
gtP _ 01,0 : 
thỏa mãn 
Dãy xét 
là dãy 
ngẫu 
nhiên 
Frequency 
Test 
winthin a 
Block 
gtP _ = 
2
)(
,
2
2 obsXN
igamc
: ngẫu nhiên; 
gtP _ = 
0,706438 
gtP _ 01,0 : 
thỏa mãn 
Dãy xét 
là dãy 
ngẫu 
nhiên 
Kỹ thuật điều khiển & Điện tử 
L. D. Cường, H. V. Canh, V. V. Tùng, “Phương pháp tạo dãy giả  giao thức mật mã.” 108 
The Runs 
Test 
gtP _
)1(22
)1(2)(2
n
nobsV
erfc
n 
gtP _ = 
0,500798 
gtP _ 01,0 : 
thỏa mãn 
Dãy xét 
là dãy 
ngẫu 
Nhiên 
The Serial 
Test 
   22 ,21_ mmigamcgtP 
và 
   23 ,22_ mmigamcgtP 
1_ gtP = 
0,9057 
2_ gtP = 
0,8805 
2_;1_ gtPgtP
01,0 : thỏa mãn 
Dãy xét 
là dãy 
ngẫu 
Nhiên 
The 
Approxim
ate 
Entropy 
Test 
gtP _ 
2
,2
2
1 Xigamc m 
gtP _ = 
0,261961 
01,0_ gtP : 
thỏa mãn 
Dãy xét 
là dãy 
ngẫu 
Nhiên 
+ Trong ví dụ trên, chúng tôi trình bày trường hợp 5 thanh ghi dịch phản hồi với các 
thanh ghi bằng nhau và bằng 31 (là số nguyên tố). 
Trong thực tế ta có, thể dùng 4, 6, 7 hoặc 8 thanh ghi dịch có độ dài khác nhau nhưng 
độ dài đó phải là các số nguyên tố hoặc nguyên tố cùng nhau. Tùy theo mỗi yêu cầu cụ 
thể, các tác giả sẽ nghiên cứu tiếp để tạo ra k các thanh ghi dịch phản hồi phi tuyến với 
L nguyên tố và sẽ xây dựng một module mã hóa khóa dòng an toàn dùng trong thực tế. 
4. KẾT LUẬN 
Việc xây dựng các thanh ghi dịch phản hồi tuyến tính vừa được trình bày trong bài báo 
dễ dàng có thể cứng hóa thành một modul mật mã để ứng dụng trong an ninh - quốc 
phòng. Về mặt toán học, hệ thống được xây dựng bằng cách tổ hợp các đầu ra của 5 thanh 
ghi dịch phản hồi tuyến tính như trên cho chuỗi khóa ra là phi tuyến. Thật vậy, hàm 
 tj, và tj, đã được định nghĩa, là những hàm phi tuyến (non-linear). Do vậy hàm 
hợp  ),(),,( tjtjf  tạo ra dãy bít giả ngẫu nhiên được đề xuất là hàm phi tuyến. 
Việc tấn công vào các hệ mật mã chủ yếu sử dụng tấn công vào mầm khóa. Không gian 
khóa sinh ra trong trường hợp này là 2620x 2610 = 2630. Con số này còn lớn hơn không gian 
khóa của nhiều thuật toán mã hóa dùng trong thương mại như DES, 3DES, IDEA... Do vậy, 
có thể đối phó với các tấn công vét cạn nhằm tìm ra khóa đúng của các nhà thám mã. Hơn 
nữa, với việc tạo dãy giả ngẫu nhiên như đã đề xuất đã khắc phục được nhược điểm mà các 
hệ mật mã khối mắc phải khi mã hóa từng khối một. Dựa trên ưu điểm đó, có thể nghiên cứu 
xây dựng thuật toán mật mã khóa dòng ứng dụng trong an ninh - quốc phòng. 
Hướng phát triển tiếp theo bài này sẽ nghiên cứu đề xuất modul mật mã có ứng dụng các 
thanh ghi dịch phản hồi phi tuyến nhằm tạo ra dãy bít giả ngẫu nhiên phục vụ việc mã hóa 
văn bản bất kỳ với đầu vào và đầu ra đều là chữ cái La tinh thuộc bảng 26 chữ cái La tinh. 
TÀI LIỆU THAM KHẢO 
[1]. Andrew Rukhin, Juan Soto, James Nechvatal, Miles Smid, Elaine Barker, Stefan 
Leigh, Mark Levenson, Mark Vangel, David Banks, Alan Heckert, James Dray, San 
Nghiên cứu khoa học công nghệ 
Tạp chí Nghiên cứu KH&CN quân sự, Số 50, 08 - 2017 109
Vo, “A Statistical Test Suite for Random and Pseudorandom Number Generators for 
Cryptographic Applications”, 2010. 
[2]. Andreas Klein, “Stream Ciphers”, Springer-Verlag London, 2013. 
[3]. A. Shamir “On the generation of cryptographically strong pseudorandom sequences”, 
ACM Transactions on Information Systems, 1983. 
[4]. L Blum,M Blum,M Shub, “A Simple Unpredictable Pseudo-Random Number 
Generator”, SIAM Journal on Computing, 1986, pp.364-383. 
[5]. Ashish Jain, Narendra S. Chaudhari: ‘‘Cryptanalytic Results on Knapsack 
Cryptosystem Using Binary Particle Swarm Optimization’’, International Conference 
on Computational Intelligence in Secuirty for Information System (CISIS 2014), 
Springer International Publishing, pp. 375-384, 2014; 
[6]. Bruce Schneier, “Applied Cryptography: Protocols, Algorithms, and Source Code in 
C”, Second Edition, John Wiley & Sons, 1996. 
[7]. Dieter Gollmann, “Pseudo random properties of cascade connections of clock 
controlled shift registers”, Advances in Cryptology. Proceedings of EURO-CRYPT 
84 (LNCS 209), 1985; 
[8]. J Håstad, “Pseudo-Random Generators under Uniform Assumptions”, Proceedings of 
the 22nd Annual ACM Symposium on Theory of Computing, pp.395-404,1990; 
[9]. Kalendri, Maria; Pnevmatikatos, Dionisios; Papaefstathiou, Ioannis; Manifav-as, 
Charalampos, “Breaking The GSM A5/1 Cryptography. Algorithm with Rainbow 
Tables and High-end FPGAs”, In proc. Of 22nd International Con-ference on Field-
programmable Logic and Applications, pp.747-753, 2012; 
[10]. Lano J., “Cryptanalysis and Design of Synchronous Stream Ciphers” PhD 
thesis, Katholieke Universiteit Leuven, Faculteit Ingenieurswetenschappen, 
Department Elektrolechnik_ESAT, 2006; 
[11]. M. Blum and S. Micali, “How to generate cryptographically strong sequences of of 
Pseudorandom bits”, Proceedings of the 23rd Annual Symposium on Foundations of 
Computer Science, IEEE, New York, pp. 112–117,1982 
[12]. Matthew Robshaw, Olivien Billet, “New Stream Cipher Designs: The eSTREAM 
Finalists”, Springer-Verlag Berlin, Heidelberg ©2008; 
[13]. D. Eastlake, S. Crocker and J. Schiller, “Randomness requirements for security”, 
Internet Request for Comments 1750, December 1994; 
[14]. W. Meier and O. Staffelbach, “Analysis of pseudo random sequences generated by 
cellular automata”, In EUROCRYPT ’91, Lecture Notes in Computer, Science. 
Springer Verlag, 1991; 
[15]. Wicker, S.B., “Error Control Systems for Digital Communication and Storage”, 
Englewood Cliffs: Prentice Hall, 1995. 
[16]. Martin K. Simon, Jim K. Omura, Robert A. Scholtz, Barry K. Levitt, ‘‘Spread 
spectrium commucications handbook’’, Mc Graw- Hill, Inc (Resived Editon) New 
York, London, Madrid, Mexico, City Milan, New Delhi, Singapror, Syney, Tokyo, 
Toronto, 2005. 
Kỹ thuật điều khiển & Điện tử 
L. D. Cường, H. V. Canh, V. V. Tùng, “Phương pháp tạo dãy giả  giao thức mật mã.” 110 
ABSTRACT 
A PSEUDO-RANDOM NUMBER GENERATION METHOD 
FOR CRYPTOGRAPHIC APPLICATIONS 
Information protection by using crytography is an effective method, especially in 
the field of national security and defense. For crytography systems, the security 
depends much on the key. Therefore, the problem of key generation that guarantees 
the security of a cipher system is crucial in the field of information security. There 
are two basic key generation methods, namely random key generation and pseudo-
random key generation. However, pseudo-random key generation method currently 
attracts more attention in the communication crytography. In the paper, a new 
pseudo-random key generation method which generate random bits using a 
generation algorithm based on Linear-feedback shift register (LFSR) to guarantee 
the security of the key used in crytography systems for national security and defense 
is proposed. 
Keywords: Cryptography; Cryptoanalysis; Linear-feedback shift register (LFSR); Pseudo-random key 
generation; Pseudo-random bit. 
Nhận bài ngày 21 tháng 6 năm 2017 
Hoàn thiện ngày 08 tháng 8 năm 2017 
Chấp nhận đăng ngày 18 tháng 8 năm 2017 
Địa chỉ: 1 Cục Kỹ thuật, Bộ Công an; 
 2 Cục Kỹ thuật nghiệp vụ, Tổng cục I, Bộ Công an. 
 *Email: cuongqt34@yahoo.com.