Unpredictability of a kind of combined linear congruential generator

doi:10.16511/j.cnki.qhdxxb.2016.23.003

Download: PDF(965 KB)
Export: BibTeX | EndNote | Reference Manager | ProCite | RefWorks

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.

Keywords security secrecy random number combined linear congruential generator forward unpredictability backward unpredictability

ZTFLH:

TP309.7

Issue Date: 15 January 2016

	Service

	E-mail this article
	E-mail Alert
	RSS
	Articles by authors

	HUANG Xiaoli
	SHI Hongsong
	ZHANG Chongbin
	YANG Yongsheng
	ZHU Kelei

Cite this article:

HUANG Xiaoli,SHI Hongsong,ZHANG Chongbin, et al. Unpredictability of a kind of combined linear congruential generator[J]. Journal of Tsinghua University(Science and Technology), 2016, 56(1): 22-27.

URL:

http://jst.tsinghuajournals.com/EN/10.16511/j.cnki.qhdxxb.2016.23.003 OR http://jst.tsinghuajournals.com/EN/Y2016/V56/I1/22

[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.

[1]	LONG Yu, WANG Xin, XU Xian, HONG Xuan. Highly-descriptive chain of trust in trusted computing[J]. Journal of Tsinghua University(Science and Technology), 2018, 58(4): 387-394.
[2]	LI Taoshen, LIU Qing, HUANG Ruwei. Multi-user fully homomorphic encryption scheme based on proxy re-encryption for cloud computing[J]. Journal of Tsinghua University(Science and Technology), 2018, 58(2): 143-149.
[3]	SHAN Chun, HU Kangwen, XUE Jingfeng, HU Changzhen, ZHAO Xiaolin. Improved pairing-free constant round certificateless authenticated group key agreement protocol[J]. Journal of Tsinghua University(Science and Technology), 2017, 57(6): 580-585.