高速数字物理噪声源设计
|
摘要
由于数字物理噪声源可以产生随机性较好的随机数作为密钥，已被广泛应用于安全信息系统。随着计算技术和密码学的发展，当今的安全信息系统迫切需要更高速率的数字物理噪声源。
本文讨论了高速数字物理噪声源的系统级设计方案。本文从自然界的随机噪声入手，提出并阐述了基于硬币模型和迭代环理论的高速数字物理噪声源的电路设计方案，同时在电路设计过程中注意兼顾后期芯片集成的可行性。本文还给出了电路方案的测试结果，并且从理论分析和实际测试结果两个方面说明了我们设计的高速数字物理噪声源具有很好的随机性。
The digital physical noise generation is widely used in secure
information system because it can produce random numbers which possesses good randomness, which are generally used as key. With the development of computing technology and cryptography, high-speed digital physical noise generator is urgently required in cryptography at present.
Circuit design scheme of the high-speed digital physical noise generator was mainly discussed in this paper. Circuit design based on rotating coin model and iteration loop theory was proposed and explained beginning with the hot noise. At the same time we also considered the probability
of the chip integrity of the digital physical noise generation. The test outcome was given in this paper. In the end we proved that the highspeed digital physical noise generation we designed possesses good randomness both in analysis of the theory and result of the virtual testing.
本文讨论了高速数字物理噪声源的系统级设计方案。本文从自然界的随机噪声入手，提出并阐述了基于硬币模型和迭代环理论的高速数字物理噪声源的电路设计方案，同时在电路设计过程中注意兼顾后期芯片集成的可行性。本文还给出了电路方案的测试结果，并且从理论分析和实际测试结果两个方面说明了我们设计的高速数字物理噪声源具有很好的随机性。
The digital physical noise generation is widely used in secure
information system because it can produce random numbers which possesses good randomness, which are generally used as key. With the development of computing technology and cryptography, high-speed digital physical noise generator is urgently required in cryptography at present.
Circuit design scheme of the high-speed digital physical noise generator was mainly discussed in this paper. Circuit design based on rotating coin model and iteration loop theory was proposed and explained beginning with the hot noise. At the same time we also considered the probability
of the chip integrity of the digital physical noise generation. The test outcome was given in this paper. In the end we proved that the highspeed digital physical noise generation we designed possesses good randomness both in analysis of the theory and result of the virtual testing.
引文
[1]相曙华，“数字物理噪声源及其芯片集成”，硕士论文，1998。
[2]王玉柱，“随机性测试工具研究与实现”，硕士论文，2001。
[3]阎石，数字电子技术基础，高等教育出版社，1997。
[4]张建人，MOS集成电路分析与设计基础，电子工业出版社，1994。
[5]曹志刚，钱亚生，现代通信原理，清华大学出版社，1992。
[6]Schneier, Applied Cryptography---Protocols, Algorithms, and Source Code in C, John Wiley & Sons, 1994.
[7]Knuth, D.E.,The Art of Computer Programming, volume 2: Seminumerical Algorithms. Addison-Wesley, Reading, MA, 3rd edition, 1997.
[8]Benjamin Jun and Paul Kocher, The Intel Random Number Generator,Cryptography Research, Inc. White Paper Papered for intel corporation.
[9]Concept for a High Performance Random Number Generator Based on Physical Random Phenomena, Michael Gude. Fruquenze(Germany) 1985, Vol 39.
[10]Eastlake, D.S.Crocker and J. Schiller,"Randomness Recommendations for Security." Internet Engineering Task Force RFC 1750, 1994.
[11] Ellison,Carl."Cryptogrophic Random Numbers."Draft P1363 Appendix E.
[12] A.Menezes,P.Van Oorschot,and S.Vanstone,Handbook of Applied Cryptography,CRC Press,1997．
[13] Markoff,John."Security Flaw Is Discovered In Software Used in Shopping/The New York Times,19 September 1995,sec.A,p.
[14] Anant P.Godbole and Stavros G.Papastavidis,(ed),Runs and patterns in probability:Selected papers.Dordrecht:Kluwer Academic,1994．
[15] S.Pincus and B.H.Singer,"Randomness and degrees of irregularity," Proc.Natl.Acad.Sci.USA.Vol.93,March 1996,pp.2083-2088．
[16] S.Pincus and R.E.Kalman,"Not all (possibly) "random" sequences are created equal," Proc.Natl.Acad.Sci.USA.Vol.94, April 1997,pp.3513-3518．
[17] Niederreiter,H.:Random Number Generation and Quasi-Monte Carlo Methods SIAM,Philadelphia,1992．
[18] Hellekalek,P.:Good Number Generator are (not so )easy to find. Mathematics and Computers in Simulation,46:485-505,1998．
[19] Marsaglia,G.:A current view of random number generators.In Billard,L.,editor(s),Computer Science and Statistics:The Interface,pp.3-10． Elsevier Science Publishers B.V.,Amsterdam, 1985．
[20] L'Ecuyer,P.:Random number generation.In Jerry Banks,editor(s),
The Handbook of Simulation,pp.93--137． Wiley,New York, 1998．
[21] Ripley,B.D.:Thoughts on pseudorandom number generators.J. Comput.Appl.Math.,31:153-163,1990．
[22] H.Becker,F.Pipe,Cryptographic system-secure communications,1980．
[23] Matsumoto,M.and Kurita,Y.:Twisted GFSR generators Ⅱ.ACM Trans.Model.Comput.Simul.,4:254-266,1994．
[24] Niederreiter,H.and Shparlinski,I.~E.:On the distribution and lattice structure of nonlinear congruential pseudorandom numbers. Finite Fields and Their Applications,5:246-253,1999．
[25] Ueli M.Maurer,"A Universal Statistical Test for Random Bit Generators," Journal of Cryptology.Vol.5,No.2,1992．
[26] Weingartner,A.:Nonlinear congruential pseudorandom number generators.Master's thesis,University of Salzburg,1994．
[27] A.Rukhin (2000) ,"Approximate entropy for testing randomness," Journal of Applied Probability.Vol.37,2000．
[28] Blum,M.and Micali,S.:How to generate cryptographically strong sequences of pseudo-random bits.SIAM Journal of Computing,13: 850-864,1984．
[29] Frank Spitzer,Principles of Random Walk.Princeton:Van Nostrand,1964．
[30] Pal Revesz,Random Walk in Random And Non-Random Environments.Singapore:World Scientific,1990．
[31 ]Goldreich,O.:Modern Cryptography,Probabilistic Proofs and Pseudorandomness.Springer Verlag,Berlin,1999．
[32] J-S Coron and D.Naccache,"An Accurate Evaluation of Maurer's Universal Test," Proceedings of SAC'98． Berlin:Springer-Verlag,1998．
[33] H.Gustafson,E.Dawson,L.Nielsen,W.Caelli,"A computer package for measuring the strength of encryption algorithms," Computer &Security.13(1994) ,pp.687-697．
[34] J.Ziv,"Compression tests for randomness and estimating the statistical model of an individual sequence," Sequences (ed.R.M. Capocelli).Berlin:Springer-Verlag,1990．
[35] J.Ziv and A.Lempel,"A Universal algorithm for sequential data compression," IEEE Transactions on Information Theory.Vol.23, pp.337-343．
[36] D.Aldous and P.Shields (1988) ." A Diffusion Limit for a Class of Randomly-Growing Binary Trees",Probability Theory and Related Fields.79,pp.509-542．
[37] P.Kirschenhofer,H.Prodinger,and W.Szpankowski (1994) , "Digital Search Trees Again Revisited:The Internal Path Length Perspective," SIAM Journal on Computing.23,pp.598-616．
[38] F.N.David and D.E.Barton,Combinatorial Chance.New York: Hafner Publishing Co.,1962,p.230．
[39] Anant P.Godbole and Stavros G.Papastavridis (ed),Runs and Patterns in Probability:Selected Papers.Dordrecht:Kluwer
Academic,1994．
[40] Lagarias,J.C.:Pseudorandom Numbers.Statistical Science,8:31--39,1993．
[41] Pal Revesz,Random Walk in Random and Non-Random Environments.Singapore:World Scientific,1990．
[42] R.N.Bracewell,The fourier Transform and Its Application.New York:McGraw-Hill,1986
[43] Juan Soto,Statistical Testing of Random Number Generators.
[44] Niederreiter,H.and Winterhof,A.:Incomplete exponential sums over finite fields and their applications to new inversive pseudorandom number generators.Finite Fields and Their Applications,93:387-399,2000．
[45] Juan Soto and Lawrence Bassham,Randomness Testing of the Advanced Encryption Standard Finalist Candidates,March 28,2000．
[46] Adnrew Rukin,Juan Soto,A statistical test for random number generators for cryptographic applications.
[47] Matsumoto,M.and Nishimura,T.:Mersenne Twister:A 623-dimensionally equidistributed uniform pseudorandom number generator.ACM Trans.Modeling and Computer Simulation,8:3-30,1998．
[48] Hagit Shatkay,The Fourier Transfer-A Primer,Department of Computer Science,Brown University,Provindence,RI 02912
[49] Stephan Neuhaus,Statistical Properties of IDEA Session Keys in
PGP,Hilgardring 32．
[50] Hellekalek,P.:On the assessment of random and quasi-random point sets.In Hellekalek,P.and Larcher,G.,editor(s),Pseudo and Quasi-Random Point Sets of Lecture Notes in Statistics.Springer-Verlag,New York,1998．
[51] Michael Baron and Adnrew L.Rukhin,distribution of the number of visits of a random walk and a test of randomness,Programs in Mathematical Sciences,University of Texas at Dallas,Richardson, TX 75083 USA.
[52] L.Blum,M.Blum,and M.Shub (1994) ,"A Simple Unpredictable Pseudorandom Number Generator," SIAM Journal on Computing. 15,pp.364-383．
[2]王玉柱，“随机性测试工具研究与实现”，硕士论文，2001。
[3]阎石，数字电子技术基础，高等教育出版社，1997。
[4]张建人，MOS集成电路分析与设计基础，电子工业出版社，1994。
[5]曹志刚，钱亚生，现代通信原理，清华大学出版社，1992。
[6]Schneier, Applied Cryptography---Protocols, Algorithms, and Source Code in C, John Wiley & Sons, 1994.
[7]Knuth, D.E.,The Art of Computer Programming, volume 2: Seminumerical Algorithms. Addison-Wesley, Reading, MA, 3rd edition, 1997.
[8]Benjamin Jun and Paul Kocher, The Intel Random Number Generator,Cryptography Research, Inc. White Paper Papered for intel corporation.
[9]Concept for a High Performance Random Number Generator Based on Physical Random Phenomena, Michael Gude. Fruquenze(Germany) 1985, Vol 39.
[10]Eastlake, D.S.Crocker and J. Schiller,"Randomness Recommendations for Security." Internet Engineering Task Force RFC 1750, 1994.
[11] Ellison,Carl."Cryptogrophic Random Numbers."Draft P1363 Appendix E.
[12] A.Menezes,P.Van Oorschot,and S.Vanstone,Handbook of Applied Cryptography,CRC Press,1997．
[13] Markoff,John."Security Flaw Is Discovered In Software Used in Shopping/The New York Times,19 September 1995,sec.A,p.
[14] Anant P.Godbole and Stavros G.Papastavidis,(ed),Runs and patterns in probability:Selected papers.Dordrecht:Kluwer Academic,1994．
[15] S.Pincus and B.H.Singer,"Randomness and degrees of irregularity," Proc.Natl.Acad.Sci.USA.Vol.93,March 1996,pp.2083-2088．
[16] S.Pincus and R.E.Kalman,"Not all (possibly) "random" sequences are created equal," Proc.Natl.Acad.Sci.USA.Vol.94, April 1997,pp.3513-3518．
[17] Niederreiter,H.:Random Number Generation and Quasi-Monte Carlo Methods SIAM,Philadelphia,1992．
[18] Hellekalek,P.:Good Number Generator are (not so )easy to find. Mathematics and Computers in Simulation,46:485-505,1998．
[19] Marsaglia,G.:A current view of random number generators.In Billard,L.,editor(s),Computer Science and Statistics:The Interface,pp.3-10． Elsevier Science Publishers B.V.,Amsterdam, 1985．
[20] L'Ecuyer,P.:Random number generation.In Jerry Banks,editor(s),
The Handbook of Simulation,pp.93--137． Wiley,New York, 1998．
[21] Ripley,B.D.:Thoughts on pseudorandom number generators.J. Comput.Appl.Math.,31:153-163,1990．
[22] H.Becker,F.Pipe,Cryptographic system-secure communications,1980．
[23] Matsumoto,M.and Kurita,Y.:Twisted GFSR generators Ⅱ.ACM Trans.Model.Comput.Simul.,4:254-266,1994．
[24] Niederreiter,H.and Shparlinski,I.~E.:On the distribution and lattice structure of nonlinear congruential pseudorandom numbers. Finite Fields and Their Applications,5:246-253,1999．
[25] Ueli M.Maurer,"A Universal Statistical Test for Random Bit Generators," Journal of Cryptology.Vol.5,No.2,1992．
[26] Weingartner,A.:Nonlinear congruential pseudorandom number generators.Master's thesis,University of Salzburg,1994．
[27] A.Rukhin (2000) ,"Approximate entropy for testing randomness," Journal of Applied Probability.Vol.37,2000．
[28] Blum,M.and Micali,S.:How to generate cryptographically strong sequences of pseudo-random bits.SIAM Journal of Computing,13: 850-864,1984．
[29] Frank Spitzer,Principles of Random Walk.Princeton:Van Nostrand,1964．
[30] Pal Revesz,Random Walk in Random And Non-Random Environments.Singapore:World Scientific,1990．
[31 ]Goldreich,O.:Modern Cryptography,Probabilistic Proofs and Pseudorandomness.Springer Verlag,Berlin,1999．
[32] J-S Coron and D.Naccache,"An Accurate Evaluation of Maurer's Universal Test," Proceedings of SAC'98． Berlin:Springer-Verlag,1998．
[33] H.Gustafson,E.Dawson,L.Nielsen,W.Caelli,"A computer package for measuring the strength of encryption algorithms," Computer &Security.13(1994) ,pp.687-697．
[34] J.Ziv,"Compression tests for randomness and estimating the statistical model of an individual sequence," Sequences (ed.R.M. Capocelli).Berlin:Springer-Verlag,1990．
[35] J.Ziv and A.Lempel,"A Universal algorithm for sequential data compression," IEEE Transactions on Information Theory.Vol.23, pp.337-343．
[36] D.Aldous and P.Shields (1988) ." A Diffusion Limit for a Class of Randomly-Growing Binary Trees",Probability Theory and Related Fields.79,pp.509-542．
[37] P.Kirschenhofer,H.Prodinger,and W.Szpankowski (1994) , "Digital Search Trees Again Revisited:The Internal Path Length Perspective," SIAM Journal on Computing.23,pp.598-616．
[38] F.N.David and D.E.Barton,Combinatorial Chance.New York: Hafner Publishing Co.,1962,p.230．
[39] Anant P.Godbole and Stavros G.Papastavridis (ed),Runs and Patterns in Probability:Selected Papers.Dordrecht:Kluwer
Academic,1994．
[40] Lagarias,J.C.:Pseudorandom Numbers.Statistical Science,8:31--39,1993．
[41] Pal Revesz,Random Walk in Random and Non-Random Environments.Singapore:World Scientific,1990．
[42] R.N.Bracewell,The fourier Transform and Its Application.New York:McGraw-Hill,1986
[43] Juan Soto,Statistical Testing of Random Number Generators.
[44] Niederreiter,H.and Winterhof,A.:Incomplete exponential sums over finite fields and their applications to new inversive pseudorandom number generators.Finite Fields and Their Applications,93:387-399,2000．
[45] Juan Soto and Lawrence Bassham,Randomness Testing of the Advanced Encryption Standard Finalist Candidates,March 28,2000．
[46] Adnrew Rukin,Juan Soto,A statistical test for random number generators for cryptographic applications.
[47] Matsumoto,M.and Nishimura,T.:Mersenne Twister:A 623-dimensionally equidistributed uniform pseudorandom number generator.ACM Trans.Modeling and Computer Simulation,8:3-30,1998．
[48] Hagit Shatkay,The Fourier Transfer-A Primer,Department of Computer Science,Brown University,Provindence,RI 02912
[49] Stephan Neuhaus,Statistical Properties of IDEA Session Keys in
PGP,Hilgardring 32．
[50] Hellekalek,P.:On the assessment of random and quasi-random point sets.In Hellekalek,P.and Larcher,G.,editor(s),Pseudo and Quasi-Random Point Sets of Lecture Notes in Statistics.Springer-Verlag,New York,1998．
[51] Michael Baron and Adnrew L.Rukhin,distribution of the number of visits of a random walk and a test of randomness,Programs in Mathematical Sciences,University of Texas at Dallas,Richardson, TX 75083 USA.
[52] L.Blum,M.Blum,and M.Shub (1994) ,"A Simple Unpredictable Pseudorandom Number Generator," SIAM Journal on Computing. 15,pp.364-383．