One of the important tasks related to the implementation of the Digital Economy program is to improve cybersecurity when creating digital platforms, as distributed information and communication systems of the subjects of a single digital market. When building distributed information security subsystems 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 number 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 devices (encoders) is built using a serial connection of the control unit with an encryption unit, where the actual control unit performs the role of a pseudorandom 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 encryption 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 pseudorandom number generator. The results obtained below allow us to apply the method of equivalent keys developed in the article to ciphers that have equivalent keys in a pseudo-random number generator.
For many ciphers, decoding methods other than the “brute force” technique,
sometimes called the Monte Carlo method, or the total method, the key testing method
[13], have not yet been found. At the same time, for many of them, the absence of
equivalent keys has not been proven [
The decoding methods described in the paper are given with estimation of their complexity 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, xX, K, yY.
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 xX.
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 fulfilled). 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` . j1 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 determining 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 equivalence 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 performance 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 |К | of choosing a key from the class Kj is equal to j . Therefore, the average number |К| Tr tested in the implementation of the key algorithm is
r-1 j |К j | rL | К j | Тr= j1 | К | jr | К | , and the reliability of the method is When r = L we have = r|К j| j1 |К| ТL= L j|К j| j1 |К| 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 of choosing the key from the class Kjis equal to |К |
j . Let’s denote by T (j) the |К| average number of tests of the algorithm, provided that the key sought is Кj. Then |К|1 and the total average number of algorithm tests is Т(j)=
|К j |1
L Т= Т(j) j1 |К j|=|К|1 L |К j| |К| |К| j1|К 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 | j1|К j||К|
L . 1 Т
K 1 , Consequently, under the conditions of the third problem, always T <L. Obviously, 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 then
cj|Кj|Cj , j 1, L , |К|1 L с
|К| j1 с j 1 j Т |К|1 L Сj |К| j1 С 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 equivalence of keys with respect to a given xX (“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 randomly 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 [
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 probability 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.
-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).
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) classes 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 χjare 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 equivalence 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 The random value Y equal to the sum of all Xij (in all Ck2 k(k 1) ) has a mathemat2 ical expectation equal to the sum of all М(Xij)
М(Y)= 1 k(k 1) .
2 L 2 L 1 ko (k0 1) =1.
1 1 8L This value is
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.
2L . Consequently, when k ≥k0, the average value of 7
Conclusion 1. The concept of weak key equivalence in the C. Shannon cipher model is introduced. A method is proposed for decrypting both symmetric and asymmetric ciphers using the weak key equivalence parameters and calculating performances and reliabilities. 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.