NIST随机性检测方法及应用

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

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

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

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

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

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

6、原假设被接受，序列是随机的；反之被拒绝，序列是非随机的。参数 也即是表2-1中犯第I类错误的概率，一般的，的取值范围是0.001,0.01 o美国国家标准与技术研究院（National Institute of Standards and Technology , NIST）直属美国商务部，从事物理、生物和工程方面的基础和应用研究，以及测量技术和测试方法方面的研究，提供标准、标准参考数据及有关服务，在国际上享有很高的声誉。美国国家标准与技术研究所提供的Special Publication800-22 测试包16（简称NIST随机性测试）。NIST测试程序是一个统计包，包括16种测试手段。这些

7、测试手段可测试由用作保密随机或者伪随机数发生器的硬件和软件产生的任意长的2进制序列的随机性。这些测试手段主要致力于判定可能存在于序列中的多种多样的非随机性。其中一些测试又可以分解成多种子测验。这16种测试手段是： 1.频率检验，该检验主要是看 0和1在整个序列中所占的比例。检验的目的是确定序列中的1和0数是否与真正的随机序列中的1和0数近似相同。检验评定1码占1/2,也就是说，在整个序列中0和1的数目是一样的。其余别的检验手段都是在该检验成立的基础上进行 的，并且没有任何证据表明被测序列是不随机的。2. 块内频数检验，此检验主要是看M 位的子块中“ 1”码的比例。该检验的目的是判定 M 位的子

8、块内“ 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 的通用统计检验，检验主要是看匹配模块间的 bit 数。目的是检验序列能否在没有信息损耗的条件

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

12、判定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， -3 ， -2 ， -1和 +1 ， +2， +3， +4。16. 随机游动状态频数检验。该

14、检验主要是看累计和随机游动中经历的特殊状态的总数。 检验目的是判定随机游动中实际经历多个状态的值与预期值之间的偏离程度。该检验实际上是十八个检验（和结论） ，每个状态对应着一个检验和一个结论。这些状态分别是： -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接受HiH。：假设序列是随机的正确第I类错误（弃真）Hi :假设序列是不随机的第II类错误（存伪）正确NIST测试套件的基本测试思想如下:对于每一个测试项，先给定一个显著性水平 ，0.001,0.01。再给出两个假设：原假设H0（序列是随机的）和备择假设 也（序列是不随机的），然后根据 给定统计量的分布函数和统计结果返回一个 P value ,将它与先前给定的 进行 比较，从而判断随机性。其中 P value是一个概率值，P value 0,1。若P value，则接

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

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

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

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 0 0密钥字个数：40000现在我们已经得到了 40000 32位的密钥流序列。运行后生成了两个密钥流 文件：zuc.txt和zuc1.txt,分别是以二进制和十六进制表示的。NIST测试要求密 钥流序列是以二进制表示的，所以我们需要的文件是zuc.txt。初始蜜恸；0B00B9090Q90 初始向量；B00Q00BB0OB0OB9O话福字个数X0O的密钥处X二进制己写入ZIW . txt 密南流十六求制已骂入NUCl.tXtPress any

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

21、输入序列长度，如下图：文AW ；%工 查看如 终端5 转到但 箭助出(ktiuqulDfa Iho t d3huqu$ ctl /hnrre /d s huqu/ i l i_2 Z s l s_2 J L dstiuquloca Ihas t 11s2. . 1 $12X00002 .进入测试界面，输入“0；导入文件:3 whuqu 例 I ocu Ihos l 5tL2.1.1$ “a -5 12S0000GE MERA TOR SELECTIONngruent iaI 115 XCR71 BluirBlunrShubK C gj喟 SHVIzuc.txt” ：3 .输入4.2.1中生成的

22、以二进制表示的密钥流序列文件Urrt Prescr ib*d 1 npu I File: zu c . In 14 .输入1”，对15项全部进行测试:S I A 1 S T 1 (： A LTESTSrouiF rcque-ncy02 Block FrequencyIMQi 1W 1 31 t 1 X e SuiTb04 Rujis1叫Longe s t Run o t (Jhe s|06 Rank明Di seretr F-our ifffor mOS bbnper iod i Tenp late Mi t ch i ng。9】Oei Lipping Temph te MaLuhiny*10

23、Ui iversa 1 Sts t ist i ca 111Appiux iiu U htLrvpy12 Random Ex cur i i an*1 15Randum Ek cut 斗Vai ianiLinesr 6叩 Icily14 Seria 1I hETRUCTl ONStn Le r U l f yuu CO NLJC Mitt Lu apply all ol thestat i l ica I tes L s io each sequenee and i f you DU.Liter Qi ice ： 1|5 .输入“0”，参数调整选择默认值：R j r a m e L r A d

24、 j u & l m e n I s1 Blflck Frequency Tes 1 - hlock. Icnpthf M :1282 bbntXer lapp ing Tf npla le Tcsl - b lock 1唯旧巾：9 f SJCX吧 r EppingTcnph te Tcslblock lengthfrh)：94 yYpproxhih ioEnirupy Td - block lenih(in)：1。5 Serial Te 4 1- b lock. knth( nD ：166Linear Chirplex i 1y les t - block length( M 15410Se

25、leer Test (0 ia (onc inuc)；6 入“0，ASCII的0、1序列，也就是以二进制表示的序列:I npm File Fnrna t ：0 ASCil I - A &equ*ne of ASCI O s md 11 s! Biiiia r y - Each by le in dj in f i & cunta in& * b i Ln d f tluiaSfi loct input 皿加: 唱7 试完成：Inpu t Fi le Fcnm t ：0 ASCJ I - A :equejice aT ASCJI 0 s jnd I s1 Buis r y - Each by t

26、e m da to file eon tains g hild o f da taSt leIR)/linearCainplNitj|.o l $(0BJDIR)/dF1:t .o 4.运行“cygin”Dshuqu9d - $5.进入测试包所在目录6.make f makefile 生成assess文件7.运行 assess8.进入测试Dshuqu?d a$ cd /cygdrive/d/cygwi n/home/Dshuqu/sts口等hnqu皑d /cygdrive/d/cygwi n/home/Dshuqu/sts$ ./assess 1QOQQOOGENERA.TOR SELECTI

27、ON_0. Input Fi 12 Q.uadritic Congruent!al I14 Cubi c Congru tnti al16 Modul ar Exiwnenti ationMi call -Schnarr9 -9 - 1 ri口 GprsLi near Congruential Quadrati c Cor gr uent-i si IIBl un-Bl um-ShubG Using SHA-1Enter Choice:8.测试结果及中间过程都写入了各自对应的目录中，经整理后检测结果如 表4-2所小：表4-2随机性检测结果测试项P-value频率测试(Frequency)0.4

28、72934块内频率测试(Block Frequency)(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重叠模版匹配测试(OverlappingTemplate)

29、(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 value值全部大于显著性水平(0.01),而且有5项(块内频率测试、累积和测试、二元矩阵秩

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

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

32、 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.