2.3 基于混沌的动态S盒分组加密算法

目前，绝大多数分组加密的S盒都是固定不变的，比如DES，AES等。但也有少数算法的S盒与密钥有一定的相关性，如IDEA。在加密算法中，使用动态S盒的一个很大优点是由于S盒不固定，若要事先分析S盒以寻找其弱点是不大可能的，因此从这一点上看，使用动态S盒的加密算法通常具有更好的安全性。本节，我们将首先提出一种S盒构造算法，然后再以此为基础设计一种动态S盒的分组加密方案。

2.3.1 混沌映射的选择与分析

选择式（2.31）所描述的分段线性映射（PLCM）：

式中x∈(0,1),b∈(0,1)，作为构造S盒的基本混沌映射。这是因为由PLCM产生的混沌信号不仅具有很好的遍历性，而且其概率密度是均匀的，对不同的控制参数都拥有接近一致的、不变的分布密度。图2.9为参数b分别为0.1和0.9时的概率密度分布。

虽然混沌从整体上看来类似于噪声信号，但它的迭代具有确定的规则，两个混沌信号间相距的迭代步数越小，它们之间的关系受到这种确定性规则的制约就越强。通过大量的数值仿真，我们发现分段线性映射同样存在着这种确定的制约。为了显示这种制约，定义混沌系统相邻两个状态的差的绝对值为d1, 即d1=|xn+1-xn|，类似地定义dk =|xn+k -xn|，图2.10为式（2.31）在不同控制参数下的 d 1分布。从这两幅图可以看出，虽然分段线性混沌系统的状态分布具有良好的一致性，但在相距较小迭代步数时，混沌状态之间的差值分布还是严重泄露了系统的重要信息。在图2.10中，分布曲线分别在0.4，0.3，0.2和0.1附近发生了阶跃，且发生阶跃的位置与参数b的大小相关，随着b的增大，阶跃位置逐渐减小，而且阶跃点两边接近于水平的差值分布说明分段线性混沌系统相邻状态之间有着极强的确定性制约。同样地，这种制约和参数b在二阶差值分布上也被显现了出来，如图2.11所示。

对于一个各元素在序列中出现概率相等，且任意元素之间没有任何制约的真随机序列，其差值的绝对值分布应该是随着差值从小到大增长，概率从大到小线性递减，直至为0。为说明这个问题，请考虑由数字0～9组成的真随机数序列：当差值d为9时，只有一对数(9, 0)能够满足，简记为#{d=9|(0, 9)}=1，其中符号#表示集合中元素的个数。不难发现，#{d=8|(0, 8), (1, 9)}=2, #{d=7|(0, 7), (1, 8), (2, 9)}=3, #{d=6 |(0, 6), (1, 7), (2, 8), (3, 9)}= 4, #{d=5 |(0, 5), (1, 6), (2, 7), (3, 8), (4, 9)} =5, #{d=4 |(0, 4), (1, 5), (2, 6), (3, 7), (4, 8), (5, 9)} =6，以此类推得#{d=3}=7, #{d=2}=8，#{d=1}=9，#{d=0}=10，#{d=10}=0。由于随着d的增大，满足条件的元素对数线性减少，决定了d值的分布概率线性递减。

对比图2.10和图2.11，可以看到在d2密度分布中出现了更多的阶跃，这表明xn对xn+2的制约比对xn+1弱一些，即从xn+2推出xn要比从xn+1难一些。因此为了保证密码算法的安全，抵抗差分攻击，混沌映射的迭代数应该大于一定的值，以便让产生的混沌值在各方面的表现对分析者而言与真随机信号类似，从而很好地隐藏混沌系统确定性的一面，并充分发挥其伪随机性（或类噪声）的一面。通过数值试验，发现随着迭代次数k的增加，dk的密度分布中会出现更多的阶跃。当k≥30时，dk的分布具有很明显的线性下降特征，与真随机数的差分密度分布类似。图2.12为d30的在不同b值下的密度分布。因此，在将方程（2.31）应用于加密时，所利用的状态值之间的间隔最好能够不小于30。

2.3.2 S盒构造算法描述

选择式（2.31）所描述的分段线性映射作为迭代产生S盒的混沌映射，具体设计步骤如下：

步骤1，设置初始值n = 2N , N为大于0的整数。任意设置整数序列Y为n个整数（0, 1, … , n-1）的所有排列中的一个。创建一个初始时不包含任何整数的序列S。

步骤2，任意选取式（2.31）的初值x0和参数b。为消除初值影响，将方程（2.31）迭代30次。

步骤3，将式（2.31）的混沌空间[0, 1]均分为 n个子区间，分别表示为 Ti（i=0, 1,…,n-1），且Ti=[ti,ti+1）,ti=i/n。

步骤4，将整数序列Y中的第i个整数作为区间Ti的标识符。

步骤5，将式（2.31）迭代32次。设当前的状态值为x′。找出x′所在的子区间和该子区间的标识符（记为A）。

步骤6，将A加入到序列S的末尾。

步骤7，设置Y=Y-{A}，即将整数A从整数序列Y中删除，并将删除了整数A后的序列Y-{A}作为下一次处理的Y。如果n＞0，那么设置n = n-1，并转步骤3。

步骤8，将整数序列S中的元素，转化为的表格，即得到N×N的S盒。

2.3.3 S盒仿真试验与性能测试

根据2.3.2节中介绍的S盒设计方法，设置N = 8，初值为x0=0.1234567，b=0.7654321，整数序列按照从小到大的顺序排列，即Y=（0, 1, … , n-1）。产生的S盒如表2.10所示。

参照2.1.2节介绍的方法，测试此8×8的S盒是否具有良好的密码学特性：

①双射特性：依次取a=(a 1,a2,…,an)为1，2，…，255并根据式（2.1）计算得到此S盒的所有汉明权重均为128，说明它满足双射特性。

② 非线性特性：通过计算，上述S盒的8个布尔函数的非线性度分别是104, 102, 102, 104, 110, 106, 104,106，都在100以上。由此看见，算法所构造的S盒具有较高的非线性度，能够抵抗“最佳线性逼近”的攻击。

③ 严格雪崩效应：采用计算相关矩阵的办法进行检验。计算结果显示，在相关矩阵中没有等于0的元素，所有元素的平均值为0.5010，与理论值0.5非常接近（参见表2.11）。说明所设计的S盒能够很好地满足严格雪崩效应。

④ 输出比特间独立特性：此处采用文献[80]所提出的方法，通过计算S盒中任意两个布尔函数fj，fk( j≠k)的异或结果f j⊕ fk是否具有高度非线性和几乎满足严格雪崩效应准则，来检验S盒的输出比特间独立特性。相应的计算结果如表2.12和表2.13所示。从计算结果中可以看到，所有的 f j⊕ fk均具有较高的非线性度和很好的SAC特性，所以该S盒具有较好的输出比特间独立特性。

⑤ 输入输出差分分布：此处采用计算差分逼近概率的方式来对此特性进行检验。根据式（2.7）进行计算，将其最大出现次数的分布列于表2.14。从中可以看出，其中最大值只有10，最小值为4。说明所构造的S盒具有很好的抵抗差分密码分析的能力。

从上面测试的数据来看，虽然按照该算法所产生的S盒与AES等传统密码算法的S盒相比在某些特性上还存在一定的差距，但是此算法所产生的S盒还是具有十分良好的密码学特性，能够满足数据加密的需要。提出的S盒构造算法由于充分利用了混沌映射的初值敏感性、非线性和遍历性等特性，因此微小的改变初始值x0和参数b，都可以产生另一个具有良好密码学特性的S盒。此外，在产生第一个S盒之后，按照相同的方式，继续迭代混沌映射还可以产生下一个具有良好密码学特性的S盒。重复此过程若干次，可以得到一系列良好密码学特性的S盒。所以，此处介绍的S盒构造算法不仅可以用于设计静态的S盒，而且还为设计动态S盒的加密算法提供了很好的支持。

2.3.4 一种基于动态S盒的加密算法[10,50]

① 相关问题分析

对于2.3.2节提出的S盒构造算法，分析其构造过程可知：除去为消除初始值影响而进行的30次混沌映射迭代，每产生S盒中的一个元素，需要迭代混沌映射32次。因此，在N=8即产生一个8×8的S盒时，总共需要迭代混沌映射8192次。如果每个8×8的S盒只用于加密一个字节，这意味着在付出迭代混沌映射8192次的代价之后才仅仅只加密一个字节，显然其效率是不高的。为此考虑从两个方面来解决效率不高的问题：第一，减少产生S盒时所需要的迭代混沌映射的次数；第二，用一个S盒加密多个字节。

一方面根据2.3.1节的分析可知，为了增强抗差分攻击的能力，选取的混沌状态值之间的间隔不应少于30。由此可见，直接减少迭代次数似乎是不可行的。将抽取的混沌状态值之间的间隔由32减少为30，并不能显著提高效率。2.3.2节的S盒构造算法针对的是产生一个S盒的情况，因此在产生S盒中的元素时只使用了32次混沌迭代中最后一次的状态值。当需要产生大量的S盒时，可对2.3.2节的算法做细微的调整，以便充分利用每次迭代的状态值，即利用状态值(xi,xi+32,…,xi+32 k)，(xi+1,xi+1+32,…, xi+1+32k),…,(xi+31,xi+31+32,…,xi+31+32 k)，分别产生32个S盒，从而显著提高产生S盒的效率。

另一方面，根据现代密码学中的唯一解距离来确定一个S盒至多可以加密多少个字节。在加密方案中，将方程（2.31）的初始值x0，参数b和整数序列Y的任一排列作为加密的密钥。在双精度范围内初始值和参数均有248种可能的取值，且整数序列Y是整数0,1,2,…,255排列中的一种，即有256!种可能。用表示初始值为，参数为b′，整数序列为Y′时的概率。由于x0、b和Y的取值相互独立，因此 ，对应的信息熵 。假设加密的明文是由英文字母组成的消息，而各个英文字母及空格在消息中出现的概率有一个公认的近似值[89]，通过此近似值可以算出其熵H(pi)≈2.80。另外，假设加密后密文字符的分布是等概率的，即P{ci=n}=1/256。因此。由于明文/密文在 n较小时一般都可看成近似随机信号，即H(p1…pn)≈nH(pi), H(c 1…cn)≈nH(ci)。根据信息论中的相关结论得：

要确定子密钥k，含糊度H(k|c1…cn)必须为零，根据式（2.32）可以确定唯一解距离n0为：

n0≈H(k)/(H(ci)-H(pi))=1780/(8-2.8)=342.3

在本小节的前面部分介绍过为了提高S盒的产生效率，在迭代过程中充分利用所有的状态值，会同时产生32个S盒。因此，可将需要加密的明文以32字节为一个单位，划分为若干个分组。根据唯一解距离的计算结果并考虑一定的富余，在产生的32个S盒不变的情况下，设置加密的分组个数为10（320个字节），即在加密10个分组之后需要产生新的用于加密的S盒。

② 加密算法

基于动态S盒的加密算法如下：

步骤1，选用式（2.31）作为迭代产生S盒的混沌映射。将式（2.31）的初值x0和参数b，以及一个包含256个元素的整数序列Y作为算法的加密密钥，其中Y为整数（0, 1, 2, …, 255）的一个排列。

步骤2，将明文m划分为若干个长度为32字节的分组，若最后一个分组长度不够，则进行补齐操作，即

式中pi为明文m中的第i个字节。

步骤3，为避免初始值的影响，将混沌映射式（2.31）迭代30次。

步骤4，通过迭代混沌映射式（2.31）产生32个不同的S盒（n×n）。产生S盒的细节与2.3.2节中介绍的方法类似，但由于需要一次性地产生32个S盒，因此在实现上稍有不同，具体描述如下：

（1）设置变量j的初始值为0，变量d的初始值为256。将作为密钥的整数序列Y赋给32个整数序列Si（i=0,1,…,31）。

（2）将式（2.31）的混沌空间[0,1]均分为d个子区间，分别表示为Ti（i=0,1,…, d-1），且Ti=[ti , ti+1], ti = i/n。

（3）将d个子区间与整数序列Si（i=0,1,…,31）中的前d个元素依次建立对应关系，即得到32个一一映射，将这些映射表示为fi（i=0,1,…,31）。

（4）将混沌映射式（2.31）迭代1次，通过映射fj找到序列Sj中对应的整数k，将整数k移动到序列Sj的末尾，将原来位于整数k后的所有整数依次向前移动一个位置。同时，根据式（2.33）调整j的值：

（5）如果j不为0，转步骤4，否则按照式（2.34）和式（2.35）调整混沌映射式（2.31）的状态值x和变量d的值：

式中，Si(256)为整数序列Si中的第256个整数的值。

（6）如果d不为0，转步骤3，否则将整数序列Si(i=0,1,…,31)转换为32个S盒。

步骤5，利用此32个S盒，通过置换和移位操作加密10个明文分组。为描述方便，定义SB i, pi 分别为第i个S盒和明文块中的第i个字节。对明文块进行31轮的置换和循环左移操作，如图2.13所示。

步骤6，如果对所有明文块均进行了加密，则加密过程结束。否则进行密文反馈处理，计算D=(D1+D2+…+D10)mod 256，其中Di =c 0⊕c 2⊕…⊕c31为S盒所加密的第i个密文分组中各字节值之和。然后将混沌映射式（2.31）迭代D次，并转步骤4。

③ 解密算法

解密算法与加密算法类似，其中步骤1至步骤4的操作与加密算法完全相同。只是在步骤5中需要对密文块进行逆置换和循环右移操作，而对于反馈的迭代次数D可以直接根据密文计算出来。

④ 仿真测试

对此加密方案进行仿真测试，让它加密两种不同类型和尺寸的文件：

文件1：名为Lena的图像文件（.bmp），其尺寸为143KB；

文件2：随机选择一个由40000个字符组成的文本文件。

设置密钥为：x0=0.1234567，b=0.7654321，Y=（0, 1, … , n-1）。原图像、加密图像以及对应的图像直方图如图2.14所示。原始文本文件和加密后文件中每个字节的值在0～255之间的出现次数分布如图2.15所示。从仿真结果看，算法具有很好的混乱和扩散特性。

⑤ 安全性分析

（1）S盒的特性分析

在上述加密方案中，动态产生的S盒是其中最为核心的部件，它们对整个加密系统有至关重要的影响。在加密算法中，加密完10个明文分组后由于通过密码反馈方式对混沌映射的迭代次数进行了调整，因而使得下一次产生的S盒不仅与密钥相关，而且还与密文相关，进而与明文相关。因此要测试加密过程中的S盒，需要确定明文。图2.16至图2.21为加密Lena图像时所产生的前5000个S盒的密码学特性。由产生S盒的算法知道这些S盒均满足双射条件。从图中可以看出：（i）绝大部分S盒的最小非线性度均在90以上，仅有2个（占总数的0.04%）S盒的非线性度为88，说明这些S盒具有很好的非线性度特性；（ii）这些S盒的相关矩阵的平均值均在0.5附近微小波动，说明它们具有很好的雪崩特性；（iii）对任何的 f j⊕ fk，j,k∈{1,2,…,n},且j≠k，均具有很好的非线性特性和雪崩特性，因此可以说这些S盒具有很好的输出比特间独立性；（iv）对于绝大多数S盒，其输入输出差分分布频率表中的最大值在10～14之间，仅有约0.44%的S盒的最大频率值超过了14，且最大值也仅为18，说明这些S盒均具有很好的抗差分攻击的能力。除了对加密Lena图像时所产生的S盒进行了测试之外，我们还随机挑选了一些不同类型，不同大小的文件，对其加密过程中所产生的动态S盒进行了测试。总共测试的动态S盒为50000个，测试结果表明，绝大多数S盒具有不错的密码学特性，仅有个别S盒（约占总数0.042%）的某一项指标不能到达非常理想的值，而且这样的S盒没有连续出现。在加密过程中，即使有某个S盒的某项密码学特性不是十分理想，但经过32轮的置换和移位变幻后也能弥补其中存在的不足，保证整个加密系统的安全。

（2）密钥空间及其敏感性分析

在加密算法中，混沌映射的初始值x0、参数b和整数序列Y为密钥。对密钥空间的分析如下：（i）由于整数序列Y中共有256个元素，这256个元素的任一排列都可作为密钥，因此密钥总数为256!，约为21684；（ii）x0和b的取值范围为（0, 1），根据IEEE的浮点数标准可以推出其可能的取值约为1015，两者合在一切约为1030。显然，算法总的密钥空间远大于2100的要求，能有效防止对加密算法的暴力攻击。

在加密算法中，S盒是根据混沌映射的状态值与整数序列Y之间的对应关系产生的。由于混沌映射的状态值与初始状态值x0和参数b密切相关，因此S盒与x0和参数b密切相关，所以借助混沌映射的初值敏感性，能够有效保证密文敏感的依赖于x0和参数b。另外，在算法中，还根据式（2.34），用 Y中的元素对混沌映射的状态值进行了细微的调整，以便进一步增强密文对序列Y的敏感性。

为对密钥的敏感性进行测试，将上述仿真测试中所使用的密钥做如下细微调整：

1）将x0由0.1234567更改为0.1234568；

2）将b由0.7654321更改为0.7654322；

3）将Y由（0, 1, … , n-1）更改为（1, 0, … , n-1）；

分别用调整后的密钥加密图像Lena，得到的密文与原密文之间的差别（此处仅给出了前2000个密文字节的差别）如图2.22所示。

（3）抗攻击能力分析

根据攻击者所具有的攻击条件的不同，攻击分为4类：唯密文攻击、已知密文攻击、选择明文攻击和选择密文攻击。就此处提出的加密算法而言，攻击者除了直接攻击密钥之外，还可以攻击算法中的S盒。由于在算法中使用的S盒是动态变化的，因此针对静态S盒的分析方法在此处无法发挥作用。算法中还采用了密文反馈的模式，这使动态产生的S盒不仅与密钥相关而且还与明文信息相关，因此攻击者不可能通过对比明密文来获得有用的信息，所以算法能有效抗击已知明文攻击和选择明/密文攻击。而对于唯密文攻击，我们根据唯一解距离，通过限制S盒加密的分组个数为10，可保证算法的安全性。

⑥ 加密速度分析

在本算法中，加密一个明文分组（32字节）所需要的主要计算有：（1）产生32个S盒；（2）32轮的置换与移位运算；（3）密文反馈运算。相对（1）、（2）两项而言，第（3）项运算量很小，可以忽略不计。因此，只对前两项进行讨论。由加密算法知，1个字节的明文需要进行32轮的置换和移位，产生32个S盒需要迭代混沌映射8192次，且此32个S盒可以加密10个明文分组，因此加密一个明文字节的运算约为迭代混沌映射25.6次和32轮的置换和移位。这样的运算量对现代计算机而言是微不足道的，表明此算法具有较快的执行速度。