1、第二章作业参考答案13 级线性反馈移位寄存器在 c31 时可有 4 种线性反馈函数，设其初始状态为(a 1,a2,a3)=(1,0,1)，求各线性反馈函数的输出序列及周期。解：此时线性反馈函数可表示为 f(a1,a2,a3)=a1c2a2c1a3当 c10，c 20 时，f(a 1,a2,a3)=a1c2a2c1a3a 1，输出序列为 101101， 周期3当 c10，c 21 时，f(a 1,a2,a3)=a1c2a2c1a3a 1a2，输出序列为 10111001011100，周期7当 c11，c 20 时，f(a 1,a2,a3)=a1c2a2c1a3a 1a3，输出序列为 101001
2、11010011，周期7当 c11，c 21 时，f(a 1,a2,a3)=a1c2a2c1a3a 1a2a3，有输出序列为 1010， 周期22设 n 级线性反馈移位寄存器的特征多项式为 p(x)，初始状态为(a 1,a2, ,an-1,an)=(0001)，证明输出序列的周期等于 p(x)的阶证：设 p(x)的阶为 p，由定理 2-3，由 r|p，所以 rp设 A(x)为序列a i的生成函数，并设序列a i的周期为 r，则显然有 A(x)p(x) (x)又 A(x)a 1+a2x+arxr-1+xr(a1+a2x+arxr-1)+(xr)2(a1+a2x+arxr-1)+a 1+a2x+a
3、rxr-1/(1-xr)a 1+a2x+arxr-1/(xr-1)于是 A(x)=(a1+a2x+arxr-1)/(xr-1) (x)/p(x)又(a 1,a2, ,an-1,an)=(0001)所以 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)x n-1所以必有 p(x)|(xr-1)，由 p(x)的阶的定义知，阶 pr综上所述：pr #3设 n4，f(a 1,a2,a3,a4)=a1a41a2a3，初始状态为
4、( 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 11 1 0 1 1 0 1 1 1 11 1 1 0 0 1 0 1 1 1（回到初始状态）所以此反馈序列输出为：11011周期为 54设密钥流是由 m2s 级 LFSR 产生，其前 m+2 个比特是(01) s+1，即 s1 个 01。问第 m+3 个比特有无可能是 1，为什么？解：不能是 1。可通过状态考察的方法证明以上结论。首先 m 级 LFSR 的状态是一个
5、 m 维的向量，则前 m 个比特构成一个状态 S0，可表示为(01) s，第 m1 个比特是 0，所以 S0 的下一个状态是 S1(10) s，第 m2 个比特是 1，所以 S1 的下一个状态是 S2(01) sS 0，回到状态 S0，所以下一个状态应是 S3=S1(10) s，也即第 m+3 个比特应该为 0。5设密钥流是由 n 级 LFSR 产生，其周期为 2n1，i 是任一正整数，在密钥流中考虑以下比特对(Si, Si+1), (Si+1, Si+2), , (Si+2n3 , S i+2n2 ), (Si+2n2 , S i+2n1 ),问有多少形如(S j, Sj+1)(1,1)的比
6、特对？证明你的结论。答：共有 2(n-2)证明：证明方法一：由于产生的密钥流周期为 2n1，且 LFSR 的级数为 n，所以是 m 序列以上比特对刚好是 1 个周期上，两两相邻的所有比特对，其中等于(1,1)的比特对包含在所有大于等于 2 的 1 游程中。由 m 序列的性质，所有长为 i 的 1 游程 (1 i n-2)有 2n-i-1/2 个，没有长为 n1 的 1 游程，有 1 个长为 n 的 1 游程。长为 i (i1)的 1 游程可以产生 i-1 个(1,1) 比特对，所以共有(1,1)比特对的数目 N2 n-2-2(21)2 n-3-2(31)2 n-i-2(i1) 2 n-(n2)
7、2 (n 21)n1 n12 (n-2)2)(nii证明方法 2：考察形如 11*的状态的数目，共有 2(n-2)个6已知流密码得密文串为 1010110110 和相应明文串 0100010001，而且还已知密钥流是使用 3 级线性反馈移位寄存器产生的，试破译该密码系统。解：由二元加法流密码的加密算法可知，将密文串和相应的明文串对应位模 2 加可得连续的密钥流比特为 1110100111设该三级线性反馈移位寄存器的反馈函数为 f(a1,a2,a3)=c3a1c2a2c1a3取其前 6 比特可建立如下方程(a4a5a6)(c 3,c2,c1) ，54332a即(c 3,c2,c1)(a 4a5a
8、6) (0 1 0) =(0 1 0) =(1 0 1)5432310所以 f(a1,a2,a3)=a1a3，即流密码的递推关系式为 ai+3=ai+2ai7若 GF(2)上的二元加法流密码的密钥生成器是 n 级线性反馈移位寄存器，产生的密钥是 m 序列。2.5节已知，敌手若知道一段长为 2n 的明密文对就可破译密钥流生成器。如果敌手仅知道长为 2n2 的明密文对，问如何破译密钥流生成器。解：破译 nLFSR 所产生的 m 序列，需要 2n 个连续比特，现在仅有 2n2 个连续的密钥比特(由长为2n2 的明密文对逐位异或得到)，因此需要猜测后两个比特。这有 00，01，10，11 四种情况，对
9、这些情况按下式逐一试破译(an+1an+2.a2n)( cncn-1.c1) =(cncn-1.c1) X12132na首先验证矩阵 X 的可逆性，如果不可逆则可直接排除此情况其次对于可逆的情况，求解出(c ncn-1.c1)，然后验证多项式 p(x)=1+c1x+cnxn 是否是本原多项式，如果是，则是一解。结果可能会多余 1 个。8.设 J-K 触发器中a k和b k分别为 3 级和 4 级 m 序列，且ak11101001110100bk001011011011000 001011011011000求输出序列c k及周期。解：由于 gcd(3，4)=1 且 a0b 01 所以序列 ck的
10、周期为(2 3-1)(24-1)=105又由 J-K 触发器序列的递推式 ck=( ak+bk+1) )ck-1+ak，令 c-1=0 可得输出序列为：ck=110010019设基本钟控序列产生器中a k和 bk分别为 2 级和 3 级 m 序列，且ak101101bk10011011001101求输出序列c k及周期。解：序列a k的周期 p12 213，序列 bk的周期 p22 317，w 1a 0a 1a 22而 gcd(w1, p2)=1。所以序列c k的周期 pp 1p23721记 LFSR2(产生序列b k)的状态向量为 k，则 0(100)，在 LFSR1(产生序列 ak)的控制
11、下，状态转移为：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 1ak 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
12、. 已知一有限状态自动机的状态转移图如图所示，则当初始状态为 s1，且输入字符序列为 A1(1)A2(1)A1(1)A3(1)A3(1)A1(1)时，输出的状态序列和输出符号序列分别是什么？s1( A2( 1 ), A3( 2 )s3( A2( 1 ), A2( 2 )s2( A2( 1 ), A1( 2 )( A3( 1 ), A3( 2 )( A1( 1 ), A1( 2 ) ( A1( 1 ), A3( 2 )( A3( 1 ), A2( 2 )( A1( 1 ), A2( 2 )( A3( 1 ), A1( 2 )解：根据有限状态机转移图有(1) 输出的状态序列 s1, s2, s2,
13、 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 的 n1 游程出现在一个周期的最后 n-1bit证：由于 p(x)是不可约多项式，则由 p(x)生成的非 0 序列的周期等于 p(x)的周期 r由 A(x)a 1+a2x+arxr-1+xr(a1+a2x+arxr-1)+(xr)2(a1+a2x+arxr-1)+a 1+a2x+arxr-1/(1-xr)a 1+a2x+arxr-1/(xr-1)于是 A(x)=(a1+a2x+
14、arxr-1)/(xr-1)1/ p(x)所以 p(x) (a1+a2x+arxr-1)= xr+1由于 p(x)的次数为 n，所以(a 1+a2x+arxr-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) (a1+a2x+arxr-1) (x) (xr-1)，其中 (x)满足 A(x)p(x) (x)，由于 p(x)次数为 n，而根据
15、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，所以方程右边 (x)=1，即 A(x)=1/p(x) #6.2 已知一序列的前 10 比特为 0010001111(1) 试用 B-M 算法求出产生该序列极小多项式和线性复杂度(2) 给出产生该序列的 LFSR 的递推式、结构图和周期(3) 破译该序列最少需要知道多少连续的密钥流比特解：(1) 产生该序列的极小多项式和线性复杂度分别是 1+x+x4 和 4n a10 dn fn(x) ln m fm(x) 0 0 0 1 01 0 0 1 02 1 1 1 0 2 13 0 0 1-d2x2+1=1+x3 2+1=34 0 0 1+x3 35 0 1 1+x3 36 1 1 (1+x3)+x5-2(1)=1 3 6 17 1 1 1+ x6-2(1)=1+x4 48 1 0 1+x4+x7-6(1)=1+x+x4 49 1 0 1+x+x4 410 1+x+x4 4(2)结构图、递推式和周期a4a1a2输出序列+a3递推式 ak+4=ak+3ak周期：由于是本原多项式，所以周期为 24-1=15(3) 需要知道至少 2x4=8 个连续的密钥流比特
