作者：郑晓敏
1 引言
作为分组密码算法中唯一的非线性部件，S盒的构造随DES算法的流行而引起人们的关注。S盒的密码强度对整个分组密码算法的安全有重要的影响，在抗差分密码分析和线性密码分析方面尤为突出。S盒的密码学性能主要有下面几个度量指标：差分均匀度、非线性度、正交性、项数分布、代数次数和雪崩效应等。随着传感器网络技术的发展，人们对安全的要求也越来越高，密码算法要想得到广泛使用，则需要保证使用的S盒有较高的安全强度，且不存在陷门问题。为了避免存在陷门的嫌疑，目前主流的S盒构造仍倾向于选取公开的数学计算方法。如何在数学计算方法构造S盒的基础上提高算法的安全强度，对算法进行优化改进，仍是当前研究的重点。近年来，对于动态S盒的研究已然拉开了序幕。2007年，殷新春等在Rijndael算法的基础上提出了一种基于密钥控制的多S盒的Rijndael算法。2012年，Szaban等提出了一种基于CA (cellular automata)的S盒构造方法。人们还提出了一些不同的动态S盒构造方法。本文在此基础上，结合Fesitel构架和S盒重构思想，提出了一种与密钥
和输入明文相关的动态S盒构造方法，并对其进行了性能分析。
2 S盒的相关知识
2.1 S盒的基础
S盒是目前诸多分组密码算法的核心模块，因此人们对S盒的构造方法以及性能进行了大量的研究。在分组密码算法中，通常使用表格来表示S盒，而与之对应的密码算法中的调用也大多是通过查表的方式完成。例如，在DES密码算法中，采用的是6x4的S盒，则使用4行16列的表格来表示：在AES密码算法中，采用的是8x8的S盒，表示为16行16列的表格。在很多密码算法设计中简化了S盒的模型和计算方法，但其本质仍是从域GF(2)n到域GF(2)m的多输出布尔函数。
2.2构造S盒的数学模型
S盒的构造主要分为数学方法构造和智能算法随机生成。数学方法构造相对比较稳定，可以有效地保证较好的密码安全性。在参考文献中介绍了常用的几种方法。
(1)对数函数和指数函数
SAFER系列密码采用的均是这一组函数，因为它们拥有良好的密码学性能。在8x8的S盒置换中，代数次数和项数与随机置换的相应值接近，非线性度和差分均匀度也都相对较好。
(2)有限域上的逆映射
有限域上的逆映射是当前构造S盒的主要方法，许多著名的密码算法均采用逆映射来完成S盒的构造，如Shark、Square等。但由于在有限域GF（2n)中的表达式太过简单，导致Shark密码算法不能有效抵抗插值攻击。因此常将逆映射与仿射函数相结合来弥补这个缺点。
(3)有限域上的幂函数
幂函数是人们在寻求构造S盒方法的过程中发现的一种有限域的特殊结构，因其具有一定的研究价值而受到研究人员的关注，由此诞生了名为幂函数的一种代数结构。幂函数被运用到了密码算法的设计中。但是，幂函数的代数结构相对简单，难以抵御插值攻击和高阶差分密码分析攻击，通常只将幂函数运算作为构造S盒的基础部分。
(4)混沌映射
确定性混沌系统具有很好的不可预知性和随机性，在密码算法中也占有一席之地。混沌学中的“初始敏感性”与密码学中要求输入的微小改变能够引起输出的较大变化的特性契合，也采用混沌映射构造S盒。
3动态S盒的设计
3.1 S盒的构造
AES优质密码S盒的构造主要分3步：第一步，求出伽罗瓦域CF(2n)上的既约多项式对应状态字的逆元；第二步，利用仿射变换公式对得到的逆元结果做仿射变换；第三步，利用密码学性能分析方法从得到的大量S盒中选取性能优异的S盒。
3.1.1 求乘法逆元
求某个有限域GF(2n)上的乘法逆元，首先需要知道该域的一个既约多项式。在确定有限域后，通过相关计算可以求得域GF(2n)上存在的所有n次既约多项式。例如，域GF(2#)上存在3个4次既约多项式，域GF(26)上存在9个6次既约多项式，域GF(28)上存在30个8次既约多项式。在同一个有限域GF（2n)上选取不同的既约多项式，可以计算得到不同的逆元集，同时改变仿射变换公式的输入变量，进而得到更多性能相似而输出不同的S盒。
3.1.2仿射变换求S盒
在求得选定的既约多项式的乘法逆元之后，便可以将求得的结果输入仿射变换公式进行S盒的构造。目前构造S盒的主流仿射变换公式如下：
在域GF(2n)上选取A(x)时，只需要满足最高次数是n且较为简单的多项式，比如选择多项式A(x）=xn+1。接着选取B(x)，对多项式B(x)的选取则需要保证与A(x)互素。如果选取的A(X)是不可约多项式，由于在有限域内不可约多项式与任意多项式互素，B(x)则可以任意选取。然后选取C(x)，C(x)的选取是为了保证得到的S盒不包含反不动点和不动点，因此即使在确定了多项式A(x)和B(x)后，C(x)往往还是存在多种不同选择，这也可以得到更多的S盒。
例如，在有限域CF(26)中若选取A(x)=x6+1，那么在选取B(x)时，需要与A(x)互素，而X6+1=(X+1）2(X2+X+1）2，所以在选择B(x)时可以将要求简化为：保证不含x+l和X2+X+1这两个因子的多项式，当然也可以直接选择不可约多项式作为B(x)。通过相关计算可以得出以下满足条件的部分取值，其中B(x)不是不可约多项式：
从式(2)中，任选其一作为仿射参数进行S盒的构造，首先选定既约多项式为X6+X5+1，求得其对应的乘法逆元见表1。
根据表1中的乘法逆元，选取B(x)=x5+x4+x2，C(X）=X4+X2+X+1；结合仿射公式可以求得6x6的S盒，见表2。
由于在动态S盒设计时需要使用4x4的S盒，因此重点对4x4的S盒进行了构造，并按照S盒的设计准则进行了性能分析筛选，最终得到了一批符合要求的S盒。例如：选择既约多项式为X4+X3+X2+X +1，仿射参数为：A(X)=X4+1，B(x)=x3+x2+x，C(x)=x2+x+1，通过计算可以得到4x4的S盒，见表3。
若选择既约多项式X4+X 3+1，仿射参数为：A(X)=4+1，B(X)=X3+X+1，C(X)=X，则经计算可以得到4x4的S盒，见表4。
上述计算方法可以完成不同的S盒构造，并通过S盒的性能分析进行筛选，最终将性能优异的S盒运用到密码算法的设计中。
为了满足实际应用需要，还可以考虑输入与输出位数不同的S盒。在一些密码算法的实际设计中一般要求S盒的输入位数不小于输出位数，即n≥m。比如，LOKI算法中使用规模为12x8的S盒，DES算法中使用的是6x4的S盒，而Rijndael算法和Towfish算法使用了8x8的S盒，Serpent算法中使用了4x4的S盒。在NESSIE标准中，MISYTI算法使用规模为7x7和9x9的S盒，Camellia算法使用规模为8x8的S盒。S盒的规模较大时，非线性特征一般较好，可以有效地抵抗线性分析攻击。因此一般认为m和n的值越大．S盒的密码强度越高，且当m与n的差值很小时，可以有效抵抗差分密码分析和线性密码分析等利用统计特征的攻击。然而m和n值的不断增大，也会增加算法的设计难度以及存储空间和硬件成本。因此，在选择构造S盒的规模时，往往需要考虑更多的因素。
3.2动态S盒的设计
3.2.1 Feistel结构模型和S盒重构
Feistel密码结构作为密码算法设计的主流结构之一，首先是在DES的设计中发明并应用。继而在GOST、RC5等分组密码算法中得以推广使用，Feistel将输入的明文切分为Lx和Rx两部分，如图1所示。
输入明文首先拆分为两个等长的部分：Lx和R2，Kx+l是经过密钥扩展算法求得的第x+l轮子密钥，从图1的运算过程可以看出，新的左半部分和右半部分生成方式为：Lx+1=Rx;Rx+l=Lx+F(Rx，Kx+1)，迭代n轮后最终的密文输出结果是：C=（Ln，Rn)。对Feistel结构来说，任何函数F在算法中均可正常工作，并轻松完成解密过程。
在第3.1节提到，S盒的构造规模越大，密码强度越高，抵抗差分攻击和线性攻击的能力就越好。而m和n值过大会增加算法的设计难度、存储空间和硬件消耗，不利于硬件实现和实际应用。因此，在分组密码中往往采用小S盒组合拼凑的方法，提出了S盒重构的思想，如DES中使用8个6x4的S盒，GOST中使用8个4x4的S盒。通过对S盒进行重构，用小规模S盒实现了大规模S盒的性能，增加了密码强度，降低了资源消耗。对分组密码算法的重构模型和重构设计结构做出了一定的分析研究。
3.2.2动态S盒的概念
从密码算法研究可知，当n值增大到一定程度时，域GFf21上的置换几乎都是非退化的，如果此时S盒的选取与输入明文和密钥相关，能极大提高其密码学特性。有关研究人员已经构造了置换和密钥相关的动态S盒。在参考文献中也引入了利用密钥进行选择的动态S盒构
造。置换过程中的可选择机会越多，动态S盒的密码学性能也就越好。在参考文献中，对提出的一类动态S盒构造方法进行了差分性质研究，其分析结果表示该类动态S盒变换具有良好的差分特性，动态S盒的研究改进切实可行。
考虑到Feistel结构的特点，结合S盒的重构思想，提出了动态S盒的设计原理：将n位输入进行拆分，一部分作为选取S的依据，另一部分则作为选定的S盒的输入，中间还可以进行一些简单的运算，两部分各自输出的组合作为设计方案的输出结果。
3.2.3动态S盒的设计流程
动态S盒的设计思想主要来源于S盒的拆分与组合思想和Feistel结构原理，主要步骤如下。
第一步：利用现有的S盒计算方法得到大量S盒，挑选性能优异的构建S盒容量集。
第二步：从集合中选取参与运算的m个S盒，并进行编号。
第三步：利用动态S盒原理，调用选定的S盒，进行后续运算。
在动态S盒设计中，首先对S盒的性能严格把关，选取性能优异的S盒作为候选集。保证每个候选S盒的选取概率相等，相互之间独立不相关，每个候选S盒的密码学安全强度保持一致或相近。此外，S盒选取的决定因子同时与输入的明文和密钥相关，通过明文密钥的不可预知和可随机变换的特点，使S盒的隐蔽性更强，增加了S盒的安全，提高了密码算法的安全强度。
动态S盒的设计流程如图2所示。
从实现8位主流S盒的设计角度出发，参考动态S盒的设计原理和拆分组合的设计思想，以Feistel结构为基础，考虑将8位的输入拆分为L4和R4两部分。如图2所示，选取4x4 S盒为原型，构建动态S盒。首先将8位输入明文与密钥进行运算，然后将8位的运算结果拆分为左4位和右4位，右4位用于进行S盒的选择，同时与某个变量经过异或运算后作为一部分的输出，剩下的左4位输入4x4 S盒进行置换运算，这样实际上使用一次4x4 S盒完成了8x8规模的运算。具体结构流程如图3所示。
由Fesitel结构特点可知，有一半的输入并未进行置换运算，但通过实际算法中的多轮迭代可以很好地弥补这一不足，做到全覆盖置换混淆。
在Feistel结构基础上进行拓展，还可以将8位的输入拆分为左右位数不相等的两部分。比如拆分为2位和6位，2位用来选择S盒，剩下6位也是输入6x6的S盒进行置换运算，得到2+6 S盒。以此类推，还可以构建1+7 S盒和3+5 S盒。参照8x8 S盒设计得到的动态S盒可以实现不同的8位输入使用不同的S盒进行置换的目标，同时具体使用哪个S盒由输入明文和密钥共同决定。
当然，动态S盒的思想也可以运用到输入为16位甚至更大的结构设计中，那么将会得到更多的组合。这在一定程度上完成了对S盒的隐藏保护，增加了S层置换的安全强度，提高了加密算法遭到破解的难度。
4性能分析
根据动态S盒设计方案，在性能分析时采用4x4的S盒完成了具体设计，并做一些仿真分析。首先，通过前面提到的S盒的构造方法，构造了一批性能优异的4x4 S盒，并从中随机选取了16个作为候选集。然后对选中的S盒进行了随机编号0~15，得到参与运算的4x4 S盒集：SO，Sl，…，S14，S15。
具体流程如图4所示，当输入为01100101时，拆分后，右边4位选择编号为S5的S盒，并与K进行异或运算后作为输出的左4位。然后将剩余4位输入S盒进行置换，最后得到输出为11010010。
此外，在对选择位进行异或变换时，引入了变量K，而K的取值是可以自行设定的，这就等于在引入输入明文和密钥对S盒选取的控制之外，还引入了一个影响因子，K值的变化也会导致后续运算的差异。受动态S盒设计思路的指导，此处的K值也可以作为一个动态变化的因子，进而增加S层的灵活多变性。
(1)非线性度分析
由S盒的构造准则可知，如果S(x)：GF(2n)→GF（2n)，则它的非线性度可以表示为：
度较好。而对动态S盒而言，由于引入了输入明文和密钥控制，使得在S盒的选取上更加随机灵活多变，非线性特性更好。
(2)代数次数和项数分布
该4x4 S盒可表示为4个只含“与”和“异或”逻辑符号的布尔方程：该方案具体实现如图4所示，代人图4中选择的S盒的相关参数，可以通过布尔函数的小项表示法求得4个布尔方程，由4个布尔方程可知：代数次数为：D(fi)=3，项数分别为：12、10、12、10。代数次数达到了最佳(n,-l)，而方程项数越多，复杂度就越高。因此该S盒的安全性能得到提高，可以较好地抵抗线性攻击等。
(3)雪崩效应分析
如果改变输入的1 bit，输出比特中约有一半发生改变，则称S(x)满足雪崩效应。如果改变输入的1 bit．每个输出发生改变的概率均为1/2，则称S(x)满足严格雪崩准则(SAC)。通过对上述S盒进行计算得到数据见表5，从表5中数据来看，选取的4x4 S盒满足SAC，雪崩效应理想，与已有算法相比，性能更好。
(4)差分均匀度分析
差分攻击是针对分组密码的有效攻击手段之一，δ的值越小，抵抗差分攻击的能力就越强。该S盒的差分分布见表6，其中，X表示输入的差分值，Y，表示输出的差分值。当X=l，y=E时，8=4，意味着输入差分为1，输出差分为E的情况出现了4次。
从表6中数据可知，该S盒的差分统计最多次数为4，符合4差分一致性。此外，表6中每行只有一个差分输出统计值为4，且数据分布相对均匀，可以很好地抗击差分密码分析。
5结束语
在某些加密模式下，加密的过程是高度确定的，这就意味着在密钥保持不变的情况下，输入相同的明文分组可以得到相同的密文输出。这种高度的确定性给数据带来了安全隐患，攻击者可以通过对输出数据进行流量分析，得到某些消息是否多次进行传输，进而可以对某些重复出现的明文进行重新排序，达到攻击的目的。
动态S盒设计提出的目的就是要打破这种加密过程高度确定的格局，增加明文输入和密钥对S盒的影响，改变以往使用固定不变S盒的模式，以S盒动态可变的特点来增加S层置换的复杂度，为密码算法的S层注入随机的特性，利用明文输入和密钥两者共同决定S层中对S盒的调用，并引入控制变量K，充分利用现有资源，完成了对S层的优化改进目标，更好地实现了S层的非线性混淆的任务。
通过对其性能进行分析对比，该设计能更好地保护S盒，提高密码算法的安全强度，增加算法的灵活性，进而对密码算法的差分分布和线性分布产生影响，从而显著提高整个算法的安全强度，更好地抵御更多的攻击。
6摘 要：
分组密码作为信息安全应用的主流加密方法，在无线传感器网络中也得到了广泛应用。而S盒作为分组密码算法的核心模块之一，其设计好坏直接影响着整个密码算法。为了在有限的资源下，提高分组密码算法的安全强度，对分组密码算法以及S盒构造设计进行了深入的分析研究，结合Feistel架构和S盒重构的思想，提出了动态S盒的设计方案，并对其进行了相关分析验证。结果表明，经过该设计，安全性能确实有所提高。
