数字签名Signature

好的，既然您需要深入理解这三种数字签名算法背后的数学原理，我将结合离散对数（DLOG）和群论的知识，详细推导签名和验证过程的等式关系。

深入解析数字签名算法的数学原理

这三种算法都依赖于一个共同的数学基础：循环群 $\mathbb{Z}_q^*$ 或其子群上的离散对数难题 (DLOG)。

1. ElGamal 签名算法 (DSA 的基础)

ElGamal 签名在指数上巧妙地嵌入了私钥 $\text{SK}$ 和报文 $\text{Hash}$ 值 $m$ 的信息。

核心参数

群: $\mathbb{Z}_q^*$ (模 $q$ 的乘法群).
生成元: $g$.
私钥 (指数): $a$. 公钥 (群元): $\text{PK} = g^a \bmod q$.
签名随机数 (指数): $K$. 公开随机量 (群元): $S_1 = g^K \bmod q$.
报文 Hash (指数): $m = \text{H}(M)$.

签名方程 (指数上的线性关系)

签名分量 $S_2$ 的计算公式是 $S_2 = K^{-1}(m - a S_1) \bmod (q-1)$ 。我们将等式两边同乘以 $K$: $$K S_2 \equiv m - a S_1 \pmod{q-1}$$ 移项得到一个关键的指数方程: $$\mathbf{m \equiv K S_2 + a S_1 \pmod{q-1}}$$

验证原理 (群上的等式)

验证过程是检查群元 $V_1$ 和 $V_2$ 是否相等。 * $V_1 = g^m \bmod q$. * $V_2 = \text{PK}^{S_1} S_1^{S_2} \bmod q$.

推导: 将 $V_2$ 中的项用它们的定义代入： $$V_2 = \text{PK}^{S_1} S_1^{S_2} \bmod q$$ $$V_2 = (g^a)^{S_1} (g^K)^{S_2} \bmod q$$ $$V_2 = g^{a S_1} g^{K S_2} \bmod q$$ $$V_2 = g^{a S_1 + K S_2} \bmod q$$

根据签名得到的关键指数方程 $m \equiv K S_2 + a S_1 \pmod{q-1}$，可知 $a S_1 + K S_2$ 等于 $m$ 在 $\bmod (q-1)$ 意义下的值。由于 $g$ 的阶是 $q-1$，根据群论的性质，指数在 $\bmod (q-1)$ 意义下的等式可以转化为群元在 $\bmod q$ 意义下的等式： $$V_2 = g^{m} \bmod q$$ $$V_2 = V_1$$

结论: 如果签名正确，则 $V_1 = V_2$ 恒成立。签名者通过私钥 $a$ 使得指数满足线性关系，验证者通过公钥 $\text{PK}=g^a$ 在群上重构 $g^m$ 来验证这个关系。

2. Schnorr 签名算法 (形式最简洁)

Schnorr 签名采用的是一种零知识证明的思想：挑战-响应 (Commitment-Challenge-Response) 机制，其形式最为简洁漂亮。

核心参数

群: $\mathbb{Z}_p^*$ 的 $q$ 阶子群.
私钥 (指数): $\text{sk}$. 公钥 (群元): $\text{pk} = g^{-\text{sk}} \bmod p$.
签名随机数 (指数): $r$. 公开随机量 (群元): $x = g^r \bmod p$.
挑战/承诺值: $e = \text{H}(M || x)$.

签名方程 (指数上的线性关系)

签名分量 $y$ 的计算公式是 $y = (r + \text{sk} \cdot e) \bmod q$ 。这个等式本身就是关键的指数方程: $$\mathbf{r \equiv y - \text{sk} \cdot e \pmod{q}}$$

验证原理 (群上的等式)

验证过程是检查 $x'$ 是否能根据签名和公钥恢复出 $x$ 。 * $x'$ 的计算公式是 $x' = (g^y \text{pk}^e) \bmod p$.

推导: 将 $\text{pk}$ 和 $y$ 用它们的定义代入 $x'$ 的计算公式： $$x' = g^y \text{pk}^e \bmod p$$ $$x' = g^y (g^{-\text{sk}})^e \bmod p$$ $$x' = g^y g^{-\text{sk} \cdot e} \bmod p$$ $$x' = g^{y - \text{sk} \cdot e} \bmod p$$

根据签名得到的关键指数方程 $r \equiv y - \text{sk} \cdot e \pmod{q}$： $$x' = g^r \bmod p$$

又因为 $x = g^r \bmod p$ ，所以： $$x' = x$$

结论: 如果 $x' = x$，则 $e$ 必须等于 $\text{H}(M || x')$, 因为 $e$ 的定义就是 $\text{H}(M || x)$ 。签名者通过 $\text{sk}$ 使得指数 $y$ 满足线性关系，验证者通过公钥 $\text{pk}$ 在群上重建 $g^r$ 来验证这个关系。

3. DSA (Digital Signature Algorithm)

DSA 是 ElGamal 和 Schnorr 签名的改进/结合体，它在保持安全性的同时，将签名分量 $r$ 约束在一个较小的模 $q$ 下，使其签名长度较短 (160 比特) 。

核心参数

群: $\mathbb{Z}_p^*$ 的 $q$ 阶子群.
私钥 (指数): $\text{sk}$. 公钥 (群元): $\text{pk} = g^{\text{sk}} \bmod p$.
签名随机数 (指数): $k$. 公开随机量: $r = (g^k \bmod p) \bmod q$.
报文 Hash (指数): $m = \text{H}(M)$.

签名方程 (指数上的线性关系)

签名分量 $s$ 的计算公式是 $s = (k^{-1}(m + \text{sk} \cdot r)) \bmod q$ 。我们将等式两边同乘以 $k$ 并进行移项，得到关键的指数方程: $$k s \equiv m + \text{sk} \cdot r \pmod{q}$$ $$\mathbf{k \equiv (m s^{-1} + \text{sk} r s^{-1}) \bmod q}$$

验证原理 (群上的等式)

验证过程是检查群元 $v$ 是否能恢复出 $r$ 。 * $v$ 的计算公式是 $v = ((g^a \text{pk}^b) \bmod p) \bmod q$ 。其中 $a = m w \bmod q$, $b = r w \bmod q$, $w = s^{-1} \bmod q$ 。

推导: 将 $a$, $b$, $w$ 代入群元 $g^a \text{pk}^b$: $$g^a \text{pk}^b \bmod p = g^{m w} (\text{pk})^{r w} \bmod p$$ $$= g^{m w} (g^{\text{sk}})^{r w} \bmod p$$ $$= g^{m w} g^{\text{sk} r w} \bmod p$$ $$= g^{m w + \text{sk} r w} \bmod p$$ $$= g^{(m + \text{sk} r) w} \bmod p$$

由于 $w = s^{-1} \bmod q$ ，代入指数中的 $w$: $$= g^{(m + \text{sk} r) s^{-1}} \bmod p$$

根据签名得到的关键指数方程 $k \equiv (m + \text{sk} r) s^{-1} \pmod{q}$ ，可知 $(m + \text{sk} r) s^{-1}$ 等于 $k$ 在 $\bmod q$ 意义下的值。由于 $g$ 的阶是 $q$，指数在 $\bmod q$ 意义下的等式可以转化为群元在 $\bmod p$ 意义下的等式： $$g^a \text{pk}^b \bmod p = g^k \bmod p$$

最终，验证值 $v$ 是这个群元 $g^k \bmod p$ 再对 $q$ 取模: $$v = (g^k \bmod p) \bmod q$$

又因为 $r$ 的定义就是 $r = (g^k \bmod p) \bmod q$ ，所以： $$\mathbf{v = r}$$

结论: 如果签名正确，则验证值 $v$ 必须等于 $r$ 。签名者利用私钥 $\text{sk}$ 使得指数满足线性关系，验证者通过公钥 $\text{pk}$ 在群上重构 $g^k \bmod p$ 并对 $q$ 取模，来验证这个关系。