Cryptography Reference
In-Depth Information
public key (
p, g, y
) is available to the sender. The ElGamal
Encryt
algorithm is
probabilistic. It consists of three steps:
Z
p
.
14
•
First, an integer
k
is randomly selected from
y
k
(mod
•
Second, the recipient's public key
y
and
k
are used to compute
K
≡
p
).
15
•
Third,
k
and
K
are used to compute the following pair of values:
g
k
(mod
p
)
c
1
≡
c
2
≡
Km
(mod
p
)
(
c
1
,c
2
) then represents the ciphertext for message
m
.
It is important not to reuse
k
multiple times. If
k
were used more than once,
then knowledge of one plaintext message
m
1
would enable an adversary to compute
another plaintext message
m
2
.Let
(
c
(1)
1
,c
(1)
2
)=(
g
k
(mod
p
)
,Km
1
(mod
p
))
and
(
c
(2)
1
,c
(2)
2
)=(
g
k
(mod
p
)
,Km
2
(mod
p
))
be the ciphertexts of
m
1
and
m
2
(that are both encrypted with the same key
k
). It
then follows that
c
(1)
2
/c
(2)
2
m
1
/m
2
≡
(mod
p
)
,
and hence that
m
2
can be computed if
m
1
is known. Consequently, we need a fresh
and unique
k
∈
R
Z
p
for the encryption of every plaintext message (this requirement
also applies if the ElGamal public key cryptosystem is used as a DSS).
14
This value plays the role of the sender's private exponent in the Diffie-Hellman key exchange
protocol.
15
This value basically plays the role of the outcome of the Diffie-Hellman key exchange protocol.
In the ElGamal asymmetric encryption system, however, it is used to mask (i.e., hide) the message
(using the multiplication modulo
p
operation).