Shamir 的秘密共享密码算法简介

Adi Shamir 的秘密共享是一种加密算法，它允许不同的各方通过持有股份来共同共享单个秘密的所有权。原始秘密只能通过使用最小数量的共享来重建，这允许不同的各方进行合作，而无需完全信任彼此。

示例问题

为了说明，让我们假设一个四口之家共享一个比特币钱包。这个比特币钱包包含一个所有家庭成员共同拥有的私钥。因为只有一把钥匙，任何家庭成员都可以使用该钥匙花掉所有的比特币。

这个家庭有一个问题：如果他们每个人都保留一份副本，那么只需破坏他们的一份副本就可以让所有硬币被盗。如果他们中只有一个人保留了钥匙，那么那个人可能会丢失它或决定出卖其他家庭成员。

幸运的是，其中一位家庭成员也是密码学家。他们没有天真地共享原始密钥，而是使用SSS （Shamir 的秘密共享）。该家族创建了四股，并将阈值设置为三股，并将比特币密钥作为原始秘密。现在，他们的计划具有以下属性：

• 他们没有将比特币密钥存储在一个地方，这使得窃取变得更加困难
• 家庭成员需要合作花费比特币，一个家庭成员不能背叛其他成员
• 如果一个家庭成员死亡或失去他们的份额，其他三个成员仍然可以重建密钥

了解阈值

每个 Shamir 共享方案都有一个共享的总数和一个阈值。阈值是重建原始秘密所需的共享数量。例如，有 5 份，阈值为 3，您只需要 5 份中的 3 份即可计算原始秘密。

数学 - 线条

Shamir 的秘密共享中使用的基本数学属性之一是需要k个点来定义k - 1 次多项式。例如：

• 两点之间只能画一条线
• 只有一条可能的抛物线穿过相同的三个点
• 只有一条三次曲线通过相同的四个点
• 通过同一点可以画出无数条线
• 通过相同的两点可以画出无数条抛物线

数学 - 演练

让我们构建一个方案来分享我们的秘密 1954 ( S)与 4 ( n)份和 3 ( k)的阈值。

首先，我们随机选择k - 1 个正整数，所以在我们的例子中，是 2 个正整数。我们随机选择 43 和 12。

然后，我们建立一个形式的多项式

y = a0 + a1*x + a2*x^2

其中 a0 是秘密，a1 和 a2 是我们随机选择的整数。我们剩下：

 y = 1954 + 43x + 12x^2

然后，我们使用这个公式来创建我们给每个参与者的 4 个点（份额）。

分享 1

(x, y) 其中 x = 1

y = 1954 + 43*1 + 12*1^2 = 2009

(1, 2009)

分享 2

(x, y) 其中 x = 2

y = 1954 + 43*2 + 12*2^2 = 2088

(2, 2088)

分享 3

(x, y) 其中 x = 3

y = 1954 + 43*3 + 12*3^2 = 2191

(3, 2191)

分享 4

(x, y) 其中 x = 4

y = 1954 + 43*4 + 12*4^2 = 2318

(4, 2318)

重建

我们计划中的每个参与者现在拥有一个(x,y)点，这是一个单一的份额。请记住，我们将阈值设置为 3，并且 3 个点完美地定义了抛物线（2 次多项式）。这意味着如果我们使用三个点，我们可以绘制抛物线并计算 a0（秘密）。假设我们控制了股份 1、2 和 4。

第 1 步 - 绘制我们控制的点（份额）

第 2 步 - 绘制相应的抛物线

第 3 步 - 找到x=0的点。它的y值是秘密

在我们的例子中，秘密是1954 。

其实没那么简单。我们需要有限域。

虽然我们上面的示例非常适合演示目的，但它实际上并不是很安全。对于攻击者获得的每个共享，他们实际上正在获得越来越多的关于秘密的信息。虽然有两点不能完美地描述抛物线，但它们仍然会泄露有关抛物线的关键信息。

解决方案在于有限域算术。通过在足够大的有限域上绘制函数，多项式的图变得不连贯和分散，这意味着攻击者无法对底层函数的路径做出有根据的猜测。

阿迪沙米尔

Adi Shamir 是以色列密码学家，以 Shamir 的秘密共享而闻名，但他也是绝大多数互联网所基于的广泛使用的 RSA 算法的共同发明者。 Shamir 出生在特拉维夫，并在那里的大学获得了数学本科学位。后来他获得了硕士和博士学位。分别于 1975 年和 1977 年获得魏茨曼研究所计算机科学学位。