姜丽颖

摘 要：文章提出了一个快速算法确定周期为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。则此带进位移位寄存器是生成的最短的带进位的反馈移位寄存器。……