D. J. Bernstein

Authenticators and signatures

A state-of-the-art public-key signature system
# Signatures; verification

A **signature** of a message m under a public key pq has four pieces:
- An integer e in {1,-1}.
- An integer f in {1,2}.
- An integer r in {0,1,...,15}.
- An integer s in {0,1,...,2^1536-1}.

The pieces satisfy the equation H0(r,m) = efs^2 mod pq.
Signers are actually required to generate s
in the smaller interval [0,(pq-1)/2],
but verifiers do not need to bother checking for this.

Note that there are also
compressed
and
expanded
forms of signatures.

Note that,
starting from a signature (e,f,r,s) and public key pq,
one can recover H0(r,m),
and thus recover the first 171 bytes of m;
so m can be compressed if the signature and public key are available.
However,
if m is below 96 bytes,
compressed signatures save more space.

## How do I encode a signature as a string of bytes?

The standard format is
- 192 bytes: s in little-endian form.
- 1 byte: r, plus 16 if e=-1, plus 32 if f=2; two bits unused.

## How do I verify a signature?

Square s, multiply by e and f,
divide by pq,
and check that the remainder equals H0(r,m).
Alternatively:
Square s, multiply by e and f, subtract H0(r,m),
and check that the difference is divisible by pq.