Leakage from Montgomery Multiplication
Colin D. Walter
Comodo CA Ltd, Bradford, Yorks BD7 1HR, UK.

Colin.Walter@comodo.com

1 Introduction
Modular multiplication P = A×B mod M is a fundamental operation in mostpublic key cryptography. Its efficiency is usually critical in determining theoverall efficiency of a system because it is the main component in modular
exponentiation and in elliptic curve point multiplication. There are several
algorithms which can be chosen for performing modular multiplication, of
which those by Barrett [1], Montgomery [6] and Quisquater [2] are the mostwidely known. Most optimisations which can be applied to one modular multiplication algorithm can also be applied to the others, so that all have thesame overall complexity [9]. However, Montgomery’s method is rather morestraight-forward to implement; generally less work is involved in achieving the
optimisations.
This chapter delves into certain aspects of Montgomery’s algorithm: itseeks to retain the advantages of simple and efficient code while at the sametime addressing the issue of side channel leakage from the final conditional
subtraction. We study the main loop and the final conditional subtraction
separately in order to determine a fully precise specification for the output andhence determine how much data is leaked through the conditional subtraction
side channel. This enables us to fix the leakage very satisfactorily.

2 Montgomery Reduction
Modular multiplication is really a combination of two processes: multiplicationand modular reduction. These are generally interleaved for space efficiency
reasons: this keeps the intermediate values within a very small multiple ofthe modulus. This is also called the integrated approach. With the separated
technique, the multiplication is performed completely beforehand, allowing
more time-efficient methods to be employed. This is then followed by modular
reduction of the product. We start by looking at this process of reduction.

2

Colin D. Walter

Definition 1. Suppose positive integers M and R have no common factor.
Then,i) A0 is called the Montgomery reduction of A modulo M with respect to R
if A0 ≡ AR−1 mod M and AR−1 ≤ A0 < AR−1 +M .
ii) Conversely, A is called a Montgomery representation or Montgomery
residue of A with respect to R if it satisfies A ≡ AR mod M . When
R is clear, A is called an M -residue.
Note that this definition contains two different inverses of R: one is the residue
modulo M which is the modular inverse of R in Z/M Z, the other is the rational
number which is the fractional inverse of R in Q. The context, indicated by
the presence or absence of “modM ”, makes the intended choice clear.
Co-primality of M and R guarantees that there is a one-to-one correspondence between a complete set of residues mod M and the set ofresidues {R0 .R mod M | 0 ≤ R0 < M }. So there is a value R0 such that
R0 .R ≡ 1 mod M , i.e. R has an inverse mod M . So the Montgomery reduction exists when M and R have no common factor, and the bounds ensurethat it is unique. For cryptographic applications the co-primeness property
usually holds: R is generally a power of 2 so that division by R is easily performed by shifting, whereas M is a product of some large primes, and hence
odd.
The Montgomery reduction A0 of A mod M can be obtained by finding
integers A0 and Q satisfying
A0 R − QM = A
and such that Q is in the interval [0..R[. When R has the form R = rn , thesolution can be generated using the same process as in Hensel’s Lemma, whichsolves the equation iteratively modulo higher and higher powers of r.
When A and M have representations over base (or radix) r with digits
ai and mi respectively, the Henselian process for obtaining the Montgomery
reduction A0 with respect to R = rn is given in Fig. 1. There, m0 −1 is theinverse of m0 modulo r. Usually the digits occupy words of memory, so thatr = 2k where k is the number of bits per word. Then the division by r in thelast line of that figure is simply a shift by one position of an array of words.
The choice of digit qi in the loop guarantees that the divisionPn−1 by r is exact.
Thus, if the digits qi are formed into the “quotient” Q = i=0 qi ri then the
output satisfies A0 = (A+QM )r−n where Q < rn = R, as required. The
bounds on A0 now follow, showing it is the Montgomery reduction of input A.
The term Ar−n becomes smaller as n is increased. Hence, by choosing nsuch that A < M rn the output satisfies A0 < 2M and an extra conditional
subtraction of M will yield the least non-negative residue of AR−1 mod M .
For example, if the input A were obtained as a product of two reduced residues
modulo M (i.e. least non-negative) then A < M 2 and we would just need nsuch that M < rn in order to achieve an output which is also fully reducedby the extra conditional subtraction.

3
Function MonRed(A, M, r, n): A0
Pre-condition: M and r are co-prime.
Post-condition: A0 ≡ Ar−n mod M with Ar−n ≤ A0 < Ar−n +M .
A0 ← AFor i ← 0 to n-1 do
qi ← -a00 m0 −1 mod r
A0 ← (A0 +qi M) div r
Return A0
Fig. 1. Montgomery Modular Reduction.

Unlike classical modular reduction, the choice of quotient digit qi does notdepend on the most significant digit of A0 but on its least significant. Thismeans that qi can be determined precisely without waiting for carry propagation to be completed in the previous loop iteration. This is advantageous
for application in a systolic array where the processing elements perform digit
level computations [10].

3 Montgomery Modular Multiplication
Instead of pre-computing the product A×B, the Montgomery reduction of
A×B modulo M can be obtained by interleaving the multiplication and the
reduction, as in Fig. 2. We need one of the inputs, say B, to have a representation to base r with at most n digits.
Function MonPro(A, B, M, r, n): C
Pn−1
Pre-condition: M and r are co-prime, B = i=0
bi r i < r n .
−nPost-condition: C ≡ ABr
mod M and ABr−n ≤ C < M +ABr−n .
C ← 0
For i ← 0 to n-1 do
qi ← -(c0 +a0 bi )m0 −1 mod r
C ← (C+bi A+qi M) div r
Return C
Fig. 2. Montgomery Modular Multiplication without Conditional Subtraction.

It is easy to verify the code of Fig. 2 from its similarity to MonRed and byobserving that the non-modular operations compute A×B with a shift equivalent to a factor of r−n . In fact, taking B = 1 yields the MonRed algorithm.
As in the MonRed algorithm, there is no upper bound on the value of input
A. Moreover, the bound on B is in terms of n and not M . Thus there is noneed to ensure the inputs are least non-negative residues modulo M .
Since the output of the ith iteration is exactly analogous to the outputof the nth, for which B < rn , we know that the partial product C is less

4

Colin D. Walterthan M +A throughout the calculation. This gives a bound on how large theregister for C needs to be. For most applications M < rn and A < rn so that
C requires one more bit than rn . A further extra word may also be needed forintermediate results before the shift down corresponding to the division by r.
A detailed time and space efficiency analysis of different methods to computethe update to the partial product C is given by Koç, Acar and Kaliski [3].
Pn−1
Setting Q = i=0 qi ri gives C = (AB+QM )r−n and so Q ≈ ABr−n /M
when C is bounded by a small multiple of M . To be precise, if C−δM is thesmallest non-negative residue, then Q+δ = bABr−n /M c yields the integer
quotient. So further conditional subtractions of M from C to obtain the least
non-negative residue can be combined with incrementing Q to yield the integer
quotient.
The normal presentation of the algorithm includes a final conditional subtraction of M to yield an output less than M . It is omitted in this first version of Montgomery multiplication for three reasons: it is unnecessary when
MonPro is used for exponentiation, it is a strong source of side channel leakage and, for non-fully reduced inputs, more than one subtraction of M may
be necessary. However, there are two useful versions of Montgomery multiplication which include a final conditional subtraction. They are given in Figs.
3 and 4.
Function MonPro(M ) (A, B, M, r, n): C
Pre-condition: M and r are co-prime, A < M , B < rn .
Post-condition: C ≡ ABr−n mod M and C < M .
C ← MonPro(A,B,M,r,n)
if C ≥ M then C ← C-M
Fig. 3. Montgomery Modular Multiplication with Bound M .

Function MonPro(R) (A, B, M, r, n): C
Pre-condition: M and r co-prime, A<R, B<R, M <R for R = rn .
Post-condition: C ≡ ABr−n mod M and C < R.
C ← MonPro(A,B,M,r,n)
if C ≥ R then C ← C-M
Fig. 4. Montgomery Modular Multiplication with Bound R.

It is easy to check that the input bounds imply the output bounds inboth cases. Moreover, the bounds are such that outputs can be used as inputs to another execution of the same algorithm. This is very convenient for
applications involving exponentiation. The second version, with bound R, ismarginally more efficient than the first for two reasons. First, this is because
the comparison is easier to implement: typically it just requires looking at

5

an overflow bit rather than performing a potentially full length subtraction.
Secondly, the frequency of the subtractions is usually lower for the second
version.

4 Exponentiation
All exponentiation algorithms consist of a sequence of products. Therefore, inorder to use MonPro for modular exponentiation, it suffices to adjust for the
extra power of R and to check that the output from one use of MonPro satisfies
the bounds on the input required for its use in any subsequent MonPro. If
Z = X×Y mod M
is one of the modular multiplications during the exponentiation when normal
modular products are computed, then the usual choice for the corresponding
multiplication using MonPro is
Z = MonPro(X, Y , M, r, n)which operates on the corresponding M -residues. Comparing powers of R,
we find MonPro(X, Y , M, r, n) ≡ X×Y ×R−1 ≡ XR×Y R×R−1 ≡ X×Y ×R≡ Z×R ≡ Z mod M . Thus, the entire exponentiation is done correctly with
MonPro on the corresponding M -residues if the input is adjusted to an M residue and the output is re-adjusted back from an M -residue. An example ofthis is given in Fig. 5 for the square-and-multiply method of exponentiation1 .
Function MonExp(R) (T, N, M, r, n, R(2) ) : S
Pre-conditions: M and r co-prime, T <M <R for R = rn , R(2) < R,
R(2) ≡ R2 mod M , and N =(nk−1 ...n2 n1 n0 )2 with nk−1 =1.
Post-condition: S = T N mod M and 0 ≤ S < M .
T = MonPro(R) (T,R(2) ,M,r,n)S←T
For i ← k-2 downto 0 do
S ← MonPro(R) (S,S,M,r,n)
If ni =1 then S ← MonPro(R) ( S,T,M,r,n)S ← MonPro(R) (S,1,M,r,n)Fig. 5. Square-and-Multiply Exponentiation with MonPro(R) .

To ensure the correct power of R in all operands, the evaluation of S =T N mod M requires a pre-processing step to convert T to its M -residue:
1

Strictly speaking, M must be square-free to avoid the possibility of output S = M ,which is forbidden in the post-condition of the code. The output bound is treatedlater in this section.

6

Colin D. Walter

T = MonPro(T, R2 mod M, M, r, n)
and the post-processing step to convert back from an M -residue:
S = MonPro(S, 1, M, r, n).
It is easy to see that the first of these introduces a factor of R, while thesecond removes such a factor. Corresponding similar pre- and post- processing
steps also correctly introduce and eliminate a factor of R when MonPro(M ) or
MonPro(R) is used throughout the exponentiation instead of MonPro – simply
replace MonPro by MonPro(M ) or MonPro(R) as appropriate.
For the large exponents N typical of public key cryptography, these two
extra modular multiplications have a negligible cost when compared with theadvantages of a simpler multiplication algorithm. However, R(2) ≡ R2 mod M
also needs to be pre-computed and stored. Since M is usually fixed for many
exponentiations, the time penalty for this can normally be amortized over the
lifetime of the modulus.
The other main requirement for using Montgomery modular multiplicationin exponentiation is that the output from one multiplication satisfies the preconditions for inputs to the subsequent multiplications. This is plainly thecase if MonPro(R) is used throughout: inputs and outputs are both boundedby R. To use MonPro(M ) throughout, the condition M < R must be added inorder to guarantee that the “B” input is small enough. Then all inputs andoutputs are bounded by M .
Now suppose MonPro is used in the exponentiation algorithm. In orderto achieve a common bound, say B, on all inputs and outputs of MonPro,
it is necessary that M +B 2 R−1 ≤ B. This just requires that the quadratic
B 2 R−1 −B+M has real roots, i.e. 4M < R. This is achieved by choosing alarge enough value for R, that is, a sufficiently large n where R = rn . Thenany bound B can be chosen as long as it is between the two roots. This isreadily seen to be the case for bounds such as B = 2M or B = 12 R, or even aweighted average B = 2λM + 1−λ
2 R where 0 ≤ λ ≤ 1 [13].
For all three modular multiplication algorithms, the above bounds are
sensible conditions on cryptographic inputs T to an exponentiation. Withbound B = M or B = R for MonPro(B) , the initial conditions T < B andR(2) < R ensure that T < B, making T suitable for subsequent use in the
exponentiation. Thereafter, every input to MonPro(B) is bounded above by
B, so that its output is also bound by B. For MonPro, the initial conditions
T < M and R(2) < R ensure that T < B for the acceptable bound B = 2M .
Thus, the pre-processing input R(2) need not be fully reduced in any of threecases; R is an adequate bound for it in each case.
For MonPro(B) with bound B = M or R, and for MonPro with boundB = 2M or 12 R, the loop of the post-processing modular multiplication by
1 generates output S satisfying S < M +BR−1 < M +1. Hence, for none of
the three algorithms does a final subtraction take place, nor is it necessary toobtain a fully reduced output, except possibly when S = M occurs.

7

However, a loop output of S = M is almost impossible. For MonPro(M ) ,this is irreconcilable with the obvious properties 0 < S < M and S ≡0 mod M . When M is square-free, S ≡ 0 mod M implies T ≡ 0 mod M .
In this case, a pre-condition of 0 ≤ T < M forces T = 0. Then the output of
every modular multiplication is 0, ensuring that S = 0, so that S = M does
not occur. So exponentiation with MonPro never uses even a single subtraction to achieve a fully reduced output. Otherwise, with MonPro(R) or MonProin the non-square-free case, a single subtraction may be required to obtain afully reduced output [11]2 .

5 Space and Time Comparisons
In this section, the time and space requirements of exponentiation methods
using the three modular multiplication algorithms are compared: the standard
MonPro(B) with conditional subtraction and bound B = M or R, and MonProwith no subtraction and bound B = 2M or 21 R.
The radix of the number representations here is r = 2k where k is thenative bit length of words in the processor which performs the modular multiplication. Typical word lengths are small powers of 2, such as 8-, 16-, 32and 64-bit. Standard key lengths for RSA normally coincide with multiples ofthese, such as 1024, 1536 and 2048. The same is true for many of the standard prime fields Fp used in elliptic curve cryptography [8]. Consequently, toachieve the property M < R required for MonPro(B) with minimal cost, theproperty R < 2M frequently holds as well, that is, R is the smallest powerof 2 greater than M . So, discarding the final subtraction and using MonProfor exponentiation instead of MonPro(B) comes at an initial cost of increasing
the number of iterations n, probably by just 1, to ensure 4M < R = rn .
So, with standard key and word lengths and the minimal choice for n, theregister containing C in MonPro(B) needs to have one more bit or one more
word than M because loop output values can be up to M +B in magnitude
where B = M or R. Increasing n by 1 to make 4M < R with an input boundof B = 2M or 12 R generates intermediate values also less than M +B, but
this is still below R. So MonPro exponentiation needs no extra words for theintermediate calculations. Indeed, it requires only two more bits for C thanfor M . So the loops in the modular multiplications of MonPro and MonPro(B)exponentiations have the same computational space requirements in a fully
word-based implementation, and MonPro uses only one more register bit when
the top word is reduced to contain only the bit positions that are needed.
Because both manipulate the same number of words, there is also unlikely to be any time difference between single loop iterations in MonPro and
MonPro(B) . The topmost incomplete word or equivalent individual bits cannot be processed any faster than full words because the clock speed is set tothat of the slowest word operation.
2

see Exercise 2 for the non-square-free case.

8

Colin D. Walter

So the main time and space differences will be between the final conditional
subtraction when MonPro(B) is used for exponentiation and the extra loop iteration when MonPro is used. A leak-resistant implementation of MonPro(B)exponentiation will always perform the subtraction, but needs an extra register to hold the pre-subtraction value of C (the “minuend”) as well as its
post-subtraction value. On the other hand, being more complex than a subtraction, the extra iteration of MonPro may require more time. Taking into
account their relative complexity, the loop iteration is most likely to take thesame time as a subtraction or double that time since the clock frequency willprobably be chosen to make word-level multiply-accumulate and subtraction
operations take the same time. At a theoretical level, the subtraction itself
might be equivalent to about half an extra loop iteration, and selecting theresult of the subtraction or its minuend equivalent to another half of a loop
iteration. This would make MonPro and MonPro(B) take essentially the sametime.
The subtractor itself may require significant extra dedicated hardware andassociated data manipulation require extra time. Moreover, code size will be
increased by having to incorporate instructions for the subtraction. As observed in §4, MonPro exponentiation requires no final subtraction, so that theextra hardware and code may not be necessary, although it is likely that othercryptographic operations on the chip will require them.
Although the precise cost will be implementation specific, this discussion indicates that using MonPro(B) with its conditional subtraction will be
more expensive in hardware than using MonPro for exponentiation, and thetime requirements are essentially identical. In conclusion, exponentiation using MonPro with 4M < R and no final subtraction is a cost effective andstraight-forward solution to the problem of side channel leakage from conditional subtractions.

6 Side Channel Analysis
A substantial embarrassment to many smart card manufacturers in the ’90s
was the public discovery that naı̈ve implementations of Montgomery’s algorithm can cause substantial side channel leakage, enabling private keys to be
recovered from fewer than a hundred uses of the key [4, 12]. The main problem
arises from the conditional subtraction in MonPro(M ) and MonPro(R) which,because of the length of keys, takes a large number of clock cycles to complete.
It is therefore very evident in any EMR or power trace.
Nowadays there are many effective counter-measures to prevent such leakage, not least of which is using MonPro for exponentiation rather than
MonPro(M ) or MonPro(R) . Another counter-measure is to modify MonPro(M )and MonPro(R) slightly so that the subtraction is always performed. Thenthe original loop output value C is kept, and the new or old value is selected9according to the sign of the new value. In this way the leakage is considerably reduced. Other counter-measures are discussed in other chapters; here
we limit ourselves to measuring the leakage from MonPro(M ) and MonPro(R)and varying the parameter R in order to minimise it.
Assume that an implementation of exponentiation using a public modulus and private exponent is under attack, and that all conditional subtraction
events can be observed clearly through a side channel. First, we make the simple observation that when the conditional subtraction occurs in one modular
multiplication but not in another, then the multiplications must involve different arguments. Suppose an attacker can choose the input to an exponentiation
with the secret key on the target device and he can observe individual conditional subtractions. With knowledge of the public modulus and exponentiation
algorithm, he can also write a software simulation of the exponentiation which
will generate the same sequence of conditional subtractions when it has thesame input and uses a correct guess at the secret key. He then guesses the bitsof the key in the order that they are consumed by the algorithm. Whenever
there is a difference between the conditional subtractions in the side channel
leakage and his simulation, he knows the operands at that point differ between
the two exponentiations. So he has guessed incorrectly and he backtracks tochange his most recent guesses; several previous bits may need to be adjusted.
Providing the subtractions occur with probability not too close to 0 or 1, he
has a good chance of recovering the whole of the private key in this way3 .
Such an attack uses leakage from a single exponentiation and can be applied
to both RSA and ECC, as well as other exponentiation-based protocols. The
obvious counter-measure is to blind the input text T before exponentiating.
Secondly, in elliptic curve cryptography, the classical formulae for point addition and point doubling are so different that it is easy to distinguish themin side channel traces. Then, with an algorithm such as square-and-multiply,
it becomes trivial to read the pattern of adds and doubles and deduce thesecret key. One counter-measure is to use “unified” formulae for both doubling and adding, so that the same sequence of field operations is performed
in both cases. Unfortunately, for a point doubling some pairs of these operations have identical arguments, whereas they are different for point additions.
When MonPro(M ) or MonPro(R) is used to implement the associated modular arithmetic, a difference in the behaviour of the conditional subtractions
indicates a point addition unequivocally, whereas identical behaviour makes apoint doubling more likely to be the case. With the shorter keys which occur
in ECC, the attacker is left with a small search space of possible keys which it
is often computationally feasible to traverse [15]. This attack does not require
the opponent to be able to input data of his own choosing to the exponentiation although it may require repeated use of the key until a sufficiently
favorable exponentiation occurs.
3

In the next section we find that the probability of a subtraction is at most 12 and,by increasing R, the probability can be made as close to 0 as desired.

10

Colin D. Walter

Thirdly, a number of side channel attacks depend on recording the frequency of the conditional subtraction at different points in an exponentiation
algorithm over a number of executions of it with different data and the same
unblinded (secret) exponent. In particular, as we see in the next section, thefrequency is different for squarings and multiplications. Hence repeated use of
the square-and-multiply algorithm with MonPro(R) (Fig. 5) or MonPro(M ) ,the same secret exponent and random input data T , would enable the sequence of squarings and multiplications to be deduced, and hence the bits ofthe secret key obtained.
From this summary of attacks, it is clear that no implementation of Montgomery modular multiplication or reduction should be allowed a final conditional subtraction which takes execution time which is not constant. The only
exception is if the subtraction is extremely rare – a case that may actuallyarise below for certain choices of the parameters. Otherwise MonPro(M ) and
MonPro(R) should always perform their subtraction and choose the originalor updated value as appropriate.

7 Frequencies of Conditional Subtractions
In this section we consider a set S of executions of MonPro(M ) with common
modulus M . The aim is to estimate the expected frequency of the conditional
subtraction for the main ways in which the set might have arisen. Then sidechannel leakage about the conditional subtractions can be used to deduce
which of the causes is the most likely for S. The set might represent corresponding operations in a number of different exponentiations using the same
unblinded key, and the aim may be to determine if these operations were allmultiplications or all squarings. Similar results can be obtained for MonPro(R) ,but they are considerably complicated by having non-uniform distributions forthe inputs and outputs: inputs and outputs have ranges greater than M , sothat some residues classes modulo M have more than one representative.
As an example, consider the set of all MonPro(M ) multiplications A×B
mod M for M =7 and R=8. Since R−1 ≡ 1 mod M , the output C satisfies C ≡AB mod M . So, with ABR−1 as a lower bound, the outputs from the MonProloop are those given in Table 1. The overall frequency of the conditional
5. However, restricting to squares A×A mod M , the frequency
subtraction is 49of the subtraction becomes 71 , which is a little greater. If the input A is fixed
to A=5, then the probability of the subtraction for random B rises to 27 .
Different fixed values of A result in other quite different probabilities.
There are three main types of set S to consider: those arising from squaring, those arising from multiplications in which both arguments are free toassume any values independently, and those arising from multiplications inwhich one argument has the same value for the whole set. There are other setsof interest which are not discussed. For example, none of the above matches

11
0
0
0
0
0
0
0

0
1
2
3
4
5
6

0
2
4
6
1
3
5

0
3
6
2
5
8
4

0
4
1
5
2
6
3

0
5
3
8
6
4
9

0
6
5
4
3
9
8

Table 1. A Modular Multiplication Table: unreduced outputs from MonPro(A, B)
when M = 7, R = 8. The five bold entries require reduction.

the set of all multiplications from a single m-ary or sliding windows left-toright exponentiation (unless m = 2): because one input, say A, is taken froma set of only log2 m distinct multipliers, it is neither constant nor uniformly
distributed.
Several reasonable, simplifying assumptions are made in order to derive
the frequencies of the subtraction for S. They are often very hard to justify
theoretically, but several are closely related to the diffusion properties on
which the associated cryptography relies. First,•

it is assumed that φ(M ) ≈ M .

The “Euler phi” function having a value close to M means that M is a productof a small number of large, not necessarily distinct primes, as in the case of
RSA and Fp . The property φ(M ) ≈ M just states that almost every number
is prime to M .
Suppose input A of MonPro is prime to M . Then A has an inverse modulo
M . Therefore, if the other argument B has a uniform distribution modulo M ,so will the output C. So at least one input being uniformly distributed means
that, to a very good approximation, the output is also uniformly distributed.
Such uniformity is propagated from input to output through every instanceof MonPro in an exponentiation if the initial input is uniformly distributed.
Due to formatting and construction restrictions, the inputs to the exponentiation may not be uniform in practice, but diffusion occurs so rapidly during
exponentiation that, except possibly for the initial one or two multiplicative
operations, the uniformity can be assumed.
Let A, B and Z be discrete random variables over the interval of integers 0..M −1 corresponding respectively to the two MonPro(M ) inputs
and the variation in output C of the MonPro loop within the interval[ABr−n , M +ABr−n [. Suppose•

A, B and Z are all independent and uniformly distributedand let πmu be the probability thatPthe final
subtraction takes place. Then
M −1 PM −1 PM −1−1πmu = pr(Z+ABR−1 ≥M ) = M13 Z=0≥M ) ≈
A=0
B=0 (Z+ABR
R
R
P
P
M M
M −1
M −1
1
1
−1
−1
≈ M 3 0 0 ABR dA dB where Z+ABR−1 ≥B=0 ABR
A=0
M3
M is 0 or 1 according to the truth of the inequality. (The approximations

12

Colin D. Walter

arise from using real numbers instead of integers, and are very accurate forcryptographic sized moduli.) So
1
M R−1
(1)
4
This is the probability of the subtraction for a set S of multiplications under
the above hypotheses. Suppose the ith operation in a set of exponentiations
is always a multiplication and that the inputs to the exponentiations are
uniformly distributed modulo M . Then πmu is the probability of a subtraction
when S is the corresponding set of instances of MonPro(M ) .
Now let πsq be the probability that the final subtraction takes place when
MonPro(M ) is used to square a uniformly distributed input. For the samedefinitions as above, suppose
πmu ≈

•

A and Z are independent and uniformly distributed.
PM −1 PM −1
2 −1≥M ) ≈
Then πsq = pr(Z+A2 R−1 ≥M ) = M12 Z=0
A=0 (Z+A R
RP
M 2 −1
M −1 2 −1
1
1≈ M 2 0 A R dA, whence
A=0 A R
M2
1
M R−1
(2)
3
Unlike sets of multiplications, in practice most sets of squarings satisfy thecriteria to apply this value for πsq . Since πmu < πsq , the subtraction is lessfrequent for multiplications than for squarings, as in the example with M =7.
Now suppose the value of A is fixed but the argument B is uniformly
distributed on 0..M −1. Let πA be the probability that the conditional subtraction takes place. For definitions as before, assume also that
πsq ≈

•

B and Z are independent and uniformly distributed.
PM −1 PM −1−1
Then πA = pr(Z+ABR−1 ≥M ) = M12 Z=0≥M ) ≈
B=0 (Z+ABR
R
PM −1
M
1
1
−1
−1
ABR
≈
ABR
dB.
Hence
B=0
M2
M2 0
1
AR−1
(3)
2
So, for fixed multiplier A, the frequency of subtractions depends strongly on
its size. For large A, such as 5 and 6 in the example with M = 7, the frequency
is highest. At the other extreme, note that the value is correct even for A = 0,
although it is not prime to M and so causes the output not to be uniformly
distributed. As expected, the average value of πA is πmu when A is uniformly
distributed.
πA =8 Variance in Frequencies & SCA Errors
If the frequency of the conditional subtraction is used to determine whether
the set S consists of multiplications or squarings, then the accuracy of thedecision is important to know.

13

Let Si be the set of ith modular multiplications in a collection of t squareand-multiply exponentiations using the same 1024-bit key. So |Si | = t. There
are about 1500 sets Si to classify in order to recover the bit pattern of thesecret exponent. If e errors are made, then, with a simple-minded approachin which every bit might be one that has been mis-classified, approximately
1500e different alternatives might have to be tried before the correct exponent is discovered. Of course, operations for sets Si with frequencies close to
the average of πmu and πsq are the most likely to be mis-classified, and thesearch should begin there. This would find the correct key much more quickly.
Nevertheless, it is clear that the error count e has to be kept very small forthis to become the foundation of a computationally feasible attack.
Assuming the inputs to the t exponentiations are independent, the conditional subtractions should occur independently within each Si . Then the
behaviour is that of a binomial random variable for t trials with probability
p = πmu or πsq . The expected number of subtractions is tp and its varianceis σ 2 = tp(p−1). To make use of tables for the normal distribution, it is more
likely that we will prefer to work with the probability of the subtraction rather
than its total count. In this case, the mean is p and the variance is
2
σmu
=

1
1
M R−1 (1− M R−1 )
4t
4

2
σsq
=

1
1
M R−1 (1− M R−1 )
3t
3

or

1
1
AR−1 (1− AR−1 )2t
2
The point at which classification as a squaring or multiplication is equally
likely is the weighted average
2
σA
=

π=

πsq σmu + πmu σsq
σmu + σsq

(4)

If the conditional subtraction occurs less often than this in Si then the set
probably contains multiplications; if it is greater then the set probably contains squarings. The probability of making an incorrect decision can be obtained by looking up tables for the normal distribution, which approximates
the binomial distribution when t is large. It uses the fact that if X is a normal
random variable with mean µ and variance σ 2 , then σ −1 (X−µ) has the N(0,1)
distribution, which is tabulated [7]. So, the probability of the count being on
π −πmu),the wrong side of π is easily seen to be approximately P r(Z > σsq
mu +σsq
where Z is an N(0,1) random variable. This is the average probability of misclassifying an operation, but clearly the operation is much more likely to becorrectly classified when its subtraction probability is well away from π thanwhen it is close to π.
√t) for a typical value ofThis error probability is roughly P r(Z > 13.2
3
−1
MR
≈ 4 . Then t > 1800 would lead to less than 1 error in the 1500

14

Colin D. Walteror so operations for a 1024-bit exponentiation. If√R is doubled, the value ofinterest in the N(0,1) tables is divided by about 2. Then around 18 errors
appear. More refined attacks on the same data can deduce the key with many
fewer exponentiations [14]. However, as the example shows, a very suitablecounter-measure is to reduce M R−1 by increasing R, because this reduces
the incidence of conditional subtractions, and hence reduces the side channel
leakage.

9 A Surprising Improvement
The formulae for πmu and πsq show that one of the easiest way to reduce leakage is to reduce M R−1 . Since the bit length of M is generally fixed, this meansincreasing the number of iterations n in the Montgomery Modular Multiplication algorithm MonPro (Fig. 2). This reduces the frequency of conditional
subtractions. However, as noted in the last paragraph of §4, MonPro can beused for exponentiation on its own without the final conditional subtraction
once M R−1 < 14 . This is because the extra shifting down then makes theoutput small enough for re-use as an input to the next occurrence of MonPro.
A straightforward solution to side channel leakage would be to reduce
standard key lengths by 2 bits. Then 4M < R would hold automaticallyfor the minimum choice of n in a word-based implementation. Consequently,
MonPro could be used throughout an exponentiation without the need forextra iterations or conditional subtractions, and all intermediate values would
remain within the word boundaries. However, suppose that M reaches the
top of the word boundary, so that MonPro requires one more iteration than
MonPro(M ) or MonPro(R) . We will now look in more detail at how this affects
the bounds on intermediate values when MonPro is used.
So, assume also that the word size is at least 2 bits and that n is chosenminimally to ensure 4M < R. This means r ≥ 4 and rM < R < 2rM . Let R0
denote the Montgomery multiplier which the standard version MonPro(M ) or
MonPro(R) would have used. So R = rR0 and M < R0 < 2M . This standard−1
version produces loop outputs bounded by ABR0 +M , which is only justlarger than R0 . But here MonPro performs an extra division by r. Consequently, the upper bound ABR−1 +M on the output is less, making it more
likely to satisfy ABR−1 +M < R0 . An interesting question is therefore whether
all inputs and outputs would be bounded by R0 when the extra iteration is
performed, because the hardware requirements would then be lower. Substituting in the bound R0 , the desired property holds if R0 r−1 +M < R0 , i.e. if
M < R0 (1−r−1 ). Writing this as M < R0 r−1 (r−1) shows the condition is justthat the top word of M is not r−1, i.e. not entirely 1s.
Theorem 1. ([13], Thm 5.) Suppose the top digit of M is not r−1, that r ≥ 4,
and that MonPro is executed with n iterations where M < R0 = rn−1 , i.e.
one more iteration than normal. Then inputs bounded by R0 generate outputs
bounded by R0 .

15

In other words, in almost all cases M is such that a single extra iteration of
the MonPro loop avoids any need for a conditional subtraction. In effect, it is0
equivalent to using MonPro(R ) but without the conditional subtraction sidechannel. Intermediate values of C at the end of a loop iteration in MonPro arebounded above by A+R0 so that, as usual, one extra register bit is needed.
If one is prepared to exclude the rare cases of inconvenient moduli M with
top digit r−1, this means that exponentiation can be carried out successfullyusing MonPro with the usual register sizes and omitting conditional subtractions, providing only that an extra iteration is done in the MonPro loop. Of
course, at the end of the exponentiation there is also no need for a conditional subtraction: as noted before, the adjusting MonPro multiplication by 1
reduces the output to less than M .
With the extra iteration, the exceptional cases can be included simply by0restoring the conditional subtraction, i.e. by using MonPro(M ) or MonPro(R )with an incremented value of n. Then, as in §7, equation (3), the output
can be assumed to be uniformly distributed modulo M , so the probabilityof exceeding M or R0 is at most 12 r−1 . With a typical key lifetime of 10000
uses, and the difficulty of capturing that number of side channel traces, wejust require 16-bit or larger words for the conditional subtraction to havenegligible probability of happening even once per key bit during the lifetimeof the key. This effectively eliminates the side channel leakage since there isinsufficient data at the information theoretic level to reconstruct the key. Tosummarise, MonPro(B) (B=M or R0 ) can be used securely for exponentiation
with all keys if an extra iteration is performed and a 16-bit or larger processor
is used.

10 Conclusion
This chapter has carefully derived input and output bounds for several versions of Montgomery modular multiplication in order for it to be of use inexponentiation. Some pre- and post- processing is necessary, and the precomputation of a multiplier R(2) whose one-time cost can be amortised overthe lifetime of the modulus M .
This analysis enabled the frequencies of conditional subtractions to be
deduced accurately, showing that there could be considerable side channel
leakage from the ability to observe the subtractions.
It was shown how this side channel could be closed by increasing the number of iterations in the MonPro algorithm. At the further cost of one extra
register bit, or the exclusion of some extreme modulus values, the conditional
subtraction can be totally eliminated. However, even if the conditional subtraction were retained to include the exceptional cases, the extra iteration
reduces the side channel to an unusable level except for these extreme moduli
on hardware with a very small word size.

16

Colin D. Walter

The chapter therefore provides several choices for implementing Montgomery modular multiplication in a manner which effectively eliminates any
side channel leakage emanating from the final, conditional subtraction.

11 Exercises
1 i) Find 16−1 mod 11. Using the output bounds given in Fig. 2, compute acomplete table of output from MonPro when M = 11, R = 16, and A and B
are least non-negative residues modulo M .
ii) Use this table to determine the probability of the conditional subtraction
in MonPro(M ) for a) multiplications and b) squarings which have uniformly
distributed inputs. c) For each value of A calculate the probability of the subtraction for multiplications by fixed A. d) Compare these probabilities withthe theoretical ones derived in §7.
iii) Repeat (ii) with MonPro(R) in place of MonPro(M ) (including part (d)).
iv) Compute a complete table of output from MonPro when M = 7, R = 32,
and A and B are strictly bounded above by 2M . What is the largest value inthe table? For each value B = M, M +1, ..., 2M −1, if both inputs are strictly
less than B, find out how many outputs are B or larger.
2 i) Let M = 9, T = 3, N = 2, R = 16 in the computation of S = T N mod M
using MonPro(R) . Find R−1 mod M and determine the two possible values
for R(2) . Deduce the values of T and S. Hence show that the output S stillrequires a final subtraction to be fully reduced. Why does this not contradict
the claim in the text that final subtractions are unnecessary?
ii) Repeat (i) for the same inputs but with MonPro and R = 64.
iii) Prove that using MonPro or MonPro(R) to compute S = 3N mod 9 will
always give output S = 9 when N ≥ 2 and R satisfies the usual constraints.
iv) Suppose P is a prime such that P 2 divides M , T = M/P and N ≥ 2.
With the usual requirements on R, prove that using MonPro or MonPro(R)to compute S = T N mod M will always give output S = M .
3) Let N = DDMMYY be today’s date (a pseudo-random exponent), M thefirst prime greater than the number of this page, R the first number greaterthan 89 M which is prime to M , and chosen input text T = b 41 M c.
i) Use a calculator to compute a value for R(2) and hence calculate the preprocessing value T given by MonPro(M ) for an exponentiation.
ii) Convert N into binary and hence list the operations required to perform
a left-to-right square-and-multiply exponentiation with exponent N . Use thislist to create a list of the associated values of S when MonPro(M ) is used toevaluate T N mod M . Include in the list information about whether or not the17conditional subtraction occurs.
iii) Now, using the values for T , R and M , reconstruct all the possible exponents which generate the same list of the conditional subtractions as N .
You should create a binary tree of options for the bits, and traverse the treesystematically, calcuating the corresponding values of S, and checking to see
whether or not the behaviour of the conditional subtraction is the same. Whenthe behaviour of the subtraction is different, the branch can be pruned as it
cannot represent the true value of N .
iv) Count the number of nodes in the tree which have been visited. Build anargument to justify that this number is linear in the length of the exponent.
Is such a search computationally feasible for a large exponent? What would
happen to this count if a) R/M were larger? or b) T /M were larger?

12 Projects
1) Choose any modulus M with no factors less than 28 , say, such that(M −1)2 mod M can be computed correctly and easily in the machine arithmetic that is available to you. Select a Montgomery constant R > M . R neednot be a power of 2 for this exercise, but must be prime to M .
i) Write a program to perform exponentiation with 16-bit exponents using
MonPro(M ) .
ii) Check that your code performs correctly by comparing results with a classical implementation of modular exponentiation.
iii) Check also that no final subtraction is required to get output less than M .
iv) Modify your code to collect data about the occurrences of the conditional
subtraction in the ith modular multiplication for each i. (Clearly 1 ≤ i < 32.)v) Generate t = 103 random exponentiations using the same modulus andsame exponent, and collect the conditional subtraction frequencies for eachposition i in the exponentiation.
vi) Verify that the frequencies match those expected from §7, at least on average.
vii) Compute the means and standard deviations of the frequencies for a) the
multiplications and b) the squarings. Hence compute the value of π given inequation (4).
viii) Use your value for π to partition the operations into multiplications andsquarings. How many operations are mis-classified in this way? If the numberof multiplications is known and used as the partitioning point, how many are
mis-classified then?
ix) Repeat (v)-(viii) several times for different numbers of exponentiations tosee how the number of mis-classified operations varies with t.

18

Colin D. Walter

2 i) Repeat project 1 with MonPro(R) in place of MonPro(M ) , this time selecting R such that (R−1)2 mod M is easily computable on your available
machine.
ii) Divide the interval [0, R] into, say, 50 or 100 sub-intervals, and modify the
exponentiation code to collect the frequencies for the output of MonPro(R)lying in each sub-interval. Plot these frequencies on a graph for several different values of M such that 21 R < M < R. Explain why the curve representing
these frequencies rises from 0 to R−M , is horizontal between R−M and M ,and then falls from M to R.
iii) Modify your data collection in (ii) to separate the sub-interval frequencies
for multiplication outputs from those of squaring outputs. Are the graphs ofthese frequencies different? If so, attempt to explain the difference.
3) Collect subtraction frequencies from the exponentiation software fromproject 1 or 2 when the same modulus and exponent are used for a set of
t = 103 exponentiations.
i) Use the length of the exponent (16 here) and the total number of modular
multiplications in an exponentiation to deduce the number m of multiplications and the number s of squarings.
ii) Let M be the set consisting of the m operations with the lowest frequencies for the conditional subtraction, and let S be the complementary set
consisting of the other s operations. As before, count how many operations
are mis-classified if those in M are assumed to be multiplications, and thosein S are assumed to be squarings.
iii) Modify your software to collect the data from the ith operation as at-dimensional vector over {0,1} where 0 indicates that no subtraction took
place, and 1 that a subtraction did take place. Call the vector vi . For each
operation, compute the average Hamming distance between vi and the vectors
in M. Does this distance depend on whether the operation is a multiplication
or a squaring?
iv) Suppose the m operations for which the distance of part (iii) is smallest
represent multiplications. Re-allocate all the operations in M and S under
this assumption. Does this decrease the number of errors?
v) Repeat the re-allocation process of part (iv) a number of times, and observe
whether the number of errors decreases or increases with each iteration of theprocess.
vi) Repeat a similar re-allocation process on the initial partition of part (ii)using the average Hamming distance of vi from the vectors in set S.
vii) Inconsistencies between the results of (v) and (vi) must represent allocation errors in one or other case. However, are there any operations which arestill incorrectly allocated? If not, reduce the value of t to see when errors start

19

appearing. If so, increase t to see if the number of errors decreases. Also, howdoes the number of inconsistencies vary with t?
viii) Repeat all the above for exponents with a variety of larger and larger
lengths. Does the proportion of errors change as the length increases when t
is fixed? How does the total number of errors vary for fixed t as the length
varies?
4) Following on from exercise 2, investigate more thoroughly the cases where
the computation of S = T N mod M using MonPro(M ) might require a final
conditional subtraction in the post-processing phase. Look first at when M isa prime power, then at more general non-square-free M .

References
1. P. D. Barrett, Implementing the Rivest Shamir Adleman public key encryption algorithm on standard digital signal processor, Advances in Cryptology –Crypto ’86, Springer, 1987, 311–323.
2. J.-J. Quisquater, Presentation at the rump session of Eurocrypt ’90.
3. Ç. K. Koç, T. Acar & B. S. Kaliski, Jr., Analyzing and Comparing Montgomery
Multiplication Algorithms, IEEE Micro, 16(3), 1996, 26–33.
4. P. Kocher, Timing attack on implementations of Diffie-Hellman, RSA, DSS,
and other systems, Advances in Cryptology – Crypto ’96, N. Koblitz (editor),
LNCS 1109, Springer-Verlag, 1996, 104–113.
5. P. Kocher, J. Jaffe & B. Jun, Differential Power Analysis, Advances in Cryptology – Crypto ’99, M. Wiener (ed.), LNCS 1666, Springer-Verlag, 1999,
388–397.
6. P. L. Montgomery, Modular Multiplication without Trial Division, Mathematics
of Computation, 44(170), 1985, 519–521.
7. NIST/SEMATECH, Cumulative Distribution Function of the Standard Normal Distribution §1.3.6.7.1 in the “e-Handbook of Statistical Methods” at
http://www.itl.nist.gov/div898/handbook/, 2006.
8. Digital Signature Standard, Appendix 6 (July 1999), Federal Information Processing Standard (FIPS) 186-2, NIST, Jan 2000.
9. S. E. Eldridge & C. D. Walter, Hardware Implementation of Montgomery’s
Modular Multiplication Algorithm, IEEE Trans. Comp. 42, 1993, 693–699.
10. C. D. Walter, Systolic Modular Multiplication, IEEE Trans. Comp. 42, 1993,
376–378.
11. C. D. Walter, Montgomery Exponentiation Needs No Final Subtractions, Electronics Letters, 35(21), October 1999, 1831–1832.
12. C. D. Walter & S. Thompson, Distinguishing Exponent Digits by Observing
Modular Subtractions, Topics in Cryptology – CT-RSA 2001, D. Naccache (editor), LNCS 2020, Springer-Verlag, 2001, 192–207.
13. C. D. Walter, Precise Bounds for Montgomery Modular Multiplication andSome Potentially Insecure RSA Moduli, Proceedings of CT-RSA 2002, LNCS
2271, Springer-Verlag, 2002, 30–39.
14. C. D. Walter, Longer Keys may facilitate Side Channel Attacks, Selected Areas
in Cryptography – SAC 2003, LNCS 3006, Springer-Verlag, 2004, 42–57.

20

Colin D. Walter

15. C. D. Walter, Simple Power Analysis of Unified Code for ECC Double and Add
Proceedings of CHES 2004, LNCS 3156, Springer-Verlag, 2002, 191–204.