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 thatssss
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 callingsplit()
andcombine()
.
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 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)