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

DOI：10.19339/j.issn.1674-2583.2020.04.006

一種基于隨機儲存元胞自動機真隨機發生器［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.

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

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

1 真隨機整體設計

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2 實驗驗證

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

為測試結果，數據完全通過試。

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

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

3 結語

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