Shamir secret sharing and recombination. Based on the paper How to share a secret by Adi Shamir in Communications of the ACM 22 (11): 612-613.
Recombines list of (xi, yi) pairs.
Shares is a list of threshold + 1 (player id, share) pairs. Recombination is done in the optional point x_recomb.
Note that player ids must be elements in the same field as the shares or otherwise the algorithm will not work.
>>> from field import GF
>>> Zp = GF(19)
>>> shares = [(Zp(i), 7 * Zp(i) + 3) for i in range(1, 4)]
>>> print shares
[({1}, {10}), ({2}, {17}), ({3}, {5})]
>>> del(shares[1])
>>> recombine(shares)
{3}
Shamir share secret.
The threshold indicates the maximum number of shares that reveal nothing about secret. The return value is a list of (player id, share) pairs.
It holds that sharing and recombination cancels each other:
>>> from field import GF
>>> Zp = GF(47)
>>> secret = Zp(42)
>>> recombine(share(secret, 7, 15)[:8]) == secret
True
The threshold can range from zero (for a dummy-sharing):
>>> share(Zp(10), 0, 5)
[({1}, {10}), ({2}, {10}), ({3}, {10}), ({4}, {10}), ({5}, {10})]
up to but not including num_players:
>>> share(Zp(10), 5, 5)
Traceback (most recent call last):
...
AssertionError: Threshold out of range
Verifies that a sharing is correct.
It is verified that the given shares correspond to points on a polynomial of at most the given degree.
>>> from field import GF
>>> Zp = GF(47)
>>> shares = [(Zp(i), Zp(i**2)) for i in range(1, 6)]
>>> print shares
[({1}, {1}), ({2}, {4}), ({3}, {9}), ({4}, {16}), ({5}, {25})]
>>> verify_sharing(shares, 2)
True
>>> verify_sharing(shares, 1)
False