密码学协议举例（二）：秘密共享的门限方案

电影中经常出现这样的情节：有一份绝密文件需要交给5位特工，为了防止某个特工被捕或者叛变，5名特工各自只持有其中1/5的文件（更好的做法是只持有其中1/5的密钥），这5名特工需要同时在场才能获取文件全文。但这也有一个隐患：如果真的有特工被抓了，当坏人们发现只拿到其中一份文件没有任何用处的同时，特工们也会因为少一份文件无法解开全文而烦恼。此时，你或许会想，是否有什么办法能够让特工们仍然能够恢复原文，即使一部分特工被抓住了？换句话说，有没有什么密文发布方式使得，只要5个人中半数以上的人在场就可以解开绝密文件？这样的话，侵入者必须要能操纵半数以上的特工才可能对秘密文件造成实质性的影响。这种秘密共享方式被称为(3,5)门限方案，意即5个人中至少3人在场才能解开密文。

实现(m,n)门限方案的一个传统办法是，把这份文件的密钥拆成C(n,m-1)份，每个人持有C(n-1,m-1)份密钥。在(3,5)门限方案中，我们需要C(5,2)=10个密钥，不妨分别用0到9编号；5个特工各持有6个密钥，密钥的分配如下：

特工#1:012345

特工#2:012678

特工#3:034679

特工#4:135689

特工#5:245789

上述分配表的构造其实很简单：为特工的每一种5选3组合分配一个密钥，例如把密钥0分给特工1、2、3，把密钥1分给特工1、2、4，把密钥9分给特工3、4、5。这样的话，任意两个人在场都无法打开文件，因为他们始终缺少一把钥匙（这把钥匙分给了其余三个人）。而任意三个人在场都足以打开文件，因为根据鸽笼原理，任何一个5选3组合中总有一个人落在这三个人当中。这样，我们便利用组合数学巧妙地解决了这一问题。

在密码学中，我们有一些更精妙的方案。最巧妙的方法是，把秘密文件编码为三维空间中的一个点，然后生成5个过该点的平面，每个特工持有其中一个平面方程。显然，两个特工在一起是无法获得原文件的，因为两个平面的公共点有无穷多个；但三个平面的交点是唯一的，因此任意三个人在一起都能解开原文件。

另一个有趣的办法利用了下面这个事实：知道m-1次多项式函数上的任意m个点就能恢复出整个多项式。因此，我们可以把文件编码为一个二次多项式f，然后把f(1)、f(2)、f(3)、f(4)和f(5)的值告诉对应的特工。任意三个特工碰头之后，只需要解一个三元线性方程即可恢复原文件。多项式的这一性质还曾用于数据备份当中。

利用数论知识我们还能得到一个简单的协议。中国剩余定理告诉我们，给出m个两两互质的整数，它们的乘积为P；假设有一个大整数M，如果我们已知M分别除以这m个数所得的余数，那么在0到P-1的范围内可以唯一地确定这个M。我们可以想办法构造这样一种情况，n个数之中任意m个的乘积都比M大，但是任意m-1个数的乘积就比M小。这样，任意m个模数就能唯一地确定M，但m-1个数就不足以求出M来。 Mignotte门限方案就用到了这样一个思路。我们选取n个两两互质的数，使得最小的m个数的乘积比最大的m-1个数的乘积还大。例如，在(3,5)门限方案中，我们可以取53、59、64、67、71这五个数，前面三个数乘起来得200128，而后面两个数相乘才4757。我们把秘密文件编码为一个4757和200128之间的整数，比如123456。分别算出123456模上面那五个数的结果，得到19、28、0、42、58。显然，知道任意三个同余方程就可以唯一地确定出123456，但仅知道两个方程只能得到成百上千个不定解。例如，假设我们知道了x模59等于28，也知道了x模67得42，那么我们只能确定在0到59*67-1内的解913，并且只能断定M是一个形如59 * 67 * k + 913的数，其中k的数量级和当初选的那五个数一样大。