Cryptography Reference
In-Depth Information
For a naïve implementation of this operation, we may write
m
d
mod
N
=
m
·
m
·
...
·
m
mod
N
.
d times
The computational complexity of the algorithm above is exponential with respect
to the exponent length, which is not acceptable for implementing a modular expo-
nentiation. However, a method as intuitive as the previous one, but much smarter,
consists in expressing the exponent in a binary basis:
d
=
n
−
1
i
2
i
d
i
. Then, we
can perform a modular exponentiation by scanning the bits of the exponent:
·
=
0
n
−
1
m
2
i
d
i
m
d
mod
N
=
mod
N
.
(7.1)
i
=
0
As a consequence, the power is no longer performed by multiplying
d
times a mes-
sage
m
by itself but by multiplying, at most log
2
(
times, square powers of
m
.
Hence the cost of the exponentiation methods derived from this principle, also called
binary exponentiation, is linear with respect to the exponent length, which is much
more efficient than the naïve approach. The next section briefly introduces common
implementations of binary exponentiations
d
)
7.2.2.1 “Right-to-Left” Exponentiation
The first method to perform a modular exponentiation is to scan the exponent bits
from the least to the most significant ones. That is why it is also referred as the
“right-to-left” method. In practice, this method is the most intuitive since it consists
of computing consecutive square powers of the input message and, depending on the
current exponent bit value, multiplying these powers to the accumulation register.
As a consequence, this algorithm exactly transcribes (
7.1
). The complete algorithm
is detailed below.
Algorithm 7.1
: “Right-to-left” modular exponentiation
Input
:
m
=
n
−
1
i
2
i
,
d
·
d
i
,
N
=
0
m
d
mod
N
Output
:
S
=
A
←
1;
1
←
B
m
;
2
=
−
for
i
0
to
n
1
do
3
if
d
i
=
1
then
4
A
←
A
·
B
mod
N
;
5
end
6
B
2
mod
N
;
←
B
7
end
8
return
A
9
