1 files changed, 278 insertions, 0 deletions
diff --git a/frozen_deps/Cryptodome/Protocol/SecretSharing.py b/frozen_deps/Cryptodome/Protocol/SecretSharing.py
new file mode 100644
index 0000000..6fdc9b4
--- /dev/null
+++ b/frozen_deps/Cryptodome/Protocol/SecretSharing.py
@@ -0,0 +1,278 @@
+#
+# SecretSharing.py : distribute a secret amongst a group of participants
+#
+# ===================================================================
+#
+# Copyright (c) 2014, Legrandin <[email protected]>
+# All rights reserved.
+#
+# Redistribution and use in source and binary forms, with or without
+# modification, are permitted provided that the following conditions
+# are met:
+#
+# 1. Redistributions of source code must retain the above copyright
+# notice, this list of conditions and the following disclaimer.
+# 2. Redistributions in binary form must reproduce the above copyright
+# notice, this list of conditions and the following disclaimer in
+# the documentation and/or other materials provided with the
+# distribution.
+#
+# THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+# "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+# LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
+# FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
+# COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
+# INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
+# BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
+# LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
+# CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
+# LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
+# ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
+# POSSIBILITY OF SUCH DAMAGE.
+# ===================================================================
+
+from Cryptodome.Util.py3compat import is_native_int
+from Cryptodome.Util import number
+from Cryptodome.Util.number import long_to_bytes, bytes_to_long
+from Cryptodome.Random import get_random_bytes as rng
+
+
+def _mult_gf2(f1, f2):
+ """Multiply two polynomials in GF(2)"""
+
+ # Ensure f2 is the smallest
+ if f2 > f1:
+ f1, f2 = f2, f1
+ z = 0
+ while f2:
+ if f2 & 1:
+ z ^= f1
+ f1 <<= 1
+ f2 >>= 1
+ return z
+
+
+def _div_gf2(a, b):
+ """
+ Compute division of polynomials over GF(2).
+ Given a and b, it finds two polynomials q and r such that:
+
+ a = b*q + r with deg(r)<deg(b)
+ """
+
+ if (a < b):
+ return 0, a
+
+ deg = number.size
+ q = 0
+ r = a
+ d = deg(b)
+ while deg(r) >= d:
+ s = 1 << (deg(r) - d)
+ q ^= s
+ r ^= _mult_gf2(b, s)
+ return (q, r)
+
+
+class _Element(object):
+ """Element of GF(2^128) field"""
+
+ # The irreducible polynomial defining this field is 1+x+x^2+x^7+x^128
+ irr_poly = 1 + 2 + 4 + 128 + 2 ** 128
+
+ def __init__(self, encoded_value):
+ """Initialize the element to a certain value.
+
+ The value passed as parameter is internally encoded as
+ a 128-bit integer, where each bit represents a polynomial
+ coefficient. The LSB is the constant coefficient.
+ """
+
+ if is_native_int(encoded_value):
+ self._value = encoded_value
+ elif len(encoded_value) == 16:
+ self._value = bytes_to_long(encoded_value)
+ else:
+ raise ValueError("The encoded value must be an integer or a 16 byte string")
+
+ def __eq__(self, other):
+ return self._value == other._value
+
+ def __int__(self):
+ """Return the field element, encoded as a 128-bit integer."""
+ return self._value
+
+ def encode(self):
+ """Return the field element, encoded as a 16 byte string."""
+ return long_to_bytes(self._value, 16)
+
+ def __mul__(self, factor):
+
+ f1 = self._value
+ f2 = factor._value
+
+ # Make sure that f2 is the smallest, to speed up the loop
+ if f2 > f1:
+ f1, f2 = f2, f1
+
+ if self.irr_poly in (f1, f2):
+ return _Element(0)
+
+ mask1 = 2 ** 128
+ v, z = f1, 0
+ while f2:
+ # if f2 ^ 1: z ^= v
+ mask2 = int(bin(f2 & 1)[2:] * 128, base=2)
+ z = (mask2 & (z ^ v)) | ((mask1 - mask2 - 1) & z)
+ v <<= 1
+ # if v & mask1: v ^= self.irr_poly
+ mask3 = int(bin((v >> 128) & 1)[2:] * 128, base=2)
+ v = (mask3 & (v ^ self.irr_poly)) | ((mask1 - mask3 - 1) & v)
+ f2 >>= 1
+ return _Element(z)
+
+ def __add__(self, term):
+ return _Element(self._value ^ term._value)
+
+ def inverse(self):
+ """Return the inverse of this element in GF(2^128)."""
+
+ # We use the Extended GCD algorithm
+ # http://en.wikipedia.org/wiki/Polynomial_greatest_common_divisor
+
+ if self._value == 0:
+ raise ValueError("Inversion of zero")
+
+ r0, r1 = self._value, self.irr_poly
+ s0, s1 = 1, 0
+ while r1 > 0:
+ q = _div_gf2(r0, r1)[0]
+ r0, r1 = r1, r0 ^ _mult_gf2(q, r1)
+ s0, s1 = s1, s0 ^ _mult_gf2(q, s1)
+ return _Element(s0)
+
+ def __pow__(self, exponent):
+ result = _Element(self._value)
+ for _ in range(exponent - 1):
+ result = result * self
+ return result
+
+
+class Shamir(object):
+ """Shamir's secret sharing scheme.
+
+ A secret is split into ``n`` shares, and it is sufficient to collect
+ ``k`` of them to reconstruct the secret.
+ """
+
+ @staticmethod
+ def split(k, n, secret, ssss=False):
+ """Split a secret into ``n`` shares.
+
+ The secret can be reconstructed later using just ``k`` shares
+ out of the original ``n``.
+ Each share must be kept confidential to the person it was
+ assigned to.
+
+ Each share is associated to an index (starting from 1).
+
+ Args:
+ k (integer):
+ The sufficient number of shares to reconstruct the secret (``k < n``).
+ n (integer):
+ The number of shares that this method will create.
+ secret (byte string):
+ A byte string of 16 bytes (e.g. the AES 128 key).
+ ssss (bool):
+ If ``True``, the shares can be used with the ``ssss`` utility.
+ Default: ``False``.
+
+ Return (tuples):
+ ``n`` tuples. A tuple is meant for each participant and it contains two items:
+
+ 1. the unique index (an integer)
+ 2. the share (a byte string, 16 bytes)
+ """
+
+ #
+ # We create a polynomial with random coefficients in GF(2^128):
+ #
+ # p(x) = \sum_{i=0}^{k-1} c_i * x^i
+ #
+ # c_0 is the encoded secret
+ #
+
+ coeffs = [_Element(rng(16)) for i in range(k - 1)]
+ coeffs.append(_Element(secret))
+
+ # Each share is y_i = p(x_i) where x_i is the public index
+ # associated to each of the n users.
+
+ def make_share(user, coeffs, ssss):
+ idx = _Element(user)
+ share = _Element(0)
+ for coeff in coeffs:
+ share = idx * share + coeff
+ if ssss:
+ share += _Element(user) ** len(coeffs)
+ return share.encode()
+
+ return [(i, make_share(i, coeffs, ssss)) for i in range(1, n + 1)]
+
+ @staticmethod
+ def combine(shares, ssss=False):
+ """Recombine a secret, if enough shares are presented.
+
+ Args:
+ shares (tuples):
+ The *k* tuples, each containin the index (an integer) and
+ the share (a byte string, 16 bytes long) that were assigned to
+ a participant.
+ ssss (bool):
+ If ``True``, the shares were produced by the ``ssss`` utility.
+ Default: ``False``.
+
+ Return:
+ The original secret, as a byte string (16 bytes long).
+ """
+
+ #
+ # Given k points (x,y), the interpolation polynomial of degree k-1 is:
+ #
+ # L(x) = \sum_{j=0}^{k-1} y_i * l_j(x)
+ #
+ # where:
+ #
+ # l_j(x) = \prod_{ \overset{0 \le m \le k-1}{m \ne j} }
+ # \frac{x - x_m}{x_j - x_m}
+ #
+ # However, in this case we are purely interested in the constant
+ # coefficient of L(x).
+ #
+
+ k = len(shares)
+
+ gf_shares = []
+ for x in shares:
+ idx = _Element(x[0])
+ value = _Element(x[1])
+ if any(y[0] == idx for y in gf_shares):
+ raise ValueError("Duplicate share")
+ if ssss:
+ value += idx ** k
+ gf_shares.append((idx, value))
+
+ result = _Element(0)
+ for j in range(k):
+ x_j, y_j = gf_shares[j]
+
+ numerator = _Element(1)
+ denominator = _Element(1)
+
+ for m in range(k):
+ x_m = gf_shares[m][0]
+ if m != j:
+ numerator *= x_m
+ denominator *= x_j + x_m
+ result += y_j * numerator * denominator.inverse()
+ return result.encode()