密码系统代数攻击的关键问题研究

本项目研究密码算法设计与分析中的代数方法。近十年来，主流的密码算法包括分组密码，流密码与杂凑算法广泛使用经过严格安全证明的密码部件。这些部件的代数表达式使得整个算法都可以某种形式的多项式系统来表示。这样，研究算法的安全性分析势必涉及各种代数的分析方法，其中以多项式方程求解的观点最为受到学术界的关注。我们在该项目的实施中主要完成以下三方面的成果。（1）多输出布尔函数的代数免疫度的刻画方面，我们以多输出函数的坐标函数之间的次数最小的合冲关系完全刻画了多输出函数的代数免疫度。（2）基于代数方程观点的自动密码分析方面，我们提出了一个自动搜索不可能查分路径的算法，该算法只求解线性方程组，对非线性部分呢采取查表方法，该观点有望在类似的代数分析中得到推广和应用；作为代数方法在寻找最优扩散层中的应用，我们使用二元域上单变量多项式矩阵的观点，找到了很多适合各种设计条件的最优的轻量扩散层，这些扩散层可以取代目前正在使用的算法中的扩散层以得到轻量的实现。（3）使用代数方法解决了向量密码函数中的几个公开问题。主要有：完全决定了Gold函数的EA等价类中的置换；完全解决了逆函数的EA等价类中的置换的刻画问题；完全解决了法国密码专家Carlet等人在1998年提出的一个关于AB函数的一个公开问题；提出了如何使用奇数维域上的二次APN置换构造偶数维域上的4差分函数使得其具有知道的最优非线性度和有较高的代数度。