Save the password: a fabulous implementation of the Shamir secret sharing scheme in Python

This algorithm, using the Python language and the Shamir secret sharing scheme, protects your master password from hackers and your own forgetfulness.

Many of us use password managers to securely store many unique passwords. All their work is essentially tied to a master password. This password protects all other passwords, and thus bears all risk. Anyone who picks it up or gets access to it can pretend to be you at the most inopportune moment. Naturally, you try to make your master password as complex as possible, and then remember or fix it somewhere else.

But suddenly something happens and you forget or lose the master password? For example, you took a vacation, went to a beautiful distant miracle island, and for a month did not use your computer and smartphone. And now, after daily fun and eating pineapples, you can’t remember your password. So … “long legs go fast”? No, not that. Or was there something like “sharp spoons eat fast”? No, that’s wrong. You were clearly in shock when you came up with your master password, but now it came to you sideways.

Of course, you never told anyone your password. Well, yes, this is the first rule of password management! How could it be any different? It turns out maybe.

Shamir’s secret sharing scheme allows you to distribute data between members of a certain group, dividing this data into parts that can only be used in combination with each other.

Let’s look at Shamir’s scheme in action, and at the same time I will tell you a fairy tale. To do this, you will need to refresh some knowledge of cryptography, in particular, about public keys.

The tale of the king and his terrible secret

In a certain kingdom in a certain state the king lived. The king had a terrible secret:

def int_from_bytes(s):
    acc = 0
    for b in s:
        acc = acc * 256
        acc += b
    return acc

secret = int_from_bytes("terrible secret".encode("utf-8"))

The secret was so terrible that the king could not entrust it to any of his children. He had five of them, but he foresaw that danger awaited them ahead. The king knew that 20 years after his death, children would need a secret to protect the kingdom. But the king could not accept the idea that for two decades, while the children would mourn him, they would know a terrible secret.

Therefore, he used powerful magic to divide the secret into five parts. He knew that perhaps one or even two sons would not wait 20 years and would try to find out his secret earlier. However, he believed that three of them would not violate his will:

from mod import Mod
from os import urandom

The king was well versed in the magic art of finite fields and stochastic computing. As a wise king, he used Python to share a secret.

First of all, he chose a large prime number – the 13th prime Mersenne (2 ** 521 – 1) – and ordered that it be cast from gold with symbols 10 feet high and put in front of the palace for all to see:

P = 2**521 - 1

The king knew that if P is a prime number, the numbers modulo P form an algebraic field: they can be added, multiplied, subtracted and divided if the divisor is not equal to zero.

The king is a busy person, so he used the arithmetic package from PyPI.

He made sure that his terrible secret (in numerical terms) is less than P:

secret < P
TRUE

And instead of a secret, I decided to use its comparison modulo P:

secret = mod.Mod(secret, P)

To allow the three sons to recreate the secret, the king had to generate two more parts, in order to subsequently mix them:

polynomial = [secret]
for i in range(2):
    polynomial.append(Mod(int_from_bytes(urandom(16)), P))
len(polynomial)
3

Then the king needed to evaluate the values ​​of the polynomial at random points - that is, calculate the polynomial[0] + polynomial[1]* x + polynomial[2]* x ** 2 ...
Although there are third-party modules for evaluating polynomials, they do not work with finite fields. Therefore, the king wrote the evaluation code manually:

def evaluate(coefficients, x):
    acc = 0
    power = 1
    for c in coefficients:
        acc += c * power
        power *= x
    return acc

Then the king rated the polynomial at five different points to give one piece to each son:

shards = {}
for i in range(5):
    x = Mod(int_from_bytes(urandom(16)), P)
    y = evaluate(polynomial, x)
    shards[i] = (x, y)

And indeed, not all of his children turned out to be honest and truthful. Two of them, soon after his death, conspired and tried to collect a terrible secret from the parts that they had. Naturally, they did not succeed. However, when others found out about this, they expelled them from the kingdom forever:

del shards[2]
del shards[3]

Twenty years later, as the king ordered, the older brother and two younger ones came together to find out the terrible secret of his father. To start, they combined their parts:

retrieved = list(shards.values())

But everything turned out to be not so simple: for 40 days and 40 nights they fought over this task. Like the king, they knew Python, but none of them was as wise as he was.

Finally, a solution was found.

Secret recovery can be performed using the Lagrange interpolation polynomial. To do this, we estimate the polynomial at (0), and then at n other points (n is the degree of the polynomial). The polynomial formula can be written in explicit form. At zero, the polynomial is 1, at other points it is 0. Since the polynomial's estimate is a linear function, we can estimate and interpolate the estimates at the same points.

from functools import reduce
from operator import mul

def retrieve_original(secrets):
    x_s = [s[0] for s in secrets]
    acc = Mod(0, P)
    for i in range(len(secrets)):
        others = list(x_s)
        cur = others.pop(i)
        factor = Mod(1, P)
        for el in others:
            factor *= el * (el - cur).inverse()
        acc += factor * secrets[i][1]
    return acc

No wonder it took them 40 days and 40 nights - this code is quite complicated!

retrieved_secret = retrieve_original(retrieved)

Bingo!

retrieved_secret == secret
TRUE

The beauty of mathematical magic is that even after 20 years it continues to work stably. Children, now adults and able to understand their father’s choice, used a terrible secret to protect the kingdom, which has since flourished and expanded again.

A life

Nowadays, many of us are also burdened with a terrible secret: the master password of our password manager. Few people can find one person who can be completely entrusted with their secrets, but to find a group of five people in which at least three will be responsible people is quite real.

Thanks to modern open source technology, we can use an existing solution and not write everything from scratch.

Suppose you have five people you trust (not completely, but at least a little): your best friend, spouse, your mother, colleague, and your lawyer.

To split your key, you can install and run the ssss program:

$ echo 'long legs travel fast' | ssss-split -t 3 -n 5
Generating shares using a (3,5) scheme with dynamic security level.
Enter the secret, at most 128 ASCII characters: Using a 168 bit security level.
1-797842b76d80771f04972feb31c66f3927e7183609
2-947925f2fbc23dc9bca950ef613da7a4e42dc1c296
3-14647bdfc4e6596e0dbb0aa6ab839b195c9d15906d
4-97c77a805cd3d3a30bff7841f3158ea841cd41a611
5-17da24ad63f7b704baed220839abb215f97d95f4f8

We come up with a master password: "long legs go quickly." You can never completely trust someone alone, but you can send five fragments to five proxies.

  • You send 1 to your best friend.
  • You send 2 to your spouse.
  • You send 3 to your mom.
  • You send 4 to your colleague.
  • You send 5 to your lawyer.

Now, let's say you are going on vacation. During the month you frolic on the beach. While you frolic, you do not use any electronic device. Soon enough, your master password will be forgotten.

Suppose that the spouse and mother were also on vacation and forgot all the passwords, having lost access to the fragments of your master password stored in their password manager.

Fine.

Then you turn to the best friend, and he gives you his fragment: 1-797842b76d80771f04972feb31c66f3927e7183609.
Contact a colleague: 4-97c77a805cd3d3a30bff7841f3158ea841cd41a611.
Well, to a lawyer who takes $ 150 dollars per hour:
5-17da24ad63f7b704baed220839abb215f97d95f4f8.

And then run:

$ ssss-combine -t 3
Enter 3 shares separated by newlines:
Share [1/3]: 1-797842b76d80771f04972feb31c66f3927e7183609
Share [2/3]: 4-97c77a805cd3d3a30bff7841f3158ea841cd41a611
Share [3/3]: 5-17da24ad63f7b704baed220839abb215f97d95f4f8
Resulting secret: long legs travel fast

That's all: one, two, three, and you're in the ladies. More precisely, in kings -)

Use for health

Password management is an important skill in modern online life. Of course, passwords should be quite complex. But do not stop there. You can use Shamir’s secret sharing scheme to make password storage truly secure.


As an advertisement

VDSina offers reliable daily billing servers, each server is connected to an Internet channel of 500 Megabits and is free of charge protected from DDoS attacks! And we also have eternal servers:

Similar Posts

Leave a Reply