【作者】 王秋艳；

【导师】 金晨辉；

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

【摘要】 代数攻击是目前密码学领域的研究热点之一。本文对多输出前馈模型的代数攻击进行了深入的研究,主要做出了以下几方面的工作:1.对多输出布尔函数的零化函数进行了研究。给出了零化函数集合的代数结构,证明了多输出布尔函数的零化函数集合是布尔函数环的一个理想;分析了零化函数与分量函数组合的零化子之间的关系,证明了多输出函数在某点的零化函数集合与分量函数的某组合的零化子集合是相等的;对文献[19]的寻找布尔函数零化子的方法进行了分析,提出了两个寻找多输出函数的零化函数的算法。2.对多输出布尔函数的代数免疫阶进行了研究。给出了多输出函数三种代数免疫阶之间的大小关系,证明了从零化函数角度定义的代数免疫阶与非线性代数免疫阶是相等的;给出了多输出函数的代数免疫阶与函数的平衡性和非线性性这两种密码学性质的相互关系;证明了,n进m出多输出函数的代数免疫阶的上界为|(n-1)/2|;分析了文献[35]中计算布尔函数代数免疫阶的算法,提出了计算多输出函数代数免疫阶的方法。3.对前馈模型序列密码的代数攻击进行了研究。利用零化函数,给出对多输出前馈模型的代数攻击方法;利用不同时刻单输出前馈模型中布尔函数的输入状态的相关性,将布尔函数转化为多输出布尔函数进行研究,利用零化函数找到关于密钥的低次方程组,从而提出了对单输出前馈模型的改进代数攻击算法。该算法在一般情况下均优于文献[14]给出的攻击方法,并且在某些前馈模型中该算法优于快速代数攻击,最后通过实验对该结果进行了验证。对弱化的LILI-128算法,该算法的存储复杂度和计算复杂度均与快速代数攻击相同,而所需密钥流比特数却远远小于快速代数攻击。更多还原

【Abstract】 Algebraic attack is one of the focuses in the cryptography nowadays. In this paper we will study the algebraic attack on stream ciphers with several outputs deeply, our contributions mainly include the following three parts:1. We study the annihilator functions of multi-outputs Boolean function. We give the algebraic structure of the set of annihilator functions, prove that the set of annihilator functions of multi-outputs Boolean function is equal to the set of annihilator of combinatorial function of component functions; analyze the method of finding annihilator of Boolean function in [19], present two methods of finding annihilator functions of multi-outputs Boolean function.2. We study the algebraic immunity of multi-outputs Boolean function. We show the relation of three algebraic immunity, prove that the algebraic immunity of annihilator functions is equal to the algebraic immunity of combinatorial function of component functions; show the relationship between algebraic immunity and other cryptographic properties, such as balance and nonlinearity; prove that the upper bound algebraic immunity of n-inputs m-outputs Boolean function is [(n-1)/2]; analyze the method of computing the algebraic immunity in [35], present a method of computing the algebraic immunity of multi-outputs function.3. We study the algebraic attack on stream ciphers with linear feedback. We give the method of algebraic attack on stream ciphers with multi-outputs using the annihilator function; using the relativity between inputs of Boolean function in stream with linear feedback of different clock, convert Boolean function to multi-outputs Boolean function, and find low-degree functions about the key using annihilator functions, thereby gain the improved algebraic attack on stream ciphers with linear feedback. Finally, we analyze the computational complexity of our attack which is better than the algebraic attack in [14], and in some stream ciphers with linear feedback, our attack is better than fast algebraic attack, and test the result by computer simulations; the memory complexity and the computation complexity of our attack on simplified version of LILI-128 are equal to fast algebraic attack, but the date complexity is much lower.更多还原