第2章 基于混沌的分组加密算法

保障信息的安全有多种手段，对信息进行加密是最为常见的一种方式。对加密算法进行研究始终是信息安全领域的一项重要内容。加密算法通常分为分组密码和流密码两大类。在现代密码学中，分组加密算法常常是关注的焦点，应用非常广泛。除用于信息加密外，分组加密算法还被用于构造单向散列函数、消息认证码等方面。当前使用较多的分组加密算法有DES、AES、IDEA等加密算法。与现代密码学中的分组加密算法相比较，基于混沌的分组加密算法还不成熟，尚未形成实际应用中的标准。但是该领域的研究已经得到了广泛的重视，已有学者提出了不少具有应用潜力的基于混沌的分组加密算法。

2.1 基于混沌的S盒设计方法

2.1.1 S盒简介

S盒（substitution box）首次出现在Lucifer算法中，随后因DES的使用而广为流传，至今仍是建造分组密码系统的主要元件之一（如15个AES候选算法中，就有9个采用了S盒）。它是许多分组密码算法中的唯一非线性部件，为密码系统提供Shannon所描述的混乱作用，其密码强度决定了整个密码算法的安全强度。因此，如何全面准确地度量S盒的密码强度，如何设计一个非线性度高的S盒是分组密码设计的关键，也是分组密码设计和分析中的难题。经过多年的研究，学术界提出了许多构造S盒的方法。在许多充满竞争的思想中，被认同的有如下4种[76]：

（1）随机选择。在产生S盒的各项内容时使用某种伪随机数产生方法或某个随机数码表。如果S盒既随机，又依赖于密钥，则强度会更高。IDEA和Blowfish所使用的就是与密钥有关的S盒。

（2）选择和测试。首先随机产生多个S盒，然后根据相应的性能指标来测试它，丢弃那些没有通过测试的项。只要设计者的时间和计算能力允许，采用此方式总可以构造出所需要的S盒，而且可以使用户相信没有陷门。如AES的候选算法MARS采用的就是这种方式产生的S盒。

（3）人为构造。只用到简单的数学或几乎不使用数学方法，而是使用更直接的方法来产生S盒。现在看来DES设计中采用的就是这种方式。

（4）数学方法构造。根据数学原理来产生S盒使得它们能抵抗差分攻击和线性攻击，且具有好的扩散特性。CAST采用的就是这种方式产生的S盒。为避免存在“陷门”的嫌疑，采用数学方法构造S盒越来越受到广大研究者的青睐，出现了基于指数函数和对数函数（如Safer+等）、代数函数、有限域的逆映射（SHARK，SQUARE）和有限域上幂函数的设计方法。

2.1.2 S盒的性能评价标准

S盒的另一种称呼是黑盒子，这主要是因为传统密码学中所采用的S盒，都只给出S盒的内容而不阐述设计S盒的方法。因此，它常给人造成故意设置陷门的嫌疑。为消除人们对S盒中存在“陷门”的嫌疑，美国国家安全局（NSA）透露了DES中S盒的几条设计原则[77]。自那时起，人们在分析S盒的设计和运算上做了大量的研究工作，提出了很多有关S盒设计的准则和好的S盒所应该具有的特性。其中有7个准则被认为是最重要的 [78-83]，它们常被作为评判S盒是否具有良好密码特性的标准。

① 双射特性

通常要求S盒是可逆的，尤其在代替置换网络中所使用的S盒必须是双射的。当m=n时，文献[80]给出了满足双射的充分必要条件：各分量布尔函数fi的线性运算之和为2n-1，即

式中ai∈{0,1}，(a1,a 2,…,an)≠(0,0,…,0)，wt（）表示汉明权重。如果上式成立，每个fi 是0/1平衡的，且f 是双射的。

② 非线性度

令是一个n元布尔函数，称

为 f（x）的非线性度。其中 Ln为全体 n元线性和仿射函数之集，dH(f,l)表示 f与 l之间的汉明距离。在实际应用中常通过Walsh循环谱来计算非线性度，函数f（x）的循环谱为

式中ω∈GF(2n)，x ·ω表示x与ω的点积，用Walsh谱表示的非线性度为

设，如果对任何，1≤i≤n，都有f(x)+ f(x+ei)是一个平衡布尔函数，则称 f（x）满足严格雪崩准则，其中，ei的第

③ 严格雪崩准则（SAC）i个分量为1，其余分量均为0。该准则主要用于考查布尔函数在输入发生一个比特的变化时，输出发生变化的情况。若布尔函数满足SAC，则表示改变输入的一个比特，输出中每个比特改变的概率为1/2。

在实际应用中可以通过构造相关矩阵来验证布尔函数f是否满足SAC[79]。具体步骤如下：首先，设n比特的任意明文分组X，其相应的密文分组为Y=f（X），（当m=n时，f 是可逆变换）。设分组X =[x1,x2,…,xj,…,xn]与X j =[x1,x2,…,, … ,xn]，只有第j个比特不同，它们相应的密文为Y=[y1,y2,…,ym]= f (X) 和Yj=[y j1,y j2,…,y jm]=f (Xj)。计算出 m比特的二进制雪崩向量[v1,v2,…,vm]，使得Vj =Y⊕Yj，其过程如图2.1所示。

然后构造一个m×n的相关矩阵A，向量Vj中的第i比特的值与矩阵A中的aij元素相加。重复这个过程r次（r为比较大的一个数，由明文向量X产生），并用A中的每个元素除以r。于是，A中每个元素aij的值就给出了明文第j比特与密文第i比特之间的相关强度。若aij的值为1，表示明文第j比特的改变必定要引起密文i比特的变化；而 aij的值为0，说明密文第 i比特与明文第 j比特是相互独立的，即明文第 j比特的改变对密文第i比特没有影响。如果A中的每个元素的值都接近于0.5，则表明f是满足严格雪崩效应。

④ 输出比特间独立性（BIC）

对由一个明文比特的反码所产生的雪崩向量集而言，所有雪崩变量应该是成对独立的。通过计算两个雪崩向量的相关系数可测量其独立的程度。给定变量A和B

其中ρ{A,B}为变量A和B的相关系数，cov{A,B}=E{AB}-E{A}E{B}为A和B的协方差，且σ2{A}=E{A2}-(E{A})2。

当变量是二进制变量时，相关系数为0时意味着两个变量是相互独立的，当相关系数等于1时，说明两个变量是相同的，而等于-1则表明两个变量是互补的。

另外一种测量输出比特独立的方法由C. Adams和S. Tavares提出的[80]：对于给定的布尔函数fj，fk（j≠k）是某S盒的两个输出比特，如果 f j⊕ fk高度非线性且尽可能的满足严格雪崩效应（SAC），则可以确保当一个输入比特取反时，每个输出比特对的相关系数接近于0。因此，可以通过验证S盒的任意两个输出比特间 f j⊕ fk是否满足严格雪崩效应，来检验S盒是否满足输出比特间独立准则。

⑤ 差分均匀性

S(x)=(f1(x),…,fm(x))：是一个多输出函数，令

称δ为 S（x）的差分均匀性。差分均匀性是针对差分密码分析[115]而引入的，用来度量一个密码函数抗击差分密码分析的能力。在实际计算中，也可采用差分逼近概率DPf来表示输入输出的异或分布情况[84]：

式中，X 表示所有可能输入的集合，2n是该集合的元素个数。DPf所表示的是给定一个输入差分∆x，输出为∆y的最大可能性。

⑥ 线性逼近概率

线性逼近概率是针对分组密码的线性攻击引入的，用于度量一个密码函数抗击线性密码分析的能力。根据Matsui最初的定义，线性逼近概率为在任意选定两个掩码值Γx，Γy的情况，对输入值x所有可能的取值进行掩码Γx的运算，对相应的S盒的输出值S（x）进行掩码Γy的运算，输入值与输出值进行掩码运算后所得结果相同的最大个数即为最大线性逼近数，根据式（2.8）可以计算出最大逼近概率。

式中，Γx 和 Γy 分别为输入和输出的掩码值，X 为变量x的所有可能的输入值的集合，其中包含的元素个数为2n。

2.1.3 基于混沌的S盒设计方法

从2.1.1节所介绍的设计S盒常采用的4种方法看，将混沌引入S盒的设计属于“选择和测试”与“数学方法构造”两种方法相结合的一种设计思路。基于混沌设计S盒常采用的思路有：

（1）选择某种混沌映射，对其进行不停的迭代以产生S盒中的元素，然后再利用另一个混沌映射对S盒中的元素进行重新排列以增强S盒的性能。

（2）对混沌映射进行整数化，然后利用不同的初始值和控制参数产生多个S盒，对所产生的S盒进行性能测试，从中选择采取具有优秀性能的S盒。

思路（1）常用于构造静态的S盒，而思路（2）则多用于构造动态的S盒。

① 基于混沌的静态S盒构造

在文献[85]中提出了一种基于混沌的n×n S盒产生算法，该算法是思路（1）中的典型代表，相关描述如下：

步骤1，选用Logistic映射[如式（2.9）所示]作为产生整数序列的混沌映射。

式中控制参数为：

将Logistic映射的状态值x表示成二进制形式为：

式中第i比特bi（x）可表示为：

式中，Θt(x)为阈值函数，定义为：

步骤2，将Logistic映射迭代n次，从混沌映射的状态值中抽取小数点后的n个比特值，组成一个0～2n-1范围内的整数。相关的抽取规则为，其中n为序列的长度，τn（x）为Logistic映射的第n次迭代。

步骤3，将迭代混沌映射后抽取出的整数加入一个初始时为空的整数序列S中。如当前加入的整数在序列中已经存在时，则不将该整数加入。

步骤4，反复迭代混沌映射直到整数序列S中包含0～2n-1范围内的所有整数为止。

步骤5，将整数序列S排列成的表格，构造出S盒的一种初始原形。

步骤6，使用离散后的Baker映射，如式（2.14）所示，对所得到的S盒进行Baker变换若干次。

式中k为整数，n1,…,nk的选择要使得每个整数ni能够整除N(N=n1+…+nk)。用Ni表示第 i 个划分，即Ni =n1+…+ni。S盒中的元素，设其坐标为(r；s)，其中

N i≤r＜N i+ni，0≤s＜N经过一次离散Baker映射后其坐标变换为。

步骤7，将Baker变换后所得到的结果作为算法所产生的S盒。

设置算法中Logistic映射的初值为 x0=0.618，参数μ=3.995，离散Baker映射中设置N=200，ni={10,20,5,50,10,20,20,10,5,50}。从Logistic映射的混沌序列中抽取出整数序列，再用离散Baker映射进行9次后迭代后得到一个8×8的S盒，如表2.1所示。

运用上面所描述的S盒设计准则进行性能测试，同时将文献[86]中所构造的S盒的有关性能也同时计算出来，以进行比较。

（1）双射特性：通过计算，上述S盒示例和文献[86]中S盒均满足双射特性。

（2）非线性特性：通过计算，上述S盒示例的8 个布尔函数的非线性度分别是103, 104, 106, 105, 105, 104, 109,103，都在100以上；而文献[86]中所构造的S盒的非线性度分别是106, 100, 100, 98, 108, 104, 106, 104。显然，运用该方法所构造的S盒是非线性的，具有较高的非线性度，能够抵抗“最佳线性逼近”的攻击。

（3）严格雪崩效应：采用计算相关矩阵的办法进行检验。计算结果显示，在相关矩阵中没有等于0的元素，所有元素的平均值为0.4995，与理论值0.5非常接近（参见表2.2）。相应地，根据文献[86]的方法所得到的S盒的计算结果为0.4972（参见表2.3）。测试结果说明该方法所设计的S盒能够很好地满足严格雪崩效应。

（4）BIC特性：采用C. Adams和S. Tavares所提出的方法，对所提出的S盒进行了分析，其计算的结果如表2.4所示，相应的文献[86]所构造的S盒的计算结果如表2.5所示。从测试结果看，S盒具有较好的输出比特间独立特性。

（5）最大差分逼近概率：根据式（2.7）计算示例S盒的最大差分逼近概率为0.0390625，文献[88]中S盒的最大差分逼近概率为0.046875。测试结果表明，示例S盒具有更好的抵抗差分密码分析的能力。

（6）最大线性逼近概率：根据式（2.8）分别计算示例S盒和文献[86]中S盒的最大差分逼近概率为0.132813和0.125。测试结果同样表明示例S盒具有良好的抗击线性密码分析的能力。

综合上述对S盒性能的测试与比较，可以发现对通过混沌映射的抽取所构造的S盒原形进行再次的混沌变换，能在很大程度上提高S盒的性能。

② 基于混沌的动态S盒构造

由于混沌系统是工作在浮点域，而S盒中的元素均为整数，因此将浮点域中的混沌系统转换为整数域中的运算自然成为了S盒设计中的一种思路。同时，由于混沌系统在不同初值或控制产生的情况，随着混沌迭代的不断进行，产生的混沌序列也是完全不相同的。而且这些混沌序列就具有不错的密码学特性。因此基于混沌系统完全可以产生一系列具有良好密码学特性的S盒。在文献[87]中所提出的方法，就很好地体现了上述混沌S盒的设计思想，相应的算法描述如下。

将实数域的混沌斜帐篷映射[参见式（2.15）]进行整数化得到式（2.16）其方程为：

式中

给定整数M≥2，取X∈{1,2,…,M}，A∈{1,2,…,M}，根据文献[88]的证明，当上述系统迭代次数k满足k≥2.39 log2 M +15时，序列{X}具有以下特性：（1）对初值X0敏感；（2）对临界点A敏感；（3）对迭代次数k敏感；（4）信息量成指数衰减；（5）比特独立；（6）显现随机统计特性。因此，该整数化后的方程适合于构造S盒。具体设计步骤为：

步骤1，按照任意一种方法获得一个整数序列并作为密钥K，K=X0={1,2,…,2n}；

步骤2，确定参数M=2n和A的值；

步骤3，以 X0为初值迭代混沌映射[参见式（2.16）]至少 k次，得到置乱后的整数序列{X}；

步骤4，将整数序列{X}转化成一张的表格，即算法产生的S盒。

根据混沌系统对初值和系统参数的敏感特性，按照上述方法，只需略为改变一下参数A、M或迭代次数k，就可以非常简单、方便地获得一系列具有优良密码学特性的“好”的S盒。

在应用上述基于离散混沌来动态产生S盒的过程中，需要特别注意以下两点：（1）由于Tent映射的特点，其临界点不能太接近于0或1，否则，所产生的混沌轨道分布不均匀。因此，建议在运用上述混沌映射产生动态S盒的过程中，其密钥只由两部分组成，初始整数序列X0和迭代次数k，一般情况下可以考虑采用固定临界点A的办法；（2）离散后的混沌系统在迭代过程中不可避免地具有周期性，如映射式（2.16），当M=64时，周期P=43，当M=128时，P=165。那么，用于产生S盒的迭代次数就只有[k, P]次。若明文分组的数量为L，这些迭代次数的组合仍然有r=(P-k)L之多。如M=256、L=15时，r=13015≈5×1031＞2100，完全可以抵抗穷举攻击。若再考虑到初值X0的取值范围，n个元素将有n!种不同的取法，对于256个元素的8×8的S盒，其取法有256!= 8×10506≈21684种。

运用上述产生动态S盒的方法，以1～256的整数为初始序列，取M=256，A=123，迭代Tent映射155次，取迭代次数在35～155之间（除去46～50间的6个弱密钥）的120个S盒的性能进行分析，其输入输出差分分布情况如图2.2所示，最大值不超过14。雪崩性能的相关矩阵的平均值分布如图2.3所示，均非常接近理想值0.5。非线性度的最大和最小值分布情况分别如图2.4和图2.5所示，非线性度的最小值也均大于90。这些实验测试的结果表明，上述方法能够构造出具有良好密码学特性的动态S盒，完全适合于在实际密码系统中使用。