ssss.py

#!/usr/bin/env python3

"""
A toy implementation of Shamir's secret sharing scheme in Python
Copyright (c) 2017 Daan Sprenkels <hello@dsprenkels.com>

*Do not use in production code!*

This is a toy implementation. This code is hardened against regular and cache
timing attacks. But Python is a high-level language, and thus not suitable for
production-grade cryptographic implementations. Primitive functions like
`randint`, or even integer arithmetic is not guaranteed to be in constant-time.
Remember, as always, to never trust crypto code that is implemented in Python!

Now for the specifics. This module uses the finite field with order 2^8
(a.k.a. 256). The reducing primitive polynomial that I am using is:
x**8 + x**4 + x**3 + x + 1.


Use `create_shares` to generate some shares
>>> shares = create_shares(42, 3, 5)

Use `combine_shares` to restore the secret
>>> combine_shares([shares[0], shares[3], shares[2]])
42
"""


import collections.abc
import random


def create_shares(secret, k, n):
    """
    Share a secret *byte* `secret` and split it into `n` shares. Require `k`
    shares to recover back the secret.
    """
    assert isinstance(secret, int)
    assert 0 <= secret < 256
    assert isinstance(n, int)
    assert isinstance(k, int)
    assert 1 <= n < 256
    assert 1 <= k <= n

    # create a random polynomial of order n
    poly = (random.randint(0, 2**(8*(k-1)) - 1) << 8) | secret

    # generate some points where x = 1..n that are on the polynomial
    points = [0] * n
    for point_idx, x in enumerate(range(1, n+1)):
        y = 0
        xpow = 1
        for coeff_idx in range(k):
            shift = 8 * coeff_idx
            y ^= _gf256_mul(xpow, (poly & (0xff << shift)) >> shift)
            xpow = _gf256_mul(xpow, x)
        points[point_idx] = (x, y)
    return points


def combine_shares(shares):
    """
    Combine the shares in `shares` to restore a secret byte.

    For example:
    >>> shares = [(6, 253), (8, 116), (7, 224), (5, 212), (2, 232)]
    >>> combine_shares(shares)
    123
    """
    assert isinstance(shares, collections.abc.Sequence)
    assert all(isinstance(point, collections.abc.Sequence) for point in shares)
    assert all(len(point) == 2 for point in shares)
    assert all(0 <= x < (1<<8) and 0 <= y < (1<<8) for (x, y) in shares)

    # restore the least significant coefficient in the original polynomial
    secret = 0
    for i, (this_x, this_y) in enumerate(shares):
        # use Lagrange basis polynomials to calculate secret
        numerator = 1
        denominator = 1
        for j, (other_x, _) in enumerate(shares):
            if i == j: continue
            numerator = _gf256_mul(numerator, other_x)
            denominator = _gf256_mul(denominator, this_x ^ other_x)
        basis_polynomial = _gf256_mul(numerator, _gf256_inv(denominator))
        # add scaled polynomial coefficient to restored secret
        secret ^= _gf256_mul(this_y, basis_polynomial)
    return secret


def _gf256_mul(a, b, p=0x11b):
    """
    Safely multiply two numbers in GF(2^8)
    """
    ret = 0
    for _ in range(8):
        ret ^= (b & 1) * a
        a <<= 1
        a ^= (a >> 8) * p
        b >>= 1
    return ret


def _gf256_inv(a, p=0x11b):
    """
    Invert a in GF(2**8) reduced by p
    """
    ret = a
    # square-multiply seven times (without last multiply)
    for _ in range(6):
        ret = _gf256_mul(ret, ret, p)
        ret = _gf256_mul(ret, a, p)
    ret = _gf256_mul(ret, ret, p)
    return ret


def _gf256_repr(a):
    """
    Print a human-readable representation of a polynomial in GF(2^8)

    >>> _gf256_repr(0x7b)
    'x**6 + x**5 + x**4 + x**3 + x**1 + 1'
    """
    coeffs = [a & (1 << i) for i in range(8)]
    out = ["x**{}".format(i) for (i, a) in
           reversed(list(enumerate(coeffs))[1:])
           if a]
    if coeffs[0]: out.append("1")
    return " + ".join(out)


if __name__ == '__main__':
    import doctest
    doctest.testmod()