王 超，溫 濤，段冉陽

(中國電子信息產(chǎn)業(yè)集團有限公司第六研究所，北京 100083)

0 引言

近年來，我國信息化建設(shè)步伐不斷加快，移動通信系統(tǒng)、衛(wèi)星通信系統(tǒng)和物聯(lián)網(wǎng)系統(tǒng)飛速發(fā)展，這些系統(tǒng)中的敏感信息需要密碼技術(shù)來保證信息安全。盡管密碼安全并不等于信息安全，但是如果沒有密碼安全，對整個系統(tǒng)安全而言將是災(zāi)難性的。因此，從這個角度來看，密碼安全是信息安全的基石，研究密碼安全對信息安全具有重要意義。

對輸出的序列進行隨機性檢測[1-3]是評價密碼安全的一個重要手段。美國國家標(biāo)準(zhǔn)與技術(shù)研究所(National Institute of Standards and Technology，NIST)發(fā)布的NIST統(tǒng)計檢測程序sts-2.1.2(The NIST Statistical Test Suite)[4]，包括15種隨機性檢測方法和9種偽隨機數(shù)生成器。15種隨機性檢測方法[5-6]分別從不同的角度刻畫輸出序列的偽隨機性質(zhì)。

本文首先介紹NIST統(tǒng)計檢測程序，然后闡述NIST統(tǒng)計檢測程序的不足以及如何改進。這些改進包括增加容忍度概念，從而擴展檢測程序框架；增加統(tǒng)計量T，從而非重疊模板匹配檢驗輸出唯一結(jié)論。

1 統(tǒng)計學(xué)基礎(chǔ)

檢測密碼算法輸出序列的隨機性，即檢驗其是否真隨機或與真隨機之間的差距，通常采用統(tǒng)計學(xué)中假設(shè)檢驗方法。

首先，視密碼算法輸出序列為二進制序列，是僅由0、1組成的二元序列，進行隨機性假設(shè)。假設(shè)該序列是隨機的，這個假設(shè)稱為源假設(shè)或零假設(shè)，記為H0。與源假設(shè)相反的假設(shè)，即這個序列是不隨機的，稱為備擇假設(shè)，記為H1。已知真隨機序列上構(gòu)造出的某統(tǒng)計量符合某一特定分布，那么通過源假設(shè)，即假設(shè)二元序列是隨機的，可知此二元序列的這個樣本統(tǒng)計量也應(yīng)該服從這個特定分布。分布可以是均勻分布、開方分布等。

其次，每一個檢驗可能犯兩種類型的錯誤，如表1所示。

在樣本容量固定時，犯這兩類錯誤的概率是相互制約的，無法使得它們同時盡可能地小。在檢驗中錯誤地判斷某一個隨機序列為非隨機序列的概率(即表1中的第一類錯誤概率)，稱為顯著性水平，用a來表示。

表1 統(tǒng)計檢驗錯誤概率

判斷源假設(shè)成立的方法有2類：門限值方法和Pvalue方法。

門限值方法：按指定的顯著性水平a，查指定分布的分位數(shù)表，得到臨界值，確定拒絕域。計算二元序列的樣本統(tǒng)計量，如果統(tǒng)計量落入源假設(shè)的拒絕域，則拒絕H0，否則接受H0。

Pvalue方法：Pvalue值為1代表完全隨機序列，值為0代表完全非隨機序列。于是，若Pvalue≥a，則接受H0，否則拒絕H0。

一般直接與假設(shè)總體分布對照時使用門限值方法，而與補余誤差函數(shù)(Complementary Error Function)、不完全伽馬函數(shù)(Incomplete Gamma Function)對照時使用Pvalue方法。NIST統(tǒng)計檢測程序采用Pvalue方法。

顯著性水平a通常取值為0.1，0.05，0.01，0.005，NIST統(tǒng)計檢測程序中顯著性水平的缺省值為0.01。

2 NIST統(tǒng)計檢測程序

NIST發(fā)布的NIST統(tǒng)計檢測程序sts-2.1.2，包含頻數(shù)檢驗、塊內(nèi)頻數(shù)檢驗、游程檢驗、塊內(nèi)最長游程檢驗、二元矩陣秩檢驗、離散傅里葉檢驗、非重疊模板匹配檢驗、重疊模板匹配檢驗、Maurer通用檢驗、線性復(fù)雜度檢驗、重疊子序列檢驗、近似熵檢驗、累加和檢驗、隨機游動檢驗、隨機游動狀態(tài)頻數(shù)檢驗，共計15種隨機性檢測方法。

(1)頻數(shù)檢驗

單比特頻數(shù)檢驗簡稱為頻數(shù)檢驗，是觀測1在二元序列中所占的比例，考查其是否與真隨機序列中的1所占比例近似相同。1在真隨機序列中占比為1/2。頻數(shù)檢驗的參數(shù)是二元序列的比特長度和二元序列本身。檢驗過程中使用了補余誤差函數(shù)。頻數(shù)檢驗要求二元序列比特長度至少為100。

(2)塊內(nèi)頻數(shù)檢驗

塊內(nèi)頻數(shù)檢驗是觀測1在所有非重疊M比特長子序列(稱為塊)中所占的比例，真隨機序列中占比為M/2。塊內(nèi)頻數(shù)檢驗的參數(shù)是二元序列的比特長度、分組比特長度M和二元序列本身。檢驗過程中使用了不完全伽馬函數(shù)。塊內(nèi)頻數(shù)檢驗要求二元序列比特長度至少為100，分組比特長度至少為20且分組比特長度大于二元序列比特長度的1%。從而分組的塊數(shù)(即二元序列的比特長度/分組比特長度M向下取整)小于100。

(3)游程檢驗

游程檢驗是觀測二元序列中游程(即0游程和1游程)總數(shù)是否與相應(yīng)真隨機序列游程總數(shù)接近。0游程是指二元序列中由連續(xù)的0組成的子序列，并且此子序列的前導(dǎo)與后繼元素都是1;1游程是指二元序列中由連續(xù)的1組成的子序列，并且此子序列的前導(dǎo)與后繼元素都是0。游程檢驗展示了二元序列中0游程和1游程之間的距離(即振幅)與真隨機序列相比是否太大或太小。游程檢驗的參數(shù)是二元序列的比特長度和二元序列本身。檢驗過程中使用了補余誤差函數(shù)。游程檢驗要求二元序列比特長度至少為100。

(4)塊內(nèi)最長游程檢驗

塊內(nèi)最長游程檢驗是觀測非重疊M比特長塊中最長游程長度是否與真隨機序列中最長游程長度近似致。塊內(nèi)最長游程檢驗的參數(shù)是二元序列的比特長度、分組比特長度M和二元序列本身。其中分組比特長度M由預(yù)設(shè)算法決定，即當(dāng)二元序列比特長度小于6 272時取值為8，當(dāng)小于750 000時取值為128，當(dāng)大于等于750 000時取值為10 000。檢驗過程中使用了不完全伽馬函數(shù)。塊內(nèi)最長游程檢驗要求二元序列比特長度至少為128。

(5)二元矩陣秩檢驗

二元矩陣秩檢驗是觀測二元序列中分離子矩陣的秩是否與真隨機序列的情況接近。二元矩陣秩檢驗的參數(shù)包括二元序列的比特長度和二元序列本身。NIST統(tǒng)計檢測程序中約定子矩陣為32行32列。檢驗過程中使用了不完全伽馬函數(shù)。二元矩陣秩檢驗要求二元序列比特長度至少為38 912(38×子矩陣行數(shù)×子矩陣列數(shù))。

(6)離散傅里葉檢驗

離散傅里葉檢驗是觀測二元序列進行離散傅里葉變換后峰值的數(shù)目是否與真隨機序列的情況接近。離散傅里葉檢驗的參數(shù)包括二元序列的比特長度和二元序列本身。檢驗過程中使用了補余誤差函數(shù)。離散傅里葉檢驗要求二元序列比特長度至少為1 000。

(7)非重疊模板匹配檢驗

非重疊模板匹配檢驗，是觀測二元序列中與預(yù)先指定的m(m取值為9或10，本文采用9)比特長非周期二元序列匹配次數(shù)是否與真隨機序列的情況接近。這樣的m比特長非周期二元序列有多個，由模板定義，NIST統(tǒng)計檢測程序中指定148組9比特二元序列。非重疊是指當(dāng)發(fā)現(xiàn)匹配序列后，檢測窗口跳至匹配序列整體之后再繼續(xù)檢測。非重疊模板匹配檢驗的參數(shù)包括二元序列的比特長度和二元序列本身。本文的非重疊模板匹配檢驗由148個子檢驗組成。檢驗過程中使用了不完全伽馬函數(shù)。NIST統(tǒng)計檢測程序中約定分組塊數(shù)N=8，分組比特長度M=n/N。

(8)重疊模板匹配檢驗

重疊模板匹配檢驗是觀測二元序列中與預(yù)先指定的m比特長非周期二元序列(NIST統(tǒng)計檢測程序中約定為m個比特1)匹配次數(shù)是否與真隨機序列的情況接近。重疊是指當(dāng)發(fā)現(xiàn)匹配序列后，檢測窗口跳移至下一比特，然后繼續(xù)檢測。重疊模板匹配檢驗的參數(shù)包括二元序列的比特長度和二元序列本身。檢驗過程中使用了不完全伽馬函數(shù)。重疊模板匹配檢驗中每一個模板的比特長度m取值為9或10(本文采用9)，二元序列比特長度至少為106，NIST統(tǒng)計檢測程序中約定自由度K=5(考查0次、1次、…、5次及以上，共6類)，分組比特長度M=1 032，分組的塊數(shù)N=n/M。

(9)Maurer通用檢驗

Maurer通用檢驗是考查二元序列在沒有信息損失的條件下能否進行顯著壓縮。真隨機序列不能被顯著壓縮。Maurer通用檢驗的參數(shù)包括二元序列的比特長度和二元序列本身，內(nèi)部分組長度L、初始分組數(shù)Q、檢測分組數(shù)K由算法依據(jù)二元序列的比特長度計算得到。檢驗過程中使用了補余誤差函數(shù)。Maurer通用檢驗要求二元序列比特長度至少為387 840。

(10)線性復(fù)雜度檢驗

線性復(fù)雜度檢驗是觀測二元序列對應(yīng)的線性反饋移位寄存器(LFSR)的長度(稱為線性復(fù)雜度)是否足夠大。真隨機序列的線性復(fù)雜度較大。線性復(fù)雜度檢驗的參數(shù)是二元序列的比特長度、分組比特長度M和二元序列本身。NIST統(tǒng)計檢測程序中約定自由度K=6。檢驗過程中使用了不完全伽馬函數(shù)。線性復(fù)雜度檢驗中二元序列比特長度至少為106，分組比特長度M介于500與5 000之間，本文取M=500。

(11)重疊子序列檢驗

重疊子序列檢驗是觀測二元序列中m比特長重疊子序列每一種模式(共2m種)的出現(xiàn)次數(shù)是否接近。真隨機序列中各模式出現(xiàn)次數(shù)是近似一樣的。重疊子序列檢驗的參數(shù)是二元序列的比特長度n、分組比特長度M和二元序列本身。檢驗過程中使用了不完全伽馬函數(shù)。重疊子序列檢驗中m+2小于log2n向下取整。本文取n=106，m=16。

(12)近似熵檢驗

近似熵檢驗是觀測二元序列中m比特長重疊子序列每一種模式(共2m種)的出現(xiàn)次數(shù)與m+1比特長重疊子序列每一種模式的出現(xiàn)次數(shù)之間的關(guān)系。近似熵檢驗的參數(shù)是二元序列的比特長度n、分組比特長度M和二元序列本身。檢驗過程中使用了不完全伽馬函數(shù)。近似熵檢驗中m+5小于log2n向下取整。本文取n=106，m=12。

(13)累加和檢驗

累加和檢驗首先將二元序列中0映射為-1，1映射為1，然后正序或逆序依次計算累加和，觀測整個過程中正序或逆序的累加和最大值(統(tǒng)稱為最大偏移)，最后考查累加和最大值是否過大。真隨機序列的累加和最大值接近0。累加和檢驗的參數(shù)是二元序列的比特長度n和二元序列本身。檢驗過程中使用了不完全伽馬函數(shù)。累加和檢驗中二元序列比特長度至少為100。

(14)隨機游動檢驗

隨機游動檢驗，首先將二元序列中0映射為-1，1映射為1，然后正序依次計算累加和，在累加和組成的序列中首尾添加0組成新序列，0將新序列分割成數(shù)段。約定自由度K=8，即累加和劃分為-4(含<-4)、-3、-2、-1、1、2、3、4(含>4)，共8類。最后記錄每一段內(nèi)各個累加和分類的出現(xiàn)次數(shù)，并考查其與真隨機序列情況是否類似。隨機游動檢驗由K個子檢驗組成，隨機游動檢驗的參數(shù)是二元序列的比特長度n和二元序列本身。檢驗過程中使用了不完全伽馬函數(shù)。隨機游動檢驗中二元序列比特長度至少為106。

(15)隨機游動狀態(tài)頻數(shù)檢驗

隨機游動狀態(tài)頻數(shù)檢驗，首先將二元序列中0映射為-1，1映射為1，然后正序依次計算累加和。約定自由度K=18，即累加和劃分為-9(含<-9)、-8、…、-1、1、…、8、9(含>9)，共18類。最后記錄各個累加和分類的出現(xiàn)次數(shù)，并考查其與真隨機序列情況是否類似。隨機游動狀態(tài)頻數(shù)檢驗由K個子檢驗組成，隨機游動狀態(tài)頻數(shù)檢驗的參數(shù)是二元序列的比特長度n和二元序列本身。檢驗過程中使用了補余誤差函數(shù)。隨機游動狀態(tài)頻數(shù)檢驗中二元序列比特長度至少為106。

3 NIST統(tǒng)計檢測程序的改進

NIST統(tǒng)計檢測程序存在的不足和相應(yīng)改進如下：

(1)檢測結(jié)果存儲于多個文件之中

NIST統(tǒng)計檢測程序的檢測結(jié)果存儲于多個文件之中，不方便觀察。本文通過增加標(biāo)識，將數(shù)十個日志文件整合至一個日志文件，便于檢索。同時增加顯示級別控制，根據(jù)詳細、摘要、報警等不同需求，智能顯示內(nèi)容。

(2)基于傳統(tǒng)的命令行方式交互

本文裁剪命令行交互功能，增加讀配置文件方式實現(xiàn)參數(shù)自動讀入功能，從而支持對多套參數(shù)進行檢測，為支持自動化功能奠定基礎(chǔ)。

(3)不支持自動化功能

NIST統(tǒng)計檢測程序的檢測結(jié)果需人工觀察日志文件，缺少自動化功能。本文通過遞歸返回檢測結(jié)果，自動判斷源假設(shè)是否成立，實現(xiàn)自動化功能。同時，為支持批量檢測功能提供支撐。

(4)不支持批量檢測功能

待檢測序列由密碼算法加載偽隨機產(chǎn)生的密鑰和初始向量產(chǎn)生，為降低密鑰和初始向量的選取對密碼算法輸出檢驗判斷產(chǎn)生的影響，需要進行多次檢測，并給出整體結(jié)論，即檢測程序需要支持批量檢測功能。

下面以AES算法進行頻數(shù)檢驗和塊內(nèi)頻數(shù)檢驗為例，說明容忍度的意義。

給定容忍度=0.02，顯著性水平=0.01。令明文長度為AES的分組長度，即16字節(jié)，明文值為全0。使用偽隨機方式產(chǎn)生密鑰，對明文迭代使用AES算法加密，將每次AES算法加密后的密文組成一個輸出序列，輸出序列的長度為10 240比特，遠大于進行頻數(shù)檢驗和塊內(nèi)頻數(shù)檢驗的最小長度100比特。然后對此輸出序列進行NIST統(tǒng)計檢測程序中的頻數(shù)檢驗和塊內(nèi)頻數(shù)檢驗，分別得到一個頻數(shù)檢驗Pvalue值和一個塊內(nèi)頻數(shù)檢驗Pvalue值。其中，塊內(nèi)頻數(shù)檢驗中塊長度取為128比特，滿足以下要求：128>20、128>10 240/100和10 240/128<100。使用偽隨機方式反復(fù)產(chǎn)生65 536次密鑰，進行65 536次上述頻數(shù)檢驗和塊內(nèi)頻數(shù)檢驗。這些檢驗中共有645次頻數(shù)檢驗的Pvalue小于0.01，609次塊內(nèi)頻數(shù)檢驗的Pvalue小于0.01。因為645/65 536<0.02，609/65 536<0.02，所以在容忍度=0.02，顯著性水平=0.01的前提下，認為AES算法輸出的序列是隨機的。

(5)非重疊模板匹配檢驗

考查NIST統(tǒng)計檢測程序中非重疊模板匹配檢驗，當(dāng)模板長度取9時，模板共有148個。因此非重疊模板匹配檢驗共有148個子檢驗。NIST統(tǒng)計檢測程序沒有將這148個檢驗結(jié)果進一步整合，如果1項子檢驗不通過就認為整體檢驗不通過，則整體檢驗過于嚴格，ZUC流密碼算法[7]、Snow流密碼算法[8]、Sosemanuk流密碼算法[9]都不能通過這種嚴格的檢驗。

本文構(gòu)造一個統(tǒng)計量如下：

T=

通過148個子檢驗結(jié)果衡量整體非重疊模板匹配檢驗。其中t1為1項子檢驗失敗次數(shù)，t2為2項子檢驗失敗次數(shù)，…，t6為6項及6項以上子檢驗失敗次數(shù)。此統(tǒng)計量體現(xiàn)了子檢驗失敗次數(shù)越多越嚴重。

下面分別對ZUC流密碼算法、Snow流密碼算法、Sosemanuk流密碼算法和AES分組密碼算法進行非重疊模板匹配檢驗，其中二元序列比特長度為106，模板的比特長度為9，檢驗次數(shù)為1 024，檢驗結(jié)果如表2所示。從表中最后一列值可以看出統(tǒng)計量的設(shè)計是合理的。

表2 非重疊模板匹配檢驗統(tǒng)計量表

(6)其他優(yōu)化

裁剪NIST統(tǒng)計檢測程序中偽隨機數(shù)生成器功能，增加基于除法電路的線性反饋移位寄存器。相較于NIST統(tǒng)計檢測程序中復(fù)雜的偽隨機數(shù)生成器，線性反饋移位寄存器的輸出具有易于理論推導(dǎo)的更簡單形式和更良好的統(tǒng)計學(xué)特性[10]，適合用于本文中密鑰和初始向量的隨機性構(gòu)造。

4 結(jié)論

本文首先詳細介紹NIST統(tǒng)計檢測程序，并描述了其存在的不足，然后以AES算法進行多次頻數(shù)檢驗和塊內(nèi)頻數(shù)檢驗為例，闡述了引入容忍度的意義，最后以ZUC流密碼算法、Snow流密碼算法、Sosemanuk流密碼算法和AES分組密碼算法為例，實驗證明了本文構(gòu)造的T統(tǒng)計量是合理的，從而進行非重疊模板匹配檢驗后，可得出唯一結(jié)論。