diff --git a/src/shamira/condensed.py b/src/shamira/condensed.py deleted file mode 100644 --- a/src/shamira/condensed.py +++ /dev/null @@ -1,124 +0,0 @@ -# GNU GPLv3, see LICENSE -# easier to print, single file, reconstruct-only version of the code -# encoding fixed to Base32 -# Python 3.6 -# full version available at https://bitbucket.org/Scharlach/shamira - -"""Arithmetic operations on Galois Field 2**8. See https://en.wikipedia.org/wiki/Finite_field_arithmetic""" - - -def gfmul(a, b): - """Basic multiplication. Russian peasant algorithm.""" - res = 0 - while a and b: - if b&1: res ^= a - if a&0x80: a = 0xff&(a<<1)^0x1b - else: a <<= 1 - b >>= 1 - return res - - -g = 3 # generator -E = [None]*256 # exponentials -L = [None]*256 # logarithms -acc = 1 -for i in range(256): - E[i] = acc - 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 - - -def get_constant_coef(*points): - """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 res - -### - -import base64 -import binascii - - -class SException(Exception): pass - - -def reconstruct_raw(*shares): - """Tries to recover the secret from its shares. - - :param shares: (((int) i, (bytes) share), ...) - :return: (bytes) reconstructed secret. Too few shares returns garbage.""" - if len({x for (x, _) in shares}) < len(shares): - raise SException("Found a non-unique share. Please check your inputs.") - - secret_len = len(shares[0][1]) - res = [None]*secret_len - for i in range(secret_len): - points = [(x, s[i]) for (x, s) in shares] - res[i] = (get_constant_coef(*points)) - return bytes(res) - - -def reconstruct(*shares): - """Wraps reconstruct_raw. - - :param shares: ((str) share, ...) - :return: (str) reconstructed secret. Too few shares returns garbage.""" - - bs = reconstruct_raw(*(decode(s) for s in shares)) - try: - return bs.decode(encoding="utf-8") - except UnicodeDecodeError: - raise SException('Failed to decode bytes to utf-8. Either you supplied invalid shares, or you missed the "raw" flag. Offending value: "{0}"'.format(bs)) - - -def decode(share): - try: - (*_, i, share_str) = share.split(".") - i = int(i) - if not 1<=i<=255: - raise SException("Malformed share: Failed 1<=k<=255, k={0}".format(i)) - - share_bytes = base64.b32decode(share_str) - return (i, share_bytes) - except (ValueError, binascii.Error): - raise SException('Malformed share: share="{0}"'.format(share)) - -### - -from argparse import ArgumentParser - - -def run(): - parser = ArgumentParser() - subparsers = parser.add_subparsers() - - joiner = subparsers.add_parser("join") - joiner.add_argument("share", nargs="+", help="shares to be joined") - joiner.set_defaults(func=_reconstruct) - - parser.set_defaults(func=lambda: parser.error("missing command")) - - args = parser.parse_args() - args.func(args) - - -def _reconstruct(args): - try: print(reconstruct(*args.share)) - except SException as e: print(e) - - -if __name__=="__main__": - run() diff --git a/src/shamira/tests/test_condensed.py b/src/shamira/tests/test_condensed.py deleted file mode 100644 --- a/src/shamira/tests/test_condensed.py +++ /dev/null @@ -1,88 +0,0 @@ -# GNU GPLv3, see LICENSE - -import os -import random -from unittest import TestCase - -from ..gf256 import _gfmul, evaluate -from .. import generate_raw, generate -from ..condensed import * - - -class TestCondensed(TestCase): - _urandom = os.urandom - - @classmethod - def setUpClass(cls): - random.seed(17) - os.urandom = lambda n: bytes(random.randint(0, 255) for i in range(n)) - - @classmethod - def tearDownClass(cls): - os.urandom = cls._urandom - - def test_gfmul(self): - for a in range(256): - for b in range(256): - self.assertEqual(_gfmul(a, b), gfmul(a, b)) - - def test_get_constant_coef(self): - self.assertEqual(get_constant_coef((1, 1), (2, 2), (3, 3)), 0) - - random.seed(17) - random_matches = 0 - for i in range(10): - k = random.randint(2, 255) - - # exact - res = self.check_coefs_match(k, k) - self.assertEqual(res[0], res[1]) - - # overdetermined - res = self.check_coefs_match(k, 256) - self.assertEqual(res[0], res[1]) - - # underdetermined => random - res = self.check_coefs_match(k, k-1) - if res[0]==res[1]: - random_matches += 1 - 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[-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") - self.assertNotEqual(reconstruct_raw(*shares[:k-1]), b"abcd") - - def test_generate_reconstruct(self): - for secret in ["abcde", "ěščřžý"]: - for (k, n) in [(2, 3), (254, 254)]: - with self.subTest(sec=secret, k=k, n=n): - shares = generate(secret, k, n) - random.shuffle(shares) - self.assertEqual(reconstruct(*shares[:k]), secret) - try: - self.assertNotEqual(reconstruct(*shares[:k-1]), secret) - except SException: - pass - shares = generate(b"\xfeaa", 2, 3) - with self.assertRaises(SException): - reconstruct(*shares) - - def test_decode(self): - with self.assertRaises(SException): - decode("AAA") - decode("1.") - decode(".AAA") - decode("1AAA") - decode("1.AAAQEAY") - decode("1.AAAQEAy=") - decode("256.AAAQEAY=") - self.assertEqual(decode("2.AAAQEAY="), (2, b"\x00\x01\x02\x03"))