abrightersun.de Assume you have a secret that should only be revealed when several participants team up with their corresponding shares. Say, you have a CA certificate in a big company and you don't trust one person alone to behave themself.
Adi Shamir presented in "How to share a secret" a simple yet effective method to share a secret number $D$ with $n$ participants in such a way that at least $k$ shares are needed to reconstruct $D$.
The background of the sharing method is a simple polynomial of degree $k-1$ with random (integer) coefficients except for the constant term which represents $D$. As high-school math tells us, we need at least $k$ $(x,f(x))$ pairs to reconstruct a polynomial of degree $k-1$. See the next picture for an idea of how unlikely it is to guess a polynomial of degree $4$ with just $1,2,$ or $3$ random shares.
The sharing is done by evaluating the generated polynomial at $n$ points and distributing one pair of $(x,f(x))$ to each participant.
Joining the secret is done by collecting at least $k$ shares and fitting a $k-1$-degree polynomial to the observed function values.
One way to reconstruct a polynomial is to use Lagrange interpolation polynomials. Given $k$ unique observations $(x,f(x))$, the original polynomial of degree $k-1$ will be reconstructed exactly.
All that is left is to project a string $msg$ of bytes onto a number $D$ and back again. I chose to use a base-257 representation to circumvent the problem of reconstructing $D=0$.
Okay, up til here everything is "normal" straight-forward math. One more step: Let's compute everything with finite field arithmetics modulo prime $P$. What does that get us? Reconstruction of the polynomial gets much harder on one hand (see Chinese remainder theorem), on the other hand computations get faster since our numbers are always smaller than $P$.
One problem remains: We are handling quite big integers (often bigger than 64 bit), so we need special purpose libraries (I strongly suggest gmplib). We can get around that by deliberately choosing a relatively small $P$, but that means brute-forcing the secret gets easier. To counter-act that, we split the secret string into small chunks before encoding them. This way we get a heap of by itself simpler, but in the bigger picture harder to crack polynomials. Small coefficients also allow us to get away with standard precision arithmetics.
If I have made you curious, hop on over to the code on github.
Please note: I have not extensively studied cryptography! Although I have read quite a lot on this subject, common sense dictates a thorough dissemination of my implementation before using it in any way!