SCHNORR DIGITAL SIGNATURE SCHEME
As with the ElGamal digital signature scheme, the Schnorr signature scheme is based on discrete logarithms . The Schnorr scheme minimizes the message-dependent amount of computation required to generate a signature. The main work for signature generation does not depend on the message and can be done during the idle time of the processor. The message-dependent part of the signature generation requires multiplying a 2n-bit integer with an n-bit integer.
The scheme is based on using a prime modulus p, with p - 1 having a prime factor q of appropriate size; that is, p - 1 == (mod q). Typically, we use p ~~ 21024 and q ~ 2160. Thus, p is a 1024-bit number, and q is a 160-bit number, which is also the length of the SHA-1 hash value.
The first part of this scheme is the generation of a private/public key pair, which consists of the following steps.
1. Choose primes p and q, such that q is a prime factor of p - 1.
2. Choose an integer a, such that aq = 1 mod p. The values a, p, and q comprise a global public key that can be common to a group of users.
3. Choose a random integer s with 0 < s < q. This is the user’s private key.
4. Calculate v = a - s mod p. This is the user’s public key.
A user with private key s and public key v generates a signature as follows.
1. Choose a random integer r with 0 < r < q and compute x = armod p. This computation is a preprocessing stage independent of the message M to be signed.
2. Concatenate the message with x and hash the result to compute the value e:
3. Compute y = (r + se) mod q. The signature consists of the pair (e, y).
Any other user can verify the signature as follows.
1. Compute x' = ayve mod p.
2. Verify that e = H(M || x').
To see that the verification works, observe that
Hence, H(M || x') = H(M || x).