Never forget your password with this Python encryption algorithm

  • June 15, 2020
  • 0

This unique algorithm using Python and Shamir’s Secret Sharing protects your master password from hackers and your own forgetfulness.

Moshe Zadka

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:

def int_from_bytes(s):
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 mod import Mod
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 P:

secret < P
TRUE

And he converted it to its modulus mod P:

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:

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

The king next needed to evaluate this polynomial at random points. Evaluating a polynomial is calculating polynomial[0] + polynomial[1]*x + polynomial[2]*x**2 ...

Read the full article here.