# HG changeset patch # User Laman # Date 2020-05-03 18:28:16 # Node ID 32a0e0fcabd0602a54796796b5e82bd9174a4698 # Parent eba1ea340d1f3035fb286eca86195fe111860380 optimized the reconstruction operation diff --git a/readme.md b/readme.md --- a/readme.md +++ b/readme.md @@ -10,7 +10,7 @@ Can be run straight from the cloned repo ## Performance ## -As it is, the code is not very fast. Splitting takes _n_ evaluations of a polynomial of order _k_ over Galois field 256, leading to _O(n\*k)_ finite field multiplications. Reconstruction of the constant parameters during joining similarly takes _O(k\*k)_ multiplications. +As it is, the code is not very fast. Let's assume we have a secret of length _m_. For each byte, the splitting takes _n_ evaluations of a polynomial of order _k_ over Galois field 256, leading to _O(n\*k\*m)_ finite field multiplications. Reconstruction of the constant parameters during joining takes _O(k\*k + k\*m)_ multiplications. Benchmark results, all values mean _seconds per byte_ of the secret length: @@ -21,23 +21,23 @@ Benchmark results, all values mean _seco - - + + - - + + - - + + - - + +

2 / 3 (a Raspberry Pi 3)	7.99e-05	0.000428	8.32e-05	0.000435
2 / 3 (a laptop)	1e-05	6.7e-05	1.09e-05	7.17e-05
254 / 254 (a Raspberry Pi 3)	0.417	0.471	0.414	0.0314
254 / 254 (a laptop)	0.0431	0.0542	0.0435	0.00347

diff --git a/src/shamira/condensed.py b/src/shamira/condensed.py --- a/src/shamira/condensed.py +++ b/src/shamira/condensed.py @@ -27,7 +27,7 @@ for i in range(256): L[acc] = i acc = gfmul(acc, g) L[1] = 0 -inv = [E[255-L[i]] if i!=0 else None for i in range(256)] # multiplicative inverse +INV = [E[255-L[i]] if i!=0 else None for i in range(256)] # multiplicative inverse def get_constant_coef(*points): @@ -42,7 +42,7 @@ def get_constant_coef(*points): for j in range(k): if i==j: continue (xj, yj) = points[j] - prod = gfmul(prod, (gfmul(xj, inv[xj^x]))) + prod = gfmul(prod, (gfmul(xj, INV[xj^x]))) res ^= gfmul(y, prod) return res diff --git a/src/shamira/core.py b/src/shamira/core.py --- a/src/shamira/core.py +++ b/src/shamira/core.py @@ -43,11 +43,13 @@ def reconstruct_raw(*shares): if len({x for (x, _) in shares}) < len(shares): raise MalformedShare("Found a non-unique share. Please check your inputs.") - secret_len = len(shares[0][1]) + (xs, payloads) = zip(*shares) + secret_len = len(payloads[0]) res = [None]*secret_len + weights = gf256.compute_weights(xs) for i in range(secret_len): - points = [(x, s[i]) for (x, s) in shares] - res[i] = (gf256.get_constant_coef(*points)) + ys = [s[i] for s in payloads] + res[i] = (gf256.get_constant_coef(weights, ys)) return bytes(res) diff --git a/src/shamira/gf256.py b/src/shamira/gf256.py --- a/src/shamira/gf256.py +++ b/src/shamira/gf256.py @@ -2,6 +2,9 @@ """Arithmetic operations on Galois Field 2**8. See https://en.wikipedia.org/wiki/Finite_field_arithmetic""" +from functools import reduce +import operator + def _gfmul(a, b): """Basic multiplication. Russian peasant algorithm.""" @@ -47,18 +50,25 @@ def evaluate(coefs, x): return res -def get_constant_coef(*points): +def get_constant_coef(weights, y_coords): """Compute constant polynomial coefficient given the points. See https://en.wikipedia.org/wiki/Shamir's_Secret_Sharing#Computationally_Efficient_Approach""" - k = len(points) - res = 0 - for i in range(k): - (x, y) = points[i] - prod = 1 - for j in range(k): - if i==j: continue - (xj, yj) = points[j] - prod = gfmul(prod, (gfmul(xj, INV[xj^x]))) - res ^= gfmul(y, prod) + return reduce( + operator.xor, + map(lambda ab: gfmul(*ab), zip(weights, y_coords)) + ) + + +def compute_weights(x_coords): + assert x_coords + + res = [ + reduce( + gfmul, + (gfmul(xj, INV[xj^xi]) for xj in x_coords if xi!=xj), + 1 + ) for xi in x_coords + ] + return res diff --git a/src/shamira/tests/test_gf256.py b/src/shamira/tests/test_gf256.py --- a/src/shamira/tests/test_gf256.py +++ b/src/shamira/tests/test_gf256.py @@ -30,7 +30,9 @@ class TestGF256(TestCase): self.assertEqual(evaluate([a0, a1, a2, a3], 1), a0^a1^a2^a3) # polynomial at 1 == sum of coefficients def test_get_constant_coef(self): - self.assertEqual(get_constant_coef((1, 1), (2, 2), (3, 3)), 0) + weights = compute_weights((1, 2, 3)) + ys = (1, 2, 3) + self.assertEqual(get_constant_coef(weights, ys), 0) random.seed(17) random_matches = 0 @@ -55,7 +57,10 @@ class TestGF256(TestCase): coefs = [random.randint(0, 255) for i in range(k)] points = [(j, evaluate(coefs, j)) for j in range(1, 256)] random.shuffle(points) - return (get_constant_coef(*points[:m]), coefs[0]) + + (xs, ys) = zip(*points[:m]) + weights = compute_weights(xs) + return (get_constant_coef(weights, ys), coefs[0]) if __name__=='__main__': diff --git a/src/shamira/tests/test_shamira.py b/src/shamira/tests/test_shamira.py --- a/src/shamira/tests/test_shamira.py +++ b/src/shamira/tests/test_shamira.py @@ -28,11 +28,17 @@ class TestShamira(TestCase): with self.assertRaises(ValueError): # not castable to int _share_byte("x", 2, 3) - vals = _share_byte(ord(b"a"), 2, 3) - points = list(zip(range(1, 256), vals)) - self.assertEqual(gf256.get_constant_coef(*points), ord(b"a")) - self.assertEqual(gf256.get_constant_coef(*points[:2]), ord(b"a")) - self.assertNotEqual(gf256.get_constant_coef(*points[:1]), ord(b"a")) # underdetermined => random + ys = _share_byte(ord(b"a"), 2, 3) + xs = list(range(1, 4)) + + weights = gf256.compute_weights(xs) + self.assertEqual(gf256.get_constant_coef(weights, ys), ord(b"a")) + + weights = gf256.compute_weights(xs[:2]) + self.assertEqual(gf256.get_constant_coef(weights, ys[:2]), ord(b"a")) + + weights = gf256.compute_weights(xs[:1]) + self.assertNotEqual(gf256.get_constant_coef(weights, ys[:1]), ord(b"a")) # underdetermined => random def test_generate_reconstruct_raw(self): for (k, n) in [(2, 3), (254, 254)]: