Shamira Changeset - a47ae3e113cc

Changeset - a47ae3e113cc

Parent rev.

Child rev.

[Not reviewed]

default

0 5 0

Laman - 5 years ago 2020-05-03 21:25:23

optimized the generation operation

5 files changed with 15 insertions and 14 deletions:

readme.md

src/shamira/core.py

src/shamira/gf256.py

src/shamira/tests/test_condensed.py

src/shamira/tests/test_gf256.py

0 comments (0 inline, 0 general)

readme.md

➞

Show inline comments

@@ @@ -18,27 +18,27 @@ Benchmark results, all values mean _seco @@
         <th>k / n parameters</th>
         <th>Split</th>
         <th>Join</th>
     </tr>
     <tr>
         <td>2 / 3 (a Raspberry Pi 3)</td>
-        <td>8.32e-05</td>
+        <td>6.08e-05</td>
         <td>0.000435</td>
     </tr>
     <tr>
         <td>2 / 3 (a laptop)</td>
-        <td>1.09e-05</td>
+        <td>8.7e-06</td>
         <td>7.17e-05</td>
     </tr>
     <tr>
         <td>254 / 254 (a Raspberry Pi 3)</td>
-        <td>0.414</td>
+        <td>0.226</td>
         <td>0.0314</td>
     </tr>
     <tr>
         <td>254 / 254 (a laptop)</td>
-        <td>0.0435</td>
+        <td>0.0209</td>
         <td>0.00347</td>
     </tr>
 </table>
 While the speeds are not awful, for longer secrets I recommend encrypting them with a random key of your choice and splitting only the key. Anyway, you can run your own benchmark with `shamira benchmark`

src/shamira/core.py

➞

Show inline comments

@@ @@ -16,13 +16,13 @@ class MalformedShare(SException): pass @@
 def _share_byte(secret_b, k, n):
 	if not k<=n<255:
 		raise InvalidParams("Failed k<=n<255, k={0}, n={1}".format(k, n))
 	# we might be concerned with zero coefficients degenerating our polynomial, but there's no reason - we still need k shares to determine it is the case
-	coefs = [int(secret_b)]+[int(b) for b in os.urandom(k-1)]
+	coefs = [int(b) for b in os.urandom(k-1)]+[int(secret_b)]
 	points = [gf256.evaluate(coefs, i) for i in range(1, n+1)]
 	return points
 def generate_raw(secret, k, n):
 	"""Splits secret into shares.

src/shamira/gf256.py

➞

Show inline comments

@@ @@ -38,18 +38,19 @@ def gfmul(a, b): @@
 	return E[t]
 def evaluate(coefs, x):
 	"""Evaluate polynomial's value at x.
-	:param coefs: [a0, a1, ...]."""
+	:param coefs: [an, ..., a1, a0]."""
 	res = 0
 	xk = 1
 	for a in coefs:
 		res ^= gfmul(a, xk)
 		xk = gfmul(xk, x)
 	for a in coefs:  # Horner's rule
 		res = gfmul(res, x)
 		res ^= a
 	return res
 def get_constant_coef(weights, y_coords):
 	"""Compute constant polynomial coefficient given the points.

src/shamira/tests/test_condensed.py

➞

Show inline comments

@@ @@ -49,13 +49,13 @@ class TestCondensed(TestCase): @@
 		self.assertLess(random_matches, 2)  # with a chance (255/256)**10=0.96 there should be no match
 	def check_coefs_match(self, k, m):
 		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])
+		return (get_constant_coef(*points[:m]), coefs[-1])
 	def test_generate_reconstruct_raw(self):
 		for (k, n) in [(2, 3), (254, 254)]:
 			shares = generate_raw(b"abcd", k, n)
 			random.shuffle(shares)
 			self.assertEqual(reconstruct_raw(*shares[:k]), b"abcd")

src/shamira/tests/test_gf256.py

➞

Show inline comments

@@ @@ -23,14 +23,14 @@ class TestGF256(TestCase): @@
 				self.assertEqual(_gfmul(a, b), gfmul(a, b))
 	def test_evaluate(self):
 		for x in range(256):
 			(a0, a1, a2, a3) = (x, x>>1, x>>2, x>>3)
 			self.assertEqual(evaluate([17], x), 17)  # constant polynomial
 			self.assertEqual(evaluate([a0, a1, a2, a3], 0), x)  # any polynomial at 0
 			self.assertEqual(evaluate([a0, a1, a2, a3], 1), a0^a1^a2^a3)  # polynomial at 1 == sum of coefficients
 			self.assertEqual(evaluate([a3, a2, a1, a0], 0), x)  # any polynomial at 0
 			self.assertEqual(evaluate([a3, a2, a1, a0], 1), a0^a1^a2^a3)  # polynomial at 1 == sum of coefficients
 	def test_get_constant_coef(self):
 		weights = compute_weights((1, 2, 3))
 		ys = (1, 2, 3)
 		self.assertEqual(get_constant_coef(weights, ys), 0)
@@ @@ -57,11 +57,11 @@ 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)
 		(xs, ys) = zip(*points[:m])
 		weights = compute_weights(xs)
-		return (get_constant_coef(weights, ys), coefs[0])
+		return (get_constant_coef(weights, ys), coefs[-1])
 if __name__=='__main__':
 	unittest.main()

0 comments (0 inline, 0 general)