真隨機(jī)數(shù)發(fā)生器在FPGA上的吞吐量技術(shù)解析

真隨機(jī)數(shù)發(fā)生器在FPGA上的吞吐量技術(shù)解析一.綜述真隨機(jī)數(shù)發(fā)生器（TRNG）是硬件加密的重要組成部分，它與偽隨機(jī)數(shù)生成器（PRNG）不同，是利用抖動(dòng)等不可控因素作為隨機(jī)數(shù)的熵源，所生成的隨機(jī)數(shù)具有真正的隨機(jī)性。本文講述一種新穎的熵提取方法，用來提高基于抖動(dòng)的真隨機(jī)數(shù)發(fā)生器在FPGA上的吞吐量。即通過利用超高速的進(jìn)位邏輯基元，提高熵提取的效率，從而提高吞吐量。下面以Spartan-6FPGA上基于環(huán)形振蕩器的真正隨機(jī)數(shù)發(fā)生器為例說明設(shè)計(jì)步驟和技術(shù)。這種設(shè)計(jì)方法同在FPGA上基于抖動(dòng)的高效TRNG相比，所需要的熵提取累積時(shí)間縮短了3個(gè)數(shù)量級(jí)，而且僅僅用了67個(gè)slice就實(shí)現(xiàn)了14.3Mbps的吞吐量，并且這項(xiàng)研究提供了對(duì)安全性的正式評(píng)估。二.介紹早期FPGA的TRNG實(shí)現(xiàn)不提供熵模型。早期研究出的發(fā)生器通過使用諸如NIST和DIEHARD等統(tǒng)計(jì)測(cè)試進(jìn)行驗(yàn)證，但他們?nèi)狈?duì)安全性的正式評(píng)估。在FPGA上僅有少數(shù)TRNG設(shè)計(jì)提供數(shù)學(xué)模型和熵估計(jì)。而我們的新方法從累積的定時(shí)抖動(dòng)中提取高效的熵。不是通過以高能量或面積為代價(jià)增加轉(zhuǎn)換數(shù)量來提高吞吐量，而是專注于改善單次轉(zhuǎn)換的熵提取。我們的主要想法是基于TRNG吞吐量與采樣信號(hào)的定時(shí)分辨率的平方成比例增加的事實(shí)。由于這個(gè)原因，即使定時(shí)分辨率的適度改進(jìn)也會(huì)導(dǎo)致積累時(shí)間和比例吞吐量增益的大幅降低。在XilinxFPGA上，兩種類型的slices包含一個(gè)進(jìn)位鏈（carrychain）基元，可用于生成分支，加法器或乘法器。該基元由連接到觸發(fā)器的四個(gè)延遲級(jí)組成，并可配置為抽頭延遲線?？梢酝ㄟ^專用路徑連接來自同一列上的相鄰slice的進(jìn)位鏈，以形成更大的延遲線。這種配置可用于采樣時(shí)間精度較高的信號(hào)，并已用于實(shí)現(xiàn)高分辨率時(shí)間數(shù)字轉(zhuǎn)換器。通過利用進(jìn)位鏈進(jìn)行熵提取，我們的TRNG實(shí)現(xiàn)了更小的占位面積，

更大的吞吐量。并且提供了此TRNG的安全評(píng)估。三.TRNG的實(shí)現(xiàn)方案TRNG評(píng)估的早期方法包括收集隨機(jī)數(shù)據(jù)并運(yùn)行一系列統(tǒng)計(jì)測(cè)試，如NIST和DIEHARD測(cè)試。這種黑盒子方法的一個(gè)主要缺陷是所有PRNG即使產(chǎn)生完全確定性輸出也可以輕松通過統(tǒng)計(jì)測(cè)試。即使用TRNG設(shè)計(jì)人員驗(yàn)證自己的設(shè)計(jì)，這種方法也是有問題的。例如，設(shè)計(jì)師可能認(rèn)為，隨機(jī)性是由熱抖動(dòng)引起的，而實(shí)際上它來自不穩(wěn)定的電源。在這種情況下，如果TRNG與穩(wěn)壓器一起使用，它可能會(huì)產(chǎn)生非常弱的抖動(dòng)。雖然統(tǒng)計(jì)測(cè)試可用于初始分析或健全性檢查，但它們不能代替正式的安全評(píng)估。TRNG的正式安全評(píng)估需要TRNG的數(shù)學(xué)模型和熵評(píng)估。AIS-31為TRNG的設(shè)計(jì)和評(píng)估提供了一個(gè)框架。AIS-31認(rèn)證的要求之一是熵源的隨機(jī)模型和生成熵的下邊界的估計(jì)。隨機(jī)模型用于描述隨時(shí)間演變的概率系統(tǒng)。它比物理模型（如晶體管模型）更簡(jiǎn)單，因?yàn)樗豢紤]影響隨機(jī)性的過程。這種類型的模型用于描述在電路中產(chǎn)生熵的過程，例如抖動(dòng)累積或從亞穩(wěn)狀態(tài)解析的過程。圖1顯示了TRNG的框圖。隨機(jī)模型必須基于明確陳述和實(shí)驗(yàn)可驗(yàn)證的假設(shè)。該模型的目標(biāo)是為平臺(tái)參數(shù)（例如LUT延遲或噪聲參數(shù)）和設(shè)計(jì)參數(shù)（例如環(huán)形振蕩器的數(shù)量或采樣頻率）的不同值提供熵估計(jì)。所獲得的隨機(jī)模型基于輸入?yún)?shù)（平臺(tái)和設(shè)計(jì)參數(shù)）來計(jì)算最小熵。設(shè)計(jì)流程的下一個(gè)階段是通過實(shí)驗(yàn)獲取平臺(tái)參數(shù)。之后，需要確定最佳設(shè)計(jì)參數(shù)。這可以通過使用隨機(jī)模型和平臺(tái)參數(shù)的測(cè)量值來計(jì)算設(shè)計(jì)參數(shù)的不同值的熵來完成。然后可以調(diào)整設(shè)計(jì)參數(shù)直到達(dá)到指定的熵界限。統(tǒng)計(jì)分析在評(píng)估的最后階段完成。四.實(shí)驗(yàn)架構(gòu)我們的架構(gòu)基于高精度采樣不穩(wěn)定信號(hào)的概念，從而比標(biāo)準(zhǔn)方法提取更多的熵。這種方法非常有效，因?yàn)橥掏铝糠矫娴脑鲆媾c精度的改進(jìn)平方成正比。在這個(gè)架構(gòu)中，熵源和熵提取器作為為獨(dú)立的塊來實(shí)現(xiàn)。系統(tǒng)中的所有隨機(jī)性由信號(hào)邊緣的時(shí)間不確定性產(chǎn)生。振蕩器信號(hào)首先通過抽頭延遲線傳播，取樣并根據(jù)捕獲的數(shù)據(jù)片段確定信號(hào)邊緣的位置。數(shù)字化數(shù)據(jù)被傳播到熵提取器，然后在輸出端產(chǎn)生一個(gè)隨機(jī)位。熵源和數(shù)字化模塊如圖2所示。熵源實(shí)現(xiàn)為一個(gè)自由運(yùn)行的n級(jí)振蕩器，使用一個(gè)NAND門和多個(gè)緩沖器。數(shù)字化模塊由連接到每個(gè)延遲元件輸出的快速抽頭延遲線組成。這些延遲線正在執(zhí)行噪聲信號(hào)的時(shí)間-數(shù)字轉(zhuǎn)換。圖3顯示了單抽頭延遲線的內(nèi)部結(jié)構(gòu)。該行由m個(gè)快速緩沖器和一組連接到其輸出的觸發(fā)器組成。轉(zhuǎn)換的時(shí)序分辨率等于分接延遲線單級(jí)的延遲。在時(shí)鐘上升沿之后，每個(gè)緩沖器的輸出數(shù)據(jù)在觸發(fā)器中被捕獲。這些數(shù)據(jù)反映了振蕩器的內(nèi)部狀態(tài)。為了捕捉振蕩器的完整狀態(tài)，必須選擇作為抽頭延遲線的大小的參數(shù)m，抽頭延遲線必須被選擇為使得抽頭線的延遲大于熵源中最慢元素的延遲。否則，信號(hào)邊沿可以通過任何線路檢測(cè)不到。這也是為了提供魯棒性，因?yàn)檎袷幤髟难舆t以及轉(zhuǎn)換的時(shí)間步長(zhǎng)可能因溫度或電壓變化而變化，并且在最壞情況下必須檢測(cè)到信號(hào)邊緣。由于采樣期間的時(shí)序違規(guī)，一些觸發(fā)器可能會(huì)被驅(qū)動(dòng)到亞穩(wěn)狀態(tài)，從而可能產(chǎn)生“氣泡”碼。延遲線的預(yù)期輸出是連續(xù)運(yùn)行'1'，然后運(yùn)行'0'或運(yùn)行'0'由運(yùn)行'1'休止。在大多數(shù)情況下，如圖4（a）所示，信號(hào)沿只會(huì)在一個(gè)延遲線中捕獲。熵提取器用于解碼此邊的位置，它必須能夠處理兩種效果：代碼中的多邊和邊界。由于單個(gè)抽頭線的延遲大于振蕩器元件的延遲，因此會(huì)出現(xiàn)多個(gè)邊緣。如果信號(hào)邊緣看起來靠近延遲線的末端，則信號(hào)可以通過下一個(gè)振蕩器元件傳播，這導(dǎo)致在下一行的開始處出現(xiàn)第二個(gè)邊緣。熵提取器總是解碼第一個(gè)邊緣而忽略第二個(gè)邊緣，見圖4（b）。代碼中的“氣泡”（圖4（c））使用優(yōu)先級(jí)解碼器進(jìn)行過濾。熵提取器的體系結(jié)構(gòu)如圖5所示。抽頭延遲線（由Ci，j表示，其中i是行數(shù)，j是一行中的位數(shù)）分為兩個(gè)階段進(jìn)行處理。首先，所有行均按位進(jìn)行著色，產(chǎn)生一個(gè)m位向量。該矢量被饋送到邊緣檢測(cè)器，該邊緣檢測(cè)器輸出優(yōu)先級(jí)編碼器的LSB，使得奇數(shù)位置被編碼為'0'，甚至位置被編碼為'1'。所提出的架構(gòu)的設(shè)計(jì)參數(shù)是：n環(huán)形振蕩器的級(jí)數(shù)，m-快速延遲線中的級(jí)數(shù)和tA-抖動(dòng)累積時(shí)間。五.隨機(jī)模型在本節(jié)中，我們提供對(duì)擬議設(shè)計(jì)的正式安全評(píng)估。我們從關(guān)于FPGA平臺(tái)的假設(shè)開始，為二元概率計(jì)算開發(fā)一個(gè)簡(jiǎn)單的隨機(jī)模型。主要目標(biāo)是提供每比特熵的下限，以及確定最佳設(shè)計(jì)參數(shù)，如階段數(shù)和抖動(dòng)累積時(shí)間。5.1假設(shè)我們通過以下假設(shè)開始初始安全分析：

?每個(gè)LUT的延遲由一個(gè)確定性分量d0，LUT和一個(gè)隨機(jī)分量Δd組成。隨機(jī)分量受局部熱噪聲的影響。這個(gè)隨機(jī)分量可以用正態(tài)分布N（0，σLUT2）來模擬，其中σLUT是標(biāo)準(zhǔn)偏差。

?除白噪聲之外的噪聲源可能會(huì)對(duì)可變分量產(chǎn)生影響。這些包括閃爍噪聲，由電源變化引起的全局噪聲和攻擊者的操縱影響（例如通過EM輻射）。這些噪音在我們的模型中沒有量化，因此我們將始終假設(shè)最差情況值。

?抖動(dòng)實(shí)現(xiàn)的白噪聲分量是相互獨(dú)立的。

?通過快速延遲線傳播的噪聲信號(hào)使用等距bintstep進(jìn)行采樣。前三個(gè)假設(shè)是眾所周知的并且通過實(shí)驗(yàn)驗(yàn)證。最后一個(gè)需要針對(duì)特定的實(shí)現(xiàn)平臺(tái)進(jìn)行實(shí)驗(yàn)性調(diào)查。5.2二進(jìn)制概率計(jì)算TRNG按以下方式運(yùn)行。振蕩器運(yùn)行時(shí)間tA，之后采樣信號(hào)被激活。在此期間，來自每個(gè)延遲元件輸出的信號(hào)通過快速延遲線傳播。由于振蕩器是自由運(yùn)行的，所以抖動(dòng)隨時(shí)間積累。只要延遲線足夠長(zhǎng)（m·tstep>d0，LUT），就可以保證在延遲線中至少捕獲一個(gè)噪聲信號(hào)邊緣。圖6顯示了熵提取模型。描述采樣邊緣和噪聲信號(hào)之間的相對(duì)熱抖動(dòng)使用高斯分布。由于抖動(dòng)實(shí)現(xiàn)是獨(dú)立的，在時(shí)間tA之后積累的熱抖動(dòng)的標(biāo)準(zhǔn)偏差與轉(zhuǎn)換事件的數(shù)量的平方根成比例：噪聲信號(hào)以精確的tstep采樣并且TDC的鄰近狀態(tài)使用不同的比特進(jìn)行編碼。1和0的概率等于曲線下的面積。這些概率取決于采樣邊緣和噪聲信號(hào)邊緣的最可能位置之間的偏移時(shí)間，如圖6所示。我們將τ定義為有噪聲信號(hào)邊緣與最接近采樣bin中間的間隔，如圖所示在圖中：在不失一般性的情況下，我們可以假設(shè)這個(gè)bin被解碼為1.然后，二元概率由下式給出：其中Φ是高斯分布的累積概率函數(shù)：5.3熵下界二進(jìn)制概率取決于偏移時(shí)間τ。τ的確切值取決于累積時(shí)間，序列中樣本的數(shù)量，還取決于低頻噪聲和確定性噪聲。由于這些因素不可預(yù)測(cè)也不可控，所以應(yīng)該使用最壞情況值來估計(jì)熵的下限。香農(nóng)熵然后由下式給出：圖7顯示了取決于τ的香農(nóng)熵。當(dāng)τ=0時(shí)達(dá)到下限。5.4模型使用所提出的隨機(jī)模型可用于根據(jù)平臺(tái)參數(shù)和設(shè)計(jì)參數(shù)來估計(jì)熵的下限。該模型由一組方程組成，這些方程組可以作為一個(gè)Matlab函數(shù)實(shí)現(xiàn)，該函數(shù)根據(jù)平臺(tái)和設(shè)計(jì)參數(shù)產(chǎn)生熵下限。平臺(tái)參數(shù)是實(shí)現(xiàn)平臺(tái)的物理參數(shù)，它們應(yīng)該通過測(cè)量來確定。此設(shè)計(jì)的相關(guān)平臺(tái)參數(shù)為：d0，LUT-單個(gè)LUT的平均延遲，帶有快速延遲線的tstep-bin以及由單個(gè)轉(zhuǎn)換事件生成的熱噪聲σLUT。一旦平臺(tái)參數(shù)已知，該模型用于確定不同設(shè)計(jì)參數(shù)值的熵的下限。設(shè)計(jì)參數(shù)為：環(huán)形振蕩器中的級(jí)數(shù)，快速延遲線中的m級(jí)，fCLK系統(tǒng)時(shí)鐘頻率，tA-抖動(dòng)累積時(shí)間（也可以表示為NA-系統(tǒng)時(shí)鐘周期數(shù)）和可選的下采樣因子k。下采樣可用于通過將k個(gè)鄰近倉(cāng)組合成一個(gè)倉(cāng)來提高快速延遲線中的時(shí)間-數(shù)字轉(zhuǎn)換的線性度。隨機(jī)模型用于確定不同設(shè)計(jì)參數(shù)值的熵值，從而可以探索不同的設(shè)計(jì)折衷。因此，TRNG的設(shè)計(jì)過程由以下四個(gè)步驟組成：

步驟1：測(cè)量相關(guān)的平臺(tái)參數(shù)。

步驟2：基于隨機(jī)模型和獲得的平臺(tái)參數(shù)確定最優(yōu)設(shè)計(jì)參數(shù)。

第3步：FPGA實(shí)現(xiàn)。步驟4：對(duì)生成的比特進(jìn)行統(tǒng)計(jì)評(píng)估。5.5后處理生成的位可以使用后處理來改進(jìn)。后處理是一種壓縮技術(shù)，以降低吞吐量為代價(jià)提高了每比特熵。Xor后處理是一個(gè)簡(jiǎn)單的方法，具有緊湊的硬件實(shí)現(xiàn)。它由連續(xù)產(chǎn)生的位組成，從而將吞吐量降低np倍。提出的隨機(jī)模型可以用來估計(jì)生成數(shù)的最大偏差，定義為：使用壓縮率np的后處理序列的偏差為：然后可以計(jì)算新的熵值。六.實(shí)施使用XilinxSpartan-6FPGA實(shí)現(xiàn)。熵源和數(shù)字轉(zhuǎn)換器的實(shí)現(xiàn)方法如圖8所示。環(huán)形振蕩器的階段使用LUT實(shí)現(xiàn)，快速延遲線使用進(jìn)位鏈基元實(shí)現(xiàn)。在Spartan-6上，一半的片包含這些進(jìn)位原語(yǔ)。這些切片位于偶數(shù)列中。通過連接來自相同列中相鄰切片的進(jìn)位基元來形成長(zhǎng)進(jìn)位鏈。振蕩器的延遲級(jí)放置在快速延遲線正下方的切片中。這些是我們?cè)趯?shí)現(xiàn)中使用的唯一布局約束。設(shè)計(jì)的其余部分是自動(dòng)合成和實(shí)現(xiàn)的。6.1平臺(tái)參數(shù)感興趣的平臺(tái)參數(shù)是LUT延遲d0，LUT，熱抖動(dòng)的標(biāo)準(zhǔn)偏差σG，LUT和TDC轉(zhuǎn)換的時(shí)間步長(zhǎng)tstep，即進(jìn)位鏈中單個(gè)元件的延遲。

LUT延遲是通過實(shí)現(xiàn)一個(gè)環(huán)形振蕩器并在固定時(shí)間內(nèi)計(jì)算轉(zhuǎn)換次數(shù)來確定的。發(fā)現(xiàn)d0，LUT=480ps。

抽頭行延遲步驟通過捕獲長(zhǎng)進(jìn)位鏈中的振蕩器輸出并計(jì)數(shù)時(shí)鐘周期的級(jí)數(shù)來確定。結(jié)果大約是tstep=17ps。

熱抖動(dòng)測(cè)量必須非常小心地執(zhí)行，因?yàn)榇藚?shù)非常重要。從歷史上看，有很多論文高估了這個(gè)參數(shù)，為了獲得準(zhǔn)確的結(jié)果還有幾個(gè)挑戰(zhàn)需要克服。進(jìn)行測(cè)量的最可靠的方法是，因?yàn)榭梢栽谝_，封裝和示波器上過濾出熱噪聲。根據(jù)文獻(xiàn)[4]給出的電路模型，測(cè)量時(shí)間需要很短（1μs或更短），否則低頻噪聲占主導(dǎo)地位。測(cè)量必須有差別地進(jìn)行，以便考慮全球噪聲源，例如電源的不穩(wěn)定性。我們提出了一種簡(jiǎn)單的方法來確定使用進(jìn)位鏈邏輯的FPGA上的抖動(dòng)。兩個(gè)相同的環(huán)-

振蕩器被實(shí)現(xiàn)并放置得彼此靠近。振蕩器啟用20ns，并使用基于carry4原語(yǔ)的快速抽頭延遲線捕獲輸出。捕獲的數(shù)據(jù)然后發(fā)送到PC進(jìn)行分析。通過觀察兩個(gè)振蕩器的信號(hào)邊沿之間的差異來確定累積抖動(dòng)。抖動(dòng)的標(biāo)準(zhǔn)偏差從1000個(gè)測(cè)量結(jié)果中估算出來。得到的結(jié)果表明σG，LUT≈2ps。6.2設(shè)計(jì)參數(shù)環(huán)形振蕩器的級(jí)數(shù)n不在熵模型中。為了實(shí)現(xiàn)最緊湊的實(shí)現(xiàn)，應(yīng)該選擇此參數(shù)的值盡可能小。我們選擇n=3的值，因?yàn)檫@是最短的環(huán)形振蕩器，我們可以可靠地測(cè)量頻率和抖動(dòng)參數(shù)。

快速延遲線m的級(jí)數(shù)必須選擇為始終檢測(cè)到信號(hào)邊沿，這種情況發(fā)生在m>d0，LUT/tstep。對(duì)于我們的平臺(tái)參數(shù)，這個(gè)條件變成m>29。由于每個(gè)carry4原語(yǔ)有4個(gè)元素，m必須是4的倍數(shù)。最初，我們嘗試使用8個(gè)進(jìn)位原語(yǔ)（m=32），但測(cè)量結(jié)果表明信號(hào)邊緣是沒有在0.8％的案例中被捕獲。這可能是由于d0是平均延遲值，而一些LUT可能較慢。為了提供更好的魯棒性，我們決定使用9個(gè)carry4階段（m=36），測(cè)量結(jié)果表明邊緣總是被捕獲。沒有進(jìn)一步增加米的好處。要克服的挑戰(zhàn)之一是進(jìn)位鏈的非線性，即不同的倉(cāng)具有不同的寬度。在[6]中進(jìn)行的一項(xiàng)研究表明，這種非線性的主要原因是不平衡的時(shí)鐘樹。同樣的文章還建議通過使用跨越一個(gè)時(shí)鐘區(qū)域的進(jìn)位鏈來提高線性度。在Spartan-6上，時(shí)鐘區(qū)跨越16行。由于我們的設(shè)計(jì)僅使用9個(gè)carry4階段，因此可以設(shè)置放置約束以確保所有9個(gè)階段都處于同一時(shí)鐘區(qū)域。時(shí)間-數(shù)字轉(zhuǎn)換的非線性的另一個(gè)原因是carry4原語(yǔ)的內(nèi)部結(jié)構(gòu)以及過程變化的影響。這可以通過使用k=4的下采樣來改善，這導(dǎo)致了更寬的分箱和更高的tA要求。為了探索設(shè)計(jì)空間，我們實(shí)現(xiàn)了多種版本的TRNG，使用k=1和k=4。積累時(shí)間tA必須是10ns的倍數(shù)，因?yàn)槠脚_(tái)時(shí)鐘頻率是100MHz。我們針對(duì)兩種版本的TRNG探索不同tA值的設(shè)計(jì)空間。6.對(duì)比使用隨機(jī)模型和獲得的平臺(tái)參數(shù)，我們將熵提取方法與基本TRNG在同一平臺(tái)上使用的方法進(jìn)行比較?；綯RNG由一個(gè)由系統(tǒng)鎖定采樣的自由振蕩器組成。抖動(dòng)累積過程與我們的模型中所描述的完全相同，但是熵提取是不同的，因?yàn)橛性肼暤男盘?hào)是在定時(shí)-等于環(huán)形振蕩器的半周期的情況下采樣的。在最好的情況下，環(huán)形振蕩器僅使用一個(gè)LUT來實(shí)現(xiàn)，這會(huì)導(dǎo)致tstep，RO=d0，LUT。由于吞吐量與采樣精度的平方成比例地進(jìn)行縮放，因此我們?cè)趉=1時(shí)獲得的吞吐量改進(jìn)是：這幾乎是3個(gè)數(shù)量級(jí)。對(duì)于k=4，改進(jìn)因子是49.8。七.結(jié)果我們?cè)赬ilinxSpartan-6FPGA上實(shí)現(xiàn)了兩種版本的TRNG。兩個(gè)版本的參數(shù)值都是n=3和m=36