Man Linux: Main Page and Category List


       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,

       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


       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


       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)