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)
1
-
$\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$– user94293Commented May 25, 2016 at 14:55
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
1
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).$$
-
$\begingroup$ We have $LaTeX$/MathJax enabled in this site. Please check my edits. $\endgroup$– kelalakaCommented Apr 4, 2019 at 9:30
$\begingroup$
$\endgroup$
1
The above mentioned work is focused on a hardware implementation (I have this work as a PDF). I'd suggest you to search for:
- Colin D. Walter. Montgomery Exponentiation Needs no Final Subtractions. Electronics Letters, 35(21):1831{1832, October 1999.
- 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).
-
$\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_Commented May 27, 2016 at 14:29