1、2022-6-151随机数统计测试方法随机数统计测试方法2007/12/122022-6-152常用测试标准 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)2022-6-153NIST SP800-22 概述NIST(美国国家标准技术研究所,
2、 National 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.pdf2022-6-154NIST FIPS 140_x概述F
3、IPS140-1/FIPS140-2是美国商业部批准颁发的文件，关于随机数部分测试相对比较简单.相关文件: http:/csrc.nist.gov/publications/fips/fips140-2/fips1402.pdfhttp:/csrc.nist.gov/publications/fips/fips140-1/fips1401.pdf2022-6-155DIEHARD测试Florida State University的George Marsaglia开发测试套件: http:/stat.fsu.edu/pub/diehard/diehard.zip测试项目:birthday sp
4、acings, 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.2022-6-156FIPS140-x测试项目 测试输入 一个序列,长度20,000bit 测试项目 频率测试(monobit test) 扑克测试(poker test) 游程测试(runs test) 长游程测试(long run test)2022-6-157FIPS140-x频率测试(monobit test) 测试方法 计算20,000bit序列中1的个数,记为X,如果 9654X10,346 测试通过(FIPS140-1) 9725X10,275 测试通过(FIPS140-2) 测试目的 检查1或0过多缺陷2022-6-158FIPS140-x扑克测试(poker t
6、est) 测试方法 将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的总数是否大致相同2022-6-1517SP800-22块内频率测试块内频率测试 输入 n:比特流序列长度(n=100) M:块长度(M=20,M0.01n) 测试方法 将比特流按M_bit长度分N
7、块(N=n/M) 计算每个块内1的比例 计算N块的统计量 计算 pvalue. 测试目的 检查M-bit块内1和0的总数是否大致相同.2022-6-1518SP800-22累积和测试累积和测试 输入 n:比特流序列长度 测试方法 求出n个部分和:S1Sn 找出部分和的最大值 计算pvalue. 测试目的 是否每一个阶段的1或0过多2022-6-1519SP800-22游程测试游程测试 输入 n:比特流序列长度 测试方法 计算1的比率 计算序列中1游程和0游程的总数Vn(obs) 计算 pvalue 测试目的 检查序列的游程是否震荡太快或太慢2022-6-1520SP800-22块内最长游程测试
8、块内最长游程测试 输入 n:比特流序列长度(n=750,000) 测试方法 将比特流按 M_bit (M=10,000)长度分N块(N=n/M) 计算每个块内1的最长游程; 统计不同最长游程的块数vi并计算统计量. 计算 pvalue. 测试目的 检测序列内1的最长游程是否随机2022-6-1521SP800-22二进制矩阵测试二进制矩阵测试 输入 n:比特流序列长度(n=38912) 测试方法 将比特流划分为N个MxQ矩阵(M=Q=32) 求出每个矩阵的秩(RANK) 统计不同秩矩阵的总数,计算RANK的统计量. 计算 pvalue. 测试目的 测试固定长度子序列间的线性独立性2022-6-
9、1522SP800-22离散付利叶变换测试离散付利叶变换测试 输入 n:比特流序列长度(n=1000) 测试方法 进行DFT变换及其相关统计量 计算pvalue. 测试目的 检查比特流是否具有周期特性.2022-6-1523SP800-22非重叠模板匹配测试非重叠模板匹配测试 输入 n: 比特流序列长度(n=1000000) m:模板长度(210可选,推荐使用9或10) B: m_bit模板(软件模板库中定义) 测试方法 将比特流分成N(sts1.8:N=8)个的独立的块 统计每个块中B模板出现的次数Wi 计算N块的统计量 计算 pvalue. 测试目的 检查是否序列中模板B出现太多2022-
10、6-1524SP800-22重叠模板匹配测试重叠模板匹配测试 输入 n: 比特流序列长度(n=1000000) m:模板长度(210可选,推荐使用9或10) 测试方法 将比特流分成N个的独立的块(块长M=1032bit ) 统计每个块中B模板(m个连续1)出现的次数. 计算N块的统计量 计算 pvalue. 测试目的 检查是否序列中m个连续1的子序列出现太多.2022-6-1525SP800-22 Maurers普通统计测试普通统计测试1输入 n: 比特流序列长度 L :块长度 Q :初始化段块的个数 推荐值见后表测试方法 按块长度L 和初始化段块的个数Q将序列划分初始化段和测试段, 统计两种
11、段中各块向量的位置. 计算统计量和pvalue.测试目的 检查序列信息压缩损耗是否显著,若认为序列有规律能够被压缩,可以视为不随机2022-6-1526SP800-22 Maurers普通统计测试普通统计测试22022-6-1527SP800-22连续测试连续测试 输入 n: 比特流序列长度 m:块长度 (m =1000000)测试方法 计算累计部分和序列S1Sn, Sk = X1 + +Xk 以部分和值0为界,把序列划分为J次漂移,为使计算有效,取J =500且不能小于 统计每次漂移中出现不同漂移值的频率个数(漂移值x的范围为-44). 计算统计量和 pvalue.测试目的 检测连续的二进制
12、序列(1/-1)的累计部分和序列是否为随机漂移序列2022-6-1530SP800-22随机漂移变异测试随机漂移变异测试 输入 n: 比特流序列长度(n=1000000) 测试方法 计算累计部分和序列S1Sn, Sk = X1 + +Xk 统计上述序列中出现不同漂移值x(范围为-99)的个数 计算统计量和 pvalue. 测试目的 检测二进制序列(1/-1)的累计部分和Sk 序列是否为随机分布2022-6-1531SP800-22线性复杂度测试线性复杂度测试 输入 n: 比特流序列长度 M :模块长度(500M0.01n)非重叠模板匹配测试: 模板长度m = 9 (9/10)重叠模板匹配测试:
13、 模板长度m9 (9/10)Maurers普通统计测试: 模块长度L=7, 模块数Q=1280(n=1Mbit) 模块长度L=16, 模块数Q=655360(n=1Gbit)线性复杂性测试: 模块长度M=500 (500M5000)连续测试: 模块长度m=16 (m = log2n - 2)近似熵测试: 模块长度 m=10 (m 1/alpha) 序列长度n=1Mbit,序列数=100 ,允许1%失败 序列长度n=1Gbit,序列数1(银行卡检测中心使用参数)2022-6-1533Sts1.8测试结果示例2022-6-1534Sts1.8测试结果分析-通过几率分析结果分析报告给出每个测试项目的
14、通过的几率若alpha=0.01,理想通过几率为99%.测试1000个样本序列,频率测试通过996个,则频率测试实际通过几率为99.6%.统计测试可接受通过几率: m为样本序列个数m=1000个时,可接受的通过几率98%;m=100个时,可接受的通过几率96%;2022-6-1535Sts1.8测试结果分析-p值统计分析结果分析报告给出每个测试项目的p值分布统计 根据不同测试项目的p值范围统计,计算统计值,用于判断是否均匀分布.Fi:p值分布区间序列个数S:样本数量 如果p_value=0.0001 则认为均匀分布2022-6-1536DIEHARD测试结果分析 测试结束输出一个结果文件,包括
15、各项测试p值. 测试项目的p值范围0.025 0.975认为通过。 在测试得到的上百个p值中，即使是真正的随机数也可能出现p值测试失败。 当p值出现6个以上0/1时，可以肯定序列不随机。2022-6-1537标准比较 Sp800-22测试项目比较全面, 但参数设置范围比较大,会影响测试结果.当p值出现异常时还需要测试更多的序列来判断是统计异常还是确认为不随机数序列 Fips140-x统计测试不够全面,容易通过 Diehard测试也比较全面,但是测试结果只能参考,偶然的p值不符合要求不能说明序列不随机.文档说当p值有6个以上失效时才能确认为不随机的序列.2022-6-1538标准应用情况 宏思:
16、 fips140-2(真随机数IP通过标准) 数据所: fips140-1(数据所随机数测试软件) 银行卡检测中心: SP800-22(根据测试项目)2022-6-1539宏思随机数IP测试结果 FM239测试 采集11MB的fm239 (宏思IP)数据 通过fips140-x测试(20kbit) Diehard测试不通过(80Mbit), 9个p值为1 Sp800-22测试不通过(10Mbit),不通过项目包括 块内最长游程测试 傅立叶测试 近似熵测试 连续测试 普通统计测试 模板测试2022-6-1540FM262随机数测试结果采集1Gbit的卡随机数Diehard测试32x32的二进制矩
17、阵秩测试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项测试全部通过Sp80
18、0-22测试(1Gbit序列)2022-6-1541Fm239 sts1.8测试数据(10个1Mbit序列)FreqBlkFreqCuSumFwdCuSumRevRunsLongRunsRankDFFTUnivApenSerial1Serial2LinComp0.0450.4420.0480.060.90100.40800.0390000.21300.862000.86400.68700.0020000.58700.754000.99300.028000000.6020.0210.6010.0170.0360.9300.42400.4070000.8490.0390.0150.0180.0740.30800.267000000.7590.1350.6290.1830.1950.97400.07700.1540000.9090.0050.3510.0090.0040.26500.30300.10000.2070.2930.0820.4170.3930.42700.289000000.16600.73000.86800.18100.90000.5250.0150.730.0170.0270.52600.4800.650000.461
