ECDH using arbitrary-precision arithmetic

bn_ecc.c

/**

    Running test...key : 803D8AB2E5B6E6FCA715737C3A82F7CE3C783124F6D51CD0
    Session keys match...
    OK.
    Generating random keys...OK
    Private Key for Alice : 31FA1084
    Private Key for Bob   : 2D748885

    Generating public keys...
    Public Key for Alice : (10DEE015, 7A458BE8)
    Public Key for Bob   : (49DC9B2E, 660EDB3F)

    Generating session keys...
    Session Key for Alice : (41B46B35, 45594721)
    Session Key for Bob   : (41B46B35, 45594721)

    Shared secret: 41B46B35
*/
#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>
#include <time.h>

#include "sha256.h"

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

#if defined(NIX)

uint32_t random32(void) {
    int fd;
    ssize_t len, u = 0;
    size_t outlen = 4;
    w64_t rnd = {0};

    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.w;
}

void 
random(void *out, size_t outlen) {
    int fd;
    ssize_t len, u = 0;
    uint8_t *ptr = (uint8_t*)out;

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

#else

uint32_t 
random32(void) {
    HCRYPTPROV hp;
    BOOL r = FALSE;
    size_t outlen = 4;
    w64_t rnd = {0};

    if (CryptAcquireContext(&hp, 0, 0, PROV_RSA_FULL, CRYPT_VERIFYCONTEXT | CRYPT_SILENT)) {
        r = CryptGenRandom(hp, outlen, (PBYTE)&rnd);
        CryptReleaseContext(hp, 0);
    }
    return rnd.w;
}

void 
random(void *out, size_t outlen) {
    HCRYPTPROV hp;
    BOOL r = FALSE;

    if (CryptAcquireContext(&hp, 0, 0, PROV_RSA_FULL, CRYPT_VERIFYCONTEXT | CRYPT_SILENT)) {
        r = CryptGenRandom(hp, outlen, (PBYTE)out);
        CryptReleaseContext(hp, 0);
    }
}

#endif

#define BN_MAX_BITS 384
#define BN_MAX_BYTES (BN_MAX_BITS / 8)
#define BN_MAX_WORDS (BN_MAX_BYTES / sizeof(uint32_t))

typedef union _bn_t {
    uint8_t  b[BN_MAX_BYTES];
    uint32_t w[BN_MAX_BYTES/sizeof(uint32_t)];
    uint64_t q[BN_MAX_BYTES/sizeof(uint64_t)];
} bn;

void
bn_set_word(bn *x, uint32_t w);
const char* bn_bn2hex(bn *a);
void 
bn_modexp(bn *x, bn *b, bn *e, bn *m);
void 
bn_mulmod(bn *x, bn *b, bn *e, bn *m);
void 
bn_addmod(bn *r, bn *a, bn *b, bn *m);
void 
bn_submod(bn *r, bn *a, bn *b, bn *m);
void 
bn_mod(bn *dividend, bn *divisor, bn *remainder);
int 
bn_is_zero(bn*);
int 
bn_cmp(bn *a, bn *b);
void 
bn_copy(bn *d, bn *s);
void 
bn_zero(bn *x);
int 
bn_is_bit_set(bn *x, int bit_idx);
int 
bn_hex2bn(bn *a, const char *hexStr);
int 
bn_num_bits(bn *x);
const char*
bn_bn2dec(bn *a);
int
bn_dec2bin(bn *a, const char *decStr);

void bn_set_hex(bn *x, const char *hexStr) {
    bn_zero(x);
    bn_hex2bn(x, hexStr);
}

//
// Holds x and y coordinate of curve
//
typedef struct _Point {
    bn x;
    bn y;
} Point;

//
// Zero Point P
//
void
ecp_zero(Point *P) {
    for (int i=0; i<BN_MAX_WORDS; i++) {
        P->x.w[i] = 0;
        P->y.w[i] = 0;
    }
}

//
// Copy point Q to P
//
void
ecp_copy(Point *P, Point *Q) {
    for (int i=0; i<BN_MAX_WORDS; i++) {
        P->x.w[i] = Q->x.w[i];
        P->y.w[i] = Q->y.w[i];
    }
}

//
// Test if points are equal.
// 1 = equal, else 0
//
int
ecp_equal(Point *P, Point *Q) {
    for (int i=0; i<BN_MAX_WORDS; i++) {
        if (P->x.w[i] != Q->x.w[i] || P->y.w[i] != Q->y.w[i]) return 0;
    }
    return 1;
}

int init = 0;
bn inv_mod_p;

//
// Point Addition
//
void 
ecp_add(Point *P, Point *Q, Point *R, bn *p, bn *a) {
    bn t1, t2, s;
    Point r;

    // if P is at infinity, return Q
    if (bn_is_zero(&P->x) && bn_is_zero(&P->y)) {
        ecp_copy(R, Q);
        return;
    }

    // if Q is at infinity, return P
    if (bn_is_zero(&Q->x) && bn_is_zero(&Q->y)) {
        ecp_copy(R, P);
        return;
    }
    
    // if P and Q are equal
    if (ecp_equal(P, Q)) {
        // point doubling
        bn_mulmod(&t1, &P->x, &P->x, p);
        bn_addmod(&t2, &t1, &t1, p);
        bn_addmod(&t1, &t1, &t2, p);
        bn_addmod(&t1, &t1, a, p);
        bn_addmod(&t2, &P->y, &P->y, p);
    } else {
        // point addition
        bn_submod(&t1, &P->y, &Q->y, p);
        bn_submod(&t2, &P->x, &Q->x, p);
    }
 
    bn_modexp(&t2, &t2, &inv_mod_p, p);
    bn_mulmod(&s, &t1, &t2, p);
    
    bn_mulmod(&t1, &s, &s, p);
    bn_addmod(&t2, &P->x, &Q->x, p);
    bn_submod(&r.x, &t1, &t2, p);

    bn_submod(&t1, &P->x, &r.x, p);
    bn_mulmod(&t1, &s, &t1, p);
    bn_submod(&r.y, &t1, &P->y, p);

    ecp_copy(R, &r);
}

//
// Point Multiplication
//
void 
ecp_mul(Point *A, bn *k, Point *R, bn *p, bn *a) {
    Point N;
    
    ecp_copy(&N, A);
    ecp_zero(R);
    
    int bits = bn_num_bits(k);
    
    for (int i = 0; i < bits; i++) {
        if (bn_is_bit_set(k, i)) {
            ecp_add(R, &N, R, p, a);
        }
        ecp_add(&N, &N, &N, p, a);
    }
}

void
test_ecdsa(void) {    
    Point pk;      // public and private keys
    Point G;           // base point for generating keys
    bn tn, n, p, a={0}, sk;
    
    // secp256k1 parameters

    // set prime p
    bn_hex2bn(&p, "fffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f");
    bn_copy(&inv_mod_p, &p);
    inv_mod_p.b[0] -= 2;
    
    // set the base point
    bn_hex2bn(&G.x, "79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798");
    bn_hex2bn(&G.y, "483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8");
    
    // set order
    bn_hex2bn(&n, "fffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141");
    bn_copy(&tn, &n);
    tn.b[0] -= 2;
    
    //
    // Generate keys.
    //
    //bn_set_word(&sk, random32());    // use something better later...
    
    bn_hex2bn(&sk, "caafcef23ebbef8227a87df538da046bd560162f3dee6f661c649d29797ae29a");
    ecp_mul(&G, &sk, &pk, &p, &a);
    
    printf("public key x : %s\n", bn_bn2hex(&pk.x));
    printf("public key y : %s\n", bn_bn2hex(&pk.y));
    
    //
    // Sign the message and generate signature
    //
    const char msg[] = "Hello, World!";
    size_t msg_len = strlen(msg);
    bn z={0};
    
    sha256_ctx ctx;
    
    sha256_init(&ctx);
    sha256_update(&ctx, msg, msg_len);
    sha256_final(&z.b, &ctx);
    
    // we don't need to reverse for the implementation to be correct.
    // it's needed to generate the same signature used in test vector.
    int len = ((bn_num_bits(&z) + 7) & ~7) / 8;

    for (int i = 0; i < len / 2; i++) {
        uint8_t t = z.b[i];
        z.b[i] = z.b[len - i - 1];
        z.b[len - i - 1] = t;
    }
    
    bn r={0}, s={0};
    bn k, kinv, x, y, zs, tmp;
    Point t;
    bn_hex2bn(&k, "e26ee863c09bf9880f29f43d08db0c72d6751ece202b74c87b4047b473e862da");
    
    for (;;) {
        //random(&k.b, 32);
        
        ecp_mul(&G, &k, &t, &p, &a);
        bn_mod(&t.x, &n, &r);
        if (bn_is_zero(&r)) continue;
        
        bn_modexp(&kinv, &k, &tn, &n);
        bn_mulmod(&tmp, &r, &sk, &n);
        bn_addmod(&zs, &z, &tmp, &n);
        bn_mulmod(&s, &kinv, &zs, &n);
        
        if (!bn_is_zero(&s)) break;
    }

    //
    // Verify the signature
    // 
    bn w, u1, u2, m1, m2;
    Point p1, p2, res;
    
    bn_modexp(&w, &s, &tn, &n);
    bn_mulmod(&u1, &z, &w, &n);
    bn_mulmod(&u2, &r, &w, &n);
    ecp_mul(&G, &u1, &p1, &p, &a);
    ecp_mul(&pk, &u2, &p2, &p, &a);
    ecp_add(&p1, &p2, &res, &p, &a);
    bn_mod(&res.x, &n, &m2);
}

void
test_ecdh(void) {
    printf("Running ECDH test...");
    
    bn sk, secret, p, a, b;
    Point pk={0}, G, skey={0};
    
    // Elliptic curve parameters P-192 prime192v1
    
    // set prime p
    bn_hex2bn(&p, "fffffffffffffffffffffffffffffffeffffffffffffffff");
    bn_copy(&inv_mod_p, &p);
    inv_mod_p.b[0] -= 2;
    
    // set curve parameters
    bn_hex2bn(&a, "fffffffffffffffffffffffffffffffefffffffffffffffc");
    bn_hex2bn(&b, "64210519e59c80e70fa7e9ab72243049feb8deecc146b9b1");

    // the base point is only required when generating public keys.
    //bn_hex2bn(&Gx, "188da80eb03090f67cbf20eb43a18800f4ff0afd82ff1012");
    //bn_hex2bn(&Gy, "07192b95ffc8da78631011ed6b24cdd573f977a11e794811");
    
    // set private key for Alice
    bn_hex2bn(&sk, "f17d3fea367b74d340851ca4270dcb24c271f445bed9d527");
    
    // set public key from Bob
    bn_hex2bn(&pk.x, "42ea6dd9969dd2a61fea1aac7f8e98edcc896c6e55857cc0");
    bn_hex2bn(&pk.y, "dfbe5d7c61fac88b11811bde328e8a0d12bf01a9d204b523");

    // set session key that should be generated.
    bn_hex2bn(&secret, "803d8ab2e5b6e6fca715737c3a82f7ce3c783124f6d51cd0");
    
    // generate session key based on parameters
    ecp_mul(&pk, &sk, &skey, &p, &a);
    
    printf("key : %s\n", bn_bn2hex(&skey.x));
    
    if (bn_cmp(&skey.x, &secret) == 0) {
        printf("Session keys match...\n");
    } else {
        printf("Session keys don't match!...\n");
    }

    printf("OK.\n");
}

int 
main(int argc, char *argv[]) {
    test_ecdsa();
    test_ecdh();
    return 0;
    
    bn A_sk, B_sk, p, a, b, Gx, Gy;

    bn_set_hex(&p, "7FFFFFFF");
    bn_set_hex(&a, "6E168009");
    bn_set_hex(&b, "2E59C330");
    bn_set_hex(&Gx, "6BC4C4B6");
    bn_set_hex(&Gy, "27DEDCB9");

    printf("Generating random keys...");
    bn_set_word(&A_sk, random32() % 0x7FFFFFFF);
    bn_set_word(&B_sk, random32() % 0x7FFFFFFF);

    printf("OK\n");
    printf("Private Key for Alice : %s\n", bn_bn2hex(&A_sk));
    printf("Private Key for Bob   : %s\n\n", bn_bn2hex(&B_sk));

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

    printf("Generating public keys...\n");
    ecp_mul(&G, &A_sk, &A_pk, &p, &a);
    
    printf("Public Key for Alice : (%s, %s)\n", 
        bn_bn2hex(&A_pk.x), 
        bn_bn2hex(&A_pk.y));
        
    ecp_mul(&G, &B_sk, &B_pk, &p, &a);
    
    printf("Public Key for Bob   : (%s, %s)\n\n", 
        bn_bn2hex(&B_pk.x), 
        bn_bn2hex(&B_pk.y));

    Point A_secret={0}, B_secret={0};
    
    printf("Generating session keys...\n");
    ecp_mul(&B_pk, &A_sk, &A_secret, &p, &a);
    ecp_mul(&A_pk, &B_sk, &B_secret, &p, &a);

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

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

    return 0;
}