随机性检测参数选择研究.doc

第1期范丽敏等：随机性检测参数选择研究5随机性检测参数选择研究范丽敏1, 2，冯登国1，陈华1（1. 中国科学院 软件研究所信息安全国家重点实验室，北京 100190；2.中国科学院 研究生院，北京 100039）摘 要：从统计学角度对同一个随机性检测项目中2个独立的参数所应满足的条件进行了研究，在此基础上设计了一个假设检验方法，用于检测2个参数是否满足独立的关系。以扑克检测为实例，对其参数集中的参数进行了实验研究，并对结果进行了分析。提出的方法是一个通用的方法，可以直接应用于其他带参数的检测项目的参数关系研究中，这为随机性检测中参数选择提供了一种可操作的手段。关键词：信息安全；随机性检测；假设检验；参数选择；P-Value；扑克检测中图分类号：TP309.7 文献标识码：A 文章编号：1000-436X(2009)01-0001-06On the parameter selection of randomness testFAN Li-min1,2, FENG Deng-guo1, CHEN Hua1(1. State Key Laboratory of Information Security, Institute of Software ,Chinese Academy of Sciences, Beijing 100190, China;2. Graduate University of Chinese Academy of Sciences, Beijing 100039, China)Abstract: The conditions that two different parameters in a same randomness test should satisfy if they are independent with each other was studied based on statistical theory. And a hypothesis method was proposed to test whether two parameters were independent or not. A series of experiments were designed to study the relations among the parameters gather of poker test，which was selected as a research instance by means of this method, and the experiment results were analyzed in details. The method is general and it can be used to deal with other randomness test, such as entropy test and binary derivation test. The work is helpful to select reasonable and scientific parameters in practical randomness test.Key words: information security; randomness test; hypothesis test; parameter selection; P-Value; poker test1 引言收稿日期：2008-06-21；修回日期：2008-12-20基金项目：国家自然科学基金资助项目（60503014, 60603013）；国家高技术研究发展计划（“863”计划）基金资助项目（2007AA01Z470, 2008AA01Z417）；北京市自然科学基金资助项目（4072026）Foundation Items: The National Natural Science Foundation of China (60503014, 60603013); The National High Technology Research and Development Program of China (863 Program) (2007AA01Z470, 2008AA01Z417); The Natural Science Foundation of Beijing (4072026)“随机”的概念在密码领域中有着广泛的应用，例如，一个安全的密码算法的输出需要是随机的，密码算法及密码协议中用到的密钥和一些参数也需要是随机的，随机性检测在密码应用及其相关领域起到重要的作用。理想的随机序列可以看成是投掷硬币的结果，根据抛出硬币是正面或者反面标记为“0”或“1”，对于每一次投掷结果，“0”或“1”出现的概率均为1/2，投掷结果之间相互独立，并且前面的投掷不会影响到后面的结果。显然，在实际应用中以这种方式产生随机数是不现实的，实际应用的随机数通常都是通过某些数学公式的计算而产生的伪随机数1。人们研究了多种随机序列应满足的性质，并以此为标准对产生序列的随机程度进行度量。目前已经有了众多的随机性检测项目和方法用于检测密码算法和序列的统计特性24。对于一个随机性检测项目，在实际进行检测时需要设置一些参数，参数通常分为两类，一类称为外部参数，例如测试序列的长度；另一类为内部参数，主要是指检测项目本身所涉及的参数，例如扑克检测2中子序列的长度。本文所研究的是内部参数的关系和内部参数的选择。如无特殊说明，本文后续部分所述参数均指内部参数。对于带参数的检测项目，其所有可能的参数组成一个集合，即参数有一个范围。在实际应用中最理想的情况是对该集合中的所有参数进行检测，但是通常这个集合很大，对所有参数一一进行检测不现实。并且，各参数之间可能存在依赖关系，对所有的参数进行检测也不必要。所以，对参数之间可能存在的关系进行研究，选择出合理的具有代表性的参数子集，可以提高随机性检测的实用性和有效性。目前对参数选择的研究并不多见，尽管有一些针对具体检测项目的参数选择的研究或者参数的修正57，但是，并不存在一个通用的研究参数之间关系和参数选择的方法。当前大多数参数选择通常都是根据检测者的经验和个人偏好来进行。本文从统计学角度出发，研究了2个无关的检测参数所应该满足的条件，并以此为基础设计了一个用于衡量参数关系的假设检验算法。通过该算法，可以对各参数之间存在依赖关系进行量化。本文的研究为选择最小合理参数集，避免冗余参数提供了一个有益的方法和思路。2 背景知识2.1 假设检验假设检验的基本思想是，首先提出关于总体性质的假设，称为原假设，然后在原假设的条件下导出结论，若结论发生的概率很大，则认为原假设成立，反之若概率非常小，则否定原假设。该思想源于实践中被广泛采用的一条原则，即小概率事件在一次观察中是不会出现的。小概率事件发生的概率称之为显著性水平，用来表示，它表示了假设检验的严格程度。越小，则否定原假设的说服力越强。通常情况下，取0.01、0.05或0.1。在随机性检测中，通常采用的是假设检验方法。首先假定待测的序列是随机的，按照某种统计方法，其统计值应该符合某种特定的分布。根据统计值符合特定分布的概率来判断待测的序列是否随机。2.2 扑克检测扑克检测是一种常用的重要的随机性检测方法，最早在文献2中被提出，扑克检测也是一些随机性检测软件包中基本的检测项目，例如CryptX8中的“SubBlock Test”和DIAHARD9中的“Bit Stream Test”在本质上都是扑克检测。长度为的二元子序列有2m种情况。扑克检测是用于检测在一个待测的序列中，这2m种子序列出现的次数是否与随机序列近似。将长度为n bit的待检测序列划分成个非重叠的子序列，统计每种类型的子序列个数，构造统计值，该统计值应该服从自由度为的卡方分布。记作。判断一个序列是否通过了扑克检测的通常方法是根据统计值V计算出P-Value。简略地说，P-Value是该待测序列比真随机序列随机性好的概率10。将P-Value与显著性水平进行比较，如果P-Value小于，则认为该序列未能通过扑克检测。3 参数之间的关系本文从统计的角度来研究同一个检测项目中不同参数之间的关系。对于同一个序列，判断其是否通过某参数的检测项目通常是比较计算得到的P-Value与显著性水平的大小。如果2个不同的参数对相同的序列检测结果是相互独立的，即这2个参数的检测结果互不影响，那么可以将这2个检测参数看作是独立的检测参数，这是本文研究的出发点和基础。随机性检测T的2个不同参数和的检测分别记作T()和T()。对于随机的序列，T()检测所得的P-Value分布记为X，其概率密度为。T()检测所得的P-Value分布记为Y，其概率密度为。下面研究当与独立时，Z=XY的概率分布。对于随机的序列，X应该是均匀分布于0，1之间的实数，因此X的概率密度为(1)同理，W=Y的概率密度为(2)在此定义Z=XY=X+W(3)若与独立，则二者的P-Value分布是独立的，即X与Y独立，又因为W与Y是线性关系，因此X与W也独立。对于独立的2个随机变量Z=X+W的概率密度为11(4)代入式(1)、式(2)可知(5)以上的求解过程表明，假设与独立，那么对随机序列进行T()和T()的检测得到的P-Value之差应该服从概率密度为f(z)的分布，其分布函数记为F(Z)。4 一个用于检测参数之间关系的假设检验算法第3节得出了独立的2个检测参数的P-Value之差应该服从的分布。基于此，提出了一个假设检验算法，用于检测任何2个不同参数是否满足这种独立关系，构造原假设如下。H0：2个参数检测的P-Value之差的总体符合分布函数为F(Z)的分布。相应地，备择假设如下。H：2个参数检测的P-Value之差的总体不符合分布函数为F(Z)的分布。P-Value是0，1之间的实数，因此2个P-Value之差是1，1之间的实数。将1，1分为k个区间，第个区间为(6)P-Value的差值落入第个区间的概率记作(7)在一次抽样检测中，假设样本个数为，落入第个区间中的个数为，构造统计值如果原假设成立的话，RiRPi的差距应该非常小，根据皮尔逊卡方检验，该统计值应该服从自由度为k1的卡方分布，即V 2(k1)。根据显著性水平计算拒绝阈值。如果统计值V大于阈值，则拒绝原假设，接受备择假设，认为这2个参数之间不满足独立关系。算法1是一次抽样判断参数与是否独立的算法。一次抽样中样本个数为R条，其主要步骤如下。算法1 Single_Sample_Test(，)1) 产生R条随机的二元序列，每条序列的长度为L bit。2) 对每条序列进行如下操作： 利用T()进行检测，检测结果记作P1； 利用T()进行检测，检测结果记作P2； 计算P= P1P2； 如果P1+2/k则R1+； 如果1+2(i1)/kP1+2i/k 则Ri+。3) 计算。4) 如果 则返回true，否则返回false。本文采用的是假设检验，其本质是一种概率检测，因此接受或者拒绝原假设存在一定的误差。另外，通过随机数算法产生的随机序列与真随机序列有一定的差距，仅通过一次检测就对参数之间的关系下结论是有偏差的，所以本文通过统计多次抽样的方法来提高检测的准确度。另外，通过率也可作为衡量2个参数之间相关性大小的一种度量。算法2是S次抽样进行参数无关性检测的算法，其主要步骤如下。算法2 Independence_Statis_Test(，)1) 设置 passnum=0；2) For i=1 to S do调用算法1，如果Single_Sample_Test (，)=true 则passnum+；3) 计算并返回pass_proportion= 100 passnum/S。5 实验结果本节以扑克检测为研究实例，利用第4节给出的算法，研究扑克检测参数之间的关系。表1一次抽样中参数1与其他参数的无关性检测结果子区间期望条数实验观测值(1，2)(1，3)(1，4)(1，5)(1，6)(1，7)(1，8)(1，9)(1，10)(1，11)(1，12)(1，13)110053596573749583791007483113212571105103111120128120125117118134117317512215315916119417417015516518817419042251642142022192072112032442162242322155275234268283270305260297276255253277250632541436233733934233631135431831632138373754494103843733513553723743793944013238425510497473433436448423419425434433406947559149248649248448750949249547146848310475525533526484469499455490498492508446114254164234254104614194303964174034204731237537434140340635037337237937735932738913325275313306349323295342312341339339307142752572802512632662972722832862923002761522521419922523220721320223220224622323416175152168171154205178200161171182177157171251061021231391271421451261291149813918100738178927990941031091018599统计值V196.565.6142.2422.1132.7414.8421.5416.279.8218.6225.3837.25扑克检测用到的参数m与序列长度L需要满足一个关系2，那么当序列长度L=1 000 000bit时，m的范围是的整数。即m的合理参数集合为1，2，3，4，5，6，7，8，9，10，11，12，13。本文采用BBS12随机数发生器产生模拟真随机的序列，已有研究结果表明，BBS具有较好的随机性。本文采用的参数为R=5 000，S=100， =0.05。如果有5 000条序列，将1，1均匀分成20个区间，并将第1与第2区间，第19与第20个区间进行合并，共形成18个区间，根据式(5)和式(7)，假设2个参数(，)独立，那么落入各个区间的期望条数见表1。抽样一次，利用BBS算法产生5 000条序列，利用算法1，对参数1与其他参数进行无关性检测见表1。从表1可以得出，(1，2)，(1，3)，(1，4)，(1，6)，(1，13)的检测统计值V均大于阈值(通过查表知=27.587），落入了拒绝域内，即(1，2)，(1，3)，(1，4)，(1，6)，(1，13)都未能通过独立性检测，与此对应，(1，5)，(1，7)，(1，8)，(1，9)，(1，10)，(1，11)，(1，12)通过了参数独立性检测。为了进一步表现出通过与未通过独立性检测的差异，分别选取两种情况的代表(1，10)和(1，2)进行对比，如图1所示。图1 参数 (1，10)和参数(1，2)与期望值拟合对比从图1可以看出，(1，10) 2个参数的P-Value之差的分布与独立参数的P-Value之差能够更好地吻合，差异更小，也就是参数1和10之间更符合独立的关系，而(1，2) 2个参数的P-Value之差的分布与独立参数的P-Value之差有较大的差异。为了提高检测的准确性，本文采用多次抽样的方式来减小误差。利用算法2进行统计检测，将抽样100次的实验结果汇总见表2。表2 扑克检测各参数的无关性统计检测结果参数12345678910111213100005771896693929697782000652779889859259100301583082679093988787407415921310094100659750639810085399710010060921005298855199701007898969193809710099741009098929294100949188110869312094130表2记录了在100次检测中，任意2个参数通过独立性假设检验(算法1返回为true)的次数。从表2的数值中可以看到，通过次数的数值由0到100不等。由第4节的算法1和算法2可知，该数值越大，说明2个参数之间符合独立参数的可能性越大，相反，数值越小，说明二者之间的相关性越强。从另外一个角度来说，该数值也从量上刻画了2个参数之间的独立程度。因此，这样的量化关系可以为实际使用中选择合适参数提供指导。例如，根据表2，在进行扑克检测的参数选择时，假设检测者无法确定是选择参数2还是选择参数4。通过这个量化的表格可知，参数2和参数4与其他参数关系如表2中的 和 所示。与参数2具有较强相关性的参数集合为1，3，4，6，而与参数4具有较强相关性的参数集合为1，2，3，6，8，比较而言，参数4更具有代表性，因此优先选择参数4。6 结束语本文从统计学角度出发，对随机性检测的参数选择问题进行了研究。给出了一个通用的假设检验方法，用于检测任意2个参数是否满足独立性的关系。同时，该方法的计算结果也量化反映出了各参数之间依赖关系的大小。以扑克检测为研究实例，对其合理参数集中两两参数进行了实验研究，并对研究结果进行了分析。本文提出的方法是一个通用的方法，可以直接应用于其他带参数的检测项目的参数关系研究中，它为随机性检测中的参数选择提供了一种可操作的手段。参考文献：1NEUMANN J. Various techniques used in connection with random digitsJ. National Bureau of Standards Applied Mathematics, 1951, (12): 36-38.2KNUYH D E. The Art of Computer Programming, Volume 2: Seminumerical AlgorithmsM. 3rd Ed, New Jersey : Addison- Wesley, 1981 .59-73.3RUKHIN A, SOTO J, NECHVATAL J, et al. A Statistical Test Suite for Random and Pseudorandom Number Generators for Cryptographic ApplicationsR. Technical Report, SP 800-22, 2001.4FILIOL E. A new statistical testing for symmetric ciphers and hash functionsA. Information and Communications Security: 4th International ConferenceC. Berlin : Springer, 2002. 342-353. 5TSANG W W, HUI L C K, CHOW K P. Tuning the collision test for powerA. Proceedings of the 27th Australasian conference on Computer Science - Volume 26 DunedinC. New Zealand: Australian Computer Society, 2004. 23-30. 6HAMANO K, KANEKO T. Correction of overlapping template matching test included in nist randomness test suiteJ. IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, 2007,90(19): 1788-1792.7PARESCHI F, ROVATTI R, SETTI G. Second-level NIST randomness tests for improving test