4.4 线性移位寄存器的一元多项式表示
设 n 级线性移位寄存器的输出序列满足递推 关系 an+k=c1an+k-1 c2an+k-2 … cnak (*) 对任何 k 1 成立。这种递推关系可用一个一 元高次多项式 P(x)=1+c1x+…＋cn-1xn-1＋cnxn 表示，称这个多项式为LFSR的联系多项式或 特征多项式。
初始状态由用户确定，当第i个移位时钟脉冲 到来时，每一级存储器ai都将其内容向下一级 ai-1传递，并根据寄存器此时的状态a1,a2,…,an 计算f(a1,a2,…,an)，作为下一时刻的an。反馈函 数f(a1,a2,…,an)是n元布尔函数，即n个变元 a1,a2,…,an可以独立地取0和1这两个可能的值， 函数中的运算有逻辑与、逻辑或、逻辑补等运 算，最后的函数值也为0或1。
图4-4 GF(2)上的n级线性反馈移位寄存器
输出序列{at}满足 an+t=cnat cn-1at+1 … c1an+t-1 其中t为非负正整数。 线性反馈移位寄存器因其实现简单、速度快、 有较为成熟的理论等优点而成为构造密钥流生 成器的最重要的部件之一。
例4.2 图4-5是一个5级线性反馈移位寄存器， 其初始状态为（a1,a2,a3,a4,a5）=(1,0,0,1,1)，可 求出输出序列为 1001101001000010101110110001111100110 … 周期为31。
即输出序列为101110111011…，周期为4。 如果移位寄存器的反馈函数f(a1,a2,…,an)是a1 ，a2，…，an的线性函数，则称之为线性反馈 移位寄存器LFSR（linear feedback shift register ）。此时f可写为 f(a1,a2,…,an)=cna1 cn-1a2 … c1an 其中常数ci=0或1 2加法。ci=0或1可 用开关的断开和闭合来实现，如图4-4所示。
由此可见, 序列密码的安全性主要依赖于密钥序列 k0k1…=A(k)，当k0k1…是离散无记忆的随机序列时, 则该系统就是一次一密密码, 它是不可破的. 但通常 A(k)是一个由k通过确定性算法产生的伪随机序列, 因 而此时, 该系统就不再是完全保密的. 设计序列密码的 关键是设计密钥序列A(k)，密钥序列A(k)的设计应考虑 如下几个因素: (1)系统的安全保密性; (2)密钥k易于分配、保管，更换简便； (3)产生密钥序列简单快速。 目前最为流行和实用的密钥流产生器，其驱动部分是 一个或多个线性反馈移位寄存器。
线性反馈移位寄存器输出序列的性质完全由 其反馈函数决定。n级线性反馈移位寄存器最 多有2n个不同的状态。若其初始状态为0，则 其状态恒为0。若其初始状态非0，则其后继状 态不会为0。因此n级线性反馈移位寄存器的状 态周期小于等于2n-1。其输出序列的周期与状 态周期相等，也小于等于2n-1。只要选择合适 的反馈函数便可使序列的周期达到最大值2n-1 ，周期达到最大值的序列称为m序列。
例4.1 图4-3 是一个3级反馈移位寄存器，其 初始状态为(a1,a2,a3)=(1,0,1)，求出输出序列。
图 4-3 一个3级反馈移位寄存器
一个3级反馈移位寄存器 的状态和输出
状态 （a1,a2,a3)

输出

10
1 0 1 1 1 0
常见的两种密钥流产生器
因为确定性算法产生的序列是周期的或准周 期的，为了使序列密码达到要求的安全保密性， 使得密钥经其扩展成的密钥流序列具有如下性 质：极大的周期、良好的统计特性、抗线性分 析、抗统计分析。 我们仅对实用中最感兴趣的二元情形即GF(2) 上的序列密码原理进行介绍，但其理论是可以 在任何有限域GF(q)中进行研究的。
4.1 引言
人们试图用序列密码方式仿效”一次一密” 密码. 从而促成了序列密码的研究和发展. 序列 密码是世界军事, 外交等领域应用的主流密码 体制. 在通常的序列密码中, 加解密用的密钥序 列是伪随机序列, 它的产生容易且有较成熟的 理论工具, 所以序列密码是当前通用的密码系 统. 序列密码的安全性主要依赖于密钥序列, 因而什么样的伪随机序列是安全可靠的密钥序 列, 以及如何实现这种序列就成了序列密码中 研究的一个主要方面.
设 n 级线性移位寄存器对应于递推关系 (*) ， 由于ai∈GF(2) (i=1,2,…,n)，所以共有2n组初始 状态，即有2n个递推序列，其中非恒为零的序 列 有 2 n-1 个 ， 记 2 n-1 个 非 零 序 列 的 全 体 为 G(p(x))。
图4-5 一个5级线性反馈移位寄存器
在线性反馈移位寄存器中总是假定c1,c2,…,cn 中至少有一个不为0，否则f(a1,a2,…,an)≡0，这 样的话，在n个脉冲后状态必然是00…0，且这 个状态必将一直持续下去。若只有一个系数不 为0，设仅有cj不为0，实际上是一种延迟装置。 一般对于n级线性反馈移位寄存器，总是假定 cn=1。
4.2 序列 密码的一般原理
序列密码的基本思想是利用一个短密钥k通 过一个算法来产生一个密钥流k=k0k1…，并使 用如下规则对明文串m=m0m1m2…加密： c=c0c1c2…=Ek0(m0)Ek1(m1)Ek2(m2)…。密钥流由 密钥流发生器A产生： k0k1…=A(k)，
二进制序列密码体制模型
2.2 线性反馈移位寄存器
移位寄存器是序列密码产生密钥流的一个主 要组成部分。GF(2)上一个n级反馈移位寄存器 由n个二元存储器与一个反馈函数f(a1,a2,…,an) 组成，如图4.2所示。
图4.2 GF(2)上的n级反馈移位寄存器
每一存储器称为移位寄存器的一级，在任一 时刻，这些级的内容构成该反馈移位寄存器的 状态，每一状态对应于GF(2)上的一个n维向量， 共有2n种可能的状态。每一时刻的状态可用n 长序列 a1,a2,…,an 或n维向量 (a1,a2,…,an) 表示，其中ai是第i级存储器的内容。