ssss.py

   1 # coding: utf-8
   2 # ssss -- Pure Python Shamir's secret sharing scheme implementation
   3 # Copyright (C) 2015-2020 Sergey Matveev <stargrave@stargrave.org>
   4 #
   5 # This program is free software: you can redistribute it and/or modify
   6 # it under the terms of the GNU Lesser General Public License as
   7 # published by the Free Software Foundation, version 3 of the # License.
   8 #
   9 # This program is distributed in the hope that it will be useful,
  10 # but WITHOUT ANY WARRANTY; without even the implied warranty of
  11 # MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12 # GNU Lesser General Public License for more details.
  13 #
  14 # You should have received a copy of the GNU Lesser General Public
  15 # License along with this program.  If not, see
  16 # <http://www.gnu.org/licenses/>.
  17 """ Shamir's secret sharing scheme implementation.
  18
  19 https://en.wikipedia.org/wiki/Shamir%27s_Secret_Sharing
  20 """
  21
  22 from os import urandom
  23
  24 from pygost.utils import bytes2long
  25 from pygost.utils import long2bytes
  26
  27
  28 SECRET_LEN = 32
  29 POLY = 115792089237316195423570985008687907853269984665640564039457584007913129640997  # pylint: disable=line-too-long
  30
  31
  32 def _lshift(x, bits):
  33     return x * (1 << bits)
  34
  35
  36 def _field_mult(x, y):
  37     b = x
  38     z = b if y & 1 == 1 else 0
  39     for i in range(1, SECRET_LEN * 8):
  40         b = _lshift(b, 1)
  41         if (b >> (SECRET_LEN * 8)) & 1 == 1:
  42             b ^= POLY
  43         if y & (1 << i):
  44             z ^= b
  45     return z
  46
  47
  48 def _horner(t, x, coef):
  49     y = coef[t - 1]
  50     for i in range(t - 1, 0, -1):
  51         y = _field_mult(y, x)
  52         y ^= coef[i - 1]
  53     return y
  54
  55
  56 def _field_invert(x):
  57     u, v = x, POLY
  58     g, z = 0, 1
  59     while u > 1:
  60         i = len(bin(u)[2:]) - len(bin(v)[2:])
  61         if i < 0:
  62             u, v = v, u
  63             z, g = g, z
  64             i = -i
  65         u = u ^ _lshift(v, i)
  66         z = z ^ _lshift(g, i)
  67     return z
  68
  69
  70 def _calculate_li0(t, x, i):
  71     li0 = 1
  72     for j in range(t):
  73         if j == i:
  74             continue
  75         li0 = _field_mult(li0, x[j])
  76         li0 = _field_mult(li0, _field_invert(x[i] ^ x[j]))
  77     return li0
  78
  79
  80 def split(secret, n, t):
  81     """ Split the secret
  82
  83     :param secret: secret needed to be splitted
  84     :type secret: str, <=32 bytes
  85     :param n: number of parts
  86     :type n: int
  87     :param t: number of necessary for recovery parts
  88     :type t: int
  89     :return: secret's parts
  90     :rtype: list(tuple(int, str))
  91     """
  92     coef = [bytes2long(secret[::-1])]
  93     if n < 0 or t < 0 or n < t or not secret:
  94         raise ValueError("Invalid parameters specified")
  95     for i in range(1, t):
  96         coef.append(bytes2long(urandom(SECRET_LEN)))
  97     out = []
  98     for i in range(1, n + 1):
  99         out.append((i, long2bytes(_horner(t, i, coef))[::-1]))
 100     return out
 101
 102
 103 def combine(t, parts):
 104     """ Combine the secret from the parts
 105
 106     :param t: number of necessary for recovery parts
 107     :type t: int
 108     :param parts: list of parts
 109     :type parts: similar that *split()* function returns
 110     :return: recovered secret
 111     :rtype: str, 32 bytes
 112
 113     If secret was shorter than 32 bytes, then zeros appended as a pad.
 114     """
 115     if t <= 0 or not parts:
 116         raise ValueError("Invalid parameters specified")
 117     if len(parts) != len(set(s[1] for s in parts)):
 118         raise ValueError("Equal parts found")
 119     x, y = list(zip(*[(s[0], bytes2long(s[1][::-1])) for s in parts]))
 120     sec = 0
 121     for i in range(t):
 122         li0 = _calculate_li0(t, x, i)
 123         li0si = _field_mult(li0, y[i])
 124         sec = sec ^ li0si
 125     return long2bytes(sec)[::-1]