The quantitative comparison between the integer splitting cipher and the traditional gamma cipher

Abstract

   The symbolic integer splitting cipher is a special mathematical method that is proposed by the authors and it can be considered as a generalization of a modular arithmetic operation. In this cipher, each text's symbol is represented as an integer in accordance with the selected code table after that this integer is replaced on the base of another number with a sequence of k integers (k-splitting level). This study is conducted from the point view of the possible hacker's attack. Two lemmas, which are related to the unauthorized access to the information transmission channel, were proven in this article; the first lemma is related to the probabilistic analysis of unauthorized restoration of the plaintext based on the gamma cipher while the second lemma studied the probabilistic analysis of unauthorized restoration of the plaintext processed by integer splitting cryptosystem. After that a quantitative comparison is performed based on these two lemmas. In the result of our study a conclusion was made that the effectiveness of the splitting cryptosystem supersedes essentially the traditional gamma cipher and also the increase in splitting level leads to greater protection of information and greater level of safety.

Keywords

•  1  Integer splitting cipher
• gamma cipher
• unauthorized plaintext recovery
• the level of splitting
• probability theory

1. Introduction 

where,  ‒ is the remainder of the integer division r a , q ‒ is the integer part of this division, and the symbol   means rounding down to the nearest integer. The natural number k is called the splitting level.

Gamma cipher which will be studied in this article can be executed using several mathematical formulas. For example, the encryption process can be performed by the following formula [3, 4]:                  C= P  K   ( 2 )  where, C, P, K  ASCII codes of the ciphertext, plaintext and gamma, respectively,   bitwise operation - "exclusive or". The decryption process (plaintext restoration) is performed similarly by using the following formula [3, 4]:

                   P= C  K .  ( 3 ) 

The suggested integer splitting cryptosystem can be considered as an upgraded version of the traditional gamma cipher which will provide more secrecy based on the selected level of splitting and has the advantage of hiding the length of original plaintext. This cryptosystem performs two steps during the encryption process. The first step will encrypt the plaintext M according to the splitting cipher mentioned in definition 1, and as a result the sender at this step will obtain the intermediate ciphertext C as shown in the following expression:

 ri  a при k  1 ( 4 )                           C   ( 2 ) , ( 3 ) , ( 4 ) ,..., (k1) , (k ) , q(k) при k  1  

The second step of the encryption process of the splitting cryptosystem will apply the gamma cipher on the intermediate ciphertext C in order to provide more protection of information and as a result we will obtain the final ciphertext C that will be sent to the receiver side, as shown in the following expression:

 ( j)  ri j1 , где j  2, 3, ..., k при k  1 ( 5 )                                     C      q(k )  rik

At the receiver side, the decryption process will be executed, i.e., the splitting cryptosystem will perform the steps in an inverse order to obtain the plaintext M . So, the first step of the decryption process will apply the gamma decryption model on the received ciphertext C , and as a result the intermediate ciphertext С will be obtained at this step, as shown in the following formula:  ( j)  ri j1 , где j  2, 3,..., k при k  1 ( 6 )                            C    

 q(k)  rik

The second step of the decryption process of the splitting cryptosystem will apply the splitting decryption process on the intermediate ciphertext C in order to obtain the original plaintext M , as shown in the following expression:  ri  C при k  1 ( 7 )                                              ri  ( j)     q( j) , где j  k, k 1,..., 3, 2 при k  1

This article will study the quantitative comparison of the integer splitting cryptosystem from the point view of the hacker. It is important to notice that in the article [3] a qualitative comparison was conducted between the symbolic integer splitting method over both synchronous stream ciphers and perfect secrecy ciphers, but in this article the quantitative comparison of the proposed cryptosystem and the gamma cipher will be studied and show how the proposed cryptosystem increases the level of security. 2. Formulation of the main lemmas and their proofs 

To perform the quantitative comparison between the gamma cipher and the splitting system we need to prove the following lemmas:

Lemma 1. The probability of a successful unauthorized restoration of the plaintext M from the ciphertext С by applying gamma decryption process is defined by the following formula:                        PrG (M | C,1)   LN 1   ( 8 )  ( 9 )  (11)  (12)  where N – is the size of the ciphertext C , which is created for the plaintext M based on the gamma cipher, and L – is the number of all possible events during the search in the key space R , which is used by the attacker and consists of random integers r1, r2 ,...., rL .

Proof.

It is assumed that the attacker obtains the ciphertext by simply intercepting the message in the

communication channel and also, he knows both the rule of decryption presented in the formula ( 3 ) and the ciphertext C , consists of integers с1, с2 ,..., сN  with size N , which for him looks like a random sequence of integers. But he does not know the keys (gammas) that were used during the encryption process, so he will be forced to generate a set of independent random integers, which will be formed the space R  r1, r2 ,...., rL with size L , where L  N and he will try to recover the original plaintext

M by using this space. The attacker will use a brute force search.

In an attempt to extract the ciphertext C the attacker must perform these steps:

First step: the attacker will begin to perform the brute force search on the space R with repetition.

From formula (2), we conclude that each integer, located in the ciphertext C , is calculated using one

value ri , where i  1, 2, 3,..., L . So, the attacker will search with repetition N elements from the set with size L . The number of all possible outcomes is given by the following expression [5, 6, 9,                     n1  LN  

The second step consists in an attempt to extract the plaintext M by using the rule, which is

described in formula ( 3 ), with the help of the ciphertext C and the generated set of keys R obtained in the first step.

Consider the event PrG (M | С,1) – The probability of a successful unauthorized restoration of the plaintext M from the ciphertext С by applying gamma decryption process, and it is determined by the following formula:

                          PrG (M | С,1)  sp11   ( 10 )  where, p1 – is the number of all attempts to restore a meaningful plaintext M , s1 – is the total number of all possible attempts to restore the value of the plaintext M .

First, let's find s1 – the total number of all possible attempts to get the plaintext M . From formula ( 9 ), the number s1 is determined by the following expression:

Second, let's find p1 – the number of meaningful restoration events of the plaintext M .

Of all the attempts to restore the plaintext M , only one case will give a meaningful plaintext that matches what is encrypted by the sender. This is a situation where the selected keys on the attacker's side match the same keys that were used by the sender during the encryption process of the plaintext [6,8]. So, this leads to the fact that the number of correct extractions of a meaningful text, which meets the plaintext, is equal to one.

                   s1  LN                   p1  1. 

Replacing the values of s1 and p1 , from equations (11) and (12) in the formula ( 10 ), we obtain the result:                             PrG (M | C,1)  1N   LN 1   L

The proof of Lemma 1 is complete.

Lemma 2. The probability of a successful unauthorized restoration of the plaintext M based on the result of splitting cryptosystem C decreases exponentially with increasing the level of splitting k according to the expression:  k  N  1 (14)  PrSG (M | C, k )   LN  (L  N ) i      i2  where, N – is the size of the ciphertext C created for the plaintext M based on the splitting cryptosystem, and L – is the number of all possible events in the keys’ space R , which is consisted of random integers r1, r2 ,...., rL used by the hacker during the brute force search.

Proof.

It is assumed that the attacker obtains the ciphertext C by simply intercepting the message in the

communication channel (attack based on ciphertext).

In this case, the attacker knows the ciphertext C , which represents a sequence of integers and also,

he knows the rules of restoration the symbol stated in equations ( 6 ) and ( 7 ). But the level of splitting k is assumed to be unknown to him. In addition, the gammas that were used during the encryption are also unknown, so the attacker will be forced to generate a set of random integers R and try to recover the plaintext.

Thus, the attacker has a set of integers C  с1, с2 ,..., сN  with size N , which for him looks like a random sequence of integers. The attacker knows the encryption methods of the splitting cryptosystem that are used in the formulas ( 4 ) and ( 5 ) and also, he knows the decryption process of the splitting cryptosystem that are shown in formulas ( 6 ) and ( 7 ), so he will first build a set of independent random integers

                           R  r1, r2 ,...., rL  of size L  where L  2N .   

The method that is used by the attacker will be based on a brute force procedure.

Since the attacker does not know the value of k , he will try different values of the splitting level k ,

starting with k  2 .

a. Assessment the probability of unauthorized recovery of the plaintext at the splitting level k  2 In an attempt to retrieve the plaintext M at level k  2 , the attacker must follow the outlined steps in the following formula:                               PrSG (M | C , 2)  PrS/G (M | C , 2)  PrG (C | C , 1)   (13)  (15)  (16)  where, PrSG (M | C, 2) − is the probability of a successful unauthorized recovery of the plaintext M from the result of splitting C at k  2 by applying the splitting decryption process and gamma decryption process successfully, PrS/G (M | C , 2) − is the probability of a successful unauthorized recovery of the plaintext M from the intermediate ciphertext C at k  2 , on condition, that the event of a successful unauthorized recovery of the intermediate ciphertext C from the result of splitting cryptosystem C by applying the gamma decryption process has occurred successfully, PrG (С | C, 1) − is the probability of a successful unauthorized restoration of the intermediate ciphertext C from the result of splitting cryptosystem C by applying gamma decryption process.

First step: calculating the probability of a successful unauthorized restoration of the intermediate

ciphertext C from the result of splitting system C by applying gamma decryption process, i.e. PrG (С | C, 1) .

                              PrG (C | C, 1)   LN 1    

Second step: calculating the probability of a successful unauthorized recovery of the plaintext M

from the intermediate ciphertext C at k  2 , on condition, that the event of a successful unauthorized recovery of the intermediate ciphertext C by applying the gamma decryption process has occurred successfully, i.e., PrS/G (M | C , 2) .

Sub-step 2.1: splitting the obtained ciphertext C into pairs of two integers. Each symbol is represented by two elements in space C at k  2 . As a result, the number of pairs, studied by the attacker, will be equal to  N  (18)  N2   

 2   

Sub-step 2.2: the attacker will start a brute force search on the elements of the space R with a repetition. From equation ( 4 ), we conclude that in the case of splitting at k  2 , each pair of two elements is calculated using one value ri from the space R , which is at this step consisting of L  N  N  elements. At this stage, the attacker will enumerate the values from   elements with repetition  2  from the values of the set R with the size L  N . The number of all possible outcomes is given by the following expression [2, 5-10]:                          p2  1 .    (17)   (19)  (20)  (21)  (22)   N                                   n2  (L  N ) 2    

Sub-step 2.3: consists of trying to extract the plaintext M  by applying the rule ( 7 ) by using both the built pairs of numbers obtained in sub-step 2.1 and the sets of numbers (keys or gammas) obtained in sub-step 2.2.

Consider PrS/G (M | C , 2) – the probability of a successful unauthorized restoration of the plaintext M based on the intermediate ciphertext C at the level of splitting k  2 . The probability PrS/G (M | C , 2) is determined by the following formula:                           PrS/G (M | C , 2) 

2 ,       p s2 where, p2 – is the number of attempts to restore of a plaintext M meaningfully by the attacker at the level of splitting k  2 ; s2 – the total number of all possible attempts to restore the value of the plaintext M at k  2 .

First, let's find s2 – the total number of all possible attempts to get the plaintext M at the splitting level k  2 . From formulas (18) and (19), the number s2 is determined by the following expression:  N                                       s2  (L  N ) 2  .    Now let's find p2 the number of the events that restore a plaintext M meaningfully.

Of all attempts to recover the plaintext, only one case will produce a meaningful plaintext that

matches what is encrypted by the sender. This is a case when the selected gammas on the attacker’s side match the same gammas that are used by the sender’s side when encrypting the plaintext [6, 8].

This leads to the fact that the number of correct extractions of a meaningful plaintext corresponding to the original one is equal to one.

Replacing the values of s2 and p2 , from equations (21) and (22) in formula (20), we obtain the result:                                   PrS / G (M | C , 2) 

1  N    (L  N ) N2  1 .   (L  N ) 2    (23)          (24)  (25)  (26)  (27) 

The third step: calculating PrSG (M | C, 2) − the probability of a successful unauthorized recovery of the plaintext M from the result of splitting C at k  2 by applying the splitting decryption process and gamma decryption process successfully.

Replacing the values PrG (C | C, 1) and PrS/G (M | C , 2) , from equations (17) and (23) in formula (16), we obtain the result:   N  1 PrSG (M | C, 2)  PrS/G (M | C , 2)  PrG (C | C, 1)   (L  N ) 2     LN 1

    

  N  1 PrSG (M | C, 2)   LN  (L  N ) 2       b. Assessment the probability of unauthorized recovery of the plaintext at the splitting level k  3

The attacker will start extracting the plaintext at k  3 , if he fails to extract the correct meaningful plaintext at k  2 . In an attempt to retrieve the plaintext M at k  3 the attacker should follow the outlined steps in the following formula:

                  PrSG (M | C, 3)  PrS/G (M | C , 3)  PrG (C | C, 1) ,  where, PrSG (M | C, 3) − is the probability of a successful unauthorized recovery of the plaintext M from the splitting system C at k  3 by applying both the splitting decryption process and gamma decryption one successfully, PrS/G (M | C , 3) − is the probability of a successful unauthorized recovery of the plaintext M from the intermediate ciphertext C at k  3 , on condition, that the event of a successful unauthorized recovery of the intermediate ciphertext C from C by applying the gamma decryption process has occurred successfully, PrG (С | C, 1) − is the probability of a successful unauthorized restoration of the intermediate ciphertext C from the result of splitting cryptosystem C by applying gamma decryption process.

First step: calculating PrG (С | C, 1) .

From Lemma 1, we have:

                         PrG (C | C, 1)   LN 1             Second step: calculating PrS/G (M | C , 3) .

Sub-step 2.1: splitting the obtained ciphertext C into a combination of three integers. Each symbol is represented by three elements in space C at k  3 . As a result, the number of combinations, studied by the attacker, will be equal to  N  .                        N3   3  

Sub-step 2.2: the attacker will start a brute force search on the elements of the space R with a repetition. But the space R in this step will consist of L  N elements, because N elements were correctly selected in the previous step in order to get the ciphertext C correctly from С by applying gamma decryption process. From equation ( 4 ), we conclude that in the case of splitting at k  3, each combination of three integers is calculated using one value ri from the space R , which at this step is  N  consisting of L  N elements. At this stage, the attacker will enumerate the values from   elements  3  with repetition from the values of the set R with the size L  N . The number of all possible outcomes is given by the following expression [2, 5-10]:

Sub-step 2.3: consists of trying to extract the plaintext M  by applying the rule ( 7 ) by using both the built combinations of numbers obtained in sub-step 2.1 and the sets of numbers obtained in sub-step 2.2.

Consider PrS/G (M | C , 3) – the probability of a successful unauthorized restoration of the plaintext M based on the intermediate ciphertext C at the level of splitting k  3. The probability PrS/G (M | C , 3) is determined by the following formula: p (29)                                PrS/G (M | C , 3)  3 ,  s3 where, p3 – is the number of attempts to restore the plaintext M meaningfully by the attacker at the level of splitting k  3 ; s3 – the total number of all possible attempts to restore the value of the plaintext M at k  3 .

First, let's find s3 – the total number of all possible attempts to get the plaintext M at the splitting level k  3. Since the attacker was obviously unable to extract the correct meaningful plaintext at the previous level ( k  2 ), then s3 is given by the following expression: (28)  (30)  (31)        where, n2 – is the total number of all possible attempts to get the plaintext at the level k  2 and n3 – is the total number of all possible attempts to get the plaintext at the current level k  3 .

Substituting the values n2 and n3 from equations (19) and (28) into expression (30), we obtain the following expression:

 N   N  3  N                                s3  (L  N ) 2   (L  N ) 3    (L  N ) i  .   i2 Now let's find p3 the number of the events that restore a plaintext M meaningfully.

As discussed previously, only one case will produce a meaningful plaintext that matches what is

encrypted by the sender. This is a case when the selected gammas on the attacker’s side match the same gammas that are used by the sender’s side when encrypting the plaintext [6, 8]. So                p3  1.  (32)  Replacing the values of s3 and p3 , from equations (31) and (32) in formula (29), we obtain the result:                    PrS / G (M | C, 3)  3 (L 1 N )Ni    i32 (L  N )Ni  1 .   (33) 

i2

The third step: calculating PrSG (M | C, 3) . Replacing the values PrG (C | C, 1) and PrS/G (M | C , 3) , from equations (26) and (33) in formula (25), we obtain the result:                            s3  n2  n3 , 

 3  N  1 PrSG (M | C, 3)  PrS/G (M | C , 3)  PrG (C | C,1)    (L  N ) i     LN 1

 i2                    PrSG (M | C, 3)   LN  i32 (L  N ) Ni  1                                             (3  4)  c. Assessment the probability of unauthorized recovery of the plaintext at the splitting level k .

The attacker will start extracting the plaintext at a level k if he cannot extract the correct meaningful plaintext from all previous levels of splitting.

In an attempt to retrieve the plaintext M at k level, the attacker must follow the outlined steps in the following formula:

                                  PrSG (M | C , k )  PrS/G (M | C , k )  PrG (C | C , 1) ,   where, PrSG (M | C, k ) − is the probability of a successful unauthorized recovery of the plaintext M from the result of splitting C at k by applying both the splitting decryption and gamma decryption successfully, PrS/G (M | C , k ) − is the probability of a successful unauthorized recovery of the plaintext M from the result of splitting method C at k , on condition, that the event of a successful unauthorized recovery of the intermediate ciphertext C from C by applying the gamma decryption has occurred successfully, PrG (С | C, 1) − is the probability of a successful unauthorized recovery of the intermediate ciphertext C from the result of splitting system C by applying gamma decryption.

First step: calculating PrG (С | C, 1) . From Lemma 1, we have:                              PrG (C | C, 1)   LN 1     (35)  (36)  Second step: calculating PrS/G (M k | C , k ) .

Sub-step 2.1: splitting the obtained ciphertext C into combinations of k integers. Each symbol is represented by k elements in space C . As a result, the number of combinations, studied by the attacker, will be equal to

Nk   Nk  .      (37)

Sub-step 2.2: The attacker will start a brute force search of the values in the set R with a repetition.

The space R in this step will consist of L  N elements, because N elements were correctly selected in the previous step in order to get C correctly from C by applying gamma decryption. From definition 1, we conclude that in the case of the splitting level k , each combination of k integers is calculated using one value ri from the space R , which is consisting of L  N elements in this step. The attacker will enumerate the values from  Nk  elements with repetition from the values of the set R with the size L  N . The number of all possible outcomes is given by the following expression:  N                          nk  (L  N ) k    (38) 

Sub-step 2.3 is trying to extract the plaintext using the rules (7), using combinations of numbers

constructed in sub-step 2.1 and combinations of integers obtained in sub-step 2.2.

Consider PrS/G (M k | C , k ) – The probability of a successful unauthorized restoration of the plaintext M based on the intermediate ciphertext C at the level of splitting k , it is determined by the following formula:

                     PrS/G (M | C , k )  spkk ,    (39)  where, pk – is the number of attempts to restore of a plaintext M meaningfully by the attacker at the level of splitting k ; sk – the total number of all possible attempts to get the plaintext M at the splitting level k .

First, let's find sk . Since the attacker was obviously unable to extract the correct plaintext from all previous levels of splitting, then sk is given as following:

sk  n2  n3  ...  nk   (40)  where, n2 – is the total number of all possible attempts to get the plaintext at the level k  2 , n3 – is the total number of all possible attempts to get the plaintext M at the level k  3 , and nk – is the total number of all possible attempts to get the plaintext M at the current level k .

Substituting the values nk , n3 and n2 from equations (38), (28) and (19) into expression (40), we obtain the following expression:

 N   N   N                                  sk  (L  N ) 2   (L  N ) 3   ...  (L  N ) k    Or

k  N                             sk   (L  N ) i 

i2 (41) 

Similar of what was discussed in the section (a) and (b) the number of correct extractions of the

meaningful text, which meets the plaintext M , is equal to one.

pk  1.  (42) 

Replacing the values of sk and pk , from equations (41) and (42) in formula (39), we obtain the result                                 PrS/G (M | C , k) 

1  k  N  1 k (L  N ) Ni    i2 (L  N ) i     i2 (43) 

The third step: calculating PrSG (M | C, k) .Replacing the values of PrG (C | C, 1) and PrS/G (M k | C , k ) , from equations (36) and (43) in formula (35), we obtain the result:  k  N  1 PrSG (M | C, k)  PrS/G (M | C , k)  PrG (C | C, 1)    (L  N ) i     LN 1

 i2   k  N  1                                     PrSG (M | C, k)   LN   (L  N ) i  

 i2  (44) 

The equations (24), (34), and (44) lead that Lemma 2 is valid for any natural number k . Lemma 2 is proved.

For example, if we choose the values N  9 and L  24 in accordance with the proven formulas for Lemma 1 and Lemma 2 we obtain the Figure 1: which shows a graph for the behavior of formulas ( 8 ) and (14) for the probabilities of unauthorized recovery of the plaintext at the various level of splitting k . Figure 1: Example  of  the  probability’s  behavior  of  an  unauthorized  recovery  of  the  plaintext  at  different level of splitting k 

3. Conclusion 

This article presents the effectiveness and importance of the splitting cryptosystem over the gamma cipher and what makes it special is its ability to change its level of protection of information by changing the level of splitting. A Lemma was proved that the splitting secrecy of the cryptosystem increases with increasing the splitting level, which allows us to speak about the asymptotical secrecy obtained by the splitting cipher.

4. Acknowledgements 

This work was supported by RFBR №18-07-00736A and №17-29-07053. I wish to extend my special thanks to both professor Stefanyuk Vadim Lvovich and professor Orlov Yuri Nikolaevich at the information technology department, Peoples' Friendship University of Russia, Moscow, Russia.

5. References 

References

[1] V. L. Stefanyuk , A. H. Alhussain , "Symmetric Encryption on the Base of Splitting Method" Bulletin of PFUR , Series Mathematics, Information Sciences, Physics 2 ( 2016 ) 53 - 61 .

[2] J. C. Skaff Stephanie , Probabilistic and Statistical Methods in Cryptology: An Introduction by Selected Topics , Naval Postgraduate School, ( 2009 ) 137 .

[3] A. Alhussain , The effectiveness of symbolic integer splitting method over both synchronous stream ciphers and perfectly secret ciphers , Journal of Physics: Conference Series 1687 ( 2020 ) 012006 1 - 8 . doi: 10 .1088/ 1742 -6596/1687/1/012006.

[4] D. Melnikov , V. Fomichev , Cryptographic methods of information security, 2, Systemic and applied aspects , Litres, ( 2021 ) 243 .

[5] E. P. Paul , Concepts of Probability Theory: Second Revised Edition , Courier Corporation ( 2013 ) 416 .

[6] L. Lester , Introduction to Probability Theory with Contemporary Applications , Courier Corporation ( 2012 ) 368 .

[7] E. Biham , A . Shamir, Differential Cryptanalysis of the Data Encryption Standard , Springer Science & Business Media ( 2012 ), 188 .

[8] A. H. Alhussain , "Asymptotic secrecy of the information protection by the usage of simple integer splitting method" , IOP Conference Series: Materials Science and Engineering 862 ( 2020 ) 1 - 7 . doi: 10 .1088/ 1757 -899X/862/5/052032.

[9] K. Achim , Probability Theory: A Comprehensive Course , Springer International Publishing ( 2020 ) 716 .

[10] K. Achim , Probability Theory: A Comprehensive Course , Springer International Publishing ( 2020 ) 716 .