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: 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

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.