tally

shamir's secret sharing over gf(256).
git clone https://owenrusk.dev/tally.git
tally / tests/test_shamir.py -rw-r--r-- · 2911 bytes
 1 import itertools
 2 import os
 3 import random
 4 import unittest
 5 from collections import Counter
 6 
 7 from tally import shamir
 8 
 9 LENGTHS = [1, 2, 3, 15, 16, 17, 64, 255, 256, 1000]
10 SHAPES = [(2, 2), (2, 3), (3, 5), (5, 5), (4, 7), (6, 9)]
11 
12 
13 class ShamirTest(unittest.TestCase):
14     def test_round_trip(self) -> None:
15         secret = b"not a real secret"
16         shares = shamir.split(secret, 3, 5)
17         self.assertEqual(len(shares), 5)
18         self.assertEqual(shamir.combine(shares[:3]), secret)
19 
20     def test_many_lengths(self) -> None:
21         for length in LENGTHS:
22             secret = os.urandom(length)
23             shares = shamir.split(secret, 3, 5)
24             self.assertTrue(all(len(data) == length for _, data in shares))
25             with self.subTest(length=length):
26                 self.assertEqual(shamir.combine(random.sample(shares, 3)), secret)
27 
28     def test_every_k_subset_rebuilds(self) -> None:
29         for k, n in SHAPES:
30             secret = os.urandom(random.choice([1, 17, 100]))
31             shares = shamir.split(secret, k, n)
32             for subset in itertools.combinations(shares, k):
33                 with self.subTest(k=k, n=n, xs=[x for x, _ in subset]):
34                     self.assertEqual(shamir.combine(list(subset)), secret)
35 
36     def test_order_doesnt_matter(self) -> None:
37         secret = os.urandom(32)
38         shares = shamir.split(secret, 4, 6)
39         for _ in range(20):
40             self.assertEqual(shamir.combine(random.sample(shares, 4)), secret)
41 
42     def test_widest(self) -> None:
43         secret = os.urandom(3)
44         shares = shamir.split(secret, 2, 255)
45         self.assertEqual(shamir.combine([shares[0], shares[254]]), secret)
46         shares = shamir.split(secret, 255, 255)
47         self.assertEqual(shamir.combine(shares), secret)
48 
49     def test_fewer_than_k_is_not_enough(self) -> None:
50         for k, n in SHAPES:
51             secret = os.urandom(32)
52             shares = shamir.split(secret, k, n)
53             with self.subTest(k=k, n=n):
54                 self.assertNotEqual(shamir.combine(shares[: k - 1]), secret)
55 
56     def test_one_share_of_two_looks_like_noise(self) -> None:
57         # every byte of the secret is 0. a single share should still be all over the place
58         secret = bytes(6000)
59         for x, data in shamir.split(secret, 2, 3):
60             counts = Counter(data)
61             with self.subTest(x=x):
62                 self.assertEqual(len(counts), 256)
63                 self.assertLess(max(counts.values()), 3 * len(secret) // 256)
64 
65     def test_bad_k_and_n(self) -> None:
66         for k, n in [(1, 3), (4, 3), (2, 256), (0, 0)]:
67             with self.assertRaises(ValueError):
68                 shamir.split(b"x", k, n)
69 
70     def test_same_x_twice(self) -> None:
71         shares = shamir.split(b"x", 2, 3)
72         with self.assertRaises(ValueError):
73             shamir.combine([shares[0], shares[0]])
74 
75 
76 if __name__ == "__main__":
77     unittest.main()