在前兩講中，我們主要對SSL協議中CBC模式的弱安全性進行了系統的介紹。這一講中我們對用于生成SSL中所用密鑰的PRNG做一點簡單介紹。
PRNG（pseudo Random Noise Generation），即偽隨機噪聲生成，用于生成各種密碼學操作中所需的隨機數。
一般而言，Linux系統中的PRNG（簡稱為LRNG）可以被分為3個異步的部分。第一部分把系統事件轉化為bit來表示潛在的熵；第二部分把這些bit加入到隨機數生成池；第三部分使用連續的SHA-1操作處理生成池中的bit來產生輸出，得到的反饋依然被放入生成池中來更新它。
每個從系統事件得到的隨機性都被收集為兩個32-bit的word。第一個word包含事件發生的時間，第二個word是事件的值，通常是一個按鍵、鼠標移動或者驅動訪問的編碼。
LRNG使用一個計數器來計算加入到生成池中物理隨機性的估算值，這個值用一個不同事件發生頻率的函數來計算。這個值被表示為熵。
Linux系統中PRNG的結構抽象如下圖所示：
Pools and counters：上圖描述了LRNG流程。內部狀態保持在3個熵池里：primary、secondary、urandom，它們的大小分別為512、128、128字節。熵源向primary池添加數據；它的輸出再給到secondary和urandom中，LRNG的輸出是從secondary或者urandom中提取的。提取過程中，一個池子的內部狀態會根據反饋行為更新。
每個池子有一個熵值計數器。它是0到池子大小比特值之間的一個整數。輸出從熵池中提取后，這個值就減小提取出熵值的比特數。
熵值的增加比較復雜。（1）如果增加的bit來自某一熵源，那么會根據這個熵源最近幾次事件的時序（timing）來評估它們的熵，然后相應增加計數器的值。（2）如果增加的bit來自primary，則接收池的計數器就直接增加接收到的bit數。
secondary池的計數器很重要，它用來判斷當前secondary池中的熵是否足夠用來生成隨機數，如果不夠，就進行阻塞并等待，并從primary池中提取熵，直到熵計數器的值大于某一閾值。
Adding physical entropy： 桌面及服務器PC使用的熵源有4個：鼠標、鍵盤活動，磁盤輸入輸出以及特殊中斷。事件發生時，會產生一個32bit的word表示時間（系統開機到現在經歷的毫秒數），一個word編碼它的屬性（事件類型、）。此外，同一類型連續事件的時序會被用來估算該事件提供的熵值。
收集到的熵分批加入池子，每分鐘幾次。默認加入primary，滿了的話加入secondary，不會加入urandom。
Generating output：當用戶使用/dev/urandom時，從urandom中提取隨機bit；當用戶使用/dev/random時，從secondary中提取隨機bit；當這兩個池子熵不夠時從primary池提取隨機bit。 /dev/random和/dev/urandom這兩種生成隨機數的方式特點如下：
熵提取過程包括3個步驟：（1）更新熵池內容；（2）提取隨機bit到輸出；（3）減少熵池計數器值。
Linux中PRNG的初始化 操作系統啟動時會初始化LRNG，使用固定的操作系統參數和當前時間，以及額外的磁盤操作或系統事件。這樣的操作序列很容易被攻擊者預測，并且如果沒有額外事件發生，LRNG的熵會很有限。導致LRNG的輸出具有可預測性。
可以使用一個腳本解決這個問題，在系統關閉時保存一個隨機種子，在開機時把它寫回到池子中。關機時，腳本從/dev/urandom中讀取512個字節并寫入到一個文件，開機時再把這寫字節寫回到/dev/urandom設備。寫回這些字節改變primary池的狀態，效果類似于發生一系列事件。然后由primary池更新secondary及urandom池。
這個腳本是Linux發行包中的一部分，而不是內核的一部分。在KNOPPIX及OpenWRT發行版中沒有這個腳本，他們的LRNG初始狀態是可預測的，安全性較低。
估算熵值 LRNG僅適用一個時間函數估算事件的熵，而與事件類型無關。
事件的熵為：
更新熵池 熵池的更新機制基于TGFSR（Twisted Generalized Feedback Shift Register）。
TGFSR的唯一輸入是狀態的初始值（一個p*w bit的種子），每個循環中內部狀態被用來生成新的狀態。
LRNG中用的移位寄存器是基于TGFSR的，區別在于它在每次循環中增加熵。LRNG中的熵池被定義為長度為m個word的數組。
熵通過運行add(pool, j, g）算法來增加，g是新的熵word。
每個池子基于一個本原多項式來更新。多項式根據池子大小來選，secondary和urandom用的多項式相同。
從熵池中提取隨機bit的方式為：（1）對提取的bit做hash；（2）修改池子狀態；（3）減小計數器。 依據如下算法：
OpenSSL的PRNG是一個確定性函數，知道輸入和調用次序的攻擊者可以預測輸出。為了使PRNG安全，熵池必須從/dev/random或者其它攻擊者不知道的熵源中取種。2006年，在Debian Linux發布版本中的OpenSSL增加了一個漏洞修復，而這個漏洞修復引入了一個新的漏洞，它在修復另一個漏洞時把生成隨機數選種過程的代碼給刪掉了，這導致初始選種時使用到的唯一的隨機值是當前進程ID-pid，Linux平臺默認最大進程號是32,768，所以生成隨機數的種子值范圍很小。這個漏洞到2008年才被發現，受影響的Debian Linux版本的可用熵都很有限，產生的公私鑰對是可預測的，這樣導致生成的SSL協議中使用的服務器私鑰具有脆弱性。由于漏洞存在，攻擊者可以事先生成公私鑰對，一旦發現有跟公鑰匹配的就知道了對應私鑰。加州大學圣地亞哥分校的研究人員在漏洞發布不久對流行的SSL服務器進行掃描，發現1.5%左右的服務器使用了弱密鑰證書。
事實上，因為弱PRNG生成的RSA和DSA弱密鑰在TLS和SSH服務器中廣泛存在。在2012年的一項調查中發現，0.75%的TLS證書因為熵不足共享了密鑰，其他還有1.7%的設備采用了相同實現，很可能也存在此類問題。0.5%的TLS主機和0.03%的SSH主機RSA私鑰可被獲取，因為它們的公鑰存在共享公因子現象。RSA公鑰的分解是很困難的，但是如果兩個公鑰共享了某一素因子，那么只要計算出這個素因子，就可以將這兩個公鑰分解，從而計算出對應的私鑰。
這一現象是由于PRNG在生成隨機數時，如果用于產生RSA公鑰的兩個隨機數都是在熵源不足的情況下生成的，那么采用相同實現的設備就可能生成兩個相同的素因子，導致對應的私鑰相同。如果兩個隨機數中，僅有一個是在熵源不足的情況下生成，那么兩臺采用相同實現的不同設備生成的RSA公鑰就可能共享一個素因子，導致這兩個RSA公鑰均可很容易地被分解。
弱PRNG導致的弱RSA和DSA密鑰問題在嵌入式設備如路由器、閉路電視等中也廣泛存在，因為這類設備的熵源有限（缺少鼠標鍵盤等熵源）。關于嵌入式設備中弱密鑰的問題具體可以參考USENIX Security 14年的文章A Large-Scale Analysis of the Security of Embedded Firmwares，由于導致弱密鑰的原理相同，這里就不多做介紹了。