Cryptographic Key Exchange Method for Data Factorial Coding

Abstract

The paper proposes a new cryptographic key exchange method. The basic idea of the proposed method is to use a permutation of a given set as a transformation object. The mathematical background of the method is the property of permutations to be decomposed into the product of disjoint cycles, the property of unique factorization of the product of disjoint cycles raised to the powers smaller than their order, and the complexity of factorization of the product of permutations whose cycles are noncommutative. The conditions to be met by the transformation parameters are defined. The concepts of cycleand block-noncommutative permutations are introduced. These properties of two permutations known to all participants in information exchange are sufficient for the correct operation of the method. The key space cardinality of the values of cycles' exponents of two open permutations is investigated. It is shown that this cardinality is maximized if the disjoint cycles in the decomposition of open permutations are 3-cycles. The block diagram of a cryptographic system that implements the proposed method is investigated. Its work is described. The proposed method and system make it possible to generate a cryptographic key for information factorial coding without using a secure communication channel. They can also be used to form a non-permutation key.

Keywords

• cryptography
• method
• key exchange
• permutation
• factorial coding

-

Several information security tasks, such as providing authentication, confidentiality, and integrity, are solved simultaneously when transmitting information in communication systems and systems of managing various technological processes. In particular, this is observed when transporting information arrays through noisy communication channels, including through tunneled protocols on computer networks. A separate solution of these tasks is associated with the use of different mathematical methods and algorithms. This leads to an increase in the load on means of information transforming and requirements for their productivity, to an increase in introduced redundancy, and, as a consequence, to a decrease of a relative transmission rate. These

circumstances actualize the problem of providing information security during its storing and transmitting in telecommunication systems and networks by integrating channel coding and cryptographic security methods.

The factorial coding methodology [ 1 ] provides creation and study of methods for combining the following types of data protection in a single procedure:  protection against errors caused by noise in communication channel;  protection against unauthorized data modification;  protection against unauthorized data access.

Separable factorial codes (FC) [ 2, 3 ] provide information integrity control and do not ensure its confidentiality. Code combinations of such codes contain separate information and control parts. The control part is a permutation  or its part. A permutation of a set of M elements is a bijection from a finite set X of cardinality M into itself. We denote the elements of a finite set X by nonnegative integers from 0 to M 1 . Then X  0,1, , M 1 and the permutation  will be written as a sequence of elements of the set X , where each of the numbers 0,1, , M 1 is applied only once (without gaps and repetitions).

Non-separable FCs [ 4-6 ] provide protection against unauthorized data access and are able to detect and correct a significant part of errors. Code combinations of such codes are formed by converting an information word A x into a permutation  . They do not have separate information and control parts (as, for example, CRC codes have). In addition, non-separable FCs are self-synchronizing codes. A selfsynchronization property of the code removes the problem of frame synchronization and eliminates the need for a delimiter in a data block header structure. Because of this, an amount of redundancy introduced during coding is reduced.

The key sequences for factorial coding methods are permutations. These key permutations are kept secret.

When encoding and decoding factorial codes, the same permutation is used. Therefore, factorial coding methods have the disadvantage of symmetric cryptographic transformation, such as the need to form a secret communication channel to transmit key data.

In [ 7 ], Whitfield Diffie and Martin Hellman proposed the first and the best-known key agreement method. This method and the corresponding cryptographic device is patented in the US with Ralph Merkle [ 8 ]. The proposed protocol (known as the Diffie-Hellman key exchange) allows two parties to form a shared secret key based on their own secret keys and each other's public keys. Cryptanalyst knows only public keys of two parties. He is unable to calculate their shared secret key within an acceptable amount of time and limited performance of computing facilities.

This method uses a vulnerable to eavesdropping channel. However, it does not provide user authentication. Therefore, it is vulnerable to the man-in-the-middle attack. To solve this problem, a number of modifications to the method have been proposed. In particular, they are outlined in [ 9, 10 ].

A cryptographic strength of the Diffie-Hellman protocol and its modifications, as well as the El Gamal algorithm [ 11 ], is based on the complexity of the discrete logarithm problem. At the same time, quantum computers using the Shore algorithm [ 12 ] will easily solve the problems of discrete logarithmization and factorization of integers.

To date, a number of post-quantum key exchange protocols have been developed, including Supersingular isogeny Diffie–Hellman key exchange [ 13 ], NTRU [ 14 ], Ring Learning with Errors Key Exchange [ 15 ].

One of the most promising modern research areas in the field of cryptographic key exchange is their quantum distribution [ 16-18 ]. However, to date, this direction has limitations on transmission distance and communication network structure. In addition, all of the above key exchange methods are not adapted for data factorial coding that uses permutations.

The purpose of this work is to provide the ability to generate cryptographic keys for data factorial coding without using a secret communication channel. The key exchange method should have the prerequisites for use in post-quantum cryptography [ 19-25 ].

The work is organized as follows. In Section 2, we describe our cryptographic key exchange method. In Section 3, we analyze a key space cardinality and conditions to its maximization. A cryptographic system and a description of its work are given in Section 4. In the last section, we present the conclusion. 2

Construction of Cryptographic Key Exchange Method

The essence of the proposed approach is the following.

 Each exchange party generates a shared key by converting permutations received from the other party. In this case, the direct transformations of permutations on each party of information exchange are easy to implement, and the inverse transformations are almost impossible to implement.

 The generated key is used for data factorial coding during forward and reverse transformations of messages transmitted by an insecure communication channel.

The method for factorial coding key exchange over an open channel involves the following procedures.

 Two parties Alice and Bob know two permutations,  and  , and their den  n  compositions into the products of disjoint cycles:   i ,    j . i1 j1  Alice generates a random secret key in the form of two vectors k  k1, k2 , , kn   and m  m1, m2 , , mn   of dimensions n   and n   , moreover 0  ki  l i  1 , 0  m j  l  j  1 , where l  i  , l  j  are the orders of cycles  i and  j , respectively.  Bob generates another random secret key in the form of two vectors t  t1, t2 , , tn   and s   s1, s2 , , sn   of dimensions n   and n   , and 0  ti  l i  1 , 0  sj  l  j  1 . n  n   Alice forms a permutation Y1   1 1 , where  1   iki , 1   jmj . Sends i1 j1 Y1 to Bob.

Y2 to Alice.

n  n   Bob forms a permutation Y2   2 2 , where  2   iti , 2   jsj . Sends i1 j1  Receiving Y1 , Bob computes the shared key K   2 Y1 2 . Once getting Y , 2 Alice obtains K   1 Y2 1 .

The above operations and the procedure for their implementation ensure the achievement of the claimed technical result. It consists in the possibility of data factorial coding with its secure transmission over an insecure communication channel without prearrangement of a cryptographic key over a secret channel. This is possible because each party in the exchange of information independently forms a shared key on its side.

The proposed method is suitable for practical implementation.

Correctness. We now show that if Alice and Bob do the above steps, they will share an identical key K .

Alice computes K1 1 Y2 1 1   2 2  1 and Bob computes K2  2 Y1 2  2  1 1  2 . Because of the property of associativity of reflections,

K1 1  2 2  1  1  2   2 1  K2  2  1 1  2   2 1   1 2  . Since n   1  2   2  1   iki ti i1 and and n  1 2  2 1   jmj sj , K1  K2  K .

j1

Necessary conditions. We now determine the conditions that the conversion parameters must satisfy.

First, a cryptanalyst should not be able to easily calculate the values of k , m , t , and s by the known values of Y1 and Y2 . Second, the pairs of values  k; m , t; s  must mutually uniquely determine Y1 and Y2 , respectively, that is k; m  Y1 and t; s  Y2 .

We introduce the following definitions.

Definition 1. Permutations  and  are called cycle-noncommutative if the den  n  compositions into the product of disjoint cycles    i ,    j have the i1 j1 property  i j   j i for i, j .

The property of cycle-noncommutativity of permutations  and  is sufficient to provide a high degree of mixing elements in the products  1 1 and  2 2 . This complicates the cryptanalyst work.

Unique factorization property (condition of bijections k; m  Y1 and t; s  Y2 ).

n  n  Let permutations    i and    j be cycle-noncommutative. Then the i1 j1 n  n  n  n  permutation Y1   1 1   iki   jmj (or Y2   2 2   iti   jsj ) is mutui1 j1 i1 j1 ally uniquely determined by specifying the powers k  k1, k2 , , kn   and m  m1, m2 , , mn   (or t  t1, t2 , , tn   and s   s1, s2 , , sn   ) if: 1. l i   2n  1, l  j   2n   1 for i, j ; 2. 0  ki  l i  1 , 0  m j  l  j  1 for i, j .

These conditions are sufficient.

Definition 2. Let permutations  and  be represented as the products of disjoint cycles:

 1  i1 i11  i2  iL11  iL  A1  A2   AL ,   1   j1  j1 1   j2   jL1 1   jL  B1  B2   BL , where Al il11  il , Bl   jl11   jl , 1  l  L , i0  0 , j0  0 . Then the permutations  and  are called block-noncommutative if inequalities  i j   j i , where il1 1  i  il , jl1 1  j  jl , are true for each pair of blocks Al ; Bl  , 1  l  L .

The condition of block-noncommutativity of permutations  and  is more lenient than the condition of cycle-noncommutativity. At the same time, it implies cyclenoncommutativity between the corresponding blocks of permutations  and  and allows the elements within the blocks to be mixed in the results of the products  1 1 and  2 2 .

Remark. Block-noncommutativity of permutations  and  retains the property n  n  of unique factorization of permutations of the type Y      iti   jsj if each i1 j1 block Al ; Bl  , 1  l  L , is uniquely factorized. 3

Key Space Cardinality

We now evaluate a cardinality of key space for the proposed key exchange method. A secret key to a cryptosystem is a tuple  k, m, t, s  consisting of two pairs of vectors that are Alice’s and Bob’s secret k  k1, k2 , , kn     m  m1, m2 , , mn   

t  t1, t2 , , tn   and  s   s1, s2 , , sn    keys.

The following conditions must be met: 0  mj , sj  l  j  1 , where l  i  , l  j  are the orders of cycles  i and  j , respectively. Then the key space cardinality is equal to n  2 n  2  n  n  2   l  i   l  j    l  i   l  j   .

i1 j1  i1 j1 

We define the conditions under which the value  will be maximized. Since the order of cyclic permutation is equal to its length, the following equalities are true: n  n   l  i   M   and  l  j   M   , where M   and M   are the lengths i1 j1 0  ki ,ti  l i  1, of permutations  and  , respectively.

Then n   l  i   max i1 and n  l  j   max , when l i   M   n  and l  j   M   n   for i, j j1 , as well n    M   e and n   M   e .

Because

 n  n  2 M  , M  , n , n ,l  ,l    Z , then    l  i   l  j    max ,  i1 j1  when M   mod 3  0 , M   mod 3  0 , n   M   3 , n   M   3 , and l i   l  j   3 for i, j . Then   32n n   32M  M   3 .

Thus, to achieve the maximum of key space cardinality, it is necessary to form permutations  and  as the product of disjoint 3-cycles. Under these conditions, the cardinality of the space of possible permutation  values is equal to     3n   M  !. The cardinality of the space of possible permutation  values depends on a method for its forming and requires additional research.

Consider a few examples.

Example 1. A permutation  cycle-noncommutative to a permutation  can be formed for M    M   as follows. Each of the cycles  j , 1  j  n   , contains one randomly selected element from each of the cycles  i , 1  i  n  . If l i   3 , then n    3 and l  j   n   for j . Then the cardinality of the space of possible permutation 

values is equal to     3!n  . Note that l  j   3 for j is possible only when n   n   3 .

Example 2. A method of forming a permutation  block-noncommutative to a permutation  may be as follows. Disjoint cycles are grouped into blocks of three: 1, 2 , 3  ,  4 , 5 , 6  , ,  i , i1, i2 , ,  n 2 , n 1, n   . The first element of a cycle  i is selected randomly from the elements of a cycle  i , the second element – from the elements of a cycle  i1 , and the third – from a cycle  i2 . The first element of a cycle i1 is randomly selected from the rest of the elements of a cycle  i , the second element – from the rest elements of a cycle  i1 , and the third – from a cycle  i2 . The elements of a cycle  i2 are uniquely defined. Note that this method of forming  requires n   0 . Then the cardinality of the space of pos3 sible permutation  values is equal to     3!3 n  3  3!n  . 4

Cryptographic System Description

The method for factorial coding key exchange can be implemented in a cryptographic system, a block diagram of which is shown in Fig. 1.

Two-way communication between Alice 1 and Bob 2 is exchanged on an open insecure duplex (half-duplex) communication channel 7 using transceivers 6 and 8. Alice and Bob have factorial codecs 3 and 9, shared key generators 4 and 10, as well as their own secret key generators 5 and 11, respectively. Let Alice creates a plaintext So . Then codecs 3 and 9 perform transformations FCK So  and FCK1 (the opposite of transformation FCK ), respectively. These transformations depend on the shared key, permutation K . Factorial codec 5 generates a codeword CW , which is transmitted by transceiver 6 through the open channel 7 to the Bob’s transceiver 8. The codeword CW is decoded in the codec 9.

Own key generators 5 and 11 are independent generators based on random or pseudorandom processes. Alice’s key generator 5 creates four signals:  , , k, m . The requirements for these variables are described above. Two permutations  and  are sent over the insecure communication channel 7 to the Bob’s shared key generator 10. Vectors k, m are transmitted to the shared key generator 4 and are kept secret by Alice. Bob’s own key generator 11 generates two signals t, s and transmits them to the shared key generator 10. Vectors t and s are keep secret by Bob.

So

Factorial codec

3

K Shared key gene4rator  , ,k,m

Own key gene5rator

CW  , ,Y1

Y2 Alice 1

Trans6ceiver

Insecure communication channel 7

Trans8ceiver

CW  , ,Y1

Y2

Factorial codec

9

K Shared key generator

10 t,s Own key generator 11

Bob 2

So

The shared key generators 4 and 10 form a common transformation key K . For this, the shared key generator 4 generates a signal Y1 based on the values of signals  , , k, m and transmits it to the shared key generator 10. In turn, the shared key generator 10 generates a signal Y2 based on the values of signals  , ,t, s and transmits it to the shared key generator 4. Direct calculating of Y1 and Y2 values does not cause difficulties. Inverse calculating of k and m values from known  ,  , and Y1 , as well as t and s from known  ,  , and Y2 is practically impossible.

Signal Y1 is formed in such a way as to correspond to the permutation on the set 0,1, , M 1 formed by the product of the other two permutations,  1 and 1 . The permutation  1 is formed by exponentiation of permutation elements, which values are transmitted by signal  , to powers, which values are transmitted by signal k  k1, k2 , , kn   . The permutation 1 is formed by exponentiation of permutation elements, which values are transmitted by signal  , to powers, which values are transmitted by signal m  m1, m2 , , mn   .

Signal Y2 is formed in such a way as to correspond to the permutation on the set 0,1, , M 1 formed by the product of the other two permutations,  2 and 2 . The permutation  2 is formed by exponentiation of permutation elements, which values are transmitted by signal  , to powers, which values are transmitted by signal t  t1, t2 , , tn   . The permutation 2 is formed by exponentiation of permutation elements, which values are transmitted by signal  , to powers, which values are transmitted by signal s   s1, s2 , , sn   .

Receiving signal Y2 , the shared key generator 4 generates a signal K . It corresponds to the permutation formed by the product of permutations transmitted by signals  1 , Y2 , and 1 , and strictly in that order, K   1 Y2 1 . Symbolically, the process of calculating a shared key by Alice can be represented as follows: n  n  K   1 Y2 1   1   2 2  1   1  2   2 1    iki ti   jmj sj . i1 j1 Receiving signal Y1 , the shared key generator 10 generates a signal K . It corresponds to the permutation formed by the product of permutations transmitted by signals  2 , Y1 , and 2 , and strictly in that order, K   2 Y1 2 . Symbolically, the process of calculating a shared key by Bob can be represented as follows: n  n  K   2 Y1 2   2   1 1  2   1  2   2 1    iki ti   jmj sj . i1 j1 Signals K corresponding to the same permutation key formed by the shared key generators 4 and 10, are transmitted to the inputs of the codecs 3 and 9. There they are used to encode a plaintext So and decode a codeword CW , respectively.

Similar to [ 8 ], we can show that the scheme of practical implementation of the proposed method may be different from shown in Fig. 1. Signals  and  may be in the public domain and not generated by the key generator of one of the parties. In addition, there may be significantly more than two parties. It is then advisable to place the value Yi of the i -th party to an open directory, a public file or directory, rather than transmit it between users each time. In this case, the two parties, i and j , that establish a secure connection form a shared encryption key by computing Kij   i Yj i and K ji   j Yi  j . 5

Conclusions

The proposed key exchange method allows forming a symmetric key, permutation, for data factorial coding without using a secure communication channel.

This method can be used not only for factorial coding tasks. This is explained by the fact that the obtained permutation, being the key for factorial code, corresponds to a certain number in the factorial number system. This number can easily be represented in any other number system (binary, decimal, etc.).

A detailed study of the cryptographic strength of the proposed key exchange method is an area for further research in this field.

Acknowledgments

The authors express their sincere appreciation to Ph.D., Associate Professor, Honorary Professor of Cherkasy State Technological University Valerii Shvydkyi for the full support of this area of work, constructive comments and suggestions when writing the work, and useful discussion of the results.

References

1. Faure , E.: Methodology of information security based on factorial data coding . Dr. Sc. Eng. Thesis , National Aviation University, Kyiv, Ukraine ( 2018 ).

2. Faure , E. , Shvydkyi , V. , Shcherba , A. : Information integrity control based on factorial number system . Journal of Baku engineering university - Mathematics and computer science 1(1) , 3 - 13 ( 2017 ).

3. Faure , E. , Shvydkyi , V. , Shcherba , V. : Combined factorial coding and its properties . Radio Electronics, Computer Science, Control 3 , 80 - 86 ( 2016 ).

4. Faure , E.: Factorial coding with data recovery . Visnyk Cherkaskogo derzhavnogo tehnologichnogo universitetu 2 , 33 - 39 ( 2016 ).

5. Faure , E.: Factorial coding with error correction . Radio Electronics, Computer Science, Control 3 , 130 - 138 ( 2017 ).

6. Faure , E. , Shcherba , A. , Kharin , A. : Factorial code with a given number of inversions . Radio Electronics, Computer Science, Control 2 , 143 - 153 ( 2018 ).

7. Diffie , W. , Hellman , M. : New directions in cryptography . IEEE Transactions on Information Theory (6) , 644 - 654 ( 1976 ).

8. Hellman , M. , Diffie , W. , Merkle , R.: Cryptographic apparatus and method . US Patent 4 , 200 , 770 ( 1980 ).

9. Günther , C. : An identity-based key-exchange protocol . Advances in Cryptology - Eurocrypt 89, 1989. Lecture Notes in Computer Science , vol. 434 , pp. 29 - 37 . SpringerVerlag, Berlin/New York ( 1989 ).

10. Diffie , W., van Oorschot, P. , Wiener , M. : Authentication and authenticated key exchanges . Designs, Codes and Cryptography 2 ( 2 ), 107 - 125 ( 1992 ).

11. ElGamal , T.: A public-key cryptosystem and a signature scheme based on discrete logarithms . IEEE Transactions on Information Theory 31 ( 4 ), 469 - 472 ( 1985 ).

12. Shor , P. : Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer . SIAM Journal on Computing 26 ( 5 ), 1484 - 1509 ( 1997 ).

13. Jao D. , De Feo L.: Towards quantum-resistant cryptosystems from supersingular elliptic curve isogenies . In: Yang BY . (eds) Post-Quantum Cryptography . PQCrypto 2011. Lecture Notes in Computer Science , vol. 7071 , pp. 19 - 34 . Springer, Berlin, Heidelberg ( 2011 ).

14. Initial recommendations of long-term secure post-quantum systems . PQCRYPTO.EU. Horizon 2020 ICT-645622.

15. Ding , J. , Xie , X. , Lin , X. : A simple provably secure key exchange scheme based on the learning with errors problem . Cryptology ePrint Archive, Report 2012 /688 ( 2014 ).

16. Folger , T. : The quantum hack . Scientific American 314 , 48 - 55 ( 2016 ).

17. Korchenko , O. , Vasiliu , Ye., Gnatyuk , S. : Modern quantum technologies of information security against cyberterrorist attacks , Aviation 14 ( 2 ), 58 - 69 ( 2010 ).

18. S. Gnatyuk, T. Zhmurko , P. Falat , Efficiency Increasing Method for Quantum Secure Direct Communication Protocols , Proceedings of the 2015 IEEE 8th International Conference on Intelligent Data Acquisition and Advanced Computing Systems: Technology and Applications (IDAACS' 2015 ), Warsaw, Poland, September 24-26 , Vol. 1 , 2015 , рр. 468 - 472 .

19. S. Gnatyuk , A. Okhrimenko , M. Kovtun , T. Gancarczyk , V. Karpinskyi , Method of Algorithm Building for Modular Reducing by Irreducible Polynomial , Proceedings of the 16th International Conference on Control, Automation and Systems , Oct. 16 - 19 , Gyeongju, Korea, 2016 , рр. 1476 - 1479 .

20. Hu Z. , Gnatyuk S. , Kovtun M. , Seilova N. Method of searching birationally equivalent Edwards curves over binary fields , Advances in Intelligent Systems and Computing , Vol. 754 , pp. 309 - 319 , 2019 .

21. S. Gnatyuk , V. Kinzeryavyy , M. Iavich , D. Prysiazhnyi , Kh. Yubuzova, High-Performance Reliable Block Encryption Algorithms Secured against Linear and Differential Cryptanalytic Attacks , CEUR Workshop Proceedings , Vol. 2104 , pp. 657 - 668 , 2018 .

22. Tynymbayev S. , Gnatyuk S.A. , Aitkhozhayeva Y.Z. , Berdibayev R.S. , Namazbayev T.A. Modular reduction based on the divider by blocking negative remainders , News of the National Academy of Sciences of the Republic of Kazakhstan, Series of Geology and Technical Sciences, № 2 ( 434 ), pp. 238 - 248 , 2019 .

23. Korobiichuk I. , Syerov Y. , Fedushko S. ( 2020 ) The Method of Semantic Structuring of Virtual Community Content . Mechatronics 2019: Recent Advances Towards Industry 4.0. MECHATRONICS 2019. Advances in Intelligent Systems and Computing , vol 1044 . Springer. pp 11 - 18 . https://doi.org/10.1007/978-3- 030 -29993- 4 _ 2

24. Kalimoldayev M. , Tynymbayev S. , Gnatyuk S. , Ibraimov M. , Magzom M. The device for multiplying polynomials modulo an irreducible polynomial , News of the National Academy of Sciences of the Republic of Kazakhstan, Series of Geology and Technical Sciences, № 2 ( 434 ), pp. 199 - 205 , 2019 .

25. Gnatyuk S. , Kinzeryavyy V. , Kyrychenko K. , Yubuzova Kh. , Aleksander M. , Odarchenko R. Secure Hash Function Constructing for Future Communication Systems and Networks, Advances in Intelligent Systems and Computing , Vol. 902 , pp. 561 - 569 , 2020 .

26. Iavich M. , Gagnidze A. , Iashvili G. , Gnatyuk S. , Vialkova V . Lattice based Merkle , CEUR Workshop Proceedings , Vol. 2470 , pp. 13 - 16 , 2019 .