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

 

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 模數（Modulus）：m > 0；最好是夠大的質數。

  • a 乘數（Multiplier）：0 ≦ a ＜ m。

  • c 增量（Increment）：0 ≦ c ＜ m。

  • X0 起始值，或稱種子（Seed）：0 ≦ X0 ＜ m。

如果：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 所示；將其特性歸類如下：

  • 輸入參數：使用兩個輸入參數。一者為隨時變動的日期與時間，並以 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+1，Seed）；再說，鑰匙長度又高達 112 個位元，要破解它的確是不容易的。就算攻擊者得到了當次的亂數（Ri），也無法計算出下一次種子的值（Vi+1）。

 

翻轉工作室：粘添壽

 

 

資訊與網路安全技術

 

 

 

翻轉電子書系列：