Patents

David Kravitz, formerly of the NSA, holds a patent on DSA [897]. According to NIST [538]:

NIST intends to make this DSS technique available world-wide on a royalty-free basis to the public interest. We believe this technique is patentable and that no other patents would apply to the DSS, but we cannot give firm assurances to such effect in advance of issuance of the patent.

Even so, three patent holders claim that the DSA infringes on their patents: Diffie-Hellman (see Section 22.1) [718], Merkle-Hellman (see Section 19.2) [720], and Schnorr (see Section 21.3) [1398]. The Schnorr patent is the most troublesome. The other two patents expire in 1997; the Schnorr patent is valid until 2008. The Schnorr algorithm was not developed with government money; unlike the PKP patents, the U.S. government has no rights to the Schnorr patent; and Schnorr patented his algorithm worldwide. Even if the U.S. courts rule in favor of DSA, it is unclear what other courts around the world would do. Is an international company going to adopt a standard that may be legal in some countries but infringes on a patent in others? This issue will take time to resolve; at the time of this writing it isn’t even resolved in the United States.

In June 1993 NIST proposed to give PKP an exclusive patent license to DSA [541]. The agreement fell through after public outcry and the standard was issued without any deal. NIST said [542]:

...NIST has addressed the possible patent infringement claims, and has concluded that there are no valid claims.

So the standard is official, lawsuits are threatened, and no one knows what to do. NIST has said that it would help defend people sued for patent infringement, if they were using DSA to satisfy a government contract. Everyone else, it seems, is on their own. ANSI has a draft banking standard that uses DSA [60]. NIST is working to standardize DSA within the government. Shell Oil has made DSA their international standard. I know of no other proposed DSA standards.

20.2 DSA Variants

This variant makes computation easier on the signer by not forcing him to compute k^-1 [1135]. All the parameters are as in DSA. To sign a message, m, Alice generates two random numbers, k and d, both less than q. The signature is

r = (g^k mod p) mod q

s = (H(m) + xr) * d mod q

t = kd mod q

Bob verifies the signature by computing

w = t/s mod q

u₁ = (H(m) * w) mod q

u₂ = (rw) mod q

If r = ((g^u1 * y^u2) mod p) mod q, then the signature is verified.

This next variant makes computation easier on the verifier [1040,1629]. All the parameters are as in DSA. To sign a message, m, Alice generates a random number, k, less than q. The signature is

r = (g^k mod p) mod q

s = k * (H(m) + xr)^-1 mod q

Bob verifies the signature by computing

u₁ = (H(m) * s) mod q

u₂ = (sr) mod q

If r = ((g^u1 * y^u2) mod p) mod q, then the signature is verified.

Another DSA variant allows for batch verification; Bob can verify signatures in batches [1135]. If they are all valid, he is done. If one isn’t valid, then he still has to find it. Unfortunately, it is not secure; either the signer or the verifier can easily create a set of bogus signatures that satisfy the batch criteria [974].

There is also a variant for DSA prime generation, one that embeds q and the parameters used to generate the primes within p. Whether this scheme reduces the security of DSA is still unknown.

(1)  Choose an arbitrary sequence of at least 160 bits and call it S. Let g be the length of S in bits.

(2)  Compute U = SHA(S) ⊕ SHA ((S + 1) mod 2^g), where SHA is the Secure Hash Algorithm (see Section 18.7).

(3)  Form q by setting the most significant bit and the least significant bit of U to 1.

(4)  Check whether q is prime.

(5)  Let p be the concatenation of q, S, C, and SHA(S). C is set to 32 zero bits.

(6)  p = p – (p mod q) + 1.

(7)  p = p + q.

(8)  If the C in p is 0x7fffffff, go to step (1).

(9)  Check whether p is prime.

(10)  If p is composite, go to step (7).

The neat thing about this variant is that you don’t have to store the values of C and S used to generate p and q; they are embedded within p. For applications without a whole lot of memory, like smart cards, this can be a big deal.

20.3 GOST Digital Signature Algorithm

This is a Russian digital signature standard, officially called GOST R 34.10-94 [656]. The algorithm is very similar to DSA, and uses the following parameters

p = a prime number, either between 509 and 512 bits long, or between 1020 and 1024 bits long.

q = a 254- to 256-bit prime factor of p – 1.

a = any number less than p – 1 such that a^q mod p = 1.

x = a number less than q.

y = a^x mod p.

The algorithm also makes use of a one-way hash function: H(x). The standard specifies GOST R 34.11-94 (see Section 18.11), a function based on the GOST symmetric algorithm (see Section 14.1) [657].

The first three parameters, p, q, and a, are public and can be common across a network of users. The private key is x; the public key is y.

To sign a message, m

(1)  Alice generates a random number, k, less than q

(2)  Alice generates

r = (a^k mod p) mod q

s = (xr + k(H(m))) mod q

If H(m) mod q = 0, then set it equal to 1. If r = 0, then choose another k and start again. The signature is two numbers: r mod 2²⁵⁶ and s mod 2²⁵⁶. She sends these to Bob.

(3)  Bob verifies the signature by computing

v = H(m)^q-2 mod q

z₁ = (sv) mod q

z₂ = ((q – r) * v) mod q

u = ((a^z1 * y^z2) mod p) mod q

If u = r, then the signature is verified.