# 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 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")
	joiner.set_defaults(func=lambda args: print(reconstruct(*args.share)))

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

	args=parser.parse_args()
	args.func(args)


if __name__=="__main__":
	run()