现代密码学第五讲(一)：流密码

基于移位寄存器的流密码算法

定义设n级LFSR的输出序列{ai}满足递推关系

an?k?cnan?k?1?cn?1an?k?2???c1ak(k?1).这种递推关系可用一个一元高次多项式

f(x)?cnx?cn?1xnn?1???c1x?1表示，称这个多项式为LFSR的特征多项式。

基于移位寄存器的流密码算法

nf(x)定义设是GF(2)上的多项式，使f(x)|(x?1)的最小的n称为f(x)的周期或者阶。

例：f(x)?x?x?x?x?1为GF(2)上多项式，

以它为特征多项式的LFSR 的输出序列周期。

432(x?1)?(x?x?x?x?1)(x?1)?f(x)(x?1)5432f(x)|x?1,nn?5所以f(x)的周期为5基于移位寄存器的流密码算法

解：对应的n级LFSR的反馈函数为

状态00011000110001100011000110001100 输出位10001100b4b3b2b110001100?f(b1,b2,b3,b4)输出序列的周期为5基于移位寄存器的流密码算法

n?n级LFSR输出的序列的最大周期是2为什么？?1?

?

LFSR的寄存器状态遍历2n?1个非零状态

初始状态为全零，则输出序列为0的循环

定义当LFSR的寄存器状态遍历2n?1个非零状

n态时，序列的周期达到最大2?1，这种序

列被称为m序列。