ssss.py

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