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

第2章 序列密码第2章 流密码习题及参考答案1 设3级LFSR的特征多项式为f(x)= 1+x+x3，（1）画出该LFSR的框图（2）给出输出序列的递推关系式（3）设初态为（0，0，1），写出输出序列（4）列出序列的游程解: (1) LFSR框图为： an-1an-2an-3+(2)由3级LFSR的特征多项式f(x)= 1+x+x3。得序列的递推公式为：an=an-1+an-3(3)所以输出序列如下：时刻状 态输出1级 2级 3级01 0 0011 1 0021 1 1130 1 1141 0 1150 1 0060 0 1171 0 00从上得输出序列为：0011101 00111010011101 (4)周期为7,长为1的0游程1个，长为1的1游程1个，长为2的0游程1个，长为3的1游程1个。 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) 所以输出如下：时刻状 态输出1级 2级 3级 4级01 0 1 1110 1 0 1120 0 1 0030 0 0 1141 0 0 0051 1 0 0060 1 1 0071 0 1 111101101001001000000101100011由上得11010001101000，周期为7. 状态转移图如下：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)， 所以输出如下:时刻状 态输出4级 3级 2级 1级01 0 0 1111 1 0 0021 1 1 0030 1 1 1140 0 1 1151 0 0 11所以输出序列为：10011100111001110011 ，周期为5。10010011011111101100状态转移图如下：4 设序列a=100101111000110，计算其自相关函数Ra,a(1)和Ra,a(5)。解：由 a = 100101111000110 所以 Ta = 001011110001101Ra,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= -1a = 100101111000110T5a = 111100011010010Ra, 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= 35 设序列 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.(4) 计算: d5=a5+a2=1+1=0，因此f6(x)= f5(x)= 1+x3，l6=l5=3.(5) 计算: d6=a6+a3=1+0=10，这时n=6，m=2，因此f7(x)= f6(x)+x4=1+x3+ x4，l7=max3，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 (i3),令i=3,4,5，得：解得：a1=1, a2=0, a3=1. 即 ki=ki-1+ki-3 (i3). 所以此系统的密钥 k 的反馈函数为：f(x)=1+x+x3。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)由LFSR1序列