Seeing through Mist Given a Small Fraction of
an RSA Private Key
Colin D. Walter
Comodo Research Lab
10 Hey Street, Bradford, BD7 1DQ, UK
Colin.Walter@comodogroup.com
www.comodogroup.com

Abstract. In smartcard encryption and signature applications, randomised algorithms are used to increase tamper resistance against attacks
based on side channel leakage. Mist is one of these. As is the case withthe classical m-ary and sliding windows exponentiation algorithms, themost significant half of the public modulus yields information which canbe used to halve the number of key digits which need to be guessed
to recover the secret key from a Mist side channel trace. Lattice based
methods are used to reduce this to just one quarter of the least significant
digits. This enables the strength of the Mist exponentiation algorithm
to be gauged more accurately under several threat models.
Key words: Addition chains, division chains, randomized exponentiation, Mist, randomary exponentiation, RSA, side channel leakage, power
analysis, SPA, DPA, SEMA, DEMA, blinding, smartcard.

1

Introduction

Smartcards have very limited scope for the inclusion of physical security measures. So tamper resistance should also be built into the component algorithms
whenever possible. Because exponentiation is such a major process in many
crypto-systems, including RSA, Diffie-Hellman and ECC, it is the main target
for improved algorithmic methods. Initial side channel attacks made use of timing differences [8] due to conditional subtractions during modular multiplications[17]. Such differences are now easily avoided [19]. However, because unprotected
hardware gates use different amounts of power depending upon whether or notthey are switched to a different state, power usage by any chip is also data dependent, and so provides side channel leakage which may enable secret keys tobe recovered. Although the first power attacks required averaging over a numberof exponentiations in order to reduce the effects of noise and dependence on
irrelevant data [9,12], recent progress suggests that there is enough data in the
trace of a single exponentiation to allow careful averaging to reveal the key [18].
In particular, one can average over subsets of digit-by-digit products within eachlong integer multiplication rather than the sequential traces of many exponentiations. In addition, electro-magnetic leakage seems to provide a very much more
powerful means of obtaining key data than power variation [15,16,4,1].
M. Joye (Ed.): CT-RSA 2003, LNCS 2612, pp. 391–402, 2003.
c Springer-Verlag Berlin Heidelberg 2003

392

Colin D. Walter

Such side channels and methods enable all the classical exponentiation methods to be attacked: both sliding windows and m-ary [7]. Consequently, a new
breed of algorithms has had to be developed, namely the randomised exponentiation algorithms. Two such algorithms appeared at the CHES 2001 conference[11,14] and further ones at, for example, the RSA 2002 [21] and CHES 2002 conferences [5,6]. The first two seem to provide little extra security if one assumes
squares and multiplies (adds and doubles) can usually be distinguished during
a single exponentiation and no key blinding is used [13,23]; they are also only
suitable for elliptic curve (ECC) applications because of the requirement for thecomputation of inverses. However, the more recent algorithms seem to be morerobust [22], and some of them can be applied easily to RSA because no inverses
need be computed.
The purpose of this article is to contribute further to an assessment of thestrength of the third of these randomised exponentiation algorithms, namely
Mist [21]. First, elementary methods are applied to show that half of the digits
generated by Mist suffice to reveal the key when the public modulus and exponent are known. The techniques of Boneh et al. [2] have been used formerly onclassical representations of the secret key to show that only a quarter of the bitsof the key need be known before algorithmic methods can be applied to determine the complete key in polynomial time. Here those techniques are adapted to
the “randomary” representation of the key which Mist generates. The results
are similar: a quarter of the randomary digits are sufficient to enable recoveryof the full key in polynomial time.
These results are then applied to reduce the search space for keys which arepartially revealed through side channel leakage. Although the conclusions show
the computational effort to break the keys is still infeasible for standard key
lengths, there is little room left for complacency. Key blinding or keys of atleast 1024 bits would still appear to be necessary for good tamper resistance.
By comparison, of course, the quality of side channel leakage which we assume
is instantly fatal to the classical algorithms.

2

The MIST Algorithm

For notation, suppose that the RSA crypto-system has known public modulus
N , public exponent E and private exponent D (after any required blinding), sothat plaintext P and ciphertext C are related by P = C D mod N . It is sidechannel leakage from this exponentiation that an attacker uses to extract thesecret key D.
The Mist algorithm [20,21] is a random-ary exponentiation method very
similar to m-ary exponentiation, but it reverses the order of processing the digitsof D, and the base m is varied randomly for each digit choice. The following
version computes P = C D mod N .

Seeing through Mist Given a Small Fraction of an RSA Private Key

393

The Mist Exponentiation Algorithm{ Pre-condition: D ≥ 0 }Q ← C ;
P ← 1 ;
While D > 0 do
Begin
Choose a random base m from set S ;d ← D mod m ;If d 6= 0 then P ← Qd ×P mod N ;Q ← Qm mod N ;D ← D div m ;{ Loop invariant: C D.Init = QD × P mod N }End ;{ Post-condition: P = C D.Init mod N }The values of d are analogous to digits of D in representations where the basem is constant. Generally, the random choice of m is from a fixed set with known
security and efficiency properties, such as S = {2, 3, 5}. When the random baseset S consists of the single divisor 2, the method simplifies to the binary squareand-multiply algorithm in which the least significant exponent bit is processed
first. In general, for a singleton set S = {m}, the algorithm simplifies to classicalm-ary exponentiation but performed from right to left rather than from left toright. Space and time efficiency were shown in [21] to be comparable with 4-ary
exponentiation when addition chains for computing Qm compute Qd en routerather than sequentially, and m is chosen with a suitable bias which favours
m = 2 or d = 0.
The random choice of bases generates different exponentiation schemes on
successive runs and so makes impossible the usual averaging process requiredfor power analysis (SPA/DPA) [9] or electro-magnetic analysis (SEMA/DEMA)[15]. Hence, we assume that the attacker has extracted data from a single exponentiation which enables him to determine either i) which operations are squares
and which are multiplications, or ii) which operations share an argument. In [22],the following results were established:
Theorem 1. ([22], Thm. 9) Suppose squares and multiplies can be distinguished,
but not individual reuse of operands. Then, for the choice of parameters given
in [22], the average number of exponents which can generate the same sequenceof squares and multiplications as a given one for D is bounded below by D3/5 .
Theorem 2. ([22], Thm. 8) For the choice of parameters given in [22], the average number of exponents with exponentiation schemes that have an operandsharing pattern identical to a given one for D is about D1/3 .
Both of these theorems are established by counting the number of choices forthe pairs (m, d). For example, addition chains for (2,1) and (3,0) are chosen to
give them the same operand sharing patterns and square & multiply sequences.

394

Colin D. Walter

Every time one of these patterns turns up, there is an ambiguity about the choicefor D which effectively doubles the size of the search space for the correct D.
In other cases there is a unique choice, or even three or four choices for (m, d)which give the pattern which the attacker has recognised. Simulations indicatethat there is very little collapsing of the search space as a result of duplicationin the reconstructed exponents. However, as one of the reviewers has pointed
out, the size of the search space is not necessarily an accurate measure of thetime to recover the correct key. If efficiency considerations dictate non-uniform
selection criteria for d, then some exponents are more likely than others. So,
on average, an intelligent search for the correct exponent would only have totraverse a fraction of the entire space. Nevertheless, if each d is equally likely,
then half the space must be traversed. This latter is the case assumed in theillustrative results below, but it is easy to adapt the deductions to alternative
situations.
If the digits and bases are indexed from 0 to n−1 in the order generated,then the following notation, initial conditions and properties hold, just as for a
fixed base m:
D0
= D
di
≡ Di mod mi
Di+1 = Di div mi(1)
dn−1 6= 0
Dn= 0
Di = mi Di+1 + di
Di = ((. . . (dn−1 mn−2 + dn−2 ) . . .)mi+1 + di+1 )mi + di
D = ((. . . (dn−1 mn−2 + dn−2 ) . . .)m1 + d1 )m0 + d0(2)This indexing follows that of digits in the standard base m representation. Some
additional related quantities are of use later:
Qi−1
µi =
j=0 mj(3)
δi = ((. . . (di−1 mi−2 + di−2 ) . . .)m1 + d1 )m0 + d0
which satisfy
δi ≡ D mod µi
Di = D div µi
D = µi Di + δi

(4)Exponent blinding is assumed throughout, since this is probably essential tohelp address the vulnerability of applications for which the algorithm is considered necessary. So D will always represent the exponent actual used, with its
digits as above, while D0 will be the original unblinded secret key. Notation forthe blinding is introduced in the next section.

3

Halving the Search SpaceThe starting point for both of the main results is the observation that φ(N ) has
a good approximation given in terms of N . If N = P Q is the prime factorisation

Seeing through Mist Given a Small Fraction of an RSA Private Key

395

of N , the standard choice of P and Q to have theof bits allows√ same number p
an attacker to assume that P < Q < 2P . Then 2 N < P +Q < 3 N/2 and soφ(N ) = N −(P +Q)+1 is bounded byp√
N − 3 N/2 + 1 < φ(N ) < N − 2 N + 1(5)√This interval has length less than 18 N , so that three more than half the mostsignificant bits of φ(N ) can be determined trivially.
Suppose that the public and private exponents, E and D0 respectively, arerelated by
D0 ×E = 1+kφ(N )(6)where it is reasonable to assume that D0 is chosen to make D0 < φ(N ) so thatk < E. However, to such D0 a blinding factor should normally be added [8],giving the secret key
D = D0 +rφ(N )(7)which is actually used for an exponentiation. Here r is a random number, often
of 32 bits. Then
1 + (k+rE)φ(N )
(8)
D =
E
Let B be an upper bound on such r. Then, in effect, the coefficient k+rE of φ(N )is a random number in the range 0 to BE. The attacker just has to generate eachof the O(BE) possible values of the random coefficient of φ(N ) in order to obtaina set containing an approximation to the value of D used in the exponentiation
which he has observed. If there is no blinding, r = 0 is taken, and B = 1 will
give the relevant results for that case.
For a given choice of r and k, let Dl and Du denote the (irrational) lower andupper bounds on D determined by equations (5) and (8). So, for the assumptions
made above,Du − Dl =√k+rE p(3 1/2 − 2) N
E

<

B√
N
8

(9)

Next the attacker must generate all possibilities for the last half or so of thedigits of D, taking enough of them to construct a Dj satisfying bothr
(k+rE)NDj ≥and Dj ≥ Du −Dl(10)E
The first
a consequence of the second. By (9), this is theq inequality is usually
p
p
k+rE
k+rE
case if≤ E (3 1/2 − 2), i.e. if k+rE
≥ (3 1/2 − 2)−2 , which holds
EE
for r ≥ 68. So we can normally ignore it in the following estimates.
Depending on the threat model for side channel leakage, the digit choices will
be restricted in some way. We will consider in more detail the two particular cases
covered by Theorems 1 and 2. In each case, the ambiguities for each base/digit
pair (mi , di ), j ≤ i ≤ n−1, were described in detail in [22]. The attacker’s next
problem is to identify which such choice is correct.

396

Colin D. Walter√
By√(8) and the first inequality of (10), Dj > D, so that (4) gives δj <µj < D < Dj . Thus µj = D div Dj by (4). By the second inequality of (10),Dl /Dj < D/Dj < Du /Dj ≤ Dl /Dj + 1. So, combining these,
Lemma 1. For j as chosen above, µj = D div Dj = bDl /Dj c or bDu /Dj c.
These two quantities can be calculated from the assumed values of Dl andDu and used to reject Dj if neither expression has the characteristic property ofµj , namely being a product of elements from the chosen base set S = {2, 3, 5}.
This should almost completely determine the correct Dj .
Our next task is to estimate how many values of Dj will be accepted by thisprocess. It is reasonable to assume bDl /Dj c and bDu /Dj c are effectively random
in terms of their prime factorisations. So we need to know the probability thata random number of size D/Dj will be a product of powers of only 2, 3 and 5.
Suppose µ = 2x 3y 5z < K. Then there are at most log2 K possible choices forx, log3 K for y and log5 K for z, making a total of at most (log 2 log 3 log 5)−1(log K)3 choices for µ. Differentiating with respect to K, this in turn means amaximum density of3(log 2 log 3 log 5)−1 (log K)2 /K(11)

for numbers of size K with the required form. So these forms are quite rare.
Combining (5) and (8) with the equality in (9) yields essentiallyp√√
N − 3 1/2
D
N −2
p
p
<
(12)
<
D
−D
3 1/2 − 2
3 1/2 − 2ul
If Dj is chosen to be minimal such that the second inequality of (10) holds thenDu −Dl ≤ Dj ≤ 5(Du −Dl ) because 5 is the maximum base. Thus, ignoring
insignificant terms, the numbersof interest are bounded below by D div Dj ≥√√√N −3 1/2
bDl /5(Du −Dl )c ≥ b √c ≈ 53 N and bounded above by D div Dj ≤5(3 1/2−2)√√√
Du /(Du −Dl ) ≤ √N −2 < 9 N . So we may use K = 53 N in (11) to provide
3

1/2−2

an upper bound on the density of {2, 3, 5}-powers in the region containing µj .
If, instead, Dj √is chosen√minimal such that the first inequality of (10) holds thenD div Dj > 15 D ≈ 15 rN where r < 68. So again we must choose K in (11)√to be O( N ).
However, by Theorems 1 and 2, there are up to Dj 3/5 or Dj 1/3 values√ of Dj
with the right patterns to consider. Here O(Dj ) = O(Du −Dl ) = O(B N ) by
(9). Hence, by (11), the expected number of values Dj for which Dl div Dj or
Du div Dj has the right form is at mostO(B 3/5 {log N }2 N −1/5 )orO(B 1/3 {log N }2 N −1/3 )(13)

respectively for each choice of k and r. In both cases, this is less than 1 for some
expected sizes of N (192 bits in the case of ECC, say) and B (32 bits, say). This

Seeing through Mist Given a Small Fraction of an RSA Private Key

397

indicates that essentially only one solution is likely to exist, which will be therequired one if k and r are chosen correctly. However, without the aid of any
leaked data, an exhaustive search will have Dj cases to consider and will reduce
the exponent of N in this expression to 0. Thus, any side channel which reduces
the search space to below that of an exhaustive search will reduce the expected
number of Dj generating the right form to at most O(B{log N }2 ).
Once a feasible Dj is determined, the remaining part of D is straightforward
to reconstruct iteratively. Using equation 2(i) repeatedly, each new value Di(j−1 ≥ i ≥ 0) is constructed from the preceding Di+1 and the divisibility of theassociated µi by only 2, 3 or 5 is checked in the same way as for Dj in order todetermine which choice of (mi , ri ) is correct.
The effort for this is minimal at least for i ≈ j. However, as i decreases,
the probabilities change: µi = D div Di has fewer and fewer factors, and so ismore and more likely to be of the correct form. For µi ≈ 3×29 there are only
about µi 3/5 ≈ 54 or µi 1/3 ≈ 9 remaining choices for extending Di to D in
a way consistent with the side channel leakage. Also, only 79 values from theinterval [1 .. 3×29 ] give subsequent µi0 s with the right form. So there are very
few incorrect choices which satisfy all the criteria and every plausible case canbe investigated in full. For µi > 3×29 , (11) shows that at most 1 in 12 numbers
have the requisite form. The average base value mi0 is 2.50 so that the previous tbase values reduce D by a factor of about 2.50t . So there are around (2.50t )3/5 or(2.50t )1/3 choices respectively for these t base/digit pairs. Any one of these has
a probability at most 12−t of being acceptable under the divisibility criterion.
Hence at most about (2.50t )3/5 12−t or (2.50t )1/3 12−t of the incorrect choices
will survive t base choices. These both tend to 0 as t increases. Hence, although
one may temporarily have to consider some additional incorrect choices for Di ,these will disappear very quickly as i decreases. Indeed, with a probability ofless than 1 in 12 of acceptability and at most 4 choices for extending Di+1 to
Di , the averageof further iterations which an incorrect value survives is
P∞ number
4 i) = 34 . Thus, normally there will be fewer than two values
less than i=1 i( 12of Di+1 which are under consideration for generating Di – the correct one (if kand r were selected correctly) and at most one incorrect one. The computational
cost of generating possible D from a correct Dj is therefore of the same order asthat of applying the divisibility criterion j times: once for each i < j; and thecomputational cost for an incorrect Dj is just the cost of a constant number ofapplications of the divisibility criterion.
In √total, there were O(BE)values for (k, r), and hence for Dl and Du , and√O({B N }3/5 ) or O({B N }1/3 ) ways for choosing Dj from each Dl or Du .
Thus, from this method there will be respectively at mostO(EB 8/5 N 3/10 )orO(EB 4/3 N 1/6 )(14)possible values for Dj , and hence of D, which are generated and need checking.
As noted above, almost all Dj will be rejected by the divisibility criterion on
its first or second application and not lead to a viable D. These figures give theorder of work involved in an attack. For standard RSA key sizes of 1024 or more

398

Colin D. Walter

bits and no other data to narrow the search space even further, this is still acomputationally infeasible task for any E and no blinding (B = 1). Observe that
increased security is obtained more cheaply by increasing the public exponent E
or the size of the blinding factor B rather than the modulus N .
Other parameter choices and threat scenarios for Mist can be tested in asimilar way to see if the search space still remains large enough to prevent a
successful attack.

4

Quartering the Search SpaceThe lattice-based techniques of Coppersmith [3] produce complementary results
to those in the previous section. They enable one to deduce the secret key fromthe least significant digits rather than the most significant ones. Existing relevant work for recovering secret keys from the public modulus and such partial
knowledge of the key is exclusively centred on a bit-based view of the key. Withbases 3 and 5 as possibilities, the bit-based view must be reformulated in a lessbase-dependent way. Fortunately, the generalisations involve few complications.
So, analogously to the quarter of bits of D that Boneh et al. [2] use, a similarargument here requires on average about a quarter of the digit/base pairs tobe established. Effectively, the computational effort must then be directed at an
exhaustive search of a space whose size is a fractional power of D with exponent
only a quarter of the value given in Theorems 1 or 2. The main result needed in
the proof is the following:
Theorem 3. ([2], Cor 2.2) Let N = P Q be an n-bit RSA modulus. Let µ ≥ 2n/4
be given and suppose P0 def= P mod µ is known. Then it is possible to factor Nin time polynomial in n.
Both here and in [2], the choice made for µ is a product of base values. This
makes µ a power of 2 in [2], but a product of powers of 2, 3 and 5 here. Suppose
pairs (mi , di ) have been guessed correctly for 0 ≤ i ≤ j−1 and some j. Thenδj and µj are known, and satisfy D ≡ δj mod µj , as in equation 4(i). µj is thevalue which will be taken for µ in the theorem, so we choose j large enough thatµ = µj ≥ 2n/4 .
Rewriting equation (8) entirely in terms of N and P rather than N and φ(N )gives
DE = 1 + (k+rE)(N −P −N/P +1)(15)
Reducing this modulo µ = µj , we see that P0 ≡ P mod µ is a solution for x in
the equation
δj E ≡ 1 + (k+rE)(N −x−N/x+1) mod µ(16)
and hence a root of(k+rE)x2 − (1−δj E+(k+rE)(N +1))x + (k+rE)N mod µ(17)

Seeing through Mist Given a Small Fraction of an RSA Private Key

399

The coefficients here are all divisible by k+rE because (k+rE)φ(N ) = 1−DE ≡1−δj E mod µ. Suppose g = gcd{k+rE, µ}. Then, dividing (17) through by
k+rE, P0 ≡ P mod µ is a root of the quadraticx2 − ((1−δj E)/(k+rE)+N +1)x + N mod µg −1(18)

As before, the attack must consider separately every possible value for k+rE. g
is easily computed once k+rE is chosen, and so (18) is obtained.
Solutions are most easily obtained by first completing the square. N +1 and(DE−1)/(k+rE) = φ(N ) are both even, so the coefficient of x in (18) is also
even. In fact, Q0 ≡ Q mod µ is a second solution to (18) and the coefficient of xis then −(P0 +Q0 ). So, by taking y = x− 21 ((1−δj E)/(k+rE)+N +1) in (18), x
is obtained from the solutions of an equation of the formy 2 ≡ c mod µg −1(19)where c is easily computed. For solutions to exist, any power of 2, 3 or 5 which
divides c must occur to an even power. If this is not the case, the wrong k+rE
must have been chosen, and so the next one should be selected. If it is the case,then that power can be removed from y easily and replaced later. So, without
loss of generality, assume c is prime to each of 2, 3 and 5. Thus we are looking
for a solution prime to µg −1 .
The solutions to (19) are obtained by solving modulo the maximal 2-, 3- and5- powers which divide µg −1 and then using the Chinese Remainder Theorem toreconstruct the solutions modulo µg −1 . Solutions modulo the prime powers are
obtained by lifting solutions progressively from lower powers of the prime. For
higher powers of 2 than 22 , Boneh et al. ([2], App. A) have previously noted that
there are at most 4 solutions if there are solutions at all, and have provided aconstruction process for them. For an odd prime p, residues mod pt (t≥1) which
are prime to p form a cyclic group of order φ(pt ) under multiplication (e.g. [10],Thm. 7.2.10). Hence (19) will have exactly two solutions, say ±yt , or none at allfor µg −1 = pt . Any solutions modulo pt+1 must then have the form ±(yt +δt pt )for some δt in [0 .. p−1]. Each δt can be tried in turn to find the solutions. Once
more, no solutions at any point means the wrong value for k+rE; otherwise
there will be two.
Using the Chinese Remainder Theorem to combine the results modulo thepowers of 2, 3 and 5, the number of solutions is the product of the number ofsolutions modulo the individual prime powers, namely 4×2×2 = 16, assuming
at least 23 ×3×5 divides the modulus and each has at least one solution. These
16 solutions are all different because, by reducing them modulo each of the three
prime powers, different solutions sets modulo the prime powers are recovered.
The effort in obtaining and combining the solutions in this way for a fixed
k+rE is proportional to the sum of the exponents of the powers of 2, 3 and 5
dividing µg −1 . It is thus a computation of order at most log(µg −1 ), and henceof order at most log µ. As j was chosen so that µ ≥ 2n/4 and there are up to
BE choices for k+rE, the solutions now provide all possible values for the P0
in Theorem 3 for a computational effort of O(nBE). Hence,

400

Colin D. Walter

Theorem 4. For a public RSA modulus N with n bits, public exponent E andexponent blinding using a random multiple of φ(N ) which is bounded above by
B, given the least significant randomary digits of D whose product of bases is
at least N 1/4 , it is possible to factorise N in time which is polynomial in n andlinear in BE.
As a corollary, it is possible to deduce the maximum effort required to deduce
the secret key under the assumptions stated in Theorems 1 and 2. The numberof partial keys which need to be tested is of order (N 1/4 )3/5 and (N 1/4 )1/3
respectively.
Corollary 1. Under the threat scenarios described in Theorems 1 and 2 withknown public modulus N and encryption key E, it is possible to factorise N intime which is a product of polynomial time in log N and linear time in BEN 3/20
or BEN 1/12 respectively.
It is now clear that exponent blinding is important in the prevention of suchattacks, and such blinding provides more tamper resistance per bit than increasing the key length. If similar but more powerful attacks than those describedin [22] can be developed, then blinding will become strongly advisable if the
key length is under 1024 bits. Furthermore, we have assumed the bases mi werechosen at random. However, biasing the choice for efficiency or other reasons
further reduces the time for executing the attack.

5

Conclusion

Two techniques have been demonstrated for using knowledge of the public RSA
modulus and exponent in order to reduce the computational effort of recovering
the secret key from partial knowledge of a randomary digit expansion of D
generated by the Mist exponentiation algorithm. The first relies on the scarcityof large numbers which are products of powers of only 2, 3 and 5. The othergeneralises the well-known, lattice-based, “Bellcore Attack” method of Boneh,
Durfee and Frankel [2].
Under threat models in which squares and multiplies or operand re-use canbe recognised during a single exponentiation, these techniques do not undermine
the confidence that power and EMR attacks (SPA/DPA and SEMA/DEMA) on
the Mist exponentiation algorithm still appear to be computationally infeasible
for standard key lengths and sensible implementations which include appropriate
blinding. Of course, under the same assumptions, the classical sliding windows
and m-ary exponentiation schemes provide no resistance whatsoever.

Seeing through Mist Given a Small Fraction of an RSA Private Key

401

References
1. D. Agrawal, B. Archambeault, J. R. Rao & P. Rohatgi, The EM Side-Channels,
Cryptographic Hardware and Embedded Systems – CHES 2002, B. Kaliski, Ç. Koç& C. Paar (editors), LNCS 2523, Springer-Verlag, 2002, to appear.
2. D. Boneh, G. Durfee & Y. Frankel, Exposing an RSA Private Key Given a Small
Fraction of its Bits, Advances in Cryptology – AsiaCrypt ’98, K. Ohta & D. Pei(editors), LNCS 1514, Springer-Verlag, 1998, 25–34.
3. D. Coppersmith, Small Solutions to Polynomial equations and low exponent RSA
vulnerabilities, Journal of Cryptology 10 (1997), 233–260.
4. K. Gandolfi, C. Mourtel & F. Olivier, Electromagnetic Analysis: Concrete
Results, Cryptographic Hardware and Embedded Systems – CHES 2001, Ç. Koç,D. Naccache & C. Paar (editors), LNCS 2162, Springer-Verlag, 2001, 251–261.
5. J. C. Ha & S. J. Moon, Randomized signed-scalar multiplication of ECC to resist
power attacks, Cryptographic Hardware and Embedded Systems – CHES 2002, B.
Kaliski, Ç. Koç & C. Paar (editors), LNCS 2523, Springer-Verlag, 2002, to appear.
6. K. Itoh, J. Yajima, M. Takenaka, & N. Torii, DPA Countermeasures by improving
the window method, Cryptographic Hardware and Embedded Systems – CHES
2002, B. Kaliski, Ç. Koç & C. Paar (editors), LNCS 2523, Springer-Verlag, 2002,
to appear.
7. D. E. Knuth, The Art of Computer Programming, vol. 2, “Seminumerical Algorithms”, 2nd Edition, Addison-Wesley, 1981, 441–466.
8. P. Kocher, Timing Attack on Implementations of Diffie-Hellman, RSA, DSS, andother systems, Advances in Cryptology – Crypto ’96, N. Koblitz (editor), LNCS
1109, Springer-Verlag, 1996, 104–113.
9. P. Kocher, J. Jaffe & B. Jun, Differential Power Analysis, Advances in Cryptology– Crypto ’99, M. Wiener (editor), LNCS 1666, Springer-Verlag, 1999, 388–397.
10. R. Kumanduri & C. Romero, Number Theory with Computer Applications, Prentice
Hall, 1998, ISBN 0-13-801812-X.
11. P.-Y. Liardet & N. P. Smart, Preventing SPA/DPA in ECC Systems using theJacobi Form, Cryptographic Hardware and Embedded Systems – CHES 2001, Ç.
Koç, D. Naccache & C. Paar (editors), LNCS 2162, Springer-Verlag, 2001, 391–
401.
12. T. S. Messerges, E. A. Dabbish & R. H. Sloan, Power Analysis Attacks of Modular
Exponentiation in Smartcards, Cryptographic Hardware and Embedded Systems(Proc. CHES 99), C. Paar & Ç. Koç (editors), LNCS 1717, Springer-Verlag, 1999,
144–157.
13. K. Okeya & K. Sakurai, On Insecurity of the Side Channel Attack Countermeasureusing Addition-Subtraction Chains under Distinguishability between Addition andDoubling, Information Security and Privacy, L. Batten & J. Seberry (editors),
LNCS 2384, Springer-Verlag, 2002, 420–435.
14. E. Oswald & M. Aigner, Randomized Addition-Subtraction Chains as a Countermeasure against Power Attacks, Cryptographic Hardware and Embedded Systems– CHES 2001, Ç. Koç, D. Naccache & C. Paar (editors), LNCS 2162, SpringerVerlag, 2001, 39–50.
15. J.-J. Quisquater & D. Samyde, ElectroMagnetic Analysis (EMA): Measures andCounter-Measures for Smart Cards, Smart Card Programming and Security (eSmart 2001), LNCS 2140, Springer-Verlag, 2001, 200–210.
16. J.-J. Quisquater & D. Samyde, Eddy current for Magnetic Analysis with Active
Sensor, Proc. e-Smart 2002, Nice, September 2002, 183–194.

402

Colin D. Walter

17. C. D. Walter & S. Thompson, Distinguishing Exponent Digits by Observing Modular Subtractions, Topics in Cryptology − CT-RSA 2001, D. Naccache (editor),
LNCS 2020, Springer-Verlag, 2001, 192–207.
18. C. D. Walter, Sliding Windows succumbs to Big Mac Attack, Cryptographic Hardware and Embedded Systems – CHES 2001, Ç. Koç, D. Naccache & C. Paar
(editors), LNCS 2162, Springer-Verlag, 2001, 286–299.
19. C. D. Walter, Precise Bounds for Montgomery Modular Multiplication and Some
Potentially Insecure RSA Moduli, Topics in Cryptology − CT-RSA 2002, B.
Preneel (editor), LNCS 2271, Springer-Verlag, 2001, 30–39.
20. C. D. Walter, Improvements in, and relating to, Cryptographic Methods and Apparatus, UK Patent Application 0126317.7, Comodo Research Laboratory, 2001.
21. C. D. Walter, MIST: An Efficient, Randomized Exponentiation Algorithm for Resisting Power Analysis, Topics in Cryptology − CT-RSA 2002, B. Preneel (editor),
LNCS 2271, Springer-Verlag, 2002, 53–66.
22. C. D. Walter, Some Security Aspects of the MIST Randomized Exponentiation
Algorithm, Cryptographic Hardware and Embedded Systems – CHES 2002, B.
Kaliski, Ç. Koç & C. Paar (editors), LNCS 2523, Springer-Verlag, 2002, 276–290.
23. C. D. Walter, Breaking the Liardet-Smart Randomized Exponentiation Algorithm,
Proc. Cardis ’02, San Jose, 21-22 Nov 2002, USENIX Assoc, 2002, 59–68.