I will give a simple example of Shamir secret sharing. Suppose you have
some data D which you want to split up into n pieces such that any 2
of them are sufficient to reconstruct D. Shamir solves the problem for
any k of them being sufficient, but the case k=2 is especially simple.
Pick a random number m which will be the slope of a line. Take the
equation y = mx + D, and substitute x = 1, x = 2, ... x = n. Pass out
the y's for each value of x as the secret shares.
For example, if D=12, pick random m = 4, and pass out (1,16), (2,20),
(3,24), (4,28), and so on.
Now, suppose an enemy gets hold of one of these - say (2,20). What does
this tell him about the value of D? Nothing! D could be anything,
depending on the value of m.
But suppose we have two of these values - say (1,16) and (2,20). From
these it is easy to calculate m=4, and from that it is easy to see that
D=12. Two points determine a line.
In the actual Shamir scheme, integers mod a prime p are used, where p>D.
The math is basically the same. For k=3, a parabola is used instead of
a line, so that 3 points are needed; for k=4, a third-degree polynomial
is used, and for general k, a (k-1)-degree polynomial is used. In each
case, knowing k-1 points tells you nothing, because there will be a
(k-1)-degree polynomial that would pass through any possible value of
D.
Hal Finney