步进的特征列算法及其在流密码分析中的应用

STEP-BY-STEP CS METHOD AND IT'S APPLICATION IN CRYPTANALYSIS OF STREAM CIPHERS

"吴特征列"算法是多元方程组求解的一种主要代数方法.讨论求解布尔多项式方程组特征列算法的改进算法.具体完成以下几方面工作:1)根据二阶有限域的特点,在已有工作的基础上提出布尔方程组求解的特征列算法的步进算法——SSTDCS,并且证明了该算法的正确性;2)用C语言在SzDD软件包上编程实现了该算法;3)把算法应用在流密码的代数分析中,对算法有效性进行检验,实验结果表明所给算法对大部分实例是有效与稳定的.

＂Wu characteristic set method＂ is a main algebraic method for computing zeros of polynomial systems. In this paper, we investigate an improved CS method for boolean polynomial equation systems solving. Based on our previous works and the special properties of Boolean ring, we introduce a step-by-step CS method-SSTDCS for Boolean polynomial equation systems solving and prove the correctness of the method. We implement the algorithm with C language and SZDD software package, and we test the efficiency of the algorithm by applying it to algebraic analysis of a class of stream ciphers. The experimental results show that they are quite efficient and stable for some examples.