周期为2p的二元序列的2—adic复杂度

2017-08-24姜丽颖

科技创新与应用 2017年21期

关键词：寄存器复杂度移位

姜丽颖

摘要：文章提出了一个快速算法确定周期为2p的二元序列的2-adic复杂度，给出了具体确定其序列2-adic复杂度的一个有效上界。

关键词：2-adic复杂度；周期序列；FCSR序列

中图分类号：TN918.4 文献标志码：A 文章编号：2095-2945（2017）21-0027-02

引言

流密码是私钥密码中一类非常重要的密码体制，流密码的安全性取决于密钥流的安全性，要求密钥流序列尽可能具有随机序列的某些特性。根据不同的攻击方法，人们提出了很多衡量序列安全性的指标，2-adic复杂度及线性复杂度是其中两个重要指标。它们分别是针对带进位反馈移位寄存器（FCSR）和线性反馈移位寄存器（LFSR）两种序列发生器而提出来的。较高的2-adic复杂度和线性复杂度使得密钥流序列可以有效抵抗有理逼近算法[1]和B-M算法[4]的攻击。

1994年，Klapper和Goredky提出了带进位反馈移位寄存器模型[3]。

设q为奇数，则连接数为q的FCSR结构图如图1：

其中

q+1=q1·2+…+qr·2r，qr=1，qi，an-i∈{0，1}，1？燮i？燮r，mn-1∈Z。具体实施过程如下：

（ⅰ）计算；

（ⅱ）右移一位，输出寄存器最右端的an-r；

（ⅲ）令an=？滓n（mod2）放入寄存器的最左端；

注：称m是记忆。FCSR的一个状态是指记忆m和寄存器的比特，即（mn-1，an-1，...，an-r）是FCSR的一个状态。若这个状态以后还出现，则称该状态是周期的。

1 基础知识

定义1 设=（s0，s1，s2，…）表示一条二元周期序列，称能够生成的最短的带进位反馈移位寄存器的长度为的2-adic复杂度，并记为？准2（），而称其连接数q为的最小生成数。

引理1 令=（s0，s1，s2，…）为一条二元周期序列，且其可被以q为连接数的带进位反馈移位寄存器生成，则有？琢（）=？撞si2i=s0+s12+s222+…=-r/q，其中满足-q？燮r？燮0，gcd（r，q）=1。则此带进位移位寄存器是生成的最短的带进位的反馈移位寄存器。因此，？准2（）=log2|q|。

令22p-1=（2p+1）（2p-1），L=2p+1，M=2p-1，S=（s0，s1，...，s2p-1）

记S（2）=s0+2s1+…+22p-1s2p-1。

则

引理2 设n？叟2为整数，A0，A1，...，Ak-1都是长度为n的 0，1向量，d为2n-1的因子，则有

定理1 设p为奇素数，=（s0，s1，s2，…）是周期为T=2p的二元序列，将S=（s0，s1，...，s2p-1）等分为2个长度为p的向量，S=（S0||S1），其中S0=（s0，s1，...，sp-1），S1=（sp，sp+1，...，s2p-1），则

证明：由T=2p可知

又因为

所以

因为

所以

显然，S0（2）=S1（2）和S0=S1等价。

所以