基于振蕩器采樣法的隨機數發(fā)生器設計

偏差糾正器

振蕩器采樣法的工作基于這樣一個(gè)事實(shí)，即高頻振蕩器一直保持50%的占空比，而低頻振蕩器每個(gè)周期都有明顯變化。如果情況不是這樣(盡管絕大部分情況下是這樣)，所獲得的位碼便會(huì )出現偏差，既可能是“1”，也可能是“0”，這稱(chēng)為偏移。幸運的是我們可以采取有效的后處理方法來(lái)糾正偏差，以一種確定的方式產(chǎn)生分布更均勻的位流。其中兩種最簡(jiǎn)單的技術(shù)分別稱(chēng)為奇偶生成和轉換映射，此外還有一些較復雜的偏差糾正方法，包括使用快速傅利葉變換函數和更復雜的位混排技術(shù)，它們通常采用延遲元件和反饋通路組合來(lái)去除位與位之間的相關(guān)性。

偏差糾正的目標是對位流進(jìn)行均衡分配，以便以相同的概率產(chǎn)生“1”和“0”，其做法基本上是從有偏差的位序列中提取出更隨機的數值。這種后處理功能并非振蕩器采樣技術(shù)所獨有，其應用對原始噪聲源沒(méi)有要求，要實(shí)現這種功能也并不復雜。一種簡(jiǎn)單方法是奇偶生成，它具有魯棒性強的優(yōu)點(diǎn)，可用于更大范圍的偏差分布。用硬件來(lái)實(shí)現固定長(cháng)度位采樣序列一般非常簡(jiǎn)單，例如簡(jiǎn)單的級聯(lián)XOR鏈便可有效用作一個(gè)奇偶生成器并完成適當的偏差糾正(圖5)。

轉換映射也叫做馮·諾依曼糾正器，它將一對采樣輸入位轉換成一個(gè)輸出位，例如把輸入對[0，1]轉換成1，把[1，0]轉換成0，而在輸入為[0，0]或[1，1]時(shí)什么也不輸出。這種技術(shù)可以完全消除偏差，但其代價(jià)是必須在輸入位之間創(chuàng )建一個(gè)不定量的延遲，并產(chǎn)生一個(gè)輸出位長(cháng)的任意數。

混合函數

即使采用了所有上述技術(shù)，仍然存在這樣一些擔憂(yōu)，即由于存在多種非隨機數據源(如前面提及的多個(gè)振蕩器源組合)，系統固有的隨機性可能受到影響。采用功能強大的混合函數可以確保隨機源的隨機性，這些函數將兩個(gè)或更多采樣位進(jìn)行組合，然后產(chǎn)生一個(gè)輸出位，該輸出位是先前各輸入位的復雜非線(xiàn)性函數。當然，這樣獲得的輸出隨機位數不可能多于輸入位數。對這個(gè)函數期望的功能是任何輸入位的改變都會(huì )引起大約一半輸出位的改變，這些混合函數也可作為更復雜的糾偏方法去除位流偏差，如同前面討論的那樣。

一般情況下，混合函數功能越強，它所占用的芯片面積也越大，前面提到的級聯(lián)XOR便是很簡(jiǎn)單的一例。DES加密/解密算法則是更為復雜的例子，因為它需要120個(gè)輸入位，產(chǎn)生64個(gè)輸出位，每一個(gè)輸出位都依賴(lài)一個(gè)涉及所有輸入位的復雜非線(xiàn)性函數，其它加密/解密算法的工作方式也類(lèi)似?；炫藕瘮狄部捎米鲝姶蟮幕旌虾瘮?，它們使用任意長(cháng)度的輸入位，并產(chǎn)生一定長(cháng)度的信息摘要。同樣，設計工程師需要進(jìn)行權衡，要在額外開(kāi)銷(xiāo)與所生成的位流無(wú)法達到期望隨機度之間做選擇。

統計評估

美國商業(yè)部創(chuàng )建了多種用來(lái)評估加密應用中隨機數發(fā)生器隨機程度的標準，美國國家標準技術(shù)研究所(NIST)出版的“800-22特刊”推薦了一種全面的隨機數發(fā)生器統計測試方法，并嚴格規定了滿(mǎn)足各種程度隨機性的衡量標準。測試工程師可在驗證過(guò)程中使用這種測試方法或其它類(lèi)似測試，檢驗設計是否具有非隨機特征，從而判斷是否達到了某種程度的隨機性。NIST統計測試套件中規定了16種不同類(lèi)型的測試，以便能發(fā)現被測隨機數發(fā)生器的缺陷。

NIST FIPS 140-2是美國商業(yè)部頒發(fā)的另一份文件，它定義了設計者在安全應用中采用加密設備時(shí)必須遵守的一系列要求。其中一個(gè)最重要的要求是任何使用隨機數發(fā)生器的實(shí)時(shí)加密模塊必須提供加電能力并可對RNG功能進(jìn)行持續的實(shí)時(shí)測試，確保它在工作過(guò)程中不出現故障，如果在規定的統計測試中出現任何失敗，RNG模塊都必須進(jìn)入一種錯誤狀態(tài)。對于SoC設計來(lái)說(shuō)，這意味著(zhù)如果最終產(chǎn)品希望獲得美國政府安全標準許可的話(huà)，那么進(jìn)行測試的測試器模塊必須集成在設備本身之中并滿(mǎn)足規定的要求。

某些產(chǎn)生非確定性噪聲源的技術(shù)也許并不適用，這取決于是使用標準單元設計還是使用客戶(hù)定制布局設計。的確可以保證一項設計達到期望的隨機度，但這種保證的代價(jià)是增加芯片尺寸以便實(shí)現冗余結構或更為復雜的后處理功能。即便是精心規劃的設計，最后階段也必須通過(guò)統計測試套件的驗證，只有這樣才能說(shuō)設計達到了期望的隨機度。