隨機(jī)性檢測(cè)參數(shù)選擇研究.doc

第1期范麗敏等：隨機(jī)性檢測(cè)參數(shù)選擇研究5隨機(jī)性檢測(cè)參數(shù)選擇研究范麗敏1, 2，馮登國(guó)1，陳華1（1. 中國(guó)科學(xué)院 軟件研究所信息安全國(guó)家重點(diǎn)實(shí)驗(yàn)室，北京 100190；2.中國(guó)科學(xué)院 研究生院，北京 100039）摘 要：從統(tǒng)計(jì)學(xué)角度對(duì)同一個(gè)隨機(jī)性檢測(cè)項(xiàng)目中2個(gè)獨(dú)立的參數(shù)所應(yīng)滿(mǎn)足的條件進(jìn)行了研究，在此基礎(chǔ)上設(shè)計(jì)了一個(gè)假設(shè)檢驗(yàn)方法，用于檢測(cè)2個(gè)參數(shù)是否滿(mǎn)足獨(dú)立的關(guān)系。以撲克檢測(cè)為實(shí)例，對(duì)其參數(shù)集中的參數(shù)進(jìn)行了實(shí)驗(yàn)研究，并對(duì)結(jié)果進(jìn)行了分析。提出的方法是一個(gè)通用的方法，可以直接應(yīng)用于其他帶參數(shù)的檢測(cè)項(xiàng)目的參數(shù)關(guān)系研究中，這為隨機(jī)性檢測(cè)中參數(shù)選擇提供了一種可操作的手段。關(guān)鍵詞：信息安全；隨機(jī)性檢測(cè)；假設(shè)檢驗(yàn)；參數(shù)選擇；P-Value；撲克檢測(cè)中圖分類(lèi)號(hào)：TP309.7 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1000-436X(2009)01-0001-06On the parameter selection of randomness testFAN Li-min1,2, FENG Deng-guo1, CHEN Hua1(1. State Key Laboratory of Information Security, Institute of Software ,Chinese Academy of Sciences, Beijing 100190, China;2. Graduate University of Chinese Academy of Sciences, Beijing 100039, China)Abstract: The conditions that two different parameters in a same randomness test should satisfy if they are independent with each other was studied based on statistical theory. And a hypothesis method was proposed to test whether two parameters were independent or not. A series of experiments were designed to study the relations among the parameters gather of poker test，which was selected as a research instance by means of this method, and the experiment results were analyzed in details. The method is general and it can be used to deal with other randomness test, such as entropy test and binary derivation test. The work is helpful to select reasonable and scientific parameters in practical randomness test.Key words: information security; randomness test; hypothesis test; parameter selection; P-Value; poker test1 引言收稿日期：2008-06-21；修回日期：2008-12-20基金項(xiàng)目：國(guó)家自然科學(xué)基金資助項(xiàng)目（60503014, 60603013）；國(guó)家高技術(shù)研究發(fā)展計(jì)劃（“863”計(jì)劃）基金資助項(xiàng)目（2007AA01Z470, 2008AA01Z417）；北京市自然科學(xué)基金資助項(xiàng)目（4072026）Foundation Items: The National Natural Science Foundation of China (60503014, 60603013); The National High Technology Research and Development Program of China (863 Program) (2007AA01Z470, 2008AA01Z417); The Natural Science Foundation of Beijing (4072026)“隨機(jī)”的概念在密碼領(lǐng)域中有著廣泛的應(yīng)用，例如，一個(gè)安全的密碼算法的輸出需要是隨機(jī)的，密碼算法及密碼協(xié)議中用到的密鑰和一些參數(shù)也需要是隨機(jī)的，隨機(jī)性檢測(cè)在密碼應(yīng)用及其相關(guān)領(lǐng)域起到重要的作用。理想的隨機(jī)序列可以看成是投擲硬幣的結(jié)果，根據(jù)拋出硬幣是正面或者反面標(biāo)記為“0”或“1”，對(duì)于每一次投擲結(jié)果，“0”或“1”出現(xiàn)的概率均為1/2，投擲結(jié)果之間相互獨(dú)立，并且前面的投擲不會(huì)影響到后面的結(jié)果。顯然，在實(shí)際應(yīng)用中以這種方式產(chǎn)生隨機(jī)數(shù)是不現(xiàn)實(shí)的，實(shí)際應(yīng)用的隨機(jī)數(shù)通常都是通過(guò)某些數(shù)學(xué)公式的計(jì)算而產(chǎn)生的偽隨機(jī)數(shù)1。人們研究了多種隨機(jī)序列應(yīng)滿(mǎn)足的性質(zhì)，并以此為標(biāo)準(zhǔn)對(duì)產(chǎn)生序列的隨機(jī)程度進(jìn)行度量。目前已經(jīng)有了眾多的隨機(jī)性檢測(cè)項(xiàng)目和方法用于檢測(cè)密碼算法和序列的統(tǒng)計(jì)特性24。對(duì)于一個(gè)隨機(jī)性檢測(cè)項(xiàng)目，在實(shí)際進(jìn)行檢測(cè)時(shí)需要設(shè)置一些參數(shù)，參數(shù)通常分為兩類(lèi)，一類(lèi)稱(chēng)為外部參數(shù)，例如測(cè)試序列的長(zhǎng)度；另一類(lèi)為內(nèi)部參數(shù)，主要是指檢測(cè)項(xiàng)目本身所涉及的參數(shù)，例如撲克檢測(cè)2中子序列的長(zhǎng)度。本文所研究的是內(nèi)部參數(shù)的關(guān)系和內(nèi)部參數(shù)的選擇。如無(wú)特殊說(shuō)明，本文后續(xù)部分所述參數(shù)均指內(nèi)部參數(shù)。對(duì)于帶參數(shù)的檢測(cè)項(xiàng)目，其所有可能的參數(shù)組成一個(gè)集合，即參數(shù)有一個(gè)范圍。在實(shí)際應(yīng)用中最理想的情況是對(duì)該集合中的所有參數(shù)進(jìn)行檢測(cè)，但是通常這個(gè)集合很大，對(duì)所有參數(shù)一一進(jìn)行檢測(cè)不現(xiàn)實(shí)。并且，各參數(shù)之間可能存在依賴(lài)關(guān)系，對(duì)所有的參數(shù)進(jìn)行檢測(cè)也不必要。所以，對(duì)參數(shù)之間可能存在的關(guān)系進(jìn)行研究，選擇出合理的具有代表性的參數(shù)子集，可以提高隨機(jī)性檢測(cè)的實(shí)用性和有效性。目前對(duì)參數(shù)選擇的研究并不多見(jiàn)，盡管有一些針對(duì)具體檢測(cè)項(xiàng)目的參數(shù)選擇的研究或者參數(shù)的修正57，但是，并不存在一個(gè)通用的研究參數(shù)之間關(guān)系和參數(shù)選擇的方法。當(dāng)前大多數(shù)參數(shù)選擇通常都是根據(jù)檢測(cè)者的經(jīng)驗(yàn)和個(gè)人偏好來(lái)進(jìn)行。本文從統(tǒng)計(jì)學(xué)角度出發(fā)，研究了2個(gè)無(wú)關(guān)的檢測(cè)參數(shù)所應(yīng)該滿(mǎn)足的條件，并以此為基礎(chǔ)設(shè)計(jì)了一個(gè)用于衡量參數(shù)關(guān)系的假設(shè)檢驗(yàn)算法。通過(guò)該算法，可以對(duì)各參數(shù)之間存在依賴(lài)關(guān)系進(jìn)行量化。本文的研究為選擇最小合理參數(shù)集，避免冗余參數(shù)提供了一個(gè)有益的方法和思路。2 背景知識(shí)2.1 假設(shè)檢驗(yàn)假設(shè)檢驗(yàn)的基本思想是，首先提出關(guān)于總體性質(zhì)的假設(shè)，稱(chēng)為原假設(shè)，然后在原假設(shè)的條件下導(dǎo)出結(jié)論，若結(jié)論發(fā)生的概率很大，則認(rèn)為原假設(shè)成立，反之若概率非常小，則否定原假設(shè)。該思想源于實(shí)踐中被廣泛采用的一條原則，即小概率事件在一次觀察中是不會(huì)出現(xiàn)的。小概率事件發(fā)生的概率稱(chēng)之為顯著性水平，用來(lái)表示，它表示了假設(shè)檢驗(yàn)的嚴(yán)格程度。越小，則否定原假設(shè)的說(shuō)服力越強(qiáng)。通常情況下，取0.01、0.05或0.1。在隨機(jī)性檢測(cè)中，通常采用的是假設(shè)檢驗(yàn)方法。首先假定待測(cè)的序列是隨機(jī)的，按照某種統(tǒng)計(jì)方法，其統(tǒng)計(jì)值應(yīng)該符合某種特定的分布。根據(jù)統(tǒng)計(jì)值符合特定分布的概率來(lái)判斷待測(cè)的序列是否隨機(jī)。2.2 撲克檢測(cè)撲克檢測(cè)是一種常用的重要的隨機(jī)性檢測(cè)方法，最早在文獻(xiàn)2中被提出，撲克檢測(cè)也是一些隨機(jī)性檢測(cè)軟件包中基本的檢測(cè)項(xiàng)目，例如CryptX8中的“SubBlock Test”和DIAHARD9中的“Bit Stream Test”在本質(zhì)上都是撲克檢測(cè)。長(zhǎng)度為的二元子序列有2m種情況。撲克檢測(cè)是用于檢測(cè)在一個(gè)待測(cè)的序列中，這2m種子序列出現(xiàn)的次數(shù)是否與隨機(jī)序列近似。將長(zhǎng)度為n bit的待檢測(cè)序列劃分成個(gè)非重疊的子序列，統(tǒng)計(jì)每種類(lèi)型的子序列個(gè)數(shù)，構(gòu)造統(tǒng)計(jì)值，該統(tǒng)計(jì)值應(yīng)該服從自由度為的卡方分布。記作。判斷一個(gè)序列是否通過(guò)了撲克檢測(cè)的通常方法是根據(jù)統(tǒng)計(jì)值V計(jì)算出P-Value。簡(jiǎn)略地說(shuō)，P-Value是該待測(cè)序列比真隨機(jī)序列隨機(jī)性好的概率10。將P-Value與顯著性水平進(jìn)行比較，如果P-Value小于，則認(rèn)為該序列未能通過(guò)撲克檢測(cè)。3 參數(shù)之間的關(guān)系本文從統(tǒng)計(jì)的角度來(lái)研究同一個(gè)檢測(cè)項(xiàng)目中不同參數(shù)之間的關(guān)系。對(duì)于同一個(gè)序列，判斷其是否通過(guò)某參數(shù)的檢測(cè)項(xiàng)目通常是比較計(jì)算得到的P-Value與顯著性水平的大小。如果2個(gè)不同的參數(shù)對(duì)相同的序列檢測(cè)結(jié)果是相互獨(dú)立的，即這2個(gè)參數(shù)的檢測(cè)結(jié)果互不影響，那么可以將這2個(gè)檢測(cè)參數(shù)看作是獨(dú)立的檢測(cè)參數(shù)，這是本文研究的出發(fā)點(diǎn)和基礎(chǔ)。隨機(jī)性檢測(cè)T的2個(gè)不同參數(shù)和的檢測(cè)分別記作T()和T()。對(duì)于隨機(jī)的序列，T()檢測(cè)所得的P-Value分布記為X，其概率密度為。T()檢測(cè)所得的P-Value分布記為Y，其概率密度為。下面研究當(dāng)與獨(dú)立時(shí)，Z=XY的概率分布。對(duì)于隨機(jī)的序列，X應(yīng)該是均勻分布于0，1之間的實(shí)數(shù)，因此X的概率密度為(1)同理，W=Y的概率密度為(2)在此定義Z=XY=X+W(3)若與獨(dú)立，則二者的P-Value分布是獨(dú)立的，即X與Y獨(dú)立，又因?yàn)閃與Y是線(xiàn)性關(guān)系，因此X與W也獨(dú)立。對(duì)于獨(dú)立的2個(gè)隨機(jī)變量Z=X+W的概率密度為11(4)代入式(1)、式(2)可知(5)以上的求解過(guò)程表明，假設(shè)與獨(dú)立，那么對(duì)隨機(jī)序列進(jìn)行T()和T()的檢測(cè)得到的P-Value之差應(yīng)該服從概率密度為f(z)的分布，其分布函數(shù)記為F(Z)。4 一個(gè)用于檢測(cè)參數(shù)之間關(guān)系的假設(shè)檢驗(yàn)算法第3節(jié)得出了獨(dú)立的2個(gè)檢測(cè)參數(shù)的P-Value之差應(yīng)該服從的分布。基于此，提出了一個(gè)假設(shè)檢驗(yàn)算法，用于檢測(cè)任何2個(gè)不同參數(shù)是否滿(mǎn)足這種獨(dú)立關(guān)系，構(gòu)造原假設(shè)如下。H0：2個(gè)參數(shù)檢測(cè)的P-Value之差的總體符合分布函數(shù)為F(Z)的分布。相應(yīng)地，備擇假設(shè)如下。H：2個(gè)參數(shù)檢測(cè)的P-Value之差的總體不符合分布函數(shù)為F(Z)的分布。P-Value是0，1之間的實(shí)數(shù)，因此2個(gè)P-Value之差是1，1之間的實(shí)數(shù)。將1，1分為k個(gè)區(qū)間，第個(gè)區(qū)間為(6)P-Value的差值落入第個(gè)區(qū)間的概率記作(7)在一次抽樣檢測(cè)中，假設(shè)樣本個(gè)數(shù)為，落入第個(gè)區(qū)間中的個(gè)數(shù)為，構(gòu)造統(tǒng)計(jì)值如果原假設(shè)成立的話(huà)，RiRPi的差距應(yīng)該非常小，根據(jù)皮爾遜卡方檢驗(yàn)，該統(tǒng)計(jì)值應(yīng)該服從自由度為k1的卡方分布，即V 2(k1)。根據(jù)顯著性水平計(jì)算拒絕閾值。如果統(tǒng)計(jì)值V大于閾值，則拒絕原假設(shè)，接受備擇假設(shè)，認(rèn)為這2個(gè)參數(shù)之間不滿(mǎn)足獨(dú)立關(guān)系。算法1是一次抽樣判斷參數(shù)與是否獨(dú)立的算法。一次抽樣中樣本個(gè)數(shù)為R條，其主要步驟如下。算法1 Single_Sample_Test(，)1) 產(chǎn)生R條隨機(jī)的二元序列，每條序列的長(zhǎng)度為L(zhǎng) bit。2) 對(duì)每條序列進(jìn)行如下操作： 利用T()進(jìn)行檢測(cè)，檢測(cè)結(jié)果記作P1； 利用T()進(jìn)行檢測(cè)，檢測(cè)結(jié)果記作P2； 計(jì)算P= P1P2； 如果P1+2/k則R1+； 如果1+2(i1)/kP1+2i/k 則Ri+。3) 計(jì)算。4) 如果 則返回true，否則返回false。本文采用的是假設(shè)檢驗(yàn)，其本質(zhì)是一種概率檢測(cè)，因此接受或者拒絕原假設(shè)存在一定的誤差。另外，通過(guò)隨機(jī)數(shù)算法產(chǎn)生的隨機(jī)序列與真隨機(jī)序列有一定的差距，僅通過(guò)一次檢測(cè)就對(duì)參數(shù)之間的關(guān)系下結(jié)論是有偏差的，所以本文通過(guò)統(tǒng)計(jì)多次抽樣的方法來(lái)提高檢測(cè)的準(zhǔn)確度。另外，通過(guò)率也可作為衡量2個(gè)參數(shù)之間相關(guān)性大小的一種度量。算法2是S次抽樣進(jìn)行參數(shù)無(wú)關(guān)性檢測(cè)的算法，其主要步驟如下。算法2 Independence_Statis_Test(，)1) 設(shè)置 passnum=0；2) For i=1 to S do調(diào)用算法1，如果Single_Sample_Test (，)=true 則passnum+；3) 計(jì)算并返回pass_proportion= 100 passnum/S。5 實(shí)驗(yàn)結(jié)果本節(jié)以撲克檢測(cè)為研究實(shí)例，利用第4節(jié)給出的算法，研究撲克檢測(cè)參數(shù)之間的關(guān)系。表1一次抽樣中參數(shù)1與其他參數(shù)的無(wú)關(guān)性檢測(cè)結(jié)果子區(qū)間期望條數(shù)實(shí)驗(yàn)觀測(cè)值(1，2)(1，3)(1，4)(1，5)(1，6)(1，7)(1，8)(1，9)(1，10)(1，11)(1，12)(1，13)110053596573749583791007483113212571105103111120128120125117118134117317512215315916119417417015516518817419042251642142022192072112032442162242322155275234268283270305260297276255253277250632541436233733934233631135431831632138373754494103843733513553723743793944013238425510497473433436448423419425434433406947559149248649248448750949249547146848310475525533526484469499455490498492508446114254164234254104614194303964174034204731237537434140340635037337237937735932738913325275313306349323295342312341339339307142752572802512632662972722832862923002761522521419922523220721320223220224622323416175152168171154205178200161171182177157171251061021231391271421451261291149813918100738178927990941031091018599統(tǒng)計(jì)值V196.565.6142.2422.1132.7414.8421.5416.279.8218.6225.3837.25撲克檢測(cè)用到的參數(shù)m與序列長(zhǎng)度L需要滿(mǎn)足一個(gè)關(guān)系2，那么當(dāng)序列長(zhǎng)度L=1 000 000bit時(shí)，m的范圍是的整數(shù)。即m的合理參數(shù)集合為1，2，3，4，5，6，7，8，9，10，11，12，13。本文采用BBS12隨機(jī)數(shù)發(fā)生器產(chǎn)生模擬真隨機(jī)的序列，已有研究結(jié)果表明，BBS具有較好的隨機(jī)性。本文采用的參數(shù)為R=5 000，S=100， =0.05。如果有5 000條序列，將1，1均勻分成20個(gè)區(qū)間，并將第1與第2區(qū)間，第19與第20個(gè)區(qū)間進(jìn)行合并，共形成18個(gè)區(qū)間，根據(jù)式(5)和式(7)，假設(shè)2個(gè)參數(shù)(，)獨(dú)立，那么落入各個(gè)區(qū)間的期望條數(shù)見(jiàn)表1。抽樣一次，利用BBS算法產(chǎn)生5 000條序列，利用算法1，對(duì)參數(shù)1與其他參數(shù)進(jìn)行無(wú)關(guān)性檢測(cè)見(jiàn)表1。從表1可以得出，(1，2)，(1，3)，(1，4)，(1，6)，(1，13)的檢測(cè)統(tǒng)計(jì)值V均大于閾值(通過(guò)查表知=27.587），落入了拒絕域內(nèi)，即(1，2)，(1，3)，(1，4)，(1，6)，(1，13)都未能通過(guò)獨(dú)立性檢測(cè)，與此對(duì)應(yīng)，(1，5)，(1，7)，(1，8)，(1，9)，(1，10)，(1，11)，(1，12)通過(guò)了參數(shù)獨(dú)立性檢測(cè)。為了進(jìn)一步表現(xiàn)出通過(guò)與未通過(guò)獨(dú)立性檢測(cè)的差異，分別選取兩種情況的代表(1，10)和(1，2)進(jìn)行對(duì)比，如圖1所示。圖1 參數(shù) (1，10)和參數(shù)(1，2)與期望值擬合對(duì)比從圖1可以看出，(1，10) 2個(gè)參數(shù)的P-Value之差的分布與獨(dú)立參數(shù)的P-Value之差能夠更好地吻合，差異更小，也就是參數(shù)1和10之間更符合獨(dú)立的關(guān)系，而(1，2) 2個(gè)參數(shù)的P-Value之差的分布與獨(dú)立參數(shù)的P-Value之差有較大的差異。為了提高檢測(cè)的準(zhǔn)確性，本文采用多次抽樣的方式來(lái)減小誤差。利用算法2進(jìn)行統(tǒng)計(jì)檢測(cè)，將抽樣100次的實(shí)驗(yàn)結(jié)果匯總見(jiàn)表2。表2 撲克檢測(cè)各參數(shù)的無(wú)關(guān)性統(tǒng)計(jì)檢測(cè)結(jié)果參數(shù)12345678910111213100005771896693929697782000652779889859259100301583082679093988787407415921310094100659750639810085399710010060921005298855199701007898969193809710099741009098929294100949188110869312094130表2記錄了在100次檢測(cè)中，任意2個(gè)參數(shù)通過(guò)獨(dú)立性假設(shè)檢驗(yàn)(算法1返回為true)的次數(shù)。從表2的數(shù)值中可以看到，通過(guò)次數(shù)的數(shù)值由0到100不等。由第4節(jié)的算法1和算法2可知，該數(shù)值越大，說(shuō)明2個(gè)參數(shù)之間符合獨(dú)立參數(shù)的可能性越大，相反，數(shù)值越小，說(shuō)明二者之間的相關(guān)性越強(qiáng)。從另外一個(gè)角度來(lái)說(shuō)，該數(shù)值也從量上刻畫(huà)了2個(gè)參數(shù)之間的獨(dú)立程度。因此，這樣的量化關(guān)系可以為實(shí)際使用中選擇合適參數(shù)提供指導(dǎo)。例如，根據(jù)表2，在進(jìn)行撲克檢測(cè)的參數(shù)選擇時(shí)，假設(shè)檢測(cè)者無(wú)法確定是選擇參數(shù)2還是選擇參數(shù)4。通過(guò)這個(gè)量化的表格可知，參數(shù)2和參數(shù)4與其他參數(shù)關(guān)系如表2中的 和 所示。與參數(shù)2具有較強(qiáng)相關(guān)性的參數(shù)集合為1，3，4，6，而與參數(shù)4具有較強(qiáng)相關(guān)性的參數(shù)集合為1，2，3，6，8，比較而言，參數(shù)4更具有代表性，因此優(yōu)先選擇參數(shù)4。6 結(jié)束語(yǔ)本文從統(tǒng)計(jì)學(xué)角度出發(fā)，對(duì)隨機(jī)性檢測(cè)的參數(shù)選擇問(wèn)題進(jìn)行了研究。給出了一個(gè)通用的假設(shè)檢驗(yàn)方法，用于檢測(cè)任意2個(gè)參數(shù)是否滿(mǎn)足獨(dú)立性的關(guān)系。同時(shí)，該方法的計(jì)算結(jié)果也量化反映出了各參數(shù)之間依賴(lài)關(guān)系的大小。以撲克檢測(cè)為研究實(shí)例，對(duì)其合理參數(shù)集中兩兩參數(shù)進(jìn)行了實(shí)驗(yàn)研究，并對(duì)研究結(jié)果進(jìn)行了分析。本文提出的方法是一個(gè)通用的方法，可以直接應(yīng)用于其他帶參數(shù)的檢測(cè)項(xiàng)目的參數(shù)關(guān)系研究中，它為隨機(jī)性檢測(cè)中的參數(shù)選擇提供了一種可操作的手段。參考文獻(xiàn)：1NEUMANN J. Various techniques used in connection with random digitsJ. National Bureau of Standards Applied Mathematics, 1951, (12): 36-38.2KNUYH D E. The Art of Computer Programming, Volume 2: Seminumerical AlgorithmsM. 3rd Ed, New Jersey : Addison- Wesley, 1981 .59-73.3RUKHIN A, SOTO J, NECHVATAL J, et al. A Statistical Test Suite for Random and Pseudorandom Number Generators for Cryptographic ApplicationsR. Technical Report, SP 800-22, 2001.4FILIOL E. A new statistical testing for symmetric ciphers and hash functionsA. Information and Communications Security: 4th International ConferenceC. Berlin : Springer, 2002. 342-353. 5TSANG W W, HUI L C K, CHOW K P. Tuning the collision test for powerA. Proceedings of the 27th Australasian conference on Computer Science - Volume 26 DunedinC. New Zealand: Australian Computer Society, 2004. 23-30. 6HAMANO K, KANEKO T. Correction of overlapping template matching test included in nist randomness test suiteJ. IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, 2007,90(19): 1788-1792.7PARESCHI F, ROVATTI R, SETTI G. Second-level NIST randomness tests for improving test