張鴻飛 王 堅(jiān) 羅春麗 崔 珂 姚志明 梁 昊 金 革

(中國(guó)科學(xué)技術(shù)大學(xué)近代物理系 安徽省物理電子學(xué)重點(diǎn)實(shí)驗(yàn)室 核探測(cè)與核電子學(xué)國(guó)家重點(diǎn)實(shí)驗(yàn)室 合肥 230026)

隨機(jī)數(shù)應(yīng)用于許多場(chǎng)合，如計(jì)算機(jī)仿真算法、計(jì)算機(jī)游戲、統(tǒng)計(jì)學(xué)等，在密碼學(xué)的各種應(yīng)用的中，隨機(jī)數(shù)更是必不可少。在這些應(yīng)用中，很多算法和協(xié)議依賴于隨機(jī)數(shù)來(lái)產(chǎn)生不可預(yù)測(cè)的安全密鑰，因此需要高質(zhì)量的隨機(jī)數(shù)來(lái)保證系統(tǒng)的安全。比如在量子密鑰分配的各種實(shí)現(xiàn)方案中，隨機(jī)數(shù)在密鑰的形成過(guò)程中起著至關(guān)重要的作用，如果這些隨機(jī)數(shù)被第三方竊取或破解，通訊雙方通過(guò)公共信道討論探測(cè)結(jié)果時(shí)，竊聽(tīng)者可能完全獲取密鑰而不被發(fā)現(xiàn)。因此，無(wú)論是在經(jīng)典的信息安全領(lǐng)域還是在量子信息領(lǐng)域，都須有一個(gè)真隨機(jī)數(shù)發(fā)生器(True Random Number Generator, TRNG)。

1 真隨機(jī)數(shù)產(chǎn)生方法

目前有很多辦法產(chǎn)生各種真隨機(jī)數(shù)，比如利用混沌系統(tǒng)[1]，利用噪聲ADC采樣[2]，利用光的量子效應(yīng)[3]等，本文設(shè)計(jì)的隨機(jī)數(shù)發(fā)生器是利用電子元件的噪聲引起的數(shù)字邏輯中的隨機(jī)晃動(dòng)(jitter)來(lái)產(chǎn)生的。最常見(jiàn)的基于數(shù)字電路的真隨機(jī)數(shù)產(chǎn)生方法為：

1.直接放大法[2,4]：放大電路中的電阻熱噪聲等物理噪聲，通過(guò)比較器比較以獲得隨機(jī)數(shù)序列。

2.振蕩采樣法[5–9]：通過(guò)D觸發(fā)器把兩個(gè)獨(dú)立的振蕩信號(hào)進(jìn)行數(shù)字混合，用低頻信號(hào)采樣高頻信號(hào)，利用環(huán)形振蕩器的頻率抖動(dòng)作為隨機(jī)源，并進(jìn)行后處理，從而得到隨機(jī)數(shù)序列。

3.離散時(shí)間混沌法[1,10,13]：利用混沌電路不可預(yù)測(cè)行以及對(duì)初始條件敏感的依賴性產(chǎn)生隨機(jī)數(shù)。

4.亞穩(wěn)態(tài)采樣法[14-16]：利用數(shù)字電路的亞穩(wěn)態(tài)作為隨機(jī)源。亞穩(wěn)態(tài)是指觸發(fā)器無(wú)法在某個(gè)規(guī)定時(shí)間段內(nèi)達(dá)到一個(gè)可確認(rèn)的狀態(tài)，比如在同步系統(tǒng)中，若觸發(fā)器的建立時(shí)間/保持時(shí)間不滿足，就可能產(chǎn)生亞穩(wěn)態(tài)。觸發(fā)器輸出端Q在有效時(shí)鐘沿后較長(zhǎng)的一段時(shí)間處于不確定的狀態(tài)，這種不確定狀態(tài)最終會(huì)在Q端隨機(jī)輸出0或1，與輸入并無(wú)必然聯(lián)系，從而得到隨機(jī)序列。

如圖 1所示，影響 TRNG性能者有：熵源(Entropy Source)，采集手段(Harvesting Mechanism)，以及后處理(Post-processing)。

圖1 真隨機(jī)數(shù)發(fā)生器的一般框圖Fig.1 Diagram of a true random number generator.

基于模擬電路的結(jié)構(gòu)，有直接放大法和離散事件混沌法。直接放大法真隨機(jī)數(shù)發(fā)生器的熵源的統(tǒng)計(jì)分布更為理想，且熵源噪聲不隨采樣周期變化，但由于采用模擬電路，其依賴于集成電路工藝，且資源消耗大。

基于數(shù)字電路的結(jié)構(gòu)，有振蕩采樣法和亞穩(wěn)態(tài)采樣法。對(duì)于亞穩(wěn)態(tài)采樣法，由于數(shù)字電路中的亞穩(wěn)態(tài)時(shí)間較短，且對(duì)溫度和電壓的變化非常敏感，因此利用亞穩(wěn)態(tài)獲得的隨機(jī)數(shù)一般速率都很慢，且很難做到穩(wěn)定，于是更多地使用震蕩采樣法。

振蕩采樣法真隨機(jī)數(shù)發(fā)生器的功耗較低，集成度較高，便于在通用可編程平臺(tái)(如FPGA、CPLD)上實(shí)現(xiàn)，且易于在SoC中使用。本設(shè)計(jì)所用的真隨機(jī)數(shù)產(chǎn)生方法基本思想是震蕩采樣法。

本文用在FPGA內(nèi)部產(chǎn)生的震蕩環(huán)的抖動(dòng)作為隨機(jī)源，通過(guò)二次采樣來(lái)改善隨機(jī)數(shù)的隨機(jī)性和輸出的穩(wěn)定性，采用基于LFSR(Linear Feedback Shift Register)的后處理，以很小的硬件代價(jià)改善了隨機(jī)數(shù)的統(tǒng)計(jì)特性，從而以較低的成本得到高性能、高速率的真隨機(jī)數(shù)。

2 真隨機(jī)數(shù)的設(shè)計(jì)

對(duì)應(yīng)于圖 1，本設(shè)計(jì)按三個(gè)部分來(lái)說(shuō)明：隨機(jī)數(shù)源、隨機(jī)數(shù)采集模塊和后處理模塊。

2.1 隨機(jī)源模塊及Jitter

數(shù)字電路中的時(shí)鐘信號(hào)總有抖動(dòng)現(xiàn)象，如圖2所示。隨機(jī)抖動(dòng)的來(lái)源為熱噪聲、散粒噪聲和低頻噪聲(1/f噪聲)，與電子器件和半導(dǎo)體器件的電子-空穴特性有關(guān)，因此我們討論的是抖動(dòng)是隨機(jī)抖動(dòng)，其分布是平均值為0、滿足高斯分布的隨機(jī)變量[17]。時(shí)鐘的抖動(dòng)適合于在數(shù)字電路中作為真隨機(jī)數(shù)發(fā)生器的噪聲源，而是否能準(zhǔn)確有效提取這種隨機(jī)信號(hào)是設(shè)計(jì)TRNG的關(guān)鍵。

圖2 時(shí)鐘的晃動(dòng)示意圖YFig.2 Jitter of a clock.

我們?cè)贔PGA 內(nèi)部使用2 N + 1 個(gè)反相器組成一個(gè)閉合的環(huán)路（或N個(gè)buffer加一個(gè)反向器）得到高頻振蕩時(shí)鐘。該時(shí)鐘信號(hào)的周期與門延時(shí)及反相器的個(gè)數(shù)有關(guān)，而與外部信號(hào)無(wú)關(guān)。這種完全由反相器構(gòu)成的環(huán)路功耗較大，需在環(huán)路中加入一個(gè)使能(圖3)，無(wú)需隨機(jī)數(shù)生成器工作便可關(guān)閉振蕩環(huán)，以降低系統(tǒng)功耗。

圖3 震蕩環(huán)的示意圖Fig.3 Structure of an oscillator ring.

振蕩環(huán)的輸出不可避免地存在時(shí)鐘抖動(dòng)(圖2)，相比于用PLL或DLL等采取反抖動(dòng)措施產(chǎn)生的時(shí)鐘，其具有更大的抖動(dòng)，便于采樣模塊的抖動(dòng)采樣。

2.2 前端采樣

根據(jù)上述分析，需把振蕩環(huán)的這種抖動(dòng)有效的提取為隨機(jī)數(shù)的輸出，我們采用2次采樣法。

首先用兩個(gè)頻率很接近的振蕩環(huán)，一個(gè)振蕩環(huán)對(duì)另一個(gè)振蕩環(huán)進(jìn)行采樣，如圖4(a)所示；其相應(yīng)的采樣時(shí)序如圖4(b)所示，兩振蕩環(huán)在上升沿重疊的區(qū)域形成采樣的隨機(jī)性，造成在重疊區(qū)域的前后2個(gè)時(shí)鐘，使C的輸出可能是0也可能是1，從而得到一次采樣的一路隨機(jī)數(shù)。

整個(gè)采樣模塊如圖5所示，先生產(chǎn)n個(gè)振蕩環(huán)，這些振蕩環(huán)由同樣數(shù)目的反向器組成，并且通過(guò)手工布線，使這n個(gè)振蕩器的頻率差異細(xì)微。取其中一個(gè)振蕩環(huán)作為采樣時(shí)鐘，去采樣其他n?1個(gè)振蕩環(huán)。采樣功能由子采樣模塊(圖4a)完成。通過(guò)這樣的采樣，得到n?1組數(shù)據(jù)，這n?1組數(shù)同時(shí)進(jìn)入一個(gè)異或操作，再通過(guò)一個(gè)采樣時(shí)鐘FS進(jìn)行二次采樣，得到原始的隨機(jī)數(shù)。

對(duì)于一次采樣后的信號(hào)，由于使用同樣的采樣時(shí)鐘，其跳變沿相互接近，則對(duì)上升沿-上升沿疊加或上升沿-下降沿重合進(jìn)行異或而得到的隨機(jī)信號(hào)序列(圖6)，均包含了新的采樣后的隨機(jī)性，提高了整個(gè)序列的隨機(jī)性。但由于一次采樣中存在一個(gè)時(shí)鐘的偏差，在一次采樣后的跳變沿不一定全都接近，同樣會(huì)有一個(gè)時(shí)鐘的偏差，會(huì)引入確定性偏差而導(dǎo)致隨機(jī)數(shù)輸出的偏置，這須由后處理來(lái)進(jìn)行糾偏。

圖4 一次采樣框圖與采樣時(shí)序Fig.4 Diagrams of the first sampling and its timing sequence.

圖5 采樣模塊框圖Fig.5 Structure of the sampling module.

2.3 后處理模塊

理想情況下，二次采樣所得信號(hào)具有隨機(jī)的統(tǒng)計(jì)特性。由于芯片會(huì)受溫度電壓等的影響，這導(dǎo)致采樣過(guò)程中出現(xiàn)偏置，影響結(jié)果的統(tǒng)計(jì)特性；而采樣的DFF可能出現(xiàn)亞穩(wěn)態(tài)，影響信號(hào)的偏置。我們可通過(guò)二級(jí)鎖存來(lái)減少亞穩(wěn)態(tài)的出現(xiàn)，但是溫度電壓等的影響始終存在，則通過(guò)上一步驟產(chǎn)生的原始隨機(jī)數(shù)會(huì)有偏置(bias)，須進(jìn)行削偏后處理。

本設(shè)計(jì)采用基于線性反饋移位寄存器(LFSR)的XOR后處理，如圖7所示。通過(guò)對(duì)11位移位寄存器進(jìn)行抽頭異或而得到，不同的抽頭會(huì)得到不同的糾偏效果。原始隨機(jī)數(shù)序列從隨機(jī)序列端輸入，同時(shí)給一個(gè)采樣時(shí)鐘，通過(guò)糾偏處理之后的數(shù)據(jù)通過(guò)隨機(jī)數(shù)輸出端輸出，得到最終得到的隨機(jī)數(shù)序列。在實(shí)驗(yàn)中，采用1、4、5、7、8、9之后進(jìn)行抽頭異或，可以得到比較好的結(jié)果。

圖7 基于LFSR的后處理示意圖Fig.7 LFSR-based post processing.

3 基于FPGA的實(shí)現(xiàn)

FPGA具有可重構(gòu)性且性價(jià)比高，本隨機(jī)數(shù)發(fā)生器具有集成靈活性，可很方便地與FPGA中的其他功能進(jìn)行集成；也可根據(jù)需要，在FPGA的資源范圍內(nèi)，任意添加所需隨機(jī)數(shù)產(chǎn)生器的路數(shù)；接口靈活，可很方便地設(shè)計(jì)各種硬接口和軟接口，以滿足各種應(yīng)用的需求。

本設(shè)計(jì)采用USB技術(shù)實(shí)現(xiàn)對(duì)PC的接口，使產(chǎn)生的高速隨機(jī)數(shù)流能很方便地與其他高速應(yīng)用結(jié)合，同時(shí)也提供了其他接口，如 RS232、RS485、自定義總線等。其硬件框圖如圖8所示，所用FPGA為Altera公司的Cyclone III，當(dāng)然此設(shè)計(jì)也可在其他FPGA上實(shí)現(xiàn)。

圖8 隨機(jī)數(shù)產(chǎn)生器的硬件框圖Fig.8 Hardware of the TRNG.

圖9 隨機(jī)數(shù)的測(cè)試結(jié)果 (a) NIST測(cè)試結(jié)果,(b)Diehard測(cè)試結(jié)果Fig.9 Test results of TRNG.(a) random test result of NIST, (b) random test result of Diehard.

在此硬件平臺(tái)進(jìn)行一系列的試驗(yàn)，產(chǎn)生的隨機(jī)數(shù)通過(guò)USB上傳到PC機(jī)上進(jìn)行隨機(jī)性分析，主要采用美國(guó)國(guó)家標(biāo)準(zhǔn)和技術(shù)研究所(NIST)提供的隨機(jī)數(shù)測(cè)試程序 STS[18]和由 George Marsag編寫的Diehard測(cè)試程序[19]進(jìn)行測(cè)試。在單路一次采樣的實(shí)驗(yàn)基礎(chǔ)上進(jìn)行了二次采樣的實(shí)驗(yàn)，在反向器個(gè)數(shù)為11個(gè)，周期為6.7ns左右(～150 MHz)，子采樣數(shù)為4個(gè)的情況下，通過(guò)改變二次采樣的頻率，分別在 1、2、4、8，16、24、28、32、50 MHz 的頻率下進(jìn)行采樣，采樣數(shù)據(jù)為500 Mb。在頻率低于20 MHz的數(shù)據(jù)均能通過(guò) NIST測(cè)試，如圖 9所示是20M采樣時(shí)鐘下的測(cè)試結(jié)果。

一個(gè)單路輸出的TRNG，有5個(gè)振蕩環(huán)路，每個(gè)振蕩環(huán)路有11個(gè)反相器，共有59個(gè)LUT和20個(gè)Register，全部的LE使用71個(gè)，加上USB接口，F(xiàn)PGA的邏輯資源僅使用317個(gè)LE。單路使用了非常少的資源，因此很容易在FPGA中集成幾十路、上百路的隨機(jī)數(shù)產(chǎn)生器，可使整個(gè)FPGA獲得相當(dāng)高的隨機(jī)數(shù)產(chǎn)生速率。

4 小結(jié)

基于以上設(shè)計(jì)和實(shí)驗(yàn)，完成了一個(gè)基于振蕩環(huán)抖動(dòng)的真隨機(jī)數(shù)產(chǎn)生器，速率達(dá)到20 Mbps，并通過(guò)了NIST測(cè)試程序的測(cè)試以及Diehard測(cè)試程序的測(cè)試。本設(shè)計(jì)不需要特殊的資源(如 PLL)，占用資源非常少(小于 100個(gè)邏輯單元)，可在任何 FPGA中實(shí)現(xiàn)。

1 Miloˇs Drutarovsk′y, Pavol Galajda, Chaos-based true random number generator embedded in a mixed-signal reconfigurable hardware [J], Journal of Electrical Engineering, 2006, 57(4): 218–225

2 Holman W T, Connelly J A, Dowlatabadi A, An integrated analog/digital random noise source [J], IEEE Trans.Circuits Syst.I, 1997,44(5):469

3 Dynes J F, Yuan Z L, Sharpe A W, et al.A High Speed,Post-Processing Free, Quantum Random Number Generator [J], Applied Physics Letters, 2008, 93(3),031109 - 031109-3

4 Petrie Craig S, Connelly J.Alvin, A Noise-Based IC Random Number Generator for Applications in Cryptography [J], IEEE Transactions on Circuits and Systems—I: Fundamental Theory and Applications, 2000,47(5):615–621

5 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

6 Knut Wold, Chik How Tan, Analysis and enhancement of random number generator in FPGA based on oscillator rings [C], International Conference on Reconfigurable Computing and FPGAs, Dec.2008, Cancun, Mexico

7 Alioto M, Fondelli L, Rocchi S.Analysis and performance evaluation of area-efficient true random bit generators on FPGAs, 2008 International Symposium on Circuits and Systems, May 2008, Seattle, USA

8 Schellekens Dries, Preneel Bart, Verbauwhede Ingrid.FPGA vendor agnostic true random number generator[C],International Conference on Field Programmable Logic and Applications, Aug.2006, Madrid, Spain.

9 Kohlbrenner Paul, Gaj Kris.An Embedded True Random Number Generator for FPGAs[C], Proceedings of the 2004 ACM/SIGDA 12thinternational symposium on Field programmable gate arrays, Feb.2004, Monterey, CA, USA

10 Utarovsky'Milos D R, Galajdai Pavol.A robust chaosbased true random number generator embedded in reconfigurable switched-capacitor hardware [C], The 17thinternational Conference on Radioelektronika, April 2007,Brno, Czech Republic.

11 Viktor Fischer, Milos Drutarovsky, True random number generator embedded in reconfigurable hardware [C],Proceedings of CHES 2002, the4thInternational Workshop on Cryptographic Hardware and Embedded Systems.

12 Kwok S H M, Lam E Y.FPGA-based high-speed true random number generator for cryptographic application[C], TENCON 2006.2006 IEEE Region 10 Conference,Nov.2006.

13 Gerosa A, Bernardini R, Pietri S.A fully integrated 8-bit,20 MHZ, truly random numbers generator, based on a chaotic system mixed-signal design [C], 2001 Southwest Symposium on Circuits and Systems.

14 Epstein M, Hars L, Krasinski R, et al.Design and implementation of a true random number generator based on digital circuit artifacts [J], Lecture Notes in Computer Science, 2003, 2779/2003: 152–165

15 Kinniment D J, Chester E G., Design of an on-chip random number generator using metastability [C],Proceedings of the 28thEuropean Conference on Solid-state Circuits, Sept.2002, Firenze, Italy.

16 Danger J L, Guilley S, Hoogvorst P.Fast True Random Generator in FPGAs [C], Proceedings of 2007 IEEE Northeast Workshop on Circuits and Systems, 506–509

17 John A.McNeill, Jitter in Ring Oscillators, IEEE Journal of solid-state circuits, 1997, 32(6):276

18 NIST.NIST Random Number Generation and Testing[OL], 2010, http://csrc.nist.gov/rng

19 Diehard, 1996, http://en.wikipedia.org/wiki/Diehard_tests[OL]