NIST隨機性檢測方法研究

王 超，溫 濤，段冉陽

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

0 引言

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

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

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

1 統計學基礎

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

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

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

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

表1 統計檢驗錯誤概率

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

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

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

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

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

2 NIST統計檢測程序

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

(1)頻數檢驗

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

(2)塊內頻數檢驗

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

(3)游程檢驗

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

(4)塊內最長游程檢驗

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

(5)二元矩陣秩檢驗

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

(6)離散傅里葉檢驗

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

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

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

(8)重疊模板匹配檢驗

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

(9)Maurer通用檢驗

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

(10)線性復雜度檢驗

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

(11)重疊子序列檢驗

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

(12)近似熵檢驗

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

(13)累加和檢驗

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

(14)隨機游動檢驗

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

(15)隨機游動狀態頻數檢驗

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

3 NIST統計檢測程序的改進

NIST統計檢測程序存在的不足和相應改進如下：

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

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

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

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

(3)不支持自動化功能

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

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

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

下面以AES算法進行頻數檢驗和塊內頻數檢驗為例，說明容忍度的意義。

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

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

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

本文構造一個統計量如下：

T=

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

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

表2 非重疊模板匹配檢驗統計量表

(6)其他優化

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

4 結論

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