基于時鐘抖動流水線結構的高效率真隨機數發生器

摘" 要：現代加密系統對密鑰隨機性的需求不斷增加。使用時序抖動、熱噪聲、亞穩態等作為熵源的真隨機數發生器，因其可以提供高質量的隨機性成為該領域的研究熱點。因此，提出一種可配置、輕量級、高效率的真隨機數發生器。該發生器使用基于隨機數學模型的設計方法，由差分構架的兩級時鐘抖動流水線組成。第一級流水線中兩個環形振蕩器在規定時間內累積抖動，第二級流水線利用近似相同的兩個環形振蕩器的微小周期差構建時間數字轉換器，對第一級輸出的高斯抖動進行量化，通過數字化模塊輸出隨機比特。在時間數字轉換器運行過程中，第一級流水線已經重新啟動累積下一個階段的抖動，減少了空閑時間，提高了真隨機數的質量和效率。在Xilinx Atrix?7平臺進行了驗證，該結構的硬件資源僅消耗了25個LUTs和13個DFFs，獲得高達32.55 Mb/s的吞吐量。

關鍵詞： 真隨機數發生器； 時鐘抖動； 流水線結構； 隨機性； 環形振蕩器； 時間數字轉換器

中圖分類號： TN47?34" " " " " " " " " " " " " " " " 文獻標識碼： A" " " " " " " " " " "文章編號： 1004?373X（2024）14?0070?07

An efficient true random number generator based on jitter pipeline

DONG Liang1， LING Feng1， ZHU Lei2， 3

（1. College of" Communication and Electronics Engineering， Qiqihar University， Qiqihar 161006， China;

2. Heilongjiang Key Laboratory of Big Data Network Security Detection and Analysis， Qiqihar University， Qiqihar 161006， China;

3. School of Computer and Control Engineering， Qiqihar University， Qiqihar 161006， China）

Abstract： In modern encryption systems， the demand for key randomness is constantly increasing. Therefore， the use of clock jitter， thermal noise and uncertain physical processes as entropy sources in a true random number generator has received widespread attention due to its ability to provide high?quality randomness. A configurable， lightweight， and efficient true random number generator is proposed. In this generator composed of a two?stage clock jitter pipelining with differential architecture， a design method based on stochastic mathematical models is applied. In the first stage of the pipelining， two ring oscillators accumulate jitter within a specified time， while in the second stage of the pipelining， a time to digital converter is constructed to quantify the Gaussian jitter output from the first stage using the small period difference between two ring oscillators that are approximately the same. Random bits are output by means of digital module. This structure was verified on Xilinx Atrix?7 platform. 25 LUTs and 13 DFFs are consumed by the hardware resources， achieving a throughput of up to 32.55 Mb/s.

Keywords： true random number generator; clock jitter; pipelining structure; randomness; ring oscillator; time?to?digital converter

0" 引" 言

隨著后量子安全密碼算法的出現，現代加密系統對密鑰隨機性的需求不斷增加。使用不確定的物理過程（時序抖動、熱噪聲、亞穩態）作為熵源的真隨機數發生器（True Random Number Generator， TRNG）[1?2]，因其可以提供高質量的隨機性，可以實現更高級別的算法和協議而受到了廣泛的關注。

FPGA因具有低成本、高靈活性的特點，成為TRNG設計者的首選。基于FPGA的TRNG根據熵源的不同，主要包括使用鎖相環[3?4]、數字時鐘管理器[5]的TRNG，它們的結構簡單，易于實現，但需要通過繁瑣的參數調整才能保證輸出的吞吐率和安全性，具有較差的可移植性。H. Martin等提出的基于自定時環TRNG能夠實現自動化布局布線，具有較高移植性，但該設計在FPGA 中實現較為復雜，且硬件開銷大、吞吐率低[6]。相對于前兩類TRNG，利用環形振蕩器（Ring Oscillator， RO）時鐘抖動作為熵源的TRNG易于在FPGA上實現，備受研究者的青睞。但是RO時鐘抖動的范圍非常小，容易采集到確定的值，使輸出值不具備隨機性。為解決這個問題，B. Sunar等提出將多個環形振蕩器并行來增加抖動范圍[7]，然而，該方法消耗了太多的硬件資源，且吞吐量也不高。文獻[8]中采用可配置延遲線的方式來產生較大的振蕩變化，該設計雖然較文獻[7]在資源開銷上有所降低，但是其吞吐量局限于14.3 Mb/s。為了進一步提高采樣精度，文獻[9]利用FPGA內部高速進位鏈原語構建高精度時間數字轉換器，獲得了高吞吐量，但該設計仍占用了大量的硬件資源。

為了解決TRNG的低硬件資源開銷和高吞吐量之間不能兼容的問題，本文使用基于隨機性數學模型的設計流程，提出一種基于時鐘抖動流水線結構差分構架的真隨機數發生器（Differential Two?stage Jitter Pipelining， DTJP）的TRNG。其結構簡單，硬件開銷小，差分的輸出方式能夠有效減少確定性噪聲對TRNG安全性的影響[10]。DTJP結構的TRNG以流水線方式運行，定時抖動在兩級流水線間分階段累積，最大限度地減少空閑時間。第二級流水線利用兩環形振蕩器（Ring Oscillator， RO）的微小周期差構建時間數字轉換器（Time?to?Digital Converter， TDC），對高斯抖動進行皮秒級高精度量化。本文對提出的TRNG建立隨機性數學模型，估計輸出熵的下限，并在Xilinx Atrix?7平臺進行了多次測試驗證。實驗結果表明，本文設計兼顧低硬件資源開銷和高吞吐量。

1" 基于隨機性模型的DTJP的TRNG設計

1.1" 真隨機數發生器的設計方法

傳統TRNG[3?5]的設計遵循迭代方法，令需要驗證的TRNG生成一定數量的隨機數據，將該數據應用于一系列統計測試（SP800?22、SP800?90B）[11]，通過測試表明數據具有定義上的“隨機性”。如果數據未通過測試，則對TRNG電路的設計參數進行調整，再次運行測試，直到其輸出通過為止。己有研究[11]表明，這種方法會導致TRNG容易受到機器學習帶來的預測攻擊。統計學測試集僅能評估靜態數據的隨機性，無法區分確定性算法、TRNG或兩者組合生成的序列，不能完全作為真隨機數設計的標準。

為了解決這一問題，如圖1所示的基于隨機模型的TRNG設計方法[11]被提出。新的設計流程要求設計者對提出的TRNG的工作過程建立隨機性數學模型，因為該模型源于物理噪聲源，對物理熵源的存在做出驗證是必要的。隨機性模型的輸入包括由TRNG的目標應用和測試標準所提出的熵的需求，以及需要通過實驗測量的硬件物理平臺參數；其輸出為TRNG的設計參數（環形振蕩器數目、噪聲累積時間等），通過對設計參數的優化來實現TRNG。此外，該模型可以估計所輸出的原始隨機序列的熵，然后使用統計測試集來驗證這一估計，將其作為TRNG原型的健全性依據。

1.2" 基于DTJP結構的TRNG電路

本文提出的TRNG電路如圖2所示。該結構主要包括三個子模塊：固定相位（Fixed Phase， FP）模塊、時間數字轉換器（TDC）模塊和數字化模塊。FP和TDC都由兩個周期近似相同的RO組成。

第一級流水線FP中行波計數器（減少RO輸出負載對噪聲的影響）通過對RO1TP、RO2TP的邊沿計數，當振蕩器達到固定相位后，利用兩個或門（消除寄存器穩態過程對噪聲的影響）相繼向第二級流水線輸出累積的高斯抖動，這種差分的輸出方式（減少電壓、溫度等引起的確定性噪聲對隨機性的影響）[10]讓信號FP1、FP2在時域上具有時差[ΔtFP]。

第二級流水線TDC中的RO1TDC、RO2TDC在FP模塊輸出抖動后相繼開始工作（高斯抖動在TDC中開始累積），它們之間具有由[ΔtFP]引起的初始相位差[Δφo]。TDC模塊中的RO1TDC、RO2TDC被配置為具有略微不同的振蕩周期TTDC1與TTDC2，因此RO1TDC、RO2TDC的相位差[φt]在[Δφo]基礎上會隨著時間的增加而緩慢增加或減少。在經過m個RO2TDC的完整周期后，它們的上升/下降沿會首次出現對齊（本文將這個狀態稱為同步完成），此時相位差[φt]為[kπ]（[k]為整數）。達到同步完成的過程是由TTDC1與TTDC2的差值量化的，因此它們的差值定義為TDC的量化分辨率：[res=TTDC2-TTDC1]。

數字化模塊由高速進位鏈原語Carry4[9]構建的皮秒級延遲線、觸發器、XOR門構成。其中RO1TDC觸發兩個寄存器對延遲線兩端采樣，此時XOR門的輸出信號Valid為高電平，代表RO2TDC輸出的上升/下降沿正在延遲線中傳播。Valid為高電平表示檢測到RO1TDC、RO2TDC的邊沿首次達到對齊，即同步完成。通過RO2TDC觸發的二分頻觸發器檢測同步完成時的量化結果，若m等于奇數則輸出隨機比特1，反之輸出隨機比特0。在圖3中1*、0*表示輸出的比特。

1.3" 基于DTJP結構TRNG的時序描述

為了最大限度地減少空閑時間，在TDC模塊對FP的上一次輸出進行量化時，第一級流水線FP已經重新啟動以積累下一個階段的抖動?；贒TJP結構的TRNG的時序描述如圖3所示。系統使能信號ENA為高電平時TRNG進入工作模式。固定相位振蕩器模塊FP中的RO1TP、RO2TP在第N-1個周期內的低電平狀態，對TDC模塊和數字化模塊（同步成功信號Valid）復位。在第N個振蕩周期的上升沿將帶有抖動的信號FP1、FP2以高電平形式輸出到TDC模塊，這個過程中它們的抖動累積時間分別為[TNFP1]、[TNFP2]。此后，RO1TDC、RO2TDC相繼間隔[ΔtFP]開始振蕩，對生成的高斯抖動進行量化，并分別在各自的第一個上升沿對行波計數器CNT1、CNT2和振蕩器RO1TP、RO2TP復位。CNT1、CNT2均達到復位狀態后重啟FP模塊，開始下一階段的抖動累積。

1.4" 基于DTJP結構的TRNG的隨機性數學模型

噪聲一般難以建模，故研究人員普遍的做法是對熵的下界做出估計[12]?；贒TJP結構的TRNG由于TDC模塊中的RO具有隨機的抖動累積時間（0，[max（TNFP1，TNFP2）]），致使系統的熵是動態變化的，因此為了估計提出的TRNG熵的下限，模型中取TDC模塊熵的最小值0，即TRNG的熵完全由FP模塊貢獻。該模型僅對獨立于其他噪聲的高斯噪聲做出分析。

不受噪聲影響的環形振蕩器的相位是關于時間t的連續線性函數：

[φ（t）=ωt+φo] （1）

式中：[ω]為角速度；[φo]是初始相位。

P. Adriian等人的研究[12]表明，受高斯熱噪聲影響的振蕩器的相位表現為具有正漂移的維納過程：

[φ（t）=ωt+φo+σW（t）] （2）

式中：[ωt+φo]是正漂移量；[W（t）（t≥0）]表示標準維納過程；[σ]是標準差，[σ=σ2jitter?t]，[σ2jitter]為RO高斯抖動強度[10]，是最重要的平臺參數。因此當RO振蕩時間為[ta]時，其相位服從高斯分布：

[φ（ta）～N（ωta+ωo，σ2ta）] （3）

具有正漂移的維納過程首次達到一定水平[a]所需的時間（首達時[TX]），是服從逆高斯分布的[IG]：

[TX～IG（u，λ）] （4）

式中：[u=aω]，[λ=aσ2]。[TX]的概率密度函數為：

[f（t，a）=a-φoσ2πt3exp-[（a-φo）-ωt]22σ2t] （5）

FP中兩個受高斯熱噪聲影響的自由運行RO1FP、RO2FP的隨機過程為：

[φFP1（t）=ωFP1t+σFP1WFP1（t），" " t≥0]

[φFP2（t）=ωFP2t+σFP2WFP2（t），" " t≥0] （6）

RO1FP、RO2FP在時間零點開始，初始相位等于0。兩個RO都運行規定數量的周期N，并分別在時間[TNFP1]和[TNFP2]使TDC激活，即：

[φ（TNFP1）=N2π， φ（TNFP2）=N2π] （7）

如前所述，具有正漂移的維納過程首次達到[N2π]處時，[TNFP#]由逆高斯分布描述：

[TNFP1～IGN2πωFP1，N2πσFP12]

[TNFP2～IGN2πωFP2，N2πσFP22] （8）

新的隨機變量[ΔtFP=TNFP2-TNFP1]由兩個獨立的隨機變量[TNFP#]的差來定義。它的累積分布函數可以通過對[TNFP1]和[TNFP2]的密度函數積分來計算。[FΔtFP（t）=P（ΔTFP≤t）=P（TNFP1≤t+TNFP2）" " " " "=0∞fTNFP2（t2）0t+t2fTNFP1（t1）dt1dt2，" "t≥00∞fTNFP1（t1）t1-t∞fTNFP2（t2）dt2dt1，" "tlt;0] （9）

隨機變量[ΔtFP]的密度函數為：

[fΔTFP（t）=?FΔTFP（t）?t] （10）

設TDC中的RO1TDC在第n個半周期，RO2TDC在第m個完整周期首次完成同步，它們的振蕩時間分別為[tTDC1]、[tTDC2]，公式如下：

[tTDC1=nπωTDC1，" " tTDC2=mπωTDC2] （11）

設由高速進位鏈原語Carry4構建的延遲線，圖4中陰影部分表示延遲線的延遲時間[δ]，那么RO2TDC檢測到RO1TDC邊沿時刻，RO1TDC的電平轉換信號已經在延遲線中傳播了時間[tS]。

當[ΔtFP≥0]，[TNFP1≤TNFP2]時，有如圖4a）所示的時間關系：

[ΔtFP=tTDC1-tTDC2+tS，" "tS∈（0，δ）] （12）

可以得出由m和n決定的[ΔtFP≥0]時的取值范圍：

[max（tTDC2-tTDC1，0）≤ΔtFP≤tTDC2-tTDC1+δ] （13）

當[ΔtFPlt;0]，[TNFP1gt;TNFP2]時，有如圖4b）所示的時間關系，可以得出由m和n決定的[ΔtFP≥0]時的取值范圍：

[tTDC1-tTDC2≤ΔtFP≤min（tTDC1-tTDC2+δ，0）] （14）

本文用集合[Dm，n]表示這個范圍。由于FP到達固定相位后對TDC復位，所以m為小于等于[mmax=ωTDC2TNFP22π]的正整數，n為小于等于[nmax=ωTDC1TNFP1π]的正整數。

因為RO2TDC一旦檢測到同步就會停止工作，因此m從1～[mmax]具有下降的優先級。

設[m=0]為理論上的最高優先級，定義[S0=?]表示概率[m=0]時密度函數[fΔtFP（t）]積分區間的集合。當[m=1]時，令n從1依次加至[nmax]，計算出[nmax]個集合[D1，n]。因為m=1是僅能發生一次隨機實驗，故通過將這些集合取并集，得到不分優先級的[m=1]時密度函數積分區間的集合：

[Siid1=n=1nmaxD1，n] （15）

定義這個過程為m=j時n的遍歷，記為Traversal（m=j）。

則區分優先級的[m=1]時[ΔtFP]的密度函數積分區間的集合為：

[S1=Siid1??RS0] （16）

式中：[S0]在R上的補集[?RS0]表示[m=0]未發生時[ΔtFP]所在的域。

當m=2時，執行Traversal（m=2），得到不分優先級時密度函數積分區間的集合[Siid2]。

則區分優先級的[m=2]時，[ΔtFP]的密度函數積分區間的集合為：

[S2=S2??R（S0?S1）] （17）

式中[S0]在R上的補集[?R（S0?S1）]表示[m=0]，1未發生時[ΔtFP]所在的域。

不難得出區分優先級的[m=j]時[ΔtFP]的密度函數積分區間的集合為：

[S2=Sj??Rx=1j-1Sx] （18）

式中[Sj]由[i]個不相交的子區間[D'j，x=（ax，bx）]構成，則概率[P（m=j）]為[fΔtFP（t）]在域[Sj]上的積分，公式如下：

[P（m=j）=x=1iaxbxfΔtFP（t）dt] （19）

由此，通過將m為奇數的概率累加得到輸出比特1的概率，將m為偶數的概率累加得到輸出比特0的概率：

[P（b）=P（mmod2=0），" "b=0P（mmod2≠0），" "b=1] （20）

本文設計的TRNG每比特的熵為：

[Hmin=-p（1）log2p（1）-p（0）log2p（0）] （21）

2" 實驗結果與分析

本文在Xilinx Artix?7 FPGA上實現了如圖2所示的結構。一方面利用文獻[10]的方法，在電壓為1.0 V、環境溫度為20 ℃條件下對硬件平臺參數進行測量，結果如表1所示；并以硬件平臺參數作為隨機數學模型的輸入，對TRNG的熵的下限做出了估計。另一方面，將暫存在FIFO中的原始隨機數通過串口發送到PC端，使用統計測試集來驗證這一估計，將其作為TRNG原型的健全性依據。

2.1" 熵的驗證

將硬件平臺參數作為隨機模型的輸入，對所提出的TRNG在FP模塊不同的抖動累積時間下的熵的下限做出了估計，并在相對應的抖動時間下，每次采集1 Mb序列，使用統計測試集NIST SP800?90B得到靜態序列的最小熵，結果如圖5所示。

圖5中“*”標記表示在不同累積時間下TRNG的吞吐率。根據NIST SP800?90B的要求，當輸出的最小熵達到0.99/bit，即視為TRNG合格。所設計的TRNG在TP模塊抖動累積時間為21.94 ns，達到標準，獲得32.55 Mb/s的吞吐率。

2.2" NIST隨機測試標準

NIST制定的隨機數測試標準SP800?22與SP800?90B是目前檢驗靜態隨機序列的主流方式。

SP800?22測試結果見表2，其中 P?value值大于0.01時表明熵源具有良好的隨機性，Prop.為序列按100 000位分組測試的通過率。所有測試項均以較大的P?value值通過，表明生成的隨機序列具有較好的隨機性。

SP800?90B測試中，TRNG生成的隨機序列通過了 IID測試中的排列測試、卡方測試、最長重復子串長度測試，結果如表3所示。在排列測試中，若[C0i+C1igt;5]且[C0ilt;9 995]，認為隨機序列獨立同分布。

2.3" 與其他TRNG比較

表4所示的TRNG設計均是在FPGA中實現。經對比，文獻[7]、文獻[8]硬件資源開銷較大，且吞吐量也不高；在文獻[9]中，雖然吞吐量有了質的提高，但仍然犧牲了較高的硬件資源；文獻[10]、文獻[13]中的隨機模型，也存在同樣的問題，不能同時達到資源開銷小且吞吐量高的要求。本文提出的TRNG包括控制電路，在硬件資源僅消耗25個LUTs和13個D觸發器的條件下，吞吐量高達32.55 Mb/s，能夠較好地平衡低資源開銷與高吞吐量之間的矛盾。

3" 結" 語

本文所提出的抖動流水線概念并不局限于該項研究，使用FP和TDC結構的累積抖動和的解決方案應被視為一個更廣泛的概念，可在其他TRNG架構中使用。

注：本文通訊作者為董亮。

參考文獻

[1] GONG L， ZHANG J， LIU H， et al. True random number generators using electrical noise [J]. IEEE access， 2019（99）： 1.

[2] 劉清源，劉瑞佳，王健，等.基于邊緣計算的泛在電力物聯網群組密鑰管理算法研究[J].電測與儀表，2022，59（7）：48?56.

[3] PETURA O， MUREDDU U， BACARD N， et al. Optimization of the PLL based TRNG design using the genetic algorithm [C]// 2017 IEEE International Symposium on Circuits and Systems. Baltimore， USA： IEEE， 2017： 1?4.

[4] ALLINI E N， PETURA O， FISCHER V， et al. Optimization of the PLL configuration in a PLL?based TRNG design [C]// 2018 Design， Automation amp; Test in Europe Conference amp; Exhibition. Dresden， Germany： IEEE， 2018： 1265?1270.

[5] JOHNSON A P， CHAKRABORTY R S. An improved DCM?based tunable true random number generator for Xilinx FPGA [J]. IEEE transactions on circuits and systems II： express briefs， 2017， 64（4）： 452?456.

[6] MARTIN H， PERIS P， TAPIADOR J E， et al. A new TRNG Based on coherent sampling with self?timed rings [J]. IEEE transactions on industrial in formatics， 2016， 12（1）： 91?100.

[7] SUNAR B， MARTIN W J， STINSON D R. A provablysecure true random number generator with built?intolerance to active attack [J]. IEEE transactions on computers， 2007， 56（1）： 109?119.

[8] ANANDAKUMAR N， SANADHYA S K， HASHMI M S. FPGA?based true random number generation using programmable delays in oscillator?rings [J]. IEEE transactions on circuits and systems II： express briefs， 2020， 67（3）： 570?574.

[9] 魯迎春，梁華國，王鑫宇，等.一種基于環形振蕩器的輕量級高效率的真隨機數發生器[J].電子測量與儀器學報，2021，35（3）：115?122.

[10] YANG B， ROZIC V， GRUJIC M， et al. On?chip jitter measurement for true random number generators [C]// 2017 Asian Hardware Oriented Security and Trust Symposium. Beijing： IEEE， 2017： 91?96.

[11] YANG B，ROZIC V，GRUJIC M， et al. ES?TRNG： a high?throughput low?area true random number generator based on edge sampling [J]. IACR transactions on cryptographic hardware and embedded systems， 2018， 3： 267?292.

[12] ADRIIAN P， INGRID V. An energy and area efficient， all digital entropy source compatible with modern standards based on jitter pipelining [J]. IACR transactions on cryptographic hardware and embedded systems， 2022， 4： 88?209.

[13] ROZIC V， YANG B， DEHAENE W， et al. Highly efficient entropy extraction for true random numbergenerators on FPGAs [C]// 2015 52nd ACM/EDAC/IEEE Design Automation Conference （DAC）. San Francisco， CA， USA： IEEE， 2015： 1?6.