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算法输出具有良好的随机性。