Exponential Ciphers - Introduction to Cryptography with Java Applets - page 268

Note that ElGamal basically doubles the size of the message. For this reason, cryptog-
raphers often ignore the national standard in favor of other cryptosystems.

System-Wide Parameters Note that there is no particular reason why everyone in
a system could not use the same values for the prime p and the generator g with ElGamal.
Each individual would only then need to choose a private value for a . This has been sug-
gested, and has received limited use in practice.

14.7

WEAKNESSES OF ELGAMAL
ElGamal can be broken provided proper precautions are not taken. We describe the most
important weakness here.

Equal Encryption Exponent Attack It is very important that when enciphering

using the transformations

c g k (mod p ) (0 ≤ c < p )

d Pr k

P ( g a ) k (mod p )

≤ d < p ).
that the sender choose a different random value of k for each plaintext message. If the mes-
sage must be separated into blocks, a different value of k must be used on each block. If not,
plaintext can be easily derived by an adversary. To see this, suppose the same value for k
was used to encipher the plaintext messages P and P * . Their corresponding ciphertext pairs
are ( c , d ), and ( c * , d * ). Note then that we have

(0

( d * ) P ( g a ) k ( P * ( g a ) k )

(mod p ),
where d and ( d * ) are inverses of d and d * modulo p , respectively. Thus
P *

d

P (modulo p ).
Thus, if either message, P or P * , were known to an adversary, they could easily derive
the other message. Thus, this is a known plaintext attack coupled with carelessness on the
part of the sender. If the sender always used the same value for k , an adversary would need
only one plaintext message to retrieve any others.

d ( d * )

E XAMPLE . Here we see this type of attack, which you will be asked to program in Java. We
begin by finding a safe prime:

p = 3213876088517980551083924184682325205044405987565585670609523
It turns out that g = 2 is a generator for this prime. The sender's private ElGamal key will

be:

a = 1897456254164942343917965235766273117568497123443633417036846
We compute the sender's public key value r as the lnr of g a modulo p :

r = 2063540830854289477395627063716322702415230040026373835561574