52 Things: Number 22: How do you represent a number and multiply numbers in Montgomery arithmetic?

This is the latest in a series of blog posts to address the list of '52 Things Every PhD Student Should Know' to do Cryptography: a set of questions compiled to give PhD candidates a sense of what they should know by the end of their first year. This next blog continues the topic of 'Cryptographic Implementation Details'.

Most of this blog is derived from [1].

Secure and Efficient?

While the goal of cryptography is to design highly secure cryptographic protocols, it must also be possible to implement these protocols efficiently so that they can be performed over and over again without slowing users down too much as they, for example, shop online or transfer money via internet banking. Therefore steps are taken to minimise the computational cost of each and every algorithm used in these protocols. One of the most expensive operations used in such algorithms is the reduction of integers modulo some $n>0$, since it is effectively a division operation.

The Cost of Modular Reductions

From now on we fix the notation that $x \: \mathrm{mod} \: n$ is the remainder after $x$ has been divided by $n$, so it's a particular non-negative integer which is less than $n$ (as opposed to the equivalence class of $x$ in $\mathbb{Z}/n\mathbb{Z}$, etc.)

Let $a,b \in \mathbb{Z}$ and say we know $a \: \mathrm{mod} \: n$ and $b \: \mathrm{mod} \: n$. In many cryptographic applications we wish to compute the product $ab \: \mathrm{mod} \: n$. The naive approach is to compute the usual integer product $ab$ and then reduce this modulo $n$. While this is fine for just one multiplication, we may need to carry out several consecutive multiplications which would lead to several (expensive) modular reductions. For example, in RSA the ciphertext of a message $m$ is $c = m^e \: \mathrm{mod} \: pq$ for some large primes $p,q$ and a public exponent $e$. Computing $c$ according to the naive approach means $e$ iterations of multiplying by $m$ and reducing modulo $pq$. It would be much better to somehow defer the tricky modular reduction to the end of the calculation. But at the same time, if we just compute $m^e$ over the integers and then reduce modulo $n$ at the end, we will have to store (and calculate with) extremely large numbers. So this requires a little more thought.

"Montgomery Space"

The insight, due to Montgomery, is to work over a convenient modulus, typically a power of 2. So to compute $ab \: \mathrm{mod} \: n$:

1. Move $a$ and $b$ into "Montgomery space" (remainders modulo some convenient $r$)
2. Calculate products and perform modular reductions in this nicer space
3. Convert the answer into the desired remainder modulo $n$.

Why is a power of 2 convenient? Say $x$ is an integer written in binary (as is typical for computers) and $r = 2^k$ for some integer $k>0$. Then,

• to compute $x \: \mathrm{mod} \: r$ you just discard all but the rightmost $k$ bits of $x$
• to compute $xr$ you just shift the digits of $x$ by $k$ places to the left
• to compute $x/r$ you just shift the digits of $x$ by $k$ places to the right.

The Algorithm

Let $a, b, n, r$ be positive integers with $\mathrm{gcd}(n,r)=1$ and $r > n$. We compute $ab \: \mathrm{mod} \: n$ as follows:

1. Use the extended Euclidean algorithm to find integers $r^{-1},n'$ with $rr^{-1} = 1 + nn'$
2. Compute $\overline{a} = ar \: \mathrm{mod} \: n$ and $\overline{b} = br \: \mathrm{mod} \: n$
3. Compute $ u = abr \: \mathrm{mod} \: n$ via:
1. $t \leftarrow \overline{a}\overline{b}$
2. $u \leftarrow \left ( t + \left ( n't \: \mathrm{mod} \: r \right ) \: n \right ) / r$
3. If $u \geq n$ then $u \leftarrow (u - n)$
4. Output $u$
4. Multiply $u$ by $r^{-1}$ and reduce modulo $n$.

Some remarks on speed:

• Step 1 is always possible since $r$ is coprime to $n$, and can be done very quickly when $r$ is a power of 2 and $m$ is odd.
• In Step 2, while the integer multiplication (e.g. $a \times r$) is quick (especially if $r = 2^k$), there is an expensive modular reduction for each multiplier $a$ and $b$. There is also an expensive reduction in Step 4. So for just one multiplication this algorithm is probably slower than the naive approach. But calculating many products modulo $n$ of a small number of multipliers (e.g. $a^mb^{m'}$ modulo $n$ for some integers $m,m'$) is much better this way since we can reuse the outputs of Steps 2 and 3 in subsequent multiplications.
• Step 3 involves three integer multiplications, one integer addition and, if $r=2^k$, discarding all but $k$ bits and a shift $k$ places to the right. All these processes are efficient.

Proof of Correctness 
It should be clear that the algorithm does output $ab \: \mathrm{mod} \: n$ provided that $ u = abr \: \mathrm{mod} \: n$ as is claimed in Step 3. To prove this claim, let $t = \overline{a}\overline{b}$ so that
$u = abr \: \mathrm{mod} \: n$
$= arbrr^{-1} \: \mathrm{mod} \: n$
$= tr^{-1} \: \mathrm{mod} \: n$
$ = trr^{-1}/r \: \mathrm{mod} \: n$
$ = t(1 + nn')/r \: \mathrm{mod} \: n $
$ =((t + nn't)/r + mn) \: \mathrm{mod} \: n = (t + (n't + mr)n)/r \: \mathrm{mod} \: n$, for any integer $m$.
In particular, when $m$ is chosen so that $n't + mr = n't \: \mathrm{mod} \: r$, we find
$ u = abr \: \mathrm{mod} \: n = (t + (n't \: \mathrm{mod} \: r)n)/r \: \mathrm{mod} \: n. $

Note that the quantity computed in the algorithm is like the above but without the reduction modulo $n$. This is because, since $n > r > 0$, we have
$n^2 < rn \Rightarrow n^2 + rn < 2rn \Rightarrow \left( n^2 + rn \right) / r < 2n$ which shows that $(t + (n't \: \mathrm{mod} \: r)n)/r < 2n$ since $t$ is the product of two remainders modulo $n$. So instead of reducing $(t + (n't \: \mathrm{mod} \: r)n)/r$ modulo $n$ we can just compare it against $n$ (which is an efficient operation) and subtract $n$ once if necessary (also quick). Thus the algorithm given is correct.

References
[1] - http://www.hackersdelight.org/MontgomeryMultiplication.pdf