Generalized Galois and Fibonacci Matrices in Cryptographic

Applications

ANATOLY BELETSKY

Department of Electronics

National Aviation University,

Kyiv-03058, av. Kosmonavt Komarov, 1,

UKRAINE

Abstract: The terms of the Galois matrices

G

, as well as those bijectively associated with them the Fibonacci

matrices

F

connect by the operator of the right-hand transposition (that is, transposition to the auxiliary

diagonal), are borrowed from the theory of cryptography, in which generators of pseudorandom number (PRN)

widely use according to Galois and Fibonacci schemes (in configuration). A distinctive feature of both the

G

and

F

matrices is that the identical binary sequences can programmatically calculate the sequences formed by

the PRN generators. The latter's constructions are based on linear feedback shift registers, implemented by

software or hardware methods in Galois and Fibonacci architecture. The proposed generalized Galois matrices,

discussed in the Chapter, significantly expand the variety of PRN generators. That is achieved both by increasing

the number of generating elements



(in the classical version used a single element

 =

) and since generalized

generators can construct not only using PRN but also polynomials, not necessarily (as in classical generators),

which are primitive. The listed features of generalized Galois matrices provide PRN generators with significantly

higher cryptographic security than generators based on conventional matrices.

Key-Words: generators of pseudorandom numbers, linear feedback shift registers, Galois and Fibonacci matrices,

Berlekamp–Massey algorithm.

Received: April 15, 2021. Revised: January 5, 2022. Accepted: January 25, 2022. Published: February 7, 2022.

1 Introduction

In the theory and practice of cryptographic

information protection, one of the most critical

problems is constructing generators of

pseudorandom numbers (PRN) of the maximum

length (period) with good statistical properties.

There are two main types of PRN generators built

using hardware or software. The first class of

generators is made based on linear feedback shift

registers (LFSR) in Galois or Fibonacci

configurations (according to schemes) [1, 2]. The

structural-logic diagrams of classical LFSR

generator's PRN are uniquely defined by their

generating primitive polynomials (PrP), through

which the single-loop feedbacks in the shift registers

are established [3, 4]. The software-implemented

PRN generators, which make up the second class of

generators, can also be built based on LFSR.

This Chapter focuses on constructing generalized

matrix PRN generators in Galois and Fibonacci

configurations [5, 6]. The terms of the Galois matrix

G

and those objectively associated with them by the

operator of the right-hand transposition (i.e.,

transposition to the auxiliary diagonal [7]) of the

Fibonacci matrix

F

borrowed from cryptography

theory. The Galois and Fibonacci matrices will be

called PRN generators.

In addition to the named base (initial) matrices

G

and

F

, the so-called conjugate matrices



G

and



F

introduce in the Chapter, which forms by the

classical (left-sided) transposition to the main

diagonal of the corresponding initial matrices. For

simplicity, the set of matrices

 

, , ,



=Q G F G F

, which does not lead to

ambiguity, will be called "Galois matrices". All

Galois matrices can obtain by linear transformations

of the left-sided and right-sided transposition of the

Frobenius [8] standard form:

0

1

2

1

0 0 0

1 0 0

0 1 0

0 0 1

n

c

c−

−





−



−

=



−





,

(1)

called in linear algebra the accompanying matrix of

the unitary polynomial

WSEAS TRANSACTIONS on CIRCUITS and SYSTEMS

DOI: 10.37394/23201.2022.21.1

Anatoly Beletsky

E-ISSN: 2224-266X

1

Volume 21, 2022

11

1 1 0

( ) ,

( ).

n n k

k

x x c x c x c x c

c GF p

−

 = + + + + +



The possibilities of using Frobenius matrices (1)

for constructing a PRN generator based on the

following properties

n



. First, if as a polynomial

()

nx

we choose a unitary irreducible polynomial

n

f

, represented by its vector form (by the set of

polynomial coefficients)

1 2 1 0

( ) 1 ,

( ) mod ,

n n n n k

kk

xf

cp

    



−−

  =

=−

then the matrix

n



goes into the Fibonacci matrix

0

1

2

1

0 0 0

1 0 0

0 1 0

0 0 1

n



−





=





F

.

(2)

And secondly, matrix (2) generates a linear

recurrent

m−

sequence

01

, , ,

k

  

by

transforming

1 ( 1)

1 2 ( 1)

()

p

k k k n n

k k k n k n

  

   

+ + −

+ + + − +

=

=

F

,

(3)

for all

0k

.

Let's pay attention to that recursion feature (3).

All high elements

1 2 ( 1)k k k n

  

+ + + −

of the output

vector

out

V

are contained in the set of components of

the input vector

in 1 ( 1)k k k n

  

+ + −

=

V

. The only

unknown part

kn



+

of the vector

out

V

determined,

according to relations (2), (3), by the scalar product

of vectors

in

V

and

0 1 2 1k n n

    

−−

=

A

, i.e.

0 1 1

11

(

) mod

k n k k

k n n p

    



++

+ − −

= + +

+

.

(4)

Calculating a sequence of vectors

out

V

will be

formative to illustrate the fourth-order Fibonacci

matrix

4

F

generated by the binary PrP

410011f=

4

0 0 0 1

1 0 0 1

0 1 0 0

0 0 1 0





=





F

,

(5)

generated by the binary PrP

410011f=

. As the

initialization vector, let us designate it as

n

V

, on the

left side of the expression (3), you can choose any

non-zero binary vector of the fourth-order. Let this

be the vector

41011=V

. The calculation results by

formulas (3)-(5) of the recursive sequence are

summarized in Table 1.

Table 1. The sequence of the state of the Fibonacci

PRN generators generated PrP

410011f=

Step

(k)

The elements of

out

V

Step

(k)

The elements of

out

V

0

1

2

3

0

1

2

3

0

1

0

1

8

1

0

1

0

1

0

9

0

1

2

0

1

0

1

10

0

1

0

3

1

0

1

11

0

1

0

4

0

1

12

1

0

1

5

1

13

0

1

6

1

0

14

0

1

0

7

1

0

15

1

0

1

The shading in Table 1 highlights the vector that

coincides with the initialization vector. The number

of non-repeating non-zero vectors generated by the

Fibonacci generator turned out to be 15, as it should

be for the selected parameters of the generation.

The vast majority of the generators of PRN are

based on LFSR [9]. The main requirement for LFSR

generators in cryptographic applications is to

generate a sequence of cipher bits of maximum

length (period). Its knowns that LFSR is a maximum

period shift register if the corresponding feedback

polynomial is primitive.

Along with LFSR generators, can use PRN

generators based on shift registers with generalized

feedback. Such generators include the Mersen

vortex [10], which contains a modified Frobenius

WSEAS TRANSACTIONS on CIRCUITS and SYSTEMS

DOI: 10.37394/23201.2022.21.1

Anatoly Beletsky

E-ISSN: 2224-266X

2

Volume 21, 2022

matrix. Unfortunately, matrix PRN generators are

not yet widely used in cryptography. Classic

generators (both matrix and LFSR) do not provide

the required level of cryptographic security. The

noted disadvantage is that the output serial bits of the

generator by the Berlecamp-Massey algorithm can

be uniquely defined primitive polynomial, which

generates the matrix of the PRN generator. And as a

consequence, the generator turns out to be cracked

[11].

The main task of this study is to develop PRN

generators of the maximum period based on

generalized Galois matrices in the general case over

fields of arbitrary characteristics

p

, free from the

Berlecamp-Massey attack.

2 Galois Сlassical Hardware and

Matrix Generators PRN

Definition 1. To subset of classical PRN generators

of the maximum period will include generators built

based on linear shift registers covered by single-loop

feedback, which is exclusively a function of a

primitive polynomial that plays the role of a

generator polynomial.

Usually, D-triggers are used as LFSR bits. An

example of a fourth-order Galois generator,

feedbacks in which fourth-degree PrP

410011f=

formed, is shown in Fig. 1. Using Fig. 1, let us

develop a mnemonic rule for constructing classic

LFSR generators in the Galois configuration. For

this purpose, we will supplement the drawing with

dotted strokes, placing them on those parts of the

circuit in which there are no XOR operators.

Fig. 1. Block diagram of the PRN generator

in the Galois configuration generated by PrP

410011f=

Then we put numbers 1 above the solid vertical

lines (feedback lines) and numbers 0 above the

dashed lines. Finally, we come to Fig. 2.

Fig. 2. To build a block diagram fourth-order

Galois generator

As follows from Fig. 2, the ones of the primitive

polynomial in vector form predetermine the position

of the vertical lines in a single-loop feedback circuit

in the classical LFSR Galois PRN generator.

Will illustrate the technology of applying

formulated rules for drawing up a block diagram of

the PRN generator of the maximum period in the

Galois configuration will be illustrated by

constructing a generator circuit generated by a PrP

of the eighth-degree

8101100101f=

. The solution

to this problem involves the implementation of two

stages of synthesis.

Stage 1. Form an eight-bit ring shift register (Fig.

3), in the nodes of the feedback line of which we

equidistantly arrange the coefficients of the selected

primitive polynomial

Fig. 3. To the construction of an eight-bit Galois generator circuit

Stage 2. Connecting, as shown in Fig. 4, the

internal nodes of the feedback line, above which

there are coefficients 1, with the XOR operator, we

complete the construction of the classical LFSR

Galois generator.

Fig 4. Block diagram of the Galois generator, generated PrP

8101100101f=

Similarly, by steps 1 and 2, it is possible to

construct the block diagram of the classical LFSR

generators in the Galois configuration for an

arbitrary degree of the primitive polynomial that

forms a feedback loop in the generator register.

Classical Fibonacci LFSR generators PRN created

from Galois generators by rotating the feedback loop

relative to the vertical and horizontal axes. At the

same time, the numbering of the shift register cells

remains unchanged (Fig. 5).

WSEAS TRANSACTIONS on CIRCUITS and SYSTEMS

DOI: 10.37394/23201.2022.21.1

Anatoly Beletsky

E-ISSN: 2224-266X

3

Volume 21, 2022

Fig 5. Block diagram of the Fibonacci generator, generated PrP

8101100101f=

Each LFSR generator (Galois or Fibonacci)

corresponds to uniquely associated with the

matrices, which we will denote by

G

and

F

,

respectively. A distinctive feature of the Galois and

Fibonacci matrices is that it is possible to generate

binary series similar to the

m−

sequences formed by

the classical LFSR generators on their basis.

Let be

()Sk

— the state vector of the

n−

discharge PRN generator in the Galois configuration

after the

k

sync pulse (at the

k

step of the register

shift), the calculation scheme of which is

represented by the matrix expression

()

bit

( 1) ( ) , 0,1, ,

(0) 00 01

n

f

n

S k S k k

S

+ =  =

=

G

.

(6)

Our task is to calculate the Galois matrix for a

given PrP

1 2 1

11

n n k

f−−

=    

,

 

(2) 0,1

kGF=

, with the help of which relation

(6) forms the same sequence of pseudorandom

numbers as the LFSR generator. Let us try first to

deal with this problem for small orders of matrices.

Then, let us turn to the analysis of the state of the

triggers of the PRN generator (Fig. 6), previously

shown in Fig. 1.

Fig. 6. Initial state illustration Generator

PRN, according to Galois scheme

The numbers placed above the generator bits

characterize the logic level of the signal at the output

of the corresponding cell (trigger) of the register. As

shown in Fig. 7, using sync pulses, 1 from the least

significant bit of the register moved to its most

essential bits.

From Fig.7, it follows that after the third

synchrotact, logical ones arrive at the inputs of both

the first and second flip-flops and, therefore, at the

fourth step of the PRN generation (Fig. 8) appear at

the outputs of these triggers.

a)

b)

c)

Fig. 7. PRN generator states after:

a) - the first, b) - the second, c) - the third

synchro tact

Fig. 8. State of the PRN generator after the

fourth synchro title

Let us compose a matrix

(4)

13

G

from a set of state

vectors

()Sk

, into which the Galois generator passes

after the first four synchronizations, placing the

vectors in the matrix, starting from its bottom row

1i=

.

(4)

13

0 0 1 1 4

1 0 0 0 3

.

0 1 0 0 2

0 0 1 0 1

4 3 2 1

i

j











=G

,

(7)

Note that index 13 in the notation of the matrix

()n

f

G

in (7) is the hexadecimal notation of PrP

410011f=

. We will continue to use the same form

of presentation of the numerical values of the degree

of polynomials in the future.

Thus, firstly, the matrix (7), when substituted into

relation (6), forms a sequence of four-bit codes

(Table 2), which include the multiplicative group of

the field generated by PrP

410011f=

.

WSEAS TRANSACTIONS on CIRCUITS and SYSTEMS

DOI: 10.37394/23201.2022.21.1

Anatoly Beletsky

E-ISSN: 2224-266X

4

Volume 21, 2022

Table 2. The sequence of the state of the PRN

generator from PrP

410011f=

Step

(k)

LRS discharges

Step

(k)

LRS discharges

4

3

2

1

4

3

2

1

0

1

8

0

1

0

1

0

1

0

9

1

0

1

0

2

0

1

0

10

0

1

3

1

0

11

1

0

4

0

1

12

1

5

0

1

0

13

1

0

1

6

1

0

14

1

0

1

7

1

0

1

15

0

1

6

1

0

14

1

0

1

7

1

0

1

15

0

1

6

1

0

14

1

0

1

7

1

0

1

15

0

1

And secondly, the top row of the matrix (7) is

nothing but the fourth degree PrP

410011f=

, in

which the leading unit remove, and the left element

of the truncated polynomial is the coefficient

1n



−

.

Based on the analysis of the matrix

(4)

13

G

in (7),

we arrive at the following construction rule

(synthesis algorithm) of the classical Galois matrix

(CGM)

()n

f

G

of the order

n

generated by a primitive

polynomial

n

f

of degree

n

.

Algorithm for the synthesis of CGM: let

n

f

–

a primitive binary polynomial of degree

n

and

 =

– the minimal primitive element of the field

(2 )

n

GF

, generated by the polynomial

n

f

. Place



in the lower right corner of the generated Galois

matrix

()n

f

G

. All other digits of the bottom line

()

,

n

f

G

located to the element's left



, are filled with zeros.

Suppose the stage of formation of the next row its

senior 1 goes beyond the left boundary of the matrix.

In that case, the polynomial in this row reduces to

the remainder modulo

n

f

. Thus, the row returns to

the matrix, and the formation process of

()n

f

G

continues further.

The right-hand side of the matrix (2) can

represent in a more compact form [8]:

()n

f



=



0

GE

◀

,

(8)

where

E

is the identity matrix of the

( 1)n−−

order,

the

−0

zero column vector of length

( 1)n−

, and

◀

— the pointer of the position of the highest PrP

n

f

coefficient

1n



−

.

2 3 2 1

()

1

2

3

2

1

0 0 0 0

0 0 0 0 0

0 0 0 0

1 2 3 2 1

nn

n

f

nn

n

n n n

−−

−

=







−−

α α α α 1

10

0

10

α

G

.

(9)

In matrix (9), for clarity, the elements of the main

diagonal of the identity matrix

E

and the bordering

elements of this matrix are highlighted in bold (on

the right – the zero column

0

, and on top – the row,

which is a primitive polynomial

n

f

reduced by one

digit on the left).

Compact forms of Fibonacci matrices

()n

f

F

are

interconnected with Galois matrices

()n

f

G

in

configuration (8) by the operator of right-hand

transposition

( ) ( )nn

ff

f

⊥

⎯→ = 





GF

E▼

,

(10)

where



— is the zero-row vector of the

( 1)n−−

order.

Let us give expressions for the

G

and

F

matrices of the eight-order.

WSEAS TRANSACTIONS on CIRCUITS and SYSTEMS

DOI: 10.37394/23201.2022.21.1

Anatoly Beletsky

E-ISSN: 2224-266X

5

Volume 21, 2022

0 1 1 0 0 1 0 1 8

10000000 7

01000000 6

00100000 5

00010000 4

00001000 3

00000100 2

00000010 1

8 7 6 5 4 3 2 1

i

j

=







G

,

00000001 8

10000000 7

0 1 0 0 0 0 0 1 6

00100000 5

00010000 4

0 0 0 0 1 0 0 1 3

0 0 0 0 0 1 0 1 2

00000010 1

8 7 6 5 4 3 2 1

i

j

=







F

.

(11)

Structural-logic diagrams of Galois and

Fibonacci LFSR generators, corresponding to

relations (1)), are shown above in Figures 4 and 5,

respectively. Supplementing the symbolic forms (8),

(10) of the Galois

G

and Fibonacci

F

matrices with

the corresponding conjugate matrices



G

and



F

formed by the left-hand transposition of the base

matrices,

( ) ( )

T

ff



⎯→ =



   

=

   

   



0



G F G F

EE▲

▶

,

(12)

we arrive at the interconnection scheme (Fig. 9) of

the subset of matrices, which we denote

 

, , ,



=Q G F G F

.

Fig. 9. The diagram of the relationship between

primary and adjoint Galois and Fibonacci

matrices

The conjugate eighth-order Galois



G

and

Fibonacci



F

matrices generated by

transformations (12) of matrices (11) have the form:

01000000 8 01000000

10100000 7 00100000

10010000 6 00010000

00001000 5 00001000

00000100 4 00000100

10000010 3 00000010

00000001 2 00000001

1 0 0 0 0 0 0 0 1 1 0 1 0 0 1 1 0

8 7 6 5 4 3 2 1

;



   

   



   

==

   

  

   

GF

8

7

6

5

.

4

3

2

1

8 7 6 5 4 3 2 1



(13)

LFSR generators PRN, corresponding to matrices (13), are shown in Fig. 10.

Fig. 10. Block diagrams of coupled PRN generator in configurations

Galois

)a

and Fibonacci

)b

generated by PrP

8101100101f=

WSEAS TRANSACTIONS on CIRCUITS and SYSTEMS

DOI: 10.37394/23201.2022.21.1

Anatoly Beletsky

E-ISSN: 2224-266X

6

Volume 21, 2022

The term "feedback loop" in PRN generators can

explain by their stylized graphical representation in

Fig. 11. The PrP

8101100101f=

take as the

generating polynomial.

Fig. 11. A stylized representation of feedback schemes in PRN generators

Let's pay attention to such peculiarities of

feedback. If the feedback loops of generators

G

and

F

wound clockwise, those of generators



G

and



F

wound counterclockwise. This fact can also be

a sense in the block diagrams of the PRN generators

shown in Figures 4, 5, and 10. The ways of

transforming LFSR loops of PRN generators are

present in Table 3. The table elements contain

operators of loops rotation:



— relative to the

vertical axis of symmetry and — relative to the

horizontal axis of symmetry.

Table 3: Relationship of

 

Q

LFSR feedback loops

G

F



G



F

G

–



F



–





G



–





F



–

3 Efficient Algorithms for Calculating

the States of Classical Matrix Galois

The algorithm's complexity for assessing the state of

any of four PRN generators shown in Figure 9 is,

according to relation (1), is

2

()On

, i.e., increases in

quadratic dependence on the order of the classical

Galois matrices. Based on the structures of the CGM

(due to their components — the unit matrices

E

of

( 1)n−−

order), it is possible to significantly reduce

the computer time spent on assessing the state of the

PRN generators at the next

( 1)k+

computation step.

For simplicity, let us introduce a notation system

somewhat different from the one used earlier,

assuming:

 

1 2 1 0

, , , ,

k n n

V v v v v

−−

=

— the PRN

vector at the

k

generation step, in the curly brackets

of which the binary components of the vector

indicated;

 

1 1 0

1, , , , 1

n n n

f−

=  =    =

—

primitive polynomial generating CGM. The final

relations that determine the vectors

1k

V+

for various

CGMs summarize in Table 4. The arrows in Table

2, located to the right of the column vectors

n

f

and

k

V

, indicate the location of their senior element, and

 

01

, , ,

nn

f=   

.

Table 4. State vectors of classical matrix PRN generators

Matrices

Galois

1k

V+

Matrices

Fibonacci

1k

V+

G

10

1

1 bit

\,,

\

n n n

n

kn

n

vf v

V

−

  



F

( )

1

1 bit 1 bit

\,

k n k n

n

V v V f

−

   



G

( )

0

1 bit

,\

k n k

n

V f V v

−

   



F

0

00

1 bit

,\,

\

k

nn

n

V

vvf

v

−

  

WSEAS TRANSACTIONS on CIRCUITS and SYSTEMS

DOI: 10.37394/23201.2022.21.1

Anatoly Beletsky

E-ISSN: 2224-266X

7

Volume 21, 2022

Let us confirm the correctness of the expressions

given in Table 4. For example, let us calculate the

vector

1k

V+

for the matrix

G

. Let us write the

general relation

()

1

n

k k f

VV

+=G

.

(14)

Substituting matrix (9) into (14), we have

1 2 3 2 1

1 1 2 1 0

0 0 0 0

( , , , , )

0 0 0 0 0

0 0 0 0

n n n

k n n

V v v v v

− − −

+ − −





=





α α α α α 1

10

0

10

.

(15)

From formula (15), we uniquely arrive at the

value of the vector-row, which locates at the

intersection of row

G

and column

1k

V+

of Table 3.

Similarly, expressions can determine for the

remaining cells of Table 4.

Following the analysis of Table 4, we conclude

that the proposed algorithm formation of the PRN is

much simpler than those stated above. However,

their computational complexity is

()On

, i.e.,

linearly depends on the order of Galois matrices

forming generators of binary pseudorandom

sequences.

4 Generalized Binary Hardware and

Matrix PRN Generators

Definition 2. To the subset of generalized maximum

period PRN generators, we will refer generators

based on LFSR, covered by a multi-loop feedback

circuit, which depends on the generating polynomial

n

f

(not necessarily primitive) and the generating

element

 

. One should choose a primitive

element



of the Galois field

(2 )

n

GF

produced by

an irreducible polynomial (IP)

n

f

as a generating

element.

The Galois matrix

()

,

n

f

G

, which use to

programmatically form the same PRN as the

sequence generated by the generalized LFSR

generator, is called the generalized Galois matrix

(GGM). Matrices synthesized by the rule similar to

the regulation of CGM synthesis outlined in Section

2. Namely

Algorithm for the synthesis of GGM: Let

n

f

–

an irreducible (not necessarily primitive) binary

polynomial of degree

n

and

 

– the primitive

element of the field

(2 )

n

GF

, generated by the

polynomial

n

f

. Place



in the lower right corner of

the generated Galois matrix

()

,

n

f

G

. All other digits of

the bottom line

()

,

n

f

G

, located to the element's left



, are filled with zeros. Suppose that on the stage of

formation of the following matrix row, its senior unit

goes beyond the left boundary of the matrix. In that

case, the polynomial located in this row gives by the

remainder modulo

n

f

. Thus, the row returns to the

matrix, and the formation process

()

,

n

f

G

continues

further.

Let us consider examples of synthesis of a subset

of primitive generalized Galois and Fibonacci

matrices

 

, , ,

g g g g g



Q G F G F

and build on their

basis the PRN generators of the maximum period.

First, let's choose an irreducible binary polynomial

of the fourth-degree

411111f=

, which is not

primitive, and a primitive forming element (FE)

equal to 111. Then, the matrices corresponding to

the selected parameters have the form:

The block diagram of the generalized four-bit

Galois generator corresponding to the GGM

g

G

shows in Fig. 12. The vertically arranged registers of

the generators, marked at the top by the symbol



,

implement the operation of bitwise multiplication.

In the registers is a saving symbol



— a function

of adding the contents of the register modulo 2.

WSEAS TRANSACTIONS on CIRCUITS and SYSTEMS

DOI: 10.37394/23201.2022.21.1

Anatoly Beletsky

E-ISSN: 2224-266X

8

Volume 21, 2022

0 1 1 0 1 0 1 0

0 0 1 1 1 1 1 1

;;

1 1 1 0 1 1 0 1

0 1 1 1 0 1 0 0

0 0 1 0 1 1 1 0

1 0 1 1 0 1 1 1

;.

1 1 1 1 1 1 0 0

0 1 0 1 0 1 1 0

gg



   

   

==

   

   

   

   

==

   

   

GF

(16)

Fig. 12. Block diagram of the basic generalized Galois generator

Replacing in Figure 12 the contents of the cells

of the vertical feedback registers by the elements of

the matrix

g



G

from the system (16), we obtain the

circuit (Fig. 13) of the conjugated generalized PRN

generator in the Galois configuration. Block

diagrams of the PRN generator shown in Fig. 12 and

13 are just examples of LFSR generators with multi-

loop feedback.

Figure 13. Block diagram of a conjugate generalized Galois generator

If in the graphs in Fig. 13 to replace the contents

of the feedback register cells with matrix elements

F

and



F

from the (16), we come to the basic and

conjugate generalized PRN generator schemes in the

Fibonacci configuration.

The fundamental difference between generalized

Galois matrices

 

g

Q

and classical matrices

 

Q

is

as follows. If in CGM

 

Q

we can highlight the unit

matrix

E

of (n-1)-order, the zero column-vector,

and the row-vector, containing the bits of the

generator polynomial

f

, that in generalized

matrices

 

g

Q

does not have such features. It

follows that there are no compact forms similar to

the (8) of matrices

 

g

Q

for the set matrices. It

follows that there are no compact forms similar to

matrices

 

g

Q

represented by expression (8).

It is convenient to present a scheme of the

interrelation of classical

 

Q

and generalized

 

g

Q

Galois matrices in Table 5.

WSEAS TRANSACTIONS on CIRCUITS and SYSTEMS

DOI: 10.37394/23201.2022.21.1

Anatoly Beletsky

E-ISSN: 2224-266X

9

Volume 21, 2022

Table 5. Interrelation of Galois and Fibonacci matrices

G

F



G



F

G

–

⊥

T

Т⊥

F

⊥

–

Т⊥

T



G

T

Т⊥

–

⊥



F

Т⊥

T

⊥

–

5 Generalize Hardware and Matrix

PNR Generators Over a Field of Odd

Characteristics

The developed synthesis algorithms for binary

matrix Galois PRN generators are easily generalized

for constructing PRN generators over a field of odd

characteristics

p

. The Galois matrices

corresponding to such generators denote by

()

,,

n

fp

G

.

The matrix

()

,,

n

fp

G

synthesis algorithm coincides

with the above algorithm for synthesizing binary

GGMs

()

,

n

f

G

. In this case, the algorithm is enough to

perform only such simple replacements:

(2 ())

nn

GF GF p→

and

( ) ( )

, , ,

nn

f f p

→GG

.

Let us look at an example. Let

4n=

,

3p=

,

12121f=

and

221=

. The parameters include an

irreducible polynomial

f

, the exponent of 10, and

−

a primitive element of the field

4)(3GF

,

generated by the IP

f

. The selected parameters

correspond to the generalized primitive Galois and

Fibonacci matrices over

(3)GF

,

0 1 2 2 1 0 1 2

1 2 2 1 2 1 2 2

,

2 2 1 0 2 2 2 1

0 2 2 1 0 2 1 0

0 1 2 0 1 2 2 0

1 2 2 2 0 1 2 2

,,

2 2 1 2 1 2 2 1

2 1 0 1 2 2 1 0



   

   

   

   

   

   

==

==GF

GF

(17)

in which letter indices are omitted for simplicity.

Using the matrix

G

of the system (17) and the

generator circuit shown in Fig. 14, we will compose

a generalized structural logic diagram (Figure 14) of

a ternary four-bit register PRN generators in the

Galois configuration. The numbers 3 located in the

bitwise multiplication and addition operators mean

that the calculations were modulo 3. It also assumed

that the register

D−

triggers transfer ternary

numbers from the input to the output.

Fig. 14. Block diagram of the generalized Galois generator over IP

12121f=

WSEAS TRANSACTIONS on CIRCUITS and SYSTEMS

DOI: 10.37394/23201.2022.21.1

Anatoly Beletsky

E-ISSN: 2224-266X

10

Volume 21, 2022

An alternative register generator shown in Fig. 14

is a matrix PRN generator, which generates the same

sequence of pseudorandom ternary codes (Table 6)

as a registered generator.

Table 6. A sequence of ternary vectors generated by the registered (Fig. 14)

and matrix

()

,,

n

fp

G

(

221=

) generators of the PRN over the IP

12121f=

1

0

1

0

1

0

1

0

1

0

1

2

1

2

0

2

1

2

1

0

1

2

1

0

1

2

1

2

0

3

0

1

2

0

1

2

0

2

1

2

1

2

0

2

1

4

2

0

1

2

0

1

0

1

2

1

0

1

5

2

0

1

2

1

2

0

1

0

2

0

6

2

0

1

2

1

2

1

2

0

1

0

1

0

7

2

0

2

0

2

0

2

1

2

0

1

2

1

0

1

0

1

0

1

8

1

0

1

2

0

1

0

2

1

0

2

0

1

2

0

2

Table 6 contains only the first half of the

sequence of the maximum period, consisting (for the

selected values of the generator parameters) of 80

ternary four-digit codes. The second half of the

series, starting with code 0002, is formed from codes

of the first half due to their bitwise multiplication by

2 modulo 3.

6. Isomorphism of Generalized

Galois Matrices

The theory of polynomials of one variable

x

knows

that multiplication of an arbitrary degree

k

polynomial

()

kx

by the

x

equivalent of its shift

by one digit to the left. Or, in other words,

1

( ) ( )

kk

x x x

+

→

.

(18)

Using ratio (18) and taking into account how

GGM formed, record the transformation chain

11

22

()

,mod

11

mod

nn

n

f n n

xx

ff

xx



−−

   



   



   

 = 

   



   



   

G

.

(19)

The elements of the right vector-column of

inequality (19) are monomials, which, when

presented in binary form, transform the column into

a unit matrix, i.e.

1

2

1

1 0 0 0

0 1 0 0

0 0 1 0

0 0 0 1

n

x

−











==E

,

(2

0)

which makes it possible to formulate the following

statement.

Affirmation. The GGM

()

,

n

f

G

of the order

n

above IP

n

f

isomorphous to its constitutive element



, which belongs to the field

(2 )

n

GF

, i.e.

()

,

n

f

G

≃



,

(21)

where ≃ – the isomorphism symbol.

According to the expressions (19), (20), there is

a mutually unambiguous correspondence

(isomorphism) between GGM

()

,

n

f

G

and its forming

element



, which reflects by the ratio (21) and

leads to such consequences:

Consequence 1. The generalized matrixes of

Galois

()

,

n

f

G

are non-singular at any parameters

n

f

and



, as are formed by linearly independent lines.

Consequence 2. For elevating the matrix

()

,

n

f

G

the degree

k

is enough to calculate forming element

(mod )

k

kk

f=

and make a matrix

()

,

n

f

G

.

Consequence 3. The minimum non-zero value of

degree e providing equality

( )

()

,

e

n

f=EG

coincides

WSEAS TRANSACTIONS on CIRCUITS and SYSTEMS

DOI: 10.37394/23201.2022.21.1

Anatoly Beletsky

E-ISSN: 2224-266X

11

Volume 21, 2022

with the order of the element



, which forms the

matrix

()

,

n

f

G

Consequence 4. The generalized matrix of

Galois

()

,

n

f

G

is primitive if the element forming



it is primitive, i.e., if

=

, there is



— a

primitive element of the field

(2 )

n

GF

.

Consequence 5. The operation of multiplication

matrixes Galois

1

()

,

n

f

G

and

2

()

,

n

f

G

,

12

  

, is

commutative because according to the ratio (21) of

the product in the left and right parts of the equality

1 2 2 1

( ) ( ) ( ) ( )

, , , ,

n n n n

f f f f   

 = G G G G

is equivalent to

the products of elements

12

()

and

21

()

,

calculated on the module of the IP

n

f

.

Consequence 6. Arbitrary modular arithmetic

transformations over Galois matrixes are isomorphic

to the same changes over the forming elements of

these matrixes.

Consequence 7. The generalized matrixes of

Galois

()

,

n

f

G

, inverse matrix

()

,

n

f

G

, can be

constructed according to the rule formulated in item

4. The forming element of the matrix

()

,

n

f

G

is

element



, the inverse of the forming element

matrix

()

,

n

f

G

.

7 Calculating Inverse Elements of the

Galois Field

For each "direct" matrix from subset

 

( )

, , ,



Q G F G F

, we will match the so-called

"reverse" matrices, the set of which forms subset

 

( )

, , ,



Q G F G F

. Let us supplement the

internal matrix contour

 

Q

, shown in Figure 9,

another so-called external contour, placing the

matrixes of the subset in its nodes

 

Q

. The posed

problem has a trivial solution. Indeed, according to

(21) Galois matrices

()n

f

G

and their forming

elements are connected by the isomorphism relation.

And, as a consequence, two Galois matrices

generated by the same non-acceptance (primitive for

CGM) polynomial become mutually convertible if

the elements forming them are mutually convertible.

Therefore, to construct

()

,

n

f

G

a reverse matrix

()n

f

G

,

it is sufficient to replace forming element



with its

reverse value



at the stage of matrix synthesis, i.e.,

( ) ( )

,,

nn

ff



=GG

.

For CGM, generated by PrP

n

f

, the forming

element

 =

. By definition, some non-zero

element



of the Galois extended field is a reverse

element



if and only if the condition met

) mod 1f( =

. Let

1 2 1

1 , , 1

n n n

f

  

−−

=

—

the primitive binary polynomial and

( =)

—

forming element matrix

()

,

n

f

G

. Then

1 2 1

1 , ,

nn

  

−−

=

and

1 2 1

1 , , 0

nn

  

−−

 =

.

The product

 

by modulo

n

f

forms a subtraction

of 1, required for a pair of reciprocal values. Thus,

we come to the following general form of inverse

CGM

()

1 2 3 2 1

0 0 0 0

0 0 0 0 0

0 0 0 0

1 2 3 2 1

1

2

3

2

1

n

f

nn

n n n

n

−−





=





−−

−

01

0

01

1    

G

,

(22)

which can present in such a compact form

()n

ff



=



0E

G◀

.

In particular, for PrP

8101100101f=

under

(22), we will receive

WSEAS TRANSACTIONS on CIRCUITS and SYSTEMS

DOI: 10.37394/23201.2022.21.1

Anatoly Beletsky

E-ISSN: 2224-266X

12

Volume 21, 2022

01000000 8

00100000 7

00010000 6

00001000 5

00000100 4

00000010 3

00000001 2

1 0 1 1 0 0 1 0 1

8 7 6 5 4 3 2 1

i

j

=







G

.

(23)

Hardware implementation of the LFSR generator's PRN, to which the matrix (23) responds, is shown in Fig.

15.

Fig. 15. Block diagram of the "reverse" generator PRN in the

Galois configuration generated by the PrP

8101100101f=

The interrelation of Galois

 

Q

inverse matrices

is determined by the same operators

⊥

and

Т

performed according to the same scheme as direct

matrices

 

Q

. The scheme of the interrelation of the

complete set of matrices

 

Q

is shown in Fig. 16.

Fig. 16. The scheme of the interconnection

of the set of classical Galois matrices

The matrix (23) is converted into a reverse Fibonacci matrix by right-hand transposition.

01000000 8

1 0 1 0 0 0 0 0 7

00010000 6

00001000 5

1 0 0 0 0 1 0 0 4

1 0 0 0 0 0 1 0 3

00000001 2

10000000 1

8 7 6 5 4 3 2 1

i

j

=







F

.

(24)

WSEAS TRANSACTIONS on CIRCUITS and SYSTEMS

DOI: 10.37394/23201.2022.21.1

Anatoly Beletsky

E-ISSN: 2224-266X

13

Volume 21, 2022

Hardware implementation of the LFSR of the PRN generator to which the matrix (24) responds shows in Fig.

17.

Fig. 17. Block diagram of the "reverse" generator PRN in the

Fibonacci configuration generated by the PrP

8101100101f=

Reverse conjugate Galois



G

and Fibonacci



F

matrices of the eighth order are generated, according

to transformations 13), by left-hand transposition of

matrices (23), (24), and have a form:

8 0 1 0 0 1 1 0 1

0 000001

7 10000000

10000000

6 01000000

0 1 0 0 0 0 0 1

5 00100000

0 0 1 0 0 0 0 1

;

4 00010000

0 0 1 0 0 0 0

3 00001000

0 0 0 0 1 0 0 0

2 00000100

0 0 0 0 0 1 0 1

1 00000010

0 0 0 0 0 1 0

8 7 6 5 4 3 2 1

0

































==GF

8

7

6

5

.

4

3

2

1

8 7 6 5 4 3 2 1



(25)

Structural diagrams of inverse conjugate LFSR generators of PRN, corresponding to matrixes (25), are

presented in Fig. 18.

Fig. 18. in the of reverse conjugate generators of PRN in Galois (a)

and Fibonacci (b) configurations, generated by PrP

8101100101f=

The main problem in the designated calculation

chain is the definition of the element

ω

. There are

different ways of finding the inverse elements of the

Galois field [12]. The most frequently used method

is based on the extended Euclidian algorithm [13].

Below is an alternative approach to calculations of

ω

that is easier to implement than the Euclidian

algorithm.

It is known that for any non-zero element



of a

binary Galois field, the equality

( )

21 1

n

nn

n

f

L

f

−

==

,

(

2

6)

where

n

L

is the order of the element



, and

( )

(mod )

f

a a f=

.

Introducing (26) in the form

( ) ( )

( )

2 1 2 2

1

n

nn

n

ff

f

−−

=

= 



=



,

we'll get

( )

22

n

f

−

=

.

(

2

7)

According to formula (27), the inverse element

ω

is determined by the residue of the even degree

22

n−

of the field

(2 )

n

GF

element



modulo

.

n

f

These residues are placed in the odd lines of Table

7.

WSEAS TRANSACTIONS on CIRCUITS and SYSTEMS

DOI: 10.37394/23201.2022.21.1

Anatoly Beletsky

E-ISSN: 2224-266X

14

Volume 21, 2022

Table 7. The algorithm for calculating inverse elements of a binary Galois field

n

L

k

Residue

n

L

k

Residue

VI

1

2

1()

f

 = 

6

63

8

87

()

f

 =  

3

7

2

21

()

f

 =  

9

2

98

()

f

 = 

3

2

32

()

f

 = 

7

127

10

10 9

()

f

 =  

4

15

4

43

()

f

 =  

11

2

11 10

()

f

 = 

5

2

54

()

f

 = 

8

255

12

12 11

()

f

 =  

5

31

6

65

()

f

 =  

13

2

13 12

()

f

 = 

7

2

76

()

f

 = 

Table 7 it is indicated:

n

− the degree of the

irreducible polynomial

f

;

k

− step of iteration;

n

L

− the order of the multiplicative group of the field

(2 )

n

GF

, generated by IP

f

; VI − initialization

vector equal to

2

()

f



.

Based on Table 7, we quickly come to the

expression for the number of iterations

k

,

performed when calculating the inverse field

elements



over the IP degree

n

23kn=−

.

Let's consider a numerical example. Suppose

4n=

,

10011f=

and

 = 

. According to

Table 7, the first step is the calculation

( )

2

110011

1101 1101 1110

f

 =  =  =

For the next step, we find

( )

( ) ( )

( )

( ) ( )

( )

( ) ( )

( )

21

2

32

43

2

54

1110 1101 1000110 1010;

1010 1010 1000100 1000;

1000 1101 1101000 10;

10 10 100.

ff

f

ff

f

ff

f

 =   =  = =

 =  =  = =

 =   =  = =

 =  =  =

Residue

5100=

is the opposite of the element

 =

.

The vector of initialization

( )

2

1f

VI =  = 

starts the computational process. The further

procedure consists of

2n−

cycles, each of which

includes two iteration steps. We find the auxiliary

vector

2( 2)n−



as the first (on the even step

k

) and

the second (on the odd iteration stage) — the inverse

element

23n−

 = 

.

The algorithm for calculating the inverse

elements of the field

(2 )

n

GF

can easily be

generalized to determine the inverse elements of an

arbitrary characteristic

p

. The block scheme of the

algorithm shows in Fig. 19.

WSEAS TRANSACTIONS on CIRCUITS and SYSTEMS

DOI: 10.37394/23201.2022.21.1

Anatoly Beletsky

E-ISSN: 2224-266X

15

Volume 21, 2022

Fig. 19. Block scheme of the algorithm for

calculating inverse field

()

n

GF p

elements.

For example, let's

5p=

,

3n=

,

1032f=

,

234=

. The sequence of results of calculations the inverse

element



is as follows:

1.

1s=

,

1R=

,

( )

44

234 24

f

с=  = =

,

( )

55

24 131

ff

R R c=  = =

;

2.

2s=

,

( ) ( )

55

131 24 423

ff

R R c=  =  =

;

3.

3s=

,

( ) ( )

33

423 234 202

ff

R =  =  =

;

( ) ( )

ff

 =  = 1

.

8 Hacking Problems of Galois PRN

Generators

Its knowns that the classic Galois LFSR generators

have lower crypto stability; the reason for which is

that they quickly hacked using the Berlekamp-

Massey (BM) algorithm [9]. This algorithm uses the

known elements of the sequence

 

1 2 2

, , , n

x x x=X

produced by a

n−

discharge oscillator to calculate

the PrP

n

f

in the feedback circuit of a linear register

of minimum length

n

. It should note that all

primitive Galois matrices, both classical and

generalized, can serve as generators of PRN length

sequences

21

n

L=−

. Each of these sequences,

removed from the output of an arbitrary discharge

LFSR, satisfies all three postulates of Golomb [10].

For this reason, it may seem that the generalized

Galois generators do not bring any new properties to

the PRN formed by classical generators. But this is

not entirely true. As established in [6], generators of

PRN built based on generalized Galois matrices are

free from the BM attack. The noted feature of the

generators appears due to the following reason. The

classical generators by mean of BM algorithm are

successfully determining only one unknown –

primitive polynomial

n

f

. For generalized

generators, besides the polynomial

n

f

, the primitive

FE



of the Galois matrix is also unknown. But the

classical algorithm of the BM is not intended for

calculating two unknown parameters and therefore

becomes unsuccessful in attacking the generalized

generators. That, for one thing. And secondly, in any

case (whether the conditions of applicability of the

BM algorithm are satisfied or not) the processor

implements the Berlekamp-Massey algorithm

outputs as a solution that or the value of degree n

primitive polynomial.

Below it will show that the transition from

classical LFSR-generators of PRN to generators

based on generalized matrixes of Galois and

Fibonacci leads to the fact that the algorithm of BM

loses the ability to determine the IP is produces the

generator of PRN. The noted feature of such

generators is that the series of bits formed by them

WSEAS TRANSACTIONS on CIRCUITS and SYSTEMS

DOI: 10.37394/23201.2022.21.1

Anatoly Beletsky

E-ISSN: 2224-266X

16

Volume 21, 2022

depends not only on the chosen IP

f

but also on the

primitive element



involved in the formation of the

feedback chain of the generator.

For experimental confirmation of the stated

statement and the basic theoretical positions

concerning properties of matrixes of feedback, we

shall address to results of computer modeling

(reduced in Table 8) of the generalized eight-digit

Galois generator of PRN. The PrP

100011101f=

was chosen as the polynomial forming the feedback

loop of the generator.

Table 8. BM tester solutions on many primitive elements

of the field generated by the PrP

100011101f=

№

IP:

100011101

Forming element

PrP

1

2

3

4

5

6

7

8

1

100011101

002

004

020

035

114

137

205

235

2

100101011

006

015

024

121

207

302

321

332

3

100101101

113

033

210

130

220

227

300

336

4

101001101

112

123

211

233

307

313

322

325

5

101011111

037

122

110

232

306

312

323

324

6

101100011

036

102

111

133

215

225

237

311

7

101100101

022

103

030

132

214

224

236

310

8

101101001

022

023

030

031

134

135

200

201

9

101110001

011

036

101

107

203

216

314

330

10

110000111

050

064

071

074

077

171

273

345

11

110001101

052

060

143

151

242

274

367

370

12

110101001

043

161

166

172

245

252

260

340

13

111000011

042

160

167

173

244

253

261

341

14

111001111

157

176

262

267

354

360

363

372

15

111100111

062

155

257

343

350

352

356

376

16

111110101

053

061

142

150

243

275

366

371

According to Table 8, the eight forming elements

located in the top row of the table are such that each

of them leads to the correct solution produced by the

BM tester. We will call such forming elements

"weak keys" of the flow code, the encrypting gamma

formed by the analyzed PRN generator. It is quite

easy to eliminate weak keys. For this purpose, it is

enough to choose a polynomial

f

that is not

primitive while keeping the forming element

primitive



.

9 Conclusion

The main results are as follows:

1. Different variants of construction of binary

PRN generators based on the so-called generalized

Galois and Fibonacci matrices developed. The

transition from classical to generalized matrix

generators PSF is accompanied by an expansion of

diversity of generators and leads to a significant

increase in their cryptographic strength. This effect

is achieved by increasing the number of form

elements and by the polynomials generating Galois

matrices, which are not necessarily primitive.

2. It is shown that PRN generators based on

generalized Galois matrices are not subject to BM

attacks. The noted property is a consequence of this

feature of the BM algorithm. The classical BM

algorithm solves the problem of computing one

unknown parameter: the minimal primitive

polynomial

f

in the LFSR feedback circuit of the

PRN generator. In the generalized matrix generators,

two unknown parameters have to be determined: an

irreducible polynomial

f

and a generating element



, jointly forming Galois matrices. This problem

becomes unsolvable for the BM algorithm.

3. Recurrence estimates of the states of classical

matrix Galois generators of PRN have been

proposed, significantly increasing the computational

speed.

4. The developed algorithms of synthesis of

generalized Galois and Fibonacci matrices allow to

build cryptographically secure information

protection systems and be useful in other

applications.

WSEAS TRANSACTIONS on CIRCUITS and SYSTEMS

DOI: 10.37394/23201.2022.21.1

Anatoly Beletsky

E-ISSN: 2224-266X

17

Volume 21, 2022

References:

[1] Schneier B., Applied cryptography, Second

Edition: Protocols, Algorithms, and Source

Code in C. John Wiley & Sons, New York

(1996).

[2] Chen L., Gong G. Pseudorandom 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] 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, pp. 3692-3709.

[5] Beletsky A. 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)

[6] Beletsky A., Beletsky E. Generators of Pseudo

Random Sequences of Galois. Electronics and

Control Systems, (2014, # 4(42). – P. 116-127.

(In Russia)

[7] Mullajonov R.V. Generalized transposition of

matrices and structures of linear large-scale

systems. Reports of the National Academy of

Sciences of Ukraine, 2009, №10. – P. 27-35. (In

Russia)

[8] Gantmacher F.R. Theory of Matrices. — AMS

Chelsea Publishing: Reprinted by American

Math. Society, 2000. — 660 p.

[9] Beker H. and Piper F. Cipher Systems: The

Protection of Communication, London:

Northwood Books, 1982

[10] Matsumoto M. and Nishimura T. Mersenne

twister: A 623-dimensionally equidistributed

uniform pseudorandom number generator.

ACM Transactions on Modeling and Computer

Simulation, 8:3–30, 1998.

[11] Meyer C.H. end Tuchman W.I. Pseudorandom

Codes Can be Cracked, Electronic Design, v.

23, Nov 1972.

[12] Smart N. Cryptography: An Introduction, 3rd

ed. McGraw-Hill College, 2013

[13] Van der Warden, B., L. Mathematics Statistic.

Moscow, IL, 1960, 371 p. (In Russia)

WSEAS TRANSACTIONS on CIRCUITS and SYSTEMS

DOI: 10.37394/23201.2022.21.1

Anatoly Beletsky

E-ISSN: 2224-266X

18

Volume 21, 2022

WSEAS TRANSACTIONS on CIRCUITS and SYSTEMS

DOI: 10.37394/23201.2022.21.1

Anatoly Beletsky

E-ISSN: 2224-266X

19

Volume 21, 2022

Contribution of Individual Authors to the

Creation of a Scientific Article (Ghostwriting

Policy)

The author contributed in the present research, at all

stages from the formulation of the problem to the

final findings and solution.

Sources of Funding for Research Presented in a

Scientific Article or Scientific Article Itself

No funding was received for conducting this study.

Conflict of Interest

The author has no conflict of interest to declare that

is relevant to the content of this article.

Creative Commons Attribution License 4.0

(Attribution 4.0 International, CC BY 4.0)

This article is published under the terms of the

Creative Commons Attribution License 4.0

https://creativecommons.org/licenses/by/4.0/deed.en

_US