| 0,0 → 1,82 |
|---|
| 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)) |