如何分摊秘密（八）

十一、Shamir分摊法

本节要介绍的是以色列密码学家Adi Shamir在1979年提出的一个非常优雅高效的基于有限域上拉格朗日插值法的秘密分摊方法。Shamir最为杰出和广为人知的贡献是同Ron Rivest和Leonard Adleman一起建立了著名的RSA加密系统，他们因此获得了2002年的图灵奖。

Shamir分摊法的思想是相当简单的：首先将需要分摊的秘密藏入一个k-1次多项式，需要知道秘密，就需要恢复出多项式；在n个（n>k）点上对多项式取值，这些值被分摊给n人；而只要其中任意的k个值，我们就可以通过拉格朗日插值法来恢复出原多项式，从而揭示出原始秘密。

让我们来看一下具体方法。

和先前一样，首先得固定秘密的范围即一个整数N，而秘密s是0到N-1之间的某数。但现在我们对N有另外两个要求。一是要求N必须大于参与分摊秘密的总人数。如果是在100个人之间分摊一个6位账号密码，那么原来N=1000000已经大于100，没有必要变动N；但如果是在100个人里面分摊一个是非题的答案，也就是1比特的信息，那么原来N可取2，现在则必须取大于100的数。二是要求N必须为素数，因为这次我们不但将在以N为模的同余类之间做加减法，还要做乘除法，也即我们要在域GF(N)上运算。如果要分摊一个6位账号密码，原来N=1000000，现在就要取N为大于1000000的素数，比如可以取满足这个要求的最小素数1000003。

现在用一个好的随机数产生器产生k-1个0到N-1之间的整数，令它们为a₁，a₂，……，a_k-1。考虑下面系数在GF(N)中的k-1次多项式： P(x) = [a_k-1]x^k-1+……+[a₂]x²+[a₁]x+[s] 其中[]表示以N为模的同余类。接着计算出P([1])，P([2])，……，P([n])，把它们分别给n人，这就是分摊给他们的那部分秘密；同时也分别告诉每人他们是第几人。（相当于给每个人一个二元组([t],P([t]))，但只有P([t])这部分被看作是秘密，每人对应的那个[t]不被看作是秘密，甚至可以是公开的。）我们看出为什么前面要求N必须大于参与分摊秘密的总人数的目的，因为这样才能使[1]，[2]，……，[n]都是在GF(N)中的不同的同余类。更一般地，我们其实并不需要这n个取值点一定是[1]，[2]，……，[n]，只需这是GF(N)内n个不同于[0]的值就可以了。

如果有k个以上的人同意合作，我们只需任意选择其中的k人，把分摊给他们的秘密收集起来，这相当于知道了多项式P在k个点上的值，于是可以用拉格朗日插值法来恢复出P，然后计算P([0])就得到了原秘密[s]。

如果只有k-1个人同意合作，他们能得到什么样的关于原始秘密的结论？对于每一个可能的原始秘密[s’]，也即每一个可能的P([0])，我们都可以用它和这k-1个人所持有的P在另外k-1个点的值一起来使用拉格朗日插值法，得到一个多项式P’。因为对P的系数的随机选取的原因，任何一个这样插值出来的多项式P’是真正的P的可能性都是一样的，而且P’([0])=[s’]。于是每个[s’]是真正的秘密[s]的可能性也是一样的。所以这k-1人无法更多地了解原始秘密。

我们可以看到，这个分摊秘密的方法是非常高效的，它只需要每个分摊秘密的人记住自己的编号（一般来说不会很大），和一个GF(N)中的元素，所需要的储存空间和原秘密一样。也许有人会指出在一开始我们需要增加N让它成为一个素数，会增加所需的储存空间。但根据伯特兰-切比雪夫定理，对任何自然数m，我们总能在p和2p之间找到一个素数。即便在上面N为素数的要求下，需要将原来的N增加到2N-1，也只不过多增加1比特的空间而已，所以因为这个原因增加的储存空间可以忽略不计。

最后让我们具体看一个例子。本来应该举一个100个人分摊秘密需至少80个人同意才能揭晓秘密的例子，但这得产生一个79次的多项式，并计算P在100个点上的值，用电脑倒是不麻烦，可写出来没法读。所以我们退而求其次，举一个10人分摊秘密需至少8人同意才能揭晓秘密的例子，被分摊的原始秘密则仍是一个6位账号密码。

按照前面所说，我们取N=1000003。令被分摊的秘密是123456。

用随机数产生器产生7个0到1000002之间的随机数，这里举例就用401993, 875845, 799228, 672942, 171533, 797326, 384241，得到多项式 P(x) = [401993]x⁷+[875845]x⁶+[799228]x⁵+[672942]x⁴+[171533]x³+[797326]x²+[384241]x+[123456] 在GF(N)内计算得到： P([1]) = [226552] P([2]) = [304611] P([3]) = [448569] P([4]) = [759237] P([5]) = [232780] P([6]) = [368644] P([7]) = [538534] P([8]) = [155130] P([9]) = [679162] P([10]) = [503465] 这就是分别分摊给第一到第十个人的秘密。

如果其中的8个人，比如是第三到第十人决定要揭开秘密，他们拥有上面所列的P([3])到P([10])的值，但没有P([1])和P([2])。

按照上节拉格朗日插值法，我们要先计算以下8个多项式： r₁(x) = (x-[4])(x-[5])(x-[6])(x-[7])(x-[8])(x-[9])(x-[10])/(([3]-[4])([3]-[5])([3]-[6])([3]-[7])([3]-[8])([3]-[9])([3]-[10])) r₂(x) = (x-[3])(x-[5])(x-[6])(x-[7])(x-[8])(x-[9])(x-[10])/(([4]-[3])([4]-[5])([4]-[6])([4]-[7])([4]-[8])([4]-[9])([4]-[10])) r₃(x) = (x-[3])(x-[4])(x-[6])(x-[7])(x-[8])(x-[9])(x-[10])/(([5]-[3])([5]-[4])([5]-[6])([5]-[7])([5]-[8])([5]-[9])([5]-[10])) r₄(x) = (x-[3])(x-[4])(x-[5])(x-[7])(x-[8])(x-[9])(x-[10])/(([6]-[3])([6]-[4])([6]-[5])([6]-[7])([6]-[8])([6]-[9])([6]-[10])) r₅(x) = (x-[3])(x-[4])(x-[5])(x-[6])(x-[8])(x-[9])(x-[10])/(([7]-[3])([7]-[4])([7]-[5])([7]-[6])([7]-[8])([7]-[9])([7]-[10])) r₆(x) = (x-[3])(x-[4])(x-[5])(x-[6])(x-[7])(x-[9])(x-[10])/(([8]-[3])([8]-[4])([8]-[5])([8]-[6])([8]-[7])([8]-[9])([8]-[10])) r₇(x) = (x-[3])(x-[4])(x-[5])(x-[6])(x-[7])(x-[8])(x-[10])/(([9]-[3])([9]-[4])([9]-[5])([9]-[6])([9]-[7])([9]-[8])([9]-[10])) r₈(x) = (x-[3])(x-[4])(x-[5])(x-[6])(x-[7])(x-[8])(x-[9])/(([10]-[3])([10]-[4])([10]-[5])([10]-[6])([10]-[7])([10]-[8])([10]-[9])) （注意到诸r_i(x)的下标是独立的，和十个人本身的编号无关。在重构原多项式P时，r₁(x)到r₈(x)将分别和第三到第十人拿的P([3])到P([10])的值相乘后再相加。）

为了计算简单起见，考虑到我们想知道的秘密其实是最终的多项式P在[0]点的值P([0])，我们也只需计算上面这些多项式在[0]点的值： r₁([0]) = (-[4])(-[5])(-[6])(-[7])(-[8])(-[9])(-[10])/(([3]-[4])([3]-[5])([3]-[6])([3]-[7])([3]-[8])([3]-[9])([3]-[10])) = [-604800]/[-5040] r₂([0]) = (-[3])(-[5])(-[6])(-[7])(-[8])(-[9])(-[10])/(([4]-[3])([4]-[5])([4]-[6])([4]-[7])([4]-[8])([4]-[9])([4]-[10])) = [-453600]/[720] r₃([0]) = (-[3])(-[4])(-[6])(-[7])(-[8])(-[9])(-[10])/(([5]-[3])([5]-[4])([5]-[6])([5]-[7])([5]-[8])([5]-[9])([5]-[10])) = [-362880]/[-240] r₄([0]) = (-[3])(-[4])(-[5])(-[7])(-[8])(-[9])(-[10])/(([6]-[3])([6]-[4])([6]-[5])([6]-[7])([6]-[8])([6]-[9])([6]-[10])) = [-302400]/[144] r₅([0]) = (-[3])(-[4])(-[5])(-[6])(-[8])(-[9])(-[10])/(([7]-[3])([7]-[4])([7]-[5])([7]-[6])([7]-[8])([7]-[9])([7]-[10])) = [-259200]/[-144] r₆([0]) = (-[3])(-[4])(-[5])(-[6])(-[7])(-[9])(-[10])/(([8]-[3])([8]-[4])([8]-[5])([8]-[6])([8]-[7])([8]-[9])([8]-[10])) = [-226800]/[240] r₇([0]) = (-[3])(-[4])(-[5])(-[6])(-[7])(-[8])(-[10])/(([9]-[3])([9]-[4])([9]-[5])([9]-[6])([9]-[7])([9]-[8])([9]-[10])) = [-201600]/[-720] r₈([0]) = (-[3])(-[4])(-[5])(-[6])(-[7])(-[8])(-[9])/(([10]-[3])([10]-[4])([10]-[5])([10]-[6])([10]-[7])([10]-[8])([10]-[9])) = [-181440]/[5040] 读者可以自行验证，在GF(1000003)中我们有：[1]/[144]=[701391]，[1]/[240]=[220834]，[1]/[720]=[740280]，[1]/[5040]=[534327]，于是 r₁([0]) = [-604800]/[-5040] = [-604800][-534327] = [323160969600] = [120] r₂([0]) = [-453600]/[720] = [-453600][740280] = [-335791008000] = [999373] r₃([0]) = [-362880]/[-240] = [-362880][-220834] = [80136241920] = [1512] r₄([0]) = [-302400]/[144] = [-302400][701391] = [-212100638400] = [997903] r₅([0]) = [-259200]/[-144] = [-259200][-701391] = [181800547200] = [1800] r₆([0]) = [-226800]/[240] = [-226800][220834] = [-50085151200] = [999058] r₇([0]) = [-201600]/[-720] = [-201600][-740280] = [149240448000] = [280] r₈([0]) = [-181440]/[5040] = [-181440][534327] = [-96948290880] = [999967]

于是最后的秘密就可以通过第三到第十人知道的P([3])，P([4])，……，P([10])和上述的诸r_i([0])的值求出： P([0]) = P([3])r₁([0])+P([4])r₂([0])+P([5])r₃([0])+P([6])r₄([0])+P([7])r₅([0])+P([8])r₆([0])+P([9])r₇([0])+P([10])r₈([0]) = [448569][120]+[759237][999373]+[232780][1512]+[368644][997903]+[538534][1800]+[155130][999058]+[679162][280]+[503465][999967] = [1786629483328] = [123456] 正是原始秘密。