门限共享秘密算法与代码实战丨区块链技术课程 #6

作者丨Seek

密码学的发展可以追溯到公元前 400 年前，人类使用密码学的历史几乎和文字的历史一样长。

公元前 400 年前，斯巴达人发明了 “塞塔式密码“。在中国古代，也出现过密码学的影子的，中国古代的藏头诗大家应该都知道，这也属于密码学的使用范畴。

在密码学的发展过程中，战争起到了很大的作用，从古至今，军方使用的技术都是世界上最先进的，包括密码学也一样。

密码学体系在当今时代已经是一个完善的学科体系，全世界有很多专家学者终其一生为密码学的发展添砖加瓦。

我们现在所熟知的 对称密码，非对称密码，数字签名，单项散列函数，PKI 体系，共享密码 等都可以是一个值得深入研究的方向。

本文将带领大家去 理解共享秘密相关的一些技术 ，希望大家从中能学到一些共享密码的知识。

作者丨Seek

共享密钥的发展历程

秘密的共享 是信息安全研究的一个重要的分支，密码主要是为了对重要信息进行加密，保证信息的安全新，而秘密共享却可以保证密钥的安全性，它为密码学的发展提供了一个崭新的思路。

秘密共享的原理 是将秘密分成若干份，交给不同的人去保管，设定管理秘密的一定数量的人贡献出自己持有的秘密，就可以恢复秘密了。

1.1 秘密共享的产生

秘密共享的概念最早 由著名密码学家 Shamir 和 Blakley 于 1979 年分别独立提出并给出了各自的方案。

Shamir 的( t，n) 门限方案基于 Lagrnage ( 拉格朗日) 插值法来实现，Blakley 的( t，n) 门限方案是利用多维空间点的性质来建立的。

秘密共享的概念一经提出，受到专家学者们的极大的关注与研究。这些年取得的成果颇丰。大致可以分为如下几类。

1.2 门限秘密共享方案

在( t，n) 门限秘密共享方案中，任何包含至 少 t 个参与者的集合都是授权子集，而包含 t-1 或更少参与者的集合都是非授权子集，实现( t， n) 门限秘密共享的方法除了 Shamir 和 Blakley 的方案外，还有基于中国剩余定理的 Asmuth-Bloom 法以及使用矩阵乘法的 Karnin-Greene Hellman 方法等。

1.2.1.一般访问结构上秘密共享方案

门限方案是实现门限访问结构的秘密共享方案，对于其它更广泛的访问结构存在局限性， 如在 甲 、乙 、丙 、丁 四 个成员中共享秘 密 ，使甲和丁或乙和丙合作能恢复秘密，门限秘密共享方案就不能解决这样的情况. 针对这类问题，1987 年密码学研究人士提出了一般访问结构上的秘密共享方案。1988 年有人又提出了一个更简单有效的方法—单调电路构造法，并且证明了任何访问结构都能够通过完备的秘密共享方案加以实现。

1.2.2 多重秘密共享方案

只需保护一个子秘密就可以实现多个秘密的共享，在多重秘密共享方案中每个参与者的子秘密可以使用多次，但是一次秘密共享过程只能共享一个秘密。

1.2.3.多秘密共享方案

多重秘密共享解决了参与者的子秘密重用 的问题，但其在一次秘密共享过程中只能共享一个秘密。

1.2.4.可验证秘密共享方案

参与秘密共享的成员可以通过公开变量验证自己所拥有的子秘密的正确性，从而有效地防止了分发者与参与者，以及参与者之间的相互欺骗的问题。可验证秘密共享方案分为交互式和非交互式两种。交互式可验证的秘密共享方案是指各个参与者在验证秘密份额的正确性时需要相互之间交换信息；非交互式可验证的秘密共享是指各个参与者在验证秘密份额的正确性时不需要相互之间交换信息。在应用方面，非交互式可验证秘密共享可以减少网络通信费用，降低秘密泄漏的机会，因此应用领域也更加广泛。

1.2.5.动态秘密共享方案

动态秘密共享方案是 1990 年提出，它具有很好的安全性与灵活性，它允许新增或删除参与者、定期或不定期更新参与者的子秘密以及在不同的时间恢复不同的秘密等等. 以上是几种经典的秘密共享方案. 需要说明的是，一个具体的秘密共享方案往往是几个类型的集合体。

1.2.6. 其他秘密共享

量子秘密共享、可视秘密共享、 基于多分辨滤波的秘密共享、基于广义自缩序列的秘密共享。

经典秘密共享方案介绍

2.1 shamir 门限秘密共享方案

Shamir 的( t，n) 门限方案基于 Lagrnage ( 拉格朗日) 插值法来实现，简单地说， 设秘密通过秘密共享算法分发给个成员共享，每一个成员持有一个子密钥也称为 shadow 或 Secret debris，如果满足:

• 任何不少于 t 个的有效成员使用他持有的正确的碎片都可以恢复秘密。

• 任何 t 个以下的成员集都无法恢复秘密。

我们称这种方案为 (t ,n) 门限秘密共享方案，简称为门限方案，t 称为方案的门限值。

作为各种秘密共享方案中最简单实用的门限秘密共享方案， (k,n) 门限秘密共享方案也是这些方案中最具有代表性和广泛应用的方案。

下面简单介绍一下这个方案。

2.1.1.系统参数

假定 n 是参与者的数目，n 是门限值，p 是一个大素数要求 p > n 并且大于 p 秘密 s 的可能的最大取值;秘密空间与份额空间均为有限域 GF(p)。

2.1.2. 秘密分发

秘密分发者 D 给 n 个参与者 Pi(0 ≤ i ≤ n) 分配份额的过程，即方案的分配算法如下:

• 随机选择一个 GF(p) 上的 k - 1 次多项式 使得 f(0) = a0 = s要在个参与者中分享的秘密 D 对 f(x) 保密。

• D 在 Zp 中选择 n 个互不相同的非零元素 x1, x2, …, xn，计算 (0≤ i ≤ n)。

• 将 ( xi , yi ) 分配给参与者 Pi( 0 ≤ i ≤ n)，值 xi 是公开的，yi 作为的秘密份额，不公开。

  2.1.3. 秘密重构

给定任何 t 个点,不妨设为前 t 个点（x1， y1），(x2, y2)，…, (xt, yt)。由插值公式：

2.1.3. Shamir 方案优缺点

Shamir 方案作为一种被广泛选用的门限方案，具有以下优点：

• t 个秘密份额可以确定出整个多项式，并可计算出其他的秘密份额。

• 在原有分享者的秘密份额保持不变的情况下，可以增加新的分享者，只要增加后分享者的总数不超过。

• 还可以在原有共享密钥未暴露之前，通过构造常数项仍为共享密钥的具有新系数的次多项式，重新计算新一轮分享者的秘密份额，从而使得分享者原有的秘密份额作废。

  但同时方案存在以下问题：

• 在秘密分发阶段，不诚实的秘密分发者可分发无效的秘密份额给参与者

• 在秘密重构阶段，某些参与者可能提交无效的秘密份额使得无法恢复正确秘。

• 秘密分发者与参与者之间需点对点安全通道。

  2.2 基于中国剩余定理的秘密共享方案

中国剩余定理最早出现在我国古代数学名著 《孙子算经》 中，因而又被称为 孙子定理 ，中国剩余定理在密码学中被广泛的使用。

令 p1, p2,...,pm 表示 m 个两两互素的正整数。给定任意 m 个整数，k1,k2,k3,...,km，存在唯一的一个整数 K 属于 GF(p1p2 ..., pm)满足：

K = K1 mod p1
K = K2 mod P2
......
K = Km mod Pm

1983 年，密码学专家提出两一种基于中国剩余定理的秘密共享方案，整体思路如下。

2.2.1. 初始化阶段

设 P = {p1, p2, ... , Pn} 为参与者的集合。{p, d1, d2, ... dn} 是一组满足下列条件的整数。

• s < p, s 是需要共享的密明。

• d1 < d2 < ... dn。

• 对i = 1,2, ... , n, 有 gcd(di, p) = 1，其中 gcd(x, y) 表示 x 和 y 的最大公约数。

• 对于所有 i 不等于 j，有 gcd(di, dj) = 1。

• d1d2...dk > pdn-t+2dn-k+3 ... dn。

其中第 5 条意味着最小的 k 个 di 的乘积要大于 p 和 k—1 个最大的di之积。

2.2.2. 密明分发阶段

令 N = d1d2...dt，则 N/p 大于任意的 k-1 个 di 之积。令 r 是 [0, N/p-1] 中一个随机数。为了将密明 s 分割为 n 份，密朗分发者 D 计算 s' = s + rp，这里将 s' 限制在 [0, N - 1] 中，则每个参与者 Pi 的子密钥 xi 为：

xi = s' mod (di)

2.2.3. 密钥重构阶段

任意 k 个参与者，不妨假设为 P1, P2, ... Pk 拿出他们的 k 个子密钥 x1, x2, ... xk，由中国剩余定理可得到对应的模：

N1 = d1d2 ... dk

因为 N1 大于等于 N，可由中国剩余定理唯一的确定 s'。而后可由 s', r, p 计算出密钥：

s = s' - rp

如果仅仅知道 k-1 个子密朗，虽然由N2可知s'，

N2 = d1d2 ... dk-1

但由于 N/N2 > p，且gcd(N2, p) = 1，所以使 x 大于等于 N 和 x=s'mod(p) 的数 x 在模 p 下的同余类上均匀分布，因此没有足够的信息决定s'。在该方案中，密钢恢复算法的时间复杂度为O(k)，空间复杂度为O(n)。

可验证秘密共享

通常的密钥共享方案，都假设密钥分发者是诚实的。

这会导致基本密钥共享中存在一个主要的安全问题： 不能防止密钥分发者的欺骗，即分发者在分发子密钥时可能会给一个或者多个参与者分发伪造的子密钥。

为了解决这个问题， Chor 等人提出了可验证密钥共享的概念。

可验证密钥共享就是 把一个普通的密明共享方案附加上一个允许参与者认证他们收到的子密钥的交互式算法，参与者可通过认证算法检验自己的子密明是否有效。

可验证密钥共享可以分为 条件安全可验证密明共享和无条件安全可验证密钥共享 两大类。

下面我们介绍几个比较有代表性可验证秘密共享方案。

3.1 Feldman 的方案

Feldman 在 Shamir 的密钥共享方案基础上提出了一种可验证的密朗共享方案。下面我们介绍一下这个算法的详细过程：

3.1.1. 初始化阶段

设 p 是一个大素数，q 为 p -1 的一个大素数因子，g 属于 Z*p 且为 q 阶元素，三元组 (p, q, g) 是公幵的，k 是门限值，n 是参与者的数目，s 为要共享的密钥。

3.1.2. 子密明分发阶段

密朗分发者（dealer）选取一个 k-1 次的随机多项式 f(x) 属于 Zq(x)，并使得 f(0) = s。即在 Zq 任意选取个随机数 a1, a2, ..., ak-1，构造多项式

随后，计算并密销发送子密钥 mi = f(i) mod (q) 给参与者 Pi，并且广播验证信息。

3.1.3. 验证阶段

参与者Pi（i = 1, 2, ..., n）在收到子密钥之后，可通过检查等式

是否成立来验证子密朗的正确性。若等式成立相等则说明参与者Pi拥有的子密明是正确的，否则说明收到的子密销是不正确的。

3.1.4. 密明恢复阶段

当 k 个参与者，不妨假设为 P1, P2, ..., Pn 合作恢复密朗时，每一个参与者 Pi 都要公开他的子密钥份额 mi。此时任何一个参与者都可以通过验证上述等式来验证其他参与者的子密钥的正确性。若经检验，所有公开的子密朗都是正确的，那么密钥可以由拉格朗日插值函数来恢复。

可以看到，在 Feldman 的方案中，验证子密朗的正确性的关键是密钥分发者公布了验证信息 aj = gaj mod p，j = 1, 2, 3, ..., k。其中 g 与 p 是公幵的，验证信息 aj 是 aj 的离散对数。基于离散对数问题的困难性，由验证信息 aj 和 (g, p) 无法计算出。由此可见，Feldman 的方案的安全性是建立在离散对数问题的困难性基础上的，所以它是条件安全的。另外，从密钥恢复的阶段我们还可以看到，当参与者公开自己的子密钥后，所有的参与者都能够利用密钥分发阶段的信息来验证其他参与者的子密钢的正确性，这实际上是解决了参与者在密朗恢复过程中的欺骗问题。

3.2 Benaloh 方案

Benaloh 的可验证密明共享方案也是建立在 Shamir 的密朗共享方案基础上的。与 Feldman 的方案不同， Benaloh 的方案是无条件安全的 。

首先我们介绍一下 Benaloh 的可验算法的主要思路。在的密钥共享方案中，所有的参与者的子密明都是来自一个 k - 1 次的线性多项式，如果密钥分发者分发出一个或者多个错误的子密钥，那么这些 n 个子密钥必然会不一致，它们的插值多项式的次数在很大的概率上会大于 k -1。

换句话说，如果我们能过在不泄露子密钥信息的前提下得出这些子密明的插值多项式的次数，那么就可以验证出子密朗的有效性。

Benaloh 的方案正是利用这一性质对 Shamir 的密钥共享方案进行了验证，具体的算法如下：

3.2.1. 初始化阶段

设 q 是一个大素数，s 属于 Zq 是将要分享的密钥。k 是门限值，n 是参与者的数目。

3.2.2. 子密钥分发阶段

密钥分发者 (dealer) 选取一个 k -1 次的随机多项式 f(x) = Zq(x)，并使得 f(0) = s。随后，计算并密明发送子密钥mi = f(i) mod (q)给参与者 Pi。

接下来密钥分发者又随机选择多个 (不妨假设为 100) Zq(x) 上的 k-1 次多项式，f1(x), f2(x), ..., f100(x)。并且为每一位参与者 Pi 计算并且发送 100 个验证子密钥mij（mij 表示 mi 的 j 次方），j = 1, 2, … 100，其中。mij = fj(i)。

3.2.3. 验证阶段

所有参与者合作随机选取 50 组（一组包含 n 个）验证子密钥，将其公开后分别验证这 50 组验证子密朗是否都是出自 k-1 次的多项式。由于这 50 组验证子密钥是由参与者随机选取，如果它们全都源于 k-1 次的多项式，那么参与者可以认为剩下的 50 组未公开的子密钥也都来源于是 k-1 次的多项式。

接下来，所有参与者将子密朗与剩下的任意一个未公开的验证子密钥的和公开，并且验证这 n 个值是否来源于 k-1 次的多项式。如果是，那么根据插值多项式的线性性质可以推断出这个 n 子密明也是来源于一个 k-1 次的多项式。从而验证出子密钥的有效性。反之，这个子密明是不一致的，密朗分发者在计算和分发子密朗的过程中出错。

3.2.4. 密钥恢复阶段

当子密钥的有效性被验证过后，任意 k 个参与者利用拉格朗日插值公式可以将密钥恢复出来。

由以上的算法我们可以看到，在 Benaloh 的方案中，密钥分发者没有公布任何验证信息，而整个验证算法也没有依靠任何困难问题假设，所以 Benaloh 的可验证密钥共享方案是无条件安全的。但是，每个参与者为了要验证子密钥的有效性，他们要存储 100 个验证子密钥，这就对每个参与者的存储空间提出了很高的要求。另外，从验证的效果上来分析，Benaloh 的方案只能够验证出是否存在错误的子密朗，却无法判断哪一个子密钥是错误的。相对于 Feldman 的方案，该方案在验证的效果上是要弱一些，并且参与者需要更大的存储空间，这会引起一定程度的安全问题。不过这也是达到无条件安全所必须要付出的代价。

去中心化秘密共享方案

自从密钥共享方案诞生以来，大量的不同环境下的密钥共享方案己经被提了出来。大部分的方案中都假设存在一个可信中心密钥分发者，负责将密钥分割成为子密钥，并且安全密钥的将子密钢发送给参与者。但是在实际环境中，可信中心往往是不存在的。所以 一种新的无可信中心的密钥共享协议被提了出来以适应没有可信中心的环境。

在无可信中心的密钥共享中，子密钥的产生和分配都是由参与者本身合作完成的。在实际应用中，有可信中心的密钥共享可能存在可信中心的“权威欺骗”，并且在现实中需要成员具有较高的可信度也不是明智的假设。因此，和有可信中心的密钥共享相比， 无可信中心的密钥共享安全性更高，实用性更强。

对无可信中心密钥共享研究的主要目的就是： 寻找合适的方案来保证信息能够安全，有效地发布和传输。 此外， 无可信中心密明共享中的子密钥如何分发，是人们研究的热点问题， 其发展空间还很大。因此，无可信中心密钥共享不仅存在着重要的理论价值，更在实际应用中存在着广泛的应用前景。目前对于无可信中心的密钥共享的应用主要集中在数字签名方面。对无可信中心的密钥共享的加密研究并不多。

下面是笔者个人提出的一种去中心化秘密共享方案。

去中心的化密钥共享方案实际上就是把密钥拆分成 n 份之后，对每一份秘密进行加密，然后将他们存储到区块链上去，这样可以解决密钥的分发存储。密钥发送到相应的节点后，该节点先对密钥做二次加密，签名，然后写到区块链上，当密钥恢复者需要恢复密钥时，它可以全网广播一条恢复密钥的信息，然后付给密钥段存储节点一定的 token，密钥存储节点验证密钥并解密之后发送给恢复密钥的客户端。这样就可以达到去中心的秘密共享的目标。

4.1 (t，n）门限的动态秘密共享方案

1979 年 Shamir 和 Blakley 分别提出了一个（t，n）门限秘密共享方案，Shamir 的（t，n）门限方案是基于 Lagrange（拉格朗日）插值法来实现的，它通过构造一个 t-1 次多项式，并将需要共享的秘密作为该多项式的常数项，每个份额（子秘密）为满足该多项式的一个坐标点，由 Lagrange 插值定理可知，任意 t 个份额（子秘密）可以重构该多项式从而恢复秘密，而 t-1 个或更少的份额（子秘密）不能重构该多项式，因而得不到关于秘密的任何信息。

动态秘密共享体制的提出主要源于秘密共享方案的安全性问题。在（t，n）门限秘密共享方案中，方案的安全性是建立在攻击者不可能在秘密的生命周期内获取 t 个子秘密的前提之下的。然而实际上很难保证这一点，尤其是在秘密的生命周期较长的情况下，这一点就更难以保证。可验证秘密共享方案主要用来解决传统秘密共享方案中存在的分发者不诚实性问题和子秘密持有者的不诚实性问题，而面对敌手的破坏性攻击，可验证秘密共享方案并没有更好的安全性。

当然，对于周期上的安全性，可以通过不断更换秘密的办法得到解决，但是更换秘密并不总是可行的（比如说该秘密是一个重要文件或是一些军事、商业秘密等）。动态秘密共享方案通过在不改变秘密的情况下解决了秘密共享方案在周期上的安全性问题。动态秘密共享方案在保证秘密不变的情况下周期性地更换子秘密，从而使得每次更换子秘密时攻击者在前一个周期内所获得的信息完全失效。

这样一来，就可以根据可能受攻击程度的不同来相应地决定子秘密更换周期的长短，以保证在每一个周期内秘密的安全性。动态秘密共享还要保证过期的子秘密所包含的信息不会对未来秘密的构造产生不安全的影响。

4.2 Amir Herzberg 方案

有关动态秘密共享的方案已有不少，Amir Herzberg 提出的方案是很经典的一个，方案是对 Shamir 的秘密共享方案实现动态化。

分发者 D 选择一个有限域 GF(q)（q 为大素数），为了方便说明，用 i 代替 Shamir 方案中的 xi的。在第 k 个时段，Pi 持有的子秘密用 si(k)(si 的 k 次方) 表示。

子秘密更新协议：每个时段开始时要进行子秘密更新，进入第 k 时段后，Pi 持有的子秘密要从 si(k-1) =f(k-1)（i）更新至 si(k) ，其中 f(k-1) (0) = s。整个过程如下：

更新后的子秘密显然符合门限秘密共享的要求，任意大于或等于 t 个参与者利用 Lagrange 插值法可恢复秘密。之后 Amir Herzberg 等人在他们的这篇文章中进一步提出了一个防止主动攻击的子秘密更新方案，并增加了可验证性，进一步加强了方案的安全性。

4.3 Amir Herzberg 方案的改进

事实上 Amir Herzberg 的子秘密更新方案相当于 n 个参与者协商了一个常数项为零的 t-1 次多项式，事实上少于 n 个参与者也可以进行子秘密更新，步骤和原方案相同，如果参与子秘密更新的参与者少于门限值 t 时，可以对此方案进行改进，使它具有更好的灵活性和执行效率，方案描述如下：

4.3.1. Amir Herzberg 方案的改进分析

这样 k（k<t）个参与者就实现了子秘密的更新，并且这个方案有很大的灵活性，在上面步骤中，只需对 si′="si+χ·i" ic="" 中="" i="" 的次数进行修改，使次数大于="" t-k="" 就可以提高门限值，如="" t+θ，这相当于把储存秘密="" s="" 的多项式变为="" t+θ-1="" 次多项式。由于参与子秘密更新的成员只需选择一随机数，并进行简单的直和分解运算，与原方案相比执行效率很高。由于传递信息是通过安全信道，安全性可以得到保证。amir="" herzberg="" 的子秘密更新方案相当于="" n="" 个参与者协商了一个常数项为零的="" t-1="" 次多项式，给出参与子秘密更新的参与者少于门限值="" t="" 也可以进行子秘密更新，并具有更好的灵活性和执行效率。进一步考虑，对于参与子秘密更新的人数大于或等于门限值时，即="" k≥t="" 时，此方案仍可以更新子秘密，但是门限值却会发生变化，不太适合需要保持门限值不变的场合，没有="" k<t="" 时方案更加灵活。

**实现代码库

🔗 Java 版本：

https://github.com/guoshijiang/beeKey_java

🔗 Node 版本:

https://github.com/eniac-x-labs/dapplink-secret