摘要： 线性递归序列的容错综合问题在流密码分析领域具有重要的理论分析与应用价值。利用伽罗华域上2个变元多项式 的齐次理想刻画齐次关键方程的解空间，通过齐次关键方程解决线性递归序列综合问题不但具有可行性，而且具有某些容错性质。为此，根据二元多项式齐次理想Gr?bner基算法，提出一种求解齐次关键方程的快速算法，并给出一个定理来论述算法实现序列综合的充分条件。通过实验仿真对该算法在不同的序列复杂度和误码率下的容错性能进行分析，结果表明，该算法的成功率与序列复杂度呈线性关系，在误码率为10–3的情况下，对于序列复杂度为65、序列长度为1 000的序列，成功率可达86.6%以上。

关键词: 序列综合, 关键方程, Berlekamp-Massey算法, Gr?bner基, 容错性能

Abstract: The Synthesis of Linear Shift Register(LSR) with error tolerance is an important problem in the analysis of stream cipher. This paper constructs a homogenous key equation which is described by homogenous ideal of . It shows that the Homogenous key module equation can be used to solve the synthesis problem of the LSR sequence. By means of a fast computation of Gr?bner basis of homogenous polynomial ideal with two variables, the paper finds an efficient algorithm to solve the Homogenous key module equation. It gives a theorem to show the error tolerance of the algorithm. Results show that the success rate of the algorithm has a linear relationship with the complexity of the sequence, for a sequence with length of 1 000 and complexity of 65, the success rate of the algorithm is up to 86.6% at an error code rate of 10–3.

Key words: sequence synthesis, key equation, Berlekamp-Massey algorithm, Gr?bner basis, error tolerance performance

中图分类号: 

• TP309