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
:
The coefficient is fixed with the secret value.
The coefficients
are random and they are discarded as soon as the shares are created.
Each share is a pair , where
is an arbitrary
but unique number assigned to the share’s recipient and
.
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
).
The polynomial
is defined over the field GF(
) with the same irriducible polynomial as used in AES-GCM:
.
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 thatssss
uses a slightly different polynomial:which requires you to specify
ssss=True
when callingsplit()
andcombine()
.
Each recipient needs to hold both the share number (, 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(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 collectk
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 thessss
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 originaln
. 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 thessss
utility. Default:False
.
- Return (tuples):
n
tuples. A tuple is meant for each participant and it contains two items:the unique index (an integer)
the share (a byte string, 16 bytes)