"""
The following Python implementation of Shamir's Secret Sharing is
released into the Public Domain under the terms of CC0 and OWFa:
https://creativecommons.org/publicdomain/zero/1.0/
http://www.openwebfoundation.org/legal/the-owf-1-0-agreements/owfa-1-0

See the bottom few lines for usage. Tested on Python 2 and 3.
"""

from __future__ import division
from __future__ import print_function

import random
import functools
from CH.ChameleonHash import SK, PK

# 12th Mersenne Prime
# (for this application we want a known prime number as close as
# possible to our security level; e.g.  desired security level of 128
# bits -- too large and all the ciphertext is large; too small and
# security is compromised)
_PRIME = 2 ** 127 - 1
# 13th Mersenne Prime is 2**521 - 1

_RINT = functools.partial(random.SystemRandom().randint, 0)

def _eval_at(poly, x, prime):
    """Evaluates polynomial (coefficient tuple) at x, used to generate a
    shamir pool in make_random_shares below.
    """
    accum = 0
    for coeff in reversed(poly):
        accum *= x
        accum += coeff
        accum %= prime
    return accum

def make_random_shares(secret, minimum, shares, prime=_PRIME):
    """
    Generates a random shamir pool for a given secret, returns share points.
    """
    if minimum > shares:
        raise ValueError("Pool secret would be irrecoverable.")
    poly = [secret] + [_RINT(prime - 1) for i in range(minimum - 1)]
    points = [(i, _eval_at(poly, i, prime))
              for i in range(1, shares + 1)]
    return points

def _extended_gcd(a, b):
    x = 0
    last_x = 1
    y = 1
    last_y = 0
    while b != 0:
        quot = a // b
        a, b = b, a % b
        x, last_x = last_x - quot * x, x
        y, last_y = last_y - quot * y, y
    return last_x, last_y


def _divmod(num, den, p):
    """Compute num / den modulo prime p

    To explain what this means, the return value will be such that
    the following is true: den * _divmod(num, den, p) % p == num
    """
    inv, _ = _extended_gcd(den, p)
    return num * inv

def _lagrange_interpolate(x, x_s, y_s, p):
    """
    Find the y-value for the given x, given n (x, y) points;
    k points will define a polynomial of up to kth order.
    """
    k = len(x_s)
    assert k == len(set(x_s)), "points must be distinct"
    def PI(vals):  # upper-case PI -- product of inputs
        accum = 1
        for v in vals:
            accum *= v
        return accum
    nums = []  # avoid inexact division
    dens = []
    for i in range(k):
        others = list(x_s)
        cur = others.pop(i)
        nums.append(PI(x - o for o in others))
        dens.append(PI(cur - o for o in others))
    den = PI(dens)
    num = sum([_divmod(nums[i] * den * y_s[i] % p, dens[i], p)
               for i in range(k)])
    return (_divmod(num, den, p) + p) % p

def recover_secret(shares, prime=_PRIME):
    """
    Recover the secret from share points
    (x, y points on the polynomial).
    """
    if len(shares) < 2:
        raise ValueError("need at least two shares")
    x_s, y_s = zip(*shares)
    return _lagrange_interpolate(0, x_s, y_s, prime)


def split(SK):
    SK = str(SK)
    print(SK)
    secret_1 = SK[:len(SK)//2]
    secret_2 = SK[len(SK)//2:]
    return int(secret_1), int(secret_2)


def recover_split(secret_1, secret_2):
    return int(str(secret_1) + str(secret_2))


def secret_share(SK, minimum, shares):
    secret_1, secret_2 = split(SK)
    shares_1 = make_random_shares(secret_1, minimum=minimum, shares=shares)
    shares_2 = make_random_shares(secret_2, minimum=minimum, shares=shares)
    return recover_split(recover_secret(shares_1[:minimum]), recover_secret(shares_2[-minimum:]))

def main():
    """Main function"""

    secret_1, secret_2 = split(SK)
    print(secret_1)
    print(secret_2)

    shares_1 = make_random_shares(secret_1, minimum=2, shares=5)
    shares_2 = make_random_shares(secret_2, minimum=2, shares=5)

    print('Secret 1:                                                     ',
          secret_1)
    print('Secret 2:                                                     ',
          secret_2)
    print('Shares:')
    if shares_1:
        for share in shares_1:
            print('  ', share)

    if shares_2:
        for share in shares_2:
            print('  ', share)

    print('Secret recovered from minimum subset of shares:             ',
          recover_secret(shares_1[:2]))
    print('Secret recovered from a different minimum subset of shares: ',
          recover_secret(shares_2[-2:]))

    print(type(recover_split(recover_secret(shares_1[:2]), recover_secret(shares_2[-2:]))))

    secret_share(SK, 2, 3)

if __name__ == '__main__':
    main()