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