Modular exponentiation is an important operation in many applications that requires a large number of operations. Efficient computations of the modular exponentiation are extremely necessary for efficient computations for provide high crypto capability of information data and in many other applications. Modular exponentiation is implemented using of the development of the right-to-left binary exponentiation method for a fixed base with precomputation of redused set of residuals. To efficient compute the modular exponentiation over big numbers, the property of a periodicity for the sequence of residuals of a fixed base with exponents equal to an integer power of two is used. The multithreading software implementation of modular exponentiation is described. The MPIR library with an integer data type with the number of binary digits from 256 to 2048 bits is used to develop an algorithm for computing the modular exponentiation. Comparison of the runtimes of four variants of functions for computing the modular exponentiation is performed. In the algorithm with pre-computation of residues for fixed-base provide faster computation of modular exponentiation compared to the functions of modular exponentiation of the MPIR, OpenSSL and Crypto++ libraries.
Computing the modular exponentiation for big numbers is widely used to find the discrete logarithm, in number-theoretic transforms, and in cryptographic algorithms. New methods, algorithms and means of their implementation are being researched for efficient computation of the modular exponentiation. There are three directions of modular exponentiation methods: general modular exponentiation, and computation of a modular exponentiation with a fixed exponent or with a fixed base [1]. Special functions have been developed to perform modular exponentiation in mathematical and cryptographic software libraries (Crypto++, OpenSSL, Pari/GP).
Modular exponentiation and discrete logarithm for big numbers require significant computing resources for their implementation. The discrete logarithm is considered a unidirectional function (1), because it is quite difficult to calculate it in a conventionally acceptable time, for example, for breaking a cryptographic code.
The discrete logarithm problem [2] is formulated as follows: for known integers A, N, y, find an integer x such that x lo g A y , ( 0 x N 1) , (1) (2)
That is, having determined the number x, which is the solution of equation (2), we will find the discrete logarithm. Thus, the problem of the discrete logarithm is reduced to the calculation of the modular exponentiation in the form (2).
The paper considers the basic iterative algorithm for computing the modular exponentiation (2) using pre-computation to form a shortened sequence of residues of the fixed base A. The software implementation of multi-threaded computation of the modular exponentiation for big numbers is described. In the discussion section of the results, a comparison of the average executing time of computing the modular exponentiation with the primitives of cryptographic libraries (OpenSSL, Crypto++) is made. The conclusions summarize the possibility of applying the computation of the modular exponentiation (2) using the pre-computation of the remainders of the fixed base A.
Modular exponentiation, Ax mod N, is a basic arithmetic operation in most public-key cryptosystems. Many effective methods of modular exponentiation have been developed and are often used to reduce the execution time of the modular exponentiation operation, which are reviewed in works [3-6]. In paper [3] is described well-known exponentiation algorithms with their complexity analysis and general exponentiation algorithm of zero-one sequences.
There are three types of exponentiation algorithms Ах mod N [1], which include: 1) basic techniques for exponentiation; 2) fixed-exponent x exponentiation algorithms; 3) fixed-base A exponentiation algorithms.
Among the main modular exponentiation algorithms, the following effective solutions are distinguished: right-to-left k-ary exponentiation, right-to-left k-ary exponentiation, left-to-right k-ary exponentiation, exponent with a sliding window (sliding window exponentiation), Montgomery ladder, simultaneous multiple exponentiation and their modifications.
In many works, the method of binary exponentiation with a right-to-left shift is used. Cohen's book [7] presents a more complete discussion of the binary right-to-left and left-to-right methods together with their generalizations to the k-binary method.
A fixed element of a group (generally z/qz) is repeatedly raised to many different exponent in several cryptographic systems. A popular application of fixed-base exponentiation is in elliptic curve cryptography, for instance for Diffie-Hellman key agreement and elliptic curve digital signature algorithm verification. Therefore, many research works have been focused on a fixed base of modular exponentiation [1, 8].
Considerable attention is paid to the hardware implementation aimed at efficient computation of the modular exponentiation. One of the ways to speed up the computation of modular exponentiation is the parallelization of calculations using modern technologies in universal computer systems [9, 10] or the creation of specialized computing tools [11].
The modern software libraries are used to implement the computation of modular exponentiation. The software implementation of the modular exponentiation computation is included in the software libraries Crypto++ and OpenSSL, PARI/GP, MPIR designed for working with big numbers [12-15]. For example, the Pari/GP software library [12] contains a large set of programs for efficient computations of mathematical functions. The Pari/GP library also includes computation of the modular exponentiation function for big numbers and other special numbers. A highly optimized modification of the well-known GMP or GNU Multiple Precision Arithmetic Library the MPIR library [13] contains the function of the realization the computation of modular exponentiation. The library of cryptographic algorithms and schemes Crypto++ is implemented in C++ and fully supports 32 and 64-bit architectures of many operating systems and platforms [14]. The library contains a set of available primitives for theoretical and numerical operations, such as generation and verification of prime numbers, arithmetic over a finite field, operations on polynomials.
The importance of speeding up the software calculation of modular exponentiation leads to new algorithmic solutions and their implementations [16].
The parallelization of computation of modular exponentiation, based on the use of the exponent x as a binary number ( x(k-1) x(k-2)… x2 x1 x0 ), uses the application of the fundamental property of modularity was described in paper [9]. Accordingly, the computation of the modular exponentiation (1) takes the form y A x ( k -1 ) x( k 2 ) ... x2 x 1 x0 mod N ( A x ( k -1 ) 2 k-1 mod N A x( k 2 ) 2 k-2 mod N ... A x2 2 2 mod N A x 1 2 1 mod N A x0 2 0 mod N ) mod N ; (3) In accordance with formula (3), a scheme for computing of the modular exponentiation [17] is shown on Figure 1. Figure 1: The scheme for computation of modular exponentiation Ах mod N. The scheme for computing the modular exponentiation consists of the denotations: A is the input of the base number; N is the input of the module; (A^2i) mod N are blocks of computation of the integer exponent of exponent 2i of the number
A by the module, i = 0,1,2,…, (k-1); x is the input of an exponent with binary digits x.(k-1), x.(k-2),…,x.2, x.1, x.0; (X) mod N is the block of multiplier under modulo N; y is the output of the modular exponentiation.
Consistently determined residuals of the number a raised to the power of 2i under modulo N in blocks (A^2i) mod N, for i=0, 1,…, k-1 are multiplied. In the case of presence of the exponent of the number of binary the value of zero in i-th binary digit (x.i) block (A^2i) mod N is not execute the operation, otherwise is computed the multiplication of exponent 2i of the number A under modulo N, which corresponds to the denotation in Figure 1. The determined product, in the final stage, are formed in blocks (X) mod N the value y of the result of the computation of the modular exponentiation.
For the organization of modular exponentiation execution, in accordance with Figure 1, it is possible to consider the possibility of creating two threads. The thread I computes the numbers a raised to the power of 2i under modulo N. The thread II computes the product of the results (A^2i) mod N, starting with the readiness of the first two values (A^2i)mod N. Theoretical it is possible to reduce the computation time to 50% of the modular exponentiation in comparison with single thread computation. However, serial or parallel computations (A^2i) mod N for big data create a significant delay in the thread I execution [9].
Consider the basic iterative algorithm for computing the modular exponentiation (3) using precomputation to form a shortened sequence of residues of the fixed base A. Compute, respectively (3), the value modulo N for a simple fixed-base A with exponents x =2i = 1, 2, 4, 8, 16… , (i =0,1,2,…, r1).
Let A and N be relatively prime positive integers (A, N) = 1 and denote the least positive integer x = expN A. Accordance, if A and N relatively prime (A, N) = 1, positive integer x is solution of the congruence, if and only if
x q exp N A, (4)
Accordance the Euler’s theorem, if A and N relatively prime (A, N) = 1, that Аφ(N)≡1 (mod N). Consequently, we can do conclusion
( N ) q exp N A , (5)
In case q=1, then φ(N) = expN R, where R is the positive integer is called a primitive root modulo N. However the positive integer of modulo N, possesses a primitive root R if only if N=2, 4, P k or 2P k, where k is positive integer. The primitive root for modulo N =P1k1 P2k2… Pmkm does not have, except if φ(P1k1), φ(P2k2) ,…, φ(Pmm1) are relatively prime.
Thus, calculating (R)i mod N (i = 0,1, 2 ,,… N-1), we form a sequence of residuals (r0, r1, r 2, …, ri,…, rN-1), which periodically repeated for x > (N-1) exponents. For all values of A ∈ Zp, the sequence Ai mod P is cyclic for a non-primitive element.
For example, for a primitive element R = 7, the sequence of residual values r i = (7i) mod 11, (r0, r1, r2, r3, r4, r5, r6, r7, r8, r9) = (1, 7, 5, 2, 3, 10, 4, 6, 9, 8).
The maximum period of repetitions is equal to exp117 = 10, because 710 mod 11=1, i =0, 1, 2, …, 9. The unique integer x with 1≤ x ≤ φ (N) and Rx mod N ≡ A is called index (or discrete logarithm) indRA of A to base R modulo N. Then the sequence of the indices is equal
(0, 1, 2, 3, 4, 5, 6, 7, 8, 9) = (ind71, ind77, ind75, ind72, ind73, ind710, ind74, ind76, ind79, ind78). Accordingly of the property of indeces ind7 1= 0, ind7 6 = ind7 (2*3)= ind7 (2)+ ind7 3 mod 10= 3+4=7; ind7 9 = ind7 (32) = 2 * ind7 3 mod 10 =2*4=8.
In the case of calculating 7x mod 11 with index x = 32, the index will be equal to (32 mod (ind117)) = 2, and accordingly ind75. In the case of determining (72 ^ 6) mod 11, we find the number of the residue in the sequence with the index ind73, which is equal to (26) mod 10 = 4. After all, the value of the modular exponentiation for 2 elements in the sequence of residual values r4 = 3 = (72 ^ 6) mod 11. For computations according to formula (3), we determine the residuals for exponents 2i, (i =2, 3, 4, where t={i /T ’} is integer part from division.
Therefore, for a fixed-base A of the modular exponentiation (3), which is equal to the product of the residuals of the exponent (A^2i) mod N, (i = 2, 3, 4, …), you can speed up the process of computing the modular exponentiation by pre-computing (Figure 2) the sequence of residuals, what repetitions with the period T' after the offset u. Figure 2: The scheme for computation of modular exponentiation Ах mod N with pre‐computation.
Thus, on base to the parallel execution of the computation of the modular exponentiation with pre-computation, in accordance with Figure 2, consider the possibility of creating the threads of execution of the product of the residual values under modulo defined in the parallel previous threads residuals of the exponents (A^2i) mod N, (i = 2, 3, 4, …) under modulo operations. The only difficulty of organizing the computation with such threads is the need to synchronize the performance of threads to ensure the correct computation of the final value y of the modular exponentiation.
The algorithm is implemented in C++ language as modular exponentiation function precompute_parallel() with aim to compare the performance execution. To implement the algorithm, the library functions mpz_init_set (mul, base), mpz_sizeinbase (exp, 2), mpz_tstbit (exp, i), mpz_mul (r, r, mul) from the MPIR library are used, the parameters of which are multi-bit data up to 2048 bits. The software implementation consist the functions:
precompute_parallel (const RemaindersData&data, const mpz_class&exp, ctpl::thread_pool&pool); parallel (const mpz_class& base, const mpz_class& exp, const mpz_class& mod); precompute (const RemaindersData& data, const mpz_class& exp); find_remainders (const mpz_class& base, const mpz_class& mod, size_t max_exp_bits); find_period (const std::vector<mpz_class>& remainders); get_remainder (const RemaindersData& data, size_t power); update_remainders (RemaindersData& data); thread_function(bool* quit_thread); multiplication_thread (int id, MultiplicationThreadData* data) and others.
The functions find_period (const std::vector<mpz_class>& remainders) computes the products modulo over the pre-computed values of the residuals (A ^2i) mod N, which are read using the function get_remainder (const RemaindersData & data, size_t power). In the cycle of the function mpz_tstbit (exp, i) binary bits x.i of exponent exp are analyzed to determine to perform or not a multiplication operation modulo, accordance the Figure 3 in the pre-computation unit. The computation of the value of the modular exponentiation ends by writing the result in the variable period_mod_exp_result.
The precompute_parallel() function finds the sequence of residuals for fixed numbers Base and mod for Exp = 2i (i = 0, 1, 2, …) and analysis of periodicity. In the program for computing the sequence of residuals is performed by the function find_remainders (const mpz_class & base, const mpz_class & mod, size_t max_exp_bits), which contains the bool function find_period (const std::vector<mpz_class> & remainders) to set the indication of finding the period. The precomputation have been made in a separate function find_remainders () to optimize multiple residual searches (A ^2i) mod N. The function update_remainders (RemaindersData & data), shortens the length of the sequence of residuals to the end of the first periodicity. This function writes the offset period_offset beginning of the period and the length of the period period_size in the corresponding fields of the structure
RemaindersData { mpz_class base; mpz_class mod; std::vector <mpz_class> remainders; size_t period_offset; size_t period_size; } also.
The peculiarity of the large values of Base, mod and Exp is also taken into account for which the residuals must be calculated, in case when the value of the period T' is many orders of magnitude greater than the number of bits of the Exp exponent.
To organize efficient multithreading computation of modular exponentiation according the precompute_parallel() function, the thread_function(bool* quit_thread) and parallel (const mpz_class& base, const mpz_class& exp, const mpz_class& mod) are used. Accordingly, these threads are created to perform the computation of the modular exponentiation. The result of the function is written to the variable s_thread_result, and the computation time is fixed and averaged to output.
To protect the queue from simultaneous access of the threads is used the s_mutex mutex with the basic lock() and unlock() methods. The s_mutex object is passed to our functions, which should use it for interacting. Before accessing the shared data queue s_thread_queue, the mutex is locked by the method lock(s_mutex) and is unlocked after the work with the shared data is completed. The use of a combination a conditional variable and a mutex lock indicates the complexity of the synchronization the performance of threads for computing the modular exponentiation.
To compare the computation efficiency of the developed modular exponentiation functions precompute_parallel () for a fixed base with pre-computation with three functions implemented from the Crypto++ 8.2, MPIR and OpenSSL libraries are used. The developed precompute_parallel () function uses multithreads computation of the modular exponentiation.
The Crypto++ library of cryptographic algorithms and schemes is implemented in the C++ language and supports Unix platforms (AIX, OpenBSD, Linux, MacOS, Solaris, etc.), Win32, Win64, Android, iOS, ARM [14]. The library contains a set of available primitives for number-theoretic operations, such as generation and verification of prime numbers, arithmetic over a finite field, operations over polynomials. Each of the primitives of the Crypto++ library includes a set of functions, among which is the function exp_crypto () for calculating the modular exponent.
The OpenSSL library (The Open Source toolkit for SSL/TLS) contains a set of tools for cryptography that implements the Secure Sockets Layer (SSL v2/v3) and Transport Layer Security (TLS v1) network protocols, as well as the corresponding cryptography standards [15]. OpenSSL supports Solaris, HP-UX, Linux, Android, BSD, UnixWare, Win 32 and 64, macOS, iOS, and other platforms. The library includes three functions to calculate the modular exponent using Montgomery multiplication:
BN_mod_exp_mont () calculates A to the power of p modulo m;
BN_mod_exp_mont_consttime () calculates A to the power of p modulo m. This is a variant of the pre-function, that uses fixed windows and dedicated memory for pre-computation to keep data dependency to a minimum to protect secret exponents;
BN_mod_exp_mont_consttime_x2 () calculates two independent raises of A1 to the power of p1 modulo m1 and A2 to the power of p2 modulo m2. For some fixed and equal modulus values of m1 and m2, the function uses optimizations that make it possible to speed up the calculation.
A highly optimized modification of the well-known GMP or GNU Multiple Precision Arithmetic Library the MPIR library [13] contains the function mpz_powm () to realize computation of ME. The MPIR library uses an optimized version of the ME algorithm, called the "Sliding-window method" [3], which reduce the average number of multiplication operations.
Numerical experiments were carried out on a computer system with a multi-core microprocessor with shared memory in a 64-bit Windows. Testing was performed on computer systems with processors) an Intel Core i5-10600 (6 cores, 12 threads, 3.30GHz) and an Intel Core i9-10980XE (18 cores, 36 threads, 3.0GHz. According to hyper-threading technology, each physical core consists of two virtual ones.
To compute the modular exponentiation with a given number of trials the values of exponent Exp, number Base and mod were given by pseudo-random numbers with number of binary digit of 1024, 2048 bits. To reduce the total computation time on increasing the number of binary digits of long numbers the number of trials of latch-up of the computation time is decrease correspondent. The result of the execution of the function is recorded in the variable expected_result, and the computation time is fixed and averaged with the output of the average value "average time" in microseconds.
The results are presented in Table 2, which contains the values of average execution time (μs microseconds) of computing the modular exponentiation for pseudo-random data Base1, Exp1, mod1 for 1024 bits and Base2, Exp2, mod2 for 2048 bits, that are
The developed function precompute_parallel() performs the computation of modular exponentiation by forming (precompute average time) a reduced sequence of residuals (Figure 4).
The work compares and analyses the developed software implementation precompute_parallel() function of the computation of modular exponentiation and the software implementation of the functions of Crypto++, OpenSSL and MPIR libraries. The computational scheme of modular exponentiation, the software implementation of the algorithm for computing of modular exponentiation, the run time results of the computation on multi-core microprocessors of universal computer systems have been described. As a result, has been developed the computation function precompute_parallel() speedups the execution of the computations using modular exponentiation of the right-to-left binary exponentiation method for a big number of fixed base with pre-computation of redused set of residuals.
The scientific novelty of obtained results lies in the implementation of parallelism using multithreading in the algorithm of computing the modular exponentiation based on the use of the representation of exponent in the form of a binary number and pre-computation for a fixed base of a reduced set of residuals.
The practical significance of the work lies in the fact that the obtained results can be successfully apply in the modern asymmetric cryptography, for efficient computation of number-theoretic transforms and other computational problems. The developed function precompute_parallel() speedups the execution of the computations of modular exponentiation of big numbers in comparison with existing libraries. The especially effective will be use function precompute_parallel() for application with fixed-base exponentiation is in elliptic curve cryptography, for instance for DiffieHellman key agreement and elliptic curve digital signature algorithm verification.
Prospects for further research are the development and implementation Montgomery Modular Multipliers in developed function precompute_parallel() of multithreading computations of modular exponentiation for big numbers. 7. References [1] A. J. Menezes, P. C. van Oorschot, S. A. Vanstone, Handbook of applied cryptography. 5th printing, CRC Press, Boca Raton, 2001. doi:10.1201/9780429466335. [2] C. Studholme, The Discrete Log Problem, 2002. URL: http://www.cs.toronto.edu/~cvs/dlog/research_paper.pdf [3] A. Jakubski, R. Perlinski, "Review of general exponentiation algorithms", Scientific Research of the Institute of Mathematics and Computer Science, 10.2 (2011): 87-98. [4] A. Rezai, P. Keshavarzi, "Algorithm design and theoretical analysis of a novel CMM modular exponentiation algorithm for large integers". RAIRO – Theoretical Informatics and Applications, 49.3, (2015): 255-268. doi:10.1051/ita/2015007. [5] I. Marouf, M. M. Asad, Q. A. Al-Haija, "Comparative Study of Efficient Modular Exponentiation Algorithms". COMPUSOFT, International journal of advanced computer technology, 6.8 (2017): 2381-2392. [6] S. Vollala, K. Geetha, N. Ramasubramanian, "Efficient modular exponential algorithms compatible with hardware implementation of public-key cryptography". Security and Communication Networks, 9.16 (2016): 3105-3115. [7] H. Cohen, A course in computational algebraic number theory. Berlin, Heidelberg: Springer, 1993. doi:10.1007/978-3-662-02945-9. [8] J.-M. Robert, C. Negre, T. Plantard, "Efficient Fixed Base Exponentiation and Scalar Multiplication based on a Multiplicative Splitting Exponent Recoding", Journal of Cryptographic Engineering, Springer, 9.2 (2019): 115-136. doi:10.1007/s13389-018-0196-7. [9] P. Lara, F. Borges, R. Portugal, N. Nedjah, "Parallel modular exponentiation using load balancing without precomputation". Journal of Computer and System Sciences, 78.2 (2012): 575-582. doi:10.1016/j.jcss.2011.07.002. [10] N. Emmart, F. Zheng, C. Weems, C. Faster Modular Exponentiation using Double Precision Floating Point Arithmetic on the GPU, in: Proceedings of the 25th IEEE Symposium on Computer Arithmetic (ARITH), Amherst, MA, USA, 2018, pp. 126-133. doi:10.1109/ARITH.2018.8464792. [11] S. Li, J. Tian; H. Zhu; Z. Tian; H. Qiao; X. Li; J. Liu, Research in Fast Modular Exponentiation Algorithm Based on FPGA, in: Proceedings of the 11th International Conference on Measuring Technology and Mechatronics Automation (ICMTMA), Qiqihar, China, 2019, pp. 79-82. [12] PARI/GP home, 2021. URL: http://pari.math.u-bordeaux.fr/. [13] MPIR: Multiple Precision Integers and Rationals. 2021.URL: http://mpir.org/. [14] Crypto++ Library 8.6, 2021. URL: https://www.cryptopp.com [15] OpenSSL. Cryptography and SSL/TLS Toolkit, 2021. URL: http://www.openssl.org/. [16] C. Negre, T. Plantard, "Efficient Regular Modular Exponentiation Using Multiplicative HalfSize Splitting", Journal of Cryptographic Engineering, Springer, 7.3 (2017): 245-253. doi:10.1007/s13389-016-0134-5. [17] I. Prots’ko, N. Kryvinska, O. Gryshchuk, "The Runtime Analysis of Computation of Modular Exponentiation", Radio Electronics, Computer Science, Control, 3 (2021): 42-47. doi:10.15588/1607-3274-2021-3-4. [18] I. Prots’ko, O. Gryshchuk, "The Modular Exponentiation with precomputation of redused set of resedues for fixed-base". Radio Electronics, Computer Science, Control, 1 (2022): 58-65. doi:10.15588/1607-3274-2022-1-7 . [19] Exponentiation by squaring, 2022. URL: https://en.wikipedia.org/wiki/Exponentiation_by _squaring.