Subversion Repositories Code-Repo

from operator import mul
from random import randrange, sample
from functools import reduce

def Extended_Euclidian(a, b):
    ''' Takes values a and b and returns a tuple (r,s,t) in the following format:
        r = s * a + t * b where r is the GCD and s and t are the inverses of a and b'''
    t_ = 0
    t = 1
    s_ = 1
    s = 0
    q = a//b
    r = a - q * b
    # print("%d\t= %d * %d + %d" % (a, q, b, r))
    while r > 0:
        temp = t_ - q * t
        t_ = t
        t = temp
        temp = s_ - q * s
        s_ = s
        s = temp
        a = b
        b = r
        q = a//b
        r = a - q * b
        # print("%d\t= %d * %d + %d" % (a, q, b, r))
    r = b
    return (r, s, t)

def Inverse(a, b):
    '''Returns the multiplicative inverse of a mod b'''
    ret = Extended_Euclidian(a,b)
    if (ret[1] < 0):
        inv = ret[1] + b
    else:
        inv = ret[1]
    return inv

def prod(nums):
    """Product of nums"""
    return reduce(mul, nums, 1)

def horner_mod(coeffs, mod):
    """Polynomial with coeffs of degree len(coeffs) via Horner's rule; uses
    modular arithmetic. For example, if coeffs = [1,2,3] and mod = 5, this
    returns the function x --> (x, y) where y = 1 + 2x + 3x^2 mod 5."""
    return lambda x: (x,
            reduce(lambda a, b: a * x + b % mod, reversed(coeffs), 0) % mod)


def shamir_threshold(S, k, n, p):
    """Shamir's simple (k, n) threshold scheme. Returns xy_pairs genrated by
    secret polynomial mod p with constant term = S. Information is given to n
    different people any k of which constitute enough to reconstruct the secret
    data."""
    coeffs = [S]
# Independent but not necessarily unique; choose k - 1 coefficients from [1, p)
    coeffs.extend(randrange(1, p) for _ in range(k - 1))
# x values are unique
    return map(horner_mod(coeffs, p), sample(range(1, p), n))


def interp_const(xy_pairs, k, p):
    """Use Lagrange Interpolation to find the constant term of the degree k
    polynomial (mod p) that gave the xy-pairs; we get to use a shortcut since
    we are only after the constant term for which x = 0."""
    assert len(xy_pairs) >= k, "Not enough points for interpolation"
    x = lambda i: xy_pairs[i][0]
    y = lambda i: xy_pairs[i][1]
    return sum(y(i) * prod(x(j) * Inverse(x(j) - x(i), p) % p for j in range(k) if j != i) for i in range(k)) % p


if __name__ == "__main__":
    k, n, p = 5, 9, 81342267667
    pairs = [(11,29952055635),(22,26786192733),(33,77756881208),(44,80139093118),(55,24225052606),
            (66,74666503567),(77,1078845979),(88,72806030240),(99,1471177497)]
    for i in range(9):
        lst = []
        for j in range(9):
            if i != j:
                lst.append(pairs[j])
        print("Omitting Share", (i), ":", interp_const(lst,k,p))