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

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

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

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


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

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


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


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


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


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


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


  從表2可以看到,在硬件上以極低的邏輯資源使用(18個(gè)Slices約合1800+門(mén))實(shí)現(xiàn)了本文提出的混沌RNG方案,對(duì)比參考文獻(xiàn)[2]中的方案(3000+門(mén)),該電路得到大大簡(jiǎn)化,而參考文獻(xiàn)[2]中的偽高斯噪聲生成器占用了很大的硬件資源。該方案的最高輸出速率受到了板載最高時(shí)鐘頻率的限制。如果本文的混沌RNG用IC方案實(shí)現(xiàn),則可以進(jìn)一步減小所需要的硬件資源并進(jìn)一步提高輸出速率。
  本文提出的方案通過(guò)了一系列高要求的隨機(jī)性測(cè)試,其邏輯資源的占用遠(yuǎn)小于傳統(tǒng)的混沌RNG方案,最高輸出速率可達(dá)8Mbps。因而這種RNG方案可以用于對(duì)安全性和性能需求日益增長(zhǎng)的加密系統(tǒng)中。
參考文獻(xiàn)
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)站贊同其觀(guān)點(diǎn)。轉(zhuǎn)載的所有的文章、圖片、音/視頻文件等資料的版權(quán)歸版權(quán)所有權(quán)人所有。本站采用的非本站原創(chuàng)文章及圖片等內(nèi)容無(wú)法一一聯(lián)系確認(rèn)版權(quán)者。如涉及作品內(nèi)容、版權(quán)和其它問(wèn)題,請(qǐng)及時(shí)通過(guò)電子郵件或電話(huà)通知我們,以便迅速采取適當(dāng)措施,避免給雙方造成不必要的經(jīng)濟(jì)損失。聯(lián)系電話(huà):010-82306118;郵箱:aet@chinaaet.com。