More Detail for a Combined Timing and Power
Attack against Implementations of RSA
Werner Schindler1 and Colin D. Walter2
1

Bundesamt für Sicherheit in der Informationstechnik (BSI)
Godesberger Allee 185-189, 53175 Bonn, Germany
Werner.Schindler@bsi.bund.de2
Comodo Research Laboratory
10 Hey Street, Bradford, BD7 1DQ, UK
Colin.Walter@comodogroup.com

Abstract. Implementations of Montgomery’s modular multiplication
algorithm (MMM) typically make conditional subtractions in order tokeep the output within register or modulus bounds. For some standard
exponentiation algorithms such as m-ary, it has been shown that thisyields enough information to deduce the value of the exponent. This has
serious implications for revealing the secret key in cryptographic applications without adequate counter-measures. Much more detail is provided
here about the distribution of output values from MMM when the output
is only reduced to keep it within register bounds, about how implementations of sliding windows can be attacked, and about handling errors.
Key Words. RSA cryptosystem, side channel leakage, power analysis, timing attack, Montgomery modular multiplication, exponentiation,
statistical decision problem.

1

Introduction

Side-channel leakage occurs through data dependent variation in the use ofresources such as time and hardware. The former results from branching in
the code or compiler optimisation [4], and the latter from data causing gate
switching in the circuitry. Both manifest themselves measurably through overall
current variation as well as local or global electro-magnetic radiation (EMR)[5–7]. Information leaking in these ways might be used by an attacker to deduce
secret cryptographic keys which are contained securely inside a smart card.
Timing variation can be measured using overall delay during decryption orsigning [1, 4, 11, 13]. However, for successful attacks on keys with limited lifespans
for which only a bounded number of decryptions with the same key is allowed,
some finer detail may become necessary, such as the time variations for executing
component procedures. This detail can be seen by observing delays between thecharacteristic power consumption wave form for loading instructions and dataat the start of the procedure. Here this is applied to the version of Montgomery
modular multiplication [9] which contains a final conditional subtraction for

246

Cryptography and Coding, LNCS 2898, c Springer 2003

reducing the output by only enough to fit within register bounds. The aim isto recover a secret RSA [10] exponent from deductions of whether or not thisconditional subtraction occurs.
An essential assumption is that there is no blinding of the exponent or randomisation in the exponentiation algorithm so that the same type of multiplicative operations are performed (but with different data) every time the key is used.
This enables an attacker to capture the collection of instances of the extra final
subtraction for each individual operation. We will show how to determine exponent digits from this data, recover from any errors, and hence obtain the secretkey even if the input text (the base of the exponentiation) has been blinded.
The results emphasise the need for care in the implementation of RSA. Indeed, similar results apply to elliptic curve cryptography (ECC) [8] and othercrypto-systems based on modular arithmetic. In all cases where a key is reused, some counter-measures should be employed to ensure that the conditional
subtraction is removed, or at least hidden, and that the same sequence of keydependent operations is not re-used for each exponentiation. In elliptic curve
cryptography, standard key blinding adds about 20% to the cost of a point
multiplication. The temptation to avoid this overhead should be resisted.
Montgomery modular multiplication [9] is arguably the preferred method for
hardware implementation. We treat this algorithm here, but equivalent results
should hold for any method for which there are correlations between the data
and the multiplication time. The generic timing attack methodology which weadopt was first described in [16]. This approach established the feasibility ofrecovering the key within its lifetime and also gave the theoretical justification
behind the different frequencies of final subtractions observed between squaringsand multiplications.
A closer study of such distributions reduces the number of exponentiations
required to recover the key. This was done for various settings in [11–13] when the
final reduction yields output less than the modulus. However, reducing output
only as far as the same length as the modulus is more efficient, and is thecase studied here. The mathematics is more involved and so requires numericalapproximation methods, but this is easy for an attacker. In addition, more detailis given concerning the recovery of the key when sliding windows exponentiation
is employed.

2

The Computational Model

In order to clarify the precise conditions of the attack, each assumption is numbered. First, the computational model requires several assumptions, namely:i) secret keys are unblinded in each exponentiation;ii) Montgomery Modular Multiplication (MMM) is used with a conditional subtraction which reduces the output to the word length of the modulus;iii) the most significant bit of the modulus lies on a word boundary; andiv) exponentiation is performed using the m-ary sliding windows method [2, 3].

W. Schindler & C. D. Walter, A Combined Timing & Power Attack

247

Exponent blinding might be deemed an unnecessary expense if other countermeasures are in place. So we still need better knowledge of how much data leaks
out under the first assumption. For a sample of one exponentiation this particular assumption is irrelevant, but then, with data leaked from other sources, thetechniques here might be just sufficient to make a search for the key computationally feasible.
As shown below, efficiency is good justification for the second hypothesis. The
word length referred to there is the size of inputs to the hardware multiplier,typically 8-, 16- or 32-bit. However, standards tend to specify key lengths which
are multiples of a large power of 2, such as 768, 1024, 1536 and 2048 bits. So thethird hypothesis is almost certainly the case.
Because of its small memory requirements and greater safety if an attacker
can distinguish squares from multiplications, a sliding window version of 4-ary
exponentiation is the usual algorithm employed in smartcards. The exponent is
re-coded from least to most significant bit. When a bit 0 occurs, it is re-coded
as digit 0 with base 2 and when a bit 1 occurs, this bit and the next one arerecoded as digit 1 or 3 with base 4 in the obvious way. This representation isthen processed left to right, with a single modular squaring of the accumulating
result for digit 0, and two modular squarings plus a modular multiplication for
digits 1 and 3. According to the digit, the first or pre-computed third power ofthe initial input is used as the other operand in the multiplications.
An attacker can recover the secret exponent if he can i) distinguish squarings
from multiplications, and ii) determine whether the first or third power was used
as an operand in the multiplications. The classical square-and-multiply or binary
algorithm (m = 2) is less secure against this type of attack as the second task
is omitted. The attack here treats any m, and applies equally well when the
Chinese Remainder Theorem (CRT) is used.

3

Initial Notation

Let R be the so-called “Montgomery factor” associated with an n-bit RSA
modulus M . Then the implementation of Montgomery’s algorithm satisfies thefollowing specification [15]:v) For inputs 0 ≤ A, B < R, MMM generates output P ≡ A∗B∗R−1 mod M satisfying ABR−1 ≤ P < M +ABR−1 before any final, conditional subtraction.
Clearly this specifies P uniquely. The division by R is the result of shifting
the accumulating product down by the multiplier word length for a number of
iterations equal to the number of words in A. Since A, B and M will all havethe same word length for the applications here, hypothesis (iii) yieldsvi) M < R < 2M
i.e. R is the smallest power of 2 which exceeds M .
The output bound P < M +R implied by (v) means that any overflow into
the next word above the most significant of M has value at most 1. When

248

Cryptography and Coding, LNCS 2898, c Springer 2003

this overflow bit is 1, the conditional subtraction can be called to reduce theoutput to less than R without fear of a negative result. Hence that bit can beused efficiently to produce an output which satisfies the pre-conditions of (v) for
further applications of MMM. This is the case of MMM that is considered here.
Alternatively, the condition P < M is often used to control the final subtraction. This is the standard version, but the test requires evaluating the signof P −M , which is more expensive than just using the overflow bit. This caseof MMM was discussed in [12]. A constant time version of MMM is possible
by computing and storing both P and P −M , and then selecting one or otheraccording to the sign of the latter. However, the subtraction can be avoided
entirely if the inputs satisfy A, B < 2M and R satisfies 4M < R. This, too, ismore expensive [15].
As usual, the private and public exponents are denoted d and e. For deciphering (or signing), ciphertext C is converted to plaintext C d mod M . The m-ary
sliding windows exponentiation algorithm using MMM requires pre-computationof a table containing C (i) ≡ C i R mod M for each odd i with 1 ≤ i < m. Thisis done using MMM to form C (1) from C and R2 mod M , C (2) from C (1) , andthen iteratively C (i+2) from C (i) and C (2) . By our assumptions, the word lengthof each C (i) is the same as that of M , but it may not be the least non-negative
residue. We also define b = log2 m and assume it to be integral.

4

The Threat Model

The security threat model is simply that:vii) an attacker can observe and record every occurrence of the MMM conditional
subtraction over a number of exponentiations with the same key.
Section 1 provided the justification for this. The attack still works, althoughless efficiently, if manufacturers’ counter-measures reduce certainty about theoccurrence or not of the subtraction.
Unlike many attacks in the past, we make no assumptions about the attacker
having control or knowledge of input to, or output from, the exponentiation.
Although he may have access to the ciphertext input or plaintext output of adecryption, random nonces and masking should be employed to obscure suchknowledge so that he is unable to use occurrences of the conditional subtraction
to determine whether a square or multiply occurred. It is therefore assumed thatviii) the attacker can neither choose the input nor read either input or output.
Indeed, even without masking this is bound to be the case for exponentiations
when the Chinese Remainder Theorem has been used. Lastly, as the attacker
may have legitimate access to the public key {M, e}, it is assumed thatix) the correctness of a proposed value for the private exponent d can be checked.

W. Schindler & C. D. Walter, A Combined Timing & Power Attack

249

The assumptions so far mean that the same sequence of multiplicative operations is carried out for every decryption. So, from a sample of N decryptions withthe same key, the attacker can construct an array Q = (qi,j ) whose elements are
1 or 0 depending on whether or not the ith MMM of the jth decryption includes
the conditional subtraction. The elements qi,j are called extra reduction or er0
values. Similarly, initialisation gives a matrix Q0 = (qi,j): if Cj is the input to0
the jth decryption then the er-value qi,j is associated with the calculation of(i)

Cj ≡ Cj i R mod M for the digit i.

5Some Limiting Distributions

The timing attack here was first reported in [16], but precise MMM output
bounds now allow a much more accurate treatment of the probabilities andhence more reliable results. More exact figures should make it easier to determine the precise strength of an implementation against the attack. Importantfirst aims are to determine the probability of extra reductions and to establish
the probability distribution function for the MMM outputs P . To this end two
reasonable assumptions are made about such distributions:x) The ciphertext inputs C behave as realizations of independent random variables which are uniformly distributed over [0, M ).
xi) For inputs A and B to MMM during an exponentiation, the output prior
to the conditional subtraction is uniformly distributed over the interval[ABR−1 , M +ABR−1 ).
Assumption (x) is fulfilled if, for example, the ciphertext is randomly chosen(typical for RSA key exchange) or message blinding has been performed as proposed in [4]. Here it is also a convenient simplification. In fact, there may besome initial non-uniformity (with respect to the Euclidean metric) which mightarise as a result of content or formatting, such as with constant prefix padding.
We return to this topic in Remark 1.
In (xi), the multiples of M subtracted from the partial product P during theexecution of MMM are certainly influenced by all bits of A, B and M . However,the probability for the final conditional subtraction is essentially determined by
the topmost bits of the arguments.
Before the formal treatment we illustrate the limit behaviour of the distributions which will be considered and provide the informal reasoning behind theirconstruction. In order to exhibit the difference between squares and multiplications software was written to graph the probability of the extra subtraction in
the limit of three cases, namely the distribution of outputs after a long sequenceof i) squarings of a random input, ii) multiplications of independent random
inputs, and iii) multiplications of a random input by the same fixed constant A.
The result is illustrated in Figure 1. In the second case, two independent values
are chosen from the kth distribution in the sequence. They are used as the inputs
to MMM and the output generates the k+1st distribution. In all three cases theconvergence is very rapid, with little perceptible change after 10 or so iterations.

Cryptography and Coding, LNCS 2898, c Springer 2003

250
M-1

0
0

Squaring
Multns by const
Indepnt Multns

R–M

M

R

Fig. 1. Probability (vertical axis) of output in the range 0..R−1 (horizontal axis) after
a number of squarings, independent multiplications or multiplications by a constant A
for the case M = 0.525R and A = 1.5M .

The density functions have three distinct sections which correspond to the output belonging to one of the intervals [0, R−M ), [R−M, M ) or [M, R). This isbecause outputs with a residue in [R−M, M ) have only one representative in[0, R) and so, under hypothesis (xi), they occur in [R−M, M ) with probability
M −1 whereas outputs with a residue in [0, R−M ) have two representatives in[0, R) with combined probability M −1 . Note the discontinuities in the functions
at R−M and that probabilities tend to 0 as the output approaches 0.
Because M is large, the discrete probabilities are approximated accurately by
the density functions of continuous random variables. If f is the limiting density
function of a sequence of independent multiplications, thenRR1) 0 f (x)dx= 12) f (x)= 0for x < 0 and R < x3) f (x)= M −1for R−M ≤ x ≤ M4) f (x)+f (x+M ) = M −1
for 0 ≤ x ≤ R−M
Rx
R R R Rx/y
115) f (x) = M 0 f (y)dy + M x 0
f (y)f (z)dz dy for 0 ≤ x ≤ R−M
Properties 1 to 4 are already clear, and apparent in the figure. Property 5 encapsulates the restrictions imposed by MMM. To establish it, consider outputs
x in the interval [0, R−M ). These do not involve a final conditional subtraction, and so, by (xi), they are derived from MMM inputs y and z for which[yzR−1 , M +yzR−1 ) contains x. As the distribution is assumed to be uniform on
this interval, there is a 1 in M chance of obtaining x if yzR−1 ≤ x < M +yzR−1 ,i.e. if R(x−M )/y < z ≤ Rx/y. Since R(x−M )/y ≤ R(R−2M )/y < 0, the lower
bound on feasible z is 0 and the upper bound is min{R, Rx/y}. Thus,
R R R min{R,Rx/y}1f (y)f (z)dz dy.
f (x) = M00
The integral over y can be split into the sub-intervals [0, x] and [x, R] in order
to separate the cases of the upper limit on z being R or Rx/y. This yields
RxRR
R R R Rx/y11f (x) = M
f (y)f (z)dz dy + M
f (y)f (z)dz dy
0 0
x 0

W. Schindler & C. D. Walter, A Combined Timing & Power Attack251

in which the first integral simplifies to give the expression in property 5.
These properties determine f completely. Although an algebraic solution does
not exist, numerical approximations are easy to obtain. The other two density
functions satisfy the √same properties 1 to 4. The analogues to property 5 are:R Rx
10
f (y)dyfor 0 ≤ x ≤ R−M
5)f (x) = M 0
for the limit of consecutive squarings, andR Rx/A1500 ) a) f (x) = M
f (y)dy for 0 ≤ x ≤ A ≤ R−M01b) f (x) = M
for A ≤ x ≤ R−M
for the limit of consecutive multiplications by a constant A.
Although there are differences between the distributions for squaring andmultiplication, they are substantially the same. Figure 1 illustrates the largest
possible differences, which occur for M close to 21 R. For M close to R they are
essentially all equal to the same uniform distribution. The distributions whichlead to these limiting cases are considered in more detail in the next section.

6

Conditional Probabilities

As before, a prime 0 is used on quantities relating to the initialisation phase,and unprimed identifiers relate to the computation stage. The attacker wants toestimate the types of the Montgomery multiplications in the computation phase0on basis of the observed extra reduction (er-) values qj,kand qj,k within theinitialization and computation phases respectively. These types will be denoted
using the text characters of the set T := {‘S’, ‘M1 ’, . . . , ‘Mm−1 ’} where ‘S’ corresponds to a square, and ‘Mi ’ to multiplication by the precomputed table entry
C (i) associated with digit i of the re-coded exponent. In this section we derive explicit formulas for the probabilities of these events given the observed er-values.
We begin with some definitions. It is convenient to normalise the residues mod
M to the unit interval through scaling by a factor M .
Definition 1. A realization of a random variable X is a value assumed by X.
00
For sample number k, the er-values qj,kand qj,k are defined by qj,k:= 1 if(j)computation of table entry Ck
in the initialisation phase requires an extra
00reduction (this includes both q1,kand q2,k), and similarly qj,k := 1 if the jth
Montgomery multiplication in the computation phase requires an extra reduction.
0
0
0
Otherwise qj,k:= 0 and qj,k := 0. As abbreviations, let q 0k := (q1,k, . . . , qm−1,k)and q i,...,i+f −1;k := (qi,k , . . . , qi+f −1,k ). For A ⊆ B the indicator or characteristic function 1A : B → IR is defined by 1A (x) := 1 if x ∈ A and 0 otherwise.
Further, for γ := M/R, let χ: [0, 1 + γ −1 ) → [0, γ −1 ) be given by χ(x) := x if
x < γ −1 and χ(x) := x − 1 otherwise; that is, χ(x) := x − 1x≥γ −1 . Lebesgue
measure is denoted by λ.
ABM ∗ (mod R)
A B M
Lemma 1. (i) MMM(A,B)
=χ M
M
M R +
R
where M ∗ = (−M )−1 (mod R).
(ii) The extra reduction in MMM is necessary exactly when −1 is subtracted
by the application of χ.

252

Cryptography and Coding, LNCS 2898, c Springer 2003

This lemma follows immediately from the definition of Montgomery’s multiplication algorithm. Assertion (xi) is equivalent to saying that the second summandin the right-hand side of Lemma 1(i) is uniformly distributed on the unit interval [0, 1). For a formal justification, the ideas from the proof of Lemma A.3(iii)
in [13] can be adjusted in a straightforward way. To formulate a mathematicalmodel we need further definitions which mirror the operations which comprisethe exponentiation:
Definition 2. Assume T (i) ∈ T , i = 1, 2, . . . , describes the sequence of multiplicative operations in the exponentiation. Let F := {i | 1 ≤ i ≤ m−1, i odd}.
Suppose the random variables Vi0 (i ∈ F ∪ {2}) and V1 , V2 , . . . are independentand equidistributed on the unit interval [0, 1). Define the random variables Si0(i ∈ F ∪ {0, 2}) so that S00 assumes values in [0, 1) and
S10 := χ S00 (R2 (mod M )/M )γ + V10
(1)


2
S20 := χ S10 γ + V20
(2)

m
0
0
0
(3)
S2i−1
:= χ S2i−3
S20 γ + V2i−1
for 1 < i ≤2
Similarly, define S0 := Sr0 where r ∈ F is the left-most digit of the secret exponent
d after recoding (cf. Sect. 2) and, for i ≥ 1, let2χ Si−1
γ + Vi 
if T (i) = ‘S’
Si :=
(4)
χ Si−1 Sj0 γ + Vi
if T (i) = ‘Mj ’0Lastly, define {0, 1}-valued random variables W10 , . . . , Wm−1
and W1 , W2 ,. . . by

W10 := 1S10 <S00 (R2 ( mod M )/M )γ

(5)

W20

(6)

:= 1S20 <S10 2 γ

0
0
0
W2i−1
:= 1S2i−1<S2i−3
S20 γ

(
Wi :=

2
1Si <Si−1γ
1Si <Si−1 Sj0 γ

for 1 < i ≤if T (i) = ‘S’
if T (i) = ‘Mj ’

m
2

(7)

(8)

Thus the distribution of Si describes the random behaviour of the output
from the ith multiplication, Vi0 and Vi correspond to the variation described inassumption (xi), and Wi0 , Wi are the associated distributions of final subtractions
recorded in Q0 and Q:
Mathematical Model. We interpret the components of the er-vector q 0k =
0
0
(q1,k
, . . . , qm−1,k), row subscripts in F ∪ {2}, as realizations of the random vari00ables W1 , . . . , Wm−1
with S00 having the uniform distribution of the normed (random) input Ck /M to the kth exponentiation. Similarly, we interpret q1,k , q2,k , . . .
as realizations of the random variables W1 , W2 , . . ..

W. Schindler & C. D. Walter, A Combined Timing & Power Attack

253

Consequently, we have to study the stochastic processes W10 , W20 , W30 , W50 , . . . ,0
Wm−1
and W1 , W2 , . . .. However, the situation is much more complicated thanin the case of the standard Montgomery algorithm considered in [12] because therandom variables S1 , S2 , . . . are neither independent nor identically distributed.
Their distribution depends on the sequence of operations T (1), T (2), . . ..
Definition 3. (i) For i ∈ F ∪{2}, w ∈ {0, 1} and indices of the components
1
ranging over F ∪{0, 2}, let the subset D0 (i; w) ⊆ [0, 1)×[0, γ −1 ) 2 m+1 be given0by those vectors (s00 , . . . , s0m−1 ) for which v10 , . . . , vm−1
∈ [0, 1) exist such that000s00 , . . . , s0m−1 , v10 , . . . , vm−1
satisfy (1)-(3) in place of S00 , . . . , Sm−1
, V10 , . . . , Vm−1
and, additionally, the component s0i and its predecessor must result in w wheninserted into whichever of (5), (6) or (7) describes Wi0 . Thus, for example, by(6) the vectors (s00 , . . . , s0m−1 ) in D0 (1; 1) satisfy s01 < s00 (R2 (mod M ))/R, andby (7) those in D0 (2i−1; 1) satisfy s02i−1 < s02i−3 s02 γ.
(ii) For i ≤ j ≤ i+f −1, w ∈ {0, 1} and t ∈ T , define Df (i, j; w, t) ⊆ [0, γ −1 )f +1
to be the subset of vectors (si−1 , . . . , si+f −1 ) for which there are vi , . . . , vi+f −1 ∈[0, 1) such that si−1 , . . . , si+f −1 , vi , . . . , vi+f −1 satisfy (4) in place of Si−1 , . . .,Si+f −1 , Vi , . . . , Vi+f −1 with the assumption that T (j) = t and, additionally, thecomponent sj and its predecessor must result in w when inserted into the instanceof (8) which describes Wj for T (j) = t. Thus, for example, the elements of
Df (i, j; 1, ‘Mk ’) satisfy the constraint sj < sj−1 s0k γ.
Remark 1. As already mentioned in Sect. 5, there may also be scenarios of practical interest which imply distributions of S00 other than the uniform distributionof assertion (x). For signing with constant prefixed padding, for instance, the random variable S00 can be assumed to have a Dirac (= single-point) distribution
due to the definition of S10 . Generally speaking, the distribution of S00 influences
the conditional density g(·|·) in Lemma 2(i) and hence implicitly the conditional
probabilities in Theorem 1 and the optimal decision strategy. Then it is necessary to adjust the derivation of g(·|·) to the concrete distribution of S00 but
otherwise the remaining steps in this and the forthcoming sections pass throughidentically.
The (conditional) probability of a given er-vector can be described using the setsof Definition 3:
Lemma 2. (i) Assume the random variable S00 is equidistributed on [0, 1). Then10
) on [0, 1) 2 m+1
the conditional distribution of the random vector (S10 , . . . , Sm−10000under the condition W1 =w1 , . . . , Wm−1 =wm−1 has Lebesgue probability density0) :=g(s01 , . . . , s0m−1 | w10 , . . . , wm−1

R1
0

R
1
[0,1)×[0,γ −1 ) 2 m+1

1∩i∈F ∪{2} D0 (i;wi0 ) (s00 , s01 , . . . , s0m−1 ) ds00
1∩i∈F ∪{2} D0 (i;wi0 ) (s00 , s01 , . . . , s0m−1 ) ds00 ds01 · · · ds0m−1.

(9)Cryptography and Coding, LNCS 2898, c Springer 2003

254(ii) The distribution of Si−1 has a Lebesgue density, say hi−1 . Moreover,00Prob(Wi = wi , . . . , Wi+f −1 = wi+f −1 | W10 = w10 , . . . , Wm−1
= wm−1) = (10)Z
0g(s01 , . . . , s0m−1 | w10 , . . . , wm−1
) · hi−1 (si−1 ) ×
1[0,γ −1 ) 2 m+f +2

× 1∩i+f −1 Df (i,u;wi ,T (u)) (si−1 , . . . , si+f −1 ) ds01 · · · ds0m−1 dsi−1 dsi · · · dsi+f −1 .
u=i(iii) If S0 = Sr0 then00Prob(W1 = 1 | W10 = w10 , . . . , Wm−1
= wm−1
) =
(11)
Z
2
0
g(s01 , . . . , s0m−1 | w10 , . . . , wm−1
) · max{0, 1−γ −1 +s0r γ} ds01 · · · ds0m−1 .
1[0,γ −1 ) 2 m+1
1

Proof. We first note that {(s00 , . . . , s0m−1 ) ∈ [0, 1) × [0, γ −1 ) 2 m+1 | W10 = w10 , . . . ,
T
0
0
Wm−1
= wm−1} = i∈F ∪{2} D0 (i, wi0 ). For the moment let Ψ : [0, 1)m/2+2 →0[0, 1) × [0, γ −1 )m/2+1 be given by Ψ (s00 , v10 , . . . , vm−1
) := (s00 , s01 , . . . , s0m−1 ). By
0
this we mean that the coordinates si of image points are determinedby in
stances of the equation (3) of the form s0i = χ s0i−2 s02 γ + vi0 when i > 2
and the similar ones from equations (1) and (2) for i = 1, 2. The mapping Ψ
is injective (though not surjective) and differentiable almost everywhere with
0
0
Jacobian 1. As Ψ (S00 , V10 , . . . , Vm−1
) = (S00 , S10 , . . . , Sm−1
) and since the ran000
dom variables S0 , V1 , . . . , Vm−1 are independent and equidistributed on [0, 1) thetransformation theorem (applied to the inverse Ψ −1 where it is differentiable)
0
implies that the random vector (S00 , S10 , . . . , Sm−1
) has constant density on the
m/2+2
image Ψ ([0, 1)). The definition of conditional probabilities and computing
the marginal density with respect to s00 proves (9). The first assertion of (ii)follows immediately from Lemma 3 (in the Appendix) with G = IR, µ = λ,2
ν = λ |[0,1) and τ (depending on T (i−1)) denoting the distribution of Si−2
γ or
0
Si−2 Sj γ for a particular index j∈F . Equation (10) can be verified in a similar
way to (9). For fixed s00 , . . . , s0m−1 we define Ψs : [0, γ −1 ) × [0, 1)f → [0, γ −1 )f +1
by Ψ (si−1 , vi , vi+f −1 ) := (si−1 , . . . , si+f −1 ). Again, Ψs is almost everywhere differentiable with Jacobian 1, and the transformation theorem completes the proofof (ii) as the random variables Si−1 , Vi , . . . , Vi+f −1 are independent and equidistributed on [0, γ −1 ) or [0, 1), resp. (Note that Ψs−1 (si−1 , ∗) = (si−1 , ∗).) The
first Montgomery multiplication in the computation phase is a squaring. Hence22
Prob(W1 = 1) = Prob(Sr0 γ + V1 ≥ γ −1 ). As Sr0 γ ∈ [0, γ −1 ) this proves (iii). tuRemark 2. In the Appendix, Theorem 2 (i) to (iv) and (v) respectively consider
the fictional situations that the computation phase consists only of squarings ormultiplications by a fixed table entry. The distributions of the S1 , S2 , . . . thenconverge respectively to f · λ[0,γ −1 ) and f(s0j ) · λ[0,γ −1 ) for fixed s0j ∈ [0, γ −1 ).
These were graphed in Figure 1 for γ = 0.525 and C (j) = 1.5γR. In fact, thedensity hi−1 (·) depends on T (1), . . . , T (i−1) and s01 , . . . , s0m−1 (cf. Sect. 10).

W. Schindler & C. D. Walter, A Combined Timing & Power Attack

255

Theorem 1 quantifies the probabilities for the different type vectors of theMontgomery multiplications i, . . . , i+f −1 given the observed extra reductions:
Theorem 1. Let θ = (ωi , . . . , ωi+f −1 ) ∈ T f . If T (i) = ωi , . . . , T (i+f −1) =ωi+f −1 then let pθ ((q i,...,i+f −1;k )1≤k≤N | (q 0k )1≤k≤N ) denote the conditional probability for the er-vectors (q i,...,i+f −1;k )1≤k≤N if (q 0k )1≤k≤N were observed in theinitialization phase. Then,pθ ((q i,...,i+f −1;k )1≤k≤N | (q 0k )1≤k≤N) ≈

N Z
Y
k=1

0
0
g(s01 , ..., s0m−1 | q1,k, ..., qm−1,k) ×
1[0,γ −1 ) 2 m+f +2

×hi−1 (si−1 ) · 1∩i+f −1 Df (i,u;wu ,ωu ) (si−1 , ..., si+f −1 ) ds01 ...ds0m−1 dsi−1 ...dsi+f −1 (12)u=i

If r is the left-most block (i.e. digit) of the secret exponent after recoding then
Prob ((q1,k )1≤k≤N | (q 0k )1≤k≤N ) ≈
(13)
Z
N
Y
2
0
0
g(s01 , ..., s0m−1 | q1,k, ..., qm−1,k) max{0, 1−γ −1 +s0r γ} ds01 ...ds0m−1 .
k=1
1[0,γ −1 ) 2 m+1

Proof. According to our mathematical model we interpret the observed er-vectors
00
q 0k and q i,...,i+f −1;k as realizations of random variables W1,k, . . . , Wm−1,k
andWi,k , . . . , Wi+f −1,k respectively, where the latter correspond to T (i) = ωi , ...,T (i+f −1) = ωi+f −1 . Theorem 1 is an immediate consequence of Lemma 2 andthe mathematical model.
tu

7

A priori Distribution

In Section 9 we determine an optimal decision strategy for simultaneous guessingof the types T (i), . . . , T (i+f −1) of the ith,. . . ,(i+f −1)th Montgomery multiplications. It seems to be reasonable for the attacker to choose the hypothesis θwithin the set Θ ⊆ T f of all admissible hypotheses which is the most likely one,given the observed er-vectors. In the sliding window exponentiation scheme amultiplication using a particular table entry is preceded by at least b = log2 msquarings. Consequently, for the chosen f ,Θ = θ0 ∪ {θk,j | 1 ≤ k ≤ f ; 1 ≤ j ≤ m−1 for odd j}

if f ≤ b+1

(14)

where
θ0 := (‘S’, . . . , ‘S’) means T (i) = ‘S’, . . ., T (i+f −1) = ‘S’ andθk,j := (‘S’, . . . , ‘S’, ‘Mj ’, ‘S’, . . . , ‘S’) means
T (i+k−1) = ‘Mj ’ but T (v) = ‘S’ for v 6= i+k−1.
However, the admissible hypotheses occur with different probabilities. The
optimal decision strategy in Section 9 exploits this fact. In the present section
we determine a distribution η on Θ which approximates the exact distribution

Cryptography and Coding, LNCS 2898, c Springer 2003

256of the admissible hypotheses and which depends on the secret key. We call η the(approximate) a priori distribution, and ηk,j denotes the approximate probability that (T (i), . . . , T (i+f −1)) = θk,j for randomly chosen i.
When re-coding, the secret exponent d is divided into blocks (digits) of length
1 and b. If d is assumed to be random then both block lengths should occur withthe same frequency, and the average block length is about (b+1)/2. Hence weshould expect about n/(b+1) blocks of length b and n/(b+1) blocks of length 1
where n is the bit length of the modulus M . Consequently, about 2n/(b+1)mblocks of length b should equal any given odd exponent digit j. Thus we expect
this many vectors (T (i), . . . , T (i+f −1)) of type θk,j for 1 ≤ k ≤ f . As there
are about n + n/(b+1) = (b+2)n/(b+1) Montgomery multiplications (including
squares) we set
η1,1 := · · · := ηf,m−1 :=η0 := 1 −

8

1
2 mf
(b+2) 21 m=n(b+1)=(b+1) 21 m(b+2)n

b+2−f
b+2

if f ≤ b+1.

1
1
2 m(b+2)

and(15)

Error Detection and Correction

It seems to be unhelpful to consider error detection and error correction strategies
before the decision strategy itself has been derived. However, the optimal decision
strategy considers the different types of possible error. Roughly speaking, it tries
to avoid estimation errors but ‘favours’ those kinds of errors which are easier todetect and correct than others. The following example illuminates the situation.
Example 1. Let b = 2 (i.e. m = 4), and assume that the secret exponent d isgiven by . . . |0|01|0|01|0| . . .. The correct type sequence is then given by. . . , ‘S’, ‘S’, ‘S’, ‘M1 ’, ‘S’, ‘S’, ‘S’, ‘M1 ’, ‘S’, . . .
whereas the following a), b) and c) are possible estimation sequences:a) . . . , ‘S’, ‘S’, ‘S’, ‘M1 ’, ‘S’, ‘M3 ’, ‘S’, ‘M1 ’, ‘S’, . . .
b) . . . , ‘S’, ‘S’, ‘S’, ‘S’, ‘S’, ‘S’, ‘S’, ‘M1 ’, ‘S’, . . .
c) . . . , ‘S’, ‘S’, ‘S’, ‘M3 ’, ‘S’, ‘S’, ‘S’, ‘M1 ’, ‘S’, . . .
Each of the subsequences a), b), and c) contains exactly one false guess. The error
in a) (‘M3 ’) is obvious as the number of squarings between two multiplications
must be at least b = 2. This type-a error (‘Mj ’ instead of ‘S’) is usually easy
to detect if its occurrence is isolated, i.e. if there are no further type-a or type-b
errors (‘S’ instead of ‘Mj ’) within a neighbourhood of the error. Then one orat most two positions remain for which exactly one guess is false, and we callthe type-a error locally correctable. A type-a error is not locally correctable if it
occurs within a long series of squarings or if bursts of type-a and type-b errors
occur. Then we call it a global type-a error. The type-b errors and type-c errors(‘Mi ’ instead of ‘Mj ’) illustrated in sequences b) and c) are less obvious. If all
type-a errors have been corrected the attacker knows the number of type-b errors(since the number of squarings equals the bit length d minus 1) but not their

W. Schindler & C. D. Walter, A Combined Timing & Power Attack

257

positions. In particular, type-b and type-c errors are global errors. Of course,
to correct type-b and type-c errors it is reasonable first to change those guesses
where the respective decisions have been “close” and then to check the new
exponent estimator (cf. Sect. 10).

9The Optimal Decision Strategy

The preliminary work has now been done. Here the pieces are assembled to derive
an optimal decision strategy for guessing the types of f consecutive Montgomery
multiplications simultaneously when 1 ≤ f ≤ b+1. Therefore, we interpret theestimation of T (i), . . . , T (i+f −1) as a statistical decision problem.
Roughly speaking, in a statistical decision problem the statistician (here theattacker) observes a sample ω ∈ Ω (here the observed extra reduction vectors(q 0k , q i,...,i+f −1,k )1≤k≤N ) which he interprets as a realization of a random variable
X. The distribution pθ of X depends on the unknown parameter θ ∈ Θ which
has to be guessed (here θ = (T (i), . . . , T (i+f −1))). The decision strategy clearly
depends on the observation ω but also considers the a priori distribution η(cf. Sect. 7) which quantifies the likeliness of the possible parameters and the‘damage’ caused by the possible guessing errors. The ‘damage’ is quantified by
the loss function s(θ, a) where θ ∈ Θ denotes the true parameter whereas a ∈ Θstands for a potential guess. In our case the loss function corresponds to theeffort which is necessary for the detection, localization and correction of wrong
guesses (cf. Sects. 8 and 10). Of course, correct decisions do not cause any loss,
i.e. s(θ, θ) = 0 for all θ ∈ Θ. A decision strategy is optimal if its expected loss
attains a minimum.
Optimal Decision Strategy. Let the a priori distribution η be given by (15).
Let τopt ((q 0k , q i,...,i+f −1,k )1≤k≤N ) := a∗ if the sumXs(θ, a0 )pθ ((q i,...,i+f −1;k | q 0k )1≤k≤N ) η(θ)
(16)
θ∈Θ

is minimal for a0 = a∗ (i.e. the attacker picks a∗ ∈ Θ when he observes the vector (q 0k , q i,...,i+f −1,k )1≤k≤N ). Then τopt is optimal among all decision strategies
which estimate T (i), . . . , T (i+f −1) simultaneously.
Proof. The proof of the analogous assertion in Section 7 of [12] can be re-applied
here almost literally. The conditional probabilities pθ (·|·) were computed in Theorem 1.
tu

10Experimental Results

Although theoretical considerations were not significantly more difficult for f ≥1, in this section we fix f =1 in order to simplify the calculations (cf. [12], §8).
Thus the types of the particular Montgomery multiplications are guessed separately. The restriction on f means it is convenient to attack a sliding windowCryptography and Coding, LNCS 2898, c Springer 2003

258

exponentiation scheme, and m = 4 (i.e. b = 2) was chosen for a simulation.
00Extra reduction values q1,k, . . . , qm−1,kand q1,k , q2,k , . . . were obtained from thesimulation using pseudo-randomly chosen moduli M and inputs C1 , . . . , CN .
We first determined the optimal decision strategy given in Section 9. We used
the loss function given by s(‘S’, ‘Mj ’) = 1 (type-a error), s(‘Mj ’, ‘S’) = 1.5 (typeb error) and s(‘Mi ’, ‘Mj ’) = 2.5 for i 6= j (type-c error). Equation (15) gives thea priori distribution η(‘S’) = 0.75 and η(‘M1 ’) = η(‘M3 ’) = 0.125. Next, we
computed approximations as follows for the density hi−1(k) for each of the threealternatives θ = ‘S’, θ = ‘M1 ’ and θ = ‘M3 ’. First, Theorem 2 was applied toobtain the ‘pure’ limit densities f (cf. Thm. 2(iii)) and f(s) (cf. Thm. 2(v)). The
iterates of the densities fup (x) := 1[0,1) (x) and flow (x) := 1[γ −1 −1,γ −1 ) (cf. Thm.
2(iv)) squeeze the respective limit distribution. The convergence is monotonic
and exponentially fast (Thm. 2(iv)). If T (i) = ‘Mj ’ then at least two squarings
had been carried out just before. As the convergence to f is exponentially fast
we assumed hi−1(k) ≈ f in that case. For the hypothesis T (i) = ‘S’ we set
hi−1(k) := η0 ·f + η1 ·f(s1 ) + η3 ·f(s3 ) with η1 = η3 = 0.125 and η0 = 0.75, andsj denoting the ratio of table entry j divided by the modulus M . Then we put
the pieces together, determined the conditional probabilities p‘S ’(·), p‘M1 ’(·) andp‘M3 ’(·) using Theorem 1, and so derived the optimal decision strategy.
Table 1. Average number of errors per 100 guesses with b = 2, f = 1.
M/R
0.99
0.99
0.85
0.85
0.85
0.70

N
350
400
400
450
500
700

type-a global type-a type-b
0.53
0.11
0.29
0.37
0.07
0.21
0.74
1.58
0.12
0.54
0.11
0.62
0.44
0.08
0.03
1.24
0.19
0.22

type-c
0.67
0.04
0.06
0.03
0.25
0.35

Applying this optimal decision strategy we obtained guesses Te(1), Te(2), . . ..
A large number of simulation runs gave the results in Tables 1 to 3. The “type-a”
column in Table 1 covers all errors of type a, namely both the locally correctableand global type-a errors. In a first step the attacker corrects the locally correctable type-a errors. Usually, he knows a reference equation y d ≡ x(modM ), e.g.
a signature. Using this he can check whether a guess de for d is correct. As alreadyobserved in Section 8, the number of global errors is relevant for the practicalfeasibility of the attack. This is the sum of the type-b, type-c and global type-aerrors. Table 2 gives the percentage of trials for which the number of such global
errors is no more than a given bound. For example, at most one global error
occurred in 76% of the trials for the parameter set M/R ≈ 0.85, N = 500,
n = 512. Clearly, for the sake of efficiency the attacker first tries to change thoseguesses for which the decision has been ‘close’.
A successful attack on a 512-bit exponent requires about 680 correct guesses.
For this, about 2 · 680 = 1360 hypotheses have to be rejected. To each rejected

W. Schindler & C. D. Walter, A Combined Timing & Power Attack

259

Table 2. Number of global errors.
M/R
0.99
0.99
0.85
0.85
0.85
0.70

N
350
400
400
450
500
700

n
512
512
512
512
512
512

0
10%
16%
19%
33%
46%
35%

≤1
31%
46%
43%
62%
76%
60%

≤2
49%
62%
60%
80%
90%
71%

≤3
64%
78%
71%
90%
97%
76%

hypothesis about the types of a sequence of f =1 multiplicative operations, weassign the ratio between the expected loss if this hypothesis had been chosen
divided by the expected loss for the hypothesis chosen in this decision. The
rejected hypotheses are ordered using these ratios, that with the smallest ratio(i.e. the most likely alternative) first. If the estimator de is false the attacker
replaces one, two or three guesses respectively by those from the rejected list,
beginning with the first, i.e. that with lowest ratio.
Table 3 gives the average rank of the lowest correct hypothesis which has
been rejected for a given number of global errors. For instance, if there were
three global errors, and the correct guesses for them were ranked 3, 29 and 53 in
the list, then the rank of the lowest would be 53. The second row of the table saysthat if there are exactly three global errors for parameters M/R ≈ 0.99, N = 400,n = 512 then 57 is the average rank of the lowest correct hypothesis which was
initially rejected. If the lowest rank is ≤ 100 (which would
 normally be the casefor an average of 57), the correction requires at most 100= 161700 evaluations
3of the reference equation (neglecting the unsuccessful efforts to correct exactly
1 or 2 global errors). This is clearly computationally feasible.
Table 3. Average rank of the last correct hypothesis for 1, 2 or 3 global errors.
M/R
0.99
0.99
0.85
0.85
0.85
0.70

N
350
400
400
450
500
700

n
512
512
512
512
512
512

1
2
3
31
66
63
30
25
57
39
57
55
22
37
59
24
57
70
63 132 271

The conditional probabilities (Section 6), and hence the optimal decision
strategy, only depend on the ratio γ = M/R. In our simulations we assumed
that the attacker knows this ratio. However, our attack is also feasible if theattacked device uses the Chinese Remainder Theorem (CRT). Then the attacker
uses the extra reductions within the initialization phase and known squarings
from the computation stage to estimate the parameter γ. The moduli M for the
exponentiations are the prime factors of the RSA modulus M 0 =p1 p2 . For thesecret RSA key d0 , the attacker guesses the exponents actually used, namely d =Cryptography and Coding, LNCS 2898, c Springer 2003

2600d0 (mod (pi −1)) for i = 1 or 2. If the guess de for d is correct then gcd(C d (modM 0 ) − C de(mod M 0 ), M 0 ) = pi and, similarly, gcd(C − C dee (mod M 0 ), M 0 ) = pi .
Since the parameter γ has to be estimated the error probability for a singulardecision increases somewhat (cf. [12], first paragraph of Sect.10). However, since
CRT involves an exponent of only half the length, the number of wrong guesses
per exponentiation will be smaller and so the attack more likely to be successful.

11

Conclusion

A timing attack on RSA implementations has been given further detail in the
more complex situation of modular reductions being driven by a register length
bound rather than a modulus bound. Graphs of the limiting distributions weredrawn illustrating one source of the attack. Another source was the combinationof exact conditional probabilities for the modular reductions with statisticaldecision theory for treating sequences of modular multiplications. This reduces
the sample size necessary to deduce the secret RSA key from side channel leakage.
The resulting powerful methods reduce the number of errors far enough for theircorrection to be computationally feasible for keys with standard lengths using
data obtained well within the normal lifespan of a key.

References
1. J.-F. Dhem, F. Koeune, P.-A. Leroux, P. Mestré, J.-J. Quisquater & J.-L. Willems,
A practical implementation of the Timing Attack, Proc. CARDIS 1998, J.-J.
Quisquater & B. Schneier (editors), LNCS 1820, Springer-Verlag, 2000, pp. 175–
190.
2. D. E. Knuth, The Art of Computer Programming, vol. 2, Seminumerical Algorithms, 2nd Edition, Addison-Wesley, 1981, pp. 441–466.
3. Ç. K. Koç, Analysis of Sliding Window Techniques for Exponentiation, Computers
and Mathematics with Applications 30, no. 10, 1995, pp. 17–24.
4. P. Kocher, Timing attack on implementations of Diffie-Hellman, RSA, DSS, andother systems, Proc. Crypto 96, N. Koblitz (editor), LNCS 1109, Springer-Verlag,
1996, pp. 104–113.
5. P. Kocher, J. Jaffe & B. Jun, Differential Power Analysis, Advances in Cryptology− Crypto ’99, M. Wiener (editor), LNCS 1666, Springer-Verlag, 1999, pp. 388–397.
6. R. Mayer-Sommer, Smartly Analyzing the Simplicity and the Power of Simple
Power Analysis on Smartcards, Cryptographic Hardware and Embedded Systems(Proc CHES 2000), C. Paar & Ç. Koç (editors), LNCS 1965, Springer-Verlag,
2000, pp. 78–92.
7. 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,
pp. 144–157.
8. V. Miller, Use of Elliptic Curves in Cryptography, Proc. CRYPTO ’85,
H. C. Williams (editor), LNCS 218, Springer-Verlag, 1986, pp. 417–426.
9. P. L. Montgomery, Modular Multiplication without Trial Division, Mathematics ofComputation 44, no. 170, 1985, pp. 519–521.

W. Schindler & C. D. Walter, A Combined Timing & Power Attack

261

10. R. L. Rivest, A. Shamir & L. Adleman, A Method for obtaining Digital Signatures
and Public-Key Cryptosystems, Comm. ACM 21, 1978, pp. 120–126.
11. W. Schindler, A Timing Attack against RSA with Chinese Remainder Theorem,
Cryptographic Hardware and Embedded Systems (Proc CHES 2000), C. Paar &Ç. Koç (editors), LNCS 1965, Springer-Verlag, 2000, pp. 109–124.
12. W. Schindler, A Combined Timing and Power Attack, Public Key Cryptography(Proc PKC 2002), P. Paillier & D. Naccache (editors), LNCS 2274, SpringerVerlag, 2002, pp. 263–279.
13. W. Schindler, Optimized Timing Attacks against Public Key Cryptosystems, Statistics & Decisions 20, 2002, pp. 191–210.
14. C. D. Walter, Montgomery Exponentiation Needs No Final Subtractions, Electronics Letters 35, no. 21, October 1999, pp. 1831–1832.
15. C. D. Walter, Precise Bounds for Montgomery Modular Multiplication and Some
Potentially Insecure RSA Moduli, Proc. CT-RSA 2002, B. Preneel (editor), LNCS
2271, Springer-Verlag, 2002, pp. 30–39.
16. 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, pp. 192–207.

Appendix
Lemma 3. Let τ and ν denote probability measures on a locally compact abeliangroup G. If µ is a Haar measure on G and ν has a µ-density then the convolution
product τ ∗ ν also has a µ-density.
R
Proof. For any measurable B ⊆ G we have τ ∗ ν(B) = G ν(B−x) τ (dx). Ifµ(B) = 0 then µ(B−x) = 0 and hence ν(B−x) = 0. This proves the lemma. tuTheorem 2. Suppose γ ∈ (0.5, 1), and let F and χ: [0, γ −1 + 1) → IR be defined
as in Section 6. Assume further that U0 , V1 , V2 , . . . denote independent randomvariables where U0 assumes values on [0, γ −1 ), while V1 , V2 , . . . are equidistributedon the unit interval [0, 1). Finally, let Un+1 := χ(Un2 γ + Vn+1 ) for all n ∈ IN.
(i) Regardless of the distribution of U0 , for each n ≥ 1 the distribution µn of
Un has a Lebesgue density fn . Moreover, fn (x) = 1 for x ∈ [γ −1 −1, 1) andfn (x) + fn (x+1) = 1 for x ∈ [0, γ −1 −1).
(ii) For n ≥ 2 we have
Z √
xγ −1

fn+1 (x) =fn (u) dufor x ∈ [0, γ −1 −1).

(17)

0

(iii) Regardless of the distribution of U0 we have
kfn+1 − fn k∞ :=sup|fn+1 (x) − fn (x)| ≤γ −1 −1

n−1

kf2 − f1 k∞ (18)x∈[0,γ −1 )for all n ≥ 2. In particular, the sequence f1 , f2 , . . . converges uniformly to aprobability density f : [0, γ −1 ) → [0, 1] which does not depend on the distribution

262

Cryptography and Coding, LNCS 2898, c Springer 2003

of U0 . To be precise, f (x) = 1 for x ∈ [γ −1 −1, 1), f (x) + f (x+1) = 1 forx ∈ [0, γ −1 −1), and f is the unique solution of (17) possessing these properties,
i.e. (17) holds with f in place of fn and fn+1 .
(iv) If f1 ≤ f on [0, γ −1 −1) then also fn ≤ f for all n ≥ 1. If f1 ≤ f2 then thesequence f1 , f2 , . . . is monotonically increasing on [0, γ −1 −1). Similarly, f1 ≥ f
on [0, γ −1 −1) implies fn ≥ f for all n ≥ 1, and if f1 ≥ f2 then the sequence
f1 , f2 , . . . is monotonically decreasing on [0, γ −1 −1). If the distribution of U0 has
a Lebesgue density f0 then the assertions of (iv) even hold for f0 , f1 , . . . in placeof f1 , f2 , . . ..
0(v) Let U00 := U0 and Un+1:= χ(Un0 sγ + Vn+1 ) for all n ∈ IN where s ∈ [0, γ −1 )is fixed. Then all assertions from (i) to (iv) can be transferred almost literally tothis case. In particular, for x ∈ [0, γ −1 −1) we havefn+1 (x) = R x/sγ0fn (u) du

if x < sotherwise.

1

(19)

The limit distribution f(s) of f1 , f2 , . . . is the unique solution of (19) with f(s) (x)=1 for x ∈ [γ −1 −1, 1) and such that f(s) (x) + f(s) (x+1) = 1 for x ∈ [0, γ −1 −1).
Proof. To prove the first assertion of (i) we apply Lemma 3 with G = IR and2µ = λ while τ is the distribution of Un−1γ and ν the restriction of the Lebesgue−12
measure to [0, 1). If γ −1 ≤ a < b ≤ 1 we have Un ∈ [a, b) iff Un−1
γ + Vn ∈[a, b) ∪ [a+1, b+1). As Un−1 and Vn are independent, and χ coincides with the
reduction modulo 1 on this union and Vn is equidistributed on [0, 1), this proves
the second assertion of (i). However, for any 0 ≤ a < b ≤ γ −1 −1, we have2
Un ∈ [a, b) ∪ [a+1, b+1) iff Un−1
γ + Vn ∈ [a, b) ∪ [a+1, b+1) ∪ [a+2, b+2). Frommod 1 = mod 1 ◦ χ we obtain the final assertion of (i) as Vn is equidistributedon [0, 1). For x ∈ [0, γ −1 −1) the pre-image χ−1 (x) equals x and henceZ √xγ −1

Z x
Prob(Un+1 ≤ x) =fn+1 (u) du =√Z0

fn (u)Prob(u2 γ + Vn ≤ x) du

0

xγ −1

fn (u)(x − u2 γ) du
Z √

=
0

Z √xγ −1

fn (u) du − γ

=x
0

xγ −1

fn (u)u2 du.

0p
If fn is continuous at xγ −1 differentiating the left- and the right-hand side
verifies assertion (ii) for fn+1 (x). We denote the density of U12 γ + V2 by h2 forthe moment. Applying the convolution formula for densities (to that of U12 γ andV2 ) yields |h2 (x + s) − h2 (x)| ≤ Prob(U12 γ ∈ [−s, 0] ∪ [1, 1 + s]) for |s| < 0.5. As[−s, 0] ∪ [1, 1 + s] converges to {0, 1} the right-hand probability converges to 0 as
s → 0, i.e. h2 is continuous at x. As x was arbitrary this proves the continuity of
h2 , and f2 has at most two discontinuity points in (0, γ −1 ), namely γ −1 −1 and1. This proves (ii) for n = 1 since densities may be defined arbitrarily on zero

W. Schindler & C. D. Walter, A Combined Timing & Power Attack

263

sets. For arbitrary n, assertion (ii) follows by induction. Clearly,
kfn+1 − fn k∞ =|fn+1 (x) − fn (x)|supx∈[0,γ −1 −1)Z √xγ −1=

(fn (u) − fn−1 (u)) dusupx∈[0,γ −1 −1)

0

Z z
≤

(fn (u) − fn−1 (u)) dusupy,z∈[0,γ −1 −1)≤
γ −1 −1 kfn − fn−1 k∞ .

y

The first inequality follows from the fact that fn (x) = fn−1 (x) = 1 on [γ −1 −1, 1)
while fn (x) + fn (x+1) = 1 for x ∈ [0, γ −1 −1). Equation (18) follows by induction. Similarly, one concludes kfn − fn∗ k∞ ≤ (γ −1 −1)n−2 kf2 − f2∗ k∞ for arbitrary sequences f1 , f2 , . . . and f1∗ , f2∗ , . . .. This shows the uniqueness of f and, as
f1 , f2 , . . . converges uniformly, f fulfils (17). If, in addition, f1 (x) ≤ f2 (x) for allx ∈ [0, γ −1 −1) then by induction we obtain
Z √
xγ −1

fn+1 (x) − fn (x) =(fn (u) − fn−1 (u)) du
0

Z
=

√
[0,

√

xγ −1 )∩[0,γ −1 −1)∩{u:u>(fn (u) − fn−1 (u)) duxγ −1 −1}

≥ 0.

Replacing fn by f we obtain the first assertion of (iv), and the second part canbe shown similarly. Assertion (v) can be verified in same way as (i) to (iv). tu