基于布爾混沌的物理隨機(jī)數(shù)發(fā)生器

張琪琪，張建國(guó)，李璞，郭龑強(qiáng)，王云才

（1. 太原理工大學(xué)新型傳感器與智能控制教育部山西省重點(diǎn)實(shí)驗(yàn)室，山西 太原 030024；2. 太原理工大學(xué)物理與光電工程學(xué)院，山西 太原 030024）

1 引言

隨機(jī)數(shù)被廣泛應(yīng)用于蒙特卡洛仿真、深度學(xué)習(xí)、身份認(rèn)證、密碼學(xué)等領(lǐng)域[1-4]，尤其在密碼學(xué)中，不可預(yù)測(cè)、統(tǒng)計(jì)無(wú)偏的物理隨機(jī)數(shù)是確保加密信息安全的關(guān)鍵。

目前，很多隨機(jī)數(shù)發(fā)生器（RNG，random number generator）是通過(guò)計(jì)算機(jī)或微處理器運(yùn)行某種確定性的數(shù)學(xué)算法（如線性同余、線性反饋移位等）來(lái)產(chǎn)生偽隨機(jī)數(shù)；但偽隨機(jī)數(shù)具有周期性，存在可被預(yù)測(cè)的安全隱患，因此偽隨機(jī)數(shù)發(fā)生器（PRNG，pseudo-random numbers generator）難以確保加密信息的安全。

與PRNG不同，物理隨機(jī)數(shù)發(fā)生器（Physical-RNG，physical random number generator）可以產(chǎn)生無(wú)周期、不可預(yù)測(cè)的物理隨機(jī)數(shù)，這對(duì)于數(shù)據(jù)加密技術(shù)來(lái)說(shuō)，是真正安全的。目前，Physical-RNG主要利用不可預(yù)測(cè)的物理隨機(jī)過(guò)程作為熵源（也稱為物理熵源）來(lái)產(chǎn)生隨機(jī)序列，例如電路中的熱噪聲[5]、振蕩器的相位抖動(dòng)[6]及非線性系統(tǒng)中的混沌[7]等。電路熱噪聲Physical-RNG由于熱噪聲幅度較小，需要高增益運(yùn)算放大器進(jìn)行放大，而放大器不僅功耗大，其有限的帶寬和失調(diào)還會(huì)使Physical-RNG 的隨機(jī)特性變差。振蕩器Physical-RNG利用低頻時(shí)鐘源的隨機(jī)相位抖動(dòng)來(lái)獲取隨機(jī)數(shù)序列，然而該技術(shù)存在隨機(jī)數(shù)產(chǎn)生速率較低的不足?；煦缡怯煞蔷€性系統(tǒng)產(chǎn)生的一種類噪聲信號(hào)，它具有對(duì)初值敏感、不可預(yù)測(cè)等特點(diǎn)[8]，因而在Physical-RNG設(shè)計(jì)中得到了廣泛的應(yīng)用，如利用離散混沌迭代[9]、時(shí)空混沌[10]、多混沌系統(tǒng)耦合[11]、無(wú)簡(jiǎn)并高維離散超混沌[12]等方法都可以產(chǎn)生高質(zhì)量的隨機(jī)數(shù)。然而，上述混沌系統(tǒng)都屬于數(shù)字混沌系統(tǒng)，存在混沌退化效應(yīng)[13]，其產(chǎn)生的隨機(jī)數(shù)本質(zhì)上都是偽隨機(jī)的[8-13]。

2013年，一種結(jié)構(gòu)簡(jiǎn)單的可集成式 Physical-RNG被報(bào)道，該方法利用帶有自反饋結(jié)構(gòu)的自治布爾網(wǎng)絡(luò)作為物理熵源，實(shí)現(xiàn)了速率為100 Mbit/s（單個(gè) Physical-RNG 單元）的物理隨機(jī)數(shù)產(chǎn)生[14]。但是自反饋結(jié)構(gòu)會(huì)引入相關(guān)性，使得該物理熵源使用了較多、較復(fù)雜的節(jié)點(diǎn)（16個(gè)三輸入邏輯門）以保證產(chǎn)生足夠的熵值。

本文提出并實(shí)驗(yàn)驗(yàn)證了一種無(wú)自反饋結(jié)構(gòu)的自治布爾網(wǎng)絡(luò)物理熵源，它由多個(gè)二輸入異或門節(jié)點(diǎn)組成。在文中，使用了節(jié)點(diǎn)數(shù)量為 15的網(wǎng)絡(luò)結(jié)構(gòu)，產(chǎn)生了帶寬達(dá)680 MHz，最小熵接近于1的布爾混沌信號(hào)。利用該熵源構(gòu)建的Physical-RNG具有實(shí)時(shí)速率為100 Mbit/s（單個(gè)Physical-RNG單元）的物理隨機(jī)數(shù)產(chǎn)生能力。相比于文獻(xiàn)[14]，本方法具有兩項(xiàng)突出優(yōu)勢(shì)：1） 物理熵源結(jié)構(gòu)更為簡(jiǎn)單，最少可由15個(gè)節(jié)點(diǎn)組成；2） 所提出的Physical-RNG擁有更低的功耗，這是因?yàn)樵陔娐分圃爝^(guò)程中，二輸入邏輯門比三輸入邏輯門使用更少的晶體管（約為三輸入邏輯門使用數(shù)的一半），而較少的晶體管意味著更低的功耗。隨機(jī)性測(cè)試結(jié)果表明，本方法產(chǎn)生的物理隨機(jī)數(shù)序列可成功通過(guò)NIST SP800-22及DIEHARD所有測(cè)試項(xiàng)，因而具有良好的隨機(jī)統(tǒng)計(jì)特性。

2 布爾混沌物理熵源

2.1 無(wú)自反饋結(jié)構(gòu)的自治布爾網(wǎng)絡(luò)特征

本文提出的無(wú)自反饋結(jié)構(gòu)的自治布爾網(wǎng)絡(luò)由N個(gè)節(jié)點(diǎn)（二輸入邏輯門）組成，其結(jié)構(gòu)如圖1所示，N個(gè)節(jié)點(diǎn)以雙向耦合連接方式組成環(huán)狀拓?fù)浣Y(jié)構(gòu)。在該網(wǎng)絡(luò)中，N-1個(gè)節(jié)點(diǎn)執(zhí)行異或（xor）運(yùn)算，一個(gè)節(jié)點(diǎn)執(zhí)行異或非（xnor）運(yùn)算。經(jīng)數(shù)值仿真，發(fā)現(xiàn)所設(shè)計(jì)的自治布爾網(wǎng)絡(luò)存在2種狀態(tài)：振蕩狀態(tài)與非振蕩狀態(tài)。當(dāng)自治布爾網(wǎng)絡(luò)中節(jié)點(diǎn)數(shù)量是3的倍數(shù)時(shí)（即N=3n，n為正整數(shù)），該網(wǎng)絡(luò)進(jìn)入振蕩狀態(tài)；否則進(jìn)入非振蕩狀態(tài)，即進(jìn)入所謂的布爾固定點(diǎn)[15]。

為了驗(yàn)證上述情況，在FPGA中搭建了節(jié)點(diǎn)個(gè)數(shù)分別為N=3,4,5,…,11的自治布爾網(wǎng)絡(luò)，并通過(guò)觀測(cè)xnor的電壓輸出來(lái)判定網(wǎng)絡(luò)狀態(tài)。實(shí)驗(yàn)結(jié)果如圖2所示，當(dāng)N=5,7,8,10,11時(shí)，xnor的輸出電壓保持恒定，表明網(wǎng)絡(luò)進(jìn)入了布爾固定點(diǎn)；當(dāng)N= 6,9時(shí)，xnor的輸出電壓持續(xù)變化，表明網(wǎng)絡(luò)處于振蕩狀態(tài)。但是需要說(shuō)明的是，實(shí)驗(yàn)中當(dāng)N= 3時(shí)，網(wǎng)絡(luò)并未進(jìn)入振蕩狀態(tài)，與仿真結(jié)果不符，其原因是如下。1） FPGA中的邏輯門并非響應(yīng)速度無(wú)限快的理想器件，無(wú)法響應(yīng)變化速度過(guò)快的信號(hào)，即存在所謂的低通濾波效應(yīng)[15-16]。2） 自治布爾網(wǎng)絡(luò)處于振蕩狀態(tài)時(shí)，其振蕩頻率f與節(jié)點(diǎn)數(shù)量N成反比。當(dāng)N=3時(shí)，振蕩頻率f較高，高頻振蕩信號(hào)無(wú)法被網(wǎng)絡(luò)中的邏輯門節(jié)點(diǎn)響應(yīng)（即低通濾波效應(yīng)），因此振蕩信號(hào)被衰減和抑制，導(dǎo)致振蕩停止，如圖2（a）所示；而隨著節(jié)點(diǎn)數(shù)量N的增加（如N= 6,9,…），自治布爾網(wǎng)絡(luò)的振蕩頻率f逐漸降低，當(dāng)f小于低通濾波效應(yīng)的截止頻率時(shí)，自治布爾網(wǎng)絡(luò)表現(xiàn)出持續(xù)振蕩，如圖 2（d）和圖 2（g）所示。

圖1 二輸入邏輯門節(jié)點(diǎn)組成的自治布爾網(wǎng)絡(luò)

圖2 N分別為3～11時(shí)節(jié)點(diǎn)自治布爾網(wǎng)絡(luò)中xnor輸出電壓時(shí)序

2.2 布爾混沌的產(chǎn)生及動(dòng)力學(xué)行為

布爾混沌是由自治布爾網(wǎng)絡(luò)電路產(chǎn)生的一種幅值呈二值變化（邏輯高電平和邏輯低電平），觸發(fā)時(shí)間（相鄰2個(gè)上升沿的時(shí)間間隔）呈混沌變化的信號(hào)。其產(chǎn)生的動(dòng)力學(xué)原因是自治布爾網(wǎng)絡(luò)中電子邏輯器件固有的非理想特性，包括低通濾波效應(yīng)、退化效應(yīng)等[15-16]。

經(jīng)2.1節(jié)分析可知，所設(shè)計(jì)自治布爾網(wǎng)絡(luò)要保持振蕩狀態(tài)，其節(jié)點(diǎn)個(gè)數(shù)必須滿足N=3n（n為大于或等于 2的正整數(shù)）。本部分從最大李雅普諾夫指數(shù)與最小熵這2個(gè)方面進(jìn)一步分析了振蕩狀態(tài)下自治布爾網(wǎng)絡(luò)的動(dòng)力學(xué)特性。參照文獻(xiàn)[17]，計(jì)算了N≥6時(shí)自治布爾網(wǎng)絡(luò)輸出信號(hào)的最大李雅普諾夫指數(shù)（λmax）。如圖 3所示，λmax均大于 0，表明這些網(wǎng)絡(luò)均產(chǎn)生了布爾混沌信號(hào)[18-19]。進(jìn)一步研究發(fā)現(xiàn)，隨著節(jié)點(diǎn)數(shù)量N的增加，布爾混沌信號(hào)的最大李雅普諾夫指數(shù)也隨之增大，當(dāng)N≥12時(shí)，最大李雅普諾夫指數(shù)達(dá)到極大值，之后其變化趨勢(shì)逐漸平穩(wěn)；因此，為了產(chǎn)生高質(zhì)量的布爾混沌信號(hào)，應(yīng)選取N≥12的自治布爾網(wǎng)絡(luò)。同時(shí)，利用最小熵對(duì)所產(chǎn)生布爾混沌的隨機(jī)特性進(jìn)行了分析，最小熵接近于1則表明布爾混沌信號(hào)完全隨機(jī)且獨(dú)立同分布，適合作為 Physical-RNG的物理熵源。實(shí)驗(yàn)測(cè)量了N≥6時(shí)布爾混沌信號(hào)的最小熵，實(shí)驗(yàn)結(jié)果如圖 3所示。從圖中可觀察到，當(dāng)自治布爾網(wǎng)絡(luò)的節(jié)點(diǎn)數(shù)N≥15時(shí)，所產(chǎn)生的布爾混沌信號(hào)的最小熵趨近于1，之后趨勢(shì)逐漸平穩(wěn)，因此，作為 Physical-RNG的物理熵源，應(yīng)選取N≥15的自治布爾網(wǎng)絡(luò)。

圖3 自治布爾網(wǎng)絡(luò)（N≥6）的最大李雅普諾夫指數(shù)與最小熵

2.3 布爾混沌物理熵源特性

根據(jù)2.2節(jié)分析結(jié)果，同時(shí)考慮到自治布爾網(wǎng)絡(luò)的最優(yōu)功耗，選擇N= 15的自治布爾網(wǎng)絡(luò)作為Physical-RNG的熵源。熵源產(chǎn)生的布爾混沌信號(hào)的時(shí)序曲線、頻譜曲線和自相關(guān)曲線如圖4所示，從圖4（a）中可以看出，布爾混沌信號(hào)的電壓呈現(xiàn)大幅度隨機(jī)起伏（約2 V）；從圖4（b）中可以看出，布爾混沌信號(hào)的頻譜平坦且?guī)掃_(dá)680 MHz；從圖4（c）中可以看出，布爾混沌信號(hào)的自相關(guān)曲線的半高全寬（FWHM，full width at half maximum）約為1 ns。較寬的頻譜與較短的自相關(guān)時(shí)間表明可以從該物理熵源中提取高速物理隨機(jī)數(shù)序列。

圖4 自治布爾網(wǎng)絡(luò)（N=15）產(chǎn)生的布爾混沌信號(hào)特性

3 物理隨機(jī)數(shù)發(fā)生器

本文設(shè)計(jì)的基于布爾混沌的物理隨機(jī)數(shù)發(fā)生器結(jié)構(gòu)如圖5（a）所示，由兩部分構(gòu)成：物理熵源和熵提取電路。物理熵源以節(jié)點(diǎn)個(gè)數(shù)N=15的自治布爾網(wǎng)絡(luò)構(gòu)成，布爾混沌信號(hào)可以由其中任意節(jié)點(diǎn)輸出。熵提取電路由一個(gè)三輸入xor邏輯門和3個(gè)D觸發(fā)器構(gòu)成，其工作原理如下：由3個(gè)D觸發(fā)器對(duì)節(jié)點(diǎn)0、節(jié)點(diǎn)6和節(jié)點(diǎn)9輸出的混沌序列進(jìn)行采樣，所采樣樣本再經(jīng)異或處理以減少物理隨機(jī)數(shù)中的偏差和相關(guān)性，最終產(chǎn)生物理隨機(jī)數(shù)序列。

該P(yáng)hysical-RNG已在FPGA（芯片型號(hào)：Altera Cyclone IV FPGA，EP4CE10F17C8N）中進(jìn)行了實(shí)驗(yàn)驗(yàn)證，僅需16個(gè)邏輯單元（LE，logic element）即可實(shí)現(xiàn)，消耗資源極少。實(shí)驗(yàn)中，利用FPGA的PLL（phase locked loop）單元產(chǎn)生100 MHz信號(hào)作為D觸發(fā)器的時(shí)鐘，此時(shí)該P(yáng)hysical-RNG的隨機(jī)數(shù)實(shí)時(shí)產(chǎn)生速率為100 Mbit/s，圖5（b）為實(shí)時(shí)產(chǎn)生的隨機(jī)比特序列。值得一提的是，以目前中等規(guī)模FPGA芯片的容量及規(guī)模（如Cyclone V 的LE單元數(shù)量為3×105左右[20]），其內(nèi)部可以同時(shí)構(gòu)建數(shù)萬(wàn)個(gè)該P(yáng)hysical-RNG結(jié)構(gòu)，此時(shí)物理隨機(jī)數(shù)的實(shí)時(shí)產(chǎn)生速率可至太比特每秒量級(jí)，因此，本技術(shù)在海量隨機(jī)數(shù)應(yīng)用領(lǐng)域有著廣闊的發(fā)展前景。

圖5 實(shí)時(shí)速率為100 Mbit/s的物理隨機(jī)數(shù)發(fā)生器及產(chǎn)生的信號(hào)

4 隨機(jī)性測(cè)試

為了評(píng)估基于布爾混沌的 Physical-RNG產(chǎn)生隨機(jī)序列的隨機(jī)性，應(yīng)用了2種國(guó)際通用的隨機(jī)性測(cè)試檢驗(yàn)標(biāo)準(zhǔn)，分別為 NIST SP800-22[21]和DIEHARD[22]，測(cè)試的物理隨機(jī)數(shù)樣本量均為1 Gbit。NIST SP800-22由美國(guó)標(biāo)準(zhǔn)局發(fā)布，包含15項(xiàng)統(tǒng)計(jì)測(cè)試，每項(xiàng)測(cè)試均會(huì)針對(duì)測(cè)試本文數(shù)據(jù)生成一個(gè)P值，測(cè)試需要1 000組數(shù)據(jù)，每組數(shù)據(jù)為1 Mbit。DIEHARD由George Marsaglia發(fā)布，包括18項(xiàng)測(cè)試，其中少數(shù)測(cè)試重復(fù)不同的參數(shù)多次測(cè)試，每項(xiàng)測(cè)試均會(huì)生成一個(gè)P值，如果測(cè)試項(xiàng)有多個(gè)P值，則利用KS檢驗(yàn)生成一個(gè)綜合P值作為最終測(cè)試結(jié)果。在NIST SP800-22檢驗(yàn)標(biāo)準(zhǔn)的15項(xiàng)測(cè)試中，設(shè)置顯著水平值為α=0.01，當(dāng)P值大于0.000 1，通過(guò)P值百分比大于0.980 6時(shí)，則表示通過(guò)該項(xiàng)測(cè)試。在DIEHARD檢驗(yàn)標(biāo)準(zhǔn)的18項(xiàng)測(cè)試中，設(shè)置顯著水平值為α=0.01，當(dāng)每項(xiàng)測(cè)試的P值大于0.01且小于0.99時(shí)，則表示通過(guò)該項(xiàng)測(cè)試。2種檢驗(yàn)標(biāo)準(zhǔn)的測(cè)試結(jié)果分別如表1和表2所示，所測(cè)試的物理隨機(jī)數(shù)序列均通過(guò)NIST SP800-22及DIEHARD所有測(cè)試項(xiàng)，這表明該P(yáng)hysical-RNG產(chǎn)生的物理隨機(jī)序列具有良好的隨機(jī)統(tǒng)計(jì)特性。

表1 NIST SP800-22檢驗(yàn)標(biāo)準(zhǔn)測(cè)試結(jié)果

5 結(jié)束語(yǔ)

本文提出并實(shí)驗(yàn)驗(yàn)證了一種基于自治布爾網(wǎng)絡(luò)的寬帶物理混沌熵源，并基于該熵源構(gòu)建了實(shí)時(shí)速率為100 Mbit/s 的物理隨機(jī)數(shù)發(fā)生器。隨機(jī)性檢測(cè)結(jié)果表明，物理隨機(jī)數(shù)發(fā)生器產(chǎn)生的隨機(jī)數(shù)序列可以通過(guò)NIST SP800-22檢驗(yàn)標(biāo)準(zhǔn)和DIEHARD檢驗(yàn)標(biāo)準(zhǔn)，具有良好的隨機(jī)統(tǒng)計(jì)特性。此外，值得一提的是，基于該熵源設(shè)計(jì)技術(shù)，可以在FPGA中構(gòu)建出速率更高的隨機(jī)數(shù)發(fā)生器；這是由于該熵源僅需 16個(gè) LE即可實(shí)現(xiàn)；因此在

表2 DIEHARD檢驗(yàn)標(biāo)準(zhǔn)測(cè)試結(jié)果

FPGA中可以大規(guī)模部署，達(dá)到多熵源并行產(chǎn)生高速隨機(jī)數(shù)的效果。以目前Altera公司中低端FPGA

芯片Cyclone V 為例，其LE單元數(shù)量在3×105左右，因此可以在芯片內(nèi)部同時(shí)構(gòu)建數(shù)萬(wàn)個(gè)本文提出的物理熵源，實(shí)現(xiàn)太比特每秒量級(jí)的高速物理隨機(jī)數(shù)實(shí)時(shí)在線產(chǎn)生。未來(lái)，本技術(shù)在高速隨機(jī)數(shù)發(fā)生器應(yīng)用領(lǐng)域?qū)⒂兄鴱V闊的發(fā)展前景。