Cryptography Reference
In-Depth Information
Elgamal Encryption Protocol
Alice
Bob
choose large prime
p
choose primitive element α
∈
Z
p
or in a subgroup of
Z
p
choose
k
pr
=
d
∈{
2
,...,
p
−
2
}
d
compute
k
pub
= β = α
mod
p
)
←−−−−−−−−−−−−−−
k
pub
=(
p
,
α
,
β
choose
i
∈{
2
,...,
p
−
2
}
compute ephemeral key
k
E
≡
α
i
mod
p
compute masking key
k
M
≡
β
i
mod
p
encrypt message
x
∈
Z
p
y
≡
x
·
k
M
mod
p
(
k
E
,
y
)
−−−−−−−−−−−−−−→
compute masking key
k
M
≡
k
E
mod
p
decrypt
x
≡
y
·
k
−
M
mod
p
The actual Elgamal encryption protocol rearranges the sequence of operations
from the naıve Diffie-Hellman inspired approach we saw before. The reason for
this is that Alice has to send only one message to Bob, as opposed to two messages
in the earlier protocol.
The ciphertext consists of two parts, the ephemeral key,
k
E
, and the masked plain-
text,
y
. Since in general all parameters have a bit length of
, the ciphertext
(
k
E
,
y
) is twice as long as the message. Thus, the
message expansion factor
of Elga-
mal encryption is two.
We prove now the correctness of the Elgamal protocol.
log
2
p
Proof.
We have to show that
d
k
pr
(
k
E
,
y
) actually yields the original message
x
.
(
k
M
)
−
1
d
k
pr
(
k
E
,
y
)
≡
y
·
mod
p
(
k
E
)
−
1
≡
[
x
·
k
M
]
·
mod
p
d
)
i
][(
i
)
d
]
−
1
≡
[
x
·
(
α
α
mod
p
d
·
i
−
d
·
i
≡
x
·
α
≡
x
mod
p
Let's look at an example with small numbers.
Example 8.14.
In this example, Bob generates the Elgamal keys and Alice encrypts
the message
x
= 26.
