Table of Contents
About
Secret sharing (also called secret splitting) refers to methods for distributing a secret among a group of participants, each of whom is allocated a share of the secret. The secret can be reconstructed only when a sufficient number, of possibly different types, of shares are combined together; individual shares are of no use on their own.
Secret sharing schemes are ideal for storing information that is highly sensitive and highly important. Examples include: encryption keys, missile launch codes, and numbered bank accounts. Each of these pieces of information must be kept highly confidential, as their exposure could be disastrous, however, it is also critical that they should not be lost. Traditional methods for encryption are ill-suited for simultaneously achieving high levels of confidentiality and reliability. This is because when storing the encryption key, one must choose between keeping a single copy of the key in one location for maximum secrecy, or keeping multiple copies of the key in different locations for greater reliability. Increasing reliability of the key by storing multiple copies lowers confidentiality by creating additional attack vectors; there are more opportunities for a copy to fall into the wrong hands. Secret sharing schemes address this problem, and allow arbitrarily high levels of confidentiality and reliability to be achieved.
Shamir’s Secret Sharing, formulated by Adi Shamir, is one of the first secret sharing schemes in cryptography. It is based on polynomial interpolation over finite fields.
Adi Shamir is also a co-inventor of the Rivest–Shamir–Adleman (RSA) algorithm (along with Ron Rivest and Len Adleman).
Explanation
The secret is split into multiple parts, called shares, which are later used to reconstruct the original secret. To unlock the secret via Shamir’s secret sharing, you need a minimum number of shares. This is called the threshold, and is used to denote the minimum number of shares needed to unlock the secret.
The essential idea of the scheme is based on Lagrange interpolation theorem, specifically that k points is enough to uniquely determine a polynomial of degree less than or equal to k - 1
For instance, 2 points are sufficient to define a line, 3 points are sufficient to define a parabola, 4 points to define a cubic curve and so forth.
We construct a polynomial such that our secret is encoded as the zeroth coefficient or the y-intercept of the function. Take random k - 1 elements as the rest of the coefficients a1, a2, a3, …., a(k-1), such that the final polynomial becomes f(x) = a0 + a1 x + a2 x2 + …. + a(k-1) x(k-1). Now we can construct the shares required, by computing (i, f(i)) where i is a natural number. Every participant is given a point (a non-zero integer input to the polynomial, and the corresponding integer output). Given any random subset of k of these pairs, we can obtain the secret (a0) with interpolation using the following formula:
Galois Fields
In mathematics, a finite field or Galois field (so-named in honor of Évariste Galois) is a field that contains a finite number of elements. As with any field, a finite field is a set on which the operations of multiplication, addition, subtraction and division are defined and satisfy certain basic rules. The most common examples of finite fields are given by the integers mod p when p is a prime number.
Unlike the real field where we have infinite number of coordinates and axes, a finite field is limited to certain number of elements. The number of elements of a finite field is called its order or, sometimes, its size. A finite field of order q exists if and only if q is a prime power pk (where p is a prime number and k is a positive integer). In a field of order pk, adding p copies of any element always results in zero; that is, the characteristic of the field is p.
Most common galois fields are the prime fields, for e.g. GF (256) or GF(28) which is also used in the RSA encryption.
Example
Let the secret be s = 245, number of shares be n = 7 and the threshold be k = 4. This means that we need to generate 7 pairs of points to share among the members, and any 4 members can reconstruct the secret using their pairs. We choose random k - 1 numbers 18, 84 and 184. Therefore a0 = 245, a1 = 18, a2 = 84, a3 = 184, and our polynomial becomes: f(x) = 245 + 18 x + 84 x2 + 184 x3
Now we can generate 7 points by putting x = 1, 2, 3, …, 7 in our polynomial. We get D1 = (1, 461), D2 = (2, 1529), D3 = (3, 4133), D4 = (4, 8957), D5 = (5, 16685), D6 = (6, 28001), D7 = (7, 43589)
Now, given these shares, we would need only 4 pairs to reconstruct our polynomial and get the free coefficient as our original secret. Which can be done using the formula given above.
Although the simplified version of the method demonstrated above, which uses integer arithmetic rather than finite field arithmetic, works fine, there is a security problem. Suppose that we know 3 points D3, D7, D4. We still don’t know the minimum number of points to construct the polynomial, but if we combine this with the public info, (n = 7, k = 4), our polynomial should look something like f(x) = S + a1x + a2x2 + a3x3. By putting in the values for the 3 points we know, we get 3 equations and 4 unkowns which finally results in a linear relation of two variables with a negative slope. Since every coefficient is a natural number, this narrows down the possibilities and can be done via simple brute-forcing. Geometrically this attack exploits the fact that we know the order of the polynomial and so gain insight into the paths it may take between known points. This reduces possible values of unknown points since it must lie on a smooth curve.
This problem can be fixed by using finite field arithmetic. The graph shows a polynomial curve over a finite field, in contrast to the usual smooth curve it appears very disorganised and disjointed.
Setup
- Make sure you have Python3 installed on your system.
- Run
git clone https://github.com/adviksinghania/sharmir-secret-sharingto clone the repo andcd shamir-secret-sharingto navigate inside the directory. - Run
sudo python3 -m pip install -r requirements.txtto install the required libraries (matplotlib, seaborn). - You can run the individual scripts for the algorithm with or without the galois field with a pre-defined driver code, or type
python3 main.py -hfor info on how to use the main script. - Now run the
main.pyfile by giving inline arguments to the terminal like this…$ python main.py --secret 2357 --shares 12 --threshold 5Or
$ python main.py -S 14351 -s 22 -t 10
End:
More examples:
NOTE: I’ve added docstrings and comments wherever needed in the scripts so that it’s easy to understand.
Check out Matt Parker’s video for a wonderful explanation for this cipher.
Another benefit of using prime fields is that the output of the polynomial will be small compared to the polynomial using integer arithmetic, where the numbers may even cross the range of int and therefore, the secret may not be properly reconstructed.
If you have any doubts, you can reach me on Twitter, LinkedIn, or Instagram
