3
$\begingroup$

I'm reading the paper “COMPARISON OF SCALABLE MONTGOMERY MODULAR MULTIPLICATION IMPLEMENTATIONS EMBEDDED IN RECONFIGURABLE HARDWARE” (PDF) on hardware algorithms for montgomery multiplication for modular exponentiation, and I'm confused as to how the standard radix-2 montgomery mulitplication algorithm (R2MM), and the multiple-word radix-2 montgomery multiplication algorithm (MWR2MM) differ with regards to the final subtraction of the modulus.

The standard algorithm is as follows:

$\newcommand{\newkeyword}[2]{\newcommand{#1}{\mathrm{#2}}}% \newkeyword{\for}{for}% \newkeyword{\to}{to}% \newkeyword{\loop}{loop}% \newkeyword{\if}{if}% \newkeyword{\then}{then}% \newkeyword{\else}{else}% \newkeyword{\end}{end}% S_0 := 0\\ \for\ i:=0\ \to\ (m-1)\ \loop\\ \ \ \ \ q_i := (S_i + x_iY) \bmod 2\\ \ \ \ \ \if\ (q_i=1)\ \then\\ \ \ \ \ \ \ \ \ S_{i+1} := (S_i + x_iY + M)/2\\ \ \ \ \ \else\\ \ \ \ \ \ \ \ \ S_{i+1} := (S_i + x_iY)/2\\ \ \ \ \ \end\ \if\\ \end\ \for\\ \if\ (S_m \geq M)\ \then\\ \ \ \ \ S_m:=S_m-M\ \ \ \ \ \ \ \ \text{// the final correction step}\\ \end\ \if\\ Z:=S_m\\ $

where:

  • $\\S$ is the result
  • $M$ is the modulus
  • $Y$ is the multiplicand
  • $X$ is the multiplier and $x_i$ is the single bit (e.g. $X =

The MWR2MM_CSA algorithm is as follows

$ S = 0\\ \for\ i=0\ \to\ (m-1)\ \loop\\ \ \ \ \ (C,S^{(0)}) := x_i\cdot Y^{(0)}+S^{(0)}\\ \ \ \ \ \if\ S^{(0)}_{0} = 1\ \then\\ \ \ \ \ \ \ \ \ (C,S^{(0)}) := (C,S^{(0)}) + M^{(0)}\\ \ \ \ \ \ \ \ \ \for\ j = 1\ \to\ e-1\ \loop\\ \ \ \ \ \ \ \ \ \ \ \ \ (C,S^{(j)}) := C+ x_i \cdot Y^{(j)} + M^{(j)} + S^{(j)}\\ \ \ \ \ \ \ \ \ \ \ \ \ S^{(j-1)} := (S_0^{(j)},S^{(j-1)}_{w-1..1}) \\ \ \ \ \ \ \ \ \ \end\ \loop\\ \ \ \ \ \ \ \ \ S^{(e-1)} := (C,S^{(e-1)}_{w-1..1})\\ \ \ \ \ \else\\ \ \ \ \ \ \ \ \ \for\ j := 1\ \to\ e-1\ \loop\\ \ \ \ \ \ \ \ \ \ \ \ \ (C,S^{(j)}) := C+ x_i \cdot Y^{(j)} + S^{(j)}\\ \ \ \ \ \ \ \ \ \ \ \ \ S^{(j-1)} := (S_0^{(j)},S^{(j-1)}_{w-1..1}) \\ \ \ \ \ \ \ \ \ \end\ \loop\\ \ \ \ \ \ \ \ \ S^{(e-1)} := (C,S^{(e-1)}_{w-1..1})\\ \ \ \ \ \end\ \if\\ \end\ \loop\\ $

where:

  • $\\S$ is the result
  • $M$ is the modulus
  • $Y$ is the multiplicand
  • $X$ is the multiplier and $x_i$ is the single bit (e.g. $X = (x_n,...,x_1,x_0)$.
  • The superscript are the words vectors (e.g. $M = (0,M^{e-1},...,M^1,M^0)$
  • $(A,B)$ is the concatenation of two bit vectors.
  • $m$ is the total bit-width of the operands (2048, in my case)
  • $w$ is the width of choosen words
  • $e$ is the number of words of bit-width $w$ required to complete the vectors ($e = \lceil(m+1)/w\rceil$

This result is only guaranteed to be in the range of $0<S<2M$, so there is the possibility of needing a final subtraction

The paper states that, in the standard algorithm,

In typical applications (e.g. RSA, ECC), input operands X , Y are transformed into Montgomery domain by pre-multiplication with a factor $2^{2m}\bmod M$. The final MM with value ($A = \mathit{MM} (A, 1)$ in the exponentiation algorithm) makes the final result smaller than M (without any final correction) and provides the result $XY \bmod M$.

My questions are therefore:

  1. If you don't subtract the modulus from R2MM result, then the results of both R2MM and MWR2MM should be identical, right?
  2. If you premultiply both algorithms' input by $2^{2m} \bmod M$, then the results should still be the same (no final subtraction needed) right?

I ask this because my results do not seem to support this, and I find myself needing to perform subtraction regardless of premultiplication.

$\endgroup$

Your Answer

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

Browse other questions tagged or ask your own question.