门限密码学的背景和概念:

门限密码学的思想基于秘密分享,即使用秘密分享方法将基本的公钥密码体系分布于若干参与者之间.

门限密码学包括门限加密和门限签名.

门限加密:

直接将密钥作为秘密,以秘密分享体系分享给参与者不失为一种方案,但这样会带来几个问题:

分发者知道密钥,不可信的分发者可能会盗用密钥
参与重构的成员因为得到了密钥,因此也可能在未经允许的情况下盗用密钥

为避免此类问题,给出如下的门限加密的定义:

分布式密钥生成:

由$P_1,P_2,\cdots,P_n$运行的生成公钥$h$的协议

协议运行结束后,每个参与者获得
1. 私钥$x$的碎片$x_i$,
2. 对应该碎片的碎片验证公钥$h_i$,
3. 与私钥$x$相对应的公钥$h$
加密算法:

输入:公钥$h$,明文$m$

输出:密文$c$
门限解密:

由任意$t$个参与者,不妨设为$P_1,P_2,\cdots,P_t$运行的协议

输入:
1. 密文$c$,
2. $t$个私钥碎片$x_1,x_2,\cdots,x_t$,
3. 碎片验证公钥$h_1,h_2,\cdots,h_t$
输出:明文$m$

对于成员数为$n$,门限值为$t$的门限密码协议,其不依赖任何特殊的可信方,其基本要求是,私钥$x$总是保密的,除非不少于$t$个参与者泄露了自己的秘密碎片.

门限ElGamal密码体系:

系统参数:

大素数$p$

$G$为$p$阶循环群

$g$为$G$的生成元

参与者数量为$n$,门限值为$t$

分布式密钥生成:

该步骤的目标是由$P_1,P_2,\cdots,P_n$共同生成生成公共公钥$h$,再各自生成自己的私钥碎片$x_i$和用于验证私钥碎片的碎片验证公钥$h_i$

参与者$P_i$进行如下的工作:

随机生成多项式$$f_i(x)=\alpha_{(i,0)}+\alpha_{(i,1)}x+\alpha_{(i,2)}x^2+\cdots+\alpha_{(i,t-1)}x^{t-1}$$并记$S_i=\alpha_{(i,0)}$
将$g^{S_i}$发送给其他参与者.
收到其他参与者发来的$$g^{S_1},g^{S_2},\cdots,g^{S_{i-1}},g^{S_{i+1}},\cdots,g^{S_n}$$后,计算并发布$$h=\Pi_{j=1}^ng^{S_j}$$作为公共公钥.
以秘密分发者的身份执行Feldman的VSS方案(回顾密码协议学习笔记(8.1):秘密分享 - Isakovsky - 博客园 (cnblogs.com)),在$$P_1,P_2,\cdots,P_n$$之间分享秘密$S_i$,记$P_j$得到的关于$S_i$的碎片是$s_{(ij)}=f_i(j)$
将自己收到的碎片相加,就得到自己关于私钥$x$的私钥碎片$$x_i=\Sigma_{j=1}^{n}s_{(j,i)}$$
计算自己的碎片验证公钥$$h_i=g^{x_i}$$

加密:

收到公共公钥$h$并意图向参与者们$P_1,P_2,\cdots,P_n$所代表的组织发送信息$m$的人,其工作和和ElGamal加密体系类似,

随机选取$k\in[1,p-1]$
计算$a=g^k$
计算$b=mh^k$
将$(a,b)$作为密文发送

门限解密:

收到消息$(a,b)$后,任意$t$个参与者,不妨记为$P_1,P_2,\cdots,P_t$可进行解密

参与者$P_i$的工作如下:

使用自己的私钥碎片$x_i$计算$$d_i=a^{x_i}$$并发送给其他人
生成一个知识证据$PROOF_i$以证明自己使用了正确的$x_i$计算出了$d_i$,即$x_i$使得$d_i=a^{x_i},h_i=g^{x_i}$同时成立,生成的方式可参考密码协议学习笔记(8.15):知识证据 - Isakovsky - 博客园 (cnblogs.com)
收到其他人发来的$d_j$后,使用$PROOF_j$验证$d_j$的有效性
计算如下式子以恢复明文$$m'=\frac{b}{\Pi_{i=1}^td_i^{\lambda_i}}$$其中$$\lambda_i=\underset{j=1,2,\cdots,i-1,i+1,\cdots,t}{\Pi}\frac{j}{j-i}$$为Lagrange插值系数.

正确性证明:

$$\begin{aligned}
m'&=\frac{b}{\Pi_{i=1}^td_i^{\lambda_i}}\\
=&\frac{mh^k}{\Pi_{i=1}^t(a^{x_i})^{\lambda_i}}\\
=&\frac{mh^k}{a^{\Sigma_{i=1}^tx_i\lambda_i}}\\
=&\frac{mh^k}{a^{\Sigma_{i=1}^t(\Sigma_{j=1}^nf_j(i))\lambda_i}}\\
=&\frac{mh^k}{a^{\Sigma_{j=1}^n\Sigma_{i=1}^tf_j(i)\lambda_i}}\\
=&\frac{mh^k}{a^{\Sigma_{j=1}^nf_j(0)}}\\
=&\frac{mh^k}{a^{\Sigma_{j=1}^nS_i}}\\
=&\frac{mh^k}{(g^k)^{\Sigma_{j=1}^nS_i}}\\
=&\frac{mh^k}{h^k}\\
=&m
\end{aligned}$$

可以看出,即使在门限解密环节,私钥$x$也未被直接计算出来,这防止了经手私钥的人暗中保存并在之后滥用.

门限签名:

定义:成员数为$n$,门限值为$t$的门限签名是由以下三个协议构成的体系:

密钥生成协议:

各参与者$P_1,P_2,\cdots,P_n$协作运行的协议.

协议结束时,参与者$P_i$获得私钥$x$的碎片$x_i$,公钥$y$公开发布
签名生成协议:

至少$t$个参与者,不妨记为$P_1,P_2,\cdots,P_t$协作运行的协议

公开输入为待签名信息$m$和公钥$y$

公开输出为签名$\sigma=Sign(m,x)$
签名验证算法:

与通常的签名验证算法完全一致

门限RSA签名协议:

系统参数:

参与者数量为$n$,门限值为$t$

碎片分发:

分发者做如下工作以生成并分发密钥碎片:

选取大质数$p,q$,计算$n=pq$,$\varphi(n)=(p-1)(q-1)$
选取$e\in (\max(p,q),\varphi(n))$,计算$d=e^{-1} \mod \varphi(n)$
使用Shamir秘密分享方案生成$d$的碎片$d_1,d_2,\cdots,d_n$并分发给成员$P_1,P_2,\cdots,P_n$
随机生成盐$t_1,t_2,\cdots,t_n\in[1,p-1]$,计算碎片验证公钥$h_1,h_2,\cdots,h_n$,$h_i=t_i^{d_i}$,然后将$(t_1,h_1),(t_2,h_2),\cdots,(t_n,h_n)$公开.
将$(n,e)$作为公钥公开.
由于正常运行协议时,参与者不应知道$\varphi(n)$的值,因此需预先计算出模$\varphi(n)$下的Lagrange插值系数$$\lambda_1,\lambda_2,\cdots,\lambda_t$$供参与者使用$$\lambda_i=\underset{j=1,2,\cdots,i-1,i+1,\cdots,n}{\Pi}\frac{j}{j-i}\mod \varphi(n)$$另,由于$i,j\leq n \ll \min(p,q)$,所以$\forall i,j, gcd(i-j,\varphi(n))=1$其逆元必然存在.

分布式签名:

对于待签名信息$m$,$t$个参与者,不妨记为$P_1,P_2,\cdots,P_t$协作运行此算法,生成签名$\sigma$

$P_i$的工作如下:

计算$s_i=m^{d_i}$
生成知识证据$PROOF_i$以证明$\log_{m}s_i=\log_{t_i}h_i$,和$s_i$一同发送给其他参与者.
通过知识证据验证其他人发来的$s_j$的有效性
计算$$\sigma=\Pi_{j=1}^t(s_j)^{\lambda_j}$$作为签名.

实际上,

$$\begin{aligned}
\sigma=&\Pi_{j=1}^t(s_j)^{\lambda_j}\\
=&\Pi_{j=1}^t(m^{d_j})^{\lambda_j}\\
=&m^{\Sigma_{j=1}^td_j\lambda_j}\\
=&m^d
\end{aligned}$$