Man Linux: Main Page and Category List

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

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