key: cord-0549541-sbkjo51g
authors: Kumari, Shipra; Mahato, Hrishikesh; Pushp, Sumant
title: On Construction of weighted orthogonal matrices over finite field and its application in cryptography
date: 2020-05-29
journal: nan
DOI: nan
sha: e8ddcd11d09491f9ac15dedc24fbe13cd3fe8a14
doc_id: 549541
cord_uid: sbkjo51g

In this article, we propose a method to construct self orthogonal matrix, orthogonal matrix and anti orthogonal matrix over the finite field. Orthogonal matrices has numerous applications in cryptography, so here we demonstrate the application of weighted orthogonal matrix into cryptography. Using the proposed method of construction we see that it is very easy to transmit the private key and can easily convert the encrypted message into original message and at the same time it will be difficult to get the key matrix for intruder.

"code" is designed to have a large minimum distance between its code words. As opposite of "large minimum distance" is "small maximum distance". Farrell used the term "anti-code" to describe a set of n-tuple designed to have small maximum distance between its code words [4] . To get inspired by Farrel's "anti code" James L. Massey [4] introduced anti-orthogonal matrix, as opposite of I is −I. If BB T = −I then B is known as anti-orthogonal matrix. If each row of a matrix is orthogonal to every row including itself is self orthogonal matrix i.e. if CC T = 0 , then C is a self-orthogonal matrix.

Cryptography is the study of techniques through which a secured communication of message or information executed i.e. communicated message/information cant be understood by anyone who is not the intended receiver. The method to obtain the cipher text from plain text is encryption and the reverse method is decryption. There are several techniques for encryption scheme [12, 9, 6, 1] . In 1929 Lester S. Hill [6] introduced the Hill cipher in which an invertible matrix is used as a private key and inverse of that matrix is used to decrypt. It is very difficult to obtain the inverse of a matrix for large size. Later on orthogonal matrices are used as a private key to disposed off the calculation of inverse of the matrix. As inverse of an orthogonal matrix is its transpose. C. Koukouvinos and D.E. Simos [1] also developed an encryption scheme using circulant Hadamard core in which the first row of the Hadamard core required to be transmitted as a private key.

In this paper we present a method to construct the weighted orthogonal matrices over a finite field GF (q), where q = p α such that p is a prime and α is a positive integer. Also we develop an encryption scheme using the weighted orthogonal matrices over finite field GF (q). Our main aim is to protect the information about the elements of the key matrix. In this encryption scheme there is no need to transmit the matrix or first row or any element of the matrix to get the private key. Along with the encrypted message we need to transmit three numbers which include the size of the key matrix and additionally a primitive polynomial in case of α > 1. So for intruder it will be difficult to find the private key and the numbers make an easy transmission. The paper is organized as follows:

In section 2, the required definitions and information have been discussed as preliminaries.

In section 3, we present the methods to construct orthogonal, self-orthogonal and antiorthogonal matrices of order q over the finite field GF (q). In section 4, we present the application of orthogonal matrix into cryptography. Here encryption scheme and analysis of time complexity of the scheme have been discussed. In section 5, we provide the example of the encryption scheme defined in section 4 and in section 6 we conclude the results.

Definition 2.1. Weighted orthogonal matrix over a field A square matrix A = [a ij ] n×n , where a ij ∈ GF (q) is said to be an orthogonal matrix with weight k if AA T = kI n (1)

over GF (q).

In particular if k = 0, 1, −1, then A is a self orthogonal matrix, orthogonal matrix and anti orthogonal matrix of order n respectively over GF (q)

Remark 2.1. If q = 3, then the matrix defined over GF (3) which satisfies the equation (1) is a weighing matrix of order 3.

Let GF (q) be a finite field of order q. A primitive root is an element of GF (q) which is a generator of the multiplicative group of the field GF (q).

In this section we discuss some method to construct the orthogonal matrices of order q over GF (q). Let q = p α , where p is a prime and α is any positive integer, GF (q) = {0 = a 0 , a 1 , a 2 , · · · , a q−1 } Lemma 3.1. Let q = p α , where p is a prime and α is any positive integer. Then for any

Proof. Let g be a primitive root of GF (q) so for every non-zero element a i ∈ GF (q), a i can be written as

As g is a primitive root of GF (q) and 1 ≤ k < q − 1 so g (q−1) ≡ 1(mod p) and g k = 1. Thus

2 . So, each element of i th row can be expressed as

Now, inner product of u th row with itself is

A is a self orthogonal matrix of order q. Now, to show that A is a skew symmetric matrix it is enough to show that a ij = −a ji .

So, A is a skew symmetric matrix of order q.

In particular, if matrix A has same sequence of leading rows and columns then it can be observed that all diagonal entries of A are 0.

, is an orthogonal matrix with weight r 2 , a quadratic residue in GF (q).

Here

Remark 3.1. For any q = p α , 1 is a quadratic residue in GF (q). So B + rI is an orthogonal matrix of order q for r 2 ≡ 1(mod p). However, for q = p α with p ≡ 1(mod 4), −1 is a quadratic residue in GF (q) implies that B + rI is an anti-orthogonal matrix of order q for r 2 ≡ −1(mod p).

From the above discussion we observed that the weight of the orthogonal matrices is a quadratic residue of GF (q). It is know that each element of GF (2 α ) is a quadratic residue in GF (2 α ) [8] . So for each k ∈ GF (2 α ) there exist an orthogonal matrix of order 2 α with weight k.

We are interested to find orthogonal matrices of any weight k ∈ GF (q) over GF (q), where q is an odd prime power. It is known that every element of a finite field GF (q) can be written as sum of two squares [8] .

Using this result the orthogonal matrices of order 2q of weight k ∈ GF (q) may be obtained in next results. Proof. Let A = [a ij ] and B = [b ij ] be two self orthogonal matrices over GF (q). Then using

Hence AB ≡ 0(mod p) Theorem 3.5. If A and B are two skew symmetric self orthogonal matrices of order q = p α , where p is a prime, then there is a weighted orthogonal matrix of order 2q with any weight k ∈ GF (q).

Proof. Since A and B are skew symmetric self orthogonal matrices of order q. Since each element of GF (q) can be expressed as a sum of two squares, consider k = r 2 + s 2 for some r, s ∈ GF (q). Consider

Then

Therefore A ′ is a weighted orthogonal matrix of order 2q with weight k.

In particular, if r = 1 and s = 0, A ′ is an orthogonal matrix of order 2q.

Theorem 3.6. Let A + rI be a weighted orthogonal matrix of order p with weight r 2 . If H 4n is a Hadamard matrix of order 4n then the kronecker product of (A + rI) and H 4n is a weighted orthogonal matrix with weight 4nr 2 .

Proof. Let A + rI be a weighted orthogonal matrix of order p with weight r 2 . So,

Since H n is a Hadamard matrix of order 4n so by the definition of Hadamard matrix

This shows that kronecker product of Hadamard matrix and weighted orthogonal matrix is again a weighted orthogonal matrix.

Note: If gcd(n, p) = 1 then H 4n ⊗ (A + rI) is a self orthogonal matrix of order 4np.

Orthogonal matrix is widely used in cryptography. In this section we have used the weighted orthogonal matrix, discussed above, in encryption scheme. Suppose the language, in which message or information is written, contains q = p α (p is a prime) distinct characters. Let M be the numeric plain text of the corresponding message which has to be transmitted securely. Here weighted orthogonal matrix of order q is used to encrypt the message. The encrypted message C is obtained from the plain text M using the transformation

where W is a weighted orthogonal matrix of order q with weight r 2 . W is defined as

where A is a self orthogonal matrix of order q. Using theorems (3.2) and (3.3) the key matrix W of order q = p α over a field GF (q) may be constructed. For α = 1 the field may be considered as Z q but for α > 1 it requires a primitive polynomial P (p α ) to construct the required field GF (q). Thus formation of private key for α = 1 it requires the numbers (p, t, r) however for α > 1 it requires P (p α ) as an additional information.

Here algorithm has been discussed to develop the key matrix

The encryption algorithm for the scheme is given by:

In general, to obtain the original message it requires W −1 . Since W is a weighted orthogonal matrix, so W −1 = lW T , where l is a solution of r 2 x ≡ 1(mod p). The intended receiver has to decrypt the message using the transformation

Along with the security, the main objective of the cryptography is to decrypt the message uniquely. Form an array Z q and Z q = [0, 1, 2, · · · , q − 1] element of the field GF (q) 4: for i ← 0 to q − 1 do Form an array F and element of F is defined as:

end for 13: end if 14: Construct a square matrix A = [e ij ] of order q 15: for i ← 0 to q − 1 do 16: for j ← 0 to q − 1 do 17:

end for 19: end for Algorithm 2 Encryption Algorithm Require: Require msg to encrypt 1: select (p, α, t, r, P (p α )) 2: if α = 1 then 3:

k ← (p, t, r) set private key 4: else {α > 1}

k ← (p, t, r, P (p α )) set private key 6: end if 7: W ← A + rI construct matrix A using algorithm (1) 8: M ← convert(msg) convert msg into its numerical value 9: C ← W M(modp) 10: Transmit(k, C)

as l is a solution of r 2 x ≡ 1(modp)

It shows that message is uniquely decrypted. The decryption algorithm is defined below

Require: Require obtained cipher text 1: receive (C, p, t, r, P (p α )) 2: obtain the value of l *// using euclidean algorithm 3: construct matrix A *// using algorithm (1) 4: W ← A + rI 5: M ← lW T C(mod p) *// decrypt the message

In the above discussed encryption scheme, sender transmits numbers (p, r, t) and P (p α ) in either case as an additional information to form the private key. To get the plain text intended receiver has to use the transformation (6) . So receiver has to find out W T and l only. The matrix W T and integer l may be obtained by using algorithm (1) and the Euclidean algorithm respectively. The time complexity to find W T and the integer l is O(q 3 ) and O(log q) the respectively. The main aim of encryption scheme is to protect the information about the private key. But the intruder always tries all possible combinations to find the keys and checks which one of them return the plain text . Since in this encryption scheme numbers (p, r, t) and P (p α ) in either case as an additional information will be transmitted as a private key. So it will be difficult to guess the size of the key matrix. And if any one could guess the order of a key matrix it is still difficult to obtain the key matrix W . As matrix W consist the elements of GF (q). So the size of the key space, K(W ), is q q 2 . Thus the computational complexity to find the key matrix W is O(q q 2 ) and it increases exponentially.

1. To form the private key numbers (p, r, t, P (p α )) is used, so it is easy to transmit.

2. As orthogonal matrix is used to encrypt the message so it is easy to decrypt the message as inverse of an orthogonal matrix is its transpose.

3. For intruder after knowing the actual size still it is difficult to find the key matrix as the computational complexity to find the key matrix is O(q q 2 ).

Suppose the plain text COVID−19 has to be transmit. Firstly we convert the plain text into its corresponding numerical value (ASCII Code)

C O V I D − 1 9 67 79 86 73 68 45 49 57

Here highest value present in the plain text is 86. Consider p = 89 (we need to choose a prime number which is greater or equal to the highest numeric value present in plain text).

In plain text we need to add "space" 81 times. Thus 

We transmit C, 89, 5, 2 .

To obtain the plain text intended receiver has to construct the weighted orthogonal matrix W using algorithm (1) . 

In this paper we have developed a method to construct weighted orthogonal matrices over a finite field GF (q). There is no non-zero self-orthogonal matrix over R however self orthogonal matrix has been developed over GF (q) in modular arithmetic. Furthermore an encryption scheme has been developed using the obtained weighted orthogonal matrices. In this scheme it is easier to transmit a finite number of numbers which yields private key.

Encryption schemes based on Hadamard Matrices with Circulant Cores

The Theory of Error Correcting Codes Amsterdam

A theorem in finite projective geometry and some applications to number theory

Anti orthogonal and Self-Orthogonal Matrices and their Codes, Signal & Information Processing Laboratory Swiss Federal Institute of Technology CH-8092

Orthogonal Matrices with Zero Diagonal

Cryptography in an Algebraic Alphabet

Combinatorial Theory, Wiley Interscience Series in Discrete Mathematics

Integral Matrices, A Series of Monographs and Textbooks

Cryptography Based on the Matrices

Orthogonal Circulant Matrices over Finite Fields, and How to Find Them

Orthogonal Matrices with Zero Diagonal-II

Encryption Schemes using Finite Frames and Hadamard arrays

Linear Binary Anticodes

On orthogonal matrices

Finite Fields, Semester

Elementary Number Theory: Primes, Congruences, and Secrets