Nghiên cứu nguồn nhiễu có entropy cao dựa trên nửa bền cho ứng dụng sinh số ngẫu nhiên thực

Nghiên cứu khoa học công nghệ Tạp chí Nghiên cứu KH&CN quân sự, Số 42, 04 - 2016 133 NGHIÊN CỨU NGUỒN NHIỄU CÓ ENTROPY CAO DỰA TRÊN NỬA BỀN CHO ỨNG DỤNG SINH SỐ NGẪU NHIÊN THỰC Nguyễn Hồng Quang* Tóm tắt: Số ngẫu nhiên thực là thành phần quan trọng và quyết định độ an toàn của mật mã hiện đại. Thiết kế nguồn nhiễu ngẫu nhiên analog thường phức tạp, khó tích hợp trong các mạch digital và thường phải kèm xử lý sau dẫn đến đưa thêm thành phần tất định vào kết quả ra. Bài báo này trình bày một nghiên cứu nguồn ngẫu nhiên hoàn toàn digital, dựa trên khai thác hiện tượng nửa bền trong mạch điện tử số, có entropy cao, tương quan thấp, không cần xử lý sau. Nguồn nhiễu đã được đánh giá và vượt qua các phép test thống kê của NIST. Từ khóa: Số ngẫu nhiên thực, Nửa bền, Tự tương quan, TRNG, Mật mã, Đánh giá thống kê. 1. ĐẶT VẤN ĐỀ Số ngẫu nhiên là thành phần quan trọng của mật mã hiện đại. An toàn của hầu hết các hệ thống mật mã đều dựa trên việc đối phương không thể đoán được khóa hay số ngẫu nhiên sử dụng. Các TRNG truyền thống, dù sử dùng entropy từ nhiễu nhiệt Johnson, hiệu ứng Jitter, phân ra phóng xạ, hỗn loạn hay lượng tử đều là nguồn analog. Nhiễu từ các nguồn này thường rất nhỏ, và thường nhạy với những biến động của nguồn nuôi và môi trường, đòi hỏi thiết kế và bố trí đặc biệt, và khó tích hợp nguồn nhiễu analog như vậy vào các hệ thống số. Bởi vậy tìm một nguồn nhiễu digital có entropy đủ cao, thuận lợi cho tích hợp trong FPGA luôn là nhu cầu. Chất lượng số ngẫu nhiên thực phụ thuộc vào entropy của nguồn nhiễu. Nguồn nhiễu entropy cao như phân rã phóng xạ hay lượng tử thường phức tạp và giá thành rất cao. Các thiết kế thực tế thường nhắm vào những nguồn nhiễu dễ thực hiện, kết hợp xử lý sau để cải thiện các đặc tính thống kê của số ngẫu nhiên. Mặc dù xử lý sau góp phần làm tăng chất lượng ngẫu nhiên nhưng lại làm tất định hóa cái cần bất định. Nghiên cứu nguồn ngẫu nhiên chất lượng để có thể sử dụng trực tiếp các bits, không cần xử lý sau, luôn là điều thách thức. Bài báo đề xuất một nghiên cứu nguồn ngẫu nhiên phi truyền thống, không chứa thành phần analog, dễ tích hợp vào các thiết kế digital, có entropy cao, không cần xử lý sau. Thiết kế mới này đã được kiểm chứng các đặc tính thống kê qua bộ tiêu chuẩn đánh giá số ngẫu nhiên của NIST và đã vượt qua tất cả các yêu cầu. 2. NGHIÊN CỨU NGUỒN ENTROPY CAO DỰA TRÊN NỬA BỀN 2.1. Các nghiên cứu liên quan Các nghiên cứu nhằm đạt được nguồn nhiễu hoàn toàn digital phần lớn đều xoay quanh hiện tượng jitter trong mạch điện tử. Một trong những nghiên cứu digital TRNG đầu tiên là của nhóm tác giả đứng đầu là R. Fairfeld [1]. Họ sử dụng nhiễu pha trong các bộ dao động tự do và dùng bộ dao động tần số thấp trích mẫu bộ dao động tần số cao. V. Fischer và M. Duratovsky [10] đề xuất hai hệ thống PLL sinh ra jitter ngẫu nhiên. Còn Sunar và các cộng sự [6] đề xuất nguồn ngẫu nhiên từ jitter giữa các bộ dao động vòng tự do RO, với đầu ra được XOR với nhau. Bock, Bucci và Luzzi đã đề xuất một sơ đồ có các bộ dao động được tái đồng bộ trước mỗi lần sinh bit [8], nhờ đó khắc chế được hoạt động theo chu kỳ của nguồn entropy và khởi động lại nguồn sau mỗi bit sinh ra. Fisher và Drutarovsky đề xuất trích mẫu jitter bằng một số flip-flop dịch trong khoảng thời gian không xác định [10]. Một loại nguồn ngẫu nhiên khác khai thác tính chất nửa bền của tín hiệu trong mạch điện tử, xuất hiện khi các mạch logic chuyển trạng thái ở thời điểm các tín Công nghệ thông tin & Khoa học máy tính Nguyễn Hồng Quang, “Nghiên cứu nguồn nhiễu có Entropy sinh số ngẫu nhiên thực.” 134 hiệu vào data và clock vi phạm các yêu cầu timing và . Trong trạng thái này, tín hiệu ra trôi nổi trong khoảng giữa mức logic cao vào thấp và mang tính ngẫu nhiên [7], [10]. Golic đã kết hợp tính nửa bền của D flip-flop với jitter trong RO trong [7]. H.Hata trong [1] khai thác nửa bền của chốt RS. Tuy tính nửa bền có thể được khai thác như nguồn nhiễu ngẫu nhiên, nhưng nửa bền tự nhiên xảy ra với thời gian rất ngắn và không ổn định. Bởi vậy, nhiều nghiên cứu TRNG đã tìm cách cải thiện nửa bền tự nhiên [2], [4]. Trong nghiên cứu này chúng tôi đề xuất một phương pháp riêng, ép các vòng dao động tự do RO vào trạng thái nửa bền, và sử dụng nhiều RO để tăng entropy nguồn nhiễu. Sau mỗi bit ngẫu nhiên trích xuất ra, nguồn nhiễu lại được reset để đi vào trạng thái nửa bền mới. Bằng cách này giảm thiệu tự tương quan và tăng hiệu suất sinh số ngẫu nhiên. 2.2. Nội dung nghiên cứu 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 nửa bền trong mạch điện tử 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. Một RO có thể được tạo ra với số lẻ các bộ đảo. Trong [4] các tác giả đã bằng thực nghiệm chứng minh sự tồn tại của nửa bền trong TERO, trong [2] là mô hình toán học phân tích và đánh giá entropy nửa bền đó. Do TERO gồm số chẵn mạch đảo nên sau một khoảng thời gian ngắn, dao động sẽ tự tắt. Trong thiết kế này ta chỉ khai thác nửa bền của RO ở giai đoạn trước dao động ổn định Hình 1. Hình 1. Các giai đoạn trong bộ dao động vòng. Thời gian nửa bền được tính như sau [10]: = ( × × × ) MTBF là thời gian giữa các lần lỗi mạch do nửa bền gây ra. và là tần số clock và tần số chuyển mạch tín hiệu vào. và là các hằng số, phụ thuộc vào công nghệ chế tạo linh kiện. thường rất ngắn. Có thể tăng thời gian này khi tăng tần số chuyển mạch bằng cách chọn phần tử đảo CMOS có độ khuếch đại lớn và trễ lan truyền nhỏ, hoặc lựa chọn hợp lý các hằng số và . Tuy nhiên do quá trình dao động bắt đầu với các tác động ngẫu nhiên của nhiệt độ, nhiễu và sự nạp của các tụ ký sinh [2], nên thời gian nửa bền cũng mang tính ngẫu nhiên cao. Bởi vậy không trích mẫu vào giai đoạn này, mà vào thời điểm khi mạch bắt đầu đi vào dao động. Lúc này, do tác động của nửa bền mà tần số và pha dao động cũng mang tính ngẫu nhiên ở các lần khởi động khác nhau. Dựa vào các phân tích trên, một nguồn nhiễu ngẫu nhiên được đề xuất thiết kế như Hình 2. Nguồn nhiễu gồm các bộ dao động vòng tự do RO, mỗi vòng gồm số lẻ các mạch đảo có điều khiển với đường hồi tiếp. Khi ctrl ở mức logic 0, các mạch đảo không làm việc, đầu ra của chúng ở trạng thái Z không xác định. Khởi đầu ctrl chuyển mức logic 1 cho phép các cổng ba trạng thái làm việc. Đầu vào mỗi cổng đảo nhận các tín hiệu không xác định từ cổng đảo trước, cộng thêm nhiễu nhiệt vốn có làm tăng entropy của mỗi cổng. Giá Nghiên cứu khoa học công nghệ Tạp chí Nghiên cứu KH&CN quân sự, Số 42, 04 - 2016 135 trị điện áp tức thời của cả vòng được định nghĩa bởi các giá trị bất định khác nhau và nhiễu. Tiếp theo mạch đi vào trạng thái nửa bền. Qua đường hồi tiếp, các giá trị ngẫu nhiên ban đầu được khuếch đại và bắt đầu tăng biên độ. Quá trình này rất ngắn, dưới 5 ns và biên độ chưa đủ lớn. Khi RO đi vào dao động, mỗi vòng có các giá trị khởi đầu khác nhau do các giá trị nửa bền khác nhau cả về biên độ lẫn thời gian, nên các pha dao động có giá trị khác nhau ngẫu nhiên. Hình 2. Nguồn nhiễu dựa trên nửa bền đề xuất. Để tăng thêm entropy nguồn nhiễu, chúng tôi thiết kế nhiều RO và cộng các kết quả ra nhờ cây XOR. Kết quả ra được trích mẫu nhờ D flip-flop và cân bằng độ lệch thống kê bằng T flip-flop. Thời điểm trích mẫu vào giữa xung ctrl. Sau mỗi bit ngẫu nhiên trích xuất, ctrl trở về logic 0, ngắt toàn bộ các mạch đảo, đưa về trạng thái Z sẵn sàng cho lần sinh bit ngẫu nhiên tiếp theo. Do mỗi lần reset, mỗi mạch đảo nằm ở một trạng thái độc lập khác nhau nên các bits sinh ra có độ tương quan rất thấp, chỉ chịu ảnh hưởng của vị trí bố trí linh kiện mà thôi. Hình 3 là giản đồ thời gian mô tả các giai đoạn của quá trình sinh bit ngẫu nhiên. Hình 3. Giản đồ các giai đoạn hoạt động của mạch điện. 2.3. Kết quả thực nghiệm Kết quả nghiên cứu được thực hiện với một nguồn entropy gồm ba mạch RO, mỗi mạch gồm ba, năm và bảy buffers đảo có điều khiển 74F540 của Phillips. Tần số của mỗi vòng dao động được tính theo = , trong đó N là số tầng, là trễ lan truyền của mỗi mạch đảo. Đối với 74F540, = 3.5 . Các ROs có tần số tương ứng là 47 MHz, 28 MHz và 20 MHz. Tín hiệu điều khiển ctrl = 1, 2 và 3 MHz. Các D flip-flop và bộ đếm modulo 2 T flip-flop được thiết kế thêm nhằm mục đích lấy dữ liệu ra phục vụ đánh giá. Mỗi lần lấy số liệu 1 Mbit và lấy 100 lần. 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à khoảng tin cậy 99%. Khoảng tin cậy thực tế CI được tính theo = ± 3 () , với = 1 − và m là số lượng chuỗi bit lấy ra, ta có trong dải từ 0.96 đến 1.02 nhưng tất nhiên cận trên không thể lớn hơn 1. P- value được dùng để đo mức độ ngẫu nhiên. Yêu cầu là ˗ ≥ thì số sinh ra được coi là ngẫu nhiên. Bảng dưới là kết quả đánh giá. Công nghệ thông tin & Khoa học máy tính Nguyễn Hồng Quang, “Nghiên cứu nguồn nhiễu có Entropy sinh số ngẫu nhiên thực.” 136 Tên phép test ctrl = 1 MHz ctrl = 2 MHz ctrl = 3 MHz K.quả Đ.giá K.quả Đ.giá K.quả Đ.giá Test tần suất (đơn bit) 0.739 P 0.401 P 0.848 P Test tần suất trong một khối bits 0.606 P 0.311 P 0.796 P Test các dãy bits 0.723 P 0.575 P 0.722 P Phép test dãy số 1 dài nhất trong một khối 0.834 P 0.366 P 0.746 P Test hạng ma trận nhị phân 0.312 P 0.499 P 0.310 P Test biến đổi Fourier rời rạc 0.602 P 0.201 P 0.421 P Test tìm các tổ hợp đã định, không chồng 0.655 P 0.825 P 0.345 P Test tìm các tổ hợp đã định, chồng nhau 0.463 P 0.364 P 0.439 P Test “Thống kê toàn bộ” 0.421 P 0.302 P 0.237 P Test độ phức tạp tuyến tính 0.647 P 0.630 P 0.699 P Test chuỗi m-bit 0.697 P 0.569 P 0.436 P Test entropy xấp xỉ 0.901 P 0.468 P 0.049 P Test tổng cộng dồn 0.624 P 0.052 P 0.964 P 3. KẾT LUẬN Nghiên cứu nửa bền trong mạch điện tử cho thấy có thể sử dụng nửa bền như một nguồn entropy chất lượng phục vụ sinh số ngẫu nhiên. Nguồn nhiễu dựa trên hiện tượng nửa bền của chúng tôi không chứa thành phần analog và có entropy cao. Kết quả thực nghiệm cho thấy nguồn nhiễu này đã vượt qua tất cả các phép thử thống kê của NIST mà không cần xử lý sau. Ưu điểm của nguồn nhiễu đề xuất này là số hóa hoàn toàn, cho phép dễ tích hợp với các thiết kế digital; entropy của nguồn nhiễu là tổng entropy từ các nguồn độc lập; sau mỗi bit ngẫu nhiên sinh ra nguồn nhiễu lại được khởi động lại đảm bảo giảm thiểu tương quan giữa các bit liền kề. Chất lượng nhiễu sinh ra đủ lớn để không cần xử lý sau và như vậy, không có thành phần tất định trong số ngẫu nhiên sinh ra. TÀI LIỆU THAM KHẢO [1]. H. Hata và S. Ichikawa, “FPGA Implementation of metasbility-based true random number generator”, IEICE TRANS. INF. & SYST., vol.E95-D, 2012. [2]. M. Varchola và M. Drutarovský, “New High Entropy Element for FPGA based TRNG”, CHES 2010. [3]. Milos Drutarovsky và Michal Varchola, “Analysis of Randomness Sources in Transition Effect Ring Oscillator based TRNG”, CryptArchi, 2010. [4]. Understanding Metastability in FPGAs, Altera, 2009. [5]. M. Varchola và M. Drutarovsky. “New FPGA based TRNG Principle Using Transition Effect with Built-In Malfunction Detection”, CryptArchi, 2009. [6]. B. Sunar, W. J. Martin và D. R. Stison, “Aprovably secure true random number generator with built-in tolerance to active attacks”, IEEE Transaction on Computers, 2007. [7]. J. Golic, “New methods for digital generation and postprocessing of random data”, IEEE Trans. Computers, 2006. [8]. H. Bock, M. Bucci và R. Luzzi, “Offset-compensated oscillator-based random bit source for security applications”, CHES 2004, Springer, 2004. [9]. M. Epstein và cộng sự, “Design and implementation of a true random number generator based on digital circuits artifacts”. CHES 2003, Springer, 2003. Nghiên cứu khoa học công nghệ Tạp chí Nghiên cứu KH&CN quân sự, Số 42, 04 - 2016 137 [10]. V. Fischer, M. Duratovsky, “True random number generator embedded in reconfigurable hardware”, CHES 2002, Springer, 2002. [11]. V. Fischer, M. Drutarovsky, “True Random Number Generator Embedded in Reconfigurable Hardware”, CHES 2002, Springer, 2002. [12]. J. Horstmann, H. Eichel, R. Coates, “Metastability behavior of CMOS ASIC flip-flops in theory and test”, IEEE J. Solid-State Circuits, 1989. [13]. R. Fairfeld và cộng sự, “An LSI random number generator”, CRYPTO, Springer, 1985. ABSTRACT A TRUE RANDOM GENERATOR WITH LOW STATISTICAL BIAS AND CORRELATION True random numbers are important and crucial for security of contemporary cryptography. It is complicated and difficult to design and integrating an analog random source into digital circuits. Plus, they are usually designed with a post process but this method puts some determination into output bit stream. The paper introduces a reseach of metasbility in electronic circuit based full digital random source with high entropy, low correlation and without the post processing. The proposed noise source has estimated by NIST statistic tests and overcomes them. Keywords: True random number, Metastability, Correlation, TRNG, Cryptography, Statistical test. Nhận bài ngày 10 tháng 3 năm 2016. Hoàn thiện ngày 15 tháng 4 năm 2016. Chấp nhận đăng ngày 20 tháng 4 năm 2016. Địa chỉ: Học viện Kỹ thuật Mật mã - Ban Cơ yếu Chính phủ. *Email: quang27269@gmail.com