Shamir's Secret Sharing — Java source

// Shamir's Secret Sharing over GF(256) — the Galois field of 256 elements.
//
// Language: Java (17+, standard library only)
// Ported from src/lib/secret-sharing.ts
// 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).

import java.security.SecureRandom;
import java.util.ArrayList;
import java.util.LinkedHashMap;
import java.util.List;
import java.util.Map;

public final class SecretSharing {

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

    static {
        int x = 1;
        for (int 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;
    }

    private static final SecureRandom RANDOM = new SecureRandom();

    private SecretSharing() {
    }

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

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

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

    /** Multiplicative inverse of a non-zero element. */
    public static int gfInv(int a) {
        if (a == 0) {
            throw new ArithmeticException("0 has no multiplicative inverse in GF(256)");
        }
        return GF256_EXP[(255 - GF256_LOG[a]) % 255];
    }

    /** Divide a by b in GF(256). */
    public static int gfDiv(int a, int b) {
        if (b == 0) {
            throw new ArithmeticException("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. */
    public static int evalPoly(byte[] coeffs, int x) {
        int y = 0;
        for (int i = coeffs.length - 1; i >= 0; i--) {
            y = gfAdd(gfMul(y, x), coeffs[i] & 0xff);
        }
        return y;
    }

    /** One (x, y) point for Lagrange interpolation. */
    public record Point(int x, int 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.
     */
    public static int interpolateAtZero(List<Point> points) {
        int result = 0;
        for (int j = 0; j < points.size(); j++) {
            int xj = points.get(j).x();
            int weight = 1;
            for (int m = 0; m < points.size(); m++) {
                if (m == j) {
                    continue;
                }
                int xm = points.get(m).x();
                weight = gfMul(weight, gfDiv(xm, xj ^ xm));
            }
            result = gfAdd(result, gfMul(points.get(j).y(), weight));
        }
        return result;
    }

    private static String toHex(byte[] bytes) {
        StringBuilder sb = new StringBuilder(bytes.length * 2);
        for (byte b : bytes) {
            sb.append(String.format("%02x", b));
        }
        return sb.toString();
    }

    private static byte[] fromHex(String hex) {
        byte[] out = new byte[hex.length() / 2];
        for (int i = 0; i < out.length; i++) {
            out[i] = (byte) Integer.parseInt(hex.substring(i * 2, i * 2 + 2), 16);
        }
        return out;
    }

    /** A parsed share: its x-coordinate and its per-byte polynomial evaluations. */
    public record ParsedShare(int x, byte[] y) {
    }

    /** Parse one "xx-hex" share string; throws on any malformed input. */
    public static ParsedShare parseShare(String share) {
        String s = share.trim();
        if (s.indexOf('-') != 2 || !s.substring(0, 2).matches("[0-9a-fA-F]{2}")) {
            throw new IllegalArgumentException(
                    "Malformed share \"" + s + "\" - expected the format \"xx-hex…\" (e.g. \"01-a3b2c1\")");
        }
        String yHex = s.substring(3);
        if (!yHex.matches("[0-9a-fA-F]*") || yHex.length() % 2 != 0) {
            throw new IllegalArgumentException(
                    "Malformed share \"" + s + "\" - the payload must be an even-length hex string");
        }
        int x = Integer.parseInt(s.substring(0, 2), 16);
        if (x == 0) {
            throw new IllegalArgumentException("Share x-coordinate 00 is invalid - shares are numbered from 01");
        }
        return new ParsedShare(x, fromHex(yHex));
    }

    /**
     * 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.
     */
    public static List<String> splitSecret(String secret, int totalShares, int threshold) {
        if (threshold < 2) {
            throw new IllegalArgumentException(
                    "Threshold must be at least 2 (a 1-of-N split is just the secret itself)");
        }
        if (totalShares > 255) {
            throw new IllegalArgumentException(
                    "Total shares must be at most 255 (share x-coordinates live in 1..255)");
        }
        if (threshold > totalShares) {
            throw new IllegalArgumentException(
                    "Threshold (" + threshold + ") cannot exceed total shares (" + totalShares + ")");
        }

        byte[] bytes = secret.getBytes(java.nio.charset.StandardCharsets.UTF_8);
        byte[][] yParts = new byte[totalShares][bytes.length];
        byte[] coeffs = new byte[threshold];

        // Per secret byte: constant term = the byte, fresh random higher
        // coefficients, then evaluate the polynomial at every share's x.
        for (int b = 0; b < bytes.length; b++) {
            coeffs[0] = bytes[b];
            if (threshold > 1) {
                byte[] rnd = new byte[threshold - 1];
                RANDOM.nextBytes(rnd);
                System.arraycopy(rnd, 0, coeffs, 1, threshold - 1);
            }
            for (int i = 1; i <= totalShares; i++) {
                yParts[i - 1][b] = (byte) evalPoly(coeffs, i);
            }
        }

        List<String> shares = new ArrayList<>(totalShares);
        for (int idx = 0; idx < totalShares; idx++) {
            shares.add(String.format("%02x-%s", idx + 1, toHex(yParts[idx])));
        }
        return shares;
    }

    /**
     * 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.
     */
    public static String reconstructSecret(List<String> shares) {
        if (shares.size() < 2) {
            throw new IllegalArgumentException("Need at least 2 shares to reconstruct");
        }
        Map<Integer, byte[]> byX = new LinkedHashMap<>();
        for (String share : shares) {
            ParsedShare parsed = parseShare(share);
            byte[] existing = byX.get(parsed.x());
            // The same share pasted twice is harmless (dedupe); a colliding
            // x-coordinate with a different payload cannot belong to one split.
            if (existing == null) {
                byX.put(parsed.x(), parsed.y());
            } else if (!java.util.Arrays.equals(existing, parsed.y())) {
                throw new IllegalArgumentException("Two different shares both claim x="
                        + String.format("%02x", parsed.x()) + " - they cannot come from the same split");
            }
        }
        List<Map.Entry<Integer, byte[]>> points = new ArrayList<>(byX.entrySet());
        points.sort(Map.Entry.comparingByKey());
        if (points.size() < 2) {
            throw new IllegalArgumentException("Need at least 2 distinct shares to reconstruct");
        }
        int len = points.get(0).getValue().length;
        for (Map.Entry<Integer, byte[]> e : points) {
            if (e.getValue().length != len) {
                throw new IllegalArgumentException(
                        "All shares must be the same length - they do not come from the same split");
            }
        }

        byte[] out = new byte[len];
        List<Point> pair = new ArrayList<>();
        for (Map.Entry<Integer, byte[]> point : points) {
            pair.add(new Point(point.getKey(), 0));
        }
        for (int b = 0; b < len; b++) {
            for (int i = 0; i < points.size(); i++) {
                pair.set(i, new Point(points.get(i).getKey(), points.get(i).getValue()[b] & 0xff));
            }
            out[b] = (byte) interpolateAtZero(pair);
        }
        return new String(out, java.nio.charset.StandardCharsets.UTF_8);
    }
}