Cryptography Reference
In-Depth Information
f
d
mod
n
r
e
c
d
mod
n
rc
d
mod
n
=
=
(
)
=
=
,
x
rm
mod
n
r
−
1
x
mod
n
. She computes
so that she can recover the plaintext
m
by computing
m
=
it and converts it to the extended ASCII alphabet:
> convert(convert(x/r mod n, base, 256), bytes);
"Eve will not be able to decrypt this message"
Eve finally recovers the plaintext!
Note that the fictional scenario in the preceding example faithfully models a
CCA attack because the adversary is entitled to query the decryption oracle about
any ciphertext distinct from the challenge ciphertext such as with the ciphertext
f
which is indeed distinct from
c
. The property that was exploited in this attack is
the
malleability
of plain RSA. Roughly speaking, an encryption scheme is called
non-
malleable
if, given a ciphertext, it is infeasible for an adversary to produce a distinct
valid ciphertext for a related plaintext. In particular, a homomorphic encryption
scheme such as plain RSA is always malleable because if
Enc
c
, then
it is always possible to pick an arbitrary plaintext
a
and construct the ciphertext
Enc
(
pk
,
m
)
=
m
, related to the
(unknown) plaintext
m
by multiplication with
a
. While it is intuitively clear that a
malleable schemewill always be vulnerable to aCCAattackwe remark, however, that
malleability does not always imply that the full plaintext is recoverable under such
an attack as in the previous example. Non-malleability requires, for example, that it
should be infeasible to produce a ciphertext which corresponds to a plaintext which
changes, say, a number contained in the original plaintext
m
, even if the adversary is
not able to learn
m
. Thus non-malleability is a strong security property which is not
a necessary condition for a public-key encryption scheme to be IND-CPA secure. In
fact, for these schemes, non-malleability under chosen ciphertext attacks is equivalent
to being IND-CCA secure (see [87, Proposition 5.4.34, Proposition 5.4.35] and also
[14] for a detailed discussion of the relations among security properties). As we have
seen, the adversary goal, OW, IND or NM (non-malleability), can be combined with
the adversary capability (either CPA or CCA) and the relations between the security
properties we have mentioned are summarized in the following diagram, in which
an arrow means implication and an equality sign equivalence:
(
pk
,
a
)
·
c
which is also the result of encrypting the plaintext
a
·
NM-CCA
IND-CCA
−−−−→
OW-CCA
⏐
⏐
⏐
NM-CPA
−−−−→
IND-CPA
−−−−→
OW-CPA
The previous discussion on the security of plain RSA can be summarized as
follows:
Plain RSA is OW-CPA secure but is neither IND-CPA nor OW-CCA secure
.
We next describe some attacks against plain RSA allowed by poor choices of some
of the involved parameters and we stress that these attacks, even if they can be pre-
vented by amore sensible parameter choice, showagain the inadequacy of plainRSA.
