标签：方案 数字签名 mathcal 签名 delta alpha gamma mod

数字签名方案

数字签名安全模型(Sig-forge实验流程)：

攻击者通过查询一些消息的签名，不能构造出没有查询过的消息的签名，即\(Pr[Sig-forge_{A,\Pi}(n)=1]\leq negl(n)\)

RSA签名方案

签名方案

• KeyGen：\(\mathcal{K}=\{(n,p,q,a,b):n=pq, p和q均为素数,ab = 1\mod(\varPhi(n))\}\)，公钥\((n,b)\)，私钥\((p,q,a)\)
• Sig：对于消息\(x\)，用私钥计算\(x\)的签名，\(y = Sig_{\mathcal{K}}(x)=x^a\mod n\)
• Vrfy：给定消息\(x\)和签名\(y\)，用公钥验证\(Vrty_{\mathcal{K}}(x,y)=1 \iff x = y^b \mod n\)

伪造签名

1. 选择\(y \leftarrow Z_n\)，并计算\(x = e_k(y)\)，则\(y\)是\(x\)的有效签名；
2. 已知合法消息签名对\((x_1,y_1),(x_2,y_2)\)，尅构造消息\(x_1x_2\)的签名为\(y_1y_2\)；
3. 已知\(x\)，计算\(x = x_1x_2\mod n\)，分别计算\(x_1,x_2\)的签名\(y_1,y_2\)，则\(x\)的签名为\(y_1y_2\).

可以利用HASH函数生成消息的摘要再生成签名

graph LR 消息x -- "z=Hash(x)" --> 摘要z -- "Sig=(sk,x)" --> 签名y

\[Vrfy(Hash(x), y) = 1 \]

ElGamal签名方案

ElGamal签名方案具有非确定性，一个明文可能具有多个有效签名

• KeyGen：设\(\alpha \in Z_p\)是一个生成元，\(\mathcal{P}=Z_p^*\)，\(A = Z_p^* \times Z_{p-1}\)，定义\(\mathcal{K}=\{(p,\alpha,b,\beta):\beta=\alpha^b\}\)，则\(p,\alpha,\beta\)是公钥，\(b\)是私钥；

b作为私钥，安全性基于离散对数问题

• Sig：对于消息\(x\)，选择一个秘密随机数\(r\in Z^*_{p-1}\)，计算\(\gamma=\alpha^r \mod p, \delta = (x-b\gamma)r^{-1}\mod (p-1)\)，定义签名为\(Sig_{\mathcal{K}}(x,r) = (\gamma, \delta)\)；

若随机数\(r\)泄露，则私钥\(b = (x - \delta r)\gamma ^{-1}\mod (p-1)\)

• Vrfy：对于给定的签名\((\gamma, \delta)\)和消息\(x\)，\(Vrfy(x, (\gamma, \delta)) = 1 \iff \beta^{\gamma}\gamma^{\delta} = \alpha ^x \mod p\).

数字签名算法(DSA)

• KeyGen：设\(p\)是长为\(Lbits\)的素数，在\(Z_p^*\)上其离散对数问题是难解的，其中\(L=0 \mod 64\)且\(512 \leq L \leq 1024\)，\(q\)是能整除\(p-1\)的\(160bits\)的素数，设\(\alpha \in Z_p^*\)且\(\alpha ^q\mod p = 1\)，定义

\[\mathcal{K} = \{(p,q,\alpha,b,\beta):\beta = \alpha ^b \mod p\} \]

其中\(0\leq b\leq q - 1\)，\(p,q,\alpha,\beta\)是公钥，\(b\)是私钥；

• Sig：对于消息\(x\)，\(\mathcal{K} = \{(p,q,\alpha,b,\beta)和一个秘密随机数r\in Z_p^*,1\leq r\leq q-1\}\)，计算

\[\gamma = (\alpha ^{r}\mod p) \mod q, \delta = (SHA-1(x)+ b\gamma)r^{-1}\mod q. \]

定义签名为\(Sig(x,r) = (\gamma, \delta)\)

• Vrfy：对\(x\in \{0,1\}^*,\gamma, \delta \in Z_q\)，验证通过下面计算完成

\[\begin{aligned} &e_1 = SHA-1(x)\delta^{-1}\mod q, e2 = \gamma \delta^{-1}\mod q\\ &Vrfy(x,(\gamma, \delta)) = 1 \iff (\alpha ^{e_1}\beta ^{e_2}\mod p)\mod q = \gamma\\ \end{aligned} \]

Schnorr签名算法

• KeyGen：设\(p\)是使得\(Z_p^*\)上离散对数问题难解的一个素数，\(q\)是能整除\(p-1\)的素数，设\(\alpha\in Z_p^*\)是\(1\)模\(p\)的\(q\)次根，\(h:\{0,1\}^*\rightarrow Z_q\)是一个安全的HASH函数，定义

\[\mathcal{K} = \{(p,q,\alpha,a,\beta):\beta = \alpha^a\mod p\} \]

其中\(0\leq a\leq q-1\)，\(p,q,\alpha,\beta\)是公钥，\(a\)是私钥

• Sig：对于消息\(x\)，\(\mathcal{K}=\{(p,q,\alpha,a,\beta)\}\)和一个秘密随机数\(r\in Z_q^*\)，\(1\leq r\leq q-1\)，计算

\[\gamma = h(x||\alpha ^r\mod p), \delta = r + a\gamma \mod p\\ \]

定义签名为\(Sig_{\mathcal{K}}(x,r) = (\gamma, \delta)\)

• Vrty：对\(x\in \{0,1\}^*，\gamma, \delta \in Z_q\)，验证通过下面的计算完成

\[Vrty_{\mathcal{K}}(x, (\gamma, \delta)) = q \iff h(x|| \alpha ^{\delta}\beta^{-\gamma}\mod p) = \gamma \]

椭圆曲线数字签名算法(ECDSA)

• KenGen：设\(p\)是一个大素数，\(E\)是定义在\(F_p\)上的椭圆曲线，设\(A\)是\(E\)上阶为\(q\)(q是素数)的一个点，使得\(<A>\)上的离散对数问题是一个困难问题，定义

\[\mathcal{K} = \{(p,q,E,A,m,B):B = mA,m\in Z_q\} \]

其中\(0\leq m\ q-1\)，\(p,q,E,A,B\)是公钥，\(m\)是私钥

• Sig：对于消息\(x\)，\(\mathcal{K} = (p,q,E,A,m,B)\)和一个秘密随机数\(k \in Z_q^*\)，\(1\leq k\leq q-1\)，计算

\[\begin{aligned} &(u,v) = kA\\ &r = u \mod q\\ &s = (SHA-1(x)+ mr)k^{-1} \mod q\\ \end{aligned} \]

定义签名为\(Sig_{\mathcal{K}}(x,k) = (r,s)\)

• Vrty：

\[\begin{aligned} &w = s^{-1} \mod q\\ &i = w Sha-1(x) \mod q\\ &j = wr \mod q\\ &(u,v) = iA+jB\\ &Vrty_{\mathcal{K}}(x(r,s)) = 1\iff u \mod q = r\\ \end{aligned} \]

SM2签名算法

系统参数：\((p,a,b,G,n,H)\)定义了椭圆曲线\(\mathbb{E}(\mathbb{F}_p) = \{(x,y)\in \mathbb{F}_p:y^2 = x^3 + ax+b\}\)及一个\(n\)阶元\(G \in \mathbb{E}(\mathbb{F}_p)\)，其中\(p,n\)均为大素数，H为哈希算法

公钥：\(P\leftarrow dG\)，私钥\(d\leftarrow [1,n-2]\)

• Sig：
  1. \(e = H(m)\);
  2. \(k\leftarrow [1,n-2]\)，计算\(kG = (x_1,y_2)\)
  3. \(r = e+x_1 \mod n\);
  4. \(s = \dfrac{k-rd}{1+d}\mod n\)
• Vrty：
  1. \(t = r+s \mod n\)
  2. \((x_1,y_1 = sG+tP)\)
  3. \(R = e+x_1\mod n\)
  4. \(R \overset{?}{=} r\)

标签：方案,数字签名,mathcal,签名,delta,alpha,gamma,mod
From： https://www.cnblogs.com/euler0525/p/16931615.html