密码分析中的几类代数方程组求解问题研究

Solving algebraic equations over finite fields is a fundamental problem in mathematics and computer science, and has a lot of applications in cryptanalysis especially in algebraic attacks. In this project, based on the needs of cryptanalysis, we focus on the solving problems for three kinds of algebraic equations. The first one is solving Boolean parametric equations, which is relevant to the problems of checking the balancedness and computing the nonlinearity of vectorial Boolean functions. The second one is solving Boolean polynomial systems with noises, which widely occurs in side channel attacks and probabilistic algebraic attacks. The third one is solving algebraic equations over GF(2^n), and many cryptanalysis problems for ciphers designed based on GF(2^n) can be converted into this problem. In this project, we will design some efficient algorithms for solving these three problems and analyze the properties and complexities of these algorithms, then we will apply these algorithms to solve some cryptanalysis problems, and try to achieve leading cryptanalysis results for some open ciphers.

有限域上的代数方程组求解问题是数学与计算机科学中的基本问题之一，其在密码分析尤其是代数攻击中具有广泛的应用。本项目将结合密码分析需求，研究有限域上三类具有特点的代数方程组求解问题。第一类问题为布尔参数方程组的求解问题，该问题与向量布尔函数的平衡性判定、非线性度计算等问题密切相关。第二类问题为含错布尔多项式方程组的求解问题，该问题的求解在侧信道攻击与概率代数攻击中具有广泛的运用。第三类问题为GF(2^n)上的代数方程组求解问题，众多基于GF(2^n)所设计的密码算法的分析问题都能转化为该问题的求解。本项目中，我们将针对这三类求解问题，设计高效的求解算法并分析其性质与复杂度，之后将这些求解算法应用于密码分析实例中，力争在一些公开密码算法的分析问题中取得领先的研究成果。

有限域尤其是二元域上的代数方程组求解问题是数学与计算机科学中的重要基础问题之一，同时在密码分析领域具有广泛的应用。本项目针对密码分析中广泛出现的几类代数方程组求解问题展开研究，建立相关问题的求解算法理论，设计与实现高效的求解算法，并分析算法的复杂度。我们研究的代数方程组主要包括布尔参数方程组，二元域上的含错多项式方程组以及GF(2^n)上的一般代数方程组这三类问题。对于二元域上的参数方程组求解问题，我们给出了一套计算其精确解覆盖的高效算法，并利用此算法分析了一系列现有方法无法分析的具有大变量数的布尔函数的平衡性、相关性、以及非线性度这些基本性质。对于二元域上的含错多项式方程组求解问题，我们分析了基于递增求解与回溯搜索思想的ISBS算法的复杂度，基于回溯搜索树的结构分析，我们给出了ISBS的复杂度分析结果，同时提出两种新策略改进了ISBS算法，并通过冷启动密码恢复攻击实例验证了改进算法的有效性。对于GF(2^n)上的一般代数方程组求解问题，我们在Groebenr基方法与特征列方法这两类方法方面都取得了重要进展。我们改进了求解签名Groebner基的GVW算法并基于M4RI线性代数包完成了GVW算法的高效软件实现。针对特征列方法，我们提出了一种新型的基于加法约化思想的求解算法，给出了特征列算法的最佳复杂度结果，并且我们设计实现了具有极高加速比的并行特征列算法，在1024核的并行环境下得到了高效的实现。通过本项目的研究，我们在密码分析相关的几类重要代数方程组求解问题上均取得了突破，在数学上完善了有限域上的代数方程求解理论，同时为密码代数分析领域提供了新的求解技术与求解工具。