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.
黄小莉, 石竑松, 张翀斌, 杨永生, 朱克雷. 对一类组合线性同余发生器的不可预测性研究[J]. 清华大学学报(自然科学版), 2016, 56(1): 22-27.
HUANG Xiaoli, SHI Hongsong, ZHANG Chongbin, YANG Yongsheng, ZHU Kelei. Unpredictability of a kind of combined linear congruential generator. Journal of Tsinghua University(Science and Technology), 2016, 56(1): 22-27.
[1] Stallings W. 密码编码学与网络安全——原理与实践(第四版) [M]. 孟庆树, 王丽娜, 傅建明, 等译. 北京: 电子工业出版社, 2007.
[2] Knuth D E. The Art of Computer Programming [M]. 2nd ed. New York:Addison-Wesley Publishing Company, 2002.
[3] 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.
[4] Boyar J. Inferring sequences produced by a linear congruential generator missing low-order bits [J]. Journal of Cryptology, 1989, 1(3):177-184.
[5] 沈华韵, 张鹏, 王侃. 改进线性同余法随机数发生器 [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)
[6] Wichmann B A, Hill I D. An efficient and portable pseudo-random number generator [J]. Applied Statistics, 1982, 31(2):188-190.
[7] L'Ecuyer P. Efficient and portable combined random number generators [J]. Communications of the ACM, 1988, 31(6):742-749, 774.
[8] L'Ecuyer P, Tezuka S. Structural properties for two classes of combined random number generators [J]. Mathematics of Computation, 1991, 57(196):735-746.
[9] 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.
[10] 周燕. 关于线性同余组合发生器的周期性和统计性质 [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)
[11] 张贤达. 矩阵分析与应用 [M]. 北京: 清华大学出版社, 2004.
[12] Blum L, Blum M, Shub M. A simple unpredictable pseudo-random number generator [J]. SIAM J Comput, 1986, 15(2):364-383.