《非线反馈移位寄存器探讨.ppt》由会员分享，可在线阅读，更多相关《非线反馈移位寄存器探讨.ppt（20页珍藏版）》请在三一办公上搜索。
1、非线性反馈移位寄存器探讨,戚文峰,2,3,eSTREAM中Trivium,4,eSTREAM中Grain,5,eSTREAM的特点：1.序列源的非线性2.过滤函数简洁3.非线性序列代数结构刻画困难,6,目前关于非线性反馈移位寄存器序列(或非线性递归序列)的理论分析成果非常少,尽管对其研究的历史并不短.,7,Galois非线性反馈移位寄存器,定义 设fi(x0,x1,xn1)是n元布尔函数,i0,1,n1,n级Galois型非线性反馈移位寄存器(简称Galois NFSR)如下图定义,8,称F(f0(x0,xn1),fn1(x0,xn1)是NFSR的反馈函数,若i时刻时(x0,xn1)的状态为(
2、a0(i),an1(i),则i1时刻的状态为(a0(i1),an1(i1)(f0(a0(i),an1(i),fn1(a0(i),an1(i),并称aj(aj(0),aj(1),)为寄存器xj的输出序列,记Gj(F)为xj的输出序列全体.特别称x0的输出为该反馈移位寄存器输出序列.简记G(F)G0(F).,9,Fibonacci非线性反馈移位寄存器(Fibonacci NFSR),若f0 x1,fn2xn1,并令f(x0,xn1)fn1(x0,xn1).以f为反馈函数的n级Fibonacci NFSR如右图,x0的输出序列全体记为G(f).,10,Galois NFSR与Fibonacci NF
3、SR的等价问题,设F(f0(x0,xn1),fn1(x0,xn1)是Galois NFSR的反馈函数,考虑是否存在f(x0,xn1)和0in1,使得 G(f)Gi(F),11,Elena Dubrova(瑞典)研究了该问题,定义 设n级Galois NFSR以F(f0(x0,xn1),fn1(x0,xn1)为反馈函数,定义其反馈有向图为:以n个寄存器x0,x1,xn1为n个顶点,对于 xi 和 xj(i和j可以相同),若fj(x0,xn1)含变元 xi,则 xi 到 xj 有一有向弧,记为edge(xi,xj),此时,称 xi为xj 的先导,xj 为 xi 的后继.,E.Dubrova,“A
4、Transformation from the Fibonacci to the Galois NLFSRs,”IEEE Transactions on Information Theory,vol.55,pp.5263-5271,Nov.2009.,12,设f0(x0,x3)x1f1(x0,x3)x0 x2f2(x0,x3)x0 x3f3(x0,x3)x0 x1x3,13,定义 设U是n级NLFSR的反馈有向图,xj是U中一个顶点,若xj有唯一的先导xi,则删除顶点xj,对xj的每个后继xk,edge(xj,xk)由edge(xi,xk)代替,得到一个新的有向图,这个图的变换称为代替变换.,
5、对U的每个顶点重复进行代替变换,直到不能再进行代替变换(即所到的图中没有顶点有唯一的先导),变换所得的有向图称为U的既约反馈图.,14,定理1 给定n级NFSR,U是其反馈图,若U可以既约成单点xi,则xi的输出是一个n级Fibonacci NFSR,即存在n元布尔函数g(x0,x1,xn1),使得xi的任意一条输出序列ai(ai(0),ai(1),)满足ai(kn)g(ai(k),ai(kn1),k0,1,.,E.Dubrova,“A Transformation from the Fibonacci to the Galois NLFSRs,”IEEE Transactions on Information Theory,vol.55,pp.5263-5271,Nov.2009.,15,16,17,18,19,20,谢 谢!,
