作业参考 答案3级线性反馈移位寄存器在c3=1时可有4种.doc

第二章作业参考答案 1．3级线性反馈移位寄存器在c3＝1时可有4种线性反馈函数，设其初始状态为(a1,a2,a3)=(1,0,1)，求各线性反馈函数的输出序列及周期。 解：此时线性反馈函数可表示为f(a1,a2,a3)=a1? 当c1＝0，c2＝0时，f(a1,a2,a3)=a1?c2a2 输出序列为101101…， 周期＝3 当c1＝0，c2＝1时，f(a1,a2,a3)=a1?c2a2? 输出序列为10111001011100…，周期＝7 当c1＝1，c2＝0时，f(a1,a2,a3)=a1?c2a2? 输出序列为10100111010011…，周期＝7 当c1＝1，c2＝1时，f(a1,a2,a3)=a1?c2a2? 有输出序列为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)＝?(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)＝?(x)/p(x) 又(a1,a2, …,an-1,an)=(00…01) 所以p(x)(anxn-1+…+arxr-1)=?(x)(xr-1) 即 p(x)xn-1(an+…+arxr-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(a1,a2,a3,a4)=a1?a4?1?a2a3，初始状态为(a1,a2,a3, 解：由反馈函数和初始状态得状态输出表为 (a4 a3 a 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 (i1)的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 设该三级线性反馈移位寄存器的反馈函数为