SYNTHESIS OF СRYPTORESISTANT GENERATORS OF PSEUDORANDOM NUMBERS BASED ON GENERALIZED GALOIS AND FIBONACCI MATRIXES
DOI:
https://doi.org/10.15588/1607-3274-2019-3-10Keywords:
Irreducible polynomials, primitive matrixes, Galois fields, linear shift registers, pseudorandom number generatorsAbstract
Context. The problem to form generalized primitive matrixes on the Galois and Fibonacci any order over the field characteristics2 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.
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
How to Cite
Issue
Section
License
Copyright (c) 2019 A. Ya. Beletsky
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.
Creative Commons Licensing Notifications in the Copyright Notices
The journal allows the authors to hold the copyright without restrictions and to retain publishing rights without restrictions.
The journal allows readers to read, download, copy, distribute, print, search, or link to the full texts of its articles.
The journal allows to reuse and remixing of its content, in accordance with a Creative Commons license СС BY -SA.
Authors who publish with this journal agree to the following terms:
-
Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License CC BY-SA that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
-
Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
-
Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work.
