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ử<br /> <br /> PHƯƠNG PHÁP TẠO DÃY GIẢ NGẪU NHIÊN ĐỂ<br /> ỨNG DỤNG TRONG GIAO THỨC MẬT MÃ<br /> Lê Danh Cường1*, Hồ Văn Canh2, Võ Văn Tùng1<br /> 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<br /> 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ụ<br /> 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ệ<br /> 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ó<br /> 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<br /> 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<br /> đượ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<br /> 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<br /> 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<br /> của khóa mã sử dụng trong các hệ mật mã đối với lĩnh vực ANQP.<br /> 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ã;<br /> <br /> 1. ĐẶT VẤN ĐỀ<br /> 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<br /> 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,<br /> 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à<br /> 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<br /> đ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<br /> 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<br /> 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ố<br /> 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ẽ<br /> 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<br /> đượ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ụ<br /> thuộc vào mầm khóa và thuật toán sinh khóa.<br /> 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<br /> 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<br /> 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<br /> 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<br /> 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<br /> 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<br /> 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<br /> 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ể<br /> 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<br /> là k thì lực lượng không gian mầm sẽ là 2k khóa mầm.<br /> Một số ví dụ điển hình chứng minh điều nhận xét ở trên:<br /> - Đố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ó<br /> 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<br /> 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,<br /> độ 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.<br /> - Hiện nay, thay vì DES, người ta sử dụng mật mã AES (Advance Encryption<br /> 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<br /> 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<br /> toán tiềm năng của thế hệ máy tính mới.<br /> <br /> <br /> 98 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ã.”<br /> Nghiên cứu khoa học công nghệ<br /> <br /> Đố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ẽ<br /> 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.<br /> 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<br /> IDEA (International Data Encryption Algorithm), thuật toán này sử dụng độ dài mầm khóa<br /> 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à<br /> 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<br /> 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<br /> 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ì<br /> 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<br /> công bản mã. Đó là:<br /> - 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<br /> 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<br /> ra một số quy luật giúp cho tấn công.<br /> - 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<br /> 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ã<br /> tương ứng nhiều nhất là 26 8 và không gian khóa thực tế nhiều nhất là 26 8 khóa có thể có.<br /> Từ đó, nếu có một thuật toán thực hiện phân hoạch không gian khóa K  K1  K 2 ; Trong<br /> đó, K1  K 2   thì khả năng tìm khóa đúng trong lớp gồm 26 8 khóa (chẳng hạn K1) có<br /> thể khả thi.<br /> 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ư<br /> 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<br /> 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<br /> tạp của thuật toán sinh khóa.<br /> 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ò<br /> 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<br /> 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<br /> 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ã.<br /> 2. MỘT SỐ KHÁI NIỆM CƠ SỞ<br /> 2.1. Một số định nghĩa<br /> Định nghĩa 1: Một thuật toán sinh bit giả ngẫu nhiên được gọi là tất định<br /> (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à<br /> một dãy bit giả ngẫu nhiên độ dài l l  k  . Dãy đầu vào k bit đó được gọi là mầm<br /> (seed). Còn đầu ra l bit của nó được gọi là dãy giả ngẫu nhiên.<br /> Đị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ả<br /> 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<br /> thống kê [1].<br /> 2.2. Một số thuật toán sinh bit giả ngẫu nhiên [4]<br /> 2.2.1. Thuật toán tạo bit giả ngẫu nhiên bởi thuật toán RSA<br /> Cho hệ mật RSA: n  p  q với p, q là hai số nguyên tố khác nhau và đủ lớn. Đặt:<br />  (n)   p  1q  1 (2.1)<br /> Lấy b là một số nguyên sao cho:<br /> b, (n)   1 (2.2)<br /> Ký hiệu: Z n*  1  x  n : x, n   1<br /> <br /> <br /> Tạp chí Nghiên cứu KH&CN quân sự, Số 50, 08 - 2017 99<br />  Kỹ thuật điều khiển & Điện tử<br /> <br /> Lấy một số r  Z n* và tính:<br /> x0  r , xi 1  xib (mod n) ; i  0,1,2,.. (2.3)<br /> Khi đó định nghĩa:<br /> Z i  xi mod 2  với i  1,2,.. (2.4)<br /> Lúc đó, dãy Z i : i  1 được gọi là dãy bit giả ngẫu nhiên được tạo ra từ thuật toán<br /> RSA.<br /> 2.2.2. Thuật toán tạo bit giả ngẫu nhiên BBS (Blum_Blum_Shub)<br /> Thuật toán: Chọn n  p  q , trong đó p, q là 2 số nguyên tố khác nhau sao cho<br />  p, q   3 mod 4 . Ký hiệu<br /> Q (n) là tập các thặng dư bình phương theo mod n . Với mỗi<br /> r  Q(n) , xác định dãy số x0 , x1 , x2 ,.. như sau:<br /> B1 : x0  r<br /> B2 : Với i  0,1,2,.. tính<br /> xi 1  xi2 mod n (2.5)<br /> B3 : Đặt Z i  xi mod 2 với i  0,1,2,..<br /> B4 : Quay lại Z i  ; i  1,2,.. là dãy bit giả ngẫu nhiên BBS<br /> 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<br /> Cho p là một số nguyên tố đủ lớn,  là một phần tử nguyên thủy trong Z *p , xác định<br /> dãy: x0  r<br /> xi 1  xi2 mod n (2.6)<br /> xi 1   mod p bây giờ đặt:<br /> xi<br /> <br /> <br />  p<br /> 1ifxi  2<br /> Zi   (2.7)<br /> 0ifx  p<br />  i 2<br /> Z  Z1 , Z2 ,.. là dòng bit giả ngẫu nhiên được sinh ra từ bài toán logarit rời rạc.<br /> 2.3. Nhận xét<br /> 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<br /> 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<br /> 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<br /> 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ó<br /> 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<br /> phần tử là nguyên thủy Z *p là không đơn giản và nếu số  không phải là nguyên thủy thì<br /> 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<br /> sẽ tuần hoàn với chu kỳ ngắn.<br /> 3. ĐỀ XUẤT THUẬT TOÁN TẠO CHUỖI BIT GIẢ NGẪU NHIÊN<br /> ỨNG DỤNG CHO GIAO THỨC MẬT MÃ<br /> 3.1. Khái niệm thanh ghi dịch có phản hồi<br /> <br /> <br /> <br /> 100 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ã.”<br /> Nghiên cứu khoa học công nghệ<br /> <br /> 3.1.1. Định nghĩa<br /> Đị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<br /> ô) được đánh số từ 0,1,2,.., l  1 ; mỗi ô chứa một bit 0/1 và có một đầu vào và một đầu ra.<br /> Đồ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.<br /> Định nghĩa 2: Thanh ghi dịch R được ký hiệu:<br /> R  L, C ( x ) (3.1)<br /> trong đó:<br /> C( x)  1  C1 x1  ...  CL xL  GF ( 2)[ x] (3.2)<br /> 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<br /> suy biến (nonsingular) nếu bậc của C(x) là L, tức là CL=1.<br /> Giả sử nội dung của ô thứ i là si{0,1}, đối với mỗi i  0,1,.., L  1 . Khi đó, dãy<br /> S L1 ,.., S1 , S 0  được gọi là trạng thái ban đầu (khởi tạo) của thanh LFSR.<br /> Định nghĩa 3: Cho:<br /> C ( x )  GF ( 2)[ x ] là đa thức nguyên thủy (primitive polynomial) bậc L.<br /> Khi đó, ( L, C ( x) ) được gọi là LFSR có độ dài cực đại (maximum length).<br /> Đầ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<br /> L<br /> sequence (m_sequence). Khi đó với mỗi một 2  1 trạng thái ban đầu khác 0 của một<br /> 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<br /> đại là 2 L  1 .<br /> 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 2 L  1 ,<br /> L<br /> điều kiện cần là độ dài thanh ghi dịch đó phải là số nguyên tố ( 2  1 là số nguyên tố<br /> mersenne).<br /> 3.1.2. Các khẳng định<br /> Khẳng định 1: Nếu trạng thái ban đầu của LFSR là S L1 ,.., S1 , S 0  thì dãy đầu ra<br /> S  S0 , S1 ,.. được xác định một cách duy nhất bởi phép đệ quy (recursion) sau đây:<br /> S J  C1S j 1  C2 S j 2  ..  C L S j  L  mod 2 (3.3)<br /> đối với j  L .<br /> Khẳng định 2: Với mọi dãy đầu ra của một LFSR  L, C ( x)  là tuần hoàn với chu kỳ<br /> L<br /> 2  1 nếu và chỉ nếu đa thức C (x) là đa thức nguyên thủy có bậc (degree) đúng bằng L .<br /> Khẳng định 3: Cho đa thức C ( x )  GF ( 2)[ x ] có bậc L . Khi đó: Nếu C (x) là bất khả<br /> quy trên trường GF (2) , thì mỗi một 2 L  1 trạng thái ban đầu khác 0 của một LFSR<br /> 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<br /> N sao cho 1  x N chia hết cho C (x) (có nghĩa là đa thức C (x) nguyên thủy trên trường<br /> GF (2) [15].<br /> 3.2. Thuật toán sinh dãy giả ngẫu nhiên được đề xuất<br /> 3.2.1. Cấu tạo hệ thống các thanh ghi dịch phản hồi phi tuyến<br /> 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à<br /> 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<br /> <br /> <br /> Tạp chí Nghiên cứu KH&CN quân sự, Số 50, 08 - 2017 101<br />  Kỹ thuật điều khiển & Điện tử<br /> <br /> 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<br /> 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<br /> chọn 5 thanh ghi dịch với độ dài bằng nhau (bằng 31).<br /> Giả sử, ta có K thanh ghi dịch phản hồi tuyến tính, ký hiệu là R1 , R2 ,..RK , mỗi thanh<br /> ghi dịch Ri có độ dài Li ; i  1,2,..K . Trong đó, các Li là những số nguyên tố.<br /> Lược đồ hoạt động của các thanh ghi dịch:<br /> <br /> <br /> <br /> <br /> 3.2.2. Tạo mầm khóa<br /> 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à:<br />  K1  b1b2 ..bm1<br />  (3.4)<br /> K 2  d1d 2 ..d m2<br /> Để dễ hình dung, ta lấy m1  20 , m2  10 , trong đó, bi , d j  a, b, c,.., z và K  5 ,<br /> L1  L2  L3  L4  L5  31 .<br /> Các chữ cái bi , d j : i  1, 20; j  1,10 được chuyển thành các vectơ nhị phân 5 hoặc 8<br /> thành phần. Trong thuật toán này, ta chuyển các bi , d j thành các vectơ nhị phân 5 thành<br /> phần, được cho trong bảng 1 sau đây:<br /> <br /> <br /> <br /> 102 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ã.”<br /> Nghiên cứu khoa học công nghệ<br /> <br /> Bảng 1. Bảng véc tơ nhị phân 5 thành phần.<br /> 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 + /<br /> 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<br /> 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<br /> 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<br /> 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<br /> 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<br /> Bây giờ ta đặt:<br /> 5<br /> g1 ( )   2 j 1. j   1*  Z 32<br /> j 1<br /> 5<br /> (3.5)<br /> j 1 *<br /> g 2 ( )   2 . 6  j    Z 32 1<br /> j 1<br /> <br /> <br /> Trong đó,   1 ,  2 ,..,  5  là vectơ nhị phân tương ứng các chữ cái của bảng trên:<br /> Ta lập bảng 2 sau đây:<br /> Bảng 2. Bảng véc tơ chuyển đổi tương ứng.<br /> <br /> <br /> <br /> <br /> 3.2.3. Lấp đầy các thanh ghi dịch (5 thanh ghi)<br /> Mầm khóa K1 , K 2 lấp đầy các ô của 5 thanh ghi dịch thực hiện như sau:<br /> K1 K<br /> Ký hiệu: các vectơ nhị phân của khóa là b1 , b2 ,.., b20 , khóa 2 là d1 , d 2 ,.., d10 , với<br /> bt  (bi(1) , bi( 2 ) ,.., bi(5) ); i  1,20<br /> (3.6)<br /> d t  (d i(1) , d i( 2 ) ,.., d i( 5) ); i  1,10<br /> Ký hiệu yi( j ) là ô thứ i của thanh ghi R j với i  1, 2,..; j  1, 2,..,5<br /> Đặt:<br /> yi( j )  1j  1, 5<br /> yi(j1)  bi( j ) , i  1, 20, j  1,5 (3.7)<br /> ( j) ( j)<br /> y i  21 c i<br /> <br /> với ci( j ) là thành phần thứ j của vectơ nhị phân<br /> ci  (ci(1) , ci(2) , ci(3) , ci(4) , ci(5) ), i  1,10 và<br /> (3.8)<br /> ci  [g 2 (di )-g1 (bi 10 )] mod32<br /> Nói cách khác ci  g 21 (ci ) , trong đó, ci  [g 2 (di )-g1 (bi 10 )] mod32<br /> <br /> <br /> <br /> Tạp chí Nghiên cứu KH&CN quân sự, Số 50, 08 - 2017 103<br />  Kỹ thuật điều khiển & Điện tử<br /> <br /> Các hàm g1 (.) , g 2 (.) được cho trong bảng 3.2, tức là<br /> 5<br /> <br />  <br /> g1 bi   2 j 1 bi j mod 32<br /> j 1<br /> <br /> 5<br /> (3.9)<br />  <br /> g 2 bi   2 b<br /> j 1<br /> j 1 b i<br /> i mod 32<br /> <br /> 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ệ<br /> thống các mầm khóa cho trước K1 và K 2 .<br /> 3.2.4. Sự hoạt động của 5 thanh ghi R1,R2,..,R5<br /> 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<br /> là y1( j ) , y2( j ) ,.., y31( j ) và yij  0,1 , i  1, 31; j  1, 5 .<br /> Ta ký hiệu     t(1) ,  t(2) ,..,  t(5)  là vectơ ngẫu nhiên được các thanh ghi tạo ra ở nhịp<br /> thứ t với t  1, 2,3,.. Ta có:<br /> <br /> *) Bước 1: Với t  1 ,<br />     1(1) ,  1(2) ,  1(3) ,  1(4) ,  1(5)  (3.10)<br /> ( j) ( j)<br /> Trong đó,  1  y27 , j  1,5<br /> *) Bước 2: Với i  1, 2,3,.. đặt<br /> yi(j31<br /> )<br />  yi( J )  yi(j28<br /> )<br /> , j  1, 5 (3.11)<br /> *) Bước 3: từ (3.10)(3.11), t  2,3,... tính     t(1) ,  t(2) ,  t(3) ,  t(4) ,  t(5)  , trong đó<br /> <br />  t( j )  y( (j )j ,t ) 27 với j  1,5 (3.12)<br /> <br /> Và hàm hai biến  ( j, t ) được định nghĩa là:  ( j ,1)  0<br />  ( j, t  1)   ( j, t )  ( j, t )  1 (3.13)<br /> đối với j  1,5; t  1, 2,3,..<br /> <br /> Hàm  ( j, t ) được định nghĩa là:  (1, t )  1 với t  1, 2,3,..<br />  (2, t )  y(1)(1,t )19  1<br />  ( j  1, t )   ( j, t )  y( (j )j ,t )19  1 (3.14)<br /> với j  2,3, 4<br /> 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 ý<br />  <br />  t với t  1 .<br /> <br /> 3.2.5. Ví dụ<br /> *) Bước 1: Giả sử ta có:<br /> K1= JOMPC NXRJO MDHJX BVKFM (20 ký tự)<br /> K2= CPWKV EEBSN (10 ký tự)<br /> Khi đó ta lập bảng 3 đối với K1 và bảng 4 đối với K 2 như sau:<br /> <br /> <br /> <br /> 104 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ã.”<br /> Nghiên cứu khoa học công nghệ<br /> <br /> Bảng 3. Lập bảng cho K1.<br /> CC J O M P C N X R I O M D H J X B V K F M<br /> Tt<br /> 1 1 0 0 0 0 0 1 0 0 0 0 1 0 1 1 1 0 1 1 0<br /> 2 1 0 0 1 1 0 0 1 1 0 0 0 0 1 0 0 1 1 0 0<br /> 3 0 0 1 1 1 1 1 0 1 0 1 0 1 0 1 0 1 1 1 1<br /> 4 1 1 1 0 1 1 1 1 0 1 1 1 0 1 1 1 1 1 1 1<br /> 5 0 1 1 1 0 0 1 0 0 1 1 0 1 0 1 1 1 0 0 1<br /> <br /> Bảng 4. Lập bảng cho K2.<br /> CC<br /> C P W K V E E B S N<br /> TT<br /> 1 0 0 1 1 0 1 1 1 1 0<br /> 2 1 1 1 1 1 0 0 0 0 0<br /> 3 1 1 0 1 1 0 0 0 1 1<br /> 4 1 0 0 1 1 0 0 1 0 1<br /> 5 0 1 1 0 1 0 0 1 0 0<br /> <br /> *) Bước 2: Lập các trạng thái ban đầu cho 5 thanh ghi dịch R1 , R2 ,..R5 Tính<br /> Ci , i  1,10<br /> C1  g 2 (d1 )  g1 (b11 ) mod 32  g 2 (01110)  g1 (00111) mod 32  (14  28) mod 32  18<br /> C2  g 2 (d 2 )  g1 (b12 )  (13  9) mod 32  4<br /> C3  g3 (d3 )  g1 (b13 )  (25  20) mod 32  5<br /> C4  19 ; C5  18 ; C6  23 ; C7  18 ;<br /> C8  4 ; C9  7 ; C10  10<br /> Từ đó áp dụng bảng 3.2 ta có các kết quả:<br /> 1 1 1 1<br /> C1  g 2 (C1 )  g 2 (18)  10010 C6  g 2 (C6 )  g 2 (23)  10111<br /> 1 1 1 1<br /> C2  g 2 (C2 )  g 2 (4)  00100 C7  g 2 (C7 )  g 2 (18)  10010<br /> 1 1 1 1<br /> C3  g 2 (C3 )  g 2 (5)  00101 C8  g 2 (C8 )  g 2 (4)  00100<br /> 1 1 1 1<br /> C4  g 2 (C4 )  g 2 (19)  10011 C9  g 2 (C9 )  g 2 (7)  00111<br /> 1 1 1 1<br /> C5  g 2 (C5 )  g 2 (18)  10010 C10  g 2 (C10 )  g 2 (10)  01010<br /> <br /> 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:<br /> Bảng 5. 55 trạng thái của các thanh ghi dịch.<br /> 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21<br /> R1 1 1 0 0 0 0 0 1 0 0 0 0 1 0 1 1 1 0 1 1 0<br /> R2 1 1 0 0 1 1 0 0 1 1 0 0 0 0 1 0 0 1 1 0 0<br /> R3 1 0 0 1 1 1 1 1 0 1 0 1 0 1 0 1 0 1 1 1 1<br /> R4 1 1 1 1 0 1 1 1 1 0 1 1 1 0 1 1 1 1 1 1 1<br /> R5 1 0 1 1 1 0 0 1 0 0 1 1 1 1 0 1 1 1 0 0 1<br /> <br /> <br /> Tạp chí Nghiên cứu KH&CN quân sự, Số 50, 08 - 2017 105<br />  Kỹ thuật điều khiển & Điện tử<br /> <br /> 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42<br /> R1 1 0 0 1 1 1 1 0 0 0 1 1 0 1 1 0 1 0 0 1 0<br /> R2 0 0 0 0 0 0 0 0 0 1 1 1 1 1 0 0 1 0 1 0 0<br /> R3 0 1 1 0 0 1 0 1 1 0 0 1 0 1 0 1 0 1 1 1 1<br /> R4 1 0 0 1 1 1 1 0 1 1 1 0 0 0 0 1 1 1 0 1 0<br /> R5 0 0 1 1 0 1 0 0 1 0 1 1 1 0 0 1 0 1 1 0 0<br /> <br /> 43 44 45 46 47 48 49 50 51 52 53 54 55 …<br /> R1 0 0 0 1 1 1 1 0 0 1 1 0 1 …<br /> R2 1 0 0 0 0 0 1 1 0 1 1 0 1 …<br /> R3 0 1 0 0 0 0 1 1 1 0 1 0 1 …<br /> R4 1 0 0 0 1 1 1 0 0 0 1 0 0 …<br /> R5 0 0 1 0 1 0 1 1 0 0 1 0 1 …<br /> *) Bước 3: Tạo dãy giả ngẫu nhiên<br /> Cho j  1, 2,..,5; t  1, 2,3,..<br /> i/ Theo (3.12), (3.13), (3.14) ta có:<br />  ( j,1)  0; j  1,5<br />  (1, t )  1; t  1, 2,3,..<br /> ii/ Cuối cùng ta có bảng 6 tương ứng t  1, 2,3,.. như sau:<br /> Bảng 6. Bảng dãy giả ngẫu nhiên tương ứng.<br /> t 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15…<br /> R1  (1, t ) 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1…<br />  (1, t ) 0 2 4 6 8 10 12 14 16 18 20 22 24 26 28…<br /> <br /> t 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15…<br /> R2  (2, t ) 0 1 1 0 0 1 1 0 0 1 1 0 1 1 0…<br />  (2, t ) 0 1 3 5 6 7 9 11 12 13 15 17 18 20 22…<br /> <br /> t 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15…<br /> R3  (3, t ) 0 1 1 1 0 1 1 1 1 1 0 0 0 0 0…<br />  (3, t ) 0 1 3 5 7 8 10 12 14 16 18 19 20 21 22…<br /> <br /> t 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15…<br /> R4  (4, t ) 0 1 1 0 0 1 0 0 1 1 1 0 1 1 0…<br />  (4, t ) 0 1 3 5 6 7 9 10 11 13 15 17 18 20 22…<br /> <br /> t 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15…<br /> R5  (5, t ) 0 1 1 1 0 1 0 1 0 1 0 0 0 0 0…<br />  (5, t ) 0 1 3 5 7 8 10 11 13 14 16 17 18 19 20…<br /> <br /> <br /> <br /> 106 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ã.”<br /> Nghiên cứu khoa học công nghệ<br /> <br /> iii/ Tạo dãy bit giả ngẫu nhiên<br /> Áp dụng công thức<br />  t( j )  y( (j )j ,t ) 27 ; j  1,5; t  1, 2,..,15,..<br /> ta nhận được dãy giả ngẫu nhiên sau:<br />  = 10111 00010 00111 11011 11001 01100 00101 11110 00111 01000<br /> 10000 10000 00001 10010 11111 …<br /> iv/ Nhận xét<br /> + Từ kết quả trên, chu kỳ của dãy giả ngẫu nhiên vừa đươc tạo ra là (231  1)5 . Để chứng<br /> minh, xem [16] bằng cách sử dụng các định nghĩa 1, 2, 3 và định lý sau:<br /> Đị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<br /> dãy các phần tử từ trường GF ( p ) với chu kỳ cực đại nếu và chỉ nếu đa thức đặc trưng của<br /> chúng nguyên thủy. Khi đó, chu kỳ của chúng là:<br /> <br /> ( p L  1) k ( pi  1)<br /> N p ( L)   (3.15)<br /> p  1 i 1 pi<br /> <br /> Trong đó, pi là những nhân tử nguyên tố của p L  1<br /> <br /> Đặ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<br /> và bằng L thì N p ( L)  ( p L  1) k (3.16)<br /> <br /> + Kết quả thực nghiệm theo một số tiêu chuẩn NIS<br /> 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<br /> chọn n  10.000 ) từ  :<br /> <br />    1 ,  2 ,  3 ,..,  10.000 với  i  0,1, i  1..n<br /> Kiểm tra kết quả test 5 tiêu chuẩn của NIS [1], ta thu được P_giá trị ( P _ gt ) . Sau đó,<br /> so sánh với mức được NIS chọn   0,001;0,01 (tương ứng với xác suất sai lầm loại 1).<br /> Kết quả đạt được thỏa mãn 5 tiêu chuẩn của NIS.<br /> Phép test Tiêu chuẩn Kết quả So sánh Kết<br /> luận<br /> The P _ gt  1 : ngẫu nhiên hoàn hảo; P _ gt  0,01 : Dãy xét<br /> Frequency P _ gt  0 : hoàn toàn không ngẫu thỏa mãn là dãy<br /> test P _ gt = ngẫu<br /> nhiên;<br /> 0,109599 nhiên<br /> P _ gt   : ngẫu nhiên;<br /> P _ gt   : không ngẫu nhiên.<br /> Frequency  N X 2 (obs )  P _ gt = P _ gt  0,01 : Dãy xét<br /> Test P _ gt = igamc ,    0,706438 thỏa mãn là dãy<br /> winthin a 2 2  ngẫu<br /> Block : ngẫu nhiên; nhiên<br /> <br /> <br /> <br /> Tạp chí Nghiên cứu KH&CN quân sự, Số 50, 08 - 2017 107<br />  Kỹ thuật điều khiển & Điện tử<br /> <br /> The Runs P _ gt P _ gt = P _ gt  0,01 : Dãy xét<br /> Test  2Vn (obs )  2n (1   )  0,500798 thỏa mãn là dãy<br />  erfc  <br />  ngẫu<br />  2 2n (1   )  Nhiên<br /> <br />  <br /> The Serial P _ gt1  igamc 2 m  2 ,  2  <br /> m<br /> P _ gt1 = P _ gt1; P _ gt 2 Dãy xét<br /> Test 0,9057  0,01 : thỏa mãn là dãy<br /> và ngẫu<br />  <br /> P _ gt 2  igamc 2 m 3 ,  m2   P _ gt 2 =<br /> Nhiên<br /> 0,8805<br /> The  m 1 X 2  P _ gt = P _ gt  0,01 : Dãy xét<br /> Approxim P _ gt  igamc 2 ,    0,261961 thỏa mãn là dãy<br /> ate  2  ngẫu<br /> Entropy Nhiên<br /> Test<br /> <br /> <br /> + 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<br /> thanh ghi bằng nhau và bằng 31 (là số nguyên tố).<br /> 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<br /> độ 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ụ<br /> 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<br /> 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ế.<br /> 4. KẾT LUẬN<br /> 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<br /> 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<br /> 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<br /> 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<br />   j, t  và   j, t  đã được định nghĩa, là những hàm phi tuyến (non-linear). Do vậy hàm<br /> hợp f  ( j , t ), ( j , t ) tạo ra dãy bít giả ngẫu nhiên được đề xuất là hàm phi tuyến.<br /> 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<br /> 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<br /> 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,<br /> 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<br /> 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<br /> 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<br /> 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.<br /> 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<br /> 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<br /> 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.<br /> TÀI LIỆU THAM KHẢO<br /> [1]. Andrew Rukhin, Juan Soto, James Nechvatal, Miles Smid, Elaine Barker, Stefan<br /> Leigh, Mark Levenson, Mark Vangel, David Banks, Alan Heckert, James Dray, San<br /> <br /> <br /> 108 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ã.”<br /> Nghiên cứu khoa học công nghệ<br /> <br /> Vo, “A Statistical Test Suite for Random and Pseudorandom Number Generators for<br /> Cryptographic Applications”, 2010.<br /> [2]. Andreas Klein, “Stream Ciphers”, Springer-Verlag London, 2013.<br /> [3]. A. Shamir “On the generation of cryptographically strong pseudorandom sequences”,<br /> ACM Transactions on Information Systems, 1983.<br /> [4]. L Blum,M Blum,M Shub, “A Simple Unpredictable Pseudo-Random Number<br /> Generator”, SIAM Journal on Computing, 1986, pp.364-383.<br /> [5]. Ashish Jain, Narendra S. Chaudhari: ‘‘Cryptanalytic Results on Knapsack<br /> Cryptosystem Using Binary Particle Swarm Optimization’’, International Conference<br /> on Computational Intelligence in Secuirty for Information System (CISIS 2014),<br /> Springer International Publishing, pp. 375-384, 2014;<br /> [6]. Bruce Schneier, “Applied Cryptography: Protocols, Algorithms, and Source Code in<br /> C”, Second Edition, John Wiley & Sons, 1996.<br /> [7]. Dieter Gollmann, “Pseudo random properties of cascade connections of clock<br /> controlled shift registers”, Advances in Cryptology. Proceedings of EURO-CRYPT<br /> 84 (LNCS 209), 1985;<br /> [8]. J Håstad, “Pseudo-Random Generators under Uniform Assumptions”, Proceedings of<br /> the 22nd Annual ACM Symposium on Theory of Computing, pp.395-404,1990;<br /> [9]. Kalendri, Maria; Pnevmatikatos, Dionisios; Papaefstathiou, Ioannis; Manifav-as,<br /> Charalampos, “Breaking The GSM A5/1 Cryptography. Algorithm with Rainbow<br /> Tables and High-end FPGAs”, In proc. Of 22nd International Con-ference on Field-<br /> programmable Logic and Applications, pp.747-753, 2012;<br /> [10]. Lano J., “Cryptanalysis and Design of Synchronous Stream Ciphers” PhD<br /> thesis, Katholieke Universiteit Leuven, Faculteit Ingenieurswetenschappen,<br /> Department Elektrolechnik_ESAT, 2006;<br /> [11]. M. Blum and S. Micali, “How to generate cryptographically strong sequences of of<br /> Pseudorandom bits”, Proceedings of the 23rd Annual Symposium on Foundations of<br /> Computer Science, IEEE, New York, pp. 112–117,1982<br /> [12]. Matthew Robshaw, Olivien Billet, “New Stream Cipher Designs: The eSTREAM<br /> Finalists”, Springer-Verlag Berlin, Heidelberg ©2008;<br /> [13]. D. Eastlake, S. Crocker and J. Schiller, “Randomness requirements for security”,<br /> Internet Request for Comments 1750, December 1994;<br /> [14]. W. Meier and O. Staffelbach, “Analysis of pseudo random sequences generated by<br /> cellular automata”, In EUROCRYPT ’91, Lecture Notes in Computer, Science.<br /> Springer Verlag, 1991;<br /> [15]. Wicker, S.B., “Error Control Systems for Digital Communication and Storage”,<br /> Englewood Cliffs: Prentice Hall, 1995.<br /> [16]. Martin K. Simon, Jim K. Omura, Robert A. Scholtz, Barry K. Levitt, ‘‘Spread<br /> spectrium commucications handbook’’, Mc Graw- Hill, Inc (Resived Editon) New<br /> York, London, Madrid, Mexico, City Milan, New Delhi, Singapror, Syney, Tokyo,<br /> Toronto, 2005.<br /> <br /> <br /> <br /> Tạp chí Nghiên cứu KH&CN quân sự, Số 50, 08 - 2017 109<br />  Kỹ thuật điều khiển & Điện tử<br /> <br /> ABSTRACT<br /> A PSEUDO-RANDOM NUMBER GENERATION METHOD<br /> FOR CRYPTOGRAPHIC APPLICATIONS<br /> Information protection by using crytography is an effective method, especially in<br /> the field of national security and defense. For crytography systems, the security<br /> depends much on the key. Therefore, the problem of key generation that guarantees<br /> the security of a cipher system is crucial in the field of information security. There<br /> are two basic key generation methods, namely random key generation and pseudo-<br /> random key generation. However, pseudo-random key generation method currently<br /> attracts more attention in the communication crytography. In the paper, a new<br /> pseudo-random key generation method which generate random bits using a<br /> generation algorithm based on Linear-feedback shift register (LFSR) to guarantee<br /> the security of the key used in crytography systems for national security and defense<br /> is proposed.<br /> Keywords: Cryptography; Cryptoanalysis; Linear-feedback shift register (LFSR); Pseudo-random key<br /> generation; Pseudo-random bit.<br /> <br /> <br /> Nhận bài ngày 21 tháng 6 năm 2017<br /> Hoàn thiện ngày 08 tháng 8 năm 2017<br /> Chấp nhận đăng ngày 18 tháng 8 năm 2017<br /> <br /> 1<br /> Địa chỉ: Cục Kỹ thuật, Bộ Công an;<br /> 2<br /> Cục Kỹ thuật nghiệp vụ, Tổng cục I, Bộ Công an.<br /> *<br /> Email: cuongqt34@yahoo.com.<br /> <br /> <br /> <br /> <br /> 110 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ã.”<br />