gfshare - explanation of Shamir Secret Sharing in gf(2**8)

In simple terms, this package provides a library for implementing the sharing of
secrets and two tools for simple use-cases of the algorithm. The library
implements what is known as Shamir's method for secret sharing in the Galois
Field 2**8. In slightly simpler words, this is N-of-M secret-sharing
byte-by-byte. Essentially this allows us to split a secret S into any M shares
S(1) to S(M) such that any N of those shares can be used to reconstruct S but
any less than N shares yields no information whatsoever.

Alice has a GPG secret key on a usb keyring. If she loses that keyring, she will
have to revoke the key. This sucks because she go to conferences lots and is
scared that she will, eventually, lose the key somewhere. So, if, instead she
needed both her laptop and the usb keyring in order to have her secret key,
losing one or the other does not compromise her gpg key. Now, if she splits
the key into a 3-of-5 share, put one share on her desktop, one on the laptop,
one on her server at home, and two on the keyring, then the
keyring-plus-any-machine will yield the secret gpg key, but if she loses the
keyring, She can reconstruct the gpg key (and thus make a new share, rendering
the shares on the lost usb keyring worthless) with her three machines at home.

What Shamir's method relies on is the creation of a random polynomial, the
sampling of various coordinates along the curve of the polynomial and then the
interpolation of those points in order to re-calculate the y-intercept of the
polynomial in order to reconstruct the secret. Consider the formula for a
straight line:

**Y = Mx + C**. This formula (given values for M and C)
uniquely defines a line in two dimensions and such a formula is a polynomial
of order 1. Any line in two dimensions can also be uniquely defined by stating
any two points along the line. The number of points required to uniquely
define a polynomial is thus one higher than the order of the polynomial. So a
line needs two points where a quadratic curve needs three, a cubic curve four,
etc.

When we create a N-of-M share, we encode the secret as the y-intercept of a
polynomial of order N-1 since such a polynomial needs N points to uniquely
define it. Let us consider the situation where N is 2: We need a polynomial of
order 1 (a straight line). Let us also consider the secret to be 9, giving the
formula for our polynomial as:

**Y = Ax + 9**. We now pick a random
coefficient for the graph, we'll use 3 in this example. This yields the final
polynomial:

**Sx = 3x + 9**. Thus the share of the secret at point x is
easily calculated. We want some number of shares to give out to our
secret-keepers; let's choose three as this number. We now need to select three
points on the graph for our shares. For simplicity's sake, let us choose 1, 2
and 3. This makes our shares have the values 12, 15 and 18. No single share
gives away any information whatsoever about the value of the coefficient A and
thus no single share can be used to reconstruct the secret.

Now, consider the shares as coordinates (1, 12) (2, 15) and (3, 18) - again, no
single share is of any use, but any two of the shares uniquely define a line
in two-dimensional space. Let us consider the use of the second and third
shares. They give us the pair of simulaneous equations:

**15 = 2M + S** and

**18 = 3M + S**. We can trivially solve these equations for A and S and
thus recover our secret of 9.

Solving simultaneous equations isn't ideal for our use due to its complexity, so
we use something called a '

*Lagrange Interpolating Polynomial*'. Such a
polynomial is defined as being the polynomial P(x) of degree n-1 which passes
through the n points (x1, y1 = f(x1)) ... (xn, yn = f(xn)). There is a long
and complex formula which can then be used to interpolate the y-intercept of
P(x) given the n sets of coordinates. There is a good explanation of this at
http://mathworld.wolfram.com/LagrangeInterpolatingPolynomial.html.

A Galois Field is essentially a finite set of values. In particular, the field
we are using in this library is gf(2**8) or gf(256) which is the values 0 to
255. This is, cunningly enough, exactly the field of a byte and is thus rather
convenient for use in manipulating arbitrary amounts of data. In particular,
performing the share in gf(256) has the property of yielding shares of exactly
the same size as the secret. Mathematics within this field has various
properties which we can use to great effect. In particular, addition in any
Galois Field of the form gf(2**n) is directly equivalent to bitwise
exclusive-or (an operation computers are quite fast at indeed). Also, given
that

**(X op Y) mod F == ((X mod F) op (Y mod F)) mod F** we can perform
maths on values inside the field and keep them within the field trivially by
truncating them to the relevant number of bits (eight).

For speed reasons, this implementation uses log and exp as lookup tables to
perform multiplication in the field. Since

**exp( log(X) + log(Y) ) == X *
Y** and since table lookups are much faster than multiplication and then
truncation to fit in a byte, this is a faster but still 100% correct way to do
the maths.

Written by Daniel Silverstone.

Report bugs against the libgfshare product on www.launchpad.net.

libgfshare is copyright © 2006 Daniel Silverstone.

This is free software. You may redistribute copies of it under the terms of the
MIT licence (the COPYRIGHT file in the source distribution). There is NO
WARRANTY, to the extent permitted by law.

gfsplit(1), gfcombine(1), libgfshare(3)