diff options
| -rw-r--r-- | shamir.py | 63 |
1 files changed, 23 insertions, 40 deletions
@@ -1,51 +1,33 @@ -# Code modified from https://github.com/kurtbrose/shamir/tree/master +# Code modified from https://github.com/kurtbrose/shamir/tree/master (under CC0 +# license, so we took liberty to refactor it here) -''' -An implementation of shamir secret sharing algorithm. +import secrets -To the extent possible under law, -all copyright and related or neighboring rights -are hereby waived. (CC0, see LICENSE file.) - -All possible patents arising from this code -are renounced under the terms of -the Open Web Foundation CLA 1.0 -(http://www.openwebfoundation.org/legal/the-owf-1-0-agreements/owfa-1-0) -''' - -from __future__ import division -import random -import functools - -# 12th Mersenne Prime is 2**127 - 1 # use the prime to be compatible with the Shamir tool developed by Ava Labs: # https://github.com/ava-labs/mnemonic-shamir-secret-sharing-cli/tree/main # This is a 257-bit prime, so the returned points could be either 256-bit or # (infrequently) 257-bit. _PRIME = 187110422339161656731757292403725394067928975545356095774785896842956550853219 +# Other good choices: +# 12th Mersenne Prime is 2**127 - 1 # 13th Mersenne Prime is 2**521 - 1 -def _eval_at(poly, x, prime): - 'evaluate polynomial (coefficient tuple) at x' - accum = 0 - for coeff in reversed(poly): - accum *= x - accum += coeff - accum %= prime - return accum - def split(secret, minimum, shares, prime=_PRIME): - ''' - Generates a random shamir pool, returns - the secret and the share points. - ''' - randint = functools.partial(random.SystemRandom().randint, 0) + def y(poly, x, prime): + # evaluate polynomial (coefficient tuple) at x + accum = 0 + for coeff in reversed(poly): + accum *= x + accum += coeff + accum %= prime + return accum + if minimum > shares: raise ValueError("pool secret would be irrecoverable") - poly = [randint(prime) for i in range(minimum - 1)] + poly = [secrets.randbelow(prime) for i in range(minimum - 1)] poly.insert(0, secret) - return [_eval_at(poly, i, prime) for i in range(1, shares + 1)] + return [y(poly, i, prime) for i in range(1, shares + 1)] # division in integers modulus p means finding the inverse of the denominator @@ -60,7 +42,7 @@ def _extended_gcd(a, b): last_y = 0 while b != 0: quot = a // b - a, b = b, 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 @@ -84,7 +66,8 @@ def _lagrange_interpolate(x, x_s, y_s, p): ''' k = len(x_s) assert k == len(set(x_s)), "points must be distinct" - def PI(vals): # upper-case PI -- product of inputs + + def prod(vals): # product of inputs accum = 1 for v in vals: accum *= v @@ -94,9 +77,9 @@ def _lagrange_interpolate(x, x_s, y_s, p): 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) + nums.append(prod(x - o for o in others)) + dens.append(prod(cur - o for o in others)) + den = prod(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 @@ -105,7 +88,7 @@ def _lagrange_interpolate(x, x_s, y_s, p): def combine(shares, prime=_PRIME): ''' Recover the secret from share points - (x,y points on the polynomial) + (shares contain (x, y) as points on the polynomial) ''' if len(shares) < 2: raise ValueError("need at least two shares") |