Shamir 秘密共享算法 特性： Shamir 的 (k , n) 秘密共享算法将秘密 S 分为 n 个子秘密，任意 k 个子秘密都可以恢复 出 S ，而任意 k 1 个子秘密无法恢复出 S 。 加密过程： 假设有秘密 S ，任取随机数 a1 ,..., ak 1 。令 a0 S ，构造多项式如下多项式：
将 x 0 代入到多项式可以求得 x) a0 a1 x a2 x 2 ... ak 1 x k 1 ，其中所有的运算都在有限域 F 中进行。
任取 n 个数 x1 ,..., xn 分别带入多项式得到 f ( x1 ),..., f ( xn ) 。 将 ( x1 , f ( x1 )),..., ( xn , f ( xn )) 分别存储在 n 个服务器上。 解密过程： 任取 k 个服务器上的数据，假设取 {x1 , y1},...,{xk , yk } ，代入并求解多项式系数。
用矩阵乘法可以表示如下：
x1k 1 a0 y1 a0 1 x1 x1k 1 y1 k 1 k 1 a1 1 x2 x2 y2 x2 a1 y2 1 x x k 1 y a y a xkk 1 k 1 k 1 k 1 k k k 1 求得 a0 , a1 ,..., ak 1 之后便可以构造出多项式 f ( x) a0 a1 x a2 x 2 ... ak 1 x k 1 1 x1 1 x2 1 x k
a0 a1 x1 ... ak 1 x1k 1 y1
k 1 a0 a1 x2 ... ak 1 xx y2
............................................ a0 a1 xk ... ak 1 xkk 1 yk