Standard signatures; signing

• r = H1(z,m);
• H0(r,m) = efs^2 mod pq;
• e is 1 if H0(r,m) is a square modulo q, otherwise -1;
• f is 1 if e H0(r,m) is a square modulo p, otherwise 2;
• s is in {0,1,...,(pq-1)/2}; and
• {s,pq-s} contains a square modulo pq.

Signers are required to generate standard signatures.

How do I sign a message?

1. Compute r = H1(z,m).
2. Compute h = H0(r,m).
3. Compute u = h^{(q+1)/4} mod q.
4. If (u^2-h) mod q = 0, set e = 1; otherwise set e = -1.
5. Compute v = (eh)^{(p+1)/4} mod p.
6. If (v^2-eh) mod p = 0, set f = 1; otherwise set f = 2.
7. Compute w = f^{(3q-5)/4}u mod q. (This takes just one multiplication modulo q, since the signer precomputed 2^{(3q-5)/4} mod q; recall that f is 1 or 2.)
8. Compute x = f^{(3p-5)/4}v mod p. (The signer precomputed 2^{(3p-5)/4} mod p.)
9. Compute y = w + q(q^(p-2)(x-w) mod p). (The signer precomputed q^(p-2) mod p.)
10. Set s = min{y,pq-y}.
11. Print (e,f,r,s).

Note that there are no Euclid-type Jacobi-symbol computations here.

Signers worried about faults in the computation can check at the end that efs^2 mod pq = h. This is very fast, so I recommend that all signers do it. A more thorough double-check is provided by the following alternate algorithm:

1. Compute r = H1(z,m).
2. Compute h = H0(r,m).
3. Compute U = h^{(q+1)/8} mod q.
4. If (U^4-h) mod q = 0, set e = 1; otherwise set e = -1.
5. Compute V = (eh)^{(p-3)/8} mod p.
6. If (V^4(eh)^2-eh) mod p = 0, set f = 1; otherwise set f = 2.
7. Compute W = f^{(3q-5)/8}U mod q.
8. Compute X = f^{(9p-11)/8}V^3 eh mod p.
9. Compute Y = W + q(q^(p-2)(X-W) mod p).
10. Compute y = Y^2 mod pq.
11. Set s = min{y,pq-y}.
12. Check that efs^2 mod pq = h.
13. Print (e,f,r,s).

What is the hash function H1?