BTC#: Elliptic Curves over Finite Fields

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

« Previous: Elliptic Curve Point Addition

Next: The Bitcoin Curve »

Coding for elliptic curves over finite fields is the target of our work so far. In Programming Bitcoin, Song just passes FieldElement objects into Point’s constructor and lets the Python interpreter’s type inference do the rest. The mathematical code in the Point class just calls the operator functions defined on FieldElement instead of the integer versions.

In the strictly typed world of C#, we don’t get that luxury. There’s no interface or other generic type constraint common to our FiniteFieldElement and Int32, so I’ve written a new class, EllipticCurveFiniteFieldPoint. (Get the repo.)

New Types

The code is very similar. The major difference is that the constructor takes BigInteger arguments and creates FiniteFieldElement properties from them.

I’ve deviated from the book by splitting the point class in two, into a point class and a curve class. They’re two different things in my mind and so I’ve modelled them as two different things in the code.

The curve class, EllipticCurveOverFiniteField, is created by supplying the A and B parameters for the elliptic curve and the order of the finite field.

public EllipticCurveOverFiniteField(BigInteger a, BigInteger b, BigInteger order)

The coefficients A and B are converted to FiniteFieldElements of the right order.

The point class, EllipticCurveFiniteFieldPoint, takes the x and y coordinates of the point and the curve that they’re supposed to appear on.

public EllipticCurveFiniteFieldPoint(BigInteger x, BigInteger? y, EllipticCurveOverFiniteField curve)

A point can also be created by calling GetPoint(x, y) on the curve.

public EllipticCurveFiniteFieldPoint GetPoint(BigInteger x, BigInteger? y)
{
    return new EllipticCurveFiniteFieldPoint(x, y, this);
}

I migrated the unit tests to the new types so we can confirm that nothing got broken in translation.

Scalar Multiplication

Scalar multiplication is just repeated addition. If we have a point G then

2G = G + G

and

3G = G + G + G

etc.

One of the reasons this is so relevant to cryptography is because multiplication and division are asymmetric. Song describes what’s called the “discrete log problem”: why point division is not easy.

I won’t repeat it here but think of it in the same way that multiplication is easy whereas factorisation, finding the numbers that were multiplied together to get a product, is much harder.

Cryptonomicon2701Quote.png

For example, calculating 37 x 73 is easy. If you were just given the number 2701, you’d have to try all of the options to find the answer. The bigger the product gets, the slower that process gets.

It’s also worth reading and understanding this section to understand “finite cyclic groups”, which are important to the cryptography that’s coming up next.

Two Python implementations are given in Programming Bitcoin, a naïve repeated addition function and a much faster binary expansion implementation.

In binary expansion, the scalar coefficient is considered in binary form and if the least significant bit is set, the current multiple is added to the accumulating result. Each round the current multiple is doubled and the coefficient is bit-shifted to the right so the next most significant bit is considered next time.

Multiplying G by 45 using repeated addition would take 45 times round a loop. With binary expansion it takes 6.

BinaryExpansion.png

To multiply by a billion would take 30 loops. (1,000,000,000 is a 30-bit number in binary.)

Here’s the C# version

public static EllipticCurveFiniteFieldPoint operator *(BigInteger s, EllipticCurveFiniteFieldPoint p)
{
    var coefficient = s % p.Curve.Order;
    var currentMultiple = p;
    var result = new EllipticCurveFiniteFieldPoint(0, null, p.Curve);

    //Binary expansion to multiply in log time.
    while (coefficient > 0)
    {
        if((coefficient & 1) > 0)
        {
            result += currentMultiple;
        }
        currentMultiple += currentMultiple;
        coefficient >>= 1;
    }
    return result;
}

In the C# version, because we’re multiplying two different types, we also need to override the operator with the arguments in reverse order, so that 2 x G and G x 2 are both defined.

public static EllipticCurveFiniteFieldPoint operator *(EllipticCurveFiniteFieldPoint p, BigInteger s)
{
    return s * p;
}

With the mathematical foundations in place, next time we’ll put those BigIntegers to work and try out our code on Bitcoin’s secp256k1 curve.

« Previous: Elliptic Curve Point Addition

Next: The Bitcoin Curve »

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