=Paper=
{{Paper
|id=Vol-2413/paper02
|storemode=property
|title=
Definition of Chipher Key on Plaintexts and Chipher Texts by the Method of Equivalent Keys

|pdfUrl=https://ceur-ws.org/Vol-2413/paper02.pdf
|volume=Vol-2413
|authors=Alexander Babash,Valery Sizov,Andrey Mikrukov
}}
==
Definition of Chipher Key on Plaintexts and Chipher Texts by the Method of Equivalent Keys
==
<pdf width="1500px">https://ceur-ws.org/Vol-2413/paper02.pdf</pdf>
<pre>
    Definition of Chipher Key on Plaintexts and Chipher
          Texts by the Method of Equivalent Keys

           Alexander Babash 1[0000-0001-7578-6923],Valery Sizov [0000-0002-4844-4714]

                         and Andrey Mikrukov [0000-0002-8206-677X]

                         Plekhanov Russian University of Economics
                                M oscow, Russian Federation
                                 1
                                   babash@yandex.ru



       Abstract. One of the important tasks related to the implementation of the Digi-
       tal Economy program is to improve cybersecurity when creating digital plat-
       forms, as distributed information and communication systems of the subjects of
       a single digital market. When building distributed information security subsys-
       tems of digital platforms, an urgent task is to increase the cryptographic
       strength of the cryptographic mechanisms used to encrypt short texts. The paper
       deals with the problem of encrypting short texts with ciphers with a large num-
       ber of keys, from which the equivalent keys appear in the cipher, which leads to
       a significant reduction in the cryptographic strength of ciphers. The concept of
       weak key equivalence in the C. Shannon cipher model is introduced. M ethods
       for determining the key from the open and encrypted texts with the calculation
       of the parameters of their complexity are proposed. The methods are applicable
       to both symmetric ciphers and asymmetric ciphers. The following situations are
       considered: 1) representatives of classes of equivalent keys are known; 2) the
       capacities of the classes of equivalent keys and representatives of these classes
       are known; 3) only the capacities of the classes of equivalent keys are known;
       4) the number of classes of equivalent keys is known. A part of encryption de-
       vices (encoders) is built using a serial connection of the control unit with an en-
       cryption unit, where the actual control unit performs the role of a pseudo-
       random number generator. The keys of such an encoder are the keys of the
       pseudo-random number generator. The output sequence of the pseudo-random
       number generator is the control sequence of the encryption unit. Often the en-
       cryption unit uses the gamming cipher. In this case, the equivalence of the keys
       of such an encoder is equivalent to the equivalence of the keys of the pseudo-
       random number generator. The results obtained below allow us to apply the
       method of equivalent keys developed in the article to ciphers that have equiva-
       lent keys in a pseudo-random number generator.

       Keywords: Equivalent Keys, Cipher Encoding Algebra, Plaintext, Ciphertext.


1      Introduction

For many ciphers, decoding methods other than the “brute force” technique, some-
times called the Monte Carlo method, or the total method, the key testing method [1-
3], have not yet been found. At the same time, for many of them, the absence of

Proceedings of the XXII International Conference “Enterprise Engineering and Knowledge
M anagement” April 25-26, 2019, M oscow, Russia
equivalent keys has not been proven [4–11]. Moreover, when encrypting short texts
with ciphers with a large number of keys, the presence of equivalent keys in the ci-
pher follows from quantitative considerations. The concept is introduced in the paper
- weak equivalence of keys relative to a given plaintext. The presence of equivalent
keys in the cipher or weak equivalent keys leads to the possibility of grouping keys
into classes of keys with subsequent testing of representatives of such classes. Su ch a
situation, as a rule, significantly reduces the cryptographic strength of ciphers. This
idea lies in the cipher key identification methods developed below. Finally, the solu-
tions of two problems of interest for decoding of cipher are given:
1) what is the largest k, at which the probability that all the keys χ1 , χ2 , ..., χk pairwise
are not equivalent is less than the given probability P;
2) what is the minimum k for the average number of equivalent key pairs from the set
χ1 , χ2 , ..., χk greater than 1.
The decoding methods described in the paper are given with estimation of their com-
plexity parameters.


2      Basic Concepts and Notation
Let’s denote the cipher encoding algebra by A = (X, K, Y, f). Here: X – a set of
plaintexts; K – a number of keys; Y – a set of ciphertexts (cryptograms); f - encoding
function f(х,)=y, xX, K, yY.
     Definition 1. Keys ,` are called equivalent if f(х,)=f(х,`)for any хХ.
     Definition 2. The keys ,`К are called equivalent with respect to the subset
X` X if f(х,)=f(х,`) for any xX.
The binary relation  (X `) introduced in this definition for a set of keys K is a binary
equivalence relation (the properties of reflexivity, symmetry and transitivity are ful-
filled). Therefore, the entire set of keys K is divided into equivalence classes of the
                                                                     L ( Х `)
                                                                                   Х`
binary relation (Х`). We denote this partition by R( (Х`))=         UК .
                                                                      j 1
                                                                                   j


It is obvious that the equivalence of keys ,`Кwith respect to Х`implies also their
equivalence with respect to any X` ` subset of a X` set. It results that any equivalence
         Х`                                                                     Х ``
class К j is contained entirely in a certain equivalence class К j ` with respect to a
                                            Х ``
subset X `` of the set X`. Each class К j ` consists of the combination of some classes

К Хj ` . In particular, L(Х``)  L(Х`), and classes К Хj ` are “smaller” than classes К Хj ` `` .


3      Formulation of the Problem

Find solutions of the equation f(х,)=у with respect to К, i.e. the problem of de-
termining the key  by agiven plaintext x and a cipher text y. In the terminology
adopted above, this task consists in finding the key up to equivalence with respect to a
set consisting of a single element x.
Let’s denote byК 1 ,К2 ,…,КLequivalence classes with respect to the element
хХ.Further, for brevity, we will call these classes simply the equivalence classes of
keys, although their more meaningful name, in our opinion, would be "weak equiva-
lence classes of keys."


4      Problem Solutions with Various Additional Assumptions

1. The representatives 1 ,2 ,…,𝐿 of classes К 1 , К2 ,…, КL of equivalent keys are
known.
In this case, testing is carried out without the return of representatives until the first
success (until receiving a representative of the equivalence class in which the key is
located). That is, f(х,)=y is estimated for each test key  , and y is compared with
the given у. The testing process ends when the equality y=у is obtained.The perfor-
mance of Т in testing such a method coincides with the performance of the total
method with r=|К|=L and zero errors of the statistical criterion:
                                             Т=
                                                        L1
                                                         2
The reliability method is =1.
2.Capacities of classes of equivalent keys and representatives of these classes are
known.
Let’s arrange i( 1),i( 2),…,i( L)the representatives known to us in accordance with the
capacities of the classes of equivalent keys:
                                       |К i( 1)| |Кi(2)| … |Кi(L)|
and try them out according to this order i( 1),i( 2),…,i(L),r  L . The algorithm stops its
operation if the key sought is found (up to equivalence) or r tests are performed.
If the cipher key was chosen randomly and equiprobably from K, then the probability
                                                            |К j |
of choosing a key from the class Kj is equal to                      . Therefore, the average number
                                                            |К|
Tr tested in the implementation of the key algorithm is
                                     r-1     |К j |          L     | Кj |
                                    j
                               Тr = j 1     |К|
                                                          r
                                                            j r   |К|      ,


and the reliability of the method is
                                                    r    |К j |
                                           =      |К| .
                                                  j 1
When r = L we have
                                              L         |К j |
                                       ТL=    j |К| ,=1.
                                             j 1
3. Only the capacities |К1 |, |К2 |,…,|КL| of the equivalent key classes are known.
Let’s conduct testing without returning the K keys until a true key is obtained, up
to equivalence.
If the cipher key was chosen randomly and equiprobably from K, then the probability
                                                            |К j |
of choosing the key  from the class Kj is equal to               . Let’s denote by T (j) the
                                                            |К|
average number of tests of the algorithm, provided that the key sought is Кj . Then
                                                 |К|1
                                         Т(j)=
                                                 |К j |1
and the total average number of algorithm tests is
                             L        |К j | |К|1 L |К j |
                        Т=   
                             j 1
                                  Т(j)      =     
                                       |К| |К| j 1|К j |1
                                                            .

The reliability method is =1.
Let’s note that if in this method testing is carried out with return, then the average
number of tests of the algorithm will be equal to
                                     L
                                           |К||К j |
                                   |К ||К|  L .
                                    j 1     j
Consequently, under the conditions of the third problem, always T <L.
Obviously,
                                                   K 1
                                         1Т           ,
                                                    2
in this case, the lower bound is attained at L = 1, | Kj | = | K |, and the upper one at L
= | K |, | Kj | = 1.
If the estimated capacities ratings of equivalent key classes are
                                    cj |К j | Cj , j 1, L ,
then
                       |К|1 L с j          |К|1 L С j
                            
                        |К| j 1 с j  1
                                         Т
                                             |К| j 1 С j  1
                                                             .

4. The number L of classes of equivalent keys is known. Carrying out the method of
paragraph 3, for the complexity of the method, we obtain the estimate T <L.


5      Discussion

Let’s draw attention to the fact that the methods outlined were based on the equiva-
lence of keys with respect to a given xX (“weak equivalence of keys”). Usually, the
exact estimation of capacities of such equivalence classes is difficult, and therefore,
the equivalence of keys with respect to the whole set X is used. In this case, it is easy
to obtain lower bounds for the capacities of the classes of weak equivalences we used.
The direct use of the capacities of the classes of equivalent keys with respect to the
whole set X in methods 1–4 allows to estimate upper bounds of performances of the
above methods of “weak equivalences”.
The second circumstance to which attention should be paid is that in a number of
cases other key equivalences can be used in a similar way. For example, using the
mode of generating one-time keys with the help of a markant (special cipher mode for
obtaining one-time keys from a long-term key).


6      Methods of using equivalent keys and the birthday paradox

Let the number L of classes of equivalent keys of the used cipher be known, all the
classes having equally capacities and the number k of ciphered texts being used ran-
domly and equally probably selected keys χ1 , χ2 , ..., χk.
In various tasks of cryptographic practice, the solution of the following problems is of
interest.
1. what is the largest k, at which the probability that all the keys χ1 , χ2 , ..., χk pairs are
not equivalent is less than the given probability P.
2. what is the minimum k for the average number of equivalent key pairs from the set
χ1 , χ2 , ..., χk greater than 1.
The birthday paradox [11] is connected with the answer to the question: how many
people should be in the room so that with high probability there are two born on the
same day? The paradox is that the answer is significantly less than the number of days
in a year, which seems implausible. So, we consider that keys are people, and the
number L of classes of equivalent keys is the number of possible dates of birth. We
believe that in the year 365 = L days and that the birthdays of k people are chosen
randomly and independently from each other.
We first estimate the probability that all the birthdays of the selected k people (k  L)
will be different. Let the birthday of the first is already chosen. Then the birthday of
the second coincides with it with a probability of 1/L. With selected (and different)
birthdays of the first and second person, the probability that the third birthd ay will
coincide with one of the existing ones will have 2 / L, and so on. As a result, the prob-
ability Pk that k people will have different birthdays has Рk=(1-1/L)(1-2/L)…(1-(k-
1/L)).
The factors Pk can be increased using a known inequality 1+х≤ех:
                            Рk≤е-1/Lе-2/L… е-( k-1)/L=e-(1+2+3+…+(k-1))/L=e-k(k-1)/2L.
     With increasing k, the probability Pkdecreases. For which k is this probability
strictly less than a given P? Let’s solve inequality
                                                 e-k( k-1)/2L<P.
We have
                            -k(k-1)/2L<lnP, -k 2 +k< 2LlnP, k 2 -k>2Lln(1/P),
                                       k 2 -k+1/4>2Lln(1/P)+ 1/4,
                                       (k-(1/2)) 2>2Lln(1/P)+ 1/4.

Find k 0 in which (k 0 -(1/2))2=2Lln(1/P)+ 1/4. We have
                                k 0 -(1/2)= (2Lln(1/P)+ 1/4)(1/2).
Whence,
                                k 0 =(1/2) (1+(1+8Lln(1/P))1/2 .
In this connection, when k is smaller than k 0 , the probability Pk is less than the given
P. Therefore, when k is not less than k 0 , the probability Pk is not less than the given P.
Assuming, for example, L = 365 (669) is the number of different birthdays, P = 0,5,
we find that for k  23 (k  31) the probability that among k people there will be two
born on one day no less than P = 0.5. In other words, if the cipher has 365 (669) clas-
ses of equivalent keys and there is a set of k  23 (k  31) cipher telegrams, then
among them with a probability of at least 0.5 there will be a pair of cipher telegrams
encrypted on equivalent keys.
Let us turn to the solution of the second task. At what minimum k the average number
of equivalent key pairs of χ1 , χ2 , …, χkis greater than 1. For each key pair (i, j) from
the set {χ1 , χ2 , ..., χk}, let’s consider the random variable Xij
                           Xij =1, if χi and χj are equivalent, otherwise Xij =0.
Since the classes of equivalent keys of the used cipher have equal capacities and the
keys χ1 , χ2 , …, χkare chosen randomly and equiprobably, the probability of equiva-
lence of any key pair is 1/L. Therefore, the mathematical expectation М(Xij )of the
random value Xij (i≠j) is calculated by the formula
                                      М(Xij )=1∙1/L+0∙(1-1/L)= 1/L
                                                               k (k  1)
The random value Y equal to the sum of all Xij (in all Ck2              ) has a mathemat-
                                                                   2
ical expectation equal to the sum of all М(Xij )
                                             1 k (k  1) .
                                    М(Y)=      
                                             L     2
Let’s find the value k 0 from equality
                                      1 ko (k0  1)
                                                   =1.
                                      L      2
                1  1  8L
This value is               2 L . Consequently, when k ≥k 0 , the average value of
                    2
pairs of equivalent keys will be no less than 1. So if L=365, (669), then with k≥28
(k≥38) the expected number of pairs of equivalent keys is not less than
(28∙27)/ 2∙365=1.0356.


7      Conclusion

1. The concept of weak key equivalence in the C. Shannon cipher model is intro-
duced. A method is proposed for decrypting both symmetric and asymmetric ciphers
using the weak key equivalence parameters and calculating performances and relia-
bilities.
2. The proposed method can be used to determine the initial states of pseudo -random
generators from known input and output sequences.
3. Due to the lack of proof of the absence of weakly equivalent keys, many ciphers
have a successful chance of practical application of the above described method of
decoding.
 References
 1. Panasenko S.P. Encryption algorithms. Special reference book BHV-Petersburg, 2009.
 2. 2Schneier Bruce, Ferguson Nils. Practical cryptography, (2005).
 3. Schneier B. Applied Cryptography. Protocols, Algorithms, and Source Code in 2nd ed.
    N.Y.: Wiley, (1996).
 4. GOST 28147-89. Information processing systems. Cryptographic protection. Algorithm of
    cryptographic transformation. M .: State Standard of the USSR, (1989).
 5. Adams C. RFC 2144: The CAST - 128 Encryption Algorithm // Entrust Technologies, (May
    1997).
 6. Adams C., Gilchrist J / RFC 2612: The CAST-256 Encryption Algorithm // Entrust Tech-
    nologies, June (1999).
 7. Advanced Encryption Standart (AES). Questions and Answers // http // csrc.nist.gov - Janu-
    ary 28, (2002).
 8. AES Round 1 Inforation //http:csrc.nist.gov - January 26,( 2001).
 9. Biham E., Dunkelman O., Ketller N. Rectangle Attacks on the 49th Round SHACAL-1
    //http: //vipe.technion,ac.il - Technion, Haifa, Israel.
10. Biham E., Biryukov A., Dunkelman A., RichardsonE., Shamir A. Observations on Skipjack:
    cryptanalysis of Skipjack-3XOR // http://www.cs.technion.ac.il - Technion –(1998).
11. T. Cormen, C. Lazerson, R. Rivest. Algorithms and analysis. M ., M CNM O, (2002).

</pre>