Shamir's Secret Sharing — Swift source

// secret-sharing — Shamir's Secret Sharing over GF(256), the Galois field of 256 elements.
//
// Language: Swift 5.9+ (Foundation 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 Foundation

// MARK: - Errors

enum SecretSharingError: Error, CustomStringConvertible {
    case zeroInverse
    case divisionByZero
    case thresholdTooLow
    case tooManyShares
    case thresholdExceedsTotal(Int, Int)
    case noCsprng
    case malformedShare(String, String)
    case zeroXCoordinate
    case notEnoughShares
    case collidingX(Int)
    case mismatchedLengths

    var description: String {
        switch self {
        case .zeroInverse: return "0 has no multiplicative inverse in GF(256)"
        case .divisionByZero: return "Division by zero in GF(256)"
        case .thresholdTooLow: return "Threshold must be at least 2 (a 1-of-N split is just the secret itself)"
        case .tooManyShares: return "Total shares must be at most 255 (share x-coordinates live in 1..255)"
        case .thresholdExceedsTotal(let t, let n): return "Threshold (\(t)) cannot exceed total shares (\(n))"
        case .noCsprng: return "No CSPRNG available (SystemRandomNumberGenerator is the source)"
        case .malformedShare(let s, let why): return "Malformed share \"\(s)\" - \(why)"
        case .zeroXCoordinate: return "Share x-coordinate 00 is invalid - shares are numbered from 01"
        case .notEnoughShares: return "Need at least 2 distinct shares to reconstruct"
        case .collidingX(let x): return String(format: "Two different shares both claim x=%02x - they cannot come from the same split", x)
        case .mismatchedLengths: return "All shares must be the same length - they do not come from the same split"
        }
    }
}

// MARK: - GF(256) arithmetic

/// Exponent table: gf256Exp[i] = 3^i in GF(256). Index 255 mirrors index 0.
var gf256Exp = [UInt8](repeating: 0, count: 256)
/// Discrete log table: gf256Log[3^i] = i (gf256Log[0] is unused).
var gf256Log = [UInt8](repeating: 0, count: 256)

/// Multiply by 2 (x) in GF(256), reducing by 0x11B - the AES "xtime".
func xtime(_ a: UInt8) -> UInt8 {
    let doubled = UInt8((Int(a) << 1) ^ (a & 0x80 != 0 ? 0x11b : 0))
    return doubled & 0xff
}

private var tablesInitialized = false
func initTables() {
    guard !tablesInitialized else { return }
    var x: UInt8 = 1
    for i in 0..<255 {
        gf256Exp[i] = x
        gf256Log[Int(x)] = UInt8(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
    tablesInitialized = true
}

/// Addition in GF(256) is bitwise XOR (also serves as subtraction).
func gfAdd(_ a: UInt8, _ b: UInt8) -> UInt8 {
    a ^ b
}

/// Multiply two field elements via log/exp tables.
func gfMul(_ a: UInt8, _ b: UInt8) -> UInt8 {
    initTables() // idempotent - the log/exp tables are built on first use
    if a == 0 || b == 0 { return 0 }
    return gf256Exp[(Int(gf256Log[Int(a)]) + Int(gf256Log[Int(b)])) % 255]
}

/// Multiplicative inverse of a non-zero element.
func gfInv(_ a: UInt8) throws -> UInt8 {
    if a == 0 { throw SecretSharingError.zeroInverse }
    initTables()
    return gf256Exp[(255 - Int(gf256Log[Int(a)])) % 255]
}

/// Divide a by b in GF(256).
func gfDiv(_ a: UInt8, _ b: UInt8) throws -> UInt8 {
    if b == 0 { throw SecretSharingError.divisionByZero }
    if a == 0 { return 0 }
    initTables()
    return gf256Exp[(Int(gf256Log[Int(a)]) + 255 - Int(gf256Log[Int(b)])) % 255]
}

/// Evaluate a polynomial (coeffs[0] = constant term) at x, Horner style.
func evalPoly(_ coeffs: [UInt8], _ x: UInt8) -> UInt8 {
    var y: UInt8 = 0
    for i in stride(from: coeffs.count - 1, through: 0, by: -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.
 */
func interpolateAtZero(_ points: [(x: UInt8, y: UInt8)]) throws -> UInt8 {
    var result: UInt8 = 0
    for j in 0..<points.count {
        let xj = points[j].x
        let yj = points[j].y
        var weight: UInt8 = 1
        for m in 0..<points.count where m != j {
            let xm = points[m].x
            weight = gfMul(weight, try gfDiv(xm, xj ^ xm))
        }
        result = gfAdd(result, gfMul(yj, weight))
    }
    return result
}

// MARK: - Hex codec

private func toHex(_ bytes: [UInt8]) -> String {
    bytes.map { String(format: "%02x", $0) }.joined()
}

private func fromHex(_ hex: String) throws -> [UInt8] {
    var out = [UInt8]()
    out.reserveCapacity(hex.count / 2)
    var i = hex.startIndex
    while i < hex.endIndex {
        let next = hex.index(i, offsetBy: 2)
        guard next <= hex.endIndex, let b = UInt8(hex[i..<next], radix: 16) else {
            throw SecretSharingError.malformedShare(hex, "the payload must be an even-length hex string")
        }
        out.append(b)
        i = next
    }
    return out
}

/// Default CSPRNG source. SystemRandomNumberGenerator is cryptographically
/// secure on Apple platforms; injectable for deterministic tests.
typealias RandomBytes = (Int) -> [UInt8]

private func defaultRandomBytes(_ n: Int) -> [UInt8] {
    var rng = SystemRandomNumberGenerator()
    return (0..<n).map { _ in UInt8.random(in: .min ... .max, using: &rng) }
}

// MARK: - Split

/**
 * 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.
 */
func splitSecret(_ secret: String, totalShares: Int, threshold: Int,
                 getRandomBytes: RandomBytes? = nil) throws -> [String] {
    initTables()
    guard threshold >= 2 else { throw SecretSharingError.thresholdTooLow }
    guard totalShares <= 255 else { throw SecretSharingError.tooManyShares }
    guard threshold <= totalShares else { throw SecretSharingError.thresholdExceedsTotal(threshold, totalShares) }

    let bytes = Array(secret.utf8)
    let rand = getRandomBytes ?? defaultRandomBytes
    var yParts = [[UInt8]](repeating: [UInt8](repeating: 0, count: bytes.count), count: totalShares)
    var coeffs = [UInt8](repeating: 0, count: threshold)

    for b in 0..<bytes.count {
        coeffs[0] = bytes[b]
        if threshold > 1 {
            let tail = rand(threshold - 1)
            coeffs.replaceSubrange(1..., with: tail)
        }
        for i in 1...totalShares {
            yParts[i - 1][b] = evalPoly(coeffs, UInt8(i))
        }
    }

    return yParts.enumerated().map { idx, ys in
        String(format: "%02x", idx + 1) + "-" + toHex(ys)
    }
}

// MARK: - Reconstruct

/// A parsed share: its x-coordinate and its per-byte polynomial evaluations.
struct ParsedShare {
    let x: UInt8
    let y: [UInt8]
}

/// Parse one "xx-hex" share string; throws on any malformed input.
func parseShare(_ share: String) throws -> ParsedShare {
    let s = share.trimmingCharacters(in: .whitespacesAndNewlines)
    let chars = Array(s)
    guard chars.count > 3, chars[2] == "-",
          let x = UInt8(String(chars[0..<2]), radix: 16) else {
        throw SecretSharingError.malformedShare(s, "expected the format \"xx-hex\u{2026}\" (e.g. \"01-a3b2c1\")")
    }
    let yHex = String(chars[3...])
    guard yHex.allSatisfy({ $0.isASCII && $0.isHexDigit }), yHex.count % 2 == 0 else {
        throw SecretSharingError.malformedShare(s, "the payload must be an even-length hex string")
    }
    if x == 0 { throw SecretSharingError.zeroXCoordinate }
    return ParsedShare(x: x, y: try 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.
 */
func reconstructSecret(_ shares: [String]) throws -> String {
    initTables()
    guard shares.count >= 2 else { throw SecretSharingError.notEnoughShares }
    var byX: [UInt8: [UInt8]] = [:]
    for share in shares {
        let parsed = try parseShare(share)
        // The same share pasted twice is harmless (dedupe); a colliding
        // x-coordinate with a different payload cannot belong to one split.
        if let existing = byX[parsed.x] {
            if existing != parsed.y { throw SecretSharingError.collidingX(Int(parsed.x)) }
        } else {
            byX[parsed.x] = parsed.y
        }
    }
    let points = byX.sorted { $0.key < $1.key }.map { (x: $0.key, y: $0.value) }
    guard points.count >= 2 else { throw SecretSharingError.notEnoughShares }
    let len = points[0].y.count
    guard points.allSatisfy({ $0.y.count == len }) else { throw SecretSharingError.mismatchedLengths }

    var out = [UInt8](repeating: 0, count: len)
    var pair = points.map { (x: $0.x, y: UInt8(0)) }
    for b in 0..<len {
        for i in 0..<points.count { pair[i].y = points[i].y[b] }
        out[b] = try interpolateAtZero(pair)
    }
    guard let secret = String(bytes: out, encoding: .utf8) else {
        // Fewer than the true threshold yields non-UTF-8 garbage; surface it raw.
        return String(decoding: out, as: UTF8.self)
    }
    return secret
}