Cryptography Reference
In-Depth Information
a plaintext message. This question can be answered in the affirmative. In fact, it
has been shown that all plaintext message bits are protected by the RSA function
in the sense that having a nontrivial advantage for predicting a single message bit
would enable an adversary to invert the RSA function entirely. This result about
the bit security of the RSA asymmetric encryption system can be proven by a
reduction technique. More specifically, one must show that an efficient algorithm
for solving the RSAP can be constructed from an algorithm for predicting one
(or more) plaintext message bit(s). Note, however, that the bit-security proof of
the RSA asymmetric encryption system is a double-edged sword, because the
security reduction used in the proof also provides a possibility to attack a “leaky”
implementation. In fact, if an implementation of the RSA
Decrypt
algorithm leaked
some bits of a plaintext message, then this leakage could be (mis)used to solve the
RSAP and to decrypt a ciphertext without knowing the private key.
Specific Attacks
Several attacks are known and must be considered with care when it comes to an
implementation of the RSA asymmetric encryption system. In addition to the attacks
mentioned next, there is always the risk of having side-channel attacks against a
specific implementation. Refer to Section 1.2.2 for a corresponding overview and
discussion. Side-channel attacks are not further addressed in this topic.
Common modulus attacks:
To avoid generating a different modulus
n
=
pq
for
every user, it is tempting to work with a common modulus
n
for all (or at least
several) users. In this case, a trusted authority must generate the public key pairs and
provide user
i
with a public key (
n, e
i
) and a corresponding private key (
n, d
i
).At
first sight, this seems to work, because a ciphertext
c
m
e
i
(mod
n
) encrypted for
user
i
cannot be decrypted by user
j
(as user
j
does not know the private exponent
d
i
). Unfortunately, this argument is incorrect, and the use of a common modulus is
completely insecure. There are common modulus attacks that can be mounted from
both an insider and an outsider:
≡
•
Remember from the previous discussion that knowing the private key
d
j
is
computationally equivalent to knowing the prime factors of
n
(or knowing
φ
(
n
), respectively). Consequently, insider
j
can use
d
j
to factorize
n
,andthe
prime factors of
n
can then be used to efficiently compute
d
i
from
e
i
.
•
Even more worrisome, an outsider can also mount a common modulus attack
against a message
m
that is encrypted with the public keys of two users having
the same modulus
n
.Let(
n, e
1
) be the public key of the first user and (
n, e
2
)
be the public key of the second user. The message
m
is then encrypted as
