Linux内核随机数产生器的设计与实现--转

这几天抽了点时间看了看linux 2.6.10的代码,对里面的那个内核随机数产生器发生兴趣,花了点工夫分析了下,贴在这里灌水.
--------------------------------------------------------------------------------------------
随机数在许多领域都有重要应用,如Monte Carlo模拟、密码学和网络安全。随机数的质量直接关系到网络安全系统的可靠性和安全性，关系到 Monte Carlo模拟结果的可信度。自从计算机诞生起，寻求用计算机产生高质量的随机数序列的研究就一直是个长期受到关注的课题。Linux内核从 1.3.30版本开始实现了一个高强度的随机数发生器，本文根据Linux 2.6.10内核的源代码，详细分析该随机数产生器的设计与实现。

1． 基本原理
Linux内核采用熵来描述数据的随机性。熵（entropy）是描述系统混乱无序程度的物理量，一个系统的熵越大则说明该系统的有序性越差，即不确定性越大。在信息学中，熵被用来表征一个符号或系统的不确定性，熵越大，表明系统所含有用信息量越少，不确定度越大。
计算机本身是可预测的系统，因此，用计算机算法不可能产生真正的随机数。但是机器的环境中充满了各种各样的噪声，如硬件设备发生中断的时间，用户点击鼠标的时间间隔等是完全随机的，事先无法预测。Linux内核实现的随机数产生器正是利用系统中的这些随机噪声来产生高质量随机数序列。
内核维护了一个熵池用来收集来自设备驱动程序和其它来源的环境噪音。理论上，熵池中的数据是完全随机的，可以实现产生真随机数序列。为跟踪熵池中数据的随机性，内核在将数据加入池的时候将估算数据的随机性，这个过程称作熵估算。熵估算值描述池中包含的随机数位数，其值越大表示池中数据的随机性越好。

2． 设计与实现
Linux 内核随机数产生器在/drivers/char/random.c中作为字符设备实现。在模块初始化函数rand_initialize()中调用 create_entropy_store()分别创建名为random_state的缺省熵池，一个名为sec_random_state和一个名为 urandom_state的熵池。熵池用struct entropy_store来表示。
内核实现了一系列接口函数用于获取系统环境的噪声数据，并加入熵池，分别是：
void add_interrupt_randomness(int irq)；
void add_keyboard_randomness(unsigned char scancode)；
void add_mouse_randomness(__u32 mouse_data)；
void add_disk_randomness(struct gendisk *disk)；
其中add_interrupt_randomness()函数利用设备两次中断的间隔时间作为噪声源将随机数据加入熵池。要使设备的中断作为系统噪声，必须用SA_SAMPLE_RANDOM标志注册其中断服务程序。这样，每当设备发生中断时，中断系统会自动调用 add_interrupt_randomness()将熵加入熵池。
Add_keyboard_randomness()将按键的扫描码和两次按键之间的时间间隔作为噪声源；而add_mouse_randomness()则利用鼠标位置和连续两次鼠标中断时间间隔填充熵池；最后 add_disk_randomness()函数则以连续两次磁盘操作之间的间隔产生随机数。
上面的函数最终都是通过调用 add_timer_randomness()函数将熵加入熵池的。Add_timer_randomness()首先估算所加数据的熵，再调用 batch_entropy_store()函数将数据加入熵池。为了避免中断的延迟过长影响系统性能，batch_entropy_store()并不直接将熵加入熵池，而是将其加入队列中。当队列长度达到一定长度后，由keventd内核线程通过调用batch_entropy_process()函数将队列中的熵加入池中。
Batch_entropy_process()函数枚举队列中的每个熵，对每个熵调用 add_entropy_words()函数将其加入熵池，但它并不更新熵池的熵估算值。为此，batch_entropy_process()对每个熵调用完add_entropy_words()后，立刻调用credit_entropy_store()函数更新熵估算值。
相对于输入接口，Linux内核同样实现了一系列输出接口用来向用户空间或内核其他模块输出随机数序列。
其中void get_random_bytes(void *buf, int nbytes)函数用于向内核其他模块输出随机数。它从熵池中返回 nbytes个字节的随机数序列存入buf中。该函数优先从urandom_state池中返回随机数，如果不存在urandom_state熵池则从 sec_random_state池返回数据，只有在前两者都不存在的时候才从缺省池random_state返回随机数。 get_random_bytes()总是返回nbytes个字节的随机数序列，即使熵池的熵估算值为0。
此外，内核提供了两个字符设备： /dev/random和/dev/urandom，其read函数（random_read()和urandom_read()）用于向用户模式程序输出随机数序列。上层应用程序可以通过read系统调用从它们获取随机数序列。相对于/dev/urandom接口，/dev/random输出的随机数序列质量更高，适合于高强度的加密算法。/dev/urandom总是返回所请求的随机数序列，无论熵池的熵估算值是否为零；而/dev/random则只返回熵估算值所允许的最长的随机数序列，当熵估算值为零时，请求将被阻塞直到熵估算值增大到一定域值。
上述输出接口最终均是通过调用 extract_entropy()函数输出随机数序列。Extract_entropy()函数使用SHA或MD5算法散列(Hash)熵池，将散列后的结果作为随机数序列输出给用户使用，这样避免了直接访问熵池中的内容。由于从SHA或MD5算法散列的结果反推原始数据的可能性几乎为零，所以这种设计极大的提高了安全性。攻击者无法直接访问熵池，也无法根据过去的随机数序列预测将来的序列。
当系统启动的时候，由于启动过程是个确定的可预测的过程，这种情况下，熵池的熵值将非常小，导致产生的随机数序列质量下降，从而给攻击者破解的可能。为了克服系统启动过程的可预测性带来的影响，Linux操作系统在系统关机的时候保存当前熵池的内容，当系统下次启动的时候恢复上次关机时熵池的数据，这样就有效增加了熵池的熵估算值，避免了随机数序列质量的下降。