Please wait a minute...
 首页  期刊介绍 期刊订阅 联系我们 横山亮次奖 百年刊庆
最新录用  |  预出版  |  当期目录  |  过刊浏览  |  阅读排行  |  下载排行  |  引用排行  |  横山亮次奖  |  百年刊庆
清华大学学报(自然科学版)  2016, Vol. 56 Issue (1): 22-27    DOI: 10.16511/j.cnki.qhdxxb.2016.23.003
  信息安全 本期目录 | 过刊浏览 | 高级检索 |
黄小莉, 石竑松, 张翀斌, 杨永生, 朱克雷
中国信息安全测评中心, 北京 100085
Unpredictability of a kind of combined linear congruential generator
HUANG Xiaoli, SHI Hongsong, ZHANG Chongbin, YANG Yongsheng, ZHU Kelei
China Information Technology Security Evaluation Center, Beijing 100085, China
全文: PDF(965 KB)  
输出: BibTeX | EndNote (RIS)      
摘要 线性同余发生器是使用很广的一类随机数发生器。为克服这类发生器的缺陷, 可组合多个发生器得到组合线性同余发生器。不可预测性是度量序列安全性的一个重要指标。一些应用必须满足不可预测。为了评估某类组合线性同余发生器的不可预测性, 该文利用代数法对这类组合线性同余发生器的不可预测性进行了研究, 给出了对这类组合线性同余发生器进行预测的数据复杂度与时间复杂度, 并以3篇重要文献中的5个组合线性同余发生器为例, 给出预测的分析结果与建议。结果显示, 这类组合线性同余发生器在一些推荐参数下可以预测, 不适合作密码应用。
E-mail Alert
关键词 安全保密随机数组合线性同余发生器前向不可预测性后向不可预测性    
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.
Key wordssecurity secrecy    random number    combined linear congruential generator    forward unpredictability    backward unpredictability
收稿日期: 2014-10-28      出版日期: 2016-01-29
ZTFLH:  TP309.7  
黄小莉, 石竑松, 张翀斌, 杨永生, 朱克雷. 对一类组合线性同余发生器的不可预测性研究[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 例I-1中x y 对应的值
  表2 例I-2 中x y 对应的值
  表3 例I-2 中x y 对应的值
  表4 例II-1 中xy 对应的值
  表5 例II-2中x y 对应的值
[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.
No related articles found!
Full text



版权所有 © 《清华大学学报(自然科学版)》编辑部
本系统由北京玛格泰克科技发展有限公司设计开发 技术支持