随机性测试研究读书报告.pdf

随机性测试研究读书报告——彭斌一、随机性测试现状随机数在密码学中的应用日益广泛很多密码算法和协议中都要用到一些随机数，如密钥、初始向量等对一个密码算法来说，其输出序列的随机性是其安全性的很重要的一个方面因此，随机性测试技术在密码学中占有很重要的作用二、随机性测试的基础测试序列的随机性， 实质上是检验其是否是真随机的或与真随机的差距，假设检验是随机性测试技术的基本理论在检验时，提出一个待检验的假设，称为原假设或零假设，记作H0；还有个与原假设相反的称备择假设，记作 H1 原假设 H0：序列是随机的；备择假设H1 ：序列是非随机的对每个检验来说，其检验结果是否接受原假设也就意味着待检数据是否是随机的三、随机性测试目前，已公开的随机性测试方法不下百种这些测试方法为测试序列的不同特性而设计， 主要是基于序列特性的不同侧重点，它们中多数使用的原理没有显著差别， 而且有的方法往往还蕴涵于另外的方法之中因此，在选择随机性测试方法时既要考虑到能够测试序列随机特性的各个方面，又要兼顾测试的效率，根据这种思想，并参考相关文献，最终确定 16 种测试方法1、 测试内容16 种随机性测试分别为频数测试、块内频数测试、游程测试、块内最长连续“ 1”测试、矩阵秩的测试、离散傅里叶变换测试、非重叠模板匹配测试、重叠模板匹配测试、通用统计测试、压缩测试、线性复杂度测试、连续性测试、近似熵测试、部分和测试、随机游走测试和随机游走变量测试等。

1)频数测试：目的是确定二进制序列中，“0”和“ 1”数目是否如真随机序列那样近似相等如果是，则序列是随机的2)块内频数测试：目的是确定在待测序列中， 所有非重叠的 M - bit 块内的“0”和“1”的数目是否表现为随机分布如果是，则序列是随机的3)游程测试：目的是确定待测序列中，各种特定长度的“0”和“1”的游程数目是否如真随机序列期望的那样如果是，则序列是随机的4)块内最长连续“ 1”测试：目的是确定待测序列中，最长连“1”串的长度是否与真随机序列中最长连“1”串的长度近似一致如果是，则序列是随机的5)矩阵秩的测试：目的是检测待测序列中，固定长度子序列的线性相关性如果线性相关性较小，则序列是随机的6)离散傅里叶变换测试：目的是通过检测待测序列的周期性质，并与真随机序列周期性质相比较， 通过它们之间的偏离程度来确定待测序列随机性如果偏离程度较小，序列是随机的7)非重叠模板匹配测试：目的是检测待测序列中，子序列是否与太多的非周期模板相匹配太多就意味着待测序列是非随机的8)重叠模板匹配测试： 目的是统计待测序列中， 特定长度的连续 “1”的数目，是否与真随机序列的情况偏离太大太大是非随机的。

9)通用统计测试：目的是检测待测序列是否能在信息不丢失的情况下被明显压缩一个不可被明显压缩的序列是随机的10)压缩测试：目的是确定待测序列能被压缩的程度，如果能被显著压缩，说明不是随机序列11)线性复杂度测试：目的是确定待测序列是否足够复杂，如果是，则序列是随机的12) 连续性测试：目的是确定待测序列所有可能的m- bit 组合子串出现的次数是否与真随机序列中的情况近似相同，如果是，则序列是随机的13)近似熵测试：目的是通过比较m- bit 串与(m- 1) - bit串在待测序列中出现的频度， 再与正态分布的序列中的情况相对比，从而确定随机性14)部分和测试：目的确定待测序列中的部分和是否太大或太小太大或太小都是非随机的15)随机游走测试：目的是确定在一个随机游程中，某个特定状态出现的次数是否远远超过真随机序列中的情况如果是，则序列是非随机的16)随机游走变量测试：目的是检测待测序列中，某一特定状态在一个游机游程中出现次数与真随机序列的偏离程度如果偏离程度较大，则序列是非随机的2、密码算法的随机性测试如果要测试某个密码算法的性能好坏，一般的方法是： 选定由加密算法产生的若干个序列进行随机性测试，产生对应的 p 值集合，根据显著性水平 α 来判断p 值是否通过测试，并通过考察p 值通过率及其分布特性检验加密算法的好坏。

序列通过测试的比例如果选取显著性水平为0.01，那么将允许在 100 个序列中有一个序列不通过， 也就是说通过率不得低于1-0.01=0.99那么就可以这样处理数据：测试 1 000 个序列，有 996 个通过，显著性水平为 0.01，此时通过率 =996/1 000=0.996，显然0.996>(1-0.01)=0.99，就可以认为通过了随机性测试但事实上，对一个密码算法来说，要其产生的序列以这样的比例通过每一个检验还是比较困难，也是不全面的3、随机测试的工程实现class RandTest {private: byte *m_pdata; //待测数据 int m_dataLen; //待测数据长度 tchar *m_errorMessage; // 错误消息 tchar *m_testName; //测试名称 public: //各种测试方法 RandTest( ); RandTest(byte *a, int dataLen); ~RandTest( ); bool FrequencyTest( ); bool BlockFrequencyTest( ); bool Runs( ); bool LongestRunOfOnes( ); bool Rank( ); bool DiscreteFourierTransform( ); bool NonOverlappingTemplateMatchings( ); bool OverlappingTemplateMatchings( ); bool Universal( ); bool LempelZivCompression( ); bool CommonLempelZivCompression( ); bool LinearComplexity( ); bool Serial( ); bool ApproximateEntropy( ); bool CumulativeSums( ); bool RandomExcursions( ); bool RandomExcursionsVariant( ); tchar *GetMessageFromError( );}; 一个返回结果的结构体如下： struct testRandRes {dword NameID:8; // 用8 个bit 位标识NameID dword TestID:24; //用24 个bit 位标识 TestID bool Res; //返回测试结果 “1”或“0” double pValue; //返回pValue 值 double confidence; // 返回可信度 }; 四、结束语16 种常用的随机性测试方法，从不同角度考察二进制序列的随机特性，涵盖了序列随机性的各个方面， 具有重要的理论和实际意义。

通过对随机性测试的阅读， 让我了解到随机性测试不仅仅在密码学中占据了重要地位， 在当今社会也将占据了越来越重要的地位，随机性测试将会得到更加广泛的应用 我们还需要对随机性测试进行更深层次的研究，将它广泛应用到密码学，应用到各个领域中。