Shamira Changeset - a47ae3e113cc

Changeset - a47ae3e113cc

Parent rev.

Child rev.

[Not reviewed]

default

0 5 0

Laman - 4 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

@@ @@ -21,22 +21,22 @@ Benchmark results, all values mean _seco @@
     </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>

src/shamira/core.py

➞

Show inline comments

@@ @@ -19,7 +19,7 @@ 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

src/shamira/gf256.py

➞

Show inline comments

@@ @@ -41,12 +41,13 @@ def gfmul(a, b): @@
 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

src/shamira/tests/test_condensed.py

➞

Show inline comments

@@ @@ -52,7 +52,7 @@ class TestCondensed(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])
+		return (get_constant_coef(*points[:m]), coefs[-1])
 	def test_generate_reconstruct_raw(self):
 		for (k, n) in [(2, 3), (254, 254)]:

src/shamira/tests/test_gf256.py

➞

Show inline comments

@@ @@ -26,8 +26,8 @@ class TestGF256(TestCase): @@
 		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))
@@ @@ -60,7 +60,7 @@ class TestGF256(TestCase): @@
 		(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__':

0 comments (0 inline, 0 general)