ZUC算法隨機性檢測研究

王 超，范國浩，付寶仁

(中國電子信息產業集團有限公司第六研究所，北京 100083)

0 引言

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

密碼算法輸出序列隨機性檢測[5]的結果，是評價密碼算法安全的一個重要指標。美國國家標準與技術研究所(National Institute of Standards and Technology，NIST)發布的NIST統計檢測程序sts-2.1.2(The NIST Statistical Test Suite)[6]，涵蓋了15種隨機性檢測方法。

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

1 ZUC算法

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

圖1 初始化專用結構圖

圖2 密鑰流生成結構圖

2 NIST統計檢測程序

NIST發布的NIST統計檢測程序sts-2.1.2包含頻數檢驗、塊內頻數檢驗、游程檢驗、塊內最長游程檢驗、二元矩陣秩檢驗、離散傅里葉檢驗、非重疊模板匹配檢驗、重疊模板匹配檢驗、Maurer通用檢驗、線性復雜度檢驗、重疊子序列檢驗、近似熵檢驗、累加和檢驗、隨機游動檢驗、隨機游動狀態頻數檢驗，共計15種隨機性檢測方法。

不同隨機性檢測方法，其參數要求不一樣。為滿足針對同一二元序列進行全部15種隨機性檢測，本文的NIST統計檢測程序參數設置如下：

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

(2)塊內頻數檢驗分組比特長度為10 240；

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

(4)線性復雜度檢驗分組比特長度為500；

(5)重疊子序列檢驗分組比特長度為16；

(6)近似熵檢驗分組比特長度為12。

3 隨機性檢測設計

本文從檢測對象和檢測源兩方面展開隨機性檢測設計。

(1)檢測對象

密碼算法隨機性檢測是指對密碼算法輸出的序列進行二元序列轉換，然后進行測試。字或字節轉換時，需考慮大小字節序，本文采用大字節序，小字節序情況類似。ZUC算法每一節拍產生一個32比特的字。于是存在3種方式將輸出序列轉換為二元序列:

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

②將ZUC算法每一節拍輸出中的每1個字節視為1個通道，于是生成4個獨立的序列；

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

第1種二元序列轉換方式是經典方式，體現了ZUC算法輸出的連續比特之間的關系。

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

本文在對ZUC算法隨機性進行檢測時，分別采用第1種和第3種二元序列轉換方式。

(2)檢測源

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

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

于是密鑰和初始向量的構造存在3種方式：

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

②隨機產生方式；

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

本文在對ZUC算法隨機性進行檢測時，分別采用密鑰隨機并且初始向量隨機方式，以及弱密鑰隨機選取并且固定初始向量方式。

4 ZUC算法隨機性檢測

本文中硬件檢測環境為聯想M910T標準臺式計算機，處理器為Intel Core i7-6700，內存為8 GB。軟件檢測環境為操作系統為Windows 7 64位旗艦版Service Pack 1，集成開發環境為Eclipse IDE for C/C++ Developers 4.6.3，編譯器為Cygwin 64環境中的gcc 5.4.0。

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

（1）在路基施工結束后，為了防止社會車輛對施工造成影響，施工單位應及時聯系交通部門，制定道路管制的方案，經過監理單位的審查之后及時實施。

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

共隨機生成216組密鑰和初始向量，進行算法隨機性檢測，檢測結果如表1所示。

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

共隨機生成211組密鑰和初始向量，進行算法隨機性檢測，檢測結果如表2所示。

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

表1 情形1檢測結果

表2 情形2檢測結果

表3 情形3檢測結果

從表1、表2、表3可以觀察到ZUC算法隨機性檢測各項結果與Snow算法、Sosemanuk算法和Trivium算法基本一致，因此ZUC算法具有良好隨機性。

5 結論

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