第2章流密码

第二章流密码1.3级线性反馈移位寄存器在31c时可有4种线性反馈函数，设其初始状态为123,,1,0,1aaa，求各线性反馈函数的输出序列及周期。解：设3级线性反馈特征多项式为231231pxcxcxcx，若31c则12,cc共有224种可能，对应初态123,,1,0,1aaa。4种线性反馈函数分别记为：311pxx输出序列101101101a，周期3p321pxxx是不可约多项式，输出序列1010011101a，周期7p是m序列2331pxxx是不可约多项式，输出序列1011100101a，周期7p是m序列2341pxxxx输出序列101010a，周期2p2．设n级线性反馈移位寄存器的特征多项式为px，初始状态为121,,,,0001nnaaaa，证明输出序列的周期等于px的阶。解：px的阶定义为|1ppxx的最小的p。因为初始状态不为零，设r为序列的最小周期。又因为|1ppxx，所以必存在qx，使得1pxpxqx。又因为pxAxx,则pxqxAxxqx1pxAxxqx而qx的次数为pn，x的次数不超过1n，1pxAx的次数不超过11pnnp。所以i，i是正整数，都有ipiaa。设pkrt，0ipikrtitiaaaat，|rp。即周期为px的阶，若px是n次不可约多项式，则序列的最小周期等于px的阶。生成函数xAxpx，0pxAxx，x的次数不超过1n。111211riririxaaxaxAxaxxpx1121rrrpxaaxaxxxpx不可约，所以gcd,1pxx，|1rpxx。又因为mr，所以rm。3.设4n，12341423,,,1faaaaaaaa，初始状态为1234,,,1,1,0,1aaaa，求此非线性反馈移位寄存器的输出序列及周期。解：由12341423,,,1faaaaaaaa，初态为1234,,,1,1,0,1aaaa。线性递归可得：511101a611101a701111a811110a910111a1011101a可以得到输出序列为1101111011，周期为5p。4.已知流密码的密文串1010110110和相应的明文串0100010001，而且还已知密钥流是使用3级线性反馈移位寄存器产生的，试破译该密码系统。解：由已知可得相应的密钥流序列为1110100111，又因为是3级线性反馈移位寄存器，可得以下方程：123456321234345aaaaaacccaaaaaa将值代入得:321111010110101ccc1111110101AA,1111101101A1111111110101101110321111010101101110ccc由此可得密钥流的递推关系为：33122iiiiiacacaaa。5.设J-K触发器中ka和kb分别为3级和4级m序列，且11101001110100ka，001011011011000001011011011000kb求输出序列kc及周期。解：由J-K触发器可知11kkkkkcabcakkkacb11,0,1kkcc此时ka和kb分别为3级和4级m-序列，3,41则kc的周期为342121715105。由于周期太大这里就不一一列出了。11001001010100kc。6.设基本钟控序列生成器中ka和kb分别为2级和3级m序列，且101101ka，10011011001101kb求输出序列kc及周期。解：令基本钟控序列生成器中ka的周期为1p，kb的周期为2p，则输出序列kc的周期为1212gcd,pppwp，11102piiwa，21213p，32217p3721gcd(2,7)p。记LFSR2产生kb，其状态向量为k，可得k的变化情况如下：0112334556001223445660112输出序列100011100111000111011kc