# How to Become Immortal 101: Shamir’s Secret Sharing

## Table Of Contents

Have you ever wondered how to protect your master password from getting lost? Or how to create a *perfect* democracy
where nuke access is shared between most important people in the government *equally*? Or how to achieve immortality by
splitting your soul and putting the pieces into objects? 🪄

If so, then you’ve come to the right place. Join me, my friend, on this discovery of Shamir’s secret sharing.

## Chapter 1: Learning dark magic

Shamir’s secret sharing is a secret sharing algorithm first formulated by Adi Shamir in How to share a secret
(). It allows to split and distribute a secret among a group, in such a way that no single
person from that group can recreate the secret. Only when a quorum decides to merge their *shards*, the secret can be
recreated.

At its core, Shamir’s secret sharing is based on polynomial interpolation and is really easy to understand conceptually. Once of its main features is that the group size ($n$) and the minimal quorum size ($k$) do not have to be the same number. Obviously, $n \ge k$, but other than that we can adjust those numbers to match our needs.

*OK, but how does this work?*

Let’s start by encoding our secret as a number. (Technical details will be discussed in Chapter 3, so for now let’s just say it’s possible.) We get $S = 42$.

Next step is to select $n$ and $k$. Let’s say we share our encoded master password (secret) with 8 friend and any 4 of them can reconstruct the secret. That gives us $n = 8$ and $k = 4$.

To get the shards, we need to construct a polynomial of degree $k - 1$, where coefficient zero ($a_0$) is the secret; the rest of coefficients are chosen randomly.

$$ f(x) = 165x^3 + 51x^2 + 98x + 42 $$

We can clearly see that $f(0) = 42$ is our secret. Our shards are $f(1), f(2), …, f(n)$, which gives us:

$$ \begin{array}{ l l } (1, 356) & (2, 1762) \\[0.25em] (3, 5250) & (4, 11810) \\[0.25em] (5, 22432) & (6, 38106) \\[0.25em] (7, 59822) & (8, 88570) \end{array} $$

…if coupled with indexes. And that’s it! Any 4 of these numbers can be used to reconstruct the polynomial, thus allowing to calculate the secret $\big(f(0)\big)$.

That’s half of our dark magic theory. Let’s learn how to undo what we did.

### Reverting spell’s effect

To reconstruct the secret we need any 4 shards. Chosen randomly these are:

$$ \begin{aligned} &(2, 1762) \\[0.25em] &(4, 11810) \\[0.25em] &(6, 38106) \\[0.25em] &(8, 88570) \end{aligned} $$

There are a lot of ways we can reconstruct a polynomial from a series of points. If you like math you might be tempted to use the formula for Lagrange interpolating polynomial:

$$ \begin{aligned} f(x) &= \sum_{j=0}^{n}\big(y_j \cdot \ell_j(x)\big) \\[0.25em] \ell_j(x) &= \prod_{\substack{0 \le m \le k \\ m \ne j}} \frac{x - x_m}{x_j - x_m} \end{aligned} $$

Or — if you’re lazy — use `scipy`

:

```
1>>> from scipy.interpolate import lagrange
2>>> lagrange([2, 4, 6, 8], [1762, 11810, 38106, 88570])
3poly1d([165., 51., 98., 42.])
```

These, indeed, are our polynomial coefficients. Even without reconstruction, we can clearly see that $f(0) = 42$; secret recovered. 👌

## Chapter 2: Protecting our enchantments from counter-curses

Frankly, to *almost* any curse, there’s a counter-curse. A counter-curse for Shamir’s secret sharing is integer
arithmetic.

A good secret sharing algorithm should have two characteristics:

- Secret can be computed with any $k$ or more shards.
- Knowledge of any number of shards less than $k$ makes does not reveal any information about the secret. In other words all possible values of the secret should be equally probable.

While (1) is still true, (2) is not so much. Let’s go over this step by step; assume that we only know three out of four required shards:

$$ \begin{aligned} &(1, 456) \\[0.25em] &(2, 1762) \\[0.25em] &(3, 5250) \end{aligned} $$

It gives us:

$$ \begin{alignat}{1} f(1) &= S + a_1 + a_2 + a_3 = 356 \\[0.25em] f(2) &= S + 2a_1 + 4a_2 + 8a_3 = 1762 \\[0.25em] f(3) &= S + 3a_1 + 9a_2 + 27a_3 = 5250 \end{alignat} $$

By solving $(1)$ for $a_1$ and substituting $a_1$ in $(2)$ we get:

$$ \begin{alignat}{1} a_1 &= 356 - S - a_2 - a_3 \\[0.25em] 1050 &= - S + 2a_2 + 6a_3 \end{alignat} $$

Solving $(5)$ for $a_2$ and substituting $a_1$, and $a_2$ in $(3)$ we get:

$$ \begin{alignat}{1} 5250 &= S + 3(356 - S - (525 + \frac{S}{2} - 3a_3) - a_3) + 9(525 + \frac{S}{2} - 3a_3) + 27a_3 \\[0.25em] S &= -6(a_3 - 172) \end{alignat} $$

From $(7)$ we conclude that $S$ is even. (See WolframAlpha.)

### Finite field arithmetic

We can protect from this by using finite field arithmetic. In simple terms — those of you who know math don’t kill
me please — finite field arithmetic *is* applying modulo to your calculation. So, $GF(256)$ is doing calculations
over $mod \ 256$.

With the Galois field of order 256 our polynomial becomes:

$$ f(x) = 165x^3 + 51x^2 + 98x + 42 \mod 256 $$

Which produces these shards:

$$ \begin{array}{ l l } (1, 100) & (2, 226) \\[0.25em] (3, 130) & (4, 34) \\[0.25em] (5, 160) & (6, 218) \\[0.25em] (7, 174) & (8, 250) \end{array} $$

By repeating the attack above we *could* conclude that

$$ S \equiv -6(a_3 - 172) \mod 256 $$

However, it does not provide any additional information.

## Chapter 3: Wands out! Time to practice

**NB**: SSS with a Galois field is *math*; it doesn’t mean it’s easy to use in practice. The catch is that the order of
the Galois field must be greater than the secret $S$. This is problematic if we decide to split a *large enough* secret.
A naive way of encoding an arbitrary string as a number can be done with *base10*, or with something like:

```
1int('An arbitrary large secret. Lorem ipsum dolor sit amet, consectetur adipiscing elit.'.encode().hex(), 16)
```

Do you want to guess how many digits it has?

## Spoiler!

It’s 200.

```
1>>> a = int('An arbitrary large secret. Lorem ipsum dolor sit amet, consectetur adipiscing elit.'.encode().hex(), 16)
2>>> a
319563893103164139046164760092383861391703768554892418063070031848050953623578314862989468034439094655520808050846734560200990268693032238066103008403886443361299427067274060838050276743694708128707630
4>>> len(str(a))
5200
```

A known solution for this is to split the secret into chunks and apply SSS to each chunk individually:

```
1chunks = [int(b) for b in 'An arbitrary large secret. Lorem ipsum dolor sit amet, consectetur adipiscing elit.'.encode()]
2shards = sss(chunks, k=4, n=8)
```

Shout-out to RustySecrets where I first saw this idea. (Frankly, this project seems to be abandoned.) Still, on the web, there’re numerous other SSS implementations:

- Shamir Secret Sharing Scheme
- Shamir Secret Sharing @ asecuritysite.com
- Simple Shamir’s Secret Sharing
- sss @ point-at-infinity.org
- …

## P.S. Why did I wrote this blog post?

Initially, I had a grand idea of implementing SSS from scratch and writing about technical challenges along the way.
That was on . In that time I got busy and distracted with other things, so SSS had been
moved to the back of my head and *stayed* there. I had some time today, so I’ve decided to quickly finish this blog post
and make it *on-paper-only* without any code.

There’s nothing new here. If you take a look at Wikipedia’s Shamir’s secret sharing, you’ll see that it heavily
*inspired* this blog post; it’s basically Wikipedia’s with Harry Potter’s twist in it. Still, I find value in writing
about subjects in my own words. Helps me understand them better and SSS is something I wanted to understand for some
time now.

###### Interested in my work?

Consider subscribing to the RSS Feed or joining my mailing list: madebyme-notifications on Google Groups .

**Disclaimer:** Only group owner (i.e. me) can view e-mail addresses
of group members. I will not share your e-mail with any third-parties
— it will be used exclusively to notify you about new blog posts.