简述
秘密共享技术是密码学和信息安全的一个重要研究内容，$Shamir$密钥分享算法最早是由$Shamir$和$Blackly$在1970年基于$Lagrange$插值和矢量方法提出的，其基本思想是分发者通过秘密多项式，将秘密$s$分解为$n$个秘密分发个持有者，其中任意不少于$k$个秘密均能恢复密文，而任意少于$k$个秘密均无法得到密文的任何信息。
实际应用
比如在门限体系中，为了保证信息安全性，一个秘密通常不能由单个持有者保存。比如一些重要场所的通行，比如遗嘱的生效等，必须将秘密分由多人保管并且只有当多人同时在场时秘密才能得以恢复。在这些场合，就需要这样一套的密钥分享技术。
算法思路
表示
$Shamir$密钥共享算法由一个二元数$(k,n)$表示，其中$n$表示将明文$s$加密为$n$个$Shadow$，$k$表示必须至少同时拥有$k$个$Shadow$才能解密获得成明文。
加密
对于待加密的明文$s\in\ Z_p$($p$为大素数)，在有限群$GF(p)$任取$k-1$个随机数$a_1,a_2,…,a_{k-1}$，并令$a_0=s$，从而构造如下的多项式：$$f(x)=a_0+a_1x+a_2x^2+a_3x^3+…+a_{k-1}x^{k-1}mod(p)$$对于这个多项式，任取$n$个数$x_1,x_2,x_3,…,x_n$分别带入多项式得到$n$个密钥对:$$(x_1,f(x_1)),(x_2,f(x_2)),(x_3,f(x_3)),…,(x_n,f(x_n))$$分发给$n$个持有者。
解密
假设得到了$k$个密钥对$\{x_1,y_1\}\{x_2,y_2\}…\{x_k,y_k\}$，我们可以得到如下方程(运算均在$GF(p)$)：
$$\begin{matrix}a_0+a_1 x_1+a_2 x_1^2+…+a_{k-1}x_1^{k-1}=y_1\\a_0+a_1x_2+a_2x_2^2+…+a_{k-1}x_2^{k-1}=y_2\\……………….\\a_0+a_1x_k+a_2x_k^2+…+a_{k-1}x_{k-1}^k=y_k\end{matrix}$$
由矩阵乘法或者$Lagrange$插值法均可求的$a_0$即为明文$s$。
安全性
由伽罗华域以及矩阵运算的性质可知该算法的安全性是显然的。
补充
当$k=n$的时候，Shamir算法还有一种用异或运算的实现:任取$n-1$个随机数$(r_1,r_2,r_3,…,r_{n-1})$,对于明文$s$计算$$r_n=r_1 \oplus r_2 \oplus r_3 …\oplus r_{n-1}$$
这样就可以通过将这$n$个数全部进行异或来得到明文，同时，任意一个$Shadow$都不会泄露有关秘密的任何信息。