基于振蕩器采樣法的隨機(jī)數(shù)發(fā)生器設(shè)計(jì)
本文引用地址:http://m.butianyuan.cn/article/190678.htm
偏差糾正器
振蕩器采樣法的工作基于這樣一個(gè)事實(shí),即高頻振蕩器一直保持50%的占空比,而低頻振蕩器每個(gè)周期都有明顯變化。如果情況不是這樣(盡管絕大部分情況下是這樣),所獲得的位碼便會(huì)出現(xiàn)偏差,既可能是“1”,也可能是“0”,這稱為偏移。幸運(yùn)的是我們可以采取有效的后處理方法來糾正偏差,以一種確定的方式產(chǎn)生分布更均勻的位流。其中兩種最簡單的技術(shù)分別稱為奇偶生成和轉(zhuǎn)換映射,此外還有一些較復(fù)雜的偏差糾正方法,包括使用快速傅利葉變換函數(shù)和更復(fù)雜的位混排技術(shù),它們通常采用延遲元件和反饋通路組合來去除位與位之間的相關(guān)性。
偏差糾正的目標(biāo)是對位流進(jìn)行均衡分配,以便以相同的概率產(chǎn)生“1”和“0”,其做法基本上是從有偏差的位序列中提取出更隨機(jī)的數(shù)值。這種后處理功能并非振蕩器采樣技術(shù)所獨(dú)有,其應(yīng)用對原始噪聲源沒有要求,要實(shí)現(xiàn)這種功能也并不復(fù)雜。一種簡單方法是奇偶生成,它具有魯棒性強(qiáng)的優(yōu)點(diǎn),可用于更大范圍的偏差分布。用硬件來實(shí)現(xiàn)固定長度位采樣序列一般非常簡單,例如簡單的級聯(lián)XOR鏈便可有效用作一個(gè)奇偶生成器并完成適當(dāng)?shù)钠罴m正(圖5)。
轉(zhuǎn)換映射也叫做馮·諾依曼糾正器,它將一對采樣輸入位轉(zhuǎn)換成一個(gè)輸出位,例如把輸入對[0,1]轉(zhuǎn)換成1,把[1,0]轉(zhuǎn)換成0,而在輸入為[0,0]或[1,1]時(shí)什么也不輸出。這種技術(shù)可以完全消除偏差,但其代價(jià)是必須在輸入位之間創(chuàng)建一個(gè)不定量的延遲,并產(chǎn)生一個(gè)輸出位長的任意數(shù)。
混合函數(shù)
即使采用了所有上述技術(shù),仍然存在這樣一些擔(dān)憂,即由于存在多種非隨機(jī)數(shù)據(jù)源(如前面提及的多個(gè)振蕩器源組合),系統(tǒng)固有的隨機(jī)性可能受到影響。采用功能強(qiáng)大的混合函數(shù)可以確保隨機(jī)源的隨機(jī)性,這些函數(shù)將兩個(gè)或更多采樣位進(jìn)行組合,然后產(chǎn)生一個(gè)輸出位,該輸出位是先前各輸入位的復(fù)雜非線性函數(shù)。當(dāng)然,這樣獲得的輸出隨機(jī)位數(shù)不可能多于輸入位數(shù)。對這個(gè)函數(shù)期望的功能是任何輸入位的改變都會(huì)引起大約一半輸出位的改變,這些混合函數(shù)也可作為更復(fù)雜的糾偏方法去除位流偏差,如同前面討論的那樣。
一般情況下,混合函數(shù)功能越強(qiáng),它所占用的芯片面積也越大,前面提到的級聯(lián)XOR便是很簡單的一例。DES加密/解密算法則是更為復(fù)雜的例子,因?yàn)樗枰?20個(gè)輸入位,產(chǎn)生64個(gè)輸出位,每一個(gè)輸出位都依賴一個(gè)涉及所有輸入位的復(fù)雜非線性函數(shù),其它加密/解密算法的工作方式也類似?;炫藕瘮?shù)也可用作強(qiáng)大的混合函數(shù),它們使用任意長度的輸入位,并產(chǎn)生一定長度的信息摘要。同樣,設(shè)計(jì)工程師需要進(jìn)行權(quán)衡,要在額外開銷與所生成的位流無法達(dá)到期望隨機(jī)度之間做選擇。
統(tǒng)計(jì)評估
美國商業(yè)部創(chuàng)建了多種用來評估加密應(yīng)用中隨機(jī)數(shù)發(fā)生器隨機(jī)程度的標(biāo)準(zhǔn),美國國家標(biāo)準(zhǔn)技術(shù)研究所(NIST)出版的“800-22特刊”推薦了一種全面的隨機(jī)數(shù)發(fā)生器統(tǒng)計(jì)測試方法,并嚴(yán)格規(guī)定了滿足各種程度隨機(jī)性的衡量標(biāo)準(zhǔn)。測試工程師可在驗(yàn)證過程中使用這種測試方法或其它類似測試,檢驗(yàn)設(shè)計(jì)是否具有非隨機(jī)特征,從而判斷是否達(dá)到了某種程度的隨機(jī)性。NIST統(tǒng)計(jì)測試套件中規(guī)定了16種不同類型的測試,以便能發(fā)現(xiàn)被測隨機(jī)數(shù)發(fā)生器的缺陷。
NIST FIPS 140-2是美國商業(yè)部頒發(fā)的另一份文件,它定義了設(shè)計(jì)者在安全應(yīng)用中采用加密設(shè)備時(shí)必須遵守的一系列要求。其中一個(gè)最重要的要求是任何使用隨機(jī)數(shù)發(fā)生器的實(shí)時(shí)加密模塊必須提供加電能力并可對RNG功能進(jìn)行持續(xù)的實(shí)時(shí)測試,確保它在工作過程中不出現(xiàn)故障,如果在規(guī)定的統(tǒng)計(jì)測試中出現(xiàn)任何失敗,RNG模塊都必須進(jìn)入一種錯(cuò)誤狀態(tài)。對于SoC設(shè)計(jì)來說,這意味著如果最終產(chǎn)品希望獲得美國政府安全標(biāo)準(zhǔn)許可的話,那么進(jìn)行測試的測試器模塊必須集成在設(shè)備本身之中并滿足規(guī)定的要求。
某些產(chǎn)生非確定性噪聲源的技術(shù)也許并不適用,這取決于是使用標(biāo)準(zhǔn)單元設(shè)計(jì)還是使用客戶定制布局設(shè)計(jì)。的確可以保證一項(xiàng)設(shè)計(jì)達(dá)到期望的隨機(jī)度,但這種保證的代價(jià)是增加芯片尺寸以便實(shí)現(xiàn)冗余結(jié)構(gòu)或更為復(fù)雜的后處理功能。即便是精心規(guī)劃的設(shè)計(jì),最后階段也必須通過統(tǒng)計(jì)測試套件的驗(yàn)證,只有這樣才能說設(shè)計(jì)達(dá)到了期望的隨機(jī)度。
評論