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