This unique algorithm using Python and Shamir’s Secret Sharing protects your master password from hackers and your own forgetfulness.
Many of us use password managers to securely store our many unique passwords. A critical part of a password manager is the master password. This password protects all others, and in that way, it is a risk. Anyone who has it can pretend to be you… anywhere! Naturally, you keep your master password hard to guess, commit it to memory, and do all the other things you are supposed to do.
But what if something happens and you forget it? Maybe you took a vacation to a lovely, far-away island with no technology for a month. After frolicking in the water daily and eating pineapples, you cannot quite remember your password. Maybe it was “long legs travel fast”? Or was it something like “sharp spoons eat quick”? It was definitely clever when you thought of it.
Of course, you never told a single soul your password. Why, this is literally the first rule of password management. What could you have done differently?
Enter Shamir’s Secret Sharing, an algorithm that allows users to divide a secret into parts that can be used only in combination with the other pieces.
Let’s take a look at Shamir’s Secret Sharing in action through a story of ancient times and modern times.
This story does assume some knowledge of cryptography. You can brush up on it with this introduction to cryptography and public key infrastructure.
A story of secrets in ancient times
In an ancient kingdom, it came to pass that the king had a secret. A terrible secret:
acc = 0
for b in s:
acc = acc * 256
acc += b
return accsecret = int_from_bytes(“terrible secret”.encode(“utf-8”))
So terrible, the king could entrust it to none of his offspring. He had five of them but knew that there would be dangers on the road ahead. The king knew his children would need the secret to protect the kingdom after his death, but he could not bear the thought of the secret being known for two decades, while they were still mourning him.
So he used powerful magic to split the secret into five shards. He knew that it was possible that one child or even two would not respect his wishes, but he did not believe three of them would:
from os import urandom
The king was well-versed in the magical arts of finite fields and randomness. As a wise king, he used Python to split the secret.
The first thing he did was choose a large prime—the 13th Mersenne Prime (
2**521 - 1)—and ordered it be written in letters 10 feet high, wrought of gold, above the palace:
P = 2**521 - 1
This was not part of the secret: it was public data.
The king knew that if
P is a prime, numbers modulo
P form a mathematical field: they can be added, multiplied, subtracted, and divided as long as the divisor is not zero.
As a busy king, he used the PyPI package
mod, which implements modulus arithmetic.
He made sure his terrible secret was less than
secret < P
And he converted it to its modulus
secret = mod.Mod(secret, P)
In order to allow three offspring to reconstruct the secret, the king had to generate two more parts to mix together:
for i in range(2):
The king next needed to evaluate this polynomial at random points. Evaluating a polynomial is calculating
polynomial + polynomial*x + polynomial*x**2 ...