Ao基于振蕩采樣的真隨機數發生器設計與實現

王曉燕 ,楊先文

（1.河南中醫學院,河南鄭州,450008;2.信息工程大學,河南鄭州,450000）

0 引言

在信息系統中，密碼技術是保護信息安全的核心。密鑰管理、密碼協議、數字簽名、身份認證等對隨機序列的應用也越來越廣泛。同時隨著芯片設計SoC時代的到來，FPGA憑借成本低、設計周期短等優點倍受青睞，基于FPGA實現密碼算法已越來越普及，密碼SoC具備隨機數產生功能是系統安全性的根本要求。因此，如何設計噪聲隨機可靠，可完全FPGA實現，且資源消耗少的真隨機數發生器（true random number generator, TRNG）是重要研究內容之一。本文在對噪聲源模型分析的基礎上，設計了數字噪聲源模塊。基于此，在并行輸出及控制、在線隨機測試等方面進一步探討，設計并實現了一款TRNG。其噪聲源理論可靠，具有速度快、性能好、成本低的應用價值。

1 真隨機數發生器結構

為滿足應用系統的實際需求，隨機數發生器不僅要保證足夠高的輸出速率，而且要確保產生序列具有良好的隨機性。本文提出的適合FPGA實現的TRNG結構如圖1所示，主要由鎖相環（PLL）模塊、數字噪聲源模塊、偏置后處理模塊、在線隨機測試模塊、輸出控制模塊和并行輸出模塊組成。

圖1 基于振蕩采樣的真隨機數發生器結構

PLLs模塊由三個獨立PLL組成，用于產生TRNG所需的三個時鐘信號clj、clk和cll；數字噪聲源模塊產生隨機驅動信號drv_signal，經后處理模塊糾偏后產生隨機比特rb，依次進入并行輸出模塊后等待輸出。

由于芯片在啟動前可能遭受硬件篡改攻擊，從而影響隨機數發生器自身性能，為確保隨機數的質量，保證密碼系統的應用安全，在系統上電時對TRNG的啟動狀態進行自檢。在本文設計中，每次上電自檢產生20,000比特傳送給在線隨機測試模塊，并將測試結果傳送給輸出控制模塊。若測試未通過，則輸出控制模塊置控制使能enable為0、報警信號alarm為1，即禁止并行輸出模塊向外輸出產生序列，同時向外部應用環境發送報警信號；否則表示TRNG未遭受硬件篡改。

2 具體模塊設計

2.1 數字噪聲源模塊設計

基于FPGA的噪聲源有兩種參考設計：1) 環形振蕩器或鎖相環的抖動；2) 邏輯單元的亞穩態性。本文基于時鐘振蕩采樣原理，利用FPGA內置PLL的抖動行為設計隨機噪聲源，如圖2所示。

圖2 基于PLL的噪聲源模型

噪聲源模型由兩個PLL、一個D觸發器和一個異或鏈電路組成。其中，PLLs模塊輸出兩個時鐘信號clk和clj，且它們之間滿足

其中，Tclk和Tclj分別是clk和clj的周期，fclk和fclj分別是clk和clj的頻率，CM和CD分別是clk和clj的系數因子，且為了使得采樣點有最大的循環周期，有GCD(CM，CD)=1成立。當采樣個數達到CD時，異或鏈電路進行工作，將CD比特異或后輸出1比特隨機數。

異或鏈電路由CD個D觸發器構成，采樣得到的隨機比特經過 個觸發器存儲移位后相異或最終輸出1比特，即其統計特性由定理保證（定理證明省略）。

綜上，在CD個采樣點中，只要有一個采樣為1的概率為1 2，則Bias(bout) = 0，即異或鏈電路輸出比特為1的概率為1 2。即使不存在i∈ {0，1，...，CD-1}，使得P(xi= 1 )=1 2，但隨著CD的增大，Bias(bout)也將趨向于0。

2.2 并行輸出及控制模塊設計

并行輸出模塊將32級T觸發器構成的翻轉采樣模塊輸出的r1,r2,…,r32進行異或輸出，然后輸入至32位移位寄存器中并輸出所需要的隨機數。端口連接是將32位移位寄存器的時鐘端連接至時鐘clk，輸入使能信號置1，輸出使能信號連接至輸出控制模塊的enable，數據輸入端口din連接經翻轉采樣模塊各輸出端口相異或的結果rb。當檢測到clk上升沿時將隨機比特rb存入寄存器，存滿32位時檢測enable是否有效。若enable有效，則將隨機序列從端口dout并行輸出，同時將狀態信號state設置有效，用以標識當前32位隨機數產生完畢；否則停止輸出隨機序列，并保持state無效。

圖3 輸出控制模塊

輸出控制模塊由2個與門和1個選擇器組成，如圖3所示。當test_state為0時，表示上電自檢未完成，則選擇器選通端口A，輸出信號0，此時enable和alarm均無效；當test_state由0跳變為1時，表示在線隨機測試結束，選擇器選通端口B，若所有測試項目均通過測試，則與門輸出為1，此時enable有效，alarm無效；若其中一項或多項測試未通過，則與門輸出為0，此時enable無效，alarm有效，輸出控制模塊通過enable控制并行輸出模塊停止向外輸出序列，同時向外輸出報警信號。

2.3 在線隨機測試模塊設計

以FIPS 140-2為依據，設計了在線隨機性測試模塊，包括4個測試單元，如圖4所示。

圖4 在線隨機測試模塊

1）控制單元

控制單元主要有兩個功能：1) 計數輸入隨機序列的比特數，當計數輸入序列達到20,000比特時，向各測試單元傳送bit_finish，各模塊接收后結束測試，將各統計值與標準值進行比較判定，得出相應的測試結果，并向控制單元返回完成信號X_test_finish；2) 當各測試單元的X_test_finish均有效后，置test_state為1，隨機性測試結束，輸出控制模塊接收測試結果。

2）頻數測試單元

頻數測試的硬件實現較容易，僅需要1個寄存器用來計數輸入序列中1的個數，當檢測到輸入比特為1時，寄存器中的內容加1。當bit_finish有效時，將寄存器中的值與參考值進行比較，若在參考范圍內則表示通過該項測試，否則表示不通過。

3）撲克測試單元

撲克測試是將20,000比特隨機序列分割成5,000個連續的4比特數據塊，數據塊取值范圍為0～15，統計5,000個數據塊16種取值出現的次數，記為ni(i=0，1，...，15)。計算統計值S，

若2.16 ≤S≤46.17，則表示通過測試；否則表示不通過測試。進一步，因為式(1)很難硬件實現，所以可將其轉換為先計算，再將結果與新的取值范圍[Smin ，Smax ]作比較。其中，

為了減少硬件資源消耗，可計算通過測試時計數器ni中最大值的上限，從而確定計數器所需要的位數。記ni中最大值為ni0，通過上述數據求解得到ni0≈429（求解過程省略）。因此，撲克測試單元的實現需要16個9位計數寄存器、16個9位乘法器、15個21位加位器和部分比較邏輯。

4）游程和長游程測試單元

3 實現性能及測試

采用Verilog描述語言作為TRNG模型的原型設計工具，選擇Altera公司Cyclone III系列EP3C80F780C6型號FPGA芯片作為TRNG實現的原型器件，并使用QuartusII 9.0軟件對實現進行了編譯綜合。TRNG綜合后共占用1,535個邏輯單元和3,160比特存儲器，系統工作時鐘頻率（即fclk）最高為33.5MHz，隨機數生成速率的最大值為33.5Mb/s。同時通過采用16種隨機性測試方法對產生序列進行的測試發現，各項測試統計值p-value均大于顯著性水平0.01，即表示產生序列通過了所有的隨機性測試，表明本文提出的TRNG模型能夠產生隨機性良好的隨機序列。

圖5 游程和長游程測試狀態機

游程和長游程測試實質上可歸并為同一類測試，它們由一個狀態機控制完成，狀態跳轉如圖5所示，包括空閑狀態（idle），比較狀態（compare），游程狀態zi和 ，其中i=1，...，6，26，表示相應狀態下0游程或1游程的長度。當reset有效時，狀態機進入空閑等待狀態。之后，隨機比特將依次進入狀態機，當輸入的第1比特為0，則狀態機由空閑狀態轉向狀態z1，如果第2比特同樣為0，則狀態機轉向z2，繼續接收下一比特；反之，如果第2比特為1，則狀態機轉向o1，此時表示1個游程結束，狀態z1相對應的計數寄存器值加1，即長度為1的0游程個數加1。同樣，當狀態機從o1開始后，若下一輸入比特為1，則轉向o2；否則轉向z1，相應的計數寄存器值加1。特別地，當狀態機進入到狀態z6或o6后，輸入比特仍為0或1，則狀態機仍保持原狀態，直至輸入的0或1的個數超過25時轉向z26或o26。當bit_finish有效時，狀態機轉向比較狀態，如果各寄存器值處于相應的閾值范圍內，則表示通過測試；否則表示不通過測試。

4 結束語

鑒于隨機數在密碼技術中大量使用，文章給出了一種基于振蕩采樣的真隨機數發生器，分別設計了數字噪聲源模塊、并行輸出及控制模塊、在線隨機測試模塊。原型實現結果表明其序列產生速度為33.5Mb/s，且產生序列的隨機性通過了NIST SP800-22標準。下一步工作，將研究其與密碼SoC的集成應用。

[1]韓越,黑勇,喬樹山.一種資源優化的祖沖之算法的硬件實現方法[J].科學技術與工程,2013,13(5)∶1330-1334.

[2]王晨光,喬樹山,黑勇.低復雜度SM4加密算法IP核設計[J].科學技術與工程,2013,13(2)∶ 347-350, 378.

[3]李崢,楊先文,王安.利用競爭冒險的真隨機數發生器設計[J].信息安全與通信保密,2011,(1)∶72-74, 80.