第十九个知识点：Shamir密钥交换场景

Shamir密钥交换场景是一个被Adi Shamir提出的算法.算法允许多方分割一个密码,例如一个密钥.当足够多的秘密结合起来,整个密钥就被计算出来了.

正式的说,如果我们有秘密(S)和(n)方,我们能把(S)划分成(n)方.然后把它们分发给不同的组织.通过这样发送的密钥有一个限定值(k),如果密钥(S)的(k)数量的部分被收集到,那么就可以计算出(S).如果(k-1)或者更少的密钥被收集,那么(S)将无法被计算.这个场景就叫做((k,n))限定场景.

解释为什么场景能够被这样构造的最好方式就是通过一个例子.假设我们想要把分割秘密(S = 1425).分割成5部分((n = 5)).同时需要3方才能允许密钥((S))被计算出来.首先我们构造一个多项式(f(x)).它的阶为((k-1 = 2)).系数是随机的.假如说是(a_1 = 64, a_2 = 112).和一个常数(S).

[f(x) = S + a_1x + a_2x^2 = 1425 + 64x + 112x^2 ]

从这个多项式中我们可以看到,我们可以构造5个点.这些点分发给不同的组织.

[P_0=(1,1601),P_1=(2,2001),P_2=(3,2625),P_3=(4,3473),P_4=(5,4545) ]

如果我们假设我们知道5个点中的3个点.我们能够计算出这个多项式的系数.通过3个三元一次多项式.

就上面的例子来看,这个方法工作的很好.但是,窃听者也能够收集更多关于秘密的信息.因为上面我们已经工作在一个有理数的算数.然而，如果我们在有限域内工作(因此秘密和多项式是在q大小的域上定义的)，那么如果任何两个或更少的参与方走到一起，他们对秘密一无所知。

这是因为这样的两方假如说组织一和组织二,然后密钥的值S来源于这个域.那么就有一个总有一个在这个多项式域中定义的值:(0,S'), (2,2001 mod q) and (3,2625 mod q).

[1] - http://en.wikipedia.org/wiki/Polynomial

[2] - http://en.wikipedia.org/wiki/Lagrange_polynomial

[3] - http://en.wikipedia.org/wiki/Shamir%27s_Secret_Sharing