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

HAL
open science

# Interleaved Ladders: One more Step on Generalizing the Montgomery Ladder

Yoann Marquer, Tania Richmond, Pascal Véron

► To cite this version:

Yoann Marquer, Tania Richmond, Pascal Véron. Interleaved Ladders: One more Step on Generalizing the Montgomery Ladder. 2024. hal-03157804v2

HAL Id: hal-03157804

https://hal.science/hal-03157804v2

Preprint submitted on 11 Mar 2024

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_2.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Interleaved Ladders: One more Step on Generalizing the Montgomery Ladder

Yoann Marquer, Tania Richmond, Pascal Véron

► To cite this version:

Yoann Marquer, Tania Richmond, Pascal Véron. Interleaved Ladders: One more Step on Generalizing the Montgomery Ladder. 2024. hal-03157804v2

HAL Id: hal-03157804

https://hal.science/hal-03157804v2

Preprint submitted on 11 Mar 2024

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
# Interleaved Ladders: One more Step on Generalizing the Montgomery Ladder

Yoann Marquer¹,⁴, Tania Richmond²,⁴, and Pascal Véron³

¹SnT, SVV, University of Luxembourg, Luxembourg, yoann.marquer@uni.lu

²Institut de Sciences Exactes et Appliquées, Université de la Nouvelle-Calédonie, France, tania.richmond@unc.nc

³Laboratoire IMath, Université de Toulon, France, pascal.veron@univ-tln.fr

⁴Most of this work was done while Y. Marquer and T. Richmond were affiliated with Inria, Univ. Rennes, CNRS, IRISA, France

## Abstract

Iterative conditional branchings appear in various sensitive algorithms, like the modular exponentiation in the RSA cryptosystem or the scalar multiplication in elliptic-curve cryptography. The Montgomery ladder is a common example of such algorithm with desirable security properties against some side-channel and fault-injection attacks. In this paper, we abstract away and generalize these security properties by formalizing, using systems of equations, what we call semi-interleaved and fully-interleaved ladders. This fruitful approach allows us to design novel fault-injection attacks, able to obtain some/all bits of the secret against different ladders, breaking the common Montgomery ladder. We also demonstrate the generality of our approach by applying our ladder equations to the modular exponentiation and the scalar multiplication, both in the semi- and fully-interleaved cases, to propose novel and more secure algorithms.

# 1 Introduction

## 1.1 Context

An *iterative conditional branching* is a loop containing a conditional branching. Such iterative conditional branching is said *sensitive* if the condition of the conditional branching depends on a sensitive value, like the value of the secret key in a cryptosys-

tem. Sensitive iterative conditional branchings are frequent (Subsection 3.1) and, unfortunately, usually prone to vulnerability to side-channel (Subsection 2.1) or fault-injection (Subsection 2.2) attacks.

The square-and-multiply (Algorithm 1 p.4) and the Montgomery ladder (Algorithm 3 p.6) are common examples of sensitive iterative conditional branchings. As opposed to the square-and-multiply algorithm, the Montgomery ladder demonstrates desirable security properties against side-channel and fault-injection attacks (Subsection 2.3). We call *ladderization* the refactoring process transforming, for instance, the vulnerable square-and-multiply algorithm into the more protected Montgomery ladder.

## 1.2 Contribution

The purpose of this paper is to solve the computational problem of ladderizing sensitive iterative conditional branchings in order to reduce their security vulnerabilities. This is done by abstracting away the desirable security properties from the Montgomery ladder and by generalizing ladderization to a more general class: the ladderizable algorithms obtained in Theorem 1 p.10.

To our knowledge, this ladderization approach is the first systematic attempt to generalize these security properties, by using systems of equations called the *ladder equations*. While investigating this novel problem, we distinguish between semi-
# Interleaved Ladders: One more Step on Generalizing the Montgomery Ladder

Yoann Marquer¹,⁴, Tania Richmond²,⁴, and Pascal Véron³

¹SnT, SVV, University of Luxembourg, Luxembourg, yoann.marquer@uni.lu

²Institut de Sciences Exactes et Appliquées, Université de la Nouvelle-Calédonie, France, tania.richmond@unc.nc

³Laboratoire IMath, Université de Toulon, France, pascal.veron@univ-tln.fr

⁴Most of this work was done while Y. Marquer and T. Richmond were affiliated with Inria, Univ. Rennes, CNRS, IRISA, France

## Abstract

Iterative conditional branchings appear in various sensitive algorithms, like the modular exponentiation in the RSA cryptosystem or the scalar multiplication in elliptic-curve cryptography. The Montgomery ladder is a common example of such algorithm with desirable security properties against some side-channel and fault-injection attacks. In this paper, we abstract away and generalize these security properties by formalizing, using systems of equations, what we call semi-interleaved and fully-interleaved ladders. This fruitful approach allows us to design novel fault-injection attacks, able to obtain some/all bits of the secret against different ladders, breaking the common Montgomery ladder. We also demonstrate the generality of our approach by applying our ladder equations to the modular exponentiation and the scalar multiplication, both in the semi- and fully-interleaved cases, to propose novel and more secure algorithms.

# 1 Introduction

## 1.1 Context

An *iterative conditional branching* is a loop containing a conditional branching. Such iterative conditional branching is said *sensitive* if the condition of the conditional branching depends on a sensitive value, like the value of the secret key in a cryptosys-

tem. Sensitive iterative conditional branchings are frequent (Subsection 3.1) and, unfortunately, usually prone to vulnerability to side-channel (Subsection 2.1) or fault-injection (Subsection 2.2) attacks.

The square-and-multiply (Algorithm 1 p.4) and the Montgomery ladder (Algorithm 3 p.6) are common examples of sensitive iterative conditional branchings. As opposed to the square-and-multiply algorithm, the Montgomery ladder demonstrates desirable security properties against side-channel and fault-injection attacks (Subsection 2.3). We call *ladderization* the refactoring process transforming, for instance, the vulnerable square-and-multiply algorithm into the more protected Montgomery ladder.

## 1.2 Contribution

The purpose of this paper is to solve the computational problem of ladderizing sensitive iterative conditional branchings in order to reduce their security vulnerabilities. This is done by abstracting away the desirable security properties from the Montgomery ladder and by generalizing ladderization to a more general class: the ladderizable algorithms obtained in Theorem 1 p.10.

To our knowledge, this ladderization approach is the first systematic attempt to generalize these security properties, by using systems of equations called the *ladder equations*. While investigating this novel problem, we distinguish between semi-
interleaved ladders (Subsection 3.2), including the
usual Montgomery ladder, and fully-interleaved
ladders (Subsection 3.3) with a more complex pat-
tern.

Based on the code symmetry of the semi- and
fully-interleaved ladders, the same operations are
performed regardless the sensitive value, so these
algorithms are secure against simple side-channel
attacks depending on these operations, like tim-
ing side-channel attacks [32] or SPA (Simple Power
Analysis) [31].

Based on fault-propagation patterns that prevent an attacker to compare outputs with or without fault injection (Section 4), we demonstrate in Table 1 p.14 that fully-interleaved ladders are more secure against fault-injection attacks than semi-interleaved ladders, which are more secure than algorithms without interleaving. This fruitful investigation leads to the discovery of novel fault-injection attacks applicable to the common Montgomery ladder (Section 4). Moreover, a violation of the ladder invariant $y = l(x)$ between intermediate variables $x$ and $y$ allows the protected system to detect a fault-injection, and thus to trigger countermeasures (Subsection 2.3).

Solving the ladder equations was feasible by
a solver for the semi-interleaved ladders with
if-then branchings (i.e., without else branch).
Thus, the ladderization refactoring was semi-
automatized in this simple case [11]. But, because
of the complexity of the ladder equations in the gen-
eral case, we focus in this paper on manually solving
the ladder equations for common cryptosystems.

We validate our approach and demonstrate its
generality by obtaining novel and more secure al-
gorithms for the modular exponentiation in the
RSA [45] and DSA [40] cryptosystems (Section 5),
and for the scalar multiplication in elliptic-curve
cryptography [5, 40] (Section 6). In most of the
cases, solving the ladder equations leads to a de-
gree of freedom, that we exploit by blinding inter-
mediate computations using a randomly generated
integer, in order to prevent advanced side-channel
attacks like CPA (Correlation Power Analysis) [10].
We also discuss the feasibility of our solutions. Ta-
bles 2 and 4 summarize their cost compared to the
Montgomery ladder, demonstrating a trade-off be-
tween security and performance.

The ladder equations, the first two fault-injection
attacks and the solutions for the modular exponen-

tiation have already been published [37], but they
are included here so that the paper is entirely self-
contained. This paper extends and complete these
results with the following contributions:

* a third fault-injection attack (for the second attacker model) against all (including fully-interleaved) ladders (Subsection 4.2),

* in the case of the modular exponentiation, a) more performant algorithms for the solutions than initially published [37] and b) a proof that the fully-interleaved ladder solution is applicable, more precisely that the probability to randomly obtain a suitable ladder constant (which was an open problem in [37]) is almost 1 when used in concrete applications like RSA or DSA cryptosystems (Subsections 5.5 and 5.6),

* and novel semi- and fully-interleaved ladder al-
  gorithms for the scalar multiplication over el-
  liptic curves (Section 6).

1.3 Organization of the Paper

We introduce in Section 2 related works on side-
channel and fault-injection attacks, then we use the
case of the modular exponentiation to introduce
security concerns and we present the Montgomery
ladder both the in this case and in the case of scalar
multiplication in elliptic-curve cryptography. We
conclude this section by introducing related works
on parallel computation, in particular in the con-
text of elliptic-curve cryptography. In Section 3, we
formalize the iterative conditional branchings to de-
duce the equations satisfied by the semi-interleaved
and fully-interleaved ladders, and thus the require-
ments for ladderizable algorithms. We state our re-
search questions in Subsection 3.5. In Section 4, we
introduce two attacker models using fault-injection
techniques, and we compare the vulnerability of the
non-, semi- and fully-interleaved ladders to these
attacks. We then detail how to produce examples of
the semi- and fully-interleaved ladders in Section 5
for the modular exponentiation and in Section 6 for
the scalar multiplication. Subsections 5.7 and 6.6
answer the research questions, then Section 7 con-
cludes.
*interleaved ladders* (Subsection 3.2), including the usual Montgomery ladder, and *fully-interleaved ladders* (Subsection 3.3) with a more complex pattern.

Based on the code symmetry of the semi- and fully-interleaved ladders, the same operations are performed regardless the sensitive value, so these algorithms are secure against simple side-channel attacks depending on these operations, like timing side-channel attacks [32] or SPA (Simple Power Analysis) [31].

Based on fault-propagation patterns that prevent an attacker to compare outputs with or without fault injection (Section 4), we demonstrate in Table 1 p.14 that fully-interleaved ladders are more secure against fault-injection attacks than semi-interleaved ladders, which are more secure than algorithms without interleaving. This fruitful investigation leads to the discovery of novel fault-injection attacks applicable to the common Montgomery ladder (Section 4). Moreover, a violation of the ladder invariant $y = l(x)$ between intermediate variables $x$ and $y$ allows the protected system to detect a fault-injection, and thus to trigger countermeasures (Subsection 2.3).

Solving the ladder equations was feasible by a solver for the semi-interleaved ladders with *if-then* branchings (i.e., without *else* branch). Thus, the ladderization refactoring was semi-automatized in this simple case [11]. But, because of the complexity of the ladder equations in the general case, we focus in this paper on manually solving the ladder equations for common cryptosystems.

We validate our approach and demonstrate its generality by obtaining novel and more secure algorithms for the modular exponentiation in the RSA [45] and DSA [40] cryptosystems (Section 5), and for the scalar multiplication in elliptic-curve cryptography [5, 40] (Section 6). In most of the cases, solving the ladder equations leads to a degree of freedom, that we exploit by blinding intermediate computations using a randomly generated integer, in order to prevent advanced side-channel attacks like CPA (Correlation Power Analysis) [10]. We also discuss the feasibility of our solutions. Tables 2 and 4 summarize their cost compared to the Montgomery ladder, demonstrating a trade-off between security and performance.

The ladder equations, the first two fault-injection attacks and the solutions for the modular exponentiation have already been published [37], but they are included here so that the paper is entirely self-contained. This paper extends and completes these results with the following contributions:

* a third fault-injection attack (for the second attacker model) against all (including fully-interleaved) ladders (Subsection 4.2),

* in the case of the modular exponentiation, a) more performant algorithms for the solutions than initially published [37] and b) a proof that the fully-interleaved ladder solution is applicable, more precisely that the probability to randomly obtain a suitable ladder constant (which was an open problem in [37]) is almost 1 when used in concrete applications like RSA or DSA cryptosystems (Subsections 5.5 and 5.6),

* and novel semi- and fully-interleaved ladder algorithms for the scalar multiplication over elliptic curves (Section 6).

## 1.3 Organization of the Paper

We introduce in Section 2 related works on side-channel and fault-injection attacks, then we use the case of the modular exponentiation to introduce security concerns and we present the Montgomery ladder both the in this case and in the case of scalar multiplication in elliptic-curve cryptography. We conclude this section by introducing related works on parallel computation, in particular in the context of elliptic-curve cryptography. In Section 3, we formalize the iterative conditional branchings to deduce the equations satisfied by the semi-interleaved and fully-interleaved ladders, and thus the requirements for ladderizable algorithms. We state our research questions in Subsection 3.5. In Section 4, we introduce two attacker models using fault-injection techniques, and we compare the vulnerability of the non-, semi- and fully-interleaved ladders to these attacks. We then detail how to produce examples of the semi- and fully-interleaved ladders in Section 5 for the modular exponentiation and in Section 6 for the scalar multiplication. Subsections 5.7 and 6.6 answer the research questions, then Section 7 concludes.
# 2 Related Works

In this section, we first introduce context on side-channel (Subsection 2.1) and fault-injection attacks (Subsection 2.2). Then, we explain step-by-step in Subsection 2.3 the rationale behind known algorithms for the modular exponentiation, and their respective relevance regarding desirable security properties. In particular, we introduce in this subsection the Montgomery ladder for modular exponentiation, then its variant in Subsection 2.4 for scalar multiplication. Finally, we briefly describe in Subsection 2.5 works aiming at improving performance using parallel computations, to better compare our solutions with the Montgomery ladder.

## 2.1 Side-Channel Attacks

A *side-channel* is a way of transmitting information (purposely or not) to another system out of the intended communication channels. Side-channel attacks rely on the relationship between information leaked through a side-channel and the secret data to obtain confidential information. In particular, they can be used to break cryptographic protocols by exploiting information that is observed during execution of the implementation of an algorithm.

The ability to extract information on the secret key of a cryptosystem through side-channel observations has been achieved in practice using:

* *Timing side-channel attacks* [32] rely on the correlation between execution time and the sensitive information. For instance, we illustrate in Subsection 2.3 how timing attacks can be used to obtain the number of 1s in the binary representation of a secret key.

* *Simple Power Analysis (SPA)* [31] consists in observing the power profile of a chip during execution to retrieve sensitive information. For instance, in Figure 1 it is possible to read directly on the screen of an oscilloscope the first bits of the secret key.

* More advanced techniques can be applied to a power side-channel, like *Correlation Power Analysis* (CPA) [10] based on the linear correlation between the number of bits flipping at an iteration and the evolution of the power consumption.

Countermeasures against simple side-channel attacks like timing attacks or SPA involve *code symmetry*: if the same operations are computed in any case then the attacker cannot leverage execution time or a single power trace to gain sensitive information.

But code symmetry is not sufficient against more advanced attacks like CPA. Against such attacks, a more advanced countermeasure like *blinding* is required. The idea is to hide the correlation between intermediate values and the sensitive information by using a random value during intermediate computations.

For instance, in the context of the RSA [45] cryptosystem, let $k$ be the private key and $e$ be the public key such that, for every integer $x$, $x^{ke} = x \bmod n$. A message $m$ is encrypted using the public key $e$ into a ciphertext $c = m^e \bmod n$ and publicly sent to the chip. Then, without countermeasure, the chip uses the private key $k$ to decrypt the ciphertext into the original message $c^k = m^{ke} = m \bmod n$. But in the case of a blinding countermeasure the chip picks a random integer $r$ invertible modulo $n$ and decrypt $cr^e$ instead of $c$. Indeed, $(cr^e)^k = (mr)^{ke} = mr \bmod n$. Then, because $r$ is invertible, from $mr$ the message $m$ can be computed by the chip. So, during the computation of $(cr^e)^k$, the intermediate values depend on the random integer $r$, and the attacker is not able to distinguish bit flips due to the message or due to the random variable. In this article, we call such a random integer used in blinding techniques a *blinding integer*.

## 2.2 Fault Injection Attacks

A *fault* is a physical defect, imperfection or flaw that occurs within some hardware or software component, while an *error* is a deviation from accuracy or correctness, and is the manifestation of a fault [50]. Hardware (also called physical) faults can be permanent, transient or intermittent, while software faults are the consequence of incorrect design, at specification or at coding time. *Fault injection* is defined as the validation technique of the dependability of fault tolerant systems, which consists in performing controlled experiments where the observation of the system's behavior in presence of faults is induced explicitly by the writing introduction (called injection) of faults in the sys-
# 2 Related Works

In this section, we first introduce context on side-channel (Subsection 2.1) and fault-injection attacks (Subsection 2.2). Then, we explain step-by-step in Subsection 2.3 the rationale behind known algorithms for the modular exponentiation, and their respective relevance regarding desirable security properties. In particular, we introduce in this subsection the Montgomery ladder for modular exponentiation, then its variant in Subsection 2.4 for scalar multiplication. Finally, we briefly describe in Subsection 2.5 works aiming at improving performance using parallel computations, to better compare our solutions with the Montgomery ladder.

## 2.1 Side-Channel Attacks

A *side-channel* is a way of transmitting information (purposely or not) to another system out of the intended communication channels. Side-channel attacks rely on the relationship between information leaked through a side-channel and the secret data to obtain confidential information. In particular, they can be used to break cryptographic protocols by exploiting information that is observed during execution of the implementation of an algorithm.

The ability to extract information on the secret key of a cryptosystem through side-channel observations has been achieved in practice using:

* *Timing side-channel attacks* [32] rely on the correlation between execution time and the sensitive information. For instance, we illustrate in Subsection 2.3 how timing attacks can be used to obtain the number of 1s in the binary representation of a secret key.

* *Simple Power Analysis (SPA)* [31] consists in observing the power profile of a chip during execution to retrieve sensitive information. For instance, in Figure 1 it is possible to read directly on the screen of an oscilloscope the first bits of the secret key.

* More advanced techniques can be applied to a power side-channel, like *Correlation Power Analysis* (CPA) [10] based on the linear correlation between the number of bits flipping at an iteration and the evolution of the power consumption.

Countermeasures against simple side-channel attacks like timing attacks or SPA involve *code symmetry*: if the same operations are computed in any case then the attacker cannot leverage execution time or a single power trace to gain sensitive information.

But code symmetry is not sufficient against more advanced attacks like CPA. Against such attacks, a more advanced countermeasure like *blinding* is required. The idea is to hide the correlation between intermediate values and the sensitive information by using a random value during intermediate computations.

For instance, in the context of the RSA [45] cryptosystem, let $k$ be the private key and $e$ be the public key such that, for every integer $x$, $x^{ke} = x \bmod n$. A message $m$ is encrypted using the public key $e$ into a ciphertext $c = m^e \bmod n$ and publicly sent to the chip. Then, without countermeasure, the chip uses the private key $k$ to decrypt the ciphertext into the original message $c^k = m^{ke} = m \bmod n$. But in the case of a blinding countermeasure the chip picks a random integer $r$ invertible modulo $n$ and decrypt $cr^e$ instead of $c$. Indeed, $(cr^e)^k = (mr)^{ke} = mr \bmod n$. Then, because $r$ is invertible, from $mr$ the message $m$ can be computed by the chip. So, during the computation of $(cr^e)^k$, the intermediate values depend on the random integer $r$, and the attacker is not able to distinguish bit flips due to the message or due to the random variable. In this article, we call such a random integer used in blinding techniques a *blinding integer*.

## 2.2 Fault Injection Attacks

A *fault* is a physical defect, imperfection or flaw that occurs within some hardware or software component, while an *error* is a deviation from accuracy or correctness, and is the manifestation of a fault [50]. Hardware (also called physical) faults can be permanent, transient or intermittent, while software faults are the consequence of incorrect design, at specification or at coding time. *Fault injection* is defined as the validation technique of the dependability of fault tolerant systems, which consists in performing controlled experiments where the observation of the system's behavior in presence of faults is induced explicitly by the writing introduction (called injection) of faults in the sys-
tem [2]. Fault injection techniques can be grouped into *invasive* and *non-invasive* techniques, the latter being able to hide their presence so as to have no effect on the system other than the faults they inject [50].

We illustrate in Subsection 2.3 a non-invasive technique called *safe-error attack* [24], which consists in 1) running the source code with a given input to get the corresponding output, then 2) run it again with the same input but while introducing a transient fault when the execution reaches a particular location to get another output, and finally 3) compare both outputs to see if the fault injection altered the execution, and thus retrieve some information about the execution.

In this paper, we do not assume a specific mean (hardware, software, simulation, emulation, etc.) for fault injection and we consider only two types of fault injections: *random fault* (the affected variable is set to a random value) and *zeroing/one-ing fault* (all bits are set to 0 or 1). We detail attacker models and fault-propagation patterns in Section 4.

## 2.3 Modular Exponentiation

Modular exponentiation algorithms compute $a^k \text{ mod } n$, where $k$ is a secret key and $a, n$ are public values. They are commonly used in cryptosystems like RSA [45], and we use them as running example. We denote by $k = \sum_{0 \le i \le d} k[i] 2^i$ the binary expansion of size $d+1$ of the secret key, where $k[i]$ is the bit $i$ of $k$.

The *square-and-multiply* Algorithm 1 computes the left-to-right modular exponentiation using $a^{\sum_{0 \le i \le d} k[i] 2^i} = \prod_{0 \le i \le d} (a^{2^i})^{k[i]}$. For every iteration, the squaring $x^2$ is computed at Line 3 in every case while the multiplication $ax$ is computed at Line 5 only if the current secret bit is $k[i] = 1$. This dependency on the secret key can be detected by observing side-channels.

Observing the execution time [32] leaks the number of multiplications performed during the execution, hence the Hamming weight (i.e., the number of non-zero bits) of the secret key. This narrows down the search space, compared to brute-force attacks.

Observing the power profile during the execution leaks even more information than observing execution time, as demonstrated in Simple Power

<caption>**Algorithm 1 Square and Multiply**</caption>

**input** public $a, n$; secret $k$
1: $x \leftarrow 1$
2: **for** $i = d$ **to** 0 **do**
3: &nbsp;&nbsp;&nbsp;&nbsp; $x \leftarrow x^2 \text{ mod } n$
4: &nbsp;&nbsp;&nbsp;&nbsp; **if** $k[i] = 1$ **then**
5: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; $x \leftarrow ax \text{ mod } n$
6: &nbsp;&nbsp;&nbsp;&nbsp; **end if**
7: **end for**
8: **return** $x$
**output** $x = a^k \text{ mod } n$

<caption>**Algorithm 2 Square and Multiply Always**</caption>

**input** public $a, n$; secret $k$
1: $x \leftarrow 1$
2: **for** $i = d$ **to** 0 **do**
3: &nbsp;&nbsp;&nbsp;&nbsp; $x \leftarrow x^2 \text{ mod } n$
4: &nbsp;&nbsp;&nbsp;&nbsp; **if** $k[i] = 1$ **then**
5: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; $x \leftarrow ax \text{ mod } n$
6: &nbsp;&nbsp;&nbsp;&nbsp; **else**
7: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; $y \leftarrow ax \text{ mod } n$
8: &nbsp;&nbsp;&nbsp;&nbsp; **end if**
9: **end for**
10: **return** $x$
**output** $x = a^k \text{ mod } n$

Analysis (SPA) [31]. We illustrate in Figure 1 a profile obtained in the screen of an oscilloscope. The x-axis corresponds to timestamps, while the y-axis corresponds to positions in the screen of the oscilloscope, linearly correlated with the differential voltage from a baseline, measured on the chip during execution. An iteration requires only one operation if the secret bit is $k[i] = 0$ and two operations<fnref n="1" /> if the secret bit is $k[i] = 1$. Hence, based on the length of each period of power consumption, an attacker can read the first bits of the secret key on the screen of the oscilloscope<fnref n="2" />.

To prevent SPA, regularity of the modular exponentiation algorithms is required, which means that both branches of the sensitive conditional branch

<footnote n="1">¹Actually, a multiplication can be distinguished from a squaring, so variants with squaring only have been proposed in [12] and improved in [20], but this is out of the scope of this paper.</footnote>

<footnote n="2">²To improve readability of the plot, we padded the end of iterations so that each one has the same execution time, making easier to distinguish long from short periods of power consumption.</footnote>
tem [2]. Fault injection techniques can be grouped into *invasive* and *non-invasive* techniques, the latter being able to hide their presence so as to have no effect on the system other than the faults they inject [50].

We illustrate in Subsection 2.3 a non-invasive technique called *safe-error attack* [24], which consists in 1) running the source code with a given input to get the corresponding output, then 2) run it again with the same input but while introducing a transient fault when the execution reaches a particular location to get another output, and finally 3) compare both outputs to see if the fault injection altered the execution, and thus retrieve some information about the execution.

In this paper, we do not assume a specific mean (hardware, software, simulation, emulation, etc.) for fault injection and we consider only two types of fault injections: *random fault* (the affected variable is set to a random value) and *zeroing/one-ing fault* (all bits are set to 0 or 1). We detail attacker models and fault-propagation patterns in Section 4.

## 2.3 Modular Exponentiation

Modular exponentiation algorithms compute $a^k \text{ mod } n$, where $k$ is a secret key and $a, n$ are public values. They are commonly used in cryptosystems like RSA [45], and we use them as running example. We denote by $k = \sum_{0 \le i \le d} k[i] 2^i$ the binary expansion of size $d+1$ of the secret key, where $k[i]$ is the bit $i$ of $k$.

The *square-and-multiply* Algorithm 1 computes the left-to-right modular exponentiation using $a^{\sum_{0 \le i \le d} k[i] 2^i} = \prod_{0 \le i \le d} (a^{2^i})^{k[i]}$. For every iteration, the squaring $x^2$ is computed at Line 3 in every case while the multiplication $ax$ is computed at Line 5 only if the current secret bit is $k[i] = 1$. This dependency on the secret key can be detected by observing side-channels.

Observing the execution time [32] leaks the number of multiplications performed during the execution, hence the Hamming weight (i.e., the number of non-zero bits) of the secret key. This narrows down the search space, compared to brute-force attacks.

Observing the power profile during the execution leaks even more information than observing execution time, as demonstrated in Simple Power

<caption>**Algorithm 1 Square and Multiply**</caption>

**input** public $a, n$; secret $k$
1: $x \leftarrow 1$
2: **for** $i = d$ **to** 0 **do**
3: &nbsp;&nbsp;&nbsp;&nbsp; $x \leftarrow x^2 \text{ mod } n$
4: &nbsp;&nbsp;&nbsp;&nbsp; **if** $k[i] = 1$ **then**
5: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; $x \leftarrow ax \text{ mod } n$
6: &nbsp;&nbsp;&nbsp;&nbsp; **end if**
7: **end for**
8: **return** $x$
**output** $x = a^k \text{ mod } n$

<caption>**Algorithm 2 Square and Multiply Always**</caption>

**input** public $a, n$; secret $k$
1: $x \leftarrow 1$
2: **for** $i = d$ **to** 0 **do**
3: &nbsp;&nbsp;&nbsp;&nbsp; $x \leftarrow x^2 \text{ mod } n$
4: &nbsp;&nbsp;&nbsp;&nbsp; **if** $k[i] = 1$ **then**
5: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; $x \leftarrow ax \text{ mod } n$
6: &nbsp;&nbsp;&nbsp;&nbsp; **else**
7: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; $y \leftarrow ax \text{ mod } n$
8: &nbsp;&nbsp;&nbsp;&nbsp; **end if**
9: **end for**
10: **return** $x$
**output** $x = a^k \text{ mod } n$

Analysis (SPA) [31]. We illustrate in Figure 1 a profile obtained in the screen of an oscilloscope. The x-axis corresponds to timestamps, while the y-axis corresponds to positions in the screen of the oscilloscope, linearly correlated with the differential voltage from a baseline, measured on the chip during execution. An iteration requires only one operation if the secret bit is $k[i] = 0$ and two operations<fnref n="1" /> if the secret bit is $k[i] = 1$. Hence, based on the length of each period of power consumption, an attacker can read the first bits of the secret key on the screen of the oscilloscope<fnref n="2" />.

To prevent SPA, regularity of the modular exponentiation algorithms is required, which means that both branches of the sensitive conditional branch

<footnote n="1">¹Actually, a multiplication can be distinguished from a squaring, so variants with squaring only have been proposed in [12] and improved in [20], but this is out of the scope of this paper.</footnote>

<footnote n="2">²To improve readability of the plot, we padded the end of iterations so that each one has the same execution time, making easier to distinguish long from short periods of power consumption.</footnote>
<figure><img src="image_3.png" /><figcaption>Figure 1: Power profile for the first 32 iterations of Algorithm 1. Based on the length of periods of power consumption (long for 1 and short for 0), an attacker can read the 32 first bits 10010110010000000001100000011101 of the secret key on the screen of the oscilloscope.</figcaption></figure>

ching perform the same operations, independently from the value of the secret key. Thus, an obvious solution is to add an `else` branch containing a dummy instruction [14] at Line 7 of the *square-and-multiply-always* Algorithm 2.

But power profiles also depend on values in the considered registers, so computing a multiplication in every case is better against SPA but not against more advanced side-channel attacks like CPA [10]. Fortunately, standard blinding techniques can prevent differential [14, 38] or correlation power analysis [10]. We use such a blinding technique in Subsection 5.2 and Subsection 6.2 to improve security in most solutions.

Moreover, countermeasures developed against a given attack may benefit another one [48]. The multiplication in the `else` branch of the square-and-multiply-always algorithm is a dummy operation in the sense that if the current secret bit is $k[i] = 0$ then the result is not used by the rest of the computation. Thus, a random fault injected [50] in the register containing $ax$ will propagate through

successive iterations and alter the final result only if the current secret bit is $k[i] = 1$. So, an attacker (see the attacker models in Section 4) able to inject a fault in a register at a given iteration can apply such a process called a *safe-error attack* to obtain any digit of the secret key by comparing the final output with or without fault.

Such simple safe-error attack cannot happen in the case of the Algorithm 3 proposed by Montgomery [33], where a fault injected in a register will eventually propagate to the other one. Thus, the fault alters the final result in any case, preventing the attacker to obtain information. But, as we detail in Section 4, some information on the last digits may still leak, weakening the protection obtained from this ladder.

The Montgomery ladder is algorithmically equivalent [36] to the square-and-multiply(-always) algorithm(s), in the sense that $x$ has the same value for every iteration. Actually, some variants [9] of the
<figure><img src="image_2.png" /><figcaption>Figure 1: Power profile for the first 32 iterations of Algorithm 1. Based on the length of periods of power consumption (long for 1 and short for 0), an attacker can read the 32 first bits 10010110010000000001100000011101 of the secret key on the screen of the oscilloscope.</figcaption></figure>

ching perform the same operations, independently from the value of the secret key. Thus, an obvious solution is to add an `else` branch containing a dummy instruction [14] at Line 7 of the *square-and-multiply-always* Algorithm 2.

But power profiles also depend on values in the considered registers, so computing a multiplication in every case is better against SPA but not against more advanced side-channel attacks like CPA [10]. Fortunately, standard blinding techniques can prevent differential [14, 38] or correlation power analysis [10]. We use such a blinding technique in Subsection 5.2 and Subsection 6.2 to improve security in most solutions.

Moreover, countermeasures developed against a given attack may benefit another one [48]. The multiplication in the `else` branch of the square-and-multiply-always algorithm is a dummy operation in the sense that if the current secret bit is $k[i] = 0$ then the result is not used by the rest of the computation. Thus, a random fault injected [50] in the register containing $ax$ will propagate through

successive iterations and alter the final result only if the current secret bit is $k[i] = 1$. So, an attacker (see the attacker models in Section 4) able to inject a fault in a register at a given iteration can apply such a process called a *safe-error attack* to obtain any digit of the secret key by comparing the final output with or without fault.

Such simple safe-error attack cannot happen in the case of the Algorithm 3 proposed by Montgomery [33], where a fault injected in a register will eventually propagate to the other one. Thus, the fault alters the final result in any case, preventing the attacker to obtain information. But, as we detail in Section 4, some information on the last digits may still leak, weakening the protection obtained from this ladder.

The Montgomery ladder is algorithmically equivalent [36] to the square-and-multiply(-always) algorithm(s), in the sense that $x$ has the same value for every iteration. Actually, some variants [9] of the
<caption>**Algorithm 3** Montgomery Ladder for the Modular Exponentiation</caption>

**input** public $a, n$; secret $k$
1: $x \leftarrow 1$
2: $y \leftarrow a \bmod n$
3: **for** $i = d$ **to** 0 **do**
4: &nbsp;&nbsp;&nbsp;&nbsp;**if** $k[i] = 1$ **then**
5: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$x \leftarrow xy \bmod n$
6: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$y \leftarrow y^2 \bmod n$
7: &nbsp;&nbsp;&nbsp;&nbsp;**else**
8: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$y \leftarrow xy \bmod n$
9: &nbsp;&nbsp;&nbsp;&nbsp;**end if**
10: **end for**
11: **end for**
12: **return** $x$
**output** $x = a^k \bmod n$

square-and-multiply-always algorithm<fnref n="3" /> may be as resistant as the Montgomery ladder [24], by checking invariants [28] violated if a fault is injected. For instance, in the case of the Montgomery ladder, the invariant $y = ax$ is satisfied for every iteration. These invariants are important because their violation in case of fault injection can be detected by the algorithm itself, which then is able to trigger self-secure countermeasures [18], as discussed briefly in Subsection 4.3.

Note that the **else** branch in Algorithm 3 is identical to the **then** branch except that $x$ and $y$ are swapped which, because of code symmetry, provides also (partial<fnref n="4" />) protection against timing and power leakage. Moreover, the variable dependency makes these variables interleaved, so this exponentiation is algorithmically (but partially, as we demonstrate in Section 4) protected against safe-error attacks. Finally, as opposed to square-and-multiply-always in Algorithm 2, the code in the **else** branch of Algorithm 3 is not dead, so will not be removed by compiler optimizations.

Thus, such algorithmic properties provide some protection against side-channel and fault-injection attacks, and are therefore security properties which are desirable in more algorithms. We formalize

these properties in Section 3, then we propose secure algorithms for the modular exponentiation in Section 5.

## 2.4 Elliptic-curve cryptography (ECC)

ECC was independently introduced in 1985 by Victor Miller [39] and Neal Koblitz [30]. It is nowadays considered as an excellent choice for key exchange or digital signatures, especially when these mechanisms run on resource-constrained devices. The security of most cryptocurrencies is based on ECC, which has been standardized by the NIST [5, 40].

**Definition 1** (Elliptic Curve). Let $p$ be a prime. An elliptic curve in short Weierstrass form over a finite field $\mathbb{F}_p$ is the set $E(\mathbb{F}_p) = \{(x, y) \in \mathbb{F}_p \times \mathbb{F}_p \mid y^2 = x^3 + ax + b\} \cup \{\mathcal{O}\}$ with parameters $a, b \in \mathbb{F}_p$ satisfying $4a^3 + 27b^2 \neq 0$ and $\mathcal{O}$ being called the point at infinity.

The set $E(\mathbb{F}_p)$ is an additive Abelian group with an efficiently computable group law. The point $\mathcal{O}$ is the identity element of the group law. Point addition $P + Q$ or point doubling $2P$ involves additions and multiplications over $\mathbb{F}_p$. Depending on the parameters $a$ and $b$ of the curve, there exists many formulas<fnref n="5" /> to optimize these two operations.

The main operation in ECC is scalar multiplication $kA = A + \dots + A$, where $A$ is a point on a curve and $k$ is an integer. It can be performed by using the double-and-add Algorithm 4, similar to the square-and-multiply Algorithm 2. The initialization $x \leftarrow 1$ in square-and-multiply is replaced by $P \leftarrow \mathcal{O}^6$ in double-and-add, the squaring $x \leftarrow x^2$ is replaced by a doubling $P \leftarrow 2P$ and the multiplication $x \leftarrow ax$ is replaced by an addition $P \leftarrow A + P$, producing the output $P = ka$.

As the double-and-add Algorithm 4 for the scalar multiplication is the counterpart of the square-and-

<footnote n="3">³See [22] for highly regular right-to-left variants, [23] for a generalization to any basis and left-to-right/right-to-left variants, and [49] for their duality.</footnote>

<footnote n="4">⁴For instance, the variables $x$ and $y$ may have different access time, which would hinder protection against cache-timing leakage.</footnote>

<footnote n="5">⁵A large and updated survey on the elliptic curves explicit formulas database web site [46].</footnote>

<footnote n="6">⁶Definition 1 corresponds to the common representation of the elliptic curves in affine coordinates, but the point $\mathcal{O}$ at infinity cannot be represented in this coordinate system. Nevertheless, for efficiency reasons, operations on elliptic curves are computed in practice using projective coordinates [13], where $\mathcal{O}$ can be represented. Hence, Algorithm 4 is practical. Describing the various projective systems is out of the scope of this paper, hence we presented only the affine coordinates for the sake of simplicity.</footnote>
<caption>**Algorithm 3** Montgomery Ladder for the Modular Exponentiation</caption>

input public $a, n$; secret $k$
1: $x \leftarrow 1$
2: $y \leftarrow a \bmod n$
3: **for** $i = d$ **to** 0 **do**
4: &nbsp;&nbsp;&nbsp;&nbsp;**if** $k[i] = 1$ **then**
5: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$x \leftarrow xy \bmod n$
6: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$y \leftarrow y^2 \bmod n$
7: &nbsp;&nbsp;&nbsp;&nbsp;**else**
8: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$y \leftarrow xy \bmod n$
9: &nbsp;&nbsp;&nbsp;&nbsp;**end if**
10: **end for**
11: **end for**
12: **return** $x$
output $x = a^k \bmod n$

square-and-multiply-always algorithm<fnref n="3" /> may be as resistant as the Montgomery ladder [24], by checking invariants [28] violated if a fault is injected. For instance, in the case of the Montgomery ladder, the invariant $y = ax$ is satisfied for every iteration. These invariants are important because their violation in case of fault injection can be detected by the algorithm itself, which then is able to trigger self-secure countermeasures [18], as discussed briefly in Subsection 4.3.

Note that the **else** branch in Algorithm 3 is identical to the **then** branch except that $x$ and $y$ are swapped which, because of code symmetry, provides also (partial<fnref n="4" />) protection against timing and power leakage. Moreover, the variable dependency makes these variables interleaved, so this exponentiation is algorithmically (but partially, as we demonstrate in Section 4) protected against safe-error attacks. Finally, as opposed to square-and-multiply-always in Algorithm 2, the code in the **else** branch of Algorithm 3 is not dead, so will not be removed by compiler optimizations.

Thus, such algorithmic properties provide some protection against side-channel and fault-injection attacks, and are therefore security properties which are desirable in more algorithms. We formalize

these properties in Section 3, then we propose secure algorithms for the modular exponentiation in Section 5.

## 2.4 Elliptic-curve cryptography (ECC)

ECC was independently introduced in 1985 by Victor Miller [39] and Neal Koblitz [30]. It is nowadays considered as an excellent choice for key exchange or digital signatures, especially when these mechanisms run on resource-constrained devices. The security of most cryptocurrencies is based on ECC, which has been standardized by the NIST [5, 40].

**Definition 1** (Elliptic Curve). Let $p$ be a prime. An elliptic curve in short Weierstrass form over a finite field $\mathbb{F}_p$ is the set $E(\mathbb{F}_p) = \{(x, y) \in \mathbb{F}_p \times \mathbb{F}_p \mid y^2 = x^3 + ax + b\} \cup \{\mathcal{O}\}$ with parameters $a, b \in \mathbb{F}_p$ satisfying $4a^3 + 27b^2 \neq 0$ and $\mathcal{O}$ being called the point at infinity.

The set $E(\mathbb{F}_p)$ is an additive Abelian group with an efficiently computable group law. The point $\mathcal{O}$ is the identity element of the group law. Point addition $P + Q$ or point doubling $2P$ involves additions and multiplications over $\mathbb{F}_p$. Depending on the parameters $a$ and $b$ of the curve, there exists many formulas<fnref n="5" /> to optimize these two operations.

The main operation in ECC is scalar multiplication $kA = A + \dots + A$, where $A$ is a point on a curve and $k$ is an integer. It can be performed by using the double-and-add Algorithm 4, similar to the square-and-multiply Algorithm 2. The initialization $x \leftarrow 1$ in square-and-multiply is replaced by $P \leftarrow \mathcal{O}^6$ in double-and-add, the squaring $x \leftarrow x^2$ is replaced by a doubling $P \leftarrow 2P$ and the multiplication $x \leftarrow ax$ is replaced by an addition $P \leftarrow A + P$, producing the output $P = ka$.

As the double-and-add Algorithm 4 for the scalar multiplication is the counterpart of the square-and-

<footnote n="3">³See [22] for highly regular right-to-left variants, [23] for a generalization to any basis and left-to-right/right-to-left variants, and [49] for their duality.</footnote>

<footnote n="4">⁴For instance, the variables $x$ and $y$ may have different access time, which would hinder protection against cache-timing leakage.</footnote>

<footnote n="5">⁵A large and updated survey on the elliptic curves explicit formulas database web site [46].</footnote>

<footnote n="6">⁶*Definition 1* corresponds to the common representation of the elliptic curves in affine coordinates, but the point $\mathcal{O}$ at infinity cannot be represented in this coordinate system. Nevertheless, for efficiency reasons, operations on elliptic curves are computed in practice using projective coordinates [13], where $\mathcal{O}$ can be represented. Hence, Algorithm 4 is practical. Describing the various projective systems is out of the scope of this paper, hence we presented only the affine coordinates for the sake of simplicity.</footnote>
**Algorithm 4** Double-and-Add

input public A; secret k

1: $P \leftarrow \mathcal{O}$

2: **for** $i = d$ **to** 0 **do**

3: $P \leftarrow 2P$

4: **if** $k[i] = 1$ **then**

5: $P \leftarrow A + P$

6: **end if**

7: **end for**

8: **return** $P$

output $P = kA$

**Algorithm 5** Montgomery Ladder for the Scalar
Multiplication

input public A; secret k

1: $P \leftarrow \mathcal{O}$

2: $Q \leftarrow A$

3: **for** $i = d$ **to** 0 **do**

4: **if** $k[i] = 1$ **then**

5: $P \leftarrow P + Q$

6: $Q \leftarrow 2Q$

7: **else**

8: $Q \leftarrow Q + P$

9: $P \leftarrow 2P$

10: **end if**

11: **end for**

12: **return** $P$

output $P = kA$

multiply Algorithm 1 for the modular exponentiation, a variant of the Montgomery ladder is also available in Algorithm 5 for the scalar multiplication, providing another example of ladderization.

We propose secure algorithms for the scalar multiplication in Section 6.

## 2.5 Parallel Computations

Finally, we compare the secure algorithms we obtain in this paper with the Montgomery ladder, respectively in Section 5 for the modular exponentiation and in Section 6 for the scalar multiplication. Restricting such a comparison in terms of performance to sequential computations only would not reflect the current state of the art.

Indeed, parallel implementations of algorithms on multicore systems was investigated for scalar multiplication [25, 15]. Parallelism was lever-

aged in Graphical Processing Units (GPUs) to drastically increase the number of operations per second performed for the elliptic-curve factorization method [7]. Moreover, efficient elliptic curve point multiplications were obtained using an algorithm where both the pre-computation and post-computation stages are performed in parallel, on machines with up to eight cores [6]. Finally, leveraging an approach based on the residue number system, a parallel algorithm was proposed for elliptic curve point multiplication, efficient on more than four cores [1].

Therefore, when comparing our solutions to the Montgomery ladder in Subsections 5.4 and 6.5, we consider both sequential and parallel computations.

## 3 Ladder Equations

In this section, we formalize the desirable security properties occurring in algorithms like the Montgomery ladder (Algorithm 3) by using systems of equations we call *ladder equations*. These constraints are sufficient to refactor iterative conditional branchings (Subsection 3.1) as in the square-and-multiply algorithm (Algorithm 1 p.4) into semi- (Subsection 3.2) or fully-interleaved (Subsection 3.3) ladders, to make them more secure. The algorithms satisfying these constraints are called *ladderizable* and are characterized in Theorem 1 (Subsection 3.4). Finally, in Subsection 3.5 we state our research questions and we provide first answers.

### 3.1 Iterative Conditional Branchings

In this paper, we focus on code patterns like Algorithm 6, which consists in a conditional branching in (potentially nested) loop branching(s) and which we call an *iterative conditional branching*. Moreover, if the condition involves a sensitive value, i.e., which depends on confidential information, we call it a *sensitive iterative conditional branching*. Iterative conditional branching appear in algorithms like the square-and-multiply Algorithm 1 p.4 for the modular exponentiation, its counterpart the double-and-add Algorithm 4 p.7 for the elliptic curve point multiplication [39, 30], or the secure bit permutation in the McEliece cryptosystem [47],
**Algorithm 4** Double-and-Add

**input** public A; secret k

1: $P \leftarrow \mathcal{O}$

2: **for** $i = d$ **to** 0 **do**

3: $P \leftarrow 2P$

4: **if** $k[i] = 1$ **then**

5: $P \leftarrow A + P$

6: **end if**

7: **end for**

8: **return** P

**output** $P = kA$

**Algorithm 5** Montgomery Ladder for the Scalar
Multiplication

**input** public A; secret k

1: $P \leftarrow \mathcal{O}$

2: $Q \leftarrow A$

3: **for** $i = d$ **to** 0 **do**

4: **if** $k[i] = 1$ **then**

5: $P \leftarrow P + Q$

6: $Q \leftarrow 2Q$

7: **else**

8: $Q \leftarrow Q + P$

9: $P \leftarrow 2P$

10: **end if**

11: **end for**

12: **return** P

**output** $P = kA$

multiply Algorithm 1 for the modular exponentiation, a variant of the Montgomery ladder is also available in Algorithm 5 for the scalar multiplication, providing another example of ladderization.

We propose secure algorithms for the scalar multiplication in Section 6.

## 2.5 Parallel Computations

Finally, we compare the secure algorithms we obtain in this paper with the Montgomery ladder, respectively in Section 5 for the modular exponentiation and in Section 6 for the scalar multiplication. Restricting such a comparison in terms of performance to sequential computations only would not reflect the current state of the art.

Indeed, parallel implementations of algorithms on multicore systems was investigated for scalar multiplication [25, 15]. Parallelism was lever-

aged in Graphical Processing Units (GPUs) to drastically increase the number of operations per second performed for the elliptic-curve factorization method [7]. Moreover, efficient elliptic curve point multiplications were obtained using an algorithm where both the pre-computation and post-computation stages are performed in parallel, on machines with up to eight cores [6]. Finally, leveraging an approach based on the residue number system, a parallel algorithm was proposed for elliptic curve point multiplication, efficient on more than four cores [1].

Therefore, when comparing our solutions to the Montgomery ladder in Subsections 5.4 and 6.5, we consider both sequential and parallel computations.

## 3 Ladder Equations

In this section, we formalize the desirable security properties occurring in algorithms like the Montgomery ladder (Algorithm 3) by using systems of equations we call *ladder equations*. These constraints are sufficient to refactor iterative conditional branchings (Subsection 3.1) as in the square-and-multiply algorithm (Algorithm 1 p.4) into semi- (Subsection 3.2) or fully-interleaved (Subsection 3.3) ladders, to make them more secure. The algorithms satisfying these constraints are called *ladderizable* and are characterized in Theorem 1 (Subsection 3.4). Finally, in Subsection 3.5 we state our research questions and we provide first answers.

### 3.1 Iterative Conditional Branchings

In this paper, we focus on code patterns like Algorithm 6, which consists in a conditional branching in (potentially nested) loop branching(s) and which we call an *iterative conditional branching*. Moreover, if the condition involves a sensitive value, i.e., which depends on confidential information, we call it a *sensitive iterative conditional branching*. Iterative conditional branching appear in algorithms like the square-and-multiply Algorithm 1 p.4 for the modular exponentiation, its counterpart the double-and-add Algorithm 4 p.7 for the elliptic curve point multiplication [39, 30], or the secure bit permutation in the McEliece cryptosystem [47],
**Algorithm 6** Iterative Conditional Branching

1: $x \leftarrow \text{init}$

2: **for** $i = 1$ **to** $n$ **do**

3: ...

4: **if** secret **then**

5: $x \leftarrow \theta(x)$

6: **else**

7: $x \leftarrow \varepsilon(x)$

8: **end if**

9: ...

10: **end for**

**Algorithm 7** Loop bounded by a sensitive variable

1: assert(secret $\le$ bound)

2: **for** $i = 0$ **to** secret **do**

3: ...

4: **end for**

attacked in [43]. It also appears naturally when one tries to turn a loop on sensitive information as in Algorithm 7 into a safe loop containing a sensitive conditional branching as in Algorithm 8, that can itself be balanced to obfuscate the dependency on the secret. So, iterative conditional branchings are frequent in cryptosystems. Hence, making them at least as secure as the Montgomery ladder is desirable.

Note that our approach does not depend on the number or depth of the considered loops, hence the dots in Algorithm 6. We assume only that the conditional branching uses only one variable $x$, the multivariate case being left for future work.

**Definition 2** (Iterative Conditional Branching). An algorithm like Algorithm 6 is said with a (univariate) *iterative conditional branching* with two (unary) functions $\theta$ and $\varepsilon$.

## 3.2 Semi-Interleaved Ladders

To prevent information leakage from side-channel (Subsection 2.1) or fault injection (Subsection 2.2) attacks, we use a fresh variable $y$ in the *semi-interleaved ladder* presented in Algorithm 9. As in the Montgomery ladder in Algorithm 3 p.6, we look for two functions $\ell$ and $f$ such that for each iteration:

* the invariant $y = \ell(x)$ holds, and

**Algorithm 8** Equivalent iterative conditional branching

1: **for** $i = 0$ **to** bound **do**

2: **if** $i \le$ secret **then**

3: ...

4: **end if**

5: **end for**

**Algorithm 9** Semi-Interleaved ladders

1: $x \leftarrow \text{init}$

2: $y \leftarrow \ell(\text{init})$

3: **for** $i = 1$ **to** $n$ **do**

4: ...

5: **if** secret **then**

6: $x \leftarrow f(x, y)$

7: $y \leftarrow \varepsilon(y)$

8: **else**

9: $y \leftarrow f(y, x)$

10: $x \leftarrow \varepsilon(x)$

11: **end if**

12: ...

13: **end for**

* $x$ has the same value for every iteration as in Algorithm 6.

the Montgomery ladder being a particular case, where $\ell(x) = ax$ and, depending on the secret bit, $x$ is updated by either $\theta(x) = ax^2$ or $\varepsilon(x) = x^2$.

We determine by induction the constraints that $\ell$ and $f$ should satisfy. In Algorithm 9, $y = \ell(x)$ holds at the initialization. Then, we assume by induction that $y = \ell(x)$ holds at the beginning of an iteration.

In the **then** branch<fnref n="7" /> we have $x \leftarrow f(x, y)$ then $y \leftarrow \varepsilon(y)$, thus in order to satisfy the invariant $y = \ell(x)$ at the end of an iteration, the following equation must hold:

$$ \forall x, \varepsilon(\ell(x)) = \ell(f(x, \ell(x))) $$

where $x$ is quantified over the considered values e.g., modular integers for the modular exponentiation or points in elliptic-curve cryptography. In order to

<footnote n="7">⁷The condition depends on the secret, hence exploiting the condition to determine $\ell$ and $f$ could lead to data dependencies that could be attacked. Thus, we do not assume in the **then** branch that the condition is satisfied and we do not assume in the **else** branch that the negation of the condition is satisfied.</footnote>
**Algorithm 6** Iterative Conditional Branching

1: $x \leftarrow \text{init}$

2: **for** $i = 1$ **to** $n$ **do**

3: $\vdots$

4: **if** secret **then**

5: $x \leftarrow \theta(x)$

6: **else**

7: $x \leftarrow \varepsilon(x)$

8: **end if**

9: $\vdots$

10: **end for**

**Algorithm 7** Loop bounded by a sensitive variable

1: assert(secret $\le$ bound)

2: **for** $i = 0$ **to** secret **do**

3: $\vdots$

4: **end for**

attacked in [43]. It also appears naturally when one tries to turn a loop on sensitive information as in Algorithm 7 into a safe loop containing a sensitive conditional branching as in Algorithm 8, that can itself be balanced to obfuscate the dependency on the secret. So, iterative conditional branchings are frequent in cryptosystems. Hence, making them at least as secure as the Montgomery ladder is desirable.

Note that our approach does not depend on the number or depth of the considered loops, hence the dots in Algorithm 6. We assume only that the conditional branching uses only one variable $x$, the multivariate case being left for future work.

**Definition 2** (Iterative Conditional Branching). An algorithm like Algorithm 6 is said with a (univariate) *iterative conditional branching* with two (unary) functions $\theta$ and $\varepsilon$.

## 3.2 Semi-Interleaved Ladders

To prevent information leakage from side-channel (Subsection 2.1) or fault injection (Subsection 2.2) attacks, we use a fresh variable $y$ in the *semi-interleaved ladder* presented in Algorithm 9. As in the Montgomery ladder in Algorithm 3 p.6, we look for two functions $\ell$ and $f$ such that for each iteration:

* the invariant $y = \ell(x)$ holds, and

**Algorithm 8** Equivalent iterative conditional branching

1: **for** $i = 0$ **to** bound **do**

2: **if** $i \le$ secret **then**

3: $\vdots$

4: **end if**

5: **end for**

**Algorithm 9** Semi-Interleaved ladders

1: $x \leftarrow \text{init}$

2: $y \leftarrow \ell(\text{init})$

3: **for** $i = 1$ **to** $n$ **do**

4: $\dots$

5: **if** secret **then**

6: $x \leftarrow f(x, y)$

7: $y \leftarrow \varepsilon(y)$

8: **else**

9: $y \leftarrow f(y, x)$

10: $x \leftarrow \varepsilon(x)$

11: **end if**

12: $\dots$

13: **end for**

* $x$ has the same value for every iteration as in Algorithm 6.

the Montgomery ladder being a particular case, where $\ell(x) = ax$ and, depending on the secret bit, $x$ is updated by either $\theta(x) = ax^2$ or $\varepsilon(x) = x^2$.

We determine by induction the constraints that $\ell$ and $f$ should satisfy. In Algorithm 9, $y = \ell(x)$ holds at the initialization. Then, we assume by induction that $y = \ell(x)$ holds at the beginning of an iteration.

In the **then** branch<fnref n="7" /> we have $x \leftarrow f(x, y)$ then $y \leftarrow \varepsilon(y)$, thus in order to satisfy the invariant $y = \ell(x)$ at the end of an iteration, the following equation must hold:

$$ \forall x, \varepsilon(\ell(x)) = \ell(f(x, \ell(x))) $$

where $x$ is quantified over the considered values e.g., modular integers for the modular exponentiation or points in elliptic-curve cryptography. In order to

<footnote n="7">⁷The condition depends on the secret, hence exploiting the condition to determine $\ell$ and $f$ could lead to data dependencies that could be attacked. Thus, we do not assume in the **then** branch that the condition is satisfied and we do not assume in the **else** branch that the negation of the condition is satisfied.</footnote>
<caption>**Algorithm 10** Fully-Interleaved ladders</caption>

1: $x \leftarrow \text{init}$
2: $y \leftarrow \ell(\text{init})$
3: **for** $i = 1$ **to** $n$ **do**
4:     ...
5:     **if** secret **then**
6:         $x \leftarrow f(x, y)$
7:         $y \leftarrow g(x, y)$
8:     **else**
9:         $y \leftarrow f(y, x)$
10:        $x \leftarrow g(y, x)$
11:     **end if**
12:     ...
13: **end for**

have $x$ updated to $\theta(x)$ during the iteration, the following equation must hold:

$$ \forall x, f(x, \ell(x)) = \theta(x) $$

In the `else` branch we have $y \leftarrow f(y, x)$ then $x \leftarrow \varepsilon(x)$, thus in order to satisfy $y = \ell(x)$ at the end of an iteration the following equation must hold:

$$ \forall x, f(\ell(x), x) = \ell(\varepsilon(x)) $$

and $x$ is already updated to $\varepsilon(x)$ during the iteration. Therefore, we obtained the *ladder equations* for the semi-interleaved ladders:

**Definition 3** (Semi-Ladderizable). Let $A$ be an algorithm with a univariate iterative conditional branching with two unary functions denoted $\theta$ and $\varepsilon$. $A$ is semi-ladderizable if there exists a unary function $\ell$ and a binary function $f$ such that, for every considered input value $x$:

$$ \left\{ \begin{array}{l} \varepsilon(\ell(x)) = \ell(\theta(x)) \quad (1a) \\ f(x, \ell(x)) = \theta(x) \quad (1b) \\ f(\ell(x), x) = \ell(\varepsilon(x)) \quad (1c) \end{array} \right. $$

For instance, in the square-and-multiply Algorithm 1, we have $\theta(x) = ax^2$ and $\varepsilon(x) = x^2$, and we know that this iterative conditional branching can be semi-ladderized by using the Montgomery ladder Algorithm 3 with $\ell(x) = ax$ and $f(x, y) = xy$, but we demonstrate in Section 5 that there are other solutions.

Note that, to respect the form of the semi-interleaved ladder, we should have written $y \leftarrow yx$

instead of $y \leftarrow xy$ in the `else` branch of the Montgomery ladder Algorithm 3. The former is actually better regarding vulnerability to the M safe-error [24] or collision [27] attacks, demonstrating that the ladderization approach provides good practice.

Note also that the invariant function $\ell(x) = ax$ of the Montgomery ladder can directly be read in the `then` branch of Algorithm 1. This was leveraged in a previous study [11] to automatically infer $f(x, y) = xy$ and thus to automatically refactor the code to make it more secure. But this was done only in the simplest case of the semi-interleaved ladders with `if-then` branchings (so without `else` branch). In this paper we address the general case by manually solving these ladders equations for common cryptographic examples: the modular exponentiation in the RSA and DSA cryptosystems in Section 5, and the scalar multiplication in elliptic-curve cryptography in Section 6.

## 3.3 Fully-Interleaved Ladders

Unfortunately, the semi-interleaved ladder (Algorithm 9) is vulnerable to fault injection attacks, as we demonstrate in Section 4, because in every branch at least one variable ($x$ or $y$) depends only on its previous value and not on the previous value of both variables. Moreover, an attacker able to determine whether the output of one operation is used as the input to another can apply collision attacks<fnref n="8" /> to infer whether two following bits are the same [21].

To tackle these challenges, we propose in Algorithm 10 a *fully-interleaved ladder* using three functions $\ell$, $f$, and $g$. As in the previous subsection, we look for functions satisfying that for each iteration:

* the invariant $y = \ell(x)$ holds, and

* $x$ has the same value for every iteration as in Algorithm 6.

Similarly to the semi-interleaved ladders, we determine by induction the constraints that the functions $\ell$, $f$, and $g$ have to satisfy. Again, $y = \ell(x)$ is satisfied at the initialization. Then, we assume

<footnote n="8">⁸A possible countermeasure is to randomly blend variants of the ladder, or compute the exponentiation by taking a random (bounded) walk [35].</footnote>
<caption>**Algorithm 10** Fully-Interleaved ladders</caption>

1: $x \leftarrow \text{init}$
2: $y \leftarrow \ell(\text{init})$
3: **for** $i = 1$ **to** $n$ **do**
4:     ...
5:     **if** secret **then**
6:         $x \leftarrow f(x, y)$
7:         $y \leftarrow g(x, y)$
8:     **else**
9:         $y \leftarrow f(y, x)$
10:        $x \leftarrow g(y, x)$
11:     **end if**
12:     ...
13: **end for**

have $x$ updated to $\theta(x)$ during the iteration, the following equation must hold:

$$ \forall x, f(x, \ell(x)) = \theta(x) $$

In the `else` branch we have $y \leftarrow f(y, x)$ then $x \leftarrow \varepsilon(x)$, thus in order to satisfy $y = \ell(x)$ at the end of an iteration the following equation must hold:

$$ \forall x, f(\ell(x), x) = \ell(\varepsilon(x)) $$

and $x$ is already updated to $\varepsilon(x)$ during the iteration. Therefore, we obtained the *ladder equations* for the semi-interleaved ladders:

**Definition 3** (Semi-Ladderizable). Let $A$ be an algorithm with a univariate iterative conditional branching with two unary functions denoted $\theta$ and $\varepsilon$. $A$ is semi-ladderizable if there exists a unary function $\ell$ and a binary function $f$ such that, for every considered input value $x$:

$$ \left\{ \begin{array}{l} \varepsilon(\ell(x)) = \ell(\theta(x)) \quad (1a) \\ f(x, \ell(x)) = \theta(x) \quad (1b) \\ f(\ell(x), x) = \ell(\varepsilon(x)) \quad (1c) \end{array} \right. $$

For instance, in the square-and-multiply Algorithm 1, we have $\theta(x) = ax^2$ and $\varepsilon(x) = x^2$, and we know that this iterative conditional branching can be semi-ladderized by using the Montgomery ladder Algorithm 3 with $\ell(x) = ax$ and $f(x, y) = xy$, but we demonstrate in Section 5 that there are other solutions.

Note that, to respect the form of the semi-interleaved ladder, we should have written $y \leftarrow yx$

instead of $y \leftarrow xy$ in the `else` branch of the Montgomery ladder Algorithm 3. The former is actually better regarding vulnerability to the M safe-error [24] or collision [27] attacks, demonstrating that the ladderization approach provides good practice.

Note also that the invariant function $\ell(x) = ax$ of the Montgomery ladder can directly be read in the `then` branch of Algorithm 1. This was leveraged in a previous study [11] to automatically infer $f(x, y) = xy$ and thus to automatically refactor the code to make it more secure. But this was done only in the simplest case of the semi-interleaved ladders with `if-then` branchings (so without `else` branch). In this paper we address the general case by manually solving these ladders equations for common cryptographic examples: the modular exponentiation in the RSA and DSA cryptosystems in Section 5, and the scalar multiplication in elliptic-curve cryptography in Section 6.

## 3.3 Fully-Interleaved Ladders

Unfortunately, the semi-interleaved ladder (Algorithm 9) is vulnerable to fault injection attacks, as we demonstrate in Section 4, because in every branch at least one variable ($x$ or $y$) depends only on its previous value and not on the previous value of both variables. Moreover, an attacker able to determine whether the output of one operation is used as the input to another can apply collision attacks<fnref n="8" /> to infer whether two following bits are the same [21].

To tackle these challenges, we propose in Algorithm 10 a *fully-interleaved ladder* using three functions $\ell$, $f$, and $g$. As in the previous subsection, we look for functions satisfying that for each iteration:

* the invariant $y = \ell(x)$ holds, and

* $x$ has the same value for every iteration as in Algorithm 6.

Similarly to the semi-interleaved ladders, we determine by induction the constraints that the functions $\ell$, $f$, and $g$ have to satisfy. Again, $y = \ell(x)$ is satisfied at the initialization. Then, we assume

<footnote n="8">⁸A possible countermeasure is to randomly blend variants of the ladder, or compute the exponentiation by taking a random (bounded) walk [35].</footnote>
by induction that $y = \ell(x)$ at the beginning of an iteration.

In the **then** branch we have $x \leftarrow f(x, y)$ then $y \leftarrow g(x, y)$, thus in order to have $y = \ell(x)$ satisfied at the end of any iteration, the following equation must hold:

$$ \forall x, g(f(x, \ell(x)), \ell(x)) = \ell(f(x, \ell(x))) $$

and in order to have $x$ updated to $\theta(x)$ during the iteration, the following equation must hold:

$$ \forall x, f(x, \ell(x)) = \theta(x) $$

In the **else** branch we have $y \leftarrow f(y, x)$ then $x \leftarrow g(y, x)$, thus, in order to have $y = \ell(x)$ satisfied at the end of an iteration, the following equation must hold:

$$ \forall x, f(\ell(x), x) = \ell(g(f(\ell(x), x), x)) $$

and in order to have $x$ updated to $\varepsilon(x)$ during the iteration, the following equation must hold:

$$ \forall x, g(f(\ell(x), x), x) = \varepsilon(x) $$

Therefore, we obtain the ladder equations for the fully-interleaved ladders:

**Definition 4 (Fully-Ladderizable).** Let $A$ be an algorithm with a univariate iterative conditional branching with two unary functions denoted $\theta$ and $\varepsilon$. $A$ is fully-ladderizable if there exists a unary function $\ell$ and two binary functions $f$ and $g$ such that, for every considered input value $x$:

$$ \left\{ \begin{array}{ll} g(\theta(x), \ell(x)) = \ell(\theta(x)) & (2a) \\ f(x, \ell(x)) = \theta(x) & (2b) \\ f(\ell(x), x) = \ell(\varepsilon(x)) & (2c) \\ g(f(\ell(x), x), x) = \varepsilon(x) & (2d) \end{array} \right. $$

Note that Equation (1b) is Equation (2b) and Equation (1c) is Equation (2c). Without surprise, if $g$ is chosen such that $g(x, y) = \varepsilon(y)$ then Equation (1a) is a special case of Equation (2a), and Equation (2d) is satisfied. Thus, semi-interleaved ladders are subcases of fully-interleaved ladders for $g(x, y) = \varepsilon(y)$.

## 3.4 Ladderizable Algorithms

From Subsections 3.2 and 3.3 we obtained ladder equations, sufficient to guarantee that, for each iteration, the invariant holds and the considered variable $x$ is correctly updated. We use these constraints to define the class of the ladderizable algorithms, i.e., the algorithms that can be refactored to be more secure using ladderization:

**Theorem 1.** Let $A$ be an algorithm with an iterative conditional branching with two unary functions denoted $\theta$ and $\varepsilon$. If $A$ is semi-ladderizable with $\ell$ and $f$, or fully-ladderizable with $\ell$, $f$ and $g$, then for every iteration of the ladderized variant:

* $y = \ell(x)$

* $x$ is updated as in $A$ and takes on the value:

$$ x \leftarrow \begin{cases} \theta(x) & \text{if secret} \\ \varepsilon(x) & \text{otherwise} \end{cases} $$

Thus, for every algorithm with an iterative conditional branching, as in Algorithm 6, if there exists $\ell$ and $f$ satisfying the ladder equations in Definition 3 then the conditional branching can be refactored as in Algorithm 9 as a semi-interleaved ladder. Even better, if there exists $\ell$, $f$ and $g$ satisfying the ladder equations in Definition 4 then it can be refactored as in Algorithm 10 as a fully-interleaved ladder. In any case, the obtained algorithm is algorithmically equivalent [36] in the sense that for every iteration the considered variable $x$ has the same value for both original and ladderized variants.

## 3.5 Research Questions

In this paper we aim to answer the following research questions regarding the ladderization approach:

* **RQ1:** To which extent can the algorithmic strength of the Montgomery ladder be generalized to other algorithms?

* **RQ2:** How secure are interleaved ladders compared to the Montgomery ladder?

* **RQ3:** How feasible are interleaved ladders in practice and, if so, how performant are they compared to the Montgomery ladder?
by induction that $y = \ell(x)$ at the beginning of an iteration.

In the **then** branch we have $x \leftarrow f(x, y)$ then $y \leftarrow g(x, y)$, thus in order to have $y = \ell(x)$ satisfied at the end of any iteration, the following equation must hold:

$$ \forall x, g(f(x, \ell(x)), \ell(x)) = \ell(f(x, \ell(x))) $$

and in order to have $x$ updated to $\theta(x)$ during the iteration, the following equation must hold:

$$ \forall x, f(x, \ell(x)) = \theta(x) $$

In the **else** branch we have $y \leftarrow f(y, x)$ then $x \leftarrow g(y, x)$, thus, in order to have $y = \ell(x)$ satisfied at the end of an iteration, the following equation must hold:

$$ \forall x, f(\ell(x), x) = \ell(g(f(\ell(x), x), x)) $$

and in order to have $x$ updated to $\varepsilon(x)$ during the iteration, the following equation must hold:

$$ \forall x, g(f(\ell(x), x), x) = \varepsilon(x) $$

Therefore, we obtain the ladder equations for the fully-interleaved ladders:

**Definition 4 (Fully-Ladderizable).** Let $A$ be an algorithm with a univariate iterative conditional branching with two unary functions denoted $\theta$ and $\varepsilon$. $A$ is fully-ladderizable if there exists a unary function $\ell$ and two binary functions $f$ and $g$ such that, for every considered input value $x$:

$$ \left\{ \begin{array}{l} g(\theta(x), \ell(x)) = \ell(\theta(x)) \quad (2a) \\ f(x, \ell(x)) = \theta(x) \quad (2b) \\ f(\ell(x), x) = \ell(\varepsilon(x)) \quad (2c) \\ g(f(\ell(x), x), x) = \varepsilon(x) \quad (2d) \end{array} \right. $$

Note that Equation (1b) is Equation (2b) and Equation (1c) is Equation (2c). Without surprise, if $g$ is chosen such that $g(x, y) = \varepsilon(y)$ then Equation (1a) is a special case of Equation (2a), and Equation (2d) is satisfied. Thus, semi-interleaved ladders are subcases of fully-interleaved ladders for $g(x, y) = \varepsilon(y)$.

## 3.4 Ladderizable Algorithms

From Subsections 3.2 and 3.3 we obtained ladder equations, sufficient to guarantee that, for each iteration, the invariant holds and the considered variable $x$ is correctly updated. We use these constraints to define the class of the ladderizable algorithms, i.e., the algorithms that can be refactored to be more secure using ladderization:

**Theorem 1.** Let $A$ be an algorithm with an iterative conditional branching with two unary functions denoted $\theta$ and $\varepsilon$. If $A$ is semi-ladderizable with $\ell$ and $f$, or fully-ladderizable with $\ell$, $f$ and $g$, then for every iteration of the ladderized variant:

* $y = \ell(x)$

* $x$ is updated as in $A$ and takes on the value:

$$ x \leftarrow \begin{cases} \theta(x) & \text{if secret} \\ \varepsilon(x) & \text{otherwise} \end{cases} $$

Thus, for every algorithm with an iterative conditional branching, as in Algorithm 6, if there exists $\ell$ and $f$ satisfying the ladder equations in Definition 3 then the conditional branching can be refactored as in Algorithm 9 as a semi-interleaved ladder. Even better, if there exists $\ell$, $f$ and $g$ satisfying the ladder equations in Definition 4 then it can be refactored as in Algorithm 10 as a fully-interleaved ladder. In any case, the obtained algorithm is algorithmically equivalent [36] in the sense that for every iteration the considered variable $x$ has the same value for both original and ladderized variants.

## 3.5 Research Questions

In this paper we aim to answer the following research questions regarding the ladderization approach:

* **RQ1:** To which extent can the algorithmic strength of the Montgomery ladder be generalized to other algorithms?

* **RQ2:** How secure are interleaved ladders compared to the Montgomery ladder?

* **RQ3:** How feasible are interleaved ladders in practice and, if so, how performant are they compared to the Montgomery ladder?
Theorem 1 provides a theoretical answer to **RQ1**. We abstracted away the Montgomery ladder to the largest class of algorithms possible while preserving, through the ladder equations, its desirable security properties.

The protection against side-channel attacks comes from the code symmetry. In semi- or fully-interleaved ladders the *else* branch is identical to the *then* branch, except that *x* and *y* are swapped. So, the same operations are performed regardless the secret value, and both ladder types are secure against side-channel attacks depending on these operations, like simple timing attacks [32] or SPA [31]. Therefore, the ladderization refactoring is an algorithmic countermeasure against these side-channel attacks. Moreover, Subsections 5.2 and 6.2 demonstrate solutions with blinding integers which are randomly generated and thus provide protection against more complex side-channel attacks like CPA [10].

The protection against fault-injection attacks is investigated in Section 4. Then, to provide a more concrete answer to **RQ1**, we construct examples of semi- and fully-interleaved ladders in Section 5 for the modular exponentiation and in Section 6 for the scalar multiplication.

# 4 Vulnerability against Fault Injection Attacks

To investigate the vulnerability protection of the interleaved ladders (Section 3), we introduce in Subsections 4.1 and 4.2 two attacker models using fault injection techniques. As described in the background (Subsection 2.2), we consider only two types of fault injections: *random fault* (the affected variable is set to a random value) and *zeroing/one-ing fault* (some/all bits are set to 0 or 1). Injecting a random fault requires dedicated material and knowledge, and zeroing/one-ing bits is even more costly. But the feasibility of these (attacker) techniques does not impact the feasibility of the (defender) ladderization approach (**RQ3**), hence we do not consider in this paper the cost for the attacker.

We describe the fault-propagation patterns of the non-, semi- and fully-interleaved ladders in Subsection 4.1.1, then we describe the first attack in

Subsubsection 4.1.2, the second attack in Subsection 4.2.1, and the third attack in Subsection 4.2.2. Finally, we compare the vulnerability of the non-, semi- and fully-interleaved ladders in Subsection 4.3 and we provide there more answers to our research questions.

## 4.1 First Attacker Model

For ease of presentation, we assume as in the Montgomery ladder (Algorithm 3) that “secret” in the iterative conditional branching (Algorithm 6) and the semi- and fully-interleaved ladders (Algorithms 9 and 10) is the condition $k[i] = 1$, where $k[i]$ is the bit $i$ of the secret key $k$. But the approach would be similar for any other sensitive condition.

We start by the first attacker model, which uses only random faults.

**Definition 5 (First Attacker Model).** We assume that:

* The attacker wants to obtain the secret key stored in the chip and copied in the register $k$.

* The attacker can run the program any number of times:

- inputting $x_{\text{init}}$ and $y_{\text{init}}$, the initial values in the registers $x$ and $y$,

- obtaining $x_{\text{final}}$ and/or $y_{\text{final}}$, the final value(s) returned by the program.

* A run consists of iterations $i$ over $^91, \dots, n$, where:

- $k[i]$ is the bit $i$ of $k$,

- $x_i$ (resp. $y_i$) denotes the value in the register $x$ (resp. $y$) between iterations$^{10}$ $i-1$ and $i$.

* The attacker can $\ell x_i$ (resp. $\ell y_i$) inject a random fault (i.e., set the affected variable to a random value) in the register $x$ (resp. $y$) between iterations $i-1$ and $i$.

<footnote>$^9$To simplify the notations, we assume in this section that the counter is incremented (from 1 to $n$ with a step 1), but the approach is similar for other initial or final values, a decremented counter, and/or other step values.</footnote>

<footnote>$^{10}$Iteration 0 being the initialization.</footnote>
Theorem 1 provides a theoretical answer to **RQ1**. We abstracted away the Montgomery ladder to the largest class of algorithms possible while preserving, through the ladder equations, its desirable security properties.

The protection against side-channel attacks comes from the code symmetry. In semi- or fully-interleaved ladders the *else* branch is identical to the *then* branch, except that *x* and *y* are swapped. So, the same operations are performed regardless the secret value, and both ladder types are secure against side-channel attacks depending on these operations, like simple timing attacks [32] or SPA [31]. Therefore, the ladderization refactoring is an algorithmic countermeasure against these side-channel attacks. Moreover, Subsections 5.2 and 6.2 demonstrate solutions with blinding integers which are randomly generated and thus provide protection against more complex side-channel attacks like CPA [10].

The protection against fault-injection attacks is investigated in Section 4. Then, to provide a more concrete answer to **RQ1**, we construct examples of semi- and fully-interleaved ladders in Section 5 for the modular exponentiation and in Section 6 for the scalar multiplication.

# 4 Vulnerability against Fault Injection Attacks

To investigate the vulnerability protection of the interleaved ladders (Section 3), we introduce in Subsections 4.1 and 4.2 two attacker models using fault injection techniques. As described in the background (Subsection 2.2), we consider only two types of fault injections: *random fault* (the affected variable is set to a random value) and *zeroing/one-ing fault* (some/all bits are set to 0 or 1). Injecting a random fault requires dedicated material and knowledge, and zeroing/one-ing bits is even more costly. But the feasibility of these (attacker) techniques does not impact the feasibility of the (defender) ladderization approach (**RQ3**), hence we do not consider in this paper the cost for the attacker.

We describe the fault-propagation patterns of the non-, semi- and fully-interleaved ladders in Subsection 4.1.1, then we describe the first attack in

Subsubsection 4.1.2, the second attack in Subsection 4.2.1, and the third attack in Subsection 4.2.2. Finally, we compare the vulnerability of the non-, semi- and fully-interleaved ladders in Subsection 4.3 and we provide there more answers to our research questions.

## 4.1 First Attacker Model

For ease of presentation, we assume as in the Montgomery ladder (Algorithm 3) that “secret” in the iterative conditional branching (Algorithm 6) and the semi- and fully-interleaved ladders (Algorithms 9 and 10) is the condition $k[i] = 1$, where $k[i]$ is the bit $i$ of the secret key $k$. But the approach would be similar for any other sensitive condition.

We start by the first attacker model, which uses only random faults.

**Definition 5 (First Attacker Model).** We assume that:

* The attacker wants to obtain the secret key stored in the chip and copied in the register $k$.

* The attacker can run the program any number of times:

- inputting $x_{\text{init}}$ and $y_{\text{init}}$, the initial values in the registers $x$ and $y$,

- obtaining $x_{\text{final}}$ and/or $y_{\text{final}}$, the final value(s) returned by the program.

* A run consists of iterations $i$ over $^91, \dots, n$, where:

- $k[i]$ is the bit $i$ of $k$,

- $x_i$ (resp. $y_i$) denotes the value in the register $x$ (resp. $y$) between iterations$^{10}$ $i-1$ and $i$.

* The attacker can $\ell x_i$ (resp. $\ell y_i$) inject a random fault (i.e., set the affected variable to a random value) in the register $x$ (resp. $y$) between iterations $i-1$ and $i$.

<footnote>$^9$To simplify the notations, we assume in this section that the counter is incremented (from 1 to $n$ with a step 1), but the approach is similar for other initial or final values, a decremented counter, and/or other step values.</footnote>

<footnote>$^{10}$Iteration 0 being the initialization.</footnote>
After injecting a random fault in a register, the attacker might be unlucky and obtain the same value as before in this register. But this is unlikely (especially considering the size of modern cryptographic keys and messages) and can be mitigated by performing several tries. So, we assume for the sake of simplicity that the new value is always different. We also assume that this new value leads to a different final value. Otherwise, the attacker should try different $x_{init}$ and $y_{init}$ inputs.

### 4.1.1 Fault-Propagation Patterns

As described in Subsection 2.3, the attacker can perform a safe-error attack:

* run a program for the square-and-multiply(-always) Algorithm 1 (resp. Algorithm 2) for a given input $x_{init}$, obtaining a value $x_{final}$,

* then run the program again with the same input while injecting a fault $\ell y_i$ in the register $y = ax$ between iterations $i-1$ and $i$, obtaining a value $x_{fault}$.

If $x_{fault} = x_{final}$ then $k[i] = 0$, otherwise $k[i] = 1$. Hence, this safe-error attack leaks the value of this secret bit. The same attack can be repeated for every iteration, thus the attacker can obtain that way all the bits of the secret key.

In the square-and-multiply(-always) algorithm, because the current value of $x$ determines the next value of $x$, a faulted value $\ell x_i$ for an iteration $i$ always propagates to the next iteration $\ell x_{i+1}$, which we denote by $\ell x_i \Rightarrow \ell x_{i+1}$. To obtain the bit $k[i]$, the attacker has exploited the fact that a fault in register $y = ax$ propagates to $x$, denoted by $\ell y_i \Rightarrow \ell x_{i+1}$, only if $k[i] = 1$.

As opposed to this non-ladderized variant, in Algorithms 9 and 10 the values of $x$ and $y$ are interleaved and the fault-propagation patterns are the following:

1. For the semi-interleaved ladder:

$$ \ell x_i \Rightarrow (\ell x_{i+1} \text{ and } (\ell y_{i+1} \text{ only if } k[i] = 0)) $$

$$ \ell y_i \Rightarrow (\ell y_{i+1} \text{ and } (\ell x_{i+1} \text{ only if } k[i] = 1)) $$

which means that a fault always propagates to the same register, but propagates to the other depending on the current bit of the secret key.

$$ \begin{array}{ccc} k & \dots & k[n-1] & k[n] \\ x & & & \\ y & & \ell x_{\text{final}} & \\ & & \ell y_n & \ell y_{\text{final}} \end{array} $$

<caption>Figure 2: Fault-injection $\ell y_n$ on the last bit $k[n]$; if the final $x$ value has changed then $k[n] = 1$, otherwise $k[n] = 0$.</caption>

2. For the fully-interleaved ladder:

$$ (\ell x_i \text{ or } \ell y_i) \Rightarrow (\ell x_{i+1} \text{ and } \ell y_{i+1}) $$

which means that any fault in one register propagates in every case to both.

The fully-interleaved ladder has a lower fault tolerance i.e., it is easier to disrupt the computation. This is not convenient for properties like functionality, availability, or redundancy, but this prevents an attacker from obtaining the secret key, i.e., this increases security. In other words, the ladderization refactoring reduces the information leakage from fault injection by reducing also the fault tolerance. The semi-interleaved ladder is more robust, but this comes at the price of a fault-propagation pattern depending on the secret key, which can be exploited by our first attack.

### 4.1.2 First Fault-Injection Attack

The attacker can $\ell y_n$ inject a random fault in register $y$ just before the last iteration, as in Figure 2, then compare the $x$ output. If $x_{fault} = x_{final}$ then $k[n] = 0$, otherwise $k[n] = 1$. Thus, the attacker can obtain $k[n]$, the last bit of the secret key.

If the obtained bit was 0 as in Figure 3, the attacker can $\ell y_{n-1}$. In that case if $x_{fault} = x_{final}$ then $k[n-1] = 0$, otherwise $k[n-1] = 1$. This process can be repeated until a 1 is found.

If the obtained bit was 1 as in Figure 4, the attacker can $\ell x_{n-1}$. In that case if $y_{fault} = y_{final}$ then $k[n-1] = 1$, otherwise $k[n-1] = 0$. This process can be repeated until a 0 is found.

One may think that these processes can be alternated in order to recover all the bits of the secret key, but if there is a bit alternation i.e., $(k[i], k[i+1]) = (0, 1)$ or $(1, 0)$, then the bits before $i$ cannot be obtained, as illustrated in Figures 5 and 6. The attacker could obtain that way all the
After injecting a random fault in a register, the attacker might be unlucky and obtain the same value as before in this register. But this is unlikely (especially considering the size of modern cryptographic keys and messages) and can be mitigated by performing several tries. So, we assume for the sake of simplicity that the new value is always different. We also assume that this new value leads to a different final value. Otherwise, the attacker should try different $x_{init}$ and $y_{init}$ inputs.

### 4.1.1 Fault-Propagation Patterns

As described in Subsection 2.3, the attacker can perform a safe-error attack:

* run a program for the square-and-multiply(-always) Algorithm 1 (resp. Algorithm 2) for a given input $x_{init}$, obtaining a value $x_{final}$,

* then run the program again with the same input while injecting a fault $\ell y_i$ in the register $y = ax$ between iterations $i-1$ and $i$, obtaining a value $x_{fault}$.

If $x_{fault} = x_{final}$ then $k[i] = 0$, otherwise $k[i] = 1$. Hence, this safe-error attack leaks the value of this secret bit. The same attack can be repeated for every iteration, thus the attacker can obtain that way all the bits of the secret key.

In the square-and-multiply(-always) algorithm, because the current value of $x$ determines the next value of $x$, a faulted value $\ell x_i$ for an iteration $i$ always propagates to the next iteration $\ell x_{i+1}$, which we denote by $\ell x_i \Rightarrow \ell x_{i+1}$. To obtain the bit $k[i]$, the attacker has exploited the fact that a fault in register $y = ax$ propagates to $x$, denoted by $\ell y_i \Rightarrow \ell x_{i+1}$, only if $k[i] = 1$.

As opposed to this non-ladderized variant, in Algorithms 9 and 10 the values of $x$ and $y$ are interleaved and the fault-propagation patterns are the following:

1. For the semi-interleaved ladder:

$$ \ell x_i \Rightarrow (\ell x_{i+1} \text{ and } (\ell y_{i+1} \text{ only if } k[i] = 0)) $$

$$ \ell y_i \Rightarrow (\ell y_{i+1} \text{ and } (\ell x_{i+1} \text{ only if } k[i] = 1)) $$

which means that a fault always propagates to the same register, but propagates to the other depending on the current bit of the secret key.

$$ k \cdots k[n-1] k[n] $$

$x$

$1?/

$\ell x_{final}$

$y$

$\ell y_n - \ell y_{final}$

Figure 2: Fault-injection $\ell y_n$ on the last bit $k[n]$; if the final $x$ value has changed then $k[n] = 1$, otherwise $k[n] = 0$.

2. For the fully-interleaved ladder:

$$ (\ell x_i \text{ or } \ell y_i) \Rightarrow (\ell x_{i+1} \text{ and } \ell y_{i+1}) $$

which means that any fault in one register propagates in every case to both.

The fully-interleaved ladder has a lower fault tolerance i.e., it is easier to disrupt the computation. This is not convenient for properties like functionality, availability, or redundancy, but this prevents an attacker from obtaining the secret key, i.e., this increases security. In other words, the ladderization refactoring reduces the information leakage from fault injection by reducing also the fault tolerance. The semi-interleaved ladder is more robust, but this comes at the price of a fault-propagation pattern depending on the secret key, which can be exploited by our first attack.

### 4.1.2 First Fault-Injection Attack

The attacker can $\ell y_n$ inject a random fault in register $y$ just before the last iteration, as in Figure 2, then compare the $x$ output. If $x_{fault} = x_{final}$ then $k[n] = 0$, otherwise $k[n] = 1$. Thus, the attacker can obtain $k[n]$, the last bit of the secret key.

If the obtained bit was 0 as in Figure 3, the attacker can $\ell y_{n-1}$. In that case if $x_{fault} = x_{final}$ then $k[n-1] = 0$, otherwise $k[n-1] = 1$. This process can be repeated until a 1 is found.

If the obtained bit was 1 as in Figure 4, the attacker can $\ell x_{n-1}$. In that case if $y_{fault} = y_{final}$ then $k[n-1] = 1$, otherwise $k[n-1] = 0$. This process can be repeated until a 0 is found.

One may think that these processes can be alternated in order to recover all the bits of the secret key, but if there is a bit alternation i.e., $(k[i], k[i+1]) = (0, 1)$ or $(1, 0)$, then the bits before $i$ cannot be obtained, as illustrated in Figures 5 and 6. The attacker could obtain that way all the
<figure><img src="image_4.png" /><figcaption>Figure 3: The obtained bit $k[n]$ was 0. Fault-injection $\ell y_{n-1}$ on $k[n-1]$; if the final $x$ value has changed then $k[n-1] = 1$, otherwise $k[n-1] = 0$.</figcaption></figure>

<figure><img src="image_5.png" /><figcaption>Figure 4: The obtained bit $k[n]$ was 1. Fault-injection $\ell x_{n-1}$ on $k[n-1]$; if the final $y$ value has changed then $k[n-1] = 0$, otherwise $k[n-1] = 1$.</figcaption></figure>

bits only if the key is trivial, and it seems improbable that the attacker can obtain that way more than a small number of bits. In short, the attacker can obtain the final bits 10...0 if $x_{final}$ can be read, and the final bits 01...1 if $y_{final}$ can be read.

The vulnerability to fault injection is summarized in Table 1. Against the first attack, fully-interleaved ladders are more secure than semi-interleaved ladders, which are more secure than without interleaving at all. But we demonstrate in the next subsection that a stronger attacker is able to obtain all the bits of the key from both the semi- and fully-interleaved ladders.

## 4.2 Second Attacker Model

As opposed to the first attacker model, which uses only random faults, the second attacker model uses both random and zeroing/one-ing faults, thus allowing a wider range of attacks.

**Definition 6** (Second Attacker Model). We assume that:

* The second attacker has the same goal and means as the attacker in Definition 5.

* The second attacker can also $\ell k_{>i} = 0$ (resp. $\ell k_{>i} = 1$) stuck-at 0 (resp. 1) all the bits [50] of the register $k$ between iterations $i$ and $i+1$.

<figure><img src="image_6.png" /><figcaption>Figure 5: Fault-injection attack $\ell x_i$ or $\ell y_i$ before the bit alternation 01: in both cases the fault propagates to both $\ell x_{i+2}$ and $\ell y_{i+2}$.</figcaption></figure>

<figure><img src="image_7.png" /><figcaption>Figure 6: Fault-injection attack $\ell x_i$ or $\ell y_i$ before the bit alternation 10: in both cases the fault propagates to both $\ell x_{i+2}$ and $\ell y_{i+2}$.</figcaption></figure>

### 4.2.1 Second Fault-Injection Attack

The second attack is similar to the first one, but it leverages zeroing/one-ing faults to circumvent the bit alternation preventing the first attack from breaking the semi-interleaved ladders. Indeed, after retrieving the last bits of the secret key and reaching a bit alternation 01 (resp. 10), the attacker can:

* run the program on the unknown bits then, when reaching the known bits, zeroing (resp. one-ing) all the secret bits to obtain the final values $x_{final}$ and $y_{final}$,

* run the program on the unknown bits then, just before the last unknown bits, inject a random fault and finally, when reaching the known bits, zeroing (resp. one-ing) all the secret bits to obtain the faulted values $x_{fault}$ and $y_{fault}$.

Then, as in the first attack, the faulted values can be compared to the final values to determine the current secret bit. Finally, by repeating this process from the last to the first bit, the attacker can obtain all the bits of the secret key.

Therefore, this stronger attacker is able to break the semi-interleaved ladders by using the attack protocol represented<fnref n="11" /> in Algorithm 11,

<footnote n="11">¹¹Note that the iterations are reversed in the attack protocol compared to the execution of the studied device.</footnote>
<figure><img src="image_3.png" /><figcaption>Figure 3: The obtained bit $k[n]$ was 0. Fault-injection $\ell y_{n-1}$ on $k[n-1]$; if the final $x$ value has changed then $k[n-1] = 1$, otherwise $k[n-1] = 0$.</figcaption></figure>

<figure><img src="image_4.png" /><figcaption>Figure 4: The obtained bit $k[n]$ was 1. Fault-injection $\ell x_{n-1}$ on $k[n-1]$; if the final $y$ value has changed then $k[n-1] = 0$, otherwise $k[n-1] = 1$.</figcaption></figure>

bits only if the key is trivial, and it seems improbable that the attacker can obtain that way more than a small number of bits. In short, the attacker can obtain the final bits 10...0 if $x_{final}$ can be read, and the final bits 01...1 if $y_{final}$ can be read.

The vulnerability to fault injection is summarized in Table 1. Against the first attack, fully-interleaved ladders are more secure than semi-interleaved ladders, which are more secure than without interleaving at all. But we demonstrate in the next subsection that a stronger attacker is able to obtain all the bits of the key from both the semi- and fully-interleaved ladders.

## 4.2 Second Attacker Model

As opposed to the first attacker model, which uses only random faults, the second attacker model uses both random and zeroing/one-ing faults, thus allowing a wider range of attacks.

**Definition 6** (Second Attacker Model). We assume that:

* The second attacker has the same goal and means as the attacker in Definition 5.

* The second attacker can also $\ell k_{>i} = 0$ (resp. $\ell k_{>i} = 1$) stuck-at 0 (resp. 1) all the bits [50] of the register $k$ between iterations $i$ and $i+1$.

<figure><img src="image_5.png" /><figcaption>Figure 5: Fault-injection attack $\ell x_i$ or $\ell y_i$ before the bit alternation 01: in both cases the fault propagates to both $\ell x_{i+2}$ and $\ell y_{i+2}$.</figcaption></figure>

<figure><img src="image_6.png" /><figcaption>Figure 6: Fault-injection attack $\ell x_i$ or $\ell y_i$ before the bit alternation 10: in both cases the fault propagates to both $\ell x_{i+2}$ and $\ell y_{i+2}$.</figcaption></figure>

### 4.2.1 Second Fault-Injection Attack

The second attack is similar to the first one, but it leverages zeroing/one-ing faults to circumvent the bit alternation preventing the first attack from breaking the semi-interleaved ladders. Indeed, after retrieving the last bits of the secret key and reaching a bit alternation 01 (resp. 10), the attacker can:

* run the program on the unknown bits then, when reaching the known bits, zeroing (resp. one-ing) all the secret bits to obtain the final values $x_{final}$ and $y_{final}$,

* run the program on the unknown bits then, just before the last unknown bits, inject a random fault and finally, when reaching the known bits, zeroing (resp. one-ing) all the secret bits to obtain the faulted values $x_{fault}$ and $y_{fault}$.

Then, as in the first attack, the faulted values can be compared to the final values to determine the current secret bit. Finally, by repeating this process from the last to the first bit, the attacker can obtain all the bits of the secret key.

Therefore, this stronger attacker is able to break the semi-interleaved ladders by using the attack protocol represented<fnref n="11" /> in Algorithm 11,

<footnote n="11">¹¹Note that the iterations are reversed in the attack protocol compared to the execution of the studied device.</footnote>
<table><caption>Table 1: Vulnerability against fault-injection attacks</caption><thead><tr><th rowspan="3">Interleaving</th><th colspan="3">Obtained Bits</th></tr><tr><th>Model 1</th><th colspan="2">Model 2</th></tr><tr><th>Attack 1</th><th>Attack 2</th><th>Attack 3</th></tr></thead><tbody><tr><th>non</th><td>all</td><td>all</td><td>all</td></tr><tr><th>semi</th><td>some</td><td>all</td><td>all</td></tr><tr><th>fully</th><td>none</td><td>none</td><td>all</td></tr></tbody></table>

where EXE($x_{init}, y_{init}, \mathcal{L}k_{>i} = 1$) at Line 4 means that the studied program is executed with inputs $x_{init}, y_{init}$ and a stuck-at $\mathcal{L}k_{>i} = 1$, and EXE($x_{init}, y_{init}, \mathcal{L}k_{>i} = 1, \mathcal{L}x_i$) at Line 5 is the same but with a random fault $\mathcal{L}x_i$. In particular, if both $x_{final}$ and $y_{final}$ can be read, then the Montgomery Ladder can be broken by iterating over 0 to $d$ in Algorithm 3 p.6. This attack does not work against fully-interleaved ladders, but a fully-interleaved ladder is more difficult to obtain (when even possible), as discussed in Subsections 5.3 and 6.3. As before, the vulnerabilities against this attack are summarized in Table 1.

### 4.2.2 Third Fault-Injection Attack

According to Kerckhoffs principle [26], an attacker is assumed to know the architecture and the program, and thus is able to duplicate the setup of the targeted chip for a chosen value of the secret key. Thus, the attacker should be able to input $k$ at will and even to inject random faults in the register $k$, as in registers $x$ and $y$.

This assumption does not change the initial attacker model in Definition 5 because injecting a random fault in $k$ between the iterations $i-1$ and $i$ is equivalent, if the last $i-1$ bits are known, to input $k$ with the known bits and generate randomly the beginning of the key. But this assumption changes the second attacker model in Definition 6, who is now able to test the bits of the key from left to right.

Actually, being able to write deterministically in the key register is enough to obtain with a third attack all the bits of the key, even against fully-interleaved ladders. Indeed, we consider the second attacker knows the first $i$ bits $k[1]...k[i]$, where $i = 0$ for the initialization when no bit is known. By $\mathcal{L}k_{>i} = 0$ (resp. $\mathcal{L}k_{>i} = 1$) zeroing (resp. one-ing)

the last $i$ bits and $\mathcal{L}k_{>i+1} = 0$ (resp. $\mathcal{L}k_{>i+1} = 1$) zeroing (resp. one-ing) the last $i+1$ bits, the second attacker can compare $x_{fault0}$ and $x_{final0}$ (resp. $x_{fault1}$ and $x_{final1}$) obtained respectively for $k[1]...k[i]00...0$ and $k[1]...k[i]k[i+1]0...0$ (resp. with 1s instead of 0s at the end), and the same for $y$. Thus, the second attacker can (almost) determine whether $k[i+1] = 1$ (resp. 0):

* if $x_{fault0} \neq x_{final0}$ or $y_{fault0} \neq y_{final0}$ then $k[i+1] = 1$,

* if $x_{fault1} \neq x_{final1}$ or $y_{fault1} \neq y_{final1}$ then $k[i+1] = 0$.

If $x_{fault0} = x_{final0}$, $x_{fault1} = x_{final1}$, $y_{fault0} = y_{final0}$ and $y_{fault1} = y_{final1}$ then another inputs $x_{init}$, $y_{init}$ should be chosen in the protocol described in Algorithm 12.

That way all the bits of the secret key $k$ can be obtained, except the ones such that for every possible $x_{init}$, $x_{fault0} = x_{final0}$ and $x_{fault1} = x_{final1}$. But this case is unlikely, it does not prevent the attacker from discovering the other bits, and these bits make no difference in the output of the program of interest, thus it is likely that the attacker does not care. Therefore, such attacker can obtain all the (relevant) bits of the key, even against semi- and fully-interleaved ladders. Again, the vulnerabilities against this attack are summarized in Table 1.

## 4.3 Comparison

Investigating the general pattern of the semi- and fully-interleaved ladders in Algorithms 9 and 10 lead to exhaustively describe the fault-propagation patterns in Subsection 4.1.1, which in turn lead to the discovery of the three attacks described in this section. To our knowledge, these attacks are novel, which contributes to the fruitfulness of the ladderization approach, partly answering the RQ2 research question.

The vulnerabilities against these three fault-injection attacks are summarized in Table 1. Against the first attack, fully-interleaved ladders are more secure than semi-interleaved ladders, which are more secure than without interleaving at all. The second attack is able to break semi-interleaved ladders (for instance, the common Montgomery ladder), but not fully-interleaved ladders. Finally, the third attack is able to break all ladders.
<table><caption>Table 1: Vulnerability against fault-injection attacks</caption><thead><tr><th rowspan="3">Interleaving</th><th colspan="3">Obtained Bits</th></tr><tr><th>Model 1</th><th colspan="2">Model 2</th></tr><tr><th>Attack 1</th><th>Attack 2</th><th>Attack 3</th></tr></thead><tbody><tr><th>non</th><td>all</td><td>all</td><td>all</td></tr><tr><th>semi</th><td>some</td><td>all</td><td>all</td></tr><tr><th>fully</th><td>none</td><td>none</td><td>all</td></tr></tbody></table>

where EXE($x_{init}, y_{init}, \mathcal{L}k_{>i} = 1$) at Line 4 means that the studied program is executed with inputs $x_{init}, y_{init}$ and a stuck-at $\mathcal{L}k_{>i} = 1$, and EXE($x_{init}, y_{init}, \mathcal{L}k_{>i} = 1, \mathcal{L}x_i$) at Line 5 is the same but with a random fault $\mathcal{L}x_i$. In particular, if both $x_{final}$ and $y_{final}$ can be read, then the Montgomery Ladder can be broken by iterating over 0 to $d$ in Algorithm 3 p.6. This attack does not work against fully-interleaved ladders, but a fully-interleaved ladder is more difficult to obtain (when even possible), as discussed in Subsections 5.3 and 6.3. As before, the vulnerabilities against this attack are summarized in Table 1.

### 4.2.2 Third Fault-Injection Attack

According to Kerckhoffs principle [26], an attacker is assumed to know the architecture and the program, and thus is able to duplicate the setup of the targeted chip for a chosen value of the secret key. Thus, the attacker should be able to input $k$ at will and even to inject random faults in the register $k$, as in registers $x$ and $y$.

This assumption does not change the initial attacker model in Definition 5 because injecting a random fault in $k$ between the iterations $i-1$ and $i$ is equivalent, if the last $i-1$ bits are known, to input $k$ with the known bits and generate randomly the beginning of the key. But this assumption changes the second attacker model in Definition 6, who is now able to test the bits of the key from left to right.

Actually, being able to write deterministically in the key register is enough to obtain with a third attack all the bits of the key, even against fully-interleaved ladders. Indeed, we consider the second attacker knows the first $i$ bits $k[1]...k[i]$, where $i = 0$ for the initialization when no bit is known. By $\mathcal{L}k_{>i} = 0$ (resp. $\mathcal{L}k_{>i} = 1$) zeroing (resp. one-ing)

the last $i$ bits and $\mathcal{L}k_{>i+1} = 0$ (resp. $\mathcal{L}k_{>i+1} = 1$) zeroing (resp. one-ing) the last $i+1$ bits, the second attacker can compare $x_{fault0}$ and $x_{final0}$ (resp. $x_{fault1}$ and $x_{final1}$) obtained respectively for $k[1]...k[i]00...0$ and $k[1]...k[i]k[i+1]0...0$ (resp. with 1s instead of 0s at the end), and the same for $y$. Thus, the second attacker can (almost) determine whether $k[i+1] = 1$ (resp. 0):

* if $x_{fault0} \neq x_{final0}$ or $y_{fault0} \neq y_{final0}$ then $k[i+1] = 1$,

* if $x_{fault1} \neq x_{final1}$ or $y_{fault1} \neq y_{final1}$ then $k[i+1] = 0$.

If $x_{fault0} = x_{final0}$, $x_{fault1} = x_{final1}$, $y_{fault0} = y_{final0}$ and $y_{fault1} = y_{final1}$ then another inputs $x_{init}$, $y_{init}$ should be chosen in the protocol described in Algorithm 12.

That way all the bits of the secret key $k$ can be obtained, except the ones such that for every possible $x_{init}$, $x_{fault0} = x_{final0}$ and $x_{fault1} = x_{final1}$. But this case is unlikely, it does not prevent the attacker from discovering the other bits, and these bits make no difference in the output of the program of interest, thus it is likely that the attacker does not care. Therefore, such attacker can obtain all the (relevant) bits of the key, even against semi- and fully-interleaved ladders. Again, the vulnerabilities against this attack are summarized in Table 1.

## 4.3 Comparison

Investigating the general pattern of the semi- and fully-interleaved ladders in Algorithms 9 and 10 lead to exhaustively describe the fault-propagation patterns in Subsection 4.1.1, which in turn lead to the discovery of the three attacks described in this section. To our knowledge, these attacks are novel, which contributes to the fruitfulness of the ladderization approach, partly answering the RQ2 research question.

The vulnerabilities against these three fault-injection attacks are summarized in Table 1. Against the first attack, fully-interleaved ladders are more secure than semi-interleaved ladders, which are more secure than without interleaving at all. The second attack is able to break semi-interleaved ladders (for instance, the common Montgomery ladder), but not fully-interleaved ladders. Finally, the third attack is able to break all ladders.
<caption>**Algorithm 11** Protocol to Attack Semi-Interleaved Ladders</caption>

1: FIx ← False
2: **for** i = n to 1 **do**
3: &nbsp;&nbsp;&nbsp;&nbsp;**if** FIx = True **then**
4: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;($x_{final}, y_{final}$) ← EXE($x_{init}, y_{init}, \mathcal{L}k_{>i} = 1$)
5: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;($x_{fault}, y_{fault}$) ← EXE($x_{init}, y_{init}, \mathcal{L}k_{>i} = 1, \mathcal{L}x_i$)
6: &nbsp;&nbsp;&nbsp;&nbsp;**if** $y_{fault} = y_{final}$ **then**
7: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$k[i] \leftarrow 1$
8: &nbsp;&nbsp;&nbsp;&nbsp;**else**
9: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$k[i] \leftarrow 0$
10: &nbsp;&nbsp;&nbsp;&nbsp;FIx ← False
11: &nbsp;&nbsp;&nbsp;&nbsp;**end if**
12: &nbsp;&nbsp;&nbsp;&nbsp;**else**
13: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;($x_{final}, y_{final}$) ← EXE($x_{init}, y_{init}, \mathcal{L}k_{>i} = 0$)
14: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;($x_{fault}, y_{fault}$) ← EXE($x_{init}, y_{init}, \mathcal{L}k_{>i} = 0, \mathcal{L}y_i$)
15: &nbsp;&nbsp;&nbsp;&nbsp;**if** $x_{fault} = x_{final}$ **then**
16: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$k[i] \leftarrow 0$
17: &nbsp;&nbsp;&nbsp;&nbsp;**else**
18: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$k[i] \leftarrow 1$
19: &nbsp;&nbsp;&nbsp;&nbsp;FIx ← True
20: &nbsp;&nbsp;&nbsp;&nbsp;**end if**
21: &nbsp;&nbsp;&nbsp;&nbsp;**end if**
22: &nbsp;&nbsp;&nbsp;&nbsp;**end for**
23: &nbsp;&nbsp;&nbsp;&nbsp;**return** $k$

But these results have to be mitigated for semi-
and fully-interleaved ladders. Indeed, the invari-
ant $y = l(x)$ holds for every iteration. So, if a
random fault is injected in $x$ or $y$ as in the first
two attacks, the violation of the invariant allows
the algorithm to detect the fault [18] and thus to
enhance the appropriate fault policy e.g., stopping
the program or switching to a random key for the
rest of the computation. Moreover, the secret key
being known by the algorithm, self-secure counter-
measures could also be triggered against the third
attack.

Therefore, by design, semi- and fully-interleaved
ladders provide partial protection against the con-
sidered fault-injection attacks, completing the an-
swer to **RQ1** provided in Subsection 3.5. Semi-
interleaved ladders are as secure as the Mont-
gomery ladder regarding fault-injection attacks,
while fully-interleaved ladders provide more protec-
tion.

5 Generalizing the Mont-
gomery Ladder for the
Modular Exponentiation

Sections 5 and 6 generalize the algorithmic strength
of the Montgomery ladder by providing concrete
solutions for the ladder equations in the context
of various cryptosystems. In this section we con-
tinue our running example started in Subsection 2.3
by focusing on solving (Subsections 5.1 to 5.3)
the ladder equations for the modular exponenti-
ation. We compare the complexity of the novel
algorithms in Subsection 5.4 with the complexity
of the Montgomery ladder. Then, we demonstrate
in the case of the RSA [45] (Subsection 5.5) and
DSA [40] (Subsection 5.6) cryptosystems that our
fully-interleaved solution is practical. Results are
summarized in Subsection 5.7.

In the following, for any $n$ we consider $\mathbb{Z}/n\mathbb{Z}$ i.e.,
integers modulo $n$, and we denote $(\mathbb{Z}/n\mathbb{Z})^*$ the inte-
gers invertible modulo $n$. In this section, we assume
that the functions $\theta(x), \varepsilon(x), f(x, y), g(x, y)$, and
<caption>**Algorithm 11 Protocol to Attack Semi-Interleaved Ladders**</caption>

1: FIx ← False
2: **for** i = n to 1 **do**
3: &nbsp;&nbsp;&nbsp;&nbsp;**if** FIx = True **then**
4: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;($x_{final}, y_{final}$) ← EXE($x_{init}, y_{init}, \mathcal{L}k_{>i} = 1$)
5: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;($x_{fault}, y_{fault}$) ← EXE($x_{init}, y_{init}, \mathcal{L}k_{>i} = 1, \mathcal{L}x_i$)
6: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**if** $y_{fault} = y_{final}$ **then**
7: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$k[i] \leftarrow 1$
8: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**else**
9: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$k[i] \leftarrow 0$
10: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;FIx ← False
11: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**end if**
12: &nbsp;&nbsp;&nbsp;&nbsp;**else**
13: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;($x_{final}, y_{final}$) ← EXE($x_{init}, y_{init}, \mathcal{L}k_{>i} = 0$)
14: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;($x_{fault}, y_{fault}$) ← EXE($x_{init}, y_{init}, \mathcal{L}k_{>i} = 0, \mathcal{L}y_i$)
15: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**if** $x_{fault} = x_{final}$ **then**
16: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$k[i] \leftarrow 0$
17: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**else**
18: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$k[i] \leftarrow 1$
19: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;FIx ← True
20: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**end if**
21: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**end if**
22: &nbsp;&nbsp;&nbsp;&nbsp;**end for**
23: &nbsp;&nbsp;&nbsp;&nbsp;**return** $k$

But these results have to be mitigated for semi-
and fully-interleaved ladders. Indeed, the invari-
ant $y = l(x)$ holds for every iteration. So, if a
random fault is injected in $x$ or $y$ as in the first
two attacks, the violation of the invariant allows
the algorithm to detect the fault [18] and thus to
enhance the appropriate fault policy e.g., stopping
the program or switching to a random key for the
rest of the computation. Moreover, the secret key
being known by the algorithm, self-secure counter-
measures could also be triggered against the third
attack.

Therefore, by design, semi- and fully-interleaved
ladders provide partial protection against the con-
sidered fault-injection attacks, completing the an-
swer to RQ1 provided in Subsection 3.5. Semi-
interleaved ladders are as secure as the Mont-
gomery ladder regarding fault-injection attacks,
while fully-interleaved ladders provide more protec-
tion.

5 Generalizing the Mont-
gomery Ladder for the
Modular Exponentiation

Sections 5 and 6 generalize the algorithmic strength
of the Montgomery ladder by providing concrete
solutions for the ladder equations in the context
of various cryptosystems. In this section we con-
tinue our running example started in Subsection 2.3
by focusing on solving (Subsections 5.1 to 5.3)
the ladder equations for the modular exponenti-
ation. We compare the complexity of the novel
algorithms in Subsection 5.4 with the complexity
of the Montgomery ladder. Then, we demonstrate
in the case of the RSA [45] (Subsection 5.5) and
DSA [40] (Subsection 5.6) cryptosystems that our
fully-interleaved solution is practical. Results are
summarized in Subsection 5.7.

In the following, for any $n$ we consider $\mathbb{Z}/n\mathbb{Z}$ i.e.,
integers modulo $n$, and we denote $(\mathbb{Z}/n\mathbb{Z})^*$ the inte-
gers invertible modulo $n$. In this section, we assume
that the functions $\theta(x), \varepsilon(x), f(x, y), g(x, y)$, and
<caption>**Algorithm 12** Protocol to Attack Both Semi- and Fully-Interleaved Ladders</caption>

1: **for** i = 0 to n − 1 **do**
2: &nbsp;&nbsp;&nbsp;&nbsp;($x_{final}, y_{final}$) ← EXE($x_{init}, y_{init}, \mathcal{L}k_{>i} = 0$)
3: &nbsp;&nbsp;&nbsp;&nbsp;($x_{fault}, y_{fault}$) ← EXE($x_{init}, y_{init}, \mathcal{L}k_{>i+1} = 0$)
4: &nbsp;&nbsp;&nbsp;&nbsp;**if** $x_{fault} \neq x_{final}$ or $y_{fault} \neq y_{final}$ **then**
5: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$k[i+1] \leftarrow 1$
6: &nbsp;&nbsp;&nbsp;&nbsp;**else**
7: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;($x_{final}, y_{final}$) ← EXE($x_{init}, y_{init}, \mathcal{L}k_{>i} = 1$)
8: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;($x_{fault}, y_{fault}$) ← EXE($x_{init}, y_{init}, \mathcal{L}k_{>i+1} = 1$)
9: &nbsp;&nbsp;&nbsp;&nbsp;**if** $x_{fault} \neq x_{final}$ or $y_{fault} \neq y_{final}$ **then**
10: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$k[i+1] \leftarrow 0$
11: &nbsp;&nbsp;&nbsp;&nbsp;**end if**
12: &nbsp;&nbsp;&nbsp;&nbsp;**end if**
13: &nbsp;&nbsp;&nbsp;&nbsp;**end for**
14: &nbsp;&nbsp;&nbsp;&nbsp;**return** k

$\ell(x)$ occurring in ladder equations (Section 3) are
quadratic polynomials with coefficients in $\mathbb{Z}/n\mathbb{Z}$.

Because we consider the modular exponentia-
tion case (Subsection 2.3), the **then** branch corre-
sponds to the function $\theta(x) = ax^2$ and the **else**
branch to $\varepsilon(x) = x^2$. For the ladder function
$\ell(x) = \ell_2 x^2 + \ell_1 x + \ell_0$, to simplify the analysis we
assume $\ell_2 = 0$, obtaining $\ell(x) = \ell_1 x + \ell_0$, which
is still a generalization of the invariant $\ell(x) = ax$
obtained in the usual Montgomery ladder. More
complicated cases are left for future work.

To summarize, we consider the following coeffi-
cients:

$$
\begin{align*}
\theta(x) &= ax^2 \\
\varepsilon(x) &= x^2 \\
f(x,y) &= f_{20}x^2 + f_{11}xy + f_{02}y^2 + f_{10}x + f_{01}y + f_{00} \\
g(x,y) &= g_{20}x^2 + g_{11}xy + g_{02}y^2 + g_{10}x + g_{01}y + g_{00} \\
\ell(x) &= \ell_1 x + \ell_0
\end{align*}
$$

To ensure that $\theta(x) = ax^2$ and $\ell(x) = \ell_1 x + \ell_0$
depend on $x$, we assume that $a \neq 0$ and $\ell_1 \neq 0$.
Moreover, in the following we focus on solutions
without constraint on $a$ to preserve the generality
of the original Montgomery ladder.

Finally, note that $\mathbb{Z}/n\mathbb{Z}$ may not be an integral
domain i.e., there exists $x, y \in \mathbb{Z}/n\mathbb{Z} \setminus \{0\}$ such that
$xy = 0 \bmod n$, which is the case for RSA (Subsec-
tion 5.5) with $p$ and $q$ such that $n = pq$. Because
in this case $n$ cannot be easily factorized into $p$ and
$q$, and because we are looking for general solutions
for any $n$, if $x \neq 0$ and $xy = 0$ we look for solutions

$y = 0$, thus losing some generality but simplifying
the analysis.

5.1 Both Semi- and Fully-
Interleaved Ladders

We start by solving the ladder equations which are
common to the semi- and fully-interleaved cases.
By substituting the coefficients and simplifying,
Equation (1b) p.9 (resp. Equation (2b) p.10)
$f(x, \ell(x)) = \theta(x)$ for the semi- (resp. fully-) in-
terleaved cases is equivalent to:

$$
\left\{
\begin{array}{l}
f_{20} + f_{11}\ell_1 + f_{02}\ell_1^2 = a \\
f_{11}\ell_0 + 2f_{02}\ell_1\ell_0 + f_{10} + f_{01}\ell_1 = 0 \\
f_{02}\ell_0^2 + f_{01}\ell_0 + f_{00} = 0
\end{array}
\right.
$$

Similarly, Equation (1c) p.9 (resp. Equation (2c)
p.10) $f(\ell(x), x) = \ell(\varepsilon(x))$ for the semi- (resp.
fully-) interleaved cases is equivalent to:

$$
\left\{
\begin{array}{l}
f_{20}\ell_1^2 + f_{11}\ell_1 + f_{02} = \ell_1 \\
2f_{20}\ell_1\ell_0 + f_{11}\ell_0 + f_{10}\ell_1 + f_{01} = 0 \\
f_{20}\ell_0^2 + f_{10}\ell_0 + f_{00} = \ell_0
\end{array}
\right.
$$

5.2 Semi-Interleaved Ladder Solution

In this subsection we solve the ladder equations for
the semi-interleaved case. The remaining Equa-
tion (1a) p.9 $\varepsilon(\ell(x)) = \ell(\theta(x))$ for the semi-
<caption>**Algorithm 12** Protocol to Attack Both Semi- and Fully-Interleaved Ladders</caption>

1: **for** i = 0 to n − 1 **do**
2: &nbsp;&nbsp;&nbsp;&nbsp;$(x_{final}, y_{final}) \leftarrow \text{EXE}(x_{init}, y_{init}, \mathcal{L}k_{>i} = 0)$
3: &nbsp;&nbsp;&nbsp;&nbsp;$(x_{fault}, y_{fault}) \leftarrow \text{EXE}(x_{init}, y_{init}, \mathcal{L}k_{>i+1} = 0)$
4: &nbsp;&nbsp;&nbsp;&nbsp;**if** $x_{fault} \neq x_{final}$ or $y_{fault} \neq y_{final}$ **then**
5: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$k[i+1] \leftarrow 1$
6: &nbsp;&nbsp;&nbsp;&nbsp;**else**
7: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$(x_{final}, y_{final}) \leftarrow \text{EXE}(x_{init}, y_{init}, \mathcal{L}k_{>i} = 1)$
8: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$(x_{fault}, y_{fault}) \leftarrow \text{EXE}(x_{init}, y_{init}, \mathcal{L}k_{>i+1} = 1)$
9: &nbsp;&nbsp;&nbsp;&nbsp;**if** $x_{fault} \neq x_{final}$ or $y_{fault} \neq y_{final}$ **then**
10: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$k[i+1] \leftarrow 0$
11: &nbsp;&nbsp;&nbsp;&nbsp;**end if**
12: &nbsp;&nbsp;&nbsp;&nbsp;**end if**
13: &nbsp;&nbsp;&nbsp;&nbsp;**end for**
14: &nbsp;&nbsp;&nbsp;&nbsp;**return** k

$\ell(x)$ occurring in ladder equations (Section 3) are
quadratic polynomials with coefficients in $\mathbb{Z}/n\mathbb{Z}$.

Because we consider the modular exponentia-
tion case (Subsection 2.3), the **then** branch corre-
sponds to the function $\theta(x) = ax^2$ and the **else**
branch to $\varepsilon(x) = x^2$. For the ladder function
$\ell(x) = \ell_2 x^2 + \ell_1 x + \ell_0$, to simplify the analysis we
assume $\ell_2 = 0$, obtaining $\ell(x) = \ell_1 x + \ell_0$, which
is still a generalization of the invariant $\ell(x) = ax$
obtained in the usual Montgomery ladder. More
complicated cases are left for future work.

To summarize, we consider the following coeffi-
cients:

$$
\begin{align*}
\theta(x) &= ax^2 \\
\varepsilon(x) &= x^2 \\
f(x,y) &= f_{20}x^2 + f_{11}xy + f_{02}y^2 + f_{10}x + f_{01}y + f_{00} \\
g(x,y) &= g_{20}x^2 + g_{11}xy + g_{02}y^2 + g_{10}x + g_{01}y + g_{00} \\
\ell(x) &= \ell_1 x + \ell_0
\end{align*}
$$

To ensure that $\theta(x) = ax^2$ and $\ell(x) = \ell_1 x + \ell_0$
depend on $x$, we assume that $a \neq 0$ and $\ell_1 \neq 0$.
Moreover, in the following we focus on solutions
without constraint on $a$ to preserve the generality
of the original Montgomery ladder.

Finally, note that $\mathbb{Z}/n\mathbb{Z}$ may not be an integral
domain i.e., there exists $x, y \in \mathbb{Z}/n\mathbb{Z} \setminus \{0\}$ such that
$xy = 0 \bmod n$, which is the case for RSA (Subsec-
tion 5.5) with $p$ and $q$ such that $n = pq$. Because
in this case $n$ cannot be easily factorized into $p$ and
$q$, and because we are looking for general solutions
for any $n$, if $x \neq 0$ and $xy = 0$ we look for solutions

$y = 0$, thus losing some generality but simplifying
the analysis.

5.1 Both Semi- and Fully-
Interleaved Ladders

We start by solving the ladder equations which are
common to the semi- and fully-interleaved cases.
By substituting the coefficients and simplifying,
Equation (1b) p.9 (resp. Equation (2b) p.10)
$f(x, \ell(x)) = \theta(x)$ for the semi- (resp. fully-) in-
terleaved cases is equivalent to:

$$
\left\{
\begin{array}{l}
f_{20} + f_{11}\ell_1 + f_{02}\ell_1^2 = a \\
f_{11}\ell_0 + 2f_{02}\ell_1\ell_0 + f_{10} + f_{01}\ell_1 = 0 \\
f_{02}\ell_0^2 + f_{01}\ell_0 + f_{00} = 0
\end{array}
\right.
$$

Similarly, Equation (1c) p.9 (resp. Equation (2c)
p.10) $f(\ell(x), x) = \ell(\varepsilon(x))$ for the semi- (resp.
fully-) interleaved cases is equivalent to:

$$
\left\{
\begin{array}{l}
f_{20}\ell_1^2 + f_{11}\ell_1 + f_{02} = \ell_1 \\
2f_{20}\ell_1\ell_0 + f_{11}\ell_0 + f_{10}\ell_1 + f_{01} = 0 \\
f_{20}\ell_0^2 + f_{10}\ell_0 + f_{00} = \ell_0
\end{array}
\right.
$$

5.2 Semi-Interleaved Ladder Solution

In this subsection we solve the ladder equations for
the semi-interleaved case. The remaining Equa-
tion (1a) p.9 $\varepsilon(\ell(x)) = \ell(\theta(x))$ for the semi-
interleaved case is equivalent to:

$$ \begin{cases} \ell_1^2 = \ell_1 a \\ 2\ell_1\ell_0 = 0 \\ \ell_0^2 = \ell_0 \end{cases} $$

So, because $\ell_1 \neq 0$, we assume $\ell_1 = a$ and $\ell_0 = 0$. Therefore Equation (1b) is equivalent to:

$$ \begin{cases} f_{20} + f_{11}a + f_{02}a^2 = a \\ f_{10} + f_{01}a = 0 \\ f_{00} = 0 \end{cases} $$

and Equation (1c) is equivalent to:

$$ \begin{cases} f_{20}a^2 + f_{11}a + f_{02} = a \\ f_{10}a + f_{01} = 0 \\ f_{00} = 0 \end{cases} $$

From $f_{10} + f_{01}a = f_{10}a + f_{01}$ we deduce $f_{10}(a-1) = f_{01}(a-1)$, which is satisfied without constraint on $a$ if $f_{10} = f_{01}$. Moreover, from $f_{10} + f_{01}a = 0$ we obtain $f_{10} = -f_{01}a$, thus from $f_{10}a + f_{01} = 0$ we obtain $f_{01}(a^2 - 1) = 0$, which is always true without constraint on $a$ if $f_{01} = 0$. Therefore, we assume $f_{10} = 0 = f_{01}$.

From $f_{20} + f_{11}a + f_{02}a^2 = f_{20}a^2 + f_{11}a + f_{02}$ we deduce $f_{20}(a^2 - 1) = f_{02}(a^2 - 1)$, which is satisfied without constraint on $a$ if $f_{20} = f_{02}$. The remaining constraint is $f_{20}(a^2 + 1) + f_{11}a = a$, which is equivalent to $f_{20} = \frac{a}{a^2+1}(1 - f_{11})$. Because the coefficients are integers there exists $m$ such that $1 - f_{11} = m(a^2 + 1)$. Thus, we have $f_{20} = ma$ and $f_{11} = 1 - m(a^2 + 1)$.

**Theorem 2.** *The square-and-multiply algorithm in Algorithm 2 for the modular exponentiation with $\theta(x) = ax^2$ and $\varepsilon(x) = x^2$ is semi-ladderizable with:*

$$ \ell(x) = ax \\ f(x, y) = ma(x^2 + y^2) + (1 - m(a^2 + 1))xy $$

producing (after memoization of one squaring in $z$) Algorithm 13.

Note that if $m = 0$, then $f(x, y) = xy$, in which case this solution is the common Montgomery ladder. In this restricted case, the solution was generated semi-automatically in a previous paper [11] by solving the ladder equations.

<caption>**Algorithm 13** Semi-Interleaved Ladder for the Modular Exponentiation</caption>

**input** public $a, n$; secret $k$
1: $x \leftarrow 1$
2: $y \leftarrow a \bmod n$
3: $m \leftarrow \text{random}([0, n-1])$
4: $c_1 \leftarrow ma \bmod n$
5: $c_2 \leftarrow 1 - (c_1a + m) \bmod n$
6: **for** $i = d$ **to** 0 **do**
7: &nbsp;&nbsp;&nbsp;&nbsp;**if** $k[i] = 1$ **then**
8: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$z \leftarrow y^2 \bmod n$
9: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$x \leftarrow c_1(x^2 + z) + c_2xy \bmod n$
10: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$y \leftarrow z$
11: &nbsp;&nbsp;&nbsp;&nbsp;**else**
12: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$z \leftarrow x^2 \bmod n$
13: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$y \leftarrow c_1(y^2 + z) + c_2yx \bmod n$
14: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$x \leftarrow z$
15: &nbsp;&nbsp;&nbsp;&nbsp;**end if**
16: **end for**
17: **return** $x$
**output** $x = a^k \bmod n$

Note also that the coefficients $c_1$ and $c_2$ only depend on $m$, so they can be precomputed (Lines 4 and 5) before the loop, for the sake of performance.

Finally, because there is no constraint on $m$, it can be randomly generated (Line 3). Even if we have $x \leftarrow \theta(x) = ax^2$ at the end of each iteration (Section 3), such a randomly generated integer would affect the bits flips that can be observed during intermediate computations of $x \leftarrow c_1(x^2 + z) + c_2xy \bmod n$ (Line 9). Thus, $m$ can be used as a blinding integer (Subsection 2.3) to reduce vulnerability against advanced side-channel attacks like CPA [10].

## 5.3 Fully-Interleaved Ladder Solution (General Case)

In this subsection we solve the ladder equations for the fully-interleaved case. Remain two equations. Equation (2a) p.10 $g(\theta(x), \ell(x)) = \ell(\theta(x))$ for the
interleaved case is equivalent to:

$$ \left\{ \begin{array}{l} \ell_1^2 = \ell_1 a \\ 2\ell_1\ell_0 = 0 \\ \ell_0^2 = \ell_0 \end{array} \right. $$

So, because $\ell_1 \neq 0$, we assume $\ell_1 = a$ and $\ell_0 = 0$. Therefore Equation (1b) is equivalent to:

$$ \left\{ \begin{array}{l} f_{20} + f_{11}a + f_{02}a^2 = a \\ f_{10} + f_{01}a = 0 \\ f_{00} = 0 \end{array} \right. $$

and Equation (1c) is equivalent to:

$$ \left\{ \begin{array}{l} f_{20}a^2 + f_{11}a + f_{02} = a \\ f_{10}a + f_{01} = 0 \\ f_{00} = 0 \end{array} \right. $$

From $f_{10} + f_{01}a = f_{10}a + f_{01}$ we deduce $f_{10}(a-1) = f_{01}(a-1)$, which is satisfied without constraint on $a$ if $f_{10} = f_{01}$. Moreover, from $f_{10} + f_{01}a = 0$ we obtain $f_{10} = -f_{01}a$, thus from $f_{10}a + f_{01} = 0$ we obtain $f_{01}(a^2 - 1) = 0$, which is always true without constraint on $a$ if $f_{01} = 0$. Therefore, we assume $f_{10} = 0 = f_{01}$.

From $f_{20} + f_{11}a + f_{02}a^2 = f_{20}a^2 + f_{11}a + f_{02}$ we deduce $f_{20}(a^2 - 1) = f_{02}(a^2 - 1)$, which is satisfied without constraint on $a$ if $f_{20} = f_{02}$. The remaining constraint is $f_{20}(a^2 + 1) + f_{11}a = a$, which is equivalent to $f_{20} = \frac{a}{a^2+1}(1 - f_{11})$. Because the coefficients are integers there exists $m$ such that $1 - f_{11} = m(a^2 + 1)$. Thus, we have $f_{20} = ma$ and $f_{11} = 1 - m(a^2 + 1)$.

**Theorem 2.** *The square-and-multiply algorithm in Algorithm 2 for the modular exponentiation with $\theta(x) = ax^2$ and $\varepsilon(x) = x^2$ is semi-ladderizable with:*

$$ \ell(x) = ax \\ f(x, y) = ma(x^2 + y^2) + (1 - m(a^2 + 1))xy $$

*producing (after memoization of one squaring in z)*

**Algorithm 13.**

Note that if $m = 0$, then $f(x, y) = xy$, in which case this solution is the common Montgomery ladder. In this restricted case, the solution was generated semi-automatically in a previous paper [11] by solving the ladder equations.

<caption>**Algorithm 13** Semi-Interleaved Ladder for the Modular Exponentiation</caption>

**input** public $a, n$; secret $k$
1: $x \leftarrow 1$
2: $y \leftarrow a \bmod n$
3: $m \leftarrow \text{random}([0, n-1])$
4: $c_1 \leftarrow ma \bmod n$
5: $c_2 \leftarrow 1 - (c_1a + m) \bmod n$
6: **for** $i = d$ **to** 0 **do**
7: &nbsp;&nbsp;&nbsp;&nbsp;**if** $k[i] = 1$ **then**
8: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$z \leftarrow y^2 \bmod n$
9: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$x \leftarrow c_1(x^2 + z) + c_2xy \bmod n$
10: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$y \leftarrow z$
11: &nbsp;&nbsp;&nbsp;&nbsp;**else**
12: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$z \leftarrow x^2 \bmod n$
13: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$y \leftarrow c_1(y^2 + z) + c_2yx \bmod n$
14: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$x \leftarrow z$
15: &nbsp;&nbsp;&nbsp;&nbsp;**end if**
16: **end for**
17: **return** $x$
**output** $x = a^k \bmod n$

Note also that the coefficients $c_1$ and $c_2$ only depend on $m$, so they can be precomputed (Lines 4 and 5) before the loop, for the sake of performance.

Finally, because there is no constraint on $m$, it can be randomly generated (Line 3). Even if we have $x \leftarrow \theta(x) = ax^2$ at the end of each iteration (Section 3), such a randomly generated integer would affect the bits flips that can be observed during intermediate computations of $x \leftarrow c_1(x^2 + z) + c_2xy \bmod n$ (Line 9). Thus, $m$ can be used as a blinding integer (Subsection 2.3) to reduce vulnerability against advanced side-channel attacks like CPA [10].

## 5.3 Fully-Interleaved Ladder Solution (General Case)

In this subsection we solve the ladder equations for the fully-interleaved case. Remain two equations. Equation (2a) p.10 $g(\theta(x), \ell(x)) = \ell(\theta(x))$ for the
fully-interleaved cases is equivalent to:

$$
\left\{
\begin{array}{l}
g_{20}a^2 = 0 \\
g_{11}\ell_1 a = 0 \\
g_{11}\ell_0 a + g_{02}\ell_1^2 + g_{10}a = \ell_1 a \\
2g_{02}\ell_1\ell_0 + g_{01}\ell_1 = 0 \\
g_{02}\ell_0^2 + g_{01}\ell_0 + g_{00} = \ell_0
\end{array}
\right.
$$

So, because $a \neq 0$ and $\ell_1 \neq 0$, we assume $g_{20} = 0$ from the first equation, $g_{11} = 0$ from the second, and the remaining constraints are:

$$
\left\{
\begin{array}{l}
g_{02}\ell_1^2 + g_{10}a = \ell_1 a \\
2g_{02}\ell_1\ell_0 + g_{01}\ell_1 = 0 \\
g_{02}\ell_0^2 + g_{01}\ell_0 + g_{00} = \ell_0
\end{array}
\right.
$$

According to Equation (2c) investigated in Sub-
section 5.1, $f(\ell(x), x) = \ell(\varepsilon(x)) = \ell_1 x^2 + \ell_0$, so
by using $g_{20} = g_{11} = 0$ we have:

$$
\begin{align*}
g(f(\ell(x), x), x) \\
&= (g_{02} + g_{10}\ell_1)x^2 + (g_{01})x + (g_{10}\ell_0 + g_{00})
\end{align*}
$$

Finally, the last equation is Equation (2d) p.10
g(f(ℓ(x), x), x) = ε(x) for the fully-interleaved
cases is equivalent to:

$$
\left\{
\begin{array}{l}
g_{02} + g_{10}\ell_1 = 1 \\
g_{01} = 0 \\
g_{10}\ell_0 + g_{00} = 0
\end{array}
\right.
$$

Because $g_{20} = g_{11} = g_{01} = 0$ and we require $g(x,y) = g_{02}y^2 + g_{10}x + g_{00}$ to depend on both $x$ and $y$, we have to assume $g_{02} \neq 0$ and $g_{10} \neq 0$. By using $g_{01} = 0$ the remaining constraints from Equation (2a) are:

$$
\left\{
\begin{array}{l}
g_{02}\ell_1^2 + g_{10}a = \ell_1 a \\
g_{02}\ell_1\ell_0 = 0 \\
g_{02}\ell_0^2 + g_{00} = \ell_0
\end{array}
\right.
$$

Because $g_{02} \neq 0$ and $\ell_1 \neq 0$, the second equality im-
plies that $\ell_0 = 0$. Thus, the remaining constraints
from Equation (2a) and Equation (2d) are:

$$
\left\{
\begin{array}{l}
g_{02}\ell_1^2 + g_{10}a = \ell_1 a \\
g_{02} + g_{10}\ell_1 = 1 \\
g_{20} = g_{11} = g_{01} = g_{00} = 0
\end{array}
\right.
$$

By using the second equality $g_{02} = 1 - g_{10}\ell_1$, the
first equality is equivalent to:

$g_{10}(a - \ell_1^3) = \ell_1(a - \ell_1)$

Because $g_{10} \neq 0$ and $\ell_1 \neq 0$, note that $a = \ell_1^3 \Leftrightarrow a = \ell_1$, in which case $\ell_1^3 = \ell_1$, thus $a = \ell_1 = \pm 1$. To remove the constraint on $a$, we assume that $a \neq \ell_1^3$, and thus $g_{10}$ and $g_{02}$ depend only on $a$ and $\ell_1$:

$$
\begin{align*}
g_{10} &= \ell_1 \frac{a - \ell_1}{a - \ell_1^3} \\
g_{02} &= 1 - g_{10}\ell_1 = a \frac{1 - \ell_1^2}{a - \ell_1^3} \\
\text{so } g(x, y) &= g_{02}y^2 + g_{10}x \\
&= \frac{1}{a - \ell_1^3} (a(1 - \ell_1^2)y^2 + \ell_1(a - \ell_1)x)
\end{align*}
$$

Because $\ell_1 \neq 0$ and $g_{10} \neq 0$ we have to assume that,
as opposed to the semi-interleaved cases, $\ell_1 \neq a$.
As for the semi-interleaved cases, because $\ell_0 = 0$,
the constraints from the common Equations (2b)
and (2c) can be simplified:

$$
\left\{
\begin{array}{l}
f_{20} + f_{11}\ell_1 + f_{02}\ell_1^2 = a & (L_1) \\
f_{20}\ell_1^2 + f_{11}\ell_1 + f_{02} = \ell_1 & (L_2) \\
f_{10} + f_{01}\ell_1 = 0 & (L_3) \\
f_{10}\ell_1 + f_{01} = 0 & (L_4) \\
f_{00} = 0 &
\end{array}
\right.
$$

In order to have a non-trivial ladder $\ell(x) = \ell_1 x$,
we assume that $\ell_1 \neq \pm 1$. With $(L_4) - (L_3)$ we
obtain $(f_{10} - f_{01})(\ell_1 - 1) = 0$ thus $f_{10} = f_{01}$, and
with $(L_3)$ we have $f_{10}(\ell_1 + 1) = 0$, so $f_{10} = f_{01} = 0$.
With $(L_1) - (L_2)$ we obtain $(f_{02} - f_{20})(\ell_1^2 - 1) =$
$a - \ell_1$, so $f_{02} = f_{20} + \frac{a-\ell_1}{\ell_1^2-1}$. Therefore, remain the
following constraints:

$$
\left\{
\begin{array}{l}
f_{20}(\ell_1^2 + 1) + f_{11}\ell_1 = a - \ell_1^2 \frac{a - \ell_1}{\ell_1^2 - 1} = \ell_1 - \frac{a - \ell_1}{\ell_1^2 - 1} \\
\\
f_{02} = f_{20} + \frac{a - \ell_1}{\ell_1^2 - 1} \\
\\
f_{10} = f_{01} = f_{00} = 0
\end{array}
\right.
$$

The first equality is obtained from (L1) and the
second from (L2). Note that $a - \ell_1^2 \frac{a - \ell_1}{\ell_1^2 - 1} = \ell_1 - \frac{a - \ell_1}{\ell_1^2 - 1}$
is already satisfied and thus is not a constraint.
Moreover, because $\ell_1 \neq 0$, by using the second line,
fully-interleaved cases is equivalent to:

$$
\left\{
\begin{array}{l}
g_{20}a^2 = 0 \\
g_{11}\ell_1 a = 0 \\
g_{11}\ell_0 a + g_{02}\ell_1^2 + g_{10}a = \ell_1 a \\
2g_{02}\ell_1\ell_0 + g_{01}\ell_1 = 0 \\
g_{02}\ell_0^2 + g_{01}\ell_0 + g_{00} = \ell_0
\end{array}
\right.
$$

So, because $a \neq 0$ and $\ell_1 \neq 0$, we assume $g_{20} = 0$ from the first equation, $g_{11} = 0$ from the second, and the remaining constraints are:

$$
\left\{
\begin{array}{l}
g_{02}\ell_1^2 + g_{10}a = \ell_1 a \\
2g_{02}\ell_1\ell_0 + g_{01}\ell_1 = 0 \\
g_{02}\ell_0^2 + g_{01}\ell_0 + g_{00} = \ell_0
\end{array}
\right.
$$

According to Equation (2c) investigated in Sub-
section 5.1, $f(\ell(x), x) = \ell(\varepsilon(x)) = \ell_1 x^2 + \ell_0$, so
by using $g_{20} = g_{11} = 0$ we have:

$$
\begin{align*}
g(f(\ell(x), x), x) \\
&= (g_{02} + g_{10}\ell_1)x^2 + (g_{01})x + (g_{10}\ell_0 + g_{00})
\end{align*}
$$

Finally, the last equation is Equation (2d) p.10
g(f(ℓ(x), x), x) = ε(x) for the fully-interleaved
cases is equivalent to:

$$
\left\{
\begin{array}{l}
g_{02} + g_{10}\ell_1 = 1 \\
g_{01} = 0 \\
g_{10}\ell_0 + g_{00} = 0
\end{array}
\right.
$$

Because $g_{20} = g_{11} = g_{01} = 0$ and we require $g(x,y) = g_{02}y^2 + g_{10}x + g_{00}$ to depend on both $x$ and $y$, we have to assume $g_{02} \neq 0$ and $g_{10} \neq 0$. By using $g_{01} = 0$ the remaining constraints from Equation (2a) are:

$$
\left\{
\begin{array}{l}
g_{02}\ell_1^2 + g_{10}a = \ell_1 a \\
g_{02}\ell_1\ell_0 = 0 \\
g_{02}\ell_0^2 + g_{00} = \ell_0
\end{array}
\right.
$$

Because $g_{02} \neq 0$ and $\ell_1 \neq 0$, the second equality im-
plies that $\ell_0 = 0$. Thus, the remaining constraints
from Equation (2a) and Equation (2d) are:

$$
\left\{
\begin{array}{l}
g_{02}\ell_1^2 + g_{10}a = \ell_1 a \\
g_{02} + g_{10}\ell_1 = 1 \\
g_{20} = g_{11} = g_{01} = g_{00} = 0
\end{array}
\right.
$$

By using the second equality $g_{02} = 1 - g_{10}\ell_1$, the
first equality is equivalent to:

$g_{10}(a - \ell_1^3) = \ell_1(a - \ell_1)$

Because $g_{10} \neq 0$ and $\ell_1 \neq 0$, note that $a = \ell_1^3 \Leftrightarrow a = \ell_1$, in which case $\ell_1^3 = \ell_1$, thus $a = \ell_1 = \pm 1$. To remove the constraint on $a$, we assume that $a \neq \ell_1^3$, and thus $g_{10}$ and $g_{02}$ depend only on $a$ and $\ell_1$:

$$
\begin{align*}
g_{10} &= \ell_1 \frac{a - \ell_1}{a - \ell_1^3} \\
g_{02} &= 1 - g_{10}\ell_1 = a \frac{1 - \ell_1^2}{a - \ell_1^3} \\
\text{so } g(x, y) &= g_{02}y^2 + g_{10}x \\
&= \frac{1}{a - \ell_1^3} (a(1 - \ell_1^2)y^2 + \ell_1(a - \ell_1)x)
\end{align*}
$$

Because $\ell_1 \neq 0$ and $g_{10} \neq 0$ we have to assume that,
as opposed to the semi-interleaved cases, $\ell_1 \neq a$.
As for the semi-interleaved cases, because $\ell_0 = 0$,
the constraints from the common Equations (2b)
and (2c) can be simplified:

$$
\left\{
\begin{array}{l}
f_{20} + f_{11}\ell_1 + f_{02}\ell_1^2 = a & (L_1) \\
f_{20}\ell_1^2 + f_{11}\ell_1 + f_{02} = \ell_1 & (L_2) \\
f_{10} + f_{01}\ell_1 = 0 & (L_3) \\
f_{10}\ell_1 + f_{01} = 0 & (L_4) \\
f_{00} = 0 &
\end{array}
\right.
$$

In order to have a non-trivial ladder $\ell(x) = \ell_1 x$,
we assume that $\ell_1 \neq \pm 1$. With $(L_4) - (L_3)$ we
obtain $(f_{10} - f_{01})(\ell_1 - 1) = 0$ thus $f_{10} = f_{01}$, and
with $(L_3)$ we have $f_{10}(\ell_1 + 1) = 0$, so $f_{10} = f_{01} = 0$.
With $(L_1) - (L_2)$ we obtain $(f_{02} - f_{20})(\ell_1^2 - 1) =
a - \ell_1$, so $f_{02} = f_{20} + \frac{a-\ell_1}{\ell_1^2-1}$. Therefore, remain the
following constraints:

$$
\left\{
\begin{array}{l}
f_{20}(\ell_1^2 + 1) + f_{11}\ell_1 = a - \ell_1^2 \frac{a - \ell_1}{\ell_1^2 - 1} = \ell_1 - \frac{a - \ell_1}{\ell_1^2 - 1} \\
\\
f_{02} = f_{20} + \frac{a - \ell_1}{\ell_1^2 - 1} \\
\\
f_{10} = f_{01} = f_{00} = 0
\end{array}
\right.
$$

The first equality is obtained from (L1) and the
second from (L2). Note that $a - \ell_1^2 \frac{a - \ell_1}{\ell_1^2 - 1} = \ell_1 - \frac{a - \ell_1}{\ell_1^2 - 1}$
is already satisfied and thus is not a constraint.
Moreover, because $\ell_1 \neq 0$, by using the second line,
we can rewrite $f_{11}$ as:

$$ 
\begin{aligned}
f_{11} &= \frac{1}{\ell_1} \left( \ell_1 - \frac{a - \ell_1}{\ell_1^2 - 1} - f_{20}(\ell_1^2 + 1) \right) \\
&= \frac{1}{\ell_1} \left( \frac{\ell_1^3 - a}{\ell_1^2 - 1} - f_{20}(\ell_1^2 + 1) \right)
\end{aligned}
$$

Thus, we have:

$$ 
\begin{aligned}
f(x, y) &= f_{20}x^2 + f_{11}xy + f_{02}y^2 \\
&= f_{20}x^2 + \frac{1}{\ell_1} \left( \frac{\ell_1^3 - a}{\ell_1^2 - 1} - f_{20}(\ell_1^2 + 1) \right) xy \\
&\quad + \left( f_{20} + \frac{a - \ell_1}{\ell_1^2 - 1} \right) y^2 \\
&= f_{20} \left( x^2 - \frac{\ell_1^2 + 1}{\ell_1} xy + y^2 \right) \\
&\quad + \frac{1}{\ell_1^2 - 1} \left( \frac{\ell_1^3 - a}{\ell_1} xy + (a - \ell_1)y^2 \right)
\end{aligned}
$$

Finally, $f_{20}$ has no constraint. It could have been used as a blinding integer for $f$, but unfortunately not for $g$. So, for the sake of simplicity and performance, we assume $f_{20} = 0$ and we obtain the following functions:

**Theorem 3.** The square-and-multiply Algorithm 2 for the modular exponentiation with $\theta(x) = ax^2$ and $\varepsilon(x) = x^2$ is fully-ladderizable with:

$$ 
\begin{aligned}
\ell(x) &= \ell_1 x \\
f(x, y) &= \frac{1}{\ell_1^2 - 1} \left( \frac{\ell_1^3 - a}{\ell_1} xy - (\ell_1 - a)y^2 \right) \\
g(x, y) &= \frac{1}{\ell_1^3 - a} (a(\ell_1^2 - 1)y^2 + \ell_1(\ell_1 - a)x)
\end{aligned}
$$

where ① $\ell_1 \neq a \bmod n$, ② $\ell_1 \in (\mathbb{Z}/n\mathbb{Z})^*$, ③ $\ell_1^2 - 1 \in (\mathbb{Z}/n\mathbb{Z})^*$, and ④ $\ell_1^3 - a \in (\mathbb{Z}/n\mathbb{Z})^*$, producing (after memoization of one squaring in $z$) Algorithm 14.

**Definition 7 (Ladder Constant).** We call ladder constant and denote by $\ell$ an integer satisfying constraints ①, ②, ③, and ④ from Theorem 3.

The first constraint ① on the ladder constant can be satisfied by checking whether $\ell - a = 0 \bmod n$. The other constraints can be satisfied by using the Extended Euclidean Algorithm ($d, u, u'$) $\leftarrow$ EEA($v, n$), where $uv + u'n = d$, and $d = \gcd(v, n)$. Indeed, we have $uv = d \bmod n$, such that if $d = 1$

then $v$ is invertible modulo $n$ and $v^{-1} = u \bmod n$. Because we ignore the last Bézout coefficient $u'$, for sake of simplicity we denote this function call ($d, u) \leftarrow$ EEA($v, n$) in Algorithm 14.

Because of ①, we have $\ell \neq a \bmod n$. Moreover, $0 \notin (\mathbb{Z}/n\mathbb{Z})^*$, so according to ②, we have $\ell \neq 0$. Finally, if $\ell = \pm 1$, then $\ell_1^2 - 1 \notin (\mathbb{Z}/n\mathbb{Z})^*$, so according to ③, we have $\ell \neq \pm 1$. Hence, we have that $\ell \in \mathbb{Z}/n\mathbb{Z}$ has to be chosen in $L_{a,n} = [2, n-2] \setminus \{a\}$ (Line 2).

Then, Algorithm 14 checks if $\ell$ satisfies the constraints of Theorem 3 (Line 9). After a suitable ladder constant $\ell$ is chosen, the coefficients of $f$ and $g$ only depend on $a$ and $\ell$, thus can be pre-computed (Lines 10–13).

These computations to find suitable constants may cause an overhead (Lines 1–15) but that does not depend on the secret thus, in theory, trading performance for security. Nevertheless, we prove in the RSA case (Subsection 5.5) and the DSA case (Subsection 5.6) that a ladder constant $\ell$ satisfying the constraints from Theorem 3 is almost always obtained after one iteration. So, in practice, such overhead is negligible compared to the operations performed for each bit of the secret key.

Finally, note that $\ell$ is randomly generated (Line 2) and affects the computation of intermediate values (Lines 19, 20, 23 and 24) depending on the secret key. Hence, as in our semi-interleaved solution (Subsection 5.2), $\ell$ is a blinding integer that reduces vulnerability against advanced side-channel attacks.

## 5.4 Complexity and Performance

We provide in Table 2 a comparison of complexities for the Montgomery, semi-, and fully-interleaved ladders. The complexities are given in terms of cost per key bit, where $M$ stands for multiplication, $S$ for squaring, $A$ for addition and subtraction, all modulo $n$, and $T$ for the thread creation cost. Because the costs are given per key bit, we did not include the cost of the pre-computations, which are negligible in the RSA and the DSA cases, as described at the end of Subsections 5.2 and 5.3.

The first line of Table 2 demonstrates a trade-off between security and performance. As opposed to the Montgomery ladder, our semi- (Theorem 2) and fully- (Theorem 3) interleaved solutions have a blinding integer reducing vulnerability to advanced
we can rewrite $f_{11}$ as:

$$ 
\begin{aligned}
f_{11} &= \frac{1}{\ell_1} \left( \ell_1 - \frac{a - \ell_1}{\ell_1^2 - 1} - f_{20}(\ell_1^2 + 1) \right) \\
&= \frac{1}{\ell_1} \left( \frac{\ell_1^3 - a}{\ell_1^2 - 1} - f_{20}(\ell_1^2 + 1) \right)
\end{aligned}
$$

Thus, we have:

$$ 
\begin{aligned}
f(x, y) &= f_{20}x^2 + f_{11}xy + f_{02}y^2 \\
&= f_{20}x^2 + \frac{1}{\ell_1} \left( \frac{\ell_1^3 - a}{\ell_1^2 - 1} - f_{20}(\ell_1^2 + 1) \right) xy \\
&\quad + \left( f_{20} + \frac{a - \ell_1}{\ell_1^2 - 1} \right) y^2 \\
&= f_{20} \left( x^2 - \frac{\ell_1^2 + 1}{\ell_1} xy + y^2 \right) \\
&\quad + \frac{1}{\ell_1^2 - 1} \left( \frac{\ell_1^3 - a}{\ell_1} xy + (a - \ell_1)y^2 \right)
\end{aligned}
$$

Finally, $f_{20}$ has no constraint. It could have been used as a blinding integer for $f$, but unfortunately not for $g$. So, for the sake of simplicity and performance, we assume $f_{20} = 0$ and we obtain the following functions:

**Theorem 3.** The square-and-multiply Algorithm 2 for the modular exponentiation with $\theta(x) = ax^2$ and $\varepsilon(x) = x^2$ is fully-ladderizable with:

$$ 
\begin{aligned}
\ell(x) &= \ell_1 x \\
f(x, y) &= \frac{1}{\ell_1^2 - 1} \left( \frac{\ell_1^3 - a}{\ell_1} xy - (\ell_1 - a)y^2 \right) \\
g(x, y) &= \frac{1}{\ell_1^3 - a} (a(\ell_1^2 - 1)y^2 + \ell_1(\ell_1 - a)x)
\end{aligned}
$$

where ① $\ell_1 \neq a \bmod n$, ② $\ell_1 \in (\mathbb{Z}/n\mathbb{Z})^*$, ③ $\ell_1^2 - 1 \in (\mathbb{Z}/n\mathbb{Z})^*$, and ④ $\ell_1^3 - a \in (\mathbb{Z}/n\mathbb{Z})^*$, producing (after memoization of one squaring in $z$) Algorithm 14.

**Definition 7 (Ladder Constant).** We call ladder constant and denote by $\ell$ an integer satisfying constraints ①, ②, ③, and ④ from Theorem 3.

The first constraint ① on the ladder constant can be satisfied by checking whether $\ell - a = 0 \bmod n$. The other constraints can be satisfied by using the Extended Euclidean Algorithm ($d, u, u'$) $\leftarrow$ EEA($v, n$), where $uv + u'n = d$, and $d = \gcd(v, n)$. Indeed, we have $uv = d \bmod n$, such that if $d = 1$

then $v$ is invertible modulo $n$ and $v^{-1} = u \bmod n$. Because we ignore the last Bézout coefficient $u'$, for sake of simplicity we denote this function call ($d, u) \leftarrow$ EEA($v, n$) in Algorithm 14.

Because of ①, we have $\ell \neq a \bmod n$. Moreover, $0 \notin (\mathbb{Z}/n\mathbb{Z})^*$, so according to ②, we have $\ell \neq 0$. Finally, if $\ell = \pm 1$, then $\ell_1^2 - 1 \notin (\mathbb{Z}/n\mathbb{Z})^*$, so according to ③, we have $\ell \neq \pm 1$. Hence, we have that $\ell \in \mathbb{Z}/n\mathbb{Z}$ has to be chosen in $L_{a,n} = [2, n-2] \setminus \{a\}$ (Line 2).

Then, Algorithm 14 checks if $\ell$ satisfies the constraints of Theorem 3 (Line 9). After a suitable ladder constant $\ell$ is chosen, the coefficients of $f$ and $g$ only depend on $a$ and $\ell$, thus can be pre-computed (Lines 10–13).

These computations to find suitable constants may cause an overhead (Lines 1–15) but that does not depend on the secret thus, in theory, trading performance for security. Nevertheless, we prove in the RSA case (Subsection 5.5) and the DSA case (Subsection 5.6) that a ladder constant $\ell$ satisfying the constraints from Theorem 3 is almost always obtained after one iteration. So, in practice, such overhead is negligible compared to the operations performed for each bit of the secret key.

Finally, note that $\ell$ is randomly generated (Line 2) and affects the computation of intermediate values (Lines 19, 20, 23 and 24) depending on the secret key. Hence, as in our semi-interleaved solution (Subsection 5.2), $\ell$ is a blinding integer that reduces vulnerability against advanced side-channel attacks.

## 5.4 Complexity and Performance

We provide in Table 2 a comparison of complexities for the Montgomery, semi-, and fully-interleaved ladders. The complexities are given in terms of cost per key bit, where $M$ stands for multiplication, $S$ for squaring, $A$ for addition and subtraction, all modulo $n$, and $T$ for the thread creation cost. Because the costs are given per key bit, we did not include the cost of the pre-computations, which are negligible in the RSA and the DSA cases, as described at the end of Subsections 5.2 and 5.3.

The first line of Table 2 demonstrates a trade-off between security and performance. As opposed to the Montgomery ladder, our semi- (Theorem 2) and fully- (Theorem 3) interleaved solutions have a blinding integer reducing vulnerability to advanced
<table><caption>Table 2: Cost per key bit (after memoization) of the Montgomery (Algorithm 3), semi- (Algorithm 13) and fully-interleaved ladders (Algorithm 14) for the modular exponentiation, where *M* stands for multiplication, *S* for squaring, *A* for addition/subtraction, and *T* for thread creation cost.</caption><thead><tr><th></th><th>Montgomery</th><th>Semi-Interleaved</th><th>Fully-Interleaved</th></tr></thead><tbody><tr><td>sequential (1 core)</td><td><i>M</i> + <i>S</i></td><td>3<i>M</i> + 2<i>S</i> + 2<i>A</i></td><td>5<i>M</i> + <i>S</i> + 2<i>A</i></td></tr><tr><td>parallel (2 cores)</td><td><i>M</i> + <i>S</i></td><td><i>M</i> + 2<i>S</i> + 2<i>A</i> + <i>T</i></td><td>3<i>M</i> + <i>S</i> + <i>A</i> + <i>T</i></td></tr><tr><td>parallel (3 cores)</td><td><i>M</i> + <i>S</i></td><td>2<i>M</i> + 2<i>A</i> + <i>T</i></td><td>2<i>M</i> + <i>S</i> + <i>A</i> + <i>T</i></td></tr></tbody></table>

side-channel attacks, but at the price of a factor 3 for the former and 5 for the latter, in terms of multiplications. Nevertheless, as illustrated in Table 1 p.14, our fully-interleaved solution provides more protection against fault-injection attacks than the Montgomery ladder or our semi-interleaved solution.

As introduced in the background (Subsection 2.5), we also consider parallel computations to evaluate performance. The second and third line of Table 2 provide a comparison when the algorithms run on a multi-core system, respectively with two and three cores. This does not change the cost for the Montgomery ladder (Algorithm 3) because the squaring must be computed after the multiplication. But this changes the cost for our solutions.

We now consider the *then* branch of our semi-interleaved ladder (Algorithm 13), both branches having the same complexity. We first consider two cores. $c_1(x^2+y^2)$ can be computed on the first core using two squarings, one addition, then one multiplication, i.e., $M+2S+A$. $c_2xy$ can be computed on the second core using two multiplications, i.e., $2M$. Since usually $S \approx 0.8M$, we have $M \le 2S+A$ and the maximal complexity between both cores is $M+2S+A$. Finally, the results are added together to obtain the value for $x$, obtaining a total complexity $M+2S+2A$, and the computed value $y^2$ is assigned to $y$. We now consider three cores. $c_1x^2$ can be computed on the first core in $M+S$, $c_1y^2$ can be computed on the second core in $M+S$, and $c_2xy$ can be computed on the third core in $2M$. Since $M \ge S$, the maximal complexity between the cores is $2M$. Then, the three results are summed together, for a total complexity of $2M+2A$. Note that, since usually $S \approx 0.8M$, the total complexity for two cores is larger than for three cores, as expected.

In the same way, we consider the *then* branch of the fully-interleaved ladder (Algorithm 14). We

first consider two cores. $c_0xy + c_1y^2$ can be computed on the first core in $3M + S + A$ to obtain the value for $x$. $c_2y^2+c_3x$ can be computed on the second core in $2M+S+A$ to obtain the value for $y$. Hence, the total complexity is $3M+S+A$. We now consider three cores. $c_0xy$ can be computed on the first core in $2M$, $c_1y^2$ can be computed on the second core in $M+S$, and $c_2y^2+c_3x$ can be computed on the third core in $2M+S+A$. The results of the first two cores are then added to obtain the value for $x$, for a total complexity of $2M + A$ for these cores. The third core for $y$ requires $2M + S + A$, hence the total complexity is $2M + S + A$.

These parallel computations do no change qualitatively the trade-offs between performance and security properties, but the price for the semi-interleaved ladder is now a factor 2 for the number of multiplications (instead of 3), and a factor 3 (instead of 5) for the fully-interleaved ladder. Hence, in that case, our solutions demonstrate performances closer to the Montgomery ladder.

In practice, performances are even closer than in theory. As a proof of concept, we implemented the Montgomery and semi-interleaved ladders using the GNU Multiple Precision (GMP) library [19]. To lower the non-negligible cost of memory management induced by this library, we used the provided low-level functions. We measured the number of cycles necessary to execute these algorithms for various key sizes on a single core. We also used the OpenMP API to measure the number of cycles for respectively 2 and 3 cores [42].

We provide a repository [34] to replicate the results, which was tested on a Intel® Core™ i9-11900KF @ 3.50GHz, gcc 11.3.0, Ubuntu 22.04. Each measured function was first executed 700 times (warm-up). Then, to lower the effect of background tasks running on the system, each iteration was repeated 700 times with the same inputs for the median value to be recorded.
<table><caption>Table 2: Cost per key bit (after memoization) of the Montgomery (Algorithm 3), semi- (Algorithm 13) and fully-interleaved ladders (Algorithm 14) for the modular exponentiation, where *M* stands for multiplication, *S* for squaring, *A* for addition/subtraction, and *T* for thread creation cost.</caption><thead><tr><th></th><th>Montgomery</th><th>Semi-Interleaved</th><th>Fully-Interleaved</th></tr></thead><tbody><tr><td>sequential (1 core)</td><td><i>M</i> + <i>S</i></td><td>3<i>M</i> + 2<i>S</i> + 2<i>A</i></td><td>5<i>M</i> + <i>S</i> + 2<i>A</i></td></tr><tr><td>parallel (2 cores)</td><td><i>M</i> + <i>S</i></td><td><i>M</i> + 2<i>S</i> + 2<i>A</i> + <i>T</i></td><td>3<i>M</i> + <i>S</i> + <i>A</i> + <i>T</i></td></tr><tr><td>parallel (3 cores)</td><td><i>M</i> + <i>S</i></td><td>2<i>M</i> + 2<i>A</i> + <i>T</i></td><td>2<i>M</i> + <i>S</i> + <i>A</i> + <i>T</i></td></tr></tbody></table>

side-channel attacks, but at the price of a factor 3 for the former and 5 for the latter, in terms of multiplications. Nevertheless, as illustrated in Table 1 p.14, our fully-interleaved solution provides more protection against fault-injection attacks than the Montgomery ladder or our semi-interleaved solution.

As introduced in the background (Subsection 2.5), we also consider parallel computations to evaluate performance. The second and third line of Table 2 provide a comparison when the algorithms run on a multi-core system, respectively with two and three cores. This does not change the cost for the Montgomery ladder (Algorithm 3) because the squaring must be computed after the multiplication. But this changes the cost for our solutions.

We now consider the *then* branch of our semi-interleaved ladder (Algorithm 13), both branches having the same complexity. We first consider two cores. $c_1(x^2+y^2)$ can be computed on the first core using two squarings, one addition, then one multiplication, i.e., $M+2S+A$. $c_2xy$ can be computed on the second core using two multiplications, i.e., $2M$. Since usually $S \approx 0.8M$, we have $M \le 2S+A$ and the maximal complexity between both cores is $M+2S+A$. Finally, the results are added together to obtain the value for $x$, obtaining a total complexity $M+2S+2A$, and the computed value $y^2$ is assigned to $y$. We now consider three cores. $c_1x^2$ can be computed on the first core in $M+S$, $c_1y^2$ can be computed on the second core in $M+S$, and $c_2xy$ can be computed on the third core in $2M$. Since $M \ge S$, the maximal complexity between the cores is $2M$. Then, the three results are summed together, for a total complexity of $2M+2A$. Note that, since usually $S \approx 0.8M$, the total complexity for two cores is larger than for three cores, as expected.

In the same way, we consider the *then* branch of the fully-interleaved ladder (Algorithm 14). We

first consider two cores. $c_0xy + c_1y^2$ can be computed on the first core in $3M + S + A$ to obtain the value for $x$. $c_2y^2 + c_3x$ can be computed on the second core in $2M + S + A$ to obtain the value for $y$. Hence, the total complexity is $3M + S + A$. We now consider three cores. $c_0xy$ can be computed on the first core in $2M$, $c_1y^2$ can be computed on the second core in $M+S$, and $c_2y^2 + c_3x$ can be computed on the third core in $2M + S + A$. The results of the first two cores are then added to obtain the value for $x$, for a total complexity of $2M + A$ for these cores. The third core for $y$ requires $2M + S + A$, hence the total complexity is $2M + S + A$.

These parallel computations do no change qualitatively the trade-offs between performance and security properties, but the price for the semi-interleaved ladder is now a factor 2 for the number of multiplications (instead of 3), and a factor 3 (instead of 5) for the fully-interleaved ladder. Hence, in that case, our solutions demonstrate performances closer to the Montgomery ladder.

In practice, performances are even closer than in theory. As a proof of concept, we implemented the Montgomery and semi-interleaved ladders using the GNU Multiple Precision (GMP) library [19]. To lower the non-negligible cost of memory management induced by this library, we used the provided low-level functions. We measured the number of cycles necessary to execute these algorithms for various key sizes on a single core. We also used the OpenMP API to measure the number of cycles for respectively 2 and 3 cores [42].

We provide a repository [34] to replicate the results, which was tested on a Intel® Core™ i9-11900KF @ 3.50GHz, gcc 11.3.0, Ubuntu 22.04. Each measured function was first executed 700 times (warm-up). Then, to lower the effect of background tasks running on the system, each iteration was repeated 700 times with the same inputs for the median value to be recorded.
**Algorithm 14** Fully-Interleaved Ladder for the Modular Exponentiation (General Case)

**input** public $a, n$; secret $k$
1: **do**
2:     $\ell \leftarrow \text{random}([2, n-2] \setminus \{a\})$
3:     $v_0 \leftarrow \ell - a \bmod n$
4:     $(d_1, u_1) \leftarrow \text{EEA}(\ell, n)$
5:     $v_2 \leftarrow \ell^2 - 1 \bmod n$
6:     $(d_2, u_2) \leftarrow \text{EEA}(v_2, n)$
7:     $v_3 \leftarrow \ell^3 - a \bmod n$
8:     $(d_3, u_3) \leftarrow \text{EEA}(v_3, n)$
9:     **while** $v_0 \bmod n = 0 \lor d_1 \neq 1 \lor d_2 \neq 1 \lor d_3 \neq 1$
10:    $c_0 \leftarrow u_1 u_2 v_3 \bmod n$
11:    $c_1 \leftarrow -v_0 u_2 \bmod n$
12:    $c_2 \leftarrow av_2 u_3 \bmod n$
13:    $c_3 \leftarrow \ell v_0 u_3 \bmod n$
14:    $x \leftarrow 1$
15:    $y \leftarrow \ell$
16:    **for** $i = d$ **to** 0 **do**
17:        **if** $k[i] = 1$ **then**
18:            $z \leftarrow y^2 \bmod n$
19:            $x \leftarrow c_0 x y + c_1 z \bmod n$
20:            $y \leftarrow c_2 z + c_3 x \bmod n$
21:        **else**
22:            $z \leftarrow x^2 \bmod n$
23:            $y \leftarrow c_0 y x + c_1 z \bmod n$
24:            $x \leftarrow c_2 z + c_3 y \bmod n$
25:        **end if**
26:    **end for**
27:    **return** $x$
**output** $x = a^k \bmod n$

The results are reported in Table 3. As the Montgomery ladder cannot be parallelized, we use the number of cycles obtained for this algorithm on a single core as a reference. Thus, we report the number of cycles for the semi-interleaved ladder as well as the ratio, i.e., this number divided by the number of cycles for the Montgomery ladder, for a relative comparison.

Dealing with parallelism increases the ratio for small key sizes (1024 and 2048). This is because thread creation has a fixed cost, which has a major impact on overall performance. This is compensated for larger key sizes, where the performed computations take precedence over the thread creation cost. For several cores and large key sizes, we obtain a ratio between 1.4 and 1.9, which is below

the ratio of 2 expected from the cost analysis. One of the reasons is the instructions per cycle (IPC) for the semi-interleaved ladder is larger than for the Montgomery ladder.

Therefore, the price for the more secure semi-interleaved ladder compared to the Montgomery ladder is lower in practice, up to 1.4 for several cores and large key sizes.

## 5.5 Fully-Interleaved Ladder Solution (RSA Case)

We prove in this subsection that in the RSA case a ladder constant $\ell$ satisfying the constraints from Theorem 3 can almost always be obtained in one iteration from Algorithm 14.

In the context of RSA [45], we assume that the modulus is a product $n = pq$, where $p, q$ are distinct primes. The modular exponentiation aims at computing $a^k \bmod n$, so we assume that the input $a$ is already given modulo $n$ i.e., $0 \le a \le n-1$. Because $0^k$ and $(\pm 1)^k$ are fairly trivial to compute, we assume that $a \ne 0, \pm 1$. So $2 \le a \le n-2$, thus $\text{card}(L_{a,n}) = n-4$ where $L_{a,n} = [2, n-2] \setminus \{a\}$, which simplifies the following reasoning.

We assume that $\ell$ is randomly chosen in $L_{a,n}$ and we compute the probability that $\ell$ satisfies the ladder constraints. To satisfy constraints (1) and (2) of Theorem 3, i.e., $\ell \ne a$ and $\ell \in (\mathbb{Z}/n\mathbb{Z})^*$, $\ell$ has to be chosen in $L_{a,n}$ such that $\text{gcd}(\ell, n) = 1$. The only integers in $L_{a,n}$ such that $\text{gcd}(\ell, n) > 1$ are $jp$ for $j \in [1, q-1]$ or $jq$ for $j \in [1, p-1]$, so the probability to randomly select a ladder constant not verifying (2) is:

$$ \Pr(\text{not } \textcircled{2}) \le \frac{(p-1) + (q-1)}{n-4} \approx \frac{1}{p} + \frac{1}{q} $$

In the RSA context, this means that a random $\ell \in L_{a,n}$ is invertible modulo $n$ with probability almost equal to 1. Indeed, according to the National Institute of Standards and Technology (NIST) recommendations [4], if $n\text{Bits} = \lfloor \log_2 n \rfloor + 1$ denotes the number of bits of $n = pq$, then $p$ and $q$ satisfy:

$$ 2^{\frac{n\text{Bits}-1}{2}} < p < 2^{\frac{n\text{Bits}}{2}} \\ 2^{\frac{n\text{Bits}-1}{2}} < q < 2^{\frac{n\text{Bits}}{2}} $$

so $\frac{1}{2^{\frac{n\text{Bits}-2}{2}}} < \frac{1}{p} + \frac{1}{q} < \frac{1}{2^{\frac{n\text{Bits}-3}{2}}}$, where $n\text{Bits}$ is assumed to be large.
<caption>**Algorithm 14** Fully-Interleaved Ladder for the Modular Exponentiation (General Case)</caption>

**input** public $a, n$; secret $k$
1: **do**
2:     $\ell \leftarrow \text{random}([2, n-2] \setminus \{a\})$
3:     $v_0 \leftarrow \ell - a \bmod n$
4:     $(d_1, u_1) \leftarrow \text{EEA}(\ell, n)$
5:     $v_2 \leftarrow \ell^2 - 1 \bmod n$
6:     $(d_2, u_2) \leftarrow \text{EEA}(v_2, n)$
7:     $v_3 \leftarrow \ell^3 - a \bmod n$
8:     $(d_3, u_3) \leftarrow \text{EEA}(v_3, n)$
9:     **while** $v_0 \bmod n = 0 \lor d_1 \neq 1 \lor d_2 \neq 1 \lor d_3 \neq 1$
10:    $c_0 \leftarrow u_1 u_2 v_3 \bmod n$
11:    $c_1 \leftarrow -v_0 u_2 \bmod n$
12:    $c_2 \leftarrow av_2 u_3 \bmod n$
13:    $c_3 \leftarrow \ell v_0 u_3 \bmod n$
14:    $x \leftarrow 1$
15:    $y \leftarrow \ell$
16:    **for** $i = d$ **to** 0 **do**
17:        **if** $k[i] = 1$ **then**
18:            $z \leftarrow y^2 \bmod n$
19:            $x \leftarrow c_0 x y + c_1 z \bmod n$
20:            $y \leftarrow c_2 z + c_3 x \bmod n$
21:        **else**
22:            $z \leftarrow x^2 \bmod n$
23:            $y \leftarrow c_0 y x + c_1 z \bmod n$
24:            $x \leftarrow c_2 z + c_3 y \bmod n$
25:        **end if**
26:    **end for**
27:    **return** $x$
**output** $x = a^k \bmod n$

The results are reported in Table 3. As the Montgomery ladder cannot be parallelized, we use the number of cycles obtained for this algorithm on a single core as a reference. Thus, we report the number of cycles for the semi-interleaved ladder as well as the ratio, i.e., this number divided by the number of cycles for the Montgomery ladder, for a relative comparison.

Dealing with parallelism increases the ratio for small key sizes (1024 and 2048). This is because thread creation has a fixed cost, which has a major impact on overall performance. This is compensated for larger key sizes, where the performed computations take precedence over the thread creation cost. For several cores and large key sizes, we obtain a ratio between 1.4 and 1.9, which is below

the ratio of 2 expected from the cost analysis. One of the reasons is the instructions per cycle (IPC) for the semi-interleaved ladder is larger than for the Montgomery ladder.

Therefore, the price for the more secure semi-interleaved ladder compared to the Montgomery ladder is lower in practice, up to 1.4 for several cores and large key sizes.

## 5.5 Fully-Interleaved Ladder Solution (RSA Case)

We prove in this subsection that in the RSA case a ladder constant $\ell$ satisfying the constraints from Theorem 3 can almost always be obtained in one iteration from Algorithm 14.

In the context of RSA [45], we assume that the modulus is a product $n = pq$, where $p, q$ are distinct primes. The modular exponentiation aims at computing $a^k \bmod n$, so we assume that the input $a$ is already given modulo $n$ i.e., $0 \le a \le n-1$. Because $0^k$ and $(\pm 1)^k$ are fairly trivial to compute, we assume that $a \ne 0, \pm 1$. So $2 \le a \le n-2$, thus $\text{card}(L_{a,n}) = n-4$ where $L_{a,n} = [2, n-2] \setminus \{a\}$, which simplifies the following reasoning.

We assume that $\ell$ is randomly chosen in $L_{a,n}$ and we compute the probability that $\ell$ satisfies the ladder constraints. To satisfy constraints (1) and (2) of Theorem 3, i.e., $\ell \ne a$ and $\ell \in (\mathbb{Z}/n\mathbb{Z})^*$, $\ell$ has to be chosen in $L_{a,n}$ such that $\text{gcd}(\ell, n) = 1$. The only integers in $L_{a,n}$ such that $\text{gcd}(\ell, n) > 1$ are $jp$ for $j \in [1, q-1]$ or $jq$ for $j \in [1, p-1]$, so the probability to randomly select a ladder constant not verifying (2) is:

$$ \Pr(\text{not } \textcircled{2}) \le \frac{(p-1) + (q-1)}{n-4} \approx \frac{1}{p} + \frac{1}{q} $$

In the RSA context, this means that a random $\ell \in L_{a,n}$ is invertible modulo $n$ with probability almost equal to 1. Indeed, according to the National Institute of Standards and Technology (NIST) recommendations [4], if $n\text{Bits} = \lfloor \log_2 n \rfloor + 1$ denotes the number of bits of $n = pq$, then $p$ and $q$ satisfy:

$$ \begin{aligned} 2^{\frac{n\text{Bits}-1}{2}} &< p < 2^{\frac{n\text{Bits}}{2}} \\ 2^{\frac{n\text{Bits}-1}{2}} &< q < 2^{\frac{n\text{Bits}}{2}} \end{aligned} $$

so $\frac{1}{2^{\frac{n\text{Bits}-2}{2}}} < \frac{1}{p} + \frac{1}{q} < \frac{1}{2^{\frac{n\text{Bits}-3}{2}}}$, where $n\text{Bits}$ is assumed to be large.
<table><caption>Table 3: Performance comparison between the Montgomery ladder and the semi-interleaved ladder for the modular exponentiation</caption><thead><tr><th rowspan="3">Key size<br>(bits)</th><th colspan="4">Number of cycles (ratio compared to Montgomery)</th></tr><tr><th rowspan="2">Montgomery</th><th colspan="3">Semi-Interleaved</th></tr><tr><th>1 core</th><th>2 cores</th><th>3 cores</th></tr></thead><tbody><tr><td>1 024</td><td>3 324 108</td><td>7 549 860 (2.27)</td><td>11 144 772 (3.35)</td><td>9 430 042 (2.84)</td></tr><tr><td>2 048</td><td>21 047 774</td><td>48 250 646 (2.29)</td><td>49 601 524 (2.36)</td><td>39 992 556 (1.90)</td></tr><tr><td>4 096</td><td>130 630 682</td><td>290 334 462 (2.22)</td><td>248 868 716 (1.90)</td><td>206 804 182 (1.58)</td></tr><tr><td>8 192</td><td>811 361 402</td><td>1 755 290 126 (2.16)</td><td>1 393 469 694 (1.71)</td><td>1 173 139 582 (1.44)</td></tr><tr><td>16 384</td><td>4 971 382 772</td><td>10 437 469 318 (2.10)</td><td>8 181 204 906 (1.65)</td><td>6 979 736 808 (1.40)</td></tr></tbody></table>

Moreover, note that if one can compute $\ell$ such that $\gcd(\ell, n) > 1$, then $\gcd(\ell, n) = p$ or $q$, thus one is able to factorize $n$. The same problem occurs in RSA cryptosystem: if Bob can generate a message $m$ such that $\gcd(m, n) > 1$, where $n$ is Alice's public key, then Bob can factorize $n$ and find Alice's private key. Such an event could occur but with a probability nearly equal to 0.

To satisfy constraint ③ of Theorem 3 i.e., $\ell^2 - 1 \in (\mathbb{Z}/n\mathbb{Z})^*$, note that, according to the Chinese remainder theorem, integers $\ell$ such that $\ell^2 - 1$ are not invertible modulo $n$ verify $\ell^2 = 1 \pmod p$ and $\ell^2 = 1 \pmod q$. There are at most four such integers: $1, n-1, \gamma, n-\gamma$, where $\gamma = 1 \pmod p$ and $\gamma = -1 \pmod q$. $1$ and $n-1$ are excluded, so the probability to randomly select a ladder constant in $L_{a,n} = [2, n-2]$ not verifying ③ is:

$$Pr(\text{not } \textcircled{3}) \leq \frac{2}{n-4}$$

Finally, to determine integers such that the last constraint ④ of Theorem 3, i.e., $\ell^3 - a \in (\mathbb{Z}/n\mathbb{Z})^*$, is satisfied, we use the following lemma from Gauss:

**Definition 8 (r<sup>th</sup> Residues).** Let $n$ and $r \ge 2$ be two integers. An integer $a \in (\mathbb{Z}/n\mathbb{Z})^*$ is a $r^{th}$ residue modulo $n$ if there exists an integer $\ell \in \mathbb{Z}/n\mathbb{Z}$ such that $\ell^r = a \pmod n$, otherwise it is a non-residue modulo $n$.

**Lemma 1 (Gauss [17]).** Let $p$ be a prime and $r \ge 2$ be an integer. We denote $b = \gcd(p-1, r)$ and we have:

1. For every integer $a \in (\mathbb{Z}/p\mathbb{Z})^*$, $a$ is a $r^{th}$ residue modulo $p$ if and only if $a^{\frac{p-1}{p}} = 1 \pmod p$,

2. there exists exactly $\frac{p-1}{p}$ $r^{th}$ residues in $(\mathbb{Z}/p\mathbb{Z})^*$,

3. if $a \in (\mathbb{Z}/p\mathbb{Z})^*$ is a $r^{th}$ residue modulo $p$, then there exists exactly $b$ integers $\ell \in \mathbb{Z}/p\mathbb{Z}$ such that $\ell^r = a \pmod p$.

According to the Chinese remainder theorem, $\ell^3 - a$ is invertible modulo $n = pq$ if and only if $\ell^3 - a$ is invertible modulo $p$ and $\ell^3 - a$ is invertible modulo $q$. Moreover, because $p$ is prime, $\ell^3 - a$ is invertible mod $p$ if and only if $\ell^3 - a \neq 0 \pmod p$, i.e., $a$ is a $3^{rd}$ non-residue modulo $p$. Therefore, constraint ④ is not satisfied only if $a$ is a $3^{rd}$ residue modulo $p$ or $q$.

For an input $a$ fixed, because $b_p = \gcd(p-1, 3) = 1$ or $3$ and $b_q = \gcd(q-1, 3) = 1$ or $3$, according to Lemma 1, there are at most 9 non invertible $\ell^3 - a$ integers modulo $n$, so the probability to randomly select a ladder constant in $L_{a,n}$ not verifying ④ is:

$$Pr(\text{not } \textcircled{4}) \leq \frac{9}{n-4}$$

At worst, the unfavorable cases are distinct, thus the probability to randomly select a suitable ladder constant is:

$$ \begin{aligned} Pr(\textcircled{1}\textcircled{2}\textcircled{3}\textcircled{4}) &\ge 1 - \left( \frac{p-1+q-1}{n-4} + \frac{2}{n-4} + \frac{9}{n-4} \right) \\ &= 1 - \frac{p+q+9}{n-4} \approx 1 - \frac{1}{p} - \frac{1}{q} - \frac{1}{n} \end{aligned} $$

which is almost equal to 1 in a cryptographic context. Thus, in the RSA case $n = pq$, finding a suitable ladder constant (Lines 1–9) in Algorithm 14 costs only one iteration with probability almost equal to 1. Therefore, the overhead to pre-compute a suitable ladder constant in Algorithm 14 is not costly in practice.

## 5.6 Fully-Interleaved Ladder Solution (DSA Case)

We prove in this subsection that in the DSA case a ladder constant $\ell$ satisfying the constraints from
<table><caption>Table 3: Performance comparison between the Montgomery ladder and the semi-interleaved ladder for the modular exponentiation</caption><thead><tr><th rowspan="3">Key size<br>(bits)</th><th colspan="4">Number of cycles (ratio compared to Montgomery)</th></tr><tr><th rowspan="2">Montgomery</th><th colspan="3">Semi-Interleaved</th></tr><tr><th>1 core</th><th>2 cores</th><th>3 cores</th></tr></thead><tbody><tr><td>1 024</td><td>3 324 108</td><td>7 549 860 (2.27)</td><td>11 144 772 (3.35)</td><td>9 430 042 (2.84)</td></tr><tr><td>2 048</td><td>21 047 774</td><td>48 250 646 (2.29)</td><td>49 601 524 (2.36)</td><td>39 992 556 (1.90)</td></tr><tr><td>4 096</td><td>130 630 682</td><td>290 334 462 (2.22)</td><td>248 868 716 (1.90)</td><td>206 804 182 (1.58)</td></tr><tr><td>8 192</td><td>811 361 402</td><td>1 755 290 126 (2.16)</td><td>1 393 469 694 (1.71)</td><td>1 173 139 582 (1.44)</td></tr><tr><td>16 384</td><td>4 971 382 772</td><td>10 437 469 318 (2.10)</td><td>8 181 204 906 (1.65)</td><td>6 979 736 808 (1.40)</td></tr></tbody></table>

Moreover, note that if one can compute $\ell$ such that $\gcd(\ell, n) > 1$, then $\gcd(\ell, n) = p$ or $q$, thus one is able to factorize $n$. The same problem occurs in RSA cryptosystem: if Bob can generate a message $m$ such that $\gcd(m, n) > 1$, where $n$ is Alice's public key, then Bob can factorize $n$ and find Alice's private key. Such an event could occur but with a probability nearly equal to 0.

To satisfy constraint ③ of Theorem 3 i.e., $\ell^2 - 1 \in (\mathbb{Z}/n\mathbb{Z})^*$, note that, according to the Chinese remainder theorem, integers $\ell$ such that $\ell^2 - 1$ are not invertible modulo $n$ verify $\ell^2 = 1 \pmod p$ and $\ell^2 = 1 \pmod q$. There are at most four such integers: $1, n-1, \gamma, n-\gamma$, where $\gamma = 1 \pmod p$ and $\gamma = -1 \pmod q$. $1$ and $n-1$ are excluded, so the probability to randomly select a ladder constant in $L_{a,n} = [2, n-2]$ not verifying ③ is:

$$Pr(\text{not } ③) \le \frac{2}{n-4}$$

Finally, to determine integers such that the last constraint ④ of Theorem 3, i.e., $\ell^3 - a \in (\mathbb{Z}/n\mathbb{Z})^*$, is satisfied, we use the following lemma from Gauss:

**Definition 8 (r<sup>th</sup> Residues).** Let $n$ and $r \ge 2$ be two integers. An integer $a \in (\mathbb{Z}/n\mathbb{Z})^*$ is a $r^{th}$ residue modulo $n$ if there exists an integer $\ell \in \mathbb{Z}/n\mathbb{Z}$ such that $\ell^r = a \pmod n$, otherwise it is a non-residue modulo $n$.

**Lemma 1 (Gauss [17]).** Let $p$ be a prime and $r \ge 2$ be an integer. We denote $b = \gcd(p-1, r)$ and we have:

1. For every integer $a \in (\mathbb{Z}/p\mathbb{Z})^*$, $a$ is a $r^{th}$ residue modulo $p$ if and only if $a^{\frac{p-1}{b}} = 1 \pmod p$,

2. there exists exactly $\frac{p-1}{b}$ $r^{th}$ residues in $(\mathbb{Z}/p\mathbb{Z})^*$,

3. if $a \in (\mathbb{Z}/p\mathbb{Z})^*$ is a $r^{th}$ residue modulo $p$, then there exists exactly $b$ integers $\ell \in \mathbb{Z}/p\mathbb{Z}$ such that $\ell^r = a \pmod p$.

According to the Chinese remainder theorem, $\ell^3 - a$ is invertible modulo $n = pq$ if and only if $\ell^3 - a$ is invertible modulo $p$ and $\ell^3 - a$ is invertible modulo $q$. Moreover, because $p$ is prime, $\ell^3 - a$ is invertible mod $p$ if and only if $\ell^3 - a \ne 0 \pmod p$, i.e., $a$ is a $3^{rd}$ non-residue modulo $p$. Therefore, constraint ④ is not satisfied only if $a$ is a $3^{rd}$ residue modulo $p$ or $q$.

For an input $a$ fixed, because $b_p = \gcd(p-1, 3) = 1$ or $3$ and $b_q = \gcd(q-1, 3) = 1$ or $3$, according to Lemma 1, there are at most 9 non invertible $\ell^3 - a$ integers modulo $n$, so the probability to randomly select a ladder constant in $L_{a,n}$ not verifying ④ is:

$$Pr(\text{not } ④) \le \frac{9}{n-4}$$

At worst, the unfavorable cases are distinct, thus the probability to randomly select a suitable ladder constant is:

$$ \begin{aligned} Pr(①②③④) &\ge 1 - \left( \frac{p-1+q-1}{n-4} + \frac{2}{n-4} + \frac{9}{n-4} \right) \\ &= 1 - \frac{p+q+9}{n-4} \approx 1 - \frac{1}{p} - \frac{1}{q} - \frac{1}{n} \end{aligned} $$

which is almost equal to 1 in a cryptographic context. Thus, in the RSA case $n = pq$, finding a suitable ladder constant (Lines 1–9) in Algorithm 14 costs only one iteration with probability almost equal to 1. Therefore, the overhead to pre-compute a suitable ladder constant in Algorithm 14 is not costly in practice.

## 5.6 Fully-Interleaved Ladder Solution (DSA Case)

We prove in this subsection that in the DSA case a ladder constant $\ell$ satisfying the constraints from
Theorem 3 can almost always be obtained in one iteration from Algorithm 14. In a Digital Signature Algorithm (DSA) [40] context (or for Diffie-Hellman key-exchange mechanism [44]), the exponentiation is computed modulo $n = p$, where $p$ is prime.

The argument is similar to the previous one in Subsection 5.5 for the RSA case, but even simpler. If $\ell \in L_{a,n} = [2, n-2] \setminus \{a\}$ then $\ell \neq a$. Moreover $\ell \neq 0 \pmod n$ so $\ell$ is invertible modulo $n$. Finally, $\ell \neq \pm 1$ so $\ell^2 - 1 \neq 0 \pmod n$ thus $\ell^2 - 1$ is invertible modulo $n$. So the first three constraints are always satisfied for $n = p$, where $p$ is prime.

Remains the last constraint $\mathbf{④} \ell^3 - a$ is invertible modulo $n$. In the following, we denote $R_n^3(a)$ that $a$ is a cubic residue modulo $n$, and let $b = \text{pgcd}(n-1, 3)$. To compute the probability of satisfying the fourth constraint, we use the formula of total probability $\text{Pr}(\mathbf{④}) = \text{Pr}(\mathbf{④} | R_n^3(a)) \times \text{Pr}(R_n^3(a)) + \text{Pr}(\mathbf{④} | \text{not } R_n^3(a)) \times \text{Pr}(\text{not } R_n^3(a))$.

According to Lemma 1, there exists $\frac{n-1}{b}$ cubic residue in $(\mathbb{Z}/n\mathbb{Z})^*$. The excluded values $-1$ and $1$ are cubic residue modulo $n$, as opposed to $0$. So, the probability that an integer $a \in [2, n-2]$ is a cubic residue is:

$$ \text{Pr}(R_n^3(a)) = \frac{\frac{n-1}{b} - 2}{n-3} = \frac{1}{b} - \frac{2(1 - \frac{1}{b})}{n-3} $$

According to Lemma 1, if $a$ is a cubic residue, then there exists $b$ cubic roots $\ell$ of $a$ in $(\mathbb{Z}/n\mathbb{Z})^*$. If $\ell = 0$ or $\pm 1$ then $a = \ell^3 = 0$ or $\pm 1$, which is excluded. If $\ell = a$ then $a = a^3$ i.e., $a(a+1)(a-1) = 0 \pmod p$, thus $a = 0, \pm 1$, which is also excluded. So, cubic roots $\ell$ of $a$ are automatically in $L_{a,n} = [2, n-2] \setminus \{a\}$. Thus, the probability that an integer $\ell \in L_{a,n}$ is a cubic root of $a$ is $\frac{b}{n-4}$. Therefore, if $a$ is a cubic residue then the probability that $\ell \in L_{a,n}$ satisfies the last constraint is:

$$ \text{Pr}(\mathbf{④} | R_n^3(a)) = 1 - \frac{b}{n-4} $$

Moreover, if $a$ is not a cubic residue, then there exists no $\ell$ such that $a = \ell^3 \pmod n$. So, every $\ell \in L_{a,n}$ satisfies $a - \ell^3 \neq 0 \pmod n = p$, where $p$ is prime. Thus, in that case, every $\ell \in L_{a,n}$ satisfies the last constraint $\mathbf{④}$, i.e., $\ell^3 - a$ is invertible modulo $n$. Therefore, $\text{Pr}(\mathbf{④} | \text{not } R_n^3(a)) = 1$.

Finally, the probability to randomly select a suit-

able ladder constant is:

$$ \begin{aligned} & \text{Pr}(\mathbf{①②③④}) \\ &= \text{Pr}(\mathbf{④}) \\ &= \text{Pr}(\mathbf{④} | R_n^3(a)) \times \text{Pr}(R_n^3(a)) \\ & \quad + \text{Pr}(\mathbf{④} | \text{not } R_n^3(a)) \times \text{Pr}(\text{not } R_n^3(a)) \\ &= \left(1 - \frac{b}{n-4}\right) \left(\frac{1}{b} - \frac{2(1-\frac{1}{b})}{n-3}\right) \\ & \quad + 1 \left(1 - \frac{1}{b} + \frac{2(1-\frac{1}{b})}{n-3}\right) \\ &= 1 - \frac{1}{n-4} + \frac{2(b-1)}{(n-3)(n-4)} \end{aligned} $$

which is almost equal to $1$ in a cryptographic context. Therefore, again, the overhead to pre-compute a suitable ladder constant in Algorithm 14 is not costly in practice.

## 5.7 Results for the Modular Exponentiation

In this section, we provided concrete answers to **RQ1** by solving the ladder equations for cryptosystems using the modular exponentiation. We obtained Algorithm 13 for the semi-interleaved case and Algorithm 14 for the fully-interleaved case.

Both Algorithms 13 and 14 use a blinding integer, providing more protection against side-channel attacks than the Montgomery ladder, for instance against advanced power attacks like CPA [10]. This protection naturally arose from a free parameter while solving the ladder equations, demonstrating the fruitfulness of the ladderization approach (**RQ2**). Moreover, as detailed in Subsection 4.3, Algorithm 14 is more secure against fault-injection attacks than the Montgomery ladder. So, the security properties of the Montgomery ladder have not only been generalized, but improved in both cases.

We compared in Subsection 5.4 the complexity of these novel algorithms with the complexity of the Montgomery ladder, demonstrating a trade-off between security and performance: Algorithm 13 is more secure than the Montgomery ladder but less performant, and Algorithm 14 is even more secure but even less performant, even if these novel algorithms have performance closer to the Montgomery ladder if the computations can be parallelized. For instance, we demonstrated for the semi-interleaved ladder that in practice, for several cores and large key sizes, the cost is only 40% larger.

Finally, Algorithm 14 requires a ladder constant (Definition 7), which raised a challenge regarding
Theorem 3 can almost always be obtained in one iteration from Algorithm 14. In a Digital Signature Algorithm (DSA) [40] context (or for Diffie-Hellman key-exchange mechanism [44]), the exponentiation is computed modulo $n = p$, where $p$ is prime.

The argument is similar to the previous one in Subsection 5.5 for the RSA case, but even simpler. If $\ell \in L_{a,n} = [2, n-2] \setminus \{a\}$ then $\ell \neq a$. Moreover $\ell \neq 0 \pmod n$ so $\ell$ is invertible modulo $n$. Finally, $\ell \neq \pm 1$ so $\ell^2 - 1 \neq 0 \pmod n$ thus $\ell^2 - 1$ is invertible modulo $n$. So the first three constraints are always satisfied for $n = p$, where $p$ is prime.

Remains the last constraint $\mathbf{④} \ \ell^3 - a$ is invertible modulo $n$. In the following, we denote $R_n^3(a)$ that $a$ is a cubic residue modulo $n$, and let $b = \text{pgcd}(n-1, 3)$. To compute the probability of satisfying the fourth constraint, we use the formula of total probability $\text{Pr}(\mathbf{④}) = \text{Pr}(\mathbf{④} | R_n^3(a)) \times \text{Pr}(R_n^3(a)) + \text{Pr}(\mathbf{④} | \text{not } R_n^3(a)) \times \text{Pr}(\text{not } R_n^3(a))$.

According to Lemma 1, there exists $\frac{n-1}{b}$ cubic residue in $(\mathbb{Z}/n\mathbb{Z})^*$. The excluded values $-1$ and $1$ are cubic residue modulo $n$, as opposed to $0$. So, the probability that an integer $a \in [2, n-2]$ is a cubic residue is:

$$ \text{Pr}(R_n^3(a)) = \frac{\frac{n-1}{b} - 2}{n-3} = \frac{1}{b} - \frac{2(1 - \frac{1}{b})}{n-3} $$

According to Lemma 1, if $a$ is a cubic residue, then there exists $b$ cubic roots $\ell$ of $a$ in $(\mathbb{Z}/n\mathbb{Z})^*$. If $\ell = 0$ or $\pm 1$ then $a = \ell^3 = 0$ or $\pm 1$, which is excluded. If $\ell = a$ then $a = a^3$ i.e., $a(a+1)(a-1) = 0 \pmod p$, thus $a = 0, \pm 1$, which is also excluded. So, cubic roots $\ell$ of $a$ are automatically in $L_{a,n} = [2, n-2] \setminus \{a\}$. Thus, the probability that an integer $\ell \in L_{a,n}$ is a cubic root of $a$ is $\frac{b}{n-4}$. Therefore, if $a$ is a cubic residue then the probability that $\ell \in L_{a,n}$ satisfies the last constraint is:

$$ \text{Pr}(\mathbf{④} | R_n^3(a)) = 1 - \frac{b}{n-4} $$

Moreover, if $a$ is not a cubic residue, then there exists no $\ell$ such that $a = \ell^3 \pmod n$. So, every $\ell \in L_{a,n}$ satisfies $a - \ell^3 \neq 0 \pmod n = p$, where $p$ is prime. Thus, in that case, every $\ell \in L_{a,n}$ satisfies the last constraint $\mathbf{④}$, i.e., $\ell^3 - a$ is invertible modulo $n$. Therefore, $\text{Pr}(\mathbf{④} | \text{not } R_n^3(a)) = 1$.

Finally, the probability to randomly select a suit-

able ladder constant is:

$$ \begin{aligned} & \text{Pr}(\mathbf{①②③④}) \\ &= \text{Pr}(\mathbf{④}) \\ &= \text{Pr}(\mathbf{④} | R_n^3(a)) \times \text{Pr}(R_n^3(a)) \\ & \quad + \text{Pr}(\mathbf{④} | \text{not } R_n^3(a)) \times \text{Pr}(\text{not } R_n^3(a)) \\ &= \left(1 - \frac{b}{n-4}\right) \left(\frac{1}{b} - \frac{2(1-\frac{1}{b})}{n-3}\right) \\ & \quad + 1 \left(1 - \frac{1}{b} + \frac{2(1-\frac{1}{b})}{n-3}\right) \\ &= 1 - \frac{1}{n-4} + \frac{2(b-1)}{(n-3)(n-4)} \end{aligned} $$

which is almost equal to $1$ in a cryptographic context. Therefore, again, the overhead to pre-compute a suitable ladder constant in Algorithm 14 is not costly in practice.

## 5.7 Results for the Modular Exponentiation

In this section, we provided concrete answers to **RQ1** by solving the ladder equations for cryptosystems using the modular exponentiation. We obtained Algorithm 13 for the semi-interleaved case and Algorithm 14 for the fully-interleaved case.

Both Algorithms 13 and 14 use a blinding integer, providing more protection against side-channel attacks than the Montgomery ladder, for instance against advanced power attacks like CPA [10]. This protection naturally arose from a free parameter while solving the ladder equations, demonstrating the fruitfulness of the ladderization approach (**RQ2**). Moreover, as detailed in Subsection 4.3, Algorithm 14 is more secure against fault-injection attacks than the Montgomery ladder. So, the security properties of the Montgomery ladder have not only been generalized, but improved in both cases.

We compared in Subsection 5.4 the complexity of these novel algorithms with the complexity of the Montgomery ladder, demonstrating a trade-off between security and performance: Algorithm 13 is more secure than the Montgomery ladder but less performant, and Algorithm 14 is even more secure but even less performant, even if these novel algorithms have performance closer to the Montgomery ladder if the computations can be parallelized. For instance, we demonstrated for the semi-interleaved ladder that in practice, for several cores and large key sizes, the cost is only 40% larger.

Finally, Algorithm 14 requires a ladder constant (Definition 7), which raised a challenge regarding
performance (RQ3). We tackled this challenge by proving, in the case of the RSA [45] (Subsection 5.5) and DSA [40] (Subsection 5.6) cryptosystems, that this ladder constant can be obtained at a negligible cost with probability almost equal to 1.

# 6 Generalizing the Montgomery Ladder for the Scalar Multiplication in ECC

As detailed in Subsection 2.4, the main operation in elliptic-curve cryptography (ECC) is the scalar multiplication $kA = A + \dots + A$, where A is a point on a curve and k is an integer. Following the double-and-add Algorithm 4 p.7, for a given point A we consider in this section the following known functions:

$$ 
\begin{aligned}
\theta(P) &= 2P + A \\
\varepsilon(P) &= 2P
\end{aligned}
 $$

Moreover, we consider ladder functions (Section 3) of the following form:

$$ 
\begin{aligned}
f(P,Q) &= f_{P}P + f_{Q}Q + f_{A}A \\
g(P,Q) &= g_{P}P + g_{Q}Q + g_{A}A \\
\ell(P) &= \ell_{P}P + \ell_{A}A
\end{aligned}
 $$

with $f_P, f_Q, \ell_P \neq 0$ for both cases, and $g_P, g_Q \neq 0$ for the fully-interleaved ladders case. Using scalar multiplications to compute scalar multiplications may seem circular, but we distinguish between non-secure and secure scalar multiplications. So, in the following, we assume that non-secure scalar multiplications (on public scalars $f_P, f_Q, f_A, g_P, g_Q, g_A, \ell_P$, and $\ell_A$) can be used to compute secure scalar multiplications (on sensitive scalars $k$).

As in Section 5, we provide concrete solutions to the ladder equations. In this section, we generalize the algorithmic strength of the Montgomery ladder by solving (Subsections 6.1 to 6.3) the ladder equations for the scalar multiplication used in ECC. We discuss in Subsection 6.4 the feasibility and performance of the novel solutions in the context of ECC. Then, in Subsection 6.5, we compare the complexity of the novel algorithms with the complexity of the Montgomery ladder. Results are summarized in Subsection 6.6.

## 6.1 Both Semi- and Fully-Interleaved Ladders

We start by solving the ladder equations which are common to the semi- and fully-interleaved cases. Equation (1b) (resp. Equation (2b)) $f(x, \ell(x)) = \theta(x)$ and Equation (1c) (resp. Equation (2c)) $f(\ell(x), x) = \ell(\varepsilon(x))$ for the semi- (resp. fully-) interleaved cases imply that:

$$ 
\begin{cases}
f_P + f_Q \ell_P = 2 \\
f_Q = (2 - f_P) \ell_P
\end{cases}
 $$

So $(2 - f_P)(\ell_P^2 - 1) = 0$. If $f_P = 2$, then $f_Q = 0$, so we assume $f_P \neq 2$. To make no assumption about the finite field, we assume for the following $\ell_P = \pm 1$. The equations also imply that:

$$ 
\begin{cases}
f_Q \ell_A + f_A = 1 \\
f_A = (2 - f_P) \ell_A - \ell_A
\end{cases}
 $$

So $(2 - f_P)(\ell_P + 1)\ell_A = 1 + \ell_A$.

* If $\ell_P = -1$ then $\ell_A = -1$, $f_Q = f_P - 2$ and $f_A = (f_P - 2) + 1$, thus the candidate ladder functions are:

$$ 
\begin{aligned}
f(P,Q) &= f_P(P + Q + A) - (2Q + A) \\
\ell(P) &= -(P + A)
\end{aligned}
 $$

* If $\ell_P = 1$, then by assuming that $3 - 2f_P$ is invertible we obtain $\ell_A = \frac{1}{3-2f_P}$, $f_Q = 2 - f_P$ and $f_A = 1 - \frac{2-f_P}{3-2f_P}$, thus the candidate ladder functions are:

$$ 
\begin{aligned}
f(P,Q) &= f_P(P - Q) + 2Q + \frac{1 - f_P}{3 - 2f_P}A \\
\ell(P) &= P + \frac{1}{3 - 2f_P}A
\end{aligned}
 $$

## 6.2 Semi-Interleaved Ladder Solution

In this subsection we solve the ladder equations for the semi-interleaved case. The remaining Equation (1a) $\varepsilon(\ell(x)) = \ell(\theta(x))$ for the semi-interleaved ladders is already satisfied for the $\ell_P = -1$ case. For the $\ell_P = 1$ case, it implies that $(\frac{1}{3-2f_P} - 1)A = O$, thus to avoid constraint on A we assume $f_P = 1$.

**Theorem 4.** The double-and-add algorithm with $\theta(P) = 2P + A$ and $\varepsilon(P) = 2P$ is semi-ladderizable with two solutions:
performance (RQ3). We tackled this challenge by proving, in the case of the RSA [45] (Subsection 5.5) and DSA [40] (Subsection 5.6) cryptosystems, that this ladder constant can be obtained at a negligible cost with probability almost equal to 1.

# 6 Generalizing the Montgomery Ladder for the Scalar Multiplication in ECC

As detailed in Subsection 2.4, the main operation in elliptic-curve cryptography (ECC) is the scalar multiplication $kA = A + \dots + A$, where A is a point on a curve and k is an integer. Following the double-and-add Algorithm 4 p.7, for a given point A we consider in this section the following known functions:

$$ 
\begin{aligned}
\theta(P) &= 2P + A \\
\varepsilon(P) &= 2P
\end{aligned}
 $$

Moreover, we consider ladder functions (Section 3) of the following form:

$$ 
\begin{aligned}
f(P,Q) &= f_{P}P + f_{Q}Q + f_{A}A \\
g(P,Q) &= g_{P}P + g_{Q}Q + g_{A}A \\
\ell(P) &= \ell_{P}P + \ell_{A}A
\end{aligned}
 $$

with $f_P, f_Q, \ell_P \neq 0$ for both cases, and $g_P, g_Q \neq 0$ for the fully-interleaved ladders case. Using scalar multiplications to compute scalar multiplications may seem circular, but we distinguish between non-secure and secure scalar multiplications. So, in the following, we assume that non-secure scalar multiplications (on public scalars $f_P, f_Q, f_A, g_P, g_Q, g_A, \ell_P$, and $\ell_A$) can be used to compute secure scalar multiplications (on sensitive scalars $k$).

As in Section 5, we provide concrete solutions to the ladder equations. In this section, we generalize the algorithmic strength of the Montgomery ladder by solving (Subsections 6.1 to 6.3) the ladder equations for the scalar multiplication used in ECC. We discuss in Subsection 6.4 the feasibility and performance of the novel solutions in the context of ECC. Then, in Subsection 6.5, we compare the complexity of the novel algorithms with the complexity of the Montgomery ladder. Results are summarized in Subsection 6.6.

## 6.1 Both Semi- and Fully-Interleaved Ladders

We start by solving the ladder equations which are common to the semi- and fully-interleaved cases. Equation (1b) (resp. Equation (2b)) $f(x, \ell(x)) = \theta(x)$ and Equation (1c) (resp. Equation (2c)) $f(\ell(x), x) = \ell(\varepsilon(x))$ for the semi- (resp. fully-) interleaved cases imply that:

$$ 
\begin{cases}
f_P + f_Q \ell_P = 2 \\
f_Q = (2 - f_P) \ell_P
\end{cases}
 $$

So $(2 - f_P)(\ell_P^2 - 1) = 0$. If $f_P = 2$, then $f_Q = 0$, so we assume $f_P \neq 2$. To make no assumption about the finite field, we assume for the following $\ell_P = \pm 1$. The equations also imply that:

$$ 
\begin{cases}
f_Q \ell_A + f_A = 1 \\
f_A = (2 - f_P) \ell_A - \ell_A
\end{cases}
 $$

So $(2 - f_P)(\ell_P + 1)\ell_A = 1 + \ell_A$.

* If $\ell_P = -1$ then $\ell_A = -1$, $f_Q = f_P - 2$ and $f_A = (f_P - 2) + 1$, thus the candidate ladder functions are:

$$ 
\begin{aligned}
f(P,Q) &= f_P(P + Q + A) - (2Q + A) \\
\ell(P) &= -(P + A)
\end{aligned}
 $$

* If $\ell_P = 1$, then by assuming that $3 - 2f_P$ is invertible we obtain $\ell_A = \frac{1}{3-2f_P}$, $f_Q = 2 - f_P$ and $f_A = 1 - \frac{2-f_P}{3-2f_P}$, thus the candidate ladder functions are:

$$ 
\begin{aligned}
f(P,Q) &= f_P(P - Q) + 2Q + \frac{1 - f_P}{3 - 2f_P}A \\
\ell(P) &= P + \frac{1}{3 - 2f_P}A
\end{aligned}
 $$

## 6.2 Semi-Interleaved Ladder Solution

In this subsection we solve the ladder equations for the semi-interleaved case. The remaining Equation (1a) $\varepsilon(\ell(x)) = \ell(\theta(x))$ for the semi-interleaved ladders is already satisfied for the $\ell_P = -1$ case. For the $\ell_P = 1$ case, it implies that $(\frac{1}{3-2f_P} - 1)A = O$, thus to avoid constraint on A we assume $f_P = 1$.

**Theorem 4.** The double-and-add algorithm with $\theta(P) = 2P + A$ and $\varepsilon(P) = 2P$ is semi-ladderizable with two solutions: