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

密码系统的代数攻击是将密码系统的加密运算归结为某种形式的多变非线性方程,然后借助于各种形式的多项式求解算法计算加密密钥，是近年来密码分析一个活跃的研究方向。几乎每一类密码系统的研究都能有相应的代数攻击方法。该项目研究密码系统的代数攻击方法的几个关键问题，如多输出流密码的各种代数免疫度的刻画问题，带有记忆的流密码的快速代数攻击算法问题。对分组密码，研究使用概率插值的Sudan算法多变形式在寻找概率非线性关系中的应用。这些问题的深入研究，将有助于深刻理解和运用代数攻击方法在设计和分析密码系统中的应用，提高我们在这个重要方向上的研究能力，同时在该方向上为国家培养需要的青年研究人才。

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