Applied Cryptography, Second Edition: Protocols, Algorthms, and Source Code in C (cloth)
(Publisher: John Wiley & Sons, Inc.)
Author(s): Bruce Schneier
ISBN: 0471128457
Publication Date: 01/01/96

Guillou-Quisquater Signature Scheme

This identification can be converted to a signature scheme, also suited for smart-card implementation [671,672].

The public and private key setup is the same as before. Here’s the protocol:

(1)  Alice picks a random integer r, such that r is between 1 and n - 1. She computes T = rv mod n.
(2)  Alice computes d = H(M,T), where M is the message being signed and H(x) is a one-way hash function. The d produced by the hash function must be between 0 and v - 1 [1280]. If the output of the hash function is not within this range, it must be reduced modulo v.
(3)  Alice computes D = rBd mod n. The signature consists of the message, M, the two calculated values, d and D, and her credentials, J. She sends this signature to Bob.
(4)  Bob computes T´ = DvJd mod n. He then computes d´ = H(M,T´). If d = d´, then Alice must know B and the signature is valid.

Multiple Signatures

What if many people want to sign the same document? The easy solution has each of them signing separately, but this signature scheme can do better than that. Here Alice and Bob sign the same document and Carol verifies the signatures, but any number of people can be involved in the signature process. As before, Alice and Bob have their own unique J and B values: (JA, BA) and (JB, BB). The values n and v are common to the system.

(1)  Alice picks a random integer, rA, such that rA is between 1 and n - 1. She computes TA = rAv mod n and sends TA to Bob.
(2)  Bob picks a random integer, rB, such that rB is between 1 and n - 1. He computes TB = rBv mod n and sends TB to Alice.
(3)  Alice and Bob each compute T = (TATB) mod n.
(4)  Alice and Bob each compute d = H(M,T), where M is the message being signed and H(x) is a one-way hash function. The d produced by the hash function must be between 0 and v - 1 [1280]. If the output of the hash function is not within this range, it must be reduced modulo v.
(5)  Alice computes DA = rABAd mod n and sends DA to Bob.
(6)  Bob computes DB = rBBBd mod n and sends DB to Alice.
(7)  Alice and Bob each compute D = DADB mod n. The signature consists of the message, M, the two calculated values, d and D, and both of their credentials: JA and JB.
(8)  Carol computes J = JAJB mod n.
(9)  Carol computes T´ = DvJd mod n. She then computes d´ = H(M,T´). If dd´, then the multiple signature is valid.

This protocol can be extended to any number of people. For multiple people to sign, they all multiply their individual Ti values together in step (3), and their individual Di values together in step (7). To verify a multiple signature, multiply all the signers Ji values together in step (8). Either all the signatures are valid or there is at least one invalid signature.

### 21.3 Schnorr

Claus Schnorr’s authentication and signature scheme [1396,1397] gets its security from the difficulty of calculating discrete logarithms. To generate a key pair, first choose two primes, p and q, such that q is a prime factor of p - 1. Then, choose an a not equal to 1, such that aq ≡ 1 (mod p). All these numbers can be common to a group of users and can be freely published.

To generate a particular public-key/private-key key pair, choose a random number less than q. This is the private key, s. Then calculate v = a-s mod p. This is the public key.

Authentication Protocol

(1)  Peggy picks a random number, r, less than q, and computes x = ar mod p. This is the preprocessing stage and can be done long before Victor is present.
(2)  Peggy sends x to Victor.
(3)  Victor sends Peggy a random number, e, between 0 and 2t - 1. (I’ll discuss t in a moment.)
(4)  Peggy computes y = (r + se) mod q and sends y to Victor.
(5)  Victor verifies that x = ayve mod p.

The security is based on the parameter t. The difficulty of breaking the algorithm is about 2t. Schnorr recommended that p be about 512 bits, q be about 140 bits, and t be 72.

Digital Signature Protocol

Schnorr can also be used as a digital signature protocol on a message, M. The public-key/private-key key pair is the same, but we’re now adding a one-way hash function, H(M).

(1)  Alice picks a random number, r, less than q, and computes x = ar mod p. This computation is the preprocessing stage.
(2)  Alice concatenates M and x, and hashes the result:
e = H(M,x)
(3)  Alice computes y = (r + se) mod q. The signature is e and y; she sends these to Bob.
(4)  Bob computes x´ = ayve mod p. He then confirms that the concatenation of M and x´ hashes to e.
e = H(M,x´)
If it does, he accepts the signature as valid.

In his paper, Schnorr cites these novel features of his algorithm:

Most of the computation for signature generation can be completed in a preprocessing stage, independent of the message being signed. Hence, it can be done during idle time and not affect the signature speed. An attack against this preprocessing stage is discussed in [475], but I don’t think it’s practical.

For the same level of security, the length of signatures is less for Schnorr than for RSA. For example, with a 140-bit q, signatures are only 212-bits long, less than half the length of RSA signatures. Schnorr’s signatures are also much shorter than ElGamal signatures.

Of course, practical considerations may make even fewer bits suitable for a given scheme: For example, an identification scheme where the cheater must perform an on-line attack in only a few seconds, versus a signature scheme where the cheater can calculate for years off-line to come up with a forgery.

A modification of this algorithm, by Ernie Brickell and Kevin McCurley, enhances its security [265].

Patents

Schnorr is patented in the United States [1398] and in many other countries. In 1993, PKP acquired the worldwide rights to the patent (see Section 25.5). The U.S. patent expires on February 19, 2008.

### 21.4 Converting Identification Schemes to Signature Schemes

There is a standard method of converting an identification scheme into a signature scheme: Replace Victor with a one-way hash function. The message is not hashed before it is signed; instead the hashing is incorporated into the signing algorithm. In principle, this can be done with any identification scheme.

[an error occurred while processing this directive]