Mathematical Cryptography

Section 4.2 Elliptic addition on \(E\text{.}\)

Let us briefly describe the generic case of adding two points in an elliptic curve \(E: Y^2 = X^3 + AX + B\text{.}\) Let \(E\) be a curve that doesn't self-intersect, and let \(P, Q \in E\) be distinct points with different \(x\)-coordinates. A fundamental feature of \(E\) is that the line connecting them passes through the curve \(E\) at precisely one additional point \(R\text{.}\) If the point \(R\) has coordinates \(R = (x,y)\text{,}\) then the reflection of \(R\) across the \(x\)-axis is the point \(R' = (x, -y)\text{.}\) We define the sum of \(P\) and \(Q\) in \(E\) by

Let us perform a sample computation. Let \(E: Y^2 = X^3 - 2X + 5\text{,}\) and let \(P = (1, 2)\) and \(Q = (2, -3)\text{.}\) First, we note that the line between \(P\) and \(Q\) has equation \(y = -5x + 7\text{.}\) To find where the line intersects \(E\text{,}\) we substitute in for \(Y\) to get

which looks like a total nightmare to factor. But recall that we already know that \(x = 1\) and \(x = 2\) are roots of this equation. So we can use division to factor, and we get

By plugging in to the line, we get that the point \(R\) on the curve has coordinates \(R = (22, 10609)\text{,}\) and so \(P \oplus Q = R'\) where \(R' = (22, -10609)\text{.}\) Of course, most additions don't result in integer outputs, particularly since square roots are involved. (This is going to need to be addressed before we can use elliptic curves as the basis of cryptographic systems.)

Some questions should present themselves to you.

1. What is \(P \oplus P\text{?}\) After all, there isn't a way to draw a unique line through \(P\) and itself.
2. What happens if we add \(P\) to its reflection \(P'\text{?}\) A vertical line won't intersect \(E\) at a third point.

Both of the questions will need to be addressed in order to establish that the elliptic curve operation \(\oplus\) is actually a group addition.

To answer the first question, imagine that we draw a line from \(P\) to a nearby point \(Q\) and note the intersection \(R\) with the curve \(E\text{.}\) As we slide \(Q\) towards \(P\text{,}\) the line gets closer and closer to the tangent line of the elliptic curve at \(P\text{,}\) and the point \(R\) approaches the intersection of the tangent line at \(P\) with the curve \(E\text{.}\) This is how we define \(P \oplus P\text{.}\) We can use implicit differentiaion to get an expression for the slope of \(E\) at a point \((x,y)\text{.}\)

and so

which gives us the slope of the tangent line at \(P\text{.}\) After writing out the equation of the tangent line, we can use substitution to find the intersection with \(E\) as we did before, but now the \(x\)-coordinate of \(P\) will be double root of the resulting cubic equation.

Finally, we deal with the case of adding a point \(P\) to its reflection \(P'\text{.}\) Since a vertical line will only ever intersect \(E\) at two points, we add a new point \(\mathcal O\text{,}\) called “the point at infinity”, which we imagine to be at the end of every vertical line. Since every vertical line passes through \(\mathcal O\text{,}\) we can use it to fix the problem of \(P \oplus P'\text{.}\) If we take \(P\) and add it to its reflection \(P'\text{,}\) we “intersect” \(E\) at \(\mathcal O\text{.}\) After reflecting \(\mathcal O\) across the \(x\)-axis, we still land at the infinite end of a vertical line, and so we define \(P \oplus P' = \mathcal O\text{.}\)

Since we've introduced a new point, we should see how it interacts with other points and addition. So what is \(P \oplus \mathcal O\text{?}\) The vertical line through \(P\) and \(\mathcal O\) intersects \(E\) at \(P'\text{,}\) the reflection of \(P\text{.}\) When we reflect \(P'\) across the \(x\)-axis, we end up back at \(P\text{.}\) That is to say, \(\mathcal O\) acts like the number 0. In fact, for all \(P\text{,}\) \(P \oplus \mathcal O = P\text{,}\) and so \(\mathcal O\) is the additive identity of the operation \(\oplus\text{.}\)

Putting this together with the fact that \(P \oplus P' = \mathcal O\text{,}\) we see that the reflection \(P'\) of \(P\) is also the additive inverse of \(P\) in the operation \(\oplus\text{.}\) Thus, we can safely use the symbol \(-P = P'\text{,}\) and so we have a notion of subtraction as well. Finally, we denote by \(nP\) the \(n\) times repeated addition \(P \oplus P \oplus \ldots \oplus P\text{.}\)

To summarize, we have shown that the operation \(\oplus\) on \(E\) is well-defined, has an identity, and has inverses. The last required property to be a group operation is that \(\oplus\) must be associative, but to prove that it is would require exhaustive analysis of cases, or deceptively inadequate pictures, or methods that are beyond the scope of this class. For now, we will take it on the assertion of experts that \(\oplus\) is indeed an associative operation.

As we have now shown that elliptic addition follows the structure and rules of integer addition, we will drop the special notation \(P \oplus Q\) and simply refer to elliptic addition with \(+\text{,}\) i.e. \(P + Q\text{.}\)

We also have a natural notion of of a distributive property with respect to repeated addition (this is an exact analogue of the exponent rules in the multiplicative group setting). That is,

and similarly, \((m+n)P = mP + nP\text{.}\)

Finally, we present a set of implementable formulae that allow easy computation of elliptic curve addition.