wssccc


我们在世纪末的流光中追寻过往,追寻那些渐渐模糊的面容


简明Shamir门限方案

使用场景

一个密码箱的密码需要分成多个部分,由不同的人保存,只有大于一定数量的人联合起来,才能开启密码箱。

例子

vault使用了Shamir密钥共享算法来把master key分成多个保存,只有多于threshold个数的key shares才能还原出master key。

原理

定义

秘密S分成n个子秘密,任意k个可以重建S,k-1个不能重建S。

生成Key Shares

$a_0=S$,取随机数 $a_1 \cdots a_{k-1}$

构造多项式 $f(x) = a_0 + a_1x … + a_{k-1}x^{k-1}$

取随机数 $x_1 \cdots x_n$,代入多项式$f(x)$,得到$f(x_1) \cdots f(x_n)$

$(x_1,f(x_1)) \cdots (x_n,f(x_n))$ 即为生成的key shares。

还原Key

任取k个key shares,代入多项式
$$a_0 + a_1x_1 + … + a_{k-1}x_1^{k-1} = y_1$$$$a_0 + a_1x_2 + … + a_{k-1}x_2^{k-1} = y_2$$$$…$$$$a_0 + a_1x_k + … + a_{k-1}x_k^{k-1} = y_k$$

表示为矩阵形式

$$\begin{pmatrix}
1& x_1& \cdots& x_1^{k-1} \\
1& x_2& \cdots& x_2^{k-1} \\
\vdots& \vdots& \ddots& \vdots \\
1& x_k& \vdots& x_k^{k-1} \\
\end{pmatrix}
\begin{pmatrix}
a_0 \\
a_1 \\
\vdots \\
a_{k-1} \\
\end{pmatrix}
=
\begin{pmatrix}
y_1 \\
y_2 \\
\vdots \\
y_k \\
\end{pmatrix}
$$

$$\downarrow$$

$$\begin{pmatrix}
a_0 \\
a_1 \\
\vdots \\
a_{k-1} \\
\end{pmatrix}
=
\begin{pmatrix}
1& x_1& \cdots& x_1^{k-1} \\
1& x_2& \cdots& x_2^{k-1} \\
\vdots& \vdots& \ddots& \vdots \\
1& x_k& \vdots& x_k^{k-1} \\
\end{pmatrix}^{-1}
\begin{pmatrix}
y_1 \\
y_2 \\
\vdots \\
y_k \\
\end{pmatrix}
$$

求得$a_0 \cdots a_{k-1}$,$S=a_0$即为原Key。

相关库

<dependency>
<groupId>com.tiemens</groupId>
<artifactId>secretshare</artifactId>
<version>1.4.2</version>
</dependency>