The Method of Joint Execution of the Basic Operations of the Rabin Cryptosystem

Abstract

The process of performing arithmetic operations of addition, multiplication, and exponentiation, where the operands are multi-bit numbers, is extremely common in applied problems of number theory, computational and discrete mathematics. This applies to methods of pattern recognition, digital signal processing, tamper-proof coding, statistical data processing, etc. However, their most important application is in asymmetric cryptography. In this field, for example, in the Rabin cryptosystem, it is often necessary to simultaneously perform the Euclidean algorithm and multiply two multi-bit numbers. The work presents new methods of finding the greatest common divisor based on the formation of appropriate matrices, which allows parallelization of calculations. Their advantages over the existing ones are indicated, in particular, the possibility of increasing speed. It was established that these methods, in addition to finding the greatest common divisor, make it possible to factorize it simultaneously. In the C+ high-level programming language, a program implementation of the simultaneous execution of the Euclidean algorithm and the multiplication of two multibit numbers by the classical Euclidean algorithm and the proposed methods was carried out. Corresponding experimental studies of the time characteristics of this software implementation have been conducted. The proposed method involves the use of intermediate results of the Euclidean algorithm and access to the table of squares stored in the computer's memory. The Rabin encryption scheme based on the proposed method of multiplying multi-bit numbers is given. Numbers of different digits were used for the experiment. It is shown that in the vast majority of cases considered, the proposed method is characterized by a higher speed of processing multi-bit numbers. The average time of operations is reduced by approximately 1.43 times. All calculations were repeated 5000 times to eliminate random influences on the time characteristics of the computer. The proposed method can be effectively used when simultaneous execution of the Euclidean algorithm and multiplication of two multi-bit numbers is required.

Keywords

• 1 Multiplication operation
• Euclidean algorithm
• Rabin cryptosystem
• prime numbers
• time characteristics
• number digits

1. Introduction

Currently, the performance of arithmetic operations on multi-bit numbers is very widely used in various fields of science and technology, in particular, when solving problems of computational, applied and discrete mathematics [1-2]. Moreover, each of the corresponding algorithms has its own area of effective use depending on the bit rate, calculation model, programming language, hardware or software implementation [3]. Multi-bit number processing processes are extremely common in digital signal and image processing [4-6], methods of tamper-proof coding [7-8]. But this especially applies to the problems of cryptography [9-11], where the most common operations are multiplication, exponentiation [12], finding the greatest common divisor (GCD), use of the Chinese remainder theorem (CRT) [13-14], etc. The combination of the first two with the rest of the operations requires a strictly sequential implementation, which significantly reduces the speed of computer systems. An example can be the Rabin cryptosystem, in which the Euclidean algorithm is used to apply the CRT, and the same numbers must be multiplied to form the public key. Therefore, the question of the possibility of parallelization of similar operations [15], in particular, the use of the residual number system (RNS) [16, 17].

2. Related works

2.1. Rabin cryptosystem

To generate keys in the Rabin cryptosystem, two large prime numbers p and q are chosen, which act as a secret key. Their product m=pq is a public key. The encryption of the plaintext block V, which must be maximal but less than m, occurs according to the formula Z=V2mod m.

Decryption is much more complicated and takes place in several stages. First, the residuals z1=Z mod p and z2=Z mod q. are sought. Next, you need to determine the square roots modulo: z1 mod p  z11, z12  z11  p  z11; z2 mod q  z21, z22  z21  q  z21.

After that, four pairs of residues are formed from the values of zij, where i, j=1, 2: (z11, z21), (z11, z22), (z12, z21), (z12, z22).The last stage of deciphering is a four-fold application of CRT. However, before that, it is necessary to find the values of parameters s i t in the fornula sp+tq=1 using the Euclidean algorithm and its consequence. This gives four variants of the plaintext block, one of which is correct: 1) V1=spz21+tqz11; 2) V2=spz22+tqz11; 3) V3=spz21+tqz12; 4) V4=spz22+tqz12.

Figure 1 shows the Rabin encryption scheme.

So, the complete cycle of Rabin cryptosystem involves the execution of Euclidean algorithm for two numbers (private keys) and their multiplication.

2.2. Greatest common divisor search methods

The mathematical notation of Euclidean algorithm looks like this: for any X>Y=r0, where X and Y are integers, the system of equations is fulfilled.

X  r0  q1  r1, q1  Y , 0  r1  r0; r0  r1  q2  r2 , 0  r2  r1; ................................ rn2  rn1  qn  rn , 0  rn  rn1; rn1  rn  qn1  0.

GCD (X, Y), calculated using the Euclidean algorithm, will be equal to rn, that is, the last non-zero term of the sequence ri. When the numbers X and Y are mutually prime, which is important for asymmetric cryptography, then rn=1.

In addition, in [18], entitled Optimized GCDSAD, proposed a new method that computes the GCD of two 32-bit numbers using an absolute difference sum block.

2.3. Methods of performing the multiplication operation

Many algorithms have been developed for multiplication (standard, binary, Montgomery, Karatsuba-Ofman, etc.), which are characterized by different computational complexity. It should be noted that multiplication, in particular, modular, is the most critical operation when using asymmetric cryptosystems. For example, in [19] they present new optimal methods of modular multiplication, which are based on interleaved Montgomery multiplication on 16-bit MSP430X microprocessors. Meanwhile, a part of the multiplication is performed in the hardware multiplier, and part - in the basic arithmetic logic device. In [20] it is presented the implementation of multiplication and squaring for 32-bit ARM Cortex-M4 microcontrollers. Implementation and research of fast modular exponentiation on FPGAs using multiplication is presented in [21]. В 22[-23] a hardware architecture for efficient modular exponentiation in asymmetric cryptography is presented. In [24] prospects for the use of modern software in Montgomery arithmetic are given.

However, theoretical studies do not always show the real picture regarding the speed of calculations, as they do not take into account all the factors that affect the computer's operation, in particular, memory access, features of the processor load, its bit rate and parallelization of calculations, etc.

Therefore, the aim of our work is to find, compare and analyze the time of simultaneous execution of the Euclid algorithm and multiplication of two multi-bit numbers performed using the classical and proposed methods for numbers of different bits on a computer with given parameters.

3. Proposed model

3.1. The method of searching for GCD using parallelization

To parallelize the search for GCD, it is advisable to use the proposed algorithm based on RNS, which involves working with residues [25]. It consists of the following stages.

1. Numbers are represented in the binary numbering system:

X  xn1  2n1  xn2  2n2   xi  2i   x0  20 ;

Y  yn1  2n1  yn2  2n2   yi  2i   y0  20 .

Where n is the bit rate of the input data.

2. Binary codes of numbers X and Y are represented in the delimited system of residual classes in the form of residual vectors according to the following expressions:

(xi  2i ) mod p j  aij , ( yi  2i ) mod p j  bij , where і=n-1, n-2, …, 1, j=00;, 1, …k.,

As a result, the codes of numbers X ,Y in the system of simple modules p j can be represented in the form of residual vectors that form the corresponding matrices: an1,1 an2,1  ai,1  a0,1 bn1,1 an1,2  an1, j  an2,2

 an2, j      ai,2  ai, j      a0,2

... a0, j  bn1,2  bn1, j  bn2,1 bn2,2

 bn2, j       bi,1 bi,2  bi, j       b0,1 b0,2

 b0, j  an1,k an2,k  ai,k  a0,k bn1,k bn2,k  bi,k  b0,k The given representation of X ,Y in the form of residual vectors can be summarized as follows:

X  aij , Y  bij , деі=n-1, n-2, …, 1, j=00;, 1, …k.,, 0  aij ,bij  pj 1.

Then, for the multiplicative GCD (MGCD) z, the inequality must hold:

k 1  z   p j .

j1 3. Next, the elements of matrices ( 2 ) need to be represented in the form of two vectors:  n1   n1  a j    aij  mod p j ;bj   bij  mod p j

 i1   i1  for all j  0, k .

From ( 4 ), two vectors are obtained that represent numbers X ,Y in the integer system of residual classes:

X  (a1 a j  bj  0, j 1, k . Then, the desired MGCD is obtained from the following expressions: z  j1 p j , p j   p j 1,,aaj jbbjj 0 . ( 6 )

k 4. In order to find the GCD Z, the input numbers X and Y are represented in the delimited numbering system by modules p j that meet the condition ( 6 ). Then, according to ( 2 ), matrices of residues are created by modules p jm , where m , is the exponent of the degree for which condition ( 6 ) is fulfilled: ( 1 ) ( 2 ) ( 3 ) ( 4 ) ( 5 )  a j 2   ki11 aij  mod p j 2  bj 2   ki11 bij  mod p j 2 ...a..j..3........ki.1.1.a..i.j...m...o..d..p...j3.... ; ...b..j..3........ki.1.1.b..ij....m..o..d...p..j.3.... ( 7 )  a j m   ki11 aij  mod p j m  bj m   ki11 bij  mod p j m .

The verification of condition ( 6 ) for powers is performed according to comparisons

YXmm  ((bajj22 bajj33 ...... abjjkk ));. ( 8 ) Then the GCD is calculated according to the following multiplicative function:

k Z   p j m . ( 9 )

j1

In comparison with the well-known Euclidean algorithm, the proposed algorithm for finding the GCD is characterized by the following advantages: 1. Formation of matrices can occur in parallel using several processors. 2. Simultaneously with the search for the GCD, its factorization takes place.

An improved method of searching for GCD using parallelization

The proposed algorithm can be significantly improved by removing the third step with the fulfillment of an additional condition:

min j : a j  bj  0 .

The search of the GCD for the components p j that meet the condition ( 10 ) is carried out on the basis of the representation of the input numbers X and Y in the delimited RNS according to ( 2 ). Next, the matrices ( 10 ) of the residuals are formed by p j m , where m , is the exponent of the power at which the condition ( 10 ) is fulfilled. After that, the remainders are searched for products of modules, p j,k ms  p j m  p jk s , where s is the exponent of the power at which the condition is fulfilled, a j,k  bj,k  0 , k is the next simple module after the j . Residue matrices are formed:  a j,k 2   n1 aij  mod p j,k m2   i1   a j,k 3   ni11 aij  mod p j,k m3  ...................................... a j,k ms    n1 aij  mod p j,k ms   i1   bj,k 2   n1 bij  mod p j,k m2   i1   bj,k 3   ni11 bij  mod p j,k m3 ...................................... bj,k ms    ni11 bij  mod p j,k ms .

Thus, the product of all simple modules to Y powers, for which the condition a j,k  bj,k  0 is fulfilled, will be GCD, i.e.: k Z   p j mj . (12)

j1

The main advantage of this algorithm in comparison with the previous one is the avoidance of the search for MGCD, which will significantly increase the speed of operation. 3.2. Algorithmic support for the simultaneous execution of the Euclid algorithm and multiplication

In Rabin cryptosystem, the given numbers a and b are prime, so it is known that in this case GCD (а,b)=rn=1. In contrast to the execution of the Euclidean algorithm followed by the multiplication of ( 10 ) (11) begin a>b a=a-b

Yes c=c+ square[b] c=c+ square[a] No

b=b-a

No a,b, square[1..max(a,b)] a=1 or b=1 c=c+max(a,b)

Yes c end these same numbers, it is proposed, according to ( 1 ), to use the intermediate and final results of the Euclidean algorithm in the multiplication as follows: a  b  r02q1  r12q2  r22q3  ...  rn21qn  rn2qn1 . (13)

It should be noted that the number of terms in (13) corresponds to the number of steps in Euclidean algorithm. Although this method involves the performance of a larger number of arithmetic operations, they will be performed on numbers of smaller digits. Having a table of squares in the computer's memory is an essential step to increase performance, although this leads to an increase in the use of computer system resources. The block diagram of the algorithm is shown in Figure 2.

4. Results and Discussions

4.1. Selection of hardware and software

A Lenovo IdeaPad 1 15IAU7 Cloud Gray laptop computer with an Intel Core i5-1235U processor (4.4 GHz) was chosen for experimental research. The amount of RAM in the device was 8 GB. When designing the software complex that provided calculations, the C++ high-level programming language was chosen. A special purpose library written by A. Lenstra was used to work with multi-bit numbers. This made it possible to provide flexible possibilities for working with multi-bit numbers, the size of which depends only on available system resources. The selected programming language and the cross-platform nature of the special library allow you to transform the codes for different architectures and operating systems. The most common method of software implementation of Euclidean algorithm is to subtract a smaller number from a larger number successively until the difference becomes less than the denominator. Then the same procedure must be performed with the subtractor and the difference. The subtraction process will continue until the numerator and the difference are equal.

4.2. Obtained results and their discussion

0,05 0,04 0,03 0,02 0,01 0 t1 t2 t2av b 2 4 6 8 10 12 14 16 18 20 22 24 26 28 30 32 34 36 38 40 42 44 46 48 50 52 54 56 58 60 62 64 66 68 70

The graphs have an oscillating character, which is explained by the different number of steps in the Euclid algorithm for different numbers. In 60 cases out of 69, which is 87%, calculations using the proposed method are performed faster, in 7 (10%) - slower, in 2 cases (3%) the execution time of both methods is the same. The average time values are respectively t1av=0,040333 s and t2av=0,028174 s, which is also presented on the graph. Therefore, the speed increased by an average of 1.43 times.

Table 2 presents the average time of simultaneous execution of the Euclidean algorithm and multiplication by the classical (t3) and proposed (t4) methods in the case when the prime numbers a are within one bit from 67 to 127, and Figure 4 shows the corresponding graphs depending on the number. Meanwhile, b changes from 2 to а-1. t3 t4

Number 67 71 73 79 83 89 97

It can be seen from Figure 4 that the average working time of the proposed method is in all cases less than that of the classical method. The general trend shows an increase in time when the given numbers increase, and the graph for the classical method grows more intensively.

Table 3 presents the average time of simultaneous execution of the Euclidean algorithm and multiplication by the classical (t5) and proposed (t6) methods in the case when the bit size of n prime numbers a is in the range from 7 to 16 bits, and in Figure 5 - the corresponding graphic dependencies in the logarithmic scale. The number b changes similarly to the previous case.

It can be seen that the average working time increases almost linearly with the increase in the number of bits, and the graph for the classical method grows more intensively. 0,07 0,065

0,06 0,055

0,05 0,045

0,04 0,035

0,03 0,025 0,02

t5 log2a t7, s t8, s 0,14 0,13 0,12 0,11

0,1 0,09 0,08 0,07 0,06 0,05 0,04

16 t6 t8 log2a 7 7,5 8 8,5 9 9,5 10 10,5 11 11,5 12 12,5 13 13,5 14 14,5 15 15,5 t7

5. Conclusion

The work deals with an experimental study of the time of simultaneous execution of the Euclidean algorithm and multiplication of two multi-bit numbers by classical and proposed methods. The C++ high-level programming language is used. The proposed method stipulates the use of intermediate results of the Euclidean algorithm and the table of squares available in the computer's memory. The research was conducted on numbers of different digits. It is shown that for the vast majority of the considered numbers, the proposed method requires less time to perform arithmetic operations. The average time of simultaneous execution of the Euclidean algorithm and multiplication decreases by approximately 1.43 times.

In addition, new methods of finding the greatest common divisor based on the formation of residual matrices are given. This makes it possible to parallelize the process of processing multi-bit numbers and, accordingly, increase the speed. It was established that the procedure for finding the greatest common divisor by the proposed methods is accompanied by its factorization.

References

[1] K.C. Fuson , The Best Multidigit Computation Methods: ACross-cultural Cognitive, Empirical, and Mathematical Analysis . Universal Journal of Educational Research , Vol. 8 ( 4 ), 2020 , pp. 1299 - 1314 . doi: 10 .13189/ujer. 2020 .080421

[2] J.S. Milne , Algebraic Number Theory. Version 3 .08. MilneANT, 2020 , 166 p.

[3] P. Pandey , R. Gupta , M. Khan , S. Iqbal, Multi-Digit Number Classification using MNIST and ANN . International Journal of Engineering Research & Technology (IJERT) , 9 ( 05 ) ( 2020 ) 415 - 421 .

[4] C. Luo , Y. Hao , Z. Tong , Research on Digital Image Processing Technology and Its Application. Proceedings of the 2018 8th International Conference on Management, Education and Information (MEICI 2018 ). Series: Advances in Intelligent Systems Research , 2018 , pp. 587 - 592 . DOI: 10 .2991/meici- 18 . 2018 .116

[5] K. Priya , B. Rasheeda Banu , T. Umme Habiba , A. Boosra , Digital image processing techniques-a review . International Journal of Emerging Technologies and Innovative Research , 6 ( 9 ) ( 2019 ) 56 - 61 .

[6] L. Zhang , L. Zhang , L. Zhang, Application research of digital media image processing technology based on wavelet transform . J Image Video Proc. , 138 ( 2018 ). doi: https://doi.org/10.1186/s13640-018-0383-6

[7] I.A. Aremu , K.A. Gbolagade , Redundant Residue Number System Based Multiple Error Detection and Correction Using Chinese Remainder Theorem . Software Engineering , Vol. 5 ( 5 ), 2017 , pp. 72 - 80 . doi: 10 .11648/j.se. 20170505 .12

[8] H. Xiao , H. Garg , J. Hu , G.Xiao, New Error Control Algorithms for Residue Number System Codes . Electronics and Telecommunications Research Institute , 38 ( 2 ) ( 2016 ) 326 - 336 . doi:https://doi.org/10.4218/etrij.16.0115.0575

[9] M. Kasianchuk , I.Yakymenko, Y. Nykolaychuk , Symmetric Cryptoalgorithms in the Residue Number System . Cybernetics and Systems Analysis , 57 ( 2 ) ( 2021 ) 329 - 336 . doi:https://doi.org/10.1007/s10559-021-00358-6

[10] V. Adki , S. Hatkar , A Survey on Cryptography Techniques. International Journal of Advanced Research in Computer Science and Software Engineering , 6 ( 6 ) ( 2016 ) 469 - 475 . doi:https://doi.org/10.15587/ 2706 - 5448 . 2020 .202099