第 二 章 作 业 参 考 答 案1. 3级线性反应移位寄存器在C3=l时可有4种线性反应函数，设其初始状态为(0,〃2以3尸(11)，求各线 性反应函数的输出序列及周期解：此时线性反应函数可表示为| ,〃2,〃3)=0 ?C2〃2?C I1=0,2 = 0 时，火〃1,〃2,〃3)=〃1?3 = 0，输出序列为101101...,周期=3当 Cl=0, C2= 1 时，加10,〃3)=〃1?，2〃2?口〃3 =防？42,・・・，周期=7当= 1 ,2 = 0 时，,/(3，・・・，周期=7当 Cl = 1,2 = 1 时,有输出序列为1010...,周期=22.设n级线性反应移位寄存器的特征多项式为p(x),初始状态为(mm,…,斯」,斯)二(00.・.01)，证明输出序 列的周期等于p(x)的阶证：设p(x)的阶为p,由定理2-3,由r|p,所以〃?p设&x)为序列｛㈤的生成函数，并设序列｛㈤的周期为r,那么显然有4幻〃(外=心)又 A(X)= Q1 +〃21+ .・・+/(］+42X+...)+*)2(a 1 +〃2X+... +川广1)+ …=0 +zx+... +©"" /(I -V) = 〃 1+Q2X+... +©/" /(xr-1)于是 A(x)=(a। +6Z2X+...^arx!'1)/(xr-1)=ax)/p(x)又(〃i,42,・・・，瓯i，%)=(00・・.01)所以.(%)3M"+…+。
旷i)= /(x)(xr-1) 即 p(x)/i(a〃+... +♦¥〃)=取)(r-1)由于?"不能整除X--1,所以必有?而为x)的次数小于n,所以必有心)=f1所以必有p(x)|(『-l),由p(x)的阶的定义知，阶p?尸综上所述：p=r#3.设11 = 4,大见〃2M3,〃4)二〃1?4?1?〃2的，初始状态为(1血的，4)= (1』,』)，求此非线性反应移位寄存器的 输出序列及周期解：由反应函数和初始状态得状态输出表为(“4 〃32101110111(“4 〃321011101110) 输出111100(31 10 11 01)1 11 11 1输出111 (回到初始状态)所以此反应序列输出为：11011…周期为5.设密钥流是由m=2s级LFSR产生，其前m+2个比特是(01广1,即s+1个01问第m+3个比特有无 可能是1,为什么？ 解：不能是1可通过状态考察的方法证明以上结论首先m级LFSR的状态是一个m维的向量，那么前m个比特构成一个状态So,可表示为(01)5,第m+1个比特是0,所以So的下一个状态是S】=(10)s,第m+2个比特是1,所以Si的下一个状态是S2=(OD' = So，回到状态So, 所以下一个状态应是S3=Si = (10y,也即第m+3个比特应该为0。
4 .设密钥流是由〃级LFSR产生，其周期为2〃一1, i是任一正整数，在密钥流中考虑以下比特对(Si, S/+1), (S/+1, Si+2),…，(Sj+2n-3, si+2n-2), 6+2n-2, Sj+2n-1),问有多少形如(+a+i)=(Li)的比特对？证明你的结论答：共有*2)证明：证明方法一：由于产生的密钥流周期为2〃一1,且LFSR的级数为n,所以是m序列以上比特对刚好是1个周期上，两两相邻的所有比特对，其中等于(1,1)的比特对包含在所有大于等于2的1游程中由m序列的性质，所有长为i的1游程(1? i ?n-2)有2〃打/2个，没有长为n—1的1游程, 有1个长为n的1游程长为i (i>l)的1游程可以产生i-1个(1』)比特对，所以共有(1』)比特对的数目 N= 2"-2X(2-1)+2-32x(3-l) + ...+ 2〃年2X(i — 1) + …+ 2ML.2x(n〃—2—2—l） + n—1 = £2〃-"2（1）+n—1=2什2） i=2证明方法2:考察形如11*…*的状态的数目,共有方迎)个6设该三级线性反应移位寄存器的反应函数为10屹,阕3取其前6比特可建立如下方程（04。
5a6）=（C3,C2,C1）%a2a3a2 %4a4 a5a]〃2%-1-i 1 r-1-i 1 r% %=（0 1 0）1 1 0=（0 1 0）1 0 1=（10 1）a4 a5__1 0 11 1 0_即（2©） = （6）a2〃3所以J(41?的，即流密码的递推关系式为初3=0+2?07 .假设GF(2)上的二元加法流密码的密钥生成器是n级线性反应移位寄存器，产生的密钥是m序列2.5 节，敌手假设知道一段长为2n的明密文对就可破译密钥流生成器如果敌手仅知道长为2n-2的明密 文对，问如何破译密钥流生成器解：破译n—LFSR所产生的m序列，需要2n个连续比特，现在仅有2n—2个连续的密钥比特(由长为2n —2的明密文对逐位异或得到)，因此需要猜想后两个比特这有00, 01, 10, 11四种情况，对这些情况 按下式逐一试破译% a2 …an、(Q〃+1Q〃+2・.Q2〃) =・・C1) % 3 … a”+1 —(CnC/7-1 ..Cl) X*4〃+1…a2n-\ >首先验证矩阵X的可逆性，如果不可逆那么可直接排除此情况其次对于可逆的情况，求解出然后验证多项式p(x)=l+cix+…+C/V是否是本原多项式, 如果是，那么是一解。
结果可能会多余1个8 .设J-K触发器中｛四｝和｛勿｝分别为3级和4级m序列，且｛《〃｝・・・｛6｝…求输出序列｛以｝及周期解：由于gcd(3, 4)=1且〃()+加=1所以序列｛以｝的周期为(23-1)(2勺)=105又由J-K触发器序列的递推式以=(ak+bk+1))以」+以，令ci=0可得输出序列为：｛以｝….设基本钟控序列产生器中｛以｝和｛勿｝分别为2级和3级m序列，且｛或｝ = 101101.・.也｝・・・求输出序列｛以｝及周期解:序列｛以｝的周期“1=22—1=3,序列｛仄｝的周期“2=23—1=7, Wi=4o+〃i+〃2=2而 gcd(wi,/?2)=lo 所以序列｛以｝的周期 P=P1P2=3X7=21记LFSR2(产生序列也｝)的状态向量为双，那么见=(100),在LFSR1(产生序列｛四｝)的控制下，状态转移为:{ak}(100)X001),(001)X011),(110),(110),(101),(Oil),(Oil),(110),(100),( 100),(001),(011),(011),(110){ak] 101101101(101),(101),(011),(110),(110),(100),(001), (001),(011)110111000• • • 复习题4.3.一有限状态自动机的状态转移图如下图，那么当初始状态为si,且输入字符序列为4(%2⑴4(以3⑴小(%⑴时，输出的状态序列和输出符号序列分别是什么？解：根据有限状态机转移图有(1)输出的状态序列 S1, 52,S2,S3,S2, Si, S2(2)输出的符号序列 4⑵4⑵4⑵4⑵4⑵4⑵5.3 n次不可约多项式p(x)的周期为一,试证A(x)=l/p(x)的充要条件是0的n—1游程出现在一 个周期的最后n-lbit证：由于p(x)是不可约多项式，那么由p(x)生成的非。
序列的周期等于p(x)的周期一由 A (%) = 41 +〃2%+ …+x-(a I+42X+ …+arXr~X )+(f)2ml +〃2%+ .・・ +[次")+ …=I +〃2X+... +©"" /(I -V) = 〃 I+Q2X+..." /(xr-1)于是 A{x}-{a। +(72%+... +arxr'1 )/(xr-1) = l/p(x)所以 p(x)(0 +〃2X+... +0/")= +1由于P(x)的次数为n,所以(0+〃2%+..・+初川)的最大次数为r-1-n,也就是说从x"用开始系数都为0即从九六〃到下「共n-1个系数都为0,由0的最大游程长度是n-l,所以0的n-1游程出现在一个周期的 最后n-lbit必要性：如果的n-1游程出现在最后n-lbit,我们考察p(x) (〃1+怎什…+©步i)=*x)(三-1),其中心)满足A(x)p(x) =⑥)，由于p(x)次数为n,而根据0的n-1游程出现在最后n-lbit知⑷+3十一+初%的最大次数是 --1-(小1),所以方程左边p(x) (1+3+.・・+初E)的次数为〃+六1-5-1)』,所以方程右边心)=1,即A(x)=l/P(x) #6.2一序列的前10比特为(1)试用B-M算法求出产生该序列极小多项式和线性复杂度(2)给出产生该序列的LFSR的递推式、结构图和周期(3)破译该序列最少需要知道多少连续的密钥流比特解：(1)产生该序列的极小多项式和线性复杂度分别是l+x+f和4na10dnfn(X)Inmfm(X)000101001021110213001-如2+1 = 1+/2+1=3400l+x335011+x33611(l+x3)+x5-2(l)=l361711l+/2(l)=l+x44810l+x4+x7-6(l)=l +x+x449101 +x+x44101 +x+x44⑵结构图、递推式和周期递推式以+4=四+3?为周期：由于是本原多项式，所以周期为24-1 = 15(3)需要知道至少2x4=8个连续的密钥流比特。