ay: block;">
在保障互聯(lián)網(wǎng)安全的各種加密算法中,隨機數(shù)產(chǎn)生至關(guān)重要。產(chǎn)生隨機數(shù)的方法有多種,其中振蕩器采樣法最適于構(gòu)建SoC設(shè)計所需的隨機數(shù)發(fā)生器。本文介紹振蕩器采樣法的工作原理,并概述在具體使用這種振蕩器時應(yīng)注意的事項。
隨著許多企業(yè)的網(wǎng)絡(luò)應(yīng)用從內(nèi)部網(wǎng)擴展到公眾互聯(lián)網(wǎng),對虛擬專用網(wǎng)絡(luò)(VPN)設(shè)備的需求也開始逐漸上升。為了服務(wù)于這個市場,半導體廠商推出了一些專用產(chǎn)品,把所有必需安全功能都集成在一個器件里面。
專用于互聯(lián)網(wǎng)協(xié)議安全(IPsec)的AES和3DES類加密/解密算法以及SHA1和MD5等散列算法已廣為人知并得到普遍重視,然而,保證VPN系統(tǒng)安全的關(guān)鍵在于生成隨機數(shù)的能力,但這點卻常常被忽視。
隨機數(shù)是許多加密應(yīng)用的基礎(chǔ),其作用是生成Diffie-Hellman、Rivest-Shamir-Adelman和數(shù)字簽名等算法所需的公共/專用密鑰對,并為大批量加密算法和IPsec分別生成初始向量和即時隨機數(shù),此外,大量其它類型的安全協(xié)議也靠隨機數(shù)發(fā)生器的不可預(yù)測性來防止系統(tǒng)被破解。常用一些復雜數(shù)學函數(shù)生成高質(zhì)量偽隨機數(shù)發(fā)生器(PRNG)位流,但事實證明有很多途徑可以攻擊用PRNG加密的系統(tǒng),因此加密安全系統(tǒng)需要使用更高質(zhì)量的隨機數(shù)發(fā)生器。
在明確了這些需求之后,到底有沒有一種真正的隨機數(shù)發(fā)生器可以根據(jù)非確定噪聲源產(chǎn)生隨機數(shù),并特別適用于系統(tǒng)級芯片(SoC)設(shè)計呢？大多數(shù)隨機數(shù)發(fā)生器方案通常可以歸為三大類,即直接放大、離散時間混沌和振蕩器采樣。前兩種方法更適用于客戶定制的單元設(shè)計,因為在這些場合設(shè)計人員可以控制實際電路的布局；而振蕩器采樣技術(shù)可以作為標準單元設(shè)計流程的一部分,因此在SoC設(shè)計中很流行。不過設(shè)計人員即使選用了振蕩器技術(shù),仍然有許多實施問題需要仔細考慮。
隨機數(shù)生成技術(shù)
直接放大技術(shù)使用高增益高帶寬放大器來處理由熱噪聲或散射噪聲引起的電壓變化。例如可采用N阱電阻對將其熱噪聲轉(zhuǎn)換成一個電壓變化信號,然后以抖動的形式輸入隨機數(shù)發(fā)生器模塊微系統(tǒng)中(圖1)。采用這種方法時設(shè)計人員必須要考慮其它一些因素,如系統(tǒng)熱噪聲通常與基底噪聲及電源電壓波動等局部特征耦合在一起,如果電路沒有正確屏蔽,這些因素便會使熱噪聲源的隨機性受到影響。克服這種現(xiàn)象的方法是對一對鄰近的電阻進行采樣,再對結(jié)果求差以減少其它噪聲源的影響。
離散時間混沌法使用模擬信號處理技術(shù)產(chǎn)生隨機位流。這種方式下,隨機性不是從熱噪聲源獲得,而是從非常穩(wěn)定的動態(tài)變化中得到,其系統(tǒng)設(shè)計與模/數(shù)轉(zhuǎn)換器性質(zhì)類似。在傳統(tǒng)的A/D轉(zhuǎn)換器中,殘余信號經(jīng)過采樣和保持,再饋送到A/D轉(zhuǎn)換器的輸入端(圖2)。一般來說,單是這種技術(shù)本身尚不足以產(chǎn)生隨機序列,因為電路的不準確性限制了A/D轉(zhuǎn)換分辨率,也降低了系統(tǒng)產(chǎn)生隨機序列的能力。因此,為獲得非確定隨機性,這種技術(shù)常常要與其它技術(shù)配合使用。
目前,隨機數(shù)發(fā)生器(RNG)設(shè)計中最流行的方法是振蕩器采樣法(圖3),其基本設(shè)計思想是利用兩個獨立工作的高、低頻振蕩器之間的相對關(guān)系來得到非確定噪聲源,用高抖動低頻振蕩器采樣高頻振蕩器,從而產(chǎn)生隨機數(shù)序列。在數(shù)字電路中,低頻方波源可作為一個正沿觸發(fā)D觸發(fā)器的時鐘,高頻方波源則作為觸發(fā)器的數(shù)據(jù)輸入,并在時鐘脈沖的上升沿對其進行采樣。
在該系統(tǒng)中,產(chǎn)生隨機數(shù)的關(guān)鍵元件是低頻振蕩器,因為它的設(shè)計具有頻率不穩(wěn)定性,即抖動,而且低頻與高頻之比經(jīng)過仔細選擇可以符合一定條件。設(shè)計中最重要的是低頻振蕩器的抖動量,這個抖動就是隨機源。頻率不穩(wěn)定性可以是此類振蕩器的一個功能,也可由另一個非確定噪聲源直接“植入”,因此可以說,正是采樣時鐘相對于高頻數(shù)據(jù)輸入的相位變化保證了可以獲得隨機位流。
如果兩個振蕩器在工作過程中都不發(fā)生漂移,那么采樣得到的位流便具有周期性而且可以預(yù)測,這種周期性和通常稱為節(jié)拍頻率的頻率比有關(guān)。此外,兩個振蕩器的頻率比對所產(chǎn)生的位流有著非常重要的影響。多項研究表明,為了保證高度隨機性,低頻振蕩器周期變化標準差的兩倍與高頻振蕩器周期之比應(yīng)該大于3:2,否則位碼之間便會存在明顯的相關(guān)性,以致于后面的位將比其前面的位更容易預(yù)測。
使用振蕩器采樣法
選用振蕩器采樣法來設(shè)計隨機數(shù)發(fā)生器的設(shè)計人員還必須考慮其它一些實施問題,所選振蕩器的類型也會影響整個系統(tǒng)設(shè)計的固有隨機性。此外,為了保證相關(guān)噪聲源不會降低系統(tǒng)隨機性,必須仔細選擇振蕩器,這必然又會增加器件電路布局的復雜性。作為一種補償,可采用數(shù)字后處理技術(shù)來降低設(shè)計風險并保留系統(tǒng)的隨機性。
在考慮實施振蕩器采樣法時,設(shè)計人員可從幾種不同類型的振蕩器中進行選擇,包括差分振蕩器、單端振蕩器及混合振蕩器,不同類型振蕩器對不同噪聲源的敏感度也不一樣。顯而易見,不同振蕩器的特性比較需要豐富的知識,本文在此只作簡單討論。
通常,差分振蕩器對電源及基底噪聲的敏感度不如單端振蕩器。這是因為差分放大器對的電源和接地點會同時出現(xiàn)電壓擺動,所以兩個輸入之間的差值保持一致,輸出也一致,呈現(xiàn)出較高的共模抑制比(CMRR)。差分邏輯常用于模擬邏輯壓控振蕩器設(shè)計中,例如鎖相環(huán)中的振蕩器,因為鎖相環(huán)需要較高的CMRR,所以差分振蕩器方案并不特別適用于那些需要非確定噪聲源的設(shè)計。另一方面,單端反相振蕩器極易受電壓擺動或輸入信號中直流分量的影響,如果噪聲對電平帶來任何波動,都會影響振蕩器的抖動。此外,差分、感容及張弛振蕩器設(shè)計需要客戶定制的電路布局,所以無法集成到標準單元的SoC設(shè)計中。因此,在SoC設(shè)計中最簡單直接的解決方案通常是單端環(huán)形振蕩器(圖4)。
盡管單端環(huán)形振蕩器有這樣的優(yōu)勢,在選用時還是有一些復雜因素必須考慮。由于高速數(shù)字系統(tǒng)存在切換動作,因此熱噪聲與電源/基底噪聲相比一般可以忽略不計。電源和基底噪聲是引起噪聲耦合的主要原因,噪聲耦合的振蕩器在反相電路中會產(chǎn)生δ延遲。電源電壓變化或來自基底耦合的噪聲會改變每級電路輸出節(jié)點的電容,從而使振蕩器的總頻率不斷改變。此外,除熱噪聲外,所有環(huán)形振蕩器延遲電路級中的電源和基底噪聲都是相關(guān)的,所以如果沒有牢靠的接地環(huán)保護電路,設(shè)計人員都不希望讓兩個振蕩器電路靠得太近。如果屏蔽不是很好,會造成兩個位流源之間的隨機性相互關(guān)聯(lián)。在最終的振蕩器設(shè)計中,所有這些因素都必須要考慮到。
此外,就算設(shè)計人員有良好的意愿,實施方案也可能無法產(chǎn)生真正的隨機位流。設(shè)計人員或許要借助一些成本高昂的額外測試來保證隨機數(shù)發(fā)生器系統(tǒng)能產(chǎn)生期望的結(jié)果。如前所述,隨機性主要來自電源和基底噪聲與振蕩器電路的耦合,由于這些振蕩器會耦合同一個噪聲源,因此設(shè)計人員不希望將它們靠得太近。進一步來說,如果兩個振蕩器鎖定在同一個噪聲源上并相互耦合,那么它們之間的相關(guān)性也會增加,從而使兩個源的隨機輸出相互關(guān)聯(lián)。如果在最終布局上將兩個振蕩器分開,電源和基底噪聲的相關(guān)效應(yīng)便可減輕。
采用振蕩器采樣法的一種常見做法是多設(shè)計一對振蕩器,萬一主隨機源失效了,它還可以降低RNG系統(tǒng)沒有非確定性噪聲源的風險,隨后通過一個強大的混合函數(shù)將采樣位流進行混合,以便保留各個源固有的隨機性,這一點將在后面詳述。為了從混合位流中獲得更好的隨機性,必須給各振蕩器選擇一個獨特的主標稱頻率,或者使其頻率能夠調(diào)節(jié),這可盡量減少多個源之間的互相關(guān)性。當然,設(shè)計者必須權(quán)衡考慮,要么接受額外成本,要么承擔不能生成真正隨機數(shù)的風險。
偏差糾正器
振蕩器采樣法的工作基于這樣一個事實,即高頻振蕩器一直保持50%的占空比,而低頻振蕩器每個周期都有明顯變化。如果情況不是這樣(盡管絕大部分情況下是這樣),所獲得的位碼便會出現(xiàn)偏差,既可能是“1”,也可能是“0”,這稱為偏移。幸運的是我們可以采取有效的后處理方法來糾正偏差,以一種確定的方式產(chǎn)生分布更均勻的位流。其中兩種最簡單的技術(shù)分別稱為奇偶生成和轉(zhuǎn)換映射,此外還有一些較復雜的偏差糾正方法,包括使用快速傅利葉變換函數(shù)和更復雜的位混排技術(shù),它們通常采用延遲元件和反饋通路組合來去除位與位之間的相關(guān)性。
偏差糾正的目標是對位流進行均衡分配,以便以相同的概率產(chǎn)生“1”和“0”,其做法基本上是從有偏差的位序列中提取出更隨機的數(shù)值。這種后處理功能并非振蕩器采樣技術(shù)所獨有,其應(yīng)用對原始噪聲源沒有要求,要實現(xiàn)這種功能也并不復雜。一種簡單方法是奇偶生成,它具有魯棒性強的優(yōu)點,可用于更大范圍的偏差分布。用硬件來實現(xiàn)固定長度位采樣序列一般非常簡單,例如簡單的級聯(lián)XOR鏈便可有效用作一個奇偶生成器并完成適當?shù)钠罴m正(圖5)。
轉(zhuǎn)換映射也叫做馮·諾依曼糾正器,它將一對采樣輸入位轉(zhuǎn)換成一個輸出位,例如把輸入對[0,1]轉(zhuǎn)換成1,把[1,0]轉(zhuǎn)換成0,而在輸入為[0,0]或[1,1]時什么也不輸出。這種技術(shù)可以完全消除偏差,但其代價是必須在輸入位之間創(chuàng)建一個不定量的延遲,并產(chǎn)生一個輸出位長的任意數(shù)。
混合函數(shù)
即使采用了所有上述技術(shù),仍然存在這樣一些擔憂,即由于存在多種非隨機數(shù)據(jù)源(如前面提及的多個振蕩器源組合),系統(tǒng)固有的隨機性可能受到影響。采用功能強大的混合函數(shù)可以確保隨機源的隨機性,這些函數(shù)將兩個或更多采樣位進行組合,然后產(chǎn)生一個輸出位,該輸出位是先前各輸入位的復雜非線性函數(shù)。當然,這樣獲得的輸出隨機位數(shù)不可能多于輸入位數(shù)。對這個函數(shù)期望的功能是任何輸入位的改變都會引起大約一半輸出位的改變,這些混合函數(shù)也可作為更復雜的糾偏方法去除位流偏差,如同前面討論的那樣。
一般情況下,混合函數(shù)功能越強,它所占用的芯片面積也越大,前面提到的級聯(lián)XOR便是很簡單的一例。DES加密/解密算法則是更為復雜的例子,因為它需要120個輸入位,產(chǎn)生64個輸出位,每一個輸出位都依賴一個涉及所有輸入位的復雜非線性函數(shù),其它加密/解密算法的工作方式也類似。混排函數(shù)也可用作強大的混合函數(shù),它們使用任意長度的輸入位,并產(chǎn)生一定長度的信息摘要。同樣,設(shè)計工程師需要進行權(quán)衡,要在額外開銷與所生成的位流無法達到期望隨機度之間做選擇。
統(tǒng)計評估
美國商業(yè)部創(chuàng)建了多種用來評估加密應(yīng)用中隨機數(shù)發(fā)生器隨機程度的標準,美國國家標準技術(shù)研究所(NIST)出版的“800-22特刊”推薦了一種全面的隨機數(shù)發(fā)生器統(tǒng)計測試方法,并嚴格規(guī)定了滿足各種程度隨機性的衡量標準。測試工程師可在驗證過程中使用這種測試方法或其它類似測試,檢驗設(shè)計是否具有非隨機特征,從而判斷是否達到了某種程度的隨機性。NIST統(tǒng)計測試套件中規(guī)定了16種不同類型的測試,以便能發(fā)現(xiàn)被測隨機數(shù)發(fā)生器的缺陷。
NIST FIPS 140-2是美國商業(yè)部頒發(fā)的另一份文件,它定義了設(shè)計者在安全應(yīng)用中采用加密設(shè)備時必須遵守的一系列要求。其中一個最重要的要求是任何使用隨機數(shù)發(fā)生器的實時加密模塊必須提供加電能力并可對RNG功能進行持續(xù)的實時測試,確保它在工作過程中不出現(xiàn)故障,如果在規(guī)定的統(tǒng)計測試中出現(xiàn)任何失敗,RNG模塊都必須進入一種錯誤狀態(tài)。對于SoC設(shè)計來說,這意味著如果最終產(chǎn)品希望獲得美國政府安全標準許可的話,那么進行測試的測試器模塊必須集成在設(shè)備本身之中并滿足規(guī)定的要求。
某些產(chǎn)生非確定性噪聲源的技術(shù)也許并不適用,這取決于是使用標準單元設(shè)計還是使用客戶定制布局設(shè)計。的確可以保證一項設(shè)計達到期望的隨機度,但這種保證的代價是增加芯片尺寸以便實現(xiàn)冗余結(jié)構(gòu)或更為復雜的后處理功能。即便是精心規(guī)劃的設(shè)計,最后階段也必須通過統(tǒng)計測試套件的驗證,只有這樣才能說設(shè)計達到了期望的隨機度。
參考文獻
1. Jun and Kocher, "Intel Random Number Generator," Cryptography Research Inc. white paper, April 1999
2. Craig Petrie and J. Alvin Connelly, "A Noise-Based IC Random Number Generator for Applications in Cryptography," IEEE TCAS I, Vol. 47, No. 5, May 2000, p615-621
3. Fairfield, Mortenson, Coulthart, "An LSI Random Number Generator," Advances in Cryptology, Proceedings of Crypto 84, p203-230
4. Frank Herzel and Behzad Razavi, "A Study of Oscillator Jitter Due to Supply and Substrate Noise," IEEE TCAS II, Vol. 46, No. 1, January 1999, p56-62
5. Eastlake, Crocker and Schiller, "Randomness Recommendations for Security," RFC-1750
6. NIST Special Publication 800-22, "A Statistical Test Suite for Random and Pseudorandom Number Generators for Cryptographic Applications," Information Technology Laboratory of the National Institute of Standards and Technology, Gaithersburg, Md., September 2000
7. Federal Information Processing Standards Publication 140-2, "Security Requirements for Cryptographic Modules," Information Technology Laboratory of the National Institute of Standards and Technology, Gaithersburg, Md., May 2001
作者: Alex Soohoo
系統(tǒng)應(yīng)用經(jīng)理
互聯(lián)產(chǎn)品事業(yè)部
IDT公司
Email: @
