非线性反馈移位寄存器探讨(杭州会议)2011-12)ppt.ppt

《非线性反馈移位寄存器探讨(杭州会议)2011-12)ppt.ppt》由会员分享，可在线阅读，更多相关《非线性反馈移位寄存器探讨(杭州会议)2011-12)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,

2、xn1)的状态为(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),若f0x1,fn2xn1, 并令f(x0,xn1)fn1(x0,xn1).以f为反馈函数的n级Fibonacci NFSR如右图,x0的输出序列全体记为G(f).,10, Galois NF

3、SR与Fibonacci NFSR的等价问题,设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 的先导

4、, xj 为 xi 的后继.,E. Dubrova, “A 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)x0x2f2(x0,x3)x0x3f3(x0,x3)x0x1x3,13,定义 设U是n级NLFSR的反馈有向图, xj是U中一个顶点, 若xj有唯一的先导xi, 则删除顶点xj, 对xj的每个后继xk, edge(xj,xk)由ed

5、ge(xi,xk)代替, 得到一个新的有向图, 这个图的变换称为代替变换.,对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,谢 谢 !,