一种组合式伪随机数发生器的构造
|
摘要
伪随机数发生器(Pseudorandom Number Generator,PRNG)是密码学应用系统的一个重要组成部分.本文利用线性同余发生器(Linear Congruential Generator,LCG)、流密码算法RC4和密码学Hash函数,构造了一种基于软件实现的组合式伪随机数发生器.该伪随机数发生器可以快速生成伪随机数列并且从理论上证明了产生的数列具备不可预测性.同时,采用美国国家标准和技术研究院(National Institute of Standard Technology,NIST)发行的随机性测试包对该新构造的伪随机数发生器所产生的序列进行统计测试.实验结果显示,该新构造的伪随机数发生器产生的序列能够很好地通过各项测试,可以应用于信息安全领域.
Pseudo-random number generator( PRNG) is an important part of cryptography application system. This paper constructs a combined pseudo-random number generator based on software using linear congruential generator( LCG),stream cipher algorithm RC4 and cryptographic Hash function. This pseudo-random number generator can quickly generate pseudo-random numbers and theoretically proves that the resulting sequence is unpredictable. At the same time,statistical tests were performed on the sequences generated by the newly constructed pseudo-random number generator using a randomness test package issued by the National Institute of Standards and Technology. Experimental results showthat the newly constructed pseudo-random number generator can pass all tests well and can be applied to the information security field.
Pseudo-random number generator( PRNG) is an important part of cryptography application system. This paper constructs a combined pseudo-random number generator based on software using linear congruential generator( LCG),stream cipher algorithm RC4 and cryptographic Hash function. This pseudo-random number generator can quickly generate pseudo-random numbers and theoretically proves that the resulting sequence is unpredictable. At the same time,statistical tests were performed on the sequences generated by the newly constructed pseudo-random number generator using a randomness test package issued by the National Institute of Standards and Technology. Experimental results showthat the newly constructed pseudo-random number generator can pass all tests well and can be applied to the information security field.
引文
[1]Stipcevic M,Cetin Kaya Koc.True random number generators[M].Open Problems in Mathematics and Computational Science,Springer International Publishing,2014:275-315.
[2]Goldwasser S,Micali S.Probabilistic encryption[J].Journal of Computer&System Sciences(JCSS),1984,28(2):270-299.
[3]Shen Bing,Dong Xin-feng,Xu Bing-jie,et al.Random number generators and their applications in cryptography(1st edition)[M].Beijing:National Defense Industry Press,2016.
[4]Lih-Yuandeng,Olusegungeorge E.Generation of uniform variates from several nearly uniformly distributed variables[J].Communications in Statistics-Simulation and Computation,1990,19(1):145-154.
[5]Huang Xiao-li,Shi Hong-song,Zhang Chong-bin,et al.Unpredictability of a kind of combined linear congruential generator[J].Journal of Tsinghua University,2016,56(1):22-27.
[6]Knuth D E.The art of computer programming,volume 3:(2nd ed.)sorting and searching[M].Addison Wesley Longman Publishing Co.Inc.1998.
[7]Robshaw M.Stream ciphers[R].RSA Laboratories Technical Report TR-701,July 1995.
[8]Chefranov A G,Mazurova T A.Pseudo-random number generator RC4 period improvement[C].IEEE International Conference on Automation(ICRA),Quality and Testing,Robotics,2006:38-41.
[9]Shen H,Peng Z,Kan W.Improved linear congruential random number generators[J].Journal of Tsinghua University,2009,49(2):191-193.
[10]Ronald L Rivest,Jacob C N Schuldt.Spritz-a spongy RC4-like stream cipher and hash function[Z].http://people.csail.mit.edu/rivest/pubs/RS14.pdf,2014:1-30.
[11]Gupta S S,Maitra S,Paul G,et al.Nonrandom sequences from nonrandom permutations-analysis of RC4 stream cipher[J].Journal of Cryptology,2014,27(1):67-108.
[12]Jindal P,Singh B.A survey on RC4 stream cipher[J].Computer Netw ork and Information Security,2015,(7):37-45.
[13]Popov A.Prohibiting RC4 cipher suites[R].Internet Engineering Task Force(IETF),RFC7465,2015.
[14]Johnson D.Hash functions and pseudo-randomness[C].Proceedings,First NIST Cryptographic Hash Workshop,2005.
[15]Barker E B,Kelsey J M.Recommendation for random number generation using deterministic random bit generators[M].National Institute of Standards&Technology(NIST),2012.
[16]Levin L A.One way functions and pseudorandom generators[J].Combinatorica,1987,7(4):357-363.
[17]Boldyreva Alexandra,Kumar V.A new pseudorandom generator from collision-resistant hash functions[C].Conference on Topics in Cryptology Springer-Verlag(CT-RSA 2012),2012:187-202.
[18]Andrew Rukhin,Juan Soto,James Nechvatal,et al.A statistical test suite for random and pseudorandom number generators for cryptographic applications[S].NIST Special Publication 800-22,2001:1-162.
[19]Yang Bo.Modern cryptography(4th edition)[M].Beijing:Tsinghua University Press,2015.
[20]Goldreich O.Foundations of cryptography:basic tools[M].Cambridge University Press,2001.
[21]Blum,Manuel,Micali S.How to generate cryptographically strong sequences of pseudo-random bits[C].Sfcs'08.Symposium on IEEE,Foundations of Computer Science(FOCS),2008:112-117.
[3]申兵,董新峰,徐兵杰,等.随机数发生器及其在密码学中的应用(第1版)[M].北京:国防工业出版社,2016.
[5]黄小莉,石竑松,张翀斌,等.对一类组合线性同余发生器的不可预测性研究[J].清华大学学报(自然科学版),2016,56(1):22-27.
[19]杨波.现代密码学(第3版)[M].北京:清华大学出版社,2015.
[2]Goldwasser S,Micali S.Probabilistic encryption[J].Journal of Computer&System Sciences(JCSS),1984,28(2):270-299.
[3]Shen Bing,Dong Xin-feng,Xu Bing-jie,et al.Random number generators and their applications in cryptography(1st edition)[M].Beijing:National Defense Industry Press,2016.
[4]Lih-Yuandeng,Olusegungeorge E.Generation of uniform variates from several nearly uniformly distributed variables[J].Communications in Statistics-Simulation and Computation,1990,19(1):145-154.
[5]Huang Xiao-li,Shi Hong-song,Zhang Chong-bin,et al.Unpredictability of a kind of combined linear congruential generator[J].Journal of Tsinghua University,2016,56(1):22-27.
[6]Knuth D E.The art of computer programming,volume 3:(2nd ed.)sorting and searching[M].Addison Wesley Longman Publishing Co.Inc.1998.
[7]Robshaw M.Stream ciphers[R].RSA Laboratories Technical Report TR-701,July 1995.
[8]Chefranov A G,Mazurova T A.Pseudo-random number generator RC4 period improvement[C].IEEE International Conference on Automation(ICRA),Quality and Testing,Robotics,2006:38-41.
[9]Shen H,Peng Z,Kan W.Improved linear congruential random number generators[J].Journal of Tsinghua University,2009,49(2):191-193.
[10]Ronald L Rivest,Jacob C N Schuldt.Spritz-a spongy RC4-like stream cipher and hash function[Z].http://people.csail.mit.edu/rivest/pubs/RS14.pdf,2014:1-30.
[11]Gupta S S,Maitra S,Paul G,et al.Nonrandom sequences from nonrandom permutations-analysis of RC4 stream cipher[J].Journal of Cryptology,2014,27(1):67-108.
[12]Jindal P,Singh B.A survey on RC4 stream cipher[J].Computer Netw ork and Information Security,2015,(7):37-45.
[13]Popov A.Prohibiting RC4 cipher suites[R].Internet Engineering Task Force(IETF),RFC7465,2015.
[14]Johnson D.Hash functions and pseudo-randomness[C].Proceedings,First NIST Cryptographic Hash Workshop,2005.
[15]Barker E B,Kelsey J M.Recommendation for random number generation using deterministic random bit generators[M].National Institute of Standards&Technology(NIST),2012.
[16]Levin L A.One way functions and pseudorandom generators[J].Combinatorica,1987,7(4):357-363.
[17]Boldyreva Alexandra,Kumar V.A new pseudorandom generator from collision-resistant hash functions[C].Conference on Topics in Cryptology Springer-Verlag(CT-RSA 2012),2012:187-202.
[18]Andrew Rukhin,Juan Soto,James Nechvatal,et al.A statistical test suite for random and pseudorandom number generators for cryptographic applications[S].NIST Special Publication 800-22,2001:1-162.
[19]Yang Bo.Modern cryptography(4th edition)[M].Beijing:Tsinghua University Press,2015.
[20]Goldreich O.Foundations of cryptography:basic tools[M].Cambridge University Press,2001.
[21]Blum,Manuel,Micali S.How to generate cryptographically strong sequences of pseudo-random bits[C].Sfcs'08.Symposium on IEEE,Foundations of Computer Science(FOCS),2008:112-117.
[3]申兵,董新峰,徐兵杰,等.随机数发生器及其在密码学中的应用(第1版)[M].北京:国防工业出版社,2016.
[5]黄小莉,石竑松,张翀斌,等.对一类组合线性同余发生器的不可预测性研究[J].清华大学学报(自然科学版),2016,56(1):22-27.
[19]杨波.现代密码学(第3版)[M].北京:清华大学出版社,2015.