作業(yè)參考答案3級線性反饋移位寄存器在c3=1時(shí)可有4種

1、第二章作業(yè)參考答案1 3 性反 移位寄存器在c 1 可有 4 種 性反 函數(shù)， 其初始狀 ( a , a , a )=(1,0,1) ，求3123各 性反 函數(shù)的 出序列及周期。解：此 性反 函數(shù)可表示 f(1,a2,3)= 1221 3aaac ac a當(dāng) c1 0， c2 0 ， f ( a1 , a2, a3)= a1c2a2c1a3 a1， 出序列 101101，周期 3當(dāng) c1 0， c2 1 ， f ( a1 , a2, a3)= a1c2a2c1a3 a1a2， 出序列 10111001011100，周期 7當(dāng)c1 1，2 0 ，f( 1 ,a2, 3)= 12 21 3 13，

2、caa a c a c a a a 出序列 10100111010011，周期 7當(dāng) c1 1， c2 1 ， f ( a1 , a2, a3)= a1c2a2c1a3 a1a2 a3，有 出序列 1010，周期 22 n 性反 移位寄存器的特征多 式 (x)，初始狀 (a1,a2, ,an-1, n)=(00 01) ， 明 pa出序列的周期等于p( x) 的 ： p( x) 的 p，由定理2-3 ，由 r | p，所以 rp設(shè) A( x) 序列 a 的生成函數(shù)，并 序列 a 的周期 r ， 然有 A( x) p( x) ( x)ii又 A( x) a1+a2x+ar xr -1 +xr (

3、 a1+a2x+ar xr -1 )+( xr ) 2( a1+a2x+ar xr -1 )+ 1+ 2+r -1/(1-r) 1+ 2 +r -1/(r-1)xxxaa xaa a xa xrrr -1r ( x)/ p( x)于是 A( x)=( a +a x+a x)/(x -1)12r又 ( a1, a2, , an-1 , an)=(00 01)nr-1 )=rnrnr所以 p( x)( anx-1 +ar x( x)( x-1)即 p( x) x -1 ( an+ar x-)=( x)( x -1)由于 xn-1不能整除 xr -1，所以必有 xn-1 |( x) ，而( x) 的

4、次數(shù)小于 n，所以必有( x) xn-1所以必有(x)|(r -1)，由() 的 的定 知， p rpxp x 上所述： p r #3 n 4，f ( a1, a2, a3, a4)= a1a41a2a3，初始狀 ( a1, a2, a3, a4) (1,1,0,1)，求此非 性反 移位寄存器的 出序列及周期。解：由反 函數(shù)和初始狀 得狀 出表 ( a a3a a ) 出(a a3a a ) 出421421101 111 1 1 11110 110 1 1 11111 001 0 1 11（回到初始狀 ）所以此反 序列 出 ：11011周期 54 密 流是由 2s級 LFSR 生，其前m+2個(gè)

5、比特是 (01) s+1，即 s 1 個(gè) 01。 第 m+3個(gè)比特有無可m能是 1， 什么？解：不能是 1。可通 狀 考察的方法 明以上 。首先 m級 LFSR的狀 是一個(gè)m 的向量， 前0s，m個(gè)比特構(gòu)成一個(gè)狀 S ，可表示 (01)第 m1 個(gè)比特是 0，所以 S0 的下一個(gè)狀 是 S1(10) s，第 m2 個(gè)比特是 1，所以 S1 的下一個(gè)狀 是 S2(01) s S0，回到狀 S0，所以下一個(gè)狀 是 S3=S1 (10) s，也即第 m+3個(gè)比特 0。5 密 流是由n 級 LFSR 生，其周期 2n 1， i 是任一正整數(shù)，在密 流中考 以下比特 (Si , Si +1), (Si

6、+1,Si +2),nnnn, ( Si +2 3,S i +2 2), ( Si +2 2,S i +2 1), 有多少形如 ( Sj ,Sj +1) (1,1)的比特 ？ 明你的 。答：共有 2(n-2) 明： 明方法一：由于 生的密 流周期 2n 1，且 LFSR的 數(shù) n，所以是 m序列以上比特 好是1 個(gè)周期上，兩兩相 的所有比特 ，其中等于(1,1) 的比特 包含在所有大于等于 2 的 1 游程中。由 m序列的性 ，所有 i的 1游程 (1in-2) 有 2n- i -1 /2 個(gè)，沒有 n 1 的1 游程，有 1 個(gè) n 的 1 游程。長為 i (i1) 的 1 游程可以 生i-

7、1 個(gè) (1,1)比特 ，所以共有 (1,1)比特 的數(shù)目 2n-2-2 (2 1) 2n-3-2 (3 1) 2n-i-2 (i 1) 2n-( n 2) 2Nn2(n 2 1) n 12n i 2 (i 1) n 1 2(n-2)i2 明方法2：考察形如11* * 的狀 的數(shù)目，共有2(n-2) 個(gè)6已知流密 得密文串 1010110110 和相 明文串0100010001 ，而且 已知密 流是使用3 性反 移位寄存器 生的， 破 密 系 。解：由二元加法流密 的加密算法可知，將密文串和相 的明文串 位模2 加可得 的密 流比特為 1110100111 三 性反 移位寄存器的反 函數(shù) f(

8、 1,2,a3)= 3 12 21 3aac ac ac a取其前 6 比特可建立如下方程a1a2a3( a4 a5 a6 ) ( c3, c2, c1) a2a3a4，a3a4a5a1a2a311111111即( c3, c2, c1) ( a4a5a6 ) a2a3a4(0 1 0)110=(0 1 0)101=(1 0 1)a3a4a5101110所以f(a1,2,a3)=1a3，即流密 的 推關(guān)系式 ai +3=i +2iaaaa7若 GF(2) 上的二元加法流密 的密 生成器是n 性反 移位寄存器， 生的密 是m 序列。 2.5 已知， 手若知道一段 2n 的明密文 就可破 密 流生

9、成器。如果 手 知道 2n 2 的明密文 ， 如何破 密 流生成器。解：破 n LFSR所 生的 m序列，需要2n 個(gè) 比特， 在 有2n 2 個(gè) 的密 比特 ( 由 2n2 的明密文 逐位異或得到) ，因此需要猜 后兩個(gè)比特。 有00，01，10，11 四種情況， 些情況按下式逐一 破 an+1an+2a2ncncn -1c1a1a2ancncn-1c1X(.).a2a3an 1=(.)()anan1a2n 1首先 矩 X 的可逆性，如果不可逆 可直接排除此情況p xc1x cnxn 是否是本原多 其次 于可逆的情況，求解出(cncn-1.c1，然后 多 式)=1+)(+ +式，如果是， 是

10、一解。 果可能會(huì)多余1 個(gè)。8. 設(shè) J-K 觸 器中 ak 和 bk 分 3 和 4 級 m序列，且 ak 11101001110100 bk 001011011011000 001011011011000 求 出序列 ck 及周期。解：由于 gcd(3 ， 4)=1 且 a0 b0 1 所以序列 ck 的周期 (2 3-1)(2 4-1)=105又由 J-K 觸 器序列的 推式 ck=(a k bk+1) )ck-1ak，令 c-1=0可得輸出序列為：+ ck=11001001 9 基本 控序列 生器中 ak 和 bk 分 2 和 3級 m序列，且 ak 101101 bk 1001101

11、1001101求 出序列 ck 及周期。解：序列 ak 的周期 p1 22 1 3，序列 bk 的周期 p2231 7， w1 a0 a1 a2 2而 gcd( w1, p 2)=1 。所以序列 ck 的周期 p p1p2 37 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

12、),(110)1000111001110001 ak 1 0 1 1 0 1 1 0 1(101),(101),(011),(110),(110),(100),(001), (001),(011)110111000所以 出序列 100011100111000111011 1000 復(fù) 4.3.已知一有限狀態(tài)自動(dòng)機(jī)的狀態(tài)轉(zhuǎn)移圖如圖所示，則當(dāng)初始狀態(tài)為s1，且輸入字符序列為 A1(1) A2(1) A1(1) A3(1) A3(1) A1 (1) 時(shí)，輸出的狀態(tài)序列和輸出符號(hào)序列分別是什么？(A2(1) , A3(2) )s1(A3(1) , A3(2) )(A3(1) , A2(2) )(A1(

13、1), A1 (2)(A1(1) , A3(2) )(A2(1) , A1(2) )s2(A1(1) , A2(2) )3(A2(1) , A2(2) )s(A3(1), A1 (2)解：根據(jù)有限狀 機(jī) 移 有(1) 出的狀 序列 s ,s,s, s,s,s,s2122321(2) 出的符號(hào)序列(2)A(2)A(2)A(2)A(2)A(2)A213111p x的周期為 r ，試證 A x)=1/p x的充要條件是0的游程出現(xiàn)5.3 n 次不可約多項(xiàng)式 ( )( )n 1在一個(gè)周期的最后 n-1bit ：由于 () 是不可 多 式， 由() 生成的非 0 序列的周期等于() 的周期rp xp x

14、p x由 A( x) a1+a2x+ar xr -1 +xr ( a1+a2x+ar xr -1 )+( xr ) 2( a1+a2x+ar xr -1 )+ a1+a2x+ar xr -1/(1-xr ) a1+a2x+ar xr -1/( xr -1)于是 A( x)=( a1+a2x+ar xr -1 )/(xr -1) 1/ p( x)r -1r所以 p( x) ( a +a x+a x)= x +112r由于 p( x) 的次數(shù) n，所以 ( a+a x+ar -1的最大次數(shù) r -1- n，也就是 從 xr -1- n+1x)開始系數(shù)都 012rr - nr -1共 n-1個(gè)系數(shù)都

15、 0，由 0 的最大游程 度是 n-1 ，所以0 的 n-1游程出 在一個(gè)周期即從 x到 x的最后 n-1bit必要性：如果 0 的 n-1游程出 在最后n-1bit，我 考察 p( x)rr-1r，其中 ( x)( a1+a2x+a x) ( x) ( x -1) 足 A( x) p( x) ( x) ，由于 p( x) 次數(shù) n，而根據(jù) 0 的 n-1游程出 在最后n-1bit知 ( a1+a2x+ar xr -1 )的最大次數(shù)是r -1-( n-1) ，所以方程左 p( x) (a +a x+axr -1n+ r -1-( n-1)=r，所以方程右 ( x)=1 ，即) 的次數(shù) 12rA( x)=1/ p( x) #6.2已知一序列的前 10 比特為 0010001111(1) 試用 B-M算法求出產(chǎn)生該序列極小多項(xiàng)式和線性復(fù)雜度(2) 給出產(chǎn)生該序列的 LFSR的遞推式、結(jié)構(gòu)圖和周期(3) 破譯該序列最少需要知道多少連續(xù)的密鑰流比特解： (1)產(chǎn)生該序列的極小多項(xiàng)式和線性復(fù)雜度分別是x x4和 41+ +n10dnf nx