对一类组合线性同余发生器的不可预测性研究

Unpredictability of a kind of combined linear congruential generator

线性同余发生器是使用很广的一类随机数发生器。为克服这类发生器的缺陷,可组合多个发生器得到组合线性同余发生器。不可预测性是度量序列安全性的一个重要指标。一些应用必须满足不可预测。为了评估某类组合线性同余发生器的不可预测性,该文利用代数法对这类组合线性同余发生器的不可预测性进行了研究,给出了对这类组合线性同余发生器进行预测的数据复杂度与时间复杂度,并以3篇重要文献中的5个组合线性同余发生器为例,给出预测的分析结果与建议。结果显示,这类组合线性同余发生器在一些推荐参数下可以预测,不适合作密码应用。

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.