Techniques for the Hardware
Implementation of Modular Multiplication
byColin D. Walter
Computation Department, U.M.I.S.T.,
PO Box 88, Sackville Street, Manchester M60 1QD, U.K.
C.Walter@co.umist.ac.uk

http://www.co.umist.ac.uk/

An RSA cryptosystem consists of a modulus M
of around 1024 bits and two keys d and e with theproperty that Ade ≡ A mod M. Message blocks A
satisfying 0 ≤ A < M are encrypted to A’ = Ae mod
M and so uniquely decrypted by A = A’d mod M
using the same algorithm for both processes.
M = PQ is chosen as a product of two large primes,
e is often small with few non-zero bits so thatencryption is relatively fast, and d chosen to satisfy
de ≡ 1 mod (P–1)(Q–1). Thus d has as many bits
as M. The owner of the cryptosystem publishes M
and e but keeps secret the factorization of M andthe key d. Breaking the system requires discovering
P and Q, which is computationally infeasible.
Indeed, each addition of a small, almost constantnumber of bits (around 15) to the size of M doubles
the effort required for this [2].

Index
Terms:
Computerarithmetic,
cryptography, RSA cryptosystem, Montgomery
modular multiplication, redundant number
systems, higher radix representation, optimal
speed, area complexity.

Abstract
Hardware for modular multiplication isrequired for strong cryptosystems so that large
volumes of encrypted data can be safely stored inpublic areas and obtained over a public network(e.g. the WWW) but only understood by authorised
users. This article reviews the main bottlenecks
which may arise in the more obvious
implementations of RSA and outlines a variety ofsolutions to them so that plain text can be recovered
in real time.

This paper discusses the major problems
associated with space and time efficient hardware
implementation of the cryptosystem and reviews
their solution. Among the issues of concern arecarry propagation, digit distribution, buffering,
communication and use of available area.

1. Introduction
RSA [1] is an arbitrarily strong, two key
cryptosystem which is generally only currently used
for authentication protocols and for exchange ofsession keys to enable secure communication byarithmetically less intensive encryption methods.
However, there is a growing need for secure
encryption of large volumes of data. In particular,
this is the case for data accessible over the internet
which is commercially sensitive and should only becomprehensible to certain readers. It is also thecase for much private data which is stored on
public servers. The quantity of such data can makeweak cryptosystems essentially useless in suchsituations. However, software implement-ations ofa strong cryptosystem such as RSA are too slow fordecrypting retrieved data in real time for viewing or
editing purposes. Only dedicated hardware canachieve a speed equal to the disk access times,
internal bus speeds, etc. which dictate the retrieval
times for unencrypted data.

2. Notation
The computation of Ae mod M is split into two
main processes: modular multiplication andexponentiation. The exponentiation is discussed
last as it has to make repeated use of the modular
multiplication hardware. Thus we look first atcomputing (A×B) mod M.
Each number X has a representation of the formn −1

X = ∑i = 0 xi r i where r is the radix or base (usually
a power of 2) and xi is the ith digit (usually0 ≤ xi < r). Let n be the number of digits for thisrepresentation of M.
The representation isredundant if numbers can be represented in morethan one way. Here this occurs by allowing digits
1Proc. 2nd IMACS Internat. Conf. on Circuits, Systems & Computers, Athens, Oct 1998, vol. 2, pp 945-949

digits and so halves the time taken. If the k-bit
multiplier works in one cycle with no pipelining andk is roughly the bandwidth of the internal bus, it iseasy to calculate that sufficient throughput for realtime decryption requires n multipliers so that acomplete multiplier digit times multiplicand aiB (orequivalent) can be computed in one cycle. Then, in
effect, each cycle processes all the multiplicand bitswith k of the multiplier bits. A different regime
would lead to more complex data paths and hence
less efficient use of chip area, and so is notconsidered.

in a range larger than 0..r−1, and typically thatgiven by an extra (carry) bit, that is, 0..2r−1. For
example, the output from a carry-save adderprovides two bits for each digit and so, in effect, isa redundant representation where digits lie in therange 0..2 rather than the usual 0..1. We use k forthe number of bits used to represent a digit, so thatkn is approximately 210 here, and O(kn) is
effectively constant.
The choice of k and n splits the formation of
A×B into two multiplication levels: forming
products of k-bit digits and forming products of ndigit numbers. More levels could be created.
Different algorithms are used for each level. The
lower level is of combinational logic, possibly
pipelined to increase throughput. The hardware
will be built around n k-bit digit multipliers, andthis defines our choice of k. The upper level viewsa product as a sequence of additions of digits
multiples aiB of the multiplicand, and so will take anumber of clock cycles.

Suppose therefore that the n digit multipliers
are used to add aiB to a partial product in one clock
cycle. If the carries are propagated then this takes
extra time beyond the digit multiplic-ations. The
digit multipliers ought not to lie idle while thishappens. The equivalent of a carry save addermight be used to avoid carry propagation, so thatthe partial product has a redundant representation[10].
Alternatively, successive aiB can be
pipelined: either ai+1B can be formed as the previous
carries are propagated or, if aibj and its carry arecalculated on one cycle, the next multiplier along
should use this carry on the next cycle to computeaibj+1 and another carry [9].

3. Multiplication
Practical planar designs are well known for
multipliers which are optimal with respect to somemeasure of time and area [3]-[8]. Under a model
which assumes that wires take area but do notcontribute to time, Area×Time2 complexity for a kbit multiplication is bounded below by k2 [3] andthis bound can be achieved for any time in the range
log k to k [6]. Such designs tend to use theDiscrete Fourier Transform and consequently
involve large constants in their measures of timeand area. There are more useful designs which are
asymptotically poorer but perform better if k is not
too large. Since the cross-over point is claimed to
be around k = 3×103 bits [5], i.e. greater than thesize of the numbers here, classical methods are
preferable. Indeed, it makes sense to pick a
standard k-bit combinational multiplier off the shelfsince it will contain years of optimisation, it will
have a known latency and will be known to becorrect. For a current standard chip of perhaps 107transistors devoted entirely to RSA, k = 32 or 64 is
the maximum practical [9] since there must be
space for registers and for other operations such as
modular reduction.

4. Modular Reduction
The reduction of A×B to (A×B) mod M can be
carried out in several ways, but each involves
repeatedly choosing a suitable digit q and
subtracting a shifted qM from the current
remainder. The successive choices of digit q can bepieced together to form the integer quotient Q =(A×B) div M or a closely related quantity if desired.
Classically, shifted multiples of M are subtracted
from the most significant end of A×B:
{ Pre-condition: 0 ≤ A×B < M×rn }R := A×B ;For i := n−1 downto 0 do
Begin
q := R div (M×ri) ;R := R − q×M×ri;i{ Invariant: 0 ≤ R < M×r& R ≡ (A×B) mod M }End ;{ Post-Condition: R = (A×B) mod M }There is a direct trade-off between time andarea. Doubling the number of digit multipliers
allows the parallel processing of twice as many

This requires waiting for a full carry propagation
with each subtraction if the largest possible multiple2Colin D. Walter, Hardware Implementation of Modular Multiplication

is to be removed. A better solution is just to use the
top digit or two of M and the remaining product todetermine a sufficiently good multiple of M toremove [10]. This reduces the result enough toguarantee an upper bound of rM, say, when theprocess terminates.
This can be cleaned up
properly at the end of the de-cryption. The critical
path is now in the circuitry for computing q, but
this can be reduced by scaling M [11,12]. M isreplaced by a small multiple so that its top digits
are known and simple, say, 10... Minor postprocessing will again recover the correct residue.

chosen so that R+qM is a multiple of r, and this isshifted down (i.e. divided by r) for use in the next
iteration. Consequently, (A×B×r–n) mod M iscomputed:{ Pre-condition: 0 ≤ A < rn }R := 0 ;For i := 0 to n−1 do
Beginq := (-(r0+ai×b0)m0-1) mod r;
R := (R+ai×B+q×M) div r ;{ Invariant: 0 ≤ R < M+B }End ;{ Post-Condition: R ≡ (A×B×r–n) mod M }If the product A×B is fully computed before themodular reduction starts, then a register of 2n digits
is required. However, if the product is performedby repeated shifting and addition, the modular
reductions can be interleaved with the additions tokeep the partial sum down to only about n digits,
thereby saving space. This has the added advantagethat the multiplier hardware and modular reduction
hardware can work simultaneously on the same
modular product; otherwise full utilisation of thesetwo parts of the hardware would require thecomplication of handling two modular products at
once.

The extra factor, a power of r, is easily cleared up
in minor post-processing [14]. Any extra multipleof M is also easily removed.
With this algorithm, the digit q is computedfrom the lowest digits of R and M without waiting
for any carry propagation. So pipelining of thedigits
can
now
take
place
with
aibj+1 computed on the cycle after aibj using its
carry and the same values of q and ai. Thus, a nonredundant representation can be used and q and ai
no longer need to be broadcast to all digit slices inthe same clock cycle.

The modular reduction requires another n digit
multipliers to compute qM, so that the main area
taken up by the RSA circuitry is 2n k×k-bit
multipliers and an adder to combine their outputs.
It has been suggested that a table be formed
containing some or all digit multiples of M in order
to avoid re-computing them so many times. This is
unwise as it requires O(2k) entries, so the time andspace requirements would exceed those of recomputation unless k were very small.

Once more the critical path length is incomputing q. To reduce this path M is again scaled[15], this time ensuring that its lowest digits are
known and simple, say ...01. This moves thecritical path to within the multiplier of each digit
slice, so that most of the hardware is operating atfull capacity.
Further optimisation must
concentrate on the digit slice and improved
communications.

5. Montgomery’s Algorithm

6. Communications

The above modular reduction method has
several disadvantages. It requires a redundant
representation (which takes up more space) to avoid
carry propagation, makes a poor choice of multiple
to subtract, takes time to compute the digit q, andrequires the global broadcasting of q to each digit
position. Peter Montgomery [13] has shown how to
use the least significant digit of an accumulatingproduct to determine the multiple of M to subtract.
He reverses the usual multiplication order bychoosing multiplier digits from least to mostsignificant and shifting down on each iteration. If R
is the current partial modular product, then q is

Our goal is to have only local intercommunication because of the delays and wiringassociated with global movement of data. The
standard approach, namely parallel processing ofdigit operations for the same multiplier digit,
requires broadcasting q and ai to all digit slices oneach cycle [10,12].
Avoiding this requires
pipelining digits as described above and yields asystolic array [16,17,9].
If the term aibj were added to the partial resultin digit slice j on cycle i+j, the first output digit
would occur at time n−1. Full utilisation of the3Proc. 2nd IMACS Internat. Conf. on Circuits, Systems & Computers, Athens, Oct 1998, vol. 2, pp 945-949

hardware could only occur if another modular
multiplication were to start at time n when digit
slice 0 becomes free again. Fortunately, theexponentiation involved in the cryptosystem meansthat the output from one modular multiplication is
the input to the next modular multiplication, and sono time is lost and little wiring and buffering isrequired to achieve this. The precise timing details
are actually slightly more complex because of theshift down in Montgomery’s algorithm [16,17,9].
Since this system requires input digit serially, kbits at a time for each number and produces output
similarly, its I/O matches internal bus speeds andbandwidth and so reduces the need for on chip
buffering of data.

7. Exponentiation
The exponentiation required for encryption anddecryption is generally achieved simply byincorporating several registers and making repeateduse of the modular multiplier hardware. If the
exponent d has the same size as M, namely about
nk bits, then the usual square and multiply
algorithm for exponentiation takes between nk and
2nk modular multiplications, and 1.5nk on average.
There are ways to reduce this towards nk [18,19]
but the possible improvements are very limited.
Much more is achieved by good design for themodular multiplier.

8. Conclusion
We have reviewed the main bottlenecks which
may arise in hardware for implementing the RSA
cryptosystem and shown how to make the mostefficient use of area. The key solutions are to use
Montgomery’s modular multiplication algorithm[13], scale the modulus, pipeline digit products anduse an existing k-bit combinational multiplier.
Finally, k is chosen as large as possible to make fulluse of the available chip area so that real time
decryption is achieved.

N. Koblitz, A Course in Number Theory and
Cryptography,
Graduate
Texts
inMathematics, vol. 114, Springer-Verlag,
1987.

[3]

R. P. Brent & H. T. Kung, “The Area-Time
Complexity of Binary Multiplication”, J.
ACM, vol. 28, 1981, pp. 521-534.

[4]

R. P. Brent & H. T. Kung, “A Regular
Layout for Parallel Adders”, IEEE Trans.
Comp., vol. C-31, no. 3, March 1982, pp.
260-264.

[5]

W. K. Luk & J. E. Vuillemin, “Recursive
Implementation of Optimal Time VLSI
Integer Multipliers”, VLSI ’83, F. Anceau &E.J. Aas (eds.), Elsevier Science, 1983, pp.
155-168.

[6]

K. Mehlhorn & F. P. Preparata, “Area-Time
Optimal VLSI Integer Multiplier with
Minimum Computation Time”, Information& Control, vol. 58, 1983, pp. 137-156.

[7]

F. P. Preparata & J. Vuillemin, “Area-Time
Optimal VLSI Networks for computing
Integer Multiplication and Discrete Fourier
Transform”, Proc. ICALP, Haifa, Israel,
1981, pp. 29-40.

[8]C. S. Wallace, “A Suggestion for a Fast
Multiplier”, IEEE Trans. Electronic
Computers, vol. EC-13, no. 2, Feb. 1964,
pp. 14-17.

[9]C. D. Walter, “Redundant Arithmetic is notnecessary for Fast Modular Exponentiation”,
submitted to IEEE Trans on Comp.

[10] E. F. Brickell, “A Fast Modular
Multiplication Algorithm with Application to
Two Key Cryptography”, Advances in
Cryptology - CRYPTO ’82, Chaum et al.
(eds.), New York, Plenum, 1983, pp. 51-60.
[11] C.
D.
Walter,“FasterModularMultiplication by Operand Scaling”,
Advances in Cryptology - CRYPTO ’91, J.
Feigenbaum (ed.), Lecture Notes in Comp.
Sci. vol. 576, 1992, pp. 313-323, SpringerVerlag.

References
[1]

[2]

[12] C. D. Walter, “Space/Time Trade-offs forHigher Radix Modular Multiplication using
Repeated Addition”, IEEE Trans. Comp.,
vol. 46, 1997, pp. 139-141.

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

Colin D. Walter, Hardware Implementation of Modular Multiplication[18] D. E. Knuth, The Art of Computer
Programming, vol. 2, “Seminumerical
Algorithms”, 2nd Edition, Addison-Wesley,
1981, pp. 441-466.

[13] P. L. Montgomery, “Modular Multiplication
without Trial Division”, Math. Computation,
vol. 44, 1985, pp. 519-521.
[14] S. E. Eldridge, “A Faster Modular
Multiplication Algorithm”, Intern. J.
Computer Math., vol. 40, 1991, pp. 63-68.

[19] C. D. Walter, “Exponentiation using
Division Chains”, IEEE Trans. Comp., vol.
47, 1998, no. 7, to appear.

[15] S. E. Eldridge & C. D. Walter, “Hardware
Implementation of Montgomery’s Modular
Multiplication Algorithm”, IEEE Trans.
Comp., vol. 42, 1993, pp. 693-699.
[16] C.
D.
Walter,“Systolic
ModularMultiplication”, IEEE Trans. Comp., vol.
42, 1993, pp. 376-378.

26th May 1998[17] P. Kornerup, “A Systolic, Linear-Array
Multiplier for a Class of Right-Shift
Algorithms”, IEEE Trans. Comp., 1994, vol.
43, no. 8, pp. 892-898.

5