隨機數(shù)統(tǒng)計測試方法

1、2024/3/17,1,隨機數(shù)統(tǒng)計測試方法,2007/12/12,2024/3/17,2,常用測試標準,NISTSP800-22 (序列長度>=1Mbit)SP: NIST Special Publication (800 Series) FIPS 140_1/2(序列長度=20kbit)FIPS:The Federal Information Processing Standards由美國商業(yè)部批準頒發(fā)Florid

2、a State UniversityDIEHARD(序列長度>=80Mbit),2024/3/17,3,NIST SP800-22,概述NIST(美國國家標準技術(shù)研究所, National Institute of Standards and Technology )的一種全面的隨機數(shù)統(tǒng)計測試方法，規(guī)定了滿足各種程度隨機性的衡量標準。軟件套件(NIST Statistical Test Suite) http://csrc

3、.nist.gov/groups/ST/toolkit/rng/documentation_software.html: sts-1.8.zip相關(guān)標準: http://csrc.nist.gov/groups/ST/toolkit/rng/documents/SP800-22b.pdf,2024/3/17,4,NIST FIPS 140_x,概述FIPS140-1/FIPS140-2是美國商業(yè)部批準頒發(fā)的文件，關(guān)于隨機數(shù)部分測

4、試相對比較簡單.相關(guān)文件: http://csrc.nist.gov/publications/fips/fips140-2/fips1402.pdfhttp://csrc.nist.gov/publications/fips/fips140-1/fips1401.pdf,2024/3/17,5,DIEHARD測試,,Florida State University的George Marsaglia開發(fā)測試套件: http://

5、stat.fsu.edu/pub/diehard/diehard.zip測試項目:birthday spacings, overlapping permutations, ranks of 31x31 and 32x32 matrices, ranks of 6x8 matrices, monkey tests on 20-bit Words,monkey tests OPSO, OQSO, DNA, count the

6、 1's in a stream of bytes, count the 1's in specific bytes, parking lot, minimum distance,random spheres, squeeze, Overlapping sums, runs, and craps.,2024/3/17,6,FIPS140-x測試項目,測試輸入一個序列,長度20,000bit測試項目頻率測試(

7、monobit test)撲克測試(poker test)游程測試(runs test)長游程測試(long run test),2024/3/17,7,FIPS140-x頻率測試(monobit test),測試方法計算20,000bit序列中1的個數(shù),記為X,如果9654<X<10,346 測試通過(FIPS140-1)9725<X<10,275 測試通過(FIPS140-2)測試目的檢查1或

8、0過多缺陷,2024/3/17,8,FIPS140-x撲克測試(poker test),測試方法將20,000位的比特流按4位一組分成5000組每組共有16種可能的數(shù)據(jù)產(chǎn)生統(tǒng)計每種數(shù)據(jù)的個數(shù)記為f(i),其中i=0~15計算判斷若2.16<X<46.17,測試通過(fips140-2)若1.03<X<57.4,測試通過(fips140-1)測試目的檢查4bit模板的分布缺陷,2024/

9、3/17,9,FIPS140-x游程測試1(runs test),定義游程:一個游程是指連續(xù)0或1的序列測試方法統(tǒng)計20,000bit流中各種長度游程的個數(shù)若游程長度大于6的按6記若每種長度的游程個數(shù)都符合標準要求(見后頁表格)時，認為通過Runs測試測試目的檢查bit流數(shù)據(jù)變化是否太快或太慢,2024/3/17,10,FIPS140-x游程測試2 (runs test),游程測試標準表1,2024/3/17,11,FIP

10、S140-x長游程測試(long run test),定義長游程Fips140-1:當游程的長度大于等于34時Fips140-2:當游程的長度大于等于26時測試方法統(tǒng)計20,000bit流中長游程的個數(shù)若無長游程，則通過長游程測試測試目的檢查是否存在長游程,2024/3/17,12,SP800-22 測試項目(sts_1.8),頻率測試塊內(nèi)頻率測試 游程測試 塊內(nèi)最長游程測試 二進制矩陣測試 離散付利葉變換測試

11、 非重疊模板匹配測試 重疊模板匹配測試,普通統(tǒng)計測試 線性復(fù)雜性測試 連續(xù)測試 近似熵測試 累積和測試 隨機漂移測試 隨機漂移變異測試,2024/3/17,13,SP800-22定義,輸入?yún)?shù)序列長度: n塊長度: m矩陣的秩 (Rank of a binary matrix)將矩陣做初等行變換后，非零行的個數(shù)反映矩陣的固有特性 熵(Entropy)H(X) = - pi log pi游程(Ru

12、ns)序列中包含連續(xù)的0或1的子序列.,2024/3/17,14,P-value計算用函數(shù),2024/3/17,15,SP800-22評估方法,基于bit的統(tǒng)計測試方法計算Pvalue.度量序列為隨機序列可能性大小的一個數(shù)值 比較 pvalue to alpha:若 pvalue > alpha SUCCESS 若 pvalue < alpha FAILURE alpha = [0.001, 0.01]代表容

13、許的錯誤機率上限若alpha =0.01,序列數(shù)應(yīng)不小于100若alpha =0.001,序列數(shù)應(yīng)不小于1000,2024/3/17,16,SP800-22頻率測試,輸入比特流序列長度 (n)n>=100測試方法Sn=X1+X2+…+Xn (根據(jù)序列值,求Xi=1或-1)計算統(tǒng)計量Sobs計算pvalue.測試目的檢查1和0的總數(shù)是否大致相同,2024/3/17,17,SP800-22塊內(nèi)頻率測試,輸入

14、n:比特流序列長度(n>=100)M:塊長度(M>=20,M>0.01n)測試方法將比特流按M_bit長度分N塊(N=[n/M])計算每個塊內(nèi)1的比例計算N塊的統(tǒng)計量計算 pvalue.測試目的檢查M-bit塊內(nèi)1和0的總數(shù)是否大致相同.,2024/3/17,18,SP800-22累積和測試,輸入n:比特流序列長度測試方法求出n個部分和:S1~Sn找出部分和的最大值計算pvalue.測試目

15、的是否每一個階段的1或0過多,2024/3/17,19,SP800-22游程測試,輸入n:比特流序列長度測試方法計算1的比率計算序列中1游程和0游程的總數(shù)Vn(obs)計算 pvalue測試目的檢查序列的游程是否震蕩太快或太慢,2024/3/17,20,SP800-22塊內(nèi)最長游程測試,輸入n:比特流序列長度(n>=750,000)測試方法將比特流按 M_bit (M=10,000)長度分N塊(N=[n/

16、M])計算每個塊內(nèi)1的最長游程;統(tǒng)計不同最長游程的塊數(shù)vi并計算統(tǒng)計量.計算 pvalue.測試目的檢測序列內(nèi)1的最長游程是否隨機,2024/3/17,21,SP800-22二進制矩陣測試,輸入n:比特流序列長度(n>=38912)測試方法將比特流劃分為N個MxQ矩陣(M=Q=32) 求出每個矩陣的秩(RANK)統(tǒng)計不同秩矩陣的總數(shù),計算RANK的統(tǒng)計量.計算 pvalue.測試目的測試固定長度子序列間

17、的線性獨立性,2024/3/17,22,SP800-22離散付利葉變換測試,輸入n:比特流序列長度(n>=1000)測試方法進行DFT變換及其相關(guān)統(tǒng)計量計算pvalue.測試目的檢查比特流是否具有周期特性.,2024/3/17,23,SP800-22非重疊模板匹配測試,輸入n: 比特流序列長度(n=1000000)m:模板長度(2~10可選,推薦使用9或10)B: m_bit模板(軟件模板庫中定義)測試方法將

18、比特流分成N(sts1.8:N=8)個的獨立的塊統(tǒng)計每個塊中B模板出現(xiàn)的次數(shù)Wi計算N塊的統(tǒng)計量計算 pvalue.測試目的檢查是否序列中模板B出現(xiàn)太多,2024/3/17,24,SP800-22重疊模板匹配測試,輸入n: 比特流序列長度(n=1000000)m:模板長度(2~10可選,推薦使用9或10)測試方法將比特流分成N個的獨立的塊(塊長M=1032bit )統(tǒng)計每個塊中B模板(m個連續(xù)1)出現(xiàn)的次數(shù).計算N

19、塊的統(tǒng)計量計算 pvalue.測試目的檢查是否序列中m個連續(xù)1的子序列出現(xiàn)太多.,2024/3/17,25,SP800-22 Maurer's普通統(tǒng)計測試1,輸入n: 比特流序列長度L :塊長度Q :初始化段塊的個數(shù)推薦值見后表測試方法按塊長度L 和初始化段塊的個數(shù)Q將序列劃分初始化段和測試段, 統(tǒng)計兩種段中各塊向量的位置.計算統(tǒng)計量和pvalue.測試目的檢查序列信息壓縮損耗是否顯著,若認為序列有規(guī)律能

20、夠被壓縮,可以視為不隨機,2024/3/17,26,SP800-22 Maurer's普通統(tǒng)計測試2,2024/3/17,27,SP800-22連續(xù)測試,輸入n: 比特流序列長度m:塊長度 (m <=log2(n)-2)測試方法計算各種塊向量(2m種)出現(xiàn)的頻率.計算統(tǒng)計量.計算 pvalue.測試目的檢測序列中給定長度(m)的不同向量分布的均勻性,當m=1時等效為頻率測試.m=4時等效為fips140-

21、x的Poker測試,2024/3/17,28,SP800-22近似熵測試,輸入n: 比特流序列長度m:塊長度 測試方法統(tǒng)計各種塊向量(2m種)出現(xiàn)的頻率.計算近似熵ApEn (一種對數(shù)的頻率測量).計算 pvalue.測試目的檢測給定序列是否為無規(guī)律序列.,2024/3/17,29,SP800-22隨機漂移測試,輸入n: 比特流序列長度(n>=1000000)測試方法計算累計部分和序列S1~Sn, Sk =

22、X1 + …+Xk以部分和值0為界,把序列劃分為J次漂移,為使計算有效,取J >=500且不能小于統(tǒng)計每次漂移中出現(xiàn)不同漂移值的頻率個數(shù)(漂移值x的范圍為-4~4).計算統(tǒng)計量和 pvalue.測試目的檢測連續(xù)的二進制序列(1/-1)的累計部分和序列是否為隨機漂移序列,2024/3/17,30,SP800-22隨機漂移變異測試,輸入n: 比特流序列長度(n>=1000000)測試方法計算累計部分和序列S1~S

23、n, Sk = X1 + …+Xk統(tǒng)計上述序列中出現(xiàn)不同漂移值x(范圍為-9~9)的個數(shù)計算統(tǒng)計量和 pvalue.測試目的檢測二進制序列(1/-1)的累計部分和Sk 序列是否為隨機分布,2024/3/17,31,SP800-22線性復(fù)雜度測試,輸入n: 比特流序列長度M :模塊長度(500<M<5000)測試方法將比特流分成N個長度為M的塊.評估產(chǎn)生二進制序列所需的最短的LFSR (線性反饋移位寄存器)長

24、度.計算 pvalue.測試目的檢測序列是否具有較長的移位寄存器特性.,2024/3/17,32,SP800-22測試軟件(Sts_1.8)參數(shù)設(shè)置,塊內(nèi)頻率測試:塊長度M=128 (M>0.01n)非重疊模板匹配測試: 模板長度m = 9 (9/10)重疊模板匹配測試: 模板長度m＝9 (9/10)Maurer's普通統(tǒng)計測試: 模塊長度L=7, 模塊數(shù)Q=1280(n=1Mbit)模塊長度L=16, 模

25、塊數(shù)Q=655360(n=1Gbit)線性復(fù)雜性測試: 模塊長度M=500 (5001/alpha)序列長度n=1Mbit,序列數(shù)>=100 ,允許1%失敗序列長度n=1Gbit,序列數(shù)1(銀行卡檢測中心使用參數(shù)),2024/3/17,33,Sts1.8測試結(jié)果示例,2024/3/17,34,Sts1.8測試結(jié)果分析-通過幾率分析,結(jié)果分析報告給出每個測試項目的通過的幾率若alpha=0.01,理想通過幾率為99%.測試

26、1000個樣本序列,頻率測試通過996個,則頻率測試實際通過幾率為99.6%.統(tǒng)計測試可接受通過幾率: m為樣本序列個數(shù)m=1000個時,可接受的通過幾率98%;m=100個時,可接受的通過幾率96%;,2024/3/17,35,Sts1.8測試結(jié)果分析-p值統(tǒng)計分析,結(jié)果分析報告給出每個測試項目的p值分布統(tǒng)計根據(jù)不同測試項目的p值范圍統(tǒng)計,

27、計算統(tǒng)計值,用于判斷是否均勻分布.Fi:p值分布區(qū)間序列個數(shù)S:樣本數(shù)量如果p_value>=0.0001 則認為均勻分布,2024/3/17,36,DIEHARD測試結(jié)果分析,測試結(jié)束輸出一個結(jié)果文件,包括各項測試p值.測試項目的p值范圍0.025 ~ 0.975認為通過。在測試得到的上百個p值中，即使是真正的隨機數(shù)也可能出現(xiàn)p值測試失敗。當p值出現(xiàn)6個以上0/1時，可以肯定序列不隨機。,202

28、4/3/17,37,標準比較,Sp800-22測試項目比較全面, 但參數(shù)設(shè)置范圍比較大,會影響測試結(jié)果.當p值出現(xiàn)異常時還需要測試更多的序列來判斷是統(tǒng)計異常還是確認為不隨機數(shù)序列Fips140-x統(tǒng)計測試不夠全面,容易通過Diehard測試也比較全面,但是測試結(jié)果只能參考,偶然的p值不符合要求不能說明序列不隨機.文檔說當p值有6個以上失效時才能確認為不隨機的序列.,2024/3/17,38,標準應(yīng)用情況,宏思: fips140-2(

29、真隨機數(shù)IP通過標準)數(shù)據(jù)所: fips140-1(數(shù)據(jù)所隨機數(shù)測試軟件)銀行卡檢測中心: SP800-22(根據(jù)測試項目),2024/3/17,39,宏思隨機數(shù)IP測試結(jié)果,FM239測試采集11MB的fm239 (宏思IP)數(shù)據(jù)通過fips140-x測試(20kbit)Diehard測試不通過(80Mbit), 9個p值為1Sp800-22測試不通過(10Mbit),不通過項目包括塊內(nèi)最長游程測試傅立葉測試近似熵測

30、試連續(xù)測試普通統(tǒng)計測試模板測試,2024/3/17,40,FM262隨機數(shù)測試結(jié)果,采集1Gbit的卡隨機數(shù)Diehard測試32x32的二進制矩陣秩測試p值為1,其余p值沒發(fā)現(xiàn)異常.Sp800-22測試(1Mbit序列)RANK測試失敗(10/20/100個/1000序列均失敗)非重疊匹配模板測試測試100個序列(m=9),1個模板失敗測試1000個序列(m=9), 所有模板測試通過連續(xù)測試(測試100個序列)m