ay: block;">
在保障互聯(lián)網(wǎng)安全的各種加密算法中,隨機(jī)數(shù)產(chǎn)生至關(guān)重要。產(chǎn)生隨機(jī)數(shù)的方法有多種,其中振蕩器采樣法最適于構(gòu)建SoC設(shè)計(jì)所需的隨機(jī)數(shù)發(fā)生器。本文介紹振蕩器采樣法的工作原理,并概述在具體使用這種振蕩器時(shí)應(yīng)注意的事項(xiàng)。
隨著許多企業(yè)的網(wǎng)絡(luò)應(yīng)用從內(nèi)部網(wǎng)擴(kuò)展到公眾互聯(lián)網(wǎng),對虛擬專用網(wǎng)絡(luò)(VPN)設(shè)備的需求也開始逐漸上升。為了服務(wù)于這個(gè)市場,半導(dǎo)體廠商推出了一些專用產(chǎn)品,把所有必需安全功能都集成在一個(gè)器件里面。
專用于互聯(lián)網(wǎng)協(xié)議安全(IPsec)的AES和3DES類加密/解密算法以及SHA1和MD5等散列算法已廣為人知并得到普遍重視,然而,保證VPN系統(tǒng)安全的關(guān)鍵在于生成隨機(jī)數(shù)的能力,但這點(diǎn)卻常常被忽視。
隨機(jī)數(shù)是許多加密應(yīng)用的基礎(chǔ),其作用是生成Diffie-Hellman、Rivest-Shamir-Adelman和數(shù)字簽名等算法所需的公共/專用密鑰對,并為大批量加密算法和IPsec分別生成初始向量和即時(shí)隨機(jī)數(shù),此外,大量其它類型的安全協(xié)議也靠隨機(jī)數(shù)發(fā)生器的不可預(yù)測性來防止系統(tǒng)被破解。常用一些復(fù)雜數(shù)學(xué)函數(shù)生成高質(zhì)量偽隨機(jī)數(shù)發(fā)生器(PRNG)位流,但事實(shí)證明有很多途徑可以攻擊用PRNG加密的系統(tǒng),因此加密安全系統(tǒng)需要使用更高質(zhì)量的隨機(jī)數(shù)發(fā)生器。
在明確了這些需求之后,到底有沒有一種真正的隨機(jī)數(shù)發(fā)生器可以根據(jù)非確定噪聲源產(chǎn)生隨機(jī)數(shù),并特別適用于系統(tǒng)級芯片(SoC)設(shè)計(jì)呢？大多數(shù)隨機(jī)數(shù)發(fā)生器方案通?？梢詺w為三大類,即直接放大、離散時(shí)間混沌和振蕩器采樣。前兩種方法更適用于客戶定制的單元設(shè)計(jì),因?yàn)樵谶@些場合設(shè)計(jì)人員可以控制實(shí)際電路的布局；而振蕩器采樣技術(shù)可以作為標(biāo)準(zhǔn)單元設(shè)計(jì)流程的一部分,因此在SoC設(shè)計(jì)中很流行。不過設(shè)計(jì)人員即使選用了振蕩器技術(shù),仍然有許多實(shí)施問題需要仔細(xì)考慮。
隨機(jī)數(shù)生成技術(shù)
直接放大技術(shù)使用高增益高帶寬放大器來處理由熱噪聲或散射噪聲引起的電壓變化。例如可采用N阱電阻對將其熱噪聲轉(zhuǎn)換成一個(gè)電壓變化信號,然后以抖動的形式輸入隨機(jī)數(shù)發(fā)生器模塊微系統(tǒng)中(圖1)。采用這種方法時(shí)設(shè)計(jì)人員必須要考慮其它一些因素,如系統(tǒng)熱噪聲通常與基底噪聲及電源電壓波動等局部特征耦合在一起,如果電路沒有正確屏蔽,這些因素便會使熱噪聲源的隨機(jī)性受到影響?？朔@種現(xiàn)象的方法是對一對鄰近的電阻進(jìn)行采樣,再對結(jié)果求差以減少其它噪聲源的影響。
離散時(shí)間混沌法使用模擬信號處理技術(shù)產(chǎn)生隨機(jī)位流。這種方式下,隨機(jī)性不是從熱噪聲源獲得,而是從非常穩(wěn)定的動態(tài)變化中得到,其系統(tǒng)設(shè)計(jì)與模/數(shù)轉(zhuǎn)換器性質(zhì)類似。在傳統(tǒng)的A/D轉(zhuǎn)換器中,殘余信號經(jīng)過采樣和保持,再饋送到A/D轉(zhuǎn)換器的輸入端(圖2)。一般來說,單是這種技術(shù)本身尚不足以產(chǎn)生隨機(jī)序列,因?yàn)殡娐返牟粶?zhǔn)確性限制了A/D轉(zhuǎn)換分辨率,也降低了系統(tǒng)產(chǎn)生隨機(jī)序列的能力。因此,為獲得非確定隨機(jī)性,這種技術(shù)常常要與其它技術(shù)配合使用。
目前,隨機(jī)數(shù)發(fā)生器(RNG)設(shè)計(jì)中最流行的方法是振蕩器采樣法(圖3),其基本設(shè)計(jì)思想是利用兩個(gè)獨(dú)立工作的高、低頻振蕩器之間的相對關(guān)系來得到非確定噪聲源,用高抖動低頻振蕩器采樣高頻振蕩器,從而產(chǎn)生隨機(jī)數(shù)序列。在數(shù)字電路中,低頻方波源可作為一個(gè)正沿觸發(fā)D觸發(fā)器的時(shí)鐘,高頻方波源則作為觸發(fā)器的數(shù)據(jù)輸入,并在時(shí)鐘脈沖的上升沿對其進(jìn)行采樣。
在該系統(tǒng)中,產(chǎn)生隨機(jī)數(shù)的關(guān)鍵元件是低頻振蕩器,因?yàn)樗脑O(shè)計(jì)具有頻率不穩(wěn)定性,即抖動,而且低頻與高頻之比經(jīng)過仔細(xì)選擇可以符合一定條件。設(shè)計(jì)中最重要的是低頻振蕩器的抖動量,這個(gè)抖動就是隨機(jī)源。頻率不穩(wěn)定性可以是此類振蕩器的一個(gè)功能,也可由另一個(gè)非確定噪聲源直接“植入”,因此可以說,正是采樣時(shí)鐘相對于高頻數(shù)據(jù)輸入的相位變化保證了可以獲得隨機(jī)位流。
如果兩個(gè)振蕩器在工作過程中都不發(fā)生漂移,那么采樣得到的位流便具有周期性而且可以預(yù)測,這種周期性和通常稱為節(jié)拍頻率的頻率比有關(guān)。此外,兩個(gè)振蕩器的頻率比對所產(chǎn)生的位流有著非常重要的影響。多項(xiàng)研究表明,為了保證高度隨機(jī)性,低頻振蕩器周期變化標(biāo)準(zhǔn)差的兩倍與高頻振蕩器周期之比應(yīng)該大于3:2,否則位碼之間便會存在明顯的相關(guān)性,以致于后面的位將比其前面的位更容易預(yù)測。
使用振蕩器采樣法
選用振蕩器采樣法來設(shè)計(jì)隨機(jī)數(shù)發(fā)生器的設(shè)計(jì)人員還必須考慮其它一些實(shí)施問題,所選振蕩器的類型也會影響整個(gè)系統(tǒng)設(shè)計(jì)的固有隨機(jī)性。此外,為了保證相關(guān)噪聲源不會降低系統(tǒng)隨機(jī)性,必須仔細(xì)選擇振蕩器,這必然又會增加器件電路布局的復(fù)雜性。作為一種補(bǔ)償,可采用數(shù)字后處理技術(shù)來降低設(shè)計(jì)風(fēng)險(xiǎn)并保留系統(tǒng)的隨機(jī)性。
在考慮實(shí)施振蕩器采樣法時(shí),設(shè)計(jì)人員可從幾種不同類型的振蕩器中進(jìn)行選擇,包括差分振蕩器、單端振蕩器及混合振蕩器,不同類型振蕩器對不同噪聲源的敏感度也不一樣。顯而易見,不同振蕩器的特性比較需要豐富的知識,本文在此只作簡單討論。
通常,差分振蕩器對電源及基底噪聲的敏感度不如單端振蕩器。這是因?yàn)椴罘址糯笃鲗Φ碾娫春徒拥攸c(diǎn)會同時(shí)出現(xiàn)電壓擺動,所以兩個(gè)輸入之間的差值保持一致,輸出也一致,呈現(xiàn)出較高的共模抑制比(CMRR)。差分邏輯常用于模擬邏輯壓控振蕩器設(shè)計(jì)中,例如鎖相環(huán)中的振蕩器,因?yàn)殒i相環(huán)需要較高的CMRR,所以差分振蕩器方案并不特別適用于那些需要非確定噪聲源的設(shè)計(jì)。另一方面,單端反相振蕩器極易受電壓擺動或輸入信號中直流分量的影響,如果噪聲對電平帶來任何波動,都會影響振蕩器的抖動。此外,差分、感容及張弛振蕩器設(shè)計(jì)需要客戶定制的電路布局,所以無法集成到標(biāo)準(zhǔn)單元的SoC設(shè)計(jì)中。因此,在SoC設(shè)計(jì)中最簡單直接的解決方案通常是單端環(huán)形振蕩器(圖4)。
盡管單端環(huán)形振蕩器有這樣的優(yōu)勢,在選用時(shí)還是有一些復(fù)雜因素必須考慮。由于高速數(shù)字系統(tǒng)存在切換動作,因此熱噪聲與電源/基底噪聲相比一般可以忽略不計(jì)。電源和基底噪聲是引起噪聲耦合的主要原因,噪聲耦合的振蕩器在反相電路中會產(chǎn)生δ延遲。電源電壓變化或來自基底耦合的噪聲會改變每級電路輸出節(jié)點(diǎn)的電容,從而使振蕩器的總頻率不斷改變。此外,除熱噪聲外,所有環(huán)形振蕩器延遲電路級中的電源和基底噪聲都是相關(guān)的,所以如果沒有牢靠的接地環(huán)保護(hù)電路,設(shè)計(jì)人員都不希望讓兩個(gè)振蕩器電路靠得太近。如果屏蔽不是很好,會造成兩個(gè)位流源之間的隨機(jī)性相互關(guān)聯(lián)。在最終的振蕩器設(shè)計(jì)中,所有這些因素都必須要考慮到。
此外,就算設(shè)計(jì)人員有良好的意愿,實(shí)施方案也可能無法產(chǎn)生真正的隨機(jī)位流。設(shè)計(jì)人員或許要借助一些成本高昂的額外測試來保證隨機(jī)數(shù)發(fā)生器系統(tǒng)能產(chǎn)生期望的結(jié)果。如前所述,隨機(jī)性主要來自電源和基底噪聲與振蕩器電路的耦合,由于這些振蕩器會耦合同一個(gè)噪聲源,因此設(shè)計(jì)人員不希望將它們靠得太近。進(jìn)一步來說,如果兩個(gè)振蕩器鎖定在同一個(gè)噪聲源上并相互耦合,那么它們之間的相關(guān)性也會增加,從而使兩個(gè)源的隨機(jī)輸出相互關(guān)聯(lián)。如果在最終布局上將兩個(gè)振蕩器分開,電源和基底噪聲的相關(guān)效應(yīng)便可減輕。
采用振蕩器采樣法的一種常見做法是多設(shè)計(jì)一對振蕩器,萬一主隨機(jī)源失效了,它還可以降低RNG系統(tǒng)沒有非確定性噪聲源的風(fēng)險(xiǎn),隨后通過一個(gè)強(qiáng)大的混合函數(shù)將采樣位流進(jìn)行混合,以便保留各個(gè)源固有的隨機(jī)性,這一點(diǎn)將在后面詳述。為了從混合位流中獲得更好的隨機(jī)性,必須給各振蕩器選擇一個(gè)獨(dú)特的主標(biāo)稱頻率,或者使其頻率能夠調(diào)節(jié),這可盡量減少多個(gè)源之間的互相關(guān)性。當(dāng)然,設(shè)計(jì)者必須權(quán)衡考慮,要么接受額外成本,要么承擔(dān)不能生成真正隨機(jī)數(shù)的風(fēng)險(xiǎn)。
偏差糾正器
振蕩器采樣法的工作基于這樣一個(gè)事實(shí),即高頻振蕩器一直保持50%的占空比,而低頻振蕩器每個(gè)周期都有明顯變化。如果情況不是這樣(盡管絕大部分情況下是這樣),所獲得的位碼便會出現(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ù)期望的功能是任何輸入位的改變都會引起大約一半輸出位的改變,這些混合函數(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ī)度。
參考文獻(xiàn)
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: @
