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

隨機(jī)數(shù)統(tǒng)計(jì)測(cè)試方法2007/12/128/6/20231隨機(jī)數(shù)統(tǒng)計(jì)測(cè)試方法2007/12/128/4/20231常用測(cè)試標(biāo)準(zhǔn)NISTSP800-22(序列長(zhǎng)度>=1Mbit)SP:NISTSpecialPublication(800Series)FIPS140_1/2(序列長(zhǎng)度=20kbit)FIPS:TheFederalInformationProcessingStandards由美國(guó)商業(yè)部批準(zhǔn)頒發(fā)FloridaStateUniversityDIEHARD(序列長(zhǎng)度>=80Mbit)8/6/20232常用測(cè)試標(biāo)準(zhǔn)NIST8/4/20232NISTSP800-22概述 NIST(美國(guó)國(guó)家標(biāo)準(zhǔn)技術(shù)研究所,NationalInstituteofStandardsandTechnology)的一種全面的隨機(jī)數(shù)統(tǒng)計(jì)測(cè)試方法，規(guī)定了滿足各種程度隨機(jī)性的衡量標(biāo)準(zhǔn)。軟件套件(NISTStatisticalTestSuite)/groups/ST/toolkit/rng/documentation_software.html:sts-1.8.zip相關(guān)標(biāo)準(zhǔn):/groups/ST/toolkit/rng/documents/SP800-22b.pdf8/6/20233NISTSP800-22概述8/4/20233NISTFIPS140_x概述 FIPS140-1/FIPS140-2是美國(guó)商業(yè)部批準(zhǔn)頒發(fā)的文件，關(guān)于隨機(jī)數(shù)部分測(cè)試相對(duì)比較簡(jiǎn)單.相關(guān)文件:/publications/fips/fips140-2/fips1402.pdf/publications/fips/fips140-1/fips1401.pdf8/6/20234NISTFIPS140_x概述8/4/20234DIEHARD測(cè)試FloridaStateUniversity的GeorgeMarsaglia開(kāi)發(fā)測(cè)試套件:/pub/diehard/diehard.zip測(cè)試項(xiàng)目:birthdayspacings,overlappingpermutations,ranksof31x31and32x32matrices,ranksof6x8matrices,monkeytestson20-bitWords,monkeytestsOPSO,OQSO,DNA,countthe1'sinastreamofbytes,countthe1'sinspecificbytes,parkinglot,minimumdistance,randomspheres,squeeze,Overlappingsums,runs,andcraps.8/6/20235DIEHARD測(cè)試FloridaStateUniversFIPS140-x測(cè)試項(xiàng)目測(cè)試輸入一個(gè)序列,長(zhǎng)度20,000bit測(cè)試項(xiàng)目頻率測(cè)試(monobittest)撲克測(cè)試(pokertest)游程測(cè)試(runstest)長(zhǎng)游程測(cè)試(longruntest)8/6/20236FIPS140-x測(cè)試項(xiàng)目測(cè)試輸入8/4/20236FIPS140-x頻率測(cè)試(monobittest)測(cè)試方法計(jì)算20,000bit序列中1的個(gè)數(shù),記為X,如果9654<X<10,346測(cè)試通過(guò)(FIPS140-1)9725<X<10,275測(cè)試通過(guò)(FIPS140-2)測(cè)試目的檢查1或0過(guò)多缺陷8/6/20237FIPS140-x頻率測(cè)試(monobittest)測(cè)試方FIPS140-x撲克測(cè)試(pokertest)測(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è)試通過(guò)(fips140-2)若1.03<X<57.4,測(cè)試通過(guò)(fips140-1)測(cè)試目的檢查4bit模板的分布缺陷8/6/20238FIPS140-x撲克測(cè)試(pokertest)測(cè)試方法8FIPS140-x游程測(cè)試1(runstest)定義游程:一個(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)要求(見(jiàn)后頁(yè)表格)時(shí)，認(rèn)為通過(guò)Runs測(cè)試測(cè)試目的檢查bit流數(shù)據(jù)變化是否太快或太慢8/6/20239FIPS140-x游程測(cè)試1(runstest)定義8/4FIPS140-x游程測(cè)試2(runstest)游程測(cè)試標(biāo)準(zhǔn)表1LengthFips140-1Fips140-212267~27332315~268521079~14211114~13863502~748527~7234223~402240~384590~223103~2096+90~223103~2098/6/202310FIPS140-x游程測(cè)試2(runstest)游程測(cè)試FIPS140-x長(zhǎng)游程測(cè)試(longruntest)定義長(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ù)若無(wú)長(zhǎng)游程，則通過(guò)長(zhǎng)游程測(cè)試測(cè)試目的檢查是否存在長(zhǎng)游程8/6/202311FIPS140-x長(zhǎng)游程測(cè)試(longruntest)定SP800-22測(cè)試項(xiàng)目(sts_1.8)頻率測(cè)試塊內(nèi)頻率測(cè)試游程測(cè)試塊內(nèi)最長(zhǎng)游程測(cè)試二進(jìn)制矩陣測(cè)試離散付利葉變換測(cè)試非重疊模板匹配測(cè)試重疊模板匹配測(cè)試

普通統(tǒng)計(jì)測(cè)試線性復(fù)雜性測(cè)試連續(xù)測(cè)試近似熵測(cè)試?yán)鄯e和測(cè)試隨機(jī)漂移測(cè)試隨機(jī)漂移變異測(cè)試

8/6/202312SP800-22測(cè)試項(xiàng)目(sts_1.8)頻率測(cè)試普通統(tǒng)計(jì)SP800-22定義輸入?yún)?shù)序列長(zhǎng)度:n塊長(zhǎng)度:m矩陣的秩(Rankofabinarymatrix)將矩陣做初等行變換后，非零行的個(gè)數(shù)反映矩陣的固有特性熵(Entropy)H(X)=-pilogpi游程(Runs)序列中包含連續(xù)的0或1的子序列.8/6/202313SP800-22定義輸入?yún)?shù)8/4/202313P-value計(jì)算用函數(shù)8/6/202314P-value計(jì)算用函數(shù)8/4/202314SP800-22評(píng)估方法基于bit的統(tǒng)計(jì)測(cè)試方法計(jì)算Pvalue.度量序列為隨機(jī)序列可能性大小的一個(gè)數(shù)值比較pvaluetoalpha:若pvalue>alphaSUCCESS

若pvalue<alphaFAILURE

alpha=[0.001,0.01]代表容許的錯(cuò)誤機(jī)率上限若alpha=0.01,序列數(shù)應(yīng)不小于100若alpha=0.001,序列數(shù)應(yīng)不小于10008/6/202315SP800-22評(píng)估方法基于bit的統(tǒng)計(jì)測(cè)試方法8/4/20SP800-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ù)是否大致相同8/6/202316SP800-22頻率測(cè)試輸入8/4/202316SP800-22塊內(nèi)頻率測(cè)試輸入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ù)是否大致相同.8/6/202317SP800-22塊內(nèi)頻率測(cè)試輸入8/4/202317SP800-22累積和測(cè)試輸入n:比特流序列長(zhǎng)度測(cè)試方法求出n個(gè)部分和:S1~Sn找出部分和的最大值計(jì)算pvalue.測(cè)試目的是否每一個(gè)階段的1或0過(guò)多8/6/202318SP800-22累積和測(cè)試輸入8/4/202318SP800-22游程測(cè)試輸入n:比特流序列長(zhǎng)度測(cè)試方法計(jì)算1的比率計(jì)算序列中1游程和0游程的總數(shù)Vn(obs)計(jì)算pvalue測(cè)試目的檢查序列的游程是否震蕩太快或太慢8/6/202319SP800-22游程測(cè)試輸入8/4/202319SP800-22塊內(nèi)最長(zhǎng)游程測(cè)試輸入n:比特流序列長(zhǎng)度(n>=750,000)測(cè)試方法將比特流按M_bit(M=10,000)長(zhǎng)度分N塊(N=[n/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ī)8/6/202320SP800-22塊內(nèi)最長(zhǎng)游程測(cè)試輸入8/4/202320SP800-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)度子序列間的線性獨(dú)立性8/6/202321SP800-22二進(jìn)制矩陣測(cè)試輸入8/4/202321SP800-22離散付利葉變換測(cè)試輸入n:比特流序列長(zhǎng)度(n>=1000)測(cè)試方法進(jìn)行DFT變換及其相關(guān)統(tǒng)計(jì)量計(jì)算pvalue.測(cè)試目的檢查比特流是否具有周期特性.8/6/202322SP800-22離散付利葉變換測(cè)試輸入8/4/202322SP800-22非重疊模板匹配測(cè)試輸入n:比特流序列長(zhǎng)度(n=1000000)m:模板長(zhǎng)度(2~10可選,推薦使用9或10)B:m_bit模板(軟件模板庫(kù)中定義)測(cè)試方法將比特流分成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)太多8/6/202323SP800-22非重疊模板匹配測(cè)試輸入8/4/202323SP800-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塊的統(tǒng)計(jì)量計(jì)算pvalue.測(cè)試目的檢查是否序列中m個(gè)連續(xù)1的子序列出現(xiàn)太多.8/6/202324SP800-22重疊模板匹配測(cè)試輸入8/4/202324SP800-22Maurer's普通統(tǒng)計(jì)測(cè)試1輸入n:比特流序列長(zhǎng)度L:塊長(zhǎng)度Q:初始化段塊的個(gè)數(shù)推薦值見(jiàn)后表測(cè)試方法按塊長(zhǎng)度L和初始化段塊的個(gè)數(shù)Q將序列劃分初始化段和測(cè)試段,統(tǒng)計(jì)兩種段中各塊向量的位置.計(jì)算統(tǒng)計(jì)量和pvalue.測(cè)試目的檢查序列信息壓縮損耗是否顯著,若認(rèn)為序列有規(guī)律能夠被壓縮,可以視為不隨機(jī)8/6/202325SP800-22Maurer's普通統(tǒng)計(jì)測(cè)試1輸入8/4/SP800-22Maurer's普通統(tǒng)計(jì)測(cè)試28/6/202326SP800-22Maurer's普通統(tǒng)計(jì)測(cè)試28/4/20SP800-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-x的Poker測(cè)試8/6/202327SP800-22連續(xù)測(cè)試輸入8/4/202327SP800-22近似熵測(cè)試輸入n:比特流序列長(zhǎng)度m:塊長(zhǎng)度測(cè)試方法統(tǒng)計(jì)各種塊向量(2m種)出現(xiàn)的頻率.計(jì)算近似熵ApEn(一種對(duì)數(shù)的頻率測(cè)量).計(jì)算pvalue.測(cè)試目的檢測(cè)給定序列是否為無(wú)規(guī)律序列.8/6/202328SP800-22近似熵測(cè)試輸入8/4/202328SP800-22隨機(jī)漂移測(cè)試輸入n:比特流序列長(zhǎng)度(n>=1000000)測(cè)試方法計(jì)算累計(jì)部分和序列S1~Sn,Sk

=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ī)漂移序列8/6/202329SP800-22隨機(jī)漂移測(cè)試輸入8/4/202329SP800-22隨機(jī)漂移變異測(cè)試輸入n:比特流序列長(zhǎng)度(n>=1000000)測(cè)試方法計(jì)算累計(jì)部分和序列S1~Sn,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ī)分布8/6/202330SP800-22隨機(jī)漂移變異測(cè)試輸入8/4/202330SP800-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)度.計(jì)算pvalue.測(cè)試目的檢測(cè)序列是否具有較長(zhǎng)的移位寄存器特性.8/6/202331SP800-22線性復(fù)雜度測(cè)試輸入8/4/202331SP800-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,模塊數(shù)Q=655360(n=1Gbit)線性復(fù)雜性測(cè)試:模塊長(zhǎng)度M=500(500<M<5000)連續(xù)測(cè)試:模塊長(zhǎng)度m=16(m<=log2n-2)近似熵測(cè)試:模塊長(zhǎng)度m=10(m<=log2n)數(shù)據(jù)長(zhǎng)度1Gbit,alpha取0.01(序列數(shù)>1/alpha)序列長(zhǎng)度n=1Mbit,序列數(shù)>=100,允許1%失敗序列長(zhǎng)度n=1Gbit,序列數(shù)1(銀行卡檢測(cè)中心使用參數(shù))8/6/202332SP800-22測(cè)試軟件(Sts_1.8)參數(shù)設(shè)置塊內(nèi)頻率測(cè)Sts1.8測(cè)試結(jié)果示例8/6/202333Sts1.8測(cè)試結(jié)果示例8/4/202333Sts1.8測(cè)試結(jié)果分析-通過(guò)幾率分析結(jié)果分析報(bào)告給出每個(gè)測(cè)試項(xiàng)目的通過(guò)的幾率若alpha=0.01,理想通過(guò)幾率為99%.測(cè)試1000個(gè)樣本序列,頻率測(cè)試通過(guò)996個(gè),則頻率測(cè)試實(shí)際通過(guò)幾率為99.6%.統(tǒng)計(jì)測(cè)試可接受通過(guò)幾率:

m為樣本序列個(gè)數(shù)m=1000個(gè)時(shí),可接受的通過(guò)幾率98%;m=100個(gè)時(shí),可接受的通過(guò)幾率96%;8/6/202334Sts1.8測(cè)試結(jié)果分析-通過(guò)幾率分析結(jié)果分析報(bào)告給出每個(gè)測(cè)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ì),計(jì)算統(tǒng)計(jì)值,用于判斷是否均勻分布. Fi:p值分布區(qū)間序列個(gè)數(shù) S:樣本數(shù)量如果p_value>=0.0001則認(rèn)為均勻分布8/6/202335Sts1.8測(cè)試結(jié)果分析-p值統(tǒng)計(jì)分析結(jié)果分析報(bào)告給出每個(gè)測(cè)DIEHARD測(cè)試結(jié)果分析測(cè)試結(jié)束輸出一個(gè)結(jié)果文件,包括各項(xiàng)測(cè)試p值.測(cè)試項(xiàng)目的p值范圍0.025~0.975認(rèn)為通過(guò)。在測(cè)試得到的上百個(gè)p值中，即使是真正的隨機(jī)數(shù)也可能出現(xiàn)p值測(cè)試失敗。當(dāng)p值出現(xiàn)6個(gè)以上0/1時(shí)，可以肯定序列不隨機(jī)。8/6/202336DIEHARD測(cè)試結(jié)果分析測(cè)試結(jié)束輸出一個(gè)結(jié)果文件,包括各項(xiàng)標(biāo)準(zhǔn)比較Sp800-22測(cè)試項(xiàng)目比較全面,但參數(shù)設(shè)置范圍比較大,會(huì)影響測(cè)試結(jié)果.當(dāng)p值出現(xiàn)異常時(shí)還需要測(cè)試更多的序列來(lái)判斷是統(tǒng)計(jì)異常還是確認(rèn)為不隨機(jī)數(shù)序列Fips140-x統(tǒng)計(jì)測(cè)試不夠全面,容易通過(guò)Diehard測(cè)試也比較全面,但是測(cè)試結(jié)果只能參考,偶然的p值不符合要求不能說(shuō)明序列不隨機(jī).文檔說(shuō)當(dāng)p值有6個(gè)以上失效時(shí)才能確認(rèn)為不隨機(jī)的序列.8/6/202337標(biāo)準(zhǔn)比較Sp800-22測(cè)試項(xiàng)目比較全面,但參數(shù)設(shè)置范圍比標(biāo)準(zhǔn)應(yīng)用情況宏思:fips140-2(真隨機(jī)數(shù)IP通過(guò)標(biāo)準(zhǔn))數(shù)據(jù)所:fips140-1(數(shù)據(jù)所隨機(jī)數(shù)測(cè)試軟件)銀行卡檢測(cè)中心:SP800-22(根據(jù)測(cè)試項(xiàng)目)8/6/202338標(biāo)準(zhǔn)應(yīng)用情況宏思:fips140-2(真隨機(jī)數(shù)IP通過(guò)標(biāo)準(zhǔn)宏思隨機(jī)數(shù)IP測(cè)試結(jié)果FM239測(cè)試采集11MB的fm239(宏思IP)數(shù)據(jù)通過(guò)fips140-x測(cè)試(20kbit)Diehard測(cè)試不通過(guò)(80Mbit),9個(gè)p值為1Sp800-22測(cè)試不通過(guò)(10Mbit),不通過(guò)項(xiàng)目包括塊內(nèi)最長(zhǎng)游程測(cè)試傅立葉測(cè)試近似熵測(cè)試連續(xù)測(cè)試普通統(tǒng)計(jì)測(cè)試模板測(cè)試8/6/202339宏思隨機(jī)數(shù)IP測(cè)試結(jié)果FM239測(cè)試8/4/202339FM262隨機(jī)數(shù)測(cè)試結(jié)果采集1Gbit的卡隨機(jī)數(shù)Diehard測(cè)試32x32的二進(jìn)制矩陣秩測(cè)試p值為1,其余p值沒(méi)發(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è)試通過(guò)連續(xù)測(cè)試(測(cè)試100個(gè)序列)m=16/8均100%通過(guò)m=4/5,通過(guò)率99%近似熵測(cè)試(測(cè)試10