Public-Key Cryptosystems Based on the Discrete Logarithm Problem - Understanding Cryptography - page 226

Alice Bob

message x = 26 generate p = 29 and α = 2

choose k pr , B = d = 12
compute

d

β = α ≡ 7 mod 29

k pub , B =( p , α , β )

←−−−−−−−−−−−−

choose i = 5
compute k E =

i

α ≡ 3 mod 29

i

compute k M = β ≡ 16 mod 29

encrypt y = x · k M ≡ 10 mod 29

y , k E
−−−−−−−−−−−−→

compute k M = k E ≡ 16 mod 29

decrypt
x = y k − M ≡ · 10 · 20 ≡ 26 mod 29

It is important to note that, unlike the schoolbook version of the RSA scheme,
Elgamal is a probabilistic encryption scheme , i.e., encrypting two identical mes-
sages x 1 and x 2 , where x 1 , x 2 ∈ Z p using the same public key results (with extremely
high likelihood) in two different ciphertexts y 1

= y 2 . This is because i is chosen at

random from { 2 , 3 , ··· , p − 2 } for each encryption, and thus also the session key

i used for encryption is chosen at random for each encryption. In this way a
brute-force search for x is avoided a priori.

k M = β

8.5.3 Computational Aspects

Key Generation During the key generation by the receiver (Bob in our example), a
prime p must be generated, and the public and private have to be computed. Since
the security of Elgamal also depends on the discrete logarithm problem, p needs
to have the properties discussed in Section 8.3.3. In particular, it should have a
length of at least 1024 bits. To generate such a prime, the prime-finding algorithms
discussed in Section 7.6 can be used. The private key should be generated by a true
random number generater. The public key requires one exponentiation for which the
square-and-multiply algorithm is used.
Encryption Within the encryption procedure, two modular exponentiations and one
modular multiplication are required for computing the ephemeral and the masking
key, as well as for the message encryption. All operands involved have a bit length
of

. For efficient exponentiation, one should apply the square-and-multiply
algorithm that was introduced in Section 7.4. It is important to note that the two ex-
ponentiations, which constitute almost all computations necessary, are independent
of the plaintext. Hence, in some applications they can be precomputed at times of
low computational load, stored and used when the actual encryption is needed. This
can be a major advantage in practice.
Decryption The main steps of the decryption are first an exponentiation k M =
k d

log 2 p

mod p , using the square-and-multiply algorithm, followed by an inversion of k M