NIST随机性检测方法及应用

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

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

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

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

5、统计值矿求出 P-Value,并将 P-Value 与显著性水平比较.如果 P-Value至a,则接受原假设，判断该待测序列通过了该项随机性检测.作出？2分布的概率密度曲线，如图 2-1 所示，先求出统计量 X,然后计算从 X X 到无穷的积分，将积分结果（即 P Pvaluevalue）与 a 进行比较，进而确定拒绝还是接受。本文中讨论的随机性测试即是通过选取的测试统计量来计算 P-valueP-value, ,将P*leP*le 作为接受原假设的强度，其含义是：真随机数的随机性比待测序列差的概率。如果其值为 1,则是完全真随机的，如果值为 0,则是完全非随机的。对于显著性水平 0f,如果

6、P Pvaluevalue 之 a,那么原假设被接受，序列是随机的；反之被拒绝，序列是非随机的。 参数 a 也即是表 2-1 中犯第 I 类错误的概率， 一般的， a 的取值范围是 0,001,0.010图 1*分布的概率密度曲线及 P-value 值美国国家标准与技术研究院（NationalInstituteofStandardsandTechnology,NIST）直属美国商务部，从事物理、生物和工程方面的基础和应用研究，以及测量技术和测试方法方面的研究，提供标准、标准参考数据及有关服务，在国际上享有很高的声誉。美国国家标准与技术研究所提供的 SpecialPublication800-2

7、2 测试包16（简称 NIST 随机性测试）。NIST 测试程序是一个统计包，包括 16 种测试手段。这些测试手段可测试由用作保密随机或者伪随机数发生器的硬件和软件产生的任意长的 2 进制序列的随机性。这些测试手段主要致力于判定可能存在于序列中的多种多样的非随机性。其中一些测试又可以分解成多种子测验。这 16 种测试手段是：1.频率检验，该检验主要是看 0 和 1 在整个序列中所占的比例。检验的目的是确定序列中的 1 和 0数是否与真正的随机序列中的 1 和 0 数近似相同。检验评定 1 码占 1/2,也就是说，在整个序列中 0 和 1 的数目是一样的。其余别的检验手段都是在该检验成立的基础上

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

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

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

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

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

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

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

15、个测试项，用来检测任意长度二进制序列的随机性，具中每项测试都是建立在假设检验基础上的，见表 4-1表 4-1 假设检验结论实际情况接受H0接受H1H。：假设序列是随机的正确第 I 类错误（弃真）HI:假设序列是不随机的第 II 类错误（存伪）正确NIST 测试套件的基本测试思想如下：对于每一个测试项， 先给定一个显著性水平 a a, ,awaw0.001,0.010.001,0.01。 再给出两个假设：原假设 H H0（序列是随机的）和备择假设 H H（序列是不随机的），然后根据给定统计量的分布函数和统计结果返回一个 P-valueP-value,将它与先前给定的 a a 进行比较，从而判断随

16、机性。其中 P-valueP-value 是一个概率值，P-valueP-valuew w0,10,1。若 P-valueP-value，则接受原假设 H。,即序列是随机的；若 P-valueP-valueaa,则拒绝原假设 H。，即序列是不随机的；当 P-valueP-value=1=1 时，表示待测序列是一个完美的真随机序列；当 P-valueP-value=0=0 时，表示待测序列是一个完全不随机的序列。三、ZUC算法祖冲之（ZU。算法集是由我国学者自主设计的加密和完整性算法，包括祖冲之（ZUQ 算法、加密算法 128-EEA 邵口完整Tt算法 128-EIA3,已经被国际组织 3GPP

17、推荐为 4G 无线通信的第三套国际加密和完整性标准算法。2010 年 12 月 2 至 3 日由中国科学院信息工程研究所信息安全国家重点实验室和中国科学院数据与通信保护研究教育中心（DCS 中心）联合主办的第一届祖冲之算法国际研讨会在北京召开。这次国际研讨会对于加强祖冲之算法研究分析成果的国内和国际交流，扩大祖冲之算法的公开平评估范围，加强祖冲之算法的安全性评估力度，进而推进祖冲之算法 4G 通信国际加密标准的进度产生了重要的现实意义。2011 年 9 月在日本福冈召开的第 53 次 3GPP 系统架构组会议上，我国祖冲之算法（ZUQ 被批准成为新一代宽带无线移动通信系统（LTE 国际标准口网

18、。ZUC 算法是我国自主设计的一个面向字的序列密码，它用 128 位初始密钥 k k和 128 位的初始向量iv作为输入，输出 32 位字的密钥流（每 32 位称为一个密钥字），密钥流可用于对信息进行加解密。ZUC 算法逻辑上采用三层结构4910,即线性反馈移位寄存器（LFSR）1、比特重组（BR 刘非线卜t函数（F）,其整体结构如图 3-1 所示：本文选取上述 15 个测试项进行测试，若被测试序列能全部通过这 15 个测试，我们就认为该序列是随机的，取显著性水平= =0.010.01o0在密码学中， 初始密钥和初始向量都为“0”时， 算法生成密钥流的随机性性最差23,这时如果能通过随机性检测

19、，说明在其它情况也能通过测试。所以这里我们令初始密钥和初始向量都为“0”。1.运行 ZUC 算法程序，进入主界面，选择“1”:2.输入初始密钥、初始向量和密钥字个数（如图），初始密钥：0000000000000000初始向量：0000000000000000密钥字个数：40000现在我们已经得到了 40000M40000M3232 位的密钥流序列。运行后生成了两个密钥流文件：zuc.txt 和 zuc1.txt,分别是以二进制和十六进制表示的。 NIST 测试要求密钥流序列是以图 3-1ZUC 算法整体结构图LFSR二进制表示的，所以我们需要的文件是 zuc.txto四、随机性测试接下来我们对

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

21、序列长度，如下图：/ /二加巴口二加巴口4|.。肛肛- -1二二包二至包二至24.1文件文件漏相如杳吊漏相如杳吊V终热终热转到帮助以转到帮助以dshuqulocaIhostdhuqu$cd/hont/dshuqu/s15-2/s15-2.1AdshuqulocaLhostst.J.I3Jac史史“12K0UDU.进入测试界面，输入“0；导入文件：dshuqulocaIbosts15-2JI5i./assess)280000GENERATORSELECTION.输入 4.2.1 中生成的以二进制表示的密钥流序列文件s”进六k二十2(cA包用e0HputFile2QiadralicChngrufn

22、IiaIIQihicGingrucntiflJfiMxlulRkponenLtiunh4caIi-SchnorrEnterQloire;011LinerGnigruuiiliuI31QiadriiIic(hngrurntiuIII5jXCK71Rlum-Blluni-ShubGUsingSH-1zuc.txt”：000)已写入HUG.txt制，已写入NUC1.txttoContinueKJIter：16LinearGnplexilyTesi-blocklenglh(M1J50。SeIeclTest(0tocontinue)：.输入“0，ASCII 的 0、1 序列，也就是以二进制表示的序列：I

23、nputFiIeForm1(:0ASCI1AsequenceofASCIIOsand1sIBinary-Eachbyteindjlafilecontains8bitsofdalaSekcLinpulmnle：017.测试完成：InpulFilef-orirat:0ASCI1-AsequenceofASCI0snd1711Hinary-EachbytemdatafiIfcontainsSbitsofdalaSeledinpuimule：flStatistiC3ILesting1nProgress.F.F.r,.TStuI1sticaITeslingGonpIEIE!4.2sts-2.1.1 软件

24、检测法该方法可以直接在 XP 系统下运行 sts-2.1.1 软件进行随机性检查，方法如下,1.安装cygin，选择与gcc 有关的项目。CygwinSetupCygwinNetR画easeSetupProgramThissetupprogramisusedfortheinitialinstallationoJtheCygwinenvironmentaswel曰&allsubsequentLfidatss.MakesuretorememberwhereyousaveditThepagesthatfollowwillguideyouthroughthein就都讨icm.Pleaserot

25、ethatCygwinconsistsofalargenumberofpackagesspanningawidevarietyofpuiposec.We0nMinstallati.asesetoJpackagesbydefault.Youcanalwaysrumthisprogramatarytimeinthefuturetoadd.temove,orupgradepackages会necessary.Setup.exeversion2.850(32bit)Copyright2000-2013hH口:),科“内一cud丽n.corn/取消取消2.NIST 包3.记事本打开makefile修改“

26、CC=(gcc 所在位置)和“ROOTDIR=(安装包所在目录)，如CC=/cygdrive/d/cygwin/bin/gcc.exeROOTDIR=/cygdrive/d/cygwin/home/Dshuqu/ststmakefile-记事本TJfc|fX,文件任文件任) )编辑编辑格式格式Q)查看查看 9 9 帮助卸帮助卸CC=/cygdriue/d/ci|gwln/t) )in/gcc.exelGCCFLfiGS=-c-Wall!ROOTDIR=/cygdrlue/d/ctgwin/home/Dshuqu/stslSRCDIR=$(RDOTDlR)/srclOBJDlR-$(RQ)TDR

27、)/objlUPATH=src:obj:includeHOBJ=$(DBJDIR)/assess.o$(OBJDIR)/Frequency.o$(OBJDIR)/blockFrequenc_olS(OBJDIR)/cusum.0$(OBJDiR)/runs.o$(OBJDIR)/longe5tRunOFOnes.ol$(OBJDrR)/serial,o$(OIBJDIK)/rank,o$(UBJDIR)/dj.screteFourierTransFormRol$(OBJDIR)/nonOuerlappingTeRplateiiatcliings.0l$(0BJDIR)/ouerlappingT

28、enipldtel1atching5.0$(OBJDIR)/universal.ol$(OBJDlR)/approxinateEntropp.o$(OBJDIR:)/randomExcurslons.0M$(OlBJDIR)/rdndomExcursionsUariant-o$(OBJDIR)/linearGoniplexit( (i-ol$(OBJDIR)/dfft.o4.运行“cygin”厄/cygdrive/d/cygin/hoBe/Dshuqu/stsDshuqud$cd/cygdrive/d/cygwin/hcme/Dshuqu/stsDshuqud/cygdrive/d/cygwi

29、n/hoirie/Dshuqu/sts.makefmakefile 生成 assess 文件反/cygdrive/d/cygwin/hoBe/Dhuqu/stsDshuqudd$cd/cygdrive/d/cygwin/home/Dshuqu/stsDshuqud/cygdrive/d/cygwin/home/Dshuqu/sts$make-fmakefi1e|.运行 assess但/cygdrive/d/cygin/home/Dshuqu/stsDshuquAd$cd/cygdrive/d/cygwin/hoirie/bshLjqLj/stspshuqucl/cygdrive/d/cygwi

30、n/home/bshuqu/sts$*/assess1000000.进入测试0间区5.进入测试包所在目录E/cygdrive/d/cygYin/ho&e/Dshuqu/sts-XDshuqud$cd/cygdrive/d/cygwin/hotne/Dshuqu/stsD5huqud/cygdrive/d/cyn/home/DEhuqu/sts$*/assess1Q00000GENERATORSELECTIONEnterChoice:8.测试结果及中间过程都写入了各自对应的目录中，经整理后检测结果如表 4-2所小：表 4-2 随机性检测结果测试项P-value频率测试(Frequency

31、)0.472934块内频率测试(BlockFrequency)(m=128)0.666461累积和测试(CumulativeSums)-Forward0.494930累积和测试(CumulativeSums)-Reverse0.698499游程检测(Runs)0.302109块内最长连续 1 测试(LongestRunofOnes)0.107293二元矩阵秩测试(Rank)0.579405离散傅里叶变换测试(FFT)0.119393非重叠模版匹配测试(NonOverlappingTemplate)(m=9,B=000000001)0.508413重叠模版匹配测试(OverlappingTemp

32、late)(m=9)0.739918全局通用统计测试(Universal)0.338818近似嫡检测(ApproximateEntropy)(m=10)0.112173随机偏移测试(RandomExcursions)(x=+1)0.135938随机偏移变量测试(RandomExcursionsVariant)(x=-1)0.429142线性复杂度检测(LinearComplexity)(M=500)0.454981串行测试(Serial)(m=16)0.1071924.3 结果分析由上表可以看出，15 个测试项的 P-valueP-value 值全部大于显著性水平 (=0.01),(=0.01),而且有 5 项(块内频率测试、累积和测试、二元矩阵秩测试、非重叠模版匹配测试、重叠模版匹配测试)的 P-valueP-value 值超过了 0.5,所以 ZUCB 法生成的密钥流序列是随机的，也