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 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).