葉少康，李 崢

（解放軍信息工程大學(xué) 電子技術(shù)學(xué)院，河南 鄭州450004）

0 引 言

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

真隨機(jī)數(shù)因其具有隨機(jī)性強(qiáng)、無周期和不可預(yù)測性，在密碼系統(tǒng)和非密碼系統(tǒng)中都有著廣泛的應(yīng)用，如彩票抽獎、模擬仿真、密鑰生成和安全協(xié)議等。為此，設(shè)計基于硬件實現(xiàn)的真隨機(jī)數(shù)發(fā)生器具有廣闊的應(yīng)用前景。本文利用RC電路充放電的低穩(wěn)定度設(shè)計了一款真隨機(jī)數(shù)發(fā)生器。

1 真隨機(jī)數(shù)發(fā)生器的總體結(jié)構(gòu)

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

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

圖1 TRNG結(jié)構(gòu)框架

2 噪聲源模塊的設(shè)計

2.1 基本原理

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

圖2 噪聲源實現(xiàn)原理

2.2 實現(xiàn)方法

2.2.1RC電路充放電過程

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

圖3 RC電路充放電過程

2.2.2 時鐘周期量化器

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

圖4 時鐘周期量化流程

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

2.3 采樣電路的設(shè)計

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

首先給出非線性函數(shù)的一個性質(zhì)［8］：

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

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

所以

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

表1 二次布爾函數(shù)的真值表

根據(jù)定理1可得

則有

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

3 后處理模塊的設(shè)計

3.1 后處理算法

圖5 基于布爾函數(shù)的采樣電路

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

圖6 后處理算法結(jié)構(gòu)

圖6 給出了后處理算法的結(jié)構(gòu)，其具體描述如下：

（1）符號定義

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

整個實踐活動包括四個階段，分別是：M+C(強(qiáng)調(diào)創(chuàng)意的構(gòu)思)階段、M+D(強(qiáng)調(diào)創(chuàng)新的設(shè)計)階段、M+I(強(qiáng)調(diào)創(chuàng)造的實施)階段、M+O(強(qiáng)調(diào)分享的運行)階段，各個階段的活動內(nèi)容見表1。整個過程體現(xiàn)了體驗教育、快樂教育、基于項目的教育和創(chuàng)造中學(xué)等教育理念。

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

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

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

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

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

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

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

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

（2）運算符號描述

田：加法運算，表示兩個8比特數(shù)據(jù)進(jìn)行模256加；

⊕：異或運算，表示兩個8比特數(shù)據(jù)進(jìn)行逐位異或；

＜＜＜：循環(huán)左移運算，表示8比特數(shù)據(jù)循環(huán)左移1位；

＞＞＞：循環(huán)右移運算，表示8比特數(shù)據(jù)循環(huán)右移1位。

（3）算法流程

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

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

重復(fù)1）～5），即可源源不斷地產(chǎn)生隨機(jī)數(shù)序列，其中連續(xù)采集4個ci和di后，生成一組32比特的隨機(jī)序列b31～b0。

3.2 后處理電路

根據(jù)后處理算法的結(jié)構(gòu)，結(jié)合后處理模塊整體電路結(jié)構(gòu)，采用數(shù)字電路設(shè)計技術(shù)，設(shè)計如圖7所示的后處理單元電路。

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

圖7 后處理單元電路

4 串并行輸出單元的設(shè)計［14］

4.1 串行輸出單元

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

圖8 串行輸出單元電路結(jié)構(gòu)

4.2 并行輸出單元

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

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

圖9 并行輸出單元電路結(jié)構(gòu)

5 仿真與測試

根據(jù)整個真隨機(jī)數(shù)發(fā)生器的結(jié)構(gòu)框架，用Spectre模擬器對電路進(jìn)行數(shù)?；旌戏抡?，這里取量化時鐘頻率nclk＝100MHz，R＝1.69kΩ，C＝1.2nF，clk＝3.2MHz，sclk＝0.4MHz。通過實驗采集20 000比特用于隨機(jī)性檢測，隨機(jī)性檢測遵循FIPS140－2標(biāo)準(zhǔn)［15］，進(jìn)行頻數(shù)檢測、撲克檢測、游程檢測和長游程檢測，檢測結(jié)果如表2所示。

表2 FIPS140－2測試結(jié)果

測試結(jié)果表明，采用本文所提供方案產(chǎn)生的隨機(jī)序列能夠通過FIPS140－2的統(tǒng)計測試，具有良好的隨機(jī)特性。

6 結(jié)束語

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

［1］GONG Hong.Design of true random number generator［D］.Guiyang：Guizhou University，2007 （in Chinese）.［龔紅.真隨機(jī)數(shù)發(fā)生器設(shè)計 ［D］.貴陽：貴州大學(xué)，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）.［張曉峰，白國強(qiáng)，陳弘毅.應(yīng)用于網(wǎng)絡(luò)安全協(xié)處理器的真隨機(jī)數(shù)產(chǎn)生器［J］.計算機(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ī)數(shù)生成器的設(shè)計 ［J］.華中科技大學(xué)學(xué)報 （自然科學(xué)版），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）.［潘松，黃繼業(yè).EDA技術(shù)實用教程：VHDL版［M］.4版.北京：科學(xué)出版社，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.