Nghiên cứu xây dựng bộ sinh số ngẫu nhiên tích hợp với nhiều hệ điều hành

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