线性反馈移位寄存器

第二章作业参考答案

1．3级线性反馈移位寄存器在c

3

＝1时可有4种线性反馈函数，设其初始状态为(a

1

,a

2

,a

3

)=(1,0,1)，求各线

性反馈函数的输出序列及周期。

解：此时线性反馈函数可表示为f(a

1

,a

2

,a

3

)=a

1

c

2

a

2

c

1

a

3

当c

1

＝0，c

2

＝0时，f(a

1

,a

2

,a

3

)=a

1

c

2

a

2

c

1

a

3

＝a

1

，

输出序列为101101…，周期＝3

当c

1

＝0，c

2

＝1时，f(a

1

,a

2

,a

3

)=a

1

c

2

a

2

c

1

a

3

＝a

1

a

2

，

…，周期＝7

当c

1

＝1，c

2

＝0时，f(a

1

,a

2

,a

3

)=a

1

c

2

a

2

c

1

a

3

＝a

1

a

3

，

…，周期＝7

当c

1

＝1，c

2

＝1时，f(a

1

,a

2

,a

3

)=a

1

c

2

a

2

c

1

a

3

＝a

1

a

2

a

3

，

有输出序列为1010…，周期＝2

2．设n级线性反馈移位寄存器的特征多项式为p(x)，初始状态为(a

1

,a

2

,…,a

n-1

,a

n

)=(00…01)，证明输出序

列的周期等于p(x)的阶

证：设p(x)的阶为p，由定理2-3，由r|p，所以rp

设A(x)为序列{a

i

}的生成函数，并设序列{a

i

}的周期为r，则显然有A(x)p(x)＝(x)

又A(x)＝a

1

+a

2

x+…+a

r

xr-1+xr(a

1

+a

2

x+…+a

r

xr-1)+(xr)2(a

1

+a

2

x+…+a

r

xr-1)+…

＝a

1

+a

2

x+…+a

r

xr-1/(1-xr)＝a

1

+a

2

x+…+a

r

xr-1/(xr-1)

于是A(x)=(a

1

+a

2

x+…+a

r

xr-1)/(xr-1)＝(x)/p(x)

又(a

1

,a

2

,…,a

n-1

,a

n

)=(00…01)

所以p(x)(a

n

xn-1+…+a

r

xr-1)=(x)(xr-1)即p(x)xn-1(a

n

+…+a

r

xr-n)=(x)(xr-1)

由于xn-1不能整除xr-1，所以必有xn-1|(x)，而(x)的次数小于n，所以必有(x)＝xn-1

所以必有p(x)|(xr-1)，由p(x)的阶的定义知，阶pr

综上所述：p＝r

#3．设n＝4，f(a

1

,a

2

,a

3

,a

4

)=a

1

a

4

1a

2

a

3

，初始状态为(a

1

,a

2

,a

3

,a

4

)＝(1,1,0,1)，求此非线性反馈移位寄存器的

输出序列及周期。

解：由反馈函数和初始状态得状态输出表为

(a

4

a

3

a

2

a

1

)输出(a

4

a

3

a

2

a

1

)输出

1011111111

1101101111

1110010111（回到初始状态）

所以此反馈序列输出为：11011…周期为5

4．设密钥流是由m＝2s级LFSR产生，其前m+2个比特是(01)s+1，即s＋1个01。问第m+3个比特有无

可能是1，为什么？

解：不能是1。

可通过状态考察的方法证明以上结论。

首先m级LFSR的状态是一个m维的向量，则前m个比特构成一个状态S

0

，可表示为(01)s，

第m＋1个比特是0，所以S

0

的下一个状态是S

1

＝(10)s，

第m＋2个比特是1，所以S

1

的下一个状态是S

2

＝(01)s＝S

0

，回到状态S

0

，

所以下一个状态应是S

3

=S

1

＝(10)s，也即第m+3个比特应该为0。

5．设密钥流是由n级LFSR产生，其周期为2n－1，i是任一正整数，在密钥流中考虑以下比特对

(S

i

,S

i+1

),(S

i+1

,S

i+2

),…,(S

i+2

n

－3

,S

i+2

n

－2

),(S

i+2

n

－2

,S

i+2

n

－1

),

问有多少形如(S

j

,S

j+1

)＝(1,1)的比特对？证明你的结论。

答：共有2(n-2)

证明：

证明方法一：由于产生的密钥流周期为2n－1，且LFSR的级数为n，所以是m序列

以上比特对刚好是1个周期上，两两相邻的所有比特对，其中等于(1,1)的比特对包含在所有大于等

于2的1游程中。由m序列的性质，所有长为i的1游程(1in-2)有2n-i-1/2个，没有长为n－1的1游程，

有1个长为n的1游程。

长为i(i>1)的1游程可以产生i-1个(1,1)比特对，

所以共有(1,1)比特对的数目N＝2n-2-2×(2－1)＋2n-3-2×(3－1)＋…＋2n-i-2×(i－1)＋…＋2n-(n－2)－2×(n

－2－1)＋n－1＝





2

2

2)1(2

n

i

ini＋n－1＝2(n-2)

证明方法2：考察形如11*…*的状态的数目，共有2(n-2)个

6

设该三级线性反馈移位寄存器的反馈函数为f(a

1

,a

2

,a

3

)=c

3

a

1

c

2

a

2

c

1

a

3

取其前6比特可建立如下方程

(a

4

a

5

a

6

)＝(c

3

,c

2

,c

1

)





















543

432

321

aaa

aaa

aaa

，

即(c

3

,c

2

,c

1

)＝(a

4

a

5

a

6

)

1

543

432

321























aaa

aaa

aaa

＝(010)

1

101

011

111





















=(010)





















011

101

111

=(101)

所以f(a

1

,a

2

,a

3

)=a

1

a

3

，即流密码的递推关系式为a

i+3

=a

i+2

a

i

7．若GF(2)上的二元加法流密码的密钥生成器是n级线性反馈移位寄存器，产生的密钥是m序列。2.5

节已知，敌手若知道一段长为2n的明密文对就可破译密钥流生成器。如果敌手仅知道长为2n－2的明密

文对，问如何破译密钥流生成器。

解：破译n－LFSR所产生的m序列，需要2n个连续比特，现在仅有2n－2个连续的密钥比特(由长为2n

－2的明密文对逐位异或得到)，因此需要猜测后两个比特。这有00，01，10，11四种情况，对这些情况

按下式逐一试破译

(a

n+1

a

n+2

..a

2n

)＝(c

n

c

n-1

..c

1

)

































121

132

21

nnn

n

n

aaa

aaa

aaa









=(c

n

c

n-1

..c

1

)X

首先验证矩阵X的可逆性，如果不可逆则可直接排除此情况

其次对于可逆的情况，求解出(c

n

c

n-1

..c

1

)，然后验证多项式p(x)=1+c

1

x+…+c

n

xn是否是本原多项式，

如果是，则是一解。

结果可能会多余1个。

8.设J-K触发器中{a

k

}和{b

k

}分别为3级和4级m序列，且

{a

k

}…

{b

k

}…

求输出序列{c

k

}及周期。

解：由于gcd(3，4)=1且a

0

＋b

0

＝1所以序列{c

k

}的周期为(23-1)(24-1)=105

又由J-K触发器序列的递推式c

k

=(a

k

+b

k

+1))c

k-1

+a

k

，令c

-1

=0可得输出序列为：

{c

k

}…

9．设基本钟控序列产生器中{a

k

}和{b

k

}分别为2级和3级m序列，且

{a

k

}＝101101…

{b

k

}…

求输出序列{c

k

}及周期。

解：序列{a

k

}的周期p

1

＝22－1＝3，序列{b

k

}的周期p

2

＝23－1＝7，w

1

＝a

0

＋a

1

＋a

2

＝2

而gcd(w

1

,p

2

)=1。所以序列{c

k

}的周期p＝p

1

p

2

＝3×7＝21

记LFSR2(产生序列{b

k

})的状态向量为σ

k

，则σ

0

＝(100)，在LFSR1(产生序列{a

k

})的控制下，状态转移为：

{a

k

}101

(100),(001),(001),(011),(110),(110),(101),(011),(011),(110),(100),(100),(001),(011),(011),(110)

1001

{a

k

}101101101

(101),(101),(011),(110),(110),(100),(001),(001),(011)

110111000

…

复习题

4.3.已知一有限状态自动机的状态转移图如图所示，则当初始状态为s

1

，且输入字符序列为

A

1

(1)A

2

(1)A

1

(1)A

3

(1)A

3

(1)A

1

(1)时，输出的状态序列和输出符号序列分别是什么？

解：根据有限状态机转移图有

(1)输出的状态序列s

1

,s

2

,s

2

,s

3

,s

2

,s

1

,s

2

(2)输出的符号序列A

1

(2)A

1

(2)A

2

(2)A

1

(2)A

3

(2)A

1

(2)

5.3n次不可约多项式p(x)的周期为r，试证A(x)=1/p(x)的充要条件是0的n－1游程出现在一

个周期的最后n-1bit

证：由于p(x)是不可约多项式，则由p(x)生成的非0序列的周期等于p(x)的周期r

由A(x)＝a

1

+a

2

x+…+a

r

xr-1+xr(a

1

+a

2

x+…+a

r

xr-1)+(xr)2(a

1

+a

2

x+…+a

r

xr-1)+…

＝a

1

+a

2

x+…+a

r

xr-1/(1-xr)＝a

1

+a

2

x+…+a

r

xr-1/(xr-1)

于是A(x)=(a

1

+a

2

x+…+a

r

xr-1)/(xr-1)＝1/p(x)

所以p(x)(a

1

+a

2

x+…+a

r

xr-1)=xr+1

由于p(x)的次数为n，所以(a

1

+a

2

x+…+a

r

xr-1)的最大次数为r-1-n，也就是说从xr-1-n+1开始系数都为0

即从xr-n到xr-1共n-1个系数都为0，由0的最大游程长度是n-1，所以0的n-1游程出现在一个周期的

最后n-1bit

必要性：

如果0的n-1游程出现在最后n-1bit，我们考察p(x)(a

1

+a

2

x+…+a

r

xr-1)＝(x)(xr-1)，其中(x)满足A(x)p(x)

＝(x)，由于p(x)次数为n，而根据0的n-1游程出现在最后n-1bit知(a

1

+a

2

x+…+a

r

xr-1)的最大次数是

r-1-(n-1)，所以方程左边p(x)(a

1

+a

2

x+…+a

r

xr-1)的次数为n+r-1-(n-1)=r，所以方程右边(x)=1，即A(x)=1/p(x)

#6.2已知一序列的前10比特为

(1)试用B-M算法求出产生该序列极小多项式和线性复杂度

(2)给出产生该序列的LFSR的递推式、结构图和周期

(3)破译该序列最少需要知道多少连续的密钥流比特

解：(1)产生该序列的极小多项式和线性复杂度分别是1+x+x4和4

na10d

n

f

n

(x)

l

n

mf

m

(x)

0

0010

1

0010

2

111021

3

001-d

2

x2+1=1+x32+1=3

4

001+x33

5

011+x33

6

11(1+x3)+x5-2(1)=1361

7

111+x6-2(1)=1+x44

8

101+x4+x7-6(1)=1+x+x44

9

101+x+x44

10

1+x+x44

(2)结构图、递推式和周期

递推式a

k+4

=a

k+3

a

k

周期：由于是本原多项式，所以周期为24-1=15

(3)需要知道至少2x4=8个连续的密钥流比特

(4)