Cryptography Reference
In-Depth Information
'divide'
C
2
by this to obtain the plaintext
P
. To obtain
k
the attacker could either
try to extract
k
from:
g
k
mod
p
;
1.
C
1
=
Py
k
mod
p
, which is difficult because the attacker does not know
P
.
Thus
C
1
looks the best bet, since both
C
1
and
g
are known to the attacker. However,
determining
k
fromknowledge of
g
k
mod
p
involves solving the discrete logarithm
problem that we discussed in Section 5.1.4. It is thus widely
believed
(but not
proven
), that we need to solve the discrete logarithm problem in order to obtain
an ElGamal plaintext directly from an ElGamal ciphertext.
2.
C
2
=
DETERMINING THE PRIVATE KEY DIRECTLY FROM THE PUBLIC KEY
To conduct the more powerful attack of determining an ElGamal private key
directly from an ElGamal public key, we need to work out
x
from knowledge of
y
=
g
x
mod
p
. Once again, this requires a process for solving the discrete logarithm
problem. Thus directly determining the private key is also believed to be hard.
ELGAMAL SECURITY SUMMARY
We have just seen that both the 'obvious' attacks on ElGamal appear to only
be viable if a means of efficiently solving the discrete logarithm problem can be
found. Thus ElGamal is believed to be a strong public-key cryptosystem.
5.3.4
ElGamal in practice
There are several important aspects of ElGamal that deserve further discussion.
USE OF SYSTEM-WIDE PARAMETERS
One interesting aspect of ElGamal is that the values
p
and
g
can be treated as
system-wide parameters
, which are publicly known values that are shared by all
the users of the system. In this case we can regard the public key of a particular user
as simply being the value
y
. The main cost of this is that the users have to agree
to use the same system-wide parameters, but the benefit is that key generation
becomes slightly more straightforward.
PROBABILISTIC ENCRYPTION
ElGamal is an example of what is often termed
probabilistic encryption
. This is
because each time the same plaintext is encrypted using the same public key, the
resulting ciphertext should be
different
since the ciphertext relies on a randomly
generated temporary key
k
as well as the public key
y
.
The obvious cost of probabilistic encryption is that it requires the random
generation of a number. This could be regarded as disadvantageous in comparison
to cryptosystems that do not appear to require this, such as the version of RSA
that we described in Section 5.2.
