王 彤，朱敏玲

北京信息科技大學(xué) 計算機學(xué)院，北京 100101

1 引言

網(wǎng)絡(luò)環(huán)境的日益復(fù)雜讓信息安全逐漸成為人們關(guān)注的重點話題。隨機序列在信息安全領(lǐng)域中有著廣泛的應(yīng)用，例如眾多的密碼算法、安全協(xié)議、數(shù)字水印、密碼芯片中都利用隨機序列來增強安全性[1]。因此，隨機序列的質(zhì)量直接影響信息安全問題。

隨機序列的產(chǎn)生方式分為兩種，一種是經(jīng)過物理現(xiàn)象產(chǎn)生的真隨機序列，另一種是經(jīng)過計算機中的隨機函數(shù)產(chǎn)生的偽隨機序列[2]。著名的計算機學(xué)家馮·諾依曼曾經(jīng)說過“任何想用數(shù)學(xué)的方法產(chǎn)生真隨機數(shù)的人都是在癡心妄想”[3]。而偽隨機數(shù)發(fā)生器和密碼算法是通過一系列復(fù)雜的數(shù)學(xué)運算處理“種子值”得到偽隨機序列，因為有“種子值”，偽隨機序列在一定程度上是可控可測的，難以保證其質(zhì)量。因此，在實際應(yīng)用中需要對隨機序列進行檢測，保證隨機序列的質(zhì)量。

隨機序列實質(zhì)上是對一組均勻分布的隨機變量進行抽樣，產(chǎn)生的結(jié)果是不可控制、不可預(yù)測的，序列中的每個元素是相互獨立，且服從均勻分布[4]。為保證隨機序列在應(yīng)用過程中的穩(wěn)定性，隨機性檢測通過一些特定的特性，比如統(tǒng)計比特數(shù)量、m位非重疊子序列頻數(shù)、兩比特間異或操作等，分析待檢測序列與真隨機序列之間的差距，判斷其是否通過檢測。經(jīng)過長時間的研究和發(fā)展，目前國內(nèi)外研究學(xué)者已經(jīng)提出了大量的隨機性檢測方法。國際上通用的檢測方法是將多種隨機性檢測算法組成檢測套件，以提供更復(fù)雜和全面的隨機性分析，但是隨機套件執(zhí)行效率較低，當檢測數(shù)據(jù)達到GB級時，在標準計算機上完成一次完整的隨機性檢測可能需要數(shù)小時[5]。

在隨機性檢測的應(yīng)用價值下，國內(nèi)外眾多研究學(xué)者對隨機性檢測項目進行優(yōu)化研究，例如，楊先偉等通過將不同參數(shù)情況進行整合，對撲克檢測進行優(yōu)化研究，提高算法效率9.5倍左右[6]；康紅娟，楊先偉等通過將待檢測序列分為初始序列和檢測序列并按字節(jié)進行處理，減少數(shù)據(jù)流失，減少大量對數(shù)運算，提高Maurer通用統(tǒng)計檢測效率[7]；Suciu等采用字節(jié)處理方式優(yōu)化隨機性統(tǒng)計檢測包，檢測包整體速度提升13.45倍[8]；Sys等對NIST統(tǒng)計測試套件進行優(yōu)化，并對線性復(fù)雜度檢測和Berlekamp-Massey算法進行分析和優(yōu)化[9]。

2001年美國NIST發(fā)布了16種隨機性檢測標準，其中將傳統(tǒng)的序偶檢測和撲克檢測替換為序列檢測，于亦舟等人將三種檢測方法進行對比分析，證明序列檢測效果要優(yōu)于同時使用撲克檢測和序偶檢測的效果[10]。近似熵檢測作為一項基礎(chǔ)檢測方法，不僅出現(xiàn)在我國的隨機性檢測標準中，也出現(xiàn)在眾多國家的檢測標準中。但是序列檢測和近似熵檢測的檢測速度較慢，在NIST統(tǒng)計測試套件中檢測速度位于各檢測項的末端[11]。因此，本文對序列檢測和近似熵檢測進行優(yōu)化分析，提高檢測方法的運行效率。

2 兩種檢測算法簡介

2.1 序列檢測

序列檢測的目的是判定待檢測序列中2m個m位重疊子塊的數(shù)目是否和隨機情況下預(yù)期值一致。隨機序列具有均勻性，故序列中每種m位重疊子序列出現(xiàn)的頻數(shù)應(yīng)該是一致的[12]。

計算兩個相鄰長度可重疊子塊的頻數(shù)時，設(shè)Yi(m)=(εi+1,εi+2,…,εi+m-1)，令：

式（1）中表示模式Y(jié)i(m)在待檢測序列中出現(xiàn)的相對頻數(shù)，πi表示模式l=(i1,i2,…,im)在待檢測序列中出現(xiàn)的相對頻率。待檢測序列長度為n，m

序列檢測的執(zhí)行流程如下：

（1）將待檢測序列ε構(gòu)造成一個新的序列ε′，構(gòu)造方法是將序列ε最開始的m-1位數(shù)據(jù)添加到序列ε的結(jié)尾得到新序列ε′，新序列ε′的長度為n′=n+m-1。

（2）計算ε′中所有的2m個m位子序列模式的出現(xiàn)頻數(shù)，記m位模式i1i2…im出現(xiàn)的頻數(shù)為vi1i2…im。對于所有的j(0≤j≤2m-1)，計算待檢測序列中出現(xiàn)的相對頻數(shù)。重復(fù)上述構(gòu)造過程，分別計算不同參數(shù)下ε′中所有的m位、m-1位、m-2位子序列模式的出現(xiàn)頻數(shù)。

（3）計算觀察到的m比特模式的頻數(shù)與預(yù)期模式頻數(shù)的匹配程度，即統(tǒng)計值。

（4）計算p-value值，設(shè)顯著性水平為α，如果p-value1≥α且p-value2≥α，則此序列通過序列檢測；否則，不通過檢測。

2.2 近似熵檢測

近似熵檢測與序列檢測方法相似，目的是比較序列中相鄰長度的重疊子序列出現(xiàn)的概率是否和正態(tài)分布的序列中出現(xiàn)的概率情況接近，以此來判斷序列是否通過檢測[13]。近似熵檢測的執(zhí)行流程如下：

（1）將長度為n的二元序列ε構(gòu)造成一個新的序列ε′，構(gòu)造方法與序列檢測相同，得到新序列ε′，新序列ε′的長度為n′=n+m-1。

（2）計算ε′中所有的2m個m位子序列模式出現(xiàn)頻數(shù)vi1i2…im，對所有的j(0≤j≤2m-1)，計算待檢測序列出現(xiàn)的相對頻數(shù)，計算相對頻數(shù)方法與序列檢測中一致。

（4）用m+1代替m，重復(fù)操作（1）至（3），計算得到。

（5）計算熵ApEn(m)和統(tǒng)計值V。

（6）計算p-value值，設(shè)顯著性水平為α，如果p-value≥α，則認為待檢序列通過近似熵檢測；否則，不通過檢測。

序列檢測和近似熵檢測方法相似，兩種檢測采用相同方法將待檢測序列構(gòu)造成新序列，并統(tǒng)計新序列中所有2m個m位子序列出現(xiàn)的頻數(shù)，兩種檢測計算得到的統(tǒng)計值均服從χ2分布。

3 兩種算法的效率分析與改進

傳統(tǒng)隨機性檢測過程中將待檢測序列存儲和處理為數(shù)組，根據(jù)不同檢測算法的描述對單個比特進行操作。例如在美國國家標準與技術(shù)研究院發(fā)布的隨機性檢測包sts2.1.2中采用一種通用的方法來計算擴張序列中所有可能出現(xiàn)的重疊mbit，首先定義具有2m+1-1個元素的數(shù)組變量p[]；將待檢測序列劃分成n m個非重疊子序列；定義局部變量k、i，再對每一個子序列，依次判斷每個單比特的值，若值為1，則令X=X+1，若值為0，則令X=2X+1；每個子序列計算結(jié)束后統(tǒng)計，令p[X-1]=p[X-1]+1，同時令k=1。這種對待檢測數(shù)據(jù)進行單比特處理的操作方式，不僅浪費CPU的字長，而且當檢測數(shù)據(jù)達到GB級時，這將是一個非常耗時的轉(zhuǎn)換過程。

通過分析兩種算法的執(zhí)行流程可知，序列檢測和近似熵檢測在計算過程中均統(tǒng)計了2m個m位子序列出現(xiàn)的頻數(shù)，因此對該過程的時間復(fù)雜度進行分析。當兩種檢測的空間復(fù)雜度相同時，采用一種特殊的數(shù)據(jù)結(jié)構(gòu)——二叉樹，分析該步驟的時間復(fù)雜度。首先，查找m位重疊子序列出現(xiàn)的頻數(shù)，就要構(gòu)造深度為m+1的滿二叉樹，滿二叉樹共有2m+1-1個節(jié)點，其節(jié)點中存放的信息是該節(jié)點代表的m位子序列出現(xiàn)的頻數(shù)。在統(tǒng)計序列中m位子序列出現(xiàn)的個數(shù)過程中，需要在有匹配信息時對應(yīng)節(jié)點內(nèi)容增加1，最后統(tǒng)計底層節(jié)點中存放的頻數(shù)。在統(tǒng)計頻數(shù)過程中每次向后移動1 bit，它的時間復(fù)雜度為O(mn)。因此，在空間復(fù)雜度相同的情況下，兩種檢測計算待檢測序列中相鄰長度重疊子序列頻數(shù)的時間復(fù)雜度為O(n)。

序列檢測和近似熵檢測在統(tǒng)計2m個m位子序列出現(xiàn)的頻數(shù)時，當參數(shù)m=2時，序列檢測計算2位、1位重疊子序列出現(xiàn)的頻數(shù)，近似熵檢測計算2位、3位重疊子序列出現(xiàn)的頻數(shù)；當參數(shù)m=5時，序列檢測計算5位、4位、3位重疊子序列出現(xiàn)的頻數(shù)，近似熵檢測計算5位、6位重疊子序列出現(xiàn)的頻數(shù)。在兩種檢測算法中存在大量重復(fù)的數(shù)據(jù)加載和計算過程，例如當m=2時，兩種檢測算法各執(zhí)行一次（1）、（2）操作，如果將兩種檢測的部分數(shù)據(jù)進行復(fù)用，可以大大縮減檢測時間，提高檢測效率。

綜上所述，采用序列檢測和近似熵檢測對大量數(shù)據(jù)進行檢測時，需要通過若干輪的比特轉(zhuǎn)換和逐比特的數(shù)值判斷和數(shù)學(xué)運算才能得到統(tǒng)計值，因此對大量數(shù)據(jù)進行兩種檢測的運算量較大，執(zhí)行效率較低，檢測過程非常耗時。在實際應(yīng)用中，多數(shù)國家的隨機性檢測標準中均包含序列檢測和近似熵檢測，因此需要加快兩種檢測的運行速度，以便快速篩查出不符合隨機性特征的序列。針對以上問題，本文采取下列方法快速實現(xiàn)兩種檢測算法：

（1）優(yōu)化字節(jié)處理方式，使用位級操作一次處理多個比特，提高CPU的利用率。

（2）根據(jù)檢測算法自身特點，按字節(jié)對m位可重疊子序列模式出現(xiàn)的頻數(shù)進行預(yù)處理，將字節(jié)處理與相對頻數(shù)計算相結(jié)合。

（3）根據(jù)兩種算法自身特點合并兩種檢測方法，減少數(shù)據(jù)重復(fù)加載過程，避免冗余的計算過程。

4 優(yōu)化算法

4.1 兩種檢測算法優(yōu)化

序列檢測和近似熵檢測在計算m位子序列模式出現(xiàn)的頻數(shù)時，由于參數(shù)m無法確定，導(dǎo)致無法對字節(jié)中的重疊子序列進行預(yù)處理，因此本文根據(jù)隨機性檢測經(jīng)驗定義m=2,5。

本文中記ε=ε1||ε2||…||εL，1≤L≤n/8 為多個字節(jié)組成的待檢測數(shù)據(jù)，其中εi，1≤i≤L。為區(qū)分兩種參數(shù)下統(tǒng)計m位子塊的相對頻數(shù)情況，記為序列中m位子塊出現(xiàn)的相對頻數(shù)，其中1≤i≤2m。當參數(shù)為m時，計算相對頻數(shù)的方式為：

優(yōu)化方法中#i的值采用創(chuàng)建字節(jié)表的方式獲取，當參數(shù)m=2 時，記B=(#i,t)表示計算ε=ε1||ε2||…||εL這新序列L個字節(jié)中m位子序列出現(xiàn)的頻數(shù)，當t為1時，B=(#i,1)表示字節(jié)ε1中00、01、10、11子序列出現(xiàn)的次數(shù)。B=(#i,t)可以通過查表統(tǒng)計，得到所有重疊子序列出現(xiàn)的頻數(shù)。在查詢字節(jié)表的過程中，如果上一次是使用序列中第i～i+7位進行查表的，那本次將使用序列中第i+7～i+14位進行查表。以參數(shù)m=2為例，序列檢測算法優(yōu)化過程如下：

算法1優(yōu)化實現(xiàn)序列檢測算法

輸入：待檢測序列ε=ε1||ε2||…||εL，1≤L≤n/8，參數(shù)m=2

輸出：序列是否通過序列檢測

1.初始化數(shù)據(jù)：#i=vi1i2…im=0

2.將序列最開始的m-1位添加到序列末端，構(gòu)成新序列ε′ ，即ε=ε1||ε2||…||εL→ε1||ε2||…||εL+m-1

3.L≤n/8時，查表計算B=(#i,t)，得到m位重疊子序列出現(xiàn)的頻數(shù)

4.重復(fù)步驟1～3，分別計算m-1、m-2位重疊子序列出現(xiàn)的頻數(shù)

6.計算p-value值，如果p-value≥0.01，序列通過檢測

近似熵檢測優(yōu)化過程中，參數(shù)m=2時，計算m位重疊子序列的方法與序列檢測相同，當參數(shù)轉(zhuǎn)換為m+1=3時，查詢字節(jié)表的過程中，如果上一次是使用序列中i～i+7位進行查表的，那本次將使用序列中第i+6～i+13位進行查表。以參數(shù)m=2為例，近似熵檢測算法優(yōu)化如下：

算法2優(yōu)化實現(xiàn)近似熵檢測算法

輸入：待檢測序列ε=ε1||ε2||…||εL，1≤L≤n/8，參數(shù)m=2

輸出：序列是否通過近似熵檢測

1.初始化數(shù)據(jù)：#i=vi1i2…im=0

2.將序列最開始的m-1位添加到序列末端，構(gòu)成新序列ε′ ，即ε=ε1||ε2||…||εL→ε1||ε2||…||εL+m-1

3.L≤n/8時，查表計算B=(#i,t)，得到m位重疊子序列出現(xiàn)的頻數(shù)

4.重復(fù)步驟1～3，計算m+1位重疊子序列出現(xiàn)的頻數(shù)

5.計算近似熵ApEn(m)和統(tǒng)計值

6.計算p-value值，如果p-value≥0.01，序列通過檢測

4.2 兩種檢測算法合并優(yōu)化

將兩種檢測算法合并的過程中，字節(jié)統(tǒng)計結(jié)果可以在兩種算法之間復(fù)用。當參數(shù)m=2時，兩種檢測同時需要統(tǒng)計2位子序列出現(xiàn)的次數(shù)；當參數(shù)m=5時，兩種檢測同時需要5位子序列出現(xiàn)的次數(shù)；當同時進行參數(shù)m=2，5時，近似熵檢測可復(fù)用序列檢測中2位、3位、5位子序列查表結(jié)果。極大地減少了兩種算法的運算量，提高兩種算法同時運行的效率。下面以參數(shù)m=2為例，提出兩種檢測合并后算法。

算法3優(yōu)化實現(xiàn)兩種合并算法

輸入：待檢測序列ε=ε1||ε2||…||εL，1≤L≤n/8，m=1

輸出：檢測結(jié)果

1.初始化數(shù)據(jù)：#i=vi1i2…im=0

2.將序列最開始的m-1位添加到序列末端，構(gòu)成新序列ε′ ，即ε=ε1||ε2||…||εL→ε1||ε2||…||εL+m-1

3.L≤n/8時，查表計算B=(#i,t)，得到m位重疊子序列出現(xiàn)的頻數(shù)

4.令m+=1，m<4 ，重復(fù)步驟1～3，分別計算出1位、2位、3位重疊子序列出現(xiàn)的頻數(shù)

5.計算序列檢測統(tǒng)計量?Ψ2m、?2Ψ2m

6.計算近似熵檢測ApEn(m)和統(tǒng)計值

7.計算p-value1、p-value2、p-value3值，如果p-value≥0.01，序列通過檢測

5 實驗結(jié)果

在實際應(yīng)用中產(chǎn)生隨機序列的方式主要分為兩類，一類是由偽隨機數(shù)發(fā)生器和密碼算法產(chǎn)生的偽隨機序列，偽隨機序列并不是真正意義上的隨機序列，它是由確定事件的概率組合產(chǎn)生的，因此偽隨機序列能夠被預(yù)測和重復(fù)。另一類是通過物理方法產(chǎn)生的真隨機序列，物理方法通過利用隨機“噪音”信號產(chǎn)生序列，例如熱力學(xué)噪聲、電噪音中提取隨機序列[14]。然而理論上經(jīng)典的物理過程在考慮所有環(huán)境變量的基礎(chǔ)上是可以模擬的，唯獨量子物理過程產(chǎn)生的隨機序列是完全真隨機序列。在量子隨機數(shù)發(fā)生器中，量子是無法繼續(xù)分割的，量子組成了光子、原子、電子，它是構(gòu)成物質(zhì)的最小微粒。量子隨機數(shù)具有隨機性主要原因是量子事件中測量坍縮造成的不確定性和真空起伏導(dǎo)致的隨機噪音，量子事件具有不確定性，量子隨機數(shù)發(fā)生器利用這一特性產(chǎn)生隨機序列[15]。因此，為保證實驗數(shù)據(jù)可以通過兩種檢測，實驗采用量子隨機數(shù)發(fā)生器產(chǎn)生的真隨機數(shù)。

本實驗的測試平臺情況如表1所示。

表1 測試平臺信息

為更準確地說明本文提出的算法的效率，設(shè)計實驗測試優(yōu)化前后算法的執(zhí)行效率。測試數(shù)據(jù)是利用量子隨機數(shù)發(fā)生器生成的109bit的隨機數(shù)據(jù)，將隨機數(shù)據(jù)按106bit規(guī)格劃分為1 000條樣本數(shù)據(jù)。對比實驗采用美國NIST官網(wǎng)發(fā)布的sts-2.1.2檢測包，該檢測包僅適用于Linux系統(tǒng)，為保證實驗條件的一致性，本文按照該檢測包代碼思想，在Windows系統(tǒng)中實現(xiàn)兩種檢測算法。優(yōu)化后實驗是對待檢測序列按照上述優(yōu)化算法，分別實現(xiàn)參數(shù)m=2及m=5時的兩種檢測及合并后的檢測，所有的算法均采用標準C實現(xiàn)，計時單位為ms。

參數(shù)m=2,5時選取實驗中500條樣本，原序列檢測和近似熵檢測以及優(yōu)化后的算法1、算法2、算法3運行時間如圖1～4所示。

圖1 m=2時原算法耗時間

圖2 m=2時優(yōu)化算法耗時間

圖3 m=5時原算法耗時間

圖4 m=5時優(yōu)化算法耗時間

實驗結(jié)果如表2所示，參數(shù)m=2時，序列檢測優(yōu)化后速度提升了29.72倍，近似熵檢測優(yōu)化后速度提升了27.58倍；參數(shù)m=5時，序列檢測優(yōu)化后速度提升了30.02倍，近似熵檢測優(yōu)化后速度提升了24.14倍；參數(shù)m=2及m=5時兩種檢測合并后速度分別提升了40.12倍、45.23倍。

表2 算法性能對比

6 結(jié)束語

本文對NIST隨機性檢測標準中的序列檢測和近似熵檢測進行快速實現(xiàn)。通過對字節(jié)的預(yù)處理、字節(jié)統(tǒng)計與相對頻數(shù)統(tǒng)計相結(jié)合、頻數(shù)統(tǒng)計優(yōu)化復(fù)用等方法，使得序列檢測和近似熵檢測速度最高分別提升30.02倍、27.58倍，兩種檢測合并后整體速度最高提升45.23倍。

本文提出的序列檢測和近似熵檢測優(yōu)化方案，有利于兩種檢測方法的推廣和應(yīng)用。隨機性檢測標準中還有很多其他檢測項可以做性能優(yōu)化及算法合并，這將是以后研究工作的一個方向。