The difference between this scheme and DSA is that with DSA s = (xr + k^-1(H(m))) mod q, which leads to a different verification equation. Curious, though, is that q is 256 bits. Most Western cryptographers seem satisfied with a q of around 160 bits. Perhaps this is just a reflection of the Russian tendency to play it ultrasafe.

The standard has been in use since the beginning of 1995, and is not classified “for special use”—whatever that means.

20.4 Discrete Logarithm Signature Schemes

ElGamal, Schnorr (see Section 21.3), and DSA signature schemes are very similar. In fact, they are just three examples of a general digital signature scheme based on the Discrete Logarithm Problem. Along with thousands of other signature schemes, they are part of the same family [740,741,699,1184].

Choose p, a large prime number, and q, either p – 1 or a large prime factor of p – 1. Then choose g, a number between 1 and p such that g^q ≡ 1 (mod p). All these numbers are public, and can be common to a group of users. The private key is x, less than q. The public key is y = g^x mod p.

To sign a message, m, first choose a random k less than and relatively prime to q. If q is also prime, any k less than q works. First compute

r = g^k mod p

The generalized signature equation now becomes

ak = b + cx mod q

The coefficients a, b, and c can be any of a variety of things. Each line in Table 20.4 gives six possibilities.

To verify the signature, the receiver must confirm that

r^a = g^by^c mod p

This is called the verification equation.

Table 20.5 lists the signature and verifications possible from just the first line of potential values for a, b, and c, ignoring the effects of the ±

That’s six different signature schemes. Adding the negative signs brings the total to 24. Using the other possible values listed for a, b, and c brings the total to 120.

ElGamal [518,519] and DSA [1154] are essentially based on equation (4). Other schemes are based on equation (2) [24,1629]. Schnorr [1396,1397] is closely related to equation (5), as is another scheme [1183]. And equation (1) can be modified to yield the scheme proposed in [1630]. The rest of the equations are new.

There’s more. You can make any of these schemes more DSA-like by defining r as

r = (g^k mod p) mod q

Keep the same signature equation and make the verification equation

u₁ = a^-1b mod q

u₂ = a^-1c mod q

r = (g^u1y^u2 mod p) mod q

There are two other possibilities along these lines [740,741]; you can do this with each of the 120 schemes, bringing the total to 480 discrete-logarithm-based digital signature schemes.

But wait—there’s more. Additional generalizations and variations can generate more than 13,000 variants (not all of them terribly efficient) [740,741].

One of the nice things about using RSA for digital signatures is a feature called message recovery. When you verify an RSA signature you compute m. Then you compare the computed m with the message and see if the signature is valid for that message. With the previous schemes, you can’t recover m when you compute the signature; you need a candidate m that you use in a verification equation. Well, as it turns out it is possible to construct a message recovery variant for all the above signature schemes.

To sign, first compute

r = mg^k mod p

and replace m by 1 in the signature equation. Then you can reconstruct the verification equation such that m can be computed directly.

You can do the same with the DSA-like schemes:

r = (mg^k mod p) mod q