All the variants are equally secure, so it makes sense to choose a scheme that is easy to compute with. The requirement to compute inverses slows most of these schemes. As it turns out, a scheme in this pile allows computing both the signature equation and the verification equation without inverses and also gives message recovery. It is called the p-NEW scheme [1184].

r = mg^-k mod p

s = k – r’x mod q

And m is recovered (and the signature verified) by

m = g^sy^r’r mod p

Some variants sign two and three message blocks at the same time [740]; other variants can be used for blind signatures [741].

This is a remarkable piece of research. All of the various discrete-logarithm-based digital signature schemes have been put in one coherent framework. In my opinion this finally puts to rest any patent dispute between Schnorr [1398] and DSA [897]: DSA is not a derivative of Schnorr, nor even of ElGamal. All three are examples of this general construction, and this general construction is unpatented.

20.5 Ong-Schnorr-Shamir

This signature scheme uses polynomials modulo n [1219,1220]. Choose a large integer n (you need not know the factorization of n). Then choose a random integer, k, such that k and n are relatively prime. Calculate h such that

h = –k^-2 mod n = -(k^-1)² mod n

The public key is h and n; k is the private key.

To sign a message, M, first generate a random number, r, such that r and n are relatively prime. Then calculate:

S₁ = 1/2 * (M/r + r) mod n

S₂ = k/2 * (M/r – r) mod n

The pair, S₁ and S₂, is the signature.

To verify a signature, confirm that

S₁² + h * S₂² ≡ M (mod n)

The version of the scheme described here is based on quadratic polynomials. When it was first proposed in [1217], a $100 reward was offered for successful cryptanalysis. It was proved insecure [1255,18], but its authors were not deterred. They proposed a modification of the algorithm based on cubic polynomials, which is also insecure [1255]. The authors then proposed a quartic version, which was also broken [524,1255]. A variant which fixes these problems is in [1134].

20.6 ESIGN

ESIGN is a digital signature scheme from NTT Japan [1205,583]. It is touted as being at least as secure and considerably faster than either RSA or DSA, with similar key and signature lengths.

The private key is a pair of large prime numbers, p and q. The public key is n, when

n = p²q

H is a hash function that operates on a message, m, such that H(m) is between 0 and n – 1. There is also a security parameter, k, which will be discussed shortly.

(1)  Alice picks a random number x, where x is less than pq.

(2)  Alice computes:

w, the least integer that is larger than or equal to

(H(m) – x^k mod n)/pq

s = x + ((w/kx^k - 1) mod p)pq

(3)  Alice sends s to Bob.

(4)  To verify the signature, Bob computes s^k mod n. He also computes a, which is the least integer larger than or equal to two times the number of bits of n divided by 3. If H(m) is less than or equal to s^k mod n, and if s^k mod n is less than H(m) + 2^a, then the signature is considered valid.

This algorithm works faster with precomputation. This precomputation can be done at any time and has nothing to do with the message being signed. After picking x, Alice could break step (2) into two partial steps. The first can be precomputed.

(2a)  Alice computes:

u = x^k mod n

v = 1/(kx^k - 1) mod p

(2b)  Alice computes:

w = the least integer that is larger than or equal to

(H(m) – u)/pq)

s = x + (wv mod p)pq

For the size of numbers generally used, this precomputation speeds up the signature process by a factor of 10. Almost all the hard work is done in the precomputation stage. A discussion of modular arithmetic operations to speed ESIGN can be found in [1625,1624]. This algorithm can also be extended to work with elliptic curves [1206].

Security of ESIGN

When this algorithm was originally proposed, k was set to 2 [1215]. This was quickly broken by Ernie Brickell and John DeLaurentis [261], who then extended their attack to k = 3. A modified version of this algorithm [1203] was broken by Shamir [1204]. The variant proposed in [1204] was broken in [1553]. ESIGN is the current incarnation of this family of algorithms. Another new attack [963] does not work against ESIGN.

The authors currently recommend these values for k: 8, 16, 32, 64, 128, 256, 512, and 1024. They also recommend that p and q each be of at least 192 bits, making n at least 576 bits long. (I think n should be twice that length.) With these parameters, the authors conjecture that ESIGN is as secure as RSA or Rabin. And their analysis shows favorable speed comparison to RSA, ElGamal, and DSA [582].

Patents

ESIGN is patented in the United States [1208], Canada, England, France, Germany, and Italy. Anyone who wishes to license the algorithm should contact Intellectual Property Department, NTT, 1–6 Uchisaiwai-cho, 1-chome, Chiyada-ku, 100 Japan.