資訊與網路安全技術 第四章 雜湊與亂數演算法  上一頁    

 

4-6 亂數產生器

內容:

  • 4-6-1 亂數的應用

  • 4-6-2 典型亂數產生器

  • 4-6-3 DES 亂數產生器

  • 4-6-4 ANSI 亂數產生器

4-6-1 亂數 的應用

『亂數』(Random Number,或 Nonce[32, 36, 83]在資訊安全上常常扮演非常重要的角色,我們將其應用歸類如下:

  • 產生通訊鑰匙:通訊一方或許會選用一個亂數作為會議鑰匙(秘密鑰匙演算法使用),再用加密方式傳送給對方。

  • 演算法參數:許多演算法都需要亂數來增加它的神秘性。譬如,RSA 演算法或 Diffie-Hellman 演算法都需要選擇亂數來作為製造鑰匙的材料。

  • 計算器:許多通訊協定(如 IPSec)都會選擇一個亂數計數器做為封包的序號,並作為防禦重複攻擊的辨識。

  • 交叉確認:如雙方需要確認所持有的鑰匙是否相同時,某一方會選用一個亂數再加密後,傳送給對方;對方解密後,再將亂數加一(或其他演算),加密後回傳給發送者;如此便可以確定雙方的鑰匙是否相同。

其實,亂數的應用不祇侷限於此,還有許多地方會應用到。如果我們回想一下,為何使用亂數?主要原因在於其『隨機性』並且是『不可預測的』。利用這兩因素所構成的通訊關鍵,別人就無法預估出來我們的通訊方式,如此便能達到資訊安全的『神秘性』功能。但話說回來,電腦是一個死板的計算工具,僅僅會依照所既定的程序(或程式)計算出所期望的數值。因此,無論採用何種計算程序所算出來的亂數,還是有蛛絲馬跡可以尋找出亂數的出現規律;攻擊者只要能預測出可能使用的亂數,依然能輕而易舉的破解安全系統。況且任何一套系統都有各自的亂數產生器,並且產生一個不可預測的亂數,必須經過極複雜的運算程序,相對地會增加系統的負擔。因此,亂數的複雜度視其應用範圍而定。譬如,樂透彩卷是利用電腦(假如是)計算出六個幸運號碼,不論它的運算程序有多複雜,總是有人會不計成本去分析,因為只要能找出數字出現的規律,就有機會變成億萬富翁!如此說來,該電腦裡的亂數產生器非經過特殊設計不可。其實,許多系統利用物理現象來計算亂數,譬如,採用鍵盤鍵入時間間隔、游離電容量、或週邊電磁感應量等等,雖然這些因素會時改變,但欲製作它確實不易,除非是較專屬的系統,否則甚少使用。

既然亂數是利用某一演算法所計算出來,因此又稱為『虛擬亂數』(Pseudo-random Number, PRN,以下介紹幾種與資訊安全有關的亂數產生函數。

4-6-2 典型亂數產生器

到目前為止,最常見的典型亂數產生器是『線性同餘法』,此演算法的計算公式為:

Xn+1 = (a Xn + c) mod m

所產生的亂數序列為 {Xn};它的計算方式是由前一個亂數,再加入其它參數之後,以同餘計算出這一次的亂數。同餘計算是擷取除法運算之後的餘數,如果所加入的參數與所取用的除數都很適當的話,所產生的亂數應該符合『隨機性』與『不可預測性』。接下來,說明相關的四個參數:

  • m 模數(Modulusm > 0;最好是夠大的質數。

  • a 乘數(Multiplier0 a m

  • c 增量(Increment0 c m

  • X0 起始值,或稱種子(Seed0 X0 m

如果:mac X0 都選用整數的話,則會產生一序列的整數 Xn,其中為 0 Xn m

我們用較簡單的參數來測試看看,假設:m =7a=2c=1X0=1,則所產生的亂數序列為:X1 = 3X2 = 0X3 = 1X4 = 3...;由此可以看出所產生的亂數序列為 {0, 1, 3, 0, 1, 3, .., },這樣的選擇方式可能只出現 3 種數字(亦即週期只有 3)。如希望所產生的亂數夠亂的話,就必須將所有可能出現的週期加大(加大m,並挑選更佳的ac);如此一來,便可以在較長的序列中隨機尋找一個數字,也比較不容易被猜出來。增加序列週期最基本方法是增加 m 的數值(當然 a c 也會有所關聯),一般我們都會將該電腦所能計算的能力,來作為週期出現率;譬如,以 32 位元處理機為例,同餘模式計算就採用 232 -1mod 232-1,即是 m = 232 -1);而此函數又稱為『全週期』(Full-period函數,公式如下:

Xn+1 = (a Xn + c) mod 232-1

             

接下來的重點是如何選用 ac X0,其中 X0 c 只是隨機參數而已,依照統計分析的結果,選擇任何值對安全性來講並不是影響很大,然而 a 的內容就另當別論了。至少我們期望上一次的值(Xn)與 a 相乘以後,儘可能會大於 m,如此所產生的亂數變化才會較大;但 a 的值越大的話,處理機的計算負荷相對越高;譬如 IBM 360 系列採用 a = 75 = 16807,所產生的亂數應該夠複雜了。

線性同餘法也是可能會遭受破解的,譬如,大多知道必然會採用全週期函數(m = 232-1),只要能找出 X0a c,即可猜測出下一個亂數可能出現的數字。假設攻擊者收集到 X1X2 X3,則可排列出以下式子:

X1 = (aX0 + c) mod m

X2 = (aX1 + c) mod m

X3 = (aX2 + c) mod m

利用這三個方程式就可容易找出 a c(也可以找出 m)。由此可見,只要得到這三次以上的亂數,便可猜測出下一次可能出現的亂數。由此可見,採用線性同餘法仍需週期性的改變相關參數才行。

4-6-3 DES 亂數產生

雖然,採用線性同餘法所製造出的亂數是可以預測的,但在許多地方還是需要它這種特性。譬如,串流加密法或無線網路傳輸([4] 第十五章),都需要雙方能同時產生相同的『虛擬亂數』;此時,只要雙方協議好 mac X0 四個參數的話,便能夠同時產生相同的虛擬亂數。但要如何來增加它的安全性呢?我們可以利用密碼學的加密方法,來打亂所產生的亂數序列。圖 4-9 為全週期亂數再經過加密的運作程序。其功能是:首先利用線性同餘法產生全週期亂數之後,再經過某一加密演算法(如 DES AES 演算法)處理,處理出來便將原來亂數的格式再打亂一次;如果通訊雙方都握有相同的鑰匙,也使用相同的演算法,如此一來,雙方應該可以產生相同的虛擬亂數。要注意的是,系統必須特別加強保護這把專門用來產生亂數的鑰匙(又稱為主鑰匙),要是被盜走的話,所產生的亂數便有可能被猜算出來,系統的安全就會出大問題了。

4-9 利用 DES 加密器產生虛擬亂數

4-6-4 ANSI 亂數產生

ANSIAmerica National Standard Institute所制定的 ANSI X9.17 亂數產生器,可以說是目前最可靠的資訊安全技術之一;許多安全性系統(如 PGP)也都採用這種技術。ANSI X9.17 是採用 Triple-DES3DES 加密法,所需計算的參數是採用隨時變動的日期與時間,當然也會用到一般亂數所產生的初始值,如圖 4-10 所示;將其特性歸類如下:

  • 輸入參數:使用兩個輸入參數。一者為隨時變動的日期與時間,並以 64 位元來表示;每計算一次,下一次計算的參數就會被更新。另一者為初始值,第二次以後計算,也會製造另一個亂數種子(Seed),做為下一次計算的初始值;第一次的初始值或許會採用一般系統的亂數。

  • 加密鑰匙:本演算法係採用 Triple-DES 加密法,並使用兩把鑰匙的演算法,因此鑰匙長度為 112=56 × 2)。此鑰匙必須保護好,而且只能使用於虛擬亂數產生上。

  • 亂數輸出:亂數輸出也是 64 個位元(符合 3DES 演算法);另外輸出一個 64 位元的種子(Seed),作為下一次計算虛擬亂數的參數。

4-10 ANSI X9.17 亂數產生器

我們依照圖 4-10 來定義下列數值:

    • DTi :產生第 i 個亂數時,所輸入的日期與時間。

    • Vi :產生第 i 個亂數時,所輸入的種子值(或初始值)。

    • Ri :所產生出來的第 i 個亂數。

    • K1 || K2:產生亂數的主鑰匙。

演算法的計算輸出為:

    • Ri = 3DESK1||K2 [Vi 3DESK1||K2 [DTi]]

    • Vi+1 = 3DESK1||K2 [Ri 3DESK1||K2 [DTi]]

如此所計算出來的虛擬亂數(Ri),其中包含了 3 3DES 加密器、隨時改變的日期與時間、以及循環計算出的種子(Vi+1Seed);再說,鑰匙長度又高達 112 個位元,要破解它的確是不容易的。就算攻擊者得到了當次的亂數(Ri),也無法計算出下一次種子的值(Vi+1)。

 

主講人:粘添壽博士

 

資訊與網路安全技術