从 ElGamal 到门限秘密共享：一篇看懂分布式解密、DKG 与门限签名的教程

把一把私钥交给单个人保管很方便，但也很脆弱：私钥一旦泄露，攻击者就能解密全部历史密文；保管者离线或丢失密钥，合法用户同样无法恢复数据。

门限密码学给出的思路是：不让任何一个人持有完整私钥。私钥被拆成多个份额，只有达到门限的一组参与者协作，才能完成解密或签名。本文从 ElGamal 出发，系统梳理这条主线：

ElGamal 为什么可以“分布式解密”；
Shamir $(t,n)$ 门限秘密共享怎样拆分和恢复秘密；
如何把“恢复秘密”改造成“不暴露秘密的联合解密”；
DKG、主动份额更新为什么能减少单点风险和长期泄露风险；
门限签名、特殊份额、加权份额、可变阈值分别解决什么问题。

先建立整体图景 #

设系统私钥为 $x$，公钥为 $Y$。传统公钥密码体制中，一个人保存 $x$；门限体制中，$x$ 被共享为 $x_1,\ldots,x_n$。系统仍然只公布一个公钥 $Y$，对外的加密方式不变；区别只在于解密时，参与者各自计算一份部分解密，聚合者把足够多的部分解密合成为明文。

因此，门限方案不是“把密文切成几块”，而是“把私钥的控制权切成几块”。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
加密者：使用系统公钥 Y 加密
                 │
                 ▼
          密文 (C1, C2)
                 │
      ┌──────────┼──────────┐
      ▼          ▼          ▼
     P1         P2         Pn
   持有 x1     持有 x2     持有 xn
      │          │          │
   部分解密   部分解密   部分解密
      └──── 足够 t 份 ────┘
                 ▼
             聚合者恢复 m

下面先看“原始 ElGamal 私钥究竟做了什么”，再把这个动作分配给多人。

1. ElGamal：加密和解密到底在抵消什么？ #

1.1 密钥生成 #

在模素数 $p$ 的乘法群中选生成元 $g$，私钥是随机指数 $x$，公钥为：

$$ Y=g^x\pmod p. $$

公开 $(p,g,Y)$，只保留 $x$。这里的“生成元”是指不断计算 $g,g^2,g^3,\ldots$ 能产生群内元素的基；“离散对数问题”则是指已知 $g$ 和 $g^x$，在合适的大群中很难反推出指数 $x$。这正是 ElGamal 把 $x$ 当私钥的安全基础。

1.2 加密与解密 #

要加密消息 $m$，加密者随机选择一次性随机数 $r$：

$$ C_1=g^r\pmod p,\qquad C_2=Y^r\cdot m\pmod p. $$

密文为 $C=(C_1,C_2)$。解密者计算：

$$ \begin{aligned} m&=C_2\cdot C_1^{-x}\pmod p\\ &=(Y^r\cdot m)\cdot(g^r)^{-x}\\ &=(g^{xr}\cdot m)\cdot g^{-rx}=m\pmod p. \end{aligned} $$

关键点只有一个：$C_1^x=g^{rx}$ 正好是 $C_2$ 中的“掩码”。谁能得到 $C_1^x$，谁就能去掉掩码。 门限解密要做的就是让多人共同得到 $C_1^x$，但没有任何单人知道 $x$。

1.3 一个作业式的手算例子 #

取：

$$ p=2027,\quad g=1002,\quad x=90,\quad r=411,\quad m=888. $$

可计算得到：

$$ Y=g^x\bmod p=30, $$$$ C_1=g^r\bmod p=1514,\qquad C_2=Y^r\cdot m\bmod p=235. $$

所以密文为 $C=(1514,235)$。解密时不是计算 $C_1^{-x}$ 的小数倒数，而是在模 $p$ 的乘法群中求逆：

$$ m=C_2\cdot C_1^{-90}\pmod{2027}=888. $$

这里的上标 $-x$ 很重要：它表示“先求 $C_1^x$，再求其模逆元”，并不是把 $C_1$ 写成普通文本后在旁边减去 $x$。

工程提示：真实系统会使用远大于 2027 的安全参数；通常还会在大素数阶子群中运算。上面的数值只用于说明计算过程，不能用于真实安全场景。

2. Shamir 秘密共享：把秘密藏在多项式常数项里 #

2.1 $(t,n)$ 门限的含义 #

$(t,n)$ 方案把秘密分给 $n$ 人，任意不少于 $t$ 人可以恢复秘密；少于 $t$ 人则得不到关于秘密的有效信息。最常用的构造是 Shamir 秘密共享。

在有限域 $\mathbb{F}_q$ 中，秘密为 $s$。“有限域”可以先简单理解为：所有加、减、乘、除（除以 0 以外）都在模 $q$ 意义下进行，且结果仍落在同一个有限集合里。随机选择一个 $t-1$ 次多项式：

$$ f(z)=s+a_1z+a_2z^2+\cdots+a_{t-1}z^{t-1}\pmod q. $$

其中随机系数 $a_1,\ldots,a_{t-1}$ 决定了多项式的其他形状，而常数项固定为 $f(0)=s$。把第 $i$ 个份额定义为 $s_i=f(i)$。由于一个 $t-1$ 次多项式由 $t$ 个不同点唯一确定，任意 $t$ 个参与者可以插值得到 $f(0)$；但少于 $t$ 个点时，仍然有多个多项式可能经过这些点，常数项不确定。

2.2 $(4,7)$ 的可计算例子 #

为了共享 ElGamal 私钥 $x=90$，取 $q=1013$，构造：

$$ f(z)=90+z+z^2+z^3\pmod{1013}. $$

于是 7 个份额为：

$$ (x_1,x_2,x_3,x_4,x_5,x_6,x_7)=(93,104,129,174,245,348,489). $$

例如选取 $P_1,P_2,P_3,P_4$。“拉格朗日插值”是利用若干已知点还原唯一多项式的方法；其中的 $\lambda_i$ 是把各个份额加权组合回常数项 $f(0)$ 的系数。在 $z=0$ 处，它们为：

$$ (\lambda_1,\lambda_2,\lambda_3,\lambda_4)=(4,-6,4,-1). $$

因此：

$$ \begin{aligned} x&=\sum_{i=1}^4\lambda_i x_i\\ &=4\times93-6\times104+4\times129-174=90\pmod{1013}. \end{aligned} $$

这解释了门限恢复，但直接让大家把 $x_i$ 发给聚合者并不理想：聚合者会恢复出完整私钥 $x$。下一节把插值“搬到指数上”，避免泄露 $x$。

3. 门限 ElGamal 解密：恢复 $C_1^x$，而不是恢复 $x$ #

每个参与者 $P_i$ 用自己的份额计算部分解密。“部分解密”是不能单独还原明文、但可与其他部分解密组合的群元素：

$$ D_i=C_1^{x_i}\pmod p. $$

聚合者不需要知道任何 $x_i$，只需要收集至少 $t$ 个 $D_i$，并使用同一组拉格朗日系数：

$$ \begin{aligned} D&=\prod_{i\in S}D_i^{\lambda_i}\pmod p\\ &=\prod_{i\in S}\left(C_1^{x_i}\right)^{\lambda_i}\\ &=C_1^{\sum_{i\in S}\lambda_i x_i}=C_1^x\pmod p. \end{aligned} $$

最后：

$$ m=C_2\cdot D^{-1}\pmod p. $$

对上面的 $(4,7)$ 例子，前四个用户的部分解密可聚合为 $D=838$，从而恢复 $m=888$。即使聚合者收到了 $D_i$，它得到的也是这一次密文对应的 $C_1^x$，而不是某个用户的私钥份额。

一个容易忽略的严格条件 #

Shamir 份额的运算域阶 $q$ 与 ElGamal 指数所在群的阶必须匹配。“子群”是大群中自身仍满足群运算规则的一个较小集合；实践中通常选择 $q\mid(p-1)$ 的素数阶子群，并让公开基 $h$ 的阶为 $q$，然后使用 $h^x$ 而不是任意整个群生成元的指数。这样“在模 $q$ 下恢复指数”与群中的指数计算完全一致。

教学手算中，如果插值恰好恢复的是整数 $x=90$，常常看不出这个问题；在真实方案中，忽略它会导致正确性或安全性问题。

4. DKG：不让中心生成或看见完整私钥 #

“中心化分发”很简单：可信中心先选 $f(z)$，再私下把 $f(i)$ 发给用户。但中心在一开始见过 $x=f(0)$，它仍然是单点风险。

分布式密钥生成（Distributed Key Generation，DKG）就是“多方共同生成一把密钥”的协议：每个用户各自贡献一部分秘密，最终得到共同公钥，但没有人从头到尾见过完整私钥。第 $j$ 个用户选择：

$$ f_j(z)=a_{j0}+a_{j1}z+\cdots+a_{j,t-1}z^{t-1}. $$

它将 $f_j(i)$ 私下发送给用户 $P_i$。用户 $P_i$ 的最终份额是：

$$ x_i=\sum_{j=1}^{n}f_j(i). $$

等价的总多项式为：

$$ F(z)=\sum_{j=1}^{n}f_j(z),\qquad x=F(0)=\sum_{j=1}^{n}a_{j0}. $$

公钥贡献可写为 $Y_j=h^{a_{j0}}$，系统公钥为：

$$ Y=\prod_{j=1}^{n}Y_j=h^{\sum_j a_{j0}}=h^x. $$

没有任何一个用户主动选择了完整 $x$，也不应该知道它。实际 DKG 还必须加入可验证秘密共享（VSS）承诺：否则恶意用户可以给不同接收者发送彼此不一致的份额，破坏后续解密或签名。

Pedersen VSS 的直观作用 #

Pedersen VSS 会让分发者公开多项式系数的“承诺”。承诺可以理解成一个不可随意篡改的密封标签：它不泄露系数本身，但接收者能据此验证“我收到的份额确实来自同一个多项式”。它解决的不是“如何保密”，而是“如何在不信任分发者时仍能检查正确性”。

5. 主动份额更新：防止攻击者跨时间收集份额 #

即使每一时刻攻击者都拿不到 $t$ 份份额，长期攻击者也可能先后入侵不同用户，慢慢收集到足够多的旧份额。这就是长期密钥的“积累泄露”风险。

最直接的办法是完全重新分发：重新生成一个常数项仍为 $x$ 的新多项式，并安全发送全部份额。它有效，但通信开销大。

更优雅的方法是给原多项式加一个常数项为零的随机多项式：

$$ h(z)=b_1z+b_2z^2+\cdots+b_{t-1}z^{t-1},\qquad h(0)=0. $$

令 $f’(z)=f(z)+h(z)$，则：

$$ f'(0)=f(0)+h(0)=x. $$

因此系统私钥 $x$ 和公钥 $Y$ 不变，但每个用户的份额变为：

$$ x_i'=x_i+h(i)\pmod q. $$

例如在上一节的多项式上取：

$$ h(z)=2z+3z^2+4z^3\pmod{1013}. $$

更新后得到：

$$ f'(z)=90+3z+4z^2+5z^3\pmod{1013}. $$

核心结论：新旧份额不能混用。每轮更新都要有 epoch（轮次）标识；epoch 就是“这是第几代份额”的版本号。旧份额必须安全删除，否则攻击者仍可把不同时期的份额拼在一起。

6. 门限签名：把“联合解密”变成“联合授权” #

DKG 与份额更新并不限于解密。它们同样可用于门限签名：系统的公钥 $Y$ 对外验证签名，而任何不少于 $t$ 个参与者共同产生一个签名。

以 Schnorr/FROST 类型签名为例，签名参与者集合为 $S$。Schnorr 是一种基于离散对数的签名体制；FROST 是其高效门限化实现，设计目标是让多人的签名份额聚合为一份普通大小、可由系统公钥验证的签名：

每个 $P_i$ 选择一次性随机数 $k_i$，发出承诺 $R_i=h^{k_i}$；
聚合者计算 $R=\prod_{i\in S}R_i$ 和挑战 $e=H(M\mathbin{|}R)$；
每个参与者返回签名份额：

$$ z_i=k_i+e\lambda_i x_i\pmod q; $$

聚合者计算 $z=\sum_{i\in S}z_i\pmod q$，输出 $\sigma=(R,z)$；
验证者检查：

$$ h^z\stackrel{?}{=}R\cdot Y^e\pmod p. $$

因为 $\sum_i\lambda_i x_i=x$，验证等式成立。

一个很小的验证例子 #

取 $p=23,q=11,h=4,x=3$，则 $Y=4^3\bmod23=18$。使用 $f(z)=3+2z\pmod{11}$ 做 $(2,3)$ 分享，份额为 $(5,7,9)$。令 $P_1,P_2$ 签名，它们的拉格朗日系数是：

$$ \lambda_1=2,\qquad\lambda_2=10. $$

若 $k_1=1,k_2=2,e=4$，则：

$$ R=4^1\cdot4^2\bmod23=18, $$$$ z_1=1+4\cdot2\cdot5\equiv8\pmod{11},\qquad z_2=2+4\cdot10\cdot7\equiv7\pmod{11}. $$

所以 $z=4$。验证：

$$ 4^4\bmod23=3,\qquad18\cdot18^4\bmod23=3. $$

两边相等，签名通过。

FROST 的工程实现比这个教学式过程更严格：必须使用两轮随机数承诺和绑定因子，并且绝不能复用 $k_i$。复用签名随机数会泄露私钥份额。

7. 不只是“任意 t 人”：特殊份额与加权份额 #

7.1 必须包含某位特殊参与者 #

有时访问策略不是“任意 $t$ 人”，而是“董事长必须在场，且再加至少 $r$ 名普通成员”。可以把秘密拆为：

$$ x=u+v\pmod q. $$

把 $u$ 只交给特殊用户 $P_$，把 $v$ 用 $(r,n-1)$ Shamir 方案分给普通用户。只有 $P_$ 和至少 $r$ 名普通用户同时参与，才可得到：

$$ C_1^u\cdot C_1^v=C_1^{u+v}=C_1^x. $$

例如 $x=90,u=30,v=60$，并把 $v$ 做 $(3,6)$ 分享。没有 $P_*$ 时，即使普通用户重构了 60，也无法得到完整指数 90。

7.2 给参与者不同权重 #

若 A、B、C、D 的权重分别为 $3,2,1,1$，总门限为 $W=4$，则 A+C 可以授权，B+C+D 也可以授权，而 C+D 不可以。

一个直观实现是把权重 $w_i$ 视为 $w_i$ 个虚拟份额，再运行 $(W,\sum_iw_i)$ Shamir 共享。更一般的复杂访问策略，则应使用线性秘密共享方案（LSSS）。LSSS 的意思是“把秘密编码为若干线性份额”：满足策略的一组用户能用线性组合恢复秘密，不满足策略的用户则不能；它可以表达“AND、OR、加权门限、指定角色必须出现”等单调访问结构。

8. 可变阈值：不能只在解密时改一个数字 #

一批固定的 $(t,n)$ Shamir 份额不可能在不改变份额的前提下，同时具有多个门限。安全等级变化时，需要执行重分享；它指的是由当前合法用户协作生成一批新份额，使新份额仍对应同一秘密、但多项式次数和门限已经改变。

设当前合法集合为 $S$，旧份额为 $x_i$，旧门限下的拉格朗日系数为 $\lambda_i$。每个 $P_i$ 构造一个新多项式 $q_i(z)$，使其常数项为：

$$ q_i(0)=\lambda_i x_i, $$

且次数为 $t_{\mathrm{new}}-1$。新用户 $P_j$ 收到各方的值后计算：

$$ x_j'=\sum_{i\in S}q_i(j)\pmod q. $$

新总多项式 $Q(z)=\sum_iq_i(z)$ 满足：

$$ Q(0)=\sum_{i\in S}\lambda_i x_i=x, $$

但它的次数已经变成 $t_{\mathrm{new}}-1$，所以阈值也随之变成 $t_{\mathrm{new}}$。整个过程中不需要公开 $x$。

降低阈值是安全降级，应该由当前较高门限的合法集合批准；密文、份额和部分解密都应绑定策略编号与轮次，防止不同级别、不同轮次的数据混用。

9. 如何为实际系统选方案？ #

需求	更合适的方案
单位内部、可信密钥管理员	中心化 Shamir 分发
多机构共同托管密钥	DKG + VSS
长期保存高价值私钥	DKG + 主动份额更新
多人联合批准交易或发布	FROST 类 $(t,n)$ 门限签名
某角色必须参与	特殊份额或 LSSS 访问结构
人员权限有不同权重	加权分享或 LSSS
安全等级需要调整	经授权的重分享

总结 #

ElGamal 的解密本质是去掉 $C_1^x$ 产生的掩码；Shamir 秘密共享让 $x$ 可以被门限恢复；门限 ElGamal 则让参与者在不显式恢复 $x$ 的情况下协作得到 $C_1^x$。在此基础上，DKG 消除“可信中心见过完整私钥”的风险，主动份额更新抵抗长期份额收集，门限签名把联合解密的能力扩展为联合授权。

真正值得记住的不是某一条公式，而是三条设计原则：