随机数统计测试方法课件

随机数统计测试方法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