隨機數(shù)在計算機系統(tǒng)中處于非常重要的地位，如果沒有隨機數(shù)，可能很多應用都將陷入麻煩，隨機數(shù)在密碼學和安全領域也是至關重要。本文主要介紹隨機數(shù)的概念和重要性，Linux 系統(tǒng)中隨機數(shù)是如何產生的，最后介紹在 KVM 虛擬機中如何添加和使用硬件隨機數(shù)產生器來產生隨機數(shù)。

什么是隨機數(shù)

很多軟件和應用都需要隨機數(shù)，從紙牌游戲中紙牌的分發(fā)到 SSL 安全協(xié)議中密鑰的產生，到處都有隨機數(shù)的身影。隨機數(shù)至少具備兩個條件：

1. 數(shù)字序列在統(tǒng)計上是隨機的
2. 不能通過已知序列推算后面的序列

自從計算機誕生起，尋求用計算機產生高質量的隨機數(shù)序列的研究就一直是研究者長期關注的課題。一般情況下，使用計算機程序產生一個真正的隨機數(shù)是很難的，因為程序的行為是可預測的，計算機利用設計好的算法結合用戶提供的種子產生的隨機數(shù)序列通常是“偽隨機數(shù)”（pseudo-random number），偽隨機數(shù)就是我們平時經常使用的“隨機數(shù)”。偽隨機數(shù)可以滿足一般應用的需求，但是在對于安全要求比較高的環(huán)境和領域中存在明顯的缺點：

1. 偽隨機數(shù)是周期性的，當它們足夠多時，會重復數(shù)字序列
2. 如果提供相同的算法和相同的種子值，將會得出完全一樣的隨機數(shù)序列
3. 可以使用逆向工程，猜測算法與種子值，以便推算后面所有的隨機數(shù)列

只有實際物理過程才是真正的隨機，只有借助物理世界中事物的隨機性才能產生真正的隨機數(shù)，比如真空內亞原子粒子量子漲落產生的噪音、超亮發(fā)光二極管在噪聲的量子不確定性和放射性衰變等。

隨機數(shù)為什么如此重要

生成隨機數(shù)是密碼學中的一項基本任務，是生成加密密鑰、加密算法和加密協(xié)議所必不可少的，隨機數(shù)的質量對安全性至關重要。最近報道有人利用隨機數(shù)缺點成功攻擊了某網站，獲得了管理員的權限。美國和法國的安全研究人員最近也評估了兩個 Linux 內核 PRNG——/dev/random 和/dev/urandom 的安全性，認為 Linux 的偽隨機數(shù)生成器不滿足魯棒性的安全概念，沒有正確積累熵?？梢婋S機數(shù)在安全系統(tǒng)中占據(jù)著非常重要的地位。

Linux 中隨機數(shù)如何產生

PRNG(Pseudo-Random Number Generator)

1994 年，美國軟件工程師 Theodore Y. Ts’o 第一次在 Linux 內核中實現(xiàn)了隨機數(shù)發(fā)生器，使用 SHA-1 散列算法而非密碼，提高了密碼強度。

Linux 內核采用熵來描述數(shù)據(jù)的隨機性，熵（entropy）是描述系統(tǒng)混亂無序程度的物理量，一個系統(tǒng)的熵越大則說明該系統(tǒng)的有序性越差，即不確定性越大。內核維護了一個熵池用來收集來自設備驅動程序和其它來源的環(huán)境噪音。理論上，熵池中的數(shù)據(jù)是完全隨機的，可以實現(xiàn)產生真隨機數(shù)序列。為跟蹤熵池中數(shù)據(jù)的隨機性，內核在將數(shù)據(jù)加入池的時候將估算數(shù)據(jù)的隨機性，這個過程稱作熵估算。熵估算值描述池中包含的隨機數(shù)位數(shù)，其值越大表示池中數(shù)據(jù)的隨機性越好。 內核中隨機數(shù)發(fā)生器 PRNG 為一個字符設備 random,代碼實現(xiàn)在 drivers/char/random.c，該設備實現(xiàn)了一系列接口函數(shù)用于獲取系統(tǒng)環(huán)境的噪聲數(shù)據(jù)，并加入熵池。系統(tǒng)環(huán)境的噪聲數(shù)據(jù)包括設備兩次中斷間的間隔，輸入設備的操作時間間隔，連續(xù)磁盤操作的時間間隔等。 對應的接口包括：

void add_device_randomness(const void *buf, unsigned int size); 
void add_input_randomness(unsigned int type, unsigned int code, 
                unsigned int value); 
void add_interrupt_randomness(int irq, int irq_flags); 
void add_disk_randomness(struct gendisk *disk); 

內核提供了 1 個的接口來供其他內核模塊使用。

void get_random_bytes(void *buf, int nbytes); 

該接口會返回指定字節(jié)數(shù)的隨機數(shù)。random 設備了提供了 2 個字符設備供用戶態(tài)進程使用——/dev/random 和/dev/urandom：

• /dev/random 適用于對隨機數(shù)質量要求比較高的請求，在熵池中數(shù)據(jù)不足時， 讀取 dev/random 設備時會返回小于熵池噪聲總數(shù)的隨機字節(jié)。/dev/random 可生成高隨機性的公鑰或一次性密碼本。若熵池空了，對/dev/random 的讀操作將會被阻塞，直到收集到了足夠的環(huán)境噪聲為止。這樣的設計使得/dev/random 是真正的隨機數(shù)發(fā)生器，提供了最大可能的隨機數(shù)據(jù)熵。
• /dev/urandom，非阻塞的隨機數(shù)發(fā)生器，它會重復使用熵池中的數(shù)據(jù)以產生偽隨機數(shù)據(jù)。這表示對/dev/urandom 的讀取操作不會產生阻塞，但其輸出的熵可能小于/dev/random 的。它可以作為生成較低強度密碼的偽隨機數(shù)生成器，對大多數(shù)應用來說，隨機性是可以接受的。

/dev/random 也允許寫入，任何用戶都可以向熵池中加入隨機數(shù)據(jù)。即使寫入非隨機數(shù)據(jù)亦是無害的，因為只有管理員可以調用 ioctl 以增加熵池大小。Linux 內核中當前熵的值和大小可以通過訪問 /proc/sys/kernel/random/得到，比如：

# cat /proc/sys/kernel/random/poolsize 
4096 
# cat /proc/sys/kernel/random/entropy_avail 
298 
# cat /proc/sys/kernel/random/uuid 
4f0683ae-6141-41e1-b5b9-57f4bd299219 

但是 Linux 內核中隨機發(fā)生器中存在幾個弱點，在嵌入式系統(tǒng)（缺少鼠標鍵盤），Live CD 系統(tǒng)（缺少磁盤），路由器，無盤工作站和一些服務器系統(tǒng)中，環(huán)境熵的來源較為受限，隨機數(shù)質量會有所下降。對于有 NVRAM 的系統(tǒng)，建議在關機時保存一部分隨機數(shù)發(fā)生器的狀態(tài)，使得在下次開機時可以恢復這些狀態(tài)。對于路由器而言，可以考慮把網絡數(shù)據(jù)可以作為熵的主要來源。

EGD

EGD（熵收集守護進程，entropy gathering daemon）通常可以在不支持/dev/random 設備的 Unix 系統(tǒng)中提供類似的功能。這是一個運行于用戶態(tài)的守護進程，提供了高質量的密碼用隨機數(shù)據(jù)。一些加密軟件，比如 OpenSSL，GNU Privacy Guard 和 Apache HTTP 服務器支持在/dev/random 不可用的時候使用 EGD。

EGD，或者類似的軟件 prngd，可以從多種來源收集偽隨機的熵，并對這些數(shù)據(jù)進行處理以去除偏置，并改善密碼學質量，然后允許其它程序通過 Unix 域套接口（通常使用/dev/egd-pool），或 TCP 套接口訪問其輸出。該程序通常使用建立子進程的以查詢系統(tǒng)狀態(tài)的方式來收集熵。它查詢的狀態(tài)通常是易變和不可預測的，例如 CPU，I/O，網絡的使用率，也可能是一些日志文件和臨時目錄中的內容。

EGD 通過一個簡單的協(xié)議與那些需要隨機數(shù)的客戶端進行通信，客戶端通過連接 EGD socket 發(fā)送命令（從前八位來識別命令）：

• command 0: 查詢當前可用熵
• command 1: 非阻塞地獲取隨機字節(jié)數(shù)
• command 2: 阻塞地獲取隨機字節(jié)數(shù)
• command 3: 更新熵

硬件隨機數(shù)產生器

當前有很多硬件隨機數(shù)產生器（hwrng）用于產生可靠的隨機數(shù)，但都是商用的，價格比較昂貴，最常使用的是 ComScire QNG，截止筆者寫這篇文章，ComScire PQ4000KU 的官方價格接近 900 美元。

Intel’s Ivy Bridge family 有一個功能叫”Secure Key”, 處理器包含了一個內部硬件 DRNG（Digital Random Number Generator）用于產生隨機數(shù)，使用匯編指令 RDRAND 即可獲得高強度的隨機數(shù)，Linux Kernel 會使用異或操作把 RDRAND 產生的隨機數(shù)混合進熵池， 代碼實現(xiàn)在 drivers/char/random.c 的 extract_entropy()函數(shù)里。

for (i = 0; i < LONGS(EXTRACT_SIZE); i++) { 
unsigned long v; 
if (!arch_get_random_long(&v)) 
break; 
hash.l[i] ^= v; 
} 

還有一些第三方的硬件隨機數(shù)生成器，通常是 USB 或者 PCI 設備，主要是在服務器上使用。Linux Kernel 的 hwrng(hardware random number generator)抽象層（/dev/hwrng 設備）可以選擇監(jiān)控 RNG 設備，并且在熵池數(shù)據(jù)不足的時候要求設備提供隨機數(shù)據(jù)到 kernel 的熵池，rngd 守護進程可以讀取 hwrng 的數(shù)據(jù)然后補給到 kernel 的熵池中。

在 KVM 虛擬機中如何應用

虛擬機環(huán)境下和服務器情況類似，輸入設備操作很少，相對于 Host 而言，Disk I/O 也相對較少，因此依賴 Guest 自身 PRNG 產生的隨機數(shù)質量不高，因此虛擬機通常從 Host（宿主機）獲取部分隨機數(shù)據(jù)。對于 KVM 虛擬機來說，存在一個半虛擬化設備 virtio-rng 作為硬件隨機數(shù)產生器。Linux Kernel 從 2.6.26 開始支持 virtio-rng, QEMU 在 1.3 版本加入了對 virtio-rng 的支持。 virtio-rng 設備會讀取 Host 的隨機數(shù)源并且填充到 Guest（客戶機）的熵池中。通常情況下使用/dev/random 作為輸入源。當然，數(shù)據(jù)源可以更改，當 Host 系統(tǒng)中存在 hwrng 的情況下你可以使用/dev/hwrng 來作為 virtio-rng 的輸入源。 也可以把 hwrng 設備 pass-through（透傳）到客戶機中，但是并不實用，比如在虛擬機 Live Migration（實時遷移）時會存在問題。在 Guest 中添加 virtio-rng 設備具體操作，使用/dev/random 作為輸入源，兩種方法：

使用 libvirt 編輯虛擬機的 XML 
在虛擬機 XML 定義中，在<devices>段中添加： 
<rng model='virtio'> 
&lt;backend model='<strong>random</strong>'&gt;/dev/random&lt;/backend&gt; 
&lt;/rng&gt; 
使用 QEMU command Line 直接添加： 
-object <strong>rng-random</strong>,filename=/dev/random,id=rng0 \ 
-device virtio-rng-pci,rng=rng0 

虛擬機啟動后，在 Host 端：

$ lsof /dev/random 
COMMAND     PID USER   FD   TYPE DEVICE SIZE/OFF NODE NAME 
qemu-syst 23590 mars   11r   CHR    1,8      0t0 1032 /dev/random 

會看到當前 QEMU 進程正在使用/dev/random 設備。

Guest 端： 
$ cat /sys/devices/virtual/misc/hw_random/rng_available 
virtio 
$ cat /sys/devices/virtual/misc/hw_random/rng_current 
virtio 
$ lsmod | grep virtio_rng 
virtio_rng  12790   0 
.... 

可以看到 Guest 已經識別到硬件隨機數(shù)產生器。

$ dd if=/dev/hwrng of=/home/random-data bs=1 

添加 bs 選項并且最好設置的值比較小，因為 Host 上隨機數(shù)資源可能會比較少，如果 bs 設置值太大，短時間內可能無法獲得足夠的數(shù)據(jù)寫入文件，同時在 Host 端多做一些鼠標鍵盤或者磁盤的操作，會更快地產生隨機數(shù)。

$ hexdump /home/random-data 
00000000    9501 e702 .... 
00000010    .... .... .... 

使用 EGD 協(xié)議來作為輸入源：

使用 libvirt 編輯虛擬機的 XML： 
<rng model='virtio'> 
   &lt;backend model='<strong>egd</strong>' type='tcp'&gt; 
     &lt;source mode='connect' host='127.0.0.1' service='8000'/&gt; 
   &lt;/backend&gt; 
 &lt;/rng&gt; 
使用 QEMU command Line 直接添加： 
-chardev socket,host=localhost,port=1024,id=chr0 \ 
-object <strong>rng-egd</strong>,chardev=chr0,id=rng0 \ 
-device virtio-rng- pci,rng=rng0 

總結

隨機數(shù)在計算機系統(tǒng)中有著非常重要的作用，本文闡述了隨機數(shù)的概念和重要性，介紹了在 Linux 中產生隨機數(shù)的方法，以及在 KVM 環(huán)境下虛擬機如何使用 virtio-rng 來獲取隨機數(shù)據(jù)。