Cryptography Reference
In-Depth Information
The ElGamal
Encryt
algorithm requires only two modular exponentiations to
encrypt a plaintext message, and hence it is efficient. The efficiency can be further
improved by making use of precomputation. Note that
k
and
K
are independent
from the plaintext message that is encrypted and that they can be precomputed and
securely stored before they are used. This is also true for
c
1
.If
k
,
K
,and
c
1
are
precomputed, then it takes only one modular multiplication to encrypt a plaintext
message. This is arguably much more efficient than the modular exponentiation it
takes to encrypt a plaintext message using the RSA asymmetric encryption system.
In either case, the size of the ciphertext is double the size of the plaintext mes-
sage (i.e., there is a message expansion with a factor two). This is disadvantageous
from a practical viewpoint. From a theoretical (and security) viewpoint, the fact that
the ElGamal
Encryt
algorithm is probabilistic means that the same plaintext message
is encrypted differently in every encryption process. This is advantageous, because it
protects against a probable plaintext attack. In such an attack, the adversary suspects
that the plaintext message is
m
and then tries to encrypt
m
and checks whether the
resulting ciphertext
c
matches a specific ciphertext.
If, in our toy example, the plaintext message to be encrypted is
m
=7,
then the ElGamal
Encryt
randomly selects
k
=3(instep1),computes
K
=
10
3
(mod 27) = 1 (in step 2), and concludes with
c
1
≡
7
3
(mod 27) = 19
and
c
2
≡
7 (mod 27) = 7 (in step 3). Consequently, (19
,
7) is the ciphertext
transmitted to the recipient.
1
·
14.2.3.3
Decryption Algorithm
Upon reception of (
c
1
,c
2
), the recipient must use the ElGamal
Decryt
algorithm to
recover the plaintext message
m
. The algorithm consists of two steps:
c
1
(mod
p
). This works, because
•
First,
K
is retrieved by computing
K
≡
c
1
≡
(
g
k
)
x
(
g
x
)
k
y
k
≡
≡
≡
K
(mod
p
)
.
•
Second,
K
is used to unmask the plaintext message
m
:
m
≡
c
2
/K
(mod
p
)
Note that it is also possible to decrypt (
c
1
,c
2
) by first retrieving
x
=
p
−
1
−
x
