基于多相位自定時振蕩環的真隨機數發生器*

陳楊兵， 吳 帆， 蔣劍飛

(1.上海交通大學 電子信息與電氣工程學院，上海 200240；2.中國船舶重工集團公司第七一一研究所，上海 201100)

0 引 言

在眾多高端電子設備中，隨機數發生器是其處理器中的重要組成部分，可以通過它產生該系統所需要的安全密鑰、進行系統服務、操作協議、綁定移動電子設備ID以及發展數字簽名驗證協議等。隨機數的質量同樣對密鑰算法的安全性、操作系統的穩定性和統計模擬的準確性有著至關重要的影響，隨機數的質量越高意味著其越難以被預測，系統的安全性也就越高。在生活和工作中，集成電路的應用越來越廣泛，對電路的集成度、工作效率和可移植性有了更高的要求，所以對隨機數發生器的研究也變得越來越重要。

隨機數發生器被分為真隨機數發生器以及偽隨機數發生器兩種主要類型。真隨機數發生器的熵源一般為不確定的、隨機的事件或者一些物理現象，例如熱噪聲，電路抖動或者原子裂變等，通過這些自然界中無法預測和控制的現象產生隨機數序列，這種隨機數沒有確定的趨勢和顯著的規律性，不容易被預測和攻擊，但同時也不容易控制[1,2]。

本文針對傳統反相器振蕩環的頻率隨級數線性減小、對工作環境、電壓和工藝變化非常敏感，容易受到外部的攻擊等不足，提出了一種基于多相位自定時振蕩環的熵源結構，采用異步電路中常用的密勒單元作為隨機熵源的基本單元，通過多個密勒單元有序組合實現熵源結構的振蕩。

1 真隨機數發生器的工作原理

自定時振蕩環是由密勒單元和反相器組成的封閉環狀電路，如圖1所示，其中密勒單元的個數應當不少于3個。

圖1 兩相位的自定時振蕩環結構[2]

在圖1中，自定時振蕩環第i級的基本單元中反相器的輸入連接到密勒單元的一個輸出，其中反相器的輸入名為Ri，該級密勒單元的另一個輸入名為Fi，對應輸出名為Ci。每一級密勒單元的輸入Fi連接到上一級的輸出Ci-1，每一級反相器的輸入Ri連接到下一級的輸出Ci+1。

在自定時振蕩環的振蕩行為模型中，通過創建冒泡(bubble)位和標志(token)位對其進行行為描述。其中，bubble和token的概念主要來源于兩階段通信協議的描述[3]，主要如下：1)如果振蕩環中某級的輸出Ci與其上一級的輸出Ci-1不相等，則認為振蕩環的該級中存在一個token位；2)如果振蕩環中某級的輸出Ci與其上一級的輸出Ci-1相等，則認為振蕩環的該級中存在一個bubble位。若把自定時振蕩環中bubble位的數量記為NT,token位的數量記為NB。則在對振蕩環的設置中，設置振蕩環可以產生自主的振蕩信號，則需要滿足以下三個前提條件：1)自定時振蕩環的級數不應該少于3級；2)自定時振蕩環中bubble的數量應該大于等1；3)振蕩環中token的數量為一個正偶數。

有關研究表明，在高頻范圍工作時，自定時振蕩環魯棒性會明顯優于反相器組成的振蕩環結構。自定時振蕩環中會存在兩種振蕩模式：猝發振蕩模式以及均勻間隔振蕩模式。有關研究數據證明，在遵循自定時振蕩環的設計規則前提下，可以通過配置初始化狀態來設置自定時振蕩環的振蕩方式，而不需要考慮其他因素的影響。

如果自定時振蕩環設置的初始狀態中bubble和token的數量越接近，則該振蕩環輸出中含有抖動的時鐘頻率越高，并且此自定時振蕩環越接近均勻振蕩模式[4]。

當token與bubble的數量之比大約等于輸入端Fi到輸出端的靜態延時Dff與輸入端R到輸出端的靜態延時Drr之比時，振蕩環就可以實現均勻振蕩。在本文提出的設計中，密勒單元通過使用KCU116 FPGA中的查找表單元LUT進行實現，因此如果忽略連線之間的延時，可以近似將Dff和Drr認為是相等的，因此可配置自定時振蕩環初始狀態中的bubble和token的數目保持最小差，振蕩環就會工作在均勻振蕩模式，即滿足下面的條件NT/NB=Dff/Drr，NT=NB。

兩相握手協議的自定時振蕩環具有上述諸多優點，但通過使用Virtuoso仿真軟件仿真發現，四相握手協議的自定時振蕩環與兩相握手協議的自定時振蕩環相比，在相同級數的條件下，其具有振蕩頻率更高，熵源隨機性更好的特點。因此在上述自定時振蕩環的結構上，本文對熵源結構進行了進一步優化，采用四相握手協議組成自定時振蕩環，其中單級四相握手協議的自定時振蕩環結構如圖2所示。

圖2 單級四相協議自定時振蕩環結構

為了設置四相協議自定時振蕩環的初始狀態，需要在各個密勒單元上均添加置位Set和復位Reset信號，當Set置位信號為1，而Reset復位信號為0時，該密勒單元的輸出則為1。當Set置位信號為0，Reset復位信號為1時，該密勒單元的輸出則為0，其他情況下，密勒單元的輸出則和輸入相關，即當兩個輸入相同時，輸出與輸入相同，當兩個輸入不相等時，輸出則保持上一個狀態。

2 真隨機數發生器的電路設計

2.1 整體結構

本文提出了一種利用多相位自定時振蕩環結構為熵源，以查找表以及CARRY進位鏈結構為熵源提取電路的真隨機數發生器結構，整體系統設計結構如圖3所示。

圖3 真隨機數發生器整體設計

主要由熵源產生電路、熵源提取電路、后處理電路三個單元電路部分組成，因為本設計是基于KCU116 FPGA平臺，FPGA包含基本可編程邏輯單元(CLB)，其中包括了查找表(LUT)，因此本文電路中實現的多相位自定時振蕩環采用6輸入LUT實現。

2.2 熵源提取電路

本文新提出的熵源提取方法是基于現場可編程門陣列(FPGA)中的CARRY單元具有延遲的基本特性，通過對自定時振蕩環的上升及下降邊沿進行采樣得到隨機序列。相比于其它通過提高振蕩環的頻率從而提高吞吐率的方法，本方法主要是通過對單個振蕩周期的上升及下降邊沿進行解碼提取熵源，提出本方法的前提依據是因為隨機數的吞吐率與采樣時鐘頻率成比例，在一定情況下，采樣時鐘的頻率越高，真隨機數的吞吐率就越大。

在Xilinx FPGAs中，每個CLB中均包含有2個CARRY延遲鏈單元，本質上其是用來實現加法、乘法和分支等功能的，通過設置其原語輸入等操作，則也可以利用其對熵源進行延遲采樣，一條CARRY延遲鏈中包含有多個延遲級，因此可以通過把各個延遲級連接到觸發器中保存其采樣數據，這樣就可以實現從連續不斷的模擬數據轉換為單個的數字[5]。本結構能夠被用來進行高時鐘采樣并且實現高吞吐量的模數轉換。

CARRY延遲鏈的內部結構由CARRY快速延遲單元和多個連接到其輸出的觸發器組成，在采樣時鐘上升沿，延遲鏈的輸出被D觸發器捕捉到。而這些輸出是反映出自定時振蕩環的內部振蕩狀態，為了能夠捕捉到全部抖動狀態，可以將采樣時鐘頻率提高到振蕩時鐘頻率的2倍，這樣可以大大提高真隨機數的產生速率[6]。

本文隨機數發生器中，熵源和熵源提取電路被實現為2個獨立的部分。熵源系統中所有的隨機性都是由信號邊緣的不確定性產生的。熵源信號首先通過CARRY延遲單元進行延遲傳輸，再通過連接的觸發器進行采樣，從捕獲的數據片段解碼出信號邊緣的位置，然后熵源提取電路產生輸出一個隨機比特，采樣時序如圖4所示，其中Ci為自定時振蕩環的輸出，CLK為時鐘采樣信號，D1…D4是D觸發器的采樣輸出，因為Ci中包含抖動不確定性，因此D觸發器采樣也就帶有不確定性。

圖4 熵源提取電路的采樣時序

2.3 后處理電路

真隨機數發生器中常使用后處理電路對產生的原始隨機數序列進行糾偏。常用的后處理電路方式有馮諾依曼糾偏法以及異或鏈方法等。馮諾依曼糾偏法經常被用來消除隨機數序列存在的局部偏置，可以在很大幅度上提高輸出隨機數的隨機性質量，并且這種方法的電路設計非常簡單，容易實現。但是這種后處理方案減少了輸出的隨機數的位數，使得隨機數發生器的輸出速率降低，影響整個器件的處理速度。在正常環境下，本電路產生的隨機數已經具有很好的隨機性，但當環境或者其他因素變化時，產生的隨機數據流可能出現偏置現象，即0和1的比例不是1︰1。為了增強電路的魯棒性，本電路添加一個異或鏈進行糾偏[7]。本電路不會降低比特流輸出速率。假設隨機數發生器產生0的概率為p，則產生1的概率為1-p，那么經過上述后處理電路之后，產生0的概率則變為

P(X=0)=2p(1-p)=2p-2p2

(1)

其產生1的概率則相應變為

P(X=1)=1-P(X=0)=1-2p+2p2

(2)

3 系統實現與仿真分析

3.1 電路系統的實現

傳統由CMOS構成的密勒單元在FPGA中無法實現，但在Slice單元中的LUT可以通過定義真值表的方式來實現需要的邏輯功能，密勒單元也可通過這種方式實現。

如圖5所示，在基本的六輸入LUT單元中，兩個輸入a，b分別為密勒單元的正向輸入與反向輸入端，Set置位和Reset復位信號則為初始狀態控制信號。輸出端為O，由于密勒單元存在的一種情況保持上一狀態不變，因此需要將查找表LUT的一個輸入端和輸出端相連接，本次使用的四相協議的自定時振蕩環結構，因此每級振蕩環都需要使用2個LUT進行實現，其LUT配置的真值表均為64'hEE00FFEE8800FF88。LUT單元在FPGA電路板上資源豐富，排列整齊而且緊密，使得本結構在FPGA中很容易得到滿足，通過四相協議的自定時振蕩環的每一級都固定為2個LUT后，需要手動布局布線，固定每個密勒單元的位置。

圖5 單級四相協議在FPGA上實現原理

3.2 系統仿真與分析

在FPGA上實現電路系統后，通過使用通用異步收發器(universal asynchronous receiver transmitter,UART)串口，把真隨機數發生器產生的隨機數據導入到PC端。在PC端輸出至少100萬位的隨機數后，需要對這些隨機數序列使用NIST套件軟件進行測試，由于NIST的15項標準測試指標中有一部分測試標準的數據量要求最少為100萬位。本文中設計的真隨機數發生器采用資源占用最少的原則來進行配置，此自定時振蕩環選擇了最小的級數,即3級在250 MHz的采樣時鐘頻率下對產生的隨機數進行多次測試，其中每項測試取統計平均值，測試結果如表1所示。

表1 NIST測試結果

本文提出的四相協議自定時振蕩環結構由1個3級自定時振蕩環、3個熵源提取電路和1個后處理單元組成。因為每一級自定時振蕩環使用2個LUT6，熵源提取電路使用1個LUT6和4個寄存器，XOR鏈使用1個LUT6。最后，后處理使用1個LUT6和4個寄存器。將本文提出的方案與其他真隨機數發生器架構設計進行比較，如表2所示。對于每一個作為對比的隨機數發生器，本文均分析了所提供的吞吐量和所需的硬件資源。此外，還考慮了硬件實現，包括實現平臺和熵源。

表2 本設計與其他隨機數發生器對比

對兩相協議自定時振蕩環和四相協議自定時振蕩環在相同級數的情況下的振蕩情況做出對比，在Virtuoso中仿真結果如圖6所示，可表明，四相協議的自定時振蕩環振蕩頻率明顯高于兩相協議的自定時振蕩環。

圖6 四相(上)和兩相(下)振蕩波形

理論上,示波器可以測量周期抖動和周期偏差，但由于采樣頻率誤差的引入，不適合測量偏差很小的抖動值。因此，采用引入的理論抖動積累特性來測量累積抖動并計算初始抖動值。如圖7所示，同時測量了同為3級的兩相自定時振蕩環和四相協議自定時振蕩環結構的周期抖動。可以看出，四相協議的自定時振蕩環產生的抖動更加具有隨機性。

圖7 抖動測量

4 結束語

本文基于四相協議的自定時振蕩環結構提出了一種全數字真隨機數發生器系統，在Xilinx KCU116 FPGA上進行實現，通過使用四相協議的自定時振蕩環保證了系統的高頻情況下的抖動頻率;通過直接例化查找表保證密勒單元的實現;通過手動布局布線保證采樣傳輸的精度。仿真結果表明:本文提出的真隨機數發生器結構不僅在高頻情況下具有較高的高斯抖動，而且具有高振蕩頻率，基于全數字電路設計，具有很好的移植性，而且具有更大的隨機性。