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

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

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

3、.nist.gov/groups/ST/toolkit/rng/documentation_software.html: sts-1.8.zip相關(guān)標(biāo)準(zhǔ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è)部批準(zhǔn)頒發(fā)的文件，關(guān)于隨機(jī)數(shù)部分測

4、試相對(duì)比較簡單.相關(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測試項(xiàng)目: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測試項(xiàng)目,測試輸入一個(gè)序列,長度20,000bit測試項(xiàng)目頻率測試(

7、monobit test)撲克測試(poker test)游程測試(runs test)長游程測試(long run test),2024/3/17,7,FIPS140-x頻率測試(monobit test),測試方法計(jì)算20,000bit序列中1的個(gè)數(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)計(jì)每種數(shù)據(jù)的個(gè)數(shù)記為f(i),其中i=0~15計(jì)算判斷若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),定義游程:一個(gè)游程是指連續(xù)0或1的序列測試方法統(tǒng)計(jì)20,000bit流中各種長度游程的個(gè)數(shù)若游程長度大于6的按6記若每種長度的游程個(gè)數(shù)都符合標(biāo)準(zhǔn)要求(見后頁表格)時(shí)，認(rèn)為通過Runs測試測試目的檢查bit流數(shù)據(jù)變化是否太快或太慢,2024/3/17,10,FIPS140-x游程測試2 (runs test),游程測試標(biāo)準(zhǔn)表1,2024/3/17,11,FIP

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

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

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

13、許的錯(cuò)誤機(jī)率上限若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)計(jì)算統(tǒng)計(jì)量Sobs計(jì)算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])計(jì)算每個(gè)塊內(nèi)1的比例計(jì)算N塊的統(tǒng)計(jì)量計(jì)算 pvalue.測試目的檢查M-bit塊內(nèi)1和0的總數(shù)是否大致相同.,2024/3/17,18,SP800-22累積和測試,輸入n:比特流序列長度測試方法求出n個(gè)部分和:S1~Sn找出部分和的最大值計(jì)算pvalue.測試目

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

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

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

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

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

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

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

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

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

24、度.計(jì)算 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)計(jì)測試: 模塊長度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é)果分析報(bào)告給出每個(gè)測試項(xiàng)目的通過的幾率若alpha=0.01,理想通過幾率為99%.測試

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

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

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

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

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