Shamir’s secret sharing

If you have worked with HashiCorp Vault most likely you have come across this algorithm. It’s also heavily used in cryptographic currencies.

It will split a secret into multiple isolated parts (let’s call it n) AND

reconstruct it if a minimum number of those parts are assembled back (let’s call it k).

Now if you are going to envision it in your head it would be an initial box, later on spitted into smaller blocks and again reconstructed into the initial box.

[initial secret] -> split it into n=3 -> [1] [2] [3] -> reconstruct it back with k=2 -> [1] [2] for example -> [initial secret]

---

This is a good general abstract pattern and it works just great. Now sometimes we go a little deeper and try to understand the internals.

The core idea uses a mathematical object called polynomial but for simplicity and version 1 of our understanding we are going to be using integers.

In our scenario for understanding we have:

Secret(let’s call it S) = 5

n = 3

k = 2

On a standard coordinate system we place the S on the Y axes.

Now we must randomly select a straight line that crosses our S. Let’s use y = 2x + 5. It could be another random straight line as well, like 3x + 5. This is the equation about the slop of straight line. y = mx + b

b = our secret

m = slope

x = x

After we have this randomly selected straight line, let’s plot the values for x with {1,2,3}. We get back {7,9,11}. If we map those we end up with 3 pairs (n=3)

• (1,7) – first piece of our secret.
• (2,9) – second piece of our secret.
• (3,11) – third piece of our secret.

Now if we draw the dots in Y we are going to notice a pattern.

You could actually see that there is a straight line and that straight line crosses our S(S=5). Do we need 3 dots for that straight line ? Could we do it with just 2 dots (k2=) ?

---

Now if you are a chunk of our secret(one of the pieces highlighted above) you might be the coordinates (1,7). You are standing there in isolation and there are many lines that could cross you and cross the vertical line. Same for (2,9), same for (3,11).

So basically you do not know the secret if you are a single pair of coordinates because there are endless possibilities what the secret could be. Endless ways to cross the Y axes. But if we manage to associate just 2 of those pairs (remember k=2), will be able to match a pattern and come to a single conclusion where is the secret ?

Yes, actually if we manage to draw a line between pair(1,7) and (2,9) we could see the continuation and the crossing of the Y axes happens only in our secret.

So we were able to decrypt our secret with just 2 pairs vs 3 in total.

---

The same principles ( not details ) are applied in Shamir’s secret sharing, where when initially the HashiCorp Vault will start it will break down the encryption key into different pairs and you would have to reconstruct that key later on if needed.

If you are curious about the polynomial implementation in Vault -> https://github.com/hashicorp/vault/blob/main/shamir/shamir.go