第7讲 序列密码体制

1、应应 用用 密密 码码 学学西安电子科技大学出版社二00九年十二月 序列密码的概念序列密码的概念 线性反馈移位寄存器线性反馈移位寄存器序列和周期序列和周期 非线性序列简介非线性序列简介 常用序列密码常用序列密码起源起源 -一次一密一次一密 无条件安全：无条件安全：在理论上是不可破译的在理论上是不可破译的 但：但：要求密钥与明文具有相同长度、且不可重复使用，增加要求密钥与明文具有相同长度、且不可重复使用，增加了密钥分配与管理的困难了密钥分配与管理的困难 对策：对策：用一个较小的密钥来用一个较小的密钥来伪随机伪随机地生成密钥流。地生成密钥流。人们试图以序列密码方式仿效人们试图以序列密码方式仿效“一

2、次一密一次一密”密码密码序列密码的理论已经比较成熟，而且具有工程实现容易序列密码的理论已经比较成熟，而且具有工程实现容易、效率高等特点、效率高等特点采用一个短的种子密钥来控制某种算法产生出长的密钥采用一个短的种子密钥来控制某种算法产生出长的密钥序列，供加、解密使用，而短的种子密钥的存储、分配都较容序列，供加、解密使用，而短的种子密钥的存储、分配都较容易易 分组密码使用的是一个不随时间变化的固定变换，具有扩散性分组密码使用的是一个不随时间变化的固定变换，具有扩散性好、插入敏感等优点；其缺点是：加密处理速度慢。好、插入敏感等优点；其缺点是：加密处理速度慢。序列密码序列密码vs.分组密码分组密码 分

3、组密码以一定大小的分组作为每次处理的基本单元，而序列分组密码以一定大小的分组作为每次处理的基本单元，而序列密码则以一个元素（如一个字母或一个比特）作为基本的处理单元。密码则以一个元素（如一个字母或一个比特）作为基本的处理单元。 序列密码使用一个随时间变化的加密变换，具有转换速度快、序列密码使用一个随时间变化的加密变换，具有转换速度快、低错误传播的优点，硬件实现电路更简单；其缺点是：低扩散（意低错误传播的优点，硬件实现电路更简单；其缺点是：低扩散（意味着混乱不够）、插入及修改的不敏感性。味着混乱不够）、插入及修改的不敏感性。4.1序列密码的概念序列密码的概念 序列密码算法将明文逐位转换成密文，如

4、下图所示。序列密码算法将明文逐位转换成密文，如下图所示。密钥流发生器（也称为滚动密钥发生器）输出一系列比特流：密钥流发生器（也称为滚动密钥发生器）输出一系列比特流：K1，K2，K3，Ki。密钥流（也称为滚动密钥）跟明文比特流（密钥流（也称为滚动密钥）跟明文比特流（m1，m2，m3，mi），进行异或运算产生密文比特流。，进行异或运算产生密文比特流。加密：加密：C i =mi K i 在解密端，密文流与完全相同的密钥流异或运算恢复出明文流。在解密端，密文流与完全相同的密钥流异或运算恢复出明文流。解密：解密：m i =C i K i 显然显然，mi K i K i =m i 事实上，事实上，序列密码

5、算法其安全性依赖于简单的异或运算和序列密码算法其安全性依赖于简单的异或运算和密钥密钥序列序列。密钥流发生器生成的看似随机的密钥流实际上是确定的，在密钥流发生器生成的看似随机的密钥流实际上是确定的，在解密的时候能很好的将其再现。解密的时候能很好的将其再现。密钥流发生器输出的密钥越接近随密钥流发生器输出的密钥越接近随机，对密码分析者来说就越困难。机，对密码分析者来说就越困难。 如果密钥流发生器每次都生成同样的密钥流的话，对攻击来说，如果密钥流发生器每次都生成同样的密钥流的话，对攻击来说，破译该算法就容易了。破译该算法就容易了。 假的假的AliceAlice得到一份密文和相应的明文，她就可以将两者异

6、或得到一份密文和相应的明文，她就可以将两者异或恢复出密钥流。恢复出密钥流。或者，如果她有两个用同一个密钥流加密的密文，或者，如果她有两个用同一个密钥流加密的密文，她就可以让两者异或得到两个明文互相异或而成的消息。她就可以让两者异或得到两个明文互相异或而成的消息。这是很容这是很容易破译的，接着她就可以用明文跟密文异或得出密钥流。易破译的，接着她就可以用明文跟密文异或得出密钥流。 现在，无论她再拦截到什么密文消息，她都可以用她所拥有的现在，无论她再拦截到什么密文消息，她都可以用她所拥有的密钥流进行解密。密钥流进行解密。另外，她还可以解密，并阅读以前截获到的消息另外，她还可以解密，并阅读以前截获到的

7、消息。一旦一旦AliceAlice得到一明文得到一明文/ /密文对，她就可以读懂任何东西了。密文对，她就可以读懂任何东西了。 这就是为什么所有序列密码需要这就是为什么所有序列密码需要随机密钥随机密钥的原因。的原因。密钥流发生密钥流发生器的输出是密钥的函数。器的输出是密钥的函数。 这样，这样，AliceAlice有一个明文有一个明文/ /密文对，但她只能读到用特定密钥加密文对，但她只能读到用特定密钥加密的消息。密的消息。 更换密钥，攻击者就不得不重新分析。更换密钥，攻击者就不得不重新分析。 流密码强度完全依赖于密钥序列的随机性随机性(Randomness)和不不可预测性可预测性(Unpredic

8、tability)。核心问题是密钥流生成器的设计核心问题是密钥流生成器的设计。保持收发两端密钥流的精确同步是实现可靠解密的关键技术保持收发两端密钥流的精确同步是实现可靠解密的关键技术。 1. 1.自同步序列密码自同步序列密码 自同步序列密码就是密钥流的每一位是前面固定数量密文位的自同步序列密码就是密钥流的每一位是前面固定数量密文位的函数，下图和下页图描述了其工作原理。函数，下图和下页图描述了其工作原理。其中，内部状态是前面其中，内部状态是前面n比特密文的函数。该算法的密码复杂性在于输出函数，它收到内部比特密文的函数。该算法的密码复杂性在于输出函数，它收到内部状态后生成密钥序列位。状态后生成密钥

9、序列位。自同步序列密码的特点自同步序列密码的特点- 自同步自同步- 自同步的实现依赖于密文被删除或插入，因为解密只取自同步的实现依赖于密文被删除或插入，因为解密只取决于先前固定数量的密文字符。自同步序列密码在同步丢失后能决于先前固定数量的密文字符。自同步序列密码在同步丢失后能够自动重新建立正确的解密，只有固定数量的明文字符不能被恢够自动重新建立正确的解密，只有固定数量的明文字符不能被恢复。复。- 有限的错误传播有限的错误传播- 因为自同步序列密码的状态取决于因为自同步序列密码的状态取决于n个已有的密文字符，个已有的密文字符，如果一个密文字符在传输过程中被修改，则解密时最多影响到后如果一个密文字

10、符在传输过程中被修改，则解密时最多影响到后续续n个字符的解密恢复，会发生有限的错误传播。个字符的解密恢复，会发生有限的错误传播。 -（由于具有自同步能力，（由于具有自同步能力，)强化了其抗统计分析的能力强化了其抗统计分析的能力2同步序列密码同步序列密码同步流密码同步流密码SSC(SynchronousStreamCipher)： 内部状态内部状态 i与明文消息无关，密钥流将独立于明文。因此，与明文消息无关，密钥流将独立于明文。因此，对对于明文而言，这类加密变换是无记忆的，但它是时变的；于明文而言，这类加密变换是无记忆的，但它是时变的；只有保持只有保持两端精确同步才能正常工作两端精确同步才能正常

11、工作；无差错传播；无差错传播( (Error Propagation)Error Propagation)。同步序列密码的特点同步序列密码的特点- - 在保密通信过程中，通信的双方必须保持精确的同步在保密通信过程中，通信的双方必须保持精确的同步 对于同步序列密码，只要通信双方的密钥序列产生器具有对于同步序列密码，只要通信双方的密钥序列产生器具有相相 同的种子密钥同的种子密钥和和相同的初始状态相同的初始状态，就能产生相同的密钥序列。，就能产生相同的密钥序列。- - 对失步的敏感性对失步的敏感性 - - 收方的解密将一直错误，直到重新同步为止收方的解密将一直错误，直到重新同步为止 - - 容易检测

12、插入、删除、重播等主动攻击容易检测插入、删除、重播等主动攻击-无错误传播无错误传播 当通信中某些密文字符产生了错误（如当通信中某些密文字符产生了错误（如0 0变成变成1 1，或，或1 1变成变成 0 0），只影响相应字符的解密，不影响其它字符。），只影响相应字符的解密，不影响其它字符。-对主动攻击时异常敏感而有利于检测。对主动攻击时异常敏感而有利于检测。 密码设计者的密码设计者的最大愿望最大愿望是设计出一个滚动密钥生成器，使得是设计出一个滚动密钥生成器，使得密钥经其扩展成的密钥流序列具有如下性质：密钥经其扩展成的密钥流序列具有如下性质：- - 极大的周期；极大的周期；- - 良好的统计特性；良

13、好的统计特性；- - 抗线性分析；抗线性分析；- - 抗统计分析。抗统计分析。常见的密钥序列产生器常见的密钥序列产生器目前，最为流行和实用的密钥流产生器大多基于目前，最为流行和实用的密钥流产生器大多基于线性反馈移位线性反馈移位寄存器。寄存器。如下图所示，其驱动部分是一个或多个如下图所示，其驱动部分是一个或多个线性反馈移位寄存线性反馈移位寄存器器。LFSRFLFSR1LFSR2LFSRnF FizFiz一般地，我们把n n元布尔函数元布尔函数定义为如下映射：记为 ，其中22:FFfn)(xf1, 0,)(,),(22221FFxfFxxxxnn 布尔函数是研究数字逻辑电路的重要数学工具布尔函数是

14、研究数字逻辑电路的重要数学工具，在序列密码、，在序列密码、分组密码和公钥密码中，布尔函数都有重要的应用。特别在序列分组密码和公钥密码中，布尔函数都有重要的应用。特别在序列密码中，布尔函数是重要的数学工具之一。密码中，布尔函数是重要的数学工具之一。 小项表示实际上是布尔代数表达方式，即逻辑表达方式，此方法常用于布尔函数的设计实现。2 2、小项表示、小项表示上例的小项表示为2121)(xxxxxf3 3、多项式表示、多项式表示因为 ，将小项表示中的逻辑非的形式换掉即得多项式表示。xx121)(xxxf4.2线性反馈移位寄存器线性反馈移位寄存器- - 定义：定义：反馈移存器的反馈逻辑电路可用一布尔函

15、数反馈移存器的反馈逻辑电路可用一布尔函数f(a1,a2,an)来来表示，表示，若对应的布尔函数是线性函数，则称该反馈移存器为线性反若对应的布尔函数是线性函数，则称该反馈移存器为线性反馈移存器馈移存器LFSR(linearfeedbackshiftregister)，否则称为，否则称为非线性反非线性反馈移存器馈移存器。ajaj-2aj-3aj-1图图1 线性反馈移位寄存器线性反馈移位寄存器ajaj-2aj-3图图2 非线性反馈移位寄存器非线性反馈移位寄存器 此时此时LFSRLFSR函数函数可写为：可写为：f(a1,a2,an)=cna1 cn-1a2 c1an 上图中，常数上图中，常数c ci

16、i=0=0或或1 1， 是模是模2 2加法。加法。c ci i=0=0或或1 1可用开关的断开可用开关的断开和闭合来实现，这样的线性函数共有和闭合来实现，这样的线性函数共有2 2n n个。个。 输出序列输出序列 at 满足：满足：a1+t=cnat +1 cn-1at+2 c1an+t 其中，其中，t为非负正整数。为非负正整数。 如下图所示如下图所示，是一个，是一个LFSR:LFSR: （1 1）线性反馈移位寄存器因其实现简单、速度快、有较为成熟的理论等优）线性反馈移位寄存器因其实现简单、速度快、有较为成熟的理论等优点而成为构造密钥流生成器的最重要的部件之一，也点而成为构造密钥流生成器的最重要

17、的部件之一，也非常适合用硬件实现；非常适合用硬件实现； （2 2）可以产生大周期序列；）可以产生大周期序列； （3 3）可以产生具有良好统计性质的序列；）可以产生具有良好统计性质的序列； （4 4）易于利用代数方法对其进行分析。）易于利用代数方法对其进行分析。n级线性移存级线性移存器的线性递推器的线性递推式表示式表示假设在假设在j j时刻其内部状态为：时刻其内部状态为：),(21rjjjaaa在在j+1j+1时刻其内部状态变为：时刻其内部状态变为：),(11rjjjaaa其中：其中：),(21rjjjjaaafa此时的输出为此时的输出为j j时刻的最高级：时刻的最高级：rjan n级反馈移位寄

18、存器级反馈移位寄存器 每一存储器称为移位寄存器的一级，在任一时刻，这些级的内容构每一存储器称为移位寄存器的一级，在任一时刻，这些级的内容构成该反馈移位寄存器的状态，成该反馈移位寄存器的状态，每一状态对应于每一状态对应于GF(2)GF(2)上的一个上的一个n n维向量，维向量，共有共有2 2n n种可能的状态。种可能的状态。 移位寄存器是流密码产移位寄存器是流密码产生密钥流的一个主要组成部生密钥流的一个主要组成部分。分。GF(2)GF(2)上一个上一个n n级反馈移级反馈移位寄存器由位寄存器由n n个二元存储器与个二元存储器与一个反馈函数一个反馈函数f(af(a1 1,a,a2 2,a,an n

19、) )组成组成，如右图所示。，如右图所示。 ajaj-2aj-1第第7 7时刻时刻 0 0 10 0 1第第0 0时刻时刻 0 0 10 0 1第第1 1时刻时刻 1 0 01 0 0第第2 2时刻时刻 1 1 01 1 0第第3 3时刻时刻 1 1 11 1 1第第4 4时刻时刻 0 1 10 1 1第第5 5时刻时刻 1 0 11 0 1第第6 6时刻时刻 0 1 00 1 0产生序列为：产生序列为：1001110110011101每一时刻的状态可用每一时刻的状态可用n长序列长序列“a1,a2,an ”n维向量维向量“(a1,a2,an)”来表示，来表示，其中其中ai是第是第i级存储器的内

20、容级存储器的内容。初始状态由用户确定，当第初始状态由用户确定，当第i个移位时钟脉冲到来时，个移位时钟脉冲到来时，每一级存每一级存储器储器ai都将其内容向下一级都将其内容向下一级ai-1传递，并计算传递，并计算f(a1,a2,an)作为下一时作为下一时刻的刻的an。反馈函数反馈函数f(a1,a2,an)是是n元布尔函数，元布尔函数，即即n个变元个变元a1,a2,an可可以独立地取以独立地取0和和1两个可能的值两个可能的值，函数中的运算有逻辑与、逻辑或、，函数中的运算有逻辑与、逻辑或、逻辑补等运算，最后的函数值也为逻辑补等运算，最后的函数值也为0或或1。一个一个r r级线性移存器的线性递推式表示为

21、：级线性移存器的线性递推式表示为：)(2211rnacacacarnrnnnan-1an-2an-3an-4an)4(432naaaannnn一个一个r r级线性移存器的反馈多项式表示为：级线性移存器的反馈多项式表示为：1)(111xcxcxcxfrrrrx1x2x3x41)(234xxxxf通常，用通常，用 来表示一个来表示一个LFSRLFSR。( ),f x l例：下图是一个例：下图是一个3级反馈移位寄存器，其初始状态为级反馈移位寄存器，其初始状态为(a1,a2,a3)=(1,0,1)，输出可由下表求出。输出可由下表求出。 即输出序列为即输出序列为101110111011，周期为，周期为4

22、。在初始状态下在初始状态下, ,即即0 0时刻时刻在第一个时钟到来时在第一个时钟到来时101f(a1,a2,a3)=a1a2 a3第1级第2级第3级S0=(1, 0, 1)输出10f(a1,a2,a3)=a1a2 a3第1级第2级第3级S1=(0, 1, 1)a1=1, a2=0, a3=11输出1a0则其输出序列和状态序列如下则其输出序列和状态序列如下:状态序列状态序列:(1,0,1)(0,1,1)(1,1,1)(1,1,0)(1,0,1)(0,1,1).输出序列输出序列:101110. 由上面的结果可以看出，这个反馈移位寄存器的状态序列和输由上面的结果可以看出，这个反馈移位寄存器的状态序列

23、和输出序列都是周期序列，其周期为出序列都是周期序列，其周期为4 4。11f(a1,a2,a3)=a1a2 a3第1级第2级第3级S2=(1, 1, 1)a1=1, a2=1, a3=01输出0a0例 设一个GF(2)上的4阶线性反馈移位寄存器如下图所示，其反馈函数为f(x1，x2，x3，x4)x1 x2，初始状态为S0（1，0，1，1） 容易验证该线性反馈移位寄存器的输出序列为：容易验证该线性反馈移位寄存器的输出序列为： 101111000100110101111000100110 这个线性移位寄存器序列是一个周期序列，周期为这个线性移位寄存器序列是一个周期序列，周期为1515。x4x3x2x

24、1输出序列（1）在线性反馈移位寄存器中总是假定）在线性反馈移位寄存器中总是假定c1,c2,cn中至少有一个中至少有一个不为不为0，否则，否则f(a1,a2,an)0，这样的话，在这样的话，在n个脉冲后状态必然是个脉冲后状态必然是000，且这个状态必将一直持续下去。，且这个状态必将一直持续下去。 （2 2）若只有一个系数不为）若只有一个系数不为0，设仅有，设仅有cj不为不为0，实际上是一种延，实际上是一种延迟装置。一般对于迟装置。一般对于n级线性反馈移位寄存器，总是假定级线性反馈移位寄存器，总是假定cn=1。（3）n级线性反馈移位寄存器的状态周期小于等于级线性反馈移位寄存器的状态周期小于等于2n

25、-1。输出序输出序列的周期与状态周期相等，也小于等于列的周期与状态周期相等，也小于等于2n-1。只要选择合适的反馈只要选择合适的反馈函数便可使序列的周期达到最大值函数便可使序列的周期达到最大值2n-1。4.3序列和周期序列和周期一般地，一个移存器序列表示为：一般地，一个移存器序列表示为：iaaaaa210 对于序列 ，若存在整数p使得对任意正整数k有 成立，称满足该式的最小正整数p为序列的周期序列的周期。iaaaaa210pkkaa 即：n级线性反馈移存器的最长周期: ，能达到最长周期的线性移存器序列称为m m序列序列。12 n- - 在密码学中，我们希望参与变换的序列周期越长越好，因此对线在

26、密码学中，我们希望参与变换的序列周期越长越好，因此对线性反馈移存器我们更感兴趣的是能达到最长周期的序列，即性反馈移存器我们更感兴趣的是能达到最长周期的序列，即m m序列。序列。 定义定义1 1：n n级线性反馈移位寄存器产生的序列级线性反馈移位寄存器产生的序列 a ai i 的周期达到最大的周期达到最大值值2 2n n-1-1时，称时，称 a ai i 为为n n级级m m序列序列。 （1 1）如何利用级数尽可能小的线性移位寄存器产生周期长、统）如何利用级数尽可能小的线性移位寄存器产生周期长、统计性能好的序列；计性能好的序列；（2）已知一个序列）已知一个序列ai，如何构造一个尽可能短的线性移位

27、寄存如何构造一个尽可能短的线性移位寄存器来产生它。器来产生它。- m- m序列的随机性：序列的随机性： 序列密码的安全性取决于密钥流的安全性，要求密钥流序列有序列密码的安全性取决于密钥流的安全性，要求密钥流序列有良好的随机性，以使密码分析者对它无法预测。良好的随机性，以使密码分析者对它无法预测。 也就是说，即使截也就是说，即使截获其中一段，也无法推测后面是什么。获其中一段，也无法推测后面是什么。 如果密钥流是周期的，要完如果密钥流是周期的，要完全做到随机性是困难的。全做到随机性是困难的。 严格地说，这样的序列不可能做到随机，严格地说，这样的序列不可能做到随机，只能要求截获比周期短的一段时不会泄

28、露更多信息，这样的序列称只能要求截获比周期短的一段时不会泄露更多信息，这样的序列称为伪随机序列。为伪随机序列。1.Golomb随机性假设随机性假设 为了度量周期序列的随机性，Golomb提出了下列三条标准三条标准：凡满足这三条随机性假设的序列，被凡满足这三条随机性假设的序列，被Golomb称为称为伪随机序列伪随机序列或或者者伪噪声序列伪噪声序列。（1）一个周期中）一个周期中0、1的个数相差不超过的个数相差不超过1个；个；k2/1（2）一个周期段中，长度为）一个周期段中，长度为k的游程占游程总数的的游程占游程总数的（这里（这里假定至少有两个长为假定至少有两个长为k的游程）；的游程）；（3）周期自

29、相关函数是二值函数。）周期自相关函数是二值函数。2、m序列统计特性序列统计特性性质性质1 ：r级m序列的一个周期中，1出现 个,0出现 个。12r121r1）m序列的序列的“0、1”信号的频次规律信号的频次规律2）m序列的游程分布规律序列的游程分布规律若干个信号连续出现的现象称若干个信号连续出现的现象称游程游程。对于序列。对于序列a，称，称a中形如中形如0110或或1001的段为一个的段为一个1游程或游程或0游程游程，游程中所含，游程中所含1或或0的个数的个数称为该游程的长度，如称为该游程的长度，如0110为一个长为为一个长为2的的1游程，游程，101为一个长为为一个长为1的的0游程。游程。性

30、质性质2：将将r级级m序列的一个周期段首尾相接，其游程总数为序列的一个周期段首尾相接，其游程总数为N=2r-1；其中；其中没有没有长度大于长度大于r的游程；有的游程；有1个长度为个长度为r的的1游程，没有游程，没有长度为长度为r的的0游程；没有长度为游程；没有长度为r-1的的1游程，有游程，有1个长度为个长度为r-1的的0游程；游程；有有个长度为个长度为的的1游程，有游程，有个长度为个长度为的的0游程。游程。)21 (rkkkr22)21 (rkkkr22再如再如00110111，其前两个数字是，其前两个数字是00，称长为，称长为2的的0游程；接着是游程；接着是11，是长为，是长为2的的1游程

31、；再下来是长为游程；再下来是长为1的的0游程和长为游程和长为3的的0游程。游程。 3） m序列的自相关特性序列的自相关特性)()()(10tipiiaatC 若若 是一个周期为是一个周期为p p的的0 0、1 1序列，定义序列，定义0,10,1上上的映射的映射 为：为： ，定义序列，定义序列 的自相关函的自相关函数为数为: :)(210aaaa 1) 1 (, 1)0()(210aaaa 120, 10, 12)()()(220rrtiiittaatCr性质性质3：若：若是一个是一个r级级m序列，那么序列，那么)(210aaaa Golomb随机性假设只是随机性的必要条件随机性假设只是随机性的

32、必要条件，一随机序列应该，一随机序列应该满足满足Golomb随机性假设。但随机性假设。但满足上述标准的周期序列并不一定能满足上述标准的周期序列并不一定能满足我们对密钥流序列在安全性上的要求，满足我们对密钥流序列在安全性上的要求，这种安全性是寓于随机这种安全性是寓于随机性之中的。性之中的。例如：例如：m序列完全满足序列完全满足Golomb随机性假设，但随机性假设，但m序列是高度可序列是高度可预测的。预测的。因为因为n级线性移位寄存器的输出序列级线性移位寄存器的输出序列ai满足递推关系满足递推关系:an+k=c1an+k-1 c2an+k-2 cnak，对任何对任何k1成立。成立。这种递推关系可用

33、一个一元高次多项式这种递推关系可用一个一元高次多项式p(x)=1+c1x+cn-1xn-1cnxn 表示，称这个多项式为表示，称这个多项式为。由于由于aiGF(2)(i =1,2,n)，所以共有所以共有2n组初始状态，即有组初始状态，即有2n个递推序列，个递推序列，其中非恒零的有其中非恒零的有2n-1个，记个，记2n-1个非零序列的全体为个非零序列的全体为G(p(x)。定义定义2：给定序列给定序列ai，幂级数幂级数，称为该序列的生，称为该序列的生成函数。成函数。定义定义3：设设p(x)是是GF(2)上的多项式，使上的多项式，使p(x)|(xp-1)的最小的最小p称为称为p(x)的周期或阶。的周

34、期或阶。（选讲）（选讲）定理定理2：若序列若序列ai的特征多项式的特征多项式p(x)定义在定义在GF(2)上，上，p是是p(x)的的周期，则周期，则ai的周期的周期r|p。 n级级LFSR输出序列的周期输出序列的周期r不依赖于初始条件，而依赖于特征多不依赖于初始条件，而依赖于特征多项式项式p(x)。实际上，我们感兴趣的是实际上，我们感兴趣的是LFSR遍历遍历2n-1个非零状态，这时序列个非零状态，这时序列的周期达到最大的周期达到最大2n-1，这种序列就是这种序列就是。特征多项式满足什么条件时，特征多项式满足什么条件时，LFSR的输出序列为的输出序列为m序列。序列。定义定义4：仅能被非零常数或者

35、本身的常数倍除尽，不能被其他多仅能被非零常数或者本身的常数倍除尽，不能被其他多项式整除的多项式称为不可约多项式。项式整除的多项式称为不可约多项式。定理定理3：n级级LFSR产生的序列有最大周期产生的序列有最大周期2n-1的必要条件是其特的必要条件是其特征多项式为不可约多项式。征多项式为不可约多项式。但但该定理的逆命题不成立该定理的逆命题不成立，即，即LFSR产生的特征多项式为不可产生的特征多项式为不可约多项式，但其输出序列不一定是约多项式，但其输出序列不一定是m序列。序列。例例3：设设f(x)=x4+x3+x2+x+1是是GF(2)上的不可约多项式，但是它上的不可约多项式，但是它的输出序列是的

36、输出序列是000110001100011，周期是，周期是5，不是，不是m序列。序列。解：解：f(x)的不可约性由多项式的不可约性由多项式x，x+1， x2+x+1不能整除不能整除f(x)而而得。对于得。对于k5，输出序列用输出序列用ak=ak-1 a k-2 a k-3 ak4检验即可。检验即可。定义定义5：若若n次不可约多项式次不可约多项式p(x)的阶为的阶为2n-1，称其为称其为n次本原多次本原多项式。项式。（选讲）（选讲）定理定理4：ai为为n级级m序列的充要条件是其特征多项式序列的充要条件是其特征多项式p(x)为为n次次本原多项式。本原多项式。例例4：设设p(x)=x4+x+1,是是4次本原多项式，以其为特征多项式的线次本原多项式，以其为特征多项式的线性移位寄存器的输出是性移位寄存器的输出是10010001111010110010001111010,周期是周期是24-1=15的的m序列。序列。解：解：p(x)|(x15-1),但是不存在但是不存在l15，使得使得p(x)|(xl-1)，所以所以p(x)阶是阶是15。p(x)的不可约性由的不可约性由x，x+1， x2+x+1不能整除不能整除p(x)而得，因此而得，因此p(x)是本原多项式。是本原多项式。对于对于k5，输出序列用输出序列用ak=ak-1