D. J. Bernstein
Authenticators and signatures
A state-of-the-art public-key signature system
Secret keys; public keys
The signer's secret key has three pieces:
- A prime number p in the interval [2^767,2^768-1] such that p mod 8 = 3.
- A prime number q in the interval [2^768,2^769-1] such that q mod 8 = 7.
- A 256-bit string z.
The signer's public key is the product pq,
which is required to be in the interval [2^1536,2^1537-1],
and more precisely in the interval [(2^512)c,(2^512)(c+1)-1],
where c is a
public constant.
How do I encode a public key as a string of bytes?
The standard format is 64 bytes: pq mod 2^512 in little-endian form.
Receivers recover pq as (pq mod 2^512) + c.
How do I generate a secret key?
The general idea is to choose a random number p0;
divide it into 2^512 (c+1/2) to obtain q0;
find integers x,y up to about 2^256
with p0 y + q0 x close to 2^512 (c+1/2) - p0 q0;
set p = p0 + x and q = q0 + y;
and then try again if p or q isn't prime.
A more detailed procedure will appear here soon.
The signer then generates the 256-bit string z.
The signer also computes the secrets
q^(p-2) mod p,
2^((3p-5)/4) mod p, and
2^((3q-5)/4) mod q,
which are used together with p,q,z in computing signatures.
How do I encode a secret key as a string of bytes?
The standard format is
- 32 bytes: z in little-endian form;
- 96 bytes: bits 0...767 of q in little-endian form;
- 96 bytes: bits 0...766 of p in little-endian form,
followed by bit 768 of 2^((3q-5)/4) mod q;
- 96 bytes: q^(p-2) mod p in little-endian form;
- 96 bytes: 2^((3p-5)/4) mod p in little-endian form; and
- 96 bytes: bits 0...767 of 2^((3q-5)/4) mod q in little-endian form.
Bit 767 of p and bit 768 of q are always 1,
so those bits are not stored.