Shamir's Secret Sharing — C source

/*
 * secret-sharing — Shamir's Secret Sharing over GF(256).
 *
 * Language: C (C11, standard library only — the field arithmetic is pure math;
 *           only the default randomness source touches a system facility)
 * Source:   CosmoDev polyglot showcase port of the Secret Sharing tool, ported
 *           from src/lib/secret-sharing.ts (the canonical TypeScript
 *           implementation).
 * License:  display source — part of CosmoDev's polyglot tool pages.
 *
 * Addition in GF(256) is XOR; multiplication uses discrete log/exp tables built
 * from the generator 3 (0x03) under the same reduction polynomial as AES
 * (x^8 + x^4 + x^3 + x + 1 = 0x11B).
 *
 * Split: for each byte of the secret, build a random polynomial of degree K-1
 * whose constant term is the secret byte, then evaluate it at x = 1..N.
 * Reconstruct: with K or more shares, Lagrange interpolation at x = 0 recovers
 * each constant term. Fewer than K shares reveal nothing (information-theoretic
 * security).
 *
 * Share format, identical to the TS reference: "xx-hex…" — the two-digit hex
 * x-coordinate, a dash, then one hex byte per secret byte.
 *
 * Build: cc -std=c11 secret-sharing.c
 */

#include <ctype.h>
#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

/* --------------------------------------------------------------- constants --- */

enum {
    GF256_ORDER   = 255, /* the multiplicative order of the generator 3 */
    MAX_SHARES    = 255, /* share x-coordinates live in 1..255 */
    MIN_THRESHOLD = 2    /* a 1-of-N split is just the secret itself */
};

/* Error reporting mirrors the TS `throw new Error(...)` messages: every entry
 * point writes one into `err` and returns false rather than aborting. */
typedef struct {
    char message[192];
} ss_err;

static bool ss_fail(ss_err *err, const char *msg)
{
    if (err != NULL) {
        snprintf(err->message, sizeof err->message, "%s", msg);
    }
    return false;
}

/* ------------------------------------------------------------ gf(256) math --- */

/** Exponent table: gf256_exp[i] = 3^i in GF(256). Index 255 mirrors index 0. */
static uint8_t gf256_exp[256];
/** Discrete log table: gf256_log[3^i] = i (gf256_log[0] is unused). */
static uint8_t gf256_log[256];
static bool gf256_ready = false;

/** Multiply by 2 (x) in GF(256), reducing by 0x11B — the AES "xtime". */
uint8_t xtime(uint8_t a)
{
    return (uint8_t) (((unsigned) a << 1) ^ (((a & 0x80) != 0) ? 0x11B : 0));
}

/*
 * Build the log/exp tables. C has no module-initializer, so the tables are
 * filled on first use instead of at load time (the TS reference's IIFE).
 */
static void gf256_init(void)
{
    unsigned i;
    uint8_t x = 1;

    if (gf256_ready) {
        return;
    }
    for (i = 0; i < GF256_ORDER; i++) {
        gf256_exp[i]    = x;
        gf256_log[x]    = (uint8_t) i;
        /* step to the next power of the generator 3: x *= 3 (i.e. x ^ xtime(x)) */
        x = (uint8_t) (x ^ xtime(x));
    }
    /* 3 has order 255, so EXP wraps: EXP[255] == EXP[0]. */
    gf256_exp[GF256_ORDER] = 1;
    gf256_ready = true;
}

/** Addition in GF(256) is bitwise XOR (also serves as subtraction). */
uint8_t gf_add(uint8_t a, uint8_t b)
{
    return (uint8_t) (a ^ b);
}

/** Multiply two field elements via the log/exp tables. */
uint8_t gf_mul(uint8_t a, uint8_t b)
{
    gf256_init();
    if (a == 0 || b == 0) {
        return 0;
    }
    return gf256_exp[(gf256_log[a] + gf256_log[b]) % GF256_ORDER];
}

/*
 * Multiplicative inverse of a non-zero element. Zero has no inverse; the TS
 * reference throws, so this port returns 0 and reports through `err`.
 */
bool gf_inv(uint8_t a, uint8_t *out, ss_err *err)
{
    gf256_init();
    if (a == 0) {
        *out = 0;
        return ss_fail(err, "0 has no multiplicative inverse in GF(256)");
    }
    *out = gf256_exp[(GF256_ORDER - gf256_log[a]) % GF256_ORDER];
    return true;
}

/** Divide a by b in GF(256). b == 0 is an error, as in the TS reference. */
bool gf_div(uint8_t a, uint8_t b, uint8_t *out, ss_err *err)
{
    gf256_init();
    if (b == 0) {
        *out = 0;
        return ss_fail(err, "Division by zero in GF(256)");
    }
    *out = (a == 0)
               ? 0
               : gf256_exp[(gf256_log[a] + GF256_ORDER - gf256_log[b]) % GF256_ORDER];
    return true;
}

/** Evaluate a polynomial (coeffs[0] = constant term) at x, Horner style. */
uint8_t eval_poly(const uint8_t *coeffs, size_t n, uint8_t x)
{
    uint8_t y = 0;
    size_t i;

    for (i = n; i > 0; i--) {
        y = gf_add(gf_mul(y, x), coeffs[i - 1]);
    }
    return y;
}

/** One (x, y) point for interpolation. */
typedef struct {
    uint8_t x;
    uint8_t y;
} ss_point;

/*
 * Lagrange interpolation at x = 0 over distinct-x points — recovers the
 * polynomial's constant term. Subtraction is XOR, so (0 - xm) = xm and
 * (xj - xm) = xj ^ xm. Distinct x values make gf_div's divisor non-zero, so
 * this cannot fail once parse_share has rejected duplicates.
 */
uint8_t interpolate_at_zero(const ss_point *points, size_t n)
{
    uint8_t result = 0;
    size_t j, m;

    for (j = 0; j < n; j++) {
        uint8_t weight = 1;

        for (m = 0; m < n; m++) {
            uint8_t term;

            if (m == j) {
                continue;
            }
            if (!gf_div(points[m].x, (uint8_t) (points[j].x ^ points[m].x), &term, NULL)) {
                return 0; /* only reachable with duplicate x values */
            }
            weight = gf_mul(weight, term);
        }
        result = gf_add(result, gf_mul(points[j].y, weight));
    }
    return result;
}

/* -------------------------------------------------------------- hex codecs --- */

static void to_hex(const uint8_t *bytes, size_t n, char *out)
{
    static const char HEX[] = "0123456789abcdef";
    size_t i;

    for (i = 0; i < n; i++) {
        out[i * 2]     = HEX[bytes[i] >> 4];
        out[i * 2 + 1] = HEX[bytes[i] & 0x0F];
    }
    out[n * 2] = '\0';
}

static int hex_value(char c)
{
    if (c >= '0' && c <= '9') return c - '0';
    if (c >= 'a' && c <= 'f') return c - 'a' + 10;
    if (c >= 'A' && c <= 'F') return c - 'A' + 10;
    return -1;
}

static void from_hex(const char *hex, size_t hex_len, uint8_t *out)
{
    size_t i;

    for (i = 0; i < hex_len / 2; i++) {
        out[i] = (uint8_t) ((hex_value(hex[i * 2]) << 4) | hex_value(hex[i * 2 + 1]));
    }
}

/* ------------------------------------------------------------- randomness --- */

/*
 * Randomness source for the polynomial coefficients, injectable so tests can be
 * deterministic — the C stand-in for the TS SplitOptions.getRandomBytes.
 * Returns false when it cannot produce `n` bytes.
 */
typedef bool (*ss_random_fn)(uint8_t *out, size_t n, void *ctx);

/* The default: the kernel CSPRNG, the closest analogue to
 * crypto.getRandomValues(). Never a userspace PRNG — the coefficients are what
 * make fewer-than-K shares reveal nothing. */
static bool default_random_bytes(uint8_t *out, size_t n, void *ctx)
{
    FILE *fp;
    size_t read;

    (void) ctx;
    fp = fopen("/dev/urandom", "rb");
    if (fp == NULL) {
        return false;
    }
    read = fread(out, 1, n, fp);
    fclose(fp);
    return read == n;
}

/* ------------------------------------------------------------------- split --- */

/** The result of split_secret: `count` heap-owned "xx-hex…" share strings. */
typedef struct {
    char **shares;
    size_t count;
} ss_shares;

void ss_shares_free(ss_shares *s)
{
    size_t i;

    if (s == NULL || s->shares == NULL) {
        return;
    }
    for (i = 0; i < s->count; i++) {
        if (s->shares[i] != NULL) {
            /* Each share is secret-adjacent; wipe before release. */
            memset(s->shares[i], 0, strlen(s->shares[i]));
            free(s->shares[i]);
        }
    }
    free(s->shares);
    s->shares = NULL;
    s->count  = 0;
}

/*
 * Split a secret into `total_shares` shares (x = 1..N) where any `threshold` of
 * them reconstruct it. Mirrors the TS splitSecret(), including its validation
 * order and messages. `random` may be NULL to use the default CSPRNG.
 */
bool split_secret(const char *secret, unsigned total_shares, unsigned threshold,
                  ss_random_fn random, void *random_ctx, ss_shares *out, ss_err *err)
{
    size_t secret_len = (secret != NULL) ? strlen(secret) : 0;
    uint8_t *y_parts = NULL;
    uint8_t *coeffs  = NULL;
    size_t b;
    unsigned i;
    bool ok = false;

    if (out == NULL) {
        return ss_fail(err, "Output parameter must not be NULL.");
    }
    memset(out, 0, sizeof *out);

    /* The TS assertInt() checks have no analogue: C's unsigned parameters cannot
     * carry a fractional value in the first place. */
    if (threshold < MIN_THRESHOLD) {
        return ss_fail(err, "Threshold must be at least 2 (a 1-of-N split is just the secret itself)");
    }
    if (total_shares > MAX_SHARES) {
        return ss_fail(err, "Total shares must be at most 255 (share x-coordinates live in 1..255)");
    }
    if (threshold > total_shares) {
        if (err != NULL) {
            snprintf(err->message, sizeof err->message,
                     "Threshold (%u) cannot exceed total shares (%u)", threshold, total_shares);
        }
        return false;
    }

    if (random == NULL) {
        random = default_random_bytes;
    }

    /* One row of `secret_len` evaluations per share, laid out contiguously. */
    y_parts = calloc((size_t) total_shares * (secret_len + 1), 1);
    coeffs  = calloc(threshold, 1);
    out->shares = calloc(total_shares, sizeof *out->shares);
    if (y_parts == NULL || coeffs == NULL || out->shares == NULL) {
        ss_fail(err, "Out of memory.");
        goto done;
    }
    out->count = total_shares;

    for (b = 0; b < secret_len; b++) {
        coeffs[0] = (uint8_t) secret[b];
        /* Fresh random coefficients per secret byte: reusing them across bytes
         * would leak the secret's structure. */
        if (!random(coeffs + 1, (size_t) threshold - 1, random_ctx)) {
            ss_fail(err, "A secure random source is not available");
            goto done;
        }
        for (i = 1; i <= total_shares; i++) {
            y_parts[(size_t) (i - 1) * secret_len + b] =
                eval_poly(coeffs, threshold, (uint8_t) i);
        }
    }

    for (i = 0; i < total_shares; i++) {
        /* "xx" + "-" + 2 hex chars per byte + NUL */
        char *share = malloc(3 + secret_len * 2 + 1);

        if (share == NULL) {
            ss_fail(err, "Out of memory.");
            goto done;
        }
        snprintf(share, 4, "%02x-", i + 1);
        to_hex(y_parts + (size_t) i * secret_len, secret_len, share + 3);
        out->shares[i] = share;
    }
    ok = true;

done:
    if (coeffs != NULL) {
        memset(coeffs, 0, threshold); /* the constant term is a secret byte */
        free(coeffs);
    }
    free(y_parts);
    if (!ok) {
        ss_shares_free(out);
    }
    return ok;
}

/* --------------------------------------------------------------- reconstruct --- */

/** A parsed share: its x-coordinate and its per-byte polynomial evaluations. */
typedef struct {
    uint8_t  x;
    uint8_t *y;
    size_t   y_len;
} parsed_share;

void parsed_share_free(parsed_share *p)
{
    if (p != NULL) {
        free(p->y);
        p->y     = NULL;
        p->y_len = 0;
    }
}

/* Parse one "xx-hex" share string; rejects any malformed input. */
bool parse_share(const char *share, parsed_share *out, ss_err *err)
{
    const char *s;
    size_t len, y_len, i;

    if (out == NULL) {
        return ss_fail(err, "Output parameter must not be NULL.");
    }
    memset(out, 0, sizeof *out);

    /* share.trim() */
    s = (share != NULL) ? share : "";
    while (*s != '\0' && (unsigned char) *s <= ' ') {
        s++;
    }
    len = strlen(s);
    while (len > 0 && (unsigned char) s[len - 1] <= ' ') {
        len--;
    }

    if (len < 3 || s[2] != '-' || hex_value(s[0]) < 0 || hex_value(s[1]) < 0) {
        if (err != NULL) {
            snprintf(err->message, sizeof err->message,
                     "Malformed share \"%.*s\" - expected the format \"xx-hex…\" (e.g. \"01-a3b2c1\")",
                     (int) len, s);
        }
        return false;
    }

    y_len = len - 3;
    for (i = 0; i < y_len; i++) {
        if (hex_value(s[3 + i]) < 0) {
            y_len = SIZE_MAX; /* force the even/hex error below */
            break;
        }
    }
    if (y_len == SIZE_MAX || (y_len % 2) != 0) {
        if (err != NULL) {
            snprintf(err->message, sizeof err->message,
                     "Malformed share \"%.*s\" - the payload must be an even-length hex string",
                     (int) len, s);
        }
        return false;
    }

    out->x = (uint8_t) ((hex_value(s[0]) << 4) | hex_value(s[1]));
    if (out->x == 0) {
        return ss_fail(err, "Share x-coordinate 00 is invalid - shares are numbered from 01");
    }

    out->y_len = y_len / 2;
    out->y = malloc(out->y_len + 1);
    if (out->y == NULL) {
        return ss_fail(err, "Out of memory.");
    }
    from_hex(s + 3, y_len, out->y);
    return true;
}

/*
 * Reconstruct the secret from an arbitrary collection of share strings.
 * Needs at least 2 distinct shares (the threshold of the original split);
 * anything less than the true threshold K yields garbage without warning —
 * that is the security property of the scheme, not a bug.
 *
 * On success *out_secret is a heap NUL-terminated string owned by the caller.
 */
bool reconstruct_secret(const char *const *shares, size_t share_count,
                        char **out_secret, ss_err *err)
{
    parsed_share *parsed = NULL;
    size_t distinct = 0;
    ss_point *points = NULL;
    uint8_t *secret  = NULL;
    size_t len, i, j, b;
    bool ok = false;

    if (out_secret == NULL) {
        return ss_fail(err, "Output parameter must not be NULL.");
    }
    *out_secret = NULL;

    if (share_count < 2) {
        return ss_fail(err, "Need at least 2 shares to reconstruct");
    }
    parsed = calloc(share_count, sizeof *parsed);
    if (parsed == NULL) {
        return ss_fail(err, "Out of memory.");
    }

    for (i = 0; i < share_count; i++) {
        parsed_share current;
        bool duplicate = false;

        if (!parse_share(shares[i], &current, err)) {
            goto done;
        }
        /* The same share pasted twice is harmless (dedupe); a colliding
         * x-coordinate with a different payload cannot belong to one split. */
        for (j = 0; j < distinct; j++) {
            if (parsed[j].x != current.x) {
                continue;
            }
            duplicate = true;
            if (parsed[j].y_len != current.y_len ||
                memcmp(parsed[j].y, current.y, current.y_len) != 0) {
                if (err != NULL) {
                    snprintf(err->message, sizeof err->message,
                             "Two different shares both claim x=%02x - they cannot come from the same split",
                             current.x);
                }
                parsed_share_free(&current);
                goto done;
            }
            break;
        }
        if (duplicate) {
            parsed_share_free(&current);
        } else {
            parsed[distinct++] = current;
        }
    }

    if (distinct < 2) {
        ss_fail(err, "Need at least 2 distinct shares to reconstruct");
        goto done;
    }

    /* Sort by x, ascending — matches the TS sort on the map entries. */
    for (i = 1; i < distinct; i++) {
        parsed_share key = parsed[i];

        for (j = i; j > 0 && parsed[j - 1].x > key.x; j--) {
            parsed[j] = parsed[j - 1];
        }
        parsed[j] = key;
    }

    len = parsed[0].y_len;
    for (i = 1; i < distinct; i++) {
        if (parsed[i].y_len != len) {
            ss_fail(err, "All shares must be the same length - they do not come from the same split");
            goto done;
        }
    }

    points = calloc(distinct, sizeof *points);
    secret = calloc(len + 1, 1);
    if (points == NULL || secret == NULL) {
        ss_fail(err, "Out of memory.");
        goto done;
    }
    for (i = 0; i < distinct; i++) {
        points[i].x = parsed[i].x;
    }
    for (b = 0; b < len; b++) {
        for (i = 0; i < distinct; i++) {
            points[i].y = parsed[i].y[b];
        }
        secret[b] = interpolate_at_zero(points, distinct);
    }

    *out_secret = (char *) secret;
    secret = NULL; /* ownership transferred */
    ok = true;

done:
    for (i = 0; i < distinct; i++) {
        parsed_share_free(&parsed[i]);
    }
    free(parsed);
    free(points);
    free(secret);
    return ok;
}

/* -------------------------------------------------------------------- demo --- */

int main(void)
{
    ss_shares split;
    ss_err err = {0};
    char *recovered = NULL;
    const char *subset[3];

    if (!split_secret("correct horse battery staple", 5, 3, NULL, NULL, &split, &err)) {
        fprintf(stderr, "secret-sharing: %s\n", err.message);
        return 1;
    }
    for (size_t i = 0; i < split.count; i++) {
        printf("share %zu: %s\n", i + 1, split.shares[i]);
    }

    /* Any 3 of the 5 shares reconstruct the secret. */
    subset[0] = split.shares[4];
    subset[1] = split.shares[1];
    subset[2] = split.shares[3];
    if (!reconstruct_secret(subset, 3, &recovered, &err)) {
        fprintf(stderr, "secret-sharing: %s\n", err.message);
        ss_shares_free(&split);
        return 1;
    }
    printf("\nrecovered: %s\n", recovered);

    free(recovered);
    ss_shares_free(&split);
    return 0;
}