2
$\begingroup$

I'm trying to sum up all Curve25519 parameter and specification reasons. Can you tell me if I missed some important reasons or parameters in the following list?:

  • Curve: Montgomery Curve. $M_{A,B}: By^2 = x^3 + Ax^2 + x$

    Reason: The projective arithmetic for scalar multiplication (Montgomery ladder) is very fast.

  • Parameter $A = 486662$.

    Reason: $A$ should be as small as possible but still provides an order for the elliptic curve, which is bigger than every private key ($256$ bit length). The order should be $ n \cdot p$ with $p$ being a big prime and $n \in {4,8}$ (the reasons for this is the order of Montgomery curves in general). The order of the twisted curve should have an equal form (security reasons).

  • Parameter $p = 2^{255} \text{- } 19$.

    Reason: The curve is defined over a prime field with the prime $p$. $p$ should be close to the power of $2$ to make use of a fast modulo computation. See this post.

  • Public keys $ q\in \{ 0,1,2,\ldots,2^{256} - 1\}$.

    Reason: Every $32$ byte shall be possible, so you don't need to validate the public keys (faster). Theorem 2.1. states, that this is possible (Using extension fields).

  • Private keys $ n\in 2^{254} + 8 \cdot \{ 0,1,2,...,2^{251} - 1\}$.

    Reason: Not every $32$ byte is a good key. For security reasons, the last $3$ bits should be $0$ (this prevents subgroup attacks). To prevent side-channel attacks using other scalar multiplication than Montgomery ladder, the first bit should be $1$.

  • Base point $P = (9, y)$.

    Reason: To prevent small subgroup attacks, the base point has to have a big prime order. Also, for nothing-up-my-sleeve number the first $x$ satisfying the curve equation that is in the large prime order is chosen.

$\endgroup$
8
  • 3
    $\begingroup$ Actually, not every public key is possible. This can be easily show by seeing that there are only $2^{251}$ private keys, and that there is a one-to-one mapping between private keys and public keys. $\endgroup$ – poncho Jul 6 '20 at 14:07
  • $\begingroup$ So you mean that not every public key can be produced used the standard curve25519 key exchange, because there is a unique public key to every private key? But every 32 byte number can still be interpreted as a valid public key? $\endgroup$ – Titanlord Jul 6 '20 at 14:27
  • 1
    $\begingroup$ If you update this question with the comments, it will be better for the community. $\endgroup$ – kelalaka Jul 6 '20 at 18:09
  • 1
    $\begingroup$ What @poncho means is that the set of available private keys is larger than the set of private keys, which means that if you generate a list every possible public key from every possible private key, you will still have points on the curve that are not on that list. I think Bernstein means something different, which is that these points act as a valid public key, but they don't necessarily have an associated private key. $\endgroup$ – The Quantum Physicist Jul 7 '20 at 12:54
  • 1
    $\begingroup$ @TheQuantumPhysicist: however, there are a few values that generate tiny groups; the value $0$ is one example (which generates a group consisting of one point); there are a few others that generate small groups. Again, I don't believe those would be considered valid public keys... $\endgroup$ – poncho Jul 7 '20 at 13:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.