Shamir密钥分享算法简析

简述

秘密共享技术是密码学和信息安全的一个重要研究内容，Shamir密钥分享算法最早是由Shamir和Blackly在1970年基于Lagrange插值和矢量方法提出的，其基本思想是分发者通过秘密多项式，将秘密s分解为n个秘密分发个持有者，其中任意不少于k个秘密均能恢复密文，而任意少于k个秘密均无法得到密文的任何信息。

实际应用

比如在门限体系中，为了保证信息安全性，一个秘密通常不能由单个持有者保存。比如一些重要场所的通行，比如遗嘱的生效等，必须将秘密分由多人保管并且只有当多人同时在场时秘密才能得以恢复。在这些场合，就需要这样一套的密钥分享技术。

算法思路

表示

Shamir密钥共享算法由一个二元数(k,n)表示，其中n表示将明文s加密为n个Shadow，k表示必须至少同时拥有k个Shadow才能解密获得成明文。

加密

对于待加密的明文s∈Zp(p为大素数)，在有限群GF(p)任取k−1个随机数a1,a2,...,ak−1，并令a0=s，从而构造如下的多项式：

对于这个多项式，任取n个数x1,x2,x3,...,xn分别带入多项式得到n个密钥对:

分发给n个持有者。

解密

假设得到了k个密钥对{x1,y1}{x2,y2}...{xk,yk}，我们可以得到如下方程(运算均在GF(p))：

由矩阵乘法或者Lagrange插值法均可求的a0即为明文s。

安全性

由伽罗华域以及矩阵运算的性质可知该算法的安全性是显然的。

补充

当k=n的时候，Shamir算法还有一种用异或运算的实现:任取n−1个随机数(r1,r2,r3,...,rn−1),对于明文s计算

这样就可以通过将这n个数全部进行异或来得到明文，同时，任意一个Shadow都不会泄露有关秘密的任何信息。