Shamir" role="presentation" style="font-size: 16px; box-sizing: border-box; display: inline; line-height: normal; word-wrap: normal; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; caret-color: rgb(26, 26, 26); color: rgb(26, 26, 26); font-family: "lucida grande", "lucida sans unicode", lucida, helvetica, "Hiragino Sans GB", "Microsoft YaHei", "WenQuanYi Micro Hei", sans-serif;">Shamir's Secret Sharing算法（密钥分享算法）最早是由Shamir和Blackly在1970年基于Lagrange插值和矢量方法提出的。主要的思想是将秘密s分解为n个密钥持有者，任意k个密钥均能恢复密文，而任意k-1个密钥均无法得到密文的任何信息。
Shamir的密钥分享算法的基本思想是2点足以定义一条线，3点足以定义抛物线，4点定义立方曲线等等。也就是说，需要k个点来定义度数k-1的多项式。
如下图，两点（X1，Y1）和（X2，Y2）可以唯一的确定一条直线，从而可以获得该直线通过Y轴的值，也就是Secret。如果只知道（X1，Y1）或者（X2，Y2）都无法获取Secret，因为通过单点的直线有无数条。
0）密钥分享算法
算法由一个二元组（k，n）表示，也就是说，秘钥分成n份，需要其中的k份即可恢复出秘密。
1）加密过程
对于待加密的明文s，在有限群上任取k-1个随机数a1，a2...ak-1，并让a0=s，构造如下的多项式：
其中的p为大质数。
对于这个多项式，任取n个数，x1，x2...xn，生成n个密码对：
n个密码对，可以分发给n个不同的密码持有者。
2）解密过程
在获取k个密码的前提下，可以生成如下的方程：
求解如上的方程，可以获取a0，也就是加密前的明文。
总结：Shamir's Secret Sharing算法（密钥分享算法）最早是由Shamir和Blackly在1970年提出。Shamir的秘密分享算法的基本思想是2点足以定义一条线，3点足以定义抛物线，4点定义立方曲线等等。算法由一个二元组（k，n）表示，秘钥分成n份，需要其中的k份即可恢复出秘密。
