S盒密码性质的测试与研究

范巍

（河南牧业经济学院＜英才校区＞计算机应用系，河南 郑州 450044）

S盒密码性质的测试与研究

范巍

（河南牧业经济学院＜英才校区＞计算机应用系，河南 郑州 450044）

本文介绍了S盒的设计准则和构造方法，并利用程序实现了非线性度、扩散准则、雪崩效应、差分均匀性这几个设计准则。利用上述程序对现代主流的几个分组密码进行了分析和测试，主要就非线性度、差分均匀度、雪崩效应、扩散特性以及可逆性对其中的S盒进行了分析和讨论。此外，在上述基础上，本文采用有限域上的幂函数和逆函数线性组合的方式构造S盒。对得到的S盒的密码性质进行了分析和讨论，并与现代主流密码的S盒进行比较。

S盒；非线性度；差分均匀度；扩散特性；雪崩效应

1 绪论

分组密码是现代密码的一个重要分支，自从其诞生以来，三十多年间人们从未停止过对其的研究。不论是理论还是应用，密码学家在这期间都取得了极大的进展。分组密码的设计和安全性研究既相互对立又相互促进，从而也让分组密码有长足的进展。然而分组密码设计原理的完善并没有浇灭密码学家对于分组密码安全性的热情，反而更加激发了密码学家们的兴趣。密码学家们的兴趣最终导致分组密码攻击方法的日趋多样性。从差分分析到高阶差分分析[1]，从线性攻击到截断差分-线性攻击[2]，经典的攻击方法之间的重组创造出了新的攻击方法。大多数的分组密码采用混淆加上迭代的结构，其中S盒是大多数分组密码中混淆的关键。因此，从某种意义上讲，分组密码的安全性依赖于S盒的密码特性。也正是由此，越来越多的攻击方法被提出也给S盒带来了越来越大的挑战，这也使得对于S盒性质的研究获得了密码学家们的极大关注。

2 相关研究

从S盒的输入输出的角度来看，S盒可以看作是多输出布尔函数，因此对于S盒的研究可以通过布尔函数的一些研究方法来实现。布尔函数的相关理论和结果能够对S盒的研究提供很好地指引作用。因此，S盒的很多密码性质是由布尔函数的相关性质推广而来。

随着S盒研究的深入，一个很现实有很重要的问题出现在密码学家们的眼前，即如何全面的衡量S盒的优劣。于是很多密码学家又致力于对于S盒设计准则的研究，发表了大量的文献资料[6-10]，这些文献中给出了S盒的一些设计准则。事实上可以发现，很多S盒的设计准则来源布尔函数的相关性质。线性攻击的出现，使得非线性度这个概念对于分组密码日益重要。由于这种攻击方法的本质是用线性函数去逼近加密算法，而对于S盒的线性逼近是否有效直接关系到攻击成功与否。

3 S盒构造设计与主流算法性质研究

3.1 S盒构造方法。S盒的设计准则较多，有些设计准则之间相互限制，因此满足所有准则的S盒几乎是不存在的。所以，可以根据实际情况对S盒某些指标的要求不需要那么严格。例如，对于采用SP结构的分组密码，由于其良好的扩散性能，在这种情况下可以适当降低对S盒扩散性的要求。其一，随机选取并测试。由于规模较小的S盒的安全性可能得不到保障，因此，在随机生成S盒时往往生成规模较大的S盒，以确保S盒以较大的概率具有较好的密码性质[8]。其二，按照一定规则构造并测试使用这种方法的一个重要前提是现有的性质良好的S盒，然后通过设计者设定的一些规则来改进S盒。其三，利用密码结构。大多数情况下，这种方法以规模较小的S盒，通过特定的密码结构，以构造性质优良的且规模较大的S盒。此种方法构造的S盒通常可以用较低的硬件代价实现，对于一些资源受限的应用此种方式构造的S盒更容易满足要求。其四，利用遗传算法构造并测试所谓的遗传算法，就是利用两个旧的S盒生成新的S盒，并对新产生的S盒进行淘汰：只选取性质更加优良的S盒，让其有权力生成新的S盒。这样可以使得好的性质一步步聚集起来，从而产生一些密码特性良好的S盒。其五，数学函数。使用这种方法的好处是：S盒的性质可以从理论上证明。目前常用的此类S盒由指数函数、对数函数、有限域上的逆和幂函数、混沌映射。其六，不同群中数学函数的复合。不同群的数学函数的符合在抵抗差值攻击和高阶差分攻击方面时有效地。按照一定的规律选取参数，例如选取是奇数和可以保证S盒是双射。

3.2 现代主流分组密码的S盒性质研究。分组密码中大多数用到了S盒，而S盒的一个重要作用是对明文进行混淆。混淆的程度也在一定程度上影响着这些分组算法的加密强度和安全性。因此，对于现有S盒的密码性质的研究将为设计出更好地S盒提供重要的依据。其一，AES算法。AES算法的S盒是由限域上逆映射并加上仿射变换得到的，这种方法设计充分保证了S盒的差分均匀度、线性偏差以及较高的代数次数。因为AES算法的S盒是一个置换，因此其一定是平衡的。对其输入改变1比特来观察其输出的改变比特的概率，可以看出AES算法的S盒并不符合完全雪崩效应和一阶扩散准则，其完全雪崩距离为432，但是可以看出关于任何一个元素其与符合雪崩效应的差距并不是很大，也即当输入改变1比特时输入每一比特取反的概率都很接近0.5。非线性度一定程度上反映了S盒抵抗线性密码分析攻击的能力，而bent函数具有最高的非线性度，计算可以得到AES算法S盒的非线性度为112已经十分接近bent函数。AES S盒的差分均匀度为4，说明AES算法S盒对于差分攻击具有良好的抵抗能力。其二，Camellia算法。Camellia算法对其他较为复杂的攻击方法也具有很好地抵抗能力。此外，Camellia算法有一个很大的特点：每隔一定的轮数使用不同的函数以增加不确定性。Camellia算法中的S盒并不满足完全雪崩效应和一阶扩散准则，但是在输入改变1比特的情况下输出比特改变的比例都比较接近0.5，因此其也具有较好的雪崩效应。Camellia算法的S盒的完全雪崩距离为308，比AES算法S盒更优。S盒的非线性度和差分均匀度分别是112和4，这和AES算法S盒是一致的。其三，SMS4算法。SMS4算法是一个典型的分组密码算法，具有128比特的分组长度，而且其密钥长度与之相同。SMS4算法采用的迭代轮数比一般的分组密码都多：32轮。SMS4算法 S盒并不满足完全雪崩效应和一阶扩散准则，但是在输入改变1比特的情况下输出比特改变的概率都比较接近0.5，因此其也具有较好的雪崩效应。SMS4算法的S盒的完全雪崩距离为492，较AES算法S盒和camellia算法S盒都差。SMS4算法S盒的非线性度和差分均匀度分别是112和4，这和AES算法、Camellia算法S盒是一致的。其四，ARIA算法。ARIA算法的明文分组长度以及密钥比特的长度均与AES算法一致。算法迭代的轮数根据密钥长度不同而不同分别为：12、14和16。ARIA算法的整体结构为SP结构，每一轮由加轮密钥、混淆层和扩散层构成。

ARIA算法中的S盒并不满足完全雪崩效应和一阶扩散准则但是在输入改变1比特的情况下输出比特改变的概率都比较接近0.5，因此其也具有较好的雪崩效应。ARIA算法的S盒的完全雪崩距离为400，较AES算法S盒和Camellia算法S盒都差，但是优于SMS4算法S盒。ARIA算法S盒的非线性度和差分均匀度分别是112和4，这和AES算法S盒、Camellia算法S盒以及SMS4算法S盒是一致的。

因此，我们采用与AES算法相同的方式构造一个有限域GF（28），记作GF并首先研究GF上的单独一个幂函数f（x）=xe的性质，主要包括可逆性、平衡性、非线性度、雪崩效应、扩散特性。单独一个幂函数的形式并不能很好地满足加密算法对于S盒密码性质的要求，于是采取逆函数和幂函数相异或的形式来构造S盒，即S（X）=x-1+xe。这有以下好处：首先这样可以使得S盒的代数表达式更加复杂，其次异或运算可以提高S盒的非线性程度。由于S盒在具体的分组算法中要求是可逆的，通过计算具有上述形式且可逆的S盒的非线性度、雪崩效应以及扩散特性的指标如表1：

表 1 逆函数和幂函数线性组合生成S盒密码性质

表 2 AES算法S盒和两个幂函数线性组合生成S盒密码性质

通过上述方法仍然无法获得性质较好的S盒并且可逆S盒的数量过少，于是采取逆函数与两个幂函数相异或的构造方法，并将原来的逆函数变换成AES中经过仿射变换后的S盒，可以一些性质更为良好的S盒，具体情况如表2：

该S盒并不满足完全雪崩效应但是在输入改变1比特的情况下输出比特改变的概率都比较接近0.5，因此其也具有较好的雪崩效应。S盒的完全雪崩距离为380，优于AES算法、SMS4算法和ARIA算法的S盒，并且与Camellia算法S盒的差距也不是很大。该S盒的非线性度和差分均匀度分别是112和4，这和AES 算法S盒、ARIA算法S盒、Camellia算法S盒以及SMS4算法S盒是一致的。

上述的测试说明按照上述设计准则，利用有限域幂函数和逆函数通过异或运算组合的构造方法确实能够产生性质良好的S盒。

4 结论

本文对S盒的设计准则和构造方法进行了总结和讨论，并对现有主流分组密码中的S盒就非线性度、雪崩效应以及扩散特性等性质做了分析与研究。然后在通过本原多项式构造的有限域的基础上，采用逆函数与幂函数线性组合的方式构造S盒。最后研究这些S盒的平衡性、可逆性、非线性度、雪崩效应以及扩散特性等性质，并与现有的主流分组密码中的S盒进行对比。最终得到密码特性比较理想的S盒。

[1]胡豫濮，蔡勉，肖国镇.一类高阶差分密码分析[J].电子学报，1999（10）：74-78.

[2]贺也平，吴文玲，卿斯汉.截断差分-现行密码分析[J].软件学报，2000（10）：94-98.

[3]张丽琼，吕述望.插值攻击中的多项式表示[J].通信技术，2003（4）：80-81.

[4]温巧燕，钮心忻，杨义先.现代密码学中的布尔函数[M].北京:科学出版社，2000.

[5]冯登国，吴文玲.分组密码的设计与分析[M].北京:清华大学出版社，2009.

[6]A.F.Webster and S.E.Tavares，On the Design of S-Boxes. Advances in Cryptology-CRYPTO'85，LNCS 218，pp:523-524. Springer-Verlag，1986.

[7]S.Fischer and W.Meier，Algebraic Immunity of S-Boxes and Augmented Functions.Fast Software Encryption-FSE 2007 LNCS 4593，pp:366-381.Springer-Verlag，2007.

[8]J.A.Gordon and H.Retkin，Are Big S-Boxes Best?IEEE Workshop on Computer Security，pp:257-262，1981.

[9]L.O’Connor，Enumerating Nondegenerate Permutations，Ad⁃vances in Cryptoogy-EUROCRYPT’91，LNCS 547，pp:368-377.

[10]C.Adams and S.Tavares，The Structured Design of De⁃sign of Cryptographically Good S-Boxes，Journal of Cryptology，Vol.3，No.1，pp:27-41，1990.

[11]J.Dettombe and S.Tavares，Constructing large cryptograph⁃ically strong S-Boxes.Advances in Cryptology-Auscrypto’92，LNCS 718，pp:165-181.Springer-Verlag，1993.

[12]Ross J.Anderson，Eli Biham，Lars R.Knudsen.The Case for Serpent.AESCondidate Conference 2000:349-354.

TN918

A

1671-0037（2014）12-86-2

范巍（1982-），男，硕士研究生，助教，研究方向：计算机科学技术与应用。