The article deals with the formation of generalized primitive matrices of Galois G and Fibonacci F of any order above the field GF (2) . The terms “Galois and Fibonacci matrices” are borrowed from the theory of cryptography, in which pseudorandom sequence generators (PRS) on Galois and Fibonacci schemes are widely used. Matrixes G and F software are used to generate the same PRS as the corresponding generators. The generalized matrices include the Galois matrices (as well as the transposition related to them relative to the auxiliary diagonal of the Fibonacci matrix), formed by primitive elements of the field GF (2) over the irreducible polynomials (IP) fn , which are not necessarily primitive. In the classical Galois and Fibonacci matrices, the constitutive element is . Synthesis of matrices G and F is based on the use of IP degree and primitive field elements, generated by polynomials fn . The statement, according to which the generalized matrix of Galois is isomorphic to their forming elements of the field GF (2) . The ways of construction of conjugate ( G , F ) and inverse ( G, F ) Galois and Fibonacci matrices are considered. A new effective algorithm for calculating the inverse elements of Galois's extended fields is proposed. The interrelation of the found variety of Galois and Fibonacci matrices is established. The ways of using such matrices in cryptographic applications to solve the problem of building generalized linear PRS generators of the maximum period are discussed.
1.1
One of the key problems in the theory and practice of cryptographic protection of information is the problem of formation (generation) of binary pseudorandom sequences (PRS) of maximum length with acceptable statistical characteristics. As a rule, PRS generators are implemented using a linear feedback shift register (LFSR) [1]. Only LFSR with specially selected feedback functions can pass through all nonzero internal states - these are the so-called maximum period registers. For LFSR to be the maximum period register, the corresponding feedback polynomial must be a primitive [2].
Each PRS generator can be assigned uniquely to the associated Galois (or Fibonacci) matrices, which calculate the same sequences as those generated by the LFSR generators. The terms "Galois and Fibonacci Matrix" are borrowed from the theory of cryptography and coding [3], in which binary PRS generators based on Galois and Fibonacci schemes are used mainly.
The main task of this article is to develop algorithms for constructing PRS
generators based on the so-called generalized LFSR and primitive matrices (PrM) of Galois
and Fibonacci n order over the field GF (
The classical generator (register) Galois, which example is shown in Fig. 1, compares to each non-zero element of the field GF (2 n ) some degree 10 of a minimum primitive element of the field on module PrP fn . Feedbacks in the classic Galois generators are unambiguously determined by the selected primitive polynom (PrP) fn and are formed as follows: the responses of each digit of the register arrive at the inputs of the next digits, being for them the excitation functions. Also, the response of the register's highest digit is provided (according to the XOR scheme) to input inputs of those and only those register digits, the numbers of which coincide with the non-zero numbers of PrP monomials. The simplicity of the algorithm of construction (synthesis) of Galois generators, easily traceable in Fig. 1, is a consequence of the accepted variant of LFSR discharge numbers ranking (from right to left), whereas usually the numbering of shift register discharges is performed from left to right [4].
Let's S (t) the state of Galois register at a discrete point in time t . Denote G (fn) the Galois matrix, corresponding to the selected Galois generator. With the help of this matrix forms the same binary sequence as the corresponding PRS. The order n of the matrix G (fn) coincides with the degree of PrP fn , which generates the n bit generator Galois. Let's imagine the iterative procedure of changing Galois register states by the ratio
S (t) S (t 1) G (fn),
sequently, in the bottom line of a matrix G (fn) , it is necessary to write down the value
S (
00 on the module fn . n1 n1 1 0 G (fn) 0 0 n2 0 1 0 0 where k the polynomial coefficients, the vector form of which is fn 1 n1 n2 k 11, k 1, 2, , n 1 .
The structure of the matrix (
In addition to the classic Galois matrices (
F G .
Transposition, relative to the main matrix diagonal, indicated by the symbol T , will
be called a left-hand inversion. According to (
matrix (
M P 1 M P ,
(
In group theory, an element a of a group A is a conjugate element a of the same
group [], if there is an element z A such that
Similar to (
As follows from the ratio (
G G E , where E the single matrix is.
For example, for the fourth-order matrices, according to (
G — T
T G — 1 1
1 1
F —
T T
F 1 1 — 1 1
G T
T —
F
T T — G
1 1 — Let's specify the physical meaning of transformation operators in Table 2. The operator 1 means that the feedback scheme marked with the symbol undergoes rotation on 180 a relatively vertical axis. Such transformations occur, as it follows from Fig. 6, in pairs of generators (G, G ) or (F , F ) . The operation 1 is similar to the process of inverse shifting of matrix columns M , which is realized by multiplying it by the IPM on the right side. The operator 1 rotates the feedback scheme relative to the horizontal axis. Thus, the process is similar to the operation 1 of inverse permutation of matrix rows, if you multiply it by IPM on the left side. The specified conversions of feedback take place in pairs of generators (G, F ) or (F , G ) . Finally, the operator 1 1 means that both vertical and horizontal axes rotate the feedback scheme. Such transformations of feedback circuits are performed in pairs of generators (G, F ) or (G , F ) .
The feedback diagrams in reverse PRS generators are formed as a result of turning on the relatively 180 vertical axis of the charts shown, as an example, in Fig. 6 for the generators, generated by the PrP f8 101001101 . The way of formation of matrixes of a full set of LFSR generators of PRS (and among them - classical, conjugate, and return generators) is shown in Fig. 7.
0 G f
E ▲
T F E f ▶
◀ G
E F f f
0 T ▶E
F
E G 0 f f
▼ T E ▼
▼ F f
E
T G E ▼f 0
Fig. 7. The interrelation of classic LFSR matrixes of PRS generators
)▲define a binary vector (row or column), in which f is replaced by the digit 1, and a shaded triangle - a sequence of polynomial coefficients k , and the top of the triangle indicate the location of the senior factor. For example, f
▲it means a vector 1 n1 n2 1 , while f ▼it implies a vector n1 . Besides, symbols 0 and also suggest zero vector-column and vectorline, respectively. And finally, the symbols T indicate not only the two-way transposition but also the inversion of the polynomial coefficients k . 3 3.1
Based on the construction of generalized generators of Galois (as well as Fibonacci), we will put the generalized matrices corresponding to them.
Definition. The generalized matrix of Galois (GMG) will be called the matrix, formed by the primitive element of the field GF (2n ) over the IP fn , which is not necessarily primitive.
We come to the algorithm of GMG construction, expanding the Rule of synthesis of KMG, formulated in paragraph 1.2. The essence of the algorithm of GMG formation is as follows. Let's choose some primitive element of the field GF (2n ) generated by the IP fn , which we will place in the right corner of the bottom line of the synthesized matrix G (fn) . Subsequent matrix rows (in the direction from bottom to top) are formed from the previous rows as a result of their shift by one digit to the left. The numbers released on the right are filled with zeros. If a higher unit shifted, row goes beyond the left border of the matrix. This row is reduced to the remainder of the module fn , which also results in it becoming a digit. The row returns to matrix boundaries, and the process of filling in its rows continues as described above. The formulated rule is called the rule of GMG synthesis.
Let's consider an example of the synthesis of generalized primitive matrices and LFSR generators of PRS, choosing as an irreducible binary polynomial fn 11111 of the fourth degree, which is not primitive, and primitive forming element. Matrixes corresponding to the selected parameters are represented by expressions (14).
Let's hi, j denote the element of i th row and j th column, i, j 1, n , any of the matrices G, F , G or F underlying the construction of LFSR with generalized linear relations. The state of the k th discharge LFSR sk (t 1) at the moment t 1 coincides with the excitation function of this discharge k (t) at the moment t and is determined by the expression: n sk (t 1) νk (t) i1 hi,k si (t) .
The structural scheme of the generalized primary four-digit Galois generator is shown in Fig. 8. Vertically arranged generator records marked with a symbol at the top implement the digit multiplication operation, and registers marked with a symbol addition operation on module 2. Galois generator (Fig. 8) is converted into a Fibonacci generator by replacing the register contents with the system matrix F (14). If we place matrix column elements in the multiplication registers G or F from the system (14), we get a paired generator in the Galois or Fibonacci configuration. The scheme of the matched Galois/Fibonacci PRS generator is shown in Fig. 9. From the theory of polynomials is known, that multiplication of an arbitrary degree k polynomial k (x) by x the equivalent of a shift of a polynomial by one digit to the left and, consequently, an increase by 1 degree of a polynomial
x k (x) k 1 (x) .
Using the ratio (15) and taking into account the way OMG is formed, let's write down the chain of transformations: Elements of the right vector-column in the ratio (16) are monomers, which, being represented in the binary form, turn the vector-column into a single matrix, i.e. (15) (16) (17) which makes it possible to formulate the following
The postulate. The generalized binary matrix of Galois G f(n,) isomorphous to its forming element xn1 xn2
Therefore, according to the expressions (16) and (17), there is a mutually unambiguous correspondence (isomorphism) between GMG G f(n,) and its forming element ω, which is displayed by the ratio (18). Also, it is easy to establish that isomorphism (18) leads to such consequences.
Consequence 1. The generalized Galois matrices G f(n,) are nondegenerate for all parameters f n and are linearly independent rows of matrices, as can be readily ascertained from the ratio (17).
Consequence 2. To elevate the matrix G f(n,) in degree k , it is enough to calculate forming elements k k (mod f n ) and then calculate matrix G f(n,)k .
Consequence 3. The minimum non-zero value of degree e, which ensures equality G f(n,) e E , coincides with the order of the element forming the matrix G f(n,) .
Consequence 4. The generalized matrix of Galois G f(n,) is primitive if the forming element is primitive, i.e., if .
Consequence 5. Matrixes G f(n,) 1 and G f(n,) 2 , 1 2 , are commutative, because commutatively the product of the elements forming them.
Consequence 6. Algebraic transformations over the totality of Galois matrices are isomorphic to the same transformations over the forming elements of matrices.
Consequence 7. GMG G f(n,) , inverse matrix G f(n,) , can be constructed according to the rule of synthesis of generalized Galois matrices, formulated in item 3.1. The forming element of the matrix G f(n,) is the inverse element of the forming element
Consequence 8. A lot of GMGs can be expanded by introducing similar Galois matrix G f(n,) . matrices Gˆ f(n,) defined by the
Gˆ f(n,) P 1 G f(n,) P . (19) As P matrices in transformation (19), it is preferable to consider permutation matrices of the n order, because, for them, the inverse matrices are simply enough calculated, namely P 1 P T . Unlike the GMG G f(n,) matrixes Gˆ f(n,) , they remain commutative and lose their isomorphism property. This feature of such matrices of Galois, first of all, provides an opportunity to build on their one-way basis functions, widely used in cryptography and other applications. And, secondly, it is possible to construct one-sided functions based on them, which are widely used in cryptography and other applications, LFSR generators of PRS are free from Berlekemp-Messi attack.
The complete set of generalized Galois and Fibonacci matrices can be represented in the form of a graph (Fig. 10), similar to the chart of many classical matrices shown in Fig. 7.
G F
T
G F
T
F G
T
F
T G The location of the vectors of FE generalized matrices, all of them for simplicity, will be called Galois matrices, is shown in Fig. 11. The vector arrows are directed towards the higher classes of the forming elements. construction of GMG G f(n,) , it is necessary to calculate the element and then, using the rule of synthesis GMG, to make a matrix G f(n,) . The remaining matrices of the external contour of the graph are connected with the operators of left- and right-hand transposition.
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 [7, 8]. Among them, the most frequently used method is based on the extended Euclidian algorithm [9-11].
Below is an alternative approach to calculation — it is more straightforward in the program implementation than the Euclid algorithm. The essence of the alternative algorithm is explained in Table 3, in which it is indicated: n the degree of IP f ; k step of iteration; Ln (2 n 1) the order of the multiplicative group of the field GF (2 n ) , generated by IP f n ; means the calculation of the residual value a of the module
VI vector of initialization. Writing k (a) f f n on the k th iteration step. It is known, that for any non-zero field element the equality of
Ln ) f (2 n 1) f 1 . ( 2 n 2 )) f ) f 1 ,
(2 n 2 ) f .
According to formula (21), the inverse element is determined by residue an even degree 2 n 2 of the field element from the IP module f n . These residues are placed in odd lines in Table 3.
Based on Table 3, we quickly come to the expression for the number of iterations k , performed when calculating the inverse field elements over the IP degree n (20) (21)
Let's consider a numerical example. Suppose n 4 , f 10011 and . According to Table 3, the first step is to perform the following calculations 1 2 f f 10011 1110 .
2 1 f f 10011 1010 ; 3 22 f f 10011 1000 ; 4 3 f f 10011 10 ;
5 24 f f 100 .
The residue 5 100 is the opposite of the subtraction element .
The vector of initialization starts VI 1 (2 ) f the computational process (according to Table 3). The further procedure consists n 2 cycles, each of which includes two iteration steps. We find the auxiliary vector 2 (n2) as the first one (on the even step k ), and the second one (on the odd stage of iteration) — the inverse element 2 n3 . 4
Visual perception of the FE vectors presented in Fig. 11 can create an assumption about the possible existence of an alternative set of matrices, the vectors of forming elements which are located in the vicinity of the vertices of the auxiliary diagonal of the square (fig. 12). However, this is a false assumption, as none of the FE fields GF (2 n ) above the IP fn leads to the formation of a primitive Galois matrix. And this excludes the possibility of building PRS generators of the maximum period [12-14]. 5
The main scientific results of this study include the following:
1. Algorithms for the synthesis of the so-called generalized Galois matrices have been developed. Generalized matrices are those formed by primitive elements over IP fn , which are not necessarily primitive. In addition to Galois matrices, many generalized matrices also include other matrices (Fibonacci, conjugate, and backward matrixes). All the above matrices are interconnected by a set of linear transformations (left- and right-hand transposition). The generalized matrixes of Galois (as well as classical ones) are intended for the construction of LFSR generators of PRS of the maximum period. The advantage of the widespread PRS generators is that they, unlike the classic LFSR generators, are free from the Berlekemp-Messi attack.
2. The postulate, according to which the generalized Galois matrices appear to be isomorphic elements forming them, is formulated and confirmed [15, 16].
3. A new algorithm for calculating the inverse field elements GF (2 n ) over IP fn
is proposed, which is simpler in comparison with the widely used generalized
Euclidean algorithm.
nal of Computer Network and Information Security (IJCNIS), Vol.10, №2, pp. 38-45,
2018.
13. Zodpe H., Sapkal A. “FPGA-Based High-Performance Computing Platform for
Cryptanalysis of AES Algorithm”, Advances in Intelligent Systems and Computing, Springer,
vol. 1025, pp. 637-646, 2020.
14. Hu Z., Gnatyuk S., Okhrimenko T., Tynymbayev S. and Iavich M. High-speed and secure
PRNG for cryptographic applications, International Journal of Computer Network and
Information Security, Issue 12 (
Electrical Engineering, vol. 603, pp. 281-290, 2020, doi:10.1007/978-981-15-0058-9_27 16. Liu H., Kadir A. and Xu C. “Cryptanalysis and constructing S-box based on chaotic map and backtracking”, Applied Mathematics and Computation, vol. 376, 125153, 2020, doi:10.1016/j.amc.2020.125153