# Curve25519 key structure

In the paper regarding Curve25519, the set of public keys $$q$$ is $$\{q : q\in \{ 0,1,2,...,2^{256} - 1\}\}$$ and the set of private keys $$n$$ is $$\{n : n\in 2^{254} + 8 \cdot \{ 0,1,2,...,2^{251} - 1\}\}$$.

My main question is: Why is the structure of the public and private keys the way it is?

What I don't understand: In Theorem 2.1., $$q$$ is defined to be an element of $$F_p$$ and $$q$$ is also a parameter in the Curve25519 function: $$Curve25519(n,q) = X_0(nQ) = s$$ with $$X_0 (Q) = q$$. So why does the set of public keys not equal $$\{q : q\in \{ 0,1,2,...,F_p - 1\}\}$$?

• Interesting question! – Woodstock Jul 2 at 9:10

The first one is to make the scalar multiplication with always the same number of iterations of the loop, for constant-time reasons. The second one makes sure that the resulting point belongs to the prime order subgroup: if someone sends a point of small order, then the result of the scalar multiplication will be automatically $$0$$ since the secret key is a multiple of the cofactor (see page 8 of the paper).
For the public key, it is only that any value $$q$$ corresponds to a valid $$x$$-coordinate of a point that belongs either to the curve or its quadratic twist. Of course, you can take them only in $$[0,2^{255}-20]$$, but the main point is that it fits in $$32$$ bytes, and any $$32$$-byte values are valid.
• Montgomery ladder can work if the most significant bits are $0$, but the computation will be useless. However, fixing the top bit makes sure that if a developer uses another algorithm, the bit length of the secret scalar is less likely to be leaked. – corpsfini Jul 2 at 14:57