Cryptography Reference
In-Depth Information
large enough so that the index-calculus method cannot compute the DLP. By con-
sulting Table 6.1 we see that a security level of 80 bit is achieved by primes of
lengths 1024 bit, and for 128 bit security we need about 3072 bit. An additional
requirement is that in order to prevent the Pohlig-Hellman attack, the order
p
1of
the cyclic group must not factor in only small prime factors. Each of the subgroups
formed by the factors of
p
−
1 can be attacked using the baby-step giant-step method
or Pollards's rho method, but not by the index-calculus method. Hence, the smallest
prime factor of
p
−
1 must be at least 160 bit long for an 80-bit security level, and
at least 256 bit long for a security level of 128 bit.
−
8.5 The Elgamal Encryption Scheme
The
Elgamal encryption scheme
was proposed by Taher Elgamal in 1985 [73]. It is
also often referred to as Elgamal encryption. It can be viewed as an extension of the
DHKE protocol. Not surprisingly, its security is also based on the intractability of
the discrete logarithm problem and the Diffie-Hellman problem. We consider the
Elgamal encryption scheme over the group
Z
p
, where
p
is a prime. However, it can
be applied to other cyclic groups too in which the DL and DH problem is intractable,
for instance, in the multiplicative group of a Galois field
GF
(2
m
).
8.5.1 From Diffie-Hellman Key Exhange to Elgamal Encryption
In order to understand the Elgamal scheme, it is very helpful to see how it follows
almost immediately from the DHKE. We consider two parties, Alice and Bob. If
Alice wants to send an encrypted message
x
to Bob, both parties first perform a
Diffie-Hellman key exchange to derive a shared key
k
M
. For this we assume that a
large prime
p
and a primitive element
have been generated. Now, the new idea is
that Alice uses this key as a multiplicative mask to encrypt
x
as
y
α
≡
x
·
k
M
mod
p
.
This process is depicted below.
