随机数

   ———— 不可预测的源泉

使用随机数的密码技术

 随机数的使用场景，比如:

• 生成密钥
   用于对称密码和消息的认证码
• 生成密钥对
   用于公钥密码和数字签名
• 生成初始化向量
   用于分组密码的CBC、CFB、OFB模式
• 生成nonce
   用于防御重放攻击以及分组密码的CTR模式等
• 生成盐
   用于基于口令的密码等；
  为了不让攻击者看穿而使用随机数，因为“无法看穿”，即不可预测。

随机数性质

对随机数的性质进行分类

• 随机性 —— 不存在统计学偏差，是完全杂乱的数列
• 不可预测性—— 不能从过去的数列推测出下一个出现的数

• 不可重现性—— 除非将数列本身保存下来，否则不能重现相同的数列
  上述三个性质按顺序分别命名为“弱伪随机数”、“强伪随机数”和“真伪随机数”

  
  随机数的性质.png

随机性

 所谓随机性，简单来说，就是看上去杂乱无章的性质。我们可以用伪随机数生成器大量的生成0到9范围内的整数，然后看一看所生成的数列。如果数列是像0、1、2、3、4、5、6、7、8、9、0、1、2....这样循环不断，那肯定不是杂乱无章的。或者咋一看是杂乱无章的，但实际上在数列中0一次都没出现过，或者整个数列一半都是6，这样的数列也能算是杂乱无章的。
 如果伪随机数列中不存在统计学偏差，则我们可以认为这个伪随机数列是随机的。判断一个伪随机数是否随机的方法称为随机数测试，随机数测试的方法有很多种。
 一半在电脑游戏中使用的随机数只要具备随机性就可以了。此外，在计算机模拟软件中使用的随机数虽然需要根据目的来进行随机数测试，但也是只要具备随机性就可以了。然而，密码技术中所使用的随机数，仅仅具备随机性是不够的。
 由于随机数会被用来生成密钥，因此密钥不能被攻击者看穿。但是，杂乱无章并不代表不会被看穿，因此，将只具备随机性的伪随机数数称为 “弱为随机数”。

不可预测性

 密码中所使用的随机数仅仅具备随机性是不够的，还需要具备避免攻击者看穿的不可预测性。不可预测性（unpredictability）。
 所谓不可预测性，是指攻击者在制定过去生成伪随机数列的前提下，依然无法预测出下一个生成出来的伪随机数的性质。其中，“在制定过去生成的伪随机数列的前提下.....”是非常重要的一点。
 不可预测性是通过使用其他的密码技术来实现的。例如，可以通过单向散列函数的单向性和密码的机密性来保证伪随机数生成器的不可预测性。我们将具备不可预测性的伪随机数称为强伪随机数。

不可重新性

 所谓不可重新性，是指无法重新和某一随机数列完全相同的数列的性质。如果除了将随机数列本身本身保存下来以外，没有其他方法能够重新该数列，则我们就可以说该随机数列具备了不可重现性。
 仅靠软件时无法生成具备不可重现性的随机数列的。软件只能生成伪随机数列，这是因为运行软件的计算机本身仅具备有限的内部状态。而在内部状态相同的条件下，软件必然只能生成相同的数，因此软件所生成的数列在某一个时刻一定会出现重复的。首次出现重复之前的数列长度称为周期，对于软件所生成的数列，其周期必定是有限的。当然，这个周期可能会很长，但总归还是有限的。凡是具有周期的数列，都不具备不可重现性。
 要生成具备不可重现性的随机数列，需要从不可重新性的物理现象中获取信息，比如周围的温度和声音的变化，用户移动的鼠标的位置、键盘的输入的时间间隔、放射线测量仪的输出值等，根据从这些硬件中所获取的信息而生成的数列，一般可以认为是具备不可重新性的随机数列。
 目前，利用热噪声这一自然现象，人们已经开发出能够生成不可重新性的随机数的硬件设备。例如，英特尔的新型CPU中就内置了数字随机数生成器，并提供了生成不可重现性随机数的RDSEED指令，以及生成不可预测随机数的RDRAND指令。
我们称具备不可重现性的随机数称为真随机数。

伪随机数生成器

 随机数可以通过硬件来生成，也可以通过软件来生成。
 通过硬件生成的随机数列，是根据传感器收集的热量、声音变化等事实上无法预测和重现的自然现象信息来生成的。像这样的硬件设备就称为随机数生成器（Random Number Generator ，RNG）。
 而可以生成随机数的软件则称为伪随机生成器*（Pseudo Random Number Generator，PRNG）。因为仅靠软件无法生成真随机数，因此要加上一个“伪”字。

伪随机数生成结构

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

伪随机数生成器结构.png

• 伪随机数生成器内部状态
   伪随机数生成器的内部状态，是指伪随机数生成器所管理的内存中的数值。当有人对伪随机数生成器发出“给我一个伪随机数”的请求时，伪随机数生成器会根据内存中的数值（内部状态）进行计算，并将计算的结果作为随机数的输出。随后，为了响应下一个伪随机数请求，伪随机数生成器会改变自己的内部状态。因此，将根据内部状态计算伪随机数的方法和改变内部状态的方法组合起来，就是伪随机数生成的算法。
   由于内部状态决定了下一个生成伪随机数，因此内部状态不能被攻击者知道。
• 伪随机数生成器的种子
   为了生成伪随机数，伪随机数生成器需要被称为种子（seed）的信息。伪随机数的种子是用来对伪随机数生成器的内部状态进行初始化的。
   伪随机数的种子是一串随机的比特序列，根据种子就可以生成出专属自己的伪随机数列。伪随机数生成器是公开的，但种子是需要自己保密的，这就好像密码算法是公开的，但是密钥只能自己保密。由于种子不可以被攻击者知道，因此不可使用容易被预测的值，例如不可以使用当前时间作为种子。
   密码的密钥和伪随机数的种子之间的对比：
  密码的密钥与伪随机数的种子.png

具体伪随机数生成器

• 杂乱的方法
    既然要生成杂乱无章的数列，那么用杂乱无章的算法不就可以了吗？比如说，可以使用连程序员都无法理解的混乱又复杂的算法。然而，这种做法是错误的。如果只是把算法搞的复杂，那么该算法是无法用于密码技术的。
   其中一个原因就是周期太短了。使用复杂算法所生成的数列大多都会具有很短的周期（即短数列的不断重复）。由于密码技术使用的伪随机数必须具备不可预测性，因此周期短是不行的。
   另一个原因是，如果程序员不能够理解算方法的详细内容，那么就无法判断所生成的随机数是否具有不可预测性。
• 线性同余法
   线性同余法（linear congruential method）是一种使用很广泛的伪随机数生成器算法。然而，它并不能用于密码技术。

• 单向散列函数法
   使用单向散列函数可以编写出能够生成具备不可预测性的伪随机数列的伪随机数生成器。

  
  用单向散列函数实现伪随机数生成器.png
  

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

1. 用伪随机数的种子初始化内部状态（计数器）。
2. 用单向散列函数计算计数器的散列值
3. 将散列值作为伪随机数输出。
4. 计数器的值加1。
5. 根据需要的伪随机数数量重复2~4的步骤。
    供给制要预测下一个伪随机数，需要知道计数器的当前值。请大家注意，这里输出的伪随机数实际上相当于单向散列函数的散列值。也就是说，要想知道计数器的值，就需要破解单向散列函数的单向性，这是非常困难的，因此攻击者无法预测下一个伪随机数。总而言之，在这种伪随机数生成器中，单向散列函数的单向性是支撑伪随机数生成器不可预测性的基础。

• 密码法
   我们可以使用密码来编写能够生成强伪随机数的伪随机数生成器。既可以使用AES等对称密码，也可以使用RSA等公钥密码。

用密码实现的伪随机数生成器.png

1. 初始内部状态（计数器）
2. 用密钥加密计算器的值
3. 将密文作为伪随机数的输出
4. 计算器的值加1
5. 根据需要的伪随机数数量重复2~4步骤
    攻击者要预测下一个伪随机数，需要知道计数器的当前值然而，由于之前所输出的伪随机数相当于密码，因此要知道计数器的值，就需要破译密码，这是非常困难的，因此攻击者无法预测出下一个伪随机数。总而言之，在这种伪随机数生成器中，密码的机密性是支撑伪随机数生成器不可预测性的基础。

• ANSI X9.17
   关于用密码实现伪随机数生成器的具体方法，在ANSIX9.17和ANSI X9.31的附录中进行了描述，下面我们来介绍一下这种方法。这里所介绍的伪随机数生成器，就被用于密码软件PGP中。

  
  用ANSI X9.17方法实现伪随机数生成器.png

1. 初始化内部状态
2. 将当前时间加密生成掩码
3. 对内部状态与掩码求XOR
4. 将步骤3的结果进行加密
5. 将步骤4的结果作为伪随机数输出
6. 对步骤4的结果与掩码求XOR
7. 将步骤6的结果加密
8. 将步骤7的结果作为新的内部状态
9. 重复步骤2~8直到得到所需数量的伪随机数。
    在步骤2中，我们将当前时间进行加密生成了一个掩码。当前时间是可以被攻击者预测出来的，但是由于攻击者不知道加密密钥，因此他无法预测加密后的当前时间（即掩码）。在之后的步骤3和步骤6中，我们将使用掩码对比特序列进行随机翻转。
    步骤3~5的作用是输出伪随机数。这里输出额伪随机数是将内部状态与掩码的XOR进行加密之后的结果，那么攻击者是否能通过将伪随机数进行反算来看穿内部状态与掩码的XOR呢？不能，因为要看穿这个值，攻击者必须要破解密码。因此，根据过去输出的伪随机数列，攻击者无法推测出伪随机数生成器内部状态。
    步骤6~8的作用是更新内部状态。新的内部状态是将上个伪随机数与掩码的XOR进行加密之后的结果。那么攻击者是否能够从伪随机数推测出新的内部状态呢?不能，因为要算出新的内部状态，只知道上一个伪随机数是不够的，还必须知道掩码以及加密密钥才行。
    我们可以发现，在这种伪随机数生成器中，密码的使用保证了无法根据输出的伪随机数列来推测内部状态。换言之，伪随机数生成器的内部状态是通过密码进行保护的。

• 其他算法
   除了上面介绍的算法之外，还有很多其他的生成随机数的算法。在安全相关的软件开发中，开发者在选择随机数生成算法时必须确认“这个随机数算法是否能够用于密码学和安全相关用途”。一个随机数算法再优秀，如果它不具备不可预测性，那么久不能用于密码学和安全相关用途，。大多数情况下，随机数算法的说明都会写明是否可用于安全相关的用途，请大家仔细确认。
   有一个有名的伪随机算法叫作梅森旋转算法（Mersenne twister），但它并不能用于安全相关的用途。和线性同余一样，只要观察足够长的随机数列，就能够对之后生成的随机数列进行预测。
   Java中有一个用于生成随机数列的类，叫java.util.Random，然而这个类也不能用于安全相关用途，如果要用于安全相关用途，可以使用另一个名叫java.security.SecureRandom的类，不过这类的底层算法是经过封装的，因此实际用到的算法可能不止一种。
   和Java一样，Ruby中也分别用Random和SecureRandom模块，在安全相关用途中应该使用SecureRandom，而不是Random。

对伪随机数生成器的攻击

 和密码相比，伪随机数生成器实在是很少被人们所注意，因此我们很容易忘记伪随机数生成器也是可以受到攻击的。然而，由于伪随机数生成器承担了生成密钥的重任，因此它经常成为攻击对象。

• 对种子进行攻击
    伪随机数的种子和密码的密钥是同等重要的。如果攻击者知道了伪随机数的种子，那么就能够知道这个伪随机数生成器所生成的全部伪随机数列。因此，伪随机数的种子是不可以被攻击者知道。
   要避免种子被攻击知道，我们需要使用具备不可重现性的真随机数作为种子。
• 对随机数池进行攻击
   当然，我们一般不会到了需要的时候才当场生成真随机数，而是会事先在一个名为随机数池（random pool）的文件中积累随机比特序列。当密码软件需要伪随机数的种子时，可以从这个随机数池中取出所需要的长度的随机比特序列来使用。
   随机数池的内容不可以被攻击者知道，否则伪随机数的种子就可能被预测出来。
   随机数池本身并不存储任何有意义的信息。我们需要保护没有任何意义的比特序列，这一点优点违背常识，但其实却是非常重要的。

---

该系列的主要内容来自《图解密码技术第三版》
我只是知识的搬运工
文章中的插图来源于原著