6
$\begingroup$

I've been reading about the famous X25519, a montgomery curve from wikipedia and in that article they say that we do not have to check for point validity. Is it because that any $x < p$ satisfy the curve equation ? Is this possible for X25519 because it is a Montgomery curve or because it was specifically designed to do so (for the sake of efficiency, and more possibilities for public keys) by its discoverer Dan Bernstein ? Why every $x < p $ does not satisfy the curve equation for other curves like SECP256k1, where the equations are of the Weierstrass form, $y^2 = x^3 + ax + b \mod p $ ? I would really like to know the mathematical reasons behind it. Thankyou everyone in advance!

$\endgroup$
5
$\begingroup$

If you have an elliptic curve given by the equation $y^2 = f(x) \bmod p$, then for each $x$, either $f(x)$ is a square modulo $p$, and there exists a square root $y$ such that $(x,y)$ and $(x,-y)$ satisfy the curve equation. If $f(x)$ is not a square modulo $p$, then this value $x$ does not correspond to a point on the curve, but to a point on the quadratic twist of the curve.

Therefore knowing only $x$, we know it corresponds to a point on the curve or its quadratic twist. The thing is that many standardized curves have a weak quadratic twist (see this page on SafeCurves so it is mandatory to check the point is on the curve, and if we use only the $x$-coordinate, we still need to check it is not on the quadratic twist to avoid invalid curve attacks.

Dan Bernstein designed X25519 as a Diffie-Hellman function using Curve25519 in its Montgomery form. On this curve, the Montgomery ladder scalar multiplication is efficient and uses only the $x$-coordinate of the points. Then, manipulated points lie on the curve or its quadratic twist which is as secure as the original curve. Then any $x$ is valid, but does not necessarily correspond to a point on the curve.

| improve this answer | |
$\endgroup$

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.