2.8 随机和伪随机序列的产生
为什么在一本关于密码学的书中还不厌其烦地谈论随机数产生呢？随机数产生器已嵌入在大多数编译器中了，产生随机数仅仅是函数调用而已。为什么不用编译器的那种呢？ 不幸的是，那些随机数产生器对密码来说几乎肯定是不安全的，甚至可能不是很随机的。它们中的大多数都是非常差的随机数。
随机序列产生器并不是随机的，因为它们不必要是完全随机的。像计算机游戏，大多数简单应用中只需几个随机数，几乎无人注意到它们，然而密码学对随机数产生器的性质是极其敏感的。用粗劣的随机数产生器，你会得到十分奇妙的相关和奇怪的结果[1231，1238]。如果安全性依赖于你的随机数发生器，那么你得到的最后的东西就是这种奇妙的相关和结果。
随机数产生器不能产生随机序列，它甚至可能产生不了乍看起来像随机序列的数。当然，在计算机上不可能产生真正的随机数。Donald Knuth引用John Von Neumann的原话：“任何人考虑用数学的方法产生随机数肯定是不合情理的”。计算机确是怪兽：数据从一端进入，在内部经过完全可预测的操作，从另一端出来的却是不同的数据；把同一数据在不相干情况下输入进去，两次出来的数据是相同的；把同样的数据送入相同的两个计算机，它们的运算结果是相同的。计算机只能是一个有限的状态数（一个大数，但无论如何是有限的），并且输出状态总是过去的输入和计算机当前状态的确定的函数。这就是说计算机中的随机序列产生器（至少，在有限状态机中）是周期性的，周期性的任何东西都是可预测的。如果是可预测的，那么它就不可能是随机的。真正的随机序列产生器需要随机输入，计算机不可能提供这种随机输入。
伪随机序列
最好的计算机能产生的是伪随机序列产生器，什么意思呢？许多人试图形式化地定义它，但我不赞成，随机数序列是看起来是随机的序列，序列的周期应足够长，使得实际应用中相当长的有限序列都不是周期性的。就是说如果你需要十亿个随机比特，就不要选择仅在一万六千比特后就重复的序列产生器。这些相对短的非周期性的子序列应尽可能和随机序列没有多少区别。例如：它们应该有大约相同数目的0和1，长度为1的游程大约占一半（同一比特序列），长度为2的游程占1/4，长度为3的游程占1/8等等。它们应该是不可压缩的，0和1游程的分布应该是相同的[643，863，99，1357]。这些性质是根据实验测得的，然后用chi-square检验与统计期望值比较。
我们的意思是，如果一序列产生器是伪随机的，它应有下面的性质：
（1）看起来是随机的，这表明它通过了我们所能找到的所有随机性统计检验（开始[863]中的检验）。
人们在计算机上已经做了许多努力来产生好的伪随机序列，学术文献中有很多讨论伪随机序列产生器和各种随机性检验的，但所有这些产生器是周期的（都不可能例外）。然而周期大于2256比特的随机数序列，能够大量得到应用。
这里的关键问题还是那些奇妙的相关性和奇怪的结果。如果你以某种方式使用它们，则每个随机数序列产生器都将产生这些结果。这正是为什么密码分析者用它来对系统进行攻击的原因。
密码学意义上安全的伪随机序列
密码的应用比其他大多数应用对伪随机序列的要求更严格。密码学的随机性并不仅仅意味着统计的随机性，虽然它也是其中的一部分。密码学意义上安全的伪随机数，还必须具有下面的性质：
（2）它是不可预测的。即使给出产生序列的算法或硬件和所有以前产生的比特流的全部知识，也不可能通过计算来预测下一个随机比特应是什么。
密码学意义上安全的伪随机序列应该是不可压缩的……除非你知道密钥。密钥通常是用来设置产生器的初始状态的种子。
像任何密码算法一样，密码学意义上安全的伪随机序列产生器也会受到攻击，就好像加密算法有可能被破译一样，破译密码学意义上安全的伪随机序列产生器也是可能的。密码学讲的都是关于如何使产生器抵抗攻击。
真正的随机序列
现在我们走进哲学家的领域，真有随机数这样的东西吗？随机序列是什么？你怎么知道序列是随机的？“101110100”比“101010101”更随机吗？量子力学告诉我们，在现实世界中有真正的随机性。但是在计算机芯片和有限状态机的确定世界中，这种随机性还能保持吗？
暂且不说哲学。从我们的观点来说，如果一个随机序列产生器具有下面的第三条性质，它就是真正随机的：
（3）它不能可靠地重复产生。如果你用完全同样的输入对序列产生器操作两次（至少与人所能做到的最精确的一样），你将得到两个不相关的随机序列。
满足这三条性质的产生器的输出对于一次一密乱码本、密钥的产生和任何其它需要真正随机数序列产生器的密码应用来说都是足够好的。难点在于确定真正的随机数。如果我用一个给定的密钥，用DES算法重复地对一个字符串加密，我将得到一个好的，看起来随机的输出。但你仍不可能知道它是否真的随机数，除非你租用美国国家安全局的DES破译专家。