Corner cases of addition on short Weierstrass elliptic curves

Question

I am trying to implement arithmetic over points on a short Weierstrass elliptic curve and I have trouble with corner cases of the points addition operation. Let me specify the parameters of the curve and what is the problem exactly:

1. As a test curve I use Bitcoin elliptic curve $y^2 = x^3 + 7$
2. For testing purpose I do integer arithmetic $x\bmod 11$ to keep it simple for debugging purpose
3. I do arithmetic exactly as specified herein Wikipedia

The problem I have is with doubling of the point $(5, 0)$. In the doubling formula, there is a modulo inverse of $y$ point coordinate, that clearly doesn't exist for $(5, 0)$ since $y=0$. So my questions are:

1. How am I supposed to handle this case?
2. Is $x$ or $y$ equal to $0$ even allowed when doing math for short Weierstrass elliptic curves?
3. What is the exact list of corner cases that need to be handled when implementing an addition for short Weierstrass elliptic curve

Currently, my implementation has the following branching in the following order:

1. If one of the arguments in addition operation is the point at infinity, the other argument of operation is returned as the result
2. If one of the arguments is equal to a negative of the second argument result is the point at infinity
3. If arguments in addition operation are equal to each other then doubling formula is used as specified here in Wikipedia
4. Otherwise a basic addition formula is used as specified in Wikipedia

Negation is done by simply negating the $y$ coordinate with the exception that the negation of point at infinity gives back the point at infinity.

How far is this list from being complete? What else needs to be handled for this type of elliptic curve?

For those of you terrified by the fact that some noob is implementing math of an elliptic curve himself have no fear. This is not for practical crypto application, this is just a fun home project, the goal is to understand rather than to get a crypto-ready implementation :)

UPDATE: I used the comment of @corpsfini to update the routine and it turns out that I had an implementation flaw cause with $(5, 0)$ we have a case 2 of my branching scheme since $(5,0)$ is equal to negative of itself. So I fixed the bug and now all the unit tests work fine for $\bmod 11$ and some other random small groups. However the question remains, is it all that's out there? The SafeCurves web site warns that there are some failure cases that might not be disclosed by the random tests and that it's really hard to get them right. What I've coded up so far doesn't seem to be complex at all, yeah a bunch of if/else statements, but not something that I would call hard to get right. I expect that there is something else. Does anybody have an idea?

Answer 1

The Group Law on Affine Coordinates

Arithmetical rules are derived from the line intersection and tangent equations. The formulas are;

Let $P=(x_1,x_2)$ and $Q=(x_2,y_2)$ be two point in the elliptic curve.

1. $P+O=O+P=P$
2. If $x_1 = x_2 $ and $y_1 = - y_2$ and $Q =(x_2,y_2)=(x_1,−y_1)=−P$ then $P + (-P) = O$
3. If $Q \neq -P$ then the addition $P+Q = (x_3,y_3)$ and the coordinate can be calculated by;

\begin{align} x_3 = & \lambda^2 -x_1 - x_2 \mod p\\ y_3 = & \lambda(x_1-x_3) -y_1 \mod p \end{align}

$$ \lambda = \begin{cases} \frac{y_2-y_1}{x_2-x_1}, & \text{if $P \neq Q$} \\[2ex] \frac{3 x_1^2+a}{2y_1}, & \text{if $P = Q$} \\[2ex] \end{cases}$$

I have is with doubling of the point $(5,0)$ ... Is x or y equal to 0 even allowed when doing math for short Weierstrass elliptic curves?

When doubling we look at the tangent line. We have two cases;

1. $y_1 \neq 0$ for $P$, then

   $$x_3 = m^2 - 2x_1, \quad y_3 = m(x_1 -x_3) - y_1,\quad \text{ where } m = \dfrac{3x_p^2 + a}{2y_p}$$

2. $y_1 = 0$ for $P$ then $P + P = [2]P = \mathcal{O}$

$(5,0)$ is the special case that the tangent line is vertical, the 4th case in the top figure. This means that $P+P = \mathcal{O}$ and $P$ has order 2. It also can be seen from the formulas, case 2.

update

This is about the implementation issue that people can forget the checks;

Maybe the implementor instead has "+" check for its inputs being equal. But this is less likely as an implementation strategy: it produces a slower and more complicated implementation. Furthermore, it does not catch all the failure cases. For example, the standard Weierstrass addition formulas fail if Q happens to match -P. This will not be caught by random tests.

and

2007 Bernstein–Lange showed that the Edwards addition law is complete for every complete Edwards curve E. This means that, for every rational point P on E, and for every rational point Q on E, the Edwards addition law for inputs P and Q produces as output exactly P+Q. There are no exceptional cases. The Edwards addition law can be used for complete single-scalar multiplication, complete double-scalar multiplication, etc.

So, one addition law for all!