《密碼學》09 隨機數(shù)的產(chǎn)生與檢驗

密碼學第九章隨機數(shù)的產(chǎn)生與檢驗隨機數(shù)的描述1隨機數(shù)和偽隨機數(shù)產(chǎn)生方法2隨機數(shù)的檢驗方法3第九章隨機數(shù)的產(chǎn)生與檢驗一、隨機數(shù)的描述

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

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

若隨機變量取每一種可能值的概率均相等，則稱服從均勻分布。一、隨機數(shù)的描述設(shè)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相互獨立。

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

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

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

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

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

(2)

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

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

二、隨機數(shù)和偽隨機數(shù)產(chǎn)生方法

自然界中客觀存在的隨機現(xiàn)象是隨機數(shù)的可能來源。隨機數(shù)產(chǎn)生方法有人工產(chǎn)生和隨機數(shù)發(fā)生器產(chǎn)生兩種方式。

（一）隨機數(shù)產(chǎn)生方法

1、人工方式采用拋硬幣、擲骰子等人工方式產(chǎn)生隨機數(shù)。二、隨機數(shù)和偽隨機數(shù)產(chǎn)生方法

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

二、隨機數(shù)和偽隨機數(shù)產(chǎn)生方法

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

取s

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

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

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

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

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

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

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

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

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

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

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

當n較大時，統(tǒng)計量

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

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

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

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

3、撲克檢驗三、隨機數(shù)的檢驗方法

撲克檢驗的目的是考察將序列以m比特為單位分組后（若最后一個分組不足m比特，則將其舍去），將每組m比特看作0~2m1的數(shù)時，序列中這些數(shù)的出現(xiàn)頻次是否合理。即考察將序列以m比特為單位分組后，組序列中0,1,…,2m1的個數(shù)是否近似相等?？梢匀〔煌膍值進行撲克檢驗。由于m

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

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

i

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

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

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

4、自相關(guān)檢驗三、隨機數(shù)的檢驗方法

自相關(guān)檢驗的目的是考察原序列和其經(jīng)非循環(huán)移位變換后的序列之間的相關(guān)性，即考察序列是否具有可預測性。三、隨機數(shù)的檢驗方法近似服從標準正態(tài)N(0,1)。因為A(d)太小或太大都不好，因此應使用雙邊檢驗?？梢匀〔煌囊莆晃粩?shù)進行自相關(guān)檢驗。設(shè)移位位數(shù)為整數(shù)d，則d滿足1

d

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

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

x，則判斷序列s通過自相關(guān)檢驗；若X4

x，則判斷序列s通不過自相關(guān)檢驗。

5、游程檢驗三、隨機數(shù)的檢驗方法

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

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

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

i

k。統(tǒng)計量近似服從自由度為2k2的2分布。

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

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

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

1110001100010001010011101111001001001001

檢驗在顯著性水平

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

3）、自相關(guān)檢驗（取d

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

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

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