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

楊先偉，康紅娟，廖祖華

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

?

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

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

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

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

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

中文引用格式：楊先偉，康紅娟，廖祖華. 隨機序列的撲克檢測優(yōu)化研究[J]. 智能系統(tǒng)學報， 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.

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

1　撲克檢測

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

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

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

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

(1)

3) 計算P值：

(2)

4) 如果Pvalue≥α，則認為待檢序列通過檢測。

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

(3)

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

(4)

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

2　原算法的檢測效率分析

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

在分析算法的計算量時，本文采用如下縮略符號：XOR表示異或運算；SHIFT表示左/右移位運算；ADD表示加法運算；AND表示與運算。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

(5)

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

(6)

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

(7)

參數(shù)m=4時和m=8時的統(tǒng)計過程分開實現(xiàn)會使得待檢數(shù)據(jù)序列重復加載，這也是撲克檢測效率不高的主要原因之一。如果能更進一步將參數(shù)在兩種不同取值時的統(tǒng)計過程合并在一起，則可以減少大量的數(shù)據(jù)重復加載。參數(shù)m取4和8合并實現(xiàn)時的頻數(shù)統(tǒng)計方式為先加載字節(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)計量的計算和判斷過程還可以進行精簡和優(yōu)化：可根據(jù)余不完全伽馬函數(shù)的性質預先求出Pvalue≥α時統(tǒng)計量V的閾值，讓統(tǒng)計值V直接和此閾值比較，如此可以減少余不完全伽馬函數(shù)的計算次數(shù)。

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

(9)

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

(10)

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

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

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

輸出檢測結果。

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

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

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

2)當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)計算兩個統(tǒng)計值V4和V8。

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

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

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

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

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

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

表2　兩個算法的運算量對比

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

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

5　模擬實驗測試

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

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

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

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

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

原算法和優(yōu)化算法(算法1)對1 000個樣本進行檢測的性能統(tǒng)計結果見表3。

表3　算法性能對比

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

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

6　 結論

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

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

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

//撲克測試優(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時計算統(tǒng)計量

v = poker_get_statistics(8, n, c8);

if(v >= POKER_BOUND_M_8)

{

return -8;

}

//m = 4 時計算統(tǒng)計量

v = poker_get_statistics(4, n, c4);

if(v >= POKER_BOUND_M_4)

{

return -4;

}

return 1;

}

//撲克檢測計算統(tǒng)計量，n為序列比特長度

// 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]隨機性檢測規(guī)范[S]. 中國北京: 國家密碼管理局, 2009.

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

[4]羅影, 劉冬梅, 康紅娟. NIST新分組密碼工作模式及快速實現(xiàn)研究[J]. 通信技術, 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雜湊算法的軟件快速實現(xiàn)研究[J]. 智能系統(tǒng)學報, 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國際加密標準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ù)檢測和塊內頻數(shù)檢測的快速實現(xiàn)研究[J]. 通信技術, 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年生，講師，主要研究方向為密碼學及通信與系統(tǒng)工程。

康紅娟，女，1983年生，碩士，工程師，主要研究方向為保密通信。

廖祖華，男，957年生，教授，主要研究方向為人工智能、模糊與粗糙代數(shù)、廣義逆理論及應用。主持省自然科學基金項目1項。發(fā)表學術論文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

網絡出版地址：http://www.cnki.net/kcms/detail/23.1538.TP.20160808.0830.012.html

2016-06-01. 網絡出版日期：2016-08-08.

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

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

TP18

A

1673-4785(2016)04-0513-06