密码学协议举例[1]–秘密共享的门限方案

最近在看关于密码学的书，刚好从一个人的博客那里看到一些有趣的密码学的协议（参考网站在这篇文章的最后），所以自己上网查了一些资料后把他按照我的理解补充了一下，之后会每篇文章讲一个协议的。

当然，讲密码学协议之前要先了解一下什么是密码学协议，也是很简单的概念。

什么是密码协议

密码协议是以密码算法为基础的协议，也称作安全协议。

什么是协议

协议是指双方或者多方为了完成一项任务所进行的一系列步骤，而每一步必须依次执行，在前一步完成前，后面的步骤是不能进行的。

什么是密码协议

密码协议是使用密码技术完成某项任务并且满足安全需要的协议

秘密共享的门限方案

问题来源

电影中经常出现这样的情节：有一份绝密文件需要交给5位特工，为了防止某个特工被捕或者叛变，5名特工各自只持有其中1/5的文件（更好的做法是只持有其中1/5的密钥），这5名特工需要同时在场才能获取文件全文。

但这也有一个隐患：如果真的有特工被抓了，当坏人们发现只拿到其中一份文件没有任何用处的同时，特工们也会因为少一份文件无法解开全文而烦恼。

现在我们要解决的问题是，是否有什么办法能够让特工们仍然能够恢复原文，即使一部分特工被抓住了？换句话说，有没有什么密文发布方式使得，只要5个人中半数以上的人在场就可以解开绝密文件？这样的话，侵入者必须要能操纵半数以上的特工才可能对秘密文件造成实质性的影响。这种秘密共享方式被称为(3,5)门限方案，意即5个人中至少3人在场才能解开密文。

解决办法

办法一：拉格朗日插值法(Shamir门限法)

我们可以利用了下面这个事实：知道m-1次多项式函数上的任意m个点就能恢复出整个多项式。

例如在上面的（3，5）门限中，我么可以构造已下式子：f(x)=a x^2+b x+k，其中k为秘密，任意选出该式子上的五个点，分给5个人，这时任意三个点（任意三个人）就可以解除（a，b，k）其中k就是秘密。当只有两个或更少的人时，是无法解出的。

假设我们要保守的秘密是-7，则我们可以构造多项式f(x) = -7. + 7. x - 1. x^2，并简单计算出五个点

{1, -1}, {2, 3}, {3, 5}, {4, 5}, {5, 3}分发个5个人。

我们可以看下面的示意图，红色的点为要分配的五个点，绿的的点为多项式与y轴的交点，即我们的秘密。

只有当五个人中有三个来到，我们才能解出秘密。

上面的方法易于扩展成（k，n）门限，即只需要对k-1次多项式取n个点分给n个人即可。

方法二：利用三维空间中的点的确定

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

这种方法与上面的方法类似，上面的方程为构造形如f(x)=a x^2+b x+k的式子，而在这里是构造形如z=Ax+By+k的式子，并且，这种方法也较为容易的扩展为（k，n）门限，只需要在k维空间里取n个点即可

方法三：传统方法

把这份文件的密钥拆成C(n,m-1)份，每个人持有C(n-1,m-1)份密钥。

例如在(3,5)门限方案中，我们需要C(5,2)=10个密钥，不妨分别用0到9编号；5个人各持有C(4,2)=6个密钥，密钥的分配如下：

• 人#1: 012345
• 人#2: 012 678
• 人#3: 0 34 67 9
• 人#4: 1 3 56 89
• 人#5: 2 45 789

上述分配表的构造其实很简单：为每一个人的5选3组合分配一个密钥，例如：

• 把密钥0分给特工1、2、3
• 把密钥1分给特工1、2、4
• 把密钥9分给特工3、4、5

这样的话，任意两个人在场都无法打开文件，因为他们始终缺少一把钥匙（这把钥匙分给了其余三个人）。而任意三个人在场都足以打开文件，因为根据鸽笼原理，任何一个5选3组合中总有一个人落在这三个人当中。这样，我们便利用组合数学巧妙地解决了这一问题。

参考网站

Matrix博客