Package Cryptodome :: Package Protocol :: Module SecretSharing :: Class Shamir

Class Shamir

object --+
         |
        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 Cryptodome.Cipher import AES
>>> from Cryptodome.Random import get_random_bytes
>>> from Cryptodome.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 Cryptodome.Cipher import AES
>>> from Cryptodome.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).

Instance Methods

Inherited from object: __delattr__, __format__, __getattribute__, __hash__, __init__, __new__, __reduce__, __reduce_ex__, __repr__, __setattr__, __sizeof__, __str__, __subclasshook__

Static Methods
 
split(k, n, secret)
Split a secret into n shares.
 
combine(shares)
Recombine a secret, if enough shares are presented.
Properties

Inherited from object: __class__

Method Details

split(k, n, secret)
Static Method

 

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 (>*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.

combine(shares)
Static Method

 
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).