分组密码代数攻击及构造代数免疫S盒

As cryptographer designed many cipher algorithms without considering the solvability problems of overdetermined nonlinear equations of higher order before. Recently, with the appearance of effective methods of solving these equations, algebraic attacks have received more and more attention. Till now, stream cipher such as Toyocrypt, LILI-128, E0 and public key cipher HFE and block cipher such as KeeLoq, six rounds DES are broken by algebraic attacks one by one, which also do a good job in the analysis of block cipher such as AES, Serpent, SMS4..The project focuses on the algebraic structure of S-box which is based on the only one nonlinear transformation in the block cipher such as AES ,SMS4 and some typical lightweight block cipher and imposes algebraic attacks on encryption algorithm in different number fields . According to the results of research, our methods of attacks are better than those have been attained. Therefore, further studying the methods of solving overdetermined higher order equations is the key part of the project..In order to resist algebraic attacks, S-box algebraic immunity has been proposed. A new cryptographic properties of S-box are urgently needed. So, S-box algebraic immunity is also the major focus of the project.

由于很多密码算法在设计时没有考虑到超定多元高次方程组的可解性问题，随着较为有效的求解方程组的方法的出现，代数攻击越来越受到人们的重视。目前序列密码Toyocrypt、LILI-128、E0、公钥密码HFE、分组密码6圈的DES、Keeloq相继被代数攻击所攻破，代数攻击在分组密码AES、Serpent、SMS4的分析中也有出色的表现。.本课题瞄准AES、SMS4和一些典型的轻量级分组密码算法中唯一非线性变换S盒的代数结构，在不同数域上对加密算法实施代数攻击，现有的研究表明，我们攻击方法的计算复杂性低于目前已知的公开成果。进一步研究具有针对性的求解超定多元高次方程组的方法是本项目的研究重点之一。.代数攻击方法的出现必然导致对S盒代数免疫问题的研究，密码设计者迫切需要能抵抗代数攻击的S盒设计新准则的出现。S盒代数免疫研究是本课题的另一研究重点。

在分组密码代数攻击研究方面，对用XSL技术扩展所得方程的独立性进行分析，证明了用XSL技术得到线性方程中，线性独立的方程个数仍小于项数，此时方程仍然无法求解，因而XSL技术不能对AES-128的安全性构成威胁。证明了SMS4算法S盒与有限域乘法逆变换是仿射等价的，给出了SMS4密码算法的有限域上多项式表示，利用SMS4算法S盒与有限域乘法逆变换的仿射等价关系，将SMS4密码算法用一个256元域上由768个变量构成的包含768个方程的方程组来表示，使得SMS4算法的密钥恢复等同于求解这个方程组，证明了SMS4的安全性最终取决于代数攻击方法中的大规模稀疏方程组的求解在实际中是否能够实现。. 在密码函数研究方面，提出了布尔函数迹Walsh谱概念，并给出该谱值的一些简单性质；通过谱值分析发现有些布尔函数虽然不易用线性函数或较低次非线性函数来逼近，但却能用迹函数较好地逼近，因而这种布尔函数很容易受到采样攻击；这一研究结果表明，Bent函数虽然是一种理想的密码函数，可被用于S盒设计、序列密码以及扩频通讯等领域，但如果一个密码函数能够用次数较低的多项式近似表示，或者项数较少的多项式近似表示，或者线性复杂度较低的函数近似表示，则该密码系统就容易受到高阶差分攻击或代数攻击。. 在代数免疫S盒构造方面，研究了矩阵幂函数构造的S盒，讨论这种S盒在低维空间上方程性质。在优先于GF(4)上给出S盒的具体形式，讨论了该种S盒输入变量、密钥变量和输出变量之间的方程及其个数，并找出了方程个数最多和最少的S盒，并给出了矩阵幂S盒输入、输出变量与密钥变量之间存在的方程个数及其秩的分布情况。研究表明：在优选初始矩阵的条件下具有一定的抵抗差分分析、线性分析的能力。