資訊與網路安全技術:第四章 雜湊與亂數演算法 上一頁 |
4-6 亂數產生器
4-6-1 亂數 的應用 『亂數』(Random Number,或 Nonce)[32, 36, 83]在資訊安全上常常扮演非常重要的角色,我們將其應用歸類如下:
其實,亂數的應用不祇侷限於此,還有許多地方會應用到。如果我們回想一下,為何使用亂數?主要原因在於其『隨機性』並且是『不可預測的』。利用這兩因素所構成的通訊關鍵,別人就無法預估出來我們的通訊方式,如此便能達到資訊安全的『神秘性』功能。但話說回來,電腦是一個死板的計算工具,僅僅會依照所既定的程序(或程式)計算出所期望的數值。因此,無論採用何種計算程序所算出來的亂數,還是有蛛絲馬跡可以尋找出亂數的出現規律;攻擊者只要能預測出可能使用的亂數,依然能輕而易舉的破解安全系統。況且任何一套系統都有各自的亂數產生器,並且產生一個不可預測的亂數,必須經過極複雜的運算程序,相對地會增加系統的負擔。因此,亂數的複雜度視其應用範圍而定。譬如,樂透彩卷是利用電腦(假如是)計算出六個幸運號碼,不論它的運算程序有多複雜,總是有人會不計成本去分析,因為只要能找出數字出現的規律,就有機會變成億萬富翁!如此說來,該電腦裡的亂數產生器非經過特殊設計不可。其實,許多系統利用物理現象來計算亂數,譬如,採用鍵盤鍵入時間間隔、游離電容量、或週邊電磁感應量等等,雖然這些因素會時改變,但欲製作它確實不易,除非是較專屬的系統,否則甚少使用。 既然亂數是利用某一演算法所計算出來,因此又稱為『虛擬亂數』(Pseudo-random Number, PRN),以下介紹幾種與資訊安全有關的亂數產生函數。 4-6-2 典型亂數產生器 到目前為止,最常見的典型亂數產生器是『線性同餘法』,此演算法的計算公式為: Xn+1 = (a Xn + c) mod m 所產生的亂數序列為 {Xn};它的計算方式是由前一個亂數,再加入其它參數之後,以同餘計算出這一次的亂數。同餘計算是擷取除法運算之後的餘數,如果所加入的參數與所取用的除數都很適當的話,所產生的亂數應該符合『隨機性』與『不可預測性』。接下來,說明相關的四個參數:
如果:m、a、c 與 X0 都選用整數的話,則會產生一序列的整數 Xn,其中為 0 ≦ Xn < m。 我們用較簡單的參數來測試看看,假設:m =7、a=2、c=1、X0=1,則所產生的亂數序列為:X1 = 3、X2 = 0、X3 = 1、X4 = 3、...;由此可以看出所產生的亂數序列為 {0, 1, 3, 0, 1, 3, .., },這樣的選擇方式可能只出現 3 種數字(亦即週期只有 3)。如希望所產生的亂數夠亂的話,就必須將所有可能出現的週期加大(加大m,並挑選更佳的a、c);如此一來,便可以在較長的序列中隨機尋找一個數字,也比較不容易被猜出來。增加序列週期最基本方法是增加 m 的數值(當然 a 與 c 也會有所關聯),一般我們都會將該電腦所能計算的能力,來作為週期出現率;譬如,以 32 位元處理機為例,同餘模式計算就採用 232 -1(mod 232-1,即是 m = 232 -1);而此函數又稱為『全週期』(Full-period)函數,公式如下: Xn+1 = (a Xn + c) mod 232-1
接下來的重點是如何選用 a、c 與 X0,其中 X0 與 c 只是隨機參數而已,依照統計分析的結果,選擇任何值對安全性來講並不是影響很大,然而 a 的內容就另當別論了。至少我們期望上一次的值(Xn)與 a 相乘以後,儘可能會大於 m,如此所產生的亂數變化才會較大;但 a 的值越大的話,處理機的計算負荷相對越高;譬如 IBM 360 系列採用 a = 75 = 16807,所產生的亂數應該夠複雜了。 線性同餘法也是可能會遭受破解的,譬如,大多知道必然會採用全週期函數(m = 232-1),只要能找出 X0、a 與 c,即可猜測出下一個亂數可能出現的數字。假設攻擊者收集到 X1、X2 與 X3,則可排列出以下式子: X1 = (aX0 + c) mod m X2 = (aX1 + c) mod m X3 = (aX2 + c) mod m 利用這三個方程式就可容易找出 a 與 c(也可以找出 m)。由此可見,只要得到這三次以上的亂數,便可猜測出下一次可能出現的亂數。由此可見,採用線性同餘法仍需週期性的改變相關參數才行。 4-6-3 DES 亂數產生 雖然,採用線性同餘法所製造出的亂數是可以預測的,但在許多地方還是需要它這種特性。譬如,串流加密法或無線網路傳輸([4] 第十五章),都需要雙方能同時產生相同的『虛擬亂數』;此時,只要雙方協議好 m、a、c 與 X0 四個參數的話,便能夠同時產生相同的虛擬亂數。但要如何來增加它的安全性呢?我們可以利用密碼學的加密方法,來打亂所產生的亂數序列。圖 4-9 為全週期亂數再經過加密的運作程序。其功能是:首先利用線性同餘法產生全週期亂數之後,再經過某一加密演算法(如 DES 或 AES 演算法)處理,處理出來便將原來亂數的格式再打亂一次;如果通訊雙方都握有相同的鑰匙,也使用相同的演算法,如此一來,雙方應該可以產生相同的虛擬亂數。要注意的是,系統必須特別加強保護這把專門用來產生亂數的鑰匙(又稱為主鑰匙),要是被盜走的話,所產生的亂數便有可能被猜算出來,系統的安全就會出大問題了。
圖 4-9 利用 DES 加密器產生虛擬亂數 4-6-4 ANSI 亂數產生 ANSI(America National Standard Institute)所制定的 ANSI X9.17 亂數產生器,可以說是目前最可靠的資訊安全技術之一;許多安全性系統(如 PGP)也都採用這種技術。ANSI X9.17 是採用 Triple-DES(3DES) 加密法,所需計算的參數是採用隨時變動的日期與時間,當然也會用到一般亂數所產生的初始值,如圖 4-10 所示;將其特性歸類如下:
圖 4-10 ANSI X9.17 亂數產生器 我們依照圖 4-10 來定義下列數值:
演算法的計算輸出為:
如此所計算出來的虛擬亂數(Ri),其中包含了 3 個 3DES 加密器、隨時改變的日期與時間、以及循環計算出的種子(Vi+1,Seed);再說,鑰匙長度又高達 112 個位元,要破解它的確是不容易的。就算攻擊者得到了當次的亂數(Ri),也無法計算出下一次種子的值(Vi+1)。
|
翻轉工作室:粘添壽
資訊與網路安全技術
翻轉電子書系列:
|