密码学《图解密码技术》记录学习第十二章

第十二章

12.1 骡子的锁匠铺

12.2 本章学习的内容

12.3 使用随机数的密码技术

12.4 随机数的性质

12.4.1 对随机数的性质进行分类

12.4.2 随机性

12.4.3 不可预测性

12.4.4 不可重现性

小测验 1 骰子（答案见 12.9 节）

12.5 伪随机数生成器

伪随机数生成器的结构

编辑伪随机数生成器的内部状态

伪随机数生成器的种子

12.6 具体的伪随机数生成器

12.6.1 杂乱的方法

12.6.2 线性同余法

12.6.3 单向散列函数法

12.6.4 密码法

12.6.5 ANSI X9.17

12.6.6 其他算法

12.7 对伪随机数生成器的攻击

12.7.1 对种子进行攻击

12.7.2 对随机数池进行攻击

12.8 本章小结

12.9 小测验的答案小测验 1 的答案：骰子（12.4.4 节）

小测验 2的答案：找出伪随机数生成器的弱点（12.6.3 节）

小测验3的答案:随机数的基础知识（12.8 节）

第十二章

12.1 骡子的锁匠铺

在正式讲解随机数之前，我们先来看一个故事。

很久很久以前，骡子开了一家锁匠铺，他说：“我做的锁头很坚固，小偷绝对打不开。”因此动物村里所有的动物都为自己的房子装上了骡子做的锁。

骡子做的锁确实很坚固，但是每把锁头上用的钥匙居然都是同一个形状的。因此小偷只要得到了一幢房子的钥匙，就可以打开所有房子的锁了。

教训：坚固的锁头固然重要，但不可预测的钥匙更加重要。

12.2 本章学习的内容

本章中，我们将按下面的顺序学习关于随机数的知识。

⚪使用随机数的密码技术

⚪随机数的性质伪随机数生成器具体的

⚪伪随机数生成器

⚪对伪随机数生成器的攻击

12.3 使用随机数的密码技术

随机数是干什么用的

如果说随机数和密码技术是相关的，可能有些读者还无法理解。实际上，和对称密码、公钥密码、数字签名等技术相比,生成随机数的技术确实不是很引人注意,但是,随机数在密码技术中却扮演着十分重要的角色。

例如,下面的场景中就会用到随机数。

⚪生成密钥

用于对称密码和消息认证码。

⚪生成密钥对

用于公钥密码和数字签名。

⚪生成初始化向量（IV）

用于分组密码的CBC、CFB和OFB模式。

⚪生成 nonce

用于防御重放攻击以及分组密码的CTR模式等。

⚪生成盐

用于基于口令的密码(PBE)等。

上面这些用途都很重要,但其中尤为重要的是“生成密钥”和“生成密钥对”这两个。即使密码算法的强度再高,只要攻击者知道了密钥,就会立刻变得形同虚设。因此,我们需要用随机数来生成密钥，使之无法被攻击者看穿。

在这里,请大家记住为了不让攻击者看穿而使用随机数这一观点,因为“无法看穿”,即不可预测性，正是本章的主题。

12.4 随机数的性质

要给随机数下一个严密的定义是非常困难的，有时甚至会进入哲学争论的范畴。在这里，我们只介绍一下随机数和密码技术相关的一些性质。

12.4.1 对随机数的性质进行分类

在这里我们将随机数的性质分为以下三类。

⚪随机性——不存在统计学偏差，是完全杂乱的数列

⚪不可预测性——不能从过去的数列推测出下一个出现的数

⚪不可重现性——除非将数列本身保存下来，否则不能重现相同的数列

上面三个性质中，越往下就越严格。具备随机性，不代表一定具备不可预测性。密码技术中所使用的随机数,仅仅具备随机性是不够的,至少还需要具备不可预测性才行。

具备不可预测性的随机数，一定具备随机性。具备不可重现性的随机数,也一定具备随机性和不可预测性。

在本书中，为了方便起见，我们将上述三个性质按顺序分别命名为“弱伪随机数”、“强伪随机数”和“真随机数”,并整理成表12-1。

12.4.2 随机性

我们先来介绍一下随机性( randomness )。

所谓随机性,简单来说就是看上去杂乱无章的性质。我们可以用伪随机数生成器大量生成0到9范围内的整数，然后看一看所生成的数列。如果数列是像0、1、2、3、4、5、6、7、8、9、0、1、2…这样不断循环的,那肯定不是杂乱无章的。或者乍一看是杂乱无章的,但实际上在数列中0一次都没有出现,或者整个数列中有一半都是6,这样的数列也不能算是杂乱无章的。

如果伪随机数列中不存在统计学偏差，则我们可以认为这个伪随机数列是随机的。判断一个伪随机数列是否随机的方法称为随机数测试,随机数测试的方法有很多种。

一般在电脑游戏中使用的随机数只要具备随机性就可以了。此外，在计算机模拟中使用的随机数虽然需要根据目的来进行随机数测试,但也是只要具备随机性就可以了。然而,密码技术中所使用的随机数,仅仅具备随机性是不够的。

让我们来回忆一下密码技术中使用的随机数需要具备怎样的性质。由于随机数会被用来生成密钥,因此密钥不能被攻击者看穿。但是,杂乱无章并不代表不会被看穿,因此本书中将只具备随机性的伪随机数称为“弱伪随机数”。

12.4.3 不可预测性

密码中所使用的随机数仅仅具备随机性是不够的,还需要具备避免被攻击者看穿的不可预测性。不可预测性在英语中叫作unpredictability,将这个单词分解之后是这样的: un(否定)-pre（之前) -dict （说) -ability （可能性)。因此， unpredictability就是一种“不可能事先说中”的性质，即不可预测性。

所谓不可预测性，是指攻击者在知道过去生成的伪随机数列的前提下，依然无法预测出下一个生成出来的伪随机数的性质。其中,“在知道过去生成的伪随机数列的前提下……”是非常重要的一点。

现在我们假设攻击者已经知道伪随机数生成器的算法。此外，正如攻击者不知道密钥一样，他也不知道伪随机数的种子。伪随机数生成器的算法是公开的，但伪随机数的种子是保密的。在上述假设的前提下，即便攻击者知道过去所生成的伪随机数列，他也无法预测出下一个生成出来的伪随机数--这就是不可预测性。

那么如何才能编写出具备不可预测性的伪随机数生成器呢？嗯，这是一个很有意思的问题。其实，不可预测性是通过使用其他的密码技术来实现的。例如，可以通过单向散列函数的单向性和密码的机密性来保证伪随机数生成器的不可预测性。详细内容我们会在介绍伪随机数生成器的具体算法时进行讲解。

本书中，我们将具备不可预测性的伪随机数称为强伪随机数。

12.4.4 不可重现性

所谓不可重现性,是指无法重现和某一随机数列完全相同的数列的性质。如果除了将随机数列本身保存下来以外,没有其他方法能够重现该数列,则我们就说该随机数列具备不可重现性。

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

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

目前,利用热噪声这一自然现象,人们已经开发出能够生成不可重现的随机数列的硬件设备了。例如,英特尔的新型CPU中就内置了数字随机数生成器,并提供了生成不可重现的随机数的RDSEED指令,以及生成不可预测的随机数的RDRAND指令(参见专栏)。

本书中,我们将具备不可重现性的随机数称为真随机数。

小测验 1 骰子（答案见 12.9 节）

反复掷骰子所生成的数列,是否具备不可重现性呢?

12.5 伪随机数生成器

随机数可以通过硬件来生成,也可以通过软件来生成。

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

而可以生成随机数的软件则称为伪随机数生成器( Pseudo Random Number Generator,PRNG)。因为仅靠软件无法生成真随机数,因此要加上一个“伪”字。

伪随机数生成器的结构

伪随机数生成器具有“内部状态”,并根据外部输入的“种子”来生成伪随机数列(图12-2)。

伪随机数生成器的内部状态

伪随机数生成器的内部状态，是指伪随机数生成器所管理的内存中的数值。当有人对伪随机数生成器发出“给我一个伪随机数”的请求时,伪随机数生成器会根据内存中的数值(内部状态）进行计算，并将计算的结果作为伪随机数输出。随后，为了响应下一个伪随机数请求，伪随机数生成器会改变自己的内部状态。因此,将根据内部状态计算伪随机数的方法和改变内部状态的方法组合起来,就是伪随机数生成的算法。

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

伪随机数生成器的种子

为了生成伪随机数,伪随机数生成器需要被称为种子(seed)的信息。伪随机数的种子是用来对伪随机数生成器的内部状态进行初始化的。

随机数伪随机数的种子是一串随机的比特序列，根据种子就可以生成出专属于自己的伪随机数列。伪随机数生成器是公开的,但种子是需要自己保密的,这就好像密码算法是公开的,但密钥只能自己保密。由于种子不可以被攻击者知道,因此不可以使用容易被预测的值,例如不可以用当前时间作为种子。

密码的密钥与伪随机数的种子之间的对比请参见图12-3。

12.6 具体的伪随机数生成器

抽象的介绍就到此为止,我们来看一些更具体的内容。下面我们将介绍一些具体的伪随机数生成器。

⚪杂乱的方法

⚪线性同余法

⚪单向散列函数法密码法

⚪ANSI X9.17

12.6.1 杂乱的方法

可能有人会说，既然是要生成杂乱无章的数列，那么用杂乱无章的算法不就可以了吗？比如说,可以使用连程序员都无法理解的混乱又复杂的算法。然而,这种做法是错误的。如果只是把算法搞得复杂，那么该算法是无法用于密码技术的。

其中一个原因就是周期太短。使用复杂算法所生成的数列大多数都会具有很短的周期(即短数列的不断重复)。由于密码技术中使用的伪随机数必须具备不可预测性,因此周期短是不行的。

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

12.6.2 线性同余法

线性同余法(linear congruential method)是一种使用很广泛的伪随机数生成器算法。然而,它并不能用于密码技术。

线性同余法的算法是这样的。假设我们要生成的伪随机数列为Ro、R1、R2…。首先我们根据伪随机数的种子，用下列公式计算第一个伪随机数 Ro。

第一个伪随机数 Ro=(A x 种子 + C) mod M

在这里，A、C、M都是常量，且A和C需要小于M。

接下来，我们根据 Ro用相同的公式计算下一个伪随机数 R1。

R1= (A × Ro + C) mod M

接下来我们再用同样的方法,根据当前的伪随机数Rn来计算下一个伪随机数Rn+1。.

Rn+1 = (A × Rn+ C) mod M

简而言之,线性同余法就是将当前的伪随机数值乘以A再加上C,然后将除以M得到的余数作为下一个伪随机数。在线性同余法中,最近一次生成的伪随机数的值就是内部状态,伪随机数的种子被用来对内部状态进行初始化。线性同余法的结构如图 12-4 所示。

下面我们来用线性同余法进行一些实际的计算。为了方便,这里我们使用较小的数,假设:

A= 3

C=0

M= 7

然后将 6 作为伪随机数的种子，根据线性同余法，生成伪随机数列的过程如下。

以此类推,我们可以得到4、5、1、3、2、6、4、5、1、3、2、6.这样的伪随机数列。在这里,数列是以4、5、1、3、2、6的顺序不断循环的,因此周期为6。

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

如果改变 A 的值,生成的伪随机数列又将如何变化呢？我们可以发现,如果要让周期为6，只有A=3和A=5才能满足条件。

当A=0时:0, 0, 0, 0, 0, 0, 0,0,0,0, …(周期为1)

当A=1时:6, 6, 6, 6, 6, 6, 6, 6, 6,6, …(周期为1)

当A=2时:5, 3, 6, 5, 3, 6, 5, 3, 6, 5, (周期为3)

当A=3时:4, 5, 1,3, 2,6,4, 5, 1,3, …(周期为6)

当A=4时：3，5,6,3,5,6,3,5,6,3,…(周期为3)

当A=5 时：2，3，1，5，4，6，2，3，1，5，…(周期为6）

当A=6时：1，6，1，6，1，6，1，6,1，6, …(周期为2)

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

然而，线性同余法不具备不可预测性，因此不可以将线性同余法用于密码技术。

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

我们可以很容易地证明线性同余法不具备不可预测性。

假设攻击者已知A=3、C=0、M=70。这时，攻击者只要得到所生成的伪随机数中的任意一个，就可以预测出下一个伪随机数。因为攻击者只要用得到的伪随机数 R 根据下列公式计算就可以了。

(AxR+C) mod M=(3 x R+0) mod 7

在这个过程中,攻击者没有必要知道种子6。此外,只要重复上述计算过程,就可以预测出之后生成的全部伪随机数列。现在大家应该已经明白了吧，线性同余法是不具备不可预测性的。

12.6.3 单向散列函数法

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

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

(1)用伪随机数的种子初始化内部状态(计数器)。

(2)用单向散列函数计算计数器的散列值。

(3) 将散列值作为伪随机数输出。

（4）计数器的值加 1。

(5)根据需要的伪随机数数量重复(2)~(4)的步骤。

假设攻击者获得了这样的伪随机数生成器所生成的过去的伪随机数列,他是否能够预测出下一个伪随机数呢？

攻击者要预测下一个伪随机数,需要知道计数器的当前值。请大家注意,这里输出的伪随机数列实际上相当于单向散列函数的散列值。也就是说,要想知道计数器的值,就需要破解单向散列函数的单向性,这是非常困难的,因此攻击者无法预测下一个伪随机数。总而言之,在这种伪随机数生成器中,单向散列函数的单向性是支撑伪随机数生成器不可预测性的基础。

12.6.4 密码法

我们可以使用密码来编写能够生成强伪随机数的伪随机数生成器（图 12-7）。既可以使用AES等对称密码,也可以使用RSA等公钥密码。这种伪随机数生成器的工作方式如下。

（1) 初始化内部状态（计数器）。

（2）用密钥加密计数器的值。

(3)将密文作为伪随机数输出。

(4) 计数器的值加1。

(5)根据需要的伪随机数数量重复(2)~(4)的步骤。

假设攻击者获得了这样的伪随机数生成器所生成的过去的伪随机数列，他是否能够预测出下一个伪随机数呢？

攻击者要预测下一个伪随机数，需要知道计数器的当前值。然而，由于之前所输出的伪随机数列相当于密文,因此要知道计数器的值,就需要破译密码,这是非常困难的,因此攻击者无法预测出下一个伪随机数。总而言之,在这种伪随机数生成器中,密码的机密性是支撑伪随机数生成器不可预测性的基础。

12.6.5 ANSI X9.17

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

ANSI X9.17 伪随机数生成器的结构如图 12-8 所示。

实现伪随机数生成器的步骤如下。

（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 进行加密之后的结果。那么，攻击者是否能够从伪随机数推测出新的内部状态呢？不能，因为要算出新的内部状态，只知道上一个伪随机数是不够的，还必须知道掩码以及加密密钥才行。

通过分析上述步骤,我们可以发现,在这种伪随机数生成器中,密码的使用保证了无法根据输出的伪随机数列来推测内部状态。换言之，伪随机数生成器的内部状态是通过密码进行保护的。

12.6.6 其他算法

除了上面介绍的算法之外,还有很多其他的生成随机数的算法。在安全相关的软件开发中,开发者在选择随机数生成算法时必须确认“这个随机数算法是否能够用于密码学和安全相关用途”。一个随机数算法再优秀，如果它不具备不可预测性，那么就不能用于密码学和安全相关用途。大多数情况下,随机数算法的说明中都会写明是否可用于安全相关用途,请大家仔细确认。

举个例子,有一个有名的伪随机数生成算法叫作梅森旋转算法( Mersenne twister),但它并不能用于安全相关的用途。和线性同余法一样，只要观察足够长的随机数列，就能够对之后生成的随机数列进行预测。

Java中有一个用于生成随机数列的类,名叫java.util.Random,然而这个类也不能用于安全相关用途。如果要用于安全相关用途,可以使用另一个名叫java.security.SecureRandom的类。

不过，这个类的底层算法是经过封装的，因此实际上所用到的算法可能不止一种。和Java一样, Ruby中也分别有Random类和SecureRandom模块,在安全相关用途中应该使用SecureRandom,而不是Random。