1、2018/7/11,1,随机数统计测试方法,2007/12/12,2018/7/11,2,常用测试标准,NISTSP800-22 (序列长度=1Mbit)SP: NIST Special Publication (800 Series) FIPS 140_1/2(序列长度=20kbit)FIPS:The Federal Information Processing Standards由美国商业部批准颁发Florida State UniversityDIEHARD(序列长度=80Mbit),2018/7/11,3,NIST SP800-22,概述NIST(美国国家标准技术研究所, Nation
2、al Institute of Standards and Technology )的一种全面的随机数统计测试方法，规定了满足各种程度随机性的衡量标准。软件套件(NIST Statistical Test Suite) http:/csrc.nist.gov/groups/ST/toolkit/rng/documentation_software.html: sts-1.8.zip相关标准: http:/csrc.nist.gov/groups/ST/toolkit/rng/documents/SP800-22b.pdf,2018/7/11,4,NIST FIPS 140_x,概述FIPS14
3、0-1/FIPS140-2是美国商业部批准颁发的文件，关于随机数部分测试相对比较简单.相关文件: http:/csrc.nist.gov/publications/fips/fips140-2/fips1402.pdfhttp:/csrc.nist.gov/publications/fips/fips140-1/fips1401.pdf,2018/7/11,5,DIEHARD测试,Florida State University的George Marsaglia开发测试套件: http:/stat.fsu.edu/pub/diehard/diehard.zip测试项目:birthday spa
4、cings, 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
5、craps.,2018/7/11,6,FIPS140-x测试项目,测试输入一个序列,长度20,000bit测试项目频率测试(monobit test)扑克测试(poker test)游程测试(runs test)长游程测试(long run test),2018/7/11,7,FIPS140-x频率测试(monobit test),测试方法计算20,000bit序列中1的个数,记为X,如果9654X10,346 测试通过(FIPS140-1)9725X10,275 测试通过(FIPS140-2)测试目的检查1或0过多缺陷,2018/7/11,8,FIPS140-x扑克测试(poker test
6、),测试方法将20,000位的比特流按4位一组分成5000组每组共有16种可能的数据产生统计每种数据的个数记为f(i),其中i=015计算判断若2.16X46.17,测试通过(fips140-2)若1.03X alpha SUCCESS 若 pvalue =100测试方法Sn=X1+X2+Xn (根据序列值,求Xi=1或-1)计算统计量Sobs计算pvalue.测试目的检查1和0的总数是否大致相同,2018/7/11,17,SP800-22块内频率测试,输入n:比特流序列长度(n=100)M:块长度(M=20,M0.01n)测试方法将比特流按M_bit长度分N块(N=n/M)计算每个块内1的比
7、例计算N块的统计量计算 pvalue.测试目的检查M-bit块内1和0的总数是否大致相同.,2018/7/11,18,SP800-22累积和测试,输入n:比特流序列长度测试方法求出n个部分和:S1Sn找出部分和的最大值计算pvalue.测试目的是否每一个阶段的1或0过多,2018/7/11,19,SP800-22游程测试,输入n:比特流序列长度测试方法计算1的比率计算序列中1游程和0游程的总数Vn(obs)计算 pvalue测试目的检查序列的游程是否震荡太快或太慢,2018/7/11,20,SP800-22块内最长游程测试,输入n:比特流序列长度(n=750,000)测试方法将比特流按 M_b
8、it (M=10,000)长度分N块(N=n/M)计算每个块内1的最长游程;统计不同最长游程的块数vi并计算统计量.计算 pvalue.测试目的检测序列内1的最长游程是否随机,2018/7/11,21,SP800-22二进制矩阵测试,输入n:比特流序列长度(n=38912)测试方法将比特流划分为N个MxQ矩阵(M=Q=32) 求出每个矩阵的秩(RANK)统计不同秩矩阵的总数,计算RANK的统计量.计算 pvalue.测试目的测试固定长度子序列间的线性独立性,2018/7/11,22,SP800-22离散付利叶变换测试,输入n:比特流序列长度(n=1000)测试方法进行DFT变换及其相关统计量计
9、算pvalue.测试目的检查比特流是否具有周期特性.,2018/7/11,23,SP800-22非重叠模板匹配测试,输入n: 比特流序列长度(n=1000000)m:模板长度(210可选,推荐使用9或10)B: m_bit模板(软件模板库中定义)测试方法将比特流分成N(sts1.8:N=8)个的独立的块统计每个块中B模板出现的次数Wi计算N块的统计量计算 pvalue.测试目的检查是否序列中模板B出现太多,2018/7/11,24,SP800-22重叠模板匹配测试,输入n: 比特流序列长度(n=1000000)m:模板长度(210可选,推荐使用9或10)测试方法将比特流分成N个的独立的块(块长
10、M=1032bit )统计每个块中B模板(m个连续1)出现的次数.计算N块的统计量计算 pvalue.测试目的检查是否序列中m个连续1的子序列出现太多.,2018/7/11,25,SP800-22 Maurers普通统计测试1,输入n: 比特流序列长度L :块长度Q :初始化段块的个数推荐值见后表测试方法按块长度L 和初始化段块的个数Q将序列划分初始化段和测试段, 统计两种段中各块向量的位置.计算统计量和pvalue.测试目的检查序列信息压缩损耗是否显著,若认为序列有规律能够被压缩,可以视为不随机,2018/7/11,26,SP800-22 Maurers普通统计测试2,2018/7/11,2
11、7,SP800-22连续测试,输入n: 比特流序列长度m:块长度 (m =1000000)测试方法计算累计部分和序列S1Sn, Sk = X1 + +Xk以部分和值0为界,把序列划分为J次漂移,为使计算有效,取J =500且不能小于统计每次漂移中出现不同漂移值的频率个数(漂移值x的范围为-44).计算统计量和 pvalue.测试目的检测连续的二进制序列(1/-1)的累计部分和序列是否为随机漂移序列,2018/7/11,30,SP800-22随机漂移变异测试,输入n: 比特流序列长度(n=1000000)测试方法计算累计部分和序列S1Sn, Sk = X1 + +Xk统计上述序列中出现不同漂移值
12、x(范围为-99)的个数计算统计量和 pvalue.测试目的检测二进制序列(1/-1)的累计部分和Sk 序列是否为随机分布,2018/7/11,31,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 (5001/alpha)序列长度n=1Mbit,序列数=100 ,允许1%失
13、败序列长度n=1Gbit,序列数1(银行卡检测中心使用参数),2018/7/11,33,Sts1.8测试结果示例,2018/7/11,34,Sts1.8测试结果分析-通过几率分析,结果分析报告给出每个测试项目的通过的几率若alpha=0.01,理想通过几率为99%.测试1000个样本序列,频率测试通过996个,则频率测试实际通过几率为99.6%.统计测试可接受通过几率: m为样本序列个数m=1000个时,可接受的通过几率98%;m=100个时,可接受的通过几率96%;,2018/7/11,35,Sts1.8测试结果分析-p值统计分析,结果分析报告给出每个测试项目的p值分布统计根据不同测试项目的
14、p值范围统计,计算统计值,用于判断是否均匀分布.Fi:p值分布区间序列个数S:样本数量如果p_value=0.0001 则认为均匀分布,2018/7/11,36,DIEHARD测试结果分析,测试结束输出一个结果文件,包括各项测试p值.测试项目的p值范围0.025 0.975认为通过。在测试得到的上百个p值中，即使是真正的随机数也可能出现p值测试失败。当p值出现6个以上0/1时，可以肯定序列不随机。,2018/7/11,37,标准比较,Sp800-22测试项目比较全面, 但参数设置范围比较大,会影响测试结果.当p值出现异常时还需要测试更多的序列来判断是统计异常还是确认为不随机数序列Fips140
15、-x统计测试不够全面,容易通过Diehard测试也比较全面,但是测试结果只能参考,偶然的p值不符合要求不能说明序列不随机.文档说当p值有6个以上失效时才能确认为不随机的序列.,2018/7/11,38,标准应用情况,宏思: fips140-2(真随机数IP通过标准)数据所: fips140-1(数据所随机数测试软件)银行卡检测中心: SP800-22(根据测试项目),2018/7/11,39,宏思随机数IP测试结果,FM239测试采集11MB的fm239 (宏思IP)数据通过fips140-x测试(20kbit)Diehard测试不通过(80Mbit), 9个p值为1Sp800-22测试不通过
16、(10Mbit),不通过项目包括块内最长游程测试傅立叶测试近似熵测试连续测试普通统计测试模板测试,2018/7/11,40,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=100Rank测试通过率85%,测试失败.其余14项测试全部通过Sp800-22测试(1Gbit序列),2018/7/11,41,Fm239 sts1.8测试数据(10个1Mbit序列),
