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 is and the private key of is . Since and are publicly known, it is important that it be infeasible to calculate the solution to . This requires that have a large number of bits. When signing a message
before, we are given a prime 