Galois非线性反馈移位寄存器.ppt

非线性反馈移位寄存器探讨 戚文峰 * * eSTREAM中Trivium * eSTREAM中Grain * eSTREAM的特点： ? 1. 序列源的非线性 2. 过滤函数简洁 3. 非线性序列代数结构刻画困难 * 目前关于非线性反馈移位寄存器序列(或非线性递归序列)的理论分析成果非常少, 尽管对其研究的历史并不短. * ? 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 * 称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))) f0(x0,?,xn?1) f1(x0,?,xn?1) ? fn?1(x0,?,xn?1) x0 x1 ? xn?1 并称aj???(aj(0),?aj(1),…)为寄存器xj的输出序列, 记Gj(F)为xj的输出序列全体. 特别称x0的输出为该反馈移位寄存器输出序列. 简记G(F)???G0(F). * ? Fibonacci非线性反馈移位寄存器(Fibonacci NFSR) f0(x0,?,xn?1) f1(x0,?,xn?1) ? fn?1(x0,?,xn?1) x0 x1 ? xn?1 若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) * ? 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) f0(x0,?,xn?1) f1(x0,?,xn?1) ? fn?1(x0,?,xn?1) x0 x1 ? xn?1 ? x0 x1 xn?1 f(x0,?,xn?1) * 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.5263-5271, Nov.2009. * 设 f0(x0,?,?x3)???x1 f1(x0,?,?x3)???x0???x2 f2(x0,?,?x3)???x0???x3 f3(x0,?,?x3)???x0???x1x3 x0 x1 x2 x3 * 定义 设U是n级NLFSR的反馈有向图, xj是U中一个顶点, 若xj有唯一的先导xi, 则删除顶点xj?, 对xj的每个后继xk, edge(xj,?xk)由edge(xi,?xk)代替, 得到一个新的有向图, 这个图的变换称为代替变换. x0 x1 x2 x3 x1 x2 x3 ? ? 对U的每个顶点重复进行代替变换, 直到不能再进行代替变换(即所到的图中没有顶点有唯一的先导), 变换所得的有向图称为U的既约反馈图. * 定理1 给定n级NFSR, U是其反馈图, 若U可以既约成单点xi, 则xi的输出是一个n级Fibonacci NFSR, 即存在n元布尔函数g(x0,?x1,?,?xn?1), 使得xi的任意一条输