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?
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
2
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.
answered Jun 7, 2019 at 18:27
-
$\begingroup$ Thank you! After factoring in efficient approaches on attacking DLP, curve25519 must have at best <126bit security. Seems low? $\endgroup$ Commented Jun 7, 2019 at 22:15
-
2$\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$ Commented Jun 7, 2019 at 22:18