A Finite Field of Square Matrices of Order 2

Abstract

This paper focuses on constructing a Galois field of square matrices of order 2 and substantiates a theoretical basis for developing schemes of cryptographic transformation of information, key exchange, and digital signature. This research goal has been achieved by investigating a family of square matrices of order 2 with the commutative operation of matrix multiplication from the general linear group over the prime field of integers modulo. It has been proved that this commutative family of matrices is simultaneously diagonalized. The matrix that performs diagonalization has been calculated. This matrix is common to all matrices of the commutative family. The research has defined the family of matrices forming a Galois field of order with common operations of matrix multiplication and addition. The multiplicative cyclic group of this field has been shown.

Keywords

• 1 Finite field
• square matrices
• commutative family of matrices
• diagonalization
• key agreement
• cryptography

1. Introduction

The theory of finite fields plays one of the key roles in cryptography. Thus, the operations of addition, multiplication, and finding inverse values in symmetric encryption algorithms [1– 2] are implemented over an extended finite field GF (2n ) . Algorithms testing simplicity and factorization of integers rely on the theory of finite fields [ 3 ], which is the foundation of asymmetric cryptography [ 4–7 ]. Finite fields are an integral tool for creating electronic digital signatures, including those based on elliptic curves [ 8–14 ].

The recent trends in cryptography indicate

that applications of matrix theory in information representation and transformation are expanding. In particular, this approach has already proven its effectiveness in the AES encryption standard [2].

Previous research findings into matrix theory [15] developed a public-key cryptosystem based on commutative semirings of tropical cyclic matrices, where multiplication is the usual addition of numbers, while the usual multiplication of numbers in the tropical semiring is absent.

The study [16] investigated chaotic image

encryption technology and the application of matrix semi-tensor product theory.

In the study [17], the authors propose a homomorphic encryption technique based on matrix transformations with shifts, rotations, and transpositions. A recent study [18] proposes a code-based digital signature. The proposed scheme uses the McEliece cryptosystem [19] based on random inverse matrices.

Another major study describes Shamir’s three-pass random matrix ciphering mechanism [20] that deploys a three-pass protocol with encryption operators that are random matrices. However, this research was limited by operations on commutative matrices, and uses inverse, circular, and permutation matrices, leaving the matrix fields beyond the scope of the study.

As we have indicated above, finite matrix fields have potential applications in cryptographic schemes used in information transformation, key exchange, and digital signature. In addition, the authors of this research have described potentially effective applications of finite matrix fields in permutation-based data transmission systems [21–24].

The study [25] identifies and investigates

families of square matrices of order 2 with the commutative operation of multiplication for solving cryptographic information transformation problems.

Six families of matrices from the general

linear group GL (n, Z p ) [26–27] of the order n are defined over the prime field of integers modulo p , for which the multiplication operation is commutative.

In [25], the authors show that one of the families of square matrices of order 2 with the commutative operation of matrix multiplication is the family  t, a,b, k  Z p ,    a 1   6 = t   , t  0,b  0,  .

  b a + k    a (a + k ) − b  0 with b and k fixed and supplemented with an identity matrix. We denote this family as   a 1   1 0   t   , s   ,   b a + k   0 1     CGLb,k (2, Z p ) =  t, s, a,b, k  Z p ,  .  t, s  0,  a (a + k ) − b  0 

The study [25] has proved that the matrix family

CGLb,k ( 2, Z p ) is a commutative (abelian) group by multiplication. In addition, the study has shown that the order of the group D = k 2 + 4b  u2  Z p is CGLb,k ( 2, Z p ) for p2 − 1.

Obviously, a (a + k ) − b  0 if and only if

D = k 2 + 4b  u2  Z p .

Further, we shall accept that

  a 1   1 0   t   , s   ,   b a + k   0 1     CGLb,k (2, Z p ) = t, s, a,b, k  Z p ,  . t, s  0,    D = k 2 + 4b  u2  Z p 

This paper aims to build a Galois field of square matrices of order 2 based on the group of matrices CGLb,k ( 2, Z p ) , thus substantiating a theoretical basis for developing schemes for the cryptographic transformation of information. 2. Diagonalization of Matrices

From CGLb,k ( 2, Z p ) Note that, according to the study [28], permutable matrices of simple structure can be brought into diagonal form simultaneously, that is, by a similarity transformation.

By matrices of simple structure, we mean matrices of order n , which have linearly independent eigenvectors [28]. Since the eigenvectors corresponding to pairwise different characteristic numbers are always linearly independent, a sufficient condition for the matrix to have a simple structure is that all the roots of the characteristic equation are different [28–29].

The characteristic polynomial of the matrix

 a 1  A =   CGLb,k (2, Z p ) is  b a + k 

A −  E = a −  b

1 a + k −  = where E is an identity matrix of size n = 2 .

The discriminant of the characteristic equation is

D = (2a + k )2 − 4(a2 + ak − b) = k 2 + 4b .

If D value is a quadratic nonresidue in the prime field of integers Z p ( D = k 2 + 4b  u2  Z p ) , the characteristic polynomial has no roots in Z p . Since the power of the equation is n = 2 , the polynomial is irreducible over the Z p field.

Consider an irreducible

f ( x) = x2 − D  Z p  x . polynomial

The simple algebraic extension of degree 2

over Z p is defined as a quadratic field Fp2 = Z p  D  [30], where D = k 2 + 4b  u2  Z p .

Galois field Fp2 has the characteristic p

and degree 2 [ 3 ].

Remark 1. Fp2 is a field of decomposition

of characteristic polynomials for matrices from the group CGLb,k ( 2, Z p ) . Eigenvalues of the That is, there is a matrix C =  c11 c12  with  c21 c22  elements from Fp2 so that for each matrix A CGLb,k (2, Z p ) the product C −1  A  C is a diagonal C−1  A  C = 1 (a,t ) 0  .

 0 2 (a,t ) 

Here, we find such a matrix C .

matrix: Since C−1  A  C = 1 (a,t )  0 0 

 , then 2 (a,t )  matrix  a 1  tA = t     b a + k  Fp2 = Z p  D  are t 1,2 (a,t ) = (2a + k 

2

Thus, for the

characteristic tA −  E = t 2 A −  t

E = 0 ,

over the field D ) , t  0 .

(1) matrix tA , t  0 , the equation is whence 1,2 ( a,t ) = t 1,2 (a ) , where 1,2 ( a ) are the  a 1  eigenvalues of the matrix A =   over  b a + k  the field Fp2 = Z p  D  .

 t If  (a,t ) = (2a + k  D ) is one of the 2 roots of the characteristic polynomial irreducible over Z p , where   Fp2 , then, by Theorem 2.14 from [ 3 ], the other root of the equation is  p (a,t ) = t (2a + k D ) .

2

The eigenvalues for the matrix sE are

1,2 ( s ) = s  0 .

Lemma 1.3.19 from [29] proves that the

family of diagonalizable matrices is a commutative family if and only if it is simultaneously diagonalizable. Based on this lemma, we formulate our next remark.

Remark 2. The commutative family of

matrices CGLb,k ( 2, Z p ) over the field is simultaneously Fp2 = Z p  D 

 diagonalizable.  a 1   c11 t      b a + k   c21 c12  = c22   c11 =   c21 c12 1 (a,t )

0 c22 

After multiplying the comparing them, we arrive at 0 

.

2 (a,t )  t (ac11 + c21 ) = c111 (a,t ),  t (bc11 + (a + k ) c21 ) = c211 (a,t ),  t (ac12 + c22 ) = c122 (a,t ), t (bc12 + (a + k ) c22 ) = c222 (a,t ).

Considering that 1,2 ( a,t ) = t 1,2 (a ) , we rewrite the equation system as: matrices and ac11 + c21 = c111 (a),  bc11 + (a + k )c21 = c211 (a),  ac12 + c22 = c122 (a), bc12 + (a + k )c22 = c222 (a). (a − 1 ( a)) c11 + c21 = 0,  bc11 + (a + k − 1 (a)) c21 = 0,  (a − 2 ( a)) c12 + c22 = 0,  bc12 + (a + k − 2 ( a)) c22 = 0.

The last equation system transformed into the next one: can be

We take the first eigenvalue of the matrix

 a 1  2a + k + D tA = t   b a + k  as 1 (a) = 2 . Then the second eigenvalue of the matrix tA is 2a + k − D 2 (a) = .

2

From the first two equations of the system, we have:

We shall accept c11 = 1. Then c21 = k + D 2 and the first eigenvector of the matrix C is  1    e1 =  k + D  .

 2 

The second eigenvector of the matrix C can be found similarly from the other two  1    equations of the system: e2 =  k − D  .  2   1 1  Then the matrix C =  k + D k − D  .

 2 2 

Note that the matrix C is independent of a

and t values and is common for CGLb,k (2, Z p ) .

Here, we perform a verification to complete the presentation.

 k − D  C−1  A  C = C1  k +2 D −1t  ba a +1 k    − 2 1  1 

 k − D  =

2   1   k + D

 2 = t  2a + k2+ D 0  =

 0 2a + k2+ D  = 1 (0a,t ) 2 (0a,t ) .

Consider the set of nondegenerate diagonal

matrices D over the field Fp2 = Z p  D  :   0   D =  0  p ,  Fp2  . (2) 

Remark 3. The mapping g ( A) = C−1  A  C defines a one-to-one correspondence (bijection) between matrices from CGLb,k (2, Z p ) and diagonal matrices from D .  Hence, g : CGLb,k (2, Z p )  D .  Proof.

Let A1, A2 CGLb,k (2, Z p ) , A  A2 , 1,1p 1 and 2 ,2p are eigenvalues of matrices A1 and A2 correspondently.

Then

C−1  01 01p   C  C−1  02 02p   C   1  2.

The number of different matrices of the set

D is equal to p2 −1, which corresponds to the order of the multiplicative abelian group CGLb,k (2, Z p ) .

This implies that the mapping g = g ( A) establishes a one-to-one correspondence between CGLb,k (2, Z p ) and D . 3. Galois Field of Square 2×2

Matrices

We shall use the notation

  a 1   1 0  t   b a + k , s   ,

 0 1   Fb,k =  t, s, a,b, k  Z p , 

D = k 2 + 4b  u2  Z p  for the matrix family, where p is a prime number and b , k are fixed in Z p .

Theorem 1. The matrix family Fb,k is a Galois field of order p2 with usual ordinary operations of matrix multiplication and addition.

Proof.

It is obvious that Fb,k = CGLb,k (2, Z p )  , where  =  0 0 .

 0 0

Here, we show that the addition operation

is closed in the set Fb,k .

According to Remarks 2 and 3, there is the same matrix C for random matrices A1 and A2 from Fb,k that 0  2p   C−1;

 1 + 2  A1 + A2 = C    0

The Galois field Fp2 = Z p  D  has a  characteristic p . Therefore, due to Proposition 7.1.4 from [30], an equation 1p + 2p = (1 + 2 ) p is satisfied.

Consequently, for

A + A2 = C  3 1  0 0  3p   C−1 3 = 1 + 2 : C−1  ( A1 + A2 )  C = 3 0   0 3p   D . Obviously, C−1    C = .

According to Remark 3, there is a single

matrix A3 CGLb,k (2, Z p ) , where A + A2 = A3  Fb,k .

1 0  3p  , 3  Fp2 . Therefore,

Thus, we can present the matrix family Fb,k in the form of a fixed matrix C :   0  

 0  p   C−1,  Fp2 = Z p  D  .

Fb,k = C   

Therefore, Fb,k is an algebraic field for ordinary operations on matrices, and its order is p2 . *

Corollary 1. The multiplicative group Fb,k of the finite field Fb,k is cyclic, i.e. the group CGLb,k (2, Z p ) is cyclic.

Corollary 2. The number of primitive

elements in the field Fb,k is  ( p2 −1) , where  (m) is the Euler function of m .

4. Conclusion

Thus, this study has shown that the commutative family of matrices   a 1   1 0   t   , s   ,   b a + k   0 1   CGLb,k (2, Z p ) =  t, s, a,b, k  Z p ,   t, s  0,  a (a + k ) − b  0  is simultaneously diagonalizable over the field Fp2 = Z p  D  .



The matrix performing diagonalization is

 1 1  C =  k + D k − D  . The matrix C does   2 2  not depend on the values of a or t and is

It was also shown that the matrix family

 0 0 Fb,k = CGLb,k (2, Z p )  , where  =   ,  0 0 forms a Galois field of order p2 with usual matrix multiplication and addition operations. Consequently, CGLb,k (2, Z p ) is a multiplicative cyclic group.

The finite field of square 2 2 matrices investigated in this study can be applied to construct new schemes of cryptographic matrix transformations. In addition, the approach used to find the finite field of matrices of order 2 allows extending this approach to the study of square matrices of higher orders. Further research might explore a 3 3 matrix set and attempt to construct the

Galois field in it.

5. Acknowledgments This research was funded by the Ministry of Education and Science of Ukraine under grant 0123U100270. or common for CGLb,k (2, Z p ) . [25] A. Shcherba, et al., Families of Square

Commutative 2х2 Matrices, in:

Cybersecurity Providing in Information and Telecommunication Systems (2023). [26] T. Springer, Linear Algebraic Groups, 2nd ed., Modern Birkhäuser Classic (1998). doi: 10.1007/978-0-8176-4840-4. [27] A. Baker, Matrix Groups. An Introduction to Lie Group Theory, Springer (2002). doi: 10.1007/978-1-4471-0183-3. [28] F. Gantmacher, The Theory of Matrices,

Reprinted, American Mathematical

Society, Providence, RI (1959).

[29] R. Horn, C. Johnson, Matrix Analysis, 2nd ed., Cambridge University Press (2012). doi: 10.1017/CBO9781139020411. [30] K. Ireland, M. Rosen, A Classical

Introduction to Modern Number Theory,

Graduate texts in mathematics, 2nd ed.,

Springer-Verlag, New York (1990).

References

Data Encryption Standard (DES), National Institute of Standards and Technology , U.S. Department of Commerce ( 1999 ).

Advanced Encryption Standard (AES), National Institute of Standards and Technology , FIPS 197, US ( 2001 ).

[3] R. Lidl , H. Niederreiter , Finite Fields, Data Science, no. I , vol. 2631 ( 2020 ) 30 - Encyclopedia of Mathematics and its 39 . Applications , 2nd ed., Cambridge [14] Digital Signature Standard (DSS ), University Press ( 1997 ). National Institute of Standards and

[4] W. Diffie , M. Hellman , New Directions in Technology, Gaithersburg, MD ( 2023 ). Cryptography, IEEE Transactions on Inf. doi: 10.6028/NIST.FIPS.186-5. Theory 22 ( 6 ) ( 1976 ) 644 - 654 . doi: [15] H. Huang , C. Li , L. Deng , Public-Key 10 .1109/TIT. 1976 . 1055638 . Cryptography Based on Tropical Circular

[5] R. Rivest , A. Shamir , L. Adleman , A Matrices , Appl. Sci. 12 ( 15 ) ( 2022 ). doi: Method for Obtaining Digital Signatures 10 .3390/app12157401. and Public-Key Cryptosystems , Commu- [16] X. Wang , S. Gao , Image Encryption nications of the ACM 21 ( 2 ) ( 1978 ) 120 - Algorithm for Synchronously Updating 126. doi: 10.1145/359340.359342. Boolean Networks Based on Matrix

[6] PKCS #1: RSA Cryptography Semi-Tensor Product Theory , Inf. Sci. Specifications Version 2.2, RSA 507 ( 2020 ) 16 - 36 . doi: 10 .1016/j.ins. Laboratories ( 2012 ). 2019 . 08 .041.

[7] T. Elgamal , A Public Key Cryptosystem [17] C. Rupa , Greeshmanth, M. Shah , Novel and a Signature Scheme Based on Secure Data Protection Scheme Using Discrete Logarithms , IEEE Transactions Martino Homomorphic Encryption, J. Inf. Theory 31 ( 4 ) ( 1985 ) 469 - 472 . doi: Cloud Comput. 12 ( 1 ) ( 2023 ) 47 . doi: 10 .1109/TIT. 1985 . 1057074 . 10.1186/s13677-023-00425-7.

[8] IEEE Standard Specifications for Public- [18] F. Makoui , T. Gulliver , M. Dakhilalian , A Key Cryptography , IEEE ( 2000 ). doi: New Code‐Based Digital Signature Based 10 .1109/IEEESTD. 2000 . 92292 . on the McEliece Cryptosystem , IET

[9] A. Bessalov , et al., Analysis of 2-Isogeny Commun . 17 ( 10 ) ( 2023 ) 1199 - 1207 . Properties of Generalized Form Edwards doi: 10 .1049/cmu2.12607. Curves, in: Workshop on Cybersecurity [19] R. McEliece , A Public-Key Criptosystem Providing in Information and Based on Algebraic Coding Theory, DSN Telecommunication Systems , vol. 2746 Progress Report ( 1978 ) 42 - 44 . ( 2020 ) 1 - 13 . [20] F. Dupont , A New Shamir's Three Pass

[10] A. Bessalov , et al., Multifunctional CRS Random Matrix Ciphering Mechanism, J. Encryption Scheme on Isogenies of Non- Comput. Virol. Hacking Tech . ( 2023 ). Supersingular Edwards Curves , in: doi: 10.1007/s11416-023-00467-0. Workshop on Classic, Quantum, and [21] E. Faure , et al., A Method for Reliable Post-Quantum Cryptography , vol. 3504 Permutation Transmission in Short( 2023 ) 12 - 25 . Packet Communication Systems,

[11] A. Bessalov , et al., Implementation of the Information Technology for Education, CSIDH Algorithm Model on Science , and Technics ( 2023 ) 177 - 195 . Supersingular Twisted and Quadratic doi: 10 .1007/978-3- 031 -35467-0_ 12 . Edwards Curves, in: Workshop on [22] E. Faure , et al., Concept for Using Cybersecurity Providing in Information Permutation-Based Three-Pass and Telecommunication Systems , vol. Cryptographic Protocol in Noisy 3187, no. 1 ( 2022 ) 302 - 309 . Channels, Systems, Decision and Control

[12] A. Bessalov , et al., Computing of Odd in Energy V ( 2023 ) 99 - 113 . doi: Degree Isogenies on Supersingular 10 .1007/978-3- 031 -35088- 7 _ 7 . Twisted Edwards Curves, in: Workshop [23] E. Faure , et al., Permutation-Based Block on Cybersecurity Providing in Code for Short Packet Communication Information and Telecommunication Systems, Sensors 22 ( 14 ) ( 2022 ). doi: Systems , vol. 2923 ( 2021 ) 1 - 11 . 10 .3390/s22145391.

[13] A. Bessalov , V. Sokolov , P. Skladannyi, [24] J. Al-Azzeh , et al., Permutation-Based Modeling of 3- and 5-Isogenies of Frame Synchronization Method for Data Supersingular Edwards Curves , in: 2nd Transmission Systems with Short International Workshop on Modern Packets , Egyptian Inform . J. 23 ( 3 ) ( 2022 ) Machine Learning Technologies and 529 - 545 . doi: 10 .1016/j.eij. 2022 . 05 .005.