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ường

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.