Files @ b9f1f39cd7af
Branch filter:

Location: Shamira/src/condensed.py - annotation

Laman
check for non-unique shares on joining
6511b6f4f6c0
6511b6f4f6c0
6511b6f4f6c0
6511b6f4f6c0
6511b6f4f6c0
6511b6f4f6c0
6511b6f4f6c0
6511b6f4f6c0
6511b6f4f6c0
cc4182acd584
6511b6f4f6c0
cc4182acd584
6511b6f4f6c0
cc4182acd584
cc4182acd584
cc4182acd584
cc4182acd584
6511b6f4f6c0
6511b6f4f6c0
6511b6f4f6c0
cc4182acd584
cc4182acd584
cc4182acd584
cc4182acd584
6511b6f4f6c0
cc4182acd584
cc4182acd584
cc4182acd584
cc4182acd584
cc4182acd584
6511b6f4f6c0
6511b6f4f6c0
37a1df17b9a1
6511b6f4f6c0
6511b6f4f6c0
6511b6f4f6c0
cc4182acd584
cc4182acd584
6511b6f4f6c0
cc4182acd584
cc4182acd584
6511b6f4f6c0
6511b6f4f6c0
cc4182acd584
cc4182acd584
cc4182acd584
6511b6f4f6c0
6511b6f4f6c0
6511b6f4f6c0
6511b6f4f6c0
6511b6f4f6c0
6511b6f4f6c0
6511b6f4f6c0
6511b6f4f6c0
b52e197db5a8
b52e197db5a8
b52e197db5a8
37a1df17b9a1
6511b6f4f6c0
6511b6f4f6c0
7c94e9b021f6
6511b6f4f6c0
b9f1f39cd7af
b9f1f39cd7af
b9f1f39cd7af
37a1df17b9a1
37a1df17b9a1
37a1df17b9a1
cc4182acd584
37a1df17b9a1
6511b6f4f6c0
6511b6f4f6c0
6511b6f4f6c0
6511b6f4f6c0
37a1df17b9a1
6511b6f4f6c0
6511b6f4f6c0
6511b6f4f6c0
6511b6f4f6c0
37a1df17b9a1
b52e197db5a8
b52e197db5a8
b52e197db5a8
b52e197db5a8
6511b6f4f6c0
6511b6f4f6c0
6511b6f4f6c0
6511b6f4f6c0
7c94e9b021f6
cc4182acd584
6511b6f4f6c0
b52e197db5a8
6511b6f4f6c0
37a1df17b9a1
37a1df17b9a1
cc4182acd584
b52e197db5a8
6511b6f4f6c0
6511b6f4f6c0
6511b6f4f6c0
6511b6f4f6c0
6511b6f4f6c0
6511b6f4f6c0
6511b6f4f6c0
cc4182acd584
cc4182acd584
6511b6f4f6c0
cc4182acd584
cc4182acd584
735b9c2a61e9
6511b6f4f6c0
6511b6f4f6c0
6511b6f4f6c0
cc4182acd584
6511b6f4f6c0
6511b6f4f6c0
6511b6f4f6c0
735b9c2a61e9
735b9c2a61e9
b52e197db5a8
735b9c2a61e9
735b9c2a61e9
6511b6f4f6c0
6511b6f4f6c0
# 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()