BTC#: Elliptic Curve Point Addition

Series: BTC# – Learning to Program Bitcoin in C#

« Previous: BTC#: Elliptic Curves

Next: Elliptic Curves over Finite Fields »

Point Addition

The elliptic curve points we’ve modelled with the code in the previous post represent points (x, y) on the curve. Adding points together is going to form the basis of our elliptic curve cryptography maths. However, elliptic curve point addition is not a lot like the vector addition you’ve seen elsewhere. We don’t just add the xs and ys.

Elliptic curve point addition is an operation on two point that results in a third. However, it doesn’t work the way you might intuitively think. We don’t just add the xs and ys. There are various rules for point addition depending on the relationship of the two points to be added.

PointAddition.png

The meaning of each of these cases is covered in the book.

The Point At Infinity

In the previous post where I created the EllipticCurvePoint class, I said that I’d made the y parameter nullable. This is to model the idea of “the point at infinity”. A vertical line intersecting the curve twice is regarded as also passing through the point at infinity.

public bool AtInfinity
{
    get { return !Y.HasValue; }
}

The point at infinity act as the identity in point addition, meaning that any point plus the point at infinity results in itself

A + I = A

and that any point added to its inverse, i.e. any point minus itself, results in the point at infinity

A + (-A) = I

This gives us the first couple of cases to model for our addition operator.

public static EllipticCurvePoint operator +(EllipticCurvePoint p1, EllipticCurvePoint p2)
{
    //At least one of the points is at infinity
    //This is the identity operation for addition so return the other point.
    if (p1.AtInfinity) return p2;
    if (p2.AtInfinity) return p1;

    //Same x, different y (or same y and tangent is vertical),
    //meaning that the line is vertical.
    //Return the point at infinity.
    if ((p1.X == p2.X && p1.Y != p2.Y) || (p1 == p2 && p1.TangentIsVertical))
    {
        return new EllipticCurvePoint(p1.X, null, p1.A, p1.B);
    }

    //More code here later...
}

Remaining Cases

There are two situations left that we need to handle, the addition of two points with different xs, and the addition of a point to itself. In the first case we need to find the line between the two points and find where else it intersects the curve, as in graph 1 above. In the second case we need to find the tangent to the point and see where that line intersects the curve, as in graph 2.

The derivation of the formulae for finding the gradients of these lines and, from there, where they intersect with the curve is somewhat involved and covered in detail in the book.

It’s worth reading through the explanations in the book, because repeated point addition on the bitcoin elliptic curve will be used later, in the cryptography section, to generate signatures.

With the formulae derived we can implement the rest of the addition operator.

public static EllipticCurvePoint operator +(EllipticCurvePoint p1, EllipticCurvePoint p2)
{
    //Previous code in here.

    //Where p1 coincides with p2, find the slope of the tangent.
    //Otherwise find the slope of the line between the points
    var slope = (p1 == p2)
        ? p1.SlopeOfTangent
        : (decimal)(p2.Y.Value - p1.Y.Value) / (p2.X - p1.X);
    var x3 = slope * slope - p1.X - p2.X;
    var y3 = slope * (p1.X - x3) - p1.Y.Value;

    return new EllipticCurvePoint((int)x3, (int)y3, p1.A, p1.B);
}

There are tests to cover each scenario.

[TestMethod]
public void operatorAddition_twoPointsReturnTheThird()
{
    var a = new EllipticCurvePoint(2, 5, 5, 7);
    var b = new EllipticCurvePoint(-1, -1, 5, 7);
    var c = new EllipticCurvePoint(3, -7, 5, 7);

    Assert.AreEqual(c, a + b);
}

Of course, as good TDD practitioners, the tests were written first.

Next time, I’ll combine the FiniteFieldElement with the elliptic curve code.

« Previous: BTC#: Elliptic Curves

Next: Elliptic Curves over Finite Fields »

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s