在密码技术中，随机数被用来生成密码。

随机数的性质分为三类：随机性、不可预测性和不可重现性。

线性同余法是很多库函数所采用的生成伪随机数的方法，但不可以用于密码技术。

用于密码技术的伪随机数生成器，需要使用单向散列函数和密码技术确保不可预测性。

随机数的性质

随机数的应用场景：

  1. 生成密码，用于对称密码和消息认证码。
  2. 生成密钥对，用于公钥密码和数字签名。
  3. 生成初始化向量（IV），用于分组密码的CBC、CFB和OFB模式。
  4. 生成nonce，用于预防重放攻击以及分组密码的CTR模式。
  5. 生成盐，用于基于口令的密码（PBE）等。

随机性

伪随机数列中不存在统计学偏差，则认为该伪随机数列是随机的。

一般电脑游戏中使用的随机数只需要具备随机性即可。

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

弱伪随机数：只具备随机性的伪随机数。

不可预测性

伪随机数列具备随机性，看起来杂乱无章，但并不代表不会被看穿。

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

不可预测性是通过使用其他密码技术实现的（例如单向散列函数）。

强伪随机数：具备不可预测性的伪随机数。

不可重现性

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

仅靠软件是无法生成具备不可重现性的随机数列的，因为运行软件的计算机本身仅具备有限的内部状态。内部状态相同的条件下，随机数列就相同。

要生成具备不可重现性的随机数列，可以从不可重现的物理现象中获取信息。比如热噪声，温度和声音的变化等等。

真随机数：具备不可重现性的随机数。

伪随机数生成器

名称说明
随机数生成器通过硬件来生成随机数列，具体是根据传感器采集的热量、声音的变化等事实上无法预测和重现的自然现象信息来生成的。
伪随机数生成器使用随机数生成软件来生成的随机数。因为仅靠软件无法生成真的随机数。

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

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

种子是用来对内部状态进行初始化的。

根据种子可以生成专属于自己的伪随机数列。伪随机数生成器是公开的，种子需要自己保密。

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

密码的密钥与伪随机数的对比：

伪随机数算法

线性同余法

线性同余法是一种使用很广泛的伪随机数生成器算法。

数学原理

假设要生成的伪随机数序列为$R_{0}, R_{1}, R_{2},…$，则该序列满足如下条件： $$ R_{n}=(A \times R_{n-1} + C) \mod M $$ 其中$A,C,M$为常数，且$A < M, C < M$以及$R_{0}=(A \times [seed] +C) \mod M$。

将当前的伪随机数值乘以$A$在加上$C$，然后对$M$取余，得到的值就是下一个伪随机数。

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

示例

假设$A=3,C=0,M=7$，种子为$6$，则有 $$ \begin{aligned} R_{0}&=(A \times [seed] + C) \mod M \\ &=(3 \times 6 + 0) \mod 7 \\ &=4 \\ R_{1}&=(A \times R_{0} + C) \mod M \\ &=(3 \times 4 + 0) \mod 7 \\ &= 5 \\ R_{2}&=(A \times R_{1} + C) \mod M \\ &=(3 \times 5 + 0) \mod 7 \\ &= 1 \\ R_{3}&=(A \times R_{2} + C) \mod M \\ &=(3 \times 1 + 0) \mod 7 \\ &= 3 \\ … \end{aligned} $$ 其伪随机数序列为$4,5,1,3,2,6,4,5,1,3,6,…$等，这里的周期为$6$。

因为线性同余法不具备不可预测性，因此不能用于密码技术。

C语言中库函数rand以及Java中的java.util.Random都采用了线性同余法。

单向散列函数法

步骤如下：

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

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

密码法

步骤：

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

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

ANSI X9.17

步骤（3）~（5）的作用是输出伪随机数。这里输出的伪随机数是将内部状态和掩码先异或然后再加密的结果。

步骤（6）~（8）的作用是更新内部状态。新的内部状态是将上一个伪随机数与掩码先异或再加密的结果。

ANSI X9.17算法被用于密码软件PGP中。

攻击

对种子进行攻击

对随机数池进行攻击

在实际使用过程中，一般不会在需要的时候当场生成，而是事先会在一个名为随机数池的文件中存储随机比特序列。

当密码软件需要伪随机数的种子时，可以从随机数池中取出所需长度的随机比特来使用。

保护随机数池不被攻击者知道，等同于保护伪随机数的种子。

Linux中的/dev/random文件就是一个根据硬件设备驱动收集的背景噪声生成真随机数的随机数池。