Cryptography Reference
In-Depth Information
and then computing
c
x
1
c
2
g
kx
Km
(mod
p
)
≡
g
k
(
p−
1
−x
)
Km
(mod
p
)
≡
g
k
(
p−
1
−x
)
y
k
m
(mod
p
)
≡
(
g
p−
1
)
k
(
g
x
)
−k
y
k
m
(mod
p
)
≡
y
−k
y
k
m
(mod
p
)
≡
≡
m
(mod
p
)
.
Similar to the RSA asymmetric encryption system, the ElGamal system re-
quires a modular exponentiation to decrypt a ciphertext. In the case of the ElGamal
asymmetric encryption system, however, there is no possibility to use the CRT to
speed up the decryption algorithm.
In our toy example, the recipient receives (19
,
7) and wants to recover the
plaintext message
m
.TheElGamal
Decrypt
algorithm therefore computes
K
≡
19
6
(mod 27) = 1 and
m
≡
7
/
1
≡
7 (mod 27) = 7.
14.2.3.4
Security Analysis
The security of the ElGamal asymmetric encryption system is based on the DLA
(see Definition 7.4)—that is, the assumed intractability of computing discrete log-
arithms. In fact (and as suggested in Theorem 14.2), one can prove that breaking
the ElGamal asymmetric encryption system (by computing a discrete logarithm) is
computationally equivalent to solving the DHP (see Definition 7.6). One cannot,
however, prove that breaking the ElGamal asymmetric encryption system is com-
putationally equivalent to solving the DLP (remember from Section 7.2.1 that the
intractability assumption for the DHP is stronger than the intractability assumption
for the DLP).
Theorem 14.2
Breaking the ElGamal asymmetric encryption system is computa-
tionally equivalent to solving the DHP.
Proof.
To prove the theorem, one must show (a) that somebody who can solve
the DHP can also break the ElGamal asymmetric encryption system, and (b) that
somebody who can break the ElGamal system can also solve the DHP. To simplify
the notation, we use an arbitrary cyclic group
G
with order
p
and generator
g
for the
purpose of this proof.
For direction (a) we must show that somebody who can solve the DHP can
also break the ElGamal system. We therefore assume an adversary who has access
