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

作     者：马蓁 

作者单位：解放军信息工程大学 

学位级别：硕士

导师姓名：戚文峰

授予年度：2014年

学科分类：07[理学] 070104[理学-应用数学] 0701[理学-数学] 

主      题：Fibonacci NFSR 串联 仿射子簇 Grain v1 

摘      要：随着近十年国际序列密码设计思想的转变,非线性反馈移位寄存器(NFSR)逐渐成为序列密码算法中重要的序列源生成器,因此对NFSR序列密码性质的研究受到很多关注.然而NFSR序列的基础理论还很不完善,许多基本的密码性质仍不清楚.例如,NFSR的输出序列中是否包含线性复杂度较低的序列.如果NFSR的输出序列中包含大量低线性复杂度的序列,则基于该NFSR的密码体制可能受到相关攻击,代数攻击或者是基于线性逼近的其它攻击.特别地,如果一个n级NFSR的输出序列包含一个级数小于n的线性反馈移位寄存器(LFSR)的输出序列全体,则称该n级NFSR有一个仿射子簇.如果一个NFSR能够分解为一个NFSR2到一个LFSR的串联,并且NFSR2的特征函数常数项为0,则该LFSR是NFSR的仿射子簇.NFSR包括Fibonacci NFSR和Galois NFSR.本文研究的是Fibonacci NFSR的仿射子簇问题,取得了以下主要结果:1.对于一个NFSR,给出了NFSR分解为一个NFSR2到一个LFSR串联的算法,并求出所有这样的分解.本文说明了所有这样的分解可以通过二元有限域上的单变元多项式分解得到.进一步,证明了如果NFSR有如上分解,则当NFSR2输出序列集中有一条低线性复杂度的序列时,NFSR的输出序列集中包含大量低线性复杂度的序列.特别地,当NFSR2的特征函数常数项为0时,NFSR的输出序列集中包含LFSR的输出序列全体.2.如果一个NFSR包含仿射子簇,称能够生成该仿射子簇的最短LFSR的级数为该仿射子簇的阶.本文给出了一个新的估计NFSR仿射子簇最大阶上界的方法,说明了该上界是紧的并且证明了该上界可以通过NFSR特征函数的代数正规型直接得到.*** 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不包含其它仿射子簇.