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

羅 影，張文科，尹一樺，徐遠(yuǎn)澤

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

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

羅 影，張文科，尹一樺，徐遠(yuǎn)澤

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

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

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

0 引 言

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

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

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

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

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

1 兩種檢測算法簡介

我國的隨機(jī)性檢測規(guī)范有15項(xiàng)檢測，NIST的隨機(jī)性檢測規(guī)范有16項(xiàng)檢測，其中單比特頻數(shù)檢測和塊內(nèi)頻數(shù)檢測是二者共有的檢測項(xiàng)。單比特頻數(shù)檢測的目的是保證0、1比特的個(gè)數(shù)大致相同。塊內(nèi)頻數(shù)檢測是檢測待檢序列的分組長度為m的子序列中1所占的比例，如果1的比例接近于一半則可以認(rèn)為序列隨機(jī)。當(dāng)m取1時(shí)，塊內(nèi)頻數(shù)檢測退化為單比特頻數(shù)檢測。頻數(shù)測試是隨機(jī)性測試的基礎(chǔ)，應(yīng)首先進(jìn)行。下面以我國的隨機(jī)性檢測規(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)

計(jì)算統(tǒng)計(jì)值:

(3)

該統(tǒng)計(jì)值應(yīng)服從標(biāo)準(zhǔn)正態(tài)分布。

4) 計(jì)算對應(yīng)的P值：

(4)

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

(5)

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

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

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

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

N=?n/m」。

(6)

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

(7)

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

(8)

應(yīng)服從自由度為N的χ2分布。

4) 計(jì)算P值:

(9)

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

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

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

2 兩種檢測算法的效率

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

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

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

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

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

表3 兩個(gè)檢測項(xiàng)的性能(時(shí)間單位為微秒)

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

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

3.1 效率分析與改進(jìn)

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

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

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

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

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

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

(10)

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

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

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

輸出：檢測結(jié)果

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

2)當(dāng)i≤n/8時(shí)，執(zhí)行

Sn=Sn+g(Ei,1)

i=i+1。

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

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

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

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

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

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

(11)

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

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

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

(12)

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

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

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

輸出：檢測結(jié)果

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

2)當(dāng)i≤N時(shí)，執(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)計(jì)量V=4S/m。

4)如果V

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

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

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

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

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

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

輸出：檢測結(jié)果

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

2)當(dāng)i≤N時(shí)，執(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)分別計(jì)算兩個(gè)統(tǒng)計(jì)量：

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

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

5)如果V2

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

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

4 實(shí)驗(yàn)結(jié)果

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

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

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

5 結(jié) 語

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

本文提出的三個(gè)快速實(shí)現(xiàn)算法加快了單比特頻數(shù)檢測和塊內(nèi)頻數(shù)檢測的軟件實(shí)現(xiàn)，有利于我國隨機(jī)性檢測規(guī)范和NIST隨機(jī)性檢測規(guī)范的推廣和應(yīng)用。在實(shí)際使用中，如果只需進(jìn)行單比特頻數(shù)檢測，建議使用算法1；如果只需進(jìn)行塊內(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] 隨機(jī)性檢測規(guī)范[S]. 北京: 國家密碼管理局, 2009. Randomness Test Specification [S]. Beijing: National Cryptography Administration, 2009.

[4] 羅影, 劉冬梅, 康紅娟. NIST新分組密碼工作模式及快速實(shí)現(xiàn)研究[J]. 通信技術(shù), 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—)，男，碩士，工程師，主要研究方向?yàn)樾畔⒓夹g(shù)與安全；

張文科(1973—)，男，碩士，高級工程師，主要研究方向?yàn)楸Ｃ芡ㄐ牛?/p>

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

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

10.3969/j.issn.1002-0802.2015.09.018