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 couldalso choose the cipher text, whereis 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
