Cryptography Reference
In-Depth Information
that is performed with the extended Euclidean algorithm. However, there is a short-
cut based on Fermat's Little Theorem that combines these two steps in a single one.
From the theorem, which was introduced in Section 6.3.4, follows that
k
p
−
1
E
≡
1mod
p
for all
k
E
∈
Z
p
. We can now merge Step 1 and 2 of the decryption as follows:
k
−
M
≡
(
k
E
)
−
1
mod
p
(
k
E
)
−
1
k
p
−
1
≡
mod
p
E
k
p
−
d
−
1
E
≡
mod
p
(8.4)
The equivalence relation (8.4) allows us to compute the inverse of the masking key
using a single exponentiation with the exponent (
p
−
d
−
1). After that, one mod-
k
−
M
mod
p
. As a consequence, de-
cryption essentially requires one execution of the square-and-multiply algorithm
followed by a single modular multiplication for recovering the plaintext.
ular multiplication is required to recover
x
≡
y
·
8.5.4 Security
If we want to assess the security of the Elgamal encryption scheme it is important to
distinguish between passive, i.e., listen-only, and active attacks, which allow Oscar
to generate and alter messages.
Passive Attacks
The security of the Elgamal encryption scheme against passive attacks, i.e., recover-
ing
x
from the information
p
,
i
obtained by eaves-
dropping, relies on the hardness of the Diffie-Hellman problem (cf. Section 8.4).
Currently there is no other method known for solving the DHP than computing
discrete logarithms. If we assume Oscar has supernatural powers and can in fact
compute DLPs, he would have two ways of attacking the Elgamal scheme.
d
,
k
E
=
i
α
,
β
=
α
α
and
y
=
x
·
β
Recover
x
by finding Bob's secret key
d
:
d
= log
α
β
mod
p
.
This step solves the DLP, which is computationally infeasible if the parame-
ters are chosen correctly. However, if Oscar succeeds with it, he can decrypt the
plaintext by performing the same steps as the receiver, Bob:
(
k
E
)
−
1
x
≡
y
·
mod
p
.
