2 # pyssss -- Pure Python Shamir's secret sharing scheme implementation
3 # Copyright (C) 2015-2016 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 General Public License as published by
7 # the Free Software Foundation, either version 3 of the License, or
8 # (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 General Public License for more details.
15 # You should have received a copy of the GNU General Public License
16 # along with this program. If not, see <http://www.gnu.org/licenses/>.
17 """ Shamir's secret sharing scheme implementation.
19 https://en.wikipedia.org/wiki/Shamir%27s_Secret_Sharing
22 from os import urandom
24 from pygost.gost3410 import bytes2long
25 from pygost.gost3410 import long2bytes
29 POLY = 115792089237316195423570985008687907853269984665640564039457584007913129640997L
33 return x * (1 << bits)
36 def _field_mult(x, y):
38 z = b if y & 1 == 1 else 0
39 for i in xrange(1, SECRET_LEN * 8):
41 if (b >> (SECRET_LEN * 8)) & 1 == 1:
48 def _horner(t, x, coef):
50 for i in xrange(t - 1, 0, -1):
60 i = len(bin(u)[2:]) - len(bin(v)[2:])
70 def _calculate_li0(t, x, i):
75 li0 = _field_mult(li0, x[j])
76 li0 = _field_mult(li0, _field_invert(x[i] ^ x[j]))
80 def split(secret, n, t):
83 :param secret: secret needed to be splitted
84 :type secret: str, <=32 bytes
85 :param n: number of parts
87 :param t: number of necessary for recovery parts
89 :return: secret's parts
90 :rtype: list(tuple(int, str))
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 xrange(1, t):
96 coef.append(bytes2long(urandom(SECRET_LEN)))
98 for i in xrange(1, n + 1):
99 out.append((i, long2bytes(_horner(t, i, coef))[::-1]))
103 def combine(t, parts):
104 """ Combine the secret from the parts
106 :param t: number of necessary for recovery parts
108 :param parts: list of parts
109 :type parts: similar that *split()* function returns
110 :return: recovered secret
111 :rtype: str, 32 bytes
113 If secret was shorter than 32 bytes, then zeros appended as a pad.
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 = zip(*[(s[0], bytes2long(s[1][::-1])) for s in parts])
122 li0 = _calculate_li0(t, x, i)
123 li0si = _field_mult(li0, y[i])
125 return long2bytes(sec)[::-1]