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.