Shamir's (k, n) Threshold Secret Sharing Simulator

Shamir's scheme relies on a fundamental theorem of polynomial algebra: 2 points uniquely define a straight line, 3 points uniquely define a parabola, and $k$ points uniquely define a polynomial of degree $k-1$.

#### 1. Splitting the Secret (Degree $k-1$ Polynomial) To split a secret $S$ into $n$ shares with threshold $k$, the algorithm constructs a random polynomial $f(x)$ of degree $k-1$ where the constant term ($y$-intercept $f(0)$) is the secret itself:

$$f(x) = S + a_1 x + a_2 x^2 + \dots + a_{k-1} x^{k-1} \pmod p$$

where coefficients $a_1, \dots, a_{k-1}$ are randomly chosen from a finite Galois field $\text{GF}(p)$ with prime $p > S, n$. The $n$ shares are distinct coordinate pairs $(x_1, f(x_1)), (x_2, f(x_2)), \dots, (x_n, f(x_n))$.

#### 2. Reconstructing the Secret (Lagrange Interpolation) Given any $k$ distinct shares $(x_i, y_i)$, the master secret $S = f(0)$ is recovered using Lagrange Polynomial Interpolation:

$$f(0) = \sum_{j=1}^k y_j \prod_{m e j} \frac{-x_m}{x_j - x_m} \pmod p$$

Shamir's scheme provides information-theoretic security (perfect secrecy): having $k-1$ or fewer shares leaves all possible candidate secrets equally likely. An adversary with infinite computing power cannot extract a single bit of information about the secret without reaching the $k$ threshold.