Shamir's Secret Sharing — Kotlin source

// Shamir's Secret Sharing over GF(256) - the Galois field of 256 elements.
//
// Language: Kotlin 1.9+ (JVM), standard library only.
// Ported from src/lib/secret-sharing.ts — display source, part of CosmoDev's
// polyglot tool pages. Functionally equivalent to the TS reference: same
// inputs -> same share strings / reconstructed secrets.
//
// 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

/** Exponent table: GF256_EXP[i] = 3^i in GF(256). Index 255 mirrors index 0. */
val GF256_EXP = IntArray(256)

/** Discrete log table: GF256_LOG[3^i] = i (GF256_LOG[0] is unused). */
val GF256_LOG = IntArray(256)

/** Multiply by 2 (x) in GF(256), reducing by 0x11B - the AES "xtime". */
fun xtime(a: Int): Int =
    ((a shl 1) xor (if (a and 0x80 != 0) 0x11b else 0)) and 0xff

// Top-level property initializer: fill both tables from the generator 3.
private val tablesBuilt = run {
    var x = 1
    for (i in 0 until 255) {
        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 = x xor 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). */
fun gfAdd(a: Int, b: Int): Int = (a xor b) and 0xff

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

/** Multiplicative inverse of a non-zero element. */
fun gfInv(a: Int): Int {
    require(a != 0) { "0 has no multiplicative inverse in GF(256)" }
    return GF256_EXP[(255 - GF256_LOG[a]) % 255]
}

/** Divide a by b in GF(256). */
fun gfDiv(a: Int, b: Int): Int {
    require(b != 0) { "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. */
fun evalPoly(coeffs: IntArray, x: Int): Int {
    var y = 0
    for (i in coeffs.indices.reversed()) {
        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.
 */
fun interpolateAtZero(points: List<Pair<Int, Int>>): Int {
    var result = 0
    for (j in points.indices) {
        val (xj, yj) = points[j]
        var weight = 1
        for (m in points.indices) {
            if (m == j) continue
            val xm = points[m].first
            weight = gfMul(weight, gfDiv(xm, xj xor xm))
        }
        result = gfAdd(result, gfMul(yj, weight))
    }
    return result
}

private fun toHex(bytes: ByteArray): String =
    bytes.joinToString("") { "%02x".format(it) }

private fun fromHex(hex: String): ByteArray =
    ByteArray(hex.length / 2) { i -> hex.substring(i * 2, i * 2 + 2).toInt(16).toByte() }

private val CSPRNG = SecureRandom()

private fun defaultRandomBytes(n: Int): ByteArray =
    ByteArray(n).also(CSPRNG::nextBytes)

/** Random-bytes source for splitSecret - injectable for deterministic tests. */
fun interface RandomBytes {
    operator fun invoke(n: Int): ByteArray
}

/**
 * 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.
 */
fun splitSecret(
    secret: String,
    totalShares: Int,
    threshold: Int,
    random: RandomBytes = RandomBytes(::defaultRandomBytes),
): List<String> {
    require(threshold >= 2) {
        "Threshold must be at least 2 (a 1-of-N split is just the secret itself)"
    }
    require(totalShares <= 255) {
        "Total shares must be at most 255 (share x-coordinates live in 1..255)"
    }
    require(threshold <= totalShares) {
        "Threshold ($threshold) cannot exceed total shares ($totalShares)"
    }

    val bytes = secret.toByteArray(Charsets.UTF_8)
    val yParts = Array(totalShares) { ByteArray(bytes.size) }
    val coeffs = IntArray(threshold)

    for (b in bytes.indices) {
        coeffs[0] = bytes[b].toInt() and 0xff
        if (threshold > 1) {
            val rand = random(threshold - 1)
            for (j in 1 until threshold) coeffs[j] = rand[j - 1].toInt() and 0xff
        }
        for (i in 1..totalShares) {
            yParts[i - 1][b] = evalPoly(coeffs, i).toByte()
        }
    }

    return yParts.mapIndexed { idx, ys -> "%02x-".format(idx + 1) + toHex(ys) }
}

/** A parsed share: its x-coordinate and its per-byte polynomial evaluations. */
data class ParsedShare(val x: Int, val y: ByteArray)

/** Parse one "xx-hex" share string; throws on any malformed input. */
fun parseShare(share: String): ParsedShare {
    val s = share.trim()
    if (s.indexOf('-') != 2 || !Regex("^[0-9a-fA-F]{2}$").matches(s.take(2))) {
        throw IllegalArgumentException(
            "Malformed share \"$s\" - expected the format \"xx-hex…\" (e.g. \"01-a3b2c1\")"
        )
    }
    val yHex = s.substring(3)
    if (!Regex("^[0-9a-fA-F]*$").matches(yHex) || yHex.length % 2 != 0) {
        throw IllegalArgumentException(
            "Malformed share \"$s\" - the payload must be an even-length hex string"
        )
    }
    val x = s.take(2).toInt(16)
    if (x == 0) {
        throw IllegalArgumentException("Share x-coordinate 00 is invalid - shares are numbered from 01")
    }
    return ParsedShare(x, 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.
 */
fun reconstructSecret(shares: List<String>): String {
    if (shares.size < 2) {
        throw IllegalArgumentException("Need at least 2 shares to reconstruct")
    }
    val byX = LinkedHashMap<Int, ByteArray>()
    for (share in shares) {
        val (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.
        val existing = byX[x]
        if (existing == null) {
            byX[x] = y
        } else if (!existing.contentEquals(y)) {
            throw IllegalArgumentException(
                "Two different shares both claim x=%02x - they cannot come from the same split".format(x)
            )
        }
    }
    val points = byX.entries.sortedBy { it.key }
    if (points.size < 2) {
        throw IllegalArgumentException("Need at least 2 distinct shares to reconstruct")
    }
    val len = points[0].value.size
    if (points.any { it.value.size != len }) {
        throw IllegalArgumentException("All shares must be the same length - they do not come from the same split")
    }

    val out = ByteArray(len)
    for (b in 0 until len) {
        val pair = points.map { (x, ys) -> x to (ys[b].toInt() and 0xff) }
        out[b] = interpolateAtZero(pair).toByte()
    }
    return String(out, Charsets.UTF_8)
}