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 containing the index (an integer) and the share (a byte string, 16 bytes long) that were assigned to a participant.

Note

Pass exactly as many share as they are required, and no more.
ssss (bool) – If True, the shares were produced by the ssss utility (without using the “diffusion layer”). 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 number of shares needed to reconstruct the secret.
n (integer) – The number of shares to create (at least k).
secret (byte string) – A byte string of 16 bytes (e.g. an AES 128 key).
ssss (bool) – If True, the shares can be used with the ssss utility (without using the “diffusion layer”). Default: False.

Return (tuples):

n tuples, one per participant. A tuple contains two items:

the unique index (an integer)
the share (16 bytes)