The ideal case is when
, where
itself is prime. For example, take
so
In the ideal case,
has the greatest possible number of different generators (for its size) so that it is easy to find a generator. However, such primes
, known as
Sophie‐Germain primes, are conjectured to be rare. In any event, only a finite number are known to exist.
Using the Diffie–Hellman idea, it is possible to construct a public‐key cryptosystem called the El Gamal Cryptosystem.
El Gamal Cryptosystem
As before, we are given a prime and a generator . Each participant has, as a private key, a secret integer (which can be assumed to lie between 2 and and a public key . Suppose wants to send a secret message , which is in the form of a positive integer less than . Let the integer be the private key for . has, for a public key, . also computes the key , obtained by getting the remainder upon raising the public key of , to the power , and dividing by . (As in the DH key‐exchange, can also find by raising to the power of and dividing by to get the remainder.)
Finally, transmits the cipher text to (as well as . From , can calculate . Since is a prime can calculate , where . Then calculates . This is the El Gamal Cryptosystem.
Remark 3.7 Instead of taking the cipher text , we could also choose the cipher text , where is any keyed symmetric algorithm such as AES.
The RSA digital signature protocol is relatively easy because and are both defined on the same set, namely . For a more complicated digital signature example, we present the El Gamal Digital Signature Scheme.
The El Gamal digital signature scheme
wants to send a signed message to . begins with a large prime and a generator (a primitive root) for that prime. Then chooses an integer such that . The public key of
