How to Become Immortal 101: Shamir’s Secret Sharing

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 (1979-11-01). 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:

1. Secret can be computed with any $k$ or more shards.
2. 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?

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 2024-06-06. 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.