NIST随机性检测方法及应用

《NIST随机性检测方法及应用》由会员分享，可在线阅读，更多相关《NIST随机性检测方法及应用（13页珍藏版）》请在装配图网上搜索。

1、NIST 随机性检测方法及应用本科教学工程 大学生创新创业训练研究1 引言密码算法是构建安全信息系统的核心要素之一， 是保障信息与数据机密性、 完整性和真 实性的重要技术。 密码算法检测评估是密码算法研究的重要组成部分， 它为密码算法的设计、 分析提供客观的量化指标和技术参数， 对密码算法的应用具有重要的指导意义 在密码算法 的设计和评测过程中，需要从多个方面对其进行检测和分析。一次一密(One-Time Pad)”是序列密码产生的思想来源， 序列密码的核心是通过固定算法， 将一串短的密钥序列扩展为长 周期的密钥流序列， 且密钥流序列在计算能力内应与随机序列不可区分。 因此， 分析秘钥流 序列

2、的随机性是密码算法安全性研究的重要内容， 利用 NIST 检测方法对密码算法进行评测 可以为理论分析提供大量参考数据， 从而减少理论分析者的工作量， 同时可以暴露出用现有 的分析方法无法发现的安全漏洞。2 NIST 检测方法2.1 随机性检测随机性检测通常通过概率统计的方法考察被检测序列是否满足随机序列的某些特征以 判定其是否随机。从理论上讲，若被检测序列未通过某一随机性检测，可以肯定该序列不随机；但反之， 若被检测序列能够通过某一种随机性检测， 却不能肯定这个序列是随机的， 即通过随机性检 测是序列具有随机性的必要非充分条件。 因为各检测方法中的检测项目往往都是根据随机序 列所表现出的某一方

3、面的特征而设计的。 事实上， 任何一个由有限种检测项目组成的集合都 无法囊括随机性的所有方面。 但在实际应用中， 如果这个检测的设计对于随机序列使用时的 具体要求而言是充分的，且被检测序列又能通过该检测，则认为该序列的随机性是“合格” 的。随机性检测利用概率统计的方法对随机数发生器或者密码算法产生序列的随机性进行 描述不同的检测项目从不同的角度刻画待检测序列与真随机序列之间的差距随机性检测通常采用假设检验 的方法假设检验就是在总体分布未知或者只知其形式 但不知其参数的情况下， 为了推断总体的某些性质而提出某些关于总体的假设， 然后根据样 本对提出的假设做出判断 随机性假设检验， 就是已知真随机

4、序列的某一方面符合一个特定 的分布， 那么假设待检测序列是随机的， 则该待检测序列在这方面也应该符合这个特定的分 布在实际应用中，常用来衡量随机性的方法是 P value法，这里以测试统计量 X服从2 分布为例来说明。以随机序列的某种统计值 V符合自由度为n的卡方分布为例：原假设(零假设)H。：序列是随机的，待测序列的统计值V服从2(n)分布；2备择假设 Hi ：序列不是随机的，待测序列的统计值V不服从 (n)分布.通过判断一个待测序列的统计值V是否服从2(n)分布来确定是否接受原假设， 从而判断该序列是否通过了该项随机性检测在随机性检测中判断是否接受原假设通常采用P-Value方法.P-Va

5、lue是一个序列比真随机序列的随机性要好的概率.利用统计值矿求出 P-Value,并将P-Value与显著性水平 较如果P-Value，则接受原假设，判断该待测序列通过了该项随机性检测.作出方面的研究，提供标准、标准参考数据及有关服务，在国际上享有很高的声誉。美国国家标准与技术研究所提供的Special Publication800-22测试包16（简称NIST随机性测试）。NIST测试程序是一个统计包，包括16种测试手段。这些测试手段可测试由用作保密随机或者伪随机数发生器的硬件和软件产生的任意长的2进制序列的随机性。这些测试手段主要致力于判定可能存在于序列中的多种多样的非随机性。其中一些测试

6、又可以分解成多种子测验。这16种测试手段是： 频率检验，该检验主要是看0和1在整个序列中所占的比例。检验的目的是确定序列中的 1和0数是否与真正的随机序列中的1和0数近似相同。检验评定1码占1/2，也就是说，在整个序列中0和1的数目是一样的。其余别的检验手段都是在该检验成立的基础上进行 的，并且没有任何证据表明被测序列是不随机的。 块内频数检验，分布的概率密度曲线，如图2-1所示，先求出统计量X，然后计算从X到无穷的积分，将积分结果（即P value）与 进行比较，进而确定拒绝还是 接受。本文中讨论的随机性测试即是通过选取的测试统计量来计算P value，将P value作为接受原假设的强度，

7、其含义是：真随机数的随机性比待测序列差的 概率。如果其值为1，则是完全真随机的，如果值为 0，则是完全非随机的。对 于显著性水平 ，如果P value，那么原假设被接受，序列是随机的；反之被拒绝，序列是非随机的。参数 也即是表2-1中犯第I类错误的概率，一般的， 的取值范围是0.001,0.01。图12分布的概率密度曲线及P value值美国国家标准与技术研究院（Natio nal In stitute of Sta ndards and Tech no logy , NIST）直属美国商务部，从事物理、生物和工程方面的基础和应用研究，以及测量技术和测试方法此检验主要是看 M 位的子块中“ 1

8、”码的比例。该检验的目的是判定M 位的子块内“ 1”码的频率是否像随机假设下所预期的那样，近似于M/2。当M=1时，该检测相当于检测 1位,即频数（一位）检验。3. 游程检验，此检验主要是看游程的总数，游程指的是一个没有间断的相同数序列，即游程或者是“ 1111”或者是“ 0000”。一个长度为k的游程包含k个相同的位。游程检测的目的是 判定不同长度的 “1 ”游程的数目以及 “0”游程的数目是否跟理想的随机序列的期望值相一 致。具体的讲，就是该检验手段判定在这样的“0 ” “ 1 ”子块之间的振荡是否太快或太慢。4. 块内最长游程检验，该检验主要是看长度为 M-bits 的子块中的最长“ 1

9、”游程。这项检验的目的是判定待检验序 列的最长“ 1”游程的长度是否同随机序列的相同。注意：最长“1”游程长度上的一个不规则变化意味着相应的“ 0”游程长度上也有一个不规则变化，因此，仅仅对“ 1”游程进行检 验室足够的。5. 二元矩阵秩检验，该检验主要是看整个序列的分离子矩阵的秩。 目的是核对源序列中固定长度子链间的线性依 赖关系。6. 离散傅里叶变换检验，本检验主要是看对序列进行分步傅里叶变换后的峰值高度。目的是探测待检验信号的周期 性，以此揭示其与相应的随机信号之间的偏差程度。做法是观察超过95%阈值的峰值数目与低于 5%峰值的数目是否有显著不同。7. 非重叠模块匹配检验，此检测主要是看

10、提前设置好的目标数据串发生地次数。 目的是探测那些产生太多给出的非周 期模式的发生器。 对于非重叠模块匹配检验以及后面会谈到的重叠模块匹配检验方法，我们都是使用一个 m-bit 的窗口来搜素一个特定的 m-bit 模式。如果这个模式没有被找到，则 窗口向后移动一位。 如果模式被发现， 则窗口移动到一发现的模式的后一位， 重复前面的步 骤继续搜素下一个模式。8. 重叠模块匹配检验， 该检验主要是看提前设定的目标模块发生地数目。 检验步骤同非重叠模块匹配检验方法大致 一样，不同点在于，发现目标模块后，窗口仅向后移动 1 位，而后继续搜索。9. Maurer 的通用统计检验，检验主要是看匹配模块间的

11、 bit 数。目的是检验序列能否在没有信息损耗的条件下被大大的 压缩。一个能被大大压缩的序列被认为是一个非随机序列。10. Lempel-Ziv 压缩检验， 本检测主要是看整个序列中不同模式积累的数目（单词数目） 。检验目的是判定待测序列能 够被压缩到什么程度。 若序列不能被明显的压缩， 则该序列就是非随机的。 一个随机序列有 特征数个不同模式。11. 线性复杂度检验， 本检验手段主要是看线性反馈移位寄存器的长度。 检验的目的是判定序列的复杂程度是否达 到可视为是随 机序列的程度。随机序列的特点是有较长的线性反馈移位寄存器。一个线性 反馈移位寄存器太小的话意味着序列非随机。12. 序列检验，本

12、检验主要是看整个序列中所有可能的重叠 m-bit 模式的频率，目的是判定 2m 个 m-bit 重 叠模式的数目是否跟随机情况下预期的值相近似。随机序列具有均匀性也就是说对于每个 m-bit 模式其出现的概率应该是一样的。当 m=1 时等价于频数检验。13. 近似熵检验，同序列检验一样， 近似熵检验主要看的也是整个序列中所有可能的重叠 m-bit 模式的频率。 目的是将两相邻长度 （m 和 m+1） 的重叠子块的频数与随机情况下预期的频数相比较。14. 累加和检验， 该检验主要是看随机游动的最大偏移。随机游动被定义为序列中调整后的-1， +1 的累加和。检验的目的是判定序列的累加和相对于预期的

13、累加和过大还是过小。 这个累加和可被看做随 机游动。对于随机序列， 随机游动的偏离应该在 0 附近。 而对于非随机序列，这个随机游动 偏离将会比 0 大很多。15. 随机游动检验， 本检验主要是看一个累加和随机游动中具有 K 个节点的循环的个数。累加和随机游动由于 将关于“ 0”，“1”的部分和序列转化成适当的“ -1”、“ +1”序列产生的。一个随机游动循环 由单位步长的一个序列组成， 这个序列的起点和终点均是0。该检验的目的是确定在一个循环内的特殊状态对应的节点数是否与在随机序列中预计达到的节点数相背离。实际上， 这个检验由八个检验（和结论）组成，一个检验和结论对应着一个特定的状态：-4，

14、 -3， -2，-1和+1， +2， +3， +4 。16. 随机游动状态频数检验。该检验主要是看累计和随机游动中经历的特殊状态的总数。 检验目的是判定随机游动中实际 经历多个状态的值与预期值之间的偏离程度。该检验实际上是十八个检验（和结论） ，每个 状态对应着一个检验和一个结论。这些状态分别是：-9，-8，-7，-6，-5，-4，-3， -2， -1 和+1， +2， +3，+4， +5， +6， +7， +8。本文的随机性测试属于黑盒测试。 在测试中，被测试的算法被看作一个黑盒， 随机性测试并不深入算法内部， 也不关心算法本身的设计结构， 仅仅通过观察外 部行为来确定算法的输出特性。本节中

15、具体介绍了NIST随机性测试相关理论。NIST测试套件有15个测试项，用来检测任意长度二进制序列的随机性，其表4-1假设检验结论实际情况接受H0接受出H。：假设序列是随机的正确第1类错误（弃真）H1 :假设序列是不随机的第II类错误（存伪）正确NIST测试套件的基本测试思想如下:对于每一个测试项，先给定一个显著性水平， 0.001,0.01。再给出两个假设：原假设H0（序列是随机的）和备择假设H1 （序列是不随机的），然后根据 给定统计量的分布函数和统计结果返回一个 P value，将它与先前给定的 进行 比较，从而判断随机性。其中 P value是一个概率值，P value 0,1。若P v

16、alue，则接受原假设H。，即序列是随机的；若P value，则拒绝原假设H。，即序列是不随机的；当P value 1时，表示待测序列是一个完美的真随机序列；当P value 0时，表示待测序列是一个完全不随机的序列。三、ZUC算法祖冲之（ZUC算法集是由我国学者自主设计的加密和完整性算法，包括祖 冲之（ZUC算法、加密算法128-EEA3和完整性算法128-EIA3,已经被国际组织 3GPP推荐为4G无线通信的第三套国际加密和完整性标准算法。2010年12月2至3日由中国科学院信息工程研究所信息安全国家重点实验 室和中国科学院数据与通信保护研究教育中心（DCS中心）联合主办的第一届 祖冲之算

17、法国际研讨会在北京召开。这次国际研讨会对于加强祖冲之算法研究 分析成果的国内和国际交流，扩大祖冲之算法的公开平评估范围，加强祖冲之算法的安全性评估力度，进而推进祖冲之算法4G通信国际加密标准的进度产生了重要的现实意义。2011年9月在日本福冈召开的第53次3GPP系统架构组会议上，我国祖冲 之算法（ZUC被批准成为新一代宽带无线移动通信系统（LTE国际标准78。ZUC算法是我国自主设计的一个面向字的序列密码，它用128位初始密钥k和128位的初始向量iv作为输入，输出32位字的密钥流（每32位称为一个密钥 字），密钥流可用于对信息进行加解密。ZUC算法逻辑上采用三层结构4910，即 线性反馈移

18、位寄存器（LFSR）1、比特重组（BR）和非线性函数（F）,其整体结构如图 3-1所示：图3-1 ZUC算法整体结构图本文选取上述15个测试项进行测试，若被测试序列能全部通过这15个测试, 我们就认为该序列是随机的，取显著性水平0.01。在密码学中，初始密钥和初始向量都为“ 0”时，算法生成密钥流的随机性 性最差23，这时如果能通过随机性检测，说明在其它情况也能通过测试。 所以这 里我们令初始密钥和初始向量都为“ 0”。1. 运行ZUC算法程序，进入主界面，选择“ 1”:吨始择 =.旱“卫 gMl *初该选 =入出的 =输艮-您2. 输入初始密钥、初始向量和密钥字个数（如图），初始密钥：0 0

19、 0 0 0 0 0 0 0 0 0 0 0 0 0 0初始向量：0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0密钥字个数：40000现在我们已经得到了 40000 32位的密钥流序列。运行后生成了两个密钥流 文件：zuc.txt和zuc1.txt，分别是以二进制和十六进制表示的。NIST测试要求密 钥流序列是以二进制表示的，所以我们需要的文件是zuc.txt。初始蜜銀 0B00909090 初女古 llnlw：BB0BB0BBBBBBBBBB 宓廟字个数胡酿00密钿範二逬剖己写入iw . txt密韌流+六卅制己写入n ucl.txtPress any key to conti

20、nue四、随机性测试接下来我们对上面生成的密钥流序列进行随机性检测。 NIST提供的随机性检 测包需要在Linux系统下运行，本文所用系统为在 VM虚拟机下安装的Red Hat Linux系统。4.1 Linux 系统下的makefile检测方法首先我们需要对测试包中的 makefile文件进行配置，修改gcc（ Linux系统的 C语言编译器）的位置和输入测试包所在目录，然后运行makefile文件，进行编译，编译结束后生成可执行文件 assess assess执行时需要输入序列长度，刚才 我们生成的序列长度为：40000 32 1280000。1.运行assess并输入序列长度，如下图:I

21、tHjaEliutL ；Lr2Ad!,-2.文件汕匸査看(里)终端转到帮助(H(ktiuqulDfa Iho t ngrucn t in I 115 XCR71 Ulum-Blum-Shut)K CSHVIEn te r Clio i ce ： 03. 输入421中生成的以二进制表示的密钥流序列文件“zuc.txt”:hile r Uiu ice: 0Urej Prescr 1npuI F i le: zuc.In14. 输入1”，对15项全部进行测试：STA11 ST1CAL TESTS02 Black FroqLoncy04 Runs0& RankQg Nonper iodic TenpI

22、t10 Uiiver sa I Stdt ist i I 2 Riinduiii Etur 14 Setia1Mi 1； rh i ng g01 Frequency0A Qimi la t i ve Sum砧Lotlgest Run oi (he sIV i sere t e F-oitr ier Trans for m09 O i lapping Templa te M tchings11 Apprciiu U EdiLrvpyJ 5 RaiidumVai iaai1 石Linesr Qjnrp lexi iyI NSTRUCTl ONStn Le r 0 l f /du tt NLJL v

23、ii n t Ldppy all ol thes t ii t i 1 i ca I tests io each seque nee and 】if you DU.Enler Qice: 1|5. 输入“ 0”，参数调整选择默认值：R j r a m e L r A d j u & l m e n I s1 Blflck Frequency Tes 1 - hlock, lenpthf M :128r2bbntXer lapp ing Tf npla le Tcsl - b lock If nj lhT 9rSJCX r lappimg Tenpin te Tcslblock lengthrh

24、):94 yYpproxhih io Enirof)y Tfi - block lenih(in):1(5 St r ia I Te4 1 - block knth( nD :166 Luwai Chirp lex i 1y les t - block length( M 15(10Se lect Test (0 cont iiiue) ； 0|6. 输入“ 0”，ASCII的0、1序列，也就是以二进制表示的序列：1npui File Fnrnat:ro ASCI I - A Fqi時nE of ASCI Os 2nd 11s11 Hinar y Each by le in dj la f i

25、 le cunta inn g bi Ln cf thixSt ltd input mde ;皿7. 测试完成：Inpu t Fi le Fcrim t:0 ASCJ I - A :equejice aT ASCJI 0 s jnd I s1 Buis r y - Each by te m da to file eon tains g b 11 o f da taSt leIR)/linearCainplNitj|.o l$(0BJDIR)/dF1:t .04 .运行“ cygi n”5进入测试包所在目录/cygdcive/ d/cygwin/ho*e/D3huqu/ ata口回冈Dshuqu

26、d $ cd /cygdm ve/d/cygvui n/home/bshuqu/stflDshuqud /匚ygdrive/d/cyqwin/home/bshuqu/sts6.make - makefile 生成assess文件“ /cygdcive/ d/cypin/FmE/Dzhijqu/at s回区Dshuqud -J 匚ci 比ygdri ve/d/cygwi n/hame/tshu口口/stsDshuqud /cygdrive/d/cygwin/kiome/Dshugu/sts$ make -f makefn 1 e|7.运行 assess/pyffflriveAd/cygwj n/

27、hn巳fDshuqu/p：*?：匚口 | X_|Dshuqij(&d S cd /cygdri ve/d/cyijbji n/kiiDme/t) & huqu/st 5D-huqud /cygdrive/d/cygwi n/home/Dshuqu/st5$ ./a.5 5es5 WQOQOO8.进入测试Dshuqud *$ cd /cygdrive/d/cygwi n/home/Dshuqu/stsDhuqud /cygdrive/d/cygwi n/home/Dshuqu/sts$ ./assess 1QOQQOOGENERA.TOR SELECTION_O.工npuiz Fi 1Aj CJ

28、uadratic Ccmgrutntial I4 Cubi c Congru tnti al16 Modul ar Exiwnenti ationMi cali-Schnorr9 -9 - 一= rl口呂9Li near Congruential Quadrat-i c Cor gr uertt-i si II 倾Bl urn-el um-ShubG Using 5HA-1Enter Choice:8. 测试结果及中间过程都写入了各自对应的目录中，经整理后检测结果如表4-2所示：表4-2随机性检测结果测试项P-value频率测试(Frequency)0.472934块内频率测试(Block F

29、requency)(m=128)0.666461累积和测试(CumulativeSums)-Forward0.494930累积和测试(CumulativeSums)-Reverse0.698499游程检测(Runs)0.302109块内最长连续1测试(LongestRunofOnes)0.107293二元矩阵秩测试(Rank)0.579405离散傅里叶变换测试(FFT)0.119393非重叠模版匹配测试(No nO verlapp in gTemplate)(m=9,B=000000001)0.508413重叠模版匹配测试(Overlapp in gTemplate)(m=9)0.739918

30、全局通用统计测试(Uni versal)0.338818近似熵检测(ApproximateEntropy)(m=10)0.112173随机偏移测试(RandomExcursions)(x=+1)0.135938随机偏移变量测试(Ra ndomExcursio nsVaria nt)(x=-1)0.429142线性复杂度检测(LinearComplexity)(M=500)0.454981串行测试(Serial)(m=16)0.1071924.3结果分析由上表可以看出，15个测试项的P value值全部大于显著性水平(0.01)，而且有5项(块内频率测试、累积和测试、二元矩阵秩测试、非重叠模版匹

31、配测 试、重叠模版匹配测试)的P value值超过了 0.5，所以ZUC算法生成的密钥流 序列是随机的，也就是说ZUC算法安全性很好。参考文献1 CCSA. Specification of the 3GPP Con fide ntiality and In tegrity Algorithms 128-EEA3 & 128-EIA3. Docume nt 2: ZUC Specificatio n S,2011.2 陈希孺.概率论及数理统计M.科学出版社，2000.3 杜红红，张文英.祖冲之算法的安全分析J.计算机技术与发展ISTIC, 2012, 22(6).4 冯秀涛.3GPP LTE国

32、际加密标准 ZUC算法J.信息安全与通信保密，2012, 9(12): 45-46.5 于亦舟.密码分析工具软件包的设计与研究D.西安电子科技大学，2007. 关杰，丁林，刘树凯，SNOW 3G和ZUC流密码的猜测决定攻击J，软件学报，24(6), 2013 : 1324-1333.7 亓民勇，董金新，潘全科.信息安全中序列随机性测试系统的研究与设计J.计算机工程与设计，2008, 29(6): 1453-1455.8 Rukhi n A, Soto J, Nechvatal J, et al. A statistical test suite for ran dom and pseudora

33、 ndom number generators for cryptographic applicationsR. BOOZ-ALLEN AND HAMILTON INC MCLEAN V A, 2001.9 王宏杰.随机数的在线测试与后续处理D.太原理工大学，2012.10 彭巍.一种分组密码算法测试平台设计D.电子科技大学，2005.11 师国栋，康绯，顾海文.随机性测试的研究与实现J.计算机工程，2009, 35(20):145-147.12 刘志巍.密码算法的随机性测试研究D.西安电子科技大学，2011.13 黄佳琳，来学嘉.随机性测试的淘汰能力和相关性J.信息安全与通信保密，2009 (10):43-46.14 CCSA. Specification of the 3GPP Confidentiality and Integrity Algorithms 128-EEA3 & 128-EIA3 Document 3: Implementor s Test DataS,2011.