2 # pyssss -- Pure Python Shamir's secret sharing scheme implementation
3 # Copyright (C) 2015-2019 Sergey Matveev <stargrave@stargrave.org>
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.
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.
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.
20 https://en.wikipedia.org/wiki/Shamir%27s_Secret_Sharing
23 from os import urandom
25 from pygost.utils import bytes2long
26 from pygost.utils import long2bytes
30 POLY = 115792089237316195423570985008687907853269984665640564039457584007913129640997 # pylint: disable=line-too-long
34 return x * (1 << bits)
37 def _field_mult(x, y):
39 z = b if y & 1 == 1 else 0
40 for i in range(1, SECRET_LEN * 8):
42 if (b >> (SECRET_LEN * 8)) & 1 == 1:
49 def _horner(t, x, coef):
51 for i in range(t - 1, 0, -1):
61 i = len(bin(u)[2:]) - len(bin(v)[2:])
71 def _calculate_li0(t, x, i):
76 li0 = _field_mult(li0, x[j])
77 li0 = _field_mult(li0, _field_invert(x[i] ^ x[j]))
81 def split(secret, n, t):
84 :param secret: secret needed to be splitted
85 :type secret: str, <=32 bytes
86 :param n: number of parts
88 :param t: number of necessary for recovery parts
90 :return: secret's parts
91 :rtype: list(tuple(int, str))
93 coef = [bytes2long(secret[::-1])]
94 if n < 0 or t < 0 or n < t or not secret:
95 raise ValueError("Invalid parameters specified")
97 coef.append(bytes2long(urandom(SECRET_LEN)))
99 for i in range(1, n + 1):
100 out.append((i, long2bytes(_horner(t, i, coef))[::-1]))
104 def combine(t, parts):
105 """ Combine the secret from the parts
107 :param t: number of necessary for recovery parts
109 :param parts: list of parts
110 :type parts: similar that *split()* function returns
111 :return: recovered secret
112 :rtype: str, 32 bytes
114 If secret was shorter than 32 bytes, then zeros appended as a pad.
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]))
123 li0 = _calculate_li0(t, x, i)
124 li0si = _field_mult(li0, y[i])
126 return long2bytes(sec)[::-1]