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

项目名称： 密码分析中的几类代数方程组求解问题研究

项目编号： No.61502485

项目类型： 青年科学基金项目

立项/批准年度： 2016

项目学科： 自动化技术、计算机技术

项目作者： 黄震宇

作者单位： 中国科学院信息工程研究所

项目金额： 20万元

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

中文关键词： 密码分析；代数攻击；代数方程组；布尔参数方程组；含错多项式方程组

英文摘要： 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.

英文关键词： Cryptanalysis;Algebraic attacks;Algebraic equations ;Boolean parametric equations;Polynomial equations with noises