Modular Inverse Algorithms without Multiplications for Cryptographic Applications



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

5.1Working on the Ends


On some computational platforms speed increase can be achieved with delayed full update of the variables. See, for example [4], [5] or [7]. It means working with MS and/or LS digits only, as long as we can determine the necessary reduction steps, and fix the rest of the digits only when more precision is needed. Speedup is achieved by the reduced number of data fetch-, and combined update operations on the middle digits. Unfortunately, the resulting algorithms are much more complex, less suitable for direct hardware implementations and the combined operations involve multiplications, what we wanted to avoid. In our computational model data load-store operations are free, so having fewer of them doesn’t provide any speed advantage.

5.2Hybrid Algorithms


The right shift- and the shifting Euclidean algorithms operate on the opposite ends of the numbers. At least when the modulus is odd, the reduction steps could be intermixed: check on a few bits on the appropriate end of the intermediate values which algorithm is expected to reduce the lengths the most, and perform one step of it. However, the right shift algorithms are so much slower, that the corresponding reduction is almost never expected to be faster than the shifting Euclidean reduction. This way we could not achieve any significant speedup, but the algorithms became complicated and convoluted.

5.3Modular Division


If the initialization of S ← 1 is replaced by S ← d, we get da−1 as the result, as described in [22] for polynomials. In case the modular inverse is only needed once, and it is multiplied by another number, we could save that multiplication, like in elliptic curve cryptography. If the inverse is reused many times, like at signed digit exponentiation ([15]), this trick does not improve performance.

We start with a full length S (=d) instead of length 1, so (S,R) do not gradually increase from length 1, but start at length n. Further steps are necessary to prevent them to grow too large. These more than double the total work updating (S,R) (but not (U,V)) at the left-shift and shifting Euclidean algorithms, all together 50…100% increase. The right shift algorithms do not change much, so modular divisions significantly reduce their performance lag. In general, it only pays doing divisions this way, when the underlying modular inverse algorithm is much faster than two modular multiplications (making a modular division faster than 3 modular multiplications).


6.References


  1. D. E. Knuth, “The Art of Computer Programming”, volume 2, “Seminumerical Algorithms”, 3rd edition, Addison-Wesley, 1998.
    http://www-cs-faculty.stanford.edu/~knuth/taocp.html

  2. D.R. Hankerson, A.J. Menezes, S.A. Vanstone, “Guide to Elliptic Curve Cryptography”, Springer, 2004.

  3. T. Jebelean, “A Generalization of the Binary GCD Algorithm”, ISSAC 93, pp. 111-116. Technical report version available
    ftp://ftp.risc.uni-linz.ac.at/pub/techreports/1993/93-01.ps.gz

  4. T. Jebelean, “A Double-Digit Lehmer-Euclid Algorithm for Finding the GCD of Long Integers”, Journal of Symbolic Computation, volume 19, 1995, pp. 145-157. Technical report version also available ftp://ftp.risc.uni-linz.ac.at/pub/techreports/1992/92-69.ps.gz

  5. T. Jebelean, “Comparing several GCD algorithms” In ARITH-11: IEEE Symposium on Computer Arithmetic (Windsor, Canada, June). IEEE, New York, 180-185.

  6. R. P. Brent and H. T. Kung, “Systolic VLSI arrays for linear-time GCD computation”, in V. Anceau, E.J. Aas (eds.), VLSI’83. 1983 Elsevier (North Holland), pp 145-154.

  7. K. Weber, “The accelerated integer GCD algorithm”, ACM Transactions on Mathematical Software, volume 21, number 1, March 1995, pp. 111-122.

  8. A. Schönhage, V. Strassen, “Schnelle Multiplikation großer Zahlen”, Computing 7, 1971, pp. 281-292.

  9. GNU Multiple Precision Arithmetic Library manual
    http://www.swox.com/gmp/gmp-man-4.1.2.pdf

  10. A. Menezes, P. van Oorschot, and S. Vanstone, “Handbook of Applied Cryptography”, CRC Press, 1996.

  11. H. Cohen, A. Miyaji, and T. Ono, “Efficient elliptic curve exponentiation using mixed coordinates”. In K. Ohta and D. Pei, editors, Advances in Cryptology - ASIACRYPT 98, Lecture Notes in Computer Science, No. 1514, pages 51-65. Springer, Berlin, Germany, 1998. http://citeseer.ist.psu.edu/article/cohen98efficient.html

  12. R. Lórencz, “New Algorithm for Classical Modular Inverse”, CHES 2002, LNCS 2523, pp 57-70. Springer-Verlag, 2003.

  13. M. D. Ergovac, T. Lang, “Digital Arithmetic” Chapter 2. Morgan Kaufmann Publishers, 2004.

  14. B. Vallée, “Complete Analysis of the Binary GCD” 1998. http://citeseer.ist.psu.edu/79809.html

  15. J. Jedwab and C. J. Mitchell. “Minimum weight modified signed-digit representations and fast exponentiation”. Electronics Letters, 25(17):1171-1172, 17. August 1989.

  16. L. Hars, “Long Modular Multiplication for Cryptographic Applications”. http://eprint.iacr.org/2004/198/ CHES 2004, (LNCS 3156, pp 44-61. Springer-Verlag, 2004.)

  17. L. Hars, “Fast Truncated Multiplication and its Applications in Cryptography”, (CHES 2005), Edinburgh.

  18. E. Savaş, Ç. K. Koç: “The Montgomery Modular Inverse – Revisited”, IEEE Transactions on Computers, 49(7), pp. 763-766, July 2000

  19. B.S. Kaliski Jr. “The Montgomery inverse and its applications”, IEEE Transactions on Computers, 44(8) pp. 1064–1065, August 1995.

  20. P.L. Montgomery. “Modular multiplication without trial division”, Mathematics of Computation, 44(170) pp. 519–521, April 1985.

  21. M. Joye and P. Paillier, “GCD-free Algorithms for Computing Modular Inverses”. Cryptographic Hardware and Embedded Systems - CHES 2003, Springer-Verlag, 2003, LNCS 2779, pp. 243–253.

  22. S. C. Shantz. “From Euclid's GCD to Montgomery Multiplication to the Great Divide”. Technical Report TR-2001-95, Sun Microsystems Laboratories, 2001.

  23. R. Schroeppel, H. Orman, and S. O’Malley, "Fast Key Exchange with Elliptic Curve Systems," Tech. Report 95−03, Department of Computer Science, The University of Arizona, Tucson.

  24. J. Stein, "Computational problems associated with Racah algebra", Journal of Computational Physics, 1, 1967.

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