Shamir's Secret Sharing — TypeScript source

// Shamir's Secret Sharing over GF(256) - the Galois field of 256 elements.
//
// 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).

/** Exponent table: GF256_EXP[i] = 3^i in GF(256). Index 255 mirrors index 0. */
export const GF256_EXP = new Uint8Array(256);
/** Discrete log table: GF256_LOG[3^i] = i (GF256_LOG[0] is unused). */
export const GF256_LOG = new Uint8Array(256);

/** Multiply by 2 (x) in GF(256), reducing by 0x11B - the AES "xtime". */
export function xtime(a: number): number {
  return ((a << 1) ^ ((a & 0x80) !== 0 ? 0x11b : 0)) & 0xff;
}

(function initTables() {
  let x = 1;
  for (let i = 0; i < 255; i++) {
    GF256_EXP[i] = x;
    GF256_LOG[x] = i;
    // step to the next power of the generator 3: x *= 3 (i.e. x ^ xtime(x))
    x ^= xtime(x);
  }
  // 3 has order 255, so EXP wraps: EXP[255] === EXP[0].
  GF256_EXP[255] = 1;
})();

/** Addition in GF(256) is bitwise XOR (also serves as subtraction). */
export function gfAdd(a: number, b: number): number {
  return (a ^ b) & 0xff;
}

/** Multiply two field elements via log/exp tables. */
export function gfMul(a: number, b: number): number {
  if (a === 0 || b === 0) return 0;
  return GF256_EXP[(GF256_LOG[a] + GF256_LOG[b]) % 255];
}

/** Multiplicative inverse of a non-zero element. */
export function gfInv(a: number): number {
  if (a === 0) throw new Error('0 has no multiplicative inverse in GF(256)');
  return GF256_EXP[(255 - GF256_LOG[a]) % 255];
}

/** Divide a by b in GF(256). */
export function gfDiv(a: number, b: number): number {
  if (b === 0) throw new Error('Division by zero in GF(256)');
  if (a === 0) return 0;
  return GF256_EXP[(GF256_LOG[a] + 255 - GF256_LOG[b]) % 255];
}

/** Evaluate a polynomial (coeffs[0] = constant term) at x, Horner style. */
export function evalPoly(coeffs: Uint8Array, x: number): number {
  let y = 0;
  for (let i = coeffs.length - 1; i >= 0; i--) {
    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.
 */
export function interpolateAtZero(points: Array<[number, number]>): number {
  let result = 0;
  for (let j = 0; j < points.length; j++) {
    const [xj, yj] = points[j];
    let weight = 1;
    for (let m = 0; m < points.length; m++) {
      if (m === j) continue;
      const xm = points[m][0];
      weight = gfMul(weight, gfDiv(xm, xj ^ xm));
    }
    result = gfAdd(result, gfMul(yj, weight));
  }
  return result;
}

function toHex(bytes: Uint8Array): string {
  let out = '';
  for (const b of bytes) out += b.toString(16).padStart(2, '0');
  return out;
}

function fromHex(hex: string): Uint8Array {
  const out = new Uint8Array(hex.length / 2);
  for (let i = 0; i < out.length; i++) {
    out[i] = parseInt(hex.slice(i * 2, i * 2 + 2), 16);
  }
  return out;
}

function defaultRandomBytes(n: number): Uint8Array {
  const c = globalThis.crypto;
  if (c && typeof c.getRandomValues === 'function') {
    return c.getRandomValues(new Uint8Array(n));
  }
  throw new Error('Web Crypto (crypto.getRandomValues) is not available');
}

/** Options for splitSecret. getRandomBytes is injectable for deterministic tests. */
export interface SplitOptions {
  getRandomBytes?: (n: number) => Uint8Array;
}

function assertInt(name: string, v: number): void {
  if (!Number.isInteger(v)) {
    throw new Error(`${name} must be an integer (got ${v})`);
  }
}

/**
 * Split a secret into totalShares 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.
 */
export function splitSecret(
  secret: string,
  totalShares: number,
  threshold: number,
  opts?: SplitOptions,
): string[] {
  assertInt('Total shares', totalShares);
  assertInt('Threshold', threshold);
  if (threshold < 2) {
    throw new Error('Threshold must be at least 2 (a 1-of-N split is just the secret itself)');
  }
  if (totalShares > 255) {
    throw new Error('Total shares must be at most 255 (share x-coordinates live in 1..255)');
  }
  if (threshold > totalShares) {
    throw new Error(`Threshold (${threshold}) cannot exceed total shares (${totalShares})`);
  }

  const bytes = new TextEncoder().encode(secret);
  const rand = opts?.getRandomBytes ?? defaultRandomBytes;
  const yParts: Uint8Array[] = Array.from({ length: totalShares }, () => new Uint8Array(bytes.length));
  const coeffs = new Uint8Array(threshold);

  for (let b = 0; b < bytes.length; b++) {
    coeffs[0] = bytes[b];
    if (threshold > 1) {
      coeffs.set(rand(threshold - 1), 1);
    }
    for (let i = 1; i <= totalShares; i++) {
      yParts[i - 1][b] = evalPoly(coeffs, i);
    }
  }

  return yParts.map(
    (ys, idx) => `${(idx + 1).toString(16).padStart(2, '0')}-${toHex(ys)}`,
  );
}

/** A parsed share: its x-coordinate and its per-byte polynomial evaluations. */
export interface ParsedShare {
  x: number;
  y: Uint8Array;
}

/** Parse one "xx-hex" share string; throws on any malformed input. */
export function parseShare(share: string): ParsedShare {
  const s = share.trim();
  if (s.indexOf('-') !== 2 || !/^[0-9a-fA-F]{2}$/.test(s.slice(0, 2))) {
    throw new Error(`Malformed share "${s}" - expected the format "xx-hex…" (e.g. "01-a3b2c1")`);
  }
  const yHex = s.slice(3);
  if (!/^[0-9a-fA-F]*$/.test(yHex) || yHex.length % 2 !== 0) {
    throw new Error(`Malformed share "${s}" - the payload must be an even-length hex string`);
  }
  const x = parseInt(s.slice(0, 2), 16);
  if (x === 0) {
    throw new Error('Share x-coordinate 00 is invalid - shares are numbered from 01');
  }
  return { x, y: fromHex(yHex) };
}

/**
 * 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.
 */
export function reconstructSecret(shares: string[]): string {
  if (shares.length < 2) {
    throw new Error('Need at least 2 shares to reconstruct');
  }
  const byX = new Map<number, Uint8Array>();
  for (const share of shares) {
    const { x, y } = parseShare(share);
    // The same share pasted twice is harmless (dedupe); a colliding
    // x-coordinate with a different payload cannot belong to one split.
    const existing = byX.get(x);
    if (existing === undefined) {
      byX.set(x, y);
    } else if (!existing.every((b, i) => b === y[i])) {
      throw new Error(`Two different shares both claim x=${x.toString(16).padStart(2, '0')} - they cannot come from the same split`);
    }
  }
  const points = [...byX.entries()].sort((a, b) => a[0] - b[0]);
  if (points.length < 2) {
    throw new Error('Need at least 2 distinct shares to reconstruct');
  }
  const len = points[0][1].length;
  if (points.some(([, y]) => y.length !== len)) {
    throw new Error('All shares must be the same length - they do not come from the same split');
  }

  const out = new Uint8Array(len);
  const pair: Array<[number, number]> = points.map(([x]) => [x, 0]);
  for (let b = 0; b < len; b++) {
    for (let i = 0; i < points.length; i++) {
      pair[i][1] = points[i][1][b];
    }
    out[b] = interpolateAtZero(pair);
  }
  return new TextDecoder().decode(out);
}