王曉燕 ,楊先文

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

0 引言

在信息系統(tǒng)中，密碼技術是保護信息安全的核心。密鑰管理、密碼協(xié)議、數(shù)字簽名、身份認證等對隨機序列的應用也越來越廣泛。同時隨著芯片設計SoC時代的到來，F(xiàn)PGA憑借成本低、設計周期短等優(yōu)點倍受青睞，基于FPGA實現(xiàn)密碼算法已越來越普及，密碼SoC具備隨機數(shù)產(chǎn)生功能是系統(tǒng)安全性的根本要求。因此，如何設計噪聲隨機可靠，可完全FPGA實現(xiàn)，且資源消耗少的真隨機數(shù)發(fā)生器（true random number generator, TRNG）是重要研究內(nèi)容之一。本文在對噪聲源模型分析的基礎上，設計了數(shù)字噪聲源模塊?；诖耍诓⑿休敵黾翱刂?、在線隨機測試等方面進一步探討，設計并實現(xiàn)了一款TRNG。其噪聲源理論可靠，具有速度快、性能好、成本低的應用價值。

1 真隨機數(shù)發(fā)生器結構

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

圖1 基于振蕩采樣的真隨機數(shù)發(fā)生器結構

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

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

2 具體模塊設計

2.1 數(shù)字噪聲源模塊設計

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

圖2 基于PLL的噪聲源模型

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

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

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

綜上，在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觸發(fā)器構成的翻轉(zhuǎn)采樣模塊輸出的r1,r2,…,r32進行異或輸出，然后輸入至32位移位寄存器中并輸出所需要的隨機數(shù)。端口連接是將32位移位寄存器的時鐘端連接至時鐘clk，輸入使能信號置1，輸出使能信號連接至輸出控制模塊的enable，數(shù)據(jù)輸入端口din連接經(jīng)翻轉(zhuǎn)采樣模塊各輸出端口相異或的結果rb。當檢測到clk上升沿時將隨機比特rb存入寄存器，存滿32位時檢測enable是否有效。若enable有效，則將隨機序列從端口dout并行輸出，同時將狀態(tài)信號state設置有效，用以標識當前32位隨機數(shù)產(chǎn)生完畢；否則停止輸出隨機序列，并保持state無效。

圖3 輸出控制模塊

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

2.3 在線隨機測試模塊設計

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

圖4 在線隨機測試模塊

1）控制單元

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

2）頻數(shù)測試單元

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

3）撲克測試單元

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

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

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

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

3 實現(xiàn)性能及測試

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

圖5 游程和長游程測試狀態(tài)機

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

4 結束語

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

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

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

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