非线性反馈移位寄存器探讨 戚文峰.

Presentation on theme: "非线性反馈移位寄存器探讨 戚文峰."— Presentation transcript:

1 非线性反馈移位寄存器探讨 戚文峰

2

3 eSTREAM中Trivium

4 eSTREAM中Grain

5 eSTREAM的特点： 1. 序列源的非线性 2. 过滤函数简洁 3. 非线性序列代数结构刻画困难

6 目前关于非线性反馈移位寄存器序列(或非线性递归序列)的理论分析成果非常少, 尽管对其研究的历史并不短.

7  Galois非线性反馈移位寄存器 定义 设fi(x0, x1,…, xn1)是n元布尔函数, i  0,1,…, n  1, n级Galois型非线性反馈移位寄存器(简称Galois NFSR)如下图定义 f0(x0,,xn1) f1(x0,,xn1)  fn1(x0,,xn1) x0 x1 xn1

8 称F  ( f0(x0,, xn1),, fn1(x0,, xn1))是NFSR的反馈函数, 若i时刻时(x0,, xn1)的状态为(a0(i),…, an1(i)), 则i  1时刻的状态为 (a0(i  1),…, an1(i  1))  ( f0(a0(i),…, an1(i)) ,…, fn1(a0(i),…, an1(i))) 并称aj  (aj(0), aj(1),…)为寄存器xj的输出序列, 记Gj(F)为xj的输出序列全体. 特别称x0的输出为该反馈移位寄存器输出序列. 简记G(F)  G0(F). f0(x0,,xn1) f1(x0,,xn1)  fn1(x0,,xn1) x0 x1 xn1

9  Fibonacci非线性反馈移位寄存器(Fibonacci NFSR)
若f0  x1,…, fn2  xn1, 并令f(x0,, xn1)  fn1(x0,, xn1). 以f为反馈函数的n级Fibonacci NFSR如右图, x0的输出序列全体记为G( f ).  x0 x1 xn1 f(x0,,xn1) f0(x0,,xn1) f1(x0,,xn1)  fn1(x0,,xn1) x0 x1 xn1

10  Galois NFSR与Fibonacci NFSR的等价问题
设F  ( f0(x0,, xn1),, fn1(x0,, xn1))是Galois NFSR的反馈函数, 考虑是否存在f(x0,, xn1)和0  i  n  1, 使得 G( f )  Gi(F)  x0 x1 xn1 f(x0,,xn1) f0(x0,,xn1) f1(x0,,xn1)  fn1(x0,,xn1) x0 x1 xn1

11 Elena Dubrova(瑞典)研究了该问题
定义 设n级Galois NFSR以F  ( f0(x0,, xn1),, fn1(x0,, xn1)) 为反馈函数, 定义其反馈有向图为: 以n个寄存器x0, x1,, xn1为n个顶点, 对于 xi 和 xj  (i和j可以相同), 若fj(x0,, xn1)含变元 xi, 则 xi 到 xj 有一有向弧, 记为edge(xi, xj), 此时, 称 xi为xj 的先导, xj 为 xi 的后继. E. Dubrova, “A Transformation from the Fibonacci to the Galois NLFSRs,” IEEE Transactions on Information Theory, vol.55, pp , Nov.2009.

12 设 f0(x0,, x3)  x1 f1(x0,, x3)  x0  x2 f2(x0,, x3)  x0  x3
f3(x0,, x3)  x0  x1x3 x0 x1 x2 x3

13  定义 设U是n级NLFSR的反馈有向图, xj是U中一个顶点, 若xj有唯一的先导xi, 则删除顶点xj , 对xj的每个后继xk, edge(xj, xk)由edge(xi, xk)代替, 得到一个新的有向图, 这个图的变换称为代替变换. x1 x2 x3 x0 x1 x2 x3  对U的每个顶点重复进行代替变换, 直到不能再进行代替变换(即所到的图中没有顶点有唯一的先导), 变换所得的有向图称为U的既约反馈图.

14 ai(k  n)  g(ai(k ),, ai(k  n  1)), k  0,1,.
 定理1 给定n级NFSR, U是其反馈图, 若U可以既约成单点xi, 则xi的 输出是一个n级Fibonacci NFSR, 即存在n元布尔函数g(x0, x1,, xn1), 使得 xi的任意一条输出序列ai  (ai(0), ai(1),)满足 ai(k  n)  g(ai(k ),, ai(k  n  1)), k  0,1,. E. Dubrova, “A Transformation from the Fibonacci to the Galois NLFSRs,” IEEE Transactions on Information Theory, vol.55, pp , Nov.2009.

15

16

17

18

19

20 谢 谢 !