下载掌阅APP，畅读海量书库
立即打开
Shamir于1979年给出了秘密共享方案，基于Lagrange插值法的( t , n )门限秘密共享方案的主要步骤如下。
Step 1 初始化阶段。设 q 为一个大素数，秘密分发者 D 随机选取 n 个不同的非零元 x 1 , x 2 ,…, x n ∈ Z q ，将 x i 对应分发给参与者 P i 。
Step 2 秘密共享阶段。秘密分发者 D 随机选取 t -1个元素 a i ∈ Z p 。构造 t -1次多项式 f ( x )= a 0 + a 1 x + a 2 x 2 +…+ a t-1 x t-1 ，其中 a 0 = s ，计算 f ( x i )= s i ，并将 s i 分发给参与者 P i , i =1,2,…, n 。
Step 3 秘密重构阶段。至少任意 t 个参与者合作给出其 s i ，即可利用Lagrange插值多项式恢复秘密 s = f (0)。Lagrange插值多项式为
其中，
为Lagrange插值系数。
Shamir提出的秘密共享方案是基于信息论安全的，即至多 t -1个参与者不能得到关于秘密 s 的任何信息。该方案没有基于任何数学困难问题，故不会像 RSA （Rivest-Shamir-Adleman）算法一样因数学难题被解决而被攻破。但该方案没有考虑秘密分发者和参与者的诚实性，若某些参与者公开假的份额会导致秘密无法恢复，甚至可能导致某些恶意参与者独获秘密。