AUTHORS: Stepan Bilan, Mykola Bilan, Sergii Bilan

Download as PDF

ABSTRACT: In this paper, three pseudorandom number generators are considered which are built on asynchronous cellular automata with several active cells that form additional active cells in the field of the cellular automaton. The paper describes pseudo-random number generators based on an asynchronous cellular automaton with one, two and three active cells. Such generators use cellular automata in which each active cell performs two local functions. One local function calculates the state of the cell in the next time step, and the second local function determines the active cell at the next time step. The results of testing all the generators using graphical tests are presented. The tests allow detection of generator defects for different local transition functions. The paper also considers the method of formation of new active cells by two initial active cells. New active cells are formed as a result of the combining of the initial two active cells in one cell of cellular automata. In this case, each additionally formed active cell performs another local transition function that differs from the local transition functions of the previous active cells. The use of additional active cells allows to improve the quality of work of generators based on two-dimensional asynchronous cellular automata. The high quality of the pseudo-random number generator is proved by the used graphic tests.

KEYWORDS: Asynchronous cellular automata, pseudorandom number generator, tests, cell, neighborhood of cells, local transition function, active cell

REFERENCES:

[1] Bruce Schneier. Applied Cryptography, Second Edition: Protocols, Algorthms, and Source Code in C, Wiley Computer Publishing, John Wiley & Sons, Inc,. 784, 1996.

[2] S. Bilan, M. Bilan, S. Bilan, Novel pseudorandom sequence of numbers generator based cellular automata. Information Technology and Security, Vol. 3(1), 2015, pp. 38-50.

[3] Wolfram S., Cellular automata. Los Alamos Science, Vol. 9, 1983, pp. 2-21.

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

[5] Wolfram S., Random Sequence Generation by Cellular Automata, Advances in Applied Mathematics, vol. 7, 1986, pp. 429 – 432.

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

[7] Bruno Martin, Patrick Sole, Pseudo-random Sequences Generated by Cellular Automata, International Conference on Ralations, Orders and Graphs: Interaction with Computer Scince, May 2008, Mandia, Tunisia, Nouha editions, 2008, pp. 401-410.

[8] K. Cattell, J. C. Muzio, Synthesis of onedimensional linear hybrid cellular automata, IEEE Trans. On Computer-aided design of integrated circuits and systems, 15(3), 1996, pp. 325-335.

[9] K. Bhattachrjee, D. Paul, S. Das. Pseudorandom Pattern Generation Using 3-State Cellular Automata. In: EI Yacoubi S., Was J., Bandini S. (eds). Cellular Automatar. ACRI 2016. Lect. Not. in Comp. Scien. 9863, 2016, pp. 3-13.

[10] G. Sh. Sirakoulis. Parallel Application of Hybrid DNA Cellular Automata for Pseudorandom Number Generation. JCA. Vol. 11(1), 2016, pp. 63-89.

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

[12] S. Bilan, M. Bilan, R. Motornyuk, A. Bilan, S. Bilan, Research and Analysis of the Pseudorandom Number Generators Implemented on Cellular Automata, WSEAS TRANS. on SYS., Vol. 15, 2016, pp. 275 - 281.

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

[14] Suhinin B.M., High generators of pseudorandom sequences based on cellular automata, Applied discrete mathematics, № 2, 2010, pp. 34 – 41.

[15] Suhinin B.M., Development of generators of pseudorandom binary sequences based on cellular automata, Science and education, № 9, 2010, pp. 1 – 21.

[16] David H. K. Hoe, Jonathan M. Comer, Juan C. Cerda, Chris D. Martinez, Mukul V. Shirvaikar, Cellular Automata-Based Parallel Random Number Generators Using FPGAs. International Journal of Reconfigurable Computing, Vol. 2012, 2012, pp. 1-13, Article ID 219028

[17] S. Bilan, M. Bilan, R. Motornyuk, A. Bilan, S. Bilan, Designing of the Pseudorandom Number Generators on the Basis of TwoDimensional Cellular Automata, Applied Physics, System Science and Computers. Proceedings of the 1st International Conference on Applied Physics, System Science and Computers (APSAC2016), September 28– 30, Dubrovnik, Croatia. Lecture Notes in Electrical Engineering. Vol. 428. Springer International Publishing AG 2018, pp. 137-143.

[18] S. Bilan, O. Levchuk. Research of pseudorandom number generator based on asynchronous cellular automaton. Collection of scientific works of SETUT Series 'Transport systems and technologies', Vol. 30, 2017. pp. 184-190.

[19] Marsaglia G., Random number generators. Journal of Modern Applied Statistical Methods, Vol. 2, 2003, pp. 2-13.

[20] Chugunkov E.V., Methods and tools to evaluate the quality of pseudo-random sequence generators, focused on solving problems of information security, Textbook. M.: NEYAU MIFI, 236, 2012.