Shamir 的秘密共享密码算法简介 by@wagslane
1,202 讀數

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

2022/05/23
经过 @wagslane 1,202 讀數
tldt arrow
ZH
Read on Terminal Reader

太長; 讀書

Adi Shamir 的秘密共享* 是一种加密算法,它允许不同的各方通过持有 *shares* 来共同共享单个秘密的所有权。原始秘密只能通过使用最小数量的共享来重建,这允许不同的各方进行合作,而无需完全信任彼此。该家族创建了四份股份,并将阈值设置为三份,以比特币密钥作为原始秘密。每个 Shamir 共享方案都有股份总数和门槛。

Coin Mentioned

Mention Thumbnail
featured image - Shamir 的秘密共享密码算法简介
Lane Wagner HackerNoon profile picture

@wagslane

Lane Wagner

Founder of Boot.dev. Whining about coding sins since 2011....

关于 @wagslane
LEARN MORE ABOUT @WAGSLANE'S EXPERTISE AND PLACE ON THE INTERNET.
react to story with heart

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 步 - 绘制我们控制的点(份额)

image

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

image

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

image

在我们的例子中,秘密是1954

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

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

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

阿迪沙米尔

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

相關故事

L O A D I N G
. . . comments & more!
Hackernoon hq - po box 2206, edwards, colorado 81632, usa