shamirs module

Minimal pure-Python implementation of Shamir’s secret sharing scheme.

_MODULUS_DEFAULT = 170141183460469231731687303715884105727

Default prime modulus (equivalent to (2 ** 127) - 1) that is used for creating secret shares if a prime modulus is not specified explicitly.

class share(index, value, modulus=_MODULUS_DEFAULT)

Bases: object

Data structure for representing an individual secret share. Normally, the shares function should be used to construct a sequence of share objects.

>>> isinstance(shares(1, 3, modulus=31)[0], share)
True
>>> len(shares(1, 3, modulus=31))
3
>>> interpolate(shares(123, 12, modulus=15485867))
123
>>> interpolate(shares(2**100, 100)) == 2**100
True

It must be possible to represent the index integer using 32 bits. There is no bound on the size of the value.

>>> share(4294967296, 123)
Traceback (most recent call last):
  ...
ValueError: index must be an integer that can be represented using at most 32 bits

static from_bytes(bs)

Convert a secret share represented as a bytes-like object into a share object.

Parameters:

bs (Union[bytes, bytearray]) – Bytes-like object that is an encoding of a share instance.

Return type:

share

All share information (the index, the value, and the modulus) is assumed to be encoded (as is done by to_bytes).

>>> s = share.from_bytes(bytes.fromhex('7b00000002000000c801fd03'))
>>> (s.index, s.value, s.modulus)
(123, 456, 1021)
>>> s = share.from_bytes(share(1, 2**100).to_bytes())
>>> (s.index, s.value) == (1, 2**100)
True

static from_base64(s)

Convert a secret share represented as a Base64 encoding of a bytes-like object into a share object.

Parameters:

s (str) – String that is a Base64 encoding of a share instance.

Return type:

share

All share information (the index, the value, and the modulus) is assumed to be encoded (as is done by to_base64).

>>> s = share.from_base64('ewAAAAIAAADIAf0D')
>>> (s.index, s.value, s.modulus)
(123, 456, 1021)
>>> s = share.from_base64(share(3, 2**100).to_base64())
>>> (s.index, s.value) == (3, 2**100)
True

__add__(other)

Add two secret shares (represented as share objects) or a share and an integer.

Parameters:

other (Union[share, int]) – Secret share or integer value to be added to this share.

Return type:

share

Note that share addition must be done consistently across all shares.

>>> (r, s, t) = shares(123, 3)
>>> (u, v, w) = shares(456, 3)
>>> interpolate([r + u, s + v, t + w])
579

The integer constant 0 is supported as an input to accommodate the base case required by the built-in sum function.

>>> share(123, 456, 1021) + 0
share(123, 456, 1021)
>>> ts = [shares(n, quantity=3) for n in [123, 456, 789]]
>>> interpolate([sum(ss) for ss in zip(*ts)])
1368

When secret shares are added, it is not possible to determine whether the sum of the values they represent exceeds the maximum value that can be represented. If the sum does exceed the value, then the value reconstructed from the shares will wrap around. This corresponds to the usual behavior of field elements under addition within a field.

>>> (a, b) = shares(1020, quantity=2, modulus=1021) # One-byte integer.
>>> (c, d) = shares(2, quantity=2, modulus=1021) # One-byte integer.
>>> interpolate([a + c, b + d]) == (1020 + 2) % 1021 == 1
True

Any attempt to add secret shares that are represented using different finite fields – or that have different indices – raises an exception.

>>> (r, s, t) = shares(2, quantity=3, modulus=5)
>>> (u, v, w) = shares(3, quantity=3, modulus=7)
>>> r + u
Traceback (most recent call last):
  ...
ValueError: shares being added must have the same index and modulus
>>> (r, s, t) = shares(2, quantity=3, modulus=5)
>>> (u, v, w) = shares(3, quantity=3, modulus=5)
>>> r + v
Traceback (most recent call last):
  ...
ValueError: shares being added must have the same index and modulus

The examples below test this addition method for a range of share quantities and addition operation counts.

>>> for quantity in range(2, 20):
...     for operations in range(2, 20):
...         vs = [
...             int.from_bytes(secrets.token_bytes(2), 'little')
...             for _ in range(operations)
...         ]
...         sss = [shares(v, quantity) for v in vs]
...         assert(interpolate([sum(ss) for ss in zip(*sss)]) == sum(vs))

__radd__(other)

Add two secret shares (represented as share objects) or a share and an integer.

Parameters:

other (Union[share, int]) – Secret share or integer value to be added to this share.

Return type:

share

Note that share addition must be done consistently across all shares.

>>> (r, s, t) = shares(123, 3)
>>> (u, v, w) = shares(456, 3)
>>> interpolate([r + u, s + v, t + w])
579

The integer constant 0 is supported as an input to accommodate the base case required by the built-in sum function.

>>> 0 + share(123, 456, 1021)
share(123, 456, 1021)
>>> ts = [shares(n, quantity=3) for n in [123, 456, 789]]
>>> interpolate([sum(ss) for ss in zip(*ts)])
1368

__iadd__(other)

Add a secret share or an integer value to this secret share instance.

Parameters:

other (Union[share, int]) – Secret share or integer value to be added to this share.

Return type:

share

Note that share addition must be done consistently across all shares.

>>> (r, s, t) = shares(123, 3)
>>> (u, v, w) = shares(456, 3)
>>> r += u
>>> s += v
>>> w += t
>>> interpolate([r, s, w])
579

__mul__(scalar)

Multiply this secret share instance by an integer scalar.

Parameters:

scalar (int) – Scalar value by which to multiply this share.

Return type:

share

Note that all secret shares must be multiplied by the same integer scalar in order for the reconstructed value to reflect the correct result.

>>> (r, s, t) = shares(123, 3)
>>> r = r * 2
>>> s = s * 2
>>> t = t * 2
>>> interpolate([r, s, t])
246

When secret shares are multiplied by a scalar, it is not possible to determine whether the result exceeds the range of values that can be represented. If the result does fall outside the range, then the value reconstructed from the shares will wrap around. This corresponds to the usual behavior of field elements under scalar multiplication within a field.

>>> (s, t) = shares(512, quantity=2, modulus=1021)
>>> s = s * 2
>>> t = t * 2
>>> interpolate([s, t]) == (512 * 2) % 1021 == 3
True

The scalar argument must be a nonnegative integer.

>>> (r, s, t) = shares(123, 3)
>>> s = s * 2.0
Traceback (most recent call last):
  ...
TypeError: scalar must be an integer
>>> (r, s, t) = shares(123, 3)
>>> s = s * -2
Traceback (most recent call last):
  ...
ValueError: scalar must be a nonnegative integer

The examples below test this scalar multiplication method for a range of share quantities and a number of random scalar values.

>>> for quantity in range(2, 20):
...     for _ in range(100):
...         v = int.from_bytes(secrets.token_bytes(2), 'little')
...         c = int.from_bytes(secrets.token_bytes(1), 'little')
...         ss = shares(v, quantity)
...         assert(interpolate([c * s for s in ss]) == c * v)

__rmul__(scalar)

Multiply this secret share instance by an integer scalar (that appears on the left side of the operator).

Parameters:

scalar (int) – Scalar value by which to multiply this share.

Return type:

share

Note that all secret shares must be multiplied by the same integer scalar in order for the reconstructed value to reflect the correct result.

>>> (r, s, t) = shares(123, 3)
>>> r = r * 2
>>> s = s * 2
>>> t = t * 2
>>> interpolate([r, s, t])
246

__imul__(scalar)

Multiply this secret share instance by an integer scalar.

Parameters:

scalar (int) – Scalar value by which to multiply this share.

Return type:

share

Note that all secret shares must be multiplied by the same integer scalar in order for the reconstructed value to reflect the correct result.

>>> (r, s, t) = shares(123, 3)
>>> r *= 2
>>> s *= 2
>>> t *= 2
>>> interpolate([r, s, t])
246

__int__()

Return the least nonnegative residue of the field element corresponding to this instance.

Return type:

int

>>> int(share(123, 456, 1021))
456

__len__()

Return the modulus corresponding to the field (within which this instance represents an element).

Return type:

int

>>> len(share(123, 456, 1021))
1021

to_bytes()

Return a bytes-like object that encodes this share object.

Return type:

bytes

>>> share(123, 456, 1021).to_bytes().hex()
'7b00000002000000c801fd03'

All share information (the index, the value, and the modulus) is encoded.

>>> share.from_bytes(share(3, 2**100).to_bytes()).index
3

to_base64()

Return a Base64 string encoding of this share object.

Return type:

str

>>> share(123, 456, 1021).to_base64()
'ewAAAAIAAADIAf0D'

All share information (the index, the value, and the modulus) is encoded.

>>> share.from_base64(share(3, 2**100).to_base64()).value == 2**100
True

__str__()

Return the string representation of this share object.

Return type:

str

>>> str(share(123, 456, 1021))
'share(123, 456, 1021)'

__repr__()

Return the string representation of this share object.

Return type:

str

>>> share(123, 456, 1021)
share(123, 456, 1021)

shares(value, quantity, modulus=_MODULUS_DEFAULT, threshold=None)

Transforms an integer value into the specified number of secret shares, with recovery of the original value possible using the returned sequence of secret shares (via the interpolate function).

Parameters:

• value (int) – Integer value to be split into secret shares.

• quantity (int) – Number of secret shares (at least two) to construct and return.

• modulus (Optional[int]) – Prime modulus corresponding to the finite field used for creating secret shares.

• threshold (Optional[int]) – Minimum number of shares that will be required to reconstruct a value.

Return type:

Sequence[share]

A modulus may be supplied; it is expected (but not checked) that the supplied modulus is a prime number.

>>> len(shares(123, 100))
100
>>> len(shares(1, 3, modulus=31))
3
>>> len(shares(17, 10, modulus=41))
10

Attempts to transform a value that is greater than the supplied prime modulus raise an exception.

>>> shares(256, 3, modulus=31)
Traceback (most recent call last):
  ...
ValueError: value cannot be greater than the prime modulus

Other invocations with invalid parameter values also raise exceptions.

>>> shares('abc', 3, 17)
Traceback (most recent call last):
  ...
TypeError: value must be an integer
>>> shares(1, 'abc', 17)
Traceback (most recent call last):
  ...
TypeError: quantity of shares must be an integer
>>> shares(1, 3, 'abc')
Traceback (most recent call last):
  ...
TypeError: prime modulus must be an integer
>>> shares(-2, 3, 17)
Traceback (most recent call last):
  ...
ValueError: value must be a nonnegative integer
>>> shares(1, 1, 17)
Traceback (most recent call last):
  ...
ValueError: quantity of shares must be at least 2
>>> shares(1, 2**32, 17)
Traceback (most recent call last):
  ...
ValueError: quantity of shares must be an integer that can be represented using at most 32 bits
>>> shares(1, 3, 1)
Traceback (most recent call last):
  ...
ValueError: prime modulus must be at least 2

Requesting fewer shares than needed to reconstruct is permitted (but a warning is issued).

>>> len(shares(1, quantity=3, modulus=11, threshold=7))
3

Requesting a larger set of shares than is necessary to reconstruct the original value is permitted.

>>> len(shares(1, quantity=7, modulus=11, threshold=3))
7

interpolate(shares, threshold=None)

Reassemble an integer value from a sequence of secret shares using Lagrange interpolation (via the interpolate function exported by the lagrange library).

Parameters:

• shares (Iterable[share]) – Iterable of shares from which to reconstruct a value.

• threshold (int) – Minimum number of shares that will be required to reconstruct a value.

Return type:

int

The appropriate order for the secret shares is already encoded in the individual share instances (assuming they were created using the shares function). Thus, they can be supplied in any order.

>>> interpolate(shares(5, 3, modulus=31))
5
>>> interpolate(shares(123, 12))
123
>>> interpolate(reversed(shares(123, 12)))
123

If the threshold is known to be different than the number of shares, it should be specified as such. In the example below, the value 123 was shared with twenty parties such that at least twelve of them must collaborate to reconstruct the value.

>>> interpolate(shares(123, 20, 1223, 12)[:12], 12) # Use first twelve shares.
123
>>> interpolate(shares(123, 20, 1223, 12)[20-12:], 12) # Use last twelve shares.
123
>>> interpolate(shares(123, 20, 1223, 12)[:15], 12) # Use first fifteen shares.
123
>>> interpolate(shares(123, 20, 1223, 12)[:11], 12) # Try using only eleven shares.
Traceback (most recent call last):
  ...
ValueError: not enough points for a unique interpolation

Any attempt to interpolate using a threshold value that is smaller than the threshold value originally specified when the shares were created yields an arbitrary output. However, no confirmation is performed (at the time of interpolation) that interpolation is being performed with the correct threshold value.

>>> 123 != interpolate(shares(123, 20, 2**31 - 1, 12)[:11], 11) # Try using smaller threshold.
True
>>> 123 != interpolate(shares(123, 20, 2**31 - 1, 2)[:1], 1) # Try using smaller threshold.
True

Any attempt to interpolate using a threshold value that is larger than the threshold value originally specified when the shares were created returns the original secret-shared value.

>>> interpolate(shares(123, 20, 2**31 - 1, 12)[:13], 13) # Try using larger threshold.
123

Invocations with invalid parameter values raise exceptions.

>>> interpolate([1, 2, 3])
Traceback (most recent call last):
  ...
TypeError: input must contain share objects
>>> interpolate(shares(123, 3, 1223) + shares(123, 3, 1021))
Traceback (most recent call last):
  ...
ValueError: all shares must have the same modulus