Given that valid private keys on curve25519 must be less than the order of the curve which is (as I understand) already smaller than 2^256, AND a valid key must be clamped to be divisible by 8 and have its high bit set, what is the actual 2^X number of valid private keys approx?


The private keys are integers $x$ with $2^{254} \leq x < 2^{255}$ and $x \equiv 0 \pmod 8$, or just $x \in 2^{254} + 8\{0,1,2,\dots,2^{251} - 1\}$, so there are exactly $2^{254}/8 = 2^{251}$ of them.

| improve this answer | |
  • $\begingroup$ Thank you! After factoring in efficient approaches on attacking DLP, curve25519 must have at best <126bit security. Seems low? $\endgroup$ – Woodstock Jun 7 '19 at 22:15
  • 1
    $\begingroup$ When humanity has spent $2^{100}$ computing cycles in its entire history (which I don't think it has yet), it'll still take millions of times the computing cost spent in the history of humanity to break one X25519 key, so no, that's not really low. The cost of performing a curve addition is quite a few bit operations, so you can read that to bring the cost in bit operations up to $2^{128}$. $\endgroup$ – Squeamish Ossifrage Jun 7 '19 at 22:18

Your Answer

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

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