Montgomery Exponentiation Needs No Final Subtractions
Colin D. Walter
Computation Department, UMISTPO Box 88, Sackville Street, Manchester M60 1QD, UK
www.co.umist.ac.uk

Abstract
Montgomery’s modular multiplication algorithm is commonly used in implementations ofthe RSA cryptosystem. We observe that there is no need for extra cleaning up at the end of an
exponentiation if the method is set up in the right way.

Key Words: Cryptography, RSA cryptosystem, Montgomery modular multiplication.

1 Introduction
The RSA encryption function [6] uses a public modulus M, usually of up to 1024 bits, andtwo keys d and e, at least one of which is private, with the property that Ade ≡ A mod M.
Message blocks A satisfying 0 ≤ A < M are encrypted to C = Ae mod M and decrypted by A =Cd mod M.

The computation of Ae mod M consists of two main processes: modular

multiplication and exponentiation. The constituent modular reduction steps on partial results
S normally require a comparison of S with M which, in the worst case, means that every bit ofboth long numbers needs to be examined in turn. Such potentially expensive comparisonsneed to be done even if no subtraction is actually required. This letter will show that use ofMontgomery’s modular multiplication algorithm [5] enables every such comparison to beavoided. It develops further a remark by Blum and Paar [1]. The methods are applicable toall implementations, whether in software or hardware. As well as saving computation time,avoiding such comparisons is important in preventing the success of timing attacks on thecryptosystem [4].

1IEE

Electronics Letters, vol. 35 no. 21, October 1999, pp 1831-1832

2 Montgomery’s AlgorithmSuppose all numbers are represented with base (or radix) r which is a power of 2, say r =2k, and let n be an upper bound on the number of digits needed for any number encountered.
n −1Then every number X has a representation of the form X = ∑i =0 xi r i where, for nonredundant systems, the ith digit xi satisfies 0 ≤ xi < r. The classical modular multiplication
algorithm for (A×B) mod M simply takes the normal method of multiplication, whichaccumulates digit products ai×B, and interleaves modular reductions to keep the result below
M. Peter Montgomery [5] has provided a variation of this algorithm in which the multiplierdigits are consumed in the reverse order and no full length comparisons are required for themodular reductions:
MONTGOMERY’S MODULAR MULTIPLICATION ALGORITHM{ Pre-condition: M prime to r and A non-redundant}
S := 0 ;For i := 0 to n−1 do
Beginqi := (s0+aib0)(-m0-1) mod r ;S := (S + ai×B + qi×M) div r ;{ Invariant: 0 ≤ S < M+B }End ;{ Post-condition: Srn = A×B + Q×M }In RSA the modulus is a product of two large primes and so prime to the radix r. Hence there
is a residue m0−1 mod r which satisfies m0×m0−1 ≡ 1 mod r. The digit qi is chosen so thatiS+ai×B+qi×M is exactly divisible by r. If we define Ai = ∑ j = 0 a j r j and Qi analogously thenAi = Ai−1+airi and An = A. By induction, the value of S at the end of the ith iteration is easily

shown to satisfy ri+1S = Ai×B+Qi×M because the division is exact. Hence the post-condition
holds. Moreover, the bound on the size of the digits ai enables the loop invariant to beestablished also by induction.
Some implementations may make use of redundant representations in which the digits
have a wider range than 0 .. r−1.

However, because the digits of A are consumed inascending order, they can be converted on-line into the standard representation for A. Thus
the algorithm can treat any redundancy in A. Redundancy in the other numbers is immaterial
to the present argument.

2

C. D. Walter, Montgomery Exponentiation Needs No Final Subtractions

3 Exponentiation
In an encryption, the extra power of r factor in the output S is easily cleared up by minor
processing before and after the exponentiation [2], [3]. We associate with every number its
Montgomery class mod M, namelyA ≡ rnA mod M

Then, if × denotes Montgomery modular multiplication, the Montgomery product of A andB is A × B ≡ A B r−n ≡ ABrn ≡ AB mod M.

Hence, using × rather than × in an

exponentiation algorithm is going to produce Ae from A . The initial class A is normallyformed as a Montgomery product from A and the pre-computed value
R = r n ≡ r2n mod M

by computing
A × R ≡ Arn ≡ A mod M.

Finally, removal of the extra power of r from Ae is also done by a Montgomery
multiplication: Ae mod M is obtained fromA e × 1 ≡ Ae mod M.

4 Bounds on the I/O
Throughout the exponentiation, outputs from multiplications are re-used as inputs. So it
is important to ensure these numbers remain bounded. In particular, we will show S < 2M ismaintainable for all outputs S. Assume that n is large enough for 2M < rn−1 to hold and thatthe inputs A, B to a Montgomery multiplication both satisfy the bound, i.e. A < 2M and B <2M. Then an−1 = 0. Hence, the bound S < M+B at the end of the second last loop iteration
yields S < M+r−1B on the final round, from which S < 2M (as r ≥ 2). Therefore, as both R and
the initial message A for encryption should be below the bound 2M, the final output of the
exponentiation should also satisfy this bound.
Now consider the final scaling by 1 to remove the unwanted power of r from A e . The
post-condition of this modular multiplication is Srn = A e + QM.

3Here Q can have aIEEElectronics Letters, vol. 35 no. 21, October 1999, pp 1831-1832

maximum value of rn−1 arising from all its digits being r−1. So the bound A e < 2M leads toSrn < (rn+1)M and thence to S ≤ M because S is an integer and r−nM < 1. Hence a final

subtraction to obtain an output S < M is only necessary if S = M, i.e. when A e ≡ 0 mod M, thatis, for A ≡ 0 mod M. However, A is a plaintext or ciphertext message and hence, bydefinition, less than M. The only possibility is then that A = 0. But A = 0 clearly leads to all
numbers being identically 0 throughout the exponentiation. In particular, the final output is 0
and does not require any extra subtraction. Thus, in no circumstances does the output Ae fromthe exponentiation need any further modular adjustment to obtain a least non-negative residue
mod M.

4 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 toproduce output in the correct range.

References[1]

T. Blum & C. Paar, “Montgomery Modular Exponentiation on ReconfigurableHardware”, Proc. 14th IEEE Symp. on Computer Arithmetic, Adelaide, 14-16 April,
1999, pp. 70-77.

[2]

S. E. Eldridge, “A Faster Modular Multiplication Algorithm”, Intern. J. Computer
Math., vol. 40, 1991, pp. 63-68.

[3]

S. E. Eldridge & C. D. Walter, “Hardware Implementation of Montgomery’s Modular
Multiplication Algorithm”, IEEE Trans. Comp., vol. 42, 1993, pp. 693-699.

[4]

P. Kocher, “Timing Attacks on Implementations of Diffie-Hellman, RSA, DSS, andOther Systems”, Advances in Cryptology, Proc Crypto 96, Lecture Notes in Computer
Science, vol. 1109, N. Koblitz editor, Springer-Verlag, 1996, pp 104-113.

[5]

P. L. Montgomery, “Modular Multiplication without Trial Division”, Math.
Computation, vol. 44, 1985, pp. 519-521.

[6]

R. L. Rivest, A. Shamir & L. Adleman, “A Method for obtaining Digital Signatures andPublic-Key Cryptosystems”, Comm. ACM, vol. 21, 1978, pp. 120-126.

4