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.