使用 Python 加密算法永不忘记您的密码

我们中的许多人使用密码管理器来安全地存储我们许多唯一的密码。密码管理器的关键部分是主密码。 此密码保护所有其他密码，因此它存在风险。 拥有它的人可以伪装成你……在任何地方！ 自然，您会确保您的主密码难以猜测，牢记在心，并完成所有其他您应该做的事情。

但是，如果发生某些事情并且您忘记了它怎么办？ 也许您去一个美丽的、遥远的、没有技术的小岛度假一个月。 每天在水中嬉戏并吃菠萝后，您无法完全记住您的密码。 也许是“long legs travel fast”？ 还是像“sharp spoons eat quick”这样的东西？ 当您想到它时，它绝对很聪明。

图片来自

(XKCD, CC BY-NC 2.5)

当然，您从未向任何人透露过您的密码。 为什么，这实际上是密码管理的第一条规则。 您本来可以做些什么不同的事情？

输入 Shamir 密钥共享，这是一种允许用户将密钥分成若干部分的算法，这些部分只能与其他部分结合使用。

让我们通过古代和现代的故事来看看 Shamir 密钥共享的实际应用。

这个故事确实假设了一些密码学的知识。 您可以通过密码学和公钥基础设施介绍来复习它。

古代的秘密故事

在古代王国，国王有一个秘密。 一个可怕的秘密。

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"))

太可怕了，国王无法将它托付给他的任何后代。 他有五个孩子，但知道未来的道路上会有危险。 国王知道他的孩子们需要这个秘密来保护王国在他死后，但他无法忍受这个秘密被知道二十年，当他们还在悼念他的时候。

因此，他使用强大的魔法将秘密分成五个碎片。 他知道有可能一个孩子甚至两个孩子不会尊重他的意愿，但他不相信其中三个会这样做。

from mod import Mod
from os import urandom

国王精通有限域和随机性的魔法。 作为一位明智的国王，他使用 Python 来分割秘密。

他做的第一件事是选择一个大的质数 - 第 13 个 梅森素数 (2**521 - 1) - 并命令用 10 英尺高的字母写在宫殿上方，用黄金制成。

P = 2**521 - 1

这不是秘密的一部分：它是公共数据。

国王知道，如果 P 是一个质数，则模 P 的数字形成一个数学域：只要除数不为零，它们就可以被添加、相乘、相减和相除。

作为一个繁忙的国王，他使用了 PyPI 包 mod，它实现了模运算。

他确保他的可怕秘密小于 P

secret < P

TRUE

他将其转换为模数 mod P

secret = mod.Mod(secret, P)

为了让三个后代能够重建秘密，国王必须生成另外两个部分来混合在一起。

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

3

国王接下来需要在随机点评估这个多项式。 评估多项式是计算 polynomial[0] + polynomial[1]*x + polynomial[2]*x**2 ...

虽然有第三方模块可以评估多项式，但它们不适用于有限域。 国王需要自己编写评估代码。

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

接下来，国王在五个不同的点评估多项式，以给每个后代一片。

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

可悲的是，正如国王所担心的那样，并非他所有的后代都是诚实和真实的。 他们中的两个，在他去世后不久，试图从他们拥有的部分中找出可怕的秘密。 尽其所能，他们没有成功。 然而，当其他人得知此事后，他们将他们永远流放出了王国。

del shards[2]
del shards[3]

二十年后，正如国王所 decree 的那样，最年长的兄弟姐妹和两个最小的兄弟姐妹聚在一起，想出他们父亲可怕的秘密。 他们把他们的碎片放在一起。

retrieved = list(shards.values())

40 天 40 夜，他们都在努力寻找国王的秘密。 在他们面前的任务并不容易。 像国王一样，他们懂 Python，但没有人像他那么聪明。

最后，答案来了。

检索代码基于一个名为 拉格朗日插值的概念。 它根据多项式在 n 个其他地方的值评估 0 处的多项式，其中 n 是多项式的次数。 它的工作方式是，您可以明确地找到一个多项式的公式，该公式在 t[0] 处为 1，在 t[i] 处为 0，对于 i 与 0 不同。 由于评估多项式是线性函数，因此您可以评估每个这些多项式，并使用多项式具有的值插值评估结果。

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

毫不奇怪，这花了他们 40 天 40 夜 - 这段代码非常复杂！ 但他们在幸存的碎片上运行它，屏住呼吸等待着。

retrieved_secret = retrieve_original(retrieved)

孩子们是否得到了正确的秘密？

retrieved_secret == secret

TRUE

数学的魔力在于它每次都能可靠地工作！ 孩子们现在长大了，能够理解他们父亲的选择，用可怕的秘密来捍卫王国。 王国繁荣昌盛。

Shamir 密钥共享的现代故事

在现代，我们中的许多人也背负着一个可怕的秘密：密码管理器的密码。 虽然很少有人可以完全信任一个人他们最深、最黑暗的秘密，但许多人可以找到五个人的团体，其中不太可能有三个人一起打破他们的信任。

幸运的是，在这些现代时代，我们不需要像国王那样自己分割我们的秘密。 通过开源的现代技术，我们可以使用现有的软件。

假设你有五个你信任的人 - 不是绝对的，而是一些：你最好的朋友，你的配偶，你的妈妈，一位亲密的同事和你的律师。

您可以安装并运行程序 ssss 来分割密钥

$ 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

啊，一个强大而有力的主密码：long legs travel fast。 永远不能委托给一个人，但您可以将五个碎片发送给您的五个监护人。

• 您将 1 发送给您最好的朋友 F。
• 您将 2 发送给您的配偶 S。
• 您将 3 发送给您的妈妈 M。
• 您将 4 发送给您的同事 C。
• 您将 5 发送给您的律师 L。

现在，假设您去家庭度假。 一个月来，您在温暖的沙滩上嬉戏。 当您嬉戏时，您不会触摸任何电子设备。 不久，您强大的主密码就被遗忘了。

您心爱的配偶和亲爱的母亲和您一起度假。 他们将碎片安全地保存在密码管理器中 - 他们忘记了他们的密码。

没关系。

您联系了您最好的朋友 F，他给了您 1-797842b76d80771f04972feb31c66f3927e7183609。 您的同事，他承担了你所有的轮班，很高兴你回来，并给了你 4-97c77a805cd3d3a30bff7841f3158ea841cd41a611。 您的律师每小时向您收取 150 美元，进入他们的密码管理器，并挖出 5-17da24ad63f7b704baed220839abb215f97d95f4f8。

有了这三个碎片，您就可以运行

$ 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

因此，借助开源技术，您也可以像国王一样生活！

为了您的安全，安全共享

密码管理是当今在线生活的一项基本技能。 当然，创建一个复杂的密码，但不要止步于此。 使用方便的 Shamir 密钥共享算法安全地与他人共享它。