Kỹ thuật điều khiển & Điện tử<br />
<br />
THIẾT KẾ BỘ SINH SỐ NGẪU NHIÊN<br />
CÓ ĐỘ LỆCH THỐNG KÊ VÀ TƯƠNG QUAN THẤP<br />
Nguyễn Hồng Quang*<br />
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<br />
tố có thể ảnh hưởng đến độ lệch và tương quan trong các thiết kế đó; từ đó đề xuất<br />
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<br />
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ỉ<br />
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<br />
yêu cầu trích mẫu chậm đã được chứng minh.<br />
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ê.<br />
<br />
1. ĐẶT VẤN ĐỀ<br />
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.<br />
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ã.<br />
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<br />
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<br />
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<br />
[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à<br />
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<br />
với điều kiện / → ∞ kết hợp bộ đếm modulo 2 và điều kiện / → ∞ để giảm tự tương<br />
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<br />
nhiên khi ấy tốc độ bits ra sẽ giảm đáng kể.<br />
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 độ<br />
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ể<br />
giảm tương quan giữa các bits ngẫu nhiên mà không giảm tốc độ sinh bits.<br />
2. PHÂN TÍCH THIẾT KẾ SẴN CÓ<br />
<br />
<br />
<br />
<br />
Hình 1. Thiết kế của Baggini và Bucci [3].<br />
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 để<br />
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<br />
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<br />
và 1 trước khi đưa đến bộ cộng modulo 2.<br />
<br />
<br />
<br />
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.”<br />
Nghiên cứu khoa học công nghệ<br />
<br />
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<br />
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<br />
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<br />
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<br />
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<br />
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<br />
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<br />
chuỗi bit ra tiệm cận ngẫu nhiên khi → ∞.<br />
<br />
<br />
<br />
<br />
Hình 2. Thiết kế của Stipcevic [2].<br />
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à<br />
đ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<br />
hằng số thời gian = ( + ). Điện áp của hai nhiễu khác nhau xảy ra trong khoảng<br />
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 để<br />
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<br />
một lượng , và hằng số thời gian tổng cộng bằng:<br />
<br />
= + (1)<br />
<br />
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<br />
hiệu nhiều hơn.<br />
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ó<br />
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ẽ<br />
đượ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<br />
đượ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<br />
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<br />
của bộ sinh.<br />
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á<br />
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<br />
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<br />
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.<br />
3. THIẾT KẾ MỚI<br />
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<br />
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<br />
<br />
<br />
Tạp chí Nghiên cứu KH&CN quân sự, Số 41, 02 - 2016 77<br />
Kỹ thuật điều khiển & Điện tử<br />
<br />
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<br />
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.<br />
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<br />
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<br />
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<br />
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<br />
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à<br />
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<br />
phần giảm tương quan. R3 cấp dòng cho transistor hở collector, P3 xác định ngưỡng cho<br />
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<br />
đế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<br />
độ 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 , ….<br />
<br />
<br />
<br />
<br />
Hình 3. Thiết kế mới.<br />
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<br />
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<br />
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<br />
chuyển trạng thái. Giả sử sự xuyên áp xảy ra tại các thời điểm = 0, , , , , …<br />
Các khoảng thời gian giữa các lần xuyên áp kề nhau là ∆ = − , = 1, 2, 3 … Giá<br />
trị trung bình của các khoảng này tính theo [2]:<br />
<br />
1 (2)<br />
= lim ∆<br />
→<br />
<br />
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à<br />
T flip-flop chuyển trạng thái tại đầu ra lần từ = 0 đến = , lần từ = đến<br />
= 2 và nói chung lần từ = đến = ( + 1) , trong đó = 1, 2, 3 …, thì có thể<br />
coi mỗi chu kỳ trích mẫu bằng tổng của nhiều khoảng ∆ :<br />
<br />
<br />
≈ ∆ (3)<br />
<br />
<br />
<br />
<br />
78 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.”<br />
Nghiên cứu khoa học công nghệ<br />
<br />
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à<br />
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<br />
như xấp xỉ T. Kết hợp với (2) ta có kết quả:<br />
<br />
≈ (4)<br />
<br />
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<br />
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<br />
sinh ra “1” tại đầu ra của bộ trích mẫu. Có nghĩa / → ∞ thì độ lệch → 0.<br />
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<br />
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ớ<br />
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<br />
/ → ∞ 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<br />
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<br />
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<br />
đ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<br />
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<br />
thực tế.<br />
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<br />
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ụ<br />
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<br />
khiến optocoupler rất nhạy, phản ứng tốt với nhiễu ngẫu nhiên biên độ nhỏ.<br />
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á<br />
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<br />
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á<br />
trình vật lý của nguồn nhiễu.<br />
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<br />
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à<br />
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<br />
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.<br />
4. KẾT QUẢ<br />
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<br />
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<br />
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<br />
khi vẫn bảo đảm điều kiện ≫ .<br />
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ớ<br />
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<br />
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<br />
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;<br />
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ẽ<br />
nhờ đó tốc độ sinh cao.<br />
<br />
<br />
<br />
Tạp chí Nghiên cứu KH&CN quân sự, Số 41, 02 - 2016 79<br />
Kỹ thuật điều khiển & Điện tử<br />
<br />
TÀI LIỆU THAM KHẢO<br />
[1]. Mario Stipčević và Çetin Kaya Koç, “True Random Number Generators; Open<br />
Problems in Mathematics and Computational Science”; Springer International<br />
Publishing Switzerland, 2014.<br />
[2]. Mario Stipčević, “Fast nondeterministic random bit generator based on weakly<br />
correlated physical events”, Review of Scientific Instruments, 2004.<br />
[3]. V. Bagini and M. Bucci. “A design of reliable true random number generator for<br />
cryptographic applications”. Cryptographic Hardware and Embedded Systems<br />
(CHES), Springer 2002.<br />
[4]. “Optocoupler Designer’s Guide”, Agilent Technologies, 2002.<br />
ABSTRACT<br />
A TRUE RANDOM GENERATOR<br />
WITH LOW STATISTICAL BIAS AND CORRELATION<br />
In the article author analyzes some true random generators, shows existing<br />
factors that influence statistical bias and correlation and proposes another modified<br />
generator that can reduce the bias between 0 and 1 logics and serial correlation.<br />
The new generator is not only well improves statistical criteria but increases<br />
productivity generating of the random bits while keeps the proved slow extricated<br />
based requirement.<br />
Keywords: True random bit, Bias, Serial correlation, Noise, Cryptography, Statistical test.<br />
<br />
Nhận bài ngày 06 tháng 01 năm 2016.<br />
Hoàn thiện ngày 15 tháng 02 năm 2016.<br />
Chấp nhận đăng ngày 22 tháng 02 năm 2016.<br />
<br />
<br />
Địa chỉ: Học viện Kỹ thuật Mật mã - Ban Cơ Yếu Chính Phủ.<br />
<br />
<br />
<br />
<br />
80 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.”<br />