Skip to content
Notes
GitHub

第 7 章 数字签名

缩小范围，只考 DSA 和 ElGamal

7.2. 数字签名标准

数字签名标准 DSS (Digital Signature Standard) 是由美国 NIST 公布的联邦信息处理标准 FIPS PUB 186，其中采用了上一章介绍的 SHA 和一新的签名技术，称为 DSA (Digital Signature Algorithm)

7.2.1. DSS 的基本方式

首先将 DSS 与 RSA 的签名方式做一比较。RSA 算法既能用于加密和签名，又能用于密钥交换。与此不同，DSS 使用的算法只能提供数字签名功能。下图用于比较 RSA 签名和 DSS 签名的不同方式:

public/cypto/crypto18.svg

7.2.2. 数字签名算法 DSA

DSA 安全性基于求离散对数的困难性

算法描述如下

全局公开参数

  • p\displaystyle{ p } 满足 2{L−1}<p<2L\displaystyle{ 2 ^{ \left\lbrace L - 1 \right\rbrace } < p < 2 ^{ L } } 的大素数，其中 512⩽L⩽1024512 \leqslant L \leqslant 1024 且 L\displaystyle{ L } 是 64 的倍数
  • q\displaystyle{ q } 为 p−1\displaystyle{ p - 1 } 的素因子，满足 2{159}<q<2{160}\displaystyle{ 2 ^{ \left\lbrace 159 \right\rbrace } < q < 2 ^{ \left\lbrace 160 \right\rbrace } }，即 q\displaystyle{ q } 长为 160 比特
  • g\displaystyle{ g } 满足 g≡h(p−1)/q mod pg \equiv h^{(p-1)/q} \bmod p，其中 h\displaystyle{ h } 是满足 1<h<p−1\displaystyle{ 1 < h < p - 1 } 且使得 hp−1/q mod p>1h ^{p-1}/q \bmod p > 1 的任一整数

用户秘密钥 x

x\displaystyle{ x } 是满足 0<x<q\displaystyle{ 0 < x < q } 的随机数或伪随机数

用户公开钥 y

y≡gx mod py \equiv g^x \bmod p

用户为待签消息选取的秘密数 k

k\displaystyle{ k } 是满足 0<k<q\displaystyle{ 0 < k < q } 的随机数或伪随机数

签名过程

用户对 M\displaystyle{ M } 的签名为 (r,s)\displaystyle{ \left( r , s \right) }，其中 r≡gk mod p mod qr \equiv g ^k \bmod p \bmod q，s≡k−1(H(M)+xr) mod qs \equiv k^{-1}(H(M)+xr) \bmod q，H(M)\displaystyle{ H \left( M \right) } 是由 SHA 求出的哈希值。

签名 Sig(m,k)=(r,s)\text{Sig}(m, k)=(r, s)

验证过程

设接收方收到的消息为 M′M^\prime，签名为 (r′,s′)(r^\prime, s^\prime)，为书写简便，此处不加撇号

u1≡H(M)s−1 mod qu2≡rs−1 mod qv≡(gu1yu2) mod p mod q\begin{aligned} u_1 & \equiv H(M) s^{-1} \bmod q \\ u_2 & \equiv r s^{-1} \bmod q \\ v & \equiv (g^{u_1} y^{u_2}) \bmod p \bmod q \end{aligned}

检查 v=?r′v \overset{?}{=} r^\prime，若相等，则认为签名有效

证明过程
gu1yu2=gH(M)s−1⋅(gx)r⋅s−1=gH(M)s−1+xr⋅s−1=g(H(M)+xr)⋅s−1≡gsk⋅s−1 mod p mod q=gk=r\begin{aligned} g^{u_1} y^{u_2} & = g ^{H(M) s^{-1}} \cdot (g ^{x})^{r \cdot s ^{-1}} \\ & = g^{H(M)s^{-1} + xr \cdot s^{-1}} \\ & = g^{(H(M) + xr) \cdot s^{-1}} \\ & \equiv g ^{sk \cdot s^{-1}} \bmod p \bmod q \\ & = g^k \\ & = r \end{aligned}

public/cypto/crypto19.svg

预计算: r\displaystyle{ r } 的模指数运算 r=gk mod p mod qr= g^k \bmod p \bmod q，这一运算与待签的消息无关。

用户可以预先计算出很多 r\displaystyle{ r } 和 k{−1}\displaystyle{ k ^{ \left\lbrace - 1 \right\rbrace } } 以备以后的签名使用，可大大加快签名的速度。

例 如果 Bob 用同一个 k\displaystyle{ k } 签名不同的消息，有何风险？

解答
r≡gk mod q mod qs1≡k−1(H(M1)+xr) mod qs2≡k−1(H(M2)+xr) mod q\begin{aligned} r & \equiv g^k \bmod q \bmod q \\ s_1 & \equiv k^{-1}(H(M_1)+xr) \bmod q \\ s_2 & \equiv k^{-1}(H(M_2)+xr) \bmod q \\ \end{aligned}

可得

s1k≡H(M1)+xr(modq)s2k≡H(M2)+xr(modq)\begin{aligned} s_1 k \equiv H(M_1) + xr \pmod q \\ s_2 k \equiv H(M_2) + xr \pmod q \\ \end{aligned}

两式相减得

(s1−s2)k≡H(M1)−H(M2)(modq)\begin{aligned} (s_1 - s_2)k \equiv H(M_1) -H(M_2) \pmod q \end{aligned}

该方程是一元一次同余方程，其中只有 k\displaystyle{ k } 未知，因此 k\displaystyle{ k } 可以求出。进而私钥 x\displaystyle{ x } 也可求出。

7.3. 其他签名体制

7.3.1. 基于离散对数问题的数字签名体制

2. ElGamal 签名体制

体制参数
  • p\displaystyle{ p } : 大素数
  • g\displaystyle{ g } : Zp∗\mathbb{Z}^\ast_p 的一个生成元
  • x\displaystyle{ x } : 用户 A 的秘密钥，x∈RZp∗x \in {}_R\mathbb{Z}^\ast_p
  • y\displaystyle{ y } : 用户 A 的公开钥，y≡gx(modp)y \equiv g^x \pmod p
签名的产生过程

对于待签名的消息 m\displaystyle{ m }，A 执行以下步骤

  • 计算 m\displaystyle{ m } 的哈希值 H(m)\displaystyle{ H \left( m \right) }
  • 选择随机数 k:k←RZp−1∗k: k \leftarrow {}_R\mathbb{Z}^\ast_{p-1}，计算 r≡gk(modp)r \equiv g^k \pmod p
  • 计算 s≡(H(m)−xr)k−1(modp−1)s \equiv (H(m)-xr)k^{-1} \pmod {p-1}

签名 Sig(m,k)=(r,s)\text{Sig}(m, k)=(r, s)

验证过程
yrrs≡gH(m) mod p\begin{aligned} y^r r^s \equiv g^{H(m)} \bmod p \end{aligned}

当上式成立时，即有 Ver(y,(r,s),H(m))=True\text{Ver}(y, (r,s), H(m))=\text{True}

k 泄露的威胁

由 s≡k−1(H(m)−xr)(modp−1)s \equiv k^{-1}(H(m)-xr) \pmod{p-1} 方程变成一元一次同余方程，私钥 x\displaystyle{ x } 即可求出，攻击者可以由此伪造任意消息和签名。

7.3.3. 基于身份的数字签名体制

1. ElGamal 签名体制

体制参数
  • q\displaystyle{ q } 为大素数
  • G1,G2\mathbb{G}_1, \mathbb{G}_2 分别是阶为 q\displaystyle{ q } 的加法群和乘法群
  • e^:G1×G1→G2\hat{e}: \mathbb{G}_1 \times \mathbb{G}_1 \to \mathbb{G}_2 是一个双线性映射
  • H1:{0,1}∗→G1∗H_1: \{0, 1\}^\ast \to \mathbb{G}_1 ^\ast 和 H2:G2→{0,1}nH_2 : \mathbb{G}_2 \to \{0, 1\} ^n 是两个哈希函数
  • s←RZq∗s \leftarrow {}_R\mathbb{Z}^\ast_q 是系统的主密钥
  • P\displaystyle{ P } 是 G1\mathbb{G}_1 的一个生成元
  • 用户 ID 的公开钥 QID=H1(ID)∈G1∗Q_{ID}=H_1(ID) \in \mathbb{G}_1 ^\ast，P{pub}=sP\displaystyle{ P _{ \left\lbrace p ub \right\rbrace } = s P }
  • 秘密钥 d{ID}=sQ{ID}\displaystyle{ d _{ \left\lbrace I D \right\rbrace } = s Q _{ \left\lbrace I D \right\rbrace } }
签名产生过程

对于待签名的消息 m\displaystyle{ m }，A 执行以下步骤

  1. 选择随机数 k:k←RZq∗k: k \leftarrow {}_R\mathbb{Z}^\ast_q
  2. 计算 R=kP=to be(xR,yR)R=kP\overset{\text{to be} }{=}(x_R,y_R)
  3. 计算 S≡(H2(m)P+xRdID)k−1S \equiv (H_2(m)P+x_R d_{ID})k^{-1}

以 (R,S)\displaystyle{ \left( R , S \right) } 作为产生的数字签名

签名验证过程

接收方在收到消息 m\displaystyle{ m } 和数字签名 (R,S)\displaystyle{ \left( R , S \right) } 后，先计算 H2(m)\displaystyle{ H _{ 2 } \left( m \right) }，并按下式验证：

Ver(QID,(R,S),H2(m))=True⇔e^(R,S)=e^(P,P)H2(m)e^(Ppub,QID)xR\begin{aligned} & \text{Ver}(Q_{ID}, (R,S), H_2(m)) = \text{True} \\\Leftrightarrow & \hat{e} (R,S)=\hat{e}(P,P)^{H_2(m)} \hat{e}(P_{pub}, Q_{ID})^{x_R} \end{aligned}