# 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()

# GNU GPLv3, see LICENSE

import os

import random

from unittest import TestCase

from gf256 import _gfmul,evaluate

from shamira import generateRaw,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 testGfmul(self):

		for a in range(256):

			for b in range(256):

				self.assertEqual(_gfmul(a,b), gfmul(a,b))

	def testGetConstantCoef(self):

		self.assertEqual(getConstantCoef((1,1),(2,2),(3,3)), 0)

		random.seed(17)

		randomMatches=0

		for i in range(10):

			k=random.randint(2,255)

			# exact

			res=self.checkCoefsMatch(k,k)

			self.assertEqual(res[0], res[1])

			# overdetermined

			res=self.checkCoefsMatch(k,256)

			self.assertEqual(res[0], res[1])

			# underdetermined => random

			res=self.checkCoefsMatch(k,k-1)

			if res[0]==res[1]:

				randomMatches+=1

		self.assertLess(randomMatches, 2) # with a chance (255/256)**10=0.96 there should be no match

	def checkCoefsMatch(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 (getConstantCoef(*points[:m]), coefs[0])

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

						pass

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

		with self.assertRaises(UnicodeDecodeError):

			reconstruct(*shares)

	def testDecode(self):

		with self.assertRaises(ValueError):

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