WSEAS Transactions on Computers
Print ISSN: 1109-2750, E-ISSN: 2224-2872
Volume 22, 2023
Variety of Matrix Galois-like Generators Pseudorandom Number Free from the Berlecamp-Messy Attack
Author:
Abstract: Classical pseudorandom numbers generators (PRN) based on Galois and Fibonacci schemes are constructed, as a rule, using n-bit linear shift registers or corresponding n-order matrices and allowing both hardware and software implementation. The main disadvantage of such generators is their low crypto stability, the reason for which is that if by any means it is possible to obtain 2n bits of the generated sequence taken from any discharge of the generator, then with the help of the Berlecamp-Messy algorithm, it is possible to recover a primitive polynomial of n-degree $$f_{n}$$, generating the generator. To increase the cryptostability of the PRN matrix generators is proposed to replace the classical Galois and Fibonacci matrices, uniquely determined by the primitive polynomial $$f_{n}$$, at a fixed forming element $$ω$$, equal to 10, by the so-called generalized Galois or Fibonacci matrices. A distinctive feature of generalized matrices is that the polynomials $$f_{n}$$ generating them need not be primitive. At the same time, the constituent elements must be chosen from the subset of primitive elements of the deduction field generated by the polynomial $$f_{n}$$. The generalized PRN generators are free from the Berlecamp-Messy attack. The latter property is obtained because the Berlecamp-Messy algorithm solves the problem of computing one single unknown - the primitive polynomial $$f_{n}$$, generating the generator. For variants of generalized matrix generators of PRN, there is a need to determine two unknown parameters: both the irreducible polynomial $$f_{n}$$ and the forming element $$ω$$, jointly generating the generalized matrix, which turns out to be an unsolvable problem for the Berlecamp-Messy algorithm.
Search Articles
Pages: 190-197
DOI: 10.37394/23205.2023.22.22