移位寄存器

移位寄存器：有n个寄存器（称为n-级移位寄存器）每个寄存器中能存放1位二进制数

所有寄存器种的数可以一起向右/左移动一位，这叫进动一拍。

反馈移位寄存器（feedback shift register,FSR）：由n位的寄存器和反馈函数（feedback function）组成，n位的寄存器中的初始值称为移位寄存器的初态。

工作原理：移位寄存器中所有位的值右移移位，最右边的一个寄存器移出的值是输出位，最左边一个寄存器的值由反馈函数的输出值填充，此过程称为进动一拍。反馈函数f是n个变元(b₁,b₂,…,b_n)的布尔函数。移位寄存器根据需要，不断进动m拍，就会输出m位的序列a₁,a₂,…,a_m。 这个a₁-a_m(m可以远远大于n)就是伪随机序列。

线性反馈移位寄存器LFSR（linear feedback shift register）的反馈函数为线性函数。

作为密钥流的序列{a_i}的周期一定要大，因为密钥流的周期太小的话会不安全，攻击者可能很容易得到整个密钥流。

n级LFSR输出的序列的周期r不依赖于寄存器的初始值，而是依赖于特征多项式p(x)

设n级LFSR的输出序列{a_i}满足递推关系  a_n+k=c_na_n+k-1⊕c_n-1a_n+k-2⊕…⊕c₁a_k(k>=1) 这种递推关系可用一个一元高次多项式f(x)=c_nxⁿ+c_n-1x^n-1+…+c₁x+1表示，这个多项式就是LFSR的特征多项式。

设f(x)是GF(2)上的多项式，是f(x)|(xⁿ-1)的最小的n称为f(x)的周期或者阶。

例如f(x)=x⁴+x³+x²+x+1为GF(2)上多项式，以它为特征多项式的LFSR的输出序列周期。

(x⁵-1)=(x⁴+x³+x²+x+1)(x-1)=f(x)(x-1)

f(x)|xⁿ-1,n<5    周期为5

设初始状态：0001

状态  输出位

0001  1

1000  0

…

n级LFSR输出的序列的最大周期是2ⁿ-1

LFSR的寄存器状态遍历2ⁿ-1个非零状态

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

当LFSR的寄存器状态遍历2ⁿ-1个非零状态时，序列的周期达到最大2ⁿ-1，这种序列被称为m序列。

若n次不可约多项式f(x)的阶为2ⁿ-1，则称f(x)为n次本原多项式。

{a_i}是周期为2ⁿ-1的m-序列的充要条件是其特征多项式f(x)为n阶本原多项式。

例：一个3-级的反馈移位寄存器，反馈函数f(x)=b₃⊕b₁，初态为100

则f(x)=x³+x+1

(x⁷-1)=(x⁴+x²+x+1)(x³+x+1)=(x⁴+x²+x+1)|f(x)

f(x)|xⁿ-1        n<7          所以f(x)的周期为7

状态  输出位

100  0

110  0

111  1

…

输出序列的周期是7，所提他是m-序列。

流密码的攻击

攻击目的：获悉整个密钥流{k_i}

攻击手段： 唯密文  已知明文    选择明/密文  自适应选择明/密文

1)若LFSR的反馈函数已知,破译者已知连续n位明密文对{m₁,m₂…m_n}和{c₁,c₂…,c_n},则可以推导出n比特密钥流k_i=m_i⊕c_i,{k₁,k₂,…k_n}继而由反馈函数得到整个密钥流{k_i}

2)已知明文攻击下,假设破译者已知了2n位明密文对M={m₁,m₂…m_2n},C={c₁,c₂…c_2n}则可确定段2n位长的密钥序列K={k₁,k₂,…,k_2n},由此可以完全确定n级反馈多项式的系数。

为了提高密钥流序列的线性复杂度，需要使用非线性函数。将密钥流生成器分成 驱动部分 和 非线性组合部分。

驱动部分可由m-序列或其他长周期的LFR序列组成,用于控制密钥流生成器的状态序列,并为非线性组合部分提供伪随机性质良好的序列:非线性组合部分利用驱动部分生成的状态序列生成满足要求的密码特性好的密钥流序列。

要求：符合香农的“扩散”和“混淆”两条原则。驱动部分用LFSR将密钥k扩散成周期很大的状态序列。而状态序列与密钥k间的关系经非线性组合混淆后被隐蔽。

滤波生成器（前馈生成器）

由LFSR和滤波前馈函数组成。LFSR可以多个，它们的输出序列共同作为滤波函数的输入

滤波函数要求具有很好的非线性性质，以增强生成器的抗攻击能力。

例如：Geffe序列发生器

两个LFSR是复合器的输入，第三个LFSR控制复合器的输出。

钟控生成器

由一个或几个FSR输出序列，控制一个FSR的时钟。