段俊紅，韓煉冰，房利國

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

0 引 言

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

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

1 SP 800-22標準簡介

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

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

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

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

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

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

2 部分測試項的快速實現(xiàn)

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

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

2.1 頻數(shù)測試快速實現(xiàn)

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

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

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

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

（1）每個內(nèi)存單元中不只存1比特數(shù)據(jù)，而是8比特數(shù)據(jù)，便于一次處理多比特數(shù)據(jù)；

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

（3）優(yōu)化統(tǒng)計測試公式，降低計算復雜度。

根據(jù)erfc函數(shù)的計算方法可知，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 游程測試快速實現(xiàn)

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

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

（2）如果式（4）成立，則計算測試統(tǒng)計量V：

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

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

游程測試的快速實現(xiàn)方法為：

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

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

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

2.3 序列測試快速實現(xiàn)

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

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

（2）確定所有可能的重疊m比特、m-1比特、m-2比特模式的子序列出現(xiàn)的個數(shù)，分別用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，則判定序列是非隨機的。

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

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

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

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

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

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

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

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

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

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

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

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

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

（3）采用查表法計算序列中所有可能的重疊1比特模式的子序列出現(xiàn)的次數(shù)。此時，問題轉(zhuǎn)化為統(tǒng)計序列中‘0’和‘1’出現(xiàn)的次數(shù)?？焖賹崿F(xiàn)方式同“頻數(shù)測試”。

2.4 二元矩陣秩測試快速實現(xiàn)

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

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

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

（3）令FM為滿秩矩陣的個數(shù)，F(xiàn)M-1為秩為滿秩減1矩陣的個數(shù)，T=N-FM-FM-1，并計算統(tǒng)計量V；

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

（7）優(yōu)化統(tǒng)計測試公式，降低計算復雜度。

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

3 測試及結(jié)果分析

使用的測試平臺為Intel Core i5 @3.30 GHz處理器4 GB DDR3 1 600 MHz內(nèi)存、Windows XP SP3操作系統(tǒng)、Visual Studio 2010開發(fā)環(huán)境。測試樣本為利用NIST隨機性統(tǒng)計測試包“sts-2.1.2”產(chǎn)生的1 000 000比特偽隨機數(shù)。分別使用NIST測試包和快速實現(xiàn)后的隨機性測試程序?qū)颖緮?shù)據(jù)進行測試，并記錄每項測試需要的時間，時間單位為μs，結(jié)果如表1所示。

表1 隨機性測試結(jié)果

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

4 結(jié) 語

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