Cryptography Reference
In-Depth Information
>ct:=
"04e05cec539418485e6e97bb4b1e521d39a470c2fc482998b5b18ceb32e747bd407efda65207d3ce0\
bf70cc2355252880648217e52f3c08d4f67acc8d21021841cfddbdc996b628e7e4c8c042038835ad\
c89b4a04386613fd2fdd6178ab898a0c0f4e9df2b74f1bdd43e18ca7b3a77a436e5b42ab154c8ceb\
2ec2569ad722ccc695b5c2e3d412b627a2b32695df841d8203789c57ab4b851c2f3008d6ee2fe597\
638b77430d901edb9d0d15f1f0477cb5317eafa7f57bc11b061a4f7454e7c3eebc14fbd74097765b\
3a5b24d47f95bb5547ee7de44a95c75fe17903738fd1a41bac00635819ee3c1a658c15d328f293a0\
287448b2db4d8077fdeeb2f4e0caa45"
Eve observes the ciphertext and would like to recover the plaintext. She knows
(or she merely suspects) that the message contains Alice's answer to a question
posed by Bob and that this answer is either "Yes" or "No". So she encrypts these two
messages with Bob's public key and compares the results to the ciphertext
ct
:
> evalb(RSAEncrypt(pk, "Yes") = ct);
false
> evalb(RSAEncrypt(pk, "No") = ct);
true
This immediately reveals that the plaintext is indeed "No".
It might seem that in the preceding example the adversary breaks the one-wayness
of plain RSA but it is really not so, and this does not contradict the fact that the
scheme is OW-CPA secure under the RSA assumption. Indeed, this concept of secu-
rity requires that it is hard for the adversary to decrypt a ciphertext corresponding
to a plaintext which is randomly chosen in
Z
n
(where
n
is the RSA modulus) but
in the example the plaintexts are supposed to belong to a small subset of
Z
n
so this
condition is not satisfied. This attack can be extended to larger plaintext spaces pro-
vided that computing the ciphertexts corresponding to these plaintexts is feasible.
In fact, there is a meet-in-the-middle attack, described in [37], which is much more
efficient than a brute-force search. This attack relies on the multiplicative property
of RSA which essentially says that the product of the ciphertexts corresponding to
two messages in
Z
n
is the ciphertext corresponding to the product of these messages
or, in other words, that the RSA function is a group homomorphism (actually an
isomorphism) from
Z
n
into itself (
homomorphic
encryption schemes, for which the
decryption function is a homomorphism as is the case here, are studied in more detail
in Sect.
8.8
). The attack may be sketched as follows. Suppose that
m
∈ Z
n
is an
-bit
m
e
mod
n
is the corresponding ciphertext. Suppose, further, that
m
can be factored into two
=
plaintext and
c
/
2-bit factors
u
,
v
(which occurs with good probability in
case
m
is randomly chosen). We may even assume that these factors are in
Z
n
because
otherwise we would have gcd
1 which is
easily detectable and, in fact, allows the factorization of
n
. Then the following holds:
(
m
,
n
)
=
1 and hence also that gcd
(
c
,
n
)
=
m
e
mod
n
e
mod
n
u
e
v
e
mod
n
c
=
=
(
uv
)
=
.
Thus the algorithm tries to find
u
and
v
(and hence
m
) as follows. A table containing
all the pairs
r
e
mod
n
Z
n
, is constructed
(
r
,
)
, where
r
is an
/
2-bit integer belonging to
2-bit integer
s
,
cs
−
e
mod
n
is computed and searched among the second components of elements in the table.
When
s
and sorted by the second component. Then, for each
/
=
v
we have that:
cv
−
e
mod
n
u
e
v
e
v
−
e
mod
n
u
e
mod
n
=
=
,
