 GQ signature scheme

The Guillou-Quisquater (GQ) identification protocol (§10.4.3) can be turned into a digital signature mechanism (Algorithm 11.48) if the challenge is replaced with a one-way hash function. Let h: {0,1}* —» Z„ be a hash function where n is a positive integer.

11.47 Algorithm Key generation for the GQ signature scheme

SUMMARY: each entity creates a public key (?г, e, J,) and corresponding private key o. Entity .4 should do the folio whig:

• 1. Select random distinct secret primes p, q and form n = pq.
• 2. Select an integer e€ {1,2,... ,n—1} such that gcd(e, (p - l)(g - 1)) = 1. (See Note 11.50 for guidance on selecting e.)
• 3. Select an integer ,Ja. 1 < Ja < n, which serves as an identifier for A and such that gcd(./,i, n) = 1. (The binary representation of Ja could be used to convey information about A such as name, address, driver’s license number, etc.)
• 4. Determine an integer a e Zn such that ./да'; = 1 (mod n) as follows:
• 4.1 Compute Jj1 mod n.
• 4.2 Compute d = e-1 mod (p — 1) and d-2 = e 1 mod (q — 1).
• 4.3 Compute ai = (1)dl mod pandas = (•Тд1)**2 mod q.
• 4.4 Find a solution a to the simultaneous congruences а = a (mod p), a = «2
• (mod q).
• 5. A’s public key is (n, e, Ja)', A’s private key is a.
• 11.48 Algorithm GQ signature generation and verification

SUMMARY: entity A signs a binary message m of arbitrary length. Any entity В can verify this signature by using A’s public key.

• 1. Signature generation. Entity A should do the folio whig:
• (a) Select a random integer к and compute r = ke mod n.
• (b) Compute l = /г(т||г).
• (c) Compute s = kal mod n.
• (d) A’s signature for m is the pair (s, l).
• 2. Verification. To verify A’s signature (s, l) on m, В should do the following:
• (a) Obtain A’s authentic public key (n, e, Ja).
• (b) Compute и = .s' ./,/ mod n and l' = /i(m||u).
• (c) Accept the signature if and only if l = V.

Proof that signature verification works. Note that и = VJa = (kal)eJAl = ke(aeJA)1 = ke = r (mod n). Hence, и = r and therefore l = l'.

11.49 Example (GQ signature generation with artificially small parameters)

Key generation. Entity A chooses prunes p = 20849, q = 27457, and computes n = pq = 572450993. A selects an hiteger e = 47, an identifier Ja = 1091522, and solves the congruence J^ae = 1 (mod n) to get a = 214611724. A’s public key is (n = 572450993, e = 47, Ja = 1091522), while A’s private key is a = 214611724.

Signature generation. To sign the message m = 1101110001, A selects a random integer

к = 42134 and computes r = ke mod n = 297543350. A then computes l = /i(m||r) = 2713833 (the hash value has been contrived for this example) and s = ka mod n = (42 1 34)2 146117242713833 mod n = 252000854. A's signature for m is the pair (s = 252000854, l = 2713833).

Signature verification. В computes se mod n = 25200085447 mod n = 398641962, Ja mod n = 10915222713833 mod n = 110523867, and finally и = seJA mod n = 297543350. Since и = r, l' = h(mu) = /i(m||r) = l, and so В accepts the signature. □

• 11.50 Note (security ofGQ signature scheme) In Algorithm 11.47, e must be sufficiently large to exclude the possibility of forger)' based on the birthday paradox (see §2.1.5). The potential attack proceeds along the following hues. The adversary selects a message m and computes l = /г(?п||Тл*) for sufficiently many values of t until l = t (mod e); this is expected to occur within 0(y/e) trials. Having determined such a pair (l, t), the adversary determines an integer x such that t = xe + l and computes s = Jax mod n. Observe that s(.Ja = (Jax)£Ja = JAxe+l = Ja (mod n), and, hence, /i(m||J,4f) = l. Thus, (s, l) is a vahd (forged) signature for message m.
• 11.51 Note (parameter selection) Current methods (as of 1996) for integer factorization suggest that a modulus n of size at least 768 bits is prudent. Note 11.50 suggests that e should be at least 128 bits in size. Typical values for the outputs of secure hash functions are 128 or 160 bits. With a 768-bit modulus and a 128-bit e, the public key for the GQ scheme is 896 + и bits in size, where и is the number of bits needed to represent J a- The private key a is 768 bits in size.
• 11.52 Note (performance characteristics ofGQ signatures) Signature generation for GQ (Algorithm 11.48) requires two modular exponentiations and one modular multiplication. Using a 768-bit modulus n, a 128-bit value e, and a hash function with a 128-bit output l, signature generation (using naive techniques for exponentiation) requires on average 384 modular multiplications (128 squarings and 64 multiplications for each of e and /). Signature verification requires a similar amount of work. Compare this with RSA (naively 1152 modular multiplications) and Feige-Fiat-Shamir (64 modular multiplications) for signature generation (see Note 11.46). GQ is computationally more intensive than Feige-Fiat-Shamir but requires significantly smaller key storage space (see Note 11.51).
• 11.53 Note (message recoverу variant of GQ signatures) Algorithm 11.48 can be modified as follows to provide message recovery. Let the signing space be Ms = Z„, and let m e Ms- bi signature generation, select a random к such that gcd(fc.n) = 1 and compute r = ke mod n and I = mr mod n. The signature is s = ka mod n. Verification gives seJA = keaelJA = ke = r (mod n). Message rn is recovered from lr~ mod n. As for all digital signature schemes with message recovery, a suitable redundancy function R is required to guard against existential forgery.