import cProfile

import timeit

def measure(args):

	secret = "1234567890123456"

	shares = generate(secret, args.k, args.n)

	symbols = globals()

	symbols.update(locals())

	time = timeit.timeit("""generate(secret, args.k, args.n)""", number=1, globals=symbols)

	time = timeit.timeit("""reconstruct(*shares)""", number=1, globals=symbols)

def profile(args):

	t = TestShamira()

	cProfile.runctx(r"""t.test_generate_reconstruct()""", globals=globals(), locals=locals())

# GNU GPLv3, see LICENSE

import sys

from argparse import ArgumentParser

def run():

	parser = ArgumentParser()

	subparsers = parser.add_subparsers()

	build_split_parser(subparsers.add_parser("split"))

	build_join_parser(subparsers.add_parser("join"))

	parser.set_defaults(func=lambda _: parser.error("missing command"))

	args = parser.parse_args()

	args.func(args)

def build_split_parser(parser):

	parser.add_argument("-k", type=int, required=True, help="number of shares necessary for recovering the secret")

	parser.add_argument("-n", type=int, required=True, help="number of generated shares")

	encoding = parser.add_mutually_exclusive_group()

	encoding.add_argument("--hex", action="store_true", help="encode shares' bytes as a hexadecimal string")

	encoding.add_argument("--b32", action="store_true", help="encode shares' bytes as a base32 string")

	encoding.add_argument("--b64", action="store_true", help="encode shares' bytes as a base64 string")

	parser.add_argument("--label", help="any label to prefix the shares with")

	parser.add_argument("--omit_k_n", action="store_true", help="suppress the default shares prefix")

	parser.add_argument("secret", nargs="?", help="a secret to be split. Can be provided on the command line,"

		" redirected through stdin, or will be asked for interactively.")

	parser.set_defaults(func=_generate)

def build_join_parser(parser):

	encoding = parser.add_mutually_exclusive_group()

	encoding.add_argument("--hex", action="store_true", help="decode shares' bytes from a hexadecimal string")

	encoding.add_argument("--b32", action="store_true", help="decode shares' bytes from a base32 string")

	encoding.add_argument("--b64", action="store_true", help="decode shares' bytes from a base64 string")

	parser.add_argument("-r", "--raw", action="store_true", help="return the secret as raw bytes")

	parser.add_argument("share", nargs="*", help="shares to be joined. Can be provided on the command line,"

		" redirected through stdin, or will be asked for interactively.")

	parser.set_defaults(func=_reconstruct)

def _generate(args):

	encoding = get_encoding(args) or "b32"

	if args.secret:  # provided as a positional argument

		secret = args.secret

	elif sys.stdin.isatty():  # input from terminal

		secret = input("Enter your secret:\n")

	else:  # redirected from other source

		secret = sys.stdin.read()

	try:

		shares = generate(secret, args.k, args.n, encoding, label=args.label, omit_k_n=args.omit_k_n)

		for s in shares:

			print(s)

	except SException as e:

		print(e, file=sys.stderr)

def _reconstruct(args):

	encoding = get_encoding(args)

	if args.share:  # provided as a positional argument

		shares = args.share

	elif sys.stdin.isatty():  # input from terminal

		print("Enter the shares, each on separate line, end with an empty line:")

		shares = []

		while not shares or shares[-1]:

			shares.append(input())

		shares.pop()

	else:  # redirected from other source

		shares = sys.stdin.read().split()

	try:

		print(reconstruct(*shares, encoding=encoding, raw=args.raw))

	except SException as e:

		print(e, file=sys.stderr)

def get_encoding(args):

	if args.hex: return "hex"

	elif args.b32: return "b32"

	elif args.b64: return "b64"

	else: return ""

# GNU GPLv3, see LICENSE

import os

import re

import base64

import binascii

class SException(Exception): pass

class InvalidParams(SException): pass

class DetectionException(SException): pass

class DecodingException(SException): pass

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)]

	points = [gf256.evaluate(coefs, i) for i in range(1, n+1)]

	return points

def generate_raw(secret, k, n):

	"""Splits secret into shares.

	:param secret: (bytes)

	:param k: number of shares necessary for secret recovery. 1 <= k <= n

	:param n: (int) number of shares generated. 1 <= n < 255

	:return: [(i, (bytes) share), ...]"""

	shares = [_share_byte(b, k, n) for b in secret]

	return [(i+1, bytes([s[i] for s in shares])) for i in range(n)]

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 return garbage."""

	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])

	res = [None]*secret_len

	for i in range(secret_len):

		points = [(x, s[i]) for (x, s) in shares]

		res[i] = (gf256.get_constant_coef(*points))

	return bytes(res)

def generate(secret, k, n, encoding="b32", label="", omit_k_n=False):

	"""Wraps generate_raw().

	:param secret: (str or bytes)

	:param k: number of shares necessary for secret recovery

	:param n: number of shares generated

	:param encoding: {hex, b32, b64} desired output encoding. Hexadecimal, Base32 or Base64.

	:param label: (str) any label to prefix the shares with

	:param omit_k_n: (boolean) suppress the default shares prefix

	:return: [(str) share, ...]"""

	if isinstance(secret,str):

		secret = secret.encode("utf-8")

	shares = generate_raw(secret, k, n)

	prefix = ""

	if label:

		prefix = label + "."

	if not omit_k_n:

		prefix += "{0}.{1}.".format(k, n)

	return [prefix + encode(s, encoding) for s in shares]

def reconstruct(*shares, encoding="", raw=False):

	"""Wraps reconstruct_raw.

	:param shares: ((str) share, ...)

	:param encoding: {hex, b32, b64, ""} encoding of share strings. If not provided or empty, the function tries to guess it.

	:param raw: (bool) whether to return bytes (True) or str (False)

	:return: (str or bytes) reconstructed secret. Too few shares returns garbage."""

	if not encoding:

		encoding = detect_encoding(shares)

	bs = reconstruct_raw(*(decode(s, encoding) for s in shares))

	try:

		return bs if raw else bs.decode(encoding="utf-8")

	except UnicodeDecodeError:

		raise DecodingException('Failed to decode bytes to utf-8. Either you supplied invalid shares, or you missed the "raw" flag. Offending value: {0}'.format(bs))

def encode(share, encoding="b32"):

	if encoding=="hex": f = base64.b16encode

	elif encoding=="b32": f = base64.b32encode

	else: f = base64.b64encode

	(i, bs) = share

	return "{0}.{1}".format(i, f(bs).decode("utf-8"))

def decode(share, encoding="b32"):

	try:

		(*_, i, share_str) = share.split(".")

		i = int(i)

		if not 1<=i<=255:

			raise MalformedShare("Malformed share: Failed 1<=k<=255, k={0}".format(i))

		if encoding=="hex": f = base64.b16decode

		elif encoding=="b32": f = base64.b32decode

		else: f = base64.b64decode

		share_bytes = f(share_str)

		return (i, share_bytes)

	except (ValueError, binascii.Error):

		raise MalformedShare('Malformed share: share="{0}", encoding="{1}"'.format(share, encoding))

def detect_encoding(shares):

	classes = [

		(re.compile(r"(.*\.)?\d+\.([0-9A-F]{2})+"), "hex"),

		(re.compile(r"(.*\.)?\d+\.([A-Z2-7]{8})*([A-Z2-7]{8}|[A-Z2-7]{2}={6}|[A-Z2-7]{4}={4}|[A-Z2-7]{5}={3}|[A-Z2-7]{7}={1})"), "b32"),

		(re.compile(r"(.*\.)?\d+\.([A-Za-z0-9+/]{4})*([A-Za-z0-9+/]{4}|[A-Za-z0-9+/]{2}={2}|[A-Za-z0-9+/]{3}={1})"), "b64")

	]

	for (regexp, res) in classes:

		if all(regexp.fullmatch(share) for share in shares):

			return res

	raise DetectionException("No expected encoding detected")

# GNU GPLv3, see LICENSE

import os

import random

from unittest import TestCase

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[0])

	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"))

# GNU GPLv3, see LICENSE

import random

import unittest

from unittest import TestCase

class TestGF256(TestCase):

	def test__gfmul(self):

		self.assertEqual(_gfmul(0, 0), 0)

		self.assertEqual(_gfmul(1, 1), 1)

		self.assertEqual(_gfmul(2, 2), 4)

		self.assertEqual(_gfmul(0, 21), 0)

		self.assertEqual(_gfmul(0x53, 0xca), 0x01)

		self.assertEqual(_gfmul(0xff, 0xff), 0x13)

	def test_gfmul(self):

		for a in range(256):

			for b in range(256):

				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

	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[0])

if __name__=='__main__':

	unittest.main()

# GNU GPLv3, see LICENSE

import random

from unittest import TestCase

class TestShamira(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_share_byte(self):

		with self.assertRaises(InvalidParams):  # too few shares

			_share_byte(b"a", 5, 4)

		with self.assertRaises(InvalidParams):  # too many shares

			_share_byte(b"a", 5, 255)

		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

	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 encoding in ["hex", "b32", "b64"]:

			for secret in [b"abcd", "abcde", "ěščřžý"]:

				for (k, n) in [(2, 3), (254, 254)]:

					raw = isinstance(secret, bytes)

					with self.subTest(enc=encoding, r=raw, sec=secret, k=k, n=n):

						shares = generate(secret, k, n, encoding)

						random.shuffle(shares)

						self.assertEqual(reconstruct(*shares[:k], encoding=encoding, raw=raw), secret)

						self.assertEqual(reconstruct(*shares[:k], raw=raw), secret)

						s = secret if raw else secret.encode("utf-8")

						self.assertNotEqual(reconstruct(*shares[:k-1], encoding=encoding, raw=True), s)

		shares = generate(b"\xfeaa", 2, 3)

		with self.assertRaises(DecodingException):

			reconstruct(*shares)

	def test_encode(self):

		share = (2, b"\x00\x01\x02")

		for (encoding, encoded_str) in [("hex", '000102'), ("b32", 'AAAQE==='), ("b64", 'AAEC')]:

			with self.subTest(enc=encoding):

				self.assertEqual(encode(share, encoding), "2."+encoded_str)

	def test_decode(self):

		with self.assertRaises(MalformedShare):

			decode("AAA")

			decode("1.")

			decode(".AAA")

			decode("1AAA")

			decode("1.0001020f", "hex")

			decode("1.000102030", "hex")

			decode("1.AAAQEAY")

			decode("1.AAAQEAy=")

			decode("1.AAECAw=", "b64")

			decode("1.AAECA?==", "b64")

			decode("256.00010203", "hex")

		self.assertEqual(decode("1.00010203", "hex"), (1, b"\x00\x01\x02\x03"))

		self.assertEqual(decode("2.AAAQEAY=", "b32"), (2, b"\x00\x01\x02\x03"))

		self.assertEqual(decode("3.AAECAw==", "b64"), (3, b"\x00\x01\x02\x03"))

	def testDetectEncoding(self):

		for shares in [

			["1.00010f"],  # bad case

			["1.000102030"],  # bad char count

			["1.AAAQEAY"],  # no padding

			["1.AAAQe==="],  # bad case

			["1.AAECA?=="],  # bad char

			["1.AAECAw="],  # bad padding

			["1.000102", "2.AAAQEAY="],  # mixed encoding

			["1.000102", "2.AAECAw=="],

			["1.AAECAw==", "2.AAAQE==="],

			[".00010203"],  # no index

			["00010203"]  # no index

		]:

			with self.subTest(shares=shares):

				with self.assertRaises(DetectionException):

					detect_encoding(shares)

		self.assertEqual(detect_encoding(["10.00010203"]), "hex")

		self.assertEqual(detect_encoding(["2.AAAQEAY="]), "b32")

		self.assertEqual(detect_encoding(["3.AAECAw=="]), "b64")

		self.assertEqual(detect_encoding(["3.AAECAwQF", "1.00010203"]), "b64")