'''Secret sharing encryption and decryption.'''
from mod import Mod
from polymod import PolyMod
from random import randint
def secretShareEncrypt(c, p, n, k):
'''return a list of pairs (i, int(f(i))) for i = 1, 2, ..., k for an
n-1 degree polynomial f over Z/pZ, that has all coefficients but
the constant random, and the constant is c, where c < prime p, k < p.
This is for secret sharing with n of the pairs needed to decrypt.
For example if secretShareEncrypt(10, 11, 4, 6) were to generate the
polynomial 5x^3 + x^2 + 2x + 10 mod 11 and return
[(1, 7), (2, 3), (3, 6), (4, 2), (5, 10), (6, 5)]
then both secretShareDecrypt(11, [(3, 6), (2, 3), (5, 10), (6, 5)])
and secretShareDecrypt(11, [(2, 3), (6, 5), (5, 10), (1, 7)])
would return 10, the secret constant.
'''
# code
# simplification: You do not need to reconstruct all of f, you just need
# the number f(0) = c, so you can let x = 0 throughout the Lagrange
# calculation, from Wikipedia or the text, except make sure you only do
# division of mod p objects. (Wikipedia is over the rational field.)
def secretShareDecrypt(p, pairs):
'''Take p and any n of the pairs from secretShareEncrypt, and returns c.
>>> pairs = secretShareEncrypt(8, 17, 3, 7) #Then choose arbitrary 3 pairs:
>>> print secretShareDecrypt(17, [pairs[2], pairs[1], pairs[4]])
8
>>> print secretShareDecrypt(17, [pairs[1], pairs[6], pairs[5]])
8
>>> secretShareDecrypt(11, [(3, 6), (2, 3), (5, 10), (6, 5)])
10
>>> secretShareDecrypt(11, [(2, 3), (6, 5), (5, 10), (1, 7)])
10
'''
# code
if __name__ == '__main__':
import doctest
doctest.testmod() #verbose=True)
f = PolyMod('5x^3 + x^2 + 2x + 10', 11)
assert ([(1, 7), (2, 3), (3, 6), (4, 2), (5, 10), (6, 5)] ==
[(i, int(f(i))) for i in range(1, 7)])