非线性反馈移位寄存器串联分解唯一性探讨  

On the Uniqueness of Decomposition of a NFSR into a Cascade Connection of Smaller NFSRs

作　　者：王中孝[1] 戚文峰[1] 

机构地区：[1]解放军信息工程大学数学工程与先进计算国家重点实验室,郑州450002

出　　处：《电子与信息学报》2014年第7期1656-1660,共5页Journal of Electronics & Information Technology

基　　金：国家自然科学基金(61272042;61100202;61170235)资助课题

摘　　要：非线性反馈移位寄存器(NFSR)是目前序列密码研究的热点问题之一。假定一个NFSR可以分解为更低级数NFSR的串联,该文讨论此分解是否唯一的问题。首先,对线性反馈移位寄存器(LFSR)而言,其串联分解等价于二元有限域2F上单变元多项式的分解,因而是唯一的。其次,针对给定NFSR可以分解为更低级数NFSR到LFSR串联的情形,该文给出了此NFSR具有这样分解的一个充分必要条件,并据此指出所有这样分解中级数最大的LFSR是唯一的。该文的最后构造了一类反例,此类反例表明对一般情形而言,NFSR的串联分解并不唯一。The Nonlinear Feedback Shift Register.（NFSR） is one of hot topics of stream cipher in recent studies. The uniqueness of a NFSR assuming to be decomposed into a cascade connection of smaller NFSRs is discussed in this paper. Firstly, the decomposition of Linear Feedback Shift Register.（LFSR） is equivalent to the decomposition of univariate polynomials over the finite field of two elements F2, thus it is unique. Secondly, for the case that a NFSR can be decomposed into a cascade connection of a NFSR into a LFSR, a necessary and sufficient condition is offered for a NFSR to have such a decomposition. Based on this condition, it is indicated that during all such decompositions, the largest LFSR is unique. However, the construction of counterexamples in a class shows that, for the general cases, the decomposition of a NFSR into a cascade connection of smaller NFSRs is not unique.

关 键 词：流密码 非线性反馈移位寄存器 非线性反馈移位寄存器的串联 分解唯一性 

分 类 号：TN918.2[电子电信—通信与信息系统]