基于數?；旌系恼骐S機數發生器

葉少康，李 崢

（解放軍信息工程大學 電子技術學院，河南 鄭州450004）

0 引 言

隨機數發生器 （RNG）在許多方面有著廣泛的應用，如模擬與仿真系統、神經網絡的計算、數字系統的內建自檢測、分布與統計程序、游戲及密碼系統等等［1－3］。隨機數發生器 （RNG）可分為偽隨機數發生器 （PRNG）和真隨機數發生器 （TRNG）兩種［4－6］，偽隨機數發生器又稱確定性隨機數發生器，它由一個確定的初始向量開始，通過一個確定的算法來產生隨機數；真隨機數發生器依托于自然界中物理現象的隨機特性，如放射性衰變、電子電路的熱噪聲、散粒噪聲等［7］。

真隨機數因其具有隨機性強、無周期和不可預測性，在密碼系統和非密碼系統中都有著廣泛的應用，如彩票抽獎、模擬仿真、密鑰生成和安全協議等。為此，設計基于硬件實現的真隨機數發生器具有廣闊的應用前景。本文利用RC電路充放電的低穩定度設計了一款真隨機數發生器。

1 真隨機數發生器的總體結構

為了提高隨機序列的生成速率，本文采用8個噪聲源模塊 （N1－N8）并行工作，其總體結構如圖1所示。

整個隨機數發生器由8個噪聲源模塊、后處理模塊、在線隨機性檢測模塊、串行輸出單元和并行輸出單元組成。在隨機數生成系統工作過程中，首先由8個噪聲源模塊連續不斷地輸出16位隨機比特；然后通過后處理電路，經相應的后處理后，生成分布均勻、相對獨立的隨機序列；最后在線隨機性檢測模塊對經后處理的隨機序列進行實時檢測，并根據檢測結果進行報警和控制信號的輸出。

圖1 TRNG結構框架

2 噪聲源模塊的設計

2.1 基本原理

在RC充放電電路中，由于受到環境溫度、電壓、電流、電阻熱噪聲等因素的影響，其充放電時間極不穩定。利用RC充放電的低穩定度特性作為真隨機數發生源，收集數據，通過時鐘周期量化器計數RC電路的充放電時間，獲得不確定的2位二進制數據，其原理如圖2所示。

圖2 噪聲源實現原理

2.2 實現方法

2.2.1RC電路充放電過程

RC電路充放電策略是：vol作為RC電路電壓配置端口，ref作為電容電壓檢測端口。當時鐘周期量化器置vol為1時，該端口輸出為高，輸出電流通過電阻對電容進行充電；當時鐘周期量化器置vol為0時，該端口輸出為低，電容通過電阻進行放電。充放電過程如圖3所示。

圖3 RC電路充放電過程

2.2.2 時鐘周期量化器

時鐘周期量化器是一個數字電路模塊，主要由一個充電計數器、一個放電計數器和一個控制狀態機組成。充電計數器和放電計數器分別量化RC電路充電和放電所耗的時鐘周期，控制狀態機控制整個充放電過程，其工作流程如圖4所示。

圖4 時鐘周期量化流程

當enb信號有效且經rst復位后，設置ready為0，并置vol為1開始對RC電路充電，當充電計數器檢測到vol從0跳變為1時則開始計數并檢測ref，當檢測到ref為1時，表明充電結束；保存充電計數結果后復位充電計數器，設置vol為0，RC電路開始放電，當放電計數器檢測到vol從1跳變為0則開始計數并檢測ref，當檢測到ref為0時，表明放電結束；保存放電計數器結果后復位放電計數器，置ready為1并輸出充放電隨機比特crand（charge random bit） 和drand（discharge random bit），其 中，crand和drand分別為充電計數器和放電計數器的最低比特位；直到檢測到enb無效時則停止產生隨機數，否則進行下一次充放電過程。

2.3 采樣電路的設計

為從上述噪聲源模塊中采樣得到隨機的01序列，使得序列中0和1出現的概率盡可能地接近，本文基于非線性布爾函數，提出了一種有效的采樣方法。

首先給出非線性函數的一個性質［8］：

定理1 設f是一個→F2的非線性函數，ε為f函數的輸入向量中0和1的概率偏差，Δ（ε）為f函數的輸出比特中0和1的概率偏差，則有

式中：w（x）——x的漢明重量。

所以

根據上述非線性布爾函數的性質，本文選擇了一個易于硬件實現的二次非線性布爾函數，其表達式如下：f（x）＝f（x1，x2，x3）＝x2＋x3＋x1x2＋x2x3mod2，其真值表如表1所示。

表1 二次布爾函數的真值表

根據定理1可得

則有

圖5給出了二次布爾函數的采樣電路圖，該電路結構簡單，僅使用了3個D觸發器、4個與門和1個異或門電路。在時鐘clk的作用下，當ready信號為1時，使得EN有效，此時電路動作一次，完成一次采樣，分別獲得隨機比特c和d。

3 后處理模塊的設計

3.1 后處理算法

圖5 基于布爾函數的采樣電路

目前，常見的后處理算法有馮·諾依曼校正法［9］、級聯的異或鏈法［10］、彈性函數［11－12］及哈希函數［13］等。前3種方法電路設計簡單，易于實現；基于哈希函數的電路設計復雜，硬件實現代價相對較高。根據上述分析，本文基于模加、移位、異或、反饋等運算設計了一種新的后處理算法以生成等概、獨立的隨機序列。模加是一個有記憶變換模型，它可以將前幾個時刻的計算結果存儲下來，參與當前時刻的隨機數生成，這使得當前時刻的隨機數不僅與當前時刻輸入的原始隨機數有關，還與前幾個時刻的計算結果有關。移位是算法中常用的運算，其電路通常以移位寄存器為基礎設計的，主要包含邏輯移位和循環移位。異或有效地將兩路不相干的輸出序列進行了綜合。反饋是指反饋移位寄存器的狀態值不僅參與移位運算，其輸出值還要反饋到輸入端，參與其它函數運算。經過算法處理后，數字序列的均勻性、獨立性及游程特性均得到改善，算法結構如圖6所示。

圖6 后處理算法結構

圖6 給出了后處理算法的結構，其具體描述如下：

（1）符號定義

ci：8位采樣編碼，其為從8個噪聲源采樣得到的8比特c，其二元表示為

整個實踐活動包括四個階段，分別是：M+C(強調創意的構思)階段、M+D(強調創新的設計)階段、M+I(強調創造的實施)階段、M+O(強調分享的運行)階段，各個階段的活動內容見表1。整個過程體現了體驗教育、快樂教育、基于項目的教育和創造中學等教育理念。

di：8位采樣編碼，其為從8個噪聲源采樣得到的8比特d，其二元表示為

ri：8位移位編碼，其二元表示為

si：8位移位編碼，其二元表示為

ti：8位異或編碼，其二元表示為

xi：8位加法編碼，其二元表示為

yi：8位加法編碼，其二元表示為

zi：8位加法編碼，其二元表示為

k3～k0：4個8位并行移位寄存器，組成1組32位隨機序列b31－0。

（2）運算符號描述

田：加法運算，表示兩個8比特數據進行模256加；

⊕：異或運算，表示兩個8比特數據進行逐位異或；

＜＜＜：循環左移運算，表示8比特數據循環左移1位；

＞＞＞：循環右移運算，表示8比特數據循環右移1位。

（3）算法流程

初始化：i＝0，s0＝r0＝0，kj＝0 （j＝0，1，2，3）；

1）i＝i＋1，采樣得到ci，di；

重復1）～5），即可源源不斷地產生隨機數序列，其中連續采集4個ci和di后，生成一組32比特的隨機序列b31～b0。

3.2 后處理電路

根據后處理算法的結構，結合后處理模塊整體電路結構，采用數字電路設計技術，設計如圖7所示的后處理單元電路。

從圖7中可以看出，該電路主要由3個模加模塊、兩個循環移位模塊、1個異或模塊、兩個8位D寄存器模塊和8位寬的4級邏輯移位模塊組成。它在采樣時鐘sclk的控制下完成相應的后處理操作。

圖7 后處理單元電路

4 串并行輸出單元的設計［14］

4.1 串行輸出單元

在密碼系統中，串行輸出應用較少，但某些特殊的場合要求后處理單元輸出的隨機數序列是串行的，為此，在輸出單元模塊中設計了串行端口。其串行輸出單元電路如圖8所示。整個電路主要由1個5位二進制計數器和1個32位移位寄存器組成。在時鐘clk的作用下，5位二進制計數器模塊每32個時鐘產生一個進位CO，當CO有效時，32位移位寄存器模塊將輸入數據逐位串行輸出。

圖8 串行輸出單元電路結構

4.2 并行輸出單元

目前，大多數密碼系統要求真隨機數發生器模塊輸出的隨機數序列是并行的，這樣方便其它模塊對隨機數的并行讀取，本文設計了如圖9所示的并行輸出單元電路。

從圖9可以看出，并行輸出電路主要由八分頻模塊、2位二進制計數器模塊、32位寄存器組成。首先，將時鐘clk通過八分頻模塊得到采樣時鐘sclk；然后，在采樣時鐘sclk的控制下，2位二進制計數器模塊每4個時鐘產生一個有效的進位信號CO1，將32位隨機數據輸入到并行端口；最后，當讀信號ren有效時，經與門輸出后使得EN2有效，這時將32位數據并行輸出；否則，并行輸出控制使能信號EN2無效。

圖9 并行輸出單元電路結構

5 仿真與測試

根據整個真隨機數發生器的結構框架，用Spectre模擬器對電路進行數模混合仿真，這里取量化時鐘頻率nclk＝100MHz，R＝1.69kΩ，C＝1.2nF，clk＝3.2MHz，sclk＝0.4MHz。通過實驗采集20 000比特用于隨機性檢測，隨機性檢測遵循FIPS140－2標準［15］，進行頻數檢測、撲克檢測、游程檢測和長游程檢測，檢測結果如表2所示。

表2 FIPS140－2測試結果

測試結果表明，采用本文所提供方案產生的隨機序列能夠通過FIPS140－2的統計測試，具有良好的隨機特性。

6 結束語

本文提出了一種數?；旌系恼骐S機數發生器，并完成了各個模塊的設計與整個隨機數發生器的仿真與測試。結果表明，隨機數的生成速率為3.2MHz，且能夠通過FIPS140－2的統計測試。該隨機數發生器使用元件少，功耗低，穩定性高，在一些對隨機數生成速率要求不高的場合有較大的應用意義。為滿足信息安全系統對隨機數高質量、高速率的要求，下一步的主要工作是設計高速、穩定、可靠的噪聲源。

［1］GONG Hong.Design of true random number generator［D］.Guiyang：Guizhou University，2007 （in Chinese）.［龔紅.真隨機數發生器設計 ［D］.貴陽：貴州大學，2007.］

［2］Killmann，Schindler.A design for a physical RNG with robust entropy estimators［G］.LNCS 5154：Proceedings 10th International Workshop，2008：146－163.

［3］Dichtl M，Golic Dj.High speed true random number generation with logic gates only［G］.LNCS 4727：Proceedings of the 9th International Workshop on Cryptographic Hardware and Embedded Systems，2007：45－62.

［4］Werner Schindler.Random number generators for cryptographic applications［M］.Cryptographic Engineering，Springer，2009：5－23.

［5］Tsoi K H，Leung Ka Ho，Philip H W Leong.A high performance physical random number generator ［C］.IEEE Proc Computers ＆Digital Techniques，2007.

［6］Dries Schellekens，Bart Preneel，Ingrid Verbauwhede.FPGA vendor agnostic true random number generator ［C］.the Proceedings of the 16th International Conference on Field Programmable Logic and Applications，2007.

［7］ZHANG Wangcheng，WU Nanjian.A hybrid random number generator using single electron tunneling junctions and MOS transistors ［J］.Journal of Semiconductors，2008，29 （4）：693－700.

［8］Patrick Lacharme.Post－Processing functions for a biased physical random number generator［G］.LNCS 5086：15th International Workshop，2008：334－342.

［9］Michal Varchola.FPGA based true random number generators for embedded cryptographic applications ［C］.Proceedings of the 12th International Conference on Cryptographic Hardware and Embedded Systems，2010.

［10］ZHANG Xiaofeng，BAI Guoqiang，CHEN Hongyi.True random number generator for network security co－processor［J］.Computer Engineering，2009，35 （10）：229－231 （in Chinese）.［張曉峰，白國強，陳弘毅.應用于網絡安全協處理器的真隨機數產生器［J］.計算機工程，2009，35 （10）：229－231.］

［11］Sunar B，Martin W J，Stinson D R.A provably secure true random number generator with built－in tolerance to active attacks ［J］.IEEE Transactions on Computers，2007，56 （1）：109－119.

［12］HUO Wenjie，LIU Zhenglin，CHEN Yicheng，et al.Design of a true random number generator using FPGA ［J］.Journal of Huazhong University of Science and Technology（Natural Science Edition），2009，37 （1）：73－76 （in Chinese）.［霍文捷，劉政林，陳毅成，等.一種基于FPGA的真隨機數生成器的設計 ［J］.華中科技大學學報 （自然科學版），2009，37 （1）：73－76.］

［13］Berk，Sunar.True random number generators for cryptography ［M］.Cryptographic Engineering，Springer，2009：55－73.

［14］PAN Song，HUANG Jiye.EDA technology functional tutorial：VHDL edition［M］.4th ed.Beijing：Science Press，2010 （in Chinese）.［潘松，黃繼業.EDA技術實用教程：VHDL版［M］.4版.北京：科學出版社，2010.］

［15］Santoro R，Sentieys O，Roy S.On－the fly evaluation of FPGA－based true random number generator ［C］.IEEE Computer Society Annual Symposium on VLSI，2009：55－60.