秘密共享及门限签名

Elgamal 签名算法 Harn 的门限签名方案

RSA Shoup 门限签名方案

Asmuth-Bloom 法

Karnin-Greene-Hellman 法

Shamir 门限法（拉格朗日插值法）

Elgamal 签名算法

依赖有限域上的离散指数的难计算性，即设为素数的模循环群的原根，对任意的，计算：

$$b=g^a\bmod p$$

是容易的（通过幂取模算法）。反过来，给定计算满足上式的是非常困难的，称为以为基的离散对数。

初始化

Alice随机选择大素数和到之间的整数，找出有限域的一个生成元，计算：

$$y=g^x\bmod p$$

则公钥为，私钥为。

签名

设待签名消息为，Alice随机选择整数，满足，。计算：

$$r=g^k\bmod p$$ $$s=(m-xr)k^{-1}\bmod p$$

将的签名发送给Bob。

验证

Bob收到，利用Alice的公钥验证等式：

$$g^m\equiv y^rr^s\bmod p$$

若等式成立则签名有效。

Harn 的门限签名方案

初始化

假设有个成员，为门限值，、为大素数，，为有限域上的阶生成元，是的循环群中的一个数，待签名消息为，每个成员随机选择和，计算：

$$y_i=g^{z_i}\bmod p$$

成员私钥为，组公钥计算如下：

$$y=\prod_{i=1}^ny_i\bmod p$$

$Pi(i=1,2,\cdots,n)t-1f_i(x)=z_i+a{i,1}x+a{i,2}x^2+\cdots+a{i,t-1}x^{t-1}f_i(x_j)\bmod qP_j$，并计算验证信息：

$$y_{i,j}=g^{f_i(x_j)}\bmod p$$

产生部分签名

设参与签名的成员。成员选择一个随机数，计算并将其广播给所有成员。

收到其他成员广播的后，计算

$$r=\prod_{i=1}^tr_i\bmod p$$

通过自己的私钥、、份额计算：

$$s_i=z_i+\lbrace\sum_{j=t+1}^nf_j(x_i)(\prod_{k=1,k\neq i}^t\frac{-x_k}{x_k-x_j})\rbrace m-k_i r\bmod q$$

将部分签名发送给签名合成者。

合成者收到后，通过下式验证其有效性：

$$\lbrace y_i(\prod_{j=t+1}^ny_{j,i})^{\prod_{k=1,k\neq i}^t\frac{-x_k}{x_i-x_k}}\rbrace^m=r_i^r g^{s_j}\bmod p$$

若验证式成立，则收到的部分签名有效。

产生组签名

合成者确认接收到个正确的部分签名后，计算：

$$s=\sum_{i=1}^ts_i\bmod q$$

将作为消息的组签名。

验证签名

验证者收到组签名后，验证其有效性：

$$y^m=r^r g^s \bmod p$$

每个参与者拥有的数

$$P_1 \begin{cases} z_1\stackrel{}{\longrightarrow} y_1\stackrel{}{\longrightarrow} y \\ f_1(x)\stackrel{x_j}{\longrightarrow} f_1(x_j){\longrightarrow} y_{1,j} \\ f_j(x_1) {\longrightarrow} y_{j,1} \\ k_1\stackrel{}{\longrightarrow} r_1 \stackrel{r_j}{\longrightarrow} r \\ \end{cases}$$

Shoup 门限签名方案

RSA 体制中为安全大素数，即存在大素数使得，，记。

初始化

可信中心TC随机选取次数不超过的多项式

$$f(x)=\sum_{j=0}^{t-1}a_jx^j\in Z_m[x]$$

其中，。

TC计算，并将其发送给成员：

$$d_i=f(i)\bmod m$$

同时计算。

TC公开、、。

产生部分签名

成员计算消息摘要，然后计算：

$$x_i=x^{2\pi d_i}\bmod N$$

产生组签名

若有个成员产生正确的部分签名，则计算

$$y=\prod_{i=1}^tx_i^{2\pi \lambda_{0,i}}\bmod N=x^{4\pi^2d}\bmod N$$

令，由欧几里得定理可知存在，使得，即，最终签名：

$$s=y^bx^a\bmod N$$

验证签名

验证门限签名时，验证以下等式是否正确：

$$s^e=H(M)\bmod N$$

Asmuth-Bloom 法

初始化

假设为共享秘密，为秘密分发者，有个成员，为恢复秘密的门限值。选择大素数和严格递增的序列，满足如下条件：

$$d_1<d_2<\cdots<d_n$$ $$(d_i,d_j)=1,(i\neq j)$$ $$(d_i,q)=1,(i=1,2,\cdots,n)$$ $$\prod_{i=1}^td_i>q\prod_{i=1}^{t-1}d_{n-i+1}$$

秘密分发

令，选择满足式的整数，计算：

$$Z=S+Aq$$ $$Z_i=Z\bmod d_i,i=1,2,\cdots,n$$

并将作为秘密份额发给成员。

秘密恢复

选取个成员参与秘密的恢复，通过交换秘密份额，任意成员可以建立同余方程组：

$$\begin{cases} Z_1=Z\bmod d_1 \\\\ Z_2=Z\bmod d_2 \\\\ \vdots \\\\ Z_t=Z\bmod d_t \end{cases}$$

由可知该方程组有唯一解：

$$Z=\sum_{i=1}^t\frac{D}{d_i}\cdot e_i\cdot Z_i\bmod D,i=1,2,..,t$$

其中：

$$D=\prod_{i=1}^td_i$$ $$\frac{D}{d_i}\cdot e_i \equiv 1\bmod d_i,i=1,2,\cdots,t$$

可求出共享秘密。

Karnin-Greene-Hellman 法

产生主次密钥

(m,n)

1. 信任单位产生个任意维矩阵，矩阵元素为或，分别为
2. 信任单位产生个任意维矩阵
3. 产生n个次密钥
   ，不可暴露，分别保存
4. 主密钥为
5. 公开矩阵

密钥恢复

1. 选取m组次密钥
2. 拼接矩阵
3. 计算逆矩阵
4. 计算
5. 计算

Shamir 门限法

秘密分发

任取$a1,a_2,\cdots,a{t-1}\in GF(q)$构造一个多项式：

$$f(x)=(d+a_1x+a_2x^2+\cdots+a_{t-1}x^{t-1})modq$$

其中为密钥，计算，称为部分密钥，将分别通过安全的信道发送给每个分享者。

秘密恢复

如果有个共享者想恢复秘密信息，他们分别拿出自己的，然后利用Lagrange插值公式：

$$h(x)=\sum_{i=1}^td_i\lambda_{x,i}$$

其中$\lambda{x,i}=\prod{k=1,k\neq j}^t\frac{i-k}{j-k}d=f(0)=h(0)d$。