Thiết kế bộ sinh số ngẫu nhiên có độ lệch thống kê và tương quan thấp

Bài báo phân tích một số bộ sinh số ngẫu nhiên đã có, chỉ ra những yếu tố có thể ảnh hưởng đến độ lệch và tương quan trong các thiết kế đó; từ đó đề xuất một bộ sinh số ngẫu nhiên với những cải tiến quan trọng nhằm giảm độ lệch 0 và 1 và độ tương quan giữa các bits kề nhau. Bộ sinh mới không chỉ cải thiện tốt các chỉ tiêu thống kê của các bits ngẫu nhiên mà còn tăng hiệu suất trong khi vẫn đảm bảo yêu cầu trích mẫu chậm đã được chứng minh.
Nội dung trích xuất từ tài liệu:
Thiết kế bộ sinh số ngẫu nhiên có độ lệch thống kê và tương quan thấpKỹ thuật điều khiển & Điện tử THIẾT KẾ BỘ SINH SỐ NGẪU NHIÊN CÓ ĐỘ LỆCH THỐNG KÊ VÀ TƯƠNG QUAN THẤP Nguyễn Hồng Quang* Tóm tắt: Bài báo phân tích một số bộ sinh số ngẫu nhiên đã có, chỉ ra những yếu tố có thể ảnh hưởng đến độ lệch và tương quan trong các thiết kế đó; từ đó đề xuất một bộ sinh số ngẫu nhiên với những cải tiến quan trọng nhằm giảm độ lệch 0 và 1 và độ tương quan giữa các bits kề nhau. Bộ sinh mới không chỉ cải thiện tốt các chỉ tiêu thống kê của các bits ngẫu nhiên mà còn tăng hiệu suất trong khi vẫn đảm bảo yêu cầu trích mẫu chậm đã được chứng minh.Từ khóa: Số ngẫu nhiên thực, Độ lệch, Tự tương quan, Nhiễu, Mật mã, Đánh giá thống kê. 1. ĐẶT VẤN ĐỀ Số ngẫu nhiên đóng vai trò quyết định sự an toàn trong các giao thức mật mã hiện đại.Nghiên cứu về sinh số ngẫu nhiên là một trong những chủ đề nóng trong lĩnh vực mật mã.Tuy nhiên, có sự khác biệt lớn giữa số lượng rất nhiều bài báo đã công bố với số lượng rấtkhiêm tốn của các bộ sinh số ngẫu nhiên xuất hiện trên thị trường, điều đó cho thấy nhữngnghiên cứu này còn chưa hoàn thiện, việc nghiên cứu sinh số ngẫu nhiên vẫn đang tiếp tục[1]. Vấn đề khó khăn trong sinh số ngẫu nhiên mà các nghiên cứu cố tìm cách giải quyết làsự lệch xác suất và sự tương quan giữa các bits ra. Trong [2] tác giả đã giải quyết độ lệchvới điều kiện / → ∞ kết hợp bộ đếm modulo 2 và điều kiện / → ∞ để giảm tự tươngquan, có nghĩa trích mẫu chậm sẽ đạt được độ lệch và tự tương quan đến yêu cầu. Tuynhiên khi ấy tốc độ bits ra sẽ giảm đáng kể. Bài báo này sẽ phân tích các thiết kế trước, chỉ ra những yếu tố nào ảnh hưởng đến độlệch và tương quan và đề xuất một giải pháp thực tế bộ sinh số ngẫu nhiên thực, có thểgiảm tương quan giữa các bits ngẫu nhiên mà không giảm tốc độ sinh bits. 2. PHÂN TÍCH THIẾT KẾ SẴN CÓ Hình 1. Thiết kế của Baggini và Bucci [3]. Hình 1 là thiết kế của Baggini và Bucci [3]. Tác giả sử dụng sử dụng T flip-flop đểgiảm độ lệch xác suất. Hình 2 là thiết kế của Stipcevic [2], tác giả cải tiến bằng cách thêmvào đường hồi tiếp nhằm điều chỉnh ngưỡng của bộ so sánh để cân bằng sơ bộ thời gian 0và 1 trước khi đưa đến bộ cộng modulo 2.76 N.H. Quang, “Thiết kế bộ sinh số ngẫu nhiên có độ lệch thống kê và tương quan thấp.”Nghiên cứu khoa học công nghệ Vấn đề đối với cả hai thiết kế này là độ tương quan. Trong thiết kế hình 1, tụ giữ mẫuhoạt động như một phần tử nhớ nhớ điện áp analog. Tại điện áp tiếp theo, do tụ chưaphóng hết vì sự tồn tại trở kháng trong mạch, nên điện áp này sẽ nối thêm vào điện áptrước đó, và như vậy tạo ra sự tương quan. Vấn đề thứ hai là nếu T flip-flop hoạt động dầyquá thì nhiều khi nó sẽ tạo kết quả giống nhau gây ra tự tương quan ở đầu ra, kể cả khi đầuvào thực sự ngẫu nhiên. Chỉ có một cách vượt qua điều này là sử dụng tần số lấy bitthật chậm so với tần số trích mẫu ngẫu nhiên , chẳng hạn = / , như vậychuỗi bit ra tiệm cận ngẫu nhiên khi → ∞. Hình 2. Thiết kế của Stipcevic [2]. Trong thiết kế ở hình 2, tụ dẫn tín hiệu C nối tiếp với điện trở R của nguồn nhiễu vàđiện trở hiệu dụng đầu vào của bộ so sánh tạo thành một mạch có tính chất nhớ, vớihằng số thời gian = ( + ). Điện áp của hai nhiễu khác nhau xảy ra trong khoảngthời gian sẽ có sự tương quan qua lại vì điện nạp trong tụ C không có thời gian đểphóng qua các điện trở đó. Do có sự tương quan này mà hằng số thời gian tổng tăng thêmmột lượng , và hằng số thời gian tổng cộng bằng: = + (1)tức là tính “nhớ” của mạch điện tăng lên hay nói cách khác, sự tương quan giữa các tínhiệu nhiều hơn. Do hiệu ứng nhớ này suy giảm theo hàm mũ trong khoảng thời gian giữa hai nhiễu, cóthể kết luận là hai nhiễu cách nhau đủ xa coi như độc lập thống kê. Tính tự tương quan sẽđược giải quyết khi thỏa mãn điều kiện trích mẫu chậm sao cho ≫ . Như vậy để sinhđược một bit ngẫu nhiên cần N sự kiện ngẫu nhiên. N càng lớn thì độ lệch và tương quancàng nhỏ. Điểm yếu của phương pháp này là làm giảm băng thông và giảm tốc độ bits racủa bộ sinh. Ngoài ra, để truyền tín hiệu từ bộ sinh sang máy tính cho mục đích kiểm tra đánh giáchuỗi digital bits theo các tiêu chuẩn thống kê, phải nối chung đất nguồn nhiễu với đấtmáy tính. Quá trình làm việc trên máy tính là tất định, sẽ gây ảnh hưởng đến quá trình vậtlý trong nguồn nhiễu, làm nguồn nhiễu không còn hoàn toàn độc lập nữa. 3. THIẾT KẾ MỚI Trong thiết kế do chúng tôi đề xuất, không xử dụng tụ C làm phần tử dẫn tín hiệunhiễu, cũng không cần mạch lưu giữ mẫu, do đó hiệu ứng nhớ được triệt tiêu. Bộ cách lyTạp chí Nghi ...