算法设计

一个代理签名方案至少需要三种不同类型人的参与，即原始签名人，代理签名人(Agent)和代理签名的验证人

这篇文章分别用A,B,C代表上述三个身份

初始化参数：

椭圆曲线参数：$G$是椭圆曲线中阶为$n$的基点。

A私钥为$d_A\in[1.n-2]$,公钥为$P_A=d_AG$,私钥保密

$m_\omega$:授权证书信息（可以包含原始签名者和代理者的身份信息、代理签名者的权限等）

代理授权

B进行如下操作

用随机数生成器生成随机数$k_b\in[1,n-1]$,计算椭圆曲线上的点$G_b=k_bG$
B将$G_b$发送给A

A收到信息后进行如下操作

用随机数生成器生成随机数$k_a\in[1,n-1]$,计算椭圆曲线上的点$G_a=k_aG$
计算椭圆曲线上的另一个点$G_{ab}=(x_1,y_1)=k_aG_b$
计算$r_{ab}=x_1\pmod n$($r_{ab}=0$,重新计算)
计算$e_0=H(m_\omega||r_{ab})$
计算$s_A=$$k_a^{-1}(e_0+r_{ab}d_A)\pmod n$若$s_A=0$，返回第一步
A把（$m_\omega,G_a,G_{ab},s_A$）作为授权信息发送个B

其中$m_\omega$、$G_a$和$G_{ab}$公开，$s_A$秘密发送给B

授权验证+代理密钥生成

B收到授权信息后进行验证

3.计算椭圆曲线上另一个点$G’_{ab}=(x_2,y_2)=k_bG_a$

4.$e_0=H(m_\omega||r_{ab})$

5.计算$r’{ab}=x_2\pmod n$,若$s_AG_a≠r’{ab}P_A+e_0G$拒绝委托

6.计算代理签名密钥$d_p=s_Ak_b^{-1}\pmod n$

NAPS初始化

B生成$d_p$后

1.加密密钥对:

随机选取$x_E\in [1,n-1]$,令$P_E=x_EG$.为本次委托的NAPS辅助ElGamal密钥对

2.每个地址的份额多项式：

对地址空间中每个$\tau=1,…,L$,随机选取系数$\rho_{\tau,1},…,\rho_{\tau,N-1}\in \mathbb{Z}_N^*$

$f_\tau(X)=d_p+\sum_{j=1}^{N-1}\rho_{\tau,j}X^j\pmod n$

3.系数的可验证加密：

对每个 $j=1,\dots,N-1$，随机选 $r_{\tau,j}\in[1,n-1]$，计算

$$C_{\tau,j}=(C_{\tau,j,1},,C_{\tau,j,2})=\big(r_{\tau,j}G,\ r_{\tau,j}P_E+\rho_{\tau,j}G_{ab}\big)$$

ElGamal加密所用基点与$d_p$对应公钥所用基点保持一致。

B公开${C_{\tau,j}}{\tau\in[1,L],j\in[1,N-1]}$和$P_E$,秘密保存${\rho{\tau,j},r_{\tau,j}}$

代理签名生成

当B替代A对消息M进行签名时，使用的签名密钥四$d_p$过程如下

7.置$\overline{M}=Z_A||M$,其中$Z_A=H_{256}(ENTL_A||ID_A||a||b||x_G||y_G||x_A||y_A)$

8.计算$e=H(\overline{M})$

9.用随机数生成器生成随机数$k\in[1,n-1]$,计算($x_3,y_3$)=$kG_{ab}$

10.令$r=(e+x_3)\pmod n$若r=0或r+k=n则返回第8步

11.计算代理签名$s=(1+d_p)^{-1}(k-rd_P)\pmod n$若s=0返回第8步

NAPS部分

12.计算份额$z_\tau=f_{\tau}(p)=d_p+\sum_{j=1}^{N-1}\rho_{\tau,j}p^j\pmod n$

13.计算组和密文

$D=(D_1,D_2)=\sum_{j=1}^{N-1}p^jC_{\tau,j}=(R_\tau(p)G,R_\tau(p)P_E+(z_\tau-d_p)G_{ab})$,($R_\tau(p)=\sum_jp^jr_{\tau,j}$这个B掌握)

14.抵消未知项$D_2’=D_2+Q_p-z_\tau G_{ab}=R_\tau(p)P_E$

15.用Chaum-Pedersen型$\Sigma-$协议（Fiat-Shamir转化为非交互）证明

$\exist \omega:D_1=\omega G\land D_2’=\omega P_E $,($\omega=R_\tau(p)$)得到证明$\pi$

16.代理签名为$(m_\omega,G_a,G_{ab},r,s,\tau,p.z_\tau,\pi)$

代理签名的验证

验证者C进行如下操作

NAPS部分验证

1.$D=\sum_{J=1}^{N-1}p^jC_{\tau,j}$

2.$D_2’=D_2+Q_p-z_\tau G_{ab}=R_\tau(p)P_E$

3.验证$\pi$

SM2代理签名验证

4.检验$r’\in[1,n-1]$和$s’\in[1,n-1]$是否成立

5.置$\overline{M’}=Z_A||M’$,计算$e’=H(M’)$

6.计算$r_{ab}=x_1\pmod n$

7.计算$e_0’=H(m_\omega||r_{ab})$

8.计算$t=(r’+s’)\pmod n$若t=0验证不通过

9.计算椭圆曲线点$X=(x_3’,y_3’)=s’G_{ab}+tr_{ab}P_A+te_0’G$,计算$R=(e’+x_3’)\pmod n$当且仅当$R=r’$时接受签名

NAPS机制

NAPS定义；

$d_p=s_Ak_b^{-1}\pmod n$满足C类签名方案定义

class C:

密钥提取

同一地址$\tau$下出现$N$份不同载荷$p_1,…,p_N$的有效次代理签名，任何人可用拉格朗日插值提取代理密钥

$d_p=f_\tau(0)=\sum_{i=1}^Nz_i\prod_{k=1,k≠i}^N \frac{-p_k}{p_i-p_k}\pmod n$