|
|
- 2016
对一类组合线性同余发生器的不可预测性研究
|
Abstract:
线性同余发生器是使用很广的一类随机数发生器。为克服这类发生器的缺陷, 可组合多个发生器得到组合线性同余发生器。不可预测性是度量序列安全性的一个重要指标。一些应用必须满足不可预测。为了评估某类组合线性同余发生器的不可预测性, 该文利用代数法对这类组合线性同余发生器的不可预测性进行了研究, 给出了对这类组合线性同余发生器进行预测的数据复杂度与时间复杂度, 并以3篇重要文献中的5个组合线性同余发生器为例, 给出预测的分析结果与建议。结果显示, 这类组合线性同余发生器在一些推荐参数下可以预测, 不适合作密码应用。
Abstract：The linear congruential generator (LCG) is a kind of widely used random number generator. Several generators can be combined as combined linear congruential generators (CLCG) to compensate LCG's shortages. Unpredictability is an important index of measuring the security of sequences, which is indispensable in some applications. Unpredictability of some kind of CLCG was studied using the algebraic method to evaluate the unpredictability of the CLCG, with data complexity and time complexity of predicting the CLCG being given. Five CLCGs from three important references were analyzed as examples, which presents the analytic results of predicting the five CLCGs. The results show that the CLCGs are predictable under some recommended parameters, while these CLCGs are unsuitable for cryptographic applications.
| [1] | Boyar J. Inferring sequences produced by a linear congruential generator missing low-order bits [J]. Journal of Cryptology, 1989, 1(3):177-184. |
| [2] | Blum L, Blum M, Shub M. A simple unpredictable pseudo-random number generator [J]. SIAM J Comput, 1986, 15(2):364-383. |
| [3] | Stallings W. 密码编码学与网络安全——原理与实践(第四版) [M]. 孟庆树, 王丽娜, 傅建明, 等译. 北京: 电子工业出版社, 2007. |
| [4] | Knuth D E. The Art of Computer Programming [M]. 2nd ed. New York:Addison-Wesley Publishing Company, 2002. |
| [5] | Plumstead J B. Inferring a sequence generated by a linear congruence [C]//Proc 23rd IEEE Symp on Foundation of Computer Science. Piscataway, NJ:IEEE Computer Society Press, 1982:153-159. |
| [6] | 沈华韵, 张鹏, 王侃. 改进线性同余法随机数发生器 [J]. 清华大学学报:自然科学版, 2009, 49(2):191-193.SHEN Huayun, ZHANG Peng, WANG Kan. Improved linear congruential random number generators [J]. J Tsinghua Univ:Sci & Technol, 2009, 49(2):191-193.(in Chinese) |
| [7] | Wichmann B A, Hill I D. An efficient and portable pseudo-random number generator [J]. Applied Statistics, 1982, 31(2):188-190. |
| [8] | L'Ecuyer P. Efficient and portable combined random number generators [J]. Communications of the ACM, 1988, 31(6):742-749, 774. |
| [9] | 周燕. 关于线性同余组合发生器的周期性和统计性质 [J]. 重庆大学学报:自然科学版, 2000, 23(6):67-70. ZHOU Yan. On the research of the periodicity and statistical characteristics by linear congruence and combined generator [J]. Journal of Chongqing University:Natural Science Edition, 2000, 23(6):67-70.(in Chinese) |
| [10] | L'Ecuyer P, Tezuka S. Structural properties for two classes of combined random number generators [J]. Mathematics of Computation, 1991, 57(196):735-746. |
| [11] | L'Ecuyer P, Andres T H. A random number generator based on the combination of four LCGs [J]. Mathematics and Computers in Simulation, 1997, 44(1):99-107. |
| [12] | 张贤达. 矩阵分析与应用 [M]. 北京: 清华大学出版社, 2004. |
