NIST随机性检测方法及应用.doc

NIST随机性检测方法及应用 本科教学工程 大学生创新创业训练研究 1 引言 密码算法是构建安全信息系统的核心要素之一，是保障信息与数据机密性、完整性和真实性的重要技术。密码算法检测评估是密码算法研究的重要组成部分，它为密码算法的设计、分析提供客观的量化指标和技术参数，对密码算法的应用具有重要的指导意义．在密码算法的设计和评测过程中，需要从多个方面对其进行检测和分析。“一次一密(One-Time Pad)”是序列密码产生的思想来源，序列密码的核心是通过固定算法，将一串短的密钥序列扩展为长周期的密钥流序列，且密钥流序列在计算能力内应与随机序列不可区分。因此，分析秘钥流序列的是密码算法安全性研究的重要内容NIST检测方法对密码算法进行评测可以为理论分析提供大量参考数据，从而减少理论分析者的工作量，同时可以暴露出用现有的分析方法无法发现的安全漏洞。 2NIST检测方法法，这里以测试统计量服从分布为例来说明。 以随机序列的某种统计值V符合自由度为n的卡方分布为例： 原假设(零假设) ：序列是随机的，待测序列的统计值V服从 分布； 备择假设 ：序列不是随机的，待测序列的统计值V不服从分布． 通过判断一个待测序列的统计值V是否服从分布来确定是否接受原假设，从而判断该序列是否通过了该项随机性检测． 在随机性检测中判断是否接受原假设通常采用P-Value方法[]．P-Value是一个序列比真随机序列的随机性要好的概率．利用统计值矿求出P-Value，并将P-Value与显著性水平 比较．如果P-Value，则接受原假设，判断该待测序列通过了该项随机性检测． 作出分布的概率密度曲线，如图2-1所示，先求出统计量，然后计算从到无穷的积分，将积分结果(即)与进行比较，进而确定拒绝还是接受。本文中讨论的随机性测试即是通过选取的测试统计量来计算，将作为接受原假设的强度，其含义是：真随机数的随机性比待测序列差的概率。如果其值为1，则是完全真随机的，如果值为0，则是完全非随机的。对于显著性水平，如果，那么原假设被接受，序列是随机的；反之被拒绝，序列是非随机的。参数也即是表2-1中犯第I类错误的概率，一般的，的取值范围是。 图1 分布的概率密度曲线及值 美国国家标准与技术研究院（National Institute of Standards and Technology，NIST）直属美国商务部，从事物理、生物和工程方面的基础和应用研究，以及测量技术和测试方法方面的研究，提供标准、标准参考数据及有关服务，在国际上享有很高的声誉。Special Publication800-22测试包[16]（简称NIST随机性测试）。 NIST测试程序是一个统计包，包括 16 种测试手段。这些测试手段可测试由用作保密随机或者伪随机数发生器的硬件和软件产生的任意长的 2 进制序列的随机性。这些测试手段主要致力于判定可能存在于序列中的多种多样的非随机性。其中一些测试又可以分解成多种子测验。这 16 种测试手段是： 频率检验， 该检验主要是看 0 和 1 在整个序列中所占的比例。检验的目的是确定序列中的 1 和0 数是否与真正的随机序列中的1和 0数近似相同。检验评定1码占1/2，也就是说，在整个序列中0和 1的数目是一样的。其余别的检验手段都是在该检验成立的基础上进行的，并且没有任何证据表明被测序列是不随机的。 块内频数检验， 此检验主要是看M位的子块中“1”码的比例。该检验的目的是判定M位的子块内“1”码的频率是否像随机假设下所预期的那样，近似于M/2。当M=1时，该检测相当于检测1位，即频数（一位）检验。 游程检验， 此检验主要是看游程的总数，游程指的是一个没有间断的相同数序列，即游程或者是“1111…”或者是“0000…”。一个长度为k 的游程包含k 个相同的位。游程检测的目的是判定不同长度的“1”游程的数目以及“0”游程的数目是否跟理想的随机序列的期望值相一致。具体的讲，就是该检验手段判定在这样的“0”“1”子块之间的振荡是否太快或太慢。 块内最长游程检验， 该检验主要是看长度为M-bits的子块中的最长“1”游程。这项检验的目的是判定待检验序列的最长“1”游程的长度是否同随机序列的相同。注意：最长“1”游程长度上的一个不规则变化意味着相应的“0”游程长度上也有一个不规则变化，因此，仅仅对“1”游程进行检验室足够的。 二元矩阵秩检验， 该检验主要是看整个序列的分离子矩阵的秩。目的是核对源序列中固定长度子链间的线性依赖关系。 6. 离散傅里叶变换检验， 本检验主要是看对序列进行分步傅里叶变换后的峰值高度。目的是探测待检验信号的周期性，以此揭示其与相应的随机信号之间的偏差程度。做法是观察超过 95%阈值的峰值数目与低