Cryptography Reference
In-Depth Information
ˆ
the 'infix operator' &
. As was to be expected, this function is very fast and we will use
it extensively in the sequel as a component of many of the algorithms implemented.
Example 2.15
Let us consider again the exponentiationwe tried to compute inExam-
ple 2.14. Now we see that any of the variants of the binary method is able to carry
out this computation quickly:
> 21293&ˆ4589764534197876275671393839 mod 298483279246566637216195857103;
ModExp(21293, 4589764534197876275671393839, 298483279246566637216195857103);
RecModExp(21293, 4589764534197876275671393839, 298483279246566637216195857103);
ExpMod(21293, 4589764534197876275671393839, 298483279246566637216195857103);
157396720784600298623131794157
157396720784600298623131794157
157396720784600298623131794157
157396720784600298623131794157
2.7.2.1 Speeding up Modular Exponentiation with the Chinese
Remainder Theorem
As we shall see, modular exponentiation is the basic operation one has to perform
when doing RSA encryption or decryption. In the case of decryption, the modulus
is a product of two known large primes and the speed of the binary exponentiation
algorithm can be significantly increased. Indeed, given a modulus whose prime fac-
torization is known, one can apply the Chinese remainder theorem to recover the final
result from the smaller exponentiations corresponding to the different prime-power
factors of the modulus. We next describe how to do this in Maple when the modulus
is—as in the RSA case—a product of two different primes.
Suppose that we want to compute
x
m
e
mod
n
, where
n
=
=
pq
, with
p
and
q
distinct primes not dividing
m
.Let
x
p
=
x
mod
p
and
x
q
=
x
mod
q
. Then
m
e
mod
n
n
)
m
e
mod
p
we have that
x
p
=
(
)
mod
p
=
(since
p
|
=
(by Corollary
2.3)
m
e
mod
p
−
1
mod
p
and, similarly,
x
q
m
e
mod
q
−
1
mod
q
. Thus
m
e
mod
q
=
=
m
e
mod
n
is the unique solution
the Chinese remainder theorem implies that
x
=
modulo
n
of the system of congruences:
x
≡
x
p
(
mod
p
)
(2.5)
x
≡
x
q
(
mod
q
)
3
3
bit operations
respectively. If we assume that
p
and
q
have approximately the same length, we
will have len
The computations of
x
p
and
x
q
require
O
(
len
(
p
)
)
and
O
(
len
(
q
)
)
1
and hence each of these two computations
requires approximately one-eight of the time required by the direct computation of
x
(
p
)
≈
len
(
q
)
≈
2
len
(
n
)
m
e
mod
n
in time
O
3
. Thus the time taken by the computations of
x
p
and
x
q
will be approximately one-fourth of the time required by computing
x
directly. Since the time taken to apply the CRT is
O
=
(
len
(
n
)
)
2
, which is faster, we
see that the use of the CRT makes the process almost four times faster when
n
is
large (in other words, the computation that uses the CRT will require time roughly
(
len
(
n
)
)
