Cryptography Reference
In-Depth Information
arithmetic on elliptic curves one can choose an
x
-coordinate corresponding to a point that
lies on the quadratic twist. Further discussion is given in Section 4.3 of [
248
] and a summary
of the history of these results is given in Section 4.7 of [
248
]. We stress that such attacks do
not only arise in encryption, but also in authenticated key exchange protocols, undeniable
signatures, etc. The general way to avoid such attacks is for all parties to test membership
of group elements in every step of the protocol (see Section
11.6
).
Exercise 20.4.6
Show how a CCA1 attacker on classic textbook Elgamal can compute
u
a
for a group element
u
of their choice where
a
is the private key of a user. Show that if this
attack can be repeated for sufficiently many elements
u
of coprime small orders then the
private key
a
can be computed.
20.4.3 Semantic security under passive attacks
A serious problem with the classic textbook Elgamal cryptosystem is that, even though
encryption is randomised, it does not necessarily provide semantic security under passive
attacks.
= F
p
,
M
Example 20.4.7
Consider the case
G
=
G
.Let
g
∈
G
have prime order
r
. Then
the Legendre symbol of
g
is (
g
p
)
=
1. Hence, the Legendre symbol of the message
m
satisfies
m
p
c
2
p
=
and so can be computed in polynomial-time from the public key and the ciphertext.
To prevent the attack in Example
20.4.7
one can restrict the message space to elements
F
p
with Legendre symbol 1. However, this attack is just a special case of a more
general phenomenon. The Legendre symbol is a homomorphism
of
F
p
→
G
1
where
G
1
=
}⊆F
p
is the subgroup of order 2. The attack can be performed for any homomor-
phism onto a subgroup of order coprime to
r
(this is a slightly different application of the
ideas of Section
13.2
).
{−
1
,
1
Example 20.4.8
(Boneh, Joux and Nguyen [
77
]) Let
p
be a 3072-bit prime and let
r
|
∈ F
p
have order
r
. Suppose, in violation of the description
of classic textbook Elgamal in Section
20.3
, one chooses the message space to be
(
p
−
1) be a 256-bit prime. Let
g
1
,
2
,...,
2
32
M
={
−
1
}
F
p
. We identify
M
with
interpreted as a subset of
{
0
,
1
}
32
−{
0
}
.Let(
c
1
=
g
k
,
c
2
=
m
h
k
)
be a challenge ciphertext for classic textbook Elgamal encryption, where
m
∈
M
. Then
c
r
2
=
m
r
.
One expects that, with overwhelming probability, the 2
32
values
m
r
are distinct, and hence
one can obtain
m
with at most 2
32
F
p
.
exponentiations in
