一种基于混沌系统的ZUC动态S盒构造及应用方案

韩妍妍 何彦茹 刘培鹤 张 铎 王志强,2 何文才

1(北京电子科技学院 北京 100070) 2(国家信息中心 北京 100070)

ZUC密码算法[1]，又称祖冲之密码算法，是一个面向字设计的同步序列密码算法，已在2011年被正式批准成为3GPP LTE国际标准密码算法.该算法在设计时充分考虑了软硬件的可实现性，具有较低的复杂度，是一种应用较为广泛的轻量级密码算法.算法的结构主要包含3个基本组成部分，分别是上层线性反馈移位寄存器LFSR、中间层比特重组BR，以及下层非线性函数F.其中，非线性函数F这部分主要依靠唯一的非线性部件S盒来扰乱LFSR层输出的序列，进而增强算法的安全性.ZUC算法中的S盒是由4个8×8的非线性置换S盒共同构成，即S=(S0,S1,S2,S3).其中S0和S2相同，S1和S3相同.由此可见，ZUC算法中所使用的S盒均是固定不变且未进行复杂混乱过程.因此，设计具有良好性能的S盒是提升ZUC算法性能的一个重要因素.

然而，这些基于混沌思想所构造S盒的方法，通常在非线性度、DP和LP等性能方面与传统的数学构造方法有一定差距.与此同时，上述设计S盒方案虽然能够满足基本的置乱特性，但效果并不理想，且由于方案设计的开销大，造成硬件的可实现性较差.本文基于这些特点提出了复合混沌系统的思想，选取混沌特性良好的Tent和Henon两个混沌映射进行叠加，同时将图像置乱的思想引入到S盒的设计中来，利用Arnold映射对复合混沌系统所产生的S盒进行二次置乱，大幅度提高了S盒的非线性度.此外，通过对初始值和控制参数的控制和改变，可以动态地生成不同的S盒.最后，选取一些本文构造的S盒进行DP和LP的性能测试和分析，并与其他设计方法进行对比.此外，将本文利用混沌系统所产生的动态S盒用于替换ZUC算法中固定的S盒，并对其进行软硬件实现的性能测试，实验结果表明:本文构造方案所得S盒密码学特性良好，在增强ZUC算法密钥序列的随机性的同时，也兼具较好的软硬件可实现性.

1 相关描述

1.1 ZUC算法的S盒设计

S盒是ZUC算法中非线性函数F层的重要部分，也是算法中唯一的非线性部件.ZUC序列密码算法的S盒设计本着高非线性度、低差分均匀性、硬件实现开销低等原则，共包含4个非线性置换S盒，分别是S0,S1,S2,S3.其中，S0与S2相同，S1与S3相同.S0和S2采用3个4输入的置换表，结合异或和移位操作进行构造.S1和S3是由一个简单仿射变换算法和另一个求复杂有限域GF(28)上的乘法逆元算法构成.S0和S1的定义分别如图1、图2所示.

若将S0(或S1)的8比特输入设为x，并用x表示2个16进制数的连接，即x=h‖l，那么S0(或S1)的输出S0(x)(或S1(x))则为图1(或图2)中第h行和第l列交叉的元素.

设S盒的32比特输入X和32比特输出Y:

X=x0‖x1‖x2‖x3,

(1)

Y=y0‖y1‖y2‖y3,

(2)

其中,xi和yi均为8比特字节，i=0,1,2,3.则有yi=Si(xi)，i=0,1,2,3.

Fig. 1 S0-box图1 S0盒

Fig. 2 S1-box图2 S1盒

1.2 S盒及其设计准则

S盒又被称为置换盒，本质上可以看作是一张映射表，它是很多密码算法设计过程中唯一的非线性部件.因此，可以说在一定程度上一个密码算法的安全性强弱与S盒本身的设计息息相关.S盒的映射一般表示为

S(x)=(f(x1),f(x2),…,f(xm)):
GF(2n)→GF(2m),

(3)

也常表示为S:{0,1}n→{0,1}m，它是将n位输入映射到m位输出的非线性过程.目前普遍研究和使用的是8×8 S盒.经过众多专家和学者对S盒的大量设计和研究，提出了6个用于衡量S盒是否具有优异密码学性能的测试指标.下面分别详细介绍这6个重要检验指标.

1.2.1 双射特性

S盒在用于置换时，通常要求其满足双射特性，即S盒必须可逆.文献[15]提供了判断S盒是否满足双射特性的检验方法.当m=n时，S盒需满足的充要条件是：所有分量布尔函数fi的线性运算之和为2n-1.

1.2.2 非线性度

(4)

其中,Ln表示全部n元线性和仿射函数集合；dH(f,l)表示f和l的汉明距离.

1.2.3 严格雪崩准则(SAC)

在实际使用时，S盒的严格雪崩准则(strict avalanche criterion, SAC)是按照依赖矩阵[18]方式来计算.其中，矩阵中理想值为0.5，如果所有的值都与该理想值接近，则认为这个S盒完全符合严格雪崩准则.

1.2.4 输出间比特独立性(BIC)

定义3[19].对S盒的2个输出比特fj和fk(j≠k)，如果fj⊕fk具有很高的非线性，同时符合严格雪崩准则的相关要求，则可以保证一个输入比特对进行取反操作时，对应的输出比特对相关系数趋近于0.因此，测试S盒的比特独立性(bit inde-pendence criterion, BIC)性能时，可以对fj⊕fk的非线性度进行计算并判断其对SAC的满足程度.

1.2.5 差分均匀性

差分均匀性[20]是判断S盒在密码算法中抗差分能力强弱的重要指标.在实际计算时，输入和输出之间的异或分布情况通常用差分逼近概率DPf表示：

(5)

其中,X表示所有可能输入的集合，2n是该集合的元素个数，#表示计数，DPf表示输入改变量Δx时输出改变量Δy的最大可能性.

1.2.6 线性逼近概率

定义4[21].线性逼近概率LPf.

(6)

LPf(α,β)=(2p-1)2,

(7)

(8)

其中,ξ∘α=ξ1α1⊕ξ2α2⊕…⊕ξnαn，#表示计数.

1.3 2种经典混沌系统

众所周知，混沌系统一般都具有显著的伪随机性和高度的初值敏感性，能够起到增强置乱的作用，特别适合用在S盒设计中.Tent映射和Henon映射是代表性较强的2种混沌系统，本文对这2种经典系统进行迭代，形成新的复合混沌系统.

1) Tent映射系统[22]是一种经典的离散混沌映射系统，目前，利用Tent映射产生的混沌序列在构造混沌加密系统及实现混沌算法等领域中有着非常广泛的应用.Tent系统映射方程为

(9)

当变量xn∈(0,1)，且q∈(0,1)时，系统处于混沌状态.

2) Henon映射系统[23]是1976年由Henon提出的一个二维离散混沌系统，其映射方程为

(10)

其中，当系统参数1.07≤a≤1.4，b=0.3时，系统处于混沌状态.且当变量xn∈(-1.5,1.5)时，取a=1.4，该系统复杂度最大.

2 S盒构造方法

2.1 基于复合混沌系统的S盒设计

本文提出一种基于复合混沌系统的动态S盒构造方案.通过对Tent和Henon两个混沌映射进行复合，结合混沌映射的迭代，生成一个具有良好性能的8×8 S盒.该方法的具体设计步骤为：

2) 取初值x0，经过式(9)迭代一次得到x1，则第1个小区间上的点表示为x1×l+0×l；迭代n次得到xn，第n个小区间上的点表示为xn×l+(n-1)×l，最终得到n维序列X.

3) 选取2)中得到的序列X为Henon映射的初值，其中令Henon映射中每次x和y的值保持一致，且均来自于序列X，然后经过式(10)进行N次迭代，取所有的y值构成第2个序列Y1.

4)Y1序列中的每个元素分别属于1～m区间中的一个，依次将元素所在的区间序号记为i，Y2=i(mod 256).

5) 在Y2序列中按先后顺序选取256个不相同的元素构成新序列Y，Y序列即为所求的S盒.

上述设计中，Tent映射中q=0.5时，系统呈现短周期状态，因此q值应避免选择0.5.此外，在应用时也应避免选取和q值相同的初值，以防止系统演化为周期系统.改变参数q的取值，不仅能够实现动态产生S盒，而且可以增强混乱效果.上述步骤只涉及简单的排序和取余操作，可以有效减少算法运行过程的消耗，有助于提升运行速度和效率.最后对生成S盒的DP,LP值进行统计和分析，筛选出具有较好的密码学特性的S盒，否则对初值进行改变，重复以上5个步骤继续生成符合要求的S盒.

本文在实际S盒生成的过程中，式(9)中Tent系统参数选取q=0.4，式(10)中Henon系统参数选取a=1.4，b=0.3.当迭代次数n=5 838，N=5 000，初始值x0=0.3时，获得的混沌系统生成的S盒密码性能较为良好，如图3所示，其中DP=0.046 875 0，LP=0.132 813.

2.2 S盒重构

本文结合图像加密中使用的置乱方法，重构上述复合混沌系统构造方法得到8×8 S盒.在混沌系统产生8×8 S盒后，引入Arnold映射对其进行置乱，将其中数据的位置进行打乱重排，从而实现二次置乱.Arnold映射是一种具有周期性的映射，常应用于混沌序列的置乱过程，可表示为

(11)

为了便于应用，通常把它写成矩阵形式：

(12)

其中，S盒的行数和列数用n表示，且p=16.若数据在原始S盒中的位置坐标为(x,y)，则经过Arnold映射置乱后的新位置坐标变为(x′,y′).

将上述密码学性能最好的S盒进行重构后得到新的S盒如图4所示，其中DP=0.0390625，LP=0.109 375.由此可见，经过Arnold映射二次置乱后的结果与置乱之前相比，提升了的S盒性能.

Fig. 4 An example of the reconstructed S-box图4 重构后的S盒示例

3 算法安全性分析

3.1 S盒安全性分析

本文所设计的S盒的构造过程可分为2部分：第1部分为基于复合混沌系统的S盒设计过程；第2部分为S盒重构过程.图5、图6分别为基于复合混沌系统及重构后所产生S盒的LP值分布图.

Fig. 5 LP value distribution of S-box generated based on combined chaotic systems图5 基于复合混沌系统生成S盒的LP值分布

Fig. 6 LP value distribution of the refactored S-box图6 重构后S盒的LP值分布

在这1 000个S盒中，混沌系统所产生的S盒的LP值的主要集中在0.125 000，而重构后的S盒的LP值的主要集中在0.109 375.由此可见，经过Arnold映射置乱重构后的S盒具有更好的非线性特性.

本文选取上述重构后性能最优的一个S盒作为分析对象，同时选取了其他3种同类的性能优良的S盒进行对比分析，分别是文献[12-13]以及ZUC算法中所涉及的S盒.其中，ZUC算法有2个不同的S盒，本文选取其中一个为例，即S0盒，对6项性能指标的分析均按照选取的对象进行比对.

3.1.1 双射特性

根据判断S盒满足双射特性的充要条件，可知本文构造的8×8的S盒，其分量布尔函数的线性运算和的平均值是128，最大值和最小值也都是128，如表1所示.经过对比可见，本文产生的S盒均符合双射特性的判断标准.

Table 1 Comparison of the S-box Bijective Properties表1 S盒双射特性对比

3.1.2 非线性度

在实际应用中，计算布尔函数f(x)的非线性度一般通过Walsh-Hadamard变换实现.本文应用Walsh谱表示f(x)的非线性度，具体表达式为

(13)

其中，x·ω表示x与ω的点积.

在密码分析中，非线性度Nf与抗线性攻击正相关，Nf越大表明其能力越强，即S盒的抗线性分析性越好.本文利用式(4)和式(13)计算本文所构造S盒的非线性度，最大值为106.通过表2所示的对比结果可知，本文所构造的S盒在抵抗线性密码分析方面性能良好.

Table 2 Comparison of the S-box Nonlinearity表2 S盒非线性度对比

3.1.3 严格雪崩准则(SAC)

严格雪崩准则是用来描述序列输入和输出变化相关性的重要标准.Webster等人[19]提出了适用于S盒性能评价的计算方法.因此，一般使用相关矩阵中元素的平均值来衡量S盒是否满足该准则，若相关矩阵的元素值越趋近于0.5，则表明S盒越满足严格雪崩准则.本文所构造出的S盒相关矩阵的平均值与其他文献中S盒对比结果如表3所示，可见本文所构造的S盒与0.5更接近，因此性能更好.

Table 3 Comparison of the Mean Values on S-box Correlation Matrix

3.1.4 输出比特间独立性(BIC)

输出比特间独立性一般用于判断，如果2个雪崩分量独立不相关，说明此时S盒具有良好的随机性.S盒的布尔函数分量可表示成f0,f1,…,fn，若S盒满足BIC-SAC，则fj⊕fk(j≠k,1≤j,k≤n)应满足严格雪崩准则.如果S盒的BIC-SAC值逼近于0.5，说明其随机性良好，并且越接近这一逼近值性能越好.本文所构造的S盒的BIC-SAC值的平均值为0.504 9，与其他文献中的S盒相比可见，其具有相对较好的BIC特性.与其他同类方案相比，得到的对比结果如表4所示:

3.1.5 差分均匀性

衡量S盒抗差分密码攻击性能时，通常使用差分逼近概率DPf这一重要指标.DPf值与抗差分攻击能力反相关，值越小说明抗差分攻击能力越强.由式(5)可以计算出本文构造S盒的差分分布最大值是10，即DP=0.039 062 5.与其他文献所构造S盒的DP值对比结果如表5所示:

Table 5 Comparison of DP and LP Values on S-box表5 S盒的DP,LP值对比

3.1.6 线性逼近概率

线性逼近概率LPf通常用来证明S盒抵抗线性密码攻击的能力，LPf也与抵抗线性攻击的能力反相关，值越小越能说明抵抗线性攻击的能力强.本文构造的S盒的LPf值根据式(6)～(8)进行计算.最后，S盒的DPf和LPf，与其他文献中构造的S盒的DPf和LPf对比如表5所示.可见，本文构造的S盒具有较小的差分概率及线性概率，能有效抵抗差分密码攻击及线性密码攻击.

3.2 基于混沌系统的ZUC算法安全性分析

ZUC算法是一个面向字设计的序列密码，分析序列密码安全性的核心是检验其密钥流序列的随机性.NIST检测方法[24]为序列密码的安全测评提供了理论分析的数据基础，不仅可以减少一定的工作量，同时可以暴露出理论分析无法发现的安全漏洞.因此，本文选用NIST随机性检测方法分别对ZUC算法以及基于本文所构造的混沌S盒的优化ZUC算法进行安全性测试，如果测试结果的P-value值均大于0.01，则可证明算法通过测试.

3.2.1 密钥序列生成

在密码学中，当一个算法初始密钥和初始向量均设置为“0”，将会生成随机性最差的密钥流[25].如果此时产生的序列能通过随机性检测，则意味着它在其他情况下也可以通过测试.因此，本文通过设置初始密钥、初始向量为“0”进行测试，同时选取密钥字个数为40 000.此时，我们便可以得到2个40 000×32 b的密钥流序列，分别对应的是ZUC算法及本文所设计的基于混沌S盒的ZUC算法，然后以二进制表示形式分别存入文件key1.txt和key2.txt中作为待测序列.

3.2.2 sts-2.1.2软件随机性检测

在Windows系统下安装“sts-2.1.2”和“cygin”软件，进入测试包所在目录进行测试，ZUC算法以及基于本文所构造的混沌S盒的优化ZUC算法的NIST测试结果对比如表6所示:

Table 6 P-value Comparison of NIST Test Results表6 NIST测试P-value值结果对比

由表6可以看出，基于混沌S盒的ZUC算法的16项测试项的结果显著，所有P-value值均大于显著水平α(其中α=0.01)，且全部优于ZUC算法本身.因此，基于混沌S盒的ZUC算法生成的密钥流序列随机性较好.

3.3 基于混沌S盒的ZUC算法的实现及性能分析

3.3.1 算法实现

本文通过使用标准C语言对算法进行软件实现，然后再将其移植至单片机上，软件实现的结果如图7所示，图中所展示的是基于混沌S盒的ZUC算法的部分密钥序列.

Fig. 7 Partial key sequence of ZUC algorithm based on chaotic S-box图7 基于混沌S盒的ZUC算法部分密钥序列

3.3.2 算法性能分析

对于基于混沌思想的S盒设计而言，还要考虑其软硬件的实现性能.本文分别对基于混沌S盒的ZUC算法的软硬件实现性能进行了测试.

本文的软件实现利用PC机进行，其中PC机的操作系统为Windows 10 64 b，CPU为Intel®CoreTMi5-3337U@1.80 GHz，RAM为8 GB，通过Visual Studio2012编程软件进行测试，按照基于混沌思想的S盒设计方案替换ZUC算法中的固定S盒，分别从代码大小、运行时间和系统占比3个方面进行性能对比和分析.从表7可以看出，增加动态S盒部分的设计之后，代码大小增长了40%，占系统RAM百分比增长了0.3，但运行时间仅增加0.01 s，对算法本身的运行性能并未产生很大的影响，在可接受范围内.

Table 7 Algorithm Software Implementation Performance表7 算法软件实现性能

本文的硬件实现采用ATmega8A型8 b微控制器，片内SRAM为512 KB，同样按照设计方案分别从代码大小、运行时间和系统占比3个方面进行了性能的对比和分析.从表8可以看出，在本文的硬件运行环境下，相较于软件实现而言，ZUC算法本身的代码大小变大.这是由于单片机本身的通信接口等定义，占用了一小部分存储空间，但与算法本身所需存储空间相比，可忽略不计.在加入混沌动态S盒设计之后，代码大小增加了38%，占系统RAM百分比增长了3，运行时间仅增加0.11 s.但这是由于单片机的性能远不如PC机，对算法的硬件实现效率来讲并未产生很大的影响，完全在可以接受的范围内.

Table 8 Algorithm Hardware Implementation Performance表8 算法硬件实现性能

基于混沌S盒的ZUC算法的软硬件性能测试表明，该方案不仅提高算法的安全性, 也具有较好的软硬件可实现性.

3.3.3 算法的应用场景

本文将基于混沌S盒的ZUC算法应用于自己搭建的轻量级物联网平台中，对整个物联网平台系统中的感知层资源受限设备所采集的数据进行加密，并将密文数据传输并存储在物联网平台的数据库中，便于合法授权用户进行数据的统一管理，提高了数据在采集、传输及存储全流程的安全性.

通过使用超级终端对数据采集和传输的过程进行监控，可以看到经过单片机后数据已经被加密，传输过程中的数据为密文形式，如图8所示：

Fig. 8 Ciphertext transmission of data图8 数据的密文传输

数据上传至平台端，也是以密文形式在数据库中进行存储，如图9所示：

Fig. 9 Data of ciphertext stored in the database图9 数据库中密文形式的数据存储

4 结 论

本文所提出的S盒设计方法是基于2个经典混沌系统的复合，并将Arnold映射引入方案设计中进行二次置乱和重构.通过将本文构造的S盒严格按照S盒设计准则进行安全性分析，并与前人所提出的方法做了充分比较，验证了本文所构造S盒的密码特性.安全性分析结果表明:此方案产生的S盒相比于ZUC算法及其他相关文献具有更高的安全性，并能实现动态生成性能良好的S盒，替换ZUC算法中的2种固定的S盒.最后，本文对基于混沌S盒的ZUC算法进行了NIST随机性测试和软硬件性能测试，结果表明:本文所构造的S盒安全性更高，不仅增强了ZUC算法所产生密钥流序列的随机性，还兼具较好的软硬件可实现性，可应用于资源受限的物联网设备中的数据加密过程.