现代密码学-第2章流密码习题与解答-20091021

第2章 序列密码

第2章 流密码

习题及参考答案

1． 设3级LFSR的特征多项式为f(x)= 1+x+x3，

（1）画出该LFSR的框图

（2）给出输出序列的递推关系式 （3）设初态为（0，0，1），写出输出序列 （4）列出序列的游程 解: (1) LFSR框图为：

an-1 an-2 an-3

+

(2)由3级LFSR的特征多项式f(x)= 1+x+x3。得序列的递推公式为：an=an-1+an-3 (3)所以输出序列如下： 时 刻 0 1 2 3 4 5 6 7 状 态 1级 2级 3级 1 0 0 1 1 0 1 1 1 0 1 1 1 0 1 0 1 0 0 0 1 1 0 0 输 出 0 0 1 1 1 0 1 0 从上得输出序列为：0011101 00111010011101…… (4)周期为7,长为1的0游程1个，长为1的1游程1个，长为2的0游程1个，长为3

的1游程1个。

1

第2章 序列密码

2． 设4阶LFSR序列按如下规律生成

an=an?1+an?4+an?2

初始状态为(a0, a1, a2, a3)=(1, 1, 0, 1)，求它的输出序列、周期及状态转移图。

解:由序列递推公式：an = an?1+an?4+an?2初始状态为(a0, a1, a2, a3)=(1, 1, 0, 1) 所以输出如下：

时 刻 0 1 2 3 4 5 6 7 状 态 1级 2级 3级 4级 1 0 1 1 0 1 0 1 0 0 1 0 0 0 0 1 1 0 0 0 1 1 0 0 0 1 1 0 1 0 1 1 输 出 1 1 0 1 0 0 0 1 由上得11010001101000……，周期为7. 状态转移图如下：

1101 0110 1010 0011 0100 0001 1000

3． 设4阶NLFSR的特征多项式为f(x1, x2, x3, x4)= x1+x3+x2x4，初态为(a0, a1, a2, a3)=(1, 0, 0, 1)，求它的输出序列、周期及状态转移图。

解:由NLFSR的特征多项式为f(x1, x2, x3, x4)= x1+x3+x2x4又初态为(a0, a1, a2, a3)=(1, 0, 0, 1)， 所以输出如下:

2

第2章 序列密码

时 刻 0 1 2 3 4 5 状 态 4级 3级 2级 1级 1 0 0 1 1 1 0 0 1 1 1 0 0 1 1 1 0 0 1 1 1 0 0 1 输 出 1 0 0 1 1 1 所以输出序列为：10011100111001110011 ……，周期为5。 状态转移图如下：

1001 0011 1100 0111 1110

4． 设序列a={100101111000110}，计算其自相关函数Ra,a(1)和Ra,a(5)。 解：由 a = 100101111000110

所以 Ta = 001011110001101

Ra,a(1) = (-1)1+0+(-1)0+0+(-1)0+1+(-1)1+0+(-1)0+1+(-1)1+1+(-1)1+1+(-1)1+1+(-1)1+0+(-1)0+0+(-1)0+0+

(-1)0+1+(-1)1+1+(-1)1+0+(-1)0+1 = -1

a = 100101111000110 T5a = 111100011010010

Ra, a(5) = (-1)1+1+(-1)0+1+(-1)0+1+(-1)1+1+(-1)0+0+(-1)1+0+(-1)1+0+(-1)1+1+(-1)1+1+(-1)0+0+(-1)0+1+

(-1)0+0+(-1)1+0+(-1)1+1+(-1)0+0 = 3

5． 设序列 a ={00100110101}，利用B-M算法求其对应线性移位寄存器的特征多项式f(x)

和长度l。

解：(1) 由题设知 k=2，取a0=a1=0，d2=1，

f1(x)= f2(x)=1，f3(x)=1+x3， l1=l2=0，l3=3

(2) 计算: d3=a3+a0=0+0=0，因此f4(x)= f3(x)= 1+x3，l4=l3=3 (3) 计算: d4=a4+a1=0+0=0，因此f5(x)= f4(x)= 1+x3，l5=l4=3.

3

第2章 序列密码

(4) 计算: d5=a5+a2=1+1=0，因此f6(x)= f5(x)= 1+x3，l6=l5=3. (5) 计算: d6=a6+a3=1+0=1?0，这时n=6，m=2，因此

f7(x)= f6(x)+x4=1+x3+ x4，l7=max{3，7-3}=4.

(6) 计算: d7=a7+a4+a3=0+0+0=0， 因此f8(x)= f7(x)= 1+x3+x4，l8=l7=4. (7) 计算: d8=a8+a5+a4=1+1+0=0， 因此f9(x)= f8(x)= 1+x3+x4，l9=l8=4. (8) 计算: d9=a9+a6+a5=0+1+1=0， 因此f10(x)= f9(x)= 1+x3+ x4, l10=l9=4. (9) 计算: d10=a10+a7+a6=1+0+1=0，因此f11(x)= f10(x)= 1+x3+ x4，l11=l10=4

综上可得其对应线性移位寄存器的特征多项式f(x)=f11(x) = 1-x3+ x4=1+x3+ x4， 级数l=l11 =4.

如果取前四位0010为输入，则得到的序列为：001001101011110……，周期为24-1=15。

6． 假设攻击者得到密文1010110110和对应明文0100010001，并且攻击者也知道密钥流是由3阶LFSR产生的，试破译该系统。

解: 由题设明文串：x = 0100010001…,密文串：y=1010110110…,

所以密钥串：k=x+y=1110100111…

由于k=k0k1k2k3…是 3 级 LFSR 序列，所以有ki=a1ki-1+a2ki-2+a3ki-3 (i≥3), 令i=3,4,5，得：

?k3?a1k2?a2k1?a3k0?0?a1?a2?a3?? ?k4?a1k3?a2k2?a3k1??1?a2?a3?k?ak?ak?ak?0?a?a14233213?5?解得：a1=1, a2=0, a3=1.

即 ki=ki-1+ki-3 (i≥3).

3

所以此系统的密钥 k 的反馈函数为：f(x)=1+x+x。 7． 在钟控序列生成器中，

（1）设LFSR1为一个3级m序列生成器，特征多项式为f1 (x)= x3+x+1，初始状态为a0=a1=a2=1，求LESR1的输出序列{ ak}；

（2）设LFSR2为一个2级m序列生成器，特征多项式为f2 (x)= x2+x+1，初始状态为b0=b1=1，求LESR2的输出序列{ bk}；

（3）设钟控序列生成器的输出序列{ ck}，该序列的周期是多少。

解:(1)由LFSR1序列的特征多项式为 f1(x)= x3+ x +1，所以递推公式为：an=an-1+an-3， 又初始状态为111，则输出序列{ak}为：1110100,1110100,1110100,1110100……，周期为 7。

2

(2)由LFSR1序列的特征多项式为f2 (x)= x+ x +1，所以递推公式为：an=an-1+an-2， 又初始状态为11，则输出序列{bk}为：110,110,110,110,110……，周期为3。

(3)所以钟控序列生成器的输出序列{ck}为：110111110111000110011, ……，周期为21。

4

本文来源：https://www.bwwdw.com/article/wdy5.html