【作者】 陈银冬；

【导师】 陆佩忠；

【作者基本信息】 复旦大学 ， 计算机应用技术， 2010， 博士

【摘要】 代数攻击是近几年来最重要的密码分析技术之一。代数免疫度是随着代数攻击的出现而提出的关于布尔函数的一个新准则,用于衡量布尔函数抵抗标准代数攻击的能力。为了有效抵抗代数攻击,密码系统中使用的布尔函数必须具有尽可能高的代数免疫度,甚至要求是代数免疫最优的。求解多变元非线性方程系统的快速方法是支撑代数攻击有效实施的重要步骤,而Grobner基正是求解非线性方程系统的一个重要方法。广泛应用于代数攻击的XL算法就是Grobner基的一个快速算法(F4算法)的冗余版本。本文首先研究了代数免疫最优布尔函数的递归构造,提出了代数免疫最优布尔函数的二阶递归构造法和一阶递归构造法；其次讨论了两类对称布尔函数,对其代数免疫性,代数次数和非线性度做了深入研究并得到完整结果；最后研究了Grobner基的快速计算。具体结果如下：1)研究了代数免疫最优布尔函数的递归构造。首先,给出了代数免疫最优布尔函数的二阶递归构造方法。该方法构造的布尔函数代数免疫最优,具有优良的代数次数和非线性度,并且与之前的二阶递归构造法相比,它具有更加优良的平衡性。其次,提出了代数免疫最优布尔函数的一阶递归构造法。该方法构造的布尔函数不但代数免疫最优,而且是完全平衡的。这是首个代数免疫最优布尔函数的一阶递归构造法。最后,基于布尔函数的变换,对上述两类递归构造法进行了推广。2)分析了两类对称布尔函数。证明了这两类布尔函数代数免疫最优的充要条件,并进一步解决了其中代数免疫最优部分函数的计数问题。同时,详细讨论了这两类函数的其它密码学性质,特别是,完全确定了其代数次数和非线性度,从而解决了Braeken关于这两类函数中代数免疫最优部分函数的代数次数和非线性度的猜想。3)讨论了Grobner基的快速计算。提出了二元多项式理想Grobner基的一个快速算法。证明了在严格排序的生成集中,只需计算相邻多项式间的S-多项式即可。基于该结论,在Grobner基的计算过程中,所需计算的S-多项式的数量从1/2r(r-1)锐减到(r-1),其中r为当前生成元组中多项式的数量,从而提高了计算效率。更多还原

【Abstract】 Recently, algebraic attack is considered as one of the most powerful tools for cryptanalysis. To measure the resistance to algebraic attacks, a new cryptographic property of Boolean functions, called algebraic immunity, has been proposed. In order to resist algebraic attacks, the Boolean functions employed in cryptosystems should possess high algebraic immunity (even optimum algebraic immunity). Solving an over-defined nonlinear equation system is a key step for algebraic attack. Grobner bases theory is an important method to solve the systems. XL algorithm, which is used widely in algebraic attacks, is proved to be a redundant version of F4 algorithm (one of the efficient computing algorithms for Grobner bases).In this dissertation, we firstly investigate the recursive constructions of Boolean functions with optimum algebraic immunity. Moreover, we discuss two classes of symmetric Boolean functions with regard to algebraic immunity, algebraic degree and nonlinearity. Finally, we study the fast computing for Grobner bases. The main results are given as follows:1) The recursive constructions of Boolean functions with optimum algebraic immunity. Firstly, we provide a second-order recursive construction of Boolean functions with optimum algebraic immunity. The constructed Boolean functions have not only optimum algebraic immunity but also high algebraic degree and nonlinearity. Compared with the former recursive construction, they are much more balance. Secondly, we propose a first-order recursive construction of Boolean functions with optimum algebraic immunity. The constructed Boolean functions are completely balanced. Especially, to the best of our knowledge, it’s the first time to present such a first-order recursive construction. Thirdly, based on the transformation theory of Boolean functions, we make some generalizations for the two constructions above.2) Research on two classes of symmetric Boolean functions. For each class, we prove the necessary and sufficient condition for having optimum algebraic immunity. Then we enumerate all the Boolean functions with optimum algebraic immunity in the two classes. The algebraic degree and nonlinearity of the two classes are completely determined. Based on these results, we prove several of Braeken’s conjectures about the algebraic degree and nonlinearity of the symmetric Boolean functions with optimum algebraic immunity in the two classes.3) Fast computation of Grobner bases. We propose a fast computing algorithm for Grobner bases of polynomial ideals in two variables. We show that only the S-polynomials of neighbor pairs of a strictly ordered finite generating set are needed while computing the Grobner bases. Therefore, the number of S-polynomials needed decreases dramatically from 1/2r(r-1) to(r-1), where r is the number of generating polynomials for the current computing round.更多还原