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!
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
5
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.
-
1$\begingroup$ Thankyou, for your answer! Can you please show me from where I can learn how the standard equations for point addition / doubling are mathematically derived. Programmatically implementing them was easy but I would really like to know the math behind it in simple ways and why all those same equations are valid modulo p $\endgroup$ Commented Feb 9, 2020 at 11:05
-
1$\begingroup$ You mean: there exist $y$, whose square is $f(x)$. $\endgroup$– kelalakaCommented Feb 9, 2020 at 14:01
-
$\begingroup$ @kelalaka Yes, only then the curve equation can be satisfied. $\endgroup$ Commented Feb 9, 2020 at 14:16
-
1$\begingroup$ @VivekanandV A start would be to take a look at Christof Paar's lectures. I started with this years ago when I became interested in cryptography. You can also watch DJB and Tanja Lange introduction to elliptic curves explaining how it works starting from clocks to Edwards form of elliptic curves. Finally, the book Elliptic Curves, Number Theory and Cryptography has more technical details (see chapter 2 for basics). $\endgroup$– user69015Commented Feb 9, 2020 at 15:00
-
2$\begingroup$ Historical note: Originally, X25519 was called Curve25519, but now Curve25519 just means the elliptic curve and X25519 means the cryptosystem. $\endgroup$– kelalakaCommented Feb 10, 2020 at 17:42