利用細粒度采樣的低開銷雙輸出異或門真隨機數(shù)發(fā)生器研究

姚 亮 黃正峰 梁華國 魯迎春*

①(安徽大學集成電路學院 合肥 230000)

②(合肥工業(yè)大學微電子學院 合肥 230009)

1 引言

當今社會，人們對便捷式電子設備的依賴越來越明顯。這些設備以智能和簡單的方式執(zhí)行多項任務(例如智能手表、智能手機、平板電腦以及筆記本電腦等)的基礎是身份驗證協(xié)議、密鑰和令牌生成等安全技術的實現(xiàn)[1]。真隨機數(shù)生成器 (True Random Number Generator , TRNG)是安全應用中的關鍵構(gòu)建模塊，能夠為數(shù)據(jù)加密、加密隨機數(shù)和初始化向量提供需要高質(zhì)量的隨機位[2]。TRNG從物理過程(如熱噪聲)生成隨機位，其隨機過程是不可預測和非確定性的。

基于物理隨機現(xiàn)象的TRNG，例如熱噪聲、抖動、量子現(xiàn)象等[3]，如何從電路的自然隨機現(xiàn)象中提取快速和高質(zhì)量的隨機數(shù)具有挑戰(zhàn)性?，F(xiàn)場可編程門陣列(Field Programmable Gate Array, FPGA)在嵌入式系統(tǒng)的原型設計和部署中變得非常流行，因此越來越多的設備利用其潛力。為了開發(fā)易于集成到FPGA上的便攜式、輕量級的TRNG知識產(chǎn)權(quán)核，必須考慮FPGA中提供的構(gòu)建模塊。抖動和亞穩(wěn)態(tài)是基于FPGA型TRNG的主要隨機熵源，廣泛使用的熵源電路是構(gòu)建環(huán)形振蕩器(Ring Oscillator, RO)。

RO TRNG的基本原理是同時激勵具有不同標稱頻率的環(huán)形振蕩器，并以采樣頻率對其輸出的異或進行采樣，以產(chǎn)生取決于抖動累積的隨機輸出序列。所設計的環(huán)形振蕩器數(shù)量越多，系統(tǒng)的熵就越高，但是也導致資源使用和功耗增加。值得注意的是，這些設計通常需要后處理編碼方案(例如，馮諾伊曼編碼)才能通過統(tǒng)計測試(例如NIST[4,5]和AIS-31[6])，這也會導致額外的FPGA資源和功耗。因此，研究者針對如何降低資源開銷且提高TRNG熵進行了大量工作。以時間數(shù)字轉(zhuǎn)換(Time-to-Digital Conversion, TDC)技術作為采樣電路的方案[7]，旨在量化單位延遲較小的RO跳躍周期的延遲量，以更高的精度獲取抖動引起的隨機序列。該方案驗證了通過在FPGA上的可配置邏輯塊中設計CARRY4單元，以0.999的最小熵提高了隨機序列的質(zhì)量，但吞吐量僅為12.5 Mbit/s。另一種采用可編程延遲線(Programmable Delay Line, PDL)技術的方法是使RO的振蕩變化變大，以降低幾個等長振蕩器環(huán)之間的相關性，提高TRNG穩(wěn)定性，然而吞吐量僅為6 Mbit/s的隨機性質(zhì)量[8]。最新的基于數(shù)字時鐘管理器(Digital Clock Manager, DCM)的TRNG將吞吐量提高到 300 Mbit/s，面積為38個SLICEs[9]。然而，該方案需要嚴格控制DCM才能驅(qū)動觸發(fā)器進入亞穩(wěn)態(tài)，不同F(xiàn)PGA芯片之間的差異，導致TRNG的可移植性降低。

在這項工作中，一種新穎的輕量級TRNG架構(gòu)在本文中被提出，本架構(gòu)利用了查找表的抖動噪聲特性，通過多相位采樣機制對抖動噪聲進行細粒度采樣，輸出高熵的隨機序列。本文的結(jié)構(gòu)如下：在第2節(jié)中，主要以四相位采樣詳細介紹細粒度采樣機制；第3節(jié)描述其所提出基于多相位采樣的雙輸出異或門(Multi-phase True Random Number Generator based on Dual-output XOR gate,M_DXOR TRNG)的FPGA實現(xiàn)；第4節(jié)，介紹了隨機比特流的分析結(jié)果，采用了常用的測試套件。最后，第5節(jié)對本文進行了總結(jié)。

2 細粒度采樣機制

目前常用的方法是通過構(gòu)建環(huán)形振蕩器結(jié)構(gòu)來輸出時鐘脈沖，其缺點是輸出時鐘脈沖的占空比不是50%，且在脈沖邊界存在抖動[10,11]。電路中存在抖動是不可避免的，可能導致輸出信號出現(xiàn)毛刺，從而影響電路的功能，一般使用鎖相環(huán)(Phase Locked Loop, PLL)的閉環(huán)相位調(diào)整電路能夠確保電路在存在抖動的情況下仍能穩(wěn)定輸出脈沖[12]。本文中通過PLL生成不同相位的采樣時鐘，對抖動電路進行多相位采樣，大大提高了抖動采樣的概率，保證了隨機序列的輸出。

多相位采樣的基本思想是將具有抖動的方波信號進行N等份的分割，然后對每一等份進行采樣。在單相抖動測試模型中，只需要直接對抖動信號源的輸出進行同相積分和中相積分處理后，可得到抖動。對于N相位抖動測試模型，可以分別對N個延時信號進行中相積分和同相積分，最后相加即可得到抖動[13]。在單相抖動測試模型中，通過在具有抖動的方波信號中的每個采樣周期內(nèi)采樣1個點；而在N相位抖動測試模型中，N個延遲在每個采樣周期內(nèi)向每個采樣點發(fā)出1個信號，每個采樣點之間的差異為T/N。

根據(jù)前文介紹，將具有抖動的方波信號進行N等份的分割，并進行延遲配置，其延遲方波之間的差異記為Ts/ N，其中Ts是采樣周期。在正弦相位抖動測試模型中，只有具有抖動信號源的輸出需要直接同相和中相積分[13]。通常，測試抖動信號采用正弦信號[14]，因此抖動信號熵源產(chǎn)生具有正弦相位抖動的時鐘信號，可以表示為

其中，an表 示信號符號極性(+1表示1，–1表示0)，Tc表示符號寬度，ε表示正弦相位抖動，表示為Asin(w1t)。

如圖1所示，本文以四相抖動模型為例，進行公開推導，以證明多相位采樣能夠提高抖動誤差的測量精度。根據(jù)文獻[13]，同相積分和中相積分表達式分別為

圖1 細粒度采樣示意圖

對于抖動ε的估計，有兩種情況：ε<0和ε>0。ε<0表示同相清洗脈沖的前沿和中間相清洗脈沖的前沿分別領先于具有相位抖動的信號的前沿和中間位置。 ε>0 表示滯后。圖1是ε>0時四相抖動測試中同相積分和中相積分的波形示意圖。因此，計算式(2)和式(3)得到

ε <0，即當它領先時，可以得到計算式(2)和式(3)

其中，Ts為采樣周期，ak-1×ak=-1，即相鄰符號必須有極性跳變，歸一化抖動值λ=ε/Tc，ε為實際測試值。

結(jié)合式(4)—式(7)，四相抖動采樣可以表示為

在單相抖動測試中，圖1中帶抖動的方波信號同相和中相積分，即計算式(2)和式(3)在k=0處的值，單相抖動采樣表達式推導為

從式(8)和式(9)可以看出，相位抖動的測量精度與采樣周期直接相關，其中式(8)中的1/8Ts為固定值。因此，抖動誤差可以通過相乘同相積分通道和中相積分通道的輸出值來得到。根據(jù)式(9)可以得出單相測試下抖動ε的測試值為最小采樣間隔的1/2時，相對于式(8)中在四相測試下時的1/8，可以得出四相位測試采樣精度是單相采樣的4倍。因此，本文通過對抖動誤差采樣的推導公式可以判斷出：N相位抖動采樣的精度是單相抖動采樣的N倍，即一種N倍細粒度抖動采樣機制。

3 M_DXOR TRNG電路

本節(jié)主要對所提出的雙輸出異或門單元和TRNG系統(tǒng)框架進行介紹。

3.1 雙輸出異或編程單元

查找表(Look-Up-Table, LUT)是FPGA內(nèi)重要且基本的邏輯資源，其通過輸入端的地址信號查找單元內(nèi)對應地址所存儲的二進制信息。查找表的輸入位數(shù)由4位發(fā)展到現(xiàn)在的6位，例如AMD Xilinx Virtex-6系列FPGA內(nèi)的6輸入雙輸出查找表LUT6_2，其由兩個5輸入單輸出查找表通過一個多路選通器級聯(lián)而成[15]?？紤]到每類SLICE中均含有LUT6_2資源，可以利用LUT6_2實現(xiàn)TRNG設計當中所需的基本器件，這樣就能充分地利用每片SLICE的LUT資源，在一定程度上提高了TRNG的通用性并提升硬件的利用率?；贚UT6_2單元，本文設計了一種如圖2所示的雙輸出異或門單元。如圖2(a)所示基于異或門設計的可編程單元，當CTL=0時，門電路變?yōu)閱畏聪喹h(huán)；當CTL = 1時，電路變?yōu)殡p穩(wěn)態(tài)環(huán)。通過對CTL端口的控制，能夠保證在電路需要“休眠”要求時的逆變器環(huán)不處于振蕩狀態(tài)。

圖2 異或門邏輯單元

減少偏置和提高魯棒性的簡單策略是對多個基本單元的輸出位進行異或運算處理產(chǎn)生一位隨機數(shù)，其熵不小于任何輸入位的熵；因此，只要1個單元產(chǎn)生具有高熵的輸出，最終輸出就具有高熵。本文在最終TRNG設計中采用了多個雙輸出異或門構(gòu)成反相環(huán)，具體可見3.2節(jié)。

3.2 M_DXOR TRNG架構(gòu)

與傳統(tǒng)的基于環(huán)形振蕩器的TRNG類似，使用奇數(shù)個反相器形成自振蕩熵源[16,17]。本文提出如圖3淺黃框所示的基于雙輸出異或門熵源，每個異或門單元連接有D觸發(fā)器，最后將4個D觸發(fā)器的輸出通過異或處理作為隨機序列的輸出。值得注意的是，每個D觸發(fā)器的采樣時鐘是不一樣的，通過PLL模塊產(chǎn)生4種不同相位的時鐘。

圖3 提出的TRNG結(jié)構(gòu)

基于第2節(jié)提出的細粒度抖動采樣機制，在進行相位級數(shù)選擇中發(fā)現(xiàn)許多通過三相采樣獲得的隨機序列無法通過NIST SP800-22測試項目。當選擇四相位及以上級數(shù)時，所有隨機序列都可以通過測試。因此，在考慮降低資源開銷的前提下，本文選擇了四相位采樣，如圖3所示的多相位采樣的基于雙輸出異或門的TRNG架構(gòu)。PLL用于生成不同相位(分別為0°相位、90°相位、180°相位和270°相位)的采樣時鐘，以對抖動電路進行多相采樣。值得注意的是，PLL產(chǎn)生的四相采樣時鐘相當于圖1中的CLKjitter, CLKjitter+Ts/4, CLKjitter+2×Ts/4,CLKjitter+3×Ts/4。

4 實驗結(jié)果與分析

對于所提M_DXOR TRNG架構(gòu)實現(xiàn)于AMD Xilinx 的Virtex-6 FPGA和Artix-7 FPGA開發(fā)板上，通過提取多組1 Mbits數(shù)據(jù)進行統(tǒng)計分析，具體有自相關測試、隨機性測試和抗溫度-電壓測試。

4.1 自相關測試

如果序列不自相關，則可以認為該序列是隨機的[14]。對于自相關測試，本文中使用MATLAB對生成的隨機序列進行了驗證。通過計算皮爾遜相關系數(shù)，當小于0.3時，可以認為序列不相關[14]。如圖4所示，設置滯后值為500，通過計算當前輸出值與500個滯后變量之間的相關系數(shù)，可以看出縱坐標的自相關系數(shù)均小于且接近0，因此表明該序列沒有相關性，也能進一步證明所提出的M_DXOR TRNG能夠產(chǎn)生良好的隨機序列，不易受到攻擊。

圖4 自相關測試

4.2 隨機性測試

隨機性測試是對真隨機數(shù)序列檢驗的有效且必需的方式，目前主要有對隨機序列的隨機性檢驗的NIST SP800-22測試包和AIS-31測試包，以及針對隨機熵進行檢驗的NIST SP800-90B測試包。本文中也采用這3種測試包對實現(xiàn)于Xilinx Virtex-6和Artix-7 FPGA上的TRNG隨機序列進行檢驗。首先，本文在兩種系列FPGA產(chǎn)生的隨機序列上采集100 M bit的數(shù)據(jù)量進行NIST SP800-22測試，其中P-value值為序列隨機數(shù)的指標(P-value大于0.01時，表明通過隨機性測試)，Prop.為100組測試的通過率。如表1所示，表中P-value為100 次實驗的平均值，而對于累加和檢驗，非重疊模塊匹配檢驗、隨機游動狀態(tài)檢驗、隨機游動檢驗和序列檢驗，表中 P-value是對應測試項所有子測試P-value的平均值。可以看出，所有測試項均以較大的P-value值通過NIST SP 800-22測試，其隨機序列具有較好的隨機性。

表1 Xilinx Virtex-6和Artix-7上NIST SP800-22測試結(jié)果

此外，另一個熵估計套件AIS-31[6]也用于評估隨機數(shù)的熵源質(zhì)量，本文分別在Xilinx Virtex-6和Artix-7 FPGA兩塊開發(fā)板實現(xiàn)所提M_DXRO TRNG結(jié)構(gòu)，采集輸出隨機序列進行AIS-31 T8測試，如表2所示，可以得出均高于7.99的字節(jié)熵通過T8測試評估。

表2 AIS-31的T8字節(jié)熵測試

對于NIST SP 800-90B測試，主要用來估計隨機序列的統(tǒng)計分布和最小熵估計，分為對應著獨立同分布測試(IID測試)和非獨立同分布測試(Non-IID測試)。在本文中考慮之前NIST SP800-22和AIS-31對隨機序列的統(tǒng)計進行了分析后，利用NIST SP800-90B的Non-IID測試進行熵評估。Non-IID主要利用MCV測試、Collision測試、Markov測試、Compression測試、t_Tuple測試、LRS測試、MultiMCW測試、Lag測試、MutiMCW測試和LZ78Y測試共10項統(tǒng)計來評估熵[5]。本文分別在Xilinx Virtex-6和Artix-7兩塊FPGA上得到的隨機序列經(jīng)過Markov測試得到的p-max分別為3.62×10–39和3.73×10–39，其h-min分別為0.997 653和0.997 721，測試結(jié)果均通過了Markov測試要求。針對NIST SP800-90B Non-IID測試的另外9項，如圖5所示，其中橫坐標為測試項，左縱坐標為p-max值，右縱坐標為h-min值。可以看到所得到的p-max均在0.5左右波動(p-max越接近0.5表明隨機性越好)，h-min值均接近于1(h-min越大表明熵源質(zhì)量越好)。綜上所述，本文所提結(jié)構(gòu)能夠以較好的隨機性測試結(jié)果通過NIST SP 800-90B的Non-IID測試。

圖5 Xilinx Virtex-6和Artix-7 FPGA上NIST SP800-90B Non-IID 9項測試結(jié)果

4.3 抗溫度-電壓測試

溫度和電壓的環(huán)境變化會影響TRNG(相關TRNG的性能比較如表3所示)的生成質(zhì)量，因此本文中針對溫度和電壓設定了較大范圍，即溫度以步長為20°C從0°C到80°C，電壓以步長為0.2 V從0.8 V到1.2 V。相對于以往以NIST SP800-22測試P-value值作為評估結(jié)果展示的方式，本文采用在不同溫度和電壓的情況下Xilinx Virtex-6 FPGA生成的100組數(shù)據(jù)通過測試項的數(shù)量的平均值作為評估指標。如圖6所示的雷達圖，雷達圖中軸坐標表示不同的溫度，不同顏色表示相應的電壓。對于軸坐標上的數(shù)字，由于NIST 800-22單項數(shù)據(jù)太多，因此這里的通過率為NIST 800-22所有項通過率的平均值。可以看出，在標準1 V電壓下，通過率最高。隨著溫度的改變，通過率有所不同。在正常的溫度條件(20°C)下，通過率最高為99%。隨著溫度的逐漸升高，通過率也在降低?？梢钥闯觯岢龅腗_DXOR TRNG能夠保持平均值為93%以上的通過率，對溫度和電壓具有一定的容忍性。

表3 相關TRNG的性能比較

圖6 Virtex-6上溫度電壓變化測試結(jié)果圖

4.4 相關性能對比

本文所提M_DXOR TRNG通過雙輸出異或門構(gòu)成環(huán)形振蕩器熵源，其熵源電路僅僅占用兩個LUT來實現(xiàn)。與同期的TRNG比較，本文所提出的TRNG資源開銷很小，其ISE Xpower功耗分析為193.31 mW。由于在D觸發(fā)器采樣階段使用100 MHz工作頻率，因此M_DXOR TRNG吞吐量定為100 Mbit/s。此外與之前的TRNG結(jié)構(gòu)文獻[21,18]相比，本文提出的TRNG具有更高的吞吐量和更低的硬件資源開銷。在實現(xiàn)復雜度上，通過PLL能夠產(chǎn)生穩(wěn)定可靠的不同相位采樣時鐘設計，在FPGA中很大程度都能夠?qū)崿F(xiàn)。綜上所述，本文所提出的TRNG架構(gòu)由于在面積開銷上具有很好的競爭，具有潛力輕量級安全應用的候選者。

5 結(jié)束語

本文介紹了一種全新且輕量級的真隨機數(shù)發(fā)生器(TRNG)架構(gòu)。本架構(gòu)利用雙輸出異或門單元來控制環(huán)形振蕩器的工作時間，從而降低了電路功耗。同時，通過多相位細粒度采樣機制，該架構(gòu)顯著提高了捕獲噪聲的可能性。所提出的M_DXOR TRNG已在AMD Xilinx Virtex-6和Xilinx Artix-7 FPGA上成功實現(xiàn)，實驗結(jié)果顯示，所提出的M_DXOR TRNG是一種硬件開銷低的TRNG，以較高的p值通過NIST SP800-22測試和NIST SP800-90B測試，并通過了AIS-31測試。

未來的工作首先擬從器件可配置出發(fā)解決目前所提出的M_DXOR TRNG可靠性通過不佳問題，其次解決對提出的M_DXOR TRNG 進行故障攻擊評估。