Cryptography Reference
In-Depth Information
multiplications because 2
16
+
1 is a 17-bit number in which only the most significant
and the least significant bits are nonzero (see the discussion done when analyzing
the binary exponentiation method and its complexity). Finally, although 2
16
+
1is
Z
φ(
n
)
small in comparison with a typical element of
when
n
is chosen, say, in the
2048-4096-bit range, it is sufficiently large to make the attack against 'plain RSA
with small exponent' very unlikely to be successful in practice. We insist, however,
that the more secure variants of RSA—the only ones that should be used in real
applications—are not vulnerable to this small exponent attack.
There are no more choices in the RSA key generation algorithm assuming, as
we did, that
d
e
−
1
∈ Z
φ(
n
)
, because then the decryption exponent
d
is uniquely
determined by
n
and
e
(and, similarly, in the variant in which
d
=
e
−
1
∈ Z
λ(
n
)
). An
alternative possibility is first to choose the decryption exponent
d
and then to find
e
as
the inverse of
d
in
=
Z
φ(
n
)
but this is not very popular because it will usually produce a
large encryption exponent
e
. This allows the selection of a small decryption exponent
but, as we shall see in Sect.
8.3.4
, there is also an attack against the one-wayness of
RSA that allows the efficient recovery of
d
when the decryption exponent is small
(actually, it need not be too small, it suffices that it be roughly
n
1
/
4
). This attack is
much stronger than the one against a small encryption exponent, which only works
against plain RSA. The attack against small
d
achieves recovery of the private key
from the public key and hence breaks RSA in all its variants.
These considerations preclude the choice of a small decryption exponent but, for-
tunately, this feature is not as crucial from a performance point of view as having a
small encryption exponent because, as we are going to see, decryption can be accel-
erated (to approximately one-fourth of the time taken by the modular exponentiation
with exponent
d
) by using the Chinese remainder theorem. On the other hand, if
the encryption exponent is chosen first, then the probability that the resulting key
is vulnerable to the 'small decryption exponent attack' is very small (because the
exponents
<
n
1
/
4
are just a tiny fraction of all possible exponents) and, moreover, it
is easy to check whether
d
is small if one so wishes.
<
8.3.2.2 Decrypting with the Chinese Remainder Theorem
The Chinese remainder theorem can be used to speed up RSA decryption as follows.
Suppose that
(
,
)
=
n
d
is the private key, with
n
pq
, where
p
and
q
are primes. Then
we know that if
c
∈ Z
n
is the ciphertext corresponding to a plaintext
m
∈ Z
n
,the
decryption algorithm acts as follows:
c
d
mod
n
m
=
Dec
((
n
,
d
),
c
)
=
.
For convenience, let
d
p
=
d
mod
(
p
−
1
)
,
d
q
=
d
mod
(
q
−
1
)
,
m
p
=
m
mod
p
and
m
q
=
m
mod
q
. Then we have:
c
d
mod
n
c
d
mod
p
c
d
p
mod
p
m
p
=
(
)
mod
p
=
=
,
