Explanation of how Diffie Hellman Elliptic Curve Key Exchange works

DHECExplainer.cs

// Example:
// E: y^2 = x^3 + 2x + 2 (mod 17) - a=2, b=2
// G: (5, 1)

using Point = (int x, int y);

int a = 2, b = 2, mod = 17, Z = 19; // y^2 = x^3 + 2x + 2 (mod 17)
Point g = (5, 1); // G: (5,1)
Console.WriteLine($"G:{g}");

// Here we dump the full range of generator G.
// Note that it would be infeasible to do this for a real production-use curve because the Z space is fantastically large.
Point p = g;
for (int i = 2; i < Z; i++) {
    p = ECAdd(p, g, a, mod);
    Console.WriteLine($"{i}G:{p}");
}
// If we try to go past that, we end up trying to get the ModInv of 0 which is equivalent to trying to divide by zero
// It is just ZG and its multiples that are forbidden - you can go past it. Note that given we are working with numbers
// in the mod 17 space there is no way to end up multiplying numbers to yield any multiple of 19, so this is ok.
try {
    p = ECAdd(p, g, a, mod);
} catch (ArgumentException ex) {
    Console.WriteLine($"{Z}G: Caught exception: {ex}");
}

// Alice picks her private key at random (>0 and <Z)
int priA = 3;
// and generates her public key from that - G3
Point pubA = ECMul(g, priA, a, mod);
Console.WriteLine($"pubA:{pubA} (G{priA})"); // 10,6

// Bob picks his private key at random (>0 and <Z)
int priB = 9;
// and generates his public key from that - G9
Point pubB = ECMul(g, priB, a, mod);
Console.WriteLine($"pubB:{pubB} (G{priB})"); // 7,6

// Note that the only thing Eve knows at this point is the curve, pubA and pubB. There is no practical way to figure
// out what shared key Alice and Bob will end up computing from this information. Remember, pubA and pubB are only
// sent as the points on the curve, not the G#. So all Eve has is 10,6 and 7,6, but she needs to some how derive
// either the combined G# (8G in this case) or the final coordinates which are 13,7.

// Alice multiplies Bob's public key by her private key to get 3*9G or 27G which ends up being 8G in Z=19 space
Point shaA = ECMul(pubB, priA, a, mod);
Console.WriteLine($"shaA:{shaA}");
// Bob multiplies Alice's public key by his private key to get 9*3G or 27G which ends up being 8G in Z=19 space
Point shaB = ECMul(pubA, priB, a, mod);
Console.WriteLine($"shaB:{shaB}");
Debug.Assert(shaA == shaB);

// typically, we just use the X coordinate of the shared key and the y coordinate is just thrown away. Note that
// because the Z space is a bit larger than the mod space, some x or y coordinates get repeated.

// Validate that private key can be anywhere in Z space
for(int pb = 1; pb < Z; pb++) {
    Point pB = ECMul(g, pb, a, mod);
    for(int pa = 1; pa < Z; pa++) {
        Point pA = ECMul(g, pa, a, mod);
        Point sB = ECMul(pA, pb, a, mod);
        Point sA = ECMul(pB, pa, a, mod);
        Debug.Assert(sB == sA);
    }
}

Point ECAdd(Point p, Point q, int a, int mod) {
    int s;
    if (p.x == q.x) {
        // use doubling formula for slope if xP = xQ
        s = (3 * p.x * q.x + a) * ModInv(p.y + q.y, mod) % mod;
    } else {
        // otherwise use normal slope formula
        s = (q.y - p.y + mod) * ModInv(q.x - p.x + mod, mod) % mod;
    }
    int xR = (s * s - p.x - q.x + mod + mod) % mod;
    int yR = (s * (p.x - xR + mod) - p.y + mod) % mod;
    return (xR, yR);
}

Point ECMul(Point g, int mul, int a, int mod) {
    mul--; // minus one because we have to start with one
    for (Point r = g, p = g; ; ) {
        if ((mul & 1) != 0) r = ECAdd(r, p, a, mod);
        mul >>= 1; if (mul == 0) return r;
        p = ECAdd(p, p, a, mod);
    }
}

int ModInv(int num, int mod) {
    // Extended Euclidean Algorithm to find the modular inverse        
    int t = 0, tPrime = 1;
    int r = mod, rPrime = num % mod;

    while (rPrime != 0) {
        int quotient = r / rPrime;
        (r, rPrime) = (rPrime, r - quotient * rPrime);
        (t, tPrime) = (tPrime, t - quotient * tPrime);
    }

    if (r != 1) throw new ArgumentException($"No inverse exists for {num} mod {mod}");
    if (t < 0) t += mod;
    return t;
}