ECC-32 Implementation

ecdh.cpp

/**
    ECC-32 implementation

    Private Key for Alice : 775bd026
    Private Key for Bob   : 5133580e

    Public Key for Alice : (32f20f84, 63852a02)
    Public Key for Bob   : (6d4444c2, 1563edf9)

    Session Key for Alice : (2f3a9fa3, 6a9fa1ce)
    Session Key for Bob   : (2f3a9fa3, 6a9fa1ce)

    Shared secret: 2f3a9fa3
*/

#if defined(_WIN32) || defined(_WIN64)
#define WINDOWS
#include <windows.h>
#include <wincrypt.h>
#pragma comment(lib, "advapi32")
#else
#define NIX
#include <sys/types.h>
#include <unistd.h>
#include <fcntl.h>
#include <errno.h>
#endif

#include <stdio.h>
#include <stdint.h>
#include <string.h>
#include <ctype.h>

typedef union w64_t {
    uint8_t b[8];
    uint16_t h[4];
    uint32_t w[2];
    uint64_t q;
} w64_t;

#if defined(NIX)

uint64_t 
random64(void) {
    int fd;
    ssize_t len, u = 0;
    w64_t rnd = {0};
    size_t outlen = sizeof(rnd);

    fd = open("/dev/urandom", O_RDONLY);
    if (fd >= 0) {
        for (u = 0; u < outlen;) {
            len = read(fd, rnd.b + u, outlen - u);
            if (len < 0) break;
            u += (size_t)len;
        }
        close(fd);
    }
    return rnd.q;
}

#else

uint64_t 
random64(void) {
    HCRYPTPROV hp;
    BOOL r = FALSE;
    w64_t rnd = {0};
    size_t outlen = sizeof(rnd);
    
    if (CryptAcquireContext(&hp, 0, 0, PROV_RSA_FULL, CRYPT_VERIFYCONTEXT | CRYPT_SILENT)) {
        r = CryptGenRandom(hp, outlen, (PBYTE)&rnd);
        CryptReleaseContext(hp, 0);
    }
    return rnd.q;
}

#endif

// curve parameters. p is mersenne prime: 2^31-1
uint64_t p = 0x7fffffff;
uint64_t a = 0x6E168009;
uint64_t b = 0x2E59C330;

uint64_t Gx = 0x6BC4C4B6;
uint64_t Gy = 0x27DEDCB9;

struct Point {
    uint64_t x;
    uint64_t y;
};

uint64_t addmod(uint64_t a, uint64_t b, uint64_t m) {
    return (a + b) % m;
}

uint64_t submod(uint64_t a, uint64_t b, uint64_t m) {
    uint64_t r = (a - b);
    
    return ((int64_t)r <= 0) ? r + m : r % m;
}

uint64_t mulmod(uint64_t a, uint64_t b, uint64_t m) {
    uint64_t r = 0;
    while (b) {
        if (b & 1) {
            r = addmod(r, a, m);
        }
        a = addmod(a, a, m);
        b = b >> 1;
    }
    return r;
}

uint64_t modexp(uint64_t b, uint64_t e, uint64_t m) {
    uint64_t r = 1;
    while (e) {
        if (e & 1) {
            r = mulmod(r, b, m);
        }
        b = mulmod(b, b, m);
        e = e >> 1;
    }
    return r;
}

uint64_t modinv(uint64_t a, uint64_t m) {
    return modexp(a, m - 2, m);
}

void ecpadd(Point &P, Point &Q, Point &R) {
    // If P is the point at infinity, R = Q
    if (P.x == 0 && P.y == 0) {
        R = Q;
        return;
    }
    
    // If Q is the point at infinity, R = P
    if (Q.x == 0 && Q.y == 0) {
        R = P;
        return;
    }

    uint64_t t1, t2, s, rx, ry;
    
    // Check if P and Q are the same point
    if (P.x == Q.x && P.y == Q.y) {
        // t1 = 3 * P.x^2 + a
        t1 = mulmod(P.x, P.x, p);
        t1 = mulmod(3, t1, p);
        t1 = addmod(t1, a, p);
        // t2 = 2 * P.y
        t2 = addmod(P.y, P.y, p);
    } else {
        // t1 = P.y - Q.y
        t1 = submod(P.y, Q.y, p);
        // t2 = P.x - Q.x
        t2 = submod(P.x, Q.x, p);
    }

    // Compute the modular inverse of t2
    t2 = modinv(t2, p);
    // s = t1 * t2 (slope of the line through P and Q)
    s = mulmod(t1, t2, p);
    
    // Compute R.x
    t1 = mulmod(s, s, p);         // t1 = s^2
    t2 = addmod(P.x, Q.x, p);     // t2 = P.x + Q.x
    rx = submod(t1, t2, p);       // rx = s^2 - P.x - Q.x
 
    // Compute R.y
    t1 = submod(P.x, rx, p);      // t1 = P.x - R.x
    t1 = mulmod(s, t1, p);        // t1 = s * (P.x - rx)
    ry = submod(t1, P.y, p);      // ry = s * (P.x - rx) - P.y
    
    // Set the result point R
    R.x = rx;
    R.y = ry;
}


void 
ecpmul(Point A, uint64_t kin, Point &R) {
    uint64_t k = kin % p;
    Point N = A;
    
    R.x = 0; R.y = 0;

    while (k) {
        if (k & 1) {
            ecpadd(R, N, R);
        }
        ecpadd(N, N, N);
        k >>= 1;
    }
}

int main() {
    uint64_t A_sk = random64() % (p - 1);
    uint64_t B_sk = random64() % (p - 1);

    printf("Private Key for Alice : %llx\n", A_sk);
    printf("Private Key for Bob   : %llx\n\n", B_sk);

    Point G = {Gx, Gy};
    Point A_pk, B_pk;

    ecpmul(G, A_sk, A_pk);
    ecpmul(G, B_sk, B_pk);
    
    printf("Public Key for Alice : (%llx, %llx)\n", A_pk.x, A_pk.y);
    printf("Public Key for Bob   : (%llx, %llx)\n\n", B_pk.x, B_pk.y);

    Point A_secret, B_secret;
    
    ecpmul(B_pk, A_sk, A_secret);
    ecpmul(A_pk, B_sk, B_secret);

    printf("Session Key for Alice : (%llx, %llx)\n", A_secret.x, A_secret.y);
    printf("Session Key for Bob   : (%llx, %llx)\n\n", B_secret.x, B_secret.y);

    if (A_secret.x == B_secret.x && A_secret.y == B_secret.y) {
        printf("Shared secret: %llx\n", A_secret.x);
    } else {
        printf("ERROR: Shared secrets do not match!\n");
    }

    return 0;
}