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 = r^v 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 = rB^d 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´ = D^vJ^d 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: (J_A, B_A) and (J_B, B_B). The values n and v are common to the system.

(1)  Alice picks a random integer, r_A, such that r_A is between 1 and n - 1. She computes T_A = r_A^v mod n and sends T_A to Bob.

(2)  Bob picks a random integer, r_B, such that r_B is between 1 and n - 1. He computes T_B = r_B^v mod n and sends T_B to Alice.

(3)  Alice and Bob each compute T = (T_AT_B) 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 D_A = r_AB_A^d mod n and sends D_A to Bob.

(6)  Bob computes D_B = r_BB_B^d mod n and sends D_B to Alice.

(7)  Alice and Bob each compute D = D_AD_B mod n. The signature consists of the message, M, the two calculated values, d and D, and both of their credentials: J_A and J_B.

(8)  Carol computes J = J_AJ_B mod n.

(9)  Carol computes T´ = D^vJ^d mod n. She then computes d´ = H(M,T´). If d ≡ d´, 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 T_i values together in step (3), and their individual D_i values together in step (7). To verify a multiple signature, multiply all the signers J_i 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 a^q ≡ 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 = a^r 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 2^t - 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 = a^yv^e mod p.

The security is based on the parameter t. The difficulty of breaking the algorithm is about 2^t. 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 = a^r 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^´ = a^yv^e 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.