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

FIGURE 14.2

Figure 14.2 is a screen shot of TestPohligHellmanCipherApplet. Give it a try and see
how it works.

14.6

THE ELGAMAL CIPHER
Since DFH, there has been an explosion of public key algorithms. The proposed national
standard, backed by the National Security Agency (NSA), is called ElGamal. Though it is
a very interesting algorithm, it is possible that NSA has already broken it, which could
explain their enthusiasm for it. ElGamal is similar to Diffie-Hellman key exchange and
Pohlig-Hellman in that breaking it requires solving the discrete logarithm problem. This is
opposed to RSA (which we will soon discuss), which depends on the intractability of fac-
toring integers with large prime factors.
This is how ElGamal works: First, the recipient of a message must choose a large ran-
dom safe prime p , and a generator g modulo p . At current levels of computing power, p
should be at least 1024 bits in length. Then he selects a random integer a such that 1 < a <
p 1, and computes the least nonnegative residue r of g a modulo p . That is,
r g a (mod p ) (0 ≤ r < p ).

He makes public the values p , g , and r . The private key is a .
Now, for someone to send a message to this individual, she must do the following: Sup-
pose P is the plaintext message, considered as an integer, with 0

≤ P < p . The sender then