Cryptography Reference
In-Depth Information
key exchange protocol into a full-fledged public key cryptosystem (i.e., a public key
cryptosystem that can be used to encrypt and decrypt messages as well as to digitally
sign messages and verify digital signatures) [13].
13
In this section, we overview and discuss the ElGamal asymmetric encryption
system. The ElGamal DSS is addressed in Section 15.2.2.
14.2.3.1
Key Generation Algorithm
The ElGamal
Generate
algorithm is the same as the one employed by the Diffie-
Hellman key exchange protocol (see Section 16.3). One needs a cyclic group
in which the DLP is (assumed to be) intractable. In this section, we use the
multiplicative group of a finite field of prime order (i.e.,
Z
p
) to describe the ElGamal
asymmetric encryption system. Note, however, that there are many other cyclic
groups that can be used instead.
To make use of the ElGamal asymmetric encryption system, every user must
have a large prime
p
and a generator
g
of
Z
p
.TheElGamal
Generate
algorithm then
works in two steps:
Z
p
;
•
First, a private exponent
x
is randomly selected from
g
x
(mod
p
) is computed.
•
Second, a public exponent
y
≡
It is up to the user to make
y
publicly available (in addition to
p
and
g
). The
triple (
p, g, y
) then represents the public ElGamal key, whereas
x
represents the
private ElGamal key.
Note that the parameters
p
and
g
can be the same for all users. In this case, they
represent system parameters. The advantage of this approach is that the sum of the
lengths of all public keys can be effectively minimized. The disadvantage, however,
is that weak or vulnerable parameters affect all users. In either case, the private and
public ElGamal keys are assumed to be used for a comparably long period of time
(this is in contrast to the keys used in the Diffie-Hellman key exchange protocol).
Again, we consider a toy example that we revisit for each algorithm to
illustrate the ElGamal asymmetric encryption system. Let
p
=27and
g
=7be
system parameters. The ElGamal
Generate
algorithm randomly selects the private
key
x
=6and computes the public key
y
7
6
(mod 27) = 10.
≡
14.2.3.2
Encryption Algorithm
We assume that a user wants to use the ElGamal asymmetric encryption system
to send an encrypted message
m
∈
Z
p
to another user and that the recipient's
13
A preliminary version of [13] was presented at the CRYPTO '84 conference.
