Moduli for Testing Implementations of the RSA Cryptosystem
Colin D. Walt er
Computation Department, U.M.I.S.T.,
PO Box 88, Sackville Street, Manchester M60 1QD, U.K.
www.co.umist.ac.uk

reasonably certain of their correctness.
To ourknowledge there is currently no bench mark suite of test
values for the correctness of an RSA cryptosystem
although plans exist for a correctness validation program
in connection with ANSI X9.31-1998 [8].
Thediscussion here aims to contribute some ideas in thisdirection. Although most of the discussion is aimed at
hardware, many of the observations are directly
applicable also to software systems.
Encryption and decryption in RSA are achieved byexponentiating the plain, respectively encrypted, text T to
the power of one of two keys e or d modulo a product M
of two large primes: Te ≡ T mod M or Td ≡ T mod M
respectively. In order to recover the plain text from the
obscured text, the two keys d and e must have theproperty Tde ≡ T mod M, which is guaranteed by
selecting them so that de ≡ 1 mod φ(M) for the Euler
phi-function φ.
The modular exponentiation is achieved by a sequenceof modular multiplications which are themselves
performed through a repetition of modular additions.
Typically, efficient implementations of RSA do not
reduce intermediate calculations to yield a least nonnegative residue modulo M because this involves fulllength carry propagation. Instead, the partial results are
stored in a redundant form bounded by a small multipleof M. The multiple of M to subtract (or add) in order tokeep the result within this range is decided by the firstfew (the most significant) digits in the traditionalalgorithm [1] and the last few (the least significant)digits if Montgomery’s method [4] is used [2,7]. To
check fully the correctness of such implementations, wetherefore need at least a set of moduli which include all
possible choices for the top few digits and, separately, allpossible choices for the bottom few digits. The majorityof this paper is concerned with the generation of such
moduli.

Abstract
Comprehensive testing of any implementation of the
RSA cryptosystem requires the use of a number of moduli
with specific properties. It is shown how to generate asufficient variety of these to enable testing which will
justify high confidence in the correctness of both thedesign and the operation of hardware implementations.
The tests avoid the necessity of another implementation
for comparison. Many of these moduli are also suitable
for testing software implementations. Furthermore, themethods apply equally well to other similar modular
arithmetic
based
cryptosystems
which
use
exponentiation, such as Diffie-Helman key exchange.
Key Words: Computer arithmetic, cryptography, RSA
modulus,testing,
correctness,verification,
implementation validation benchmark.

1 Introduction
The RSA cryptosystem [5] is widely used for key
exchange and increasingly for the long term storage ofsensitive data. A large number of such systems havebeen designed and built in both software and hardware.
In a quest for greater efficiency, software
implementations can often be too complex to be fully
verified and hardware implementations can havefabrication errors that need to be screened out. Moreover
faults can arise during operation in both hardware andsoftware systems for various reasons. A test suite
containing a variety of moduli is therefore required toenable development, fabrication and in-service testing ofcorrectness. We show how to build such a test suite.
This suite aims to provide exhaustive testing of the main
components expected to form the implementation as well
as exercising all other components sufficiently to be78

C.D.Walter

Intermediate digits in any encryption/decryption will
normally all be processed in the same way by a repeateddigit slice. So the correctness of this aspect of theimplementation’s design might reasonably be verified bylooking at just one of the most significant or leastsignificant digit slices, and ensuring that all possible
inputs are generated for it. The moduli required above
for checking the multiple of M for the modular
subtraction should also cover this part of testing if
sufficiently many end digits are considered.
Fabrication or failure errors can occur at any point in
hardware implementations. It may thus be useful to havemoduli in which any short subsequence of internal digits
can be specified so that specific digit slices can be tested.
Hardware generally re-aligns the modulus by a left or
right shift. So any digit slice can normally be tested
through the most or least significant digits of themodulus just by varying the total number of its digits.
We assume that this is the case so that only the end digits
and total length of M need to be specifiable. Indeed, by
varying the length of M we can check the correctness ofsuch shifting, and the correctness of the associatednumber of addition cycles.
The third main aspect of implementation is thecorrectness of the exponentiation algorithm. In a later
section we will discuss the adequacy of testing this using
the exponents which occur naturally for the moduli
which are generated.
Clearly, if the implementation is just a modular
multiplier with external access to set any digits,
including carries, then a number of single multiplications
may suffice for full testing. Otherwise, when internal
carries are inaccessible, or only one input T can bepresented to the multiplier, it may be only possible tocarry out exponentiations in testing. Then, whereas it ispossible to verify the exponentiation output against thesame computation under a different system, it may bemuch easier and cheaper to make use of the obvious selftest analogous to Tde ≡ T mod M, namely the property
Tφ(M)+1 ≡ T mod M which is used to determine a suitable dfrom a given e.
With these three implementation aspects to consider,
we therefore initially seek moduli M with the threeproperties:
P1) Any short subsequence of end digits can be
specified (most or least significant digits) for M of
any length;
P2) φ(M) can be computed easily; and either
P3) Tφ(M) ≡ 1 mod M holds for a large known set of T,orP3') Tφ(M)+1 ≡ T mod M holds for a large known set ofT.

Under the very reasonable assumption that any errors
will tend to propagate wildly, the implementation canφφthen be tested by computing T (M) (mod M) or T (M)+1 (modM) and comparing it with the expected result for a
sufficient variety of choices for M and T.
In the next section we derive properties which ensure
moduli satisfy P3 and also guarantee a straightforward
construction to obtain P1 and P2. After performing a
construction which enables P1 to hold simultaneously atboth ends, we look at how to make use of such moduli toform an appropriate test suite, how errors might
propagate and how probabilistic arguments might enable
fewer moduli to be used than one for every possible
sequence of end digits. Some consideration is given toalternative constructions, the time complexities involved,
and the implementation errors that may not be covered bysuch a test suite.

2 The Order Property mod M
Most of the results used in this section can be found inany elementary number theory text such as Chapter 1 of[3]. The classes of residues prime to M form a
multiplicative group of order φ(M).
Hence, by
Lagrange’s theorem (see any book on group theory),
T (M) ≡ 1 mod M
φwhenever T and M have no common factor. Thus P3 andP3' will hold. Euclid’s algorithm can easily determine
whether a given T satisfies the co-primality condition. In
the case of M being prime, this is just Fermat’s Little
Theorem, which Euler generalised toTφ(M)+1 ≡ T mod M
for prime M in order to cover all T, including the casewhen T shares a factor with M. For general M, by the
Chinese Remainder Theorem, the property Tφ(M)+1 ≡ T
φmod M holds if, and only if, T (M)+1 ≡ T mod Q holds foreach maximal prime power Q dividing M. Moreover,since φ is a multiplicative function, φ(Q) divides φ(M) for
each such Q. So Tφ(M)+1 ≡ T mod Q holds if Tφ(Q)f+1 ≡ T
mod Q for every f. When M is square-free, as it is in the
RSA cryptosystem, each relevant Q is a prime. Then, by
φvirtue of Fermat’s Little Theorem, T (Q)f+1 ≡ T mod Q
holds for every f when T is prime to Q and also,
otherwise, because both sides are 0 modulo the prime Q.
Thus M being square-free guarantees that Tφ(M)+1 ≡ T
mod M for all T. This proves:
THEOREM 1.
i) Property P3' holds for all T if M is square-free;ii) The congruences of P3 and P3' hold for any T and M
which are relatively prime.

79Proc. 14th IEEE Symposium on Computer Arithmetic, Adelaide, 14-16 April, 1999, IEEE Press, 1999, pp 78-85.

Clearly the congruences of P3 and P3’ hold for at least
the φ(M) classes modulo M which are prime to M andthis will be a high proportion of all classes if M is notdivisible by any small primes. Later we will want to beable to choose T explicitly to be 1, 2 or M−1. As M isgenerally odd, they will satisfy this theorem.

exponentiation by φ(M) may not fully exercise the nonsquaring multiplication hardware, nor allow a sufficientversatility in our later choice of T which are prime to M,
nor perhaps even be a legitimate choice for the
implementation. So a slightly different choice for M isdesirable.
Thus, alternatively, assume M has the form

3 A Construction for Moduli M

M = mP

where P = ∏it = 1 (r ni ± 1) and k = ∑ it =1 ni

The ni and the signs will be chosen so that the productjust exceeds rk and each factor has a known prime
decomposition. The examples section illustrates how thefactors of P may be chosen and even varied from thegiven form in order to obtain specific factorization orcongruence properties. Thus rni±1 may be replaced by aset of values around rni, if convenient.
We must consider how to choose the signs so that m isindeed the initial sequence of most significant digits. By
choosing each ni sufficiently large, each corresponding
factor of P is close to rni so that P is close to rk and M isclose to mrk. The hope is that P should just exceed rk sothat it has a leading digit of 1 followed by a sufficientnumber of 0s to guarantee that the top digits of M
coincide with those of m.
With only + signs in the factors, the product P will
exceed rk whilst with only minus signs P will be less than
rk. Thus the signs can be systematically changed one by
one from + to – in order to make P approach rk moreclosely, stopping before the product falls below rk. The 2t
choices give considerable scope for picking P very close
to rk or giving P with other desirable properties. In
particular, enough minus signs might be chosen so thatchanging the sign in a pre-determined factor changes P
from more than rk to less than rk. Alternatively, so manysigns could be changed from + to – that no further signchange keeps P above rk.
Suppose rn+1 is one of the factors with a + sign, andassume m has at most n–1 digits. Let P’ denote theproduct given by changing rn+1 to rn–1. Assume that
this sign change makes P’ less than rk. Then P’ < rk < P
and henceM = mP = mP’(rn+1)/(rn–1)< mrk(rn+1)/(rn–1)= mrk + 2mrk/(rn–1)≤ mrk + mrk+1/(rn–1)< (m+1)rk

The key property from which the RSA cryptosystemderives its strength is the difficulty of deriving φ(M) fromM. In effect this requires the prime factorization of M.
Hence, if we need to know the value of φ(M), it follows
from the multiplicative nature of φ that the best approachto constructing moduli M is via a product of factors forwhich φ can be easily found.
Implementations of the arithmetic for RSA
encryption/ decryption rarely make use of any
factorization properties of M. Hence we should not feelbound to limit the choice of M to a product of just twolarge primes. The only exception is where the Chinese
Remainder Theorem is used, and we return to this point
below (Section 7). Thus there should be no need togenerate large primes in order to obtain suitable M;
products of small factorisable numbers will normallysuffice. However, we may need to exclude some primes
from dividing M. The most obvious case is the prime 2:
many implementations may assume M is odd because thisproperty holds for the moduli used in the RSA
cryptosystem.
Suppose numbers are represented using radix r. This
will normally be a small power of 2. It corresponds tothe smallest group of bits processed uniformly in therepeated arithmetic operation which performs a modular
addition.
r = 2 or 22 is typical for hardware
implementations and r = 232 for software
implementations which use the built-in machinearithmetic. Suppose also that M has a standard, nonredundant representation, that is, all its digits are in therange 0..r−1.
Let m be the short sequence of several digits which wewish to have as the most significant digits of M.
Normally our construction for M will make m a factor of
M. So, if m would thereby contribute undesirable factors
to M, it must be extended to have one or two more digits
which are then chosen to avoid such factors. Further, let
k be the number of digits in M other than those which are
in m.
A tentative initial proposal for M is to take 0 for eachof the digits of M below the required m. Then M = mrk.
Although φ(M) is easy to compute, it will have a highpower of 2 (assuming r is a power of 2). Therefore

because 2 ≤ r and mr ≤ (rn−1–1)r < rn–1. But (m+1)rk –1
is the largest number with leading digit sequence m.
Consequently,
THEOREM 2. Take M = mP where P is the productdefined above. Suppose n is such that rn+1 is a factor

80

C.D.Walter

digits and that ni ≥ n for each i. Then, viewing P as apolynomial in r, the lowest non-constant power of r in P
has exponent at least n. So its lowest n digits except thelast are all 0 and the last digit is 1. This means M = lP
will have l as a digit subsequence at its least significant
end.
One objective is to construct M with m at the mostsignificant end and l at the least significant end. So
suppose M has the formof P and changing its sign would make P less than rk.
If m has at most n–1 digits then the leading digits of
M are those of m.
In practice, the looseness of these inequalities for thefactor rn+1 means that more often than not m can have nor even more digits, all of which will appear at the startof M. Indeed, to obtain more available digits for m, thesigns of as many factors as possible could be changed.
Numbers of the form rn±1 include the Fermat andMersenne primes (when r is 2). Their factorization has
been widely studied. Clearly by algebra rf±1 is a factor of
rn±1 when the signs are the same, f divides n, and n/f is
odd if the shared sign is +. Also by algebra, rf+1 is afactor of rn–1 when f divides n and n/f is even. Since no
exponent ni is required to be very large, it is reasonable toassume that all the factors of P have known prime
decompositions, so that φ(M) can be calculated easily.
Furthermore, with care it may be possible to make M
square free by noting that the highest common factor
between rn±1 and rn’±1 is 1, 2, rg±1 or 2(rg±1) where g is
the greatest common divisor of n and n’. (This is derived
by repeatedly noting that the highest common factor
divides the sum or difference of such numbers, but not
the power of r which appears in that sum or difference.)
Thus an obvious choice for the ni is to take them pairwise
coprime.
As examples below illustrate, the choice of factors
rni±1 can be varied. Each factor could offer a choice
between any two factorisable numbers where one is justabove rni and the other just less than it. The closeness to
rni in enough cases will make P near enough to rk to
obtain m in the leading digits of M. As before, from an
initial choice of the larger factor in each case, the factors
are replaced by the smaller alternative, stopping while P
is still greater than rk or when changing a selected factor
would make P less than rk.
Any of these constructions enables P2 to be satisfied,
as well as P1 where the specified digit subsequence m
appears initially. Moreover, the product P need only be
computed once and then used for all choices of theinitial, most significant digits m.

M = mrnP + lP’
where n is the number of digits in l. P is constructed asin the previous section so that mrnP provides m in theright place for the most significant digits of M. Of
course, its n least significant digits are all 0. P’ will be
constructed as in the previous paragraph to make lP’provide l for the least significant digits, but not quite
large enough to prevent the digit sequence m from beingat the most significant end of M. We will also choose P
and P’ to share most of their factors so that φ(M) can beeasily found. This is done by starting with P’ = P. If thischoice of P’ is too big, factors are removed one by one
until the remaining product P’ is small enough not toaffect the topmost digit sequence m. The lowest digit of
P’ as a polynomial in r is then ±1. So one more factor(with a −) is removed if necessary to produce +1 as thelowest digit. This resulting P’ can be further adjustedwith other factors if desired, providing the main
properties are retained. In consequence, P = pR and P’ =p’R for some small p and p’ where R is the product of thefactors common to P and P’ which remain after
modifying P to P’. This yields
M = (mrnp+lp’)R
which is easily factored because mrnp+lp’ is relatively
small. So φ(M) can be evaluated. Moreover, the wide
choice for all the parameters enables the factor mrnp+lp’
to avoid any undesired divisibility properties.
In
particular, by construction p’ is already prime to r so that
M will share divisors with r only as far as is necessary toobtain l at the least significant end.

5 Examples

4 Least Significant Digits for M

Take the radix to be r = 4. If we seek a square-free M
then it is reasonable to replace each rn±1 by a pair of
numbers on either side of rn which are prime to all
numbers earlier in the list. Thus, for n = 1,2,3,... the listof selected pairs might be chosen as { (3, 5), (13, 17),(61, 67), (253, 257), (1021, 1031), (4093, 4099), (16381,
16387), (65531, 65537), ... }. As well as (4093, 4099)
we might also include the pair (4091, 4111). In this way

Although setting the lowest digits to a given sequencel can be achieved simply by taking M = l, there aresituations where a modulus of more than these few digits
is desired. In fact, the previous construction provides l =m as the digit sequence at the least significant end of M
under suitable conditions. Assume that there are an evennumber of minus signs in the product P, that l has n

81Proc. 14th IEEE Symposium on Computer Arithmetic, Adelaide, 14-16 April, 1999, IEEE Press, 1999, pp 78-85.

several factors can be close to the same rn without losing
the square-free property by repeating the same factor.
Suppose M must allow any two initial digits. These
yield a number in the range 4 to 15. To maintain thesquare-free property the initial sequence m requires athird digit, chosen to make it square free whatever the
choice of the first two digits. This is always possible:
thus the square 410 = 104 at the head of M is given bytaking m as 1710 = 1014 or 1910 = 1034 and the square 910= 214 is given by taking l as 3710 = 2114, 3810 = 2124 or
3910 = 2134.
These choices for m may have common factors with(3,5) or (13,17), which are therefore deleted from the listof numbers used for P. Similarly, the choice of m should
avoid the 7 dividing 16387 and the 19 dividing 65531 ifeither is used in P.
Suppose M is to have 20 digits (in radix 4). Then P
must be chosen to be just over 417 since m uses three
digits. The partition 17 = 8+5+4 leads to P having threefactors close to 48, 45 and 44 respectively. One acceptablechoice is
P = 6553110×102110×25710 = 1000003220332300334
Here the 257 cannot be replaced by 253 without
making P less than 417 since the other factors are alreadythe lower of the two choices from the list. Hence, byTheorem 2 applied to 257 = 44+1, we know that M = mP
will provide m for its three initial digits. Indeed, the five0s after the initial 1 in P ensure that M could provide up
to five given initial digits. M is square-free providing m
is chosen as above and is not divisible by 19. Then φ(M)= φ(m×19×3449×1021×257) = φ(m)×18×3448×1020×256.
Now consider adding the requirement on M for two
arbitrary final digits l. The lowest digits of P’ must be
014 to achieve l. So a different choice of factors is
required in P and P’ than above. For convenience, wechoose factors ≡ 1 mod 42 so that the same is true of the
product. To achieve this the list of factors to choose frommight be modified to { ..., (16369, 16417), (65521,
65537), ... }. The form of M is M = mr2P + lP’ where P
must now be just above 415 so that mr2P has 20 digits.
Using 15 = 7+8 yields
P = 6552110 × 1641710 = 10000131033201014
which again allows m to appear as the leading digit
sequence for M. Taking P’ = P gives

given by 16m+l. Rounding up the rest of P and P’,
namely 1310...4 up to 2000...4, we observe that the rest of
P and P’ contribute at most 2(16m+l) div 45 to the top 5
digits of M. This quantity is at most 1, and so could
affect the 5th digit, propagating a carry. Then, only for l= 334 might a carry (at most 1) propagate to the third top
digit. This position contains the third, chooseable digitof m. It is therefore first selected to be at most 24 in order
to absorb any carry and, secondarily, to make 16m+l
square-free if possible. So the top 2 digits of m really are
the top digits of M, as required. Again φ(M) is easily
calculated as 65521 and 16417 are both prime.

6 The Test SuiteIn this section we wish to consider what pairs ofvalues (M,T) would form an appropriate set for testing
the design, fabrication and run-time correctness of amodular exponentiator, where the Ms have been
constructed as in the previous sections. Although testingis phrased in terms of hardware, some aspects apply
equally to the testing of software implementations.
From the published literature it is quite clear that
implementations of modular exponentiation vary widelyin design. The suggestions here may therefore needadapting or extending to particular applications. Section
1 outlined the major components most likely to bepresent and in need of testing: a digit slice which isrepeated to form the modular addition cycle, a module
receiving end digits (either msd or lsd) which decides themodulus multiple for subtraction, and the component forcontrolling the squares and multiplies of the
exponentiation. In addition there are various countersdetermining, for example, how many shifts are given to
inputs and outputs, and how many addition andmultiplication cycles are performed.
The requirement for speed generally means that mostoperations are entirely locally defined (i.e. within a digit
slice or equivalent), so that different components might
be fully testable individually. In a well designed system,
the main global operation is usually only a final modular
reduction and carry propagation step to obtain a nonredundant output within the required range of [0,M−1].
This section concentrates on the testing of thosecomponents which will benefit from the above
construction for moduli although for completeness some
remarks are also made about other components.
The expected algorithm has the following format. For
any non trivial text T, if M has n bits, then theφcomputation of T (M)+1 mod M will require around 1.5n
multiplications and O(n2) addition cycles. This requires
two or more registers which hold partial products andM = (16m+l) × 65521×16417
which produces l in its lowest two digits. However, P’
may require further adjustment because it may now belarge enough for the term lP’ to affect the two leading
digits of M, which we want to be given by m. By
considering only the first 5 digits of P and P’ andignoring any lower digits, the first 5 digits of M would be82

C.D.Walter

powers of T as well as the register containing M. Since e= 17 is a typical encryption key for RSA, after only a verysmall number of multiplication/ squaring cycles, theinitial text should have been transformed into a number
which can be assumed to be a randomly distributed bit
sequence. This fact enables one to compute probabilities
for various situations with a high degree of accuracy.
The first component for consideration is the digit
slice, whose design can be tested by exhaustively
checking all combinations of input digits against a formal
specification. However, such testing of individual slices
in a fabricated chip is generally impossible since inputs
such as carries are not usually accessible formanipulating. The fabrication faults which need to bechecked for can exhibit widely differing characteristics
and need a range of inputs to detect.
Every input bit for M and T needs to be tested in both
positions in case a register bit is stuck in one value. Picka value for M which is of maximal length. Then choose
two values for T, one to be any value less than M but withthe same length as M and the other its complement.
Raising these Ts to the power 1 and checking the output
is still T should test the T input and result output registers
for stuck bits.
To test the register M, construct a small set of moduli
with known φ values such that for each bit position there
is a pair of moduli representing both values for the bit.
(This can be done just by taking M as a product ofnumbers with known prime decompositions, i.e. m=1 andl=0.) Suppose the hardware behaves as if M’ had been
loaded instead of M. If M’ ≠ M then the expected value
for φ(M) is very unlikely to match the value φ(M’) needed
for the exponentiation test to work. Hence, using any
non-trivial T satisfying Theorem 1, evaluating Tφ(M) modφ
M or T (M)+1 mod M will generally yield an unexpectedvalue if register M or its I/O is not operating properly: toobtain the expected value of 1 or T the supplied value ofφ(M) would have to be a multiple of the order of T
modulo M’, which is unlikely. (The likelihood of a false
negative is certainly at most the inverse of the averageorder of an element in the multiplicative group of residue
classes of a modulus the size of M.)
In the addition circuitry which forms the main body ofthe digit slice, a single error at any point tends to have aneffect equivalent to adding a bit to, or subtracting a bitfrom, the output whenever some input condition issatisfied. Due to carry propagation, several result bits
may then be affected. Over the large number of additions
required for a single modular multiplication, therandomness of the bits ensures that this condition for theerror occurring is most likely to be satisfied many times.
So most multiplications will be affected.
In themultiplication circuitry, a bit error is usually copied tomany or all digit slices so that a large number of output
bits are affected. It follows then that, as exponentiation
involves all bits in multiplications, almost all errors after
the input registers should have a catastrophic effect on
the output. Thus the tests for register M in the previous
paragraph will normally reveal any such errors in thedigit slices.
Simulations of errors in a digit slice can easily be run,and thereby good approximations obtained for the
probability of an addition or multiplication cycle
displaying the error. These can reveal that some errors
may not be caught with the above tests. In particular, theinclusion of table driven digit multiplications or carrylookahead circuits can lead to some errors arising only
when particular bit combinations arise for the associateddigit of M. Because adjacent digit slices interact throughcarries, it may be necessary to determine sequences ofseveral digits of M in order to generate every situation.
The number of such digits can be discovered byinvestigating the particular implementation. Thus thetesting of some implementations will need a collection ofmoduli M which provides some or all digit sequences of agiven length at a particular position. Such moduli areconstructed as described in previous sections: the lengthof M is varied over all allowable choices, and one of m orl is fixed while the other varies over all the necessary
sequences. This usually generates a sufficient variety ofmoduli because the hardware will shift M of a particularlength to align the variable m or l with the digit slice tobe tested. Then, with the same argument as above, using
one non-trivial T with each such M should normally
expose any error. Of course, when M becomes short sodoes φ(M), so that more values of T may need to beconsidered in order to maintain any certainty that at least
some combinations which expose the error have arisen.
Note that the shifting of M implies that short moduli
will not use the digit slice containing the error, but
longer ones will. Thus outputs will normally suddenly
change from being correct to being incorrect as thelength of M is increased past the point of the fault. This
enables the general position of the fault to be detected
accurately.
Testing the component which decides which multipleof the modulus to subtract (or add) is done in much thesame way as testing an end digit slice. The multiple
depends on the top (or bottom) several digits of both M
and the current partial product. Thus for full testing, m
or l, as appropriate, must vary over all values using
sufficiently many digits to ensure all possibilities arise.
The other of l or m can be kept fixed. Again a single T
will normally suffice for each M since its end digits will83

Proc. 14th IEEE Symposium on Computer Arithmetic, Adelaide, 14-16 April, 1999, IEEE Press, 1999, pp 78-85.

vary randomly over the many calls to the component
during each exponentiation.
Testing the exponentiation algorithm is normally acase of looking at boundary values, such as the maximum
and minimum possible exponents, as well as checking
that all possible bit combinations arise to exercise fully
any bit recoding process which controls the scheduling ofmultiplications and squarings.
This algorithm isnormally independent of both the text T and the modulus
M so that it would suffice to fix both of these. If it isdesired to use φ(M) or φ(M)+1 as the exponent to obtainself-checkable output, then it may be possible to generatea suitable M after fixing φ(M). We won’t supply details,
but the basis of a method would be using the prime
decomposition of φ(M) and the fact that φ is amultiplicative function (i.e. φ(xy) = φ(x)φ(y) if x and y
are coprime). For bit recoding of exponents, the tests
already described above may suffice: the values of φ(M)used should make this clear. The boundary cases of verysmall exponents can be checked easily by taking T = 2,
say, and observing what power of T is output for the
exponents 0, 1, 2 etc. At the opposite extreme, test cases
for maximal exponents should be easy to generate
although this seems to require an independent
implementation to calculate the expected output − one of
the things that has been avoided in the other tests so far.
The variety of exponentiation algorithms makes it
inappropriate to be more specific. Generally speaking,tests can be developed independently of the choice of M,
and so is not the concern here.
The final main component tackles carry propagation
and reduction to the range [0,M−1]. Input to the carrypropagation unit will be the required result in a
redundant form. Thus if T = 2h < M is the expected
output of a non-trivial exponentiation, there is likely tobe propagation of carries up most of the register toposition h. For a full length M, T = 2h should be used toφcompute T (M)+1 mod M for as large an h as possible aswell as for several of the smallest possible hs.
For the reduction to an output in the range [0,M−1]
there may be extra subtractions to perform and signs toφdetermine. The obvious test cases are evaluating T (M)+1
mod M with texts T close to the boundary points, say T =0, 1, 2 and M−1 for which the wrong multiple of M may
be added. If the pre-normalisation bound on the output
from the exponentiator is cM (c is often about r) then,before the subtraction, the output should have the form
iM+T for some i in [0,c−1]. So several different moduli
M will need to be used to ensure each possible i arises
during the test. These M should be of maximum length
to test fully the subtraction and sign determination.

In summary the following pairs (M,T) might
constitute a suitable test suite for most implementationsof modular exponentiation:i) For M of maximal length, choose T < M with the samelength as M and its complement T’. Raise these to thepower 1 and check the output equals the input.
ii) Take a small set of moduli with known φ values suchthat for each bit position there is a pair of moduli
representing both values for the bit. For each modulus
choose T prime to M with 1<T<M and check Tφ(M) mod M
yields 1.
iii) With the length of m and l determined as above
take a set which includes a modulus M of each possible
length constructed as in section 3 or 4 with each possible
value for m or l, according as the test for modulus
subtraction is performed at the most or least significant
end respectively.
For each such M choose T prime to M with 1<T<M andcheck Tφ(M) mod M yields 1.
iv) For an odd modulus M of maximum length and T = 2,
check the output of Ti mod M is really Ti for i = 0,1,2,...
such that Ti < M.
v) For a full length odd M with known φ(M) and each Thφ= 22 < M check that T (M)+1 mod M yields T.
vi) For a maximum length odd M of known φ value andφtexts T = 0, 1, 2 and M−1, check T (M)+1 mod M returns T.
If we assume the moduli have already been generated,
the number of different m and l is a constant and the
maximum M for a specific implementation has n digits,then all the above tests take an effort of at most O(n)times the time for exponentiating with an exponent of ndigits.
Finally, observe that these tests can be used todetermine the maximum clock speed at which a specificchip will perform correctly because each part of thecircuitry is tested under all possible input conditions.

7 RSA using the CRT
Some implementations of RSA (e.g. [6]) make use of
the Chinese Remainder Theorem (CRT) and thefactorization of M = pq as a product of two primes to split
the exponentiation Td mod M into two smaller, parallel,
shorter exponentiations modulo the factors:
Td mod M = ( (Td mod φ(p) mod p)(q−1 mod p)qφ−+ (Td mod (q) mod q)(p 1 mod q)p ) mod M
The properties used here are the primality andcoprimality of the factors. The first enables φ(p) to becomputed as p−1 and the second guarantees the existence−of q 1 mod p, which can be found via the Euclidean

84

C.D.Walter

this should enable the full functional verification of an
implementation at any stage in its life cycle.

algorithm. Similar computations yield the second term.
So knowledge of the factorisation of M roughly halves
the length of all the numbers, including the exponents,and so cuts the work required by a factor of 4.
We will assume that the modular reduction of d iseasy to check and that, by picking d = 1, a sufficientvariety of values for T, p and q can be chosen to test
thoroughly all the other operations apart from theexponentiations.
If the hardware allows φ(p) or d mod φ(p) to becomputed independently of p, then testing the first
exponentiation need not require p to be prime. So theprevious methods can be used. Thus p can be chosen tohave the form mP for product P and leading digits m, andany q prime to p with known φ(q) can be used tocomplete the definition of M. Otherwise, if p needs to be
prime because φ(p) is always assumed equal to p−1, thenwe can use p = mrn+1 as a seed for a prime number
generator which will keep incrementing p until a prime
is found. Then, unless n is very small, p will have theleading digit sequence m which is what we wish for thetest suite. Interchanging the roles of p and q will test
hardware which performs the other of the two
exponentiations.

Acknowledgement. The author would like to thank theanonymous referees for several useful comments toimprove the initial version of this paper.

References
[1]

[2]

[3]

[4]

[5]

[6]

8 Conclusion
The aim of this investigation has been to develop asuite of moduli M and texts T to test thoroughly the large
number hardware exponentiators used in the RSA
cryptosystem [5] and Diffie-Helman key exchange [9].
Normally, with randomly generated test cases, anequivalent amount of external calculation needs to be
performed to verify any results. Such calculations may
have to be done on much slower implementations orusing a system which may have the same design errors as
the hardware being tested.
However, the tests here are self checking: the output
should always be the same as the input or equal to 1,
depending on the test chosen. So the large quantity ofcomputation necessary to guarantee that even the rarest
fault has been exhibited is performed without having to
be matched by equivalent external work.
The effort involved is mainly in the construction ofmoduli via a small number of products P with known
factorization properties. This work can be done entirely
independently of any algorithms which may be
implemented in the hardware being tested.
The result is a suitably large set of moduli for testing
most implementations of the RSA cryptosystem. It
contains moduli of every necessary length with any given
initial and terminal sequences of digits. In most cases,

[7]

[8]

[9]

85

E. F. Brickell, “A Fast Modular Multiplication Algorithmwith Application to Two-Key Cryptography,” in Advancesin Cryptology - CRYPTO ’82, Chaum et al., Eds., New
York, Plenum, 1983, pp. 51-60.
S. E. Eldridge, “A Faster Modular Multiplication
Algorithm”, Intern. J. Computer Math., vol. 40, 1991, pp.
63-68.
N. Koblitz, A Course in Number Theory and
Cryptography, Graduate Texts in Mathematics, vol. 114,
Springer-Verlag, 1987.
P. L. Montgomery, “Modular Multiplication without Trial
Division”, Math. Computation, vol. 44,1985, pp. 519521.
R. L. Rivest, A. Shamir, and L. Adleman, “A Method for
Obtaining
DigitalSignatures
andPublic-Key
Cryptosystems,” Comm. ACM, vol. 21, 1978, pp. 120126.
M. Shand, P. Bertin & J. Vuillemin, “Hardware
Speedups in Long Integer Multiplication”, ACM
Computer Architecture News, vol. 19, March 1991, pp.
106-113.
C. D. Walter & S. E. Eldridge, “Hardware
Implementation of Montgomery’s Modular Multiplication
Algorithm,” IEEE Trans. Comp., vol. 42, 1993, pp. 693699.
ANSI X9.31-1998, Digital Signatures Using Reversible
Public Key Cryptography for the Financial Services
Industry, American National Standards Institute, New
York, USA, 1998.
W. Diffie & M. E. Hellman, “New Directions in
Cryptography”, IEEE Trans Inform Theory, vol. 22,
1976, pp. 644-654.