Novel pseudo-random sequence of numbers generator based cellular automata

Stepan Bilan, Mykola Bilan, Sergii Bilan

Abstract


This paper considers a novel pseudo-random bit sequence generator, which is implemented on a cellular automaton. It presents the hardware implementation of the generator and it the software simulation. With the help of the software model is testing of the random number generator was conducted. Tests showed a positive result, which confirms the high statistical properties of the generated random sequence.

Keywords: generator of pseudo-random sequence of numbers, cellular automata.


Full Text:

PDF

References


Shnayer, B. (2003), Applied cryptography. Protocols , algorithms and source code in C [Prikladnaya kryptografiya. Protokoly, algorytmy I ishodnye teksty na yazike C], Delo, Moskow, 24 p.

Chugunkov, I. V. (2012), Methods and tools of evaulation the quality of pseudo-random sequence generator, aimed at solving problems of information security [Metody I sredstva ocenky kachestva generatorov psevdosluchaynih posledovatelynostey, orientirovannih na reshenye zadach zasyty informacyy : uchebnoye posobye], NYAU, Moskow, 236 p.

Ivanov, M.A., Chugunkov, I.V. (2003), The theory , application and evaluation of the quality of pseudo-random sequence generator [Teoriya, prymenenye i ocenka kachestva generatorov psevdosluchaynih posledovatelynostey]. CUDYC-OBRAZ, Мoskow, 240 p.

Von Neumann, J. (1951), Various techniques used in connection with random digits, Applied Mathematics Series, Vol. 12, pp. 36-38.

L'Ecuyer, P. (1994), Uniform random number generation, Annals of Operations Research, Vol. 53, pp. 77-120.

Haryn, U. S., Bernyk, V. I., Matveev, G. V. (1999), Mathematical foundations of cryptology : tutorial [Matematycheskye osnovy kryptologyy : ucheb. posobye]. BGU, Minsk, 319 p.

Lehmer, D. (1951), Mathematical methods in large-scale computing units, Large-Scale Digital Calculating Machinery : symp. proc, Harvard, pp. 141-146.

Thomson, W. (1958), A modified congruence method of generating pseudo-random numbers, Computer Journal, Vol. 1, pp. 83-86.

Hammer, P. (1951), The mid-square method of generating digits, Monte Carlo Method : symp. proc (Los Angeles, 1949), Washington, Vol. 12, pp. 33.

Marsaglia, G. (2003), Random number generators, Journal of Modern Applied Statistical Methods, Vol. 2, pp. 2-13.

Eichenauer, J., Lehn, J., Topuzoglu, A. (1988), A nonlinear congruential pseudorandom number generator with power of two modulus, Mathematics of Computation, Vol. 51, pp. 757-759.

Lewis, Т., Payne, W. (1973), Generalized feedback shift register pseudorandom number algorithms, Journal of ACM, Vol. 21, pp. 456-468.

Matsumoto, M., Nishimura, T. (1998), Mersenne twister : a 623-dimensionally equidistributed uniform pseudo-random number generator, ACM Transactions on Modeling and Computer Simulation, Vol. 8, pp. 3-30.

Hell, M., Johansson, Т., Meier, W. (2005), Grain – A stream cipher for constrained environments, The eSTREAM Project, available at : http://www.ecrypt.eu.org/stream/p3ciphers/ grain/Grain_p3.pdf (accessed 23 March 2015).

Suhinin, B.M. (2010), High-speed generators of pseudorandom sequences based on cellular automata [Visokoskorostnye generatory psevdosluchaynih posledovatelynostey na osnove kletochnyh avtomatov], Prykladnaya dyskretnaya matematika, No. 2, pp. 34-41.

Suhinin, B.M. (2010), Development of generators of pseudorandom binary sequences based on cellular automata [Razrabotka generatorov psevdosluchaynyh dvoichnyh posledovatelynostey na osnove kletochnyh avtomatov], Nauka i obrazovanye, No. 9, pp. 1-21.

Wolfram, S. (1983), Cellular automata, Los Alamos Science, Vol. 9, pp. 2-21.

Wolfram, S. (1986), Cryptography with cellular automata, Lecture Notes in Computer Science, Vol. 218, pp. 429-432.

Wolfram, S. (1986), Random sequence generation by cellular automata, Advances in Applied Mathematics, Vol. 7, pp. 123-169.

Meier, W., Staffelbach, O. (1991), Analysis of Pseudo Random Sequences by Cellular Automata, Advances in Cryptology EUROCRYPT’91 Proceedings, Springer – Verlag, pp. 186-199.

Bartee, T.C., Schneider,D. L. (1963), Computation Finite Fields, Information and Control, Vol. 6, No. 2. pp. 79-88.

Fraile Ruboi, C., Hernandez Encinas, L., Hoya White, S., Martin del Rey and Rodrigues Sancher, A. (2004), The use of Linear Hybrid Cellular Automata as Pseudorandom bit Generators in Cryptography, Neural Parallel & Scientific Comp, No. 12 (2), pp. 175-192.

Martin, B., Sole, P. (2008), Pseudo-random Sequences Generated by Cellular Automata, International Conference on Ralations, Orders and Graphs: Interaction with Computer Scince, May 2008, Mandia, Tunisia, Nouha editions, pp. 401-410.

Wolfram, S. (1986), Theory and applications of cellular automata, World Scientific Publishing Co. Ltd., pp. 485-557.

Cattell, K., Muzio, J. (1996), Synthesis of one-dimensional linear hybrid cellular automata, IEEE Trans. On Computer-aided design of integrated circuits and systems, No. 15(3), pp. 325-335.

Cho, S. J., Choi, U. S., Kim, H. D., Hwang, Y. H., Kim, J. G., Heo, S. H. (2007), New syntheesis of one-dimensional 90/150 liner hybrid group CA, IEEE Transactions on comput-aided design of integrated circuits and systems, No. 25(9), pp. 1720-1724.

Belan, S. N. (2011), Specialized cellular structures for image contour analysis, Cybernetics and Systems Analys, September, Vol. 47, Iss. 5, pp 695-704.

Belan, S., Belan, N. (2012), Use of Cellular Automata to Create an Artificial System of Image Classification and Recognition, ACRI2012, LNCS 7495, Springer-Verlag Berlin Heidelberg, pp. 483-493.

Belan, S., Belan, N. (2013), Temporal-Impulse Description of Complex Image Based on Cellular Automata, PaCT2013, LNCS. Vol. 7979, Springer-Verlag Berlin Heidelberg, pp. 291-295.

Bilan, S. (2014), Models and hardware implementation of methods of Pre-processing Images based on the Cellular Automata, Advances in Image and Video Processing, Vol. 2, No. 5, pp. 76-90.

Bilan, S., Bilan, M., Bilan, S. (2015), Application of Methods of Organization of Cellular Automata to Implement Devices of Forming Pseudorandom Sequences, Information Technology & Computer Science Abstracts 11th Annual International Conference on Information Technology & Computer Science, 18-21 May 2015, Athens, Greece Edited by Gregory T. Papanikos, pp. 17-18.

Bilan, S. M., Bilan, M. M., Bilan, A. M., Bilan, S. S. (2014), Generator pseudorandom bit sequence based on cellular automata [Generator psevdovypadkovih bitovyh poslidovnostey na osnovi klitynnyh avtomativ], Patent of Ukraine na korysnu model, Bul. № 18 vid 25.09.14.

Bilan, S. M. (2015), Information security in telecommunication systems : a manual for students of higher educational institutions [Zahist informacii v telekomunikaciynyh systemah: navch. posyb. dlya stud. vyshih navch. zakl. zalyzn. Transp], DETUT, Кiev, 132 p.

Bilan, S. M., Bilan, M. M. (2014), A computer program to create sequences of pseudorandom numbers and pseudorandom bit sequence based on cellular automata «pseudorandom sequence generator» [Komputerna programma dlya formuvannya psevdovipadkovih poslidovnostey chisel ta psevdovipadkovih bitovih poslidovnostey na osnovy klitinnyh avtomativ «Generator psevdosluchaynoy posledovatelynosty»], Svidoctvo pro reyestraciu avtorsykogo prava na tvir № 54179 vid 20.03.2014.

National Institute of Standards and Technology (2001), NIST SP 800-38A. Recommendation for block cipher modes of operation, 66 p.

Walker, J. (2008), A Pseudorandom Number Sequence Test Program, available at : http://www.fourmilab.ch/random/ (accessed 03 February 2015).

National institute of standarts and technology, Computer security division. Computer security resource center, available at : http://csrc.nist.gov/groups/ST/toolkit/rng/documentation_ software.html (accessed 20 February 2015).

Marsaglia, G., The Marsaglia Random Number CDROM including the Diehard Battery of Tests of Randomness, Department of statistics and supercomputer computations and research institute, available at : http://www.stat.fsu.edu/pub/diehard/ (accessed 15 March 2015).

Gerard van der Galiën, J. (2006), RABENZIX Randomness Test Suite. 5.4, available at : http://members.tele2.nl/galien8/rabenzix/rabenzix.html (accessed 15 March 2015).

Hamming, R. W. (1980), Coding and Information Theory, Englewood Cliffs NJ : Prentice-Hall, 60 p.

Knuth, D. E. (1969), The Art of Computer Programming, Vol. 2, Seminumerical Algorithms, Reading MA : Addison-Wesley, 784 p.




ISSN 2411-1031 (Print), ISSN 2518-1033 (Online)