隨機數統計測試方法2007/12/128/6/20231隨機數統計測試方法2007/12/128/4/20231常用測試標準NISTSP800-22(序列長度>=1Mbit)SP:NISTSpecialPublication(800Series)FIPS140_1/2(序列長度=20kbit)FIPS:TheFederalInformationProcessingStandards由美國商業部批準頒發FloridaStateUniversityDIEHARD(序列長度>=80Mbit)8/6/20232常用測試標準NIST8/4/20232NISTSP800-22概述 NIST(美國國家標準技術研究所,NationalInstituteofStandardsandTechnology)的一種全面的隨機數統計測試方法，規定了滿足各種程度隨機性的衡量標準。軟件套件(NISTStatisticalTestSuite)/groups/ST/toolkit/rng/documentation_software.html:sts-1.8.zip相關標準:/groups/ST/toolkit/rng/documents/SP800-22b.pdf8/6/20233NISTSP800-22概述8/4/20233NISTFIPS140_x概述 FIPS140-1/FIPS140-2是美國商業部批準頒發的文件，關于隨機數部分測試相對比較簡單.相關文件:/publications/fips/fips140-2/fips1402.pdf/publications/fips/fips140-1/fips1401.pdf8/6/20234NISTFIPS140_x概述8/4/20234DIEHARD測試FloridaStateUniversity的GeorgeMarsaglia開發測試套件:/pub/diehard/diehard.zip測試項目:birthdayspacings,overlappingpermutations,ranksof31x31and32x32matrices,ranksof6x8matrices,monkeytestson20-bitWords,monkeytestsOPSO,OQSO,DNA,countthe1'sinastreamofbytes,countthe1'sinspecificbytes,parkinglot,minimumdistance,randomspheres,squeeze,Overlappingsums,runs,andcraps.8/6/20235DIEHARD測試FloridaStateUniversFIPS140-x測試項目測試輸入一個序列,長度20,000bit測試項目頻率測試(monobittest)撲克測試(pokertest)游程測試(runstest)長游程測試(longruntest)8/6/20236FIPS140-x測試項目測試輸入8/4/20236FIPS140-x頻率測試(monobittest)測試方法計算20,000bit序列中1的個數,記為X,如果9654<X<10,346測試通過(FIPS140-1)9725<X<10,275測試通過(FIPS140-2)測試目的檢查1或0過多缺陷8/6/20237FIPS140-x頻率測試(monobittest)測試方FIPS140-x撲克測試(pokertest)測試方法將20,000位的比特流按4位一組分成5000組每組共有16種可能的數據產生統計每種數據的個數記為f(i),其中i=0~15計算判斷 若2.16<X<46.17,測試通過(fips140-2)若1.03<X<57.4,測試通過(fips140-1)測試目的檢查4bit模板的分布缺陷8/6/20238FIPS140-x撲克測試(pokertest)測試方法8FIPS140-x游程測試1(runstest)定義游程:一個游程是指連續0或1的序列測試方法統計20,000bit流中各種長度游程的個數若游程長度大于6的按6記若每種長度的游程個數都符合標準要求(見后頁表格)時，認為通過Runs測試測試目的檢查bit流數據變化是否太快或太慢8/6/20239FIPS140-x游程測試1(runstest)定義8/4FIPS140-x游程測試2(runstest)游程測試標準表1LengthFips140-1Fips140-212267~27332315~268521079~14211114~13863502~748527~7234223~402240~384590~223103~2096+90~223103~2098/6/202310FIPS140-x游程測試2(runstest)游程測試FIPS140-x長游程測試(longruntest)定義長游程Fips140-1:當游程的長度大于等于34時Fips140-2:當游程的長度大于等于26時測試方法統計20,000bit流中長游程的個數若無長游程，則通過長游程測試測試目的檢查是否存在長游程8/6/202311FIPS140-x長游程測試(longruntest)定SP800-22測試項目(sts_1.8)頻率測試塊內頻率測試游程測試塊內最長游程測試二進制矩陣測試離散付利葉變換測試非重疊模板匹配測試重疊模板匹配測試

普通統計測試線性復雜性測試連續測試近似熵測試累積和測試隨機漂移測試隨機漂移變異測試

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

若pvalue<alphaFAILURE

alpha=[0.001,0.01]代表容許的錯誤機率上限若alpha=0.01,序列數應不小于100若alpha=0.001,序列數應不小于10008/6/202315SP800-22評估方法基于bit的統計測試方法8/4/20SP800-22頻率測試輸入比特流序列長度(n)n>=100測試方法Sn=X1+X2+…+Xn(根據序列值,求Xi=1或-1)計算統計量Sobs計算pvalue.測試目的檢查1和0的總數是否大致相同8/6/202316SP800-22頻率測試輸入8/4/202316SP800-22塊內頻率測試輸入n:比特流序列長度(n>=100)M:塊長度(M>=20,M>0.01n)測試方法將比特流按M_bit長度分N塊(N=[n/M])計算每個塊內1的比例計算N塊的統計量計算pvalue.測試目的檢查M-bit塊內1和0的總數是否大致相同.8/6/202317SP800-22塊內頻率測試輸入8/4/202317SP800-22累積和測試輸入n:比特流序列長度測試方法求出n個部分和:S1~Sn找出部分和的最大值計算pvalue.測試目的是否每一個階段的1或0過多8/6/202318SP800-22累積和測試輸入8/4/202318SP800-22游程測試輸入n:比特流序列長度測試方法計算1的比率計算序列中1游程和0游程的總數Vn(obs)計算pvalue測試目的檢查序列的游程是否震蕩太快或太慢8/6/202319SP800-22游程測試輸入8/4/202319SP800-22塊內最長游程測試輸入n:比特流序列長度(n>=750,000)測試方法將比特流按M_bit(M=10,000)長度分N塊(N=[n/M])計算每個塊內1的最長游程;統計不同最長游程的塊數vi并計算統計量.計算pvalue.測試目的檢測序列內1的最長游程是否隨機8/6/202320SP800-22塊內最長游程測試輸入8/4/202320SP800-22二進制矩陣測試輸入n:比特流序列長度(n>=38912)測試方法將比特流劃分為N個MxQ矩陣(M=Q=32)求出每個矩陣的秩(RANK)統計不同秩矩陣的總數,計算RANK的統計量.計算pvalue.測試目的測試固定長度子序列間的線性獨立性8/6/202321SP800-22二進制矩陣測試輸入8/4/202321SP800-22離散付利葉變換測試輸入n:比特流序列長度(n>=1000)測試方法進行DFT變換及其相關統計量計算pvalue.測試目的檢查比特流是否具有周期特性.8/6/202322SP800-22離散付利葉變換測試輸入8/4/202322SP800-22非重疊模板匹配測試輸入n:比特流序列長度(n=1000000)m:模板長度(2~10可選,推薦使用9或10)B:m_bit模板(軟件模板庫中定義)測試方法將比特流分成N(sts1.8:N=8)個的獨立的塊統計每個塊中B模板出現的次數Wi計算N塊的統計量計算pvalue.測試目的檢查是否序列中模板B出現太多8/6/202323SP800-22非重疊模板匹配測試輸入8/4/202323SP800-22重疊模板匹配測試輸入n:比特流序列長度(n=1000000)m:模板長度(2~10可選,推薦使用9或10)測試方法將比特流分成N個的獨立的塊(塊長M=1032bit)統計每個塊中B模板(m個連續1)出現的次數.計算N塊的統計量計算pvalue.測試目的檢查是否序列中m個連續1的子序列出現太多.8/6/202324SP800-22重疊模板匹配測試輸入8/4/202324SP800-22Maurer's普通統計測試1輸入n:比特流序列長度L:塊長度Q:初始化段塊的個數推薦值見后表測試方法按塊長度L和初始化段塊的個數Q將序列劃分初始化段和測試段,統計兩種段中各塊向量的位置.計算統計量和pvalue.測試目的檢查序列信息壓縮損耗是否顯著,若認為序列有規律能夠被壓縮,可以視為不隨機8/6/202325SP800-22Maurer's普通統計測試1輸入8/4/SP800-22Maurer's普通統計測試28/6/202326SP800-22Maurer's普通統計測試28/4/20SP800-22連續測試輸入n:比特流序列長度m:塊長度(m<=log2(n)-2)測試方法計算各種塊向量(2m種)出現的頻率.計算統計量.計算pvalue.測試目的檢測序列中給定長度(m)的不同向量分布的均勻性,當m=1時等效為頻率測試.m=4時等效為fips140-x的Poker測試8/6/202327SP800-22連續測試輸入8/4/202327SP800-22近似熵測試輸入n:比特流序列長度m:塊長度測試方法統計各種塊向量(2m種)出現的頻率.計算近似熵ApEn(一種對數的頻率測量).計算pvalue.測試目的檢測給定序列是否為無規律序列.8/6/202328SP800-22近似熵測試輸入8/4/202328SP800-22隨機漂移測試輸入n:比特流序列長度(n>=1000000)測試方法計算累計部分和序列S1~Sn,Sk

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

=X1+…+Xk統計上述序列中出現不同漂移值x(范圍為-9~9)的個數計算統計量和pvalue.測試目的檢測二進制序列(1/-1)的累計部分和Sk

序列是否為隨機分布8/6/202330SP800-22隨機漂移變異測試輸入8/4/202330SP800-22線性復雜度測試輸入n:比特流序列長度M:模塊長度(500<M<5000)測試方法將比特流分成N個長度為M的塊.評估產生二進制序列所需的最短的LFSR(線性反饋移位寄存器)長度.計算pvalue.測試目的檢測序列是否具有較長的移位寄存器特性.8/6/202331SP800-22線性復雜度測試輸入8/4/202331SP800-22測試軟件(Sts_1.8)參數設置塊內頻率測試:塊長度M=128(M>0.01n)非重疊模板匹配測試:模板長度m=9(9/10)重疊模板匹配測試:模板長度m＝9(9/10)Maurer's普通統計測試:模塊長度L=7,模塊數Q=1280(n=1Mbit)模塊長度L=16,模塊數Q=655360(n=1Gbit)線性復雜性測試:模塊長度M=500(500<M<5000)連續測試:模塊長度m=16(m<=log2n-2)近似熵測試:模塊長度m=10(m<=log2n)數據長度1Gbit,alpha取0.01(序列數>1/alpha)序列長度n=1Mbit,序列數>=100,允許1%失敗序列長度n=1Gbit,序列數1(銀行卡檢測中心使用參數)8/6/202332SP800-22測試軟件(Sts_1.8)參數設置塊內頻率測Sts1.8測試結果示例8/6/202333Sts1.8測試結果示例8/4/202333Sts1.8測試結果分析-通過幾率分析結果分析報告給出每個測試項目的通過的幾率若alpha=0.01,理想通過幾率為99%.測試1000個樣本序列,頻率測試通過996個,則頻率測試實際通過幾率為99.6%.統計測試可接受通過幾率:

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