1
$\begingroup$

I am looking for methods to avoid the final subtraction in Montgomery multiplication. I found this paper "A Cryptographic Library for the Motorola DSP56000 " (http://goo.gl/DHePEx) In this paper they have said that we can avoid final subtraction if we keep N(modulus)

$\endgroup$
  • $\begingroup$ Did you check Gaël Hachez and Jean-Jacques Quisquater, Montgomery Exponentiation with no Final Subtractions: Improved Results. In Cryptographic Hardware and Embedded Systems - CHES 2000, LNCS 1965, pp. 293-301, Springer, 2000. dx.doi.org/10.1007/3-540-44499-8_23 $\endgroup$ – user94293 May 25 '16 at 14:55
1
$\begingroup$

The above mentioned work is focused on a hardware implementation (I have this work as a PDF). I'd suggest you to search for:

  1. Colin D. Walter. Montgomery Exponentiation Needs no Final Subtractions. Electronics Letters, 35(21):1831{1832, October 1999.
  2. Colin D. Walter. Montgomery's Multiplication Technique: How to Make It Smaller and Faster. In C etin K. Koc and Christof Paar, editors, Cryptographic Hardware and Embedded Systems - CHES '99, volume 1717 of LNCS, pages 80{93. Springer- Verlag, August 1999.

Those I don't have and never tried to find.


Montgomery Exponentiation with no Final Subtractions: Improved Results Gael Hachez and Jean-Jacques Quisquater

Abstract. The Montgomery multiplication is commonly used as the core algorithm for cryptosystems based on modular arithmetic. With the advent of new classes of attacks (timing attacks, power attacks), the implementation of the algorithm should be carefully studied to thwart those attacks. Recently, Colin D. Walter proposed a constant time implementation of this algorithm [17, 18]. In this paper, we propose an improved (faster ) version of this implementation. We also provide gures about the overhead of these versions relatively to a speed optimised version (theoretically and experimentally).

|improve this answer|||||
$\endgroup$
  • $\begingroup$ Actually, googling for "Colin D. Walter. Montgomery Exponentiation Needs no Final Subtractions" soon gives you the PDF: Conclusion We have considered implementations of the RSA cryptosystem which use solely Montgomery’s modular multiplication algorithm and shown that under standard, easily met, inexpensive conditions, the total encryption process never needs any extra subtractions to produce output in the correct range. $\endgroup$ – tum_ May 27 '16 at 14:29
1
$\begingroup$

Brett just asked & answered this question : Confused about final subtraction of modulus in Montgomery Multiplication, during modular exponentiation

You should increase $R$ exponent by $2$. If you use $n=1024$ , increase it to be $$n=1024 + 2 = 1026.$$ Recalculate the pre-compute $R'$, based on the new exponent. $$R' = 2^{(2\cdot 1026)} \bmod(M).$$

|improve this answer|||||
$\endgroup$
  • $\begingroup$ We have $LaTeX$/MathJax enabled in this site. Please check my edits. $\endgroup$ – kelalaka Apr 4 '19 at 9:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.