Survey on hardware implementation of random number generators on FPGA: Theory and experimental analyses

Knuth, 1997, vol. 2 Gentle, 2003 Froberg, 1969 Luby, 1996 Even, 1997, A construction of a cipher from a single pseudorandom permutation, J. Cryptol., 10, 151, 10.1007/s001459900025 ElGamal, 1985, A public key cryptosystem and a signature scheme based on discrete logarithms, 10 Henson, 2014, Memory encryption: a survey of existing techniques, ACM Comput. Surv., 46, 53, 10.1145/2566673 Lamport, 1979 Shannon, 1949, Communication theory of secrecy systems, Bell Syst. Tech. J., 28, 656, 10.1002/j.1538-7305.1949.tb00928.x L. Tippett, Random sampling numbers. Arranged by L.H.C. Tippett, Etc, [Tracts for Computers. no. 15.], 1927. http://books.google.dz/books?id=CZJTMwEACAAJ. Campbell-Kelly, 2005, The history of mathematical tables, AMC, 10, 12 Kendall, 1938, Randomness and random sampling numbers, J. Roy. Stat. Soc., 147, 10.2307/2980655 Lavington, 1975 Brown, 1949 Thomson, 1959, Ernie–A mathematical and statistical analysis, J. Roy. Statist. Soc. Ser. A, 301, 10.2307/2342795 Metropolis, 1987, The beginning of the Monte Carlo method, Los Alamos Science, 15, 125 Niederreiter, 1992, N.-C. R. C. on Random Number Generation L’Ecuyer, 1994, Uniform random number generation, Ann. Oper. Res., 53, 77, 10.1007/BF02136827 Motchenbacher, 1993 Kleeman, 1987, Metastable behavior in digital systems, IEEE Des. Test Comput., 4, 4, 10.1109/MDT.1987.295189 Hsieh, 1996, Phase-locked loop techniques. A survey, Ind. Electron., IEEE Trans., 43, 609, 10.1109/41.544547 R.H. Freeman, H.-C. Hsieh, Distributed memory architecture for a configurable logic array and method for using distributed memory, Google Patents, US Patent 5,343,406, 1994. P.M. Freidin, Logic block with look-up table for configuration and memory, Google Patents, US Patent 5,414,377, 1995. E. Barker, A. Roginsky, DRAFT nIST Special Publication 800-131 Recommendation for the Transitioning of Cryptographic Algorithms and Key Sizes, 2010. G. Marsaglia, (1995) The diehard test suite, 1995.. L’Ecuyer, 2007, TestU01: AC library for empirical testing of random number generators, ACM Trans. Math. Softw., 33, 22, 10.1145/1268776.1268777 L’Ecuyer, 2005, Fast random number generators based on linear recurrences modulo 2: overview and comparison, 10 Matsumoto, 1998, Mersenne twister: a 623-dimensionally equidistributed uniform pseudo-random number generator, ACM Trans. Model. Comput. Simul., 8, 3, 10.1145/272991.272995 Tausworthe, 1965, Random numbers generated by linear recurrence modulo two, Math. Comp., 19, 201, 10.1090/S0025-5718-1965-0184406-1 Knuth, 1985, Deciphering a linear congruential encryption, IEEE Trans. Inform. Theory, 31, 49, 10.1109/TIT.1985.1056997 Lewis, 1973, Generalized feedback shift register pseudorandom number algorithm, J. ACM, 20, 456, 10.1145/321765.321777 Matsumoto, 1992, Twisted GFSR generators, ACM Trans. Model. Comput. Simul., 2, 179, 10.1145/146382.146383 Fishman, 1986, An exhaustive analysis of multiplicative congruential random number generators with modulus 2̂31-1, SIAM J. Sci. Stat. Comput., 7, 24, 10.1137/0907002 Banks, 2008, FPGA implementation of Pseudo Random Number generators for Monte Carlo methods in quantitative finance, 271 Press, 2007, Numerical recipes Marsaglia, 2003, Xorshift rngs, J. Stat. Softw., 8, 1, 10.18637/jss.v008.i14 Marsaglia, 1991, A new class of random number generators, Ann. Appl. Probab., 462, 10.1214/aoap/1177005878 Oudjida, 2014, Radix-2r arithmetic for multiplication by a constant, Circuits Syst. II, IEEE Trans., 61, 349, 10.1109/TCSII.2014.2312799 Oudjida, 2016, Multiple constant multiplication algorithm for high speed and low power design, Circuits Syst. II, IEEE Trans., 63, 176, 10.1109/TCSII.2015.2469051 Oudjida, 2015, Radix-2r arithmetic for multiplication by a constant: Further results and improvements, Circuits Syst. II, IEEE Trans., 62, 372, 10.1109/TCSII.2014.2387620 Katti, 2009, Efficient hardware implementation of a new pseudo-random bit sequence generator, 1393 Erkek, 2013, The implementation of ASG and SG Random Number Generators, 363 Gonzalez-Diaz, 2011, A pseudorandom number generator based on time-variant recursion of accumulators, Circuits Syst. II, IEEE Trans. on, 58, 580, 10.1109/TCSII.2011.2161165 Friedman, 1988, The structure of the limit cycles in sigma delta modulation, Commun., IEEE Trans., 36, 972, 10.1109/26.3777 Maloberti, 2009, Time variant digital sigma-delta modulator for fractional-n frequency synthesizers, 111 Thomas, 2008, Fpga-optimised high-quality uniform random number generators, 235 Thomas, 2010, FPGA-optimised uniform random number generators using luts and shift registers, 77 Thomas, 2013, The LUT-SR family of uniform random number generators for FPGA architectures, Very Large Scale Integr. (VLSI) Syst., IEEE Trans., 21, 761, 10.1109/TVLSI.2012.2194171 Chandrasekaran, 2008, High performance FPGA implementation of the Mersenne Twister, 482 Tian, 2009, Mersenne Twister random number generation on FPGA, CPU and GPU, 460 Dalal, 2008, On the fast generation of long-period pseudorandom number sequences, 1 Saito, 2008, SIMD-oriented fast Mersenne Twister: a 128-bit pseudorandom number generator, 607 Li, 2012, An efficient hardware random number generator based on the MT method, 1011 Wu, 2013, Hardware architecture for the parallel generation of long-period random numbers using MT method, 8 Echeverría, 2013, High Performance FPGA-oriented mersenne twister uniform random number generator, J. Signal Process. Syst., 71, 105, 10.1007/s11265-012-0684-4 Von Neumann, 1966, Theory of self-reproducing automata, IEEE Trans. Neural Netw., 5, 3 Gleick, 1997 Anghelescu, 2007, VLSI implementation of high-speed cellular automata encryption algorithm, 509 Dogaru, 2010, Algebraic normal form for rapid prototyping of elementary hybrid cellular automata in FPGA, 277 Ioana, 2014, FPGA implementation and evaluation of two cryptographically secure hybrid cellular automata, 1 Tkacik, 2003, A hardware random number generator, 450 Cerda, 2012, An efficient FPGA random number generator using LFSRs and cellular automata, 912 Guan, 2003, Pseudorandom number generator–The self programmable cellular automata, 1230 Comer, 2012, Random number generators using Cellular Automata implemented on FPGAs, 67 Raut, 2013, Stream cipher design using cellular automata implemented on FPGAs, 146 David, 2011, A2U2: a stream cipher for printed electronics RFID tags, 176 Kotoulas, 2006, 1-d cellular automaton for pseudorandom number generation and its reconfigurable hardware implementation, 4 Blum, 1986, A simple unpredictable pseudo-random number generator, SIAM J. Comput., 15, 364, 10.1137/0215025 Sewak, 2012, FPGA implementation of 16 bit BBS and LFSR PN sequence generator: A comparative study, 1 Peris-Lopez, 2010, Cryptographically secure pseudo-random bit generator for RFID tags, 1 Montgomery, 1985, Modular multiplication without trial division, Math. Comput., 44, 519, 10.1090/S0025-5718-1985-0777282-X Tsoi, 2003, Compact FPGA-based true and pseudo random number generators, 51 Pecora, 1990, Synchronization in chaotic systems, Phys. Rev. Lett., 64, 821, 10.1103/PhysRevLett.64.821 Wiggins, 2003 May, 1976, Simple mathematical models with very complicated dynamics, Nature, 261, 459, 10.1038/261459a0 Hénon, 1976, A two-dimensional mapping with a strange attractor, Comm. Math. Phys., 50, 69, 10.1007/BF01608556 Dabal, 2011, A chaos-based pseudo-random bit generator implemented in fpga device, 151 Padgett, 2009, Fixed-point signal processing, 10.1007/978-3-031-02533-4 Dabal, 2012, FPGA implementation of chaotic pseudo-random bit generators, 260 Dabal, 2014, A study on fast pipelined pseudo-random number generator based on chaotic logistic map, 195 Pande, 2010, Design and hardware implementation of a chaotic encryption scheme for real-time embedded systems, 1 Liu, 2008, An improved chaos-based stream cipher algorithm and its VLSI implementation, 191 L. Merah, A. Ali-Pacha, N.H. Said, Coupling two chaotic systems in order to increasing the security of a communication system-study and real time FPGA implementation. Giard, 2012, FPGA implementation and evaluation of discrete-time chaotic generators circuits, 3221 Geisel, 1984, Statistical properties of chaos in Chebyshev maps, Phys. Lett. A, 105, 263, 10.1016/0375-9601(84)90993-9 Mao, 2006, Design and fpga implementation of a pseudo-random bit sequence generator using spatiotemporal chaos, 2114 Černák, 1996, Digital generators of chaos, Phys. Lett. A, 214, 151, 10.1016/0375-9601(96)00179-X Li, 2006, A chaos-based pseudo random number generator using timing-based reseeding method, 4 R. B, Simultaneous carry adder, Google Patents, US Patent 2,966,305, 1960. http://www.google.com/patents/US2966305. Li, 2012, Period extension and randomness enhancement using high-throughput reseeding-mixing PRNG, Very Large Scale Integr. (VLSI) Syst., IEEE Trans., 20, 385, 10.1109/TVLSI.2010.2103332 Deng, 2005, Efficient and portable multiple recursive generators of large order, ACM Trans. Model. Comput. Simul., 15, 1, 10.1145/1044322.1044323 Oshiba, 1972, Closure property of family of context-free languages under cyclic shift operation, Electron. Commun. Japan, 55, 119 Shedletsky, 1977, Comment on the sequential and indeterminate behavior of an end-around-carry adder, IEEE Trans. Comput., 26, 271, 10.1109/TC.1977.1674817 Hariprasad, 2013, FPGA implementation of a cryptography technology using pseudo random number generator, Int. J. Eng. Res. Technol., 2 Rössler, 1976, An equation for continuous chaos, Phys. Lett. A, 57, 397, 10.1016/0375-9601(76)90101-8 Elwakil, 2001, Construction of classes of circuit-independent chaotic oscillators using passive-only nonlinear devices, Circuits Syst. I, IEEE Trans., 48, 289, 10.1109/81.915386 Elwakil, 2000, Chaotic oscillator configuration using a frequency dependent negative resistor, Int. J. Circuit Theory Appl., 28, 69, 10.1002/(SICI)1097-007X(200001/02)28:1<69::AID-CTA73>3.0.CO;2-E Zidan, 2011, The effect of numerical techniques on differential equation based chaotic generators, 1 Chen, 2003 P. Tsai, C. Merkle, T. Huang, Euler equation analysis of the propeller-wake interaction, in: Symposium on Naval Hydrodynamics, 17th, 1900. Hammer, 1958, The midpoint method of numerical integration, Math. Mag., 31, 193, 10.2307/3029196 Butcher, 2000, Numerical methods for ordinary differential equations in the 20th century, J. Comput. Appl. Math., 125, 1, 10.1016/S0377-0427(00)00455-6 Zidan, 2011, Random number generation based on digital differential chaos, 1 E. G, Latched carry save adder circuit for multipliers, Google Patents, US Patent 3,340,388, 1967. http://www.google.com/patents/US3340388. Wallace, 1964, A suggestion for a fast multiplier, Electron. Comput., IEEE Trans., 14, 10.1109/PGEC.1964.263830 Mansingka, 2013, Fibonacci-based hardware post-processing for non-autonomous signum hyperchaotic system, 1 Fang, 2014, FPGA acceleration of a pseudorandom number generator based on chaotic iterations, J. Inf. Secur. Appl., 19, 78 Bahi, 2013, FPGA design for pseudorandom number generator based on chaotic iteration used in information hiding application, Appl. Math., 7, 2175 Wang, 2015, Study on a new chaotic bitwise dynamical system and its FPGA implementation, Chin. Phys. B, 24, 060503, 10.1088/1674-1056/24/6/060503 Q. Wang, S. Yu, C. Guyeux, J. Bahi, X. Fang, A chaotic bitwise dynamical system and its FPGA-based realization, in: IWCFTA1’4, 7-Th Int. Workshop on Chaos-Fractals Theories and Applications, Qingdao, China, 2014. Bakiri, 2016, FPGA implementation of F2-linear pseudorandom number generators based on Zynq MPSoC: A chaotic iterations post processing case study, 302 Bakiri, 2017, CIPRNG: A VLSI family of chaotic iterations post-processings for F-2 linear pseudorandom number generation based on Zynq MPSoC, IEEE Trans. Circuits Syst. I. Regul. Pap., PP, 1 Bakiri, 2017, One random jump and one permutation: Sufficient conditions to chaotic, statistically faultless, and large throughput PRNG for FPGA, 295 Couchot, 2014, Pseudorandom number generators with balanced gray codes, 1 Contassot-Vivier, 2017, Random walk in a N-cube without Hamiltonian cycle to chaotic pseudorandom number generation: Theoretical and practical considerations, Int. J. Bifurcation Chaos, 27, 1750014, 10.1142/S0218127417500146 Purkayastha, 2015, Digital phase-locked loop, 103 Fischer, 2003, True random number generator embedded in reconfigurable hardware, 415 M. Šimka, M. Drutarovskỳ, V. Fischer, Embedded true random number generator in actel FPGAs, in: Workshop on Cryptographic Advances in Secure Hardware–CRASH, 2005, pp. 6–7. Simka, 2011, Testing of pll-based true random number generator in changing working conditions, Radioengineering, 20, 94 Varchola, 2008, Hardware platform for testing performance of TRNGs embedded in actel fusion FPGA, 1 Kohlbrenner, 2004, An embedded true random number generator for FPGAs, 71 C. Klein, O. Cret, A. Suciu, Design and implementation of a high quality and high throughput TRNG in FPGA, 2009, ArXiv Preprint ArXiv:0906.4762. Dichtl, 2007 Cherkaoui, 2013, A self-timed ring based true random number generator, 99 Cherkaoui, 2012, Comparison of self-timed ring and inverter ring oscillators as entropy sources in FPGAs, 1325 Cherkaoui, 2013, A very high speed true random number generator with entropy assessment, 179 Sutherland, 1989, Micropipelines, Commun. ACM, 32, 720, 10.1145/63526.63532 Vasyltsov, 2008, Fast digital TRNG based on metastable ring oscillator, 164 Majzoobi, 2011, FPGA-based true random number generation using circuit metastability with adaptive feedback control, 17 Salman, 2007, Exploiting setup–hold-time interdependence in static timing analysis, Comput.-Aided Des. Integr. Circuits Syst., IEEE Trans., 26, 1114, 10.1109/TCAD.2006.885834 Lee, 2014, Metastability-based feedback method for enhancing FPGA-based TRNG, Int. J. Multimedia Ubiquitous Eng., 9 NIST, National Institute of Standards and Technology (NIST): FIPS140−1: Security Requirements for Cryptographic Modules @ONLINE, 1994. http://csrc.nist.gov/publications/fips/fips140-1/fips1401.pdf. NIST, National Institute of Standards and Technology (NIST): A Statistical Test Suite for Random and Pseudorandom Number Generators for Cryptographic Applications @ONLINE, 2010. http://csrc.nist.gov/publications/nistpubs/800-22-rev1a/SP800-22rev1a.pdf. W. Killmann, W. Schindler, A proposal for: functionality classes and evaluation methodology for true (physical) random number generators, T-Systems Debis Systemhaus Information Security Services and Bundesamt FÜR Sicherheit in Der Informationstechnik (BSI), Tech. Rep, 2001. NIST, National Institute of Standards and Technology (NIST): FIPS140−2: Security Requirements for Cryptographic Modules @ONLINE, 2001. http://csrc.nist.gov/publications/fips/fips140-2/fips1402.pdf. Canteaut, 2011, Berlekamp–Massey algorithm, 80 Zarei Moghadam, 2010, Designing a random number generator with novel parallel LFSR substructure for key stream ciphers Zhu, 2010, A dynamic nonlinear transform arithmetic for improving the properties chaos-based PRNG, 7055 Bonato, 2013, A mersenne twister hardware implementation for the Monte Carlo localization algorithm, J. Signal Process. Syst., 70, 75, 10.1007/s11265-012-0661-y