Modular Inverse Algorithms without Multiplications for Cryptographic Applications


Performance Relative to Digit-serial Modular Multiplication



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

4.3Performance Relative to Digit-serial Modular Multiplication


Of course, the speed ratio of the modular inverse algorithms relative to the speed of the modular multiplications depends on the computational platform and the employed multiplication algorithm. We consider quadratic time modular multiplications, like Barrett, Montgomery or school multiplication with division based modular reduction (see [10]). With operand lengths in cryptography sub-quadratic time modular multiplications (like Karatsuba) are only slightly faster, more often they are even slower than the simpler quadratic time algorithms (see [9]).

If there is a hardware multiplier, which computes products of d-bit digits in c clock cycles a modular multiplication takes T = 2(n/d)2 + O(n) time alone for computing the digit products [16]. In DSP-like architectures (load, shift and add instructions performed parallel to multiplications) the time complexity is 2(n/d)2. Typical values are



  • d = 16, c = 4: T = n2/32 ≈ 0.031n2

  • d = 32, c = 12: T = 3n2/128 ≈ 0.023n2.

The fastest of the presented modular inverse algorithm on parallel shift-add architecture takes 0.666 n2 bit operations, which needs to be divided by the digit size (processing d bits together in one addition). For the above two cases we get 0.042n2 and 0.021n2 running times, respectively. These values are very close to the running time of one modular multiplication.

The situation is less favorable if there are no parallel instructions. The time a multiplication takes is dominated by computing the digit products. Additions and register manipulations are faster. On these platforms computing the modular inverse takes almost twice as much time than with parallel add and shift instructions. Consequently, computing the modular inverse without parallel instructions takes about twice as much time as a modular multiplication. Still, in case of elliptic curve cryptography the most straightforward (affine) point representation and direct implementation of the point addition is the best (computation with the projective, Jacobian and Chudnovsky-Jacobian coordinates are slower, see [11]).

It is interesting to note, that modular division (p∙q−1) can be performed faster than 3 modular multiplications. Similar results were presented in [22] and [23] for polynomials of practical lengths, showing that even in extension fields GF(pk), elliptic curve points are best represented in affine coordinates.

4.4Performance Relative to Parallel Adder-based Modular Multiplication


When very long adders are implemented in hardware, repeated shift-add steps can perform multiplications in linear time. To prevent the partial results from growing too large, interleaved modular reduction is performed. Scanning the bits of the second multiplicand from left to right, when a 1-bit is found, the first multiplicand is added in the appropriate position to the partial result r. If it gets too long: ||r|| > ||m||, it is reduced by subtracting the modulus m. These add-subtract steps are usually done in the same clock cycle, resulting in performing an n-bit modular multiplication in n clock cycles.

In these kinds of hardware architectures the speed of the different modular inverse algorithms becomes very close, because there is no advantage of having additions on diminishing length operands. An average iteration reduces the length of the longer operand by about 1.4 bits, so the left- and right shift algorithms don't differ much, in how many shift steps can be combined into one longer shift. The plus-minus right shift algorithm has the smallest number of iterations, its delayed halving variant can combine the largest number of shifts, so its running time becomes very close to that of the shifting Euclidean algorithm.

In each iteration the RSDH+− modular inverse algorithm needs to shift one of U or V, and double R or S the same many times, which give about the same amount of work as the modular multiplication performs, maybe even less. At the end we need to add-halve R, which makes the modular inverse slightly slower than one modular multiplication, but still faster than two.

4.5Testing Relative Primality


We can simplify all of our shifting modular inverse algorithms if we only want to know whether the two arguments x, y are relative primes: leaving out all the calculations with R and S. In this case all the plus-minus right shift algorithms become the same, so the simplest one, RS+− is the best, with 0.3065 n2 cost of bit-shifts and the same for subtractions. All together it is 0.6130 n2. SE3 is still slightly better, with a running time of 0.6088 n2. The modified left-shift algorithm LS3 takes 0.3967 n2 clock cycles for the shift operations, and 0.3331 n2 clock cycles for the subtract operations, which is only 9…19% more. When, in an application, not only relative primality has to be tested, but modular inverses have to be calculated as well, this little speed advantage might not justify the implementation of 2 different algorithms, so LS3 or SE3 should be used for both purposes (without computing R and S if not needed).

5.Further Optimizations Possibilities


There are countless possibilities to speed up the presented algorithms a little further. For example, when U and V become small (short), a table lookup could immediately finish the calculations. If only one of them becomes small, or there is a large difference of the lengths of U and V, we could perform a different algorithmic step, which is best tuned to this case on the particular computing platform. (Most of the time it is a traditional Euclidean reduction step.) We tried hundreds of ideas like these, but the little acceleration did not justify the increased complexity.

Some of the presented speedup methods could have been applied already somewhere in the huge literature of algorithmic optimization, but we could not find the wining combinations of these optimization techniques for the modular inverse problem published anywhere. Many modifications accelerate one part of the algorithm while they slow down – or even invalidate – other parts. We investigated hundreds of algorithmic changes, but only discussed here the original algorithms and those optimizations, which led to the largest speedups.



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