基于SP 800-22標(biāo)準(zhǔn)的隨機(jī)性測(cè)試方法研究與快速實(shí)現(xiàn)*

段俊紅，韓煉冰，房利國(guó)

（中國(guó)電子科技集團(tuán)公司第三十研究所，四川 成都 610041）

0 引 言

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

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

1 SP 800-22標(biāo)準(zhǔn)簡(jiǎn)介

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

1.1 SP 800-22標(biāo)準(zhǔn)定義的測(cè)試項(xiàng)

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

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

1.2 SP 800-22標(biāo)準(zhǔn)定義的測(cè)試項(xiàng)

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

2 部分測(cè)試項(xiàng)的快速實(shí)現(xiàn)

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

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

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

在SP 800-22標(biāo)準(zhǔn)中，對(duì)n比特二進(jìn)制序列進(jìn)行頻數(shù)測(cè)試的步驟如下：

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

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

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

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

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

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

根據(jù)erfc函數(shù)的計(jì)算方法可知，erfc(1.821 39)=0.01 erfc(1.821 40)=0.009 99，當(dāng)n=1 000 000時(shí)，有：

因此，當(dāng)n=1 000 000時(shí)，如果Sn絕對(duì)值大于2 575，則判定序列是非隨機(jī)的。

2.2 游程測(cè)試快速實(shí)現(xiàn)

在SP 800-22標(biāo)準(zhǔn)中，對(duì)n比特二進(jìn)制序列進(jìn)行游程測(cè)試的步驟如下：

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

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

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

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

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

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

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

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

2.3 序列測(cè)試快速實(shí)現(xiàn)

在SP 800-22標(biāo)準(zhǔn)中，對(duì)n比特二進(jìn)制序列進(jìn)行游程測(cè)試的步驟如下：

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

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

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

（5）計(jì)算P1和P2的值；

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

在SP 800-22標(biāo)準(zhǔn)中，對(duì)n比特二進(jìn)制序列進(jìn)行二元矩陣秩測(cè)試的測(cè)試步驟如下：

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

使用的測(cè)試平臺(tái)為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)境。測(cè)試樣本為利用NIST隨機(jī)性統(tǒng)計(jì)測(cè)試包“sts-2.1.2”產(chǎn)生的1 000 000比特偽隨機(jī)數(shù)。分別使用NIST測(cè)試包和快速實(shí)現(xiàn)后的隨機(jī)性測(cè)試程序?qū)颖緮?shù)據(jù)進(jìn)行測(cè)試，并記錄每項(xiàng)測(cè)試需要的時(shí)間，時(shí)間單位為μs，結(jié)果如表1所示。

表1 隨機(jī)性測(cè)試結(jié)果

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

4 結(jié) 語

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