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.