Cryptography: Theory and Practice:Signature Schemes | Modern Cryptography: Theory and Practice

Cryptography: Theory and Practice
by Douglas Stinson
CRC Press, CRC Press LLC
ISBN: 0849385210 Pub Date: 03/17/95

Table of Contents

What if Alice first encrypted x, and then signed the result? Then she would compute

Alice would transmit the pair (z, y) to Bob. Bob would decrypt z, obtaining x, and then verify the signature y on x using ver _Alice. One potential problem with this approach is that if Oscar obtains a pair (z, y) of this type, he could replace Alice’s signature y by his own signature

(Note that Oscar can sign the ciphertext z = e_Bob(x) even though he doesn’t know the plaintext x.) Then, if Oscar transmits (z, y′) to Bob, Oscar’s signature will be verified by Bob using ver_Oscar, and Bob may infer that the plaintext x originated with Oscar. Because of this potential difficulty, most people recommend signing before encrypting.

Figure 6.2 ElGamal Signature Scheme

6.2 The ElGamal Signature Scheme

We now describe the ElGamal Signature Scheme, which was described in a 1985 paper. A modification of this scheme has been adopted as a digital signature standard by the National Institute of Standards and Technology (NIST). The ElGamal Scheme is designed specifically for the purpose of signatures, as opposed to RSA, which can be used both as a public-key cryptosystem and a signature scheme.

The ElGamal Signature Scheme is non-deterministic, as was the ElGamal Public-key Cryptosystem. This means that there are many valid signatures for any given message. The verification algorithm must be able to accept any of the valid signatures as authentic. The description of the ElGamal Signature Scheme is given in Figure 6.2.

If the signature was constructed correctly, then the verification will succeed, since

where we use the fact that

Bob computes a signature using both the secret value a (which is part of the key) and the secret random number k (which is used to sign one message, x). The verification can be accomplished using only public information.

Let’s do a small example to illustrate the arithmetic.

Example 6.1

Suppose we take p = 467, α = 2, a = 127; then

Suppose Bob wants to sign the message x = 100 and he chooses the random value k = 213 (note that gcd(213, 466) = 1 and 213^-1 mod 466 = 431). Then

and

Anyone can verify this signature by checking that

and

Hence, the signature is valid.

Let’s look at the security of the ElGamal Signature Scheme. Suppose Oscar tries to forge a signature for a given message x, without knowing a. If Oscar chooses a value γ and then tries to find the corresponding δ, he must compute the discrete logarithm log_γ α^xβ^-γ. On the other hand, if he first chooses δ and then tries to find γ, he is trying to “solve” the equation

for the “unknown” γ. This is a problem for which no feasible solution is known; however, it does not seem to be related to any well-studied problem such as the Discrete Logarithm problem. There also remains the possibility that there might be some way to compute γ and δ simultaneously in such a way that (γ, δ) will be a signature. No one has discovered a way to do this, but conversely, no one has proved that it cannot be done.

If Oscar chooses γ and δ and then tries to solve for x, he is again faced with an instance of the Discrete Logarithm problem, namely the computation of log_α β^γγ^δ. Hence, Oscar cannot sign a “random” message using this approach. However, there is a method by which Oscar can sign a random message by choosing γ, δ and x simultaneously: Suppose i and j are integers, 0 ≤ i ≤ p -2, 0 ≤ j ≤ p - 2, and gcd(j, p - 1) = 1. Then perform the following computations:

where j^-1 is computed modulo (p - 1) (this is where we require that j be relatively prime to p - 1).

We claim that (γ, δ) is a valid signature for the message x. This is proved by checking the verification condition:

We illustrate with an example.

Example 6.2

As in the previous example, suppose p = 467, α = 2 and β = 132. Suppose Oscar chooses i = 99 and j = 179; then j^-1 mod (p - 1) = 151. He would compute the following:

Then (117, 41) is a valid signature for the message 331, as may be verified by checking that

and

Hence, the signature is valid.

Here is a second type of forgery, in which Oscar begins with a message previously signed by Bob. Suppose (γ, δ) is a valid signature for a message x. Then it is possible for Oscar to sign various other messages. Suppose h, i and j are integers, 0 ≤ h, i, j ≤ p - 2, and gcd(hγ - jδ, p - 1) = 1. Compute the following:

where (hγ - jδ)^-1 is computed modulo (p - 1). Then, it is tedious but straight-forward to check the verification condition:

Hence (λ, μ) is a valid signature for x′.

Both of these methods produce valid forged signatures, but they do not appear to enable an opponent to forge a signature on a message of his own choosing without first solving a discrete logarithm problem. Hence, they do not seem to represent a threat to the security of the ElGamal Signature Scheme.

Finally, we mention a couple of ways in which the ElGamal Scheme can be broken if it is used carelessly (these are further examples of protocol failures, some of which were discussed in the exercises of Chapter 4). First, the random value k used in computing a signature should not be revealed. For, if k is known, it is a simple matter to compute

Of course, once a is known, then the system is broken and Oscar can forge signatures at will.

Table of Contents