# Secret Sharing Schemes

This module implements the Shamir’s secret sharing protocol described in the paper “How to share a secret”.

The secret can be split into an arbitrary number of shares (`n`), such that it is sufficient to collect just `k` of them to reconstruct it (`k < n`). For instance, one may want to grant 16 people the ability to access a system with a pass code, at the condition that at least 3 of them are present at the same time. As they join their shares, the pass code is revealed. In that case, `n=16` and `k=3`.

In the Shamir’s secret sharing scheme, the `n` shares are created by first defining a polynomial of degree `k-1`:

q(x) = a_0 + a_1 x + a_2 x^2 + \ldots + a_{k-1} x^{k-1}

The coefficient a_0 is fixed with the secret value. The coefficients a_1 \ldots a_{k-1} are random and they are discarded as soon as the shares are created.

Each share is a pair (x_i, y_i), where x_i is an arbitrary but unique number assigned to the share’s recipient and y_i=q(x_i).

This implementation has the following properties:

- The secret is a byte string of 16 bytes (e.g. an AES 128 key).

- Each share is a byte string of 16 bytes.

- The recipients of the shares are assigned an integer starting from 1 (share number x_i).

- The polynomial q(x) is defined over the field GF(2^{128}) with the same irriducible polynomial as used in AES-GCM: 1 + x + x^2 + x^7 + x^{128}.

- It can be compatible with the popular ssss tool when used with the 128 bit security level and no dispersion: the command line arguments must include `-s 128 -D`. Note that `ssss` uses a slightly different polynomial:

  r(x) = a_0 + a_1 x + a_2 x^2 + \ldots + a_{k-1} x^{k-1} + x^k

  which requires you to specify `ssss=True` when calling `split()` and `combine()`.

Each recipient needs to hold both the share number (x_i, which is not confidential) and the secret (which needs to be protected securely).

As an example, the following code shows how to protect a file meant for 5 people, in such a way that any 2 of them are sufficient to reassemble it:

    >>> from binascii import hexlify
    >>> from Crypto.Cipher import AES
    >>> from Crypto.Random import get_random_bytes
    >>> from Crypto.Protocol.SecretSharing import Shamir
    >>>
    >>> key = get_random_bytes(16)
    >>> shares = Shamir.split(2, 5, key)
    >>> for idx, share in shares:
    >>>     print "Index #%d: %s" % (idx, hexlify(share))
    >>>
    >>> with open("clear.txt", "rb") as fi, open("enc.txt", "wb") as fo:
    >>>     cipher = AES.new(key, AES.MODE_EAX)
    >>>     ct, tag = cipher.encrypt(fi.read()), cipher.digest()
    >>>     fo.write(cipher.nonce + tag + ct)

Each person can be given one share and the encrypted file.

When 2 people gather together with their shares, they can decrypt the file:

    >>> from binascii import unhexlify
    >>> from Crypto.Cipher import AES
    >>> from Crypto.Protocol.SecretSharing import Shamir
    >>>
    >>> shares = []
    >>> for x in range(2):
    >>>     in_str = raw_input("Enter index and share separated by comma: ")
    >>>     idx, share = [ strip(s) for s in in_str.split(",") ]
    >>>     shares.append((idx, unhexlify(share)))
    >>> key = Shamir.combine(shares)
    >>>
    >>> with open("enc.txt", "rb") as fi:
    >>>     nonce, tag = [ fi.read(16) for x in range(2) ]
    >>>     cipher = AES.new(key, AES.MODE_EAX, nonce)
    >>>     try:
    >>>         result = cipher.decrypt(fi.read())
    >>>         cipher.verify(tag)
    >>>         with open("clear2.txt", "wb") as fo:
    >>>             fo.write(result)
    >>>     except ValueError:
    >>>         print "The shares were incorrect"

Attention

Reconstruction may succeed but still produce the incorrect secret if any of the presented shares is incorrect (due to data corruption or to a malicious participant).

It is extremely important to also use an authentication mechanism (such as the EAX cipher mode in the example).

class Crypto.Protocol.SecretSharing.Shamir

  Shamir’s secret sharing scheme.

  A secret is split into `n` shares, and it is sufficient to collect `k` of them to reconstruct the secret.

  static combine(shares, ssss=False)

    Recombine a secret, if enough shares are presented.

    Parameters:

      - shares (tuples) – The k tuples, each containin the index (an integer) and the share (a byte string, 16 bytes long) that were assigned to a participant.

      - ssss (bool) – If `True`, the shares were produced by the `ssss` utility. Default: `False`.

    Returns:

      The original secret, as a byte string (16 bytes long).

  static split(k, n, secret, ssss=False)

    Split a secret into `n` shares.

    The secret can be reconstructed later using just `k` shares out of the original `n`. Each share must be kept confidential to the person it was assigned to.

    Each share is associated to an index (starting from 1).

    Parameters:

      - k (integer) – The sufficient number of shares to reconstruct the secret (`k < n`).

      - n (integer) – The number of shares that this method will create.

      - secret (byte string) – A byte string of 16 bytes (e.g. the AES 128 key).

      - ssss (bool) – If `True`, the shares can be used with the `ssss` utility. Default: `False`.

    Return (tuples):

      `n` tuples. A tuple is meant for each participant and it contains two items:

      1. the unique index (an integer)

      2. the share (a byte string, 16 bytes)