International Journal of Computer Network and Information Security (IJCNIS)
IJCNIS Vol. 13, No. 6, 8 Dec. 2021
Cover page and Table of Contents: PDF (size: 641KB)
Generalized Galois-Fibonacci Matrix Generators Pseudo-Random Sequences
Full Text (PDF, 641KB), PP.57-69
Views: 0 Downloads: 0
Author(s)
Anatoly Beletsky
1,*
Index Terms
Generators of Pseudo-random Numbers, Linear Feedback Shift Registers, Galois and Fibonacci Matrices
Abstract
The article discusses various options for constructing binary generators of pseudo-random numbers (PRN) based on the so-called generalized Galois and Fibonacci matrices. The terms "Galois matrix" and "Fibonacci matrix" are borrowed from the theory of cryptography, in which the linear feedback shift registers (LFSR) generators of the PRN according to the Galois and Fibonacci schemes are widely used. The matrix generators generate identical PRN sequences as the LFSR generators. The transition from classical to generalized matrix PRN generators (PRNG) is accompanied by expanding the variety of generators, leading to a significant increase in their cryptographic resistance. This effect is achieved both due to the rise in the number of elements forming matrices and because generalized matrices are synthesized based on primitive generating polynomials and polynomials that are not necessarily primitive. Classical LFSR generators of PRN (and their matrix equivalents) have a significant drawback: they are susceptible to Berlekamp-Messi (BM) attacks. Generalized matrix PRNG is free from BM attack. The last property is a consequence of such a feature of the BM algorithm. This algorithm for cracking classical LFSR generators of PRN solves the problem of calculating the only unknown – a primitive polynomial generating the generator. For variants of generalized matrix PRNG, it becomes necessary to determine two unknown parameters: both an irreducible polynomial and a forming element that produces a generalized matrix. This problem turns out to be unsolvable for the BM algorithm since it is designed to calculate only one unknown parameter. The research results are generalized for solving PRNG problems over a Galois field of odd characteristics.
Cite This Paper
Anatoly Beletsky, "Generalized Galois-Fibonacci Matrix Generators Pseudo-Random Sequences", International Journal of Computer Network and Information Security(IJCNIS), Vol.13, No.6, pp.57-69, 2021. DOI: 10.5815/ijcnis.2021.06.05
Reference
[1] Schneier, B.: Applied cryptography, Second Edition: Protocols, Algorithms, and Source Code in C. John Wiley & Sons, New York (1996). — ISBN-13: 978-0471117094
[2] Chen, L., Gong, G.: Pseudo-random Sequence (Number) Generators, Communication Systems Security, Appendix A, (2008).
[3] Ivanov M. A. Cryptographic methods of information protection in computer systems and networks. M.: KUDITS-OBRAZ, 2001. – 386 р. (In Russia)
[4] Shear register with linear feedback, Wikipedia [online], Available at: https://ru.wikipedia.org/wiki/Registr_shift_with_linear_feedback.
[5] “Linear Feedback Shift Registers”, Wikipedia [online], Available at: http://homepage.mac.com/afj/lfsr.html.
[6] “Random number generation”, Wikipedia [online], Available at: http://en.wikipedia.org/wiki/
[7] Jun Choi, Dukjae Moon, Seokhie Hong and Jaechul Sung. The Switching Generator: New Clock-Controlled Generator with Resistance against the Algebraic and Side Channel Attacks. Entropy 2015, 17, 3692-3709; doi:10.3390/e17063692
[8] Beletsky A. Ya. Synthesis of Сryptoresistant Generators of Pseudorandom Numbers Based on Generalized Galois and Fibonacci Matrixes. // Radio Electronics, Computer Science, Control, (2019). Vol 3(50), pp. 86-98. (In Russia)
[9] Beletsky A. Ya. Synthesis, Analysis and Cryptographic Applications of Generalized Galois Matrixes – Group monograph: Information technology – Kharkiv, (2016). – P. 167-189. (In Russia)
[10] Beletsky A. Ya., Beletsky E. A. Generators of Pseudo Random Sequences of Galois. // Electronics and Control Systems, (2014, # 4(42). – P. 116-127. (In Russia)
[11] Mullajonov R. V. Reports of the National Academy of Sciences of Ukraine, 2009, №10. – P. 27-35. (In Russia)
[12] Gantmacher F. R. The Theory of Matrices.— AMS Chelsea Publishing: Reprinted by American Math. Society, (2000).— 660 p.— ISBN 0821813765.
[13] Berlekamp E. R. Algebraic Coding Theory, New York: McGraw-Hill, 1968. Revised ed., Aegean Park Press, 1984, ISBN 0-89412-063-8
[14] Blahut R. E. Theory and Practice of Error Control Codes. — Addison-Wesley Publishing Company Reading, (1984). — 500 p.
[15] Lidl, R., Niederreiter, H., Finite Fields, Cambridge University Press (1996)
[16] Peterson, W.W., Weldon, E.J., Jr. Error Correcting Codes, MIT press, Cambridge, MA (1972).
[17] Fomichev V. M. Discrete Mathematics and Cryptology. — M.: Dialogue-MIFI, (2013). — 397 p. — ISBN 978-5-86404-185-7 (In Russia)