密碼學第九章隨機數的產生與檢驗隨機數的描述1隨機數和偽隨機數產生方法2隨機數的檢驗方法3第九章隨機數的產生與檢驗一、隨機數的描述

隨機數在密碼學中扮演著非常重要的角色。如密碼算法中使用隨機數作為密鑰可以使破譯者通過猜測得到密鑰的成功概率達到最小；相互鑒別方案中使用隨機數充當現時可以挫敗攻擊者確定或猜到現時的努力等。下面我們對隨機性進行簡要描述。

若不特別說明，本節中的隨機變量均為離散型隨機變量。一、隨機數的描述

若隨機變量取每一種可能值的概率均相等，則稱服從均勻分布。一、隨機數的描述設1,2,,r是r個隨機變量，1,2,,r的可能值的集合分別為X1,X2,,Xr，若對任意xiXi(i=1,2,,r)，均有p(1=x1,2=x2,,r=xr)=p(1=x1)p(2=x2)p(r=xr)則稱1,2,,r相互獨立。

設1,2,是隨機變量序列，若對任意r2

，均有1,2,,r相互獨立，則稱1,2,相互獨立。一、隨機數的描述定義

由服從均勻分布且相互獨立的隨機變量

j(j=1,2,)構成的序列1,2,稱為隨機數序列。特別地，{0,1}上的隨機數序列被稱為二元隨機數序列。備注：(1)

隨機數序列是滿足下面兩個條件：（a）序列的元素服從均勻分布；（b）序列的任一截段相互獨立。的隨機變量序列。

(2)

隨機數序列并非具體的序列，具體的序列只是它們的樣本序列。一、隨機數的描述在不引起混淆的情況下，由隨機數序列產生的樣本輸出序列也往往被人們簡稱為隨機數序列，而人們通常所說的隨機數序列指的就是這類數值序列。

一、隨機數的描述一個隨機數序列應具有如下性質：(1)能通過已知的所有隨機性統計檢驗（即隨機性測試）。(2)不可預測。即使知道產生前面序列位的全部內容，也不可能預測出下一個隨機位是什么。(3)無法重復產生。如果用完全同樣的輸入對序列發生器操作兩次，將得到兩個不相關的隨機數序列。一、隨機數的描述值得注意的是，由于利用計算機或數學的方法產生的輸出狀態總是過去的輸入和當前狀態確定的函數，因此是可預測的，從而決定了利用計算機或數學的方法不可能產生真正的隨機數序列，它們最好只能產生出能夠通過隨機性測試但本質上并不是隨機數序列的偽隨機數序列，只有通過超數學的方法如用物理噪聲等產生出來的序列才有可能是真正的隨機數序列。

二、隨機數和偽隨機數產生方法

自然界中客觀存在的隨機現象是隨機數的可能來源。隨機數產生方法有人工產生和隨機數發生器產生兩種方式。

（一）隨機數產生方法

1、人工方式采用拋硬幣、擲骰子等人工方式產生隨機數。二、隨機數和偽隨機數產生方法

2、隨機數發生器采用物理噪聲、放射性衰減等客觀世界中存在的隨機現象作為信號源產生隨機數。由于這種產生隨機數的方法在客觀上是隨機的，因此理論上可能產生出真正的隨機數。

二、隨機數和偽隨機數產生方法

偽隨機數發生器使用數學方法或算法技術產生隨機數。（二）偽隨機數產生方法由于數學方法或算法是確定性的，因此不可能產生出真正的隨機數，最好只能產生出能通過隨機性測試但本質上并不是隨機數的偽隨機數。三、隨機數的檢驗方法由于人們無法從數學上證明一個序列發生器產生的數值序列的確是隨機序列，因此在實際應用中人們常常借助于統計檢驗來判斷一個數值序列隨機性的好壞，考察序列發生器是否具有特定類型的弱點。這里僅介紹隨機數的五項常規統計檢驗。五項常規統計檢驗

取s

s0s1s2…sn1是一個n長的二元序列。本部分介紹五種用來判別一條序列是否具有真正隨機序列所具有的某些特殊性質的統計檢驗。如果序列沒有通過某種檢驗，我們判斷該序列不是隨機序列，但值得注意的是，即使一條序列能夠通過這五種檢驗，也不能保證它就是隨機的，只是概率性地“證明”該序列是具有隨機特性的序列。三、隨機數的檢驗方法

1、頻數檢驗（單比特檢驗）三、隨機數的檢驗方法

頻數檢驗的目的是考察序列中0,1的個數是否近似相等，即考察序列的0,1平衡性。

用n0,n1分別表示序列s中0的個數和1的個數。當n較大時，統計量

近似服從自由度為1的2分布。

三、隨機數的檢驗方法檢驗方法：選定顯著性水平，計算統計量X1的值，查表求自由度為1時，顯著性水平下的2值x，比較x與X1的大小，若X1

x，則判斷序列s通過頻數檢驗；若X1

x，則判斷序列s通不過頻數檢驗。

2、序偶檢驗（雙比特檢驗）三、隨機數的檢驗方法

序偶檢驗的目的是考察相鄰位轉移概率是否合理，即考察序列中00，01，10和11的個數是否近似相等。

用n0,n1分別表示序列s中0的個數和1的個數，用n00,n01,n10,n11分別表示序列s中00，01，10，11的個數。

當n較大時，統計量

近似服從自由度為2的2分布。

三、隨機數的檢驗方法檢驗方法：選定顯著性水平，計算統計量X2的值，查表求自由度為2時，顯著性水平下的2值x，比較x與X2的大小，若X2

x，則判斷序列s通過序偶檢驗；若X2

x，則判斷序列s通不過序偶檢驗。

3、撲克檢驗三、隨機數的檢驗方法

撲克檢驗的目的是考察將序列以m比特為單位分組后（若最后一個分組不足m比特，則將其舍去），將每組m比特看作0~2m1的數時，序列中這些數的出現頻次是否合理。即考察將序列以m比特為單位分組后，組序列中0,1,…,2m1的個數是否近似相等。可以取不同的m值進行撲克檢驗。由于m

1時撲克檢驗退化為頻數檢驗，因此可將撲克檢驗看作頻數檢驗的更一般形式。三、隨機數的檢驗方法近似服從自由度為2m1的2分布。

選定一個整數m，令表示不大于的最大整數，則可將序列s分成k個不重疊的m比特長分組，將每組m比特看作0~2m1的數，用ni（0

i

2m1）表示s的k個分組中i出現的次數。當較大時，統計量三、隨機數的檢驗方法檢驗方法：選定整數m和顯著性水平，計算統計量X3的值，查表求自由度為2m1時，顯著性水平下的2值x，比較x與X3的大小，若X3

x，則判斷序列s通過撲克檢驗；若X3

x，則判斷序列s通不過撲克檢驗。

4、自相關檢驗三、隨機數的檢驗方法

自相關檢驗的目的是考察原序列和其經非循環移位變換后的序列之間的相關性，即考察序列是否具有可預測性。三、隨機數的檢驗方法近似服從標準正態N(0,1)。因為A(d)太小或太大都不好，因此應使用雙邊檢驗。可以取不同的移位位數進行自相關檢驗。設移位位數為整數d，則d滿足1

d

，序列s和它經d位移位變換后的序列對應位置上信號不同的個數，其中表示異或運算。當nd

較大時，統計量三、隨機數的檢驗方法檢驗方法：選定整數d和顯著性水平，計算統計量X4的值，查標準正態分布表求顯著性水平下的雙側分位數x，比較x與X4的大小，若X4

x，則判斷序列s通過自相關檢驗；若X4

x，則判斷序列s通不過自相關檢驗。

5、游程檢驗三、隨機數的檢驗方法

游程檢驗的目的是考察序列中0,1信號的游程分布是否合理，即考察序列中各個長度的0、1游程總數與隨機序列中相應長度的0、1游程總數是否近似相等。三、隨機數的檢驗方法

n長隨機序列中長為i的0游程（或1游程）的個數的期望值為ei

(ni+3)/2i+2。令k為使ei5的最大整數i。Bi,Gi分別表示序列s中長為i的0游程和1游程的個數，1

i

k。統計量近似服從自由度為2k2的2分布。

三、隨機數的檢驗方法檢驗方法：選定顯著性水平，根據n計算ei和k的值，進而計算統計量X5的值，查表求自由度為2k2時，顯著性水平下的2值x，比較x與X5的大小，若X5

x，則判斷序列s通過游程檢驗；若X5

x，則判斷序列s通不過游程檢驗。三、隨機數的檢驗方法例：將下面的序列重復四次產生長為160比特的非隨機序列

1110001100010001010011101111001001001001

檢驗在顯著性水平

0.05下，該序列是否能通過頻數檢驗、序偶檢驗、撲克檢驗（取m

3）、自相關檢驗（取d

8）和游程檢驗？三、隨機數的檢驗方法解：(1)（頻數檢驗）n084，n176，統計值X10.4；(2)（序偶檢驗）n0044，n0140，n1040，n1135，統計值X20.6252；

(3)（撲克檢驗）取m3，則k53，在s的53個分組中，000,001,010,011,100,101,110,111分別出現5,10,6,4,12,3,6,7次，統計值X39.6415；

(4)（自相關檢驗）取d8，計算得A(8)100，統計值X43.8933；三、隨機數的檢驗方法(5)（游程檢驗）計算得e120.25，e210.06