/usr/lib/python2.7/dist-packages/mnemonic/secretsharing.py is in python-mnemonic 0.18-1.
This file is owned by root:root, with mode 0o644.
The actual contents of the file can be viewed below.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 | # -*- coding: utf-8 -*-
"""
Secret Sharing
~~~~~
:copyright: (c) 2014 by Halfmoon Labs
:license: MIT, see LICENSE for more details.
"""
from random import randint
def egcd(a, b):
if a == 0:
return (b, 0, 1)
else:
g, y, x = egcd(b % a, a)
return (g, x - (b // a) * y, y)
def mod_inverse(k, prime):
k = k % prime
if k < 0:
r = egcd(prime, -k)[2]
else:
r = egcd(prime, k)[2]
return (prime + r) % prime
def random_polynomial(degree, intercept, upper_bound):
""" Generates a random polynomial with positive coefficients.
"""
if degree < 0:
raise ValueError('Degree must be a non-negative number.')
coefficients = [intercept]
for i in range(degree):
random_coeff = randint(0, upper_bound - 1)
coefficients.append(random_coeff)
return coefficients
def get_polynomial_points(coefficients, num_points, prime):
""" Calculates the first n polynomial points.
[ (1, f(1)), (2, f(2)), ... (n, f(n)) ]
"""
points = []
for x in range(1, num_points + 1):
# start with x=1 and calculate the value of y
y = coefficients[0]
# calculate each term and add it to y, using modular math
for i in range(1, len(coefficients)):
exponentiation = (x**i) % prime
term = (coefficients[i] * exponentiation) % prime
y = (y + term) % prime
# add the point to the list of points
points.append((x, y))
return points
def modular_lagrange_interpolation(x, points, prime):
# break the points up into lists of x and y values
x_values, y_values = zip(*points)
# initialize f(x) and begin the calculation: f(x) = SUM( y_i * l_i(x) )
f_x = 0
for i in range(len(points)):
# evaluate the lagrange basis polynomial l_i(x)
numerator, denominator = 1, 1
for j in range(len(points)):
# don't compute a polynomial fraction if i equals j
if i == j:
continue
# compute a fraction and update the existing numerator + denominator
numerator = (numerator * (x - x_values[j])) % prime
denominator = (denominator * (x_values[i] - x_values[j])) % prime
# get the polynomial from the numerator + mod inverse of the denominator
lagrange_polynomial = numerator * mod_inverse(denominator, prime)
# multiply the current y and the evaluated polynomial and add it to f(x)
f_x = (prime + f_x + (y_values[i] * lagrange_polynomial)) % prime
return f_x
def secret_int_to_points(secret_int, point_threshold, num_points, prime):
""" Split a secret (integer) into shares (pair of integers / x,y coords).
Sample the points of a random polynomial with the y intercept equal to
the secret int.
"""
if point_threshold < 2:
raise ValueError("Threshold must be >= 2.")
if point_threshold > num_points:
raise ValueError("Threshold must be < the total number of points.")
if secret_int > prime:
raise ValueError("Error! Secret is too long for share calculation!")
coefficients = random_polynomial(point_threshold - 1, secret_int, prime)
points = get_polynomial_points(coefficients, num_points, prime)
return points
def points_to_secret_int(points, prime):
""" Join int points into a secret int.
Get the intercept of a random polynomial defined by the given points.
"""
if not isinstance(points, list):
raise ValueError("Points must be in list form.")
for point in points:
if not isinstance(point, tuple) and len(point) == 2:
raise ValueError("Each point must be a tuple of two values.")
if not isinstance(point[0], int) and isinstance(point[1], int):
raise ValueError("Each value in the point must be an int.")
x_values, y_values = zip(*points)
free_coefficient = modular_lagrange_interpolation(0, points, prime)
secret_int = free_coefficient # the secret int is the free coefficient
return secret_int
|