C++ Implementation of Elliptic Curve

In my previous post, I implemented basic finite field and elliptic curve math and confirmed the public key generated in my code matches with the result of openssl. My next goal is to implement ECDH (Elliptic Curve Diffie-Hellman) Key Exchange for TLS sessions.

For this, I need to port my Python code to C++. With the help of GMP library, it was mostly straightforward.

Following is finite field and EC class implementation.

#include <string>
#include "gmpxx.h"

// Finite Field
class Fp
{
public:
    static void init(mpz_class _p){ p = _p;}

    Fp(){ v = 0;}
    Fp(mpz_class _v){ v = (_v + p) % p;}
    Fp(const Fp &f){ v = f.v;}

    Fp operator+(Fp f)
    {
        return Fp(v + f.v);
    }

    Fp operator-(Fp f)
    {
        return Fp(v - f.v);
    }

    Fp operator-()
    {
        return Fp(-v);
    }

    Fp operator*(Fp f)
    {
        return Fp(v * f.v);
    }

    Fp operator/(Fp f)
    {
        // get 1/f using Fermat's little theorem.
        mpz_class res;
        mpz_class p2 = p - 2;
        mpz_powm(res.get_mpz_t(), f.v.get_mpz_t(), p2.get_mpz_t(), p.get_mpz_t());

        // then multiply 1/f with 'this'.
        return Fp(v * res);
    }

    bool operator==(Fp f){ return v == f.v;}
    bool operator!=(Fp f){ return v != f.v;}

    mpz_class v; // value
    static mpz_class p; // modulo
};

// Elliptic Curve
class EC
{
public:

    static void init(mpz_class _a, mpz_class _b)
    {
        a = _a;
        b = _b;
    }

    EC()
    {
        isZero = true;
        x = Fp(0);
        y = Fp(0);
    }

    EC(Fp _x, Fp _y)
    {
        isZero = (_x.v == 0 && _y.v == 0);
        x = _x;
        y = _y;
    }

    bool isValid(void)
    {
        if (isZero) return true;

        return (y * y == (x * x + a) * x + b);
    }

    bool operator==(EC e)
    {
        return (x == e.x) && (y == e.y);
    }

    EC operator+(EC e)
    {
        if (e.isZero) return *this;
        if (isZero) return e;

        Fp L;
        if (x != e.x)
            L = (y - e.y) / (x - e.x);
        else
        {
            if (y == -e.y)
            {
                return EC();
            }
            else
            {
                L = (Fp(3) * x * x + a) / (Fp(2) * y);
            }
        }

        Fp fx(L * L - (x + e.x));
        Fp fy(L * (x - fx) - y);

        return EC(fx, fy);
    }

    EC operator*(Fp m)
    {
        if (m.v == 0)
        {
            return EC();
        }

        auto v = m.v.get_mpz_t();
        
        EC e;
        for(int i = 512; i >= 0; i--)
        {
            e = e + e;
            if (mpz_tstbit(v, i))
                e = e + *this;
        }
        return e;
    }

    bool isZero;
    Fp x;
    Fp y;

    static mpz_class a;
    static mpz_class b;
};

Following is the test code.

#include <stdio.h>
#include <iostream>
#include "ecdh.h"

mpz_class Fp::p;
mpz_class EC::a, EC::b;

int test_ecdh(int argc, char **argv)
{
    printf("test ec\n");

    mpz_class prime("fffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f", 16);
    Fp::init(prime);
    EC::init(0, 7); // a, b

    // generator coordinates
    mpz_class gx("79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798", 16);
    mpz_class gy("483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8", 16);

    // priv and pub keys
    mpz_class priv("a2d0c4edf31a2ba23140bea805d0e0b2b45579654a030793920304a1adfc57ed", 16);
    mpz_class pub_x("1d3293078eb57d86f568c028ad66b23cb579c344d4661b4e59d56cdbbd8d3edb", 16);
    mpz_class pub_y("0d23107a1f803bad2c4a0e1ed73947b2ab18c059f88b2e0446f110d13e16da91", 16);

    // let's verify our code.
    EC g((Fp(gx)), (Fp(gy)));
    EC pub((Fp(pub_x)), (Fp(pub_y)));
    EC my_pub = g * Fp(priv);

    if (my_pub == pub)
        printf("public key matched!\n");
    else
        printf("public key unmatched!\n");
    
    printf("my_pub x: 0x%s\n", my_pub.x.v.get_str(16).c_str());
    printf("my_pub y: 0x%s\n", my_pub.y.v.get_str(16).c_str());

    return 0;
}

Leave a Reply

Your email address will not be published.