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

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

2、a State UniversityDIEHARD(序列長(zhǎng)度>=80Mbit),2024/3/17,3,NIST SP800-22,概述NIST(美國(guó)國(guó)家標(biāo)準(zhǔn)技術(shù)研究所, National Institute of Standards and Technology )的一種全面的隨機(jī)數(shù)統(tǒng)計(jì)測(cè)試方法，規(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是美國(guó)商業(yè)部批準(zhǔn)頒發(fā)的文件，關(guān)于隨機(jī)數(shù)部分測(cè)

4、試相對(duì)比較簡(jiǎn)單.相關(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測(cè)試,,Florida State University的George Marsaglia開發(fā)測(cè)試套件: http://

5、stat.fsu.edu/pub/diehard/diehard.zip測(cè)試項(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測(cè)試項(xiàng)目,測(cè)試輸入一個(gè)序列,長(zhǎng)度20,000bit測(cè)試項(xiàng)目頻率測(cè)試(

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

8、0過多缺陷,2024/3/17,8,FIPS140-x撲克測(cè)試(poker test),測(cè)試方法將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,測(cè)試通過(fips140-2)若1.03<X<57.4,測(cè)試通過(fips140-1)測(cè)試目的檢查4bit模板的分布缺陷,2024/

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

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

11、 非重疊模板匹配測(cè)試 重疊模板匹配測(cè)試,普通統(tǒng)計(jì)測(cè)試 線性復(fù)雜性測(cè)試 連續(xù)測(cè)試 近似熵測(cè)試 累積和測(cè)試 隨機(jī)漂移測(cè)試 隨機(jī)漂移變異測(cè)試,2024/3/17,13,SP800-22定義,輸入?yún)?shù)序列長(zhǎng)度: n塊長(zhǎng)度: 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ì)測(cè)試方法計(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頻率測(cè)試,輸入比特流序列長(zhǎng)度 (n)n>=100測(cè)試方法Sn=X1+X2+…+Xn (根據(jù)序列值,求Xi=1或-1)計(jì)算統(tǒng)計(jì)量Sobs計(jì)算pvalue.測(cè)試目的檢查1和0的總數(shù)是否大致相同,2024/3/17,17,SP800-22塊內(nèi)頻率測(cè)試,輸入

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

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

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

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

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

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

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

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

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

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

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

26、1000個(gè)樣本序列,頻率測(cè)試通過996個(gè),則頻率測(cè)試實(shí)際通過幾率為99.6%.統(tǒng)計(jì)測(cè)試可接受通過幾率: m為樣本序列個(gè)數(shù)m=1000個(gè)時(shí),可接受的通過幾率98%;m=100個(gè)時(shí),可接受的通過幾率96%;,2024/3/17,35,Sts1.8測(cè)試結(jié)果分析-p值統(tǒng)計(jì)分析,結(jié)果分析報(bào)告給出每個(gè)測(cè)試項(xiàng)目的p值分布統(tǒng)計(jì)根據(jù)不同測(cè)試項(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測(cè)試結(jié)果分析,測(cè)試結(jié)束輸出一個(gè)結(jié)果文件,包括各項(xiàng)測(cè)試p值.測(cè)試項(xiàng)目的p值范圍0.025 ~ 0.975認(rèn)為通過。在測(cè)試得到的上百個(gè)p值中，即使是真正的隨機(jī)數(shù)也可能出現(xiàn)p值測(cè)試失敗。當(dāng)p值出現(xiàn)6個(gè)以上0/1時(shí)，可以肯定序列不隨機(jī)。,202

28、4/3/17,37,標(biāo)準(zhǔn)比較,Sp800-22測(cè)試項(xiàng)目比較全面, 但參數(shù)設(shè)置范圍比較大,會(huì)影響測(cè)試結(jié)果.當(dāng)p值出現(xiàn)異常時(shí)還需要測(cè)試更多的序列來判斷是統(tǒng)計(jì)異常還是確認(rèn)為不隨機(jī)數(shù)序列Fips140-x統(tǒng)計(jì)測(cè)試不夠全面,容易通過Diehard測(cè)試也比較全面,但是測(cè)試結(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ù)測(cè)試軟件)銀行卡檢測(cè)中心: SP800-22(根據(jù)測(cè)試項(xiàng)目),2024/3/17,39,宏思隨機(jī)數(shù)IP測(cè)試結(jié)果,FM239測(cè)試采集11MB的fm239 (宏思IP)數(shù)據(jù)通過fips140-x測(cè)試(20kbit)Diehard測(cè)試不通過(80Mbit), 9個(gè)p值為1Sp800-22測(cè)試不通過(10Mbit),不通過項(xiàng)目包括塊內(nèi)最長(zhǎng)游程測(cè)試傅立葉測(cè)試近似熵測(cè)

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