第4章 序列密码体制
目前生成随机数的几种硬件设备都是用于商业用途。得到 广泛使用的设备是ComScireQNG，它是使用并行端口连接到PC 的外部设备，它可以在每秒钟生成20000位，这对于大多数注 重安全性的应用程序来说已经足够了。
另外，Intel公司宣布他们将开始在其芯片组中添加基于 热能的硬件随机数发生器，而且基本上不会增加客户的成本。 迄今为止，已经交付了一些带有硬件RNG的CPU。
第4章 序列密码体制
现在，无论他再拦截到什么密文消息，他都可以用她所拥 有的密钥流进行解密。另外，他还可以解密，并阅读以前截获 到的消息。一旦Alice得到一明文—密文对，他就可以读懂任 何东西了。
这就是为什么所有序列密码也有密钥的原因。密钥流发生 器的输出是密钥的函数。这样，Alice有一个明文—密文对， 但他只能读到用特定密钥加密的消息。更换密钥，攻击者就不 得不重新分析。序列密码算法对加密那些永不结束的通信数据 流是特别有用的：如两台计算机之间的T1连接。
每一存储器称为移位寄存器的一级，在任一时刻，这些级 的内容构成该反馈移位寄存器的状态，每一状态对应于GF(2) 上的一个n维向量，共有2n种可能的状态。
每一时刻的状态可用n长序列“a1，a2，…，an”的n维向 量“(a1，a2，…，an)”来表示，其中ai是第i级存储器的内容。
第4章 序列密码体制 在解密端，密文流与完全相同的密钥流异或运算恢复出明
文流。
Pi =Ci⊕K i
（4-2）
由于，Pi? K i? K i = P i , 所以，该方式是正确的。
系统的安全性完全依靠密钥流发生器的内部机制。如果它 的输出是无穷无尽的“0”序列，那么密文就是明文，系统没有 加密功能。如果它产生的是一个重复性的16比特模式，那么该 算法仅是一个可忽略安全性的异或运算。如果是一系列无尽的 随机流，那就是一次一密乱码本和非常完美的安全。
第4章 序列密码体制
2．使用硬件方法的随机数产生器 真正的随机数发生器是非确定的，在计算机上执行非确定 性事情的唯一方法是从一些自然的随机过程中收集数据。最好 的一种方法涉及使用电子Geiger计数器，每次当它检测到放 射性衰变时，它就会生成一个脉冲。衰变之间的时间是一个实 足的、纯粹的随机部分。尤其是，没有人可以预测到下一次衰 变的时间大于还是小于自上次衰变以来的时间。那就产生了一 位随机信息。
第4章 序列密码体制
（2）它是不可预测的。即使给出产生序列的算法或硬件 和所有以前产生的比特流的全部知识，也不可能通过计算来预 测下一个随机比特应是什么。
（3）它不能可靠地重复产生。如果用完全同样的输入对 序列产生器操作两次将得到两个不相关的随机序列。
第4章 序列密码体制 4.2 序列密码的概念及模型
第4章 序列密码体制 4.3 线性反馈移位寄存器
移位寄存器是流密码产生密钥流的一个主要组成部分。 GF(2)上一个n级反馈移位寄存器由n个二元存储器与一个反馈 函数f(a1，a2，…，an)组成，如图4－3所示。
第4章 序列密码体制 图4－3 GF(2)上的n级反馈移位寄存器
第4章 序列密码体制
第4章 序列密码体制
发生器的周期必须非常长，要比密钥更换之前发生器所能 输出的位的长度还要长得多。如果其周期比明文还要短，那么 明文的不同部分将用同样的加密——这是一个严重的弱点。如 果密码分析者熟悉这样的一批明文，他就可以恢复出密钥流， 然后恢复出更多的明文。即使分析者仅有密文，他也可以用同 一密钥流加密的不同部分密文相异或得到明文跟明文的异或。 这只是一个有非常长密钥的单一异或运算罢了。
第4章 序列密码体制
4.1.4 伪随机数的评价标准 如果一序列产生器是伪随机的，它应有下面的性质： （1）看起来是随机的，表明它可以通过所有随机性统计
检验。 现在有许多统计测试。它们采用了各种形式，但共同思路
是它们全都以统计方式检查来自发生器的数据流，尝试发现数 据是否是随机的。
确保数据流随机性的最广为人知的测试套件就是 GeorgeMarsaglia的DIEHARD软件包（请参阅 /pub/diehard/）。另一个适合此 类测试的合理软件包是pLab（请参阅 http://random.mat.sbg.ac.at/tests/）。
序列密码算法将明文逐位转换成密文。该算法最简单的应 用如图4－1所示。密钥流发生器（也称为滚动密钥发生器）输 出一系列比特流：K1，K2，K3，…，Ki。密钥流（也称为滚动 密钥）跟明文比特流P1，P2，P3，…，Pi，进行异或运算产生 密文比特流，即
Ci =Pi⊕K i
（4－1）
பைடு நூலகம்
第4章 序列密码体制 图4－1 序列密码
第4章 序列密码体制
第4章 序列密码体制
4.1 密码学中的随机数 4.2 序列密码的概念及模型 4.3 线性反馈移位寄存器 4.4 非线性序列简介 4.5 常用的序列密码算法
第4章 序列密码体制
4.1 密码学中的随机数 为什么在密码学中要讨论随机数的产生？因为许多密码系 统的安全性都依赖于随机数的生成，例如DES加密算法中的密 钥，RSA加密和数字签名中的素数。所有这些方案都需要足够 长度并且要“随机”的数，即使得任何特定值被选中的概率足 够小，防止对方根据概率来优化搜索策略。例如DES密钥空间 大小为256，如果密钥k是随机产生的，那么对方要尝试256个可 能的密钥值。但是如果密钥k这样产生：选取一个16位随机秘 钥s，然后利用一个复杂但是公开的函数f将其扩展为56位密 钥k，这时对方只要尝试216个可能的密钥值就能找到真正密钥。
第4章 序列密码体制 实际的序列密码算法其安全性依赖于简单的异或运算和一
次一密乱码本。密钥流发生器生成的看似随机的密钥流实际上 是确定的，在解密的时候能很好地将其再现。密钥流发生器输 出的密钥越接近随机，对密码分析者来说就越困难。
如果密钥流发生器每次都生成同样的密钥流的话，对攻击
假的Alice得到一份密文和相应的明文，他就可以将两者 异或恢复出密钥流。或者，如果他有两个用同一个密钥流加密 的密文，他就可以让两者异或得到两个明文互相异或而成的消 息。这是很容易破译的，接着他就可以用明文跟密文异或得出 密钥流。
第4章 序列密码体制
1．自同步序列密码 自同步序列密码就是密钥流的每一位是前面固定数量密文 位的函数，图4－2描述了其工作原理。其中，内部状态是前面 n比特密文的函数。该算法的密码复杂性在于输出函数，它收 到内部状态后生成密钥序列位。 因为内部状态完全依赖前面n个密文位，所以解密密钥流 发生器在收到n个密文位后自动跟加密密钥流发生器同步。 在该模式的智能化应用中，每个消息都以随机的n位报头 开始。这个报头被加密、传输、解密，在n位密文之前整个解 密是不正确的，直到之后两个密钥流发生器同步。
第4章 序列密码体制
4.1.1 随机数的使用 序列密码的保密性完全取决于密钥的随机性。如果密钥是
真正的随机数，则这种体制在理论上就是不可破译的。但这种 方式所需的密钥量大得惊人，在实际中是不可行的。因此，目 前一般采用伪随机序列来代替随机序列作为密钥序列，也就是 序列存在着一定的循环周期。这样序列周期的长短就成为保密 性的关键。如果周期足够长，就会有比较好的保密性。现在周 期小于1010的序列很少被采用，周期长达1050的序列也并不少 见。
伪随机数生成器是一个生成完全可预料的数列（称为流） 的确定性程序。一个编写得很好的PRNG可以创建一个序列， 而这个序列的属性与许多真正随机数的序列的属性是一样的。 例如：
第4章 序列密码体制
（1）PRNG可以以相同几率在一个范围内生成任何数字； （2）PRNG可以生成带任何统计分布的流； （3）由PRNG生成的数字流不具备可辨别的模。
第4章 序列密码体制
4.1.3 基于密码算法的随机数产生器 1．使用软件方法的随机数产生器 一个常用的随机数产生器是属于线性拟合生成器一类的。
这类生成器相当普遍，它们采用很具体的数学公式： Xn+1=(aXn+b)mod c即第n+1个数等于第n个数乘以某个常数a， 再加上常数b。如果结果大于或等于某个常数c，那么通过除以 c，并取它的余数来将这个值限制在一定范围内。注意，a、b 和c通常都是质数。DonaldKnuth在 “TheArtofComputerProgramming”一书中详细介绍了对于这 些常数，如何挑选好的值。
周期需要多长取决于应用。用于加密连续T1连接通信的密 钥发生器每天加密237比特。那么它的周期应该比这个数大几 个数量级，尽管密钥每天都要更换。如果周期足够长，你仅仅 需要每周甚至每月才更换密钥一次。
第4章 序列密码体制
同步序列密码同样可防止密文中的插入和删除，因为它们 会使系统失去同步而立即被发现。然而，却不能避免单个位被 窜改。就像CFB模式下的分组密码算法，Mallory更换数据流 中的某个比特，如果他熟悉明文，他就可以使那些比特被解密 成他想要的。后面的比特仍被正确地解密，所以在很多应用中 Mallory仍可进行某些毁坏。
第4章 序列密码体制
这也有好的一面，同步密码并不扩散传输错误。如果有一 位在传输中改变了，比丢失一位可能性大的多，那么只有该位 不能正确解密。所有进程和结果都不会受影响。
由于在加解密两端密钥流发生器必须产生同样的输出，所 以它必须是确定的。因为它是用有限状态机器实现的（如计算 机），密钥序列终会重复。这些密钥流发生器被称为是周期性 的。除一次一密乱码本外，所有密钥流发生器都是周期性的。
第4章 序列密码体制
自同步密码的缺点是错误扩散。传输中每一个密文位被窜 改，解密密钥流发生器就有n位密钥流位不能正确生成。因此， 一位密文错误就会导致n位相应的明文错误，直到内部状态里 面不再有该错误位。
第4章 序列密码体制 图4－2 自同步密钥流发生器
第4章 序列密码体制
2．同步序列密码 在同步序列密码中密钥流是独立于消息流而产生的。加密 端密钥流发生器一位接一位地产生密钥，在解密端另一个发生 器产生出完全相同的密钥。两个密钥发生器同步以后，这种一 致就开始了。如果其中一个发生器跳过一个周期或者一个密文 位在传输过程中丢失了，那么错误后面的每一个密文字符都不 能正确解密。 如果错误不幸发生了，发方和收方就必须在继续进行之前 使两个密钥发生器重新同步。他们必须这样做以保证密钥流的 任意部分不会重复，重新设置发生器回到前一个状态，然而这 个简单的法子是不行的。