I'm especially curious about the technique djb would have used to come up with his Curve 25519. Say I have already written down my goals, such as - Twist Secure, Speed, Side Channel resistance, etc. In this case, how do I go about creating new curves? Are there specific algorithms that Cryptographers / Mathematicians use? Or is it just improvising on similar work?

up vote 8 down vote accepted

As you said, you need to define the goals. You can take a look at SafeCurves, which is a joint work by Bernstein and Lange to help choose/construct elliptic curves w.r.t. ECDLP difficulty and ECC security. Note that if you need a pairing-friendly elliptic curve you need to look at other criteria related to the embedding degree. You can read this paper by Freeman et al. for different constructions. Now talking about Curve25519, Bernstein explained his choices in his paper. These are some of the main points he mentioned in a talk:

  • Curve25519 has a large prime char field because current CPU multipliers include fast floaing-point multipliers and extension fields punish CPUs with another multiplier size.
  • Curve25519 has a Montgomery shape $y^2=x^3+Ax^2+x$ with tiny $A \in 2+4\mathbb{Z}$ because one can do projective $x$-coordinate doubling and addition together using 1 field multiplication by $(A-2)/4$, 4 field squarings and 5 extra field multiplications without needing $y$ coordinate.
  • Curve25519 uses prime very close to a power of 2. Specifically, $2^{255}-19$ instead of a Solinas prime like $2^{256}-2^{224}+2^{192}+2^{96}-1$ because repeated addition is more costly than multiplication by 19.
  • Curve25519 uses a secure curve of order $8 \times \text{prime}$ with a secure twist $y^2=x^3+486662x^2+x$ of order $4\times \text{primes}$.
  • The $A$ is chosen so that $(A-2)/4$ is a small integer to speed up multiplication by $(A-2)/4$ (formulas here) and so that the twisted curve order is either $4 \times primes$ or $8 \times primes$. The smallest positive choices were then 358990, 464586 and 486662. Bernstein rejected 358990 and 464586 because one of their prime factors is slightly smaller than $2^{252}$ and discussing the question on how one should handle the theoretical possibility of a secret key matching the prime is harder than simply moving to the last choice $A=486662$ (Nothing up my sleeve).
  • 1
    Is 486662 really a NUMS number? It was chosen based on its objective mathematical properties. – forest Dec 8 at 5:14
  • 1
    it is considered a NUMS with respect to the two other choices, but not a NUMS in general. – Youssef El Housni Dec 9 at 11:32
  • Thanks a lot for the explanation. Really appreciate the details @YoussefElHousni I also came across this interesting paper on deterministic generation of EC. eprint.iacr.org/2014/130.pdf – Cookies Dec 11 at 5:22

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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