China
Africa
Explore chapters and articles related to this topic
Exponentiation Using Binary-Fermat Number Representations
Published in Vassil Dimitrov, Graham Jullien, Roberto Muscedere, Multiple-Base Number System, 2017
Vassil Dimitrov, Graham Jullien, Roberto Muscedere
The general formulation of the problem for evaluation of modular exponentiation is: given x, y, and z, compute xy(mod z). In reality z is usually a constant (we are unaware of any cryptosystem using variable moduli). One of the two remaining parameters is a constant (a public or private key), and the last one constitutes the message to be encrypted. The Diffie-Hellman key exchange algorithm and the DSS and El-Gamal cryptosystems use a fixed base and a variable exponent. The RSA algorithm uses a fixed exponent and variable base. The speed of fixed-base cryptosystems can be increased by precomputing and storing certain powers of the base. This also includes negative powers, that is, computing certain inverse elements. In the case of RSA this consideration does not work, but one can spend some efforts in attempt to find a “nice” exponent representation that will reduce the amount of time needed to perform exponentiation.
Mathematical Background
Published in Alfred J. Menezes, Paul C. van Oorschot, Scott A. Vanstone, Handbook of Applied Cryptography, 2018
Alfred J. Menezes, Paul C. van Oorschot, Scott A. Vanstone
Modular exponentiation can be performed efficiently with the repeated square-and-multiply algorithm (Algorithm 2.143), which is crucial for many cryptographic protocols. One version of this algorithm is based on the following observation. Let the binary representation of k be ∑i=0tki2i, where each k ∈ {0, 1}. Then
An IBE Scheme with Verifiable Outsourced Key Generation Based on a Single Server
Published in IETE Technical Review, 2018
Ting Xue, Yanli Ren, Guorui Feng
Modular exponentiation is one of the most time-consuming and commonly used operations in cryptography, and many outsourcing schemes for modular exponentiations have been proposed. Hohenbergerd et al. [7] first proposed an outsourcing scheme for single modular exponentiation with two non-colluding servers, where the outsourcer could check the fault that the servers might make with a probability of 1/2, and they also defined the security model of outsourcing calculation. Then Wang et al. [8] presented an outsourcing solution for batch modular exponentiations based on a single untrusted server with increased security, but the checkability was only 1/(s + 1)(where s is the number of modular exponentiations), which means it was not efficient and the checkability was only 1/2 for outsourcing single modular exponentiation. Different from the previous schemes, Liu et al. [9] did the work for outsourcing composite modular exponentiations. Ye et al. [10] proposed a new secure outsourcing algorithm based on a single server, and the verifiable probability is close to 1 while the outsourcer appended much computation cost. Chen et al. [11] firstly presented an efficient outsourcing algorithm for bilinear pairing based on two untrusted servers and the outsourcer need not any expensive operations in their algorithm. Then another outsourcing algorithm was proposed with improved checkability based on two servers for bilinear pairing [12]. Recently, Ren et al. [13] presented a new outsourcing algorithm of bilinear pairing with a verifiability of close to 1 if one of the servers misbehaved, which improved the checkability without an interactive operation between the server and the outsourcer.
A variant RSA acceleration with parallelisation
Published in International Journal of Parallel, Emergent and Distributed Systems, 2022
Jun-Jie Liu, Kang-Too Tsang, Yu-Hui Deng
The key operation in the RSA algorithm is the modular exponentiation of large integers: . To calculate the modular exponentiation, we can transform the operation into a series of modular multiplication or modular squaring operations, named as multiply-and-square exponentiation. The following algorithm is multiply-and-square exponentiation (left-to-right method) [21] based on binary splitting. In each iteration, the square and multiplication are independent and the execution can be parallelised:
Design and verification of improved CMERE against power analysis attacks
Published in Cyber-Physical Systems, 2020
Hridoy Jyoti Mahanta, Abhilash Chakraborty, Ajoy Kumar Khan
The computation of such large modular exponentiation would in general require huge resources allocation, thus modular exponentiation uses various algorithms to speed up as well as calculate results with less resources. ‘Squaring’ and ‘multiplication’ are the two basic operations to all such algorithms, two versions of binary modular exponentiation techniques which have been widely used are shown below in algorithm 2 and 3.