内核熵池的基本原理

Linux内核采用熵来描述数据的随机性。熵（entropy）是描述系统混乱无序程度的物理量，一个系统的熵越大则说明该系统的有序性越差，即不确定性越大。在信息学中，熵被用来表征一个符号或系统的不确定性，熵越大，表明系统所含有用信息量越少，不确定度越大。

计算机本身是可预测的系统，因此，用计算机算法不可能产生真正的随机数。但是机器的环境中充满了各种各样的噪声，如硬件设备发生中断的时间，用户点击鼠标的时间间隔等是完全随机的，事先无法预测。Linux内核实现的随机数产生器正是利用系统中的这些随机噪声来产生高质量随机数序列。

内核维护了一个熵池用来收集来自设备驱动程序和其它来源的环境噪音。理论上，熵池中的数据是完全随机的，可以实现产生真随机数序列。为跟踪熵池中数据的随机性，内核在将数据加入池的时候将估算数据的随机性，这个过程称作熵估算。熵估算值描述池中包含的随机数位数，其值越大表示池中数据的随机性越好。

很多库例程产生的“随机”数是准备用于仿真、游戏等等；它们在被用于密钥生成一类的安全函数时是不够随机的。其问题在于这些库例程使用的算法的未来值可以被攻击者轻易地推导出来（虽然看起来它们可能是随机的）。对于安全函数，需要的随机值应该是基于量子效应之类的确实无法预测的值。Linux内核（1.3.30以上）包括了一个随机数发生器/dev/random，对于很多安全目的是足够的。

/dev/random 是如何创建随机数的呢？

Linux *** 作系统提供本质上随机（或者至少具有强烈随机性的部件）的库数据。这些数据通常来自于设备驱动程序。例如，键盘驱动程序收集两个按键之间时间的信息，然后将这个环境噪声填入随机数发生器库。

随机数据存储在 熵池中，它在每次有新数据进入时进行“搅拌”。这种搅拌实际上是一种数学转换，帮助提高随机性。当数据添加到熵池中后，系统估计获得了多少真正随机位。

测定随机性的总量是很重要的。问题是某些量往往比起先考虑时看上去的随机性小。例如，添加表示自从上次按键盘以来秒数的 32 位数实际上并没有提供新的 32 位随机信息，因为大多数按键都是很接近的。

从 /dev/random 中读取字节后，熵池就使用 MD5 算法进行密码散列，该散列中的各个字节被转换成数字，然后返回。

如果在熵池中没有可用的随机性位， /dev/random 在池中有足够的随机性之前等待，不返回结果。这意味着如果使用 /dev/random 来产生许多随机数，就会发现它太慢了，不够实用。我们经常看到 /dev/random 生成几十字节的数据，然后在许多秒内都不产生结果。

幸运的是有熵池的另一个接口可以绕过这个限制：/dev/urandom。即使熵池中没有随机性可用，这个替代设备也总是返回随机数。如果您取出许多数而不给熵池足够的时间重新充满，就再也不能获得各种来源的合用熵的好处了；但您仍可以从熵池的 MD5 散列中获得非常好的随机数！这种方式的问题是，如果有任何人破解了 MD5 算法，并通过查看输出了解到有关散列输入的信息，那么您的数就会立刻变得完全可预料。大多数专家都认为这种分析从计算角度来讲是不可行的。然而，仍然认为 /dev/urandom 比 /dev/random 要“不安全一些”（并通常值得怀疑）。

应用中出现的问题：

在我们的服务器程序中，用户登陆的时候会读取/dev/random产生随机数，问题来了，当用户登陆比较密集，这时候read就会返回特别慢，并且返回的字节数也比要求的少，甚至不返回――阻塞。我们把用户登陆处理函数放在了线程池里，导致的问题就是线程池里所有线程都可能会阻塞，这就造成了拒绝服务攻击。导致其他用户登陆失败。

解决方案：

CODE:1 #include <stdio.h>

2 #include <string.h>

3 #include <sys/types.h>

4 #include <sys/stat.h>

5 #include <sys/file.h>

6 #include <sys/time.h>

7 #include <errno.h>

8 #include <unistd.h>

9 #include <stdlib.h>

10

11 static int get_random_fd (void)

12 {

13 static int fd = -2

14

15 if (fd == -2)

16 {

17 fd = open ("/dev/random", O_RDONLY | O_NONBLOCK)

18 if (fd == -1)

19 fd = open ("/dev/urandom", O_RDONLY | O_NONBLOCK)

20 }

21

22 return fd

23 }

24

25 /*

26 * Generate a series of random bytes. Use /dev/random if possible,

27 * and if not, use /dev/urandom.

28 */

29 void get_random_bytes(void* buf, int nbytes)

30 {

31 int i, fd = get_random_fd()

32 int lose_counter = 0

33 char *cp = (char*)buf

34 struct timeval tv

35 static unsigned seed = 0

36

37 if (fd >= 0)

38 {

39 while (nbytes >0)

40 {

41 i = read (fd, cp, nbytes)

42 if ((i <0) &&

43 ((errno == EINTR) || (errno == EAGAIN)))

44 continue

45

46 if (i <= 0)

47 {

48 if (lose_counter++ == 8)

49 break

50

51 continue

52 }

53 nbytes -= i

54 cp += i

55 lose_counter = 0

56 }

57 }

58

59 for (i = 0i <nbytesi++)

60 {

61 if (seed == 0)

62 {

63 gettimeofday(&tv, 0)

64 seed = (getpid() <<16) ^ getuid() ^ tv.tv_sec ^ tv.tv_usec

65 }

66 *cp++ = rand_r(&seed) &0xFF

67 }

68

69 return

70 }

13行： 定义fd为静态变量，这样只打开一次设备。

17 – 19行： 无阻塞模式打开/dev/random设备。如果该设备打开失败尝试打开/dev/urandom。

29行： void get_random_bytes(void* buf, int nbytes)函数是提供给用户的接口，用户调用这个函数就可以得到随机数。

37－57行： read有可能返回的字节数小于请求的字节数。这时候就循环读直到读够了所请求的大小。这样最多重复8次。然后返回。

59－67行： 如果上面重复8次都没有读够所请求的字节数，则我们自己生成随机数来填充。

注意：打开的fd我们并没有关闭，请您根据自己需求在合适的地方关闭。

有两个最主要的方法来生成随机数：

a) 通过测量某些随机的物理现象，然后补偿测量过程中可能出现的偏差。比如大气噪声、热噪声和其他外部电磁以及量子现象。从自然资源中获取熵的速度取决于被测量的潜在物理现象，因此它们的速率是有限的，往往比较慢。

b) 使用计算算法，可以产生明显随机结果的长序列，实际上由较短的初始值（称为种子）确定。结果是，如果种子的值是已知的，整个看似随机的序列可以被重复产生。这类随机数生成器被称为伪随机数生成器。这类生成器类型是非阻塞的，可以大量产生数据。

/dev/random 可以用作随机数生成器或者伪随机数生成器，取决于不同的实现。

在linux下，随机数生成器有一个容纳噪声数据的熵池，在读取时，/dev/random设备会返回小于熵池噪声总数的随机字节。/dev/random可生成高随机性的 公钥 或 一次性密码本 。若熵池空了，对/dev/random的读 *** 作将会被 阻塞 ，直到收集到了足够的环境噪声为止。这样的设计使得/dev/random是真正的 随机数发生器 ，提供了最大可能的随机数据熵，建议在需要生成高强度的密钥时使用。

/dev/urandom（“unblocked”，非阻塞的随机数发生器），它会重复使用熵池中的数据以产生伪随机数据。这表示对/dev/urandom的读取 *** 作不会产生阻塞，但其输出的熵可能小于/dev/random的。它可以作为生成较低强度密码的伪随机数生成器，不建议用于生成高强度长期密码。

FreeBSD *** 作系统实现了256位的Yarrow算法变体，以提供伪随机数流。与Linux的/dev/random不同，FreeBSD的/dev/random不会产生阻塞，与Linux的/dev/urandom相似，提供了密码学安全的伪随机数发生器，而不是基于熵池。而FreeBSD的/dev/urandom则只是简单的链接到了/dev/random。

OpenSSL的提供了RAND_bytes方法生成随机数。在使用之前需要使用RAND_add向PRNG中添加种子及熵值。种子可以通过TSC生成。

CryptoAPI提供了CryptGenRandom方法产生随机数。CryptGenRandom已经被废弃，应该使用新版CNG API：BCryptGenRandom

CPU指令rdrand从芯片的硬件随机数生成器中获取随机数

32位：

64位：

BTC采用了多种方式混合的形式，将OpenSSL随机数生成、OS随机数生成、硬件随机数生成再混淆随机数发生器的状态来生成强随机数。

参考文档：

https://en.wikipedia.org/wiki/Random_number_generation#%22True%22_vs._pseudo-random_numbers

https://zh.wikipedia.org/wiki//dev/random

https://www.openssl.org/docs/man1.0.2/crypto/RAND_seed.html

https://zh.wikipedia.org/zh-hans/RdRand

---