SYNTHESIS OF СRYPTORESISTANT GENERATORS OF PSEUDORANDOM NUMBERS BASED ON GENERALIZED GALOIS AND FIBONACCI MATRIXES

Authors

  • A. Ya. Beletsky National Aviation University, Ukraine

DOI:

https://doi.org/10.15588/1607-3274-2019-3-10

Keywords:

Irreducible polynomials, primitive matrixes, Galois fields, linear shift registers, pseudorandom number generators

Abstract

Context. The problem to form generalized primitive matrixes on the Galois and Fibonacci any order over the field characteristics
2 for the construction by the generators gamma functions for cryptographically stable algorithms of inline data encryption, free from the attack of Berlekamp-Messi (BM).
Objective. Development of a way to eliminate the threat an attack using the BM algorithm on LFSR-generators of pseudorandom
numbers (PRN) to increase their crypto stability.
Method. Linear Feedback Shift Registers (LFSR) are themselves good pseudorandom PRN generators, but they have undesirable
properties that reduce the efficiency of their use. For the registers of length shift n their internal state is a function of the previous
output bits of the generator. Even if the feedback scheme is kept the secret, it can be determined by 2n output bits of the generator with the help of BM algorithm, which reduces the crypto-resistance of the generator PRN. The basis for single loop feedback circuits, which cover the classical LFSR-generators of PRN, are primitive polynomials.
There are various ways to increase the crypto-resistance of LFSR-generators. To their number concern: introduction of nonlinear
transformations, use poly register generators (as, for example, in the algorithm of encryption А5) and several others. The transition from classical LFSR-generators to generators basis on the generalized matrixes of Galois and Fibonacci leads to the fact that the algorithm of BM loses the ability to determine the unattainable polynomials generating multi-circuit feedback circuits in LFSRgenerators. The reason for this feature is that the series of bits generated by the generalized generator becomes dependent not only on the selected irreducible polynomial but also on the primitive element that participates in the creation of the feedback loop generator.
Results. The PRN generators developed by LFSR were used to organize bytes of streaming information encryption.
Conclusions. Statistical tests of the proposed PRN generators carried out with the help of NIST STS, and Diehard [16–18] packages
have confirmed the high quality of the generated sequences. Moreover, the generators turned out to be cryptographically resistant
to BM attacks. The use of these generators in the formation of long keys, necessary, for example, in RSA encryption protocols
and other applications is promising. As an area of further researches, development of the generalized generators of PRN above a field of Galois of any characteristic.

Author Biography

A. Ya. Beletsky, National Aviation University

Dr. Sc., Professor, Professor of the Department of Electronics

References

Schneier B. Applied Cryptography, Second Edition: Protocols, Algorithms, and Source Code in C. New York, John Wiley & Sons, 1996, 758 p. ISBN-13: 978-0471117094

Lidl R., Niederreiter H. Finite Fields. Cambridge, University Press, 1996, 407 p. ISBN 0-521-30706-6

Knuth D. E. The Art of Computer Programming: Fundamental Algorithms. Massachusetts, England, 1997, 762 p. ISBN 0-201-89683-4

Knuth D. E. The Art of Computer Programming: Seminumerical Algorithms. Massachusetts, England, 1997, 832 p. ISBN 0-201-89684-2

Peterson W. W., Weldon E. J. Error Correcting Codes MIT Press, Cambridge, 1972, 560 p. ISBN: 9780262160063

Chen L., Gong G. Pseudorandom Sequence (Number) Generators, Communication Systems Security, Appendix A, 2008, P. 750. ISBN 9781439840368

Ivanov M. A., Chugunkov I. V. Theory, application and evaluation of the quality of the pseudorandom generators. Moscow, KUDITZ-OBRAZ, 2003, 240 p. ISBN 5-93378-056-1

Fomichev V. M. Discrete mathematics and cryptology. Moscow, Dialogue-MIFI, 2013, 397 p. ISBN 978-5-86404-185-7

Shear register with linear feedback [Electronic resource] – Access mode: https://ru.wikipedia.org/wiki/Registr_shift_with_linear_feedback

Linear Feedback Shift Registers [Electronic resource] – Access mode: http://homepage.mac.com/afj/lfsr.html.

Random number generation [Electronic resource] – Access mode: http://en.wikipedia.org/wiki/Random_wikin umber_generation.

Beletsky A. Ya., Beletsky E. A. Generators of pseudorandom sequences of Galois, Electronics and Control Systems, 2014, No. 4(42), pp. 116–127.

Beletsky A. Ya. Synthesis, analysis and cryptographic applications of generalized Galois matrixes – Group monograph, Information technology. Kharkov, 2016, pp. 167–189.

Berlekamp E. R. Math. Comp., 1970. V. 24, pp. 713–735.

Hardware generator of random numbers GSCH-6. [Electronic resource]. Access mode: http://tegir.ru/ml/k66.html.

Anderson R. J. On Fibonacci Keystream Generators [Electronic source]. Access mode: http://www.iacr.org/cryptodb/data/paper.php?pubkey=2963.

NIST Statistical Test Suite. [Electronic resource]. Access mode: http://csrc.nist.gov/groups/ST/toolkit/rng/ documentation_software.html.

Marsaglia G. DIEHARD Statistical Tests. [Electronic resource]. Access mode: http://stat.fsu.edu/~geo/diehard.html.

Rukhin A., Soto J. A Statistical Test Suite for Random and Pseudorandom Number Generators for Cryptographic Applications [Electronic resource]. Access mode:http://csrc.nist.gov/publications/nistpubs/800-22-rev1a/SP800-22rev1a.pdf.

Golomb S. W. Shift register sequences. San Francisco, HoldenDay, 1967, 247 p.

Downloads

Published

2019-10-01

How to Cite

Beletsky, A. Y. (2019). SYNTHESIS OF СRYPTORESISTANT GENERATORS OF PSEUDORANDOM NUMBERS BASED ON GENERALIZED GALOIS AND FIBONACCI MATRIXES. Radio Electronics, Computer Science, Control, (3), 86–98. https://doi.org/10.15588/1607-3274-2019-3-10

Issue

Section

Progressive information technologies