libgfshare: A C repository from djpohly

Library for Shamir Secret Sharing in the Galois Field 2**8
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

This library implements what is known as Shamir Secret Sharing. This
entails encoding a secret as an integer and then constructing a
polynomial whose coefficients are random and calculating coordinate
pairs along the resultant curve. These coordinate pairs are considered
'shares' and by controlling the order of the polynomial we can control
the number of shares required to be able to recover the secret.

In this manner we can split a secret into any 'C' shares, any 'T' of
which can be used to recover the secret.

This would be useful, for example, in looking after GPG secret keys
used rarely, but whose security is paramount. For example a key used
to sign the key which signs the Debian or Ubuntu package archives.

If you wish to know more about how the secret sharing works and why it
is safe, then there exist many articles on the mathematics behind it.

This particular implementation was very heavily inspired by the work
of Mark D. Wooding (mdw) in his catacomb library. Thanks go to Mark
for offering to share this implementation with me.

Using the library is very easy. The tests and sample tools are very
straightforward and the header file tells you what each function is
used for.

 -- Daniel Silverstone. 2006-01-15

Recovering from previous versions of gfsplit producing foo.000
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

The quick version: if you have split a secret into shares and one
of them is numbered 000, recover the secret by re-labelling it to
001 (i.e. rename the file, if you're using gfcombine).

Previous versions of libgfshare could incorrectly produce a share
numbered 000, and the gfsplit utility would produce such a share
sometimes (with the default settings, a 3-of-5 share, this will
happen about 2% of the time). In gfsplit this produces filenames
ending with ".000".

Mathematically, the "share" numbered 0 would be the secret itself,
which is why it shouldn't be used. However, due to the way libgfshare
implements multiplication via exp/log tables, the output will
actually be a copy of the data that would appear in share number 001,
so the secret is not actually leaked.

Recombining shares that include share number 000 doesn't work: it's
silently ignored. If share 000 is renamed to share 001, recombination
should work; the exception is if you already had a copy of share 001,
in which case you can only recover the secret by having one extra share
above the normal threshold.

 -- Simon McVittie. 2009-11-18
djpohly/libgfshare
