Shamir's Secret Sharing — Zig source

//! secret-sharing — Shamir's Secret Sharing over GF(256).
//!
//! Language: Zig 0.14 (standard library only)
//! Ported from: src/lib/secret-sharing.ts (the canonical TypeScript implementation).
//! display source — part of CosmoDev's polyglot tool pages.
//!
//! Pure math, zero dependencies. 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).

const std = @import("std");

/// Exponent table: GF256_EXP[i] = 3^i in GF(256). Index 255 mirrors index 0.
pub var gf256_exp: [256]u8 = undefined;
/// Discrete log table: GF256_LOG[3^i] = i (GF256_LOG[0] is unused).
pub var gf256_log: [256]u8 = undefined;

var tables_initialized = false;

/// Build the log/exp tables once (the TS reference does this in an IIFE).
fn initTables() void {
    if (tables_initialized) return;
    var x: u16 = 1;
    var i: usize = 0;
    while (i < 255) : (i += 1) {
        gf256_exp[i] = @intCast(x);
        gf256_log[x] = @intCast(i);
        // step to the next power of the generator 3: x *= 3 (i.e. x ^ xtime(x))
        x ^= xtime(@intCast(x));
    }
    // 3 has order 255, so EXP wraps: EXP[255] === EXP[0].
    gf256_exp[255] = 1;
    tables_initialized = true;
}

/// Multiply by 2 (x) in GF(256), reducing by 0x11B - the AES "xtime".
pub fn xtime(a: u8) u8 {
    const ext: u16 = @as(u16, a) << 1;
    const reduced = ext ^ (if (a & 0x80 != 0) @as(u16, 0x11b) else 0);
    return @intCast(reduced & 0xff);
}

/// Addition in GF(256) is bitwise XOR (also serves as subtraction).
pub fn gfAdd(a: u8, b: u8) u8 {
    return a ^ b;
}

/// Multiply two field elements via log/exp tables.
pub fn gfMul(a: u8, b: u8) u8 {
    initTables();
    if (a == 0 or b == 0) return 0;
    const sum = @as(usize, gf256_log[a]) + @as(usize, gf256_log[b]);
    return gf256_exp[sum % 255];
}

/// Multiplicative inverse of a non-zero element.
pub fn gfInv(a: u8) !u8 {
    initTables();
    if (a == 0) return error.ZeroHasNoInverse;
    const idx = (255 - @as(usize, gf256_log[a])) % 255;
    return gf256_exp[idx];
}

/// Divide a by b in GF(256).
pub fn gfDiv(a: u8, b: u8) !u8 {
    initTables();
    if (b == 0) return error.DivisionByZero;
    if (a == 0) return 0;
    const idx = (@as(usize, gf256_log[a]) + 255 - @as(usize, gf256_log[b])) % 255;
    return gf256_exp[idx];
}

/// One (x, y) point on a share polynomial.
pub const Point = struct { x: u8, y: u8 };

/// Evaluate a polynomial (coeffs[0] = constant term) at x, Horner style.
pub fn evalPoly(coeffs: []const u8, x: u8) u8 {
    var y: u8 = 0;
    var i: usize = coeffs.len;
    while (i > 0) {
        i -= 1;
        y = gfAdd(gfMul(y, x), coeffs[i]);
    }
    return y;
}

/// 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.
pub fn interpolateAtZero(points: []const Point) u8 {
    var result: u8 = 0;
    for (points, 0..) |pj, j| {
        var weight: u8 = 1;
        for (points, 0..) |pm, m| {
            if (m == j) continue;
            weight = gfMul(weight, gfDiv(pm.x, pj.x ^ pm.x) catch 0);
        }
        result = gfAdd(result, gfMul(pj.y, weight));
    }
    return result;
}

pub const Error = error{
    ThresholdTooSmall,
    TooManyShares,
    ThresholdExceedsShares,
    MalformedShare,
    InvalidShareX,
    ConflictingShares,
    LengthMismatch,
    NeedMoreShares,
    OutOfMemory,
};

/// Split a secret into total_shares shares (x = 1..N) where any threshold of
/// them reconstruct it. Returns hex share strings like "01-a3b2c1..." - the
/// two-digit hex x-coordinate, a dash, then one hex byte per secret byte.
/// Caller owns each returned string (free with `allocator`).
pub fn splitSecret(
    allocator: std.mem.Allocator,
    secret: []const u8,
    total_shares: usize,
    threshold: usize,
) Error![][]u8 {
    if (threshold < 2) return Error.ThresholdTooSmall;
    if (total_shares > 255) return Error.TooManyShares;
    if (threshold > total_shares) return Error.ThresholdExceedsShares;

    const y_parts = try allocator.alloc([]u8, total_shares);
    var allocated: usize = 0;
    errdefer {
        for (y_parts[0..allocated]) |p| allocator.free(p);
        allocator.free(y_parts);
    }

    var coeffs = try allocator.alloc(u8, threshold);
    defer allocator.free(coeffs);

    for (0..total_shares) |i| {
        y_parts[i] = try allocator.alloc(u8, secret.len);
        allocated = i + 1;
    }

    for (secret, 0..) |secret_byte, b| {
        coeffs[0] = secret_byte;
        // coefficients 1..K-1 are fresh random bytes per secret byte
        std.crypto.random.bytes(coeffs[1..threshold]);
        for (1..total_shares + 1) |i| {
            y_parts[i - 1][b] = evalPoly(coeffs, @intCast(i));
        }
    }

    // Format each share as "xx-hex…" (xx = 2-digit hex x-coordinate).
    const out = try allocator.alloc([]u8, total_shares);
    errdefer allocator.free(out);
    for (y_parts, 0..) |ys, idx| {
        const share = try allocator.alloc(u8, 3 + ys.len * 2);
        out[idx] = share;
        _ = std.fmt.bufPrint(share[0..3], "{x:0>2}-", .{@as(u8, @intCast(idx + 1))}) catch
            unreachable;
        var p: usize = 3;
        for (ys) |byte| {
            _ = std.fmt.bufPrint(share[p .. p + 2], "{x:0>2}", .{byte}) catch unreachable;
            p += 2;
        }
        allocator.free(ys);
    }
    allocator.free(y_parts);
    return out;
}

/// A parsed share: its x-coordinate and its per-byte polynomial evaluations.
pub const ParsedShare = struct {
    x: u8,
    /// Caller-owned when allocated by parseShare.
    y: []u8,
};

/// Parse one "xx-hex" share string; fails on any malformed input.
/// The returned `y` slice is owned by the caller.
pub fn parseShare(allocator: std.mem.Allocator, share: []const u8) Error!ParsedShare {
    const s = std.mem.trim(u8, share, " \t\r\n");
    if (s.len < 3 or s[2] != '-') return Error.MalformedShare;
    const x = std.fmt.parseInt(u8, s[0..2], 16) catch return Error.MalformedShare;
    const y_hex = s[3..];
    if (y_hex.len % 2 != 0) return Error.MalformedShare;
    const y = try allocator.alloc(u8, y_hex.len / 2);
    errdefer allocator.free(y);
    for (y, 0..) |*byte, i| {
        byte.* = std.fmt.parseInt(u8, y_hex[i * 2 .. i * 2 + 2], 16) catch
            return Error.MalformedShare;
    }
    if (x == 0) return Error.InvalidShareX;
    return .{ .x = x, .y = y };
}

/// 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.
/// Caller owns the returned string.
pub fn reconstructSecret(
    allocator: std.mem.Allocator,
    shares: []const []const u8,
) Error![]u8 {
    if (shares.len < 2) return Error.NeedMoreShares;

    // Collect distinct x-coordinates (a share pasted twice is harmless; a
    // colliding x with a different payload cannot belong to one split).
    var parsed = try allocator.alloc(ParsedShare, shares.len);
    defer {
        for (parsed) |p| allocator.free(p.y);
        allocator.free(parsed);
    }
    for (shares, 0..) |share, i| {
        parsed[i] = try parseShare(allocator, share);
        for (parsed[0..i]) |prev| {
            if (prev.x == parsed[i].x) {
                if (!std.mem.eql(u8, prev.y, parsed[i].y)) return Error.ConflictingShares;
            }
        }
    }

    // Sort by x (insertion sort - share counts are tiny).
    std.mem.sort(ParsedShare, parsed, {}, struct {
        fn lt(_: void, a: ParsedShare, b: ParsedShare) bool {
            return a.x < b.x;
        }
    }.lt);

    // Dedupe equal shares.
    var distinct: usize = 0;
    for (parsed, 0..) |p, i| {
        if (i == 0 or p.x != parsed[i - 1].x) {
            parsed[distinct] = p;
            distinct += 1;
        }
    }
    const points_raw = parsed[0..distinct];
    if (points_raw.len < 2) return Error.NeedMoreShares;

    const len = points_raw[0].y.len;
    for (points_raw) |p| {
        if (p.y.len != len) return Error.LengthMismatch;
    }

    const out = try allocator.alloc(u8, len);
    errdefer allocator.free(out);
    var pair = try allocator.alloc(Point, points_raw.len);
    defer allocator.free(pair);
    for (0..len) |b| {
        for (points_raw, 0..) |p, i| pair[i] = .{ .x = p.x, .y = p.y[b] };
        out[b] = interpolateAtZero(pair);
    }
    return out;
}