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)) |