Maurer通用統計檢測的優化實現研究*

康紅娟，楊先偉，張文科

（1.四川長虹電器股份有限公司，四川 成都 610041；2.無錫職業技術學院，江蘇 無錫 214121；3.成都衛士通信息產業股份有限公司，四川 成都 610041）

0 引 言

習近平主席在2014年指出，沒有網絡安全就沒有國家安全，網絡安全已經上升到國家戰略。網絡安全主要包括信息的機密性、完整性、可鑒別性、不可抵賴性以及訪問控制等。實現這些的重要手段是密碼技術，而眾多密碼技術的一個共同之處是要實現隨機化，如密鑰、初始化向量、數字簽名等都必須是密碼學安全的隨機數。由此可見，隨機數不論在密碼工程還是在密碼理論方面，都有著舉足輕重的地位和作用。隨機性檢測是采用概率統計的方法對隨機數發生器等生成的二元序列進行分析和測試，判斷待檢序列是否在統計上難以與真隨機數區分開來。不同的隨機性檢測算法從不同的角度分析測試待檢序列與真隨機序列的差異。隨機性檢測算法經過多年的發展已經取得了豐碩的研究成果，目前有大量的隨機性檢測算法和檢測工具，而且有很多新的隨機性檢測算法還在源源不斷地涌現。美國國家標準與技術研究院（National Institute of StandardsAnd Technology，NIST）發布并反復修訂了文檔SP 800-22[1]，其中共建議了15種用于隨機性測試的統計檢驗方法。德國以此為基礎發布了BSIAIS 30規范[2]。我國國家密碼管理局于2009年頒布了我國的隨機性檢測規范[3]，其中建議了15種隨機性測試的統計檢驗方法。此外，還有很多別的著名檢測標準和工具，如Diehard、TestU01、ENT和CryptX等。

隨機性檢測在實際應用中有著廣泛應用，如測評按照特定標準生成的偽隨機數據；檢測密碼算法生成的數據流，如分組算法生成的數據流[4]；以雜湊算法如我國的SM3雜湊算法[5]為核心生成的數據流。這些檢測可以為算法分析者提供幫助，減少工作強度，同時能夠檢測出其他測試方法難以檢出的安全隱患。

NIST統計測試套件（NIST STS）[6]實現了NIST隨機性檢測規范描述的所有檢測項目。傳統的檢測通常使用此NIST STS隨機性測試代碼和工具進行檢測，但其檢測效率非常低。因此，大量的學者進行隨機性檢測規范的各個檢測項的快速現實研究。比如，撲克檢測的快速實現研究[7]、單比特檢測和塊內頻數檢測的優化實現研究[8]。也有學者設計新的統計測試方法作為隨機性檢測規范的補充[9]，還有學者研究統計測試算法的基于GPU的并行實現，并構建并行實現的統計測試框架[10]，以及分析線性復雜度檢測、B-M算法優化檢測[11]等。

SuciuA等[12]采用基于字節處理的方式，顯著改善了Maurer通用統計檢測的執行效率。文獻[13-15]在此研究成果的基礎上，對實現方式和代碼做了進一步優化，使得效率提升了42.2%。本文在文獻[13]的基礎上，對其中的Maurer通用統計檢測進行多角度綜合優化，從整體上改善Maurer通用統計檢測的效率，以提升整個國密隨機性檢測的檢測速度。

文章結構組織如下：第1節簡單介紹Maurer通用統計檢測的執行流程；第2節分析Maurer通用統計檢測的思路，并討論進一步優化的可行性；第3節提出Maurer通用統計檢測的快速實現算法；第4節測試優化算法的檢測效率和速度提升情況；最后總結全文。

1 Maurer通用統計檢測簡介

NIST的隨機性檢測規范和我國的隨機性檢測規范都有15項檢測，其中兩者有11個相同的檢測項，而Maurer通用統計檢測是其中一項。此外，我國隨機性檢測規范有4個專有的檢測項，NIST的隨機性檢測規范也有4個專有的檢測項。

Maurer通用統計檢測主要檢測待檢序列能否被無損壓縮。如果待檢序列能被顯著壓縮，則認為該序列是不隨機的，因為隨機序列是不能被顯著壓縮的。Maurer通用統計檢測可以用來檢測待檢序列多個方面的特征，但并不意味著Maurer通用統計檢測是幾個檢測的拼裝。相反，Maurer通用統計檢測采用了和別的檢測完全不同的方法。一個序列可以通過Maurer通用統計檢測，當且僅當這個序列是不可壓縮的。

記 ε=ε1,ε2…εn為長度是 n 比特的待檢二元序列，εi=(0,1)，1≤i≤n。我國的隨機性檢測規范取樣本長度n為1×106bit。

α為顯著水平。我國的隨機性檢測規范規定，顯著水平α=0.01。

erfc是余差函數，定義為：

實際使用中，通常采用字節來存儲隨機序列。對這種以字節表示的隨機序列，其Maurer通用統計檢測的檢測流程描述如下[3,13]。

算法1：Maurer通用統計檢測算法

輸入：n比特（ n ≡ 0 mod8）的待檢二元序列ε=ε1,ε2…εn以字節表示為 ε=B0B1B2…BN-1，N=n/8。

輸出：通過或者不通過Maurer通用統計檢測

步驟1：將待檢序列分成兩個部分——初始序列和測試序列。初始序列和測試序列分布包括Q個和k個L位的非重疊子序列，多余的位舍棄，即不夠組成一個完整的L位子序列的位舍棄，其中：

我國隨機性檢測規范規定L=7、Q=1 280。

步驟2：針對初始序列創建一個表T，它以L位值為表中的索引值，Tj(1≤j≤2L)表示表中第j個元素的值。計算：

其中j是初始序列中第i個L位子序列的十進制表示。

步驟3：計算sum。

其中，遍歷完第i(Q+1≤i≤Q+K)個L位子序列后應更新Tj=i。

步驟4：計算V值。

步驟5：計算P值。

步驟6：如果P-value≥α，則認為待檢序列通過離散傅立葉檢測。

Maurer通用統計檢測的示意圖見圖1，其中描述了初始序列、測試序列和末尾丟棄數據等。

圖1 Maurer通用統計檢測

2 優化實現思路

Maurer通用統計檢測需要的數據量很大，將序列分成長度為L的子序列，然后將待檢序列分成兩部分——初始序列和檢測序列。初始序列包括Q個子序列，Q應該大于等于10×2L；檢測序列包括K個子序列，K應該大于等于1 000×2L。L的取值范圍為1≤L≤16，L取不小于6的值。Q的取值應該保證L位子序列的所有2L個模式都在初始序列中至少出現一次。

從頭開始遍歷初始序列，找到每一個L位模式在初始序列中最后出現的位置（塊號）。如果一個L位模式在初始序列中沒有出現，那么將其位置設置為0。此后，從頭開始遍歷檢測序列，每一次都會得到一個L位子序列，計算這個子序列所在的位置與其前面最后一次出現的位置差也就是塊號相減，稱相減結果為距離，再對距離求以2為底的對數，最后將所有求對數的結果相加。這樣就可以得到統計值：

統計值fn應該漸進服從單邊正態分布。我國隨機性檢測規范采用式（8）計算該期望值。

fn的期望值是隨機變量log2G的期望值，其中G=GL是參數為1-2-L的幾何分布。

σ的計算方式為：

這里c(L,K)是一個影響因子。我國隨機性檢測規范采用式（10）來估計：

統計值V=(Fn-E(L))/σ應該服從標準正態分布。

NIST統計測試套件（NIST STS）實現了NIST的隨機性檢測規范描述的所有檢測項目，但是其中采用基于比特的處理方式使得Maurer通用統計檢測的效率較低。文獻[12]采用基于字節處理的方式顯著改善了Maurer通用統計檢測的執行效率。文獻[13-15]在此基礎上對代碼做進一步優化，使得效率得到了進一步改善。

對以字節表示的待檢序列，文獻[13]優化方案中還存在如下不足和可以優化改進之處。

（1）該方案中雖考慮了以字節為基礎進行處理，但沒有充分考慮基于字節的優化，丟棄了很多可用的數據。

（2）步驟3中要執行K個log2D的計算，當n=1 000 000、L=7、Q=1 280時，K=141 577。大量的對數計算，是影響檢測效率的另一個重要因素。

本節在文獻[13]優化方案的基礎上，對以字節表示的待檢序列提出Maurer通用統計檢測的如下優化改進思想。先定義如下名詞和記號以方便描述。

定義1：N字節待檢序列中任意連續的L個字節稱為一個宏塊，記為MB。

性質1：N字節待檢序列ε=B0B1B2…BN-1按連續L個字節的宏塊劃分為：

①初始序列的宏塊為：

在隨機性檢測規范中，L=7、Q=1 280。所以，初始序列按宏塊劃分無多余字節。

②測試序列的宏塊為：

測試序列末尾共有NmodL字節，BN-Nmod7,…,BN-1無法湊足一個完整宏塊。對n=1 000 000Bit的二元序列而言，測試序列末尾剩余1Byte無法湊足一個完整宏塊。

性質2：每個宏塊MBi,0≤i≤[N/L]都可拆分為8個L位非重疊子序列Ei,j,0≤i≤[N/L],0≤j＜8。

在不會造成歧義時，仍將非重疊子序列Ei,j的十進制表示為Ei,j。

Maurer通用統計檢測的優化改進思想描述如下。

（1）無論是初始序列還是測試序列，按連續L個字節為一個宏塊進行劃分，每個宏塊拆分為8個L比特非重疊子序列。對每個宏塊的8個L比特子序列執行原算法的步驟2和步驟3，減少數據的加載以及加載數據被丟棄的情況。

（2）在執行步驟3時，為了減少對數的計算，將sum的計算簡化為先對這8個子序列分別計算其十進制數與Tj的差值即距離，然后將這8個距離相乘，最后再對乘積計算對數，即采用以乘法換對數的方式。

3 優化算法

N字節的待檢序列的優化實現的Maurer通用統計檢測算法描述如下。

算法2：優化實現的Maurer通用統計檢測算法

輸入：N字節的待檢序列以字節表示為ε=B0B1B2…BN-1。

輸出：通過或者不通過Maurer通用統計檢測

步驟1：初始化表值。將初始序列的每個宏塊MBi,0≤i＜Q/8執行如下步驟：

（1）MBi拆分為8個L位非重疊子序列Ei,j，0≤j＜8；

（2）初始化表T：

步驟2：初始化累加和sum=0。對測試序列的每個宏塊MBi,Q/8≤i＜[N/L]執行如下步驟：

（1）將MBi拆分為8個L位非重疊子序列Ei,j，0≤j＜8；

（2）計算距離Dj=Li+j+1-T [Ei,j],0≤j＜8；

（3）更新表值T [Ei,j]=Li+j+1,0≤j＜8；

（5）更新累加和sum=sum+log2D。

步驟3：更新累加和sum。對測試序列的末尾不能構成完整宏塊的數據Bi，N-NmodL≤i≤N-1，執行如下步驟：

（1）依次獲取L位非重疊子序列Ei；

（2）更新累加和sum=sum+log2(i-T)；

（3）更新表值T [ j]=i。

步驟4：計算V值。

步驟5：計算P值。

步驟6：如果P-value≥α，則認為待檢序列通過離散傅立葉檢測。

考慮初始序列的計算復雜度，文獻[13]方案需要Q次數據加載，但其實現中以UINT32加載且存在內存邊界不對齊的情況，會導致數據加載效率降低。優化方案中，每L個字節的數據拆分8個L比特非重疊子序列，數據加載為L次字節加載，不存在內存邊界不對齊的情況?？紤]測試序列的計算復雜度，文獻[13]方案計算sum時需要2K次數據加載、2K次加減法和K次對數。優化方案將L個字節的數據拆分8個LBit非重疊子序列時，數據加載次數同上；此外，8個子序列對數的計算次數也從原來的8次降低為1次，但需額外的8次乘法。綜上，文獻[13]方案和本文優化方案的計算量對比如表1所示。

表1 兩種方案的運算量對比

4 實驗與結果

本節對優化算法進行效率測試，并與文獻[13]算法、NIST STS軟件包的執行效率進行對比分析。

本文使用的測試平臺信息如表2所示，所有測試均在此平臺下進行。

表2 測試平臺信息

測試使用數據為SM3算法生成的偽隨機數，按1×106bit為一個樣本生成1 000個樣本。

測試方法采用歐洲estream算法競賽的速度測試模型的簡化版本。主要執行流程為：反復測試待測代碼段的耗時C次，并保存每次的耗時值T [i]，1≤i≤C。將耗時值序列按從大到小（或從小到大）的順序排列，取新序列的中值作為本段代碼的統計耗時值。本文:實驗中將測試次數設置為51。測試使用的時間計數器為CPU頻率計時器，直接調用納秒級精度的RDTSC匯編指令，在Windows環境下調用函數rdtsc()。

Maurer通用統計檢測進行檢測的執行效率，如表3所示。

表3 優化前后的執行效率

三種Maurer通用統計檢測的檢測速度的柱狀圖如圖2所示。

圖2 優化前后的算法執行效率

三種Maurer通用統計檢測的檢測速度對比值，如表4所示。

表4 優化前后的執行效率對比

從統計數據可以看出，Maurer通用統計檢測的執行效率有了明顯改善。文獻[13]算法檢測速度是NIST STS檢測速度的16.888倍，而本文算法檢測速度為NIST STS的速度的29.127倍?？梢?，本文算法檢測速度比文獻[13]算法檢測速度提升了72.5%。

5 結 語

本文對我國隨機性檢測規范和NIST隨機性檢測規范都采用的Maurer通用統計檢測算法進行了優化實現，通過對整個宏塊做一次性加載處理、減少對數計算等方法，優化改進檢測算法。實驗結果表明，Maurer通用統計檢測的執行效率明顯改善，本文算法檢測速度為NIST STS的速度的29.127倍，同時比文獻[13]算法檢測速度提升了72.5%。NIST和我國的隨機性檢測規范還有很多檢測項，其中大部分都還有優化提升的空間，將是今后工作的一個研究方向。