Cryptography Reference
In-Depth Information
m
=
m
1
m
2
without knowing it. More interestingly, consider the situation in which
an adversary wants to decrypt
c
m
e
≡
(mod
n
) with a chosen-ciphertext attack.
He or she therefore computes
c
≡
cr
e
(mod
n
),has
c
(which is different from
c
)
be decrypted by the decryption oracle, and deduces
m
from
rm
(mod
n
) returned
by the decryption oracle (by a modular division). The multiplicative structure of the
RSA function is even more worrisome when the RSA DSS is used. Consequently,
good practices in security engineering must take care of the multiplicative structure
of the RSA function and protect against corresponding exploits. One possibility is
to require plaintext messages to have a certain (nonmultiplicative) structure. This
means that the product of two valid plaintext messages no longer yields a valid
plaintext message. Another possibility is to randomly pad the plaintext message
prior to encryption. This randomizes the ciphertext and eliminates the homomorphic
property accordingly. Again, we revisit this possibility in Section 14.3.2 when we
elaborate on OAEP.
Low exponent attacks:
To improve the performance of the RSA asymmetric
encryption system, one may consider the use of small (public or private) exponents.
The line of argumentation goes as follows: if one employed a small public exponent
e
, then the encryption (or signature verification) process would be fast, and if one
employed a small private exponent
d
, then the decryption (or signature generation)
would be fast. Unfortunately, this line of argumentation must be considered with
care, and there are a couple of low exponent attacks that are possible.
On one hand, Michael Wiener showed in 1990 that the choice of a small private
exponent
d
can lead to a total break of the RSA asymmetric encryption system [9].
This result was later improved by various authors (e.g., [10]). Given the current state
of the art, the private exponent
d
should be at least 300 bits long for a typical 1,024-
bit RSA modulus
n
. In practice, people frequently use a public exponent
e
that is
3, 17, or 2
16
+1=65
,
537. In these cases, it is guaranteed that the corresponding
private exponent
d
is nearly as long as
n
and hence that the attacks that exploit small
private exponents do not work.
On the other hand, it was already mentioned earlier that using small public
exponents (e.g.,
e
=3or
e
=17) may lead to the problem that the RSAP eventually
becomes simpler to solve than the IFP [8]. Consequently, one may not want to
work with public exponents that are too small. Furthermore, there is a very specific
problem if one uses a small public exponent
e
to encrypt a small message
m
. In fact,
if
m<
e
√
n
,then
c
=
m
e
, and hence
m
can be decrypted as follows (note that there
is no modular arithmetic involved in this computation):
m
=
e
√
c
