單比特頻數(shù)檢測和塊內(nèi)頻數(shù)檢測的快速實現(xiàn)研究*

羅 影，張文科，尹一樺，徐遠澤

(衛(wèi)士通信息產(chǎn)業(yè)股份有限公司，四川 成都 610041)

單比特頻數(shù)檢測和塊內(nèi)頻數(shù)檢測的快速實現(xiàn)研究*

羅 影，張文科，尹一樺，徐遠澤

(衛(wèi)士通信息產(chǎn)業(yè)股份有限公司，四川 成都 610041)

隨機序列在密碼技術中占有非常重要的地位，隨機性檢測利用概率統(tǒng)計的方法對隨機序列的隨機性進行分析測試。美國國家標準與技術研究院(NIST)和我國國家密碼管理局都發(fā)布了各自的隨機性檢測規(guī)范，二者都將單比特頻數(shù)檢測和塊內(nèi)頻數(shù)檢測作為其檢測項。研究了單比特頻數(shù)檢測和塊內(nèi)頻數(shù)檢測的快速實現(xiàn)，提出了三種新的快速實現(xiàn)算法。這三種算法可以使單比特頻數(shù)檢測、塊內(nèi)頻數(shù)檢測和兩種檢測綜合實現(xiàn)的速度分別提升29.2倍、15.5倍和32.8倍。

隨機序列；單比特頻數(shù)檢測；塊內(nèi)頻數(shù)檢測

0 引 言

隨機序列在密碼應用技術中占有非常重要的地位，香農(nóng)的完善保密系統(tǒng)以及現(xiàn)代密碼系統(tǒng)都將隨機序列視為安全算法的根本?，F(xiàn)在的計算機安全系統(tǒng)大量使用隨機序列，如密鑰的產(chǎn)生、數(shù)字簽名、身份認證等，這充分體現(xiàn)了隨機數(shù)的應用價值。

在應用密碼學中，隨機性檢測的目的是采用概率統(tǒng)計方法分析測試隨機數(shù)發(fā)生器等生成的序列的隨機性，判斷待檢序列在統(tǒng)計上是否難以和真隨機數(shù)區(qū)分開。不同的檢測算法從不同的角度刻畫待檢序列與真隨機序列之間的差距。經(jīng)過多年的研究和發(fā)展后，隨機性檢測已經(jīng)取得了豐碩的成果，目前已有大量的隨機性檢測算法，并且新的檢測算法還在不斷涌現(xiàn)。

美國國家標準與技術研究院(National Institute of Standards and Technology，NIST)發(fā)布的SP 800-22標準[1]建議了16種用于隨機性測試的統(tǒng)計檢驗方法，以此為基礎，德國發(fā)布了BSI AIS 30規(guī)范[2]。2009年，我國國家密碼管理局發(fā)布了隨機性檢測規(guī)范[3]。

在實際應用中，隨機性檢測方法可用于評測按照特定標準生成的偽隨機數(shù)據(jù)流，也可以對密碼算法生成的數(shù)據(jù)流進行評測，如分組算法與特定工作模式相結合生成的數(shù)據(jù)流[4]。此舉可為算法分析提供幫助，既減少了工作量，又可檢測出其它方法無法發(fā)現(xiàn)的安全隱患。AES競賽的候選算法均進行了隨機性檢測評估。目前已有大量的文章討論隨機性檢測規(guī)范的快速現(xiàn)實以及相關檢測項，比如Abdel-Rehim等[5]研究撲克檢測的快速實現(xiàn)以及性能表現(xiàn)，Kaminsky[6]研究統(tǒng)計測試算法的GPU并行實現(xiàn)并建立并行實現(xiàn)的統(tǒng)計測試框架，Alcover等[7]研究一種新的統(tǒng)計測試方法以作為測試規(guī)范的補充。

單比特頻數(shù)檢測和塊內(nèi)頻數(shù)檢測是NIST的隨機性檢測規(guī)范和我國的隨機性檢測規(guī)范都有的檢測項，研究這兩種檢測的快速實現(xiàn)是本文的主要工作。本文組織如下：首先，簡單介紹兩種檢測算法；然后，分析測試并發(fā)現(xiàn)現(xiàn)有檢測算法的效率問題；第三節(jié)分析算法效率較低的原因，并利用優(yōu)化比特統(tǒng)計、復用比特統(tǒng)計、預先判斷、消減除法等技術和方法，提出三種新的快速實現(xiàn)算法；第四節(jié)測試三種新算法的檢測效率，這三種算法可以使得單比特頻數(shù)檢測、塊內(nèi)頻數(shù)檢測和兩種檢測組合實現(xiàn)的速度分別提升29.2倍、15.5倍和32.8倍；最后總結全文。

1 兩種檢測算法簡介

我國的隨機性檢測規(guī)范有15項檢測，NIST的隨機性檢測規(guī)范有16項檢測，其中單比特頻數(shù)檢測和塊內(nèi)頻數(shù)檢測是二者共有的檢測項。單比特頻數(shù)檢測的目的是保證0、1比特的個數(shù)大致相同。塊內(nèi)頻數(shù)檢測是檢測待檢序列的分組長度為m的子序列中1所占的比例，如果1的比例接近于一半則可以認為序列隨機。當m取1時，塊內(nèi)頻數(shù)檢測退化為單比特頻數(shù)檢測。頻數(shù)測試是隨機性測試的基礎，應首先進行。下面以我國的隨機性檢測規(guī)范為例討論單比特頻數(shù)檢測和塊內(nèi)頻數(shù)檢測。

單比特頻數(shù)檢測的檢測方法如下[3]:

1) 將待檢序列εi中的比特0和1分別轉(zhuǎn)化為-1和1，Xi=2εi-1,(1≤i≤n)。

2) 對其累加求和得到:

(1)

3) 根據(jù)中心極限定理:

(2)

計算統(tǒng)計值:

(3)

該統(tǒng)計值應服從標準正態(tài)分布。

4) 計算對應的P值：

(4)

其中erfc是余差函數(shù)。

(5)

5) 如果P-value≥α，則認為待檢序列通過檢測。

步驟5中的α為顯著水平，我國的隨機性檢測規(guī)范規(guī)定α=0.01。

塊內(nèi)頻數(shù)檢測檢測的檢測方法如下[3]。

1) 將待檢序列ε按長度m劃分為N個非重疊的子序列，多余比特舍棄,其中:

N=?n/m」。

(6)

2) 計算各子序列中1所占的比例:

(7)

3) 所有子序列中1所占的比例的累加和作為統(tǒng)計量:

(8)

應服從自由度為N的χ2分布。

4) 計算P值:

(9)

其中igamc是余不完全伽馬函數(shù)。

5) 如果P-value≥α，則認為待檢序列通過檢測。

我國的隨機性檢測規(guī)范規(guī)定塊內(nèi)頻數(shù)檢測的參數(shù)m取100。如前所述，頻率檢測在隨機性檢測中具有非常重要的作用，是其它檢測的基礎，因此這兩種檢測需具有極高的檢測效率，以便快速剔除那些明顯不滿足隨機性特征的待檢樣本。

2 兩種檢測算法的效率

在通常的實現(xiàn)方式中會先將待檢數(shù)據(jù)轉(zhuǎn)化為單比特表示，以便兩種算法進行比特個數(shù)統(tǒng)計。單比特頻數(shù)檢測算法最關鍵也最耗時的步驟為步驟1和2的比特統(tǒng)計，計算統(tǒng)計量需要執(zhí)行的操作數(shù)如表1，這里Xi利用查表得出(t[0]=-1,t[1]=1)。

表1 單比特頻數(shù)檢測算法的操作數(shù)量

塊內(nèi)頻數(shù)檢測算法中最關鍵也是最耗時的步驟為步驟1—3，計算統(tǒng)計量需要執(zhí)行的操作數(shù)如表2。

表2 塊內(nèi)頻數(shù)檢測算法的操作數(shù)量

我國的隨機性檢測規(guī)范規(guī)定一組樣本長1 000 000比特。下面統(tǒng)計了按普通方式實現(xiàn)這兩個算法時檢測一組樣本所需的時間。測試平臺為Intel Core i3 @3 400 MHz處理器、4 GB DDR3 1 600 MHz內(nèi)存、WinXP SP3操作系統(tǒng)、VC6.0。測試結果見表3。

表3 兩個檢測項的性能(時間單位為微秒)

這里的兩種檢測綜合實現(xiàn)是指這兩種檢測算法都實現(xiàn)。由上表可知，這兩個檢測算法的效率并不高。在實際檢測中，需要更加快速高效的實現(xiàn)方式，以大大提高這兩個算法的效率，增強其所起的篩選作用。

3 快速實現(xiàn)算法

3.1 效率分析與改進

單比特頻數(shù)檢測和塊內(nèi)頻數(shù)檢測的效率并不高的主要原因是比特數(shù)量統(tǒng)計采用了單比特統(tǒng)計方式，使得每次只能處理一個比特，CPU的字長沒有得到充分利用。如果能一次處理多個比特，那么處理速度將會有明顯的提升。并且，兩個算法的統(tǒng)計量計算和判斷過程還可以進行精簡和優(yōu)化。

改進算法的主要想法為：首先，利用查表法直接得出w個比特中比特1的個數(shù)；其次，因為兩個算法都要用比特統(tǒng)計，所以比特統(tǒng)計的結果可以在兩個算法之間共享；第三，優(yōu)化統(tǒng)計檢測公式，去除不必要的計算，降低計算復雜度。

查表的比特寬度記為w，則表中元素個數(shù)為2w。綜合考慮連續(xù)w比特的獲取難易度以及表的規(guī)模后發(fā)現(xiàn)w取8較合適。首先，8比特是一個字節(jié)，無需做字節(jié)間的拼接或拆分；其次，可以消除將待檢數(shù)據(jù)拆分為單比特的步驟；第三，此時表的規(guī)模適中，為256字節(jié)，絕大部分處理器都能接受。

3.2 單比特頻數(shù)檢測優(yōu)化

記B=B1‖…‖BL為連續(xù)多個字節(jié)形成的數(shù)組，其中Bi,1≤i≤L為一個字節(jié)。

記g(B,t)表示計算B1‖…‖Bt這t個字節(jié)中比特1的總個數(shù)。如果t取1，則g(B,1)表示計算字節(jié)B1中比特1的個數(shù)。g(B,1)可通過查表實現(xiàn)，g(B,t)可通過多次查表實現(xiàn)。

(10)

單比特頻數(shù)檢測算法優(yōu)化如下。

算法1 優(yōu)化實現(xiàn)的單比特頻數(shù)檢測算法

輸入：n/8字節(jié)的數(shù)據(jù)Ei,1≤i≤n/8

輸出：檢測結果

1)初始化：Sn=0，i=1。

2)當i≤n/8時，執(zhí)行

Sn=Sn+g(Ei,1)

i=i+1。

3)如果|Sn|s，通過檢測；否則不通過。

優(yōu)化實現(xiàn)算法中計算累加和Sn需要執(zhí)行的操作數(shù)如表4。

表4 優(yōu)化實現(xiàn)的單比特頻數(shù)檢測算法的操作數(shù)量

由表4可知，計算量降低為原來的1/8。此外消除余差函數(shù)也將大大減少計算量。

3.3 塊內(nèi)頻數(shù)檢測優(yōu)化

塊內(nèi)頻數(shù)檢測的優(yōu)化思想如前所述，另外還可以進一步提升效率。算法在計算統(tǒng)計量時使用了N次除法，但處理器執(zhí)行除法運算的代價非常高，大約是乘法運算執(zhí)行時間的10-20倍。優(yōu)化統(tǒng)計量的計算過程可以減少除法次數(shù)。記Ni為第i個子序列中比特1的個數(shù)。統(tǒng)計量的計算可做如下簡化:

(11)

利用上式計算統(tǒng)計量可將除法次數(shù)從N次降低為1次。

與單比特頻數(shù)檢測一樣，可以根據(jù)余不完全伽馬函數(shù)的性質(zhì)求出V的界，以減少不完全伽馬函數(shù)的計算。當α=0.01，N=10000時，若V

P-value=igamc(N/2,V/2)≥α。

(12)

另外，塊內(nèi)頻數(shù)檢測的參數(shù)m=100使得子序列沒有按字節(jié)對齊。一個簡單的解決辦法是每次處理連續(xù)兩個子序列共25字節(jié)。塊內(nèi)頻數(shù)檢測算法優(yōu)化如下。

算法2 優(yōu)化實現(xiàn)的塊內(nèi)頻數(shù)檢測算法

輸入：n/8字節(jié)的數(shù)據(jù)Εi,1≤i≤n/8

輸出：檢測結果

1)N=?n/m」,S=0,i=1,a=m/2。

2)當i≤N時，執(zhí)行

Ni=g(E25i+1,12)+g(E25i+13>>4,1)

Ni+1=g(E25i+14,12)+g(E25i+13∧0xF,1)

S=S+(Ni-a)2+(Ni+1-a)2

i=i+2。

3)統(tǒng)計量V=4S/m。

4)如果V

優(yōu)化實現(xiàn)算法中，算出統(tǒng)計量V需要執(zhí)行的操作量如表5。由表5可知，除法次數(shù)降低至1次，同時加減法次數(shù)也大大減少。

表5 優(yōu)化實現(xiàn)的塊內(nèi)頻數(shù)檢測算法的操作數(shù)量

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

如前所述，比特統(tǒng)計的結果可在兩個算法之間共享：兩個子序列的比特1的個數(shù)相加，然后該和值累加便可得到整個序列中比特1的總數(shù)S1，最后累加和為|Sn|=|n-2S1|。

算法3 優(yōu)化實現(xiàn)的合并檢測算法

輸入：n/8字節(jié)的數(shù)據(jù)Ei,1≤i≤n/8

輸出：檢測結果

1)N=?n/m」,S1=S2=0,i=1,a=m/2。

2)當i≤N時，執(zhí)行

Ni=g(E25i+1,12)+g(E25i+13>>4,1)

Ni+1=g(E25i+14,12)+g(E25i+13∧0xF,1)

S2=S2+(Ni-a)2+(Ni+1-a)2

S1=S1+Ni+Ni+1

i=i+2。

3)分別計算兩個統(tǒng)計量：

Sn=n-2S1,V2=4S2/m。

4)如果|Sn|≤s，則通過單比特頻數(shù)檢測；否則不通過。

5)如果V2

優(yōu)化實現(xiàn)算法3中，需要執(zhí)行的操作量如表6。由表6可知，算法3和算法2相比，僅僅是多了2N次加法即可計算出累加和。

表6 優(yōu)化實現(xiàn)的合并檢測算法的操作數(shù)量

4 實驗結果

為了更準確地說明新算法的效率，利用前面的測試平臺對算法1-3進行測試并統(tǒng)計各自的檢測時間。測試結果見表7。

表7 算法性能對比(時間單位為微秒)T1和T2分別表示優(yōu)化前和優(yōu)化后的耗時

優(yōu)化后的單比特頻數(shù)檢測速度提升29.2倍，這歸功于累加和界的利用和比特統(tǒng)計方式的優(yōu)化。優(yōu)化后的塊內(nèi)頻數(shù)檢測速度提升15.5倍，這歸功于除法數(shù)量的減少和比特統(tǒng)計方式的優(yōu)化。優(yōu)化后的兩個檢測速度提升32.8倍，這歸功于比特統(tǒng)計的優(yōu)化復用、累加和界的利用和除法數(shù)量的減少。

5 結 語

本文對我國隨機性檢測規(guī)范和NIST隨機性檢測規(guī)范都采用的單比特頻數(shù)檢測和塊內(nèi)頻數(shù)檢測進行優(yōu)化實現(xiàn)。通過組合利用比特統(tǒng)計的優(yōu)化復用、累加和界和統(tǒng)計量優(yōu)化等方法使得單比特頻數(shù)檢測、塊內(nèi)頻數(shù)檢測和兩個檢測組合實現(xiàn)時的速度分別提升了29.2倍、15.5倍和32.8倍。

本文提出的三個快速實現(xiàn)算法加快了單比特頻數(shù)檢測和塊內(nèi)頻數(shù)檢測的軟件實現(xiàn)，有利于我國隨機性檢測規(guī)范和NIST隨機性檢測規(guī)范的推廣和應用。在實際使用中，如果只需進行單比特頻數(shù)檢測，建議使用算法1；如果只需進行塊內(nèi)頻數(shù)檢測，建議使用算法2；如果兩種檢測都要使用，建議使用算法3。

[1] NIST SP800-22. A Statistical Test Suite for Random and Pseudorandom Number Generators for Cryptographic Applications [S]. Revision 1a. Washington DC, USA: Information Technology Laboratory of National Institute of Standards and Technology, 2010.

[2] BSI AIS-20, AIS-30. Application Notes and Interpretation of the Scheme Functionality Classes and Evaluation Methodology for Deterministic and Physical Random Number Generators [S]. Berlin, Germany: German Federal Office for Information Security, 2008.

[3] 隨機性檢測規(guī)范[S]. 北京: 國家密碼管理局, 2009. Randomness Test Specification [S]. Beijing: National Cryptography Administration, 2009.

[4] 羅影, 劉冬梅, 康紅娟. NIST新分組密碼工作模式及快速實現(xiàn)研究[J]. 通信技術, 2014, 47 (9):1066-1070. 1066-1070. LUO Ying, LIU Dong-mei, KANG Hong-juan. NIST New Block Cipher Modes of Operation and Their Fast Implementation[J]. Communications Technology, 2014, 47(9):1066-1070.

[5] Wael M. F. Abdel-Rehim, Ismail A. et al. Testing Randomness: Implementing Poker Approaches with Hands of Four Numbers [J]. IJCSI International Journal of Computer Science Issues, 2012, 9(3): 59-64.

[6] Kaminsky, A. GPU Parallel Statistical and Cube Test Analysis of the SHA-3 Finalist Candidate Hash Functions [EB/OL]. http://www.cs.rit.edu/～ark/parallelcrypto/sha3test01/, 2011.

[7] Edro María Alcover, Antonio Gullamon, María del Carmen Ruiz. A New Randomness Test for Bit Sequences [J]. Informatica, 2013, 24(3): 339-356.

Fast Implementation of Monobit Frequency Test and Frequency Test Within a Block

LUO Ying, ZHANG Wen-ke, YIN Yi-hua, XU Yuan-ze

(Westone Information Industry, Ltd., Chengdu Sichuan 610041,China)

Random sequence plays a very important role in the crypto technology. Randomness test, by using the method of probability statistics, analyzes and tests randomness of the sequence. US National Institute of Standards and Technology and China National Cryptography Administration respectively released their randomness test specifications. These two specifications both take monobit frequency test and frequency test within a block as the test items. This paper discusses the fast implementation of monobit frequency test and frequency test within a block, analyzes the hotspots, and proposes three fast implementation algorithms. These new algorithms can greatly improve the speed of monobit frequency test，frequency test within a block and their combined implementation.

random sequence;monobit frequency test;frequency test within a block

2015-04-03；

2015-07-14 Received date:2015-04-03；Revised date：2015-07-14

TP309

A

1002-0802(2015)09-1073-05

羅 影(1981—)，男，碩士，工程師，主要研究方向為信息技術與安全；

張文科(1973—)，男，碩士，高級工程師，主要研究方向為保密通信；

尹一樺(1978—)，男，碩士，工程師，主要研究方向保密通信;

徐遠澤(1985—)，男，碩士，工程師，主要研究方向保密通信。

10.3969/j.issn.1002-0802.2015.09.018