2
$\begingroup$

According to http://www.secg.org/sec1-v2.pdf#page=13 ,

Rule to add two points with the same x-coordinates when the points are either distinct or have y-coordinate 0:

(x, y) + (x, −y) = O for all (x, y) ∈ E(Fp)

— i.e. the negative of the point (x, y) is −(x, y) = (x, −y).

The fact that it says "when the points are distinct" makes it sound like it applies when the x coordinates of both points match but the y coordinates do not.But if that's the case then it seems to me that that'd make the "or have y-coordinate 0" bit redundant? y is not equal to -y so it seems to me that that's redundant? I mean, I guess y is equal to -y over mod p but in ECC is it even worthwhile to handle the use case where x or y are greater than p?

And what about adding (x, 0) to itself? At that point do we do point doubling, since the points are the same or do we just return 0 because of the "or have y-coordinate 0" bit?

If y was 0 I guess you'd be doing $\frac{\mathbb{3x}_{1}^2 + a}{2y_1}$ or $\frac{\mathbb{3x}_{1}^2 + a}{0}$ so it seems like it might be good to avoid it all together by returning $\mathcal O$ but idk.

And plus, using that rationale then what is supposed to be done for when the two coordinates are different? At that point $\lambda$ is $\frac{y_2 - y_1}{x_2 - x_1}$ so what if both x coordinates match whilst the y coordinates didn't? At that point you'd have another division by zero error..

$\endgroup$
  • $\begingroup$ A note on terminology: it is an "elliptic curve", not an "elliptical curve" (it's not an uncommon mistake)! $\endgroup$ – CurveEnthusiast Sep 21 '17 at 21:19
2
$\begingroup$

Addition of a point with itself is "just" the limit case of normal addition. Geometrically, point addition starts with a line that goes through the two points to add; point doubling uses the tangent to the curve on that point, which is what you expect to have when the two points are made very close to each other.

In that geometric interpretation, the tangent to the curve on a point $P = (x,0)$ is vertical, and thus won't intersect the curve anywhere else; or, more accurately (using projective geometry terminology), that vertical line meets the curve again only at infinity. The sum of $(x,0)$ with itself is thus the point at infinity. This also means that $(x,0)$ is its own opposite.

Now, in cryptography, we use curves in finite fields, which are discrete and don't look like curves. One interesting point to make is that a point $P = (x,0)$ is such that $2P = \mathcal{0}$, i.e. it is a point of order 2. Since an elliptic curve is a group, if there is a point of order 2, then the total curve order must be a multiple of 2. Many standard curves (e.g. the very widespread NIST curve P-256) have been chosen to have a prime order, hence odd; it follows that, for such curves, there is no point $(x,0)$, and the question of doubling such a point does not arise at all.

$\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.