GFSHARE(7) | Shamir Secret Sharing in gf(2**8) | GFSHARE(7) |

# NAME¶

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

# SYNOPSIS¶

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.

# EXAMPLE USE CASE¶

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.

# THE PRINCIPLES BEHIND SHAMIR'S METHOD¶

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.

# OKAY, SO WHAT IS A GALOIS FIELD THEN?¶

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).

# OKAY, SO WHY IS THERE NO MULTIPLICATION IN THIS IMPLEMENTATION?¶

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.

# AUTHOR¶

Written by Daniel Silverstone.

# REPORTING BUGS¶

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

# COPYRIGHT¶

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.

# SEE ALSO¶

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

February 2006 | 2.0.0 |