《電子技術(shù)應(yīng)用》
您所在的位置:首頁 > 可編程邏輯 > 業(yè)界動態(tài) > 一種新的混沌隨機數(shù)生成器實現(xiàn)方案

一種新的混沌隨機數(shù)生成器實現(xiàn)方案

2008-04-25
作者:胡 濤,,郭 立,黃 昊,劉

  摘 要: 提出了一種基于時鐘相位抖動的混沌隨機數(shù)" title="隨機數(shù)">隨機數(shù)產(chǎn)生器" title="產(chǎn)生器">產(chǎn)生器,,并在Xilinx FPGA開發(fā)板上實現(xiàn)并進行了測試。測試結(jié)果" title="測試結(jié)果">測試結(jié)果表明,,最高輸出速率達8Mbps,,實現(xiàn)了設(shè)計要求。硬件結(jié)構(gòu)簡單,,并且該RNG的輸入源不受電路噪聲源的影響,,易于今后的IC實現(xiàn)。
  關(guān)鍵詞: 混沌隨機數(shù)產(chǎn)生器 真隨機數(shù) 隨機性測試


  隨著計算機網(wǎng)絡(luò),、Internet和無線設(shè)備等數(shù)字通信技術(shù)的廣泛應(yīng)用,,數(shù)據(jù)加密越來越成為人們關(guān)注的焦點。很多加密系統(tǒng)的安全性直接依賴于產(chǎn)生的密鑰的不可預(yù)測性以及非相關(guān)性,。然而要產(chǎn)生一個理想的密鑰,,僅僅由人來輸入一個密碼是無法達到要求的。因為那樣會有太強的主觀性,。要生成非主觀的密鑰,,目前常用的方法是偽隨機數(shù)產(chǎn)生器PRNG(Pseudorandom Number Generator)。但再好的PRNG只要其中一個狀態(tài)因為某種原因泄漏,,就極有可能導致整個PRNG的產(chǎn)生機制被破解,,從而使得“偽隨機”變成“不隨機”。因此人們開始研究真隨機數(shù)生成器,。有些隨機數(shù)產(chǎn)生器是基于一個模糊的類隨機源的,,如鍵盤的延遲,電腦的系統(tǒng)時鐘狀態(tài)等。這些隨機數(shù)產(chǎn)生器的安全性總是受這種模糊的類隨機源的影響,。于是采用自然界中的真隨機量產(chǎn)生密鑰便成為一個新的課題,。例如電路中的熱噪聲或者放射源的衰變等都是真隨機量。在SoC(System on Chip)廣泛應(yīng)用的今天,,如何設(shè)計一個基于IC的RNG就成為安全通信應(yīng)用的急切需要,。隨機噪聲源(如熱噪聲和發(fā)射噪聲)存在于IC中卻總是被人為地屏蔽掉了。因此,,利用電路噪聲放大的商用RNG設(shè)計需要專門的外部組件和特殊硬件來與那些需要屏蔽噪聲的組件隔開,。在IC設(shè)計中,對數(shù)?;旌闲盘柕奶幚斫?jīng)驗表明,,底層噪聲和電源噪聲電平總是高于隨機噪聲源電平。所以一個不被干擾的白噪聲源在一個基于IC的數(shù)字加解密系統(tǒng)的RNG中是不可能被使用的,,必須考慮如何利用抗干擾的隨機源來實現(xiàn)隨機數(shù)生成器,。
  本文提出一種新的混沌RNG的實現(xiàn)方案,更易于用硬件即IC實現(xiàn),。首先討論其原理和模型及其實驗,,并對其進行隨機性測試;然后討論它的FPGA實現(xiàn)方案,。
1 模型及實驗
1.1 隨機數(shù)生成器的定義

  定義1 一個理想的隨機數(shù)生成器是一個生成等概率符號的離散無記憶信息源(DMIS),, RNG是一個有著正熵的離散信息源[1]
  但是,,現(xiàn)實中的RNG都是產(chǎn)生非均勻概率符號的離散有記憶信息源,。因此采用有偏差的RNG來區(qū)別于定義1中理想的RNG。一個有偏差的RNG性能的好壞可通過它的冗余度" title="冗余度">冗余度ρ=log2Q-h來衡量,,其中Q和h分別是離散符號集的基數(shù)和相關(guān)信源的熵,。一個理想RNG的冗余度應(yīng)該等于0,而一個有偏差的RNG的冗余度則標志這個RNG跟理想RNG的差距,。例如一個冗余度為ρ的RNG產(chǎn)生長度為N位的密鑰,,則攻擊方平均要嘗試2(1-ρ)N個密鑰才能找到正確的密鑰,因此密鑰的有效長度可以被定義為Ne=(1-ρ)N,。
1.2 混沌隨機數(shù)生成器模型
  混沌理論作為非線性動態(tài)系統(tǒng)的分支,,近年來受到越來越多的關(guān)注。它使得一個低維動態(tài)系統(tǒng)也可以擁有復(fù)雜的,、不可預(yù)料的行為,,使復(fù)雜的方程不再是生成隨機數(shù)序列的必要條件[1]
  混沌系統(tǒng)可以用基于下列迭代關(guān)系式描述的Bernouli移位映射[2]
  Xn=[2(Xn-1+e(n))]mod 1.0 (1)
  式中,,e(n)表示一個高斯" title="高斯">高斯噪聲信號,。這個迭代式表明由(1)式產(chǎn)生的序列是極為平滑和均一分布的[3],。另外,與混沌相關(guān)的軌跡發(fā)散包含了噪聲,,(1)式產(chǎn)生的序列在一定范圍內(nèi)是不可預(yù)測的,,從而使系統(tǒng)能被當作一個真隨機比特源。離散時間混沌法不受其他噪聲源影響[3],。
  在電路上實現(xiàn)Bernouli移位映射的關(guān)鍵在于實現(xiàn)一個抗干擾的高斯噪聲信號,。傳統(tǒng)的混沌隨機數(shù)生成器是用一個偽隨機數(shù)生成器產(chǎn)生一個偽高斯噪聲信號來實現(xiàn)(1)中的e(n)[2],如圖1所示,,這在一定程度上降低了混沌隨機數(shù)生成器的安全性和真隨機性。


  典型的振蕩器采樣法[5]是利用時鐘的相位噪聲(理論上是MOSFET熱噪聲的副產(chǎn)品)產(chǎn)生隨機數(shù),。通過一個由較慢時鐘信號控制的D觸發(fā)器對一個高速時鐘進行采樣,,高速時鐘的相位抖動導致具體采樣值的不確定性,如圖2所示,,理論上每次采樣都會產(chǎn)生一個隨機比特,。典型采樣后的抖動電平是符合高斯分布的[4],而且這種抖動不會受到電路中其他噪聲的干擾[5],。另外,,振蕩器采樣法的隨機性可以通過仔細挑選快的和慢的時鐘頻率比來人為增強。采樣時發(fā)生的非線性偏移現(xiàn)象使得這種振蕩器采樣技術(shù)比目前的確定性噪聲更健壯,。


  基于上述原理,,提出用振蕩器采樣輸出作為一個高斯噪聲信號e(n)實現(xiàn)(1)式。結(jié)合兩種隨機數(shù)生成器方案實現(xiàn)混沌隨機數(shù)生成器,,系統(tǒng)原理框圖如圖3所示,。


  其中S/H(Shift/Hold)為一個移位保持電路,用來實現(xiàn)2(x(n-1)+e(n)),。低速時鐘控制D觸發(fā)器,、寄存器和S/H。寄存器中殘余信號作為初始輸入信號,,然后與振蕩器采樣輸出信號進行模2加操作(異或),,再通過S/H產(chǎn)生最后的輸出x(n),x(n)被反饋到寄存器中進行下次操作,。
1.3 實驗結(jié)果及討論
  根據(jù)前面的定義1來檢測本文中提出的混沌RNG的性能,,用它生成不同長度的8bit隨機數(shù)序列,計算其冗余度,,并與參考文獻[2]中的傳統(tǒng)混沌RNG方案做對比,,如圖4所示,點線表示本文提出的方案,,實線表示的是文獻[2]中的方案,。通過對比可以很明顯地看出改進后的混沌RNG性能優(yōu)于采用偽隨機高斯噪聲的傳統(tǒng)混沌RNG方案。
  僅僅由冗余度來衡量一個RNG是不夠的。為了了解本文提出的混沌RNG輸出序列的隨機性是否實現(xiàn)了“隨機”,,我們根據(jù)美國國家標準及技術(shù)研究所(NIST)的要求[6]對本文的混沌RNG方案產(chǎn)生的隨機數(shù)序列的隨機性進行一系列測試,。測試所用數(shù)據(jù)為慢速時鐘=8kHz,高速時鐘=100MHz,,輸出精度為8bit的輸出值,,測試長度為3 000 000個8位隨機數(shù)的序列,表1為測試結(jié)果,。


  經(jīng)過以上一系列的隨機性測試,,RNG表現(xiàn)良好,在置信水平為95%的情況下通過了全部測試,,沒有表現(xiàn)出非隨機性,,并且在信源相關(guān)度的測試(correlation order test)中性能超過了參考文獻[2]中的混沌RNG方案。這項測試是測試一個隨機數(shù)序列的相鄰隨機數(shù)的相關(guān)度,。一個理想RNG的前后隨機數(shù)相關(guān)度應(yīng)該為0,。由表1中數(shù)據(jù)可知,本文的混沌RNG測試結(jié)果更接近于理想RNG,。因此可以認為,,就目前已知的測試隨機數(shù)的隨機性的測試結(jié)果表明,本文介紹的混沌RNG生成的隨機數(shù)序列是比較好的,。
  光譜測試可以直觀地顯示出隨機數(shù)序列與其自身的相關(guān)情況,。通過圖5可以更直觀地看到一個相關(guān)度低的RNG與一個偽RNG(用10位線性反饋移位寄存器來做例子)的對比。相關(guān)度為0的理想RNG應(yīng)該均勻分布在整個二維空間內(nèi),,線性反饋移位寄存器的測試結(jié)果(圖b)就反映出了它的高相關(guān)度,,而本文提出的混沌RNG方案的測試結(jié)果(圖a)則顯示了其不可預(yù)測性與無規(guī)則性分布。


2 硬件實現(xiàn)
  本文采用Xilinx公司的XUPV2P30開發(fā)板實現(xiàn)這個混沌RNG,,這塊開發(fā)板上自帶兩個獨立的(不同相位)時鐘源,,二者都可以輸出8k~100MHz的不同頻率的時鐘。選擇慢速時鐘信號頻率范圍為8k~1MHz,,高速時鐘信號頻率為100MHz,,輸出精度為8bit。其邏輯使用資源情況如表2所示,。


  從表2可以看到,,在硬件上以極低的邏輯資源使用(18個Slices約合1800+門)實現(xiàn)了本文提出的混沌RNG方案,對比參考文獻[2]中的方案(3000+門),,該電路得到大大簡化,,而參考文獻[2]中的偽高斯噪聲生成器占用了很大的硬件資源。該方案的最高輸出速率受到了板載最高時鐘頻率的限制,。如果本文的混沌RNG用IC方案實現(xiàn),,則可以進一步減小所需要的硬件資源并進一步提高輸出速率,。
  本文提出的方案通過了一系列高要求的隨機性測試,其邏輯資源的占用遠小于傳統(tǒng)的混沌RNG方案,,最高輸出速率可達8Mbps,。因而這種RNG方案可以用于對安全性和性能需求日益增長的加密系統(tǒng)中。
參考文獻
1 Stojanovski T,,Kocarev L.Chaos-based random number generators-part I.IEEE Transactions on Circuits and Systems,,2001;(3):281~288
2 Petrie C S,,Connelly J A.A noise-based IC random number generator for applications in cryptography.IEEE Trans.Circuits Syst,,2000;47(5):615~621
3 Chua L O,,Yao Y,,Yang Q.Generating randomness from chaos and constructing chaos with desired randomness.Int J Circuit Theory Appl,1990,;18:215~240
4 Paul S.Little known characteristics of phase noise.Applications Note AN-741,Analog Devices,,www.analog.com
5 Petrie C S,,Connelly J A.Modeling and simulation of oscillator-based random number generators.In:Proc.ISCAS′96,vol.4,,May 1996:324~327
6 National Institute of Standards and Technology,,Kanata,ONT,,Canada.Security requirements for cryptographic modules.FIPS PUB 140-2,,Dec 2002

本站內(nèi)容除特別聲明的原創(chuàng)文章之外,轉(zhuǎn)載內(nèi)容只為傳遞更多信息,,并不代表本網(wǎng)站贊同其觀點,。轉(zhuǎn)載的所有的文章、圖片,、音/視頻文件等資料的版權(quán)歸版權(quán)所有權(quán)人所有,。本站采用的非本站原創(chuàng)文章及圖片等內(nèi)容無法一一聯(lián)系確認版權(quán)者。如涉及作品內(nèi)容,、版權(quán)和其它問題,,請及時通過電子郵件或電話通知我們,以便迅速采取適當措施,,避免給雙方造成不必要的經(jīng)濟損失,。聯(lián)系電話:010-82306118;郵箱:[email protected],。