Shamir secret sharing is a clever idea based on a clever formula by Lagrange originally designed for interpolation in mathematical tables. Suppose that you know n+1 points {(x_i, y_i)} with distinct x’s. There is a unique nth degree polynomial p such that for each i such that 1≤i≤n, y_i = p(x_i). Lagrange’s formula is an expression in x_i, y_i and x that evaluates to that p(x). The mathematical idea is that an nth degree polynomial is uniquely determined by polynomial values for n+1 distinct arguments to the polynomial. Shamir noted that the logic of Lagrange’s formula derived solely from field properties of the reals and thus Lagrange’s formula could be used for finite fields as well.

The Reed-Solomon erasure code uses the same math in 1960.

When s is a finite subset of the field values and y(t) is the value of the polynomial for each t in s, Lagrange’s formula is:
p(x) = Σ[t in s] ((y(t)) (Π[j in s but not t] (x − j))/ (Π[j in s but not t] (i − j))).

For some q and n Shamir showed how to code a small secret S, such as an encryption key, in n values, called shares of the same size as S so that any subset of q of those values can be combined to easily compute S. Of course 0 < q ≤ n. In both the programs below split produces the shares and join retrieves the secret.

Warning!! We use the stock random number generator. You must replace it if you really want to keep a secret!!

67 is prime and 67⁴ > 2²⁴. We use GF(67), the field of integers modulo 67. We want to produce k<67 versions of a secret so that we may reconstruct the message when q (0<q<k) versions of the secret are available. (“q” for quorum). Here is the code for the fields GF(67).

and for GF(2⁸) = GF(256).