Secret Sharing

I first learned about Adi Shamir’s secret sharing scheme in Bruce Schneier’s book, Applied Cryptography. Although the coverage was light, I was fascinated by the idea and thought it would make a fun feature in a movie or novel plot. But, as pointed out in the book and elsewhere (1, 2), it has practical application in everyday computing and cryptography as well.

In short, the Shamir’s scheme lets you divide a secret, M, into n shares and require only k shares (k < n) to recover the secret. For example, suppose the combination to a safe full of diamonds in a jewelry store is 42-29-56. To ensure no single employee can open the safe, the store owner divides the knowledge of the combination among five employees. However, he requires only three employees to be present to recover the entire combination and open the safe. It makes sense to distribute shares of the combination to more than just three people in case one or more are on vacation or working different shifts when the safe needs to be opened. This is where secret sharing comes in. The safe owner can distribute shares of the safe combination among five responsible employees, but require only three (any three) to recover the combination and open the safe. I’m sure you can see where this idea plays into all kinds of practical and real computing systems today (e.g., recovering master encryption keys, approving electronic payments, nuclear missile launch codes, etc.)

There are numerous, in depth explanations and examples of Shamir’s scheme on the Internet, so I won’t go into detail regarding the theory (1, 2, 3). I’ll just say it involves solving simultaneous polynomial equations using Lagrange’s Polynomial Interpolation technique. Instead, I’ll walk you through a quick example using the safe full of diamonds scenario described above.

Inputs
secret (M) = 423956
shares (n) = 5
shares required to recover secret (k) = 3

First, create a polynomial equation of degree k-1 where the secret (M) is the lone coefficient (a0) and the other coefficients are random, but larger than M. For example:
f(x) = 423956 + 266804*x^1 + 80381*x^2

Technically, the polynomial should be:
f(x) = 423956 + 266804*x^1 + 80381*x^2 mod p
where p is a prime number greater than M. Performing the mod p operation significantly reduces the size of the shares and complicates the recovery of the secret (good for security; bad for implementation). However, my reading of the scheme indicates that p must be known to all shareholders. Thus, each shareholder now has to remember two things: their share, and p. I chose to ignore p and the mod p operation for this discussion.

Generate n shares using this polynomial and distribute one share to each trusted employee.

1. f(1) = 423956 + 266804 * 1^1 + 80381 * 1^2 = 771141
2. f(2) = 423956 + 266804 * 2^1 + 80381 * 2^2 = 1279088
3. f(3) = 423956 + 266804 * 3^1 + 80381 * 3^2 = 1947797
4. f(4) = 423956 + 266804 * 4^1 + 80381 * 4^2 = 2777268
5. f(5) = 423956 + 266804 * 5^1 + 80381 * 5^2 = 3767501

Secret Recovery
Use k shares to solve k simultaneous polynomials using Lagrange Polynomial Interpolation and recover the secret (M):

1. f(1) = M + a1 * 1^1 + a2 * 1^2 = 771141
2. f(2) = M + a1 * 2^1 + a2 * 2^2 = 1279088
3. f(3) = M + a1 * 3^1 + a3 * 3^2 = 1947797

I’m not going to get into the details of Lagrange’s scheme, Wikipedia and others cover it if far more depth than I understand it. Suffice it to say, the scheme produces the polynomial: f(x) = 423956 + 266804 * x^1 + 80381 * x^2. As you can see, the secret (M), has been recovered in the a0 position of the polynomial.

Three employees with seemingly random keys were able to recover the safe combination without any one of them knowing the entire (in fact even a single digit) of the actual combination. If only two employees had tried, they would have recovered an invalid combination.

Remarks
This is a pretty cool technique; k/n shares can be combined to reconstitute a secret (M). I certainly think a movie plot is in there somewhere. A few things to note:

• The secret can only be a number. I suppose you could convert a string to an integer and use that as the secret, but due to the math involved, the integer representation of the string would need to be limited as to not overflow the polynomial calculations.
• Part of the reason I did not implement the mod p operation (in addition to what was mentioned above), is that I didn’t know how to implement a reverse mod p in the Lagrange interpolation.
• The Shamir Secret Sharing Wikipedia page does a good job explaining the scheme and the Lagrange interpolation. In addition, it contains a solid Python implementation — including the mod p calculation — should you want to experiment on your own.