Cryptography Reference
In-Depth Information
in which
G
is an elliptic curve cyclic group generated by a point
P
and we leave as
an exercise to formulate it explicitly.
Exercise 11.24
Describe the Elgamal elliptic encryption scheme.
Exercise 11.25
In a paper circulating on the Internet, the authors implement an
EC-based encryption scheme similar to Elgamal but, in their implementation, the
'double-and-add' method is not used for scalar multiplication and, instead, they
compute
kP
by adding
P
to itself
k
1 times. Explain the reasons why such a
scheme does not satisfy Definition 8.2 and, moreover, is completely insecure.
−
In the elliptic curve version of Elgamal, each ciphertext consists of a pair of points
of an elliptic curve. Since the message string has to be previously embedded in the
x
-
coordinate of a point, we see that this scheme has a 4-to-1 message expansion, which
is an undesirable feature. There is a simple procedure that allows the representation
of a point on an elliptic curve over
F
q
by using only len
(
q
)
+
1 bits instead of the
usual 2len
(
q
)
bits required by using len
(
q
)
bits for each coordinate. If theWeierstrass
equation of the curve is
y
2
x
3
=
+
ax
+
b
, then the
y
-coordinate corresponding to
∈ F
q
is one of the two square roots of
x
3
an
x
-coordinate
x
F
q
and
hence the
x
-coordinate determines the
y
coordinate up to the sign. Thus instead of
transmitting a point
+
ax
+
b
in
, it is sufficient to transmit
x
together with one additional
bit that determines which of the two square roots corresponds to the point. With this
technique, known as
point compression
, each point is represented by len
(
x
,
y
)
1 bits
and hence the message expansion of plain Elgamal is reduced from 4-to-1 to 2-to-1.
An alternative to using point compression is to transmit only the
x
-coordinate
of a point
P
, without any additional information. The receiver would not know
whether the point
P
or the point
(
q
)
+
P
is intended but in the majority of schemes the
only elliptic group operation involved at decryption is scalar multiplication. Since
k
−
are the same, and if one uses
the
x
-coordinate alone the scheme will work exactly the same.
Another cryptographic protocol that we defined in a generic cyclic group
G
(
−
P
)
=−
kP
,the
x
-coordinates of
kP
and
k
(
−
P
)
applies in particular to the elliptic curve setting, where the roles of
G
and
g
are
represented by an elliptic curve
E
=
g
of large prime order.
The DH problem and its variants have corresponding elliptic curve versions to which
the same remarks apply so that they are generally believed to be difficult.
(
F
q
)
and a point
P
∈
E
(
F
q
)
Exercise 11.26
Give an explicit formulation of the elliptic curve version of the
Diffie-Hellman protocol.
Hardness of the ECDLP is a necessary condition for the security of ECC schemes
such as Elgamal or Diffie-Hellman but, as we have seen when we described these
schemes over arbitrary cyclic groups, their security is also related to the DH problem
and its variants. These problems may be specialized to the EC setting and we will
leave the specific details to the reader.
