8.随机数

随机数的用途

• 生成密钥——用于对称密码和消息认证码
• 生成密钥对——用于公钥密码和数字签名
• 生成初始化向量（IV）——用于分组密码的CBC、CFB和OFB模式
• 生成nonce——用于防御重放攻击以及分组密码的CTR模式等
• 生成盐——用于基于口令的秘密（PBE）等

随机数的性质

随机数的性质分为三类：

• 随机性——【弱伪随机数】不存在统计学偏差，是完全杂乱的数列
• 不可预测性——【强伪随机数】不能从过去的数列推测出下一个出现的数
• 不可重现性——【真随机数】除非将数列本身保存下来，否则不能重现相同的数列

密码技术中所使用的随机数至少要具备不可预测性。

随机性

randomness

如果伪随机数列中不存在统计学偏差，则认为这个伪随机数列是随机的。判断方法称为【随机数测试】。

密码技术中所使用的随机数，仅仅具备随机性是不够的。

杂乱无章并不代表不会被看穿，所以，仅具备随机性的伪随机数称为 弱伪随机数 。

不可预测性

unpredictability，un（否定）-pre（之前）-dict（说）-ability（可能性），【不可能事先说中】，即，不可预测性。

指，攻击者在知道过去生成的伪随机数列的前提下，依然无法预测出下一个生成出来的伪随机数。

伪随机数生成器的算法是公开的，但伪随机数的种子（用于生成伪随机数的初始值）是保密的。

不可预测性是通过使用其他的密码技术来实现的。

具有不可预测性的伪随机数称为 强伪随机数 。

不可重现性

指，无法重现和某一随机数列完全相同的数列的性质。

仅靠软件是无法生成出具备不可重现性的随机数列的。软件只能生成伪随机数列。

运行软件的计算机本身仅具备有限的内部状态，在内部状态相同的条件下，软件必然只能生成相同的数，因此软件所生成的数列在某一时刻一定会出现重复。首次出现重复之前的数列长度称为 周期 ，对于软件所生成的数列，其周期必定是有限的。凡是具有周期的数列，都步具备不可重现性。

要生成具备不可重现性的随机数列，需要从不可重现的物理现象中获取信息，比如周围的温度和声音的变化、用户移动鼠标的位置信息、键盘输入的时间间隔、放射线测量仪的输出值等，根据从这些硬件中所获取的信息而生成的数列，一般可以认为是具备不可重现性的随机数列。

例如，Intel新型CPU中内置了数字随机数生成器，并提供了生成不可重现的随机数的RDSEED指令，以及生成不可预测的随机数的RDRAND指令。

具有不可重现性的随机数称为 真随机数 。

伪随机数生成器

通过硬件生成的随机数列，是根据传感器收集的热量、声音的变化等事实上无法预测和重现的自然现象信息来生成的、这类硬件设备称为 随机数生成器 （Random Number Generator，RNG）。

可以生成随机数的软件则称为 伪随机数生成器 （Pseudo Random Number Generator，PRNG）。

仅靠软件无法生成真随机数。

伪随机数生成器的结构

伪随机数生成器具有【内部状态】，并根据外部输入的【种子】来生成伪随机数列。

内部状态是指伪随机数生成器所管理的内存中的数值。

内部状态决定了下一个生成的伪随机数，因此不能被攻击者知道。

伪随机数生成器的种子

为了生成伪随机数，生成器需要被称为 种子 （seed）的信息。

种子是用来对伪随机数生成器内部状态进行初始化的。

种子不可以被攻击者知道，因此不可以使用容易被预测的值，比如当前时间。

具体的伪随机数生成器

杂乱的方法

使用复杂算法所生成的数列大多都会具有很短的周期（即短数列的不断重复），不符合不可预测性。

如果程序员不能理解算法的详细内容，就无法判断所生成的随机数是否具备不可预测性。

线性同余法

linear congruential method——线性同余法，是一种广泛使用的伪随机数生成器算法，但它不具备不可预测性，所以不能用于密码技术 。

其原理：

假设要生成的伪随机数列为 R₀ 、 R₁ 、 R ₂ ...。

首先根据伪随机数的种子，用下列公式计算第一个伪随机数R₀ ：

R₀ = （A x 种子 + C） mod M

此处，A 、C 、M都是常量，且 A 和 C 需要小于 M 。

接下来，根据R₀ 用同样的公式计算下一个伪随机数R₁ 。

R₁ = （A x R₀ + C） mod M

接下来再用同样的方法，根据当前的伪随机数 R_n 计算下一个伪随机数 R_n+1 :

R_n+1 = （A x R_n + C） mod M

简而言之，线性同余法就是 将当前的伪随机数值乘以 A 再加上 B ，然后将除以 M 得到的余数作为下一个伪随机数。

最近一次生成的伪随机数的值就是内部状态，伪随机数的种子被用来对内部状态进行初始化。

由于伪随机数是数以 M 得到的余数，因此其范围必定为 0 ~ M-1，而且，根据A、C、M的值，最终只能生成上述范围的一部分值（因此周期会缩短）。例如，当A=6 C=0 M=7，且种子为6时，周期为2。

在线性同余法中，只要谨慎选择A、C、M的值，就能够很容易地生成具备随机性的伪随机数列。

但它不具备不可预测性，故而 不能用于密码技术 。

很多伪随机数生成器的库函数（library function）都是采用线性同余法编写的。例如C语言的库函数 rand ，以及 Java 的 java.util.Random 类等，都采用了线性同余法。因此这些函数是不能用于密码技术的。

单向散列函数法

使用单向散列函数（如SHA-1）可以编写出能够生成具备不可预测性的伪随机数列（即强伪随机数）的伪随机数生成器。

工作方式如下：

1. 用伪随机数的种子初始化内部状态（计数器）
2. 用单向散列函数计算计数器的散列值
3. 将散列值作为伪随机数输出
4. 计数器的值加1
5. 根据需要的伪随机数数量重复2~4的步骤。

单向散列函数的单向性是支撑伪随机数生成器不可预测性的基础。

密码法

使用密码（AES等对称密码或RSA等公钥密码都可以）来编写能够生成强伪随机数的伪随机数生成器。

这种伪随机数生成器的工作方式如下：

1. 初始化内部状态（计数器）
2. 用密钥加密计数器的值
3. 将密文作为伪随机数输出
4. 计数器的值加1
5. 根据需要的伪随机数数量重复2~4的步骤

密码的机密性是支持伪随机数生成器不可预测性的基础 。

ANSI X9.17

关于用密码实现伪随机数生成器的具体方法，在ANSI X9.17和ANSI X9.31的附录中进行了描述，它们使用了三重DES和AES作为密码运算。

结构图如下：

步骤如下：

1. 初始化内部状态

2. 将当前时间加密生成掩码

   当前时间可以被攻击者预测，但由于攻击者不知道加密密钥，所以他无法预测加密后的掩码。

3. 对内部状态与掩码求XOR

4. 将步骤3的结果进行加密

5. 将步骤4的结果作为伪随机数输出

   以上三步的作用是输出伪随机数。

6. 对步骤4的结果与掩码求XOR

7. 将步骤6的结果加密

8. 将步骤7的结果作为新的内部状态

   以上三步的作用是更新内部状态

9. 重复步骤2~8直到得到所需数量的伪随机数。

伪随机数生成器的内部状态是通过密码进行保护的。

其他算法

生成伪随机数的算法有很多，但在安全相关的软件开发中，必须确认【这个随机数算法是否能够用于密码学和安全相关的用途】。

一个随机数算法再优秀，如果它不具备不可预测性，就不能用于密码学和安全相关用途。大多数情况下，随机数算法的说明中会写明是否可用于安全相关用途。

Java中， java.security.SecureRandom 类可以用于安全相关用途。

Ruby中，SecureRandom模块可用于安全相关用途。

对伪随机数生成器的攻击

对种子进行攻击

伪随机数的种子和密码的密钥同等重要。

要避免种子被攻击者知道，需要使用具备不可重现性的真随机数作为种子。

对随机数池进行攻击

现实情况中，我们一般会事先在一个名为 随机数池 （random pool）的文件中积累随机比特序列。当密码软件需要伪随机数的种子时，可以从随机数池中取出所需长度的随机比特序列来使用。

随机数池的内容要严格保密。

随机数池本身并不储存任何有意义的信息。

【Linux的/dev/random文件就是一个根据硬件设备驱动收集的背景噪声储存真随机数的随机数池；/dev/urandom则存储的是伪随机数】