基于SP 800-22標準的隨機性測試方法研究與快速實現*

段俊紅，韓煉冰，房利國

（中國電子科技集團公司第三十研究所，四川 成都 610041）

0 引 言

隨機數在眾多科學研究和工程技術領域都有著廣泛應用。特別是在信息安全領域，隨機數作為密碼應用的一個重要組成部分，在眾多密碼算法及密碼協議中起著至關重要的作用[1]。安全、高速地產生強隨機性的隨機數，一直是信息安全領域的重點關注問題。

物理隨機數發生器利用自然界的隨機物理過程，可獲得不重復、不具備周期性的隨機序列，被廣泛應用于金融、政府和軍事等行業的信息安全保密通信設備。但是，在實際使用過程中，由于環境的復雜性和元器件的耗損等，都可能造成物理隨機數發生器自身性能的下降[2]。一個有缺陷的隨機數序列可能會導致整個安全保密系統被攻擊者攻破，從而導致嚴重的安全漏洞。因此，當隨機數應用于安全保密系統時，必須對其進行隨機性測試。

1 SP 800-22標準簡介

隨機性測試通常通過概率統計的方法考察被檢測序列是否滿足隨機序列的某些特征（如周期性、相關性和分布特性等），從而判定其是否隨機[3]。目前，國際上的隨機性測試方法200多種，其中美國國家標準技術學會（NIST)制定的SP 800-22標準是最具代表性的方法之一。該標準專門用于對密碼應用中的隨機數和偽隨機數發生器產生的二進制隨機數序列進行統計測試。

1.1 SP 800-22標準定義的測試項

SP 800-22標準在最開始制定時共定義了16個測試項來檢驗二進制序列的隨機性。2010年，NIST又發布了一個新的版本（SP 800-22 revision 1a），里面共定義了15個測試項[4]。和原來的標準相比，減少了“Lempel-Ziv壓縮測試”這一測試項。每個測試項通過選取一個特定的統計量，計算觀察值是否符合理論分布，以此確定待測序列在某方面是否存在規律[5]。如果能檢測到這種規律，則認為序列是不隨機的；反之，則認為序列是隨機的。例如，單比特頻數測試通過查看序列中0和1的個數是否近似相同來判斷序列是否隨機。

由于每個測試項只能檢測到序列在某一方面的特性，如果只通過某一項測試，并不能說明序列一定是隨機的。例如，二進制序列“000000111111”能通過單比特頻數測試，但它顯然不是一個隨機序列。因此，在實際使用過程中，應根據需要選擇適當的測試項進行測試。

1.2 SP 800-22標準定義的測試項

NIST在制定SP800-22標準的同時，還發布了一個隨機性測試包“sts-2.1.2”。該測試包提供了標準定義的所有測試項和一些測試樣例的C語言源代碼。利用測試包可以直接在Linux平臺生成一個可執行程序“assess”。該程序可以對外部輸入或程序自己生成的隨機數進行隨機性測試，并將測試結果輸出到特定目錄的指定文件中。

2 部分測試項的快速實現

對隨機數進行隨機性測試，通常需要對待測數據進行逐比特的數值判斷和數學運算才得到統計量值，有時還要通過若干輪的逐比特運算。同時，統計測試公式也會涉及很多復雜的數學運算，如開方、對數、積分等，因此對大量數據進行隨機性測試是一個非常耗時的過程。

如果是在嵌入式平臺中進行隨機性測試，由于其運算能力有限，耗時將會更久。在需要對大量數據進行隨機性在線測試的應用場合中，對SP800-22標準定義的測試項進行研究和快速實現是非常必要的。受于篇幅限制，下面僅對部分測試項的快速實現方法進行介紹。

2.1 頻數測試快速實現

在SP 800-22標準中，對n比特二進制序列進行頻數測試的步驟如下：

（1）將序列中的0和1轉換為-1和+1，并相加得到Sn；

（2）根據式（1）計算P值，如果P＜0.01，則判定序列是非隨機的。

該測試項最耗時的是步驟（1）的Sn值計算。本文采用與文獻[6]相似的方法對頻數測試進行快速實現。方法主要包括以下幾方面內容：

（1）每個內存單元中不只存1比特數據，而是8比特數據，便于一次處理多比特數據；

（2）利用查表法直接得到轉換后序列的8比特和；

（3）優化統計測試公式，降低計算復雜度。

根據erfc函數的計算方法可知，erfc(1.821 39)=0.01 erfc(1.821 40)=0.009 99，當n=1 000 000時，有：

因此，當n=1 000 000時，如果Sn絕對值大于2 575，則判定序列是非隨機的。

2.2 游程測試快速實現

在SP 800-22標準中，對n比特二進制序列進行游程測試的步驟如下：

（1）計算待測序列中‘1’的比例π，并檢查下面的判定公式是否成立。如果不成立，則判定序列為不隨機，無需進行后面的測試；

（2）如果式（4）成立，則計算測試統計量V：

根據式（6）計算P值，如果P＜0.01，則判定序列是非隨機的。

游程測試最耗時的是步驟（1）的π值計算和步驟（2）的V值計算。其中，計算V值時需要依次對序列中的連續2比特數據進行比較，如果不相同，則將V值加1。

游程測試的快速實現方法為：

（1）共享頻數測試中對序列中‘1’的統計值，或采用與其相同的方法計算‘1’的統計值；

（2）利用查表法直接得出8比特數據的V值。

查找表大小為256 Byte，建立方法為：表中第i個數據的值Ti與i值相同的8位二進制序列的游程個數。例如，當i=5時，Ti=4。同時，如果當前8比特的最高位和前一個8比特的最低位相同，則將V值減1。

2.3 序列測試快速實現

在SP 800-22標準中，對n比特二進制序列進行游程測試的步驟如下：

（1）構建擴張序列，將待測序列的第一個m-1比特加到整個序列的末尾；

（2）確定所有可能的重疊m比特、m-1比特、m-2比特模式的子序列出現的個數，分別用Vi1…Vim，Vi1…Vim-1和 Vi1…Vim-2表示；

（3） 令 x=m、x=m-1和 x=m-2， 計 算 φ2m、和的值：

（5）計算P1和P2的值；

（6）如果P1＜0.01，或者P2＜0.01，則判定序列是非隨機的。

通過觀察上面的測試步驟可以發現，測試中最耗時的是步驟（2）。NIST的統計測試包通過一個通用的方法來計算擴張序列所有可能的重疊x比特，該方法的具體實現步驟為：

（1）定義局部變量k、i，初始值分別設為1和0；

（2）定義一個具有2x+1-1個元素的數組變量P[·]，每個元素的初始值都設為0；

（3）將序列劃分為n/x個非重疊子序列；

（4）對于每一個子序列，依次判斷每個比特的值，如果值為1，則令k=k+1；如果值為0，則令k=2k+1；

（5）每個子序列判斷結束后，令P[k-1]=P[k-1]+1，同時令k=1。

m值的不確定性是運算耗時的一個重要因素。而在實際應用過程中，m值通常固定為3。因此，當m=3時，游程測試的快速實現方法如下：

（1）采用查表法計算序列中所有可能的重疊3比特模式的子序列出現的次數。

首先，建立兩個查找表，每個查找表由256個32位數據組成。查找表內每個數據再按8比特寬度分為四個部分。第一個查找表中第i個數據的四部分，分別記為T1i1、T1i2、T1i3和T1i4；第二個查找表中第i個數據的四部分，分別記為T2i1、T2i2、T2i3和T2i4。其中，T1i1～T1i4分別為將i轉化為8位二進制序列后重疊的000、001、010和011子序列出現的次數；T2i1～T2i4分別為將i轉化為8位二進制序列后重疊的100、101、110和111子序列出現的次數。

接下來，查表統計序列中所有可能的重疊3比特模式的子序列出現的次數。因為是重疊3比特進行統計，所以如果上一次是使用序列中第j～j+7位進行查表的，那本次將使用序列中第j+6～j+13位進行查表。

（2）采用查表法計算序列中所有可能的重疊2比特模式的子序列出現的次數。

首先建立查找表，但與3比特模式不同，這里只需要建一個表即可。查找表由256個數據組成，每個數據的寬度為32位。查找表內每個數據再按8比特寬度分為四個部分，分別記為Ti1、Ti2、Ti3和Ti4。Ti1～Ti4分別為將i轉化為8位二進制序列后重疊的00、01、10和11子序列出現的次數。

接下來，查表統計序列中所有可能的重疊2比特模式的子序列出現的次數。對于2比特模式，如果上一次是使用序列中第i～i+7位進行查表的，那本次將使用序列中第i+7～i+14位進行查表。

（3）采用查表法計算序列中所有可能的重疊1比特模式的子序列出現的次數。此時，問題轉化為統計序列中‘0’和‘1’出現的次數。快速實現方式同“頻數測試”。

2.4 二元矩陣秩測試快速實現

在SP 800-22標準中，對n比特二進制序列進行二元矩陣秩測試的測試步驟如下：

（1）將序列分成N個M*Q比特的子塊，并舍棄多余位；

（2）將產生的各個子塊組成M*Q的矩陣，計算每個矩陣的秩Ri，其中i=1,2,…,N；

（3）令FM為滿秩矩陣的個數，FM-1為秩為滿秩減1矩陣的個數，T=N-FM-FM-1，并計算統計量V；

（4）計算P值（P=e-V/2），如果P＜0.01，則判定序列是非隨機的。

該項測試最耗時的是步驟（3）（求矩陣的秩），NIST的統計測試包通過行變換將矩陣化簡為三角矩陣，再通過統計主對角線上1的個數得到矩陣的秩。具體方法為：

（1）申請一個M*N的二維數組空間，將測試序列中的比特值依次放入數組空間中；

（2）檢查第i行i列的值是否為1。如果為1，則轉到步驟（3）；如果為0，則在第i列中從第i+1行開始依次遞增一行找值為1的元素，找到后將該行所有元素的值與第i行進行互換；

（3）在第i列中，從第i+1行開始依次遞增一行找值為1的元素，找到后將該行從第i列開始的元素與第i行從第i列開始的元素依次異或至行尾，并將結果存回該行對應位置；

（4）i值加1并檢查i值，如果i≠M-2，則返回步驟（2），否則設定i=M-1；

（5）檢查第i行i列的值是否為1。如果為1，則轉到步驟（6）；如果為0，則在第i列中從第i-1行開始依次遞減一行找值為1的元素，找到后將該行所有元素的值與第i行進行互換，并轉到下一步；

（6）在第i列中，從第i-1行開始依次遞減一行找值為1的元素，找到后將該行所有元素與第i行所有元素依次異或，并將結果存回該行對應位置；

（7）i值減1并檢查i值，如果i≠1，則返回步驟（5），否則結束變換。

由于SP 800-22標準中并沒有對M和Q值做具體規定，只是要求n≥38MQ。因此，本文選擇標準的推薦值（M=Q=32）。此時，二元矩陣秩的快速實現方法為：

（1）申請32個32位數組空間，將測試序列中按字節存放的值放入數組空間中，并設定i=0；檢查數組中第i個元素的第31-i比特是否為1。如果為1，則轉到步驟（3）；如果為0，則從數組第i+1個元素開始依次遞增一個找第31-i比特為1的元素，找到后將該元素的值與第i個元素進行互換；

（2）從數組第i+1個元素開始依次遞增一個找第31-i比特為1的元素，找到后將該元素從第31-i比特開始與數組第i個元素從第31-i比特開始依次異或至比特31，并將結果存回該元素對應比特位；

（3）i值加1并檢查i值，如果i≠M-2，則返回步驟（2），否則設定i=M-1；

（4）檢查數組中第i個元素的第31-i比特是否為1。如果為1，則轉到步驟（6）；如果為0，則在第i列中從第i-1個元素開始依次遞減一個找第31-i比特為1的元素，找到后將該行所有元素的值與第i行進行互換，并轉到下一步；

（5）從數組第i-1個元素開始依次遞減一個找第31-i比特為1的元素，找到后將該元素與第i個元素異或，并將結果存回該元素；

（6）i值減1并檢查i值，如果i≠1，則返回步驟（5）；

（7）優化統計測試公式，降低計算復雜度。

因為e-9.210 44/2=0.010 0，e-9.210 441/2=0.009 9，同時根據e-V/2函數的性質可知，對P值判定可以改為對V值判定：如果V大于9.210 44，則判定序列是非隨機的。

3 測試及結果分析

使用的測試平臺為Intel Core i5 @3.30 GHz處理器4 GB DDR3 1 600 MHz內存、Windows XP SP3操作系統、Visual Studio 2010開發環境。測試樣本為利用NIST隨機性統計測試包“sts-2.1.2”產生的1 000 000比特偽隨機數。分別使用NIST測試包和快速實現后的隨機性測試程序對樣本數據進行測試，并記錄每項測試需要的時間，時間單位為μs，結果如表1所示。

表1 隨機性測試結果

從表1的數據可以看出，采用快速實現法后，隨機數測試速率比NIST測試包有大幅提升，特別是頻數測試和序列測試，速率分別提升了21.4倍和111.4倍。

4 結 語

隨機數在許多領域都有著廣泛應用，對隨機數進行隨機性測試是保證隨機數質量重要的手段。本文通過對美國隨機數測試標準SP800-22定義的測試項進行研究和快速實現，大幅提升了隨機數隨機性測試的效率，同時通過優化統計測試公式降低了計算復雜度，使該快速實現方法也適用于嵌入式平臺。