// Package seal: shamir.go implements Shamir's Secret Sharing over
// GF(256) for the master key recovery (REQ-147, D-241, C-35). Splits
// a 32-byte secret into N shards with threshold T (3-of-5 default).
// Any T shards reconstruct the secret; fewer than T reveal nothing.
package seal

import (
	"crypto/rand"
	"fmt"
)

// ShamirSplit splits secret into n shards with threshold t. Any t
// shards can reconstruct the secret; fewer reveal nothing. Returns
// n shards (each is secret-length + 1 byte index). The first byte of
// each shard is the x-coordinate (1..n); the remaining bytes are the
// y-coordinates evaluated at x over GF(256).
func ShamirSplit(secret []byte, n, t int) ([][]byte, error) {
	if t < 2 || t > n {
		return nil, fmt.Errorf("shamir: threshold %d must be 2..n (%d)", t, n)
	}
	if n > 254 {
		return nil, fmt.Errorf("shamir: n %d exceeds 254 (GF(256) limit)", n)
	}
	if len(secret) == 0 {
		return nil, fmt.Errorf("shamir: secret is empty")
	}

	// Generate t-1 random coefficients (degree t-1 polynomial).
	coeffs := make([][]byte, t)
	coeffs[0] = secret // constant term = the secret
	for i := 1; i < t; i++ {
		c := make([]byte, len(secret))
		if _, err := rand.Read(c); err != nil {
			return nil, fmt.Errorf("shamir: coeff rand: %w", err)
		}
		coeffs[i] = c
	}

	shards := make([][]byte, n)
	for x := 1; x <= n; x++ {
		shard := make([]byte, len(secret)+1)
		shard[0] = byte(x) // x-coordinate
		for j := 0; j < len(secret); j++ {
			// Evaluate the polynomial at x over GF(256):
			// y = coeffs[0][j] + coeffs[1][j]*x + coeffs[2][j]*x^2 + ...
			y := byte(0)
			xPow := byte(1) // x^0
			for k := 0; k < t; k++ {
				y ^= gfMul(coeffs[k][j], xPow)
				xPow = gfMul(xPow, byte(x))
			}
			shard[j+1] = y
		}
		shards[x-1] = shard
	}
	return shards, nil
}

// ShamirCombine reconstructs the secret from >= threshold shards
// using Lagrange interpolation over GF(256). Extra shards (beyond
// threshold) are ignored.
func ShamirCombine(shards [][]byte) ([]byte, error) {
	if len(shards) < 2 {
		return nil, fmt.Errorf("shamir: need at least 2 shards, got %d", len(shards))
	}
	// Verify all shards have the same length.
	shardLen := len(shards[0])
	if shardLen < 2 {
		return nil, fmt.Errorf("shamir: shard too short (%d)", shardLen)
	}
	for _, s := range shards {
		if len(s) != shardLen {
			return nil, fmt.Errorf("shamir: shard length mismatch")
		}
	}
	secretLen := shardLen - 1
	secret := make([]byte, secretLen)

	// Lagrange interpolation: for each byte position, recover the
	// constant term (the secret byte) from the y-values at the
	// given x-coordinates.
	for j := 0; j < secretLen; j++ {
		// Collect (x, y) pairs for this byte position.
		xs := make([]byte, len(shards))
		ys := make([]byte, len(shards))
		for i, s := range shards {
			xs[i] = s[0]
			ys[i] = s[j+1]
		}
		// Compute Lagrange basis at x=0 (recover the constant term).
		secret[j] = lagrangeAtZero(xs, ys)
	}
	return secret, nil
}

// lagrangeAtZero computes the Lagrange interpolation at x=0 over
// GF(256), which recovers the constant term (the secret).
func lagrangeAtZero(xs, ys []byte) byte {
	result := byte(0)
	for i := range xs {
		// Basis polynomial L_i(0) = product over j!=i of (0 - x_j) / (x_i - x_j)
		num := byte(1)
		den := byte(1)
		for j := range xs {
			if i == j {
				continue
			}
			num = gfMul(num, xs[j]) // (0 - x_j) = x_j in GF(256) (addition = XOR)
			den = gfMul(den, xs[i]^xs[j])
		}
		// L_i(0) = num / den = num * den^-1
		lagrange := gfMul(num, gfInv(den))
		result ^= gfMul(ys[i], lagrange)
	}
	return result
}

// gfMul multiplies two elements in GF(256) using the standard
// Russian-peasant algorithm with the AES polynomial (0x11B).
func gfMul(a, b byte) byte {
	var result byte
	for i := 0; i < 8; i++ {
		if b&1 != 0 {
			result ^= a
		}
		hiBit := a & 0x80
		a <<= 1
		if hiBit != 0 {
			a ^= 0x1B // AES irreducible polynomial
		}
		b >>= 1
	}
	return result
}

// gfInv computes the multiplicative inverse in GF(256) via
// exponentiation (a^254 = a^-1 in GF(256), since a^255 = 1).
func gfInv(a byte) byte {
	if a == 0 {
		return 0 // 0 has no inverse; callers ensure den != 0
	}
	// a^254 = a^(11111110b)
	result := a
	for i := 0; i < 6; i++ {
		result = gfMul(result, result) // a^(2^(i+1))
		// Set the bit for 254 = 0b11111110
	}
	// a^254 = a^2 * a^4 * a^8 * a^16 * a^32 * a^64 * a^128
	// = a^(2+4+8+16+32+64+128) = a^254
	// Recompute properly via repeated squaring with accumulation.
	result = byte(1)
	acc := a
	for bit := 1; bit < 256; bit <<= 1 {
		if bit&254 != 0 { // 254 = 0b11111110
			result = gfMul(result, acc)
		}
		acc = gfMul(acc, acc)
	}
	return result
}
