Secret Sharing Schemes

This file implements secret sharing protocols.

In a (k, n) secret sharing protocol, a honest dealer breaks a secret into multiple shares that are distributed amongst n players.

The protocol guarantees that nobody can learn anything about the secret, unless k players gather together to assemble their shares.

class Crypto.Protocol.SecretSharing.Shamir

Shamir’s secret sharing scheme.

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

All shares are points over a 2-dimensional curve. At least k points (that is, shares) are required to reconstruct the curve, and therefore the secret.

This implementation is primarilly meant to protect AES128 keys. To that end, the secret is associated to a curve in the field GF(2^128) defined by the irreducible polynomial \(x^{128} + x^7 + x^2 + x + 1\) (the same used in AES-GCM). The shares are always 16 bytes long.

Data produced by this implementation are compatible to the popular ssss tool if used with 128 bit security (parameter “-s 128”) and no dispersion (parameter “-D”).

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

>>> from binascii import hexlify
>>> from Crypto.Cipher import AES
>>> from Crypto.Random import get_random_bytes
>>> from Crypto.Protocol.secret_sharing 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))
>>>
>>> fi = open("clear_file.txt", "rb")
>>> fo = open("enc_file.txt", "wb")
>>>
>>> cipher = AES.new(key, AES.MODE_EAX)
>>> ct, tag = cipher.encrypt(fi.read()), cipher.digest()
>>> fo.write(nonce + tag + ct)

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

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

>>> from binascii import unhexlify
>>> from Crypto.Cipher import AES
>>> from Crypto.Protocol.secret_sharing 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)
>>>
>>> fi = open("enc_file.txt", "rb")
>>> 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("clear_file2.txt", "wb") as fo:
>>>         fo.write(result)
>>> except ValueError:
>>>     print "The shares were incorrect"

Attention

Reconstruction does not guarantee that the result is authentic. In particular, a malicious participant in the scheme has the ability to force an algebric transformation on the result by manipulating her share.

It is important to use the scheme in combination with an authentication mechanism (the EAX cipher mode in the example).

static combine(shares)

Recombine a secret, if enough shares are presented.

Parameters:shares (tuples) – At least k tuples, each containin the index (an integer) and the share (a byte string, 16 bytes long) that were assigned to a participant.
Returns:The original secret, as a byte string (16 bytes long).
static split(k, n, secret)

Split a secret into n shares.

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

Each share is associated to an index (starting from 1), which must be presented when the secret is recombined.

Parameters:
  • k (integer) – The number of shares that must be present in order to reconstruct the secret.
  • n (integer) – The total number of shares to create (larger than k).
  • secret (byte string) – The 16 byte string (e.g. the AES128 key) to split.
Returns:

n tuples, each containing the unique index (an integer) and the share (a byte string, 16 bytes long) meant for a participant.