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

pdf
Số trang Phương pháp tạo dãy giả ngẫu nhiên để ứng dụng trong giao thức mật mã 13 Cỡ tệp Phương pháp tạo dãy giả ngẫu nhiên để ứng dụng trong giao thức mật mã 606 KB Lượt tải Phương pháp tạo dãy giả ngẫu nhiên để ứng dụng trong giao thức mật mã 0 Lượt đọc Phương pháp tạo dãy giả ngẫu nhiên để ứng dụng trong giao thức mật mã 5
Đánh giá Phương pháp tạo dãy giả ngẫu nhiên để ứng dụng trong giao thức mật mã
4.8 ( 10 lượt)
Nhấn vào bên dưới để tải tài liệu
Đang xem trước 10 trên tổng 13 trang, để tải xuống xem đầy đủ hãy nhấn vào bên trên
Chủ đề liên quan

Nội dung

Kỹ thuật điều khiển & Điện tử 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. 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ã.” Nghiên cứu khoa học công nghệ Đố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à 26 8 và không gian khóa thực tế nhiều nhất là 26 8 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 K  K1  K 2 ; Trong đó, 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ó 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 l l  k  . 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: n  p  q với p, q là hai số nguyên tố khác nhau và đủ lớn. Đặt:  (n)   p  1q  1 (2.1) Lấy b là một số nguyên sao cho: Ký hiệu: b, (n)   1 Z n*  1  x  n : x, n   1 Tạp chí Nghiên cứu KH&CN quân sự, Số 50, 08 - 2017 (2.2) 99 Kỹ thuật điều khiển & Điện tử Lấy một số r  Z n* và tính: x0  r , xi 1  xib (mod n) ; i  0,1,2,.. (2.3) Khi đó định nghĩa: Z i  xi mod 2  với i  1,2,.. (2.4) 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 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 n  p  q , trong đó p, q là 2 số nguyên tố khác nhau sao cho  p, q   3 mod 4 . Ký hiệu Q (n) là tập các thặng dư bình phương theo mod n . Với mỗi r  Q(n) , xác định dãy số x0 , x1 , x2 ,.. như sau: B1 : x0  r B2 : Với i  0,1,2,.. tính xi 1  xi2 mod n (2.5) B3 : Đặt Z i  xi mod 2 với i  0,1,2,.. B4 : Quay lại Z i  ; i  1,2,.. 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 Z *p , xác định dãy: x0  r xi 1  xi2 mod n (2.6) xi 1   mod p bây giờ đặt: xi  1ifxi  Zi   0ifx   i p 2 p 2 (2.7) 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. 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 Z *p 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 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ã.” Nghiên cứu khoa học công nghệ 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ừ 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. Đồ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: R  L, C ( x ) (3.1) trong đó: C( x)  1  C1 x1  ...  CL xL  GF ( 2)[ x] (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 i  0,1,.., L  1 . Khi đó, dãy S L1 ,.., S1 , S 0  được gọi là trạng thái ban đầu (khởi tạo) của thanh LFSR. Định nghĩa 3: Cho: C ( x )  GF ( 2)[ x ] là đa thức nguyên thủy (primitive polynomial) bậc L. Khi đó, ( L, C ( x) ) đượ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 L 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 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à 2 L  1 . 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 , L đ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ố 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à S L1 ,.., S1 , S 0  thì dãy đầu ra S  S0 , S1 ,.. được xác định một cách duy nhất bởi phép đệ quy (recursion) sau đây: S J  C1S j 1  C2 S j 2  ..  C L S j  L  mod 2 (3.3) đối với j  L . 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ỳ L 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 . 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ả 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 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 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 GF (2) [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 Tạp chí Nghiên cứu KH&CN quân sự, Số 50, 08 - 2017 101 Kỹ thuật điều khiển & Điện tử 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à R1 , R2 ,..RK , mỗi thanh ghi dịch Ri có độ dài Li ; i  1,2,..K . Trong đó, các Li 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à:  K1  K 2  b1b2 ..bm1  d1d 2 ..d m2 (3.4) Để dễ hình dung, ta lấy m1  20 , m2  10 , trong đó, bi , d j  a, b, c,.., z và K  5 , L1  L2  L3  L4  L5  31 . 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 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 phần, được cho trong bảng 1 sau đây: 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ã.” Nghiên cứu khoa học công nghệ A 1 1 0 0 0 B 1 0 0 1 1 C 0 1 1 1 0 D 1 0 0 1 0 E 1 0 0 0 0 F 1 0 1 1 0 G 0 1 0 1 1 H 0 0 1 0 1 I 0 1 1 0 0 J 1 1 0 1 0 K 1 1 1 1 0 L 0 1 0 0 1 M 0 0 1 1 1 N 0 0 1 1 0 O 0 0 0 1 1 P 0 1 1 0 1 Bảng 1. Bảng véc tơ nhị phân 5 thành phần. Q R S T U V W X Y Z 3 4 8 9 + / 1 0 1 0 1 0 1 1 1 1 0 0 1 0 1 0 1 1 0 0 1 1 1 0 0 0 0 1 1 0 1 0 1 0 1 0 1 1 0 1 1 0 0 0 1 1 0 0 0 1 0 0 0 1 0 1 0 0 1 0 1 0 1 0 1 0 0 1 0 1 1 1 1 1 0 0 1 0 1 0 Bây giờ ta đặt: 5 g1 ( )   2 j 1. j   1*  Z 32 j 1 (3.5) 5 j 1 * 1 g 2 ( )   2 . 6  j    Z 32 j 1 Trong đó,   1 ,  2 ,..,  5  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 K1 , K 2 lấp đầy các ô của 5 thanh ghi dịch thực hiện như sau: K1 Ký hiệu: các vectơ nhị phân của khóa K là b1 , b2 ,.., b20 , khóa 2 là d1 , d 2 ,.., d10 , với bt  (bi(1) , bi( 2 ) ,.., bi(5) ); i  1,20 (3.6) d t  (d i(1) , d i( 2 ) ,.., d i( 5) ); i  1,10 Ký hiệu yi( j ) là ô thứ i của thanh ghi R j với i  1, 2,..; j  1, 2,..,5 Đặt: yi( j )  1j  1, 5 yi(j1)  bi( j ) , i  1, 20, j  1,5 ( j) i  21 y (3.7) ( j) i c với ci( j ) là thành phần thứ j của vectơ nhị phân ci  (ci(1) , ci(2) , ci(3) , ci(4) , ci(5) ), i  1,10 và ci  [g 2 (di )-g1 (bi 10 )] mod32 Nói cách khác ci  g 21 (ci ) , trong đó, (3.8) ci  [g 2 (di )-g1 (bi 10 )] mod32 Tạp chí Nghiên cứu KH&CN quân sự, Số 50, 08 - 2017 103 Kỹ thuật điều khiển & Điện tử Các hàm g1 (.) , g 2 (.) được cho trong bảng 3.2, tức là   5 g1 bi   2 j 1 bi j mod 32 j 1   (3.9) 5 j 1 b i i g 2 bi   2 b mod 32 j 1 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 K1 và K 2 . 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à y1( j ) , y2( j ) ,.., y31( j ) và yij  0,1 , i  1, 31; j  1, 5 . 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 thứ t với t  1, 2,3,.. Ta có: *) Bước 1: Với t  1 ,     1(1) ,  1(2) ,  1(3) ,  1(4) ,  1(5)  (3.10) ( j) ( j) Trong đó,  1  y27 , j  1,5 *) Bước 2: Với i  1, 2,3,.. đặt ) ) , j  1, 5 yi(j31  yi( J )  yi(j28 (3.11) *) Bước 3: từ (3.10)(3.11), t  2,3,... tính     t(1) ,  t(2) ,  t(3) ,  t(4) ,  t(5)  , trong đó  t( j )  y( (j )j ,t ) 27 với j  1,5 (3.12) Và hàm hai biến  ( j, t ) được định nghĩa là:  ( j ,1)  0  ( j, t  1)   ( j, t )  ( j, t )  1 (3.13) đối với j  1,5; t  1, 2,3,.. Hàm  ( j, t ) được định nghĩa là:  (1, t )  1 với t  1, 2,3,..  (2, t )  y(1)(1,t )19  1  ( j  1, t )   ( j, t )  y( (j )j ,t )19  1 (3.14) với j  2,3, 4 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 t  1 . 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 K1 và bảng 4 đối với K 2 như sau: 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ã.” Nghiên cứu khoa học công nghệ CC Tt 1 2 3 4 5 J 1 1 0 1 0 O M P 0 0 0 1 1 0 0 1 1 1 Bảng 3. Lập bảng cho K1. O M D H J X B V K F M C N X R I 0 1 1 0 1 0 1 1 1 0 0 0 1 1 0 1 0 1 1 1 0 1 0 1 0 0 1 1 0 0 0 0 0 1 1 0 0 1 1 1 1 0 0 1 0 0 0 1 0 1 1 1 0 1 0 1 0 1 1 1 1 0 0 1 1 0 1 1 1 1 1 1 1 1 0 1 0 1 1 0 0 0 1 1 1 Bảng 4. Lập bảng cho K2. CC TT 1 2 3 4 5 C P W K V E E B S N 0 1 1 1 0 0 1 1 0 1 1 1 0 0 1 1 1 1 1 0 0 1 1 1 1 1 0 0 0 0 1 0 0 0 0 1 0 0 1 1 1 0 1 0 0 0 0 1 1 0 *) Bước 2: Lập các trạng thái ban đầu cho 5 thanh ghi dịch R1 , R2 ,..R5 Tính Ci , i  1,10 C1  g 2 (d1 )  g1 (b11 ) mod 32  g 2 (01110)  g1 (00111) mod 32  (14  28) mod 32  18 C2  g 2 (d 2 )  g1 (b12 )  (13  9) mod 32  4 C3  g3 (d3 )  g1 (b13 )  (25  20) mod 32  5 C4  19 ; C5  18 ; C6  23 ; C7  18 ; C8  4 ; C9  7 ; C10  10 Từ đó áp dụng bảng 3.2 ta có các kết quả: 1 1 C1  g 2 (C1 )  g 2 (18)  10010 1 1 1 1 C2  g 2 (C2 )  g 2 (4)  00100 1 1 1 1 1 1 1 1 C8  g 2 (C8 )  g 2 (4)  00100 1 C4  g 2 (C4 )  g 2 (19)  10011 1 1 C7  g 2 (C7 )  g 2 (18)  10010 C3  g 2 (C3 )  g 2 (5)  00101 1 1 C6  g 2 (C6 )  g 2 (23)  10111 C9  g 2 (C9 )  g 2 (7)  00111 1 C5  g 2 (C5 )  g 2 (18)  10010 C10  g 2 (C10 )  g 2 (10)  01010 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 R1 1 1 0 0 0 0 0 1 0 0 0 0 1 0 1 1 1 0 1 1 0 R2 1 1 0 0 1 1 R3 1 0 0 1 1 1 R4 1 1 1 1 0 1 R5 1 0 1 1 1 0 0 0 1 1 0 0 0 0 1 0 0 1 1 0 0 1 1 0 1 0 1 0 1 0 1 0 1 1 1 1 1 1 1 0 1 1 1 0 1 1 1 1 1 1 1 0 1 0 0 1 1 1 1 0 1 1 1 0 0 1 Tạp chí Nghiên cứu KH&CN quân sự, Số 50, 08 - 2017 105 Kỹ thuật điều khiển & Điện tử 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 0 0 1 1 1 1 0 0 0 1 1 0 1 1 0 1 0 0 1 0 R1 1 R2 0 0 0 0 0 0 0 0 0 1 1 1 1 1 0 0 1 0 1 0 0 R3 0 R4 1 1 1 0 0 1 0 1 1 0 0 1 0 1 0 1 0 1 1 1 1 0 0 1 1 1 1 0 1 1 1 0 0 0 0 1 1 1 0 1 0 R5 0 0 1 1 0 1 0 0 1 0 1 1 1 0 0 1 0 1 1 0 0 R1 43 44 45 46 47 48 49 50 51 52 53 54 55 … 0 0 0 1 1 1 1 0 0 1 1 0 1 … R2 1 0 0 0 0 0 1 1 0 1 1 0 1 … R3 0 1 0 0 0 0 1 1 1 0 1 0 1 … R4 1 0 0 0 1 1 1 0 0 0 1 0 0 … R5 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 j  1, 2,..,5; t  1, 2,3,.. i/ Theo (3.12), (3.13), (3.14) ta có:  ( j,1)  0; j  1,5  (1, t )  1; t  1, 2,3,.. ii/ Cuối cùng ta có bảng 6 tương ứng t  1, 2,3,.. như sau: t 1 1 0 2 1 2 3 1 4 4 1 6 5 1 8 6 1 10 Bảng 6. Bảng dãy giả ngẫu nhiên tương ứng. 7 8 9 10 11 12 13 14 15… 1 1 1 1 1 1 1 1 1… 12 14 16 18 20 22 24 26 28… R1  (1, t )  (1, t ) R2  (2, t )  (2, t ) t 1 0 0 2 1 1 3 1 3 4 0 5 5 0 6 6 1 7 7 1 9 8 0 11 9 0 12 10 1 13 11 1 15 12 0 17 13 1 18 14 1 20 15… 0… 22… R3 t 1  (3, t ) 0  (3, t ) 0 2 1 1 3 1 3 4 1 5 5 0 7 6 1 8 7 1 10 8 1 12 9 1 14 10 1 16 11 0 18 12 0 19 13 0 20 14 0 21 15… 0… 22… R4  (4, t )  (4, t ) t 1 0 0 2 1 1 3 1 3 4 0 5 5 0 6 6 1 7 7 0 9 8 0 10 9 1 11 10 1 13 11 1 15 12 0 17 13 1 18 14 1 20 15… 0… 22… R5 t 1  (5, t ) 0  (5, t ) 0 2 1 1 3 1 3 4 1 5 5 0 7 6 1 8 7 0 10 8 1 11 9 0 13 10 1 14 11 0 16 12 0 17 13 0 18 14 0 19 15… 0… 20… 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ã.” Nghiên cứu khoa học công nghệ iii/ Tạo dãy bit giả ngẫu nhiên Áp dụng công thức  t( j )  y( (j )j ,t ) 27 ; j  1,5; t  1, 2,..,15,.. 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à (231  1)5 . Để 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 GF ( p ) 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à: N p ( L)  ( p L  1) k ( pi  1)  p  1 i 1 pi (3.15) Trong đó, pi là những nhân tử nguyên tố của p L  1 Đặ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ì N p ( L)  ( p L  1) k (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 n  10.000 ) từ  :    1 ,  2 ,  3 ,..,  10.000 với  i  0,1, i  1..n 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 đó, 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). 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ả The P _ gt  1 : ngẫu nhiên hoàn hảo; Frequency P _ gt  0 : hoàn toàn không ngẫu test P _ gt = nhiên; 0,109599 P _ gt   : ngẫu nhiên; P _ gt   : không ngẫu nhiên. Frequency P _ gt =  N X 2 (obs )     0,706438 P _ gt = igamc , Test 2 2  winthin a Block : ngẫu nhiên; Tạp chí Nghiên cứu KH&CN quân sự, Số 50, 08 - 2017 So sánh P _ gt  0,01 : thỏa mãn P _ gt  0,01 : thỏa mãn Kết luận Dãy xét là dãy ngẫu nhiên Dãy xét là dãy ngẫu nhiên 107
This site is protected by reCAPTCHA and the Google Privacy Policy and Terms of Service apply.