# 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*Z_{n}such that ./да'^{;}= 1 (mod*n)*as follows: - 4.1 Compute Jj
^{1}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 = k*mod^{e}*n.* - (b) Compute
*l =*/г(т||г). - (c) Compute
*s = ka*mod n.^{l} - (d) A’s signature for m is the pair (s,
*l).*

- (a) Select a random integer
- 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.*

- (a) Obtain A’s authentic public key (n,

*Proof that signature verification works.* Note that *и = VJa =* (*ka ^{l})^{e}JA^{l} = k^{e}(a^{e}JA)^{1 }*

*=*

*k*

^{e}*= 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^a^{e} = 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 = *k ^{e}* 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 14611724

^{2713833}mod

*n*= 252000854.

*A's*signature for

*m*is the pair (s = 252000854,

*l*= 2713833).

*Signature verification. В* computes *s ^{e}* mod

*n =*252000854

^{47}mod n = 398641962, Ja mod

*n*= 1091522

^{2713833}mod

*n =*110523867, and finally

*и*=

*s*mod n = 297543350. Since

^{e}J_{A}^{}*и = 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*= Ja^{x}mod*n.*Observe that s^{(}.Ja*=*(Ja^{x})^{£}Ja =*J*= Ja (mod n), and, hence, /i(m||J,4_{A}^{xe+l}^{f}) =*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 = k*mod^{e}*n*and*I = mr*mod*n.*The signature is*s*=*ka*mod^{}*n.*Verification gives*s*(mod^{e}J_{A}= k^{e}a^{el}JA = k^{e}= r*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.