Image for post
Image for post
Source: Unsplash

Shamir’s Secret Sharing — A numeric example walkthrough

Shamir’s Secret Sharing algorithm is an old cryptography algorithm (1979) invented by the Israeli cryptographer Adi Shamir (co-inventor of RSA) for sharing a secret across multiple parties [1]. I repeatedly stumbled upon it in many research papers (mainly for MPC) so I thought that it could be useful to write an explanatory post about it as it is also a very straightforward algorithm to understand.

Shamir’s Secret Sharing Scheme

At first this may seem counterproductive in the context of secure data transmission because if there is a secure way of distributing a secret S amongst participants what is the point of using this scheme. The original purpose of the scheme is to enhance practicality and convenience when multiple parties are required to perform an authorised action. For instance consider the following problem statement from [2]:

Eleven scientists are working on a secret project. They wish to lock up the documents in a cabinet so that the cabinet can be opened if and only if six or more of the scientists are present. What is the smallest number of locks needed? What is the smallest number of keys to the locks each scientist must carry?

The answer to the above is that 462 locks are needed and also 252 keys per scientist. Obviously this is not practical. Furthermore, consider a more realistic scenario: A company that develops software signs its software deliverable with its RSA secret key in order to verify its authenticity. A possible approach would be to give a copy of the key to all of the senior developers and any of them can use that to sign each release. However, that’s easy to abuse. On the other hand, multiple keys can be issued and distributed to developers and each release would require all of them to sign it. This provides powerful safety about the authenticity of the software but it is very inconvenient.

Putting all this into the context of SSSS a secret key S can be split into N parts (and distributed to N senior developers/scientists) such that any k out of N are required to reconstruct the secret key. Immediately, the inconvenience is eliminated and even more, there is room for drop outs (i.e. senior developer leaves company). Such a fascinating scheme. Nothing less expected from the co-inventor of RSA.

How does it work?

Preparation

First, we sample k-1 random numbers {a₁, a₂…, a₍ₖ₋₁₎} from a finite field of size p where:

Image for post
Image for post

such that aᵢ < p and a₀ = S. Then those are used to generate the polynomial:

Image for post
Image for post

Back to our example we choose p = 91994388364979. Then we generate random numbers:

Image for post
Image for post

And as a result the following polynomial is generated:

Image for post
Image for post

The next step is to construct the N pieces that are distributed to the participants. Each piece is simply a point on the polynomial just defined. Each point D can be calculated in an iterative manner:

Image for post
Image for post

In our case we need 5 points so we calculate them as follows:

Image for post
Image for post

These are then distributed to the participants of the scheme.

Reconstruction

Initially, the Lagrange Basis Polynomials need to be calculated. The formula for the basis polynomials is defined as follows:

Image for post
Image for post

Then, given n points, the interpolated polynomial is a linear combination of the above basis polynomials as shown below:

Image for post
Image for post

Applying this to our example we randomly select 3 out of the 5 points we derived above:

(x0, y0)=(1, 9285275391624), (x1, y1)=(2, 27078320587385), (x2, y2)=(4, 87287720390361)

Then the basis polynomials become:

Image for post
Image for post

And the interpolated polynomial is derived from:

Image for post
Image for post

Therefore:

Image for post
Image for post

Note that since we are working over the Finite Field Z₉₁₉₉₄₃₈₈₃₆₄₉₇₉ the negative -300000000319 can be changed to +91694388364660. And guess what… if this number looks familiar you are right! This is our secret.

We have just walked through the whole operation of the scheme manually and retrieved our secret back.

Conclusion

☰ PhD Candidate @ UoG ● Combining Cyber Security with Data Science ● Writing to Understand

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store