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