This paper presents a comparative analysis of several matrix analogs of the Diffie-Hellman algorithm, namely, Yerosh-Skuratov and Megrelishvili protocols, as well as alternative protocols based on irreducible polynomials and primitive Galois or Fibonacci matrices. Binary matrix is primitive, if the sequence of its powers in the ring of residues mod 2 forms a sequence of maximum length ( m sequence). Offer alternative protocols and discuss ways to improve the reliability of their.
The Diffie-Hellman algorithm (DH-algorithm) [1] assumes that two subscribers – Alice and Bob both know the public keys p and q , where p is a large prime number, and q is a primitive root. Subscriber Alice generates a random big number a , computes A qa mod p and sends it to Bob. In turn, Bob generates a random big number b , computes B qb mod p and sends it to Alice. Then subscriber Alice raises number B received from
Ka Ba mod p qba mod p .
Bob acts similarly, calculating Kb Ab mod p qab mod p . It is obvious that both parties receive the same number K because Ka Kb . Then Alice and Bob can use this number K as a secret key, e.g. for symmetric encryption because a foe who intercepts numbers A and B faces with virtually unsolvable (in a reasonable time) the problem of calculation K , under the condition, that numbers p , a and b were chosen big enough.
In order to form a secret encryption key in the public network by subscribers Alice and Bob, the authors [2] propose to use DH protocol in the cyclic group of matrices
M , and the matrix M is considered as public information. It is assumed that Alice generates a random index x , calculates the matrix M x and sends it to Bob. In turn, Bob generates a random index y , calculates the matrix M y and sends it to Alice. Then both subscribers raise the matrices obtained from a partner in their secret powers and calculate the sheared matrix (encryption key) K M xy M yx . The matrix M must be a high-order matrix (at least 100); so, the authors assert (by the way, without a proof), cracking key has invincible complexity. However, in [3] it has been proved, that Yerosh-Skuratov protocol can easily be cracked based on the generalized Chinese remainder theorem. 3
The essence of the protocol [4] is following. Binary initialization vector V and primitive matrix M of order n are accepted as a public key. Subscriber Alice generates a random index x , calculates the vector Va V M x and sends it to Bob. In turn, Bob generates a random index y , calculates the vector Vb V M y and sends it to Alice. Then Alice computes the key Ka Vb M x V M yx , and Bob computes the key Kb Va M y V M x y . It is quite obvious that using such data exchange protocol, both parties receive the same private key K , because Ka Kb K .
The algorithm of generating the matrices in Megrelishvili protocol is fairly simple and can be explained by the following calculation scheme
M1 1,
1
M 3 1
0
0
M1
1
1
0 ,
0
1 0
1
M 5 0
1
0 1
1
М 3
0
0 1
0
1 ,
0
1 0
(
As it follows from (
The matrix form of direct (for simplicity denoted by number 2) and inverse (denoted by number 3) classical Gray transforms (codes) [6] can be presented in the form 1 1 0 0 0 1 1 0 2 : ; 0 0 1 1 0 0 0 1 1 1 1 1 0 1 1 1 3 : ; 0 0 1 1 0 0 0 1 where as an example, the order of the matrix n is set n 4 .
Matrices (
The set of operators (
Assertion. The primitiveness of matrices M is invariant to the group of linear
transformations of the CGC G generating matrix M and transformations of
similarity over these matrices.
(
The group includes the following operators: cyclical shift, assess statement, inversion and conjugation as well as arbitrary combinations of these operators. Transformation forms matrix M p , which is similar to M and determined by the relation where P is a permutation matrix. 4
M p = P M P1 , This section proposes two options for alternative matrix protocols of secret key exchange on the open channel of communications. The procedure for the formation of the encryption key K in the first version of the protocol is based on the use of two public and one private key for both subscribers. As a public key a binary initialization vector V of n order and any irreducible polynomial (IP) n of n order are chosen. Private keys are primitive (forming) elements of the Galois field GF (2n ) over the IP n , from which the subscribers (Alisa and Bob) form the primitive secret transformation matrices G(a ) and n
G(b ) respectively. The element of the field
n GF (2n ) is primitive over IP n , if the minimum rate e , at which (e 1) mod assumes the value e 2n 1 .
Matrix G() we call Galois matrices. The synthesis of algorithm for such matrices n is explained on a concrete example. Let’s IP 8 100101101 , and the generating element (GE) of subscriber Alisa a 111 . We obtain 1 1 1 1 0 1 1 1 1 1 1 0 1 1 0 1 1 1 1 0 0 0 0 0 .
0 1 1 1 0 0 0 0
A Ga 0 0 1 1 1 0 0 0
0 0 0 1 1 1 0 0
0 0 0 0 1 1 1 0
0 0 0 0 0 1 1 1
(
According to (
The introduced Galois matrices have some interesting properties. First, the matrix product is commutative, i.e. A B B A . At the same time, secondly, if at least one of the GE is not a primitive of the IP, the commutative property of matrices is lost. Based on the above properties of Galois matrices a key exchange protocol was proposed.
We consider that initialization vector V and the IP are known. Alice chooses a secret primitive over GE a , forms a Galois matrix A , calculates the vector Va V A and sends it to Bob. In turn, the subscriber Bob selects a primitive GE b , forms a matrix B that calculates the vector Vb V B and sends it to Alice. After that, both parties multiply vectors obtained from the partner, in own secret Galois matrix. Thus, a shared secret key K will be formed by the fact that the product of primitive Galois matrices over the same IP is commutative, and this implies the identity
Ka Vb A V B A
Kb Va B V A B .
Instead of Galois matrices G , Fibonacci matrices F can be used in the protocol with the same success. Fibonacci matrices are associated with Galois matrices by equation
F G, or F = G ; G F , where means the operator of right transposition, i.e. transposition with respect to the auxiliary diagonal matrix.
In the second alternative embodiment of the protocol the secret key K is computed in two rounds. In the first round, which repeats the above-considered first version of the protocol, a common to both subscribers secret binary vector of n th order Vp is formed. On the basis of this vector, Alice and Bob compute the common permutation matrix P . One can propose different ways of constructing matrices P . Let us consider one of them. Let’s n 8 and N is the decimal equivalent of the vector Vp . The task is to create permutation matrix P8 of order eight for value N . Choose one or another way of numbering elements of matrices P8 from 0 to 63. Calculate the value n8 N mod 64 and write 1 in that element of the matrix, whose number is equal n8 . After that, delete from the matrix P8 the row and column, which contains 1. We obtain a matrix P7 of 7-th order, whose elements are numbered from 0 to 48. Find the value n7 N mod 49 , which is determined by the location 1 of the matrix P7 and, consequently, in the matrix P8 . Following the proposed method, one can simply construct a permutation matrix P of any order.
Let proceed to the second variant of the encryption keys protocol. This protocol uses two public keys, which are the initialization vector V , and the irreducible polynomial , and also two private keys. These keys are generated by Alice and Bob as a random primitive over IP Gees and . The protocol runs in two rounds. In the first round based on public keys V , and secret GE network operators calculate the total permutation matrix P . The second round is performed in the following order. Alice chooses a primitive over GE a , forms Galois matrix A , then similar matrix Ap P A P1 , computes a vectorVa V Ap , and sends it to Bob. In turn, Bob chooses a primitive over GE b , forms Galois matrix B , then similar matrix Bp P B P1 , computes a vector Vb V Bp and sends it to Alice. After that, both parties multiply vectors obtained from partners on their secret similar Galois matrix. Thus, the shared key K will be generated due to the fact that the matrices Ap and Bp maintain the properties of primitiveness and commutatively of primary matrices A and B , respectively. 5
One of the major drawbacks of alternative algorithms key generation algorithms for open key cipher infrastructure, in particular the mentioned above the way of synthesis Galois matrix (by the diagonal fill method), is that it could be easily compromised. To prove that, let's see the vector created by Alice.
By the theory of polynomials of one variable x , we know that product of any polynomial n x power of n by x is equivalently either simple shift of polynomial for one bit left or incrementing the power of polynomial,
Va V G(fa ) ,
n x n x n1 x .
Taking formula (7), let's represent the Galois matrix G(fna ) the power of n by, x n 1 x n 1 x n 2 x n 2 G (fn) (m od f n ) (m od f n ) E x x 1 where E the unit matrix.
From formulas (
(9) (10)
For example, let's use the matrix G(fna ) , given by expression (
The security of alternative protocols could be increased up to security level of algorithms based on problem of factorization of modular multiplication of big numbers if we assume that there is secret parameter , both known to Bob and Alice.
The modification of protocol [6] is the be following. Assume, there are authorized subscribers that have secret parameter as binary vector of n order. Parameter could be transported from Alice to Bon (or otherwise), e.g. by RSA protocol. Alice is generating random of n order number a and computing generating element a a mod fn , (11) by means of generating element Alice is forming Galois matrix Gfna , calculating vector Va V G(fa ) and sends it to Bob. In the same way, Bob send to Alice vector n
Vb V G(fb ) , where b b mod fn .
n
As it shown above, generating elements a and b could be easily computed, so authorized subscribers Alice and Bob, but not Eva, could calculate secret parameter of partner. As example, by formula (11) Bob calculates a a 1 mod fn , that gives him and Alice ability to calculate secret key K a b mod fn . Key K as well as any function of it, could be taken as a secret parameter K for session key generation for public key cipher channels.
We call that way of key generation – protocol (algorithm) of vagus keys. Vagus keys algorithm could be used in both motioned above protocols. The major benefit of vagus key generation algorithm is protection from "man in a middle" type of attack. It's been archived by including in Galois matrices key generation elements of secret element , known only by Bob and Alice. In case of secret element is changed by element e of Eva, makes it impossible to Eva to calculate parameters a , b as well as general cipher key K . 6
The article analyzes the known matrix algorithms for exchanging encryption keys between subscribers of a network of open communication channels. The algorithms are based on the modified asymmetric Diffie-Hellman protocol. The essence of the modification is reduced to replacing the large prime numbers of Diffie-Hellman algorithm by assurance nondegenerate primitive binary matrices of high order. Methods of synthesis of these matrices are proposed based on both the generalized Gray codes, and irreducible polynomials. New key exchange matrix protocols have been developed. The protocols developed are superior for cryptographic strength to known cryptographic protocols, particularly Yerosh-Skuratov and Megrelishvili protocols described in this paper.
The proposed variants of vector-matrix protocols for exchanging by cryptographic keys on open communication channels have a good prospect to be applied for symmetric encryption in computer networks protected from the substitution of data, providing the necessary level of protection of private keys from unauthorized access. These protocols can make a strong competition to more resource-intensive RSA protocol.