Cryptography Reference
In-Depth Information
Principle of Elgamal Encryption
Alice
Bob
(a) choose
d
=
k
pr
,
B
∈{
2
,...,
p
−
2
}
(b) compute β =
k
pub
,
B
≡
α
d
mod
p
β
←−−−−−−−−−−−−−−
(c) choose
i
=
k
pr
,
A
∈{
2
,...,
p
−
2
}
(d) compute
k
E
=
k
pub
,
A
≡
α
i
mod
p
k
E
−−−−−−−−−−−−−−→
i
mod
p
k
E
mod
p
(e) compute
k
M
≡
β
(f) compute
k
M
≡
∈
Z
p
(g) encrypt message
x
y
≡
x
·
k
M
mod
p
y
−−−−−−−−−−−−−−→
(h) decrypt
x
≡
y
·
k
−
M
mod
p
The protocol consists of two phases, the classical DHKE (Steps a-f) which is
followed by the message encryption and decryption (Steps g and h, respectively).
Bob computes his private key
d
and public key
. This key pair does not change,
i.e., it can be used for encrypting many messages. Alice, however, has to generate
a new public-private key pair for the encryption of every message. Her private key
is denoted by
i
and her public key by
k
E
. The latter is an ephemeral (existing only
temporarily) key, hence the index “E”. The joint key is denoted by
k
M
because it is
used for masking the plaintext.
For the actual encryption, Alice simply multiplies the plaintext message
x
by
the masking key
k
M
in
β
Z
p
. On the receiving side, Bob reverses the encryption by
multipliying with the inverse mask. Note that one property of cyclic groups is that,
given any key
k
M
∈
Z
p
, every messages
x
maps to another ciphertext if the two
values are multiplied. Moreover, if the key
k
M
is randomly drawn from
Z
p
,every
ciphertext
y
∈{
1
,
2
,...,
p
−
1
}
is equally likely.
8.5.2 The Elgamal Protocol
We provide now a somewhat more formal description of the scheme. We distinguish
three phases. The set-up phase is executed once by the party who issues the public
key and who will receive the message. The encryption phase and the decryption
phase are executed every time a message is being sent. In contrast to the DHKE, no
trusted third party is needed to choose a prime and primitive element. Bob generates
them and makes them public, by placing them in a database or on his website.
