第九章、第十章学习笔记

第三部分密码协商

第九章——生成随机性
第十章——素数

第九章——生成随机性

为了生成密钥信息，我们需要随机数生成器（RNG）。生成良好的随机性是许多密码操作中非常重要的一部分，同时也是一项具有挑战性的工作。

序章

（1）好的随机数生成器对于许多密码学函数是非常必要的。

密钥管理系统正是利用随机数生成器来生成密钥。如果采用了错误的随机数生成器，就会得到安全性很低的弱密钥，而这正是 Netscape 浏览器早期的一个版本中存在的问题。

（2）随机数的衡量

       衡量随机性的度量称为熵。以下是一个比较粗略的解释∶ 如对一个完全随机的32位的字而言。它的熵是32位;如果这个32位的字只有4个可取值，并且每个值都是 25% 概率被选中，那么它的熵是2位。熵度量的不是随机数的位数，而是随机数的不确定性。熵可以看成是在理想的压缩算法下，能够确定一个值平均所需要的位数。值得注意的是随机数的熵取决于已知条件有多少。一个32位随机数的熵也是32位。假设已知其中18位是，14位是1，那么可以计算出这个随机数大约有2^28.8个取值，也就是说该随机数的熵只有28.8位。换言之，对一个随机数而言，知道的信息越多，它的熵越小。
       计算一个具有非均匀概率分布的随机数的嫡比较复杂。随机变量X的熵的常用定义如下∶
H(X):= -∑(x) P（X=x）log2 P（X=x）
       P（X=x）表示X取x的概率，我们不会使用这个公式，所以你不需要记住它。大部分数学家讨论熵的时候都参考这个定义，当然数学家们还使用其他一些定义，具体使用哪个定义取决于他们具体的研究工作。不要将这里的熵和物理学家研究的熵混淆起来，在物理学中，熵是热力学中的一个概念，和这里的熵几乎没有关系。

一、真实随机

在理想的世界中可以使用"真实随机"的数据，但是现实世界并不是理想的，真实随机的数据非常难以找到。
一些现代计算机内置了真实随机数生成器，这相比于单独的真实随机数生成器有了显著提高，也使得一些攻击更困难了。随机数生成器仍然只能被操作系统访问，所以每个应用必须信任操作系统处理随机数据的方法是安全的。

（1）使用真实随机数的问题

真实的随机数除了难以获取之外，在实际应用中还存在其他问题：

1、随机数不是随时都可以获取的。
2、真实的随机源有可能失效。
3、如何判断从某一具体的物理事件中能够提取多少熵。

（2）伪随机数

伪随机数作为使用真实随机数的一种替代品，实际上并不是真正随机的。伪随机数的生成一般都是通过确定性算法，从种子计算得到。如果种子泄露，那么伪随机数就可以预测了。
传统的伪随机数生成器（PRNG）是不安全的。这是因为设计伪随机数生成器的初衷是消除统计上的缺陷，而不是为了对抗攻击者。
如果对手掌握了生成随机数的算法并得到了一些伪随机数生成器的输出，那么他能否利用这些信息预测后面（或前面）输出的伪随机数?对于很多传统的伪随机数生成器来说这个答案可能是能，但是一个正确的密码学上的伪随机数生成器来说是不能的。在密码系统的上下文中，我们对伪随机数生成器还有更严格的要求。对于一个伪随机数生成器，如果攻击者即使掌握了它输出的随机数，也无法预测该生成器的其他输出结果，那么我们就称这样的伪随机数生成器是健壮的。

（3）真实随机数和伪随机数生成器

实际上，我们只使用真实随机数做一件事情∶作为伪随机数生成器的种子。这种做法解决了使用真实随机数的一些问题。一旦伪随机数生成器获得了种子，随机数可以随时获取。同时我们可以不断获得新的真实随机数作为新的种子，这样即使种子泄露，生成器的输出也不可能被完全预测。

二、伪随机数生成器的攻击模型

       利用种子生成伪随机数非常容易，关键问题在于如何获取一个随机种子并保证它在实际环境中是保密的。
       伪随机数生成器在任何时候都有一个内部状态。对于每个生成随机数的请求，生成器调用一个密码算法来生成伪随机数，同时这个算法也会更新生成器的内部状态以保证下次请求不会得到相同的随机数。
       对伪随机数生成器的攻击有很多形式。一种直接的攻击方法就是攻击者尝试从生成器的输出重构内部状态，这是一种典型的密码学攻击方法。使用密码技术也相对来说比较容易应对。如果攻击者在某一时间点能够获取内部状态，情况就变得更加困难了。在传统的伪随机数生成器中、如果攻击者获取了内部状态。那么他就可以计算出所有的输出和后续的所有内部状态，这就意味着传统的生成器一旦被攻击者成功攻破，它就不可能恢复到安全状态了。
       如果同一个伪随机数生成器状态被多次使用也会有问题。比如说，如果两个或更多的虚拟机从同样的状态启动，并从磁盘上读取相同的种子文件时，这个伪随机生成器状态就被多次使用了。避免从相同实例启动的虚拟机使用相同的状态，和恢复那些内部状态被窃取的伪随机数 [141]生成器到安全状态一样，都是非常困难的，因此我们需要一个真实的随机数生成器来作为熵源。为了让讨论更简单，我们假设存在一个或者多个熵源，它们在不可预测的时间内都能提供适量的熵。

三、Fortuna

       在实际应用中，我们最好使用一些常用的密码库中提供的密码学伪随机数生成器。为了更好地说明，下面我们将着重分析一个称为Fortuna的伪随机数生成器。

       Fortuna有三个组成部分∶

生成器负责采用一个固定长度的种子，生成任意数量的伪随机数;
累加器负责从不同的熵源收集熵再放入熵池中，并间或地给生成器重新设定种子;
种子文件管理器负责保证即使在计算机刚刚启动时伪随机数生成器也能生成随机数。

四、生成器

       生成器负责将固定长度的内部状态转换为任意长度的输出。我们使用类似AES的分组密码作为生成器，也可以使用AES（Rjndael）、Serpent或者Twofish。生成器的内部状态包括一个 256 位的分组密码密钥和一个128 位的计数器。生成器基本上可以认为是一个计数器模式的分组密码，CTR模式能够输出一串随机数据流。不过生成器还是有一些改进的细节。
       如果用户或者应用请求随机数，那么生成器就会执行算法生成伪随机数据。假设攻击者打算在请求完成之后设法破解生成器的内部状态，我们就需要做到即使攻击成功，也不能泄露生成器之前输出的结果。因此，在处理完每次请求后，我们会额外生成一个256 位的伪随机数据并把它作为分组密码的新密钥，然后清除旧密钥，这样就消除了所有泄露之前请求信息的可能性。
       为保证生成的随机数据满足统计上的随机性，我们不能同时生成太多的随机数据。这是因为真实的随机数据中可以存在重复的块值，但是计数器模式下输出的随机数中各块的值肯定不同有许多方法可以解决这个问题，比如说每个密文块我们只使用一半，这样就会消除大部分的统计误差。我们也可以不使用分组密码，而是利用伪随机函数，但是目前并没有一个安全高效、经过详尽分析的伪随机函数能满足我们的要求。最简单的解决方法限制单个请求中生成的随机数据的字节数，这样就能使统计偏差更难检测。
       在每次请求结束后，分组密码的密钥会被重置，但是计数器不需要重置。这只是一个很小的细节，但是能够避免出现密钥周期过短的问题。假设计数器每次都被重置、如果密钥重复，由于所有请求总是固定长度的，那么下一个密钥也必然是重复的，这样就会导致密钥周期过短。虽然发生这种问题的可能性不大，但是不重置计数器就可以完全避免它。由于计数器是 128位的，所以计数器值的重复问题就不需要考虑了（2块已经超过了我们计算机的计算能力）。这样也就不需要考虑密钥周期的问题了。而且，当计数器的值为0时就表示生成器没有密钥，因此不能产生任何输出。注意，对每次请求只能获得2-128数据的限制并不是一个不灵活的限制，如果需要超过2^128的随机数据，可以重复发送请求。实际上，在实现中提供了自动执行这样的重复请求的接口。
       生成器是一个非常有用的模块。它不仅是 Fortuna 的一个组成部分，而且也是实现接口的一部分。考虑一个进行 Monte Carlo仿真°的程序，希望仿真是随机的，但是希望在调试和验证时能够重复同样的仿真。一种解决方案就是在程序开始的时候调用操作系统的随机数生成器并获取一个随机种子，这个种子可以看作仿真器的一个输出，生成器从这个种子可以生成仿真需要的所有随机数据。这样一来，有了生成器的初始种子，仿真程序就可以利用同样的输人数据和种子对所有计算进行验证。同时在调试时，由于初始的种子不变，所以相同的仿真过程可以多次进行，每次的表现都会是完全相同的。

（1）初始化

这部分非常简单。将密钥和计数器设置为0，以表示生成器还没有获取种子。

（2）更新种子

更新种子操作通过输入任意字符串更新生成器状态。这时我们不用关心输入字符串的具体内容。为了保证输入字符串和现有密钥完全混合，我们使用了散列函数

计数器C被用作整数，后面它会被用作一个明文分组，我们使用了最低有效字节在前的方式来实现二者之间的转换。如果明文分组的16个字节为pe.…，pn，那么它对应的整数值为这样一来，C既可以看成一个16 字节的字符串，也可以看成一个整数。

（3）生成块

这个内部函数的作用就是生成多个随机块，但只能被生成器调用。伪随机数生成器之外的任何模块都不能调用该函数。

上面的代码中，E（K，C）是一个分组密码加密函数，密钥为K，明文为C，ε表示空字符串。GenerateBlocks 函数首先判断 C是否为0，当C等于0时就表示生成器还没有获得种子。接着以空字符串r开始一个循环，在循环中将每个新计算的随机块附加到r上以获得最终的输出。

（4）生成随机数

       当用户请求随机数时，生成器就会调用这个函数来产生随机数据，输出长度最多可达2^20字节。同时这个函数还会确保之前生成的结果信息都已经被清除。

       函数的输出是通过调用GenerateBlocks得到的，唯一的区别在于返回时只截取了前n个字节(「·]表示向上取整操作符）接着还需多生成两个随机块来生成新密钥，一旦更新了旧密钥K，r就无法被重新计算出来了。另一方面，只要 PesudoRandomData 没有保留r的副本，或者没有忘记清除保存r的内存单元，生成器就无法泄露r的任何信息。也就是说，即使以后生成器被成功攻击了，也不会影响之前生成的随机数的保密性。不过生成器之后产生的随机数的保密性就得不到保障，而这正是累加器将解决的问题之一。
       虽然 PesudoRandomData 函数的输出数据量被限制，但是可以通过多次调用来获得更长的随机字符串。值得注意的是，不能增加每次调用的最大输出长度，因为这样会增加统计偏差。重复调用PesudoRandomData 函数实现起来还是比较高效的，唯一的额外开销就是每产生 1MB 的随机数据，都必须生成额外32 字节的随机字节来更新密钥和计算分组密码的密钥表，不过这种开销相对于我们建议使用的分组密码是微不足道的。

（5）生成器速度

上面介绍的Fortuna生成器是在密码学上健壮的伪随机数生成器，它能够利用随机种子获得任意长度的伪随机输出。Fortuna生成器运行的速度主要依赖于使用的分组密码算法，如果使用个人计算机上的CPU，那么处理大量随机数请求时，平均每产生1字节的输出需要花费的时间低于 20 个时钟周期。

五、累加器

累加器负责从不同的嫡源中获取实随机数，并用来更新生成器的种子。

（1）熵源

假设环境中有多个熵源。并且每个熵源在任何时候都能及时产生事件来提供熵。具体使用哪种熵源并不重要，只需要保证至少一个熵源提供的熵（用于生成数据）是攻击者无法预测的。因为不知道攻击者会如何攻击，所以最好的选择就是将所有看起来不可预测的数据都用作熵源。按键时长和鼠标的移动都是合适的熵源。此外，应该尽可能多地使用实际可行的其他时序上的熵源，比如说，可以同时将按键的精确时长、鼠标的移动和点击、硬盘和打印机的响应都用作熵源。再次强调，只要保证攻击者无法同时获取所有熵源的随机信息就可以，不必在意他能否从部分熵源获取或者预测数据。摘源的实现是一个复杂的工作，一般来说，熵源都会被嵌入到操作系统的各种硬件驱动器中，用户几乎不可能完成这项工作。为每个熵源指定唯一的熵源编号（熵源号），熵源号的取值范围从0到 255。熵源号有静态分配和动态分配两种分配方式。熵源产生事件所包含的数据就是一连串字节，并且每个事件中都包含了不可预测的数据。比如，我们可以用精确计时器的2或4个最低有效字节来表示某个时间信息，时间数据中没必要包含年、月、日，因为攻击者获取它们非常容易。接下来，要将不同嫡源产生的事件链接起来。为了保证链接后获得的字符串唯一标识这些事件，我们必须确保这个字符串是可解析的。每个事件都被编码为3个或更多的字节。第一个字节表示事件的随机熵源号，第二个字节表示数据的附加字节数。后续字节包括熵源提供的任何数据。
当然，攻击者可能获取部分熵源产生的事件。为了模拟这个，假设攻击者控制了一些熵源。并且攻击者能够决定这些嫡源在何时产生何种事件，而且和其他用户一样，攻击者任何时候都能够向伪随机数生成器请求随机数据。

（2）熵池

为了更新生成器的种子，需要将事件放入一个足够大的熵池中，"足够大"意味着攻击者无法穷举出熵池中事件的所有可能值。利用这样的熵池生成新的种子、可以破坏攻击者之前获得的关于生成器状态的信息。不幸的是。不知道在更新生成器的种子前应该在熵池中放人多少事件。Yarrow尝试利用熵估值器和一些启发式规则来解决这个问题，不过，Fortuna以一种更好的方式解决了这个问题。

这个系统能够自动适应环境。如果攻击者了解的熵源信息非常少，那么在更新种子前他就无法预测P0中熵的大小。但是攻击者可能掌握熵源的很多信息，或者他能够伪造出许多随机事件，那样的话，他就能掌握关于P0中熵的足够多信息，进而可以从生成器的旧状态和输出计算出生成器的新状态。但是由于P1中包含的熵是P。中的两倍，P2中则为四倍等等，所以不论攻击者能够掌握或伪造多少随机事件，只要他无法预测某个熵源产生的事件，那么总会有一个嫡池能够包含足够的熵来抵抗攻击。如果生成器的某个状态被泄露了，那么它恢复到安全状态的速度取决于熵（攻击者无法预测的那部分）流人熵池的速度。假设熵以固定的速率p流入熵池，那么经过时间t后共产生pr位的熵，所以每个熵池中增加了大约pt/32 位的熵，如果在生成器更新种子时使用了一个存储了大于128 位熵的城池，则攻击者无法获得生成器的新状态。这里有两种情况。第一种情况，如果P。在下一次更新种子前能够收集到 128位的熵，那么生成器就恢复到安全状态了，不过这取决于预先设定的P。在更新种子前嫡的增加量。第二种情况，由于随机事件对于攻击者来说是已知的（或者是由攻击者生成的，而P。更新种子太快，在下一次更新种子前并不能收集到足够的熵。令t表示更新种子的时间间隔，那么每隔2^it时间Pi就会参与生成种子，这段时间内P能够收集2^ip/32位的熵，当128 ≤2^ipr/32< 256（设定上限是为了保证Pi-1，在这段时间内不能收集到128位的熵）时，一旦Pi参与新的种子，生成器就能恢复到安全状态了。从上面的不等式可以得到:从而。

这个结论令人满意。为了使生成器恢复到安全状态，解决方案所需要的时间最多是理想解决方案的64倍。这是一个常数，因此生成器即使在某个时间被攻破了，最终也必然能够恢复到安全状态。更重要的是，不必知道熵源产生的事件能够提供的熵大小，也不必知道攻击者掌握了多少关于熵源的信息，这就是Fortuna 比 Yarrow最大的改进之处，不必再花费心思构建熵估值器。生成器完全能够自动恢复到安全状态，如果熵源提供熵的速度快，那么恢复很快就能完成，如果熵源提供熵的速度比较慢，那么恢复就需要很长的时间。到目前为止，一直忽略了一个事实。就是一共只有32个熵池，所以有可能P1在两次更新种子之间无法收集到足够的随机性来使生成器恢复到安全状态。这种情况是完全可能发生的，只要攻击者能够伪造足够多的随机事件，使得在不被攻击者控制的熵源产生2"位熵之前，生成器的种子已经被更新2次。虽然发生的可能性不大，但是为了阻止这样的攻击，我们限制种子更新的速度。一个种子只有存在超过100毫秒时才可以被更新，也就是说种子每秒最多进行10次更新，这就意味着，如果存在熵池P2，那么每13年它才可能被使用一次。从经济和技术上考虑，计算机设备使用寿命一般不超过10年。所以选择使用32个熵池是合理的。

（3）实现注意事项

（4）初始化

初始化是一个简单函数。到目前为止，我们只讨论了生成器和累加器，但是下面定义的函数实现了Fortuna的一些外部接口，它们是在整个伪随机数生成器上进行操作的。

（5）获取随机数据

该函数不只简单地对伪随机数生成器的生成器组件进行封装，还要处理更新种子。

该函数首先将 P。的长度和 MinPoolSize 进行比较，以此来决定是否需要更新种子。我们可以大致地估计一下为了能够收集 128位的熵，熵池至少得有多大。假设每个事件包含8位的熵，放在熵池中需要占用4个字节（事件数据占2 个字节），那么 MinPoolSize的一个合适的大小为64字节。这不是十分重要，不过不建议使用比 32字节更小的值;选择过大的值，因为如果那样，即使熵源能够高效稳定地提供熵，种子的更新速度也会很缓慢。接下来的步骤是将种子更新计数器的值增加1。由于计数器的初始值为0、所以第一次更新种子计数器值为1，这样就保证了只有P。会参加种子的第一次更新。循环代码段的作用是将各熵池中字符串的散列值进行连接，我们也可以先将熵池的内容进行连接再计算散列值，但是这样一来，每个熵池中的整个字符串都需要被存储，显然不如现在使用的对每个熵池计算散列值更方便。2'ReseedCnt 用来检测2'是不是ReseedCnt 的因子，如果是，则值为真，不过因为一旦某个i值不能通过测试，那么后续循环中的测试也都不会通过，可以针对这一点进行优化。

六、种子文件管理

到目前为止，伪随机数生成器能够成功地收集熵，并且获取第一个种子后能够生成随机数。然而，每次计算机重启后，我们必须等到熵源提供足够的事件后，才能获取第一个种子来生成随机数据;另外，我们也无法保证第一次种子后的状态是攻击者无法预测的。
解决方案就是使用种子文件。伪随机数生成器保存了一个熵文件，叫作种子文件，种子只有伪随机数生成器可以获取。每次重启之后，伪随机数生成器读取种子文件并使用文件内容作为熵源来获得一个未知状态。当然，种子文件在每次使用之后都需要重新写人内容。下面首先描述在一个支持原子操作的文件系统中如何管理种子文件，接着讨论在实际的系统中实现种子文件管理时遇到的问题。

（1）写种子文件

第一个问题就是如何生成种子文件，这可以通过一个简单的函数实现。函数生成64字节的随机数据，然后写人文件，64字节比实际需要的稍微多一点，但是这么设定是有原因的。

（2）更新种子文件

       显然，种子文件能够被读取，不过通常将种子文件的读取和更新操作一起完成，具体原因稍后解释。

       该函数的操作包括读取种子文件、检查种子长度和更新生成器的种子，接着用新数据更新种子文件。
       该函数必须保证在更新种子和更新种子文件之间伪随机数生成器没有被调用过。因为那样会带来一个问题∶在一次重启之后，该函数读取种子文件并用来更新种子，假设攻击者在种子文件更新之前向伪随机数生成器请求获取随机数据，并且在获取到随机数据时，且在更新种子文件之前立刻重启计算机。这样，在下次启动之后，相同的种子文件会被读取并被用来更新种子，如果在种子文件更新前一个用户请求随机数据，那么他获取的随机数据就和刚才攻击者获取的随机数据是相同的。这就违背了随机数据的保密性、而我们经常使用随机数据来生成密钥，所以这是个非常严重的问题。

（3）读写种子文件的时间

在计算机刚刚启动的时候，伪随机数生成器并没有熵来生成随机数据，这正是使用种子文件的原因，所以在每次启动后，都需要对种子文件进行读取和更新。
计算机在运行的时候能够从各种嫡源收集熵，这些熵最终也能够影响种子文件的内容。一个简单的办法是在关闭计算机之前对种子文件进行更新，但是一些计算机在正常情况下不会关机，所以伪随机数生成器需要定时更新种子文件，但是实现起来比较无趣而且和具体的平台相关，这里就不详细描述了。我们只需要保证伪随机数生成器在收集到相当数量的熵后能够定时更新种子文件，一种合理的解决方案是在每次关机时以及每10分钟左右对种子文件进行一次更新。

（4）备份和虚拟机

       要保证能够正确地更新种子，还需要解决其他一些问题。因为不允许伪随机数生成器出现重复状态，所以使用种子文件。但是大部分存放种子文件的文件系统并不能保证避免出现重复状态，这就引出一些新的问题。
       首先是备份。如果先对整个文件系统进行备份，接着再重新启动，伪随机数生成器就利用种子文件来设定第一个随机种子的值。如果以后将利用备份对文件系统进行还原。再重新启动的时候，伪随机数生成器就会使用相同的种子文件。换言之，在累加器收集到足够的熵之前，伪随机数生成器在两次重启之后生成的输出是相同的。这是一个严重的问题，因为攻击者也可以利用这种方法来获取用户从伪随机数生成器那里得到的随机数据。
       对于这种攻击没有直接的防御方法。如果备份系统能够使整个计算机恢复到永久状态，那么我们无法阻止伪随机数生成器出现重复状态。最理想的是，我们修复备份系统使得它对伪随机数生成器敏感，但是这可能要求太多了。可以将种子文件的内容和当前时间进行散列之后再使用，前提是攻击者不会将时钟恢复到相同的时间。如果备份系统有一个计数器记录已经进行过多少次恢复，也可以将种子文件的内容和恢复计数器的值进行散列之后再使用。
       虚拟机上也有相似的问题，如果一个虚拟机状态被保存了，然后重启了两次，那么从同一状态启动的两个实例，其伪随机数生成器的状态也是相同的。幸运的是，针对备份中遇到的问题的一些解决方案对从相同状态启动的多个虚拟机实例中的问题同样适用。关于备份和虚拟机的问题值得深入研究，但是由于这些问题太过于依赖具体平台，这里就不给出通用的解决方案了。

（5）文件系统更新的原子性

关于种子文件的另外一个重要问题就是文件系统更新的原子性。在大多数操作系统中，对种子文件的写操作仅仅是对一些内存缓冲区进行更新，很久之后才会将数据真正写到磁盘上。虽然一些文件系统提供了"fush"命令，声称能够将缓存上的所有数据都写到磁盘上，但是这个操作执行得非常缓慢，而且有时候硬件上并不会真正执行"fNush"命令。无论何时使用种子文件来更新种子，都要在用户请求随机数据之前更新种子文件，而且必须要保证磁盘上的数据也进行了更新。在一些文件系统中，对文件数据和文件管理信息的操作是分开进行的，所以更新种子文件时文件管理信息和实际的文件信息不符，如果此时机器断电了，种子文件就会损坏甚至丢失，这样的文件系统对安全系统来说是不适用的。一些文件系统使用日志来解决部分问题。日志技术最初是在大型数据库系统中提出来的，而日志就是对文件系统的所有更新操作的列表。如果恰当地使用日志，能够保证在进行更新操作时，文件管理信息和文件信息也是一致的。从可靠性的角度看，使用了日志的文件系统更适用，遗憾的是常见的文件系统只是将日志用于文件管理信息，并不能完全达到我们的要求。如果硬件和操作系统不能保证文件更新的原子性和永久性，就不能安全地使用种子文件。在实际应用中，可以根据具体的工作平台来尽量可靠地更新种子文件。

（6）初次启动

       第一次使用伪随机数生成器时，没有种子文件可以用来设定种子。比如说，一台新的个人计算机，在出厂前就安装了操作系统。安装操作系统的时候需要使用伪随机数生成器来58]生成一些用于管理的密钥，可是为了便于生产所有的计算机都是相同的而且加载了相同的数据、并且没有初始的种子文件，只有等待嫡源产生足够的随机事件来更新种子，但是这需要很长的时间，我们无法确认是否已经收集到足够的熵来生成良好的密钥。
       一个好的方法是，可以让安装过程在配置的过程中为伪随机数生成器生成一个随机种子文件。比如说，可以使用一台单独的计算机上的伪随机数生成器来给每台机器生成种子文件。或者让安装软件要求测试人员移动鼠标来收集初始的熵。可以根据具体的环境来选择解决方案，但是无论如何都要提供初始的熵。熵累加器可能需要一段时间才能给伪随机数生成器设定合适的种子，并且在计算机完成安装之后操作系统很可能需要伪随机数生成器生成一些非常重要的密钥。
       请记住，Fortuna 累加器可能在收集到足够多的真正随机的熵之后，立即给生成器设定种子。但是Fortuna 并不知道熵源实际能提供多少熵，所以可能需要一段时间才能收集到足够的熵来更新生成器的种子。最好的解决方案就是利用一个外部随机源来创建第一个种子文件。

七、选择随机元素

随机数生成器能够提供随机字节序列，在一些情况下这正是用户所需要的，有时用户只需要从其中选出一个随机元素，但需要小心操作。无论何时要选择一个随机元素，都隐含地表示了这个元素是从一个指定的集合中均匀随机选出来的（除非我们指定使用另一种分布），也就意味着集合中的每个元素被选中的概率是相同的9。要实现这种随机性比想象中困难。

第十章——素数

素数是数学中非常重要的一部分内容，但是我们讨论素数更重要的原因在于一些非常重要的公钥密码系统都是基于素数来设计的。

一、整除性与素数

       如果b除以a余数为0，则称a是b的一个因子（记作a|b，读作"a整除b"）。比如，7是35的一个因子，记作7|35。如果一个数只有1和它自身两个正因子，我们就称这个数是素数。如果一个整数大于1且不为素数，我们就称为合数。1既不是素数也不是合数。
       下面是关于整除性的一个简单的引理：
       引理1 ：如果a|b且b|c，那么a|c。
       引理2 ：如果n为大于1的正整数且d为n除1之外最小的因子，那么d是素数。
       定理3 ：（欧几里得）素数有无穷多个
       另一个有用的定理是算术基本定理∶任何一个大于1的整数都可以唯一表示为有限个素数的乘积（不考虑素数的先后顺序）

二、产生小素数

有时候拥有一张小素数的列表是非常有用的，这就要用到Eratosthenes的筛选法，筛选法至今仍然是生成小素数最好的算法。下面的伪代码中2^20可以用任何适当小的常数代替。

三、素数的模运算

假设p为素数，那么进行模p运算时只会使用到0，1，…，p-1。素数模运算的基本规则是，把模运算当作普通的整数运算，但是每一次的结果r都要对p进行取模运算。我们不需要在模运算的两边加上括号，直接写成amod b，但是这样一来，模运算符号看起来就很像—般的正文，那些不太习惯的人就可能觉得有点迷惑。为了避免混淆，我们倾向于使用带括号的记法（amod b）或者a（mod b），到底选择哪种还要看具体的上下文。
有一点值得注意，任何整数（包括负数）取模p运算的结果都在0，…，2-1之中。而一些编语言允许模运算的结果为负值。对此数学家们非常恼火。如果对-1 取模p运算，其结果为p-1。推广到更一般的情况，要计算（amod p），就要先找到满足a=q＋r且0≤r< p的整数q和r，那么（amod p）的值就定义为r。如果令a=-1，那么q=-1，而r=p-1.。

（1）加法和减法

模p加法运算很简单，只需将两个数相加，如果结果大于或者等于p，就减去p。由于加法运算的两个参数都在0，…p-1之中，它们的和不可能超过2p-1，所以最多只要做一次减去p的运算，得到的结果就在正确的范围内了。减法和加法类似，将两数相减，如果结果是负数就加上 p。

（2）乘法

乘法比加法复杂一点。为计算（ab mod p），首先按整数乘法的规则计算ab的值。然后对结果做取模p运算。由于ab的最大可能值为（p-1）2=p-2p+1，所以就需要执行一次长除法来找到满足 ab=qp+r且0≤r< p的（q、r），去掉q，r就是结果。

（3）群和有限域

学家称模素数p的数的集合为有限域，也经常称为"mod p"域，或者简称"mod p"。对于mod p域中的计算有如下一些性质∶

对运算中的每个数，可以加上或减去p的任何倍数而不改变运算的结果。
所有运算的结果都在0，1，…，p-1范围内。
可以在整数范围内做整个计算，只在最后一步做模运算。于是所有关于整数的代数规则（比如 a（b+c）= ab ＋ ac）仍然适用。
我们还需要引入群的概念，这是一个简单的数学术语。群就是一个集合，并且在集合中的元素上定义了一种运算，比如加法或者乘法。eZ，中的元素和加法一起就构成了一个加法群，群中任意两个数相加的结果也是群中的元素。如果在这个群中进行乘法运算就不能使用0（这是因为乘以0没有什么意义，而且0不能做除数）。但是，{1，…p-1}和模p乘法一起也构成一个群，这个群称为模p乘法群并且有多种表示方法，我们使用的是Z。一个有限域包括两个群∶加法群和乘法群。比如，有限域Z，包括了由模p加法定义的加法群和乘法群Z。
群可以包含子群。一个子群由整个群中的一些元素组成，如果对子群中的两个元素进行群运算，得到的结果也要为子群中的元素。听起来有些复杂，不妨举个例子，模8的数和模8加法构成一个群，那么{0，2，4，6}就是它的一个子群子群中任何两个数进行模8加法的结果也是子群中的元素。乘法群也一样，模7乘法群由{1，…，6}和模7乘法运算组成。集合{1，6}就构成一个子群，{1，2，4}也是一个子群。可以验证同一个子群中的任何两个元素进行模7乘法的结果也是该子群中的元素。

（4） GCD 算法

       首先回顾一下GCD的概念∶两个数a和b的最大公因子（或GCD）就是满足ka和kb的最大整数太。换句话说，gcd（a，b）是能够同时整除 a和b的最大的数。欧几里得给出了一个计算两个数 GCD的算法，这个算法在几千年后的今天仍然在使用。对于这个算法的详细讨论可以参考 Knuth。

       这个算法为什么是正确的?首先注意，循环中对a和b的重新赋值不会改变a和b公因子的集合。实际上，（bmod a）就是b-sa，这里s为一个整数。任何同时整除a和b的整数k也能够同时整除a和（bmoda），反之亦然。而当a=0时，b就是a和b的公因子，并且b显然是最大的公因子。另外由于a和b都将越来越小直至为0，所以循环一定会结束。举个例子，我们使用欧几里得算法来计算21和30的GCD。我们由（a，b）=（21，30）开始，第一轮迭代计算（30 mod 21）=9，得到（a，b）=（9，21），接下来计算（21 mod 9）=3，于是有（a，b=（3，9），最后一轮迭代计算（9 mod3）=0.从而得到（a，b）=（0，3）。所以算法输出为3，而3确实是21 和 30 的最大公因子。
       对应于GCD.我们还有LCM（最小公倍数）。a和b的最小公倍数是同时为a和b倍数的最小的数。比如，lem（6，8）=24。GCD和LCM是密切相关的，且满足如下等式∶

（5）扩展欧几里得算法

       然我们无法使用欧几里得算法来做模p除法，为此我们需要扩展欧几里得算法。扩展的欧几里得算法的主要思想是，在计算 ged（a，b）的同时找到满足gcd（a，b）=ua+w的两个整数u和v，找到这样的μ和v我们就能够计算 a/b （mod p）了。

       这个算法非常类似于GCD算法。由于在不变式中涉及原始的a和b，我们引进了新的变量e和d代替a和b。如果只看c和d，这正是GCD算法（稍有不同的是我们重写了dmodc的公式，但结果是一样的）。我们增加了4个变量来保证给定的不变式始终成立，对每一个c值或d值，都明确给出了用a和b的线性组合来表示该值的方法。在初始化中这是容易做到的，因为c初始化为a，d初始化为b; 当在循环中修改ε和d时，更新变量u和，也不十分困难。
       为何要引入扩展欧几里得算法呢?假设要计算 1/bmod p，其中1≤b< p 。我们使用扩展欧几里得算法来计算extendedGCD（b，p），而由于p是素数，所以b和p的GCD是1。但是extendedGCD函数也提供了满足ub＋v= ged（bp）=1的两个数u和v，换言之，ub=1-v或ub=1（mod p），这就是说u=1/b（mod p），即u为b模p的逆。所以除法alb可以通过a乘u计算，即a/b= au（mod p），而计算au（mod p）是比较容易的。
       扩展欧几里得算法使得我们可以计算模素数的逆，从而可以计算模p除法。结合模p的加法、减法以及乘法，我们可以实现有限域模p的4个基本运算。需要注意的是，u可能是负的，所以在把u用作b的逆之前可能需要对它进行模p约化。如果仔细察看extendedGCD算法，会发现如果只需要输出u，可以不管变量v和v。因为它们不会影响u的计算，这样能稍微减少计算模p除法的工作量。

（6）模2运算

在素数的模运算中，一个有趣的特例是模2计算（2 是素数，可以进行模运算）。如果有过编程的经历，就会对下面的内容觉得熟悉。模2加法和乘法表如图 10-1 所示。模2 加法就是编程语言中的异或函数（XOR），乘法是简单的AND运算。在模2 域中，只有一个可能的逆（I/1=1），所以除法运算与乘法运算是相同的。另外，Z2域也是分析某些计算机算法的一个重要工具。

四、大素数

在公钥密码中，我们想要产生 2000～4000 位长度的素数。但是获取如此之大的素数的基本方法非常简单∶选择一个随机数并检查它是否为素数。而且已经有非常好的算法来判断一个大整数是否为素数。素数的数量实际上很多，在整数n的附近，大约每 In n个数中有一个数为素数（n的自然对数。或者简记为Inn，是任何科学计算器都支持的一个标准函数。为了表明大整数的对数值增长之慢，这里给出一个例子∶2^{k的自然对数比0.7·k稍微小一点）。一个2000位的数落在2}1999和2^2000之间，在这个范围内，每 1386个数中就有一个素数，而且其中包括大量明显的合数，比如偶数。

（1）素性测试

       事实上，检测一个数是否为素数是非常容易的，至少与分解一个数并找到其素因子比起来。它是非常容易的。但是这些测试是不完善的，都是概率算法，会有一定的可能性给出错误的答案。不过我们可以通过重复运行同一个测试。把错误的概率降低到一个可以接受的水平。
       这里选择的素性测试是 Rabin-Miller 测试，这个测试虽然简单，但是其数学基础已经超出了本书的范围。该测试的目的是检测一个奇数n是否为素数，我们选择一个不超过n的随机值a，称为基，并检验a模n的某个性质（当n是素数时该性质总是成立的）。然而，当n不是素数时，可以证明这个性质至多对 25??所有可能基值成立。通过对不同的随机值a重复进行这个测试，可以得到一个可信的最终结论。如果n是素数，它将始终被测试为素数;如果n不是素数，那么至少75?能的a值会检测出来，而且可以通过多重测试将n过这个测试的概率达到你想要的那样小。我们把错误结果的概率限定为2-12以达到所需要的安全等级。

       这个算法只对大于或等于3的奇数n有效，于是我们首先测试这一点。函数 isPrime 调用这个函数时应该提供合适的参数，但是每一个函数都应该要检查自己的输入和输出。我们永远不知道软件将会发生什么变化。

       如果对一个随机数使用这个测试，测试结论错误的概率要比我们使用的安全界限小很多很多。这是因为对所有的合数n，几乎所有的基值都将显示n是合数。而正由于这个原因，很多程序库只对大约5个或 10个基执行测试，虽然这种办法也有道理，但是只对那些随机选取的数进行 isPrime 测试时才有效。我们仍然需要分析经过多少次尝试才能使错误概率低于2-1，因为以后我们可能要对从其他人那里接收到的数进行素性测试，而这些数可能是恶意选取的，所以 isPrime 函数本身出错的概率必须要低于 2-12。对于从其他人那里接收到的数，进行完整的64次 Rabin-Miller测试是必需的。但是如果为了获取一个随机素数时，这样做就可能有点过于严格了。不过获取素数时。大部分时间都花在拒绝合数上了（几乎所有的合数都在第一次Rabin-Miller 测试时被拒绝了），所以在找到素数之前可能需要尝试几百个数，对最终的素数做64次测试也只是比 10 次测试慢一点儿而已。
       在本章内容的前一个版本中，Rabin-Miller 例程有第二个参数用于选择最大的错误概率，但这个参数是完全不必要的，所以我们把它去掉了。一般情况下，实现一个错误概率低于固定值2-1的测试更为简单，而且不正确使用的可能性也更小。

（2）计算模指数

abin-Miller测试的大多数时间都花在计算dmod n上。不过我们不可能先计算出a然后再对n取模，这是因为a和s可能都有几千位，世界上甚至都没有计算机有足够的内存来存储d，更不用说有足够的计算能力来计算它了。但我们只需要amod n，我们可以对中间结果使用 mod n来阻止它们变得过大。
有多种方法能够计算a'modn，这里提供一个简单的方案。计算dmodπ时，使用下面的规则∶

如果s =0，那么结果为1。
如果s>0并且s为偶数，那么先使用这些规则计算y=d"modn，结果为d mod n= y" mod n。
如果s>0并且s为奇数，那么先使用这些规则计算y=d-1modn。结果为a mod n = a·y mod n。

       上面使用的是二进制算法（binary algorithm）的一种递归描述。如果仔细观察所执行的操作，就会发现我们从指数的最高有效位部分到最低有效位部分，逐位地计算出最终的指数。另外，将递归算法转换成循环算法也是可行的。
       那么计算a modn需要多少次乘法呢?设s有k位，即2-≤s< 2 ，那么这个算法至多需要进行 2k次模n乘法，这并不太糟糕。如果要对一个2000位的数进行素性测试，则s大约也是 2000位，我们只需要4000次乘法，虽然工作量还是很大，不过却还在大多数桌面计算机的计算能力之内。
       很多公钥密码系统都使用了这类模指数。任何一个优秀的多精度库都应该提供一种优化例程来执行模指数运算，一种称为 Montgomery乘法的特殊方法就很适合这个任务，另外也有一些使用更少的乘法就能计算出a的方法【18，每一种方法都可以使模指数的计算时间减少 10～ 30所以将这些方法结合使用很重要。



、