葉少康，李 崢

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

0 引 言

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

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

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

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

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

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

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

2.1 基本原理

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

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

2.2 實(shí)現(xiàn)方法

2.2.1RC電路充放電過(guò)程

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

圖3 RC電路充放電過(guò)程

2.2.2 時(shí)鐘周期量化器

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

圖4 時(shí)鐘周期量化流程

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

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

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

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

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

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

所以

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

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

根據(jù)定理1可得

則有

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

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

3.1 后處理算法

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

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

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

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

（1）符號(hào)定義

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

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

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

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

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

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

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

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

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

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

（2）運(yùn)算符號(hào)描述

田：加法運(yùn)算，表示兩個(gè)8比特?cái)?shù)據(jù)進(jìn)行模256加；

⊕：異或運(yùn)算，表示兩個(gè)8比特?cái)?shù)據(jù)進(jìn)行逐位異或；

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

＞＞＞：循環(huán)右移運(yùn)算，表示8比特?cái)?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個(gè)ci和di后，生成一組32比特的隨機(jī)序列b31～b0。

3.2 后處理電路

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

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

圖7 后處理單元電路

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

4.1 串行輸出單元

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

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

4.2 并行輸出單元

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

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

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

5 仿真與測(cè)試

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

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

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

6 結(jié)束語(yǔ)

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

［1］GONG Hong.Design of true random number generator［D］.Guiyang：Guizhou University，2007 （in Chinese）.［龔紅.真隨機(jī)數(shù)發(fā)生器設(shè)計(jì) ［D］.貴陽(yáng)：貴州大學(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）.［張曉峰，白國(guó)強(qiáng)，陳弘毅.應(yīng)用于網(wǎng)絡(luò)安全協(xié)處理器的真隨機(jī)數(shù)產(chǎn)生器［J］.計(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ì) ［J］.華中科技大學(xué)學(xué)報(bào) （自然科學(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ù)實(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.