序列密码讲解及事例

1、第五讲：第五讲：序列密码序列密码2 人们试图用序列密码方式仿效”一次一密”密码. 从而促成了序列密码的研究和发展. 序列密码是世界军事, 外交等领域应用的主流密码体制. 在通常的序列密码中, 加解密用的密钥序列是伪随机序列, 它的产生容易且有较成熟的理论工具, 所以序列密码是当前通用的密码系统. 序列密码的安全性主要依赖于密钥序列, 因而什么样的伪随机序列是安全可靠的密钥序列, 以及如何实现这种序列就成了序列密码中研究的一个主要方面.3 在密码学都要涉及到随机数？因为许多密码系统的安全性都依在密码学都要涉及到随机数？因为许多密码系统的安全性都依赖于随机数的生成，例如赖于随机数的生成，例如DES

2、加密算法中的密钥，加密算法中的密钥，RSA加密和数字加密和数字签名中的素数。签名中的素数。 5.1.1 随机数的使用随机数的使用 序列密码的保密性完全取决于密钥的随机性。序列密码的保密性完全取决于密钥的随机性。如果密钥是真正如果密钥是真正的随机数，则这种体制在理论上就是不可破译的。的随机数，则这种体制在理论上就是不可破译的。但这种方式所需但这种方式所需的密钥量大得惊人，在实际中是不可行的。的密钥量大得惊人，在实际中是不可行的。 目前一般采用伪随机序列来代替随机序列作为密钥序列，也就目前一般采用伪随机序列来代替随机序列作为密钥序列，也就是序列存在着一定的循环周期。是序列存在着一定的循环周期。这样

3、序列周期的长短就成为保密性这样序列周期的长短就成为保密性的关键。如果周期足够长，就会有比较好的保密性。的关键。如果周期足够长，就会有比较好的保密性。现在周期小于现在周期小于1010的序列很少被采用，周期长达的序列很少被采用，周期长达1050的序列也并不少见。的序列也并不少见。 4 何谓伪随机数生成器（何谓伪随机数生成器（PRNG）？）？假定需要生成介于假定需要生成介于1和和 10 之之间的随机数，每一个数出现的几率都是一样的。间的随机数，每一个数出现的几率都是一样的。理想情况下，应生理想情况下，应生成成0到到1之间的一个值，不考虑以前值，这个范围中的每一个值出现之间的一个值，不考虑以前值，这个

4、范围中的每一个值出现的几率都是一样的，然后再将该值乘以的几率都是一样的，然后再将该值乘以 10。 由任何伪随机数生成器返回的数目会受到由任何伪随机数生成器返回的数目会受到 0 到到 N 之间整数数目的之间整数数目的限制。限制。因为常见情况下，伪随机数生成器生成因为常见情况下，伪随机数生成器生成 0 0 到到 N N 之间的一个之间的一个整数，返回的整数再除以整数，返回的整数再除以 N N。可以得出的数字总是处于可以得出的数字总是处于 0 0 和和 1 1 之之间。间。对生成器随后的调用采用第一次运行产生的整数，并将它传给对生成器随后的调用采用第一次运行产生的整数，并将它传给一个函数，以生成一个

5、函数，以生成 0 0 到到 N N 之间的一个新整数，然后再将新整数除之间的一个新整数，然后再将新整数除以以 N N 返回。返回。 5.1.2 伪随机数产生器5 目前，常见随机数发生器中目前，常见随机数发生器中N 是是2321 （大约等于（大约等于 40 亿），对亿），对于于 32 位数字来说，这是最大的值。位数字来说，这是最大的值。但在密码学领域，但在密码学领域， 40 亿个数根亿个数根本不算大！本不算大！ 伪随机数生成器将作为伪随机数生成器将作为“种子种子”的数当作初始整数传给函数。的数当作初始整数传给函数。由由伪随机数生成器返回的每一个值完全由它返回的前一个值所决定。伪随机数生成器返回的

6、每一个值完全由它返回的前一个值所决定。因此，最初的种子决定了这个随机数序列。因此，最初的种子决定了这个随机数序列。如果知道用于计算任何如果知道用于计算任何一个值的那个整数，那么就可以算出从这个生成器返回的下一个值。一个值的那个整数，那么就可以算出从这个生成器返回的下一个值。 伪随机数生成器是一个生成完全可预料的数列（称为流）的确定伪随机数生成器是一个生成完全可预料的数列（称为流）的确定性程序。性程序。一个编写得很好的的一个编写得很好的的PRNGPRNG可以创建一个序列，而这个序列可以创建一个序列，而这个序列的属性与许多真正随机数的序列的属性是一样的。的属性与许多真正随机数的序列的属性是一样的。

7、 例如：（例如：（1 1）PRNGPRNG可以以相同几率在一个范围内生成任何数字；可以以相同几率在一个范围内生成任何数字；（2 2）PRNG PRNG 可以生成带任何统计分布的流；（可以生成带任何统计分布的流；（3 3）由）由PRNGPRNG生成的数生成的数字流不具备可辨别的模。字流不具备可辨别的模。65.1.3 基于密码算法的随机数产生器 1使用软件方法的随机数产生器使用软件方法的随机数产生器 一个常用的随机数产生器是属于线形拟合生成器一类的。一个常用的随机数产生器是属于线形拟合生成器一类的。这这类生成器相当普遍，它们采用很具体的数学公式：类生成器相当普遍，它们采用很具体的数学公式： Xn+

8、1 = (aXn + b) mod c即第即第 n+1 个数等于第个数等于第 n 个数乘以某个常数个数乘以某个常数 a，再加上常数，再加上常数 b。如果结果大于或等于某个常数如果结果大于或等于某个常数 c，那么通过除以，那么通过除以 c，并取它的余数，并取它的余数来将这个值限制在一定范围内。来将这个值限制在一定范围内。注意：注意：a、b 和和 c 通常是质数。通常是质数。 2使用硬件方法的随机数产生器使用硬件方法的随机数产生器 目前生成随机数的几种硬件设备都是用于商业用途。目前生成随机数的几种硬件设备都是用于商业用途。得到广泛使得到广泛使用的设备是用的设备是 ComScire QNG，它是使用

9、并行端口连接到，它是使用并行端口连接到 PC 的外部设备，的外部设备，它可以在每秒钟生成它可以在每秒钟生成 20,000 位，这对于大多数注重安全性的应用程序来位，这对于大多数注重安全性的应用程序来说已经足够了。说已经足够了。 另外另外Intel 公司宣布他们将开始在其芯片组中添加基于热能的硬件公司宣布他们将开始在其芯片组中添加基于热能的硬件随机数发生器，而且基本上不会增加客户的成本。迄今为止，已经交付随机数发生器，而且基本上不会增加客户的成本。迄今为止，已经交付了一些带有硬件了一些带有硬件 PRNG 的的 CPU。 75.1.4 伪随机数的评价标准 （1）看起来是随机的，表明它可以通过所有随

10、机性统计检验。）看起来是随机的，表明它可以通过所有随机性统计检验。 现在的许多统计测试现在的许多统计测试。它们采用了各种形式，但共同思路是它们。它们采用了各种形式，但共同思路是它们全都以统计方式检查来自发生器的数据流，尝试发现数据是否是随全都以统计方式检查来自发生器的数据流，尝试发现数据是否是随机的。机的。 确保数据流随机性的最广为人知的测试套件就是确保数据流随机性的最广为人知的测试套件就是 George Marsaglia 的的 DIEHARD 软件包（请参阅软件包（请参阅/ pub/diehard/）。）。另一个适合此类测试的合理软件包是另一个适

11、合此类测试的合理软件包是 pLab（请参（请参阅阅http:/random.mat.sbg.ac.at/tests/）。）。 （2）它是不可预测的。）它是不可预测的。即使给出产生序列的算法或硬件和所有以即使给出产生序列的算法或硬件和所有以前产生的比特流的全部知识，也不可能通过计算来预测下一个随机前产生的比特流的全部知识，也不可能通过计算来预测下一个随机比特应是什么。比特应是什么。 （3）它不能可靠地重复产生。）它不能可靠地重复产生。如果用完全同样的输入对序列产生如果用完全同样的输入对序列产生器操作两次将得到两个不相关的随机序列。器操作两次将得到两个不相关的随机序列。 85.2 序列密码的概念及

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

13、显然，mi K i K i =m i9 事实上，事实上，序列密码算法其安全性依赖于简单的异或运算和一次序列密码算法其安全性依赖于简单的异或运算和一次一密乱码本。一密乱码本。密钥流发生器生成的看似随机的密钥流实际上是确定密钥流发生器生成的看似随机的密钥流实际上是确定的，在解密的时候能很好的将其再现。的，在解密的时候能很好的将其再现。密钥流发生器输出的密钥越密钥流发生器输出的密钥越接近随机，对密码分析者来说就越困难。接近随机，对密码分析者来说就越困难。 如果密钥流发生器每次都生成同样的密钥流的话，对攻击来说，如果密钥流发生器每次都生成同样的密钥流的话，对攻击来说，破译该算法就容易了。破译该算法就容

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

15、外，她还可以解密，并阅读以前截获到的消息另外，她还可以解密，并阅读以前截获到的消息。一旦一旦AliceAlice得到一明文得到一明文/ /密文对，她就可以读懂任何东西了。密文对，她就可以读懂任何东西了。10 这就是为什么所有序列密码也有密钥的原因。这就是为什么所有序列密码也有密钥的原因。密钥流发生器的密钥流发生器的输出是密钥的函数。输出是密钥的函数。 这样，这样，AliceAlice有一个明文有一个明文/ /密文对，但她只能读到用特定密钥加密文对，但她只能读到用特定密钥加密的消息。密的消息。 更换密钥，攻击者就不得不重新分析。更换密钥，攻击者就不得不重新分析。 流密码强度完全依赖于密钥序列的随

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

17、数，它收到内部比特密文的函数。该算法的密码复杂性在于输出函数，它收到内部状态后生成密钥序列位。状态后生成密钥序列位。12自同步流密码自同步流密码SSSC(Self-Synchronous Stream Cipher) 内部状态i依赖于(k kI,i-1,mi)，使密文ci不仅与当前输入mi有关，而且由于ki对i的关系而与以前的输入m1, m2 ,mi-1有关。一般在有限的n级存储下将与mi-1,mi-n有关。13特点特点: 密钥流不仅依赖于种子密钥和密钥流产生器的结构，还密钥流不仅依赖于种子密钥和密钥流产生器的结构，还与密文流（或明文流）有关。初始向量与密文流（或明文流）有关。初始向量IV在这

18、里相当在这里相当于初始密文的作用，要求收、发双方必须相同。于初始密文的作用，要求收、发双方必须相同。 自同步。解密只取决于先前特定数量的密文字符，因此，自同步。解密只取决于先前特定数量的密文字符，因此，即使出现删除、插入等非法攻击，收方最终都能够自动即使出现删除、插入等非法攻击，收方最终都能够自动重建同步解密，因而收、发双方不再需要外部同步。重建同步解密，因而收、发双方不再需要外部同步。 有差错传播。因为密钥流与密文流有关，所以一个密文有差错传播。因为密钥流与密文流有关，所以一个密文的传输错误会影响下面有限个密文的解密。的传输错误会影响下面有限个密文的解密。 14自同步序列密码举例自同步序列密

19、码举例例例 假设种子密钥为假设种子密钥为k=hk=h，之后的密钥是上一个密文。采用移位密，之后的密钥是上一个密文。采用移位密码，明文为码，明文为cryptographycryptography，列表给出它的加密和解密过程。，列表给出它的加密和解密过程。一个字符的差错传播一个字符的差错传播 不需要同步不需要同步15 2同步序列密码同步序列密码在同步序列密码中，密钥流的产生独立于明文和密文。分组加密的在同步序列密码中，密钥流的产生独立于明文和密文。分组加密的OFBOFB模模式就是一个同步序列加密的例子。式就是一个同步序列加密的例子。1 1）同步要求。在一个同步序列密码中，发送方和接收方必须是同步的

20、，）同步要求。在一个同步序列密码中，发送方和接收方必须是同步的，用同样的密钥且该秘钥操作在同样的位置，才能保证解密。如果在传输过用同样的密钥且该秘钥操作在同样的位置，才能保证解密。如果在传输过程中密文字符有插入或删除导致同步丢失，则解密失败，且只能通过重新程中密文字符有插入或删除导致同步丢失，则解密失败，且只能通过重新同步来实现恢复。同步来实现恢复。2 2）无错误传输。在传输期间，一个密文字符被改变只影响该字符的恢复，）无错误传输。在传输期间，一个密文字符被改变只影响该字符的恢复，不会对后继字符产生影响。不会对后继字符产生影响。16 2同步序列密码同步序列密码 同步流密码同步流密码SSC(Sy

21、nchronous Stream Cipher)： 内部状态i与明文消息无关，密钥流将独立于明文。特点：特点：对于明文而言，这类加密变换是无记忆的无记忆的。但它是时变的时变的。只有保持两端精确同步才能正常工作。对主动攻击时异常敏感而有利于检测无差错传播差错传播( (Error Propagation) )17 同步序列密码同样可防止密文中的插入和删除，同步序列密码同样可防止密文中的插入和删除，因为它们会使系统因为它们会使系统失去同步而立即被发现。失去同步而立即被发现。然而，却不能避免单个位被窜改。然而，却不能避免单个位被窜改。优点优点：具有自同步能力，强化了其抗统计分析的能力缺点缺点：有n位长

22、的差错传播。 密码设计者的最大愿望是设计出一个滚动密钥生成器，使得密钥经其扩展成的密钥流序列具有如下性质：极大的周期良好的统计特性抗线性分析抗统计分析。18195.3 5.3 线性反馈移位寄存器线性反馈移位寄存器( (linear feedback shift registerlinear feedback shift register，LFSRLFSR) ) nnnnnacacacaca1122111)2(,GFcaii异或表达式异或表达式-线性反馈线性反馈如果如果n n级线性反级线性反馈移位寄存器产馈移位寄存器产生的输出序列的生的输出序列的周期为周期为2 2n n-1-1，则，则称为称为m

23、 m序列产生器。序列产生器。m m序列不仅周期序列不仅周期长，而且伪随机长，而且伪随机特性好，这正是特性好，这正是序列密码的密钥序列密码的密钥流所需要的特性。流所需要的特性。 205.3 线性反馈移位寄存器 产生密钥序列的最重要部件是线性反馈移位寄存器(LFSR),是因为: (1) LFSR非常适合于硬件实现; (2) 能产生大的周期序列; (3) 能产生较好统计特性的序列; (4) 其结构能应用代数方法进行很好的分析. 移位寄存器是流密码产生密钥流的一个主要组成部分。移位寄存器是流密码产生密钥流的一个主要组成部分。GF(2)上一个上一个n级反馈移位寄存器由级反馈移位寄存器由n个二元存储器与一

24、个反馈函数个二元存储器与一个反馈函数f(a1,a2,an)组成，如下页图所示。组成，如下页图所示。 21 每一存储器称为移位寄存器的一级，在任一时刻，这些级的内容每一存储器称为移位寄存器的一级，在任一时刻，这些级的内容构成该反馈移位寄存器的状态，构成该反馈移位寄存器的状态，每一状态对应于每一状态对应于GF(2)上的一个上的一个n维维向量，共有向量，共有2n种可能的状态。种可能的状态。 每一时刻的状态可用每一时刻的状态可用n长序列长序列“a1,a2,an ”n维向量维向量“(a1,a2,an)”来表示，来表示，其中其中ai是第是第i级存储器的内容级存储器的内容。 初始状态由用户确定，当第初始状态

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

26、,1)，输出可由下表求出。 即输出序列为即输出序列为101110111011，周期为，周期为4。23 如果如果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可用开关的断开和闭可用开关的断开和闭合来实现，合来实现，如下图所示如下图所示，这样

27、的线性函数共有，这样的线性函数共有2n个。个。24 输出序列输出序列at满足：满足：an+t=cnat cn-1at+1 c1an+t-1 其中，其中，t为非负正整数。为非负正整数。 线性反馈移位寄存器因其实现简单、速度快、有较为成熟的理线性反馈移位寄存器因其实现简单、速度快、有较为成熟的理论等优点而成为构造密钥流生成器的最重要的部件之一。论等优点而成为构造密钥流生成器的最重要的部件之一。例：例：下图是一个5级线性反馈移位寄存器，其初始状态为（a1,a2,a3,a4,a5）=(1,0,0,1,1)，可求出输出序列为1001101001000010 101110110001111100110，周

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

29、周。输出序列的周期与状态周期相等，也小于等于期与状态周期相等，也小于等于2n-1。只要选择合适的反馈函数便。只要选择合适的反馈函数便可使序列的周期达到最大值可使序列的周期达到最大值2n-1。 定义定义1：n级线性反馈移位寄存器产生的序列级线性反馈移位寄存器产生的序列ai的周期达到最大的周期达到最大值值2n-1时，称时，称ai为为n级级m序列。序列。26 根据密码学需要，对于线性移位寄存器需考虑以下问题：根据密码学需要，对于线性移位寄存器需考虑以下问题： （1）如何利用级数尽可能小的线性移位寄存器产生周期长、）如何利用级数尽可能小的线性移位寄存器产生周期长、统计性能好的序列；统计性能好的序列；

30、（2）已知一个序列）已知一个序列ai，如何构造一个尽可能短的线性移位，如何构造一个尽可能短的线性移位寄存器来产生它。寄存器来产生它。 因为因为n级线性移位寄存器的输出序列级线性移位寄存器的输出序列ai满足递推关系：满足递推关系： an+k=c1an+k-1 c2a n+k-2 cnak，对任何，对任何k1成立。成立。 这种递推关系可用一个一元高次多项式这种递推关系可用一个一元高次多项式 p(x)=1+c1x+cn-1xn-1cnxn 表示，称这个多项式为表示，称这个多项式为LFSR的特征多项式。的特征多项式。 由于由于aiGF(2) (i =1, 2, n)，所以共有，所以共有2n组初始状态，

31、即有组初始状态，即有2n个递推序列，个递推序列，其中非恒零的有其中非恒零的有2n-1个，记个，记2n-1个非零序列的全体为个非零序列的全体为G(p(x)。27 定义定义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+an1xn-2) + c2x(a1+a2x+an2

32、xn-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序列。28 例例3：设设f(x)=x4+x3+x2+x+1是是GF(2)上的不可约多项式，但是它上的不可约多项式，但是它的输出序列是的输出序列是000110001100011，周期是，周期是5，不是，不是m序列。序列。

33、解：f(x)的不可约性由多项式x，x+1， x2+x+1不能整除f(x)而得。对于k5，输出序列用ak=ak-1a k-2a k-3ak4 检验即可。 定义定义4：仅能被非零常数或者本身的常数倍除尽，不能被其他多项式整除的多项式称为不可约多项式。 特征多项式满足什么条件时，特征多项式满足什么条件时，LFSR的输出序列为的输出序列为m序列。序列。 定理定理3：n级LFSR产生的序列有最大周期2n-1的必要条件是其特征多项式为不可约多项式。 该定理的逆不成立，即LFSR产生的特征多项式为不可约多项式，但其输出序列不一定是m序列。 29 定义定义5：若n次不可约多项式p(x)的阶为2n-1，称其为n

34、次本原多项式。 定理定理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序列具有良好的

35、伪随机性，序列具有良好的伪随机性，但是直接用其构造密钥流序列是极不安全的。因为利用但是直接用其构造密钥流序列是极不安全的。因为利用2n个输出位个输出位可以找到它的起始状态和特征多项式。可以找到它的起始状态和特征多项式。30 若特征多项式p(x)=x3+x+1，初始状态为（101）的移位寄存器产生序列为(101001)。 设明文为（011010），那么密文为（110011）。破译者计算mc得到密钥系列(101001)，那么可以得到下列矩阵方程式： 得到c31，c20，c11， 从而得到特征多项式：p(x)=x3+x+11 23342 34253 451 6k k kckk k kckk k kc

36、k321 101001001001ccc 31线性反馈移位寄存器举例线性反馈移位寄存器举例一个周期的输出序列一个周期的输出序列100010011010111 100010011010111 m m序列产生器序列产生器序列周期长，伪随序列周期长，伪随机特性好。机特性好。LFSRLFSR的结构过于简的结构过于简单，只要攻击者得单，只要攻击者得到到2n2n位密文和对应位密文和对应的明文，就可以导的明文，就可以导出出n n级级LFSRLFSR序列产生序列产生器的代数结构。器的代数结构。不适宜直接作为不适宜直接作为密密钥流产生器使用。钥流产生器使用。325.4 非线性序列简介 线性移位寄存器序列密码在已

37、知明文攻击下是可破译的这一事实促使线性移位寄存器序列密码在已知明文攻击下是可破译的这一事实促使人们向非线性领域探索。人们向非线性领域探索。目前研究的比较充分的由非线性移位寄存器，目前研究的比较充分的由非线性移位寄存器，对线性移位寄存器进行非线性组合等对线性移位寄存器进行非线性组合等。 为了使密钥流生成器输出的二元序列尽可能复杂，应保证其周期尽可为了使密钥流生成器输出的二元序列尽可能复杂，应保证其周期尽可能大、线性复杂度和不可预测性尽可能高，能大、线性复杂度和不可预测性尽可能高，因此常使用多个因此常使用多个LFSR来构造来构造二元序列，称每个二元序列，称每个LFSR的输出序列为驱动序列，的输出序

38、列为驱动序列，显然密钥流生成器输出显然密钥流生成器输出序列的周期不大于各驱动序列周期的乘积，序列的周期不大于各驱动序列周期的乘积，因此，提高输出序列的线性因此，提高输出序列的线性复杂度应从极大化其周期开始。复杂度应从极大化其周期开始。 1Geffe序列生成器序列生成器 Geffe序列生成器由序列生成器由3个个LFSR组成（如下图），其中组成（如下图），其中LFSR2作为控制生作为控制生成器使用。成器使用。33 当当LFSR2输出输出1时，时，LFSR2与与LFSR1相连接；当相连接；当LFSR2输出输出0时，时，LFSR2与与LFSR3相连接。相连接。 若设若设LFSRi的输出序列为的输出序列

39、为a(i)k (i=1,2,3)，则输出序列，则输出序列bk可以表可以表示为：示为： 123212323kkkkkkkkkkba aaaa aaaa3121ini1323nnnn设LFSRi的特征多项式分别为ni次本原多项式，且ni两两互素，则Geffe序列的周期为 ，线性复杂度为 。342J-K触发器触发器 其中，x1和x2分别是J和K端的输入。1211kkcxxcx J-K触发器如下图所示，它的两个输入端分别用J和K表示，其输出ck不仅依赖于输入，还依赖于前一个输出位ck-1，即001110122211012111cacabaacababaaa 在下图中，令驱动序列在下图中，令驱动序列ak

40、和和bk分分别为别为m级和级和n级级m序列，则有序列，则有 111kkkkkkkkkcabcaabca利用利用J-K触发器的非线性序列生成器触发器的非线性序列生成器 如果令如果令c-1=0，则输出序列的最，则输出序列的最初初3项为：项为： 当当m与与n互素且互素且a0+b0=1时，序列时，序列ck的周期为的周期为 (2m-1)(2n-1)。353Pless生成器生成器 Pless生成器由生成器由8个个LFSR、4个个J-K触发器和触发器和1个循环计数器构成，个循环计数器构成，由循环计数器进行选通控制，如下图所示。由循环计数器进行选通控制，如下图所示。 假定在时刻假定在时刻t输出第输出第t(mo

41、d 4)个单元，则输出序列为：个单元，则输出序列为： a a0 0 b b1 1 c c2 2 d d3 3 a a4 4 b b5 5 d d6 6365.钟控发生器钟控发生器 钟控发生器是由控制序列钟控发生器是由控制序列（由一个或多个移位寄存器来控制生成）（由一个或多个移位寄存器来控制生成）的当前值决定被采样的序列寄存器移动次数（即由控制序列的当前值的当前值决定被采样的序列寄存器移动次数（即由控制序列的当前值确定采样序列寄存器的时钟脉冲数目）。确定采样序列寄存器的时钟脉冲数目）。 控制序列和被采样序列可以是源于同一个控制序列和被采样序列可以是源于同一个LFSR（称为自控），也（称为自控），

42、也可以源于不同的可以源于不同的LFSR（称为他控），（称为他控），还可以相互控制还可以相互控制（称为互控）。（称为互控）。钟控发生器示意图如下图所示。钟控发生器示意图如下图所示。37 当控制序列当前值为当控制序列当前值为1时，被采样序列生成器被时钟驱动时，被采样序列生成器被时钟驱动k次后次后输出；输出；当控制序列当前值为当控制序列当前值为0时，被采样序列生成器被时钟驱动时，被采样序列生成器被时钟驱动d次次后输出。后输出。 另外，停走式发生器也是一种钟控模型，它由另外，停走式发生器也是一种钟控模型，它由2个个LFSR组成。组成。其中，其中，LFSR-1控制控制LFSR-2的时钟输入。的时钟输入。

43、 当且仅当当且仅当LFSR-1的时间的时间t-1的输出为的输出为1时，时，LFSR-2在时间在时间t改变改变状态（状态（也即也即LFSR-1输出时钟脉冲，使输出时钟脉冲，使LFSR-2进行输出并反馈以改进行输出并反馈以改变移位寄存器的状态变移位寄存器的状态）。）。 385收缩和自收缩发生器收缩和自收缩发生器 收缩发生器是又控制序列的当前值决定被采样序列移位寄存器收缩发生器是又控制序列的当前值决定被采样序列移位寄存器是否输出。是否输出。 该发生器由该发生器由2个个LFSR组成。组成。LFSR-1、LFSR-2分别按各自时钟分别按各自时钟运行，运行，LFSR-1在时间在时间t-1时刻的输出为时刻的

44、输出为1时，时，LFSR-2在时间在时间t时刻输时刻输出为密钥流，否则舍去。出为密钥流，否则舍去。 自收缩发生器从一个自收缩发生器从一个LFSR抽出抽出2条序列，其中一条为控制序列条序列，其中一条为控制序列，另一条为百采样序列。，另一条为百采样序列。当控制序列输出为当控制序列输出为1时，采样序列输出为时，采样序列输出为密钥流，否则舍去。密钥流，否则舍去。 此外，还有多路复合序列，这类序列也归结为非线性组合序此外，还有多路复合序列，这类序列也归结为非线性组合序列。列。39 基于基于LFSR的序列密码非常适合于硬件实现，但是不特别适合软的序列密码非常适合于硬件实现，但是不特别适合软件实现。件实现。

45、这导致出现了一些关于序列密码被计划用于快速软件实这导致出现了一些关于序列密码被计划用于快速软件实现的新建议，因为这些建议大部分具有专利，因此这里不讨论它现的新建议，因为这些建议大部分具有专利，因此这里不讨论它们的技术细节。们的技术细节。 比较常用的序列密码是比较常用的序列密码是A5、SEAL和和RC4序列密码算法，序列密码算法，A5是典是典型的基于型的基于LFSR的序列密码算法，的序列密码算法，SEAL和和RC4不是基于不是基于LFSR的的序列密码算法，而是基于分组密码的输出反馈模式（序列密码算法，而是基于分组密码的输出反馈模式（OFB）和密）和密码反馈模式（码反馈模式（CFB）来实现的。）来

46、实现的。其他不基于其他不基于LFSR的序列密码生的序列密码生成器的安全性基于数论问题的难解性，这些生成器比基于成器的安全性基于数论问题的难解性，这些生成器比基于LFSR的生成器要慢很多。的生成器要慢很多。40 A5序列密码算法是利用欧洲数字蜂窝移动电话（序列密码算法是利用欧洲数字蜂窝移动电话（GSM）加密的）加密的序列密码算法，它用于从用户手机至基站的连接加密，序列密码算法，它用于从用户手机至基站的连接加密，GSM会会话每帧数据包含话每帧数据包含228比特，比特，A5算法每次会话将产生算法每次会话将产生228比特的密比特的密钥，算法的密钥长度为钥，算法的密钥长度为64比特，还包含有一个比特，还

47、包含有一个22比特的帧数。比特的帧数。A5算法有两个版本：强算法有两个版本：强A5/1和弱和弱A5/2。 A5算法是一种典型的基于算法是一种典型的基于LFSR的序列密码算法，它由三个的序列密码算法，它由三个LFSR组成，是一种集控制与停走于一体的钟控模型，但是组成，是一种集控制与停走于一体的钟控模型，但是A5算算法没有完全公开，因而各种资料的描述也不尽相同，重要是第二法没有完全公开，因而各种资料的描述也不尽相同，重要是第二个和第三个个和第三个LFSR的联接多项式以及钟控的位置。的联接多项式以及钟控的位置。 A5算法的算法的3个个LFSR中中LFSR-1、LFSR-2、LFSR-3的级数分别为的

48、级数分别为19、22和和23。LFSR-1的反馈抽头是的反馈抽头是18、17、16、13，LFSR-2的的反馈抽头是反馈抽头是21、20、16、12，LFSR-3的反馈抽头是的反馈抽头是22、21、18、17（如下页图的数字表示抽头的位置）。（如下页图的数字表示抽头的位置）。 414243SEAL序列密码算法444546474849 5.5.3 RC4序列密码体制o RC4是是Ron Rivest 1987年为年为RSA设计，是一设计，是一个可变密钥长度、面向字节操作的序列密码个可变密钥长度、面向字节操作的序列密码o 基本思想：基本思想： 对于对于n n位长的字，它总共位长的字，它总共N=2N

49、=2n n个可能的个可能的内部置换状内部置换状 态矢量态矢量S S，这些状态是保密的，密钥，这些状态是保密的，密钥流流K K由由S S中中N N个元素按照一定方式选出一个元素而生个元素按照一定方式选出一个元素而生成。每生成一个成。每生成一个K K值，值，S S中的元素就被重新置换一次中的元素就被重新置换一次o 密钥调度算法（密钥调度算法（KSA）o 伪随机数生成算法（伪随机数生成算法（PRGA）50密钥调度算法KSAo KSA算法描述如下：o For i=0 to N-1 doo Si=i;o j=0;o For i=0 to N-1 doo J=(j+Si+KI mod L) mod N;o

50、 Swap(Si,Sj)51伪随机数生成算法PRGAo i=0；o J=0；o While(true）o i=（i+1）mod N；o J=（j+Si) mod N;o Swap(Si,Sj);o T=(Si+Sj) mod N;o Output k=St;52实例535455oRC4目前使用在：o （1）SSL（安全套接字）中广泛使用o （2）WEP(Wired Equivalent Privacy:有线对等保密) IEEE 802.11o(http:/ 真随机序列的特性真随机序列的特性 统计的随机性。即序列能够通过数学上已知的所有统计的随机性。即序列能够通过数学上已知的所有的随机性检验，满

51、足这个要求的序列称为伪随机序列。的随机性检验，满足这个要求的序列称为伪随机序列。 不可预测性。即无论采用何种方法，也无法根据以不可预测性。即无论采用何种方法，也无法根据以前的任意多元素预测序列的下一个元素。前的任意多元素预测序列的下一个元素。 不可再生性。即使使用完全相同的输入参数，也无不可再生性。即使使用完全相同的输入参数，也无法产生完全相同的输出序列。法产生完全相同的输出序列。真随机序列特性虽好，但难以在实际密码系统中应用。真随机序列特性虽好，但难以在实际密码系统中应用。实际密码系统中使用的密钥流都是伪随机序列。实际密码系统中使用的密钥流都是伪随机序列。57三、密钥流的局部随机性检验三、密

52、钥流的局部随机性检验 1 1、伪随机序列的统计特性、伪随机序列的统计特性 戈龙（戈龙（GolombGolomb）提出的三条随机性公设：）提出的三条随机性公设： 平衡特性。任何随机的二元周期序列，在一个周平衡特性。任何随机的二元周期序列，在一个周期期P P内，不同元素出现的概率应该是相同的。如果内，不同元素出现的概率应该是相同的。如果P P为为偶数，一个周期内所含有的偶数，一个周期内所含有的“0 0”和和“1 1”的个数应该相的个数应该相等；如果等；如果P P为奇数，一个周期内所含有的为奇数，一个周期内所含有的“0 0”和和“1 1”的个数应该只相差的个数应该只相差1 1个。个。58戈龙（戈龙（

53、GolombGolomb）提出的三条随机性公设）提出的三条随机性公设 游程特性。游程特性。游程是指一串相同的元素序列，其前导和后继都不同，游程是指一串相同的元素序列，其前导和后继都不同，而相同元素的个数叫做游程的长度。而相同元素的个数叫做游程的长度。由一串由一串“1 1”构成的游程叫做构成的游程叫做“1 1”游程（也叫块组），游程（也叫块组），由一串由一串“0 0”构成的游程叫做构成的游程叫做“0 0”游程（也叫间隔）。游程（也叫间隔）。例如，序列例如，序列“11100101110010”有有1 1个长度为个长度为3 3的的“1 1”游程游程（111111）、）、1 1个长度为个长度为2 2的

54、的“0 0”游程（游程（0000）、）、1 1个长度为个长度为1 1的的“1 1”游程（游程（1 1）和）和1 1个长度为个长度为1 1的的“0 0”游程（游程（0 0）。）。任意随机的二元周期序列，在一个周期任意随机的二元周期序列，在一个周期P P内，长度为内，长度为n n的游程数应占游程总数的的游程数应占游程总数的1/21/2n n，并且对于每一种长度，并且对于每一种长度，“0 0”游程的个数应和游程的个数应和“1 1”游程的个数同样多。游程的个数同样多。 59戈龙（戈龙（GolombGolomb）提出的三条随机性公设）提出的三条随机性公设 自相关特性。假定自相关特性。假定S S是一个周期

55、为是一个周期为P P的二元序列，对于任意的二元序列，对于任意固定的固定的，把，把S S的开始的开始P P项（即一个周期）和其平移项（即一个周期）和其平移（一个周（一个周期循环左移期循环左移位）后的序列进行比较，并用位）后的序列进行比较，并用A A表示它们对应位表示它们对应位相同的个数，用相同的个数，用D=P-AD=P-A表示它们对应位不同的个数，定义自相表示它们对应位不同的个数，定义自相关函数为：关函数为：PDAC)(任意随机的二元周期序列，其自相关函数应为任意随机的二元周期序列，其自相关函数应为 1;0( );0C常数自相关特性也可以表述为：异相自相关函数是一个常数。自相关特性也可以表述为：

56、异相自相关函数是一个常数。 602 2、密钥流的局部随机性检验、密钥流的局部随机性检验 频数检验频数检验序列检验序列检验扑克检验扑克检验自相关检验自相关检验游程检验游程检验 612 2、密钥流的局部随机性检验、密钥流的局部随机性检验 （1 1）频数检验）频数检验用来确保密钥流有大致相等数量的用来确保密钥流有大致相等数量的“0 0”和和“1 1”。假设被检验序列的长度为假设被检验序列的长度为n n比特，其中有比特，其中有n n0 0个个“0 0”和和n n1 1个个“1 1”，计算，计算 nnnx2012)(的数值并和的数值并和1 1自由度的自由度的 分布表中分布表中5%5%显著性水显著性水平值平值3.8413.841进行比较。若进行比较。若 ，则认为通，则认为通过了频数检验，否则，必须舍弃该序列。过了频数检验，否则，必须舍弃该序列。2x23.841x 622 2、密钥流的局部随机性检验、密钥流的局部随