20181330王茜《密码工程》学习笔记：第九章 生成随机性
第九章 生成随机性
生成随机数的目的：
我们需要随机数生成器（RNG）来生成密钥信息。
生成随机数的必要性：
生成良好的随机性是许多密码操作中非常重要的一部分
好的随机数生成器对于许多密码学函数是非常必要的。
好的随机数的非正式定义：
随机数据是指即使攻击者采取主动攻击来破坏随机性，对于攻击者来说也是不可预测的。
存在问题：
如果采用了错误的随机数生成器，就会得到安全性很低的弱密钥。
这正是 Netscape 浏览器早期的一个版本中存在的问题。
熵
是什么？
衡量随机性的度量称。
解释如下：
如对一个完全随机的32位的字而言。它的熵是32位;如果这个32位的字只有4个可取值，并且每个值都是 25%概率被选中，那么它的熵是2位。
熵度量的不是随机数的位数，而是随机数的不确定性。
对一个随机数而言，知道的信息越多，它的熵越小。
随机变量X的熵的常用定义：
H(X):=-$\sum$P((X=x)log2P(X = x)
P(X=x)表示X取x的概率。
在物理学中，熵是热力学中的一个概念，和这里的熵几乎没有关系。
9.1 真实随机
理想：使用“真实随机”的数据
现实情况：真实随机的数据非常难以找到
典型的计算机具有多个熵源
但是这些熵源在一定程度上都是值得怀疑的
因为在一些环境中，攻击者可以影响或者去测量这些随机熵源。
从各种各样的嫡源中获取的嫡的数量是可观的。
原因：攻击者总是有可能掌握“随机”事件的额外信息。
例如：一个简单的麦克风就能记录按键的声音,进而有助于测量按键时长。
必须非常仔细地估量某个特定的数据中所包含的熵。
有许多物理过程的行为都是随机的。
例如：在量子物理中，一些定律迫使某些行为是完全随机的。
如果能够度量这个随机行为并使用它，是非常好的，在技术上也行得通。
攻击方法：
攻击者可以尝试影响量子粒子的行为，使得它们的运动可以预测；
攻击者可以尝试窃听我们所做的度量。
一旦攻击者获得度量方法，尽管数据仍然是随机的，但是对攻击者而言，数据的熵值为零。
攻击者还可以建立一个强RF场来试图影响我们的检测仪器，甚至还可以想出几种基于量子物理的攻击。
Einstein-Pololsky-Rosen悖论可以用来推翻所度量的数据的随机性。
一些现代计算机内置了真实随机数生成器，特点是：
相比于单独的真实随机数生成器有了显著提高
使得一些攻击更困难
只能被操作系统访问，所以每个应用必须信任操作系统处理随机数据的方法。
9.1.1 使用真实随机数的问题
真实随机数的问题有：
难以获取。
不是随时都可以获取的。
解释：
当利用按键时长来获取随机数时，那么只有用户按键时才能获得
在那些没有键盘的Web服务器上想这样获取随机数就很困难。
相关问题：真实随机数的数量总是有限的，这对于许多需要大量随机数的应用来说是不可接受的。
真实的随机源有可能失效。
解释：
物理随机数生成器
一种失效情况：生成器的输出结果可以通过某种方式来预测。
相关问题：相比于传统的部件更容易失效，甚至可能不知道它什么时候会失效。
真实随机数生成器在计算机的噪声环境中是一个非常复杂的部件
如果直接依赖真实随机生成器，那么当这个生成器失效时就倒霉了。
如何判断从某一具体的物理事件中能够提取多少熵。
除非你为随机数生成器设计了专门的硬件，否则就很难计算嫡的值。
9.1.2 伪随机数
是什么？
是使用真实随机数的一种替代品，实际上并不是真正随机的。
伪随机数的生成：
一般都是通过确定性算法，从种子计算得到。
伪随机数存在问题：
传统的伪随机数生成器（PRNG)是不安全的
这是因为设计伪随机数生成器的初衷是消除统计上的缺陷，而不是为了对抗攻击者。
当对手掌握了生成随机数的算法并得到了一些伪随机数生成器的输出，他就能利用这些信息预测后面(或前面)输出的伪随机数。
一个正确的密码学上的伪随机数生成器来说是不能这样被预测的。
密码系统对伪随机数生成器的要求：
即使攻击者掌握了它输出的随机数，也无法预测该生成器的其他输出结果，那么我们就称这样的伪随机数生成器是健壮的。
编程库中一些常见的随机函数，几乎肯定不是严格的密码学上的伪随机数生成器。
除非给出了明确的密码强度，否则我们都不要使用库中提供的伪随机数生成器。
9.1.3 真实随机数和伪随机数生成器
使用真实随机数的目的：
作为伪随机数生成器的种子。
解决的问题：
一旦伪随机数生成器获得了种子，随机数可以随时获取。
同时我们可以不断获得新的真实随机数作为新的种子。
即使种子泄露，生成器的输出也不可能被完全预测。
真实随机数与伪随机数的区别：
理论上说，真实随机数比伪随机数生成器产生的伪随机数随机性更好。
无条件安全的协议：在一些密码协议中，如果使用真实的随机数，某些攻击是无法成功的。
计算上安全的协议：如果使用伪随机数生成器，协议只有在攻击者无法攻破伪随机数生成器的前提下保证安全。
二者的区别只有理论研究意义，实际中的所有密码协议都只要保证计算上安全。
实际应用中：
针对一种特殊攻击，将一个协议从计算上安全提高到无条件安全没有意义。
无条件安全需要生成真实的随机数，这是非常困难的工作。
真实随机数生成器的弱点也会导致安全性下降。
9.2 伪随机数生成器的攻击模型
利用种子生成伪随机数的关键问题：如何获取一个随机种子并保证它在实际环境中是保密的。
目前为止的最好的设计之一：Yarrow。
设计的目标是试图阻止所有已知的攻击。
伪随机数生成器的工作步骤：
对于每个生成随机数的请求，生成器调用一个密码算法来生成伪随机数
同时更新生成器的内部状态，以保证下次请求不会得到相同的随机数。
对伪随机数生成器的攻击：
攻击者尝试从生成器的输出重构内部状态。
如果攻击者在某一时间点能够获取内部状态，情况就变得更加困难了。
攻击者如何获得内部状态的呢？
可能是实现有漏洞
可能是计算机第一次启动还没有随机种子
或者攻击者设法获取了磁盘上的保存随机种子的文件。
在传统的伪随机数生成器中，如果攻击者获取了内部状态,那么他就可以计算出所有的输出和后续的所有内部状态。
传统的生成器一旦被攻击者成功攻破，就不可能恢复到安全状态了。
如果同一个伪随机数生成器状态被多次使用也会有问题。
例如：两个或更多的虚拟机从同样的状态启动，并从磁盘上读取相同的种子文件。
避免从相同实例启动的虚拟机使用相同的状态，和恢复那些内部状态被窃取的伪随机数生成器到安全状态一样，都非常困难。
因此我们需要一个真实的随机数生成器来作为熵源。
我们假设存在一个或者多个熵源，它们在不可预测的时间内都能提供适量的熵。
攻击者频繁地向伪随机数生成器要求获取随机数
由于两次请求之间所添加的熵总量是有限的
攻击者只需要获得随机输入的所有可能值
就能恢复出适量嫡和原内部状态结合之后的新状态。
最好的防御方法：使用一个熵池来存放包含熵的传入事件。
收集足够多的熵混入内部状态，以保证攻击者无法猜测出熵池中存放的数据。
实际问题：以任何方式估测熵的大小都是困难的，其难易程度依赖攻击者掌握的信息，但是在设计阶段开发者并不知道攻击者能够掌握多少信息。
9.3 Fortuna
是什么？
Fortuna是一个伪随机数生成器。
是 Yarrow的一个改进版本，名字取自于罗马的命运女神。
Fortuna中无须使用熵估值器，从而解决了定义熵值计量的问题。
Fortuna的三个组成部分：
生成器：负责采用一个固定长度的种子，生成任意数量的伪随机数
累加器：负责从不同的嫡源收集嫡再放入熵池中，并间或地给生成器重新设定种子
种子文件管理器：负责保证即使在计算机刚刚启动时伪随机数生成器也能生成随机数。
9.4 生成器
生成器的作用：
负责将固定长度的内部状态转换为任意长度的输出。生成器的内部状态包括一个256位的分组密码密钥和一个128位的计数器。
生成器是什么？
可以认为是一个计数器模式的分组密码，CTR模式能够输出一串随机数据流。
我们使用类似AES的分组密码作为生成器，也可以使用AES ( Rijndael)、Serpent或者Twofish。
生成器是如何工作的？
用户或者应用请求随机数
生成器执行算法生成伪随机数据。
在处理完每次请求后，会额外生成一个256位的伪随机数据并把它作为分组密码的新密钥，然后清除旧密钥
这样消除了所有泄露之前请求信息的可能性。
注意事项：
不能同时生成太多的随机数据。
原因：
真实的随机数据中可以存在重复的块值，但是计数器模式下输出的随机数中各块的值肯定不同
为保证生成的随机数据满足统计上的随机性
解决方法：
每个密文块只使用一半，这样就会消除大部分的统计误差。
不使用分组密码，而是利用伪随机函数。
但是目前并没有一个安全高效、经过详尽分析的伪随机函数能满足我们的要求。
限制单个请求中生成的随机数据的字节数，这样就能使统计偏差更难检测。
如果想从一个密钥生成264位的输出块：
希望分组值中存在一个碰撞，但是生成器缺少这样的碰撞。
所以进行多次请求就会发现输出并不是完全随机的。
解决办法：将请求生成的随机数的最大长度设为216块(也就是22字节)。
分析：
对一个理想的随机数生成器而言：
如果输出2个块，那么发生分组值碰撞的概率是2-97
所以必须经过297次请求才能检测到碰撞是否存在
攻击者完成攻击就需要经过2113步
这已经很接*2128步的目标了
缺陷：稍微降低了安全等级
因为没有适合的密码学构建块方法能够使伪随机数生成器完全达到128位安全等级。
使用SHA-256会使效率降低许多。
使用完美的密码学伪随机数生成器会降低效率。
但使用安全性很低的伪随机数生成器，会让整个系统的安全性下降。
攻击进展的快慢不是由攻击者的计算机决定的，而是由被攻击的计算机的性能决定的。
如果分组密码的分组长度为256位，就不用考虑上面的碰撞问题。
但大部分用户并不会为了帮助攻击者，而让计算机有过多的计算能力。
在每次请求结束后，分组密码的密钥会被重置，但是计数器不需要重置。
解决问题：避免出现密钥周期过短的问题。
由于计数器是128位的，所以计数器值的重复问题就不需要考虑了
当计数器的值为0时就表示生成器没有密钥,因此不能产生任何输出。
注意：
对每次请求只能获得1MB 数据的限制并不是一个不灵活的限制
如果需要超过1MB的随机数据，可以重复发送请求。
在实现中提供了自动执行这样的重复请求的接口。
生成器是一个非常有用的模块
不仅是Fortuna的一个组成部分，
也是实现接口的一部分。
一个进行Monte Carlo仿真的程序，希望仿真是随机的，但是希望在调试和验证时能够重复同样的仿真
解决方案：
在程序开始的时候调用操作系统的随机数生成器并获取一个随机种子
把种子可以看作仿真器的一个输出
生成器从这个种子可以生成仿真需要的所有随机数据
有了生成器的初始种子，仿真程序就可以利用同样的输入数据和种子对所有计算进行验证
在调试时，由于初始的种子不变，所以相同的仿真过程可以多次进行,每次的表现都会是完全相同的。
9.4.1 初始化
将密钥和计数器设置为0，表示生成器还没有获取种子。
具体步骤如下图所示：
9.4.2 更新种子
通过输入任意字符串更新生成器状态。
不用关心输入字符串的具体内容。
使用散列函数，保证输入字符串和现有密钥完全混合。
具体步骤如下图所示：
计数器C：
被用作整数
后面会被用作一个明文分组
我们使用最低有效字节在前的方式来实现二者之间的转换。
9.4.3 生成块
作用：生成多个随机块。
只能被生成器调用，伪随机数生成器之外的任何模块都不能调用该函数。
具体步骤如下图所示：
E(K,C)是一个分组密码加密函数
密钥：K
明文：C
$\varepsilon$：空字符串。
GenerateBlocks函数首先判断C是否为0
当C等于0时：生成器还没有获得种子。
接着以空字符串r开始一个循环
在循环中将每个新计算的随机块附加到r上以获得最终的输出。
9.4.4 生成随机数
作用：
当用户请求随机数时，生成器就会调用这个函数来产生随机数据。
输出长度最多可达220字节。
该函数还会确保之前生成的结果信息都已经被清除。
具体步骤如下图所示：
函数的输出：
通过调用GenerateBlocks得到的
唯一的区别：返回时只截取了前n个字节
接着还需多生成两个随机块来生成新密钥
一旦更新了旧密钥K,r就无法被重新计算出来了。
即使以后生成器被成功攻击了，也不会影响之前生成的随机数的保密性。
生成器之后产生的随机数的保密性就得不到保障。
如何获得更长的随机字符串？
可以通过多次调用来。
不能增加每次调用的最大输出长度，这样会增加统计偏差。
重复调用PesudoRandomData函数实现起来比较高效
唯一的额外开销：每产生1MB的随机数据，都必须生成额外32字节的随机字节来更新密钥和计算分组密码的密钥表。
9.4.5 生成器速度
上面介绍的Fortuna生成器：
在密码学上健壮的伪随机数生成器
能够利用随机种子获得任意长度的伪随机输出。
Fortuna生成器运行的速度主要依赖于使用的分组密码算法。
9.5 累加器
累加器：
负责从不同的熵源中获取实随机数
用来更新生成器的种子。
9.5.1 熵源
要求：
保证至少一个熵源提供的熵（用于生成数据）是攻击者无法预测的。
应该尽可能多地使用实际可行的其他时序上的熵源。
只要保证攻击者无法同时获取所有熵源的随机信息就可以。
熵源的实现：
一般来说，熵源都会被嵌入到操作系统的各种硬件驱动器中，用户几乎不可能完成这项工作。
为每个熵源指定唯一的熵源编号（熵源号)。
取值范围：0到255。
熵源号的两种分配方式：
静态分配
动态分配
熵源产生事件所包含的数据：
是一连串字节
每个事件中都包含了不可预测的数据
要将不同熵源产生的事件链接起来。
要确保这个字符串是可解析的。
每个事件都被编码为3个或更多的字节。
第一个字节表示事件的随机熵源号
第二个字节表示数据的附加字节数
后续字节包括熵源提供的任何数据。
面临攻击：攻击者可能获取部分熵源产生的事件。
9.5.2 熵池
作用：
为了更新生成器的种子，将事件放入一个足够大的熵池中
“足够大”意味着攻击者无法穷举出嫡池中事件的所有可能值。
Fortuna解决上述问题的步骤：
一共设置32个熵池P0,P1,···，P31。
理论上：每个熵池都包含一个无限长的字符串。
实际上：无须存储这个无限长的字符串，而可以在向熵池中添加事件的同时计算散列值。
每个熵源循环地向32个熵池中添加随机事件
保证每个熵源产生的熵被大致均匀地分发到各个熵池中
每个事件在被放入熵池时，就将事件包含的随机信息附加到嫡池中原来的字符串后面。
当P0池中字符串长度足够时，就更新生成器的种子。
一个或多个池中的字符串会被用来生成种子。
每次生成种子都会用到P。
一旦某个熵池参与生成新的种子，熵池中的内容就会被重置为空字符串。
攻击：
如果攻击者了解的熵源信息非常少，那么在更新种子前他就无法预测P0中熵的大小。
攻击者可能掌握熵源的很多信息，或者他能够伪造出许多随机事件
只要他无法预测某个熵源产生的事件，那么总会有一个熵池能够包含足够的嫡来抵抗攻击。
如果生成器的某个状态被泄露了，它恢复到安全状态的速度取决于熵流入熵池的速度。
假设嫡以固定的速率p流入熵池，那么经过时间t后共产生pt位的熵，所以每个熵池中增加了大约pt/32位的熵,如果在生成器更新种子时使用了一个存储了大于128位熵的熵池，则攻击者无法获得生成器的新状态。
有两种情况：
第一种情况：如果P0在下一次更新种子前能够收集到128位的熵，那么生成器就恢复到安全状态了。
第二种情况：由于随机事件对于攻击者来说是已知的，一旦Pi参与新的种子，生成器就能恢复到安全状态了。
恢复到安全状态所需时间(2‘t)的上限就是获取213位熵所需时间（8192/p)。
Fortuna 比 Yarrow最大的改进之处
不必再花费心思构建熵估值器。
生成器完全能够自动恢复到安全状态。
存在问题：有可能P在两次更新种子之间无法收集到足够的随机性来使生成器恢复到安全状态。
改进方法：限制种子更新的速度。
一个种子只有存在超过100毫秒时才可以被更新
如果存在嫡池P32，那么每13年它才可能被使用一次。
9.5.3 实现注意事项
设计累加器的一些实现上的注意事项:
基于熵池的事件分发
解决方案：
让累加器负责这项工作
风险：
如果累加器负责分发事件，那么就会有一个函数实现把事件交给累加器的功能，可能攻击者任意调用这个函数。
攻击者可以在每次生成“真实的”事件后，对该函数进行额外地重复调用来影响下一次“真实的”事件会被放入哪个熵池中。
如果攻击者用累加器将所有“真实的”事件都放入P0中，那么整个多熵池系统的效率就会下降，并且可以使用针对单熵池系统的攻击方法实施攻击。
如果攻击者使得所有的“真实的”事件都被放入P31中，那这些事件基本上永远不会被采用。
解决方案：让每个事件发生器在产生事件的同时就确定事件将要放入的熵池号。
针对的攻击：
必须要有对生成事件的程序内存的访问权限，才能影响事件被放入的熵池的选择。
但如果攻击者拥有这么大的权限，这个熵源也很可能已经被攻破了。
累加器可以检查熵源是不是按正确的顺序将事件放入到熵池中。
但是，不能通过验证时，累加器该如何应对呢？
如果整个伪随机数生成器被用作用户进程，那么这个进程可能会抛出严重错误并退出程序。
解决办法：减少这个驱动程序所占用CPU时间。
结论：
累加器不应该负责检查事件是否以正确的顺序放入熵池中，因为即使累加器检测到错误它也无法处理。
每个熵源应该负责将事件循环分发到熵池中，如果哪个熵源弄错了，那么这个熵源产生的熵可能会丢失。
事件发送的运行时间
当一个事件被发送给累加器的时候，希望能够对需要进行的计算量进行限制。
但是，有少量计算是必须要完成的。必须将事件数据添加到指定的熵池中。
对于每个熵池，我们将分配一个缓冲区，当缓冲区满的时候，计算缓冲区包含内容的部分散列值。
使用一个或多个熵池来更新种子，所需要的时间是添加事件到熵池所需要时间的一个数量级以上。
更新种子不会作为累加器处理事件的必需运算，而是等到下次用户请求获取随机数据时，在随机数据生成之前才会进行。
为了保证更新种子的操作在随机数据请求之前进行，必须对生成器进行封装。
如果熵池中的字符串长度达到一个块的长度时就立即进行处理，那么每个事件最多会导致一次散列块运算。
缺点：如果只处理一个散列块，CPU也需要将散列函数的源代码读入到最快的高速缓冲存储器中才可进行运算。
如果能够使CPU总是在执行一小段的循环程序并不让它在不同的代码段之间进行切换，那CPU的性能就会显著提高。
结论：
可以选择扩大熵池的缓冲区，使得在计算散列值之前缓冲区中能够收集到更多的数据。
优点：能够减少CPU计算总时间
缺点：将事件添加到嫡池中所需要的最长时间变长
9.5.4 初始化
函数功能：实现了Fortuna的一些外部接口，是在整个伪随机数生成器上进行操作的。
9.5.5 获取随机数据
函数功能：
对伪随机数生成器的生成器组件进行封装
处理更新种子。
函数分析：
首先将P0的长度和 MinPoolSize进行比较，以此来决定是否需要更新种子。
为了能够收集128位的熵，那么MinPoolSize的一个合适的大小为64字节。
将种子更新计数器的值增加1。
保证只有P0会参加种子的第一次更新。
循环代码段的作用：将各熵池中字符串的散列值进行连接。
先将熵池的内容进行连接再计算散列值不如现在使用的更方便。
待优化：
2ilReseedCnt用来检测2i是不是ReseedCnt 的因子
如果是，则值为真
一旦某个i值不能通过测试，那么后续循环中的测试也都不会通过。
9.5.6 添加事件
函数作用：
当熵源产生了新的随机事件时，就会调用该函数。
每个熵源都有唯一的熵源编号
函数分析：
事件e经过编码后长度为2+length(e)个字节，其中熵源号s 和 length(e)各占一个字节
将编码后的事件添加到熵池中。
注意：这里假设只有熵池被使用时才会对其进行散列运算。
在实现中：我们应该一边向熵池中添加事件一边计算散列值。
熵源应该发送简短而又不可预测的随机数据给累加器。
如果一个熵源生成了一个随机信息很长的事件，而且事件包含的嫡是均匀分布的，那么熵源先对随机信息进行散列。
要保证AddRandomEvent函数总是能够快速返回。
原因：
许多熵源提供实时服务
即使一个熵源产生事件所包含的随机信息比较短，也不应该让它在产生较大事件的熵源之后调用AddRandomEvent。
另一种实现添加事件的架构：
方法：
让熵源仅仅把事件发送给累加器进程，再由累加器创建一个单独的线程负责所有的散列运算。
评价：
这个设计更加复杂，不过能减轻嫡源的运算负担。
9.6 种子文件管理
目前存在问题：
每次计算机重启后，要等到熵源提供足够的事件后，才能获取第一个种子生成随机数据；
也无法保证第一次种子后的状态是攻击者无法预测的。
解决方案：使用种子文件。
种子文件是什么？
伪随机数生成器保存了一个熵文件。
种子只有伪随机数生成器可以获取。
每次重启之后，伪随机数生成器读取种子文件并使用文件内容作为熵源来获得一个未知状态。
种子文件在每次使用之后都需要重新写入内容。
本节内容：
在一个支持原子操作的文件系统中如何管理种子文件
在实际的系统中实现种子文件管理时遇到的问题
9.6.1 写种子文件
解决的第一个问题：如何生成种子文件
解决方法：通过以下这个简单的函数实现
函数执行结果：生成64字节的随机数据，然后写入文件。
9.6.2 更新种子文件
作用：我们通常将种子文件的读取和更新操作一起完成。
具体函数如下图：
函数分析：
函数操作：
读取种子文件
检查种子长度
更新生成器的种子
用新数据更新种子文件。
必须保证更新种子和更新种子文件之间伪随机数生成器没有被调用过。
那样会带来问题：违背了随机数据的保密性。
一次重启之后，该函数读取种子文件并用来更新种子
假设攻击者在种子文件更新之前向伪随机数生成器请求获取随机数据
并且在获取到随机数据时，且在更新种子文件之前立刻重启计算机。
在下次启动之后，相同的种子文件会被读取并被用来更新种子，
如果在种子文件更新前一个用户请求随机数据，那么他获取的随机数据就和刚才攻击者获取的随机数据是相同的。
在实现中必须保证：
种子文件是被秘密保存的
种子文件的所有更新都必须是原子操作
9.6.3 读写种子文件的时间
使用种子文件的原因：
在计算机刚刚启动的时候，伪随机数生成器并没有熵来生成随机数。
所以在每次启动后，都需要对种子文件进行读取和更新。
计算机在运行的时候能够从各种熵源收集的熵，最终也能够影响种子文件的内容。
解决办法：在关闭计算机之前对种子文件进行更新，
要保证伪随机数生成器在收集到相当数量的熵后能够定时更新种子文件
解决方案：在每次关机时以及每10分钟左右对种子文件进行一次更新。
9.6.4 备份和虚拟机
大部分存放种子文件的文件系统并不能保证避免出现重复状态，因此带来一些问题：
备份
问题描述：在累加器收集到足够的嫡之前，伪随机数生成器在两次重启之后生成的输出是相同的。
攻击：攻击者也可以利用这种方法来获取用户从伪随机数生成器那里得到的随机数据。
防御方法：
没有直接的防御方法。
最理想的方法：修复备份系统使得它对伪随机数生成器敏感。
可以将种子文件的内容和当前时间进行散列之后再使用。
前提：攻击者不会将时钟恢复到相同的时间。
可以将种子文件的内容和恢复计数器的值进行散列之后再使用。
前提：备份系统有一个计数器记录已经进行过多少次恢复
虚拟机上的问题
问题描述：如果一个虚拟机状态被保存了，然后重启了两次，那么从同一状态启动的两个实例，其伪随机数生成器的状态也是相同的。
解决方法：和解决备份的方法类似
这些问题太过于依赖具体平台。
9.6.5 文件系统更新的原子性
种子文件的另一个问题：文件系统更新的原子性。
在大多数操作系统中，对种子文件的写操作仅仅是对一些内存缓冲区进行更新，很久之后才会将数据真正写到磁盘上。
尽管一些文件系统提供了“flush”命令，但是这个操作执行得非常缓慢，而且有时候硬件上并不会真正执行。
使用种子文件来更新种子时：
都要在用户请求随机数据之前更新种子文件
必须要保证磁盘上的数据也进行了更新
存在问题：
在一些文件系统中，对文件数据和文件管理信息的操作是分开进行的
更新种子文件时会造成文件管理信息和实际的文件信息不符
解决办法：一些文件系统使用日志来解决部分问题。
日志技术最初是在大型数据库系统中提出来的。
日志：对文件系统的所有更新操作的列表。
从可靠性的角度看：使用了日志的文件系统更适用安全系统
但是常见的文件系统只是将日志用于文件管理信息，达不到我们的要求。
如果硬件和操作系统不能保证文件更新的原子性和永久性，就不能安全地使用种子文件。
9.6.6 初次启动
问题：第一次使用伪随机数生成器时，没有种子文件可以用来设定种子。
只有等待熵源产生足够的随机事件来更新种子
这不仅需要很长的时间
我们还无法确认是否已经收集到足够的熵来生成良好的密钥。
解决方法：
可以让安装过程在配置的过程中为伪随机数生成器生成一个随机种子文件。
可以根据具体的环境来选择解决方案，但是无论如何都要提供初始的熵。
Fortuna累加器可能在收集到足够多的真正随机的熵之后，立即给生成器设定种子。
但是，Fortuna并不知道熵源实际能提供多少熵。
最好的解决方案：利用一个外部随机源来创建第一个种子文件。
9.7 选择随机元素
用户一般只需要从伪随机数生成器提供的随机字节序列中选出一个随机元素。
操作问题：集合中的每个元素被选中的概率是相同的，要实现这种随机性比想象中困难。
设集合中元素个数为n，只需讨论如何从{0,1,…,n-1}中随机选择一个元素。
如果n=0，没有可以选择的元素，报错
如果n=1，只能选择唯一的一个元素，处理也比较简单
如果n=2k，向伪随机数生成器请求一个k位的随机数据并转化为0到n-1中的一个整数，这个数是均匀随机的。
当n不为2的幂时，有些程序选择一个32位的随机整数再对n取模，但是这种算法结果的概率分布是有偏差的。虽然偏差非常微小，但是也可能非常显著。
在任意范围中选择一个随机数的正确方法：试错法。
可以生成一个位数正确的随机数并丢弃那些不合适的值。
下面是在0,···,n一1 (n≥ 2）中选择一个随机数算法的正式描述：
令k为满足2k≥n的最小整数。
利用伪随机数生成器生成一个k位的随机数K，K的范围为0,···,2k-1。
可能需要丢弃最后一个字节的部分位。
如果K≥n，返回第2步。
K就是结果。
缺陷：可能有点浪费，在最坏的情况下，平均一半的中间值会被丢弃。
改进方案：
首先选择一个合适的k满足2k≥n，定义q:=[2k/n]
利用尝试法在0,···,nq-1中选择一个随机数r，一旦生成一个合适的r那么最终的随机数就是(r mod n)。
为了获取元素个数不是2的幂集合中的一个均匀随机数，算法或多或少都需要利用丢弃随机位方法。
收获&问题&思考
本章我们学*的主要是随机数相关内容，包括随机性、真/伪随机数生成器、熵、如何获得真随机数等等，对密码系统中随机数的部分有所了解和掌握。
本书已经学*了将*一半了。
书中开始的时候说我们要构建一个密码系统，刚看的时候觉得这么大的系统，无从下手。
但是书中把每一部分分开，然后慢慢分析。
从中先发现问题、提出问题，再解决问题。
这样的思路是非常好的。
平时我们不论是学*还是完成大的任务时，不要怕刚开始做得不好。
重要的是先开始做，再一点一点发现问题，去解决和优化。
否则可能永远也开始不了。
书中伪随机生成器这一节提到，要使用完美的伪随机数生成器，那么就会造成效率降低。所以在很多时候安全性和效率是不可兼得的。
要很高的安全性，就要舍弃效率，多次运算；
要高效率，就要失去一部分安全性；
在实际中要综合考虑，看实际情况更需要安全性还是效率。
在之前上课，老师都讲过一般的编程语言中自带的随机数生成算法生成的并不是真正的随机数，而是伪随机数。学*了这一章之后更深入地理解了这句话的意思。
这些生成的伪随机数在平时写一些小的程序还是可以的，但是在一些大的系统和我们书中实现的这种安全性极高的系统中，是很容易收到攻击的，不能采用这些算法。