張鴻飛 王 堅 羅春麗 崔 珂 姚志明 梁 昊 金 革

(中國科學技術大學近代物理系 安徽省物理電子學重點實驗室 核探測與核電子學國家重點實驗室 合肥 230026)

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

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

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

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

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

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

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

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

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

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

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

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

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

2 真隨機數(shù)的設計

對應于圖 1，本設計按三個部分來說明：隨機數(shù)源、隨機數(shù)采集模塊和后處理模塊。

2.1 隨機源模塊及Jitter

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

圖2 時鐘的晃動示意圖YFig.2 Jitter of a clock.

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

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

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

2.2 前端采樣

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

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

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

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

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

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

2.3 后處理模塊

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

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

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

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

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

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

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

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

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

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

4 小結

基于以上設計和實驗，完成了一個基于振蕩環(huán)抖動的真隨機數(shù)產(chǎn)生器，速率達到20 Mbps，并通過了NIST測試程序的測試以及Diehard測試程序的測試。本設計不需要特殊的資源(如 PLL)，占用資源非常少(小于 100個邏輯單元)，可在任何 FPGA中實現(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]