D. J. Bernstein

Authenticators and signatures

A state-of-the-art public-key signature system
# Standard signatures; signing

The **standard signature** of a message m
under a secret key (p,q,z) is the unique
signature (e,f,r,s)
such that
- 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.

Here H1 is the hash function specified below,
producing outputs in {0,1,...,15}.
Signers are required to generate standard signatures.

## How do I sign a message?

The signer can compute the standard signature of a message m
with Algorithm 3.1 of my rwtight paper:
- Compute r = H1(z,m).
- Compute h = H0(r,m).
- Compute u = h^{(q+1)/4} mod q.
- If (u^2-h) mod q = 0, set e = 1; otherwise set e = -1.
- Compute v = (eh)^{(p+1)/4} mod p.
- If (v^2-eh) mod p = 0, set f = 1; otherwise set f = 2.
- 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.)
- Compute x = f^{(3p-5)/4}v mod p.
(The signer precomputed 2^{(3p-5)/4} mod p.)
- Compute y = w + q(q^(p-2)(x-w) mod p).
(The signer precomputed q^(p-2) mod p.)
- Set s = min{y,pq-y}.
- Print (e,f,r,s).

The correctness of this algorithm
is proven in Theorem 3.2 of my rwtight paper.
Of course,
other algorithms that produce exactly the same output are acceptable.
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:

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

## What is the hash function H1?

H1(z,m) is the first four bits of SHA-160L(1,z,m).