# Randomizing the Montgomery Powering Ladder

Duc-Phong Le, Chik How Tan, Michael Tunstall

► To cite this version:

Duc-Phong Le, Chik How Tan, Michael Tunstall. Randomizing the Montgomery Powering Ladder. 9th Workshop on Information Security Theory and Practice (WISTP), Aug 2015, Heraklion, Crete, Greece. pp.169-184, 10.1007/978-3-319-24018-3_11. hal-01442541

HAL Id: hal-01442541

https://inria.hal.science/hal-01442541

Submitted on 20 Jan 2017

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Randomizing the Montgomery Powering Ladder

Duc-Phong Le¹, Chik How Tan¹, and Michael Tunstall²

¹ Temasek Laboratories, National University of Singapore,
5A Engineering Drive 1, #09-02, Singapore 117411
{tslld,tsltch}@nus.edu.sg

² Rambus Cryptography Research Division,
425 Market Street, 11th Floor, San Francisco,
CA 94105, United States

michael.tunstall@cryptography.com

**Abstract.** In this paper, we present novel randomized techniques to enhance Montgomery powering ladder. The proposed techniques increase the resistance against side-channel attacks and especially recently published correlation collision attacks in the horizontal setting. The first of these operates by randomly changing state such that the difference between registers varies, unpredictably, between two states. The second algorithm takes a random walk, albeit tightly bounded, along the possible addition chains required to compute an exponentiation. We also generalize the Montgomery powering ladder and present randomized (both left-to-right and right-to-left) *m*-ary exponentiation algorithms.

**Keywords:** Montgomery Powering Ladder, Side-Channel Analysis, Countermeasures.

## 1 Introduction

Side-channel analysis is one of the most serious threats to the security of a given implementation of a cryptographic algorithm. In the traditional model, a given cryptographic algorithm is typically proven secure against various attacks under assumptions regarding the computational complexity of an attack. However, in a more practical scenario, Kocher noted that the time required to compute a cryptographic algorithm could reveal information on the keys used [1]. This was then extended to analyze differences in the power consumption of a microprocessor [2] and the variations in the surrounding electromagnetic field [3, 4]. The simplest such attack is based on the inspection of an acquired power consumption (resp. electromagnetic emanation) trace to derive information. This is referred to as Simple Power Analysis (SPA) (resp. Simple ElectroMagnetic Analysis (SEMA)). The exploitation of statistical differences in the instantaneous power consumption proposed by Kocher et al. [2] is termed Differential Power Analysis (DPA) (resp. Differential ElectroMagnetic Analysis (DEMA)), and alternatives have been proposed using, for example, a model and Pearson's correlation coefficient [5] or mutual information [6].
In choosing an exponentiation algorithm for a secure implementation, one needs to consider the possible attacks that could be applied. One can often discount attacks where input values need to be known, such as the doubling attack [7], template attacks [8] or DPA [2]. Such attacks can typically be prevented by blinding input values [9] or by using a suitable padding scheme. That is, these attacks are not typically prevented by choosing a specific exponentiation algorithm. However, one also needs to consider attacks based on inspecting a limited number of traces, such as SPA [2], or power attacks in the horizontal setting [10, 11]. The later was first introduced by Walter [10]. His attack, the so-called Big Mac attack, applied to *m*-ary exponentiation, although only simulated attacks are described. Clavier et al. [12] then exploited the collision correlation between selected points from two subtraces to derive information. Recent work by Bauer et al. [13] has also detailed how one could apply such collision attacks to implementations of scalar multiplications over elliptic curves. Witteman et al. [14] demonstrated that this attack works on an ASIC implementation. Kim et al. [15] also determined how one could apply such an attack to the Montgomery ladder [16, 17]. The attack model was extended by Hanley et al. [18] to include an attacker that computes the correlation between carefully chosen points in a trace to detect where the output of one operation is used as the input to another operation.

In this paper, we present randomized variants of the Montgomery powering ladder that are resistant to SPA and power collision correlation attacks in the horizontal setting. The first algorithm is based on an amalgamation of two simple variants of the Montgomery powering ladder, where the content of the registers becomes *unpredictable*. The second algorithm is based on blinding addition chains, i.e. it takes tightly bounded random walks to compute an exponentiation. We also generalize the Montgomery powering ladder and present randomized *m*-ary exponentiation algorithms.

# 2 Preliminaries

## 2.1 Attack Model

In this paper we shall predominantly be considering an adversary that is able to take power consumption traces (or something equivalent) while a microprocessor is computing a group exponentiation algorithm. The adversary is then able to make deductions on what the microprocessor is computing. We shall consider three different attacks that require a limited number of traces when discussing the effects of our modifications to the Montgomery powering ladder.

1. The first attack is Simple Power Analysis (SPA) where one observes differences in the power consumption caused by different operations taking place. This was first demonstrated by Kocher et al. [2] who showed that one could, given a naïve implementation, observe the difference between operations during the computation of an exponentiation in $(\mathbb{Z}/N\mathbb{Z})^*$.
2. Another attack is the use of Pearson's correlation coefficient to detect collisions in variables to deduce key values [11]. For example, during the computation of an exponentiation in $(\mathbb{Z}/N\mathbb{Z})^*$ using Coron's square-and-multiply-always exponentiation algorithm, one could seek to determine the locations of multiplications with the same input. That is, operations that both take the same input should show a significant cross-correlation.

3. An extension to the collision correlation attack given above is where an adversary is able to detect collisions between the output of one operation and the input of another operation. This provides an attack where a complete defense is not possible. However, limiting the information available to an adversary can make the attack impractical since it has been shown that the error rate for this attack is significantly higher than a straightforward comparison of operations [18].

We do not consider attacks that require chosen inputs, such as the doubling attack [7] or statistical differences in the power consumption over time [2, 5]. This is because these attacks are typically prevented by padding or blinding the input by using a redundant representation where the details depend on the group being used [9, 19].

Typically, a blinded exponent is used, which is equivalent to the actual exponent, meaning that each trace must be attacked independently. The discussion of the security of the proposed algorithms will be largely informal, except where we wish to make specific claims about the amount of information available to an adversary.

## 2.2 The Montgomery Powering Ladder

The Montgomery powering ladder was originally proposed as a means of speeding up scalar multiplication over elliptic curves [16], and was later shown to be applicable to all multiplicatively written abelian groups [17].

We recall the description of the Montgomery powering ladder given by Joye and Yen [17]. We consider the problem of computing $y = x^k$ in $\mathbb{G}$ for inputs $x$ and $k$. Let $\sum_{i=0}^{n-1} k_i 2^i$ be the binary expansion of $\kappa$ with bit length $n$. For ease of expression we shall also denote this as $(k_{n-1}, \dots, k_0)_2$. The Montgomery powering ladder relies on the following observation. Defining $L_j = \sum_{i=j}^{n-1} k_i 2^{i-j}$ and $H_j = L_j + 1$, we have

$$L_j = 2L_{j+1} + k_j = L_{j+1} + H_{j+1} + k_j - 1 = 2H_{j+1} + k_j - 2 \quad (1)$$

and so we obtain

$$(L_j, H_j) = \begin{cases} (2L_{j+1}, L_{j+1} + H_{j+1}) & \text{if } k_j = 0, \\ (L_{j+1} + H_{j+1}, 2H_{j+1}) & \text{if } k_j = 1. \end{cases} \quad (2)$$
If we consider one register containing $x^{L_j}$ and another containing $x^{H_j}$ then (2) implies that

$$ (x^{L_j}, x^{H_j}) = \begin{cases} \left( (x^{L_{j+1}})^2, x^{L_{j+1}} \cdot x^{H_{j+1}} \right) & \text{if } k_j = 0, \\ x^{L_{j+1}} \cdot x^{H_{j+1}}, (x^{H_{j+1}})^2 & \text{if } k_j = 1. \end{cases} $$

Given that $L_0 = \kappa$ one can build an exponentiation algorithm that requires two group operations per bit of the exponent. Joye and Yen give several different versions of such an algorithm [17]. Algorithm 1 describes the most resistant to side-channel analysis version in their paper (as noted by Kim et al. [15] who describe implementations of cross correlation attacks on other versions).

<caption>**Algorithm 1: Montgomery Powering Ladder**</caption>

Input: $x \in \mathbb{G}$, an $n$-bit integer $\kappa = (k_{n-1}, k_{n-2}, \dots, k_0)_2$
Output: $x^\kappa$
1 $R_0 \leftarrow 1_\mathbb{G}$; $R_1 \leftarrow x$;
2 for $i = n - 1$ down to 0 do
3 & $R_{-k_i} \leftarrow R_{k_i} \cdot R_{-k_i}$;
4 & $R_{k_i} \leftarrow (R_{k_i})^2$;
5 end
6 return $R_0$

The Montgomery powering ladder, as described in Algorithm 1, has several properties that make it useful when defining a side-channel resistant implementation of an exponentiation. However, the Montgomery Powering ladder also has been shown to be vulnerable to recent collision correlation attacks in the horizontal setting [12, 18]. In the remainder of this paper we propose alternative versions of the Montgomery powering ladder to enhance its security against horizontal collision correlation attacks.

**Definition 1.** We define a variant of the Montgomery powering ladder as an exponentiation algorithm that has the following properties.

1. The algorithm uses two registers in the main loop containing group elements, both of which are updated in each iteration.

2. Each iteration of the main loop treats one bit of the exponent and contains no more than two group operations.

3. The operands in the first group operation will only involve one or both of the registers used in the main loop.

4. The operands in the second group operation can involve one or both of the registers used in the main loop and/or some precomputed value.
The 3rd and 4th properties allow for variants of the Montgomery ladder to be
defined. That is, the Montgomery ladder is in the set of possible algorithms that
satisfy these criteria.

For brevity in defining algorithms, we shall concentrate on the main loop
of the algorithm. The computation before and after the main loop may contain
**if**-statements. We shall not give fully secure versions where solutions are widely
known, e.g. dummy operations or redundant representations [9, 19, 20].

3 Randomizing the Montgomery Powering Ladder

We note that when computing $x^n$ using the Montgomery powering ladder, as
defined in Algorithm 1, then at the end of each iteration we will have the con-
dition where $R_1/R_0 = x$, or equivalently $R_0 \cdot x = R_1$. Thus, using the notation
given above, and we allow some precomputed values to be used in the algorithm,
then (2) can be rewritten as

$$
(L_j, H_j) = \begin{cases} (2 L_{j+1}, L_j + 1) & \text{if } k_j = 0, \\ (L_{j+1} + H_{j+1}, L_j + 1) & \text{if } k_j = 1. \end{cases} \quad (3)
$$

Implying that

$$
(x^{L_j}, x^{H_j}) = \begin{cases} ((x^{L_{j+1}})^2, x^{L_j} \cdot x) & \text{if } k_j = 0, \\ (x^{L_{j+1}} \cdot x^{H_{j+1}}, x^{L_j} \cdot x) & \text{if } k_j = 1. \end{cases}
$$

From which we can define Algorithm 2.

<table><caption>Algorithm 2: A Straightforward</caption>
  <thead>
    <tr>
      <th colspan="2">Variant I</th>
    </tr>
  </thead>
  <tbody>
    <tr>
      <td><b>Input:</b></td>
      <td>x &isin; G, an n-bit integer<br/>&kappa; = (k<sub>n-1</sub>, k<sub>n-2</sub>, ..., k<sub>0</sub>)<sub>2</sub></td>
    </tr>
    <tr>
      <td><b>Output:</b></td>
      <td>x<sup>&kappa;</sup></td>
    </tr>
    <tr>
      <td>1</td>
      <td>R<sub>0</sub> &leftarrow; 1<sub>G</sub> ; R<sub>1</sub> &leftarrow; x ;</td>
    </tr>
    <tr>
      <td>2</td>
      <td><b>for</b> i = n &minus; 1 <b>down to</b> 0 <b>do</b></td>
    </tr>
    <tr>
      <td>3</td>
      <td>&nbsp;&nbsp;&nbsp;&nbsp;R<sub>0</sub> &leftarrow; R<sub>0</sub> &middot; R<sub>k<sub>i</sub></sub> ;</td>
    </tr>
    <tr>
      <td>4</td>
      <td>&nbsp;&nbsp;&nbsp;&nbsp;R<sub>1</sub> &leftarrow; R<sub>0</sub> &middot; x ;</td>
    </tr>
    <tr>
      <td>5</td>
      <td><b>end</b></td>
    </tr>
    <tr>
      <td>6</td>
      <td><b>return</b> R<sub>0</sub></td>
    </tr>
  </tbody>
</table>

<table><caption>Algorithm 3: A Straightforward</caption>
  <thead>
    <tr>
      <th colspan="2">Variant II</th>
    </tr>
  </thead>
  <tbody>
    <tr>
      <td><b>Input:</b></td>
      <td>x &isin; G, an n-bit integer<br/>&kappa; = (k<sub>n-1</sub>, k<sub>n-2</sub>, ..., k<sub>0</sub>)<sub>2</sub>,<br/>and k<sub>n-1</sub> = 1</td>
    </tr>
    <tr>
      <td><b>Output:</b></td>
      <td>x<sup>&kappa;</sup></td>
    </tr>
    <tr>
      <td>1</td>
      <td>R<sub>0</sub> &leftarrow; 1<sub>G</sub> ; R<sub>1</sub> &leftarrow; 1<sub>G</sub> ;</td>
    </tr>
    <tr>
      <td>2</td>
      <td><b>for</b> i = n &minus; 1 <b>down to</b> 0 <b>do</b></td>
    </tr>
    <tr>
      <td>3</td>
      <td>&nbsp;&nbsp;&nbsp;&nbsp;R<sub>1</sub> &leftarrow; R<sub>0</sub> &middot; R<sub>-k<sub>i</sub></sub> ;</td>
    </tr>
    <tr>
      <td>4</td>
      <td>&nbsp;&nbsp;&nbsp;&nbsp;R<sub>0</sub> &leftarrow; R<sub>1</sub> &middot; x ;</td>
    </tr>
    <tr>
      <td>5</td>
      <td><b>end</b></td>
    </tr>
    <tr>
      <td>6</td>
      <td><b>return</b> R<sub>0</sub></td>
    </tr>
  </tbody>
</table>

Following the reasoning used to define (1), we can instead define $L_j = \sum_{i=j}^{n-1} k_i 2^{i-j}$ and $H_j = L_j - 1$, giving

$$
L_j = 2 L_{j+1} + k_j = L_{j+1} + H_{j+1} + k_j + 1 = 2 H_{j+1} + k_j + 2 \quad (4)
$$
and so, as with (3), we obtain

$$ (L_j, H_j) = \begin{cases} (H_j + 1, L_{j+1} + H_{j+1}) & \text{if } k_j = 0, \\ (H_j + 1, 2L_{j+1}) & \text{if } k_j = 1. \end{cases} \qquad (5) $$

If we consider one register containing $x^{L_j}$ and another containing $x^{H_j}$ then (5) implies that

$$ (x^{L_j}, x^{H_j}) = \begin{cases} (x^{H_j} \cdot x, x^{L_{j+1}} \cdot x^{H_{j+1}}) & \text{if } k_j = 0, \\ (x^{H_j} \cdot x, (x^{L_{j+1}})^2) & \text{if } k_j = 1. \end{cases} $$

From which we can define Algorithm 3. We note that at the end of each iteration we will have the condition where $R_0/R_1 = x$, or equivalently $R_1 \cdot x = R_0$.

Suppose that an adversary can distinguish multiplications from squaring operations, then the two above variants of Montgomery powering ladder are not immune to SPA. In line 3 of both algorithms, a squaring operation will occur for certain bit values. That is, a squaring operation will be computed if the bit value $k_i = 0$ in Algorithm 2 and in Algorithm 3 a squaring operation occurs when $k_i = 1$. The following randomized algorithm will deal with this problem.

We observe that Algorithms 2–3 can be blended together. That is, in loop $\ell$, for some $\ell \in \{1, \dots, n-1\}$, of Algorithm 2 if $k_\ell = 1$ one could compute $R_1 \leftarrow (R_0)^2$ followed by $R_0 \leftarrow R_1 \cdot x$. Before this step $R_1/R_0 = x$, and afterwards one bit of the exponent is treated and $R_0/R_1 = x$. Hence, one could continue to compute an exponentiation using Algorithm 3.

Likewise, in loop $\ell$, for some $\ell \in \{1, \dots, n-1\}$, of Algorithm 3, if $k_\ell = 0$, one could compute $R_0 \leftarrow (R_0)^2$ followed by $R_1 \leftarrow R_0 \cdot x$. Afterwards one bit of the exponent is treated and $R_1/R_0 = x$. Hence, one could continue to compute an exponentiation using Algorithm 2. We define Algorithm 4 as an example of how Algorithms 2 and 3 could be randomly blended together. We use a random generator producing a random bit $b$ to determine when to change from one algorithm to the other, and to determine which algorithm is used to start the exponentiation algorithm. If $b = 0$, the exponentiation is computed by using Algorithm 2, that is $R_1/R_0 = x$. Otherwise, the exponentiation is computed by using Algorithm 3, that is, $R_0/R_1 = x$.

Suppose that an adversary is able to distinguish a multiplication from a squaring operation. Then, she would be able to determine individual bits of the exponent if she could determine if $R_0/R_1 = x$ or $R_1/R_0 = x$. However, the following lemma shows that this information is not available.

**Lemma 1.** An adversary analyzing an instance of Algorithm 4 is able to reduce the hypotheses for the exponent from $\kappa$ to $\kappa^{1/2}$ by distinguishing a multiplication from a squaring operation.

*Proof.* If an adversary observes a squaring operation followed by a multiplication in the loop using index $i$, then the adversary knows one of the following operations has occurred:
<caption>**Algorithm 4: Randomized Montgomery Powering Ladder**</caption>

**Input:** $x \in \mathbb{G}$, an $n$-bit integer $\kappa = (k_{n-1}, k_{n-2}, \dots, k_0)_2$, and $k_{n-1} = 1$
**Output:** $x^\kappa$
1 &nbsp;&nbsp;1 $b \stackrel{R}{\leftarrow} \{0, 1\}$; $R_0 \leftarrow 1_\mathbb{G}$;
2 &nbsp;&nbsp;2 if $b = 0$ then
3 &nbsp;&nbsp;&nbsp;&nbsp;3 $R_1 \leftarrow x$;
4 &nbsp;&nbsp;4 else
5 &nbsp;&nbsp;&nbsp;&nbsp;5 $R_1 \leftarrow 1_\mathbb{G}$;
6 &nbsp;&nbsp;6 end
7 &nbsp;&nbsp;7 for $i = n - 1$ down to 0 do
8 &nbsp;&nbsp;&nbsp;&nbsp;8 if $b \oplus k_i = 1$ then
9 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;9 $b \stackrel{R}{\leftarrow} \{0, 1\}$;
10 &nbsp;&nbsp;10 end
11 &nbsp;&nbsp;11 $R_b \leftarrow R_0 \cdot R_{b \oplus k_i}$;
12 &nbsp;&nbsp;12 $R_{\neg b} \leftarrow R_b \cdot x$;
13 &nbsp;&nbsp;13 end
14 &nbsp;&nbsp;14 return $R_0$

1. Where $R_1/R_0 = x$ and $k_i = 0$.

2. Where $R_0/R_1 = x$ and $k_i = 1$.

3. Where $R_1/R_0 = x$ changes to $R_0/R_1 = x$ and $k_i = 1$.

4. Where $R_0/R_1 = x$ changes to $R_1/R_0 = x$ and $k_i = 0$.

At an arbitrary point, each of these occur with probability $\frac{1}{4}$. Likewise, if an adversary observes two multiplications in the loop using index $i$, hence the adversary knows one of the following operations has occurred:

1. Where $R_1/R_0 = x$ and $k_i = 1$.

2. Where $R_0/R_1 = x$ and $k_i = 0$.

Each of these occur with probability $\frac{1}{2}$. Hence, there is no information available to an adversary since for any observed sequence of operations $\text{Pr}(k_i = 0) = \text{Pr}(k_i = 1) = \frac{1}{2}$.

However, if an adversary observes $y$ consecutive pairs of multiplications then the adversary will know that $y$ consecutive bits have the same value. If an attacker observes a pair of multiplications then the distribution of the number of subsequent pairs $W$ of multiplications is geometric. That is, $W \sim \text{Geometric}(\frac{3}{4})$, since the following bit has to be the same and the randomly generated bit has to be a specific value. The, by definition, the expected length of a run of multiplication is $\frac{4}{3}$ operations, where each observation would therefore provide an expected $\frac{4}{3} - 1 = \frac{1}{3}$ of a bit of the exponent. A pair of multiplications will occur with probability $\frac{1}{4}$, giving an expected $n/4$ bits for an $n$-bit exponent. For an $n$-bit exponent an expected $\frac{1}{3} \times \frac{n}{4} = \frac{n}{12}$ bits can be expected to be derived. Hence, $\kappa$ hypotheses can be expected to be reduced to $\kappa^{\frac{11}{12}}$ hypotheses. $\square$

As with the Montgomery powering ladder shown in Algorithm 1, an attack using collisions based on the reuse of variables is not possible, but a collision
attack based in the use of the output of operations is possible. One can attempt to observe whether the second operand in line 11 of Algorithm 4 is created from line 11 or line 12 in the previous iteration of the exponentiation loop. However, an analysis based on this will return the wrong key hypothesis when the algorithm changes from using (3) to (5).

**Lemma 2.** An adversary analyzing an instance of Algorithm 4 using a collision attack an adversary would be able to reduce the hypotheses for the exponent from $\kappa$ to $\kappa^{3/4}$.

*Proof.* If we, arbitrarily, consider the $\ell$-th loop of the exponentiation loop, we have $\Pr(b \oplus k_i = 1) = \frac{1}{2}$ and the probability that $b$ changes, and hence the algorithm being used, is also $\frac{1}{2}$. An adversary making deductions using a collision attack will have to guess the value of $b$ in two consecutive loops of the algorithm. Given a correct guess for $b$ it will remain the same with probability $\frac{3}{4}$. On the assumption that an attack will validate $b$ in the first loop the value of $b$ in the second loop will remain the same with probability $\frac{3}{4}$. If it changes an incorrect result will be given. Hence, the probability that a collision would detect an incorrect key bit is $\frac{1}{4}$, and an adversary would be able to determine a given bit with a probability $\frac{3}{4}$ leading to a reduction in the number of hypotheses from $\kappa$ to $\kappa^{3/4}$. $\square$

# 4 Random Walk Method

In this section, we generalize the difference between the two registers used in the Montgomery powering ladder to be some arbitrary power of the input. This leads to an algorithm that computes a group exponentiation taking a random, albeit tightly bounded, walk through the possible addition chains.

If one is working in a group where computing the inverses of an element can be readily computed, then other options for a variant of the Montgomery powering ladder are possible. We note that (2) can be rewritten as

$$ (L_j, H_j) = \begin{cases} (H_j - 1, L_{j+1} + H_{j+1}) & \text{if } k_j = 0, \\ (L_{j+1} + H_{j+1}, L_j + 1) & \text{if } k_j = 1. \end{cases} \qquad (6) $$

Implying that

$$ (x^{L_j}, x^{H_j}) = \begin{cases} (x^{H_j} \cdot x^{-1}, x^{L_{j+1}} \cdot x^{H_{j+1}}) & \text{if } k_j = 0, \\ (x^{L_{j+1}} \cdot x^{H_{j+1}}, x^{L_j} \cdot x) & \text{if } k_j = 1. \end{cases} $$

(6) can be rewritten as follows:

$$ (L_j, H_j) = \begin{cases} (L_{j+1} + H_{j+1}, L_j - 1) & \text{if } k_j = 0, \\ (L_{j+1} + H_{j+1}, L_j + 1) & \text{if } k_j = 1. \end{cases} \qquad (7) $$
Implying that

$$ (x^{L_j}, x^{H_j}) = \begin{cases} (x^{L_{j+1}} \cdot x^{H_{j+1}}, x^{L_j} \cdot x^{-1}) & \text{if } k_j = 0, \\ (x^{L_{j+1}} \cdot x^{H_{j+1}}, x^{L_j} \cdot x) & \text{if } k_j = 1. \end{cases} $$

From which we can define Algorithm 5. In previous examples of Montgomery powering ladders presented in this paper $R_0$ has acted as an accumulator and returned the result. In Algorithm 5 the accumulator, i.e. the register containing the correct power of $x$ at the end of each loop, shifts depending on the value of the bit of the exponent being treated. Hence, $R_{-k_0}$ is returned at the end of the algorithm.

<caption>**Algorithm 5: Variant with Inverses**</caption>

Input: $x \in \mathbb{G}$, an $n$-bit integer $\kappa = (k_{n-1}, k_{n-2}, \dots, k_0)_2$
Output: $x^\kappa$
1 $R_0 \leftarrow 1_\mathbb{G}$; $R_1 \leftarrow x$;
2 $U_0 \leftarrow x^{-1}$; $U_1 \leftarrow x$;
3 **for** $i = n-1$ **down to** 0 **do**
4 & $R_0 \leftarrow R_0 \cdot R_1$;
5 & $R_1 \leftarrow R_0 \cdot U_{k_i}$;
6 **end**
7 **return** $R_{-k_0}$

In analyzing an instance of Algorithm 5, an adversary would not be able to determine any information on bits of the exponent based on distinguishing a multiplication from a squaring operation, since no squaring operations take place. However, a collision attack is possible by observing where the multiplication with $U_i$, for $i \in \{0, 1\}$, collides with the multiplications used to generate these values in line 2. If an adversary is able to determine whether $U_{k_i} = x^{-1}$ or $U_{k_i} = x$ was used, for some $i \in \{0, \dots, n-1\}$, then individual bits of the exponent can be determined.

We can modify (7) by choosing $L'_{j+1} = L_{j+1} + \alpha$ and $H'_{j+1} = H_{j+1} + \beta$, giving

$$ (L'_j, H'_j) = \begin{cases} (L'_{j+1} + H'_{j+1}, L'_j - 1) & \text{if } k_j = 0, \\ (L'_{j+1} + H'_{j+1}, L'_j + 1) & \text{if } k_j = 1. \end{cases} \quad (8) $$

where $L'_j = L_j + \gamma$, $H'_j = H_j + \mu$, and $\gamma = \alpha + \beta$. If we choose $\gamma$ as a random element from $\{-h, \dots, h\}$ for some small integer $h$, then $\alpha$ and $\beta$ can be chosen such that $\gamma = \alpha + \beta$. If we assume that $\alpha$ is fixed then $\beta = \gamma - \alpha$, i.e., $H'_{j+1} = H_{j+1} + \gamma - \alpha$. Given that $H'_{j+1}$ is computed from $L'_{j+1}$ this can be done by

$$ H'_{j+1} = \begin{cases} L_{j+1} + (\gamma - \alpha - 1) = L'_{j+1} + (\gamma - 2\alpha - 1) & \text{if } k_j = 0, \\ L_{j+1} + (\gamma - \alpha + 1) = L'_{j+1} + (\gamma - 2\alpha + 1) & \text{if } k_j = 1. \end{cases} $$

This also removes the need to have the accumulating register change as described for Algorithm 5. If we define a value $L'_j = L_j + \gamma_j$ then (8) can be rewritten as
$$ (L_j + \gamma_j, H_j + (\gamma_{j-1} - \gamma_j) = $$

$$ \begin{cases} (L_{j+1} + \gamma_{j+1} + H_{j+1} + (\gamma_j - \gamma_{j+1}), L'_j + (\gamma_{j-1} - 2\gamma_j - 1)) & \text{if } k_j = 0, \\ (L_{j+1} + \gamma_{j+1} + H_{j+1} + (\gamma_j - \gamma_{j+1}), L'_j + (\gamma_{j-1} - 2\gamma_j + 1)) & \text{if } k_j = 1. \end{cases} \quad (9) $$

If we consider one register containing $x^{L'_j}$ and another containing $x^{H'_j}$ then (9) implies that $(x^{L'_j}, x^{H'_j}) = (x^{L'_{j+1}} \cdot x^{H'_{j+1}}, x^{L'_j} \cdot x^{\Delta})$ where

$$ \Delta = \begin{cases} \gamma_{j-1} - 2\gamma_j - 1 & \text{if } k_j = 0, \\ \gamma_{j-1} - 2\gamma_j + 1 & \text{if } k_j = 1. \end{cases} $$

Given that $L_0 = \kappa$ one can build an exponentiation algorithm as shown in Algorithm 6 where we set $\gamma_0 = 0$ to produce the correct result. Assume that $\gamma$ can be arbitrarily chosen from the set $\{-h, \dots, h\}$ in each iteration of computation, then $\Delta \in \{-3h-1, \dots, 3h+1\}$. Hence, our algorithm makes use of an array of $6h+3$ elements that stores the required values of $x^\Delta$.

<caption>**Algorithm 6: Blinded Montgomery Powering Ladder**</caption>

**Input:** $x \in \mathbb{G}$, an $n$-bit integer $\kappa = (k_{n-1}, \dots, k_0)_2$, small integer $h \in \mathbb{Z}$
**Output:** $x^\kappa$
**Uses:** $U$ a $6h+3$ element array.
1 & $U_{3h+1} \leftarrow 1_\mathbb{G}$;
2 & **for** $i=1$ **to** $3h+1$ **do**
3 & & $U_{3h+1+i} \leftarrow U_{3h+i} \cdot x$;
4 & & $U_{3h+1-i} \leftarrow U_{3h+2-i} \cdot x^{-1}$;
5 & **end**
6 & $R_0 \leftarrow 1_\mathbb{G}$; $R_1 \leftarrow 1_\mathbb{G}$; $\alpha = 0$;
7 & **for** $i=n-1$ **down to** $1$ **do**
8 & & $R_0 \leftarrow R_0 \cdot R_1$;
9 & & $\gamma \leftarrow \begin{cases} -h, \dots, h \end{cases}$;
10 & & $\ell \leftarrow \gamma - 2\alpha + k_i - \neg k_i$;
11 & & $R_1 \leftarrow R_0 \cdot U_{3h+1+\ell}$;
12 & & $\alpha \leftarrow \gamma$;
13 & **end**
14 & $R_0 \leftarrow R_0 \cdot R_1$;
15 & $R_0 \leftarrow R_0 \cdot U_{3h+1-\alpha-\neg k_0}$;
16 & **return** $R_0$

An adversary who is able to distinguish a multiplication from a squaring operation would not be able to determine any information on bits of the exponent used since no squaring operations take place. However, a cross correlation attack is possible by observing where the multiplication with $U_d$, for $d \in \{0, \dots, 6h+2\}$,
collides with the multiplications used to generate these values in line 11. From
these values, an adversary can derive the addition chain that was used to compute
the exponentiation. This will not give an adversary the exponent, since there is
no means to map the digits used to bits of the exponent, but would give an
adversary an equivalent addition chain.

In determining whether an attack is practical Hanley et al. [18] determine
that when analyzing an implementation 192-bit exponentiation, the error rate
need to be less than 22 bits. This is determined to be less than 2<sup>54</sup> operations,
based on the boundary set for block ciphers by Biryukov et al. [21]. The expected
number of operations can be determined using Stinson's algorithm [22], where
an *t*-bit error in a *n*-bit hypothesis leads to the exponent in time complexity
$O(n \sum_{i=0}^{[t/2]} \binom{n/2}{i})$ [22]. Then one can apply a version of Stinson's algorithm
where one has to treat all the values that digits can take. Given a small integer
$h$, as defined in Algorithm 6, a *t*-digit error in an $\mu$-bit hypothesis leads to the
exponent in time complexity $O\left(\mu\binom{\mu/2}{t/2}(2h+1)^{\frac{\mu}{2}}\right)$. That is, there are $\mu$ possible
divisions of the digits, each of which will have $\binom{\mu/2}{t/2}$ ways of selecting $t/2$ digits
and each digit can take $(2h+1)$ values. In practice, $t$ will not be known so the
analysis will have time complexity $O\left(\mu \sum_{i=0}^{[t/2]} \binom{\mu/2}{i} (2h+1)^i\right)$ further reducing
the required error rate for a successful attack.

We note that an adversary is required to derive the entire exponent as infor-
mation on part of the exponent is not useful. Moreover, an adversary will not
know the exponent but an equivalent addition-chain. If we consider the group
exponentiation algorithm used in ECDSA (Elliptic Curve Digital Signature Al-
gorithm) [23] this provides a significant increase in security. Howgrave-Graham
and Smart [24] noted that if a few bits of the ephemeral exponent are known
for sufficiently many signatures, then the scheme can be broken, based on the
so-called hidden number problem introduced by Boneh and Venkatesan [25].

A more memory-efficient version of Algorithm 6 is described in Algorithm 7. This is a security-memory trade off where the value of $\gamma_j$ is still chosen at random, but the value range depend on the previous value $\gamma_{j+1}$. Although the available choices for $\gamma_j$ decreases, Algorithm 7 requires only $2h+2$ registers to store pre-computed values instead of $6h+3$ registers in Algorithm 6.

# 5 Generalizing the Montgomery Powering Ladder

The *square-and-multiply* (left-to-right and right-to-left)) exponentiation algo-
rithms are the most efficient implementations for raising *x* to the power *κ* when
the exponent is treated bit-by-bit. Furthermore, these exponentiation algorithms
extend easily to any radix *m* for the purpose of speeding the computation. In
this section, by using the random walk technique, we generalize the (both left-
to-right and right-to-left) exponentiation algorithms and present new blinded
*m*-ary exponentiation algorithms.
<caption>**Algorithm 7: Blinded Montgomery Powering Ladder II**</caption>

**Input:** $x \in \mathbb{G}$, an $n$-bit integer $\kappa = (k_{n-1}, k_{n-2}, \dots, k_0)_2$, small integer $h \in \mathbb{Z}$, $U$ a look-up table of $2h + 2$ precomputed values $x^{-h}, \dots, x^{h+1}$.
**Output:** $x^\kappa$
1 &nbsp;&nbsp;1 $U_h \leftarrow 1_\mathbb{G}$;
2 &nbsp;&nbsp;for $i = 1$ to $h$ do
3 &nbsp;&nbsp;&nbsp;&nbsp;1 $U_{h+i} \leftarrow U_{h+i-1} \cdot x$;
4 &nbsp;&nbsp;&nbsp;&nbsp;2 $U_{h-i} \leftarrow U_{h+1-i} \cdot x^{-1}$;
5 &nbsp;&nbsp;end
6 &nbsp;&nbsp;3 $U_{2h+1} \leftarrow U_{2h} \cdot x$; $R_0 \leftarrow 1_\mathbb{G}$; $R_1 \leftarrow 1_\mathbb{G}$; $\alpha \leftarrow 0$;
7 &nbsp;&nbsp;for $i = n-1$ down to 1 do
8 &nbsp;&nbsp;&nbsp;&nbsp;1 $R_0 \leftarrow R_0 \cdot R_1$;
9 &nbsp;&nbsp;&nbsp;&nbsp;2 if $\alpha \ge 0$ then
10 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;1 $\gamma \leftarrow^R \{2\alpha - h, \dots, h+1-k_i\}$;
11 &nbsp;&nbsp;&nbsp;&nbsp;end
12 &nbsp;&nbsp;&nbsp;&nbsp;else
13 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;1 $\gamma \leftarrow^R \{-h-k_i, \dots, 2\alpha + h - 1\}$;
14 &nbsp;&nbsp;&nbsp;&nbsp;end
15 &nbsp;&nbsp;&nbsp;&nbsp;1 $R_1 \leftarrow R_0 \cdot U_{h+\gamma+k_i}$;
16 &nbsp;&nbsp;&nbsp;&nbsp;2 $\alpha \leftarrow 2\alpha - \gamma$;
17 &nbsp;&nbsp;end
18 &nbsp;&nbsp;1 $R_0 \leftarrow R_0 \cdot R_1$;
19 &nbsp;&nbsp;1 $R_0 \leftarrow R_0 \cdot U_{h+\alpha+k_0}$;
20 &nbsp;return $R_0$

## 5.1 Left-to-right algorithms

We first consider the left-to-right exponentiation. Let $\kappa = (w_{\ell-1}, w_{\ell-2}, \dots, w_0)_2$ be the $m$-ary representation of $\kappa$, where $0 \ne w_i < m$, $w_{\ell-1} \ne 0$, and $\ell$ is the length of $\kappa$ in radix $m$. As in Section 2.2, by defining $L_j = \sum_{i=j}^{\ell-1} w_i m^{i-j}$, we have

$$L_j = m L_{j+1} + w_j \quad (10)$$

From then, the exponentiation algorithm will perform $x^{L_j} = (x^{L_{j+1}})^m \cdot x^{w_j}$. Noting that $x^{L_0} = x^\kappa$. Using the random walk technique as in Section 4, we modify $L'_j = L_j + \gamma_j$ where $\gamma_j$ can be chosen from a pre-defined set $\{-h, \dots, h\}$ for some small integer $h$. Then (10) can be rewritten as

$$L_j + \gamma_j = m L_{j+1} + \gamma_j + w_j = m L'_{j+1} - m \gamma_{j+1} + \gamma_j + w_j \quad (11)$$

This leads to a randomized algorithm (Algorithm 8) that computes a group exponentiation taking a random, albeit tightly bounded, walk through the possible addition chains. As with Algorithm 7, Algorithm 8 also requires a look-up table of $2(m+1)h+m-1$ values to stores precomputed values. Algorithm 8
can be used in the cases where the computation of inversions is cheap, otherwise Algorithm 9 is more suitable.

<caption>**Algorithm 8:** Randomized Left-to-Right *m*-ary Exponentiation</caption>

**Input:** $x \in \mathbb{G}$, an integer
$\kappa = (w_{\ell-1}, w_{\ell-2}, \dots, w_0)_m$,
where $0 \le w_i < m$ and
$w_{\ell-1} \ne 0$, small integer
$h \in \mathbb{Z}$, T a look-up table of
$2(m+1)h + m - 1$
precomputed values
$x^{-(m+1)h-m+1}, \dots, x^{(m+1)h+m-1}$.
**Output:** $x^\kappa$

1 $R \leftarrow 1_{\mathbb{G}}, \alpha \leftarrow 0$

2 **for** $i = \ell - 2$ **to** 1 **do**

3 $R \leftarrow R^m$;

4 $\gamma \leftarrow^R \{-h, \dots, h\}$;

5 $R \leftarrow R \cdot x^{m\alpha - \gamma + w_i}$;

6 $\alpha \leftarrow \gamma$;

7 **end**

8 $R \leftarrow R^m$;

9 $R \leftarrow R \cdot x^{m\alpha + w_0}$;

10 **return** R

<caption>**Algorithm 9:** Randomized Left-to-Right *m*-ary Exponentiation without Inversions</caption>

**Input:** $x \in \mathbb{G}$, an integer
$\kappa = (w_{n-1}, w_{n-2}, \dots, w_0)_m$,
where $w_i$ is *m*-bit words,
small integer $h \in \mathbb{Z}$, T a
look-up table of
$m(h+1) - 1$ precomputed
values $x, \dots, x^{m(h+1)-1}$.
**Output:** $x^\kappa$

1 $R \leftarrow 1_{\mathbb{G}}, \alpha \leftarrow 0$

2 **for** $i = \ell - 2$ **to** 1 **do**

3 $R \leftarrow R^m$;

4 $\gamma \leftarrow^R \{0, \dots, \min(h, m\alpha + w_i)\}$;

5 $R \leftarrow R \cdot x^{m\alpha - \gamma + w_i}$;

6 $\alpha \leftarrow \gamma$;

7 **end**

8 $R \leftarrow R^m$;

9 $R \leftarrow R \cdot x^{m\alpha + w_0}$;

10 **return** R

We note that Algorithm 9 works in a similar way to the Overlapping Windows method [26] for a fixed base $m = 2^{k-h_{OWM}}$ and $m(h + 1) = 2^{k^3}$. The main difference is that our algorithm generates on-the-fly a randomized recoding of the binary representation of the secret exponent $\kappa$. This allows our algorithm to avoid side-channel attacks in the recoding phase.

## 5.2 Right-to-left algorithm

Likewise, we can devise a randomized right-to-left *m*-ary algorithm. Let $\kappa = (w_{\ell-1}, w_{\ell-2}, \dots, w_0)_m$, where $w_{\ell-1} \ne 0$, the principle of the right-to-left *m*-ary exponentiation algorithm, as shown by Yao [27], makes use of the is relied on the following equality:

$$x^{\kappa} = \prod_{0 \le i \le \ell-1} x^{m^i} \cdot \prod_{d_i=2} x^{2 \cdot m^i} \cdots \prod_{0 \le i \le \ell-1} x^{(m-1) \cdot m^i} = \prod_{j=1}^{m-1} \left( \prod_{0 \le i \le \ell-1} x^{m^i} \right)^j .$$

<footnote n="3">³ We use the notation $h_{OWM}$ instead of $h$ as in [26] to distinguish it from the notation $h$ in our algorithms.</footnote>
The right-to-left m-ary exponentiation algorithm uses $(m-1)$ accumulators, $R[1], \dots, R[m-1]$. At each iteration, it applies $w$ successive squarings to compute $A = x^{m^j}$ from $x^{m^{(j-1)}}$, then multiplies the result to some accumulators $R[k]$. Let $R[k]^{(j)}$ (resp. $A^{(j)}$) denote the value of the accumulator $R[k]$ (resp. $A$) before entering step $j$. We have:

$$ 
\begin{aligned}
R[k]^{(j+1)} &= R[k]^{(j)} \cdot A^{(j)} & \text{for } k &= w_j, \\
R[k]^{(j+1)} &= R[k]^{(j)} & \text{for } k &\neq w_j,
\end{aligned}
$$

and $A^{(j+1)} = (A^{(j)})^m$. At the end of the loop each accumulator $R[k]$ contains the product $\prod_{\substack{0 \le j \le \ell-1 \\ w_j = k}} x^{m^j}$. The different accumulators are finally aggregated as $\prod_{0 \le j \le \ell-1} R[k]^k = x^\kappa$. By defining $L_j = \sum_{i=0}^j w_i \cdot m^i$, we have

$$ L_{j+1} = m^{j+1} \cdot w_{j+1} + L_j \quad (12) $$

Noting that $L_{\ell-1} = \kappa$. Similar, we use the random walk technique and modify $L'_j = L_j - m^{j+1} \cdot \gamma_j$, then equation (12) can be rewritten as:

$$ 
\begin{aligned}
L_{j+1} - m^{j+2} \cdot \gamma_{j+1} &= m^{j+1} \cdot w_{j+1} + L_j - m^{j+2} \cdot \gamma_{j+1} \\
&= m \cdot w_{j+1} + L'_j + m^{j+1} \cdot \gamma_j - m^{j+2} \cdot \gamma_{j+1} \\
&= (\gamma_j - m \cdot \gamma_{j+1} + w_{j+1}) m^{j+1} + L'_j
\end{aligned}
$$

This leads to a randomized right-to-left m-ary exponentiation algorithm (Algorithm 10). In this algorithm, we make use of $2(m+1)h+m-1$ accumulators $R[j]$, where $-(m+1)h-m+1 \le j \le (m+1)h+m-1$. Each $R[j]$ is initialized to $1_G$, and then updated if $\alpha - m\gamma + w_i = j$. The different accumulators are finally aggregated as $\prod_{j=1}^h (R[j] \cdot (R[-j]))^{-1})^j = x^\kappa$.

# 6 Conclusion

In this paper we presented variants of the Montgomery powering ladder which have properties that increase the side-channel resistance of the exponentiation algorithm. The first of these operates by randomly changing states such that the difference between the two registers varies, unpredictably, between two states. The second variant of the Montgomery powering ladder that we presented takes a random walk, albeit tightly bounded, among the possible addition chains required to compute an exponentiation. While this variant is not resistant to all side-channel analysis, it will prevent lattice-based attacks when used, for example, in implementations of ECDSA. In other cases, significantly more computation is required to derive any exploitable information and, therefore, an adversary requires a lower error rate to succeed. By applying the random walk method, we also generalized the Montgomery powering ladder and present randomized (both left-to-right and right-to-left) m-ary exponentiation algorithms.
<caption>**Algorithm 10: Randomized Right-to-Left m-ary Exponentiation**</caption>

**Input:** $x \in \mathbb{G}$, an n-bit integer $\kappa = (w_{\ell-1}, w_{\ell-2}, \dots, w_0)_m$, small integer $h \in \mathbb{Z}$.
**Output:** $x^{\kappa}$
1 **for** $j = 0$ **to** $(m+1)h + m - 1$ **do**
2 &nbsp;&nbsp;&nbsp; $R[j] \leftarrow 1_{\mathbb{G}}$; $R[-j] \leftarrow 1_{\mathbb{G}}$;
3 **end**
4 **for** $i = 0$ **to** $\ell - 1$ **do**
5 &nbsp;&nbsp;&nbsp; $A \leftarrow x$; $\alpha \leftarrow 0$;
6 &nbsp;&nbsp;&nbsp; $\gamma \leftarrow^R \{-h, \dots, h\}$;
7 &nbsp;&nbsp;&nbsp; $R[\alpha - m\gamma + k_i] \leftarrow R[\alpha - m\gamma + k_i] \cdot A$;
8 &nbsp;&nbsp;&nbsp; $\alpha \leftarrow \gamma$; $A \leftarrow A^2$;
9 **end**
10 $A \leftarrow \prod_{j=1}^h (R[j] \cdot (R[-j])^{-1})^j$;
11 **return** A

References

1. Kocher, P.: Timing attacks on implementations of Diffie-Hellman, RSA, DSS, and other systems. In Koblitz, N., ed.: CRYPTO '96. Volume 1109 of LNCS., Springer (1996) 104–113

2. Kocher, P., Jaffe, J., Jun, B.: Differential power analysis. In Wiener, M.J., ed.: CRYPTO '99. Volume 1666 of LNCS., Springer (1999) 388–397

3. Quisquater, J.J., Samyde, D.: Electromagnetic analysis (EMA): Measures and counter-measures for smart cards. In Attali, I., Jensen, T.P., eds.: E-smart 2001. Volume 2140 of LNCS., Springer (2001) 200–210

4. Gandolfi, K., Mourtel, C., Olivier, F.: Electromagnetic analysis: Concrete results. In Koç, C.K., Naccache, D., Paar, C., eds.: CHES 2001. Volume 2162 of LNCS., Springer (2001) 251–261

5. Brier, E., Clavier, C., Olivier, F.: Correlation power analysis with a leakage model. In Joye, M., Quisquater, J.J., eds.: CHES 2004. Volume 3156 of LNCS., Springer (2004) 16–29

6. Gierlichs, B., Batina, L., Tuyls, P., Preneel, B.: Mutual information analysis. In Oswald, E., Rohatgi, P., eds.: CHES 2008. Volume 5154 of LNCS., Springer (2008) 426–442

7. Fouque, P.A., Valette, F.: The doubling attack — Why upwards is better than downwards. In Walter, C.D., Koç, Ç.K., Paar, C., eds.: CHES 2003. Volume 2779 of LNCS., Springer (2003) 269–280

8. Chari, S., Rao, J.R., Rohatgi, P.: Template attacks. In Jr., B.S.K., Koç, C.K., Paar, C., eds.: CHES 2002. Volume 2523 of LNCS., Springer (2002) 13–28

9. Coron, J.S.: Resistance against differential power analysis for elliptic curve cryptosystems. In Koç, C.K., Paar, C., eds.: CHES 1999. Volume 1717 of LNCS., Springer (1999) 292–302

10. Walter, C.D.: Sliding windows succumbs to big mac attack. In Ç. K. Koç, Naccache, D., Paar, C., eds.: CHES 2001. Volume 2162 of LNCS., Springer (2001) 286–299
11. Clavier, C., Feix, B., Gagnerot, G., Giraud, C., Roussellet, M., Verneuil, V.: ROSETTA for single trace analysis. In Galbraith, S., Nandi, M., eds.: IN-DOCRYPT 2012. Volume 7668 of LNCS., Springer (2012) 140–155

12. Clavier, C., Feix, B., Gagnerot, G., Roussellet, M., Verneuil, V.: Horizontal correlation analysis on exponentiation. In: Proceedings of the 12th international conference on Information and communications security. ICICS’10, Berlin, Heidelberg, Springer-Verlag (2010) 46–61

13. Bauer, A., Jaulmes, E., Prouff, E., Wild, J.: Horizontal collision correlation attack on elliptic curves. In Lange, T., Lauter, K., Lisonek, P., eds.: SAC 2013. Volume 8282 of LNCS., Springer (2013) 553–570

14. Witteman, M.F., van Woudenberg, J.G.J., Menarini, F.: Defeating RSA multiply-always and message blinding countermeasures. In Kiayias, A., ed.: CT-RSA 2011. Volume 6558 of LNCS., Springer (2011) 77–88

15. Kim, H., Kim, T.H., Yoon, J.C., Hong, S.: Practical second-order correlation power analysis on the message blinding method and its novel countermeasure for RSA. ETRI Journal 32(1) (2010) 102–111

16. Montgomery, P.: Speeding the Pollard and elliptic curve methods of factorization. Mathematics of Computation 48(177) (1987) 243–264

17. Joye, M., Yen, S.M.: The Montgomery powering ladder. In Jr., B.S.K., Ç. K. Koç, Paar, C., eds.: CHES 2002. Volume 2523 of LNCS., Springer (2003) 291–302

18. Hanley, N., Kim, H., Tunstall, M.: Exploiting collisions in addition chain-based exponentiation algorithms using a single trace. In Nyberg, K., ed.: CT-RSA 2015. Volume 9048 of LNCS., Springer (2015) 431–448

19. Win, E.D., Mister, S., Preneel, B., Wiener, M.: On the performance of signature schemes based on elliptic curves. In Buhler, J.P., ed.: ANTS 1998. Volume 1423 of LNCS., Springer (1998) 252–266

20. Mangard, S., Oswald, E., Popp, T.: Power Analysis Attacks — Revealing the Secrets of Smart Cards. Springer (2007)

21. Biryukov, A., Dunkelman, O., Keller, N., Khovratovich, D., Shamir, A.: Key recovery attacks of practical complexity on AES-256 variants with up to 10 rounds. In Gilbert, H., ed.: EUROCRYPT 2010. Volume 6110 of LNCS., Springer (2010) 299–319

22. Stinson, D.: Some baby-step giant-step algorithms for the low Hamming weight discrete logarithm problem. Mathematics of Computation 71(237) (2002) 379–391

23. X9.62, A.: Public key cryptography for the financial services industry, the elliptic curve digital signature algorithm (ECDSA) (1999)

24. Howgrave-Graham, N.A., Smart, N.P.: Lattice attacks on digital signature schemes. Design, Codes and Cryptography 23 (2001) 283–290

25. Boneh, D., Venkatesa, R.: Hardness of computing the most significant bits of secret keys in Diffie-Hellman and related schemes. In Koblitz, N., ed.: CRYPTO '96. Volume 1109 of LNCS., Springer (1996) 129–142

26. Itoh, K., Yajima, J., Takenaka, M., Torii, N.: Dpa countermeasures by improving the window method. In: Revised Papers from the 4th International Workshop on Cryptographic Hardware and Embedded Systems. CHES '02, London, UK, UK, Springer-Verlag (2003) 303–317

27. Yao, A.C.C.: On the evaluation of powers. SIAM J. Comput. 5(1) (1976) 100–103