我们中的许多人使用密码管理器来安全地存储我们众多的唯一密码。密码管理器的关键部分是主密码。这个密码保护着所有其他密码，因此它也是一个风险。任何拥有它的人都可以在任何地方冒充你！ 当然，你会让你的主密码难以猜测，牢记在心，并做所有其他应该做的事情。
但是，如果你忘记了密码会怎么样？ 也许你到一个遥远的美丽岛屿度假一个月，那里没有任何科技设备。每天在水中嬉戏，吃着菠萝之后，你完全记不得你的密码了。 也许是“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 < PTRUE并将其转换为模 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]二十年后，正如国王所规定的，最年长的兄弟姐妹和两个最小的兄弟姐妹聚在一起，试图找出他们父亲的可怕秘密。 他们将碎片拼凑在一起
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 == secretTRUE数学魔法的美妙之处在于它每次都能可靠地工作！ 孩子们现在长大了，能够理解他们父亲的选择，他们用可怕的秘密来保卫王国。 王国繁荣昌盛。
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 秘密共享算法，安全地与他人分享。
11 条评论