Provided by: libgfshare-bin_1.0.5-1_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.

```

#### EXAMPLEUSECASE

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

```

#### THEPRINCIPLESBEHINDSHAMIR'SMETHOD

```       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,SOWHATISAGALOISFIELDTHEN?

```       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,SOWHYISTHERENOMULTIPLICATIONINTHISIMPLEMENTATION?

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

```

#### REPORTINGBUGS

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

```

```       libgfshare is copyright © 2006 Daniel Silverstone.
```       gfsplit(1), gfcombine(1), libgfshare(3)