3.8 随机数

在结束本章，介绍公钥密码之前，最后再补充介绍一下随机数的产生，因为在RSA算法中密钥的产生要用到随机数的产生方法。此外，本书后面将要介绍的其他基于密码学的安全算法和协议也要用到随机数，例如：鉴别过程中，避免重放攻击的非重复值、用于一次性使用的会话密钥。

随机数发生器已经嵌入在大多数的编译器中了，这种随机数发生器产生的随机数可以用在密码中吗？这种随机数发生器对密码来说几乎肯定是不安全的，因为这种随机数发生器并不是完全随机的。之所以在广泛使用这样的伪随机数发生器，是因为大多数的简单应用并不需要真随机数。在计算机上是不可能产生真正的随机数的，因为它只能处于有限的状态，尽管这个数很大，其输出是输入和计算机当前状态的函数。也就是说任何计算机上的随机数发生器都是周期的。著名的计算机科学家冯·诺依曼对此有一个结论，任何人考虑用数学方法产生随机数肯定是不合情理的。

对于随机数序列可以分为如下几种：

伪随机数序列：看起来是随机的序列，它能通过现有的一些随机性统计检验，序列的周期足够长，使得实际应用中相当长的有限序列都不是周期性的。对于随机序列的随机性有两个评价标准，一个是分布的均匀性，即随机数的分布应是一致的，出现频率大致相等；另一个是独立性，即序列中的任何数不能由其他数推导出。分布均匀性检验我们使用χ2拟合优度检验法；独立性常用游程检验法检验。密码算法中大量使用了这种似乎随机的随机数序列，如RSA算法中的密钥产生过程。

密码学意义上安全的伪随机序列：除了随机性，它还应该是不可预测的。在相互鉴别或会话密钥生成之类的应用中，对随机数的统计随机性要求并不很高，但是要求产生的随机数序列是不可预测的，即使给出序列的算法或硬件以及该序列所有前面的位，也很难预测下一个随机位。

真随机序列：如果序列除了具有与随机序列相同的统计特性，它还具有不能重复产生的特性，那么它就是真正随机的了。如果用完全相同的输入对序列发生器操作两次，你将得到两个不相关的随机序列。

3.8.1 真随机序列产生器

真随机数只能来源于自然界，下面将给出几种真随机序列的例子。

3.8.1.1 RAND表

1955年，Rand公司出版了一本包括100万个随机数的书。书中的随机数通过电子转轮产生的基本表再进行随机化获得。随机数字表，以5位数字组的形式列出，“100973253376520 …”一行50个数字，一页50行。行编号从00000到19999。使用该表时首先应寻找一个随机起始位置。一种办法是随机翻到一页，随机选取一个5位数，用个位数字模2来决定起始行，用右边两位数字模50来确定起始行中的起始列。每一个被确定起始位置的数字应做上标记，避免重复使用。

3.8.1.2 使用随机噪声

采集大量随机数的最好办法是利用现实世界的自然随机性，这种方法通常需要一个特定的硬件，但仍需要一定的计算机技巧。例如：寻找一个有规律但又随机的事件：如超过某一门限值的大气噪声。测量并记录相邻时间的间隔，如果第一个时间间隔大于第二个时间间隔，输出1；如果第一个时间间隔小于第二个时间间隔，输出0。然后重复。

3.8.1.3 使用计算机时钟

如果想要一个单独的随机位，可以取任意一个时钟寄存器的最低位。UNIX系统中由于存在各种同步机制可能使时钟寄存器的最低位不随机，但这在某些个人计算机上是可以实现的。这种方法不适于取很多位。例如，如果每个子程序在一个奇数时钟执行，则会得到一个无休止的与上一个程序各位相反的序列，这样一来，结果就不是随机的了。

3.8.1.4 测量键盘反应时间

人们的打字方式有随机和非随机的，非随机方式可用做身份识别。测量两次击键的时间间隔，然后取这些测量的最低有效位。这一技术在UNIX终端上不可行，因为击键信息要经过过滤和其他机制方能进入程序，但在个人计算机上是可行的。因此，该技术有一定局限性。

3.8.2 伪随机数产生器

目前计算机所能生成的是伪随机序列发生器（Pseudo Random Sequence Generator）。它看起来是随机的，实际却是周期的，只不过周期足够长，使实际使用的那个序列不是周期的。应该根据所需要的随机序列的长度选择随机序列发生器。评价随机数产生器的一般准则如下：

● 这个函数应该是一个完整周期的产生函数，这个函数在重复之前产生出0到m之间的所有数。

● 产生的序列应该看起来是随机的。

● 这个函数应该用32位算术高效实现。

3.8.2.1 线性同余发生器（Linear Congruential Generator）

到现在为止，使用最广泛的产生伪随机数的方法是Lehmer首先提出的算法，即线性同余法。随机数序列{Xn}按下面的迭代方程获得：

Xn+1 =（aXn+c）mod m

算法中的参数如下：

每个随机数满足0 ≤ Xn<m。m，a，c的选择对于算法非常关键。m一般很大，如与给定的计算机能表示的最大整数接近，对于32位计算机，m = 231-1，这时取c = 0，a的取值有很多，但能满足上述准则的只是其中一部分，a = 75 =16807时满足上述条件，并经过广泛的测试和检验。选定上述参数，改变种子X0就能产生不同的伪随机数序列。这样产生的伪随机数速度快，但缺乏不可预测性。

3.8.2.2 BBS伪随机数产生器

BBS发生器是现在产生安全伪随机数的普遍方法，它的产生过程如下：首先选择两个大素数p和q，且要求p ≡ q ≡ 3（mod 4），接着选择s与n互素，n=p×q，然后按下列算法产生随机数 序列

BBS被称为密码安全伪随机数发生器，它通过了“下一位”测试（next-bit test），即不存在多项式时间的算法使得在已知前k位的情况下预测出第k+1位的概率大于0.5，BBS的安全性基于分解n的难度。

3.8.3 基于密码编码方法的随机数

3.7节给出了分组加密的流密码工作模式，在OFB和CTR模式中，分组加密的输出被作为密钥流与明文进行异或，连续的b位输出构成了有着良好统计性质的伪随机序列。