密码核心部件新型分解方法及应用研究

The security of encryption algorithms are usually closely related to the properties of their core components, for instance the properties of their S-boxes. A key issue for cryptanalysis of these encryption algorithms is to look for some new simple relations between the input data and the output data by decomposing these complex components with certain way. The target of project is to research some new methods to decompose the core components of ciphers, and then these methods would be used to analyze the security of some symmetric encryption algorithms. (1) A new concept of linear decomposes for Boolean functions is introduced by using multiple small cascaded affine subfunctions. The fast check algorithm for partial linear relations and the linear decomposing algorithm for nonlinear Boolean functions are further investigated by using the idea behind the disjoint linear subspace. (2) The resistance of these functions against (fast) algebraic attacks are estimated by using these decomposing algorithms. In particularly, for relative large number of input variables n, some effective evaluation algorithms should be provided in this project. (3)A new meet-in-middle attack on block ciphers is proposed by using the linear decomposing idea on the S-boxes. Some preliminary research results showed that this attack has several new advantages over the previous attacks. The security of Even-Mansour scheme and AES would be further checked by using the new attack. We will try our best to achieve innovative academic results regarding of the security analysis of mainstream ciphers. These results would also provide novel theoretical framework and effective tools for the design and analysis of symmetric encryption algorithms.

密码算法的安全性通常与其核心部件（如S盒）的性质紧密相关。如何将这些“复杂”的部件按照某种方式分解出“较简单”的输入及输出关系往往是密码算法破译的关键。本课题旨在研究密码核心部件新型的分解方法，并应用于对称密码算法的破译中：(1)提出布尔函数线性分解的新概念，即将非线性函数分解为多个级联的仿射子函数；利用不相交线性子空间划分的思想，探索函数局部线性关系的快速检测及分解算法。(2)利用函数线性分解，评估密码部件抵御代数攻击及快速代数攻击的能力；特别是当输入变元n比较大时，研究其有效的评估算法。(3)利用S盒的线性分解，提出分组密码一种新的中间相遇攻击。逐步预研表明，该攻击方法比以往的攻击具有若干新的优点。利用该攻击分析Even-Mansour分组密码方案及AES等算法的新安全性。课题力图在主流密码算法的破译中取得一批创新性研究成果，并为对称密码算法的设计与分析提供新的理论支撑和有力分析工具。

密码技术是国家的重要战略资源，也是保护网络空间安全的核心技术和基础支撑。本课题研究了密码核心部件的新型分解方法，并将其应用到密码算法的设计与分析中，努力执行和完成各个研究计划要点。在四年的研究期中，发表学术论文28篇，（含12篇SCI收录论文及5篇EI 收录论文，其中5篇论文发表在本领域顶尖刊物IEEE TIT、IEEE TC及旗舰会议FSE2019）；研究成果“密码核心部件的设计与分析关键技术研究”获得2018年广西科学技术奖（自然科学类）二等奖1项（课题负责人排名第一）；申请发明专利4项，其中获得授权2项；培养了10名硕士研究生及提升了3位中青年教师的科研能力。主要的研究成果如下：(1)给出具有良好密码学性质布尔函数的一系列新构造方法，包括Bent函数、不完全M-M类Bent函数、严格几乎最优（SAO）非线性度弹性函数的设计等。(2)提出一种通用的非线性布尔函数概率分解算法，为评估布尔函数抵抗(快速)代数攻击的能力提供了新途径。与已有算法相比较，新的概率分解算法具有更低的时间复杂度。(3)研究了两种密码S盒分解方法：一种是“域分解”，另一种是“降阶分解”。通过利用分解后的S盒性质，降低了AES和GIFT算法二阶门限掩码防护方案的实现复杂度。(4)基于中间相遇的基本思想，得到了16轮LiCi算法不可能差分攻击；构造了15轮Keccak算法零和区分器。(5)基于密码部件特点、可分性和混合整数规划(MILP)自动化分析工具，给出了SIMON、SPECK、MORUS等算法的一系列新分析结果；(6)提出了广义非线性不变攻击以及闭环不变子的新概念，否定了Beirrle等人在2017年美密会上所提出的分组密码轮常数设计准则。(7)针对认证加密算法COPA、Marble、LAC分别给出一系列新分析结果。这些研究成果将为对称密码算法的设计与分析提供强有力的理论支撑和分析工具。