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

Provided by: libgfshare-bin_2.0.0-5_amd64

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.