| 219 |
Kevin |
1 |
from operator import mul
|
|
|
2 |
from random import randrange, sample
|
|
|
3 |
from functools import reduce
|
|
|
4 |
|
|
|
5 |
def Extended_Euclidian(a, b):
|
|
|
6 |
''' Takes values a and b and returns a tuple (r,s,t) in the following format:
|
|
|
7 |
r = s * a + t * b where r is the GCD and s and t are the inverses of a and b'''
|
|
|
8 |
t_ = 0
|
|
|
9 |
t = 1
|
|
|
10 |
s_ = 1
|
|
|
11 |
s = 0
|
|
|
12 |
q = a//b
|
|
|
13 |
r = a - q * b
|
|
|
14 |
# print("%d\t= %d * %d + %d" % (a, q, b, r))
|
|
|
15 |
while r > 0:
|
|
|
16 |
temp = t_ - q * t
|
|
|
17 |
t_ = t
|
|
|
18 |
t = temp
|
|
|
19 |
temp = s_ - q * s
|
|
|
20 |
s_ = s
|
|
|
21 |
s = temp
|
|
|
22 |
a = b
|
|
|
23 |
b = r
|
|
|
24 |
q = a//b
|
|
|
25 |
r = a - q * b
|
|
|
26 |
# print("%d\t= %d * %d + %d" % (a, q, b, r))
|
|
|
27 |
r = b
|
|
|
28 |
return (r, s, t)
|
|
|
29 |
|
|
|
30 |
def Inverse(a, b):
|
|
|
31 |
'''Returns the multiplicative inverse of a mod b'''
|
|
|
32 |
ret = Extended_Euclidian(a,b)
|
|
|
33 |
if (ret[1] < 0):
|
|
|
34 |
inv = ret[1] + b
|
|
|
35 |
else:
|
|
|
36 |
inv = ret[1]
|
|
|
37 |
return inv
|
|
|
38 |
|
|
|
39 |
def prod(nums):
|
|
|
40 |
"""Product of nums"""
|
|
|
41 |
return reduce(mul, nums, 1)
|
|
|
42 |
|
|
|
43 |
def horner_mod(coeffs, mod):
|
|
|
44 |
"""Polynomial with coeffs of degree len(coeffs) via Horner's rule; uses
|
|
|
45 |
modular arithmetic. For example, if coeffs = [1,2,3] and mod = 5, this
|
|
|
46 |
returns the function x --> (x, y) where y = 1 + 2x + 3x^2 mod 5."""
|
|
|
47 |
return lambda x: (x,
|
|
|
48 |
reduce(lambda a, b: a * x + b % mod, reversed(coeffs), 0) % mod)
|
|
|
49 |
|
|
|
50 |
|
|
|
51 |
def shamir_threshold(S, k, n, p):
|
|
|
52 |
"""Shamir's simple (k, n) threshold scheme. Returns xy_pairs genrated by
|
|
|
53 |
secret polynomial mod p with constant term = S. Information is given to n
|
|
|
54 |
different people any k of which constitute enough to reconstruct the secret
|
|
|
55 |
data."""
|
|
|
56 |
coeffs = [S]
|
|
|
57 |
# Independent but not necessarily unique; choose k - 1 coefficients from [1, p)
|
|
|
58 |
coeffs.extend(randrange(1, p) for _ in range(k - 1))
|
|
|
59 |
# x values are unique
|
|
|
60 |
return map(horner_mod(coeffs, p), sample(range(1, p), n))
|
|
|
61 |
|
|
|
62 |
|
|
|
63 |
def interp_const(xy_pairs, k, p):
|
|
|
64 |
"""Use Lagrange Interpolation to find the constant term of the degree k
|
|
|
65 |
polynomial (mod p) that gave the xy-pairs; we get to use a shortcut since
|
|
|
66 |
we are only after the constant term for which x = 0."""
|
|
|
67 |
assert len(xy_pairs) >= k, "Not enough points for interpolation"
|
|
|
68 |
x = lambda i: xy_pairs[i][0]
|
|
|
69 |
y = lambda i: xy_pairs[i][1]
|
|
|
70 |
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
|
|
|
71 |
|
|
|
72 |
|
|
|
73 |
if __name__ == "__main__":
|
|
|
74 |
k, n, p = 5, 9, 81342267667
|
|
|
75 |
pairs = [(11,29952055635),(22,26786192733),(33,77756881208),(44,80139093118),(55,24225052606),
|
|
|
76 |
(66,74666503567),(77,1078845979),(88,72806030240),(99,1471177497)]
|
|
|
77 |
for i in range(9):
|
|
|
78 |
lst = []
|
|
|
79 |
for j in range(9):
|
|
|
80 |
if i != j:
|
|
|
81 |
lst.append(pairs[j])
|
|
|
82 |
print("Omitting Share", (i), ":", interp_const(lst,k,p))
|