設計一種超高速全數(shù)字真隨機數(shù)發(fā)生器，使用嵌入亞穩(wěn)態(tài)環(huán)節(jié)的環(huán)路振蕩器作為隨機源。對元胞自動機電路進行改良，向其中添加隨機存儲的特性，并將其作為后處理電路的一部分，提高了數(shù)據(jù)的熵值和偽隨機性。后級電路采用異或鏈電路和 DES 加密算法，提高隨機序列的每比特熵值，改善輸出的統(tǒng)計特性。該方案具有良好的可移植性，極高的生成速率，偏低的資源使用和自定義擴展功能。通過 FPGA 版級驗證，真隨機數(shù)生成速率可達 1 Gb/s，具有一定的應用價值。

DOI：10.19339/j.issn.1674-2583.2020.04.006

一種基于隨機儲存元胞自動機真隨機發(fā)生器［J］。集成電路應用， 2020， 37（04）： 18-21.

True Random Generator Based on Random Storage Cell Automaton

JI Lei， PAN Weiqing， ZHI Yanan

Abstract — In this paper， a ultra-high-speed all-digital true random number generator is designed.The designer uses ring oscillators embedded in a metastable state as a random source. The cellular automaton circuit is improved， and the random storage feature is added to it as a part of the post-processing circuit， which improves the entropy value and pseudo-randomness of the data. The post-stage circuit uses XOR circuit and DES encryption algorithm to increase the entropy value of each bit of the random sequence and improve the statistical characteristics of the output. This solution has good portability， extremely high generation rate， low resource usage， and custom extension functions. Through FPGA-level verification， the true random number generation rate can reach 1 Gb/s， which has certain application value.

Index Terms — TRNG， ring oscillator， metastable state， cellular automata， DES， FPGA.

隨機數(shù)在密碼學中占有重要的地位，幾乎所有的密碼算法都要用到一些對攻擊者來說必須是秘密的數(shù)據(jù)，而其中密鑰必須是隨機數(shù)。隨著加解密技術的快速發(fā)展，基于軟件實現(xiàn)的偽隨機數(shù)發(fā)生器可能無法滿足安全性的要求，雖然基于物理隨機源的 TRNG 能保證安全性， 但其產(chǎn)生的真隨機數(shù)的質(zhì)量不高，生成速率偏慢?？紤]到 5G 時代的到來，基于區(qū)塊鏈、物聯(lián)網(wǎng)、車聯(lián)網(wǎng)、智慧城市技術的快速發(fā)展，海量的數(shù)據(jù)需要在信息交互節(jié)點進行加密傳輸，這對真隨機數(shù)生成的速率有了更高的要求。

本文設計了一種超高速真隨機數(shù)發(fā)生器，其具有可移植性好，生成速率高，實現(xiàn)成本低廉的特點并具有自我擴展特性。實際測試中，真隨機數(shù)生成速率高達 1 Gb/s，吞吐量/資源高于 1 Mb/LUT，遠遠高于常規(guī)真隨機數(shù)發(fā)生器吞吐量百兆級別，0.3 Mb/LUT 左右的性能。

1 真隨機整體設計

本文整體架構如 所示，框架包括 5 部分：基于亞穩(wěn)態(tài)的環(huán)振器真隨機源，基于隨機儲存的元胞自動機電路，異或鏈電路，DES 電路和千兆光口輸出單元。

J.D. Golic 最早提出 Fibonacci 和 Galois 環(huán)形振蕩器電路，但隨機數(shù)生成速率偏低。2008 年，I.Vasyltsov 等人在 Fibonacci 和 Galois 環(huán)形振蕩器的基礎上引入了亞穩(wěn)態(tài)結構，減少所需熵的積累時間。文獻中，朱亮亮等人向其中引入控制環(huán)節(jié)，降低發(fā)生器功耗。本文隨機熵源采用方案。

控制信號為低電平時，大環(huán)路斷開，各反相器自成環(huán)路，受到半導體噪聲的影響，他們的輸出會在亞穩(wěn)態(tài)區(qū)域波動。當控制信號為高電平的時候，各反相器接入大環(huán)路，迅速離開亞穩(wěn)態(tài)區(qū)域，并進入穩(wěn)態(tài)區(qū)域，此時其輸出具有隨機性。

二進制系數(shù) fi 決定環(huán)振器的反饋連接。當 fi＝1 時，反饋連接；當 fi＝0 時，反饋斷開；反饋多項式可以表示為式。

（1）式中，n 為反相器個數(shù)。為了確保輸出不會恒定不變，多項式須滿足式。

必須保證 n 為奇數(shù)，h（x） 不能被 1+x 整除，且 f（x） 可以被 1+x 整除。如果反饋多項式為本原多項式則以上都可以滿足。

本文采用 36 個 7 階 Fibonacci 震蕩環(huán)，28 個 7 階 Galois 震蕩環(huán)作為真隨機源。7 階本原多項式共 18 個，重復 3.5 次使用，其輸出作為隨機儲存元胞自動機電路的選擇輸入端。7 階本原多項式如 所示。

以上輸出的序列具有真隨機和偽隨機性，但數(shù)字熵源的統(tǒng)計特性往往不夠理想，在物理隨機過程采樣中，會引入偏差和相關性，所以需要添加后處理電路提減小偏差和相關性。

元胞自動機的概念最初被 John von Neumann 和 Ulam 提出，并常用于物理、生物和化學的建模，也用于生成偽隨機序列，是常用的后處理算法之一。元胞自動機是元胞的有限陣列，由相同的元胞組成，根據(jù)局部過度功能同步并行發(fā)展，且只能與他們最近的鄰居通信。其可以由四元組（Z，Q，V，f）所定義，其中 Z 代表 d 維的細胞空間，Q 代表可能元胞可能狀態(tài)組成的集合，V 表示局部規(guī)則使用的鄰域，f 代表本地規(guī)則。初始時，每個元胞都有一個初始狀態(tài)，根據(jù)本地規(guī)則和鄰域聯(lián)系，細胞狀態(tài)發(fā)生變化。

初級元胞自動機是一個基本元胞自動機，一維細胞空間 Z，元胞狀態(tài) Q＝{0，1}，鄰域 V＝（-1，0，1），本地規(guī)則 f：Q3→Q，Wolfram 在數(shù)學上證明了它作為高性能隨機數(shù)發(fā)生器的適用性，可以并行的有效實現(xiàn)，如式。

最上方三個方塊表示所有當前時刻 n 可能的鄰域狀態(tài)，下一單元格代表下一時刻元胞輸出的狀態(tài)。本地規(guī)則被下一時刻序列的二進制值所命名。

2014 年，一種基于儲存的元胞自動機被提出，其中 x，y，z 為包括 0 的正整數(shù)［9］。元胞的下一狀態(tài)的輸出與相鄰元胞和本身的過去狀態(tài)有關，如式。

最近，一種基于隨機儲存的元胞自動機被提出，Q＝{0，1}，鄰域 V＝（-1，0，1）。其中，τi是隨機值，其小于等于元胞儲存的狀態(tài)數(shù) M，元胞的下一狀態(tài)可以隨機地由當前狀態(tài)，以及過去狀態(tài)確定，如式。

本文設計一個基于隨機儲存的元胞自動機，其元胞儲存狀態(tài)數(shù) M 為 1，本地規(guī)則為 R150，其τi的值由上級的亞穩(wěn)態(tài)震蕩環(huán)的輸出決定。0 代表τi＝0，輸出當前狀態(tài)；1 代表τi＝1，輸出上一狀態(tài)。其元胞單元電路如圖 5 所示。bit_out 為該元胞自動隨機數(shù)的輸出端，連接到異或鏈電路。bit_i_m 為隨機儲存輸出端，連接與其相鄰的左右兩個元胞單元。

隨機儲存的元胞自動機包含 64 個元胞環(huán)形連接，其相互連接圖如圖 6 所示，其中只有一個 bit_i_m 初始值為 1。系統(tǒng)開始工作后，每個時鐘周期生成 64 個 bit_out，每相鄰 8 位進行異或壓縮操作，送入下級異或鏈電路中。

為了減小偏差，使得“0，1”分布均勻，采用異或鏈進行處理，對數(shù)據(jù)進行校正，結構如圖 7 所示。本文采用 8 路異或鏈電路，每路由 8 個觸發(fā)器進行異或鏈糾偏，每個時鐘周期輸出 8 bit 數(shù)據(jù)，輸出偏執(zhí)非常小。

1940 年代末，香農(nóng)提出了設計密碼系統(tǒng)的兩個基本方法-混淆和擴散。擴散和混淆可以極大改善輸出序列的統(tǒng)計特性，提高熵值，彌補統(tǒng)計缺陷。

設計中最后采用 DES 加密算法對數(shù)據(jù)進一步后處理，為 DES 加密算法處理過程。首先對上級輸入的 8 bit 序列進行數(shù)據(jù)重排，擴展到 128 bit，高 64 bit 和低 64 bit 分別作為明文和密鑰輸入，進行 IP 初始置換，然后 16 輪迭代變換，最后左右交換后進行逆初始置換（IP-1）得到 64 bit密文，作為真隨機數(shù)輸出序列，16 輪迭代采用 Feistel 密碼結構對明文和密鑰進行混淆和擴散。其中置換移位操作可獲得擴散，非線性函數(shù) f 操作可獲得混淆。

2 實驗驗證

本文設計真隨機發(fā)生器在 FPGA 上進行實驗實現(xiàn)，型號為 xc7z035ffg676-2。外接輸入時鐘為 100 MHz，經(jīng)過 PLL 倍頻到 500 MHz 后，最后輸出真隨機輸出速率高達 1 Gb/s。實現(xiàn)過程中沒有使用任何布局布線約束，完全由設計軟件自動處理。PC 端通過光口接受 126 組數(shù)據(jù)，每組 1 Mbit，使用NIST SP-800-22 隨機數(shù)測試套件進行隨機性評估測試。測試規(guī)定當測試通過率都大于 96 %時，則認為通過該項測試；如果數(shù)據(jù)通過全部 15 項測試，則認為序列是真隨機的。

為測試結果，數(shù)據(jù)完全通過試。

為體現(xiàn)本文所設計的真隨機數(shù)發(fā)生器的性能，本設計與國內(nèi)外已經(jīng)公開發(fā)表的真隨機數(shù)發(fā)生器進行比較，其中單個 LUT 資源相當于一個 LE 資源；可移植性的判斷是基于實現(xiàn)時是否使用特殊器件或手動布局布線，如使用則移植性較差，對比結果如表 3 所示。在吞吐量方面，本文設計的真隨機數(shù)發(fā)生器遠超常規(guī)數(shù)字發(fā)生器的百兆級別。吞吐量/邏輯資源比為 1.107 Mb/LUT，遠大于常規(guī) 0.3 Mb/LUT，更加節(jié)省資源。移植性方面由于沒有使用特殊器件和物理約束實現(xiàn)，因此可以快速集成到芯片或 FPGA 當中。

由于元胞自動機結構簡單，易擴展的特性，本文對該設計的自我擴展性能進行了實驗驗證，本文將 64 個元胞自動機裁剪為 32 個、16 個，減少硬件資源分別為 143LUT、200LUT，并依次重新實現(xiàn)設計，生成速率分別為 500 Mb/s、250 Mb/s，結果均能通過 NIST SP800-22 測試。實驗表明該隨機數(shù)發(fā)生器具有擴展性能，使用者可以根據(jù)自己實際需求自我進行裁剪或擴展。

3 結語

本文介紹了一種新的數(shù)字真隨機數(shù)發(fā)生器，解決現(xiàn)有真隨機數(shù)發(fā)生器生成速率，資源消耗，可移植性和擴展性無法全面的兼顧的問題。實際測試真隨機數(shù)生成速率可達 1 Gb/s，吞吐量/資源比為 1.1 Mb/LUT，遠遠高于常規(guī)真隨機發(fā)生器吞吐量的百兆級別和 0.3 Mb/LUT 的吞吐量/資源比。該方案純具有資源消耗低，吞吐量極高，可移植性好和可擴展的特點。便于集成到芯片和 FPGA 中，縮短開發(fā)周期，具有很好的實際應用價值，可滿足了未來區(qū)塊鏈、物聯(lián)網(wǎng)、車輛網(wǎng)、智慧城市中需要大量真隨機數(shù)進行信息加密的場合。
責任編輯:pj