第二章 流密码 —— 现代密码学(杨波)课后题答案解析

第二章作业参考答案

1.3级线性反馈移位寄存器在c3=1时可有4种线性反馈函数,设其初始状态为(a1,a2,a3)=(1,0,1),求各线性反馈函数的输出序列及周期。

解:此时线性反馈函数可表示为f(a1,a2,a3)=a1Åc2a2Åc1a3

c1=0,c2=0时,f(a1,a2,a3)=a1Åc2a2Åc1a3a1

输出序列为101101…,        周期=3

c1=0,c2=1时,f(a1,a2,a3)=a1Åc2a2Åc1a3a1Åa2

输出序列为10111001011100…,周期=7

c1=1,c2=0时,f(a1,a2,a3)=a1Åc2a2Åc1a3a1Åa3

输出序列为10100111010011…,周期=7

c1=1,c2=1时,f(a1,a2,a3)=a1Åc2a2Åc1a3a1Åa2Åa3

有输出序列为1010…,        周期=2

2.设n级线性反馈移位寄存器的特征多项式为p(x),初始状态为(a1,a2, …,an-1,an)=(00…01),证明输出序列的周期等于p(x)的阶

证:设p(x)的阶为p,由定理2-3,由r|p,所以r£p

A(x)为序列{ai}的生成函数,并设序列{ai}的周期为r,则显然有A(x)p(x)=f(x)

 又A(x)=a1+a2x+…+arxr-1+xr(a1+a2x+…+arxr-1)+(xr)2(a1+a2x+…+arxr-1)+…

       =a1+a2x+…+arxr-1/(1-xr)=a1+a2x+…+arxr-1/(xr-1)

于是A(x)=(a1+a2x+…+arxr-1)/(xr-1)=f(x)/p(x)

又(a1,a2, …,an-1,an)=(00…01)

所以p(x)(anxn-1+…+arxr-1)=f(x)(xr-1)  即 p(x)xn-1(an+…+arxr-n)=f(x)(xr-1)

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

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

综上所述:pr   #

3.设n=4,f(a1,a2,a3,a4)=a1Åa4Å1Åa2a3,初始状态为(a1,a2,a3,a4)=(1,1,0,1),求此非线性反馈移位寄存器的输出序列及周期。

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

(a4  a3  a2  a1)   输出         (a4  a3  a2  a1)   输出

1  0  1  1     1            1  1  1  1     1

1  1  0  1     1            0  1  1  1     1

1  1  1  0     0            1  0  1  1     1(回到初始状态)

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

4.设密钥流是由m=2s级LFSR产生,其前m+2个比特是(01)s+1,即s+1个01。问第m+3个比特有无可能是1,为什么?

解:不能是1。

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

首先m级LFSR的状态是一个m维的向量,则前m个比特构成一个状态S0,可表示为(01)s

第m+1个比特是0,所以S0的下一个状态是S1=(10)s

第m+2个比特是1,所以S1的下一个状态是S2=(01)s=S0,回到状态S0

所以下一个状态应是S3=S1=(10)s,也即第m+3个比特应该为0。

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

       (Si, Si+1), (Si+1, Si+2), …, (Si+2n-3, S i+2n-2), (Si+2n-2, S i+2n-1),

问有多少形如(Sj, Sj+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=+n-1=2(n-2)

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

6.已知流密码得密文串为1010110110和相应明文串0100010001,而且还已知密钥流是使用3级线性反馈移位寄存器产生的,试破译该密码系统。

解:由二元加法流密码的加密算法可知,将密文串和相应的明文串对应位模2加可得连续的密钥流比特为1110100111

设该三级线性反馈移位寄存器的反馈函数为f(a1,a2,a3)=c3a1Åc2a2Åc1a3

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

(a4a5a6)=(c3,c2,c1),

即(c3,c2,c1)=(a4a5a6)=(0 1 0) =(0 1 0) =(1 0 1)

所以f(a1,a2,a3)=a1Åa3,即流密码的递推关系式为ai+3=ai+2Åai

7.若GF(2)上的二元加法流密码的密钥生成器是n级线性反馈移位寄存器,产生的密钥是m序列。2.5节已知,敌手若知道一段长为2n的明密文对就可破译密钥流生成器。如果敌手仅知道长为2n-2的明密文对,问如何破译密钥流生成器。

解:破译n-LFSR所产生的m序列,需要2n个连续比特,现在仅有2n-2个连续的密钥比特(由长为2n-2的明密文对逐位异或得到),因此需要猜测后两个比特。这有00,01,10,11四种情况,对这些情况按下式逐一试破译

(an+1an+2..a2n)=(cncn-1..c1) =(cncn-1..c1) X

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

其次对于可逆的情况,求解出(cncn-1..c1),然后验证多项式p(x)=1+c1x+…+cnxn是否是本原多项式,如果是,则是一解。

结果可能会多余1个。

8.设J-K触发器中{ak}和{bk}分别为3级和4级m序列,且

{ak}=11101001110100…

{bk}=001011011011000 001011011011000…

求输出序列{ck}及周期。

解:由于gcd(3,4)=1且a0b0=1所以序列{ck}的周期为(23-1)(24-1)=105

又由J-K触发器序列的递推式ck=( ak+bk+1) )ck-1+ak,令c-1=0可得输出序列为:

{ck}=11001001…

9.设基本钟控序列产生器中{ak}和{bk}分别为2级和3级m序列,且

{ak}=101101…

{bk}=10011011001101…

求输出序列{ck}及周期。

解:序列{ak}的周期p1=22-1=3,序列{bk}的周期p2=23-1=7,w1a0a1a2=2

而gcd(w1, p2)=1。所以序列{ck}的周期pp1p2=3×7=21

记LFSR2(产生序列{bk})的状态向量为σk,则σ0=(100),在LFSR1(产生序列{ak})的控制下,状态转移为:

{ak}   1    0    1   1    0    1    1    0    1    1   0    1    1   0    1

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

  1    0    0    0   1    1    1    0   0    1    1    1    0    0   0    1

 

{ak}   1    0    1   1    0    1    1    0    1   

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

      1    1    0   1    1    1    0    0    0   

所以输出序列为100011100111000111011 1000…

 

复习题

4.3. 已知一有限状态自动机的状态转移图如图所示,则当初始状态为s1,且输入字符序列为A1(1)A2(1)A1(1)A3(1)A3(1)A1(1)时,输出的状态序列和输出符号序列分别是什么? 

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

(1) 输出的状态序列 s1,  s2,   s2,   s3,   s2,    s1,    s2

(2) 输出的符号序列    A1(2)  A1(2)  A2(2)  A1(2)  A3(2)    A1(2)

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

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

A(x)=a1+a2x+…+arxr-1+xr(a1+a2x+…+arxr-1)+(xr)2(a1+a2x+…+arxr-1)+…

       =a1+a2x+…+arxr-1/(1-xr)=a1+a2x+…+arxr-1/(xr-1)

于是A(x)=(a1+a2x+…+arxr-1)/(xr-1)=1/p(x)

所以p(x) (a1+a2x+…+arxr-1)= xr+1

由于p(x)的次数为n,所以(a1+a2x+…+arxr-1)的最大次数为r-1-n,也就是说从xr-1-n+1开始系数都为0

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

必要性:

如果0的n-1游程出现在最后n-1bit,我们考察p(x) (a1+a2x+…+arxr-1)=f(x) (xr-1),其中f(x)满足A(x)p(x)=f(x),由于p(x)次数为n,而根据0的n-1游程出现在最后n-1bit 知(a1+a2x+…+arxr-1)的最大次数是

r-1-(n-1),所以方程左边p(x) (a1+a2x+…+arxr-1)的次数为n+ r-1-(n-1)=r,所以方程右边f(x)=1,即A(x)=1/p(x) #

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

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

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

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

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

n

a10 

dn 

fn(x)

ln 

m

fm(x)

0

0

0

1

0

 

 

1

0

0

1

0

 

 

2

1

1

1

0

2

1

3

0

0

1-d2x2+1=1+x3

2+1=3

 

 

4

0

0

1+x3

3

 

 

5

0

1

1+x3

3

 

 

6

1

1

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

3

6

1

7

1

1

1+ x6-2(1)=1+x4

4

 

 

8

1

0

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

4

 

 

9

1

0

1+x+x4

4

 

 

10

 

 

1+x+x4

4

 

 

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

递推式 ak+4=ak+3Åak

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

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

热门相关:酒吧探戈   姐妹们的丑闻   绍宋   星界游民   黜龙