【作者】 徐永杰；

【导师】 李俊全； 鲍皖苏；

【作者基本信息】 解放军信息工程大学 ， 密码学， 2008， 硕士

【摘要】 2003年法国密码学专家N.Courtois提出代数攻击以来,代数攻击被广泛用于分析各类密码算法,密码算法中布尔函数的代数免疫性能已成为判断布尔函数密码学性能好坏的一个重要准则。目前,代数攻击最成功的实例是针对序列密码Toyocrypt和LILI-128的攻击。文献利用这两个密码算法中非线性函数各自存在的低次零化子,建立了关于输入、输出和密钥的低次方程组,成功破译了这两个算法。通过分析我们发现,这两个算法所使用的非线性函数的补函数也存在低次零化子,且数量与原函数的低次零化子数量相同,利用这一点,我们可建立两倍于文献的代数方程,使得代数攻击破译这两个算法所需明密文对的数量减少了一半。对安全性基于非线性布尔函数的密码算法,找出其非线性布尔函数的低次零化子是利用代数攻击方法破译这类密码算法成效的关键。本文利用布尔函数支撑点逻辑相邻关系和函数代数次数的联系,给出了一种计算布尔函数低次零化子的新方法——卡诺图法,并分析了卡诺图法和目前几个有代表性的计算布尔函数零化子算法的区别和联系。布尔函数的代数免疫阶是体现布尔函数抗代数攻击能力强弱的重要指标。本文分析了两个布尔函数相加生成新函数的代数免疫阶的变化情况,还给出了布尔函数通过非线性级联组合生成新函数的代数免疫阶变化结果。同时,文章还对这两种函数组合方式在均衡布尔函数其它密码学性质上的作用进行了分析。另外,文章还分析了布尔函数代数免疫阶与布尔函数汉明重量、非线性度、相关免疫阶等密码学性质之间的相互关系。最大代数免疫阶布尔函数是一类抗代数攻击最有效的布尔函数。文章证明了最大代数免疫阶平衡布尔函数本身及其补函数都存在代数次数为代数免疫阶的零化子。文章还对一种最大代数免疫阶布尔函数——择多函数进行了分析,研究了这种函数的平衡性、对称性、Walsh循环谱、自相关性、非线性度以及相关免疫阶等密码学性质。文章还介绍了三种已有的构造最大代数免疫阶布尔函数的方法,重点分析了这三种构造函数的一些其它密码学性质。更多还原

【Abstract】 Since algebraic attack method was proposed by Gallo cryptographist N.Courtois in 2003, it had been extensively used to analyze various cryptogram algorithms. The algebraic immune capability of Boolean function in cryptogram algorithm has already become an important criteria to judge the cryptographic capability of Boolean function.At present, the most successful examples of using algebraic attack on cryptogram algorithms are the attacks on stream ciphers Toyocrypt and LILI-128. Paper [4] has successfully broken out the two algorithms by building up some low-degree equations concerning inputs, outputs and keywords, using the low-degree annihilators of the nonlinear Boolean functions in the two algorithms. The same amount of low-degree annihilators are also found in the complementary functions of the nonlinear functions in the two algorithms. Consequently, double equations as paper[4] can be built up to reduce half the quantity of pairs of plain-ciphertext used to attack the two algorithms.To break out the cryptogram algorithms whose parameter of safety lies on the nonlinearity Boolean function using algebraic attack, what is the most important factor of attack efficiency is to find out the low-degree annihilators of the nonlinear Boolean functions. Making a good use of the relation between the logic border elements in the support set and the algebraic degree of the Boolean function, we got a new method to work out the low-degree annihilators of the Boolean function, called Karnargh Graphics Method. Its dissimilarity and affiliation to some typical methods used currently are expounded in the paper.The algebraic immunity (AI) of Boolean function is the significant index for Boolean function’s capacity to resist algebraic attack. This thesis gives the change of the AI of new function, when it is combined by two Boolean functions adding mutually, and the change of the AI of new function, when it is combined by some Boolean functions concatenating together. Meanwhile, we analyze how the two function-combining modes work on proportioning the other cryptographic properties. In addition, this paper shows the relationship between AI and other cryptographic properties, such as Hamming Weight, nonlinearity, correlation immunity etc.Boolean function with maximum AI is one of the most effective Boolean functions to resist algebraic attack. This paper proves that the annihilators with algebraic degree at AI exist both in the balance Boolean function with maximum AI and its complementary function. We have also talked about a sort of Boolean function with maximum AI called select-more function, and studied its balance, symmetry, Walsh transform, self-correlation, nonlinearity and correlation immunity etc. Three methods of construction of Boolean function with maximum AI are mentioned in this paper, and some other cryptographic properties of the three construction functions are unfolded as emphases.更多还原