门限机制
在现实中有效的门限机制在密钥管理的应用中有着举足轻重的地位。我们假设一个场景，有一个秘密被锁在一个箱子里面，一共有 5 个人参与这件事，最少需要 3 个人在场的时候才可以打开这个箱子，那么最少需要多少把锁，而每个人最少需要保管几把钥匙？答案是 10 把锁，6 把钥匙。但是如果将人数扩大到 11 人，最少需要 6 人才能打开箱子，那么锁和钥匙数就会扩大到 462 和 252。抽象成 N 个人，锁的数量为 C(N,N/2)，钥匙数量为 C(N-1,N/2)。随着人数增加，锁和钥匙的数量将会呈现指数级增加，这也会大大增加资源的负担。
我们将某个现实中的问题抽象成为某个数据 D 。我们的目标是将 D 分成 n 份 D1 , D2 , … Dn ，满足：
（1）任意k或多于 k 份 Di 可以很容易地计算出 D
（2）任意 k-1 或少于 k-1 份 Di 信息不能准确计算出 D （所有可能的值相同）
这样的机制称为一个 (k, n) 门限机制。
拉格朗日插值法
插值的意义在于拟合，以便求出缺失的点
这里直接给出结论，具体的介绍会另开一篇文章来讲，同时也会介绍各种插值法。
对于某个多项式函数，已知给定的 j+1 个取值点，即 (x0 , f(x0)), … , (xj , f(xj))
假设任意两个不同的 xk 都互不相同，那么这个多项式就为：
其中每个 lj(x) 为拉格朗日基本多项式（或者称之为插值基函数），其表达式为：
Shamir 门限方案
首先，我们知道在在一个平面中，两点可以确定一条直线，三个点可以确定一个 2 次方程，于是我们可以推出给定 K 个不同的点，有且仅有 K-1 次多项式 q(x) 使得 q(xi) = yi 对所有 i 成立。于是我们可以如前文所说的那样：将 D 分成 Di ，随机选择一个 k-1 次多项式：
其中 a0 = D 且 D1 = q(1)，D2 = q(2)，… ，Dn = q(n) 。于是，当我们给定任意 Di 值的 k 个子集时，就可以通过插值法找到 q(x) 的系数，然后计算出 D = q(0)。
这种 (k,n) 门限机制的优点在于：
- 每部分信息的大小不会超过原始数据
- 当 k 这个数值固定时，Di 可以动态的增删而不会影响别的信息片段
- 可以在不改变原始数据 D 的情况下轻松的改变 Di 这些信息片段，我们只需要保证这些片段最终可以组成一个恒定的自由项的多项式就可以了。同时这样可变的性质能够提高安全性。
- 我们也可以利用多项式的系数做一个分层的机制，Di 的片数取决于其重要性。例如，如果我们给公司的主席 3 个 q(x) 的值，每个副主席两个值，每个执行官 1 个值，则（3，n）门限机制给检查签名需要：任意三个执行官或者任意两个执行官其中一个执行官是副主席，或者主席自己。