Curve25519 key structure

Question

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\}\}$?

Answer 1

From the same paper:

• Use a fixed position for the leading 1 in the secret key;
• Multiply the secret key by a small power of 2 to account for cofactors in the curve group and the twist group.

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.