2009年7月Journal on Communications July 2009 第30卷第7期通信学报V ol.30No.7分组密码算法的自相关检测参数选择范丽敏1,2, 冯登国1, 周永彬1（1. 中国科学院软件研究所信息安全国家重点实验室，北京 100190；2. 中国科学院研究生院，北京 100039）摘要：自相关检测是一种用以检测一个长度为n的二元序列与其左移d位后序列的关联程度的随机性检测算法。
d的选择范围很大,对所有参数逐一进行检测不现实，需要研究检测参数之间的关系。
定义了检测参数之间可能存在的3种关系，以分组长度为m的分组密码随机性检测为对象，综合考虑分组密码和自相关检测的特点，利用统计实验研究了自相关检测参数子集D={1,2,m/4,m/2,3m/4,m,2m}中参数的关系。
研究结果表明，对分组密码进行自相关检测时，检测参数应该首选d=m。
该方法和结果为研究其他类型密码算法的随机性检测参数选择提供了新思路。
关键词：信息安全；分组密码；统计检测；自相关检测；参数选择中图分类号：TP309.7 文献标识码：B 文章编号：1000-436X(2009)07-0086-05Parameter selection of autocorrelation test for block ciphersFAN Li-min1,2, FENG Deng-guo1, ZHOU Yong-bin1(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 100049, China)Abstract: Autocorrelation test was a statistical test to evaluate the correlation between one sequence and the corresponding non-cyclic left-shifted d bits sequence. It was impractical to adopt all the values of d since its range was often very wide.Three relations between parameters of randomness test were defined firstly. Then the relationships among the subclass D={1,2,m/4,m/2,3m/4,m,2m}of autocorrelation test for block cipher were studied by statistical experiments, where m was block length. The experiments show that the prefer choice of parameter d is m when doing autocorrelation test for block cipher. The method is also available for parameter selection of other randomness test for other types of cryptosystem.Key words: information security; block cipher; statistical test; autocorrelation test; parameter selection1引言一个好的密码算法应该能够保证其输出序列的随机性，使得该密码产生的输出序列在统计上难以与真随机序列区别开来。
检测一个序列与真随机序列之间的差距通常采用统计检测方法。
事实上，统计检测已经成为密码算法检测中重要的量化检测手段。
目前，已经存在多种不同的随机性检测项目[1~3]，并且很多检测项目还带有参数。
对检测项目的参数研究并不多见，主要成果集中在正确参数的选择和错误参数收稿日期：2007-08-01；修回日期：2009-05-23基金项目：国家自然科学基金资助项目（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)第7期 范丽敏等：分组密码算法的自相关检测参数选择 ·87·的剔除上[4~6]。
文献[7]从统计学角度给出了参数之间相关性的研究方法，但是该方法不考虑具体密码算法的应用。
本文从另一个角度研究随机性检测项目的参数选择问题，首先定义参数之间可能存在的关系，综合考虑检测项目的基本特点和被测密码的基本结构，研究典型参数子集中各参数的相关性。
在众多的随机性检测项目中，自相关检测是一种十分重要的检测项目。
该项目在文献[8]中首次被提出，在文献[9,10]中进行了详细的描述。
此后，自相关检测被广泛地应用于随机性检测工具中。
其中，“使用自相关的随机性测试”作为实时检测由随机数发生器生成的随机数的方法和设备已被荷兰的L·哈尔斯申请为中国专利。
同时，我国科研与测评机构研制的相关工具也将自相关作为一项基础的检测项目。
自相关检测是用于检测一个长度为n 的二元序列与其左移（逻辑左移）d 位后的序列之间的关联程度。
除非特别说明之外，本文所指序列均为二元序列。
自相关检测中用到一个参数左移的位数d ，其取值通常有一个与序列长度有关的范围。
但是，在实际的检测中，要选择所有的参数进行逐一检测是不现实的。
此外，在实际的检测中还需要综合考虑被检测密码的结构特点。
例如，对分组密码算法的检测而言，对其进行自相关检测时，就应该考虑其按块加密的特点。
本文定义了参数之间可能存在的3种关系，并以分组密码为实例，设计大量的实验，给出了与分组长度m 有关的自相关检测参数子集D ={1,2,m /4,m /2,3m /4,m ,2m }中各参数的关系。
同时根据实验结果和最小冗余原则给出结论：对分组密码进行自相关检测时，应该优先选择d=m 。
文中制定的参数之间的关系、参数选择策略和采用的实验方法也可以应用于其他类型的密码算法以及随机性检测项目的参数相关性研究之中。
2 背景知识2.1 自相关检测自相关检测用来检测一个序列与其左移d 位的序列的关联程度。
一个随机序列应该与其左移任意位的序列都是统计独立的，关联程度应该很低。
用10()n d ii d i A d εε−−+==⊕∑表示待检序列与将其左移d 位的序列之间不同的元素个数，d 称为时延。
根据独立同分布的中心极限定理，可构造统计量为2(())n dA d V −−=(1) V 应该服从标准正态分布，记作~01V N （，）。
使用统计方法来检测一个密码算法输出序列的随机性时，需要进行多次统计检测，并利用通过检测的比例来刻画算法输出随机性的优劣。
检测的阈值通过式(2)计算求得[11]。
S A ⎛±⎜⎜⎝ (2) 其中，S 为样本数量，A =1−a ，a 为显著性水平，K 通常取3[11]。
2.2 分组密码的随机性检测当前，对分组密码的随机性检测通常是检测分组密码算法产生密文流的随机性。
也就是说，检测密码算法产生的密文流能否与真随机序列区分开来,如果能够区分，则认为密码算法输出不随机；否则,则认为密码算法的输出是随机的。
在AES 的评选过程中，NIST(national institute of standard technology)对候选密码算法的两轮评估均采用了随机性检测方法，它选用了6种方式产生密文流[12]。
这种方法将分组密码看成一个伪随机数发生器，却忽略了分组密码按分块加密的这一重要结构性特点。
在实际检测密文流的随机性时，如果在参数选择上考虑分组密码的这种结构特点，不同的参数选择可能会有不同的检测结论。
因此，对分组密码随机性检测的参数选择，不能简单照搬随机数发生器或者流密码的参数选择规则，而必须要考虑具体检测项目的特点和分组密码的结构特性，进行合理的参数设置。
2.3 参数之间的关系和参数子集选择基本原则一个随机性检测项目可能会包含多个参数，每个参数有一个选择范围。
为了研究的方便，首先定义参数之间可能存在的3种关系。
1) 包含关系对于同一个检测项目的2个不同参数A 和B ，对于任何序列，如果该序列能够通过参数A 的检测，那么它一定能通过参数B 的检测，反之不能成立，此时，称A 包含B 。
2) 等价关系对于同一个检测项目的2个不同参数A 和B ，对于任何序列，如果该序列能够通过参数A 的检测，那么它一定能通过参数B 的检测，反之亦然，此时，称A 等价B 。
·88·通信学报第30卷3) 不相关关系对于参数A和B,如果不存在包含和等价关系，则统称其不相关。
根据参数之间的关系，本文同时制定选择有效参数子集的2条基本原则。
①完备性选择出的参数子集应该尽可能可以代表参数选择范围内的所有参数。
即对于任何一个序列，通过参数子集中各参数的检测，就可以判定该序列通过了该项目的检测。
完备性原则需要将不相关的参数尽量多地包含到检测参数子集之中。
②最小冗余去除参数集之中的冗余参数。
无冗余原则需要去除包含关系中的被包含参数，多个等价的参数中只需选择其中的一个。
本文所定义的参数之间的关系和参数选择基本准则不仅适用于自相关检测，同时也适用于其他带有参数的检测项目的参数选择研究中。
3 分组密码自相关检测参数研究分组密码是按分组长度逐块加密的，如果分组密码的随机性好，则密文流应该去除分组块之间可能存在的各种关系[13]。
换句话说，若密码算法的随机化程度好，则无论明文形式如何，密文流从任何方面来看都是随机的。