Modular Inverse Algorithms without Multiplications for Cryptographic Applications



Download 288.56 Kb.
Page3/11
Date28.01.2017
Size288.56 Kb.
#9598
1   2   3   4   5   6   7   8   9   10   11

1.4.3Elliptic Curve Cryptography


Prime field elliptic curve cryptosystems (ECC) are gaining popularity especially in embedded systems, because of their smaller need in processing power and memory than RSA or ElGamal. Modular inverses are used extensively during point addition, doubling and multiplication (See more details in [2]). 20….30% overall speedup is possible, just with the use of a better algorithm.

An elliptic curve E over GF(p) (the field of residues modulo the prime p) is defined as the set of points (x,y) (together with the point at infinity O) satisfying the reduced Weierstraß equation:


E : f (X,Y) = Y 2 – X 3 – aX – b  0 mod p.
In elliptic curve cryptosystems the data to be encrypted is represented by a point P on a chosen curve. Encryption by the key k is performed by computing Q = P + P + … + P = k∙P. Its security is based on the hardness of computing the discrete logarithm in groups. This operation, called scalar multiplication (the additive notation for exponentiation), is usually computed with the double-and-add method (the adaptation of the well-known square-and-multiply algorithm to elliptic curves, usually with signed digit recoding of the exponent [15]). When the resulting point is not the point at infinity O, the addition of points P = (xP,yP) and Q = (xQ,yQ) leads to the resulting point R = (xR,yR) through the following computation:
xR = λ2 – xP – xQ mod p

yR = λ∙(xP – xR) –yP mod p

where


λ = (yP–yQ) / (xP–xQ) mod p if P =/ Q

λ = (3x2P+a) / (2yP) mod p if P = Q
Here the divisions in the equations for λ are shorthand notations for multiplications with the modular inverse of the denominator. P = (xP,yP) is called the affine representation of the elliptic curve point, but it is also possible to represent points in other coordinate systems, where the field divisions (multiplications with modular inverses) are traded to a larger number of field additions and multiplications. These other point representations are advantageous when computing the modular inverse is much slower than a modular multiplication. In [11] the reader can find discussions about point representations and the corresponding costs of elliptic curve operations.

2.Hardware Platforms

2.1Multiplications


There are situations where the modular inverse has to be, or it is better calculated without any multiplication operations. These include

  • If the available multiplier hardware is slow.

  • If there is no multiplier circuit in the hardware at all. For example, on computational platforms where long parallel adders perform multiplications by repeated shift-add operations. (See [13] for fast adder architectures.)

  • For RSA key generation in cryptographic processors, where the multiplier circuit is used in the background for the exponentiations of the (Miller-Rabin) primality test. [10]

  • In prime field elliptic or hyper elliptic curve cryptosystems, where the inversion can be performed parallel to other calculations involving multiplications.

Of course, there are also computational platforms, where multiplications are better used for modular inverse calculations. These include workstations with very fast or multiple multiplier engines (could be three: ALU, Floating point multiplier and Multimedia Extension Module).

In digit serial arithmetic engines there is usually a digit-by-digit multiplier circuit (for 8…128 bit operands), which can be utilized for calculating modular inverses. This multiplier is the slowest circuit component; other parts of the circuit can operate at much higher clock frequency. Appropriate hardware designs, with faster non-multiplicative operations, can defeat the speed advantage of those modular inverse algorithms, which use multiplications. This way faster and less expensive hardware cores can be designed.

This kind of hardware architecture is present in many modern microprocessors, like the Intel Pentium processors. They have 1 clock cycle base time for a 32-bit integer add or subtract instruction (discounting operand fetch and other overhead), and they can sometimes be paired with other instructions for concurrent execution. A 32-bit multiply takes 10 cycles (a divide takes 41 cycles), and neither can be paired.

2.2Shift and Memory Fetch


The algorithms considered in this paper process the bits or digits of their long operands sequentially, so in a single cycle fetching more neighboring digits (words) into fast registers allows the use of slower, cheaper RAM, or pipeline registers.

We will use only add/subtract, compare and shift operations. With trivial hardware enhancements the shift operations can be done “on the fly” when the operands are loaded for additions or subtractions. This kind of parallelism is customarily provided by DSP chips, and it results in a close to two-fold speedup of the shifting xGCD based modular inverse algorithms.



Shift operations could be implemented with manipulating pointers to the bits of a number. At a subsequent addition/subtraction the hardware can provide the parameter with the corresponding offset, so arbitrary long shifts take only a constant number of operations with this offset-load hardware support. (See [16].) Even in traditional computers these pointer manipulating shift operations save time, allowing multiple shift operations to be combined into a longer one.

Directory: Papers
Papers -> From Warfighters to Crimefighters: The Origins of Domestic Police Militarization
Papers -> The Tragedy of Overfishing and Possible Solutions Stephanie Bellotti
Papers -> Prospects for Basic Income in Developing Countries: a comparative Analysis of Welfare Regimes in the South
Papers -> Weather regime transitions and the interannual variability of the North Atlantic Oscillation. Part I: a likely connection
Papers -> Fast Truncated Multiplication for Cryptographic Applications
Papers -> Reflections on the Industrial Revolution in Britain: William Blake and J. M. W. Turner
Papers -> This is the first tpb on this product
Papers -> Basic aspects of hurricanes for technology faculty in the United States
Papers -> Title Software based Remote Attestation: measuring integrity of user applications and kernels Authors

Download 288.56 Kb.

Share with your friends:
1   2   3   4   5   6   7   8   9   10   11




The database is protected by copyright ©ua.originaldll.com 2024
send message

    Main page