非线性反馈移位寄存器序列仿射子簇的研究

发布时间：2018-02-25 00:19

本文关键词： Fibonacci NFSR 串联仿射子簇 Grain v1　出处：《解放军信息工程大学》2014年硕士论文　论文类型：学位论文

【摘要】：随着近十年国际序列密码设计思想的转变,非线性反馈移位寄存器(NFSR)逐渐成为序列密码算法中重要的序列源生成器,因此对NFSR序列密码性质的研究受到很多关注.然而NFSR序列的基础理论还很不完善,许多基本的密码性质仍不清楚.例如,NFSR的输出序列中是否包含线性复杂度较低的序列.如果NFSR的输出序列中包含大量低线性复杂度的序列,则基于该NFSR的密码体制可能受到相关攻击,代数攻击或者是基于线性逼近的其它攻击.特别地,如果一个n级NFSR的输出序列包含一个级数小于n的线性反馈移位寄存器(LFSR)的输出序列全体,则称该n级NFSR有一个仿射子簇.如果一个NFSR_1能够分解为一个NFSR2到一个LFSR的串联,并且NFSR2的特征函数常数项为0,则该LFSR是NFSR_1的仿射子簇.NFSR包括Fibonacci NFSR和Galois NFSR.本文研究的是Fibonacci NFSR的仿射子簇问题,取得了以下主要结果:1.对于一个NFSR_1,给出了NFSR_1分解为一个NFSR2到一个LFSR串联的算法,并求出所有这样的分解.本文说明了所有这样的分解可以通过二元有限域上的单变元多项式分解得到.进一步,证明了如果NFSR_1有如上分解,则当NFSR2输出序列集中有一条低线性复杂度的序列时,NFSR_1的输出序列集中包含大量低线性复杂度的序列.特别地,当NFSR2的特征函数常数项为0时,NFSR_1的输出序列集中包含LFSR的输出序列全体.2.如果一个NFSR包含仿射子簇,称能够生成该仿射子簇的最短LFSR的级数为该仿射子簇的阶.本文给出了一个新的估计NFSR仿射子簇最大阶上界的方法,说明了该上界是紧的并且证明了该上界可以通过NFSR特征函数的代数正规型直接得到.3.Grain v1的160级NFSR是由一个80级LFSR到一个80级NFSR串联而成.本文研究了如何求取该160级NFSR仿射子簇的问题.首先,本文证明了如果160级NFSR包含仿射子簇,则该仿射子簇必然是80级NFSR的仿射子簇.其次,利用2的结果,得到80级NFSR不包含阶大于31的仿射子簇.最后,设计了两个算法求解80级NFSR阶小于32的仿射子簇.实验结果表明除了包含一个2阶仿射子簇,Grain v1的160级NFSR不包含其它仿射子簇.
[Abstract]:With the change of the international sequence cipher design idea in recent ten years, the nonlinear feedback shift register (NFSRs) has gradually become an important sequence source generator in the sequence cipher algorithm. Therefore, much attention has been paid to the study of the cryptographic properties of NFSR sequences. However, the basic theory of NFSR sequences is not perfect. Many basic cryptographic properties are still unclear. For example, whether the output sequence of NFSR contains a sequence with lower linear complexity. If the output sequence of NFSR contains a large number of sequences with low linear complexity, Then the cryptosystem based on the NFSR may be attacked by correlation attack, algebraic attack or other attack based on linear approximation. If the output sequence of an n-order NFSR contains all the output sequences of a linear feedback shift register with a series less than n, then the n-order NFSR has an affine subfamily. If a NFSR_1 can be decomposed into a series of NFSR2 to a LFSR, And the characteristic function constant term of NFSR2 is 0, then the LFSR is an affine subfamily of NFSR_1. NFSR includes Fibonacci NFSR and Galois NFSR. In this paper, we study the affine subcluster of Fibonacci NFSR. The following main results are obtained: 1. For an NFS _ S _ 1, an algorithm is given to decompose NFSR_1 into a NFSR2 to a LFSR concatenation. All such decompositions are obtained. In this paper, we show that all such decompositions can be obtained by the polynomial decomposition of univariate variables over a binary finite field. Furthermore, it is proved that if NFSR_1 is like the upper decomposition, Then when there is a low linear sequence in the NFSR2 output sequence set, the output sequence set of NFSR1 contains a large number of low linear complexity sequences. When the characteristic function constant term of NFSR2 is 0:00, the output sequence set of NFS _ S _ S _ 1 contains the output sequence of LFSR. 2. If a NFSR contains an affine subfamily, The shortest LFSR series that can generate the affine subfamily is called the order of the affine subfamily. In this paper, a new method to estimate the upper bound of the maximum order of the NFSR affine subfamily is presented. This paper shows that the upper bound is compact and proves that the upper bound can be directly obtained by the algebraic normal form of the NFSR characteristic function. 3. The NFSR of grain v1 is formed in series from an 80 order LFSR to an 80 order NFSR. In this paper, we study how to obtain the NFSR of order 80. The problem of NFSR affine subclusters of order 160. first, In this paper, we prove that if the NFSR of order 160 contains an affine subfamily, the affine subfamily must be an affine subfamily of order 80 NFSR. Secondly, by using the result of 2, we obtain that the NFSR of order 80 does not contain an affine subfamily of order greater than 31. Two algorithms are designed to solve the affine subfamilies with order 80 NFSR less than 32. The experimental results show that no other affine subfamilies are included except for the 160-order NFSR containing a second-order affine cluster grain v1.
【学位授予单位】：解放军信息工程大学
【学位级别】：硕士
【学位授予年份】：2014
【分类号】：TN918.1

【相似文献】