3
$\begingroup$

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

$\endgroup$
1
  • 1
    $\begingroup$ Interesting question! $\endgroup$
    – Woodstock
    Jul 2, 2020 at 9:10

1 Answer 1

4
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ I still don't understand, why the first Bit has to be a 1. AFAIK the Montgomery Ladder is used for multiplication, which always takes the same amount of time. $\endgroup$
    – Titanlord
    Jul 2, 2020 at 13:06
  • 1
    $\begingroup$ 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. $\endgroup$
    – user69015
    Jul 2, 2020 at 14:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.