 The Schnorr signature scheme

Another well-known variant of the ElGamal scheme (Algorithm 11.64) is the Schnorr signature scheme. As with the DSA (Algorithm 11.56), this technique employs a subgroup of order q in Z*, where p is some large prime number. The method also requires a hash function h : {0,1}* —» Zq. Key generation for the Schnorr signature scheme is the same as DSA key generation (Algorithm 11.54), except that there are no constraints on the sizes of p and q.

11.78 Algorithm Schnorr signature generation and verification

• 2. Verification. To verify A’s signature (s, e) on m, В should do the following:
• (a) Obtain .4’s authentic public key (p, q, a, y).
• (b) Compute v = asy~e mod p and e' = /r(m||u).
• (c) Accept the signature if and only if e' = e.

Proof that signature verification works. If the signature was created by A, then v = asy~e = asa~ae = ak = r (mod p). Hence, /i(m||v) = /i(m||r) and e' = e.

11.79 Example (Sclinorr’s signature scheme with artificially small parameters)

Key generation. A selects primes p = 129841 and q = 541; here, (p - 1 )/q = 240. A then selects a random integer у = 26346 e Z* and computes a = 26 3 46240 mod p = 26. Since q Ф 1, a generates the unique cyclic subgroup of order 541 in Z*. A then selects the private key a = 423 and computes у = 26423 mod p = 115917. A’s public key is (p = 129841, q = 541, a = 26, у = 115917).

Signature generation. To sign the message m = 11101101, A selects a random number к = 327 such that 1 < к < 540, and computes r = 26327 mod p = 49375 and e = h(m ) = 155 (the hash value has been contrived for this example). Finally, A computes s = 423 • 155 + 327 mod 541 = 431. The signature for m is (s = 431, e = 155). Signature verification. В computes v = 26431 • 1159 1 7 155 mod p = 49375 and e' = /i(m||v) = 155. В accepts the signature since e = e'.

11.80 Note (performance characteristics of the Schnorr scheme) Signature generation in Algorithm 11.78 requires one exponentiation modulo p and one multiplication modulo q. The exponentiation modulo p could be done off-line. Depending on the hash algorithm used, the time to compute /i(m||r) should be relatively small. Verification requires two exponentiations modulo p. These two exponentiations can be computed by Algorithm 14.88 at a cost of about 1.17 exponentiations. Using the subgroup of order q does not significantly enhance computational efficiency over the ElGamal scheme of Algorithm 11.64, but does provide smaller signatures (for the same level of security) than those generated by the ElGamal method.