Công nghệ thông tin & Cơ sở toán học cho tin học<br />
<br />
NGHIÊN CỨU XÂY DỰNG BỘ SINH SỐ NGẪU NHIÊN<br />
TÍCH HỢP VỚI NHIỀU HỆ ĐIỀU HÀNH<br />
Nguyễn Thị Tuyết Trinh*, Nguyễn Hồng Quang, Đinh Tiến Thành<br />
Tóm tắt: Hầu hết các bộ tạo số ngẫu nhiên thực phi vật lý có được nguồn<br />
entropy dựa vào sự bất ổn trong thời gian hoạt động của các sự kiện phần cứng, do<br />
đó, không đủ đáp ứng những nhu cầu luôn tăng của số ngẫu nhiên có chất lượng<br />
cao. Vì thế, cần tìm thêm các nguồn entropy phi vật lý khác thay thế. Bài báo này<br />
trình bày một nghiên cứu thiết kế bộ sinh số dựa trên hiện tượng jitter thời gian của<br />
CPU sử dụng trên hệ điều hành Linux và Windows. Số ngẫu nhiên sinh ra được<br />
đánh giá và vượt qua hầu hết các phép test thống kê của NIST. Tốc độ sinh bit cao,<br />
không cần thiết kế phần cứng chuyên dụng, phù hợp với nhiều hệ điều hành là<br />
những ưu điểm nổi trội so với các bộ sinh số khác.<br />
Từ khóa: Số ngẫu nhiên, Jitter thời gian của CPU, TRNG, Mật mã, Đánh giá thống kê.<br />
<br />
1. MỞ ĐẦU<br />
Số ngẫu nhiên đóng vai trò hết sức quan trọng trong rất nhiều lĩnh vực khác nhau mà<br />
đặc biệt là trong mật mã. Sự an toàn của hệ thống mật mã phụ thuộc rất nhiều vào tính<br />
ngẫu nhiên. Các bộ sinh số ngẫu nhiên có nguồn entropy phi vật lý không đòi hỏi phần<br />
cứng chuyên dụng mà khai thác các sự kiện hệ thống (thời gian của máy tính, số liệu trong<br />
RAM,...) và/hoặc sự tương tác người – máy (gõ phím, di chuyển chuột), thiết kế tương đối<br />
đơn giản, dễ thực hiện bằng phần mềm máy tính và giá thành hợp lý.<br />
Hiện nay, mỗi hệ điều hành đều có thể cung cấp nguồn entropy cho bộ sinh số ngẫu<br />
nhiên thực phi vật lý. Bộ sinh số ngẫu nhiên Linux (/dev/random) dựa trên bốn nguồn<br />
entropy khác nhau là thời gian giữa các lần gõ bàn phím và di chuột, thời gian truy cập bộ<br />
nhớ và các gián đoạn cụ thể ([2], [8]). Đầu ra được chuyển vào bộ trữ entropy có độ lớn<br />
512 byte. Tuy nhiên, chất lượng của số ngẫu nhiên không cao, chỉ được đánh giá như số<br />
giả ngẫu nhiên. Tương tự, hệ điều hành Windows cũng cung cấp thư viện mật mã Crypt<br />
API với các tính năng như mã hóa, giải mã, lưu trữ khóa, hàm băm, chữ ký số và và đặc<br />
biệt là bộ sinh số ngẫu nhiên. Nguồn entropy của bộ sinh số này là thời gian xử lý của<br />
CPU, thời gian hiện thời của hệ thống..., sau đó được xử lý qua hàm SHA-512, tạo ra đầu<br />
ra 512 bit ([2]). Tháng 10 năm 2014, Stephan Müller đã đề xuất bộ sinh số ngẫu nhiên<br />
thực phi vật lý dựa trên hiện tượng jitter thời gian của CPU với quá trình xử lý sau phức<br />
tạp, ảnh hưởng đến tốc độ và chỉ chạy trên hệ điều hành Linux ([1], [3]).<br />
Do đó, trong nghiên cứu này chúng tôi đề xuất một phương pháp riêng, xây dựng bộ<br />
sinh số ngẫu nhiên cũng có nguồn entropy là jitter thời gian của CPU nhưng có thiết kế<br />
đơn giản hơn, tốc độ thực thi cao và chạy được trên cả hệ điều hành Linux và Windows.<br />
2. THIẾT KẾ BỘ SINH SỐ NGẪU NHIÊN<br />
Sau khi nghiên cứu các sản phẩm của các tác giả khác, chúng tôi phân tích hiện tượng<br />
jitter thời gian của CPU sử dụng làm nguồn entropy, tiến hành thiết kế cụ thể, triển khai<br />
thử nghiệm để kiểm chứng.<br />
2.1. Jitter trong thời gian hoạt động của CPU<br />
Với sự phức tạp cao của các hệ điều hành hiện đại và hạt nhân nguyên khối lớn của<br />
chúng, tất cả các thành phần phần cứng phức tạp đều được sử dụng rộng rãi. Tuy nhiên, do<br />
sự phức tạp, không ai có thể xác định chính xác mức độ lấp đầy của các cache hoặc vị trí<br />
<br />
<br />
126 N. T. T. Trinh, …, Đ. T. Thành, “Nghiên cứu xây dựng bộ sinh số… nhiều hệ điều hành.”<br />
Nghiên cứu khoa học công nghệ<br />
<br />
chính xác của dữ liệu trong bộ nhớ tại một thời điểm nhất định nào đó. Điều đó dẫn đến<br />
việc thực hiện các lệnh có thể có các biến động rất nhỏ trong thời gian thực hiện. Ngoài ra<br />
CPU hiện đại có một bộ đếm thời gian độ phân giải cao, có thể xác định được các biến<br />
động rất nhỏ này. Ví dụ, CPU x86 hiện đại có một bộ định giờ TSC có độ phân giải trong<br />
phạm vi nano giây.<br />
Có thể nhận thấy những thay đổi trong thời gian thực hiện một bộ giống hệt các lệnh<br />
của CPU. Hình 1 minh họa sự biến đổi của thời gian thực hiện đoạn mã sau đây:<br />
static inline void jent_get_nstime(uint64_t *out)<br />
{...<br />
if (clock_gettime(CLOCK_REALTIME, &time) == 0)<br />
...}<br />
void main(void)<br />
{...<br />
jent_get_nstime(&time);<br />
jent_get_nstime(&time2);<br />
delta = time2 - time;<br />
...}<br />
Các giá trị của biến delta là không giống nhau giữa các lần lặp lại vòng lặp riêng<br />
lẻ. Khi chạy đoạn mã trên với 1.000.000 vòng lặp trên một hệ thống đang ở trạng thái tĩnh<br />
(không thực hiện các tác vụ khác) để giảm thiểu sai khác về thời gian do các quá trình đó<br />
gây ra.<br />
<br />
<br />
<br />
<br />
Hình 1. Phân bố sự biến đổi thời gian hoạt động của CPU.<br />
2.2. Mô hình bộ sinh số ngẫu nhiên<br />
Bộ sinh số ngẫu nhiên dựa trên hiện tượng jitter thời gian của CPU sử dụng bộ đọc thời<br />
gian có độ phân giải cao để lấy tem thời gian. Đầu ra của bộ sinh là một số nguyên dương<br />
có độ lớn 64 bit được lưu trong bộ trữ entropy (được minh họa với màu xám trong hình 2).<br />
Các hộp xám này xác định bộ trữ entropy tại hai thời điểm khác nhau trong xử lý.<br />
<br />
<br />
Tạp chí Nghiên cứu KH&CN quân sự, Số 52, 12 - 2017 127<br />
Công nghệ thông tin & Cơ sở toán học cho tin học<br />
<br />
<br />
<br />
<br />
Hình 2. Mô hình bộ sinh số ngẫu nhiên.<br />
Bộ sinh số ngẫu nhiên thực hiện vòng thu thập entropy như sau:<br />
Thực hiện truy cập bộ nhớ để tạo ra sự thay đổi thời gian:<br />
Hoạt động truy cập bộ nhớ được xây dựng bằng các giá trị sau: kích thước của khối bộ<br />
nhớ (memory block), số lượng của khối bộ nhớ tạo thành và số lượng của hoạt động truy<br />
cập được thực hiện. Việc truy cập bộ nhớ đảm bảo rằng tất cả các byte của bộ nhớ được<br />
truy cập đồng đều bằng cách duy trì một con trỏ đến byte cuối cùng trong bộ nhớ đã được<br />
truy cập.<br />
Lấy một tem thời gian để tính toán delta thời gian đến thời điểm tem thời gian của<br />
vòng lặp trước đó:<br />
Đầu tiên, trước khi lấy tem thời gian độ phân giải cao, gọi tới hàm jent_memaccess(ec,<br />
0) để thực hiện hoạt động truy cập bộ nhớ làm thêm sự biến động khi lấy tem thời gian<br />
CPU. Sau đó, thực hiện lấy tem thời gian với độ chính xác đến nano giây bằng cách sử<br />
dụng các hàm khác nhau cho hệ điều hành Linux và Windows:<br />
- Đối với hệ điều hành Linux, sử dụng hàm clock_gettime;<br />
- Đối với hệ điều hành Windows, sử dụng hàm QueryPerformanceCounter.<br />
Tùy chỉnh các hàm đếm thời gian có độ phân giải cao tương ứng với các hệ điều hành<br />
khác nhau, chúng tôi đã xây dựng được bộ sinh số ngẫu nhiên tương thích với đa hệ điều<br />
hành với tốc độ sinh bit cao.<br />
Gấp giá trị delta thời gian vào trong một bit. Xử lý giá trị vừa gấp được bằng xử lý<br />
Von-Neumann. Thêm giá trị này đến bộ trữ entropy sử dụng phép XOR. Xoay bộ trữ<br />
để điền vào các giá trị bit tiếp theo của bộ trữ.<br />
Giao diện của bộ tạo số ngẫu nhiên thực phi vật lý dựa trên hiện tượng jitter thời gian<br />
của CPU cung cấp cho người dùng một con trỏ vào bộ nhớ và biến có kích thước tùy ý.<br />
Khi có yêu cầu sinh ra một dòng bit số ngẫu nhiên với kích thước đã chọn, chuỗi bit này<br />
phải được lưu trữ tại vị trí bộ nhớ được trỏ đến.<br />
<br />
<br />
128 N. T. T. Trinh, …, Đ. T. Thành, “Nghiên cứu xây dựng bộ sinh số… nhiều hệ điều hành.”<br />
Nghiên cứu khoa học công nghệ<br />
<br />
3. THỰC NGHIỆM VÀ KIỂM CHỨNG KẾT QUẢ<br />
Tiến hành thử nghiệm sinh 1024 bit trên 3 máy tính khác nhau với cấu hình như sau:<br />
Máy 1: máy Dell Optiplex 390, chip Intel Core i3 2120, RAM 2GB, chạy<br />
Windows 7 Ultimate-64bit.<br />
Máy 2: máy Vaio VPCEL 13FX, chip AMD-E350, RAM 4GB, chạy Ubuntu<br />
16.04.<br />
Máy 3: máy Acer Travel Mate P243, chip Intel Pentium B970, RAM 2GB,<br />
chạy Windows 10-64bit.<br />
Chúng tôi sử dụng bộ tiêu chuẩn test thống kê của NIST. Mức có nghĩa α chọn bằng<br />
0,01 tức là độ tin cậy pˆ 1 99% . Khoảng tin cậy thực tế được tính bằng<br />
pˆ (1 pˆ )<br />
pˆ 3 , với m là số lượng chuỗi bit lấy ra. P-value được dùng để đo mức độ ngẫu<br />
m<br />
nhiên. Yêu cầu là P value thì số sinh ra được coi là ngẫu nhiên. Bảng dưới là kết quả<br />
đánh giá.<br />
Tên phép test Máy 1 Máy 2 Máy 3<br />
K.quả Đ.giá K.quả Đ.giá K.quả Đ.giá<br />
Test thời gian sinh số ngẫu 0,034 0,019 0,028<br />
nhiên (giây)<br />
Test tần suất (đơn bit) 0,657 P 0,391 P 0,341 P<br />
Test tần suất trong một khối 0,903 P 0,856 P 0,566 P<br />
bit<br />
Test các dãy bit 0,546 P 0,733 P 0,722 P<br />
Phép test dãy số 1 dài nhất 0,612 P 0,213 P 0,483 P<br />
trong một khối<br />
Test hạng ma trận nhị phân 0,258 P 0,456 P 0,134 P<br />
Test biến đổi Fourier rời rạc 0,008 F 0,026 P 0,087 P<br />
Test tìm các tổ hợp đã định, 0,914 P 0,744 P 0,511 P<br />
không chồng<br />
Test tìm các tổ hợp đã định, 0,845 P 0,903 P 0,803 P<br />
chồng nhau<br />
Test “Thống kê toàn bộ” 0,823 P 0,903 P 0,729 P<br />
Test độ phức tạp tuyến tính 0,406 P 0,546 P 0,478 P<br />
Test chuỗi m-bit 0,513 P 0,004 F 0,823 P<br />
Test entropy xấp xỉ 0,412 P 0,783 P 0,567 P<br />
Test tổng cộng dồn 0,745 P 0,453 P 0,611 P<br />
Test sự lệch ngẫu nhiên 0,398 P 0,912 P 0,547 P<br />
Test thay đổi của độ lệch ngẫu 0,584 P 0,584 P 0,005 F<br />
nhiên<br />
4. KẾT LUẬN<br />
Nghiên cứu về bộ sinh số ngẫu nhiên thực dựa trên hiện tượng jitter thời gian của CPU<br />
cho thấy có thể sử dụng bộ sinh số này trong các ứng dụng đòi hỏi độ an toàn cao, đặc biệt<br />
là trong mật mã. Bộ sinh số ngẫu nhiên có thể được sử dụng đồng bộ với ứng dụng sử<br />
dụng số ngẫu nhiên, chẳng hạn như sinh mầm cho bộ tạo số ngẫu nhiên tất định. Kết quả<br />
thực nghiệm cho thấy số ngẫu nhiên sinh ra đã vượt qua hầu hết các phép thử thống kê của<br />
NIST. Ưu điểm của bộ sinh số là tốc độ đáp ứng được yêu cầu sinh số ngẫu nhiên hiện<br />
nay, không yêu cầu mầm với dữ liệu từ các trạng thái trước đó của bộ tạo, nguồn entropy<br />
<br />
<br />
Tạp chí Nghiên cứu KH&CN quân sự, Số 52, 12 - 2017 129<br />
Công nghệ thông tin & Cơ sở toán học cho tin học<br />
<br />
cao, thiết kế đơn giản và dễ hiểu. So với các bộ sinh số ngẫu nhiên thực vật lý, bộ sinh số<br />
này không cần thiết kế vi mạch riêng, có thể chạy trên máy tính bất kỳ và trên nhiều hệ<br />
điều hành khác nhau.<br />
TÀI LIỆU THAM KHẢO<br />
[1]. Stephan Müller, “CPU Time Jitter Based Non-Physical True Random Number<br />
Generator”, 2016.<br />
[2]. Khudran Alzhrani, Khudran Alzhrani, “Windows and Linux Random Number<br />
Generation Process: A Comparative Analysis”, 2015.<br />
[3]. Stephan Müller, “CPU Time Jitter Based Non-Physical True Random Number<br />
Generator”, 2014.<br />
[4]. Mario Stipcevic, Cetin Kaya Koc, “True Random Number Generators”, 2012.<br />
[5]. Simona Buchovecká, “Analysis of a True Random Number Generator”, Czech<br />
Technical University in Prague, 2012.<br />
[6]. Jiří Sobotka, Václav Zeman, “Design of the true random numbers generator”, ISSN<br />
1213-1539 Vol. 2 (No. 3), 2011, p47-52.<br />
[7]. Andrew Rukhin, Juan Soto, James Nechvatal, Miles Smid, Elaine Barker, Stefan<br />
Leigh, Mark Levenson, Mark Vangel, David Banks, Alan Heckert, James Dray, San<br />
Vo, “A Statistical Test Suite for Random and Pseudorandom Number Generators for<br />
Cryptographic Applications”, NIST, Special Publication 800-22, 2010.<br />
[8]. Zvi Gutterman, Benny Pinkas, Tzachy Reinman, “Analysis of the Linux Random<br />
Number Generator”, 2006.<br />
ABSTRACT<br />
HIGH SPEED RANDOM NUMBER GENERATOR RUNS ON MULTIPLE<br />
OPERATING SYSTEMS<br />
Most of non-physical true random number generators obtain entropy source<br />
from time variances of hardware events which do not occur fast enough to satisfy<br />
the ever grown needs of high-quality random numbers. Therefore, additional<br />
sources of entropy must be opened up. In this paper, a reseach of designing CPU<br />
time jitter based non-physical true random number generator which runs on Linux<br />
and Windows operating systems is introduced. The generated random numbers have<br />
estimated by NIST statistic tests and overcomes most of them.<br />
Keywords: True random number, CPU time jitter, TRNG, Cryptography, Statistical test.<br />
<br />
Nhận bài ngày 11 tháng 07 năm 2017<br />
Hoàn thiện ngày 03 tháng 08 năm 2017<br />
Chấp nhận đăng ngày 20 tháng 12 năm 2017<br />
<br />
Địa chỉ: Học viện Kỹ thuật Mật mã – Ban Cơ yếu Chính phủ.<br />
* Email: nguyentuyettrinh189@gmail.com<br />
<br />
<br />
<br />
<br />
130 N. T. T. Trinh, …, Đ. T. Thành, “Nghiên cứu xây dựng bộ sinh số… nhiều hệ điều hành.”<br />