An Improved Linear Systolic Array for Fast
Modular Exponentiation
Colin D. Walter
Computation Department, UMIST,PO Box 88, Sackville Street, Manchester M60 1QD, U.K.
e-mail: C.Walter@umist.ac.uk
www.co.umist.ac.uk

Abstract. Because of the large word lengths involved, communication
and buffering are potentially the major problems in implementing themodular arithmetic used in several cryptosystems. It is shown here howa single, linear systolic array eliminates much of the associated overheads,
thereby improving through-put and the ratio of speed to area for modular
exponentiation. Alternative forms produce simpler processing elements
and make fuller use of the hardware, making it more easily implemented
in current technology. Such designs are regarded as much safer for use
in smartcards and embedded systems as they offer greater protection
against attacks using differential power analysis. A 1024-bit array can bebuilt in an area comparable to a 64-bit multiplier.
Index Terms: Computer arithmetic, cryptography, RSA cryptosystem,
Diffie-Hellman, linear systolic array, Montgomery modular multiplication,
exponentiation, differential power analysis, DPA.

1Introduction

Efficient modular exponentiation is essential to fast encryption using, for example, the RSA [19], ElGamal [5], Diffie-Hellman [3] or DSA [17] schemes. Brickell[2] describes the earliest hardware speedups for modular multiplication. He employs digit slices working in parallel and redundant number representations inorder to perform modular multiplication by repeated addition. However, the simultaneous broadcast of multiplier digits to all digit positions is required, witha consequent burden on hardware area, capacitance and clock period. To avoid
this, digits in the adder must be processed serially using a systolic array. In[22], the author showed how this could be done by using Montgomery’s modular
multiplication algorithm [16] which reverses the order of processing multiplierdigits when compared with the standard multiplication algorithm. This was thefirst design where, apart from clock and power, all the communication was entirely local, between nearest neighbour processing elements. Without the needto await the completion of carry propagation, the clock cycle is much shorter,

2

IEE Computers and Digital Techniques 147 no. 5, Sept. 2000, pp. 323-328

so that throughput is increased and hardware cost is reduced. Indeed, there is
improved latency over the most recent implementations of traditional methods[24].
For convenience, [22] initially describes a full, rectangular, systolic array with
one row for each addition step and as many rows as are necessary to complete a
modular multiplication. The final paragraphs describe the possibilities of fewerrows and, in particular, mention its minimal linear form as a single row which canperform two multiplications in parallel by feeding the output directly back in.
This indeed provides a modular equivalent of the pipeline multiplier of Jackson
et al. [7]. Here some quantification and amplification of the benefits of this special
case are given.
In particular, we first show how to adapt the array to modular exponentiation
without having to buffer results or idle between successive multiplications. The
square and multiply algorithm for exponentiation leads to only 75% use of theresulting hardware on average. Moreover, the silicon area is still substantial sinceeach processing element (PE) contains two multipliers. The second part of thisarticle therefore reduces the PEs to contain a single multiplier and makes themwork on every cycle instead of only on alternate cycles to compute one modular
multiplication. This cuts the total area almost in half, making it more amenable
to current technology and allows 100% use of the array rather than 75%.
Alternative linear arrays have been given by Kornerup [14] and Jeong andBurleson [8]. By comparison, Jeong and Burleson [8], Fig. 5, require 50% moreclock cycles per multiplication than here and perform only one multiplication
at once rather than two as here. Their array uses the same number of PEs andthey are also more complex than here. Hence throughput for an exponentiation
is at least 3 times slower and the hardware has the additional overhead of several
extra registers (7 for the binary case). The PEs there only operate on every third
cycle. The most competitive hardware is that of Kornerup, who groups pairs of
product terms [14], Fig. 2, in order to utilise the array fully. Consequently, he
has half the number of cells as here but they are twice as complex, yielding thesame overall hardware area. By running the two halves of his PEs in parallel, hiscell speed is only marginally slower than that here but he uses half the numberof clock cycles. Thus, his array has superior latency by a factor of almost 2,
but similar throughput since two modular multiplications cannot be computedin parallel. Two copies of his array are needed for efficient exponentiation. This
provides almost twice the speed as here but at a cost of just over twice thehardware and slightly more buffering is required. The area×time product isthus similar. With pressure on chip area, the more minimal design here is ofimportance. Our second design uses only a quarter of the area of Kornerup andreduces area×time for exponentiation by 25% on average.
The exposition closes with a look at the more general context of the hardware,particularly considering its potential strength against differential power analysis[12], [13].

C. D. Walter, A Linear Systolic Array for Exponentiation

2

3

The Systolic Array for Modular Multiplication

Suppose (A×B) mod M is to be calculated, where the radix r of the representations is prime to the modulus M and the non-negative integers A, B arebounded above by, say, 2M . AssumePn−1A, B and M all have at most n digits inbase r, with, for example, A = i=0 ai ri where 0 ≤ ai < r. In practice, forthe systolic arrays here, r will probably be a power of 2 between 22 and 264 ,giving digits of between 2 and 64 bits. Historically ([2],[4],[23]), redundant representations have been used to limit carry propagation and enable parallel digit
operations. This is unnecessary here because numbers are processed digit serially, least significant digit first. This allows in-line conversion back to a standard,
non-redundant representation if necessary.
Montgomery’s modular multiplication algorithm [16] is essential here. It computes R = (A×B)r−n mod M where n is the number of addition cycles in theprocess. The extra power of r is ignored at this point, but will be treated when
exponentiation is reached. It arises because the ith iteration of the algorithm
computes the partial modular productRi+1 = r−1 (Ri + ai B + qi M )where R0 = 0 and qi is a digit chosen to make Ri + ai B + qi M exactly divisible
by r. The j−1st digit of Ri+1 is obtained using the recurrence relation
ri+1,j−1 + r×ci,j+1 = ri,j + ai bj + qi mj + ci,j(∗1)

where ci,j+1 ∈ [0..2r−2] is the carry for propagation up the adder, initialisedwith ci,0 = 0. A model (i, j)th processing element (PE) for calculating this in
the rectangular array [22] is illustrated in Figure 1. The ith row computes Ri+1
from Ri . For simplicity, suppose each PE operates in a single clock cycle. Thenthe (i, j)th PE processes the digits of (*1) at clock cycle time 2i+j, bufferingor storing them as indicated. PE (i, 0) is slightly different as it determines qi as
well, and uses 0 for its input ci,0 .
To ensure the calculation of (*1) is possible, the inputs must be generated
in time. This can be checked using a data dependency graph, but we need exact
times for later. According to the formula, ri,j is generated by cell (i−1, j+1)
at time 2i+j−1, which is just in time for its use by cell (i, j). Also, qi mustbe generated by cell (i, 0) at time 2i ready for use by cell (i, 1) at time 2i+1.
Its definition is qi ≡ −m−1
0 (ri0 + ai b0 ) mod r where ri0 is generated by cell(i−1, 1) at time 2i−1, also just in time. If cell (i, 0) has difficulty in performing
its calculation within the same time as the other PEs then various simplifications
are possible (see [22]): in particular, M might be scaled so that −m−1
0 ≡ 1 mod r
and/or B might be shifted up so that b0 = 0. Section 6 presents more detail forthe latter.
For inputs of up to n digits, the topmost ordinary PE has index j = n−1. For
greater j, the inputs bj and mj are 0 so that no multipliers are necessary in the

4

IEE Computers and Digital Techniques 147 no. 5, Sept. 2000, pp. 323-328
ri,j in @

mj in

R
@
qi out 

?

t

t
?

?

mj registerai out  

bj in

?

qi register 

qi in

t
?

t ai register 
?

ai in

bj register

Multiplierqi × mj

Multiplierai × bj?
?
ci,j+1 out  -ri,j register -

?

Adder
ri,j + qi mj + ai bj + ci,j?
?

mj out?

bj out ci,j register

ci,j in@ ri+1,j−1 out@
R@

Fig. 1. The (i, j)th Processing Element for Array Modular MultiplierPE. Since, by assumption, A < 2M and B < 2M , we can prove inductively thatRi < 3M from Ri+1 = r−1 (Ri + ai B + qi M ) < r−1 (3M + 2(r−1)M + (r−1)M )= 3M . So the (i, n)th PE will generate digit ri+1,n−1 with a carry ci,n+1 of at
most 2. Hence, (assuming a radix of at least 4) we just need a very simple top(i, n+1)th PE which calculates and stores ri+1,n = ci,n+1 (the other inputs to(*1) are zero) and feeds it back and down to the (i+1, n)th PE at the righttime. At the row with i = n we have ai = 0 so that Rn+1 = r−1 (Rn + qi M )< r−1 (3M + (r−1)M ) ≤ 2M . Thus row n generates output which satisfies the
input condition of being less than 2M . This is then suitable for re-input during
exponentiation. Note that extra PEs at the top end won’t affect the calculations
as long as the appropriate most significant digits are initialised to 0.
To obtain a linear, pipeline modular multiplier, only one row of PEs is taken(the ith, for example). For this, the jth PE behaves like cell (i, j) of the rectangular array, computing (*1) at times 2i+j for i = 0, 1, ..., n. Data which waspreviously passed between rows must be re-directed back into the single line ofPEs. So the output ri+1,j−1 from the jth PE is fed into the j−1st PE where
it arrives at exactly the right time for executing (*1). Of course, some control
must be added to initialise and clock the registers correctly and to catch thefinal output rn+1,j−1 at the right time. This is shown in Figure 2.

C. D. Walter, A Linear Systolic Array for Exponentiation
m0j inqi out 

b0j in?

t?

?

mj register?

qi register 

qi0 int ai register ?

a0i in?

bj registerai out 

Multiplierqi × mj

Multiplierai × bj

?

?

Adder
ri,j + qi mj + ai bj + ci,jri,j register - ci,j register

6

mux
0
ri,j
in
ci,j+1 out control out 

6

5

6



t

60
t

?

-

mux

0

6

t

control 6- ri+1,j−1 out
c0i,j incontrol in?

rn+1,j−1 out

Fig. 2. I/O at Time 2i+j for the j th PE of the Pipeline Multiplier

Each PE is only used on alternate clock cycles, the jth one operating on cycles
j, j+2, j+4, etc. So another modular multiplication can be interleaved in the0gaps, say (A0 ×B 0 )r−n mod M 0 , running one cycle, or any odd number of cycles,
behind the first multiplication. Some communication wires and registers mayneed to be duplicated for this and appropriate control added, but the multipliers
and adder are reused. This is also shown in Figure 2, which illustrates the arrivalof updating input for the other, interleaved multiplication.
The linear array may be modified to have all I/O through cell 0. Such a design
would allow the circuit to be incorporated easily into awkward spaces on a chip.
0
Thus, in Figure 3, the interleaved output digits rn+1,j and rn+1,j
are piped backto cell 0. Digit rn+1,j is created at time 2n+j+1 and so, progressing one PE ata time, reaches cell 0 at time 2n+2j+1, showing that it does not overwrite theother output digits on the same pipeline. A more complex arrangement may beneeded for routing the digits of M and B from cell 0. The modulus digit mj isneeded for first use in the jth PE at time j. By sending digits mj out from cell 0
at the rate of two digits per cycle and at the speed of two cells per cycle, mj canleave at time j div 2 and still arrive just in time. This explains why two digitsof M have to pass through each PE and only one is clocked through a register.
However, if the PE is slower than this pipeline, then a simpler arrangement is

6

IEE Computers and Digital Techniques 147 no. 5, Sept. 2000, pp. 323-328

possible, with all the digits of M in a single pipeline advancing by one PE every
half of a cell cycle. A control bit piped along the array to reach cell j at timej−1 enables the correct modulus digit to be captured and loaded into the PE
register and for any other cell initialisation, such as the resetting r0j = 0, to besignalled. The digits of B are treated similarly, as are the digits of M 0 and B 0 ,which are not shown in the figure.
ucontrol out 
b4i+j out 

b4i+j regcontrol


u

H

HH

H

HH
?



b4i+j+1 out 
m4i+j reg  u

m4i+j out 
m4i+j+1 out ?
ureg load

mj in

? ?

0
in
ri,j

m4i+j+1 in
m4i+j+2 in

bj in





j th PE(as in Fig. 2)

ci,j+1 out 

b4i+j+2 in? ?

qi out ai out 

control in
b4i+j+1 in

qi0 ina0i inc0i,j in- ri+1,j−1 out

rn+1,j−1 outucontrol out 0in
rn+1,j? ?
mux?

control- rn+1,j−1 regcontrol in- rn+1,j−1 out-

Fig. 3. Communication for I/O directed through cell 0

3Exponentiation

The cryptographic applications of thisarray require exponentiating plaintext or
Pd−1iciphertext T to some power ∆ =i=0 δi 2 of d bits, say. This can be doneiby computing
successive squares Si = T 2 mod M and cumulative products
Qi−1j
Pi = j=0 T δj 2 mod M using the parallel modular multiplications:
Si+1 ← Si ×Si mod M
Pi+1 ← Pi ×Si0 mod M
where Si0 = 1 f or δi = 0
and Si0 = Si f or δi = 1

C. D. Walter, A Linear Systolic Array for Exponentiation

7

If Montgomery’s algorithm is used then each multiplication picks up an extra
factor r−n where n is the number of addition cycles per multiplication. Thisis compensated for by pre-Montgomery-multiplying T by r2n mod M so thatT rn mod M is fed into the exponentiator. Each multiplication or squaring maintains the factor rn so that T ∆ rn mod M is output. The only necessary postprocessing is then another Montgomery multiplication, this time by 1, whichremoves the unwanted rn .
Both the square and multiply operations can be calculated in parallel by
the array and successive pairs pipelined with virtually no intervening breaks or
buffering. Thus the array should be very well suited to exponentiation, as eachcell can then be almost fully utilised, performing its task on almost every cycle.
The only reservation for the scheme here is that the multiplications by 1 areincluded here but generally omitted. (Multiplication by 1 here would actually bedone via Montgomery multiplication by rn .) Consequently, on average the arrayis utilised at only 75% of its full capacity. However, the exponentiation will still
normally have to perform d squarings and therefore must take at least the timeused here (but see [6]).
A PE of the exponentiating array is illustrated in Figure 4. In terms of theprevious notation, the interleaved multiplication sequences have
A = B = Si

R = Si+1A0 = Si0 (= rn or Si )B 0 = PiR0 = Pi+1

where the choice for A0 is determined by the exponent bit δi . The array is
initialised for the first two simultaneous multiplications by supplying M 0 = M
and A = B = T rn mod M (= S0 ), setting B 0 = rn (= P0 ) and computing
A0 from A, as defined. Most of this and the subsequent operation is just as in
Figure 2. The main difference is that the digits of B and B 0 are also needed for
immediate consumption by the neighbouring cell.
For the interface between successive multiplications, suppose the products
R = Si and R0 = Pi have just been computed and are about to be used as the
inputs B and B 0 for the next pair of multiplications. Since the ith multiplication0
is offset by 2in clock cycles, the jth output digits rn,j and rn,jare generated bycell j+1 at times 2in+j−1 and 2in+j respectively. These digits become inputs
bj and b0j for the following multiplications. They must be ready for use by cellj at times 2in+j and 2in+j+1 respectively. This is just possible with no gap
between successive multiplication cycles. So there is no need for buffering thedata further nor is there any idle time in the hardware.
The other inputs A and A0 must also be checked for timeliness. A is initialised
digit serially from cell 0. Thereafter, the output R = Si and Si0 provide theinputs A and A0 . The digit rn,j is computed at time 2in+j−1 and reaches cell
0 at exactly the right time 2in+2j for its first use there as aj . This leaves one
clock cycle for cell 0 to compute a0j from aj using A0 = δi A + δi rn . The final
output of the array, T ∆ mod M , is a value of R0 , and so can be collected seriallyfrom cell 0 after a multiplication by 1 to remove the extra power of r.

8

IEE Computers and Digital Techniques 147 no. 5, Sept. 2000, pp. 323-328
mj in

tj in
sj or pj

control out qi out 

?

t

?

?

t
-

mj register

control control in?

qi register 

qi0 in?

t ai register 
?

?

mux

?

bj register

S or S 0 digit out Multiplierqi × mj

Multiplierai × bj

6?
ri,j register -

?

Adder
ri,j + qi mj + ai bj + ci,j

 ci,j register6mux

S or S 0 digit in

6



0
in
ri,j
66 0
ci,j+1 out tcontrol out 
t-sj or pj reg
S or P digit in

-

mux

0

66

t

control t?

sj−1 or pj−1t- ri+1,j−1 out
c0i,j incontrol in- S or P digit out

??
mux

?


-

Fig. 4. j th PE for Exponentiation

As in Figure 2, the main control bit is set by cell 0 on every 2nth cycle andreaches the jth PE at time 2in+j−1 (i = 0, 1, 2, ...). It indicates that the cellshould update its current bj to the incoming rn,j , and make a similar change
to b0j on the next clock tick. A similar control bit indicates when the outputs
0rn,j and rn,jshould be captured for routing to cell 0. If cell 0 is now slower
than the normal PE, extra cycles can be inserted between successive multiplications to allow it to complete without slowing down the clock. Specifically, each
multiplication is just allowed to run on as necessary before starting the next one(perhaps with some updating for the next multiplication) but the result is still
extracted at the same point. This is a minimal extra cost as n is relatively large.

C. D. Walter, A Linear Systolic Array for Exponentiation

4

9

External Connections and Comparative Study

Hardware for modular multiplication will probably either reside on a dedicatedchip or be part of a larger digital signal processing chip. In both cases the I/O
bandwidth is likely to be limited. Hence the external communication problems
will be similar. With little if any loss of generality, we therefore phrase the discussion in terms of a dedicated chip. It also suffices to consider only exponentiations
since data rates for multiplication sequences will be about twice those for exponentiations to the power 1 (because the exponentiation may perform a uselessfinal squaring).
The connections of the array to the external world are fairly simple: the inputs
are M , T , ∆ and perhaps r2n mod M , and the output is R0 = T ∆ mod M
after post-processing. Each of these is required, respectively generated, digit
serially. Corresponding input and output digits are separated by time 2dnt.
At worst, three digits are input and one digit output from the array over theoperation time t of a cell. In practice, chips have relatively few pins for I/O andcommunication with the rest of the world may be at a slower clock speed. Henceexternal communication of large integers is in effect limited to the sequential
I/O of a few bits over a number of clock cycles. Providing the radix r is not toolarge, the internal clock not too fast, and also the number of pins not too small,the chip I/O will be fast enough not to hold up the exponentiation and also fastenough to avoid the need for more than minimal buffering of the I/O. Current
internal chip and communication technologies are sufficiently in line with eachother that these conditions are easily satisfied.
A desirable choice for r might involve digits with the same range as normal
machine arithmetic, say 32 or even 64 bits of input, so that PEs can use astandard off-the-shelf multiplier design containing years of optimisation (e.g.
[18]) and the I/O requirements might match internal bus speeds. However, alarge RSA word length of perhaps 210 bits leads to huge usage of chip area from,for example, 64 32×32-bit multipliers. Then, assuming a multiplication takes 4cycles, the throughput for a full length exponent is 210 bits (=text length) every
218 clock cycles (= 2dnt = 2×210 ×25 ×22 cycles). On a 400MHz clock, thiswould lead to a data decryption rate of about 1.5Mbits/sec. After scaling fortechnology differences, this is essentially the same as the programmable active
memory (FPGA) technology of Shand et al. [21] which ran at 40MHz and gavea throughput of 165Kbits/sec for 210 -bit inputs and keys. Although they used apipelined version of Montgomery’s algorithm, they also made use of a fourfold
speedup from using the factorisation of the modulus and the Chinese Remainder
Theorem to divide the operation into two parts running in parallel. This isbalanced by using about four times the silicon area here (about 400K gatesas opposed to 100K for their equivalent ASIC) to obtain similar throughput
per clock cycle. Of course, such large multipliers, which take several cycles tooperate, can be pipelined. With minor overhead, we could build each PE with

10

IEE Computers and Digital Techniques 147 no. 5, Sept. 2000, pp. 323-328

a single, pipelined multiplier. Then both the multiplications could be computedin 5 cycles rather than 4, thereby reducing the Area×T ime cost by almost half.
A 56×64 bit integer multiplier uses about 3% of a large chip in today’s technology [20]. An array with r = 256 would require about n = 18 PEs and hence 36
such multipliers (18 if pipelined) plus a little more area for the communications.
This puts it on the limit of current technology. Again, assuming it is a 4-stage
multiplier, we obtain only an average exponentiation throughput of 1 bit per
27 cycles. If the chip also has a frequency multiplier of 4, then RSA decryption
is still a mere 1 bit per 25 internal bus cycles − much below the bus capacity.
However, the I/O comes in bursts, 56×25 bits plaintext input per bus cycle forthese parameters, plus the same again for the modulus if that is also needed.
At the opposite extreme, the smallest choice of r = 2 probably suffers fromtoo high an overhead in terms of storage area and time spent clocking latches. As
the total area required is only a very small constant multiple of the area required
to hold the input data, the choice is close to the minimal possible area needed toperform exponentiation. Slightly larger r, say 4 or 8, are of more interest. The
former would require a PE with two 2-bit multipliers and containing about 26
gates. There would be 29 PEs for 210 -bit inputs, yielding an array with similararea to only a couple of 64-bit multipliers (about 212 full adders each). The array
would perform decryptions in 2dnt = 220 of its cycles, whereas the two 64-bit
multipliers could complete a modular multiplication in 28 of their cycles and soa decryption in an average of 1.5×218 of its much longer cycles. The computing
powers are therefore roughly similar for comparable areas. Thus the array here
appears to be at least as cost effective. However, with only local connections andregular nature, layout is much more straightforward and it can be adjusted moreeasily to fit unusually shaped areas on the chip. Its parameter r can be chosen
to make it utilise fully all available free space and, as we shall see, it is moreresistant to differential power analysis attacks.
Throughput for the array here is essentially the same as for the parallel digit
implementation of modular multiplication described in [24] if it uses the same
basis r and identical circuitry for computing digit sums and products. The main
advantages of the exponentiation process here are that a considerable digit distribution area is saved, and each modular multiplication avoids the small numberof extra iterations which are required there to enable the timely arrival of the
distributed digits. Thus, this array should have slightly better throughput andshould have noticeably smaller area. Moreover, in a design like that of [24], all the
input and output digits are consumed, respectively generated, simultaneously.
Since the number of I/O bits in an RSA cryptosystem exceeds the number ofpins available by an order of magnitude, the I/O data must be supplied seriallyand buffered on the chip. This decreases the performance of [24] as far as latency
is concerned, at best to what the array here produces, and makes the area discrepancy even greater. In conclusion, the design here seems to out-perform thebest modular exponentiation circuits which employ parallel digit processing andmultiplication via repeated addition.

C. D. Walter, A Linear Systolic Array for Exponentiation

5

11

Elliptic Crypto-Systems

The standard integer RSA algorithm has a corresponding version for elliptic
curves [10], [15] over a finite field F. The above hardware design is particularly
well suited to the case when this field has odd prime order p: elements are
represented by integers modulo p rather than modulo M , but otherwise thearithmetic is identical.
Integer RSA uses the multiplicative group of residues prime to the modulus M , whilst elliptic RSA uses a group of points on the elliptic curve which is
generally written additively. Encryption and decryption are performed by multiplying the message point (x, y) on the chosen elliptic curve y 2 = x3 +ax+b by
a key d. This is the analogue of exponentiation to the power d and is achievedby the equivalent of the square and multiply algorithm in Section 3. Doubling(x, y), which corresponds to squaring, gives the point (x0 , y 0 ) defined, in the caseof characteristic greater than 3, by (see [11]) :
0



x =

3x2 + a
2y

2
− 2x



0

y =

3x2 + a2y(x−x0 ) − yand the sum (x0 , y 0 ) = (x1 , y1 ) + (x2 , y2 ) is given by
0

x =



y2 − y1x2 − x1

2− x1 − x2

0

y =



y2 − y1x2 − x1(x1 −x0 ) − y1

By far the most expensive operations here are inverting y and x2 −x1 . Agnew,
Mullin & Vanstone [1] recommend swapping the affine co-ordinates (x, y) for
projective ones (x, y, z) so that no inversion is required until encryption is completed and affine co-ordinates must be recovered. For odd prime fields, elliptic
point doubling using projective co-ordinates requires 10 field multiplications andelliptic point addition 16 field multiplications (see [25], A.10.4 and A.10.5). The
miscellaneous other operations (field additions, subtractions and scalar multiplications) are trivial to perform in one cycle each.
The extra arithmetic in doubling and adding points means use of the array here is more complex: there are a few more registers and so extra control.
However, the schedule for doubling and adding elliptic points is simpler thanthat for squaring and multiplying in the integer case. Two additions from one
or other can always be done simultaneously. So doubling and adding of points
can be arranged sequentially instead of interleaved, yet still using the array fully.
Consequently, additions need only done when necessary. The final inversion torecover affine co-ordinates can be done by exponentiation, using the array in thesame way as before, without change and with the same efficiency. Overall, withinversion using only a fraction of the total time, the array is almost fully utilised.

12

IEE Computers and Digital Techniques 147 no. 5, Sept. 2000, pp. 323-328

6

Re-Structuring for 100% Use

For larger radices, the hardware cost is considerable. We suggest two ways inwhich the number of multipliers might be halved. First, the equation (*1) may
be split into two almost identical sequential multiply-accumulate operations with
one multiplication each:ti,j + r×di,j+1 = ri,j + ai ×bj + ci,jri+1,j−1 + r×ci,j+1 = ti,j + qi ×mj + r×di,j+1

(∗2a)
(∗2b)

where ti,j is an intermediate digit value with carry di,j+1 . A PE with two multipliers would perform the multiplications of (*1) in parallel. The cheaper solutionof one multiplier used twice to perform (*2) will take twice the time, but, withjust half the area, the product area×time is unchanged. In that context a larger
cell 0 with two multipliers working in parallel could dispatch the required digits
in time without any problems. If the single multiplier is large enough, it might
be pipelined to perform the two multiplications in less than double the time,
thereby reducing the area×time product.
Secondly, exponentiation is slightly unsatisfactory for a couple of reasons.
Only the standard square and multiply method is well suited to the array here,
and, on average, it still leaves the PEs unused for 25% of the time. To solve this,the array can be restructured to make each PE work on the same multiplicationfor every cycle. The original PE functionality is split in two for using a single
multiplier. Equation (*1) is re-written as
ti,j = ai ×bj
ri+1,j−1 + r×ci,j+1 = ri,j + ti,j + qi ×mj + ci,j

(∗3a)
(∗3b)

by introducing intermediate values ti,j . Both (*3a) and (*3b) are executed by
the jth PE, the first on cycle 2i+j−1 and the second on cycle 2i+j. Outputs ri,jand ci,j are produced and used on the same cycles as before. An extra control
bit selects between the two functions of the PE causing a negligible increasein execution time. Once r increases above 4, the area gained from halving thenumber of multipliers quickly outweighs the small area for extra control. Thissoon gives a hardware saving of over a third. However, exponentiation takes
only 50% longer than before because the multiplications and squares are runsequentially, but no useless multiplications by 1 are done. So, for larger r, thismay be a cost effective solution as both area and area×time are improved.
Digits ai and bj need to be available one clock cycle earlier than before.
Multiplications and squarings alternate so that Pi is only required as an input
on every other multiplication. Its value must be buffered with an extra registerin each PE. It will certainly be available in time for use as the B input. Si is usedin every multiplication as the A input and for squarings also as the B input. Its
digits rn,j are calculated at time 2in+j−1 and reach cell 1 for use as aj at time
2in+2j. It doesn’t reach cell 0 in time, but this is not important if b0 = 0. The

C. D. Walter, A Linear Systolic Array for Exponentiation

13

condition b0 = 0 was needed before to simplify cell 0 to help it operate in time.
The same solution is employed here, namely to shift B up. B is input with ahardwired shift up to make b0 = 0. The cost is cheap: at most one extra iteration
per multiplication, which is required to ensure the output is under 2M , and adifferent power of r being introduced into Montgomery products. As part of theshifted input B = rRn , rn,j is calculated at time 2in+j−1 and now first required
as bj+1 in a0 bj+1 at time 2in+j. As before, the digit qi ≡ −m−10 ri,0 mod r iscomputable by cell 0 at time 2in, the cycle after ri,0 is generated.
Other exponentiation schemes now become possible. In particular, the m-ary
method [9] requires a pre-computed list of m−1 products. These can be stored
in cyclic shift registers at cell 0 and loaded through that cell in the same way as
Si or Pi under the square and multiply scheme.

7

Differential Power Analysis

Differential power analysis (DPA) [13] is a method for attacking cryptographic
hardware through variations in current arising from data dependent calculations.
Typically an attack might be made against a smartcard or embedded cryptographic device containing a private key. The presence of a high noise-to-signal
ratio in the current means that measurements are best made by averaging overa large number of cases. When the square and multiply method is used, theattacker would hope to average over a large enough set of exponentiations to beable to separate squares from multiplies and thereby read off the secret exponent.
Similarly, where the same argument A, perhaps related to a chosen plaintext,
is used repeatedly in calculating products A×B it might be possible to averageover the many values of B to identify some property of A.
In standard implementations which use a single, large multiplier the digitsof an operand A are very clearly separated out into the discrete time intervals
when they are used. Also, with such hardware, squarings and multiplications
have clearly defined beginnings and endings. With the systolic array described
here, all multiplications merge into each other. First, successive multiplications
overlap by about 2n cycles. Also, at any instant, all the PEs which are computing
a digit product of one multiplication A×B are using different digits of A, not thesame one. Hence the power variation is very much in line with the average digitof A rather than a succession of ups and downs representing the sequential useof distinctive individual digits of A. This makes the recognition of a particular
operand A much more difficult in DPA, and the distinction between squares andmultiplies irrelevant.

14

IEE Computers and Digital Techniques 147 no. 5, Sept. 2000, pp. 323-328

8Conclusion

We have constructed three array modular multipliers and exponentiators parametrised by the radix r of the input representation, namely those implementing
equation (*1) directly, and those implementing (*1) via equations (*2) or (*3).
Each is well suited to the modular arithmetic of many encryption schemes, andalso RSA over elliptic curves of non-zero characteristic. For larger r, the last
design is not much more than half the size of the first, but uses only 50% moretime. However, in all cases a choice of r can be made to make maximal use of thechip area available for the array, and thereby minimise latency. The processing
elements consist of standard components, the main one being one or two multipliers for base r digits, which might be picked off the shelf. As the designs arelinear with I/O through one end, the circuits are easy to lay out and can evenbe bent around corners to fit into any odd-shaped space. The time per exponentiation is O(ndt) where the exponent has d bits, the modulus and input text
have n digits base r and t is the execution time for the digit multiplier. Thereis no overhead for short inputs: they are proportionally faster and use the time
expected from supplying smaller values of n and d.
Unlike parallel digit implementations using the classical modular multiplication algorithm, the array can be implemented using non-redundant representations, and yet there are no delays for carry propagation. This both increases
clock speed by reducing critical path lengths and reduces area by eliminating
redundancy and much of the communication wiring. Only local communicationis required. There is no costly simultaneous digit distribution across the wholecircuit. Furthermore, another efficiency gain comes through the sequential digit
I/O, which helps to reduce the necessity of buffering data. The design now makes
real time RSA decryption with 1024 bit keys closer on a single chip. Finally, thearrays will be of particular use in set top boxes and smartcards since they seemto give much greater protection against attacks using differential power analysis.

References[1] G. B. Agnew, R. C. Mullin & S. A. Vanstone, “On the Development of a Fast
Elliptic Curve Cryptosystem”, Proc. Eurocrypt ’92, R. A. Rueppel (ed.), Lecture
Notes in Comp. Sci. vol. 658, 1993, pp. 482-487, Springer-Verlag.
[2] 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.
[3] W. Diffie & M.E. Hellman, “New Directions in Cryptography”, IEEE Trans. Info.
Theory, vol. IT-22, no. 6, Nov 1976, pp. 644-654.
[4] S. E. Eldridge, “A Faster Modular Multiplication Algorithm”, Intern. J. Computer
Math., vol. 40, 1991, pp. 63-68.
[5] T. ElGamal, “A Public-Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms”, IEEE Trans. Info. Theory, vol. IT-31, no. 4, 1985, pp. 469-472.

C. D. Walter, A Linear Systolic Array for Exponentiation

15[6] T. Hamano, N. Takagi, S. Yajima & F. Preparata, “O(n)-Depth Modular Exponentiation Circuit Algorithm”, IEEE Trans. Comp., vol. 46, 1997, pp. 701-704.
[7] L. B. Jackson, J. F. Kaiser & H. S. McDonald, “An Approach to the Implementation of Digital Filters”, IEEE Trans. Audio & Electroacoustics, vol. AU-16, 1968,
pp. 413-421.
[8] Y. J. Jeong & W. P. Burleson, “VLSI Array Algorithms and Architectures for
RSA Modular Multiplication”, IEEE Trans. VLSI Systems, 1997, vol. 5, no. 2, pp.
211-217.
[9] D. E. Knuth, The Art of Computer Programming, vol. 2, “Seminumerical Algorithms”, 2nd Edition, Addison-Wesley, 1981, pp. 441-466.
[10] N. Koblitz, “Elliptic Curve Cryptosystems”, Mathematics of Computation, vol.
48, 1987, pp. 203-209.
[11] N. Koblitz, A Course in Number Theory and Cryptography, Graduate Texts in
Mathematics, vol. 114, Springer-Verlag, 1987.
[12] P. Kocher, “Timing Attacks on Implementations of Diffie-Hellman, RSA, DSS,
and Other Systems”, Advances in Cryptology, Proc Crypto 96, Lecture Notes in
Computer Science, vol. 1109, N. Koblitz editor, Springer-Verlag, 1996, pp 104-113.
[13] P. Kocher, J. Jaffe & B. Jun, “Introduction to Differential Power Analysis andRelated Attacks”, at www.cryptography.com/dpa, 1998.
[14] 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.
[15] V. Miller, “Use of Elliptic Curves in Cryptography”, Proc. CRYPTO ’85, H. C.
Williams (ed.), Lecture Notes in Comp. Sci., vol. 218, 1986, pp. 417-426, SpringerVerlag.
[16] P. L. Montgomery, “Modular Multiplication without Trial Division”, Math. Computation, vol. 44, 1985, pp. 519-521.
[17] National Institute of Standards and Technology, “Digital Signature Standard”,
NIST FIPS PUB 186, May 1994.
[18] S. F. Obermann, H. Al-Twaijry & M. J. Flynn, “The SNAP Project: Design of
Floating Point Arithmetic Units”, Proc. 13th IEEE Symp. on Computer Arith.,
Asilomar, CA, USA, 6-9 July 1997, IEEE Press, 1997, pp. 156-165.
[19] R. L. Rivest, A. Shamir & L. Adleman, “A Method for obtaining Digital Signatures
and Public-Key Cryptosystems”, Comm. ACM, vol. 21, 1978, pp. 120-126.
[20] E. M. Schartz, R. M. Averill III & L. J. Segal, “A Radix-8 CMOS S/390 Multiplier”, Proc. 13th IEEE Symp. on Computer Arith., Asilomar, CA, USA, 6-9 July
1997, IEEE Press, 1997, pp 2-9.
[21] M. Shand & J. Vuillemin, “Fast Implementations of RSA Cryptography”, Proc
11th IEEE Symp. on Computer Arith., Windsor, ONT, Canada , July 1993, pp.
252-259.
[22] C. D. Walter, “Systolic Modular Multiplication”, IEEE Trans. Comp., vol. 42,
1993, pp. 376-378.
[23] C. D. Walter & S. E. Eldridge, “Hardware Implementation of Montgomery’s Modular Multiplication Algorithm”, IEEE Trans. Comp., vol. 42, 1993, pp. 693-699.
[24] C. D. Walter, “Space/Time Trade-offs for Higher Radix Modular Multiplication
using Repeated Addition”, IEEE Trans. Comp., vol. 46, 1997, pp. 139-141.
[25] “Standard Specifications for Public Key Cryptography”, IEEE Standard P1363,
Draft Version 7, IEEE, New York, 1997, 1998.