Cryptography Reference
In-Depth Information
7.2.2.2 “Left-to-Right” Exponentiation
It is also possible to scan the exponent bits from the most to the least significant
bits. The associated method is not surprisingly called “left-to-right” exponentiation.
This method differs from the dual one by an accumulation register withdrawal and a
different execution flow. Indeed, each iteration begins with the execution of a square
that can be followed, depending on the current exponent bit value, by a multiplication.
This method is detailed in Algorithm 7.2.
Algorithm 7.2
: “Left-to-right” modular exponentiation
Input
:
m
=
n
−
1
i
2
i
,
d
·
d
i
,
N
=
0
m
d
mod
N
Output
:
S
=
A
←
1;
1
for
i
=
(
n
−
1
)
to
0
do
2
A
2
mod
N
if
d
i
A
←
=
1
then
3
A
←
A
·
m
mod
N
;
4
end
5
end
6
return
A
7
7.2.2.3 Other Variants
Although both the previously presented algorithms are quite efficient methods of
computing a modular exponentiation, their implementation may leak information
on the exponent. Indeed, the execution of a multiplication directly depends on the
current value of the exponent bits. This makes smart card implementations of modular
exponentiation algorithms potentially vulnerable to side-channel attacks, such as
DPA (see Sect.
1.3
). A basic solution to thwarting this flaw is to make the execution
independent of the exponent value. Such a variant was proposed by Coron [102] and
is known as the Square and Multiply Always algorithm. In this case, one square and
one multiplication are sequentially executed at each iteration, whatever the value the
current exponent bit may take.
The performance of the exponentiation algorithms can also be improved. For
example, we can derive from the previous algorithms the Sliding Window Expo-
nentiation used in the OpenSSL library. The principle of this variant is to scan the
exponent by, at most,
k
-bit windows. Hence, after precomputing some odd powers
of the input message
m
, this method significantly reduces the number of iterations
for a modular exponentiation, and so the performance.
Finally, some variants allow one to improve both security and performance. For
example, this is the case with the Montgomery exponentiation algorithm [294]. Obvi-
ously, there are other efficient implementations of modular exponentiation, but we
advise an interested reader to take a look at [234] for more details.
