The article describes a new implementation of MST3 cryptosystems based on the generalized Suzuki 2 - groups. The main difference in the presented implementation is the presence of many-stage recovery of parts of the message from the encrypted text. The presented implementation of a cryptosystem has lower costs of key data. The complexity of the cryptanalysis and the size of the message for encryption depend of the power a generalized Suzuki 2 - groups.
Current is the development of efficient cryptographic cryptosystems that can with stand quantum attacks. It is believed that the advent of quantum computers and the presence of quantum algorithms for factoring integers and discrete logarithms will lead to hacking of known cryptosystems with a public key.
The idea of constructing public-key cryptosystems on the basis of an intractable word problem was proposed by Wagner and Magyarik in [1]. The basis is the use of permutation groups. Since the 2000s, several dozen cryptosystems in group constructions have been proposed [2÷5].
The development of the idea of Wagner and Magyarik is the proposal of Magliveras [6]. Magliveras proposed a symmetric cryptosystem based on a special type of factorization of finite groups named logarithmic signatures for finite permutation groups. The idea of using a logarithmic signature was investigated by Lempken et al. and developed in the construction for random covers in [7].
In this scheme, the public key consists of a tame logarithmic signature as well as some random numbers, and the secret key is design of random cover and sandwich transformation of the cover [8].
The intractability assumptions of this scheme are group factorization problem on nonabelian groups.
Magliveras cryptosystem based on the Suzuki group is known as MST3. Further improvements to this scheme were made by Svaba and van Trung in [9]. They introduced a secret cover of a random cover. A digital signature scheme based on MST3 cryptosystems was proposed and explored in [Hong].
Using two Suzuki parametric groups to build the MST3 cryptosystem leads to security and complexity of the assessment, proportional to the square of the measurement of the final field.
A further increase in security is possible by expanding the group. The MST3 cryptosystem based on the three-parameter group of automorphisms of the functional field of the Hermite curve [14] and the small Ri group has security and complexity estimates proportional to the cube of the dimension of the finite field [15].
In this paper will be presentation MST3 cryptosystems based on the multi-parameter generalized Suzuki 2 - groups. 2
The construct a generalizations of Suzuki 2-groups was proposed by Hakai in [16] at research conjugacy classes and characters for a family of groups satisfying Bannai condition. Construction of groups.
Let F , q = 2n is the finite field, and is an automorphism of F . Define for a q positive integer l and a1, a2 ,..., al F the following matrix and 1 a1 1 S(a1, a2 ,..., al ) = aa32 aa12 a11 2 1 Ml+1(F) ... ... ... ... ... al al−1 al−2 2 ... a1 l−1 1
Al (n, ) = S (a1, a2 ,..., al ) | ai Fq .
The each element of Al (n, ) can be expressed uniquely and it follows that Al (n, ) = 2nl and Al (n, ) define a group of order 2nl . If l = 2 , this group is isomorphic to a Suzuki 2-group A(n, ) .
Group operation is defined as a product of two matrices S (a1, a2 ,..., al )S (b1, b2 ,...,bl ) = S (a1 + b1, a2 + (a1 )b1 + b2 , a3 + (a2 )b1 + (a1 2 )b2 + b3 , ..., al + (al−1 )b1 + ... + (a1 l−1)bl−1 + bl ).
Identity element is unit diagonal matrix S (01, 0,..., 0) .The inverse element is determined by the inverse of the matrix. The direct calculations can to show that S (a1 ,a2 ,a3 ,..., al )−1 = S (a1 ,a2 + a1 a1 ,a3 + a2 a1 + a1 2 (a2 + a1 a1),..., al + al−1 a1 + ...).
Put G = Al (n, ) . The group G is nonabelian group and has nontrivial center
Z (G ) = S (0,0,..., c) c Fq .
Since the center Z (G ) is elementary abelian of order q, it can be identified with the additive group of the field F . Assume that is the Frobenius automorphism of q F , : x → x2 . All the involutions of G are in the center Z (G ) . Define
Gi = S (0,..., 0, ai , ai+1,..., al ) .
The elements g Gi have order 2l−i .
Let / ≙ −1( , ). Thus Gi is a normal subgroup of Al (n, ) . Simple show that group Gi for i (l +1) / 2 is abelian. This holds by direct calculations.
Let F , λ is a generator of F and is fixed and define mapping : Al (n, ) → Al (n, ) by where
( S (a1, a2 ,..., al )) = S (1a1,2a2 ,...,l al ) 1 = , 2 = 2 , 3 = ( 2 )2 , …, i = 2i−1 +1 .
Then mapping is an automorphism of Al (n, ) and if (n, i) = 1 , then permutes Gi / Gi+1 − Gi+1 transitively. For the fixed finite field, the group Al (n, ) order is greater than classical Suzuki 2 - group. A larger group order gives an advantage to cryptosystem secrecy, and definition over small fields gives an advantage for the implementation in general. 3
The basic idea of MST cryptosystems is to surjective mapping input message into an element of group using a conversion key. Formalization of computations is given by the following definition [12]. Definition 1 (cover (logarithmic signature) mappings). Let = A1,..., As be a cover (logarithmic signature) of type (r1, r2 ,..., rs ) for G with Ai = ai,1, ai,2 ,..., ai,ri , where m = is=1 ri . Let m1 = 1 and mi = ij−=11 rj for i = 2,..., s .
Then the surjective (bijection) mapping ′: ℤ → induced by is : ℤ 1 × ℤ 2 ×. . .× ℤ → ℤ ,
s ( j1, j2 ,..., js ) = ji mi .
i=1 '( x) = a1 j1 a2 j2 asjs where ( j1, j2 ,..., js ) = −1 ( x) .
More generally, if = A1,..., As is a logarithmic signature (cover) for, then each element g G ∈ can be expressed uniquely (at least one way) as a product of the form g = a1 a2 as , for ai Ai [7].
Let G is ultimate nonabelian group with nontrivial center Z , such that G does not decompose over Z . Suppose that Z is quite large, such that the search is over Z is computational impracticable.
The cryptographic hypothesis, which is the basis for the cryptosystem, is that if = [A1, A2 ,..., As ] := (ai, j ) – accidental cover for a "large" matrices S at G , then search for the layout g = a1 j1 a2 j2 asjs for any element g G relatively is, in general, not a solvable problem. There are several encryption algorithms for MST cryptosystems. One of the latest versions of MST3 presented in [13] has the following implementation.The main steps of the encryption algorithm. Public and private key calculation step: • generating a tame logarithmic signatures = [B1, B2 ,..., Bs ] := (bij ) the class • • • • (r1 ,r2 ,...,rs ) for ℤ; generating a random cover = [A1, A2 ,..., As ] := (ai, j ) the same class as і for some subset J from G such that A1,..., As G \ Z ; generating a set of elements t0 , t1..., ts G \ Z ; definition of the homomorphism to calculate : → ℤ; calculating := (hij ) = (ti−−11 f (aij )bijti ) for i = 1,..., s , j = 1,..., ri .
Will get public key – ( = (aij ), = (hij ), f ) and private key – ( = (bij ), (t0 ,...., t s )) Encryption step. Set a random number R Z . Let the message to be encrypted x Z Z . Calculate
y1 = '(R) x , y2 = (R) = t0−1 f ( '(R))b '(R)ts .
Transmit y = ( y1, y2 ) .
Decryption step. For decryption we have the cipher text y = ( y1, y2 ) , private key ( = (bij ), (t0 ,...., t s )) and the function of the homomorphism f : G → .
Let's calculate (R) = y2ts−1 f ( y1 )−1t0 . Checking is determined by the fact that y2 = (R) = t0−1 f (a1 j1 (R))b1 j1 (R)t1 ts−−11 f (asjs (R))bsjs (R)ts = b1 j1 (R)t0−1 f (a1 j1 (R))t1 bsjs (R)ts−−11 f (asjs (R))ts = (R)t0−1 f ( (R))ts = (R)t0−1 f ( y1 )ts Recover R with (R) using −1 , because is simple.
Calculate x = '(R)−1 y1 .
Complexity analysis.The main costs of implementation in the MST3 cryptosystem are determined by the volume a logarithmic signature over the finite field of the group representation.
The long-term key is defined by a logarithmic signature array and vectors t0 , t1..., ts G \ Z .
Let type a logarithmic signatures over the finite field F , q = 2n is ( r1,..., rs ) and q is=1 ri = 2n .
Suppose that the values ri are approximately equal ri = 2n/s , then the size V of the logarithmic signature will have an estimate s2n/s . For q = 2512 and s = 25 , 26 , 27 , 28 we obtain, respectively, V = 221, 214 , 211, 210 of the 512 bit strings.
The large size of the logarithmic signature is a drawback to the practical implementation of the MST3 cryptosystem.
On the other hand, the large size of the logarithmic signature determines the potentially very large entropy of the long-term key for cryptographic transformations.
Security Analysis. Message x masked by a logarithmic signature on the arrays = (aij ) , = (hij ) which is calculated for a random number R .
The function of the homomorphism : → ℤ moves the group element to the center of the group. The random values R are actually a session keys. Calculation (R) = y2ts−1 f ( y1)−1t0 and the subsequent recovery of R is possible due to the commutativity of the center. Commutative calculations in the center reduce the secrecy of the MST3 cryptosystem based on Suzuki 2-group to evaluate (q2 ) . 4
We apply the above construction to build the MST3 cryptosystem based on the generalized Suzuki group.
Very large generalized Suzuki groups can be constructed over a finite field of fixed dimension. This allows to achieve a compromise between practical implementation and the cryptosystem secrecy. Description of the Scheme. Let’s consider basic encryption steps in MST3 cryptosystem based on the generalized Suzuki group.
Key Generation: Input: a large group Al (n, ) = S (a1, a2 ,..., al ) | ai Fq , q = 2n with the center Z f , ( k , k ) with corresponding private key Output: a public
key k , (t0(k) ,..., ts(k)
) , k = 1, l / 2 .
Choose a tame logarithmic signatures k = B1(k) ,..., Bs(k) = (bij )k = S (0,.., 0,bij(l /2+k ) , 0,..., 0) of type (r1(k) ,..., rs(k) ) , i = 1, s , j = 1, ri(k ) , bij(l/2+k ) Fq , k = 1, l / 2 . The tame logarithmic signature is defined as a bijective and factorizable map of k ( R ) . Select a random cover
k = A1(k) ,..., As(k) = (aij )k = S (0,..., 0, ai(j1()k), 0,..., 0, ai(j2(l)/2+k) , 0,..., 0) of the same type as , where aij Al (n, ) , ai(j1()k) , ai(j2()k) Fq \ 0 , i = 1, s , j = 1, ri(k ) , k = 1, l / 2 .
Choose t0(k),t1(k),...,ts(k) Al(n, ) \ Z , ti(k) = S(ti1(k),...,til(k)) , tij(k) F , i = 0,s , j =1,l , k =1,l / 2 . Let’s ts(v) = t0(v+1) , v =1,l / 2−1.
Construct a homomorphism f defined by f (S(a1,...,al)) = S(0,...,0,a'l/2+1 = a1,...,a'l = al/2).
Compute k = h1(k),...,hs(k) = (h ) = t(−i1−1)(k) f ((a ) )(bij )k ti(k) , i =1,s , j =1,ri , ij k ij k k =1,l / 2 , where f ((aij )k )(bij )k = S (0,...,0,(ai(j1) )l/2+k +(bij )l/2+k ,0,...,0).
Output public key f ,(k, k), and private key k,(t0(k),...,ts(k) ) , k =1,l / 2 .
Input: a message xGl/2+1, and the public key f ,(k, k), k =1,l / 2 .
Output: a ciphertext ( y1, y2 ) of the message x .
Choose a random R = (R1,R2,...,Rl/2) , 1, 2,..., /2 ∈ ℤ| |.
y1 = '(R)x =1 '(R1)2 '(R2 )3 '(R3)l/2 '(Rl/2 ) x
= S (a1(
The components of () in the formula are determined by cross-calculations in the group operation of the product.
Compute:
y2 = '(R) =1 '(R1) 2 '(R2 )l/2 '(Rl/2 )
= S (,,...,,al(/12)+1 (R1)+l/2+1 (R1)+,...,al(
Here, the () components are determined by cross-calculations in the group operation of the product of t0(k),...,ts(k), k =1,l / 2 .
Output ( y1, y2 ).
Decryption:
Input: a ciphertext ( y1, y2 ) and private key k,(t0(k),...,ts(k) ) , k =1,l / 2 .
Output: the message xGl/2+1 corresponding to ciphertext ( y1, y2 ).
To decrypt a message x , we need to restore random numbers R = (R1,R2,...,Rl/2)
The parameter a1(
D(R) = D(
Restore R1 with l/2+1 (R1) using l/2+1 (R1)−1 , because is simple.
For further calculations, it is necessary to remove the components of the arrays 1 '(R1) and 1 '(R1) from ciphertext ( y1, y2 ).
Compute:
y1(
D(
D(R) = D(
Restore R2 with l/2+2 (R2 ) using l/2+2 (R2 )−1 .
Repeating iteratively calculating after l / 2 steps, we obtain the recovery of R = (R1,R2,...,Rl/2) and the message x from y1.
Example. We will show the correctness of the obtained expressions in the following simple example. Fix the generalized Suzuki group G = A4(n, ) over the finite field Fq , q = 210 . Assume that is the Frobenius automorphism of Fq, : → 2.
Let’s define A4(n, ) =S(a1,a2,a3,a4) | ai Fq .
Group operation is defined as a product of two matrices
S(a1,a2,a3,a4)S(b1,b2,b3,b4) =
S(a1 +b1,a2 + a12b1 +b2,a3 + a22b1 + a14b2 +b3,a4 + a32b1 + a24b2 + a18b3 +b4). The inverse element is determined as
S(a1,a2,a3,a4)−1 = S(a1,a2 + a12a1,a3 + a22a1 + a14(a2 + a12a1), a4 + a32a1 + a24(a2 + a12a1)+ a18(a3 + a22a1 + a14(a2 + a12a1))) =
S(a1,a2 + a13,a3 + a22a1 + a14a'2,a4 + a32a1 + a24a'2+ a18a'3) where a'2 = a2 + a13 , a'3 = a3 + a22a1 + a14a'2 .
Let`s construct a tame k = B1(k),...,Bs(k) = (bij )k = S (0,..,0,bij(l/2+k),0,...,0) of type (r1(k),...,rs(k) ) , i =1,s , logarithmic signatures j =1,ri(k) , bij(l/2+k) Fq , k =1,l / 2 .
We have l = 4 , k =1,2 . Let`s define two arrays as follows
1 = B1(
q
Logarithmic signatures 1 and 2 in a group representations define bij(
As an example, (r1,..., rs ) = (22 , 22 , 23 , 23 ) . Arrays bij(
q The construction of arrays of logarithmic signatures is presented in [17].
First stage is to generate a tame logarithmic signature with the dimension of corresponding selected type (r1(k) ,..., rs(k) ) and finite field Fq .
In our
case k = B1(k) , B2(k) , B3(k) , B4(k) .
(r1(k) ,..., rs(k) ) = ( 22 , 22 , 23 , 23 ) ,
q = 210 Since 1 and 2 have a same and type (r1(k) ,..., rs(k) ) = (r1,..., rs ) we will get the same k , k = 1, 2 on the first stage.
Let's set a tame logarithmic signature with entries Bi.
β(
B1 B2 B3 B4
To calculate ( R )−1 it is enough to select groups of bits in the vector according to
the type
( R)−1 = 10 00 010 101 = ( R1, R2 , R3 , R4 ) = (
Bits positions in a logarithmic signature vector ( R ) are uniquely associated with subarrays Bi(k ) and bit values at these positions with the row number of the subarray Bi(k ) . To increase the security of arrays k various cryptographic transformations can be used. For example, simple ones like adding noise vectors, permutations of strings in subarrays Bi , merge of arrays Bi , their permutation, matrix transformations.
In our example, we use noising of β(
B1 B2 B3 B4
Here the noise bits are in bold. For R = (
( R)−1 = 0110000101 + 0100010000 = 0010 010 101 → (, , 2, 5).
Repeat this procedure until the last subarray of the logarithmic signature and restore
( R1, R2 , R3 , R4 ) = (
B3(
The numerical values of arrays determine the degree indicators of the generating
element of the field = i , whose binary representation are strings β1. Representation
of 0 defines single element 0 of the field Fq . Similarly, we construct the second
logarithmic signature 2 . We represent these permutations by a mapping of the form
1 2 3 4
2 = . We got a new type ( r1(
B2(
B3(
Arrays of logarithmic signatures 1 and 2 in the group representation, defines the
coordinates bij(
Construct random covers k , for the same type as 1 и 2
1 = A1(
Each cover k defined by only two arrays (ai(j1()k) , ai(j2()k+2) ) with non-zero entries. Let`s generate random covers 1 , 2 .
α1= A1(
(644,233),(689,439),(329,934),(188,457)} and α2=
A1(
1 (673) = h1(
Let R2 = ( R1(
2 (354) = h1(
To decrypt a message x , we need to restore random numbers R = (R1, R2 ) . Compute
D(
We get 1 ( R1 ) = 235 = (0 0 0 0 1 1 1 1 0 0) .
Recovery of R1 was done earlier R = ( R1, R2 , R3 ) = (
For further calculations, it is necessary to remove the components of the arrays 1 '( R1 ) and 1 '( R1 ) from ciphertext ( y1, y2 ) .
Compute:
y(
Perform inverse calculations 2 ( R2 )−1 . Select bit groups in vector ( R) according
to type (r1(
R2=(*,*,*,6)
row from β(
R2= (
The resulting vector along with the concatenation of array entries B2(
2 ( R ')−1 := 2 (
The
transition
from
bit
to
numeric
gives
the
desired
value
R2 = ( R1(
Security Analysis. An attack on the cryptosystem is possible by solving the
(R1, R2 ,..., Rl/2 ) = t0(
The success of an attack is determined by the selection of t0(k) and ts(k) vectors and has complexity proportional to the l / 2 power of the group Al (n, ) due to the noncommutativity of the generalized Suzuki group. Brute force attack is possible by selection R1 , R2 ,..., Rl /2l
. The complexity is determined by the value l / 2 , finite field power Fq in proportion to l / 2 Fq . Complexity analysis. Fix the generalized Suzuki group G = Al (n, ) and the logarithmic signature for the type ( r1 ,..., rs ) over the finite field F , q = 2n . Suppose that the values ri are approximately equal ri = 2n/ s .
q Early show
that the size of the logarithmic signature has the estimate V = ls Al (n, ) 1/ls . For q = 264 , Al (n, ) = 2512 , l = 8 and s = 23 , 24 , 25 we obtain, respectively, V = 214 , 211, 210 of the 64 bit strings. 5
The proposed design of the MST3 cryptosystem based on the generalized Suzuki group provides potentially higher privacy and optimizes the cost of key data. The difference from the well-known MST3 construction is the iterative key recovery from calculations in the large normal subgroup of the generalized Suzuki group. 11. A. Garcia, H. Stichtenoth, C.-P.Xing, “On Subfields of the Hermitian Function Field”,
Kluwer Academic Publishers, Compositio Mathematica 120: pp.137–170, 2000. 12. W. Lempken and T. van Trung, “On minimal logarithmic signatures of finite groups”, Experimental Mathematics,vol.14, no. 3, pp. 257–269, 2005. 13. H.Hong, J.Li, L.Wang, Y. Yang, X.Niu “A Digital Signature Scheme Based on MST3 Cryptosystems” Hindawi Publishing Corporation, Mathematical Problems in Engineering ,vol 2014, 11 pages, http://dx.doi.org/10.1155/2014/630421 14. G.Khalimov, Y. Kotukh, S.Khalimova “MST3 cryptosystem based on the automorphism group of the hermitian function field”, 2019 2019 IEEE International Scientific-Practical Conference: Problems of Infocommunications Science and Technology, PIC S and T 2019 – Proceedings 15. G. Khalimov, T.T.Simon, A.M.Adrees, E.Kotukh “MST3 cryptosystem based on a small Ree groups” 3rd IEEE international conference advanced information and communication technologies-2019 “Next-generation networking for the Internet of Things: 5g, sdn, nfv and cloud computing” 2~6 july, 2019 ,Lviv, Ukraine 16. A.Hanaki “A CONDITION ON LENGTHS OF CONJUGACY CLASSES AND
CHARACTER DEGREES” Osaka J. Math. 33 pp.207-216, 1996 17. P. Svaba, “Covers and logarithmic signatures of finite groups in cryptography”, Dissertation, https://bit.ly/2Ws2D24