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

第1期范麗敏等：隨機性檢測參數(shù)選擇研究5隨機性檢測參數(shù)選擇研究范麗敏1, 2，馮登國1，陳華1（1. 中國科學院 軟件研究所信息安全國家重點實驗室，北京 100190；2.中國科學院 研究生院，北京 100039）摘 要：從統(tǒng)計學角度對同一個隨機性檢測項目中2個獨立的參數(shù)所應滿足的條件進行了研究，在此基礎上設計了一個假設檢驗方法，用于檢測2個參數(shù)是否滿足獨立的關(guān)系。以撲克檢測為實例，對其參數(shù)集中的參數(shù)進行了實驗研究，并對結(jié)果進行了分析。提出的方法是一個通用的方法，可以直接應用于其他帶參數(shù)的檢測項目的參數(shù)關(guān)系研究中，這為隨機性檢測中參數(shù)選擇提供了一種可操作的手段。關(guān)鍵詞：信息安全；隨機性檢測；假設檢驗；參數(shù)選擇；P-Value；撲克檢測中圖分類號：TP309.7 文獻標識碼：A 文章編號：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基金項目：國家自然科學基金資助項目（60503014, 60603013）；國家高技術(shù)研究發(fā)展計劃（“863”計劃）基金資助項目（2007AA01Z470, 2008AA01Z417）；北京市自然科學基金資助項目（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)“隨機”的概念在密碼領(lǐng)域中有著廣泛的應用，例如，一個安全的密碼算法的輸出需要是隨機的，密碼算法及密碼協(xié)議中用到的密鑰和一些參數(shù)也需要是隨機的，隨機性檢測在密碼應用及其相關(guān)領(lǐng)域起到重要的作用。理想的隨機序列可以看成是投擲硬幣的結(jié)果，根據(jù)拋出硬幣是正面或者反面標記為“0”或“1”，對于每一次投擲結(jié)果，“0”或“1”出現(xiàn)的概率均為1/2，投擲結(jié)果之間相互獨立，并且前面的投擲不會影響到后面的結(jié)果。顯然，在實際應用中以這種方式產(chǎn)生隨機數(shù)是不現(xiàn)實的，實際應用的隨機數(shù)通常都是通過某些數(shù)學公式的計算而產(chǎn)生的偽隨機數(shù)1。人們研究了多種隨機序列應滿足的性質(zhì)，并以此為標準對產(chǎn)生序列的隨機程度進行度量。目前已經(jīng)有了眾多的隨機性檢測項目和方法用于檢測密碼算法和序列的統(tǒng)計特性24。對于一個隨機性檢測項目，在實際進行檢測時需要設置一些參數(shù)，參數(shù)通常分為兩類，一類稱為外部參數(shù)，例如測試序列的長度；另一類為內(nèi)部參數(shù)，主要是指檢測項目本身所涉及的參數(shù)，例如撲克檢測2中子序列的長度。本文所研究的是內(nèi)部參數(shù)的關(guān)系和內(nèi)部參數(shù)的選擇。如無特殊說明，本文后續(xù)部分所述參數(shù)均指內(nèi)部參數(shù)。對于帶參數(shù)的檢測項目，其所有可能的參數(shù)組成一個集合，即參數(shù)有一個范圍。在實際應用中最理想的情況是對該集合中的所有參數(shù)進行檢測，但是通常這個集合很大，對所有參數(shù)一一進行檢測不現(xiàn)實。并且，各參數(shù)之間可能存在依賴關(guān)系，對所有的參數(shù)進行檢測也不必要。所以，對參數(shù)之間可能存在的關(guān)系進行研究，選擇出合理的具有代表性的參數(shù)子集，可以提高隨機性檢測的實用性和有效性。目前對參數(shù)選擇的研究并不多見，盡管有一些針對具體檢測項目的參數(shù)選擇的研究或者參數(shù)的修正57，但是，并不存在一個通用的研究參數(shù)之間關(guān)系和參數(shù)選擇的方法。當前大多數(shù)參數(shù)選擇通常都是根據(jù)檢測者的經(jīng)驗和個人偏好來進行。本文從統(tǒng)計學角度出發(fā)，研究了2個無關(guān)的檢測參數(shù)所應該滿足的條件，并以此為基礎設計了一個用于衡量參數(shù)關(guān)系的假設檢驗算法。通過該算法，可以對各參數(shù)之間存在依賴關(guān)系進行量化。本文的研究為選擇最小合理參數(shù)集，避免冗余參數(shù)提供了一個有益的方法和思路。2 背景知識2.1 假設檢驗假設檢驗的基本思想是，首先提出關(guān)于總體性質(zhì)的假設，稱為原假設，然后在原假設的條件下導出結(jié)論，若結(jié)論發(fā)生的概率很大，則認為原假設成立，反之若概率非常小，則否定原假設。該思想源于實踐中被廣泛采用的一條原則，即小概率事件在一次觀察中是不會出現(xiàn)的。小概率事件發(fā)生的概率稱之為顯著性水平，用來表示，它表示了假設檢驗的嚴格程度。越小，則否定原假設的說服力越強。通常情況下，取0.01、0.05或0.1。在隨機性檢測中，通常采用的是假設檢驗方法。首先假定待測的序列是隨機的，按照某種統(tǒng)計方法，其統(tǒng)計值應該符合某種特定的分布。根據(jù)統(tǒng)計值符合特定分布的概率來判斷待測的序列是否隨機。2.2 撲克檢測撲克檢測是一種常用的重要的隨機性檢測方法，最早在文獻2中被提出，撲克檢測也是一些隨機性檢測軟件包中基本的檢測項目，例如CryptX8中的“SubBlock Test”和DIAHARD9中的“Bit Stream Test”在本質(zhì)上都是撲克檢測。長度為的二元子序列有2m種情況。撲克檢測是用于檢測在一個待測的序列中，這2m種子序列出現(xiàn)的次數(shù)是否與隨機序列近似。將長度為n bit的待檢測序列劃分成個非重疊的子序列，統(tǒng)計每種類型的子序列個數(shù)，構(gòu)造統(tǒng)計值，該統(tǒng)計值應該服從自由度為的卡方分布。記作。判斷一個序列是否通過了撲克檢測的通常方法是根據(jù)統(tǒng)計值V計算出P-Value。簡略地說，P-Value是該待測序列比真隨機序列隨機性好的概率10。將P-Value與顯著性水平進行比較，如果P-Value小于，則認為該序列未能通過撲克檢測。3 參數(shù)之間的關(guān)系本文從統(tǒng)計的角度來研究同一個檢測項目中不同參數(shù)之間的關(guān)系。對于同一個序列，判斷其是否通過某參數(shù)的檢測項目通常是比較計算得到的P-Value與顯著性水平的大小。如果2個不同的參數(shù)對相同的序列檢測結(jié)果是相互獨立的，即這2個參數(shù)的檢測結(jié)果互不影響，那么可以將這2個檢測參數(shù)看作是獨立的檢測參數(shù)，這是本文研究的出發(fā)點和基礎。隨機性檢測T的2個不同參數(shù)和的檢測分別記作T()和T()。對于隨機的序列，T()檢測所得的P-Value分布記為X，其概率密度為。T()檢測所得的P-Value分布記為Y，其概率密度為。下面研究當與獨立時，Z=XY的概率分布。對于隨機的序列，X應該是均勻分布于0，1之間的實數(shù)，因此X的概率密度為(1)同理，W=Y的概率密度為(2)在此定義Z=XY=X+W(3)若與獨立，則二者的P-Value分布是獨立的，即X與Y獨立，又因為W與Y是線性關(guān)系，因此X與W也獨立。對于獨立的2個隨機變量Z=X+W的概率密度為11(4)代入式(1)、式(2)可知(5)以上的求解過程表明，假設與獨立，那么對隨機序列進行T()和T()的檢測得到的P-Value之差應該服從概率密度為f(z)的分布，其分布函數(shù)記為F(Z)。4 一個用于檢測參數(shù)之間關(guān)系的假設檢驗算法第3節(jié)得出了獨立的2個檢測參數(shù)的P-Value之差應該服從的分布?；诖?，提出了一個假設檢驗算法，用于檢測任何2個不同參數(shù)是否滿足這種獨立關(guān)系，構(gòu)造原假設如下。H0：2個參數(shù)檢測的P-Value之差的總體符合分布函數(shù)為F(Z)的分布。相應地，備擇假設如下。H：2個參數(shù)檢測的P-Value之差的總體不符合分布函數(shù)為F(Z)的分布。P-Value是0，1之間的實數(shù)，因此2個P-Value之差是1，1之間的實數(shù)。將1，1分為k個區(qū)間，第個區(qū)間為(6)P-Value的差值落入第個區(qū)間的概率記作(7)在一次抽樣檢測中，假設樣本個數(shù)為，落入第個區(qū)間中的個數(shù)為，構(gòu)造統(tǒng)計值如果原假設成立的話，RiRPi的差距應該非常小，根據(jù)皮爾遜卡方檢驗，該統(tǒng)計值應該服從自由度為k1的卡方分布，即V 2(k1)。根據(jù)顯著性水平計算拒絕閾值。如果統(tǒng)計值V大于閾值，則拒絕原假設，接受備擇假設，認為這2個參數(shù)之間不滿足獨立關(guān)系。算法1是一次抽樣判斷參數(shù)與是否獨立的算法。一次抽樣中樣本個數(shù)為R條，其主要步驟如下。算法1 Single_Sample_Test(，)1) 產(chǎn)生R條隨機的二元序列，每條序列的長度為L bit。2) 對每條序列進行如下操作： 利用T()進行檢測，檢測結(jié)果記作P1； 利用T()進行檢測，檢測結(jié)果記作P2； 計算P= P1P2； 如果P1+2/k則R1+； 如果1+2(i1)/kP1+2i/k 則Ri+。3) 計算。4) 如果 則返回true，否則返回false。本文采用的是假設檢驗，其本質(zhì)是一種概率檢測，因此接受或者拒絕原假設存在一定的誤差。另外，通過隨機數(shù)算法產(chǎn)生的隨機序列與真隨機序列有一定的差距，僅通過一次檢測就對參數(shù)之間的關(guān)系下結(jié)論是有偏差的，所以本文通過統(tǒng)計多次抽樣的方法來提高檢測的準確度。另外，通過率也可作為衡量2個參數(shù)之間相關(guān)性大小的一種度量。算法2是S次抽樣進行參數(shù)無關(guān)性檢測的算法，其主要步驟如下。算法2 Independence_Statis_Test(，)1) 設置 passnum=0；2) For i=1 to S do調(diào)用算法1，如果Single_Sample_Test (，)=true 則passnum+；3) 計算并返回pass_proportion= 100 passnum/S。5 實驗結(jié)果本節(jié)以撲克檢測為研究實例，利用第4節(jié)給出的算法，研究撲克檢測參數(shù)之間的關(guān)系。表1一次抽樣中參數(shù)1與其他參數(shù)的無關(guān)性檢測結(jié)果子區(qū)間期望條數(shù)實驗觀測值(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)計值V196.565.6142.2422.1132.7414.8421.5416.279.8218.6225.3837.25撲克檢測用到的參數(shù)m與序列長度L需要滿足一個關(guān)系2，那么當序列長度L=1 000 000bit時，m的范圍是的整數(shù)。即m的合理參數(shù)集合為1，2，3，4，5，6，7，8，9，10，11，12，13。本文采用BBS12隨機數(shù)發(fā)生器產(chǎn)生模擬真隨機的序列，已有研究結(jié)果表明，BBS具有較好的隨機性。本文采用的參數(shù)為R=5 000，S=100， =0.05。如果有5 000條序列，將1，1均勻分成20個區(qū)間，并將第1與第2區(qū)間，第19與第20個區(qū)間進行合并，共形成18個區(qū)間，根據(jù)式(5)和式(7)，假設2個參數(shù)(，)獨立，那么落入各個區(qū)間的期望條數(shù)見表1。抽樣一次，利用BBS算法產(chǎn)生5 000條序列，利用算法1，對參數(shù)1與其他參數(shù)進行無關(guān)性檢測見表1。從表1可以得出，(1，2)，(1，3)，(1，4)，(1，6)，(1，13)的檢測統(tǒng)計值V均大于閾值(通過查表知=27.587），落入了拒絕域內(nèi)，即(1，2)，(1，3)，(1，4)，(1，6)，(1，13)都未能通過獨立性檢測，與此對應，(1，5)，(1，7)，(1，8)，(1，9)，(1，10)，(1，11)，(1，12)通過了參數(shù)獨立性檢測。為了進一步表現(xiàn)出通過與未通過獨立性檢測的差異，分別選取兩種情況的代表(1，10)和(1，2)進行對比，如圖1所示。圖1 參數(shù) (1，10)和參數(shù)(1，2)與期望值擬合對比從圖1可以看出，(1，10) 2個參數(shù)的P-Value之差的分布與獨立參數(shù)的P-Value之差能夠更好地吻合，差異更小，也就是參數(shù)1和10之間更符合獨立的關(guān)系，而(1，2) 2個參數(shù)的P-Value之差的分布與獨立參數(shù)的P-Value之差有較大的差異。為了提高檢測的準確性，本文采用多次抽樣的方式來減小誤差。利用算法2進行統(tǒng)計檢測，將抽樣100次的實驗結(jié)果匯總見表2。表2 撲克檢測各參數(shù)的無關(guān)性統(tǒng)計檢測結(jié)果參數(shù)12345678910111213100005771896693929697782000652779889859259100301583082679093988787407415921310094100659750639810085399710010060921005298855199701007898969193809710099741009098929294100949188110869312094130表2記錄了在100次檢測中，任意2個參數(shù)通過獨立性假設檢驗(算法1返回為true)的次數(shù)。從表2的數(shù)值中可以看到，通過次數(shù)的數(shù)值由0到100不等。由第4節(jié)的算法1和算法2可知，該數(shù)值越大，說明2個參數(shù)之間符合獨立參數(shù)的可能性越大，相反，數(shù)值越小，說明二者之間的相關(guān)性越強。從另外一個角度來說，該數(shù)值也從量上刻畫了2個參數(shù)之間的獨立程度。因此，這樣的量化關(guān)系可以為實際使用中選擇合適參數(shù)提供指導。例如，根據(jù)表2，在進行撲克檢測的參數(shù)選擇時，假設檢測者無法確定是選擇參數(shù)2還是選擇參數(shù)4。通過這個量化的表格可知，參數(shù)2和參數(shù)4與其他參數(shù)關(guān)系如表2中的 和 所示。與參數(shù)2具有較強相關(guān)性的參數(shù)集合為1，3，4，6，而與參數(shù)4具有較強相關(guān)性的參數(shù)集合為1，2，3，6，8，比較而言，參數(shù)4更具有代表性，因此優(yōu)先選擇參數(shù)4。6 結(jié)束語本文從統(tǒng)計學角度出發(fā)，對隨機性檢測的參數(shù)選擇問題進行了研究。給出了一個通用的假設檢驗方法，用于檢測任意2個參數(shù)是否滿足獨立性的關(guān)系。同時，該方法的計算結(jié)果也量化反映出了各參數(shù)之間依賴關(guān)系的大小。以撲克檢測為研究實例，對其合理參數(shù)集中兩兩參數(shù)進行了實驗研究，并對研究結(jié)果進行了分析。本文提出的方法是一個通用的方法，可以直接應用于其他帶參數(shù)的檢測項目的參數(shù)關(guān)系研究中，它為隨機性檢測中的參數(shù)選擇提供了一種可操作的手段。參考文獻：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