# HG changeset patch # User Laman # Date 2017-10-01 17:36:11 # Node ID 6511b6f4f6c0d3acec605de96f36a3ba15be3fef # Parent 8968eab714bcaec51952b6377775d6d15925131c added printable condensed version diff --git a/src/condensed.py b/src/condensed.py new file mode 100644 --- /dev/null +++ b/src/condensed.py @@ -0,0 +1,111 @@ +# 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() diff --git a/src/tests/test_condensed.py b/src/tests/test_condensed.py new file mode 100644 --- /dev/null +++ b/src/tests/test_condensed.py @@ -0,0 +1,88 @@ +# 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"))