楊先偉，康紅娟，廖祖華

(1. 無錫職業(yè)技術(shù)學(xué)院 基礎(chǔ)部，江蘇 無錫 214121； 2. 四川長(zhǎng)虹電器股份有限公司，四川 成都 610041； 3. 江南大學(xué)，江蘇 無錫 214122； 4.江南大學(xué) 智能系統(tǒng)與網(wǎng)絡(luò)計(jì)算研究所，江蘇 無錫214122)

?

隨機(jī)序列的撲克檢測(cè)優(yōu)化研究

楊先偉1，康紅娟2，廖祖華3,4

(1. 無錫職業(yè)技術(shù)學(xué)院 基礎(chǔ)部，江蘇 無錫 214121； 2. 四川長(zhǎng)虹電器股份有限公司，四川 成都 610041； 3. 江南大學(xué)，江蘇 無錫 214122； 4.江南大學(xué) 智能系統(tǒng)與網(wǎng)絡(luò)計(jì)算研究所，江蘇 無錫214122)

現(xiàn)代計(jì)算機(jī)系統(tǒng)的安全性依賴于二元隨機(jī)序列，隨機(jī)性檢測(cè)利用概率統(tǒng)計(jì)方法對(duì)二元序列的隨機(jī)性進(jìn)行分析測(cè)試。我國國家密碼管理局發(fā)布了隨機(jī)性檢測(cè)規(guī)范，撲克檢測(cè)為其中一個(gè)檢測(cè)項(xiàng)。本文通過充分分析撲克檢測(cè)效率不高的原因有針對(duì)性地提出一種新的快速實(shí)現(xiàn)算法，優(yōu)化算法充分利用CPU字長(zhǎng)一次處理多個(gè)比特，將m為4和8的情況整合在一起，減少不必要的處理流程。同時(shí)精簡(jiǎn)并優(yōu)化統(tǒng)計(jì)量的計(jì)算和判斷過程，避免余不完全伽馬函數(shù)的計(jì)算。分析和實(shí)驗(yàn)的結(jié)果表明該優(yōu)化算法可以使得撲克檢測(cè)的速度提升9.5倍左右。

二元序列；隨機(jī)序列；隨機(jī)數(shù)發(fā)生器；隨機(jī)性檢測(cè)；撲克檢測(cè)；密碼算法；效率分析；余不完全伽瑪函數(shù)

中文引用格式：楊先偉，康紅娟，廖祖華. 隨機(jī)序列的撲克檢測(cè)優(yōu)化研究[J]. 智能系統(tǒng)學(xué)報(bào)， 2016, 11(4): 513-518.

英文引用格式：YANG Xianwei， KANG Hongjuan， LIAO Zuhua. Study on optimization of poker test random sequences[J]. CAAI Transactions on Intelligent Systems, 2016, 11(4): 513-518.

二元隨機(jī)序列在密碼應(yīng)用中占有舉足輕重的地位?，F(xiàn)在大量的計(jì)算機(jī)系統(tǒng)的安全性需要依賴于二元隨機(jī)序列，比如各種密碼算法中使用的密鑰、非對(duì)稱密碼算法RSA加密、數(shù)字簽名方案中大素?cái)?shù)的生成以及挑戰(zhàn)應(yīng)答身份識(shí)別系統(tǒng)中的挑戰(zhàn)數(shù)等，這些都充分體現(xiàn)了二元隨機(jī)序列的實(shí)際使用價(jià)值。在應(yīng)用密碼學(xué)中，隨機(jī)性檢測(cè)采用概率統(tǒng)計(jì)的方法對(duì)隨機(jī)數(shù)發(fā)生器等生成的二元序列的隨機(jī)性進(jìn)行分析和檢測(cè)，判斷待檢序列在統(tǒng)計(jì)上是否難以和真隨機(jī)數(shù)區(qū)分開來。不同的隨機(jī)性檢測(cè)算法從不同的側(cè)面分析刻畫待檢二元序列與真隨機(jī)序列之間的差距。經(jīng)過多年的發(fā)展，隨機(jī)性檢測(cè)算法已取得豐碩成果，出現(xiàn)并頒布了大量的隨機(jī)性檢測(cè)算法和相關(guān)標(biāo)準(zhǔn)，與此同時(shí)，大量新的隨機(jī)性檢測(cè)算法還在源源不斷地涌現(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ī)性測(cè)試的統(tǒng)計(jì)檢測(cè)方法。德國以此規(guī)范為基礎(chǔ)發(fā)布了BSI AIS 30規(guī)范[2]。我國國家密碼管理局于2009年頒布了適用于我國的隨機(jī)性檢測(cè)規(guī)范[3]。隨機(jī)性檢測(cè)在實(shí)際應(yīng)用中有重要的實(shí)用價(jià)值，不僅可以用于測(cè)評(píng)按照密碼算法或特定標(biāo)準(zhǔn)生成的偽隨機(jī)數(shù)據(jù)的性質(zhì)，如分組算法與某些工作模式相結(jié)合生成的數(shù)據(jù)流[4]，還可以分析測(cè)試以雜湊算法為核心生成的數(shù)據(jù)流，如我國SM3雜湊算法[5]生成的數(shù)據(jù)流。上述工作不僅可以幫助算法分析，減少分析的難度和復(fù)雜度，而且可以檢測(cè)出其他檢測(cè)方法難以檢測(cè)出的某些安全性隱患。因此，國際上很多著名的密碼算法競(jìng)賽均進(jìn)行了大量的隨機(jī)性檢測(cè)評(píng)估，比如AES密碼算法競(jìng)賽、歐洲的NISSIE競(jìng)賽、estream算法競(jìng)賽等，我國的祖沖之序列密碼算法[6-7]也進(jìn)行了大量相關(guān)的隨機(jī)性檢測(cè)。此外，還有大量文章對(duì)隨機(jī)性檢測(cè)算法和標(biāo)準(zhǔn)進(jìn)行進(jìn)一步的分析討論，比如討論隨機(jī)性檢測(cè)規(guī)范的各項(xiàng)檢測(cè)項(xiàng)的快速實(shí)現(xiàn)，例如研究單比特檢測(cè)以及塊內(nèi)頻數(shù)的快速實(shí)現(xiàn)[8]，嘗試新的統(tǒng)計(jì)測(cè)試方法以便作為現(xiàn)有測(cè)試規(guī)范的有益補(bǔ)充[9]，考慮統(tǒng)計(jì)測(cè)試算法的GPU并行化，搭建可并行計(jì)算的統(tǒng)計(jì)測(cè)試實(shí)現(xiàn)框架[10] P。本文的研究重點(diǎn)是撲克檢測(cè)的快速實(shí)現(xiàn)，因?yàn)閾淇藱z測(cè)不僅是我國隨機(jī)性檢測(cè)規(guī)范的檢測(cè)項(xiàng)，而且也是很多基本的隨機(jī)性檢測(cè)的必檢項(xiàng)目之一，所以此項(xiàng)檢測(cè)的快速實(shí)現(xiàn)研究具有非常重要的現(xiàn)實(shí)意義。

1　撲克檢測(cè)

我國的隨機(jī)性檢測(cè)規(guī)范有15項(xiàng)檢測(cè)，包括：?jiǎn)伪忍仡l數(shù)檢測(cè)、塊內(nèi)頻數(shù)檢測(cè)、撲克檢測(cè)、重疊子序列檢測(cè)、游程總數(shù)檢測(cè)、塊內(nèi)最大1游程檢測(cè)、矩陣秩檢測(cè)、累積和檢測(cè)、近似熵檢測(cè)、線性復(fù)雜度檢測(cè)、Maurer通用統(tǒng)計(jì)檢測(cè)、離散傅里葉變換檢測(cè)、游程分布檢測(cè)、二元推導(dǎo)檢測(cè)、自相關(guān)檢測(cè)。撲克檢測(cè)不僅出現(xiàn)在我國的隨機(jī)性檢測(cè)規(guī)范中，也出現(xiàn)在很多別的基本隨機(jī)性檢測(cè)中，比如作為5項(xiàng)基本檢測(cè)項(xiàng)中的一項(xiàng)出現(xiàn)，5項(xiàng)基本檢測(cè)包括單比特頻數(shù)檢測(cè)、序偶檢測(cè)、撲克檢測(cè)、游程分布檢測(cè)、自相關(guān)檢測(cè)。

我國隨機(jī)性檢測(cè)規(guī)范對(duì)撲克檢測(cè)的執(zhí)行流程分為4個(gè)步驟，描述如下[3]：

1) 將長(zhǎng)度為n的二元待檢序列ε1ε2…εn劃分為N=n/m個(gè)長(zhǎng)度為m的非重疊子序列，將多余的比特舍棄。統(tǒng)計(jì)第i種子序列模式出現(xiàn)的頻數(shù)，用ni(1≤i≤2m)表示。我國隨機(jī)性檢測(cè)規(guī)范規(guī)定m取4和8。

2) 計(jì)算統(tǒng)計(jì)值：

(1)

3) 計(jì)算P值：

(2)

4) 如果Pvalue≥α，則認(rèn)為待檢序列通過檢測(cè)。

式(2)中使用的igamc是余不完全伽馬函數(shù)，該函數(shù)的定義為

(3)

式中：Γ(x)為伽馬函數(shù)，該函數(shù)的定義為

(4)

撲克檢測(cè)在很多基本的隨機(jī)性檢測(cè)中都會(huì)出現(xiàn)，因此這是一種基礎(chǔ)檢測(cè)項(xiàng)，在隨機(jī)性檢測(cè)中具有非常重要的作用。在實(shí)際應(yīng)用中，該檢測(cè)項(xiàng)需要具有較高的檢測(cè)速度，以便快速剔除那些明顯不滿足隨機(jī)性特征的樣本。

2　原算法的檢測(cè)效率分析

在實(shí)際應(yīng)用中，送入的待檢序列數(shù)據(jù)多為字節(jié)序列，但傳統(tǒng)的實(shí)現(xiàn)方式會(huì)根據(jù)算法描述先將待檢數(shù)據(jù)轉(zhuǎn)化為單比特表示，然后對(duì)m=4和m=8各執(zhí)行一遍算法中的1)～4)的操作。撲克檢測(cè)算法中3)和4)在一次樣本檢測(cè)中執(zhí)行兩次，1)的執(zhí)行次數(shù)則為O(n)；2)的執(zhí)行次數(shù)則為O(1)，所以其中最關(guān)鍵也最耗時(shí)操作為準(zhǔn)備工作的字節(jié)轉(zhuǎn)比特操作以及1)的統(tǒng)計(jì)各種頻數(shù)。

在分析算法的計(jì)算量時(shí)，本文采用如下縮略符號(hào)：XOR表示異或運(yùn)算；SHIFT表示左/右移位運(yùn)算；ADD表示加法運(yùn)算；AND表示與運(yùn)算。

傳統(tǒng)的撲克檢測(cè)中最關(guān)鍵也最耗時(shí)的步驟是1)，因此以下分析執(zhí)行一組樣本檢測(cè)時(shí)1)所需的運(yùn)算量。在m=4和m=8時(shí)1)需分別執(zhí)行n次SHIFT、n次LOAD和2n次ADD，即合計(jì)總共需執(zhí)行2n次SHIFT、2n次LOAD和4n次ADD。1)進(jìn)行一組樣本檢測(cè)所需執(zhí)行的操作數(shù)詳情如表1。

表1　撲克檢測(cè)算法的操作數(shù)量

按我國隨機(jī)性檢測(cè)規(guī)范規(guī)定一組樣本的大小n為106bit，因此由表1的統(tǒng)計(jì)結(jié)果可知，算法的運(yùn)算量不小，執(zhí)行效率不會(huì)太快。在實(shí)際檢測(cè)中，需要加快撲克檢測(cè)的執(zhí)行速度，以增強(qiáng)它的基礎(chǔ)篩選作用。

3　優(yōu)化思想和優(yōu)化算法

根據(jù)上一節(jié)的分析可知，撲克檢測(cè)的效率不高的主要原因是計(jì)算統(tǒng)計(jì)量時(shí)出現(xiàn)了以下問題：

1)采用了單比特統(tǒng)計(jì)方式，每次僅僅處理一個(gè)比特，CPU的字長(zhǎng)沒有得到充分利用；如果一次處理多個(gè)比特則處理速度將有明顯的提升；

2)對(duì)參數(shù)m=4和m=8，傳統(tǒng)實(shí)現(xiàn)方式會(huì)各執(zhí)行一遍算法中的1)～4)的操作，存在相同數(shù)據(jù)反復(fù)加載的情況；

3)算法的統(tǒng)計(jì)量計(jì)算和判斷過程沒有精簡(jiǎn)和優(yōu)化，存在不必要的余不完全伽馬函數(shù)的計(jì)算。

針對(duì)撲克檢測(cè)原算法出現(xiàn)的效率不高問題，下面有針對(duì)性地提出幾點(diǎn)優(yōu)化想法。具體的優(yōu)化想法如下：

1)一次處理多個(gè)比特，比如一個(gè)字節(jié)或半個(gè)字節(jié)，加快頻數(shù)統(tǒng)計(jì)過程；

2)對(duì)m=4和m=8整合在一起實(shí)現(xiàn)，減少不必要的數(shù)據(jù)加載；

3)精簡(jiǎn)并優(yōu)化統(tǒng)計(jì)量的計(jì)算和判斷過程，事先計(jì)算Pvalue≥α?xí)r統(tǒng)計(jì)量V的閾值，讓統(tǒng)計(jì)值直接和此閾值比較，避免每個(gè)樣本都計(jì)算兩次余不完全伽馬函數(shù)。

記待檢序列為n/8字節(jié)的字節(jié)數(shù)據(jù)Εi，Εi=ε8i+1‖ε8i+2‖…‖ε8i+8，0≤i≤n/8-1。為區(qū)分兩種不同參數(shù)取值時(shí)各種序列模式出現(xiàn)的頻數(shù)，記C4[i],0≤i≤15為m=4時(shí)各種序列模式出現(xiàn)的頻數(shù)，記C8[i],0≤i≤255為m=8時(shí)各種序列模式出現(xiàn)的頻數(shù)。

參數(shù)m=8時(shí)的頻數(shù)統(tǒng)計(jì)方式為直接加載字節(jié)數(shù)據(jù)并更新頻數(shù)，即

(5)

參數(shù)m=4時(shí)的頻數(shù)統(tǒng)計(jì)方式為先加載字節(jié)數(shù)據(jù)，接著獲取高半字節(jié)和低半字節(jié)，

(6)

最后利用獲取的高半字節(jié)和低半字節(jié)更新對(duì)應(yīng)的頻數(shù)，即

(7)

參數(shù)m=4時(shí)和m=8時(shí)的統(tǒng)計(jì)過程分開實(shí)現(xiàn)會(huì)使得待檢數(shù)據(jù)序列重復(fù)加載，這也是撲克檢測(cè)效率不高的主要原因之一。如果能更進(jìn)一步將參數(shù)在兩種不同取值時(shí)的統(tǒng)計(jì)過程合并在一起，則可以減少大量的數(shù)據(jù)重復(fù)加載。參數(shù)m取4和8合并實(shí)現(xiàn)時(shí)的頻數(shù)統(tǒng)計(jì)方式為先加載字節(jié)數(shù)據(jù)，然后獲取高半字節(jié)和低半字節(jié)，最后更新m=4的頻數(shù)和m=8的頻數(shù)，合并式(5)～(7)，可得

H=Ei?4,L=Ei∧0xF,0≤i≤n/8-1

(8)

統(tǒng)計(jì)量的計(jì)算和判斷過程還可以進(jìn)行精簡(jiǎn)和優(yōu)化：可根據(jù)余不完全伽馬函數(shù)的性質(zhì)預(yù)先求出Pvalue≥α?xí)r統(tǒng)計(jì)量V的閾值，讓統(tǒng)計(jì)值V直接和此閾值比較，如此可以減少余不完全伽馬函數(shù)的計(jì)算次數(shù)。

記m=4時(shí)的統(tǒng)計(jì)量為V4，即

(9)

記m=8時(shí)的統(tǒng)計(jì)量為V8，即

(10)

計(jì)算統(tǒng)計(jì)值所用的余不完全伽馬函數(shù)滿足性質(zhì)igamc(α,0)=1，igamc(α,)=0。經(jīng)簡(jiǎn)單計(jì)算可知，當(dāng)顯著水平α=0.01，m=4時(shí)，統(tǒng)計(jì)量V4的閾值為λ4=30.577 914；當(dāng)顯著水平α=0.01，m=8時(shí)，統(tǒng)計(jì)量V8的閾值為λ8=310.457 388。即如果V4<λ4且V8<λ8則認(rèn)為待檢序列通過檢測(cè)。根據(jù)以上描述，優(yōu)化實(shí)現(xiàn)的撲克檢測(cè)算法如下。

算法1 優(yōu)化實(shí)現(xiàn)的撲克檢測(cè)算法

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

輸出檢測(cè)結(jié)果。

1)初始化數(shù)據(jù)： i=0。

C4[j]=0，0≤j≤15，

C8[j]=0，0≤j≤255。

2)當(dāng)i

①X=Ei,H=X?4,L=Ei∧0xF

②C4[H]=C4[H]+1,

C4[L]=C4[L]+1,

C8[X]=C8[X]+1,

③i=i+1。

3)計(jì)算兩個(gè)統(tǒng)計(jì)值V4和V8。

4)如果V4<λ4且V8<λ8，則認(rèn)為待檢序列通過檢測(cè)。否則未通過。

算法1的主要優(yōu)化方式是直接對(duì)輸入的待檢序列按字節(jié)而不是比特進(jìn)行處理，減少了大量不必要的數(shù)據(jù)拆分為單比特等操作；并且將兩種參數(shù)下的頻數(shù)統(tǒng)計(jì)合并在一起，避免了大量的數(shù)據(jù)加載等操作。

4　優(yōu)化前后計(jì)算量分析與對(duì)比

本節(jié)對(duì)優(yōu)化前的算法和優(yōu)化后的算法的計(jì)算量進(jìn)行定量評(píng)估與對(duì)比。

原算法的2)～4)的計(jì)算量都很小，因此本節(jié)在進(jìn)行計(jì)算量評(píng)估對(duì)比時(shí)，只比較最關(guān)鍵最耗時(shí)的步驟統(tǒng)計(jì)頻數(shù)所需要的運(yùn)算量。為簡(jiǎn)化表示,將n比特二元序列的字節(jié)長(zhǎng)度記為M，M=n/8。而且通常情況下輸入的二元序列都是以字節(jié)表示，因此這里默認(rèn)待檢二元序列的比特長(zhǎng)度n能被8整除。

根據(jù)第2節(jié)的分析結(jié)果知，對(duì)一個(gè)n=106bit(M=125×103字節(jié))的樣本而言，原算法1)的計(jì)算量為16M次SHIFT、16M次LOAD和32M次ADD。撲克檢測(cè)優(yōu)化算法1的1)進(jìn)行簡(jiǎn)單分析可知，對(duì)一個(gè)n=106bit的樣本而言，算法1的2)的計(jì)算量為M次SHIFT、M次LOAD、M次AND和3M次ADD。原算法和優(yōu)化算法(算法1)的運(yùn)算量詳情以及對(duì)比情況見表2。

表2　兩個(gè)算法的運(yùn)算量對(duì)比

由表2可知，優(yōu)化后的撲克檢測(cè)的計(jì)算量顯著降低。

在現(xiàn)在的CPU中，常見的整數(shù)運(yùn)算都比較快，如整數(shù)的加、減、比較、比特運(yùn)算及移位等僅需一個(gè)時(shí)鐘周期(cycle)。但數(shù)據(jù)加載的執(zhí)行時(shí)間則有很多因素，無法以準(zhǔn)確的值計(jì)量。這里僅做粗略估計(jì)，因此加速數(shù)據(jù)加載也僅需要一個(gè)時(shí)鐘周期。這樣一來原算法對(duì)一個(gè)樣本進(jìn)行檢測(cè)的粗略估計(jì)時(shí)間為64M個(gè)時(shí)鐘周期，算法1對(duì)一個(gè)樣本進(jìn)行檢測(cè)的粗略估計(jì)時(shí)間為6M個(gè)時(shí)鐘周期，以此法粗略估計(jì)，算法1的檢測(cè)速度為原算法的10.7倍左右。當(dāng)然，此處為不精確的粗略估計(jì)而已，具體的速度提升情況以實(shí)驗(yàn)為準(zhǔn)。

5　模擬實(shí)驗(yàn)測(cè)試

為更準(zhǔn)確地說明本文提出的算法的效率，本節(jié)測(cè)試優(yōu)化前后算法的執(zhí)行效率。

測(cè)試數(shù)據(jù)是利用我國的分組密碼算法SM4算法生成的109bit的偽隨機(jī)數(shù)據(jù)，按樣本大小106比特劃分為1 000個(gè)樣本。

測(cè)試平臺(tái)為Intel Core i3 @3400MHz處理器、4 GB DDR3 1600MHz內(nèi)存、Windows XP SP3操作系統(tǒng)、Visual Studio 2008編譯器。處理器的緩存情況為：一級(jí)緩存為每個(gè)核心32 KB，二級(jí)緩存為每個(gè)核心64 KB，三級(jí)緩存為多核共享3 MB。

模擬實(shí)驗(yàn)使用的代碼情況如下。優(yōu)化前的測(cè)試代碼來源是先從NIST的官方網(wǎng)站取得檢測(cè)代碼，然后按原算法以及NIST代碼思想對(duì)以比特表示的二元序列，按比特操作實(shí)現(xiàn)撲克檢測(cè)，NIST代碼完成字節(jié)序列轉(zhuǎn)比特表示的二元序列的相關(guān)功能。優(yōu)化后的代碼(參見附錄)是對(duì)以字節(jié)表示的序列按算法1的步驟以字節(jié)處理為主實(shí)現(xiàn)撲克檢測(cè)。所有的算法都采用標(biāo)準(zhǔn)C實(shí)現(xiàn)。

實(shí)驗(yàn)采用歐洲estream算法競(jìng)賽的速度測(cè)試模型的簡(jiǎn)化版本，該測(cè)試模型不僅在estream算法競(jìng)賽中采用，后續(xù)許多算法的性能評(píng)估也常采用該測(cè)試模型。具體來講速度測(cè)試流程如下。1)在被測(cè)試代碼段的前后各設(shè)置一個(gè)時(shí)間計(jì)數(shù)器TS和TF；2)將兩個(gè)計(jì)時(shí)器之差T=TF-Ts作為這段代碼的耗時(shí)；3)重復(fù)1)和2)多次，為統(tǒng)計(jì)方便設(shè)定重復(fù)次數(shù)為奇數(shù)，記重復(fù)次數(shù)為C,得到一系列的耗時(shí)值T[i]，1≤i≤C；4)將統(tǒng)計(jì)得到的耗時(shí)值序列按從大到小的順序排列得到T′[1]≥T′[2]≥…≥T′[C]，當(dāng)然也可按從小到大的順序排列；5)取新序列的中值T′[(C+1)/2]作為本段代碼的統(tǒng)計(jì)耗時(shí)值。w為了保證測(cè)試結(jié)果的準(zhǔn)確性，本測(cè)試模型中1)的時(shí)間計(jì)數(shù)器使用CPU頻率計(jì)時(shí)器，直接調(diào)用匯編指令RDTSC，在Windows環(huán)境下也可調(diào)用__rdtsc()函數(shù)，該指令或函數(shù)返回CPU時(shí)鐘周期值，按現(xiàn)代CPU的時(shí)鐘頻率計(jì)算，此計(jì)數(shù)器可精確到納秒級(jí)。兩次RDTSC指令返回的時(shí)鐘周期之差再除以CPU頻率，即可得到以s為單位的耗時(shí)值。

原算法和優(yōu)化算法(算法1)對(duì)1 000個(gè)樣本進(jìn)行檢測(cè)的性能統(tǒng)計(jì)結(jié)果見表3。

表3　算法性能對(duì)比

理論評(píng)估時(shí)只估算了最重要也最耗時(shí)的步驟1)，略去了后面的步驟的耗時(shí)。雖然步驟2)的計(jì)算過程和原算法一樣，但優(yōu)化算法對(duì)步驟3)也做了相應(yīng)的優(yōu)化。實(shí)驗(yàn)的結(jié)果表明，優(yōu)化算法通過充分利用CPU字長(zhǎng)一次處理多個(gè)比特，優(yōu)化整合算法流程減少不必要的計(jì)算，精簡(jiǎn)統(tǒng)計(jì)量的計(jì)算和判斷過程的技術(shù)方式和方法，的確可以顯著地提升撲克檢測(cè)的檢測(cè)性能，且檢測(cè)速度可提升9.5倍左右。

此外，算法性能提升顯著的另外一個(gè)重要原因是撲克檢測(cè)中的參數(shù)m取值較為特殊，m=8恰好是一個(gè)字節(jié)，m=4恰好是將一個(gè)字節(jié)拆分為兩個(gè)“半字節(jié)”。這使得優(yōu)化算法基于字節(jié)的處理方式得到了淋漓盡致的發(fā)揮。

6　 結(jié)論

本文對(duì)我國隨機(jī)性檢測(cè)規(guī)范采用的撲克檢測(cè)算法進(jìn)行優(yōu)化實(shí)現(xiàn)。通過充分利用CPU字長(zhǎng)一次處理多個(gè)比特，優(yōu)化整合算法流程減少不必要的計(jì)算，精簡(jiǎn)統(tǒng)計(jì)量的計(jì)算和判斷過程的技術(shù)方式和方法，可以顯著地提升撲克檢測(cè)的檢測(cè)性能，實(shí)驗(yàn)結(jié)果表明檢測(cè)速度可提升9.5倍左右。因此，建議在實(shí)際檢測(cè)中采用軟件實(shí)現(xiàn)時(shí)使用本文提出的撲克檢測(cè)快速實(shí)現(xiàn)方式以提高撲克檢測(cè)的檢測(cè)效率。NIST和我國的隨機(jī)性檢測(cè)規(guī)范還有很多別的檢測(cè)項(xiàng)，其中還有很多檢測(cè)項(xiàng)可以做必要的性能優(yōu)化，這將是今后工作的一個(gè)研究方向。另外，怎樣利用并行化技術(shù)(如多線程技術(shù)、SIMD指令、GPU運(yùn)算)快速實(shí)現(xiàn)這些檢測(cè)項(xiàng)，也是今后研究的另一個(gè)方向。

附錄　優(yōu)化算法的代碼

本節(jié)列出優(yōu)化算法(算法1)的標(biāo)準(zhǔn)C代碼。其中poker_test函數(shù)為撲克測(cè)試優(yōu)化后的功能實(shí)現(xiàn)函數(shù)，poker_get_statistics函數(shù)為撲克檢測(cè)中計(jì)算統(tǒng)計(jì)量的函數(shù)。

//撲克測(cè)試優(yōu)化后代碼

int poker_test(BYTE *p_u8, int n )

{

double v;

BYTE *p_bound = p_u8 + n / 8, d;

u32 c4[16] = {0}, c8[256] = {0};

while( p_u8 < p_bound )

{

d = *p_u8++;

c8[ d ]++;

c4[ d ? 4 ]++;

c4[ d & 0xf ]++;

}

//m = 8時(shí)計(jì)算統(tǒng)計(jì)量

v = poker_get_statistics(8, n, c8);

if(v >= POKER_BOUND_M_8)

{

return -8;

}

//m = 4 時(shí)計(jì)算統(tǒng)計(jì)量

v = poker_get_statistics(4, n, c4);

if(v >= POKER_BOUND_M_4)

{

return -4;

}

return 1;

}

//撲克檢測(cè)計(jì)算統(tǒng)計(jì)量，n為序列比特長(zhǎng)度

// m為參數(shù)，p_ctr為子序列頻數(shù)

double poker_get_statistics(int m, int n, u32 *p_ctr)

{

int i, blk_sz, pow_m;

double blk_sz_inv, sum;

sum = 0.0;

pow_m = 1 << m;

blk_sz = n / m;

blk_sz_inv = 1.0 / blk_sz;

for( i = 0; i < pow_m; i++ )

{

sum += p_ctr[i] * p_ctr[i] * blk_sz_inv;

}

return ( sum * pow_m ) - blk_sz;

}

[1]National Institute of Standards and Technology. NIST SP 800-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ī)性檢測(cè)規(guī)范[S]. 中國北京: 國家密碼管理局, 2009.

Randomness test specification[S]. Beijing: National Cryptography Administration, 2009.

[4]羅影, 劉冬梅, 康紅娟. NIST新分組密碼工作模式及快速實(shí)現(xiàn)研究[J]. 通信技術(shù), 2014, 47(9): 1066-1070.

LUO Ying, LIU Dongmei, KANG Hongjuan., NIST new block cipher modes of operation and their fast implementationoperation modes and their fast implementations of nist new block cipher[J]. Communications technology, 2014, 47(9): 1066-1070.

[5]楊先偉, 康紅娟. SM3雜湊算法的軟件快速實(shí)現(xiàn)研究[J]. 智能系統(tǒng)學(xué)報(bào), 2015, 10(6): 9541-9597.

YANG Xianwei, KANG Hongjuan. Fast software implementation of SM3 hash algorithm[J]. CAAI transactions on intelligent systems, 2015, 10(6): 9541-9597.

[6]CCSA. Specification of the 3GPP confidentiality and integrity algorithms 128-EEA3 & 128-EIA3. Document 2: ZUC specification[S]. Cedex, France: CCSA, 2011.

[7]馮秀濤. 3GPP LTE國際加密標(biāo)準(zhǔn)ZUC算法[J]. 信息安全與通信保密, 2011, 9(12): 45-46.

FENG Xiutao. ZUC algorithm: 3GPP LTE international encryption standard[J]. Information security and communications privacy, 20112, 9(12): 45-46.

[8]羅影, 張文科, 尹一樺, 等. 單比特頻數(shù)檢測(cè)和塊內(nèi)頻數(shù)檢測(cè)的快速實(shí)現(xiàn)研究[J]. 通信技術(shù), 2015, 48(9): 1073-1077.

LUO Ying, ZHANG Wenke, YIN Yihua, et al. Fast Implementation of monobit frequency test and frequency test within a block[J]. Communications technology,. 2015, 48(9): 1073-1077.

[9]Edro M AALCOVER P M, GUILLAMóN A, RUIZ M D CAntonio G, et al. A new randomness test for bit sequences[J]. Informatica, 2013, 24(3): 339-356.

[10]KAMINSKY A. GPU parallel statistical and cube test analysis of the SHA-3 finalist candidate hash functions[EB/OL]. (2012-02-13) [2016-03-31]. http://www.cs.rit.edu/～ark/parallelcrypto/sha3test01/.

楊先偉,男，1980年生，講師，主要研究方向?yàn)槊艽a學(xué)及通信與系統(tǒng)工程。

康紅娟，女，1983年生，碩士，工程師，主要研究方向?yàn)楸Ｃ芡ㄐ拧?/p>

廖祖華，男，957年生，教授，主要研究方向?yàn)槿斯ぶ悄?、模糊與粗糙代數(shù)、廣義逆理論及應(yīng)用。主持省自然科學(xué)基金項(xiàng)目1項(xiàng)。發(fā)表學(xué)術(shù)論文130余篇，其中被SCI和EI檢索30余篇。

Study on optimization of poker test random sequences

YANG Xianwei1， KANG Hongjuan2， LIAO Zuhua3,4

(1. Department of Fundamental Courses, Wuxi Institute of Technology, Wuxi 214121, China； 2. Sichuan Changhong Electric Co., Ltd., Chengdu 610041, China； 3.School of Science, Jangnan University, Wuxi 214122, China； 4.Institute of Intelligence System &Network Computing, Jiangnan University, Wuxi 214122, China)

The security of modern computer systems depends on binary random sequences, such as cipher algorithms keys, RSA algorithm prime numbers, the digital signature system, the identity authentication system, etc. Randomness tests analyze and test the randomness of sequences, using probability and statistics. The Chinese National Cryptography Administration has released national randomness test specifications and the Poker test is one of these. This paper analyzed the reasons for the low efficiency of the Poker test, then proposes a fast implementation algorithm. This new algorithm deals with bytes by making full use of CPU word length, integrates the detection process, and reduces some unnecessary operations under the conditions when m equals 4 and 8. At the same time, the method reduces and optimizes the computation and assessment of statistical quantity, avoiding computation of incomplete gamma functions. The results show that the efficiency of the new algorithm increases 9.5 fold.

binary sequence; random sequence; pseudorandom bit generator; randomness test; poker test; encryption algorithms; efficiency analysis; incomplete gamma functions.

10.11992/tis.201606002

網(wǎng)絡(luò)出版地址：http://www.cnki.net/kcms/detail/23.1538.TP.20160808.0830.012.html

2016-06-01. 網(wǎng)絡(luò)出版日期：2016-08-08.

國家自然科學(xué)基金項(xiàng)目(61170121,11401259)；江蘇省自然科學(xué)基金項(xiàng)目(BK20151117).

廖祖華. E-mail：liaozuhua57@163.com.

TP18

A

1673-4785(2016)04-0513-06