The ElGamal encryption method from Section 10.5 can be modified to give a signature scheme. One feature that is different from RSA is that, with the ElGamal method, there are many different signatures that are valid for a given message.
Suppose Alice wants to sign a message. To start, she chooses a large prime and a primitive root . Alice next chooses a secret integer such that and calculates . The values of , , and are made public. The security of the system will be in the fact that is kept private. It is difficult for an adversary to determine from since the discrete log problem is considered difficult.
In order for Alice to sign a message , she does the following:
Selects a secret random with such that .
Computes (with ).
Computes .
The signed message is the triple .
Bob can verify the signature as follows:
Download Alice’s public key .
Compute , and .
The signature is declared valid if and only if .
We now show that the verification procedure works. Assume the signature is valid. Since , we have , so . Therefore (recall that a congruence mod in the exponent yields an overall congruence mod ),
Suppose Eve discovers the value of . Then she can perform the signing procedure and produce Alice’s signature on any desired document. Therefore, it is very important that remain secret.
If Eve has another message , she cannot compute the corresponding since she doesn’t know . Suppose she tries to bypass this step by choosing an that satisfies the verification equation. This means she needs to satisfy
This can be rearranged to , which is a discrete logarithm problem. Therefore, it should be hard to find an appropriate . If is chosen first, the equation for is similar to a discrete log problem, but more complicated. It is generally assumed that it is also difficult to solve. It is not known whether there is a way to choose and simultaneously, though this seems to be unlikely. Therefore, the signature scheme appears to be secure, as long as discrete logs mod are difficult to compute (for example, should not be a product of small primes; see Section 10.2).
Suppose Alice wants to sign a second document. She must choose a new random value of . Suppose instead that she uses the same for messages and . Then the same value of is used in both signatures, so Eve will see that has been used twice. The values are different; call them and . Eve knows that
Therefore,
Let . There are solutions to the congruence, and they can be found by the procedure given in Subsection 3.3.1. Usually is small, so there are not very many possible values of . Eve computes for each possible until she gets the value . She now knows . Eve now solves
for . There are possibilities. Eve computes for each one until she obtains , at which point she has found . She now has completely broken the system and can reproduce Alice’s signatures at will.
Alice wants to sign the message (which corresponds to one, if we let ). She chooses . Then is a primitive root. She has a secret number . She computes . To sign the message, she chooses a random number and keeps it secret. She computes . Then she computes
The signed message is the triple .
Now suppose Alice also signs the message (which is two) and produces the signed message . Immediately, Eve recognizes that Alice used the same value of , since the value of is the same in both signatures. She therefore writes the congruence
Since , there are two solutions, which can be found by the method described in Subsection 3.3.1. Divide the congruence by 2:
This has the solution , so there are two values of , namely 239 and . Calculate
Since the first is the correct value of , Eve concludes that . She now rewrites to obtain
Since , there are two solutions, namely and , which can be found by the method of Subsection 3.3.1. Eve computes
Since the second value is , she has found that .
Now that Eve knows , she can forge Alice’s signature on any document.
The ElGamal signature scheme is an example of a signature with appendix. The message is not easily recovered from the signature . The message must be included in the verification procedure. This is in contrast to the RSA signature scheme, which is a message recovery scheme. In this case, the message is readily obtained from the signature . Therefore, only needs to be sent since anyone can deduce as . It is unlikely that a random will yield a meaningful message , so there is little danger that someone can successfully replace a valid message with a forged message by changing .