# GNU GPLv3, see LICENSE

from argparse import ArgumentParser

from shamira import generate, reconstruct

def run():

	parser=ArgumentParser()

	subparsers=parser.add_subparsers()

	buildSplitParser(subparsers.add_parser("split"))

	buildJoinParser(subparsers.add_parser("join"))

	args=parser.parse_args()

	args.func(args)

def buildSplitParser(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("secret",help="secret to be parsed")

	parser.set_defaults(func=_generate)

def buildJoinParser(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 secret as raw bytes")

	parser.add_argument("share",nargs="+",help="shares to be joined")

	parser.set_defaults(func=_reconstruct)

def _generate(args):

	encoding=getEncoding(args) or "b32"

def _reconstruct(args):

	encoding=getEncoding(args)

def getEncoding(args):

	if args.hex: return "hex"

	elif args.b32: return "b32"

	elif args.b64: return "b64"

	else: return ""

"""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 getConstantCoef(*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

def reconstructRaw(*shares):

	"""Tries to recover the secret from its shares.

	:param shares: ((i, (bytes) share), ...)

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

	secretLen=len(shares[0][1])

	res=[None]*secretLen

	for i in range(secretLen):

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

		res[i]=(getConstantCoef(*points))

	return bytes(res)

def reconstruct(*shares):

	"""Wraps reconstructRaw.

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

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

	bs=reconstructRaw(*(decode(s) for s in shares))

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

def decode(share):

	try:

		(i,_,shareStr)=share.partition(".")

		i=int(i)

		if not 1<=i<=255:

			raise ValueError()

		shareBytes=base64.b32decode(shareStr)

		return (i,shareBytes)

	except (ValueError,binascii.Error):

		raise ValueError('bad share format: 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")

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

	args=parser.parse_args()

	args.func(args)

if __name__=="__main__":

	run()

# GNU GPLv3, see LICENSE

import os

import re

import base64

import binascii

import gf256

def _shareByte(secretB,k,n):

	coefs=[int(secretB)]+[int(b) for b in os.urandom(k-1)]

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

	return points

def generateRaw(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=[_shareByte(b,k,n) for b in secret]

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

def reconstructRaw(*shares):

	"""Tries to recover the secret from its shares.

	:param shares: ((i, (bytes) share), ...)

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

	secretLen=len(shares[0][1])

	res=[None]*secretLen

	for i in range(secretLen):

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

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

	return bytes(res)

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

	"""Wraps generateRaw().

	: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.

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

	if isinstance(secret,str):

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

	shares=generateRaw(secret,k,n)

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

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

	"""Wraps reconstructRaw.

	: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=detectEncoding(shares)

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

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

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,_,shareStr)=share.partition(".")

		i=int(i)

		if not 1<=i<=255:

			raise ValueError()

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

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

		else: f=base64.b64decode

		shareBytes=f(shareStr)

		return (i,shareBytes)

	except (ValueError,binascii.Error):

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

def detectEncoding(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 ValueError("no expected encoding detected")

if __name__=="__main__":

	import cli

	cli.run()

# GNU GPLv3, see LICENSE

import random

from unittest import TestCase

from shamira import _shareByte

from shamira import *

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_shareByte(self):

			_shareByte(b"a",5,4)

			_shareByte(b"a",5,255)

		with self.assertRaises(ValueError): # not castable to int

			_shareByte("x",2,3)

		vals=_shareByte(ord(b"a"),2,3)

		points=list(zip(range(1,256), vals))

		self.assertEqual(gf256.getConstantCoef(*points), ord(b"a"))

		self.assertEqual(gf256.getConstantCoef(*points[:2]), ord(b"a"))

		self.assertNotEqual(gf256.getConstantCoef(*points[:1]), ord(b"a")) # underdetermined => random

	def testGenerateReconstructRaw(self):

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

			shares=generateRaw(b"abcd",k,n)

			random.shuffle(shares)

			self.assertEqual(reconstructRaw(*shares[:k]), b"abcd")

			self.assertNotEqual(reconstructRaw(*shares[:k-1]), b"abcd")

	def testGenerateReconstruct(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(UnicodeDecodeError):

			reconstruct(*shares)

	def testEncode(self):

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

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

			with self.subTest(enc=encoding):

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

	def testDecode(self):

		with self.assertRaises(ValueError):

			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(ValueError):

					detectEncoding(shares)

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

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

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

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