随机数统计测试方法课件

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,随机数统计测试方法,2007/12/12,8/9/2024,1,随机数统计测试方法2007/12/128/4/20231,常用测试标准,NIST,SP800-22(序列长度=1Mbit),SP:NIST Special Publication(800 Series),FIPS 140_1/2(序列长度=20kbit),FIPS:,The Federal Information Processing Standards,由美国商业部批准颁发,Florida State University,DIEHARD(序列长度=80Mbit),8/9/2024,2,常用测试标准NIST8/4/20232,NIST SP800-22,概述,NIST(美国国家标准技术研究所,National Institute of Standards and Technology,)的一种全面的随机数统计测试方法，规定了满足各种程度随机性的衡量标准。,软件套件(NIST Statistical Test Suite),csrc.nist.gov/groups/ST/toolkit/rng/documentation_software.html,:sts-1.8.zip,相关标准:csrc.nist.gov/groups/ST/toolkit/rng/documents/SP800-22b.pdf,8/9/2024,3,NIST SP800-22概述8/4/20233,NIST FIPS 140_x,概述,FIPS140-1/FIPS140-2是美国商业部批准颁发的,文件，关于随机数部分测试相对比较简单.,相关文件:,csrc.nist.gov/publications/fips/fips140-2/fips1402.pdf,csrc.nist.gov/publications/fips/fips140-1/fips1401.pdf,8/9/2024,4,NIST FIPS 140_x概述8/4/20234,DIEHARD测试,Florida State University的George Marsaglia开发,测试套件:,stat.fsu.edu/pub/diehard,/diehard.zip,测试项目:,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 1s in a stream of bytes,count the 1s in specific bytes,parking lot,minimum distance,random spheres,squeeze,Overlapping sums,runs,and craps.,8/9/2024,5,DIEHARD测试Florida State Univers,FIPS140-x测试项目,测试输入,一个序列,长度20,000bit,测试项目,频率测试(monobit test),扑克测试(poker test),游程测试(runs test),长游程测试(long run test),8/9/2024,6,FIPS140-x测试项目测试输入8/4/20236,FIPS140-x频率测试(monobit test),测试方法,计算20,000bit序列中1的个数,记为X,如果,9654X10,346 测试通过(FIPS140-1),9725X10,275 测试通过(FIPS140-2),测试目的,检查1或0过多缺陷,8/9/2024,7,FIPS140-x频率测试(monobit test)测试方,FIPS140-x扑克测试(poker test),测试方法,将20,000位的比特流按4位一组分成5000组,每组共有16种可能的数据产生,统计每种数据的个数记为f(i),其中i=015,计算,判断,若2.16X46.17,测试通过(fips140-2),若1.03X alpha,SUCCESS,若,p,value,=100,测试方法,Sn=X1+X2+Xn(根据序列值,求Xi=1或-1),计算统计量Sobs,计算p,value,.,测试目的,检查1和0的总数是否大致相同,8/9/2024,16,SP800-22频率测试输入8/4/202316,SP800-22,块内频率测试,输入,n:比特流序列长度(n=100),M:块长度(M=20,M0.01n),测试方法,将比特流按M_bit长度分N块(N=n/M),计算每个块内1的比例,计算N块的统计量,计算 p,value,.,测试目的,检查M-bit块内1和0的总数是否大致相同.,8/9/2024,17,SP800-22块内频率测试输入8/4/202317,SP800-22,累积和测试,输入,n:比特流序列长度,测试方法,求出n个部分和:S1Sn,找出部分和的最大值,计算p,value,.,测试目的,是否每一个阶段的1或0过多,8/9/2024,18,SP800-22累积和测试输入8/4/202318,SP800-22,游程测试,输入,n:比特流序列长度,测试方法,计算1的比率,计算序列中1游程和0游程的总数Vn(obs),计算 p,value,测试目的,检查序列的游程是否震荡太快或太慢,8/9/2024,19,SP800-22游程测试输入8/4/202319,SP800-22,块内最长游程测试,输入,n:比特流序列长度(n=750,000),测试方法,将比特流按 M_bit(M=10,000)长度分N块(N=n/M),计算每个块内1的最长游程;,统计不同最长游程的块数vi并计算统计量.,计算 p,value,.,测试目的,检测序列内1的最长游程是否随机,8/9/2024,20,SP800-22块内最长游程测试输入8/4/202320,SP800-22,二进制矩阵测试,输入,n:比特流序列长度(n=38912),测试方法,将比特流划分为N个MxQ矩阵(M=Q=32),求出每个矩阵的秩(RANK),统计不同秩矩阵的总数,计算RANK的统计量.,计算 p,value.,测试目的,测试固定长度子序列间的线性独立性,8/9/2024,21,SP800-22二进制矩阵测试输入8/4/202321,SP800-22,离散付利叶变换测试,输入,n:比特流序列长度(n=1000),测试方法,进行DFT变换及其相关统计量,计算p,value,.,测试目的,检查比特流是否具有周期特性.,8/9/2024,22,SP800-22离散付利叶变换测试输入8/4/202322,SP800-22,非重叠模板匹配测试,输入,n:比特流序列长度(n=1000000),m:模板长度(210可选,推荐使用9或10),B:m_bit模板(软件模板库中定义),测试方法,将比特流分成N(sts1.8:N=8)个的独立的块,统计每个块中B模板出现的次数Wi,计算N块的统计量,计算 p,value,.,测试目的,检查是否序列中模板B出现太多,8/9/2024,23,SP800-22非重叠模板匹配测试输入8/4/202323,SP800-22,重叠模板匹配测试,输入,n:比特流序列长度(n=1000000),m:模板长度(210可选,推荐使用9或10),测试方法,将比特流分成N个的独立的块(块长M=1032bit),统计每个块中B模板(m个连续1)出现的次数.,计算N块的统计量,计算 p,value,.,测试目的,检查是否序列中m个连续1的子序列出现太多.,8/9/2024,24,SP800-22重叠模板匹配测试输入8/4/202324,SP800-22 Maurers,普通统计测试1,输入,n:比特流序列长度,L:块长度,Q:初始化段块的个数,推荐值见后表,测试方法,按块长度L 和初始化段块的个数Q将序列划分初始化段和测试段,统计两种段中各块向量的位置.,计算统计量和p,value,.,测试目的,检查序列信息压缩损耗是否显著,若认为序列有规律能够被压缩,可以视为不随机,8/9/2024,25,SP800-22 Maurers普通统计测试1输入8/4/,SP800-22 Maurers,普通统计测试2,8/9/2024,26,SP800-22 Maurers普通统计测试28/4/20,SP800-22,连续测试,输入,n:比特流序列长度,m:块长度(,m=1000000),测试方法,计算累计部分和序列S1Sn,S,k,=,X,1,+,+X,k,以部分和值0为界,把序列划分为J次漂移,为使计算有效,取,J=500,且不能小于,统计每次漂移中出现不同漂移值的频率个数(漂移值x的范围为-44).,计算统计量和 p,value,.,测试目的,检测连续的二进制序列(1/-1)的累计部分和序列是否为随机漂移序列,8/9/2024,29,SP800-22随机漂移测试输入8/4/202329,SP800-22,随机漂移变异测试,输入,n:比特流序列长度(n=1000000),测试方法,计算累计部分和序列S1Sn,S,k,=,X,1,+,+X,k,统计上述序列中出现不同漂移值x(范围为-99)的个数,计算统计量和 p,value,.,测试目的,检测二进制序列(1/-1)的累计部分和,S,k,序列是否为随机分布,8/9/2024,30,SP800-22随机漂移变异测试输入8/4/202330,SP800-22,线性复杂度测试,输入,n:比特流序列长度,M:模块长度(500M0.01n),非重叠模板匹配测试:模板长度m=9(9/10),重叠模板匹配测试:模板长度m9(9/10),Maurers普通统计测试:,模块长度L=7,模块数Q=1280(n=1Mbit),模块长度L=16,模块数Q=655360(n=1Gbit),线性复杂性测试:模块长度M=500(500M5000),连续测试:模块长度m=16(,m=,log,2,n-,2),近似熵测试:模块长度 m=10(,m 1/alpha),序列长度n=1Mbit,序列数=100,允许1%失败,序列长度n=1Gbit,序列数1(银行卡检测中心使用参数),8/9/2024,32,SP800-22测试软件(Sts_1.8)参数设置块内频率测,Sts1.8测试结果示例,8/9/2024,33,Sts1.8测试结果示例8/4/202333,Sts1.8测试结果分析-通过几率分析,结果分析报告给出每个测试项目的通过的几率,若alpha=0.01,理想通过几率为99%.,测试1000个样本序列,频率测试通过996个,则频率测试实际通过几率为99.6%.,统计测试可接受通过几率:,m为样本序列个数,m=1000个时,可接受的通过几率98%;,m=100个时,可接受的通过几率96%;,8/9/2024,34,Sts1.8测试结果分析-通过几率分析结果分析报告给出每个测,Sts1.8测试结果分析-p值统计分析,结果分析报告给出每个测试项目的p值分布统计,根据不同测试项目的p值范围统计,计算统计值,用于判断是否均匀分布.,Fi:p值分布区间序列个数,S:样本数量,如果p_value=0.0001,则认为均匀分布,8/9/2024,35,Sts1.8测试结果分析-p值统计分析结果分析报告给出每个测,DIEHARD测试结果分析,测试结束输出一个结果文件,包括各项测试p值.,测试项目的p值范围0.025 0.975认为通过。,在测试得到的上百个p值中，即使是真正的随机数也可能出现p值测试失败。,当p值出现6个以上0/1时，可以肯定序列不随机。,8/9/2024,36,DIEHARD测试结果分析测试结束输出一个结果文件,包括各项,标准比较,Sp800-22测试项目比较全面,但参数设置范围比较大,会影响测试结果.当p值出现异常时还需要测试更多的序列来判断是统计异常还是确认为不随机数序列,Fips140-x统计测试不够全面,容易通过,Diehard测试也比较全面,但是测试结果只能参考,偶然的p值不符合要求不能说明序列不随机.文档说当p值有6个以上失效时才能确认为不随机的序列.,8/9/2024,37,标准比较Sp800-22测试项目比较全面,但参数设置范围比,标准应用情况,宏思:fips140-2(真随机数IP通过标准),数据所:fips140-1(数据所随机数测试软件),银行卡检测中心:SP800-22(根据测试项目),8/9/2024,38,标准应用情况宏思:fips140-2(真随机数IP通过标准,宏思随机数IP测试结果,FM239测试,采集11MB的fm239(宏思IP)数据,通过fips140-x测试(20kbit),Diehard测试不通过(80Mbit),9个p值为1,Sp800-22测试不通过(10Mbit),不通过项目包括,块内最长游程测试,傅立叶测试,近似熵测试,连续测试,普通统计测试,模板测试,8/9/2024,39,宏思随机数IP测试结果FM239测试8/4/202339,FM262随机数测试结果,采集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%,近似熵测试(测试100个序列),m=16/10均100%通过,m=4/5,通过率99%,取m=5,LenSeq=1000000,NumSeq=1000,BlkFreqBlkLen=100,Rank测试通过率85%,测试失败.,其余14项测试全部通过,Sp800-22测试(1Gbit序列),8/9/2024,40,FM262随机数测试结果采集1Gbit的卡随机数8/4/20,Fm239 sts1.8测试数据(10个1Mbit序列),Freq,Blk,Freq,CuSum,Fwd,CuSum,Rev,Runs,Long,Runs,Rank,DF,FT,Univ,Apen,Serial1,Serial2,Lin,Comp,0.045,0.442,0.048,0.06,0.901,0,0.408,0,0.039,0,0,0,0.213,0,0.862,0,0,0.864,0,0.687,0,0.002,0,0,0,0.587,0,0.754,0,0,0.993,0,0.028,0,0,0,0,0,0.602,0.021,0.601,0.017,0.036,0.93,0,0.424,0,0.407,0,0,0,0.849,0.039,0.015,0.018,0.074,0.308,0,0.267,0,0,0,0,0,0.759,0.135,0.629,0.183,0.195,0.974,0,0.077,0,0.154,0,0,0,0.909,0.005,0.351,0.009,0.004,0.265,0,0.303,0,0.1,0,0,0,0.207,0.293,0.082,0.417,0.393,0.427,0,0.289,0,0,0,0,0,0.166,0,0.73,0,0,0.868,0,0.181,0,0.9,0,0,0,0.525,0.015,0.73,0.017,0.027,0.526,0,0.48,0,0.65,0,0,0,0.461,8/9/2024,41,Fm239 sts1.8测试数据(10个1Mbit序列)Fr,