Files @ eba1ea340d1f
Branch filter:

Location: Shamira/src/shamira/condensed.py - annotation

Laman
updated and fixed readme
4fa21dbcdb9d
4fa21dbcdb9d
4fa21dbcdb9d
4fa21dbcdb9d
4fa21dbcdb9d
4fa21dbcdb9d
4fa21dbcdb9d
4fa21dbcdb9d
4fa21dbcdb9d
4fa21dbcdb9d
4fa21dbcdb9d
4fa21dbcdb9d
4fa21dbcdb9d
4fa21dbcdb9d
4fa21dbcdb9d
4fa21dbcdb9d
4fa21dbcdb9d
4fa21dbcdb9d
4fa21dbcdb9d
4fa21dbcdb9d
4fa21dbcdb9d
4fa21dbcdb9d
4fa21dbcdb9d
4fa21dbcdb9d
4fa21dbcdb9d
4fa21dbcdb9d
4fa21dbcdb9d
4fa21dbcdb9d
4fa21dbcdb9d
4fa21dbcdb9d
4fa21dbcdb9d
4fa21dbcdb9d
4fa21dbcdb9d
4fa21dbcdb9d
4fa21dbcdb9d
4fa21dbcdb9d
4fa21dbcdb9d
4fa21dbcdb9d
4fa21dbcdb9d
4fa21dbcdb9d
4fa21dbcdb9d
4fa21dbcdb9d
4fa21dbcdb9d
4fa21dbcdb9d
4fa21dbcdb9d
4fa21dbcdb9d
4fa21dbcdb9d
4fa21dbcdb9d
4fa21dbcdb9d
4fa21dbcdb9d
4fa21dbcdb9d
4fa21dbcdb9d
4fa21dbcdb9d
4fa21dbcdb9d
4fa21dbcdb9d
4fa21dbcdb9d
4fa21dbcdb9d
4fa21dbcdb9d
4fa21dbcdb9d
4fa21dbcdb9d
4fa21dbcdb9d
4fa21dbcdb9d
4fa21dbcdb9d
4fa21dbcdb9d
4fa21dbcdb9d
4fa21dbcdb9d
4fa21dbcdb9d
4fa21dbcdb9d
4fa21dbcdb9d
4fa21dbcdb9d
4fa21dbcdb9d
4fa21dbcdb9d
4fa21dbcdb9d
4fa21dbcdb9d
4fa21dbcdb9d
4fa21dbcdb9d
4fa21dbcdb9d
4fa21dbcdb9d
4fa21dbcdb9d
4fa21dbcdb9d
4fa21dbcdb9d
4fa21dbcdb9d
4fa21dbcdb9d
4fa21dbcdb9d
4fa21dbcdb9d
4fa21dbcdb9d
4fa21dbcdb9d
4fa21dbcdb9d
4fa21dbcdb9d
4fa21dbcdb9d
4fa21dbcdb9d
4fa21dbcdb9d
4fa21dbcdb9d
4fa21dbcdb9d
4fa21dbcdb9d
4fa21dbcdb9d
4fa21dbcdb9d
4fa21dbcdb9d
4fa21dbcdb9d
4fa21dbcdb9d
4fa21dbcdb9d
4fa21dbcdb9d
4fa21dbcdb9d
4fa21dbcdb9d
4fa21dbcdb9d
4fa21dbcdb9d
4fa21dbcdb9d
4fa21dbcdb9d
4fa21dbcdb9d
4fa21dbcdb9d
4fa21dbcdb9d
4fa21dbcdb9d
4fa21dbcdb9d
4fa21dbcdb9d
4fa21dbcdb9d
4fa21dbcdb9d
4fa21dbcdb9d
4fa21dbcdb9d
4fa21dbcdb9d
4fa21dbcdb9d
4fa21dbcdb9d
4fa21dbcdb9d
4fa21dbcdb9d
4fa21dbcdb9d
# 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()