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

Kỹ thuật điều khiển & Điện tử 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.” 76 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ất khiê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ững nghiê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ệch với điều kiện / → ∞ kết hợp bộ đếm modulo 2 và điều kiện / → ∞ để giảm tự tương quan, có nghĩa trích mẫu chậm sẽ đạt được độ lệch và tự tương quan đến yêu cầu. Tuy nhiê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êm và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 0 và 1 trước khi đưa đến bộ cộng modulo 2. Nghiên cứu khoa học công nghệ Tạp chí Nghiên cứu KH&CN quân sự, Số 41, 02 - 2016 77 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ẫu hoạ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ưa phó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 áp trướ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ầy quá 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 đầu và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 bit thật chậm so với tần số trích mẫu ngẫu nhiên , chẳng hạn = /, như vậy chuỗ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ới hằng số thời gian = ( + ). Điện áp của hai nhiễu khác nhau xảy ra trong khoảng thờ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êm mộ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ín hiệ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 quan cà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 ra củ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 đất má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ật lý 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ệu nhiễ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 ly Kỹ thuật điều khiển & Điện tử 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.” 78 quang học dẫn tín hiệu nhiễu thay thế vai trò tụ C. Ảnh hưởng từ máy tính sang cũng được loại trừ do không có sự liên hệ vật lý giữa nguồn nhiễu và máy tính. Nguồn nhiễu lấy từ tiếp giáp p-n của transistor Q2 định thiên ngược, tác dụng giống như diode zener nhưng có độ nhạy cao hơn. Mạch điện gồm Q1, R1, R2, P2 và các diodes D1 và D2 tạo thành nguồn dòng giúp ổn định chế độ làm việc của nguồn nhiễu. P2 để tạo thế một chiều cân bằng giữa anode và cathode đảm bảo photo diode chỉ thông với nhiễu xoay chiều. Optocoupler dẫn tín hiệu nhiễu trong khi cách ly đất giữa hai mạch điện, và cũng đóng vai trò bộ lọc thông thấp giúp T flip-flop ở phần sau hoạt động thưa hơn, góp phần giảm tương quan. R3 cấp dòng cho transistor hở collector, P3 xác định ngưỡng cho bộ so sánh. T flip-flop chuyển trạng thái liên tục mỗi khi có sườn xung từ bộ so sánh đưa đến, cân bằng giá trị trung bình các khoảng thời gian tồn tại 0 và 1, có tác dụng làm giảm độ lệch. D trigger chốt dữ liệu theo lệnh trích xuất với tại các thời điểm , 2, 3, . Hình 3. Thiết kế mới. Mỗi khi chịu sự xuyên thủng điện áp, tiếp giáp p-n sẽ sinh ra điện áp analog vượt ngưỡng bộ so sánh. Các thời điểm xuyên áp liên tiếp là độc lập thống kê vì đó là hiện tượng vật lý không thể dự đoán được. Đầu ra bộ so sánh xuất hiện xung làm T flip-flop chuyển trạng thái. Giả sử sự xuyên áp xảy ra tại các thời điểm = 0, , , , , Các khoảng thời gian giữa các lần xuyên áp kề nhau là ∆ = − , = 1, 2, 3 Giá trị trung bình  của các khoảng này tính theo [2]: = lim → 1 ∆ (2) Khi ≫ thì trong khoảng thời gian của một T xảy ra nhiều lần xuyên áp. Giả thiết là T flip-flop chuyển trạng thái tại đầu ra lần từ = 0 đến = , lần từ = đến = 2 và nói chung lần từ = đến = ( + 1), trong đó = 1, 2, 3 , thì có thể coi mỗi chu kỳ trích mẫu bằng tổng của nhiều khoảng ∆: ≈ ∆ (3) Nghiên cứu khoa học công nghệ Tạp chí Nghiên cứu KH&CN quân sự, Số 41, 02 - 2016 79 Các biểu thức trên chỉ tính xấp xỉ vì một phần của ∆ đầu có thể nằm ở chu kỳ trước, và một phần của ∆ cuối lại nằm ở chu kỳ sau. Nếu chu kỳ trích mẫu T đủ lớn thì tổng này coi như xấp xỉ T. Kết hợp với (2) ta có kết quả: ≈ (4) Theo [2] ta có xác suất để biến ngẫu nhiên N chẵn bằng xác suất để nó là lẻ, xảy ra khi / → ∞. Như vậy, nếu trích mẫu chậm thì xác suất sinh ra “0” sẽ bằng xác suất sinh ra “1” tại đầu ra của bộ trích mẫu. Có nghĩa / → ∞ thì độ lệch → 0. Tính chất nhớ là điều không tránh khỏi nếu trong mạch điện sử dụng các phần tử điện dung. Tính nhớ này sẽ suy giảm theo hàm mũ trong nửa chu kỳ  Ảnh hưởng của sự nhớ lên sự tương quan có thể nhỏ nếu trích mẫu chậm, nhờ làm cho / đủ lớn tức là, khi / → ∞ thì các tổng (3) trở thành độc lập thống kê với nhau [2], [3]. Nếu hai tổng không kề nhau thì hiệu ứng nhớ còn nhỏ hơn. Có nghĩa một bit sẽ trở nên độc lập thống kê với bit lân cận và thậm chí còn độc lập nhiều hơn với các bits khác, nếu thỏa mãn điều kiện trích mẫu chậm. Về lý thì có thể đạt độ tương quan nhỏ theo yêu cầu, nhưng trích mẫu chậm sẽ ảnh hưởng nhiều đến hiệu suất sinh bits ngẫu nhiên trong hoạt động thực tế. Trong thiết kế mới này chúng tôi giải quyết vấn đề bằng cách sử dụng bộ cách ly quang học HCPL-4701 [4] làm phần tử cách ly một chiều và dẫn tín hiệu thay thế tụ C. Do không có phần tử điện dung nên không tồn tại  của (1). Dòng = 40 khiến optocoupler rất nhạy, phản ứng tốt với nhiễu ngẫu nhiên biên độ nhỏ. Optocoupler còn có tác dụng lọc thông thấp tránh cho T flip-flop chuyển mạch quá dầy sẽ tự sinh tương quan giữa các bit liền kề. Cách ly nguồn Vcc1 và Vcc2 và đất GND1 và GND2 có tác dụng loại trừ ảnh hưởng của các mạch xử lý phía sau lên quá trình vật lý của nguồn nhiễu. Vấn đề tương quan còn được giải quyết triệt để hơn nếu các thời điểm trích mẫu cách xa nhau. Để không làm giảm hiệu suất, chúng tôi không thay đổi tần số trích mẫu mà xen kẽ các bits lấy ra trong khoảng cách đủ lớn, triệt tiêu hoàn toàn tự tương quan các bits liền kề. Dễ dàng thực hiện điều này bằng phần cứng hoặc phần mềm. 4. KẾT QUẢ Chúng tôi đã thực nghiệm với mạch đề xuất, kết quả đánh giá cho thấy các số ngẫu nhiên sinh ra vượt qua bộ đánh giá ngẫu nhiên theo xác suất thống kê của NIST, độ lệch và độ tương quan rất tốt so với các mạch đã nói, tốc độ sinh đến xấp xỉ 100 kBd trong khi vẫn bảo đảm điều kiện ≫ . Sở dĩ đạt được kết quả đó là nhờ những cải tiến quan trọng sau: loại bỏ phần tử nhớ do đó không còn hằng số thời gian triệt tiêu hiệu ứng nhớ; cách ly vật lý nguồn nhiễu với mạch điện tử phía sau, do đó giảm tối đa ảnh hưởng các quá trình tất định trên PC qua đường nguồn và đất; nguồn dòng một chiều giúp nguồn nhiễu hoạt động ổn định; chu kỳ trích mẫu vẫn giữ đủ lớn để các bit độc lập thống kê nhưng cách trích xuất xen kẽ nhờ đó tốc độ sinh cao. Kỹ thuật điều khiển & Điện tử 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.” 80 TÀI LIỆU THAM KHẢO [1]. Mario Stipčević và Çetin Kaya Koç, “True Random Number Generators; Open Problems in Mathematics and Computational Science”; Springer International Publishing Switzerland, 2014. [2]. Mario Stipčević, “Fast nondeterministic random bit generator based on weakly correlated physical events”, Review of Scientific Instruments, 2004. [3]. V. Bagini and M. Bucci. “A design of reliable true random number generator for cryptographic applications”. Cryptographic Hardware and Embedded Systems (CHES), Springer 2002. [4]. “Optocoupler Designer’s Guide”, Agilent Technologies, 2002. ABSTRACT A TRUE RANDOM GENERATOR WITH LOW STATISTICAL BIAS AND CORRELATION In the article author analyzes some true random generators, shows existing factors that influence statistical bias and correlation and proposes another modified generator that can reduce the bias between 0 and 1 logics and serial correlation. The new generator is not only well improves statistical criteria but increases productivity generating of the random bits while keeps the proved slow extricated based requirement. Keywords: True random bit, Bias, Serial correlation, Noise, Cryptography, Statistical test. Nhận bài ngày 06 tháng 01 năm 2016. Hoàn thiện ngày 15 tháng 02 năm 2016. Chấp nhận đăng ngày 22 tháng 02 năm 2016. Địa chỉ: Học viện Kỹ thuật Mật mã - Ban Cơ Yếu Chính Phủ.