Cryptography Reference
In-Depth Information
u
e
mod
n
(
,
)
which will be in the table as the second component of the pair
u
.
Thus we know that in our search we will find
r
and
s
such that
cs
−
e
mod
n
=
r
e
mod
n
and hence
c
r
e
s
e
mod
n
. Once we find these elements, the RSA
function corresponding to decryption, which is also an isomorphism of
=
Z
n
, tells us
that
m
=
rs
mod
n
=
rs
(so that these
r
and
s
are the factors
u
,
v
we were searching
for).
This attack, similarly to the birthday attacks we have seen for hash functions,
reduces the number of encryptions to be performed to about the square root of the
number required by a pure brute-force attack. In [37] it is shown that it is possible
to recover an
2
/
2
encryption operations (i.e., modular expo-
nentiations) with a success probability of 18%, which is certainly non-negligible.
Since RSA is often used to encrypt symmetric session keys which may be 128-bit
strings, recovering such a message would require about 2
65
modular exponentiations
and seems feasible with appropriate resources.
Both Example 8.5 and the attack just sketched offer compelling evidence that
OW-CPA is not an adequate notion of security. Another reason why OW-CPA is
very weak is because to break it the full plaintext must be recovered, so it allows
partial information about the plaintext to be leaked without having to assume extra
hypotheses such as a small message space. In other words, OW-CPA security does
not imply semantic security. This can be appreciated, for example, by considering
the Jacobi symbol and noticing that, since the RSA encryption exponent is odd, if
m
is a message and
c
-bit message using 2
·
m
e
mod
n
the corresponding ciphertext, then
n
=
n
.
Since, by Exercise 2.43, half of the elements of
=
Z
n
have Jacobi symbol 1 and the
other half have Jacobi symbol -1, the knowledge of its Jacobi symbol gives about 1
bit of information about the plaintext (see, for example, [90,7.2.3] for an example
of Lipton in which this feature was exploited to break an RSA-based protocol for
'mental poker').
The fact that plain RSA is not semantically secure also follows, in a more indirect
way, from plain RSA having deterministic encryption. As we have already noted, a
deterministic encryption scheme is not IND-CPA secure and, on the other hand, the
latter property is equivalent to semantic security under chosen plaintext attacks (see
[87, Theorem 5.4.11] for a proof).
8.3.4.3 Plain RSA is Not OW-CCA Secure
Since OW-CPA security is insufficient, let us analyze the possibility that plain RSA
satisfies a stronger security property. One way to strengthen OW-CPA is by replacing
the adversary goal, namely one-wayness, by a weaker goal like indistinguishability.
This leads to IND-CPA but, as we have just remarked, plain RSA does not have this
property. Another natural way to strengthen OW-CPA is by strengthening the adver-
sary capabilities and replacing CPA by CCA to obtain what we can call OW-CCA
(one-way security against (adaptive) chosen ciphertext attacks). But it is easy to show
that plain RSA is not OW-CCA secure either, as the following example shows.
