Shamir's Secret Sharing — C# source

// Shamir's Secret Sharing over GF(256) — the Galois field of 256 elements.
// C# 12 / .NET 8 — ported from src/lib/secret-sharing.ts (the canonical
// TypeScript implementation). Display source for CosmoDev's polyglot 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).

using System.Text;

/// <summary>A parsed share: its x-coordinate and its per-byte polynomial evaluations.</summary>
/// <param name="X">Share index (1-255) parsed from the two-digit hex prefix.</param>
/// <param name="Y">One polynomial evaluation per secret byte.</param>
public sealed record ParsedShare(int X, byte[] Y);

public static class SecretSharing
{
    /// <summary>Exponent table: GF256Exp[i] = 3^i in GF(256). Index 255 mirrors index 0.</summary>
    public static readonly byte[] Gf256Exp = new byte[256];

    /// <summary>Discrete log table: GF256Log[3^i] = i (GF256Log[0] is unused).</summary>
    public static readonly byte[] Gf256Log = new byte[256];

    static SecretSharing()
    {
        var x = 1;
        for (var i = 0; i < 255; i++)
        {
            Gf256Exp[i] = (byte)x;
            Gf256Log[x] = (byte)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].
        Gf256Exp[255] = 1;
    }

    /// <summary>Multiply by 2 (x) in GF(256), reducing by 0x11B — the AES "xtime".</summary>
    public static byte Xtime(byte a) =>
        (byte)((a << 1) ^ ((a & 0x80) != 0 ? 0x11b : 0));

    /// <summary>Addition in GF(256) is bitwise XOR (also serves as subtraction).</summary>
    public static byte GfAdd(byte a, byte b) => (byte)(a ^ b);

    /// <summary>Multiply two field elements via log/exp tables.</summary>
    public static byte GfMul(byte a, byte b)
    {
        if (a == 0 || b == 0) return 0;
        return Gf256Exp[(Gf256Log[a] + Gf256Log[b]) % 255];
    }

    /// <summary>Multiplicative inverse of a non-zero element.</summary>
    public static byte GfInv(byte a)
    {
        if (a == 0) throw new ArgumentException("0 has no multiplicative inverse in GF(256).");
        return Gf256Exp[(255 - Gf256Log[a]) % 255];
    }

    /// <summary>Divide a by b in GF(256).</summary>
    public static byte GfDiv(byte a, byte b)
    {
        if (b == 0) throw new DivideByZeroException("Division by zero in GF(256).");
        if (a == 0) return 0;
        return Gf256Exp[(Gf256Log[a] + 255 - Gf256Log[b]) % 255];
    }

    /// <summary>Evaluate a polynomial (coeffs[0] = constant term) at x, Horner style.</summary>
    public static byte EvalPoly(ReadOnlySpan<byte> coeffs, byte x)
    {
        byte y = 0;
        for (var i = coeffs.Length - 1; i >= 0; i--)
        {
            y = GfAdd(GfMul(y, x), coeffs[i]);
        }
        return y;
    }

    /// <summary>
    /// 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.
    /// </summary>
    public static byte InterpolateAtZero(ReadOnlySpan<(byte X, byte Y)> points)
    {
        byte result = 0;
        for (var j = 0; j < points.Length; j++)
        {
            var (xj, yj) = points[j];
            byte weight = 1;
            for (var m = 0; m < points.Length; m++)
            {
                if (m == j) continue;
                var xm = points[m].X;
                weight = GfMul(weight, GfDiv(xm, (byte)(xj ^ xm)));
            }
            result = GfAdd(result, GfMul(yj, weight));
        }
        return result;
    }

    private static string ToHex(ReadOnlySpan<byte> bytes) => Convert.ToHexString(bytes).ToLowerInvariant();

    private static byte[] FromHex(string hex) =>
        Convert.FromHexString(hex);

    private static void DefaultRandomBytes(byte[] buffer) =>
        System.Security.Cryptography.RandomNumberGenerator.Fill(buffer);

    /// <summary>Random source injectable for deterministic tests; defaults to the CSPRNG.</summary>
    public delegate void RandomBytes(byte[] buffer);

    /// <summary>
    /// Split a secret into <paramref name="totalShares"/> shares (x = 1..N)
    /// where any <paramref name="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.
    /// </summary>
    public static string[] SplitSecret(
        string secret, int totalShares, int threshold, RandomBytes? getRandomBytes = null)
    {
        if (threshold < 2)
        {
            throw new ArgumentOutOfRangeException(
                nameof(threshold), "Threshold must be at least 2 (a 1-of-N split is just the secret itself).");
        }
        if (totalShares > 255)
        {
            throw new ArgumentOutOfRangeException(
                nameof(totalShares), "Total shares must be at most 255 (share x-coordinates live in 1..255).");
        }
        if (threshold > totalShares)
        {
            throw new ArgumentException(
                $"Threshold ({threshold}) cannot exceed total shares ({totalShares}).");
        }

        var bytes = Encoding.UTF8.GetBytes(secret);
        getRandomBytes ??= DefaultRandomBytes;
        var yParts = new byte[totalShares][];
        for (var i = 0; i < totalShares; i++) yParts[i] = new byte[bytes.Length];
        var coeffs = new byte[threshold];
        var randomTail = new byte[threshold - 1];

        for (var b = 0; b < bytes.Length; b++)
        {
            coeffs[0] = bytes[b];
            if (threshold > 1)
            {
                getRandomBytes(randomTail);
                randomTail.CopyTo(coeffs, 1);
            }
            for (var i = 1; i <= totalShares; i++)
            {
                yParts[i - 1][b] = EvalPoly(coeffs, (byte)i);
            }
        }

        return yParts.Select((ys, idx) => $"{(idx + 1):x2}-{ToHex(ys)}").ToArray();
    }

    /// <summary>Parse one "xx-hex" share string; throws on any malformed input.</summary>
    public static ParsedShare ParseShare(string share)
    {
        var s = share.Trim();
        if (s.IndexOf('-') != 2 || s.Length < 3 || !IsHex(s[..2]))
        {
            throw new FormatException(
                $"Malformed share \"{s}\" - expected the format \"xx-hex…\" (e.g. \"01-a3b2c1\").");
        }
        var yHex = s[3..];
        if (yHex.Length % 2 != 0 || !IsHex(yHex))
        {
            throw new FormatException(
                $"Malformed share \"{s}\" - the payload must be an even-length hex string.");
        }
        var x = Convert.ToInt32(s[..2], 16);
        if (x == 0)
        {
            throw new FormatException("Share x-coordinate 00 is invalid - shares are numbered from 01.");
        }
        return new ParsedShare(x, FromHex(yHex));

        static bool IsHex(string value) =>
            value.Length > 0 && value.All(Uri.IsHexDigit);
    }

    /// <summary>
    /// 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.
    /// </summary>
    public static string ReconstructSecret(IEnumerable<string> shares)
    {
        var shareList = shares.ToArray();
        if (shareList.Length < 2)
        {
            throw new ArgumentException("Need at least 2 shares to reconstruct.");
        }
        var byX = new Dictionary<int, byte[]>();
        foreach (var share in shareList)
        {
            var parsed = ParseShare(share);
            // The same share pasted twice is harmless (dedupe); a colliding
            // x-coordinate with a different payload cannot belong to one split.
            if (!byX.TryGetValue(parsed.X, out var existing))
            {
                byX[parsed.X] = parsed.Y;
            }
            else if (!existing.SequenceEqual(parsed.Y))
            {
                throw new ArgumentException(
                    $"Two different shares both claim x={parsed.X:x2} - they cannot come from the same split.");
            }
        }
        var points = byX.OrderBy(kv => kv.Key).ToArray();
        if (points.Length < 2)
        {
            throw new ArgumentException("Need at least 2 distinct shares to reconstruct.");
        }
        var len = points[0].Value.Length;
        if (points.Any(p => p.Value.Length != len))
        {
            throw new ArgumentException(
                "All shares must be the same length - they do not come from the same split.");
        }

        var output = new byte[len];
        var pair = points.Select(p => (X: (byte)p.Key, Y: (byte)0)).ToArray();
        for (var b = 0; b < len; b++)
        {
            for (var i = 0; i < points.Length; i++)
            {
                pair[i].Y = points[i].Value[b];
            }
            output[b] = InterpolateAtZero(pair);
        }
        return Encoding.UTF8.GetString(output);
    }
}