第四讲序列密码体制课件

第四讲第四讲 序列密码序列密码第四讲序列密码知识点：知识点：密码学中的随机数密码学中的随机数 序列密码的概念序列密码的概念 线性反馈移位寄存器线性反馈移位寄存器 非线性序列简介非线性序列简介 常用序列密码常用序列密码 序列密码的应用序列密码的应用知识点：密码学中的随机数4.1密码学中的随机数密码学中的随机数 在密码学都要涉及到随机数？因为许多密码系统的安全性都依在密码学都要涉及到随机数？因为许多密码系统的安全性都依赖于随机数的生成，例如赖于随机数的生成，例如DES加密算法中的密钥，加密算法中的密钥，RSA加密和数字加密和数字签名中的素数。签名中的素数。4.1.1随机数的使用随机数的使用 序列密码的保密性完全取决于密钥的随机性。序列密码的保密性完全取决于密钥的随机性。如果密钥是真正如果密钥是真正的随机数，则这种体制在理论上就是不可破译的。的随机数，则这种体制在理论上就是不可破译的。但这种方式所需但这种方式所需的密钥量大得惊人，在实际中是不可行的。的密钥量大得惊人，在实际中是不可行的。目前一般采用伪随机序列来代替随机序列作为密钥序列，也就目前一般采用伪随机序列来代替随机序列作为密钥序列，也就是序列存在着一定的循环周期。是序列存在着一定的循环周期。这样序列周期的长短就成为保密性这样序列周期的长短就成为保密性的关键。如果周期足够长，就会有比较好的保密性。的关键。如果周期足够长，就会有比较好的保密性。现在周期小于现在周期小于1010的序列很少被采用，周期长达的序列很少被采用，周期长达1050的序列也并不少见。的序列也并不少见。4.1密码学中的随机数在密码学都要涉及到随机数 何谓伪随机数生成器（何谓伪随机数生成器（PRNG）？）？假定需要生成介于假定需要生成介于1和和10之之间的随机数，每一个数出现的几率都是一样的。间的随机数，每一个数出现的几率都是一样的。理想情况下，应生理想情况下，应生成成0到到1之间的一个值，不考虑以前值，这个范围中的每一个值出现之间的一个值，不考虑以前值，这个范围中的每一个值出现的几率都是一样的，然后再将该值乘以的几率都是一样的，然后再将该值乘以10。由由任任何何伪伪随随机机数数生生成成器器返返回回的的数数目目会会受受到到0到到N之之间间整整数数数数目目的的限限制制。因因为为常常见见情情况况下下，伪伪随随机机数数生生成成器器生生成成 0 0 到到 N N 之之间间的的一一个个整整数数，返返回回的的整整数数再再除除以以 N N。可可以以得得出出的的数数字字总总是是处处于于 0 0 和和 1 1 之之间间。对对生生成成器器随随后后的的调调用用采采用用第第一一次次运运行行产产生生的的整整数数，并并将将它它传传给给一一个个函函数数，以以生生成成 0 0 到到 N N 之之间间的的一一个个新新整整数数，然然后后再再将将新新整整数数除除以以 N N 返回。返回。4.1.2伪随机数产生器伪随机数产生器何谓伪随机数生成器（PRNG）？假定需要生成介于1和 目目前前，常常见见随随机机数数发发生生器器中中N是是2321（大大约约等等于于40亿亿），对对于于32位位数数字字来来说说，这这是是最最大大的的值值。但但在在密密码码学学领领域域，40亿亿个个数数根根本不算大！本不算大！伪伪随随机机数数生生成成器器将将作作为为“种种子子”的的数数当当作作初初始始整整数数传传给给函函数数。由由伪伪随随机机数数生生成成器器返返回回的的每每一一个个值值完完全全由由它它返返回回的的前前一一个个值值所所决决定定。因因此此，最最初初的的种种子子决决定定了了这这个个随随机机数数序序列列。如如果果知知道道用用于于计计算算任任何何一个值的那个整数，那么就可以算出从这个生成器返回的下一个值。一个值的那个整数，那么就可以算出从这个生成器返回的下一个值。伪伪随随机机数数生生成成器器是是一一个个生生成成完完全全可可预预料料的的数数列列（称称为为流流）的的确确定定性性程程序序。一一个个编编写写得得很很好好的的的的PRNGPRNG可可以以创创建建一一个个序序列列，而而这这个个序序列列的属性与许多真正随机数的序列的属性是一样的。的属性与许多真正随机数的序列的属性是一样的。例例如如：（1 1）PRNGPRNG可可以以以以相相同同几几率率在在一一个个范范围围内内生生成成任任何何数数字字；（2 2）PRNG PRNG 可可以以生生成成带带任任何何统统计计分分布布的的流流；（3 3）由由PRNGPRNG生生成成的的数数字流不具备可辨别的模。字流不具备可辨别的模。目前，常见随机数发生器中N是2321（大约等于4.1.3基于密码算法的随机数产生器基于密码算法的随机数产生器1使用软件方法的随机数产生器使用软件方法的随机数产生器 一一个个常常用用的的随随机机数数产产生生器器是是属属于于线线形形拟拟合合生生成成器器一一类类的的。这这类生成器相当普遍，它们采用很具体的数学公式：类生成器相当普遍，它们采用很具体的数学公式：Xn+1=(aXn+b)modc即第即第n+1个数等于第个数等于第n个数乘以某个常数个数乘以某个常数a，再加上常数再加上常数b。如果结果大于或等于某个常数如果结果大于或等于某个常数c，那么通过除以那么通过除以c，并取它的余数来并取它的余数来将这个值限制在一定范围内。将这个值限制在一定范围内。注意：注意：a、b和和c通常是质数。通常是质数。2使用硬件方法的随机数产生器使用硬件方法的随机数产生器 目目前前生生成成随随机机数数的的几几种种硬硬件件设设备备都都是是用用于于商商业业用用途途。得得到到广广泛泛使使用用的的设设备备是是ComScireQNG，它它是是使使用用并并行行端端口口连连接接到到PC的的外外部部设设备备，它它可可以以在在每每秒秒钟钟生生成成20,000位位，这这对对于于大大多多数数注注重重安安全全性性的的应应用用程程序序来来说已经足够了。说已经足够了。另另外外Intel公公司司宣宣布布他他们们将将开开始始在在其其芯芯片片组组中中添添加加基基于于热热能能的的硬硬件件随随机机数数发发生生器器，而而且且基基本本上上不不会会增增加加客客户户的的成成本本。迄迄今今为为止止，已已经经交交付付了了一些带有硬件一些带有硬件PRNG的的CPU。4.1.3基于密码算法的随机数产生器1使4.1.4伪随机数的评价标准伪随机数的评价标准（1）看起来是随机的，表明它可以通过所有随机性统计检验。）看起来是随机的，表明它可以通过所有随机性统计检验。现现在在的的许许多多统统计计测测试试。它它们们采采用用了了各各种种形形式式，但但共共同同思思路路是是它它们们全全都都以以统统计计方方式式检检查查来来自自发发生生器器的的数数据据流流，尝尝试试发发现现数数据据是是否否是是随随机的。机的。确确保保数数据据流流随随机机性性的的最最广广为为人人知知的的测测试试套套件件就就是是 GeorgeMarsaglia的的DIEHARD软软件件包包（请请参参阅阅http:/www.stat.fsu.edu/pub/diehard/）。另另一一个个适适合合此此类类测测试试的的合合理理软软件件包包是是pLab（请请参参阅阅http:/random.mat.sbg.ac.at/tests/）。）。（2）它它是是不不可可预预测测的的。即即使使给给出出产产生生序序列列的的算算法法或或硬硬件件和和所所有有以以前前产产生生的的比比特特流流的的全全部部知知识识，也也不不可可能能通通过过计计算算来来预预测测下下一一个个随随机机比特应是什么。比特应是什么。（3）它它不不能能可可靠靠地地重重复复产产生生。如如果果用用完完全全同同样样的的输输入入对对序序列列产产生生器操作两次将得到两个不相关的随机序列。器操作两次将得到两个不相关的随机序列。4.1.4伪随机数的评价标准（1）看起来是随机的，表明4.2序列密码的概念序列密码的概念序列密码序列密码也称为流密码（也称为流密码（StreamCipher），它是对称密），它是对称密码算法的一种。序列密码具有实现简单、便于硬件实施、加码算法的一种。序列密码具有实现简单、便于硬件实施、加解密处理速度快、没有或只有有限的错误传播等特点，因此解密处理速度快、没有或只有有限的错误传播等特点，因此在实际应用中，特别是专用或机密机构中保持着优势，典型在实际应用中，特别是专用或机密机构中保持着优势，典型的应用领域包括无线通信、外交通信。的应用领域包括无线通信、外交通信。4.2序列密码的概念序列密码也称为流密码（Strea1949年年Shannon证明了只有一次一密的密码体制是绝对安证明了只有一次一密的密码体制是绝对安全的，这给序列密码技术的研究以强大的支持，序列密码方全的，这给序列密码技术的研究以强大的支持，序列密码方案的发展是模仿一次一密系统的尝试，或者说案的发展是模仿一次一密系统的尝试，或者说“一次一密一次一密”的密码方案是序列密码的雏形。如果序列密码所使用的是真的密码方案是序列密码的雏形。如果序列密码所使用的是真正随机方式的、与消息流长度相同的密钥流，则此时的序列正随机方式的、与消息流长度相同的密钥流，则此时的序列密码就是一次一密的密码体制。若能以一种方式产生一随机密码就是一次一密的密码体制。若能以一种方式产生一随机序列（密钥流），这一序列由密钥所确定，则利用这样的序序列（密钥流），这一序列由密钥所确定，则利用这样的序列就可以进行加密，即将密钥、明文表示成连续的符号或二列就可以进行加密，即将密钥、明文表示成连续的符号或二进制，对应地进行加密进制，对应地进行加密,加解密时一次处理明文中的一个或加解密时一次处理明文中的一个或几个比特。几个比特。1949年Shannon证明了只有一次一密的密码体序列密码与分组密码的对比序列密码与分组密码的对比分组密码分组密码以一定大小作为每次处理的基本单元，而序列以一定大小作为每次处理的基本单元，而序列密码则是以一个元素（一个字母或一个比特）作为基本的处密码则是以一个元素（一个字母或一个比特）作为基本的处理单元理单元。分组密码分组密码使用的是一个不随时间变化的固定变换，具有扩使用的是一个不随时间变化的固定变换，具有扩散性好、插入敏感等优点；其缺点是：加解密处理速度慢、散性好、插入敏感等优点；其缺点是：加解密处理速度慢、存在错误传播。存在错误传播。序列密码与分组密码的对比分组密码以一定大小作为每次序列密码与分组密码的对比序列密码与分组密码的对比序列密码序列密码是一个随时间变化的加密变换，具有转换速度是一个随时间变化的加密变换，具有转换速度快、低错误传播的优点，硬件实现电路更简单；其缺点是：快、低错误传播的优点，硬件实现电路更简单；其缺点是：低扩散（意味着混乱不够）、插入及修改的不敏感性。低扩散（意味着混乱不够）、插入及修改的不敏感性。序列密码序列密码涉及到大量的理论知识，提出了众多的设计原理，涉及到大量的理论知识，提出了众多的设计原理，也得到了广泛的分析，但许多研究成果并没有完全公开，这也得到了广泛的分析，但许多研究成果并没有完全公开，这也许是因为序列密码目前主要应用于军事和外交等机密部门也许是因为序列密码目前主要应用于军事和外交等机密部门的缘故。目前，公开的序列密码算法主要有的缘故。目前，公开的序列密码算法主要有RC4、SEAL等。等。序列密码与分组密码的对比序列密码是一个随时间变化的4.2序列密码模型序列密码模型 序列密码算法将明文逐位转换成密文，如下图所示。序列密码算法将明文逐位转换成密文，如下图所示。m m 密密钥钥流流发发生生器器（也也称称为为滚滚动动密密钥钥发发生生器器）输输出出一一系系列列比比特特流流：K1，K2，K3，Ki。密密钥钥流流（也也称称为为滚滚动动密密钥钥）跟跟明明文文比比特特流流，m1，m2，m3，mi，进行异或运算产生密文比特流。进行异或运算产生密文比特流。加密：加密：Ci=mi Ki 在解密端，密文流与完全相同的密钥流异或运算恢复出明文流。在解密端，密文流与完全相同的密钥流异或运算恢复出明文流。解密：解密：mi=Ci Ki 显然显然，mi Ki Ki=mi4.2序列密码模型序列密码算法将明文逐位转换成密文l序列密码体制的安全性序列密码体制的安全性l当流钥序列是具有均匀分布的离散无记忆随机序列时,在理论上是不可破译的。l实用的困难性实用的困难性真正的具有均匀分布的随机序列是不可能重复产生的密钥序列长(至少与明文序列一样长),其管理(存储、分配)难。序列密码一般模型序列密码体制的安全性序列密码一般模型 事实上，事实上，序列密码算法其安全性依赖于简单的异或运算和一次序列密码算法其安全性依赖于简单的异或运算和一次一密乱码本。一密乱码本。密钥流发生器生成的看似随机的密钥流实际上是确定密钥流发生器生成的看似随机的密钥流实际上是确定的，在解密的时候能很好的将其再现。的，在解密的时候能很好的将其再现。密钥流发生器输出的密钥越密钥流发生器输出的密钥越接近随机，对密码分析者来说就越困难。接近随机，对密码分析者来说就越困难。如如果果密密钥钥流流发发生生器器每每次次都都生生成成同同样样的的密密钥钥流流的的话话，对对攻攻击击来来说说，破译该算法就容易了。破译该算法就容易了。假假的的AliceAlice得得到到一一份份密密文文和和相相应应的的明明文文，她她就就可可以以将将两两者者异异或或恢恢复复出出密密钥钥流流。或或者者，如如果果她她有有两两个个用用同同一一个个密密钥钥流流加加密密的的密密文文，她她就就可可以以让让两两者者异异或或得得到到两两个个明明文文互互相相异异或或而而成成的的消消息息。这这是是很很容容易破译的，接着她就可以用明文跟密文异或得出密钥流。易破译的，接着她就可以用明文跟密文异或得出密钥流。现现在在，无无论论她她再再拦拦截截到到什什么么密密文文消消息息，她她都都可可以以用用她她所所拥拥有有的的密密钥钥流流进进行行解解密密。另另外外，她她还还可可以以解解密密，并并阅阅读读以以前前截截获获到到的的消消息息。一旦一旦AliceAlice得到一明文得到一明文/密文对，她就可以读懂任何东西了。密文对，她就可以读懂任何东西了。事实上，序列密码算法其安全性依赖于简单的异或运算和一 这这就就是是为为什什么么所所有有序序列列密密码码也也有有密密钥钥的的原原因因。密密钥钥流流发发生生器器的的输出是密钥的函数。输出是密钥的函数。这这样样，AliceAlice有有一一个个明明文文/密密文文对对，但但她她只只能能读读到到用用特特定定密密钥钥加加密的消息。密的消息。更换密钥，攻击者就不得不重新分析。更换密钥，攻击者就不得不重新分析。流密码是将明文划分成字符流密码是将明文划分成字符(如单个字母如单个字母)，或其编码的基本单，或其编码的基本单元元(如如0,10,1数字数字)，字符分别与密钥流作用进行加密，解密时以同步，字符分别与密钥流作用进行加密，解密时以同步产生的同样的密钥流实现。产生的同样的密钥流实现。流密码强度完全依赖于密钥序列的随机性随机性(Randomness)和不不可预测性可预测性(Unpredictability)。核心问题是密钥流生成器的设计核心问题是密钥流生成器的设计。保持收发两端密钥流的精确同步是实现可靠解密的关键技术保持收发两端密钥流的精确同步是实现可靠解密的关键技术。这就是为什么所有序列密码也有密钥的原因。密钥流发生器流密码的分类流密码的分类:1.1.自同步序列密码自同步序列密码 自自同同步步序序列列密密码码就就是是密密钥钥流流的的每每一一位位是是前前面面固固定定数数量量密密文文位位的的函函数数，下下图图和和下下页页图图描描述述了了其其工工作作原原理理。其其中中，内内部部状状态态是是前前面面n比比特特密密文文的的函函数数。该该算算法法的的密密码码复复杂杂性性在在于于输输出出函函数数，它它收收到到内内部部状态后生成密钥序列位。状态后生成密钥序列位。流密码的分类:1.自同步序列密码自同步序列密自同步流密码自同步流密码SSSC(Self-SynchronousStreamCipher)内部状态i依赖于(k kI,i-1,mi)，使密文ci不仅与当前输入mi有关，而且由于ki对i的关系而与以前的输入m1,m2,mi-1有关。一般在有限的n级存储下将与mi-1,mi-n有关。自同步流密码SSSC(Self-SynchronousSt2同步序列密码同步序列密码同步流密码同步流密码SSC(SynchronousStreamCipher)：内部状态i与明文消息无关，密钥流将独立于明文。特点：特点：对于明文而言，这类加密变换是无记忆的无记忆的。但它是时变的时变的。只有保持两端精确同步才能正常工作。对主动攻击时异常敏感而有利于检测无差错传播差错传播(Error Propagation)2同步序列密码同步流密码SSC(S 同同步步序序列列密密码码同同样样可可防防止止密密文文中中的的插插入入和和删删除除，因因为为它它们们会会使使系系统统失去同步而立即被发现。失去同步而立即被发现。然而，却不能避免单个位被窜改。然而，却不能避免单个位被窜改。优点优点：具有自同步能力，强化了其抗统计分析的能力缺点缺点：有n位长的差错传播。密钥流序列的性质密钥流序列的性质密钥流序列的性质密钥流序列的性质 密码设计者的最大愿望是设计出一个滚动密钥生成器，使得密钥经其扩展成的密钥流序列具有如下性质：极大的周期良好的统计特性抗线性分析抗统计分析。同步序列密码同样可防止密文中的插入和删除，因为它们会使系实际上实际上实际上实际上,序列密码不可能做到序列密码不可能做到序列密码不可能做到序列密码不可能做到“一次一密一次一密一次一密一次一密”但若密钥流生成器生成的密钥周期足够长，且随机性好，其安但若密钥流生成器生成的密钥周期足够长，且随机性好，其安但若密钥流生成器生成的密钥周期足够长，且随机性好，其安但若密钥流生成器生成的密钥周期足够长，且随机性好，其安全强度可以得到保证！全强度可以得到保证！全强度可以得到保证！全强度可以得到保证！因此，序列密码的设计核心在于密钥流生成器的设计，序列密因此，序列密码的设计核心在于密钥流生成器的设计，序列密因此，序列密码的设计核心在于密钥流生成器的设计，序列密因此，序列密码的设计核心在于密钥流生成器的设计，序列密码的安全强度取决于密钥流生成器生成的密钥周期、复杂度、随机码的安全强度取决于密钥流生成器生成的密钥周期、复杂度、随机码的安全强度取决于密钥流生成器生成的密钥周期、复杂度、随机码的安全强度取决于密钥流生成器生成的密钥周期、复杂度、随机（伪随机）特性等。（伪随机）特性等。（伪随机）特性等。（伪随机）特性等。实际上,序列密码不可能做到“一次一密”4.3线性反馈移位寄存器线性反馈移位寄存器产生密钥序列的最重要部件是线性反馈移位寄存器(LFSR),是因为:(1)LFSR非常适合于硬件实现;(2)能产生大的周期序列;(3)能产生较好统计特性的序列;(4)其结构能应用代数方法进行很好的分析.移位寄存器是流密码产生密钥流的一个主要组成部分。移位寄存器是流密码产生密钥流的一个主要组成部分。GF(2)上一个上一个n级反馈移位寄存器由级反馈移位寄存器由n个二元存储器与一个反馈函数个二元存储器与一个反馈函数f(a1,a2,an)组成，如下页图所示。组成，如下页图所示。4.3线性反馈移位寄存器产生密钥序列的 每每一一存存储储器器称称为为移移位位寄寄存存器器的的一一级级，在在任任一一时时刻刻，这这些些级级的的内内容容构构成成该该反反馈馈移移位位寄寄存存器器的的状状态态，每每一一状状态态对对应应于于GF(2)上上的的一一个个n维维向量，共有向量，共有2n种可能的状态。种可能的状态。每每 一一 时时 刻刻 的的 状状 态态 可可 用用 n长长 序序 列列“a1,a2,an”n维维 向向 量量“(a1,a2,an)”来表示，来表示，其中其中ai是第是第i级存储器的内容级存储器的内容。初初始始状状态态由由用用户户确确定定，当当第第i个个移移位位时时钟钟脉脉冲冲到到来来时时，每每一一级级存存储储器器ai都都将将其其内内容容向向下下一一级级ai-1传传递递，并并计计算算f(a1,a2,an)作作为为下下一一时时刻刻的的an。每一存储器称为移位寄存器的一级，在任一时刻，这些级的内容 反反馈馈函函数数f(a1,a2,an)是是n元元布布尔尔函函数数，即即n个个变变元元a1,a2,an可可以以独独立立地地取取0和和1两两个个可可能能的的值值，函函数数中中的的运运算算有有逻逻辑辑与与、逻逻辑辑或或、逻逻辑补等运算，最后的函数值也为辑补等运算，最后的函数值也为0或或1。例：下例：下图是一个3级反馈移位寄存器，其初始状态为(a1,a2,a3)=(1,0,1)，输出可由下表求出。即输出序列为即输出序列为101110111011，周期为，周期为4。反馈函数f(a1,a2,an)是n元布尔函数，即n个 如如果果f(a1,a2,an)是是(a1,a2,an)的的线线性性函函数数，则则称称之之为为线线性性反反馈馈移移位位寄寄存存器器LFSR（linearfeedbackshiftregister），否否则则称称为为非非线线性移位寄存器。性移位寄存器。此时此时f可写为：可写为：f(a1,a2,an)=cna1 cn-1a2 c1an 其其中中常常数数ci=0或或1，是是模模2加加法法。ci=0或或1可可用用开开关关的的断断开开和和闭闭合来实现，合来实现，如下图所示如下图所示，这样的线性函数共有，这样的线性函数共有2n个。个。如果f(a1,a2,an)是(a1,a2,an)输出序列输出序列at满足：满足：an+t=cnat cn-1at+1 c1an+t-1 其中，其中，t为非负正整数。为非负正整数。线性反馈移位寄存器因其实现简单、速度快、有较为成熟的理线性反馈移位寄存器因其实现简单、速度快、有较为成熟的理论等优点而成为构造密钥流生成器的最重要的部件之一。论等优点而成为构造密钥流生成器的最重要的部件之一。例例：下 图 是 一 个 5级 线 性 反 馈 移 位 寄 存 器，其 初 始 状 态 为（a1,a2,a3,a4,a5）=(1,0,0,1,1)，可求出输出序列为1001101001000010101110110001111100110，周期为31。输出序列at满足：an+t=cnat cn-1a 在在线线性性反反馈馈移移位位寄寄存存器器中中总总是是假假定定c1,c2,cn中中至至少少有有一一个个不不为为0，否否则则f(a1,a2,an)0，这这样样的的话话，在在n个个脉脉冲冲后后状状态态必必然然是是000，且这个状态必将一直持续下去。且这个状态必将一直持续下去。若若只只有有一一个个系系数数不不为为0，设设仅仅有有cj不不为为0，实实际际上上是是一一种种延延迟迟装装置置。一般对于一般对于n级线性反馈移位寄存器，总是假定级线性反馈移位寄存器，总是假定cn=1。n级线性反馈移位寄存器的状态周期小于等于级线性反馈移位寄存器的状态周期小于等于2n-1。输出序列的周输出序列的周期与状态周期相等，也小于等于期与状态周期相等，也小于等于2n-1。只要选择合适的反馈函数便只要选择合适的反馈函数便可使序列的周期达到最大值可使序列的周期达到最大值2n-1。定义定义1：n级线性反馈移位寄存器产生的序列级线性反馈移位寄存器产生的序列ai的周期达到最大的周期达到最大值值2n-1时，称时，称ai为为n级级m序列。序列。在线性反馈移位寄存器中总是假定c1,c2,cn中至 根据密码学需要，对于线性移位寄存器需考虑以下问题：根据密码学需要，对于线性移位寄存器需考虑以下问题：（1）如如何何利利用用级级数数尽尽可可能能小小的的线线性性移移位位寄寄存存器器产产生生周周期期长长、统统计性能好的序列；计性能好的序列；（2）已已知知一一个个序序列列ai，如如何何构构造造一一个个尽尽可可能能短短的的线线性性移移位位寄存器来产生它。寄存器来产生它。因为因为n级线性移位寄存器的输出序列级线性移位寄存器的输出序列ai满足递推关系：满足递推关系：an+k=c1an+k-1 c2an+k-2 cnak，对任何对任何k1成立。成立。这这种种递递推推关关系系可可用用一一个个一一元元高高次次多多项项式式p(x)=1+c1x+cn-1xn-1cnxn 表示，称这个多项式为表示，称这个多项式为LFSR的特征多项式。的特征多项式。由由于于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)的周期或阶。定定理理1：设p(x)=1+c1x+cn-1xn-1cnxn是GF(2)上的多项式，G(p(x)中任一序列ai的生成函数A(x)满足：A(x)=(x)/p(x)，其中=(a1+a2x+anxn-1)+c1x(a1+a2x+an 1xn-2)+c2x(a1+a2x+an2xn-3)+cn-1xn-1a1。定理1说明了n级线性移位寄存器的特征多项式和它的生成函数之间的关系。定定理理2：若序列ai的特征多项式p(x)定义在GF(2)上，p是p(x)的周期，则ai的周期r|p。n级LFSR输出序列的周期r不依赖于初始条件，而依赖于特征多项式p(x)。我们感兴趣的是LFSR遍历2n-1个非零状态，这时序列的周期达到最大2n-1，这种序列就是m序列。定义2：给定序列ai，幂级数 例例3：设设f(x)=x4+x3+x2+x+1是是GF(2)上上的的不不可可约约多多项项式式，但但是是它它的的输出序列是输出序列是000110001100011，周期是，周期是5，不是，不是m序列。序列。解：f(x)的不可约性由多项式x，x+1，x2+x+1不能整除f(x)而得。对于k5，输出序列用ak=ak-1ak-2ak-3ak4检验即可。定义定义4：仅能被非零常数或者本身的常数倍除尽，不能被其他多项式整除的多项式称为不可约多项式。特征多项式满足什么条件时，特征多项式满足什么条件时，LFSR的输出序列为的输出序列为m序列。序列。定定理理3：n级LFSR产生的序列有最大周期2n-1的必要条件是其特征多项式为不可约多项式。该定理的逆不成立，即LFSR产生的特征多项式为不可约多项式，但其输出序列不一定是m序列。例3：设f(x)=x4+x3+x2+x+1 是GF(2)定定义义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-1ak4检验即可。虽虽然然n级级线线性性移移位位寄寄存存器器产产生生的的m序序列列具具有有良良好好的的伪伪随随机机性性，但但是是直直接接用用其其构构造造密密钥钥流流序序列列是是极极不不安安全全的的。因因为为利利用用2n个个输输出出位位可可以找到它的起始状态和特征多项式。以找到它的起始状态和特征多项式。定义5：若n次不可约多项式p(x)的阶为2n-1，称其 若特征多项式p(x)=x3+x+1，初始状态为（101）的移位寄存器产生序列为(101001)。设明文为（011010），那么密文为（110011）。破译者计算mc得到密钥系列(101001)，那么可以得到下列矩阵方程式：得到c31，c20，c11，从而得到特征多项式：p(x)=x3+x+1若特征多项式p(x)=x3+x+1，初始状态为（101）4.4非线性序列简介非线性序列简介 线线性性移移位位寄寄存存器器序序列列密密码码在在已已知知明明文文攻攻击击下下是是可可破破译译的的这这一一事事实实促促使使人人们们向向非非线线性性领领域域探探索索。目目前前研研究究的的比比较较充充分分的的由由非非线线性性移移位位寄存器，对线性移位寄存器进行非线性组合等寄存器，对线性移位寄存器进行非线性组合等。为了使密钥流生成器输出的二元序列尽可能复杂，应保证其周期为了使密钥流生成器输出的二元序列尽可能复杂，应保证其周期尽可能大、线性复杂度和不可预测性尽可能高，尽可能大、线性复杂度和不可预测性尽可能高，因此常使用多个因此常使用多个LFSR来构造二元序列，称每个来构造二元序列，称每个LFSR的输出序列为驱动序列，的输出序列为驱动序列，显然显然密钥流生成器输出序列的周期不大于各驱动序列周期的乘积，密钥流生成器输出序列的周期不大于各驱动序列周期的乘积，因此，因此，提高输出序列的线性复杂度应从极大化其周期开始。提高输出序列的线性复杂度应从极大化其周期开始。1Geffe序列生成器序列生成器Geffe序序列列生生成成器器由由3个个LFSR组组成成（如如下下图图），其其中中LFSR2作作为为控制生成器使用。控制生成器使用。4.4非线性序列简介线性移位寄存器序列密码在已知明 当当LFSR2输输出出1时时，LFSR2与与LFSR1相相连连接接；当当LFSR2输输出出0时时，LFSR2与与LFSR3相连接。相连接。若若设设LFSRi的的输输出出序序列列为为a(i)k(i=1,2,3)，则则输输出出序序列列bk可可以以表表示为：示为：设LFSRi的特征多项式分别为ni次本原多项式，且ni两两互素，则Geffe序列的周期为，线性复杂度为 。当LFSR2输出1时，LFSR2与LFSR1相连接；当L2J-K触发器触发器 其中，x1和x2分别是J和K端的输入。J-K触发器如下图所示，它的两个输入端分别用J和K表示，其输出ck不仅依赖于输入，还依赖于前一个输出位ck-1，即 在在下下图图中中，令令驱驱动动序序列列ak和和bk分别为分别为m级和级和n级级m序列，则有序列，则有利用利用J-K触发器的非线性序列生成器触发器的非线性序列生成器 如果令如果令c-1=0，则输出序列的最则输出序列的最初初3项为：项为：当当m与与n互素且互素且a0+b0=1时，序列时，序列ck的周期为的周期为(2m-1)(2n-1)。2J-K触发器其中，x1和x2分别是J和K端的输入。3Pless生成器生成器Pless生生成成器器由由8个个LFSR、4个个J-K触触发发器器和和1个个循循环环计计数数器器构构成成，由循环计数器进行选通控制，如下图所示。由循环计数器进行选通控制，如下图所示。假定在时刻假定在时刻t输出第输出第t(mod4)个单元，则输出序列为：个单元，则输出序列为：a a0 0 b b1 1 c c2 2 d d3 3 a a4 4 b b5 5 d d6 63Pless生成器Pless生成器由8个LFS4钟控发生器钟控发生器 钟钟控控发发生生器器是是由由控控制制序序列列（由由一一个个或或多多个个移移位位寄寄存存器器来来控控制制生生成成）的的当当前前值值决决定定被被采采样样的的序序列列寄寄存存器器移移动动次次数数（即即由由控控制制序序列列的的当当前前值值确定采样序列寄存器的时钟脉冲数目）。确定采样序列寄存器的时钟脉冲数目）。控控制制序序列列和和被被采采样样序序列列可可以以是是源源于于同同一一个个LFSR（称称为为自自控控），也也可可以以源源于于不不同同的的LFSR（称称为为他他控控），还还可可以以相相互互控控制制（称称为为互互控控）。钟钟控发生器示意图如下图所示。控发生器示意图如下图所示。4钟控发生器钟控发生器是由控制序列（由一个或多个移位 当当控控制制序序列列当当前前值值为为1时时，被被采采样样序序列列生生成成器器被被时时钟钟驱驱动动k次次后后输输出出；当当控控制制序序列列当当前前值值为为0时时，被被采采样样序序列列生生成成器器被被时时钟钟驱驱动动d次次后输出。后输出。另外，停走式发生器也是一种钟控模型，它由另外，停走式发生器也是一种钟控模型，它由2个个LFSR组成。组成。其中，其中，LFSR-1控制控制LFSR-2的时钟输入。的时钟输入。当且仅当当且仅当LFSR-1的时间的时间t-1的输出为的输出为1时，时，LFSR-2在时间在时间t改变改变状态（状态（也即也即LFSR-1输出时钟脉冲，使输出时钟脉冲，使LFSR-2进行输出并反馈以改进行输出并反馈以改变移位寄存器的状态变移位寄存器的状态）。）。当控制序列当前值为1时，被采样序列生成器被时钟驱动k次5收缩和自收缩发生器收缩和自收缩发生器 收收缩缩发发生生器器是是又又控控制制序序列列的的当当前前值值决决定定被被采采样样序序列列移移位位寄寄存存器器是否输出。是否输出。该该发发生生器器由由2个个LFSR组组成成。LFSR-1、LFSR-2分分别别按按各各自自时时钟钟运运行行，LFSR-1在在时时间间t-1时时刻刻的的输输出出为为1时时，LFSR-2在在时时间间t时时刻刻输输出为密钥流，否则舍去。出为密钥流，否则舍去。自自收收缩缩发发生生器器从从一一个个LFSR抽抽出出2条条序序列列，其其中中一一条条为为控控制制序序列列，另另一一条条为为百百采采样样序序列列。当当控控制制序序列列输输出出为为1时时，采采样样序序列列输输出出为为密密钥流，否则舍去。钥流，否则舍去。此外，还有多路复合序列，这类序列也归结为非线性组合序列。此外，还有多路复合序列，这类序列也归结为非线性组合序列。5收缩和自收缩发生器收缩发生器是又控制序列的当前值决基于基于LFSR的序列密码非常适合于硬件实现，但是不特别适合软的序列密码非常适合于硬件实现，但是不特别适合软件实现。件实现。这导致出现了一些关于序列密码被计划用于快速软件实这导致出现了一些关于序列密码被计划用于快速软件实现的新建议，因为这些建议大部分具有专利，因此这里不讨论它现的新建议，因为这些建议大部分具有专利，因此这里不讨论它们的技术细节。们的技术细节。比较常用的序列密码是比较常用的序列密码是A5、SEAL和和RC4序列密码算法，序列密码算法，A5是典是典型的基于型的基于LFSR的序列密码算法，的序列密码算法，SEAL和和RC4不是基于不是基于LFSR的的序列密码算法，而是基于分组密码的输出反馈模式（序列密码算法，而是基于分组密码的输出反馈模式（OFB）和密和密码反馈模式（码反馈模式（CFB）来实现的。来实现的。其他不基于其他不基于LFSR的序列密码生的序列密码生成器的安全性基于数论问题的难解性，这些生成器比基于成器的安全性基于数论问题的难解性，这些生成器比基于LFSR的生成器要慢很多。的生成器要慢很多。4.5常用的序列密码算法常用的序列密码算法基于LFSR的序列密码非常适合于硬件实现，但是不特别适合软件A5序列密码算法是利用欧洲数字蜂窝移动电话（序列密码算法是利用欧洲数字蜂窝移动电话（GSM）加密的加密的序列密码算法，它用于从用户手机至基站的连接加密，序列密码算法，它用于从用户手机至基站的连接加密，GSM会会话每帧数据包含话每帧数据包含228比特，比特，A5算法每次会话将产生算法每次会话将产生228比特的密比特的密钥，算法的密钥长度为钥，算法的密钥长度为64比特，还包含有一个比特，还包含有一个22比特的帧数。比特的帧数。A5算法有两个版本：强算法有两个版本：强A5/1和弱和弱A5/2。A5算法是一种典型的基于算法是一种典型的基于LFSR的序列密码算法，它由三个的序列密码算法，它由三个LFSR组成，是一种集控制与停走于一体的钟控模型，但是组成，是一种集控制与停走于一体的钟控模型，但是A5算算法没有完全公开，因而各种资料的描述也不尽相同，重要是第二法没有完全公开，因而各种资料的描述也不尽相同，重要是第二个和第三个个和第三个LFSR的联接多项式以及钟控的位置。的联接多项式以及钟控的位置。A5算法的算法的3个个LFSR中中LFSR-1、LFSR-2、LFSR-3的级数分别为的级数分别为19、22和和23。LFSR-1的反馈抽头是的反馈抽头是18、17、16、13，LFSR-2的的反馈抽头是反馈抽头是21、20、16、12，LFSR-3的反馈抽头是的反馈抽头是22、21、18、17（如下页图的数字表示抽头的位置）。（如下页图的数字表示抽头的位置）。4.5.1A5序列密码算法序列密码算法A5序列密码算法是利用欧洲数字蜂窝移动电话（GSM）加密的序第四讲序列密码体制课件第四讲序列密码体制课件4.5.2SEAL序列密码算法序列密码算法4.5.2SEAL序列密码算法第四讲序列密码体制课件第四讲序列密码体制课件第四讲序列密码体制课件第四讲序列密码体制课件第四讲序列密码体制课件4.5.3RC4序列密码体制序列密码体制RC4是是RonRivest1987年为年为RSA设计，是一个可变密钥长设计，是一个可变密钥长度、面向字节操作的序列密码度、面向字节操作的序列密码基本思想：基本思想：对于对于n n位长的字，它总共位长的字，它总共N=2N=2n n个可能的内部置换个可能的内部置换状态矢量状态矢量S S，这些状态是保密的，密钥流这些状态是保密的，密钥流K K由由S S中中N N个元素按照个元素按照一定方式选出一个元素而生成。每生成一个一定方式选出一个元素而生成。每生成一个K K值，值，S S中的元素中的元素就被重新置换一次就被重新置换一次密钥调度算法（密钥调度算法（KSA）伪随机数生成算法（伪随机数生成算法（PRGA）4.5.3RC4序列密码体制RC4是RonRive密钥调度算法密钥调度算法KSAKSA算法描述如下：Fori=0toN-1doSi=i;j=0;Fori=0toN-1doJ=(j+Si+KImodL)modN;Swap(Si,Sj)密钥调度算法KSAKSA算法描述如下：伪随机数生成算法伪随机数生成算法PRGAi=0；J=0；While(true）i=（i+1）modN；J=（j+Si)modN;Swap(Si,Sj);T=(Si+Sj)modN;Outputk=St;伪随机数生成算法PRGAi=0；实例实例实例第四讲序列密码体制课件第四讲序列密码体制课件RC4目前使用在：（1）SSL（安全套接字）中广泛使用（2）WEP(WiredEquivalentPrivacy:有线对等保密)IEEE802.11(http:/