ZUC算法隨機(jī)性檢測(cè)研究

王 超，范國(guó)浩，付寶仁

(中國(guó)電子信息產(chǎn)業(yè)集團(tuán)有限公司第六研究所，北京 100083)

0 引言

祖沖之-256流密碼算法[1-4](以下簡(jiǎn)稱為ZUC算法)是我國(guó)自主研制的面向5G應(yīng)用環(huán)境的密碼算法。ZUC算法的密鑰長(zhǎng)度為32字節(jié)，初始向量長(zhǎng)度為25字節(jié)，每一節(jié)拍產(chǎn)生4字節(jié)的輸出。

密碼算法輸出序列隨機(jī)性檢測(cè)[5]的結(jié)果，是評(píng)價(jià)密碼算法安全的一個(gè)重要指標(biāo)。美國(guó)國(guó)家標(biāo)準(zhǔn)與技術(shù)研究所(National Institute of Standards and Technology，NIST)發(fā)布的NIST統(tǒng)計(jì)檢測(cè)程序sts-2.1.2(The NIST Statistical Test Suite)[6]，涵蓋了15種隨機(jī)性檢測(cè)方法。

本文首先介紹ZUC算法，接著介紹NIST統(tǒng)計(jì)檢測(cè)程序，然后從檢測(cè)對(duì)象和檢測(cè)源兩方面展開討論隨機(jī)性檢測(cè)設(shè)計(jì)，最后對(duì)ZUC算法進(jìn)行隨機(jī)性檢測(cè)，并將檢測(cè)結(jié)果與Snow流密碼算法[7-8]、Sosemanuk流密碼算法[9]和Trivium流密碼算法[10]進(jìn)行對(duì)比。

1 ZUC算法

ZUC算法由3部分組成：16個(gè)31比特寄存器單元組成的線性反饋移位寄存器(LFSR)、2*31比特至32比特的比特重組層(BR)、具有2個(gè)記憶單元的有限狀態(tài)自動(dòng)機(jī)(FSM)。ZUC算法包含2個(gè)階段：初始化階段和密鑰流生成階段，其中初始化階段由32輪圖1所示動(dòng)作和1輪圖2所示動(dòng)作共同執(zhí)行完成，密鑰流生成階段由圖2所示動(dòng)作執(zhí)行完成。

圖1 初始化專用結(jié)構(gòu)圖

圖2 密鑰流生成結(jié)構(gòu)圖

2 NIST統(tǒng)計(jì)檢測(cè)程序

NIST發(fā)布的NIST統(tǒng)計(jì)檢測(cè)程序sts-2.1.2包含頻數(shù)檢驗(yàn)、塊內(nèi)頻數(shù)檢驗(yàn)、游程檢驗(yàn)、塊內(nèi)最長(zhǎng)游程檢驗(yàn)、二元矩陣秩檢驗(yàn)、離散傅里葉檢驗(yàn)、非重疊模板匹配檢驗(yàn)、重疊模板匹配檢驗(yàn)、Maurer通用檢驗(yàn)、線性復(fù)雜度檢驗(yàn)、重疊子序列檢驗(yàn)、近似熵檢驗(yàn)、累加和檢驗(yàn)、隨機(jī)游動(dòng)檢驗(yàn)、隨機(jī)游動(dòng)狀態(tài)頻數(shù)檢驗(yàn)，共計(jì)15種隨機(jī)性檢測(cè)方法。

不同隨機(jī)性檢測(cè)方法，其參數(shù)要求不一樣。為滿足針對(duì)同一二元序列進(jìn)行全部15種隨機(jī)性檢測(cè)，本文的NIST統(tǒng)計(jì)檢測(cè)程序參數(shù)設(shè)置如下：

(1)二元序列比特長(zhǎng)度為106；

(2)塊內(nèi)頻數(shù)檢驗(yàn)分組比特長(zhǎng)度為10 240；

(3)非周期二元序列模板長(zhǎng)度為9(用于非重疊模板匹配檢驗(yàn)和重疊模板匹配檢驗(yàn))；

(4)線性復(fù)雜度檢驗(yàn)分組比特長(zhǎng)度為500；

(5)重疊子序列檢驗(yàn)分組比特長(zhǎng)度為16；

(6)近似熵檢驗(yàn)分組比特長(zhǎng)度為12。

3 隨機(jī)性檢測(cè)設(shè)計(jì)

本文從檢測(cè)對(duì)象和檢測(cè)源兩方面展開隨機(jī)性檢測(cè)設(shè)計(jì)。

(1)檢測(cè)對(duì)象

密碼算法隨機(jī)性檢測(cè)是指對(duì)密碼算法輸出的序列進(jìn)行二元序列轉(zhuǎn)換，然后進(jìn)行測(cè)試。字或字節(jié)轉(zhuǎn)換時(shí)，需考慮大小字節(jié)序，本文采用大字節(jié)序，小字節(jié)序情況類似。ZUC算法每一節(jié)拍產(chǎn)生一個(gè)32比特的字。于是存在3種方式將輸出序列轉(zhuǎn)換為二元序列:

①將ZUC算法每一節(jié)拍輸出的整體視為1個(gè)通道，于是生成1個(gè)流序列；

②將ZUC算法每一節(jié)拍輸出中的每1個(gè)字節(jié)視為1個(gè)通道，于是生成4個(gè)獨(dú)立的序列；

③將ZUC算法每一節(jié)拍輸出中的每1個(gè)比特視為1個(gè)通道，于是生成32個(gè)獨(dú)立的序列。

第1種二元序列轉(zhuǎn)換方式是經(jīng)典方式，體現(xiàn)了ZUC算法輸出的連續(xù)比特之間的關(guān)系。

ZUC算法中經(jīng)過比特重組層后，內(nèi)部計(jì)算和存儲(chǔ)單元都是32比特長(zhǎng)，如果ZUC算法初始化階段混淆與擴(kuò)散不充分，那么32比特之間將存在顯著差異，因此考查ZUC算法的輸出時(shí)采用第3種二元序列轉(zhuǎn)換方式是有理論依據(jù)的。

本文在對(duì)ZUC算法隨機(jī)性進(jìn)行檢測(cè)時(shí)，分別采用第1種和第3種二元序列轉(zhuǎn)換方式。

(2)檢測(cè)源

ZUC算法輸入為256比特密鑰和184比特初始向量。ZUC算法的輸出由ZUC算法加載密鑰和初始向量然后產(chǎn)生，不同的密鑰或初始向量將產(chǎn)生不同的輸出。在檢測(cè)ZUC算法輸出隨機(jī)性的過程中，為降低密鑰和初始向量的選取對(duì)檢測(cè)判斷的影響，本文進(jìn)行216組檢測(cè)。

本文約定密鑰的二進(jìn)制表示中，若1的出現(xiàn)次數(shù)為1或2或3，即重量為1或2或3，則稱為弱密鑰。類似地，可以定義弱初始向量。針對(duì)ZUC算法，弱密鑰數(shù)量為2 796 417，弱初始向量數(shù)量為1 038 405。

于是密鑰和初始向量的構(gòu)造存在3種方式：

①固定方式(例如全0)；

②隨機(jī)產(chǎn)生方式；

③在弱密鑰或弱初始向量中隨機(jī)選取方式。

本文在對(duì)ZUC算法隨機(jī)性進(jìn)行檢測(cè)時(shí)，分別采用密鑰隨機(jī)并且初始向量隨機(jī)方式，以及弱密鑰隨機(jī)選取并且固定初始向量方式。

4 ZUC算法隨機(jī)性檢測(cè)

本文中硬件檢測(cè)環(huán)境為聯(lián)想M910T標(biāo)準(zhǔn)臺(tái)式計(jì)算機(jī)，處理器為Intel Core i7-6700，內(nèi)存為8 GB。軟件檢測(cè)環(huán)境為操作系統(tǒng)為Windows 7 64位旗艦版Service Pack 1，集成開發(fā)環(huán)境為Eclipse IDE for C/C++ Developers 4.6.3，編譯器為Cygwin 64環(huán)境中的gcc 5.4.0。

ZUC算法的密鑰和初始向量由基于除法電路的64級(jí)線性反饋移位寄存器隨機(jī)產(chǎn)生。

（1）在路基施工結(jié)束后，為了防止社會(huì)車輛對(duì)施工造成影響，施工單位應(yīng)及時(shí)聯(lián)系交通部門，制定道路管制的方案，經(jīng)過監(jiān)理單位的審查之后及時(shí)實(shí)施。

(1)1個(gè)流序列、密鑰隨機(jī)、初始向量隨機(jī)

共隨機(jī)生成216組密鑰和初始向量，進(jìn)行算法隨機(jī)性檢測(cè)，檢測(cè)結(jié)果如表1所示。

(2)32個(gè)流序列、密鑰隨機(jī)、初始向量隨機(jī)

共隨機(jī)生成211組密鑰和初始向量，進(jìn)行算法隨機(jī)性檢測(cè)，檢測(cè)結(jié)果如表2所示。

(3)1個(gè)流序列、弱密鑰隨機(jī)選取、弱初始向量隨機(jī)選取共隨機(jī)生成216組密鑰和初始向量，進(jìn)行算法隨機(jī)性檢測(cè)，檢測(cè)結(jié)果如表3所示。

表1 情形1檢測(cè)結(jié)果

表2 情形2檢測(cè)結(jié)果

表3 情形3檢測(cè)結(jié)果

從表1、表2、表3可以觀察到ZUC算法隨機(jī)性檢測(cè)各項(xiàng)結(jié)果與Snow算法、Sosemanuk算法和Trivium算法基本一致，因此ZUC算法具有良好隨機(jī)性。

5 結(jié)論

本文首先介紹ZUC算法和NIST統(tǒng)計(jì)檢測(cè)程序。然后在討論隨機(jī)性檢測(cè)設(shè)計(jì)時(shí)，在檢測(cè)對(duì)象方面，提出將算法每一節(jié)拍輸出的32比特視為32個(gè)獨(dú)立序列分別進(jìn)行檢測(cè)；在檢測(cè)源方面，提出弱密鑰和弱初始向量概念，針對(duì)這種特定條件進(jìn)行檢測(cè)。最后進(jìn)行ZUC算法隨機(jī)性檢測(cè)實(shí)驗(yàn)，實(shí)驗(yàn)表明與Snow算法、Sosemanuk算法和Trivium算法相比，ZUC算法輸出具有良好的隨機(jī)性。