Cryptography Reference
In-Depth Information
We close this section with some advanced material for which the reader will
need some knowledge of elliptic curves. We have presented all necessary material
in Appendix A (see page 498).
ElGamal Public-Key Elliptic Curve Cryptosystem (ECC)
We assume that
E
is an elliptic curve over
F
p
where
p
is prime and
H
is a
cyclic subgroup of
E
(
F
p
). Alice wants to send
a message to Bob whose public key is (
E,P,aP
) and whose private key is the
natural number
a<p
F
p
) generated by a point
P
∈
E
(
1. Alice executes the following.
Enciphering stage
:
−
1. Choose a random natural number
b<p
−
1.
2. Consider the plaintext message units embedded as points
m
on
E
.
3. Compute
β
=
bP
and
γ
=
m
+
b
(
aP
).
4. Send the ciphertext
E
e
(
m
)=
c
=(
β,γ
) to Bob.
Deciphering stage
:
Once Bob receives the ciphertext, the plaintext
m
is recovered via the private
key as
D
d
(
c
)=
m
=
γ
−
aβ.
Example 4.9
Consider the elliptic curve group
E
given by
y
2
=
x
3
+4
x
+4
over
=15
, which is necessarily cyclic.Also,
P
=(1
,
3)
is a generator of
E
.Assuming that Bob's public key is
(
E,P,
4
P
)
where
a
=4
is the private key and
m
= (10
,
2)
is the message that Alice wants to
send to Bob, then Alice performs the following.Alice chooses
b
=7
at random.
Then she calculates
F
13
.It can be shown that
|
E
(
F
p
)
|
E
e
(
m
)=
E
e
((10
,
2)) = (
bP, m
+
b
(
aP
)) = (7
P,
(10
,
2) + 7(4
P
)) =
((0
,
2)
,
(10
,
2) + 7(6
,
6)) = ((0
,
2)
,
(10
,
2) + (12
,
5)) = ((0
,
2)
,
(3
,
2)) = (
β,γ
)=
c.
Then Alice sends
c
to Bob who uses the private key to recover
m
via
D
d
(
c
)=(3
,
2)
−
4(0
,
2) = (3
,
2)
−
(12
,
5)=(3
,
2) + (12
,
8) = (10
,
2) =
m.
The ElGamal cipher given on page 185 has what is called a
message expan-
sion factor
of 2 over
F
p
, meaning that the ciphertext is roughly twice the size
of the plaintext. However, an elliptic curve implementation of ElGamal has a
message expansion factor of approximately four, because there are
p
plaintexts,
but each ciphertext is comprised of four field elements. Moreover, and perhaps
more seriously, plaintext message units
m
lie on
E
and there does not exist
an appropriate (both theoretically and practically) method of deterministically
generating such points. A more workable scheme is the
Menezes-Vanstone ECC
,
which is described in [169, pages 245 and 246] from which the above example
was adapted. A big advantage of PKC ECCs is that key sizes are much smaller
than, say, RSA.
Search WWH ::
Custom Search