跳转至

数字签名总结

一、基本概念

数字签名（Digital Signature）用于对数字消息进行签名，防止消息的冒名伪造或篡改，亦可用于通信双方的身份鉴别。

数字签名依赖于非对称密码，其基本原理：

数字签名原理

数字签名应具有的特性： 1. 可信性：任何人都可以验证签名的有效性。 2. 不可伪造性：除合法签名者外，任何人伪造签名是困难的。 3. 不可复制性：对一个消息的签名不能通过复制变为另一个消息的签名。 4. 消息不可改变：签名后的消息不能被篡改。 5. 不可抵赖性：签名者事后不能否认自己的签名。

二、RSA 数字签名

原理

与 RSA 加密类似，不同的是使用**私钥进行加密**，将加密后的结果作为签名。验证时使用公钥解密，将解密结果与原始消息比较。

对消息 \(m\) 的签名： - 签名：\(s = m^d \bmod n\)（\(d\) 为私钥） - 验证：\(m' = s^e \bmod n\)，比较 \(m'\) 与 \(m\) 是否一致

PKCS#1 v1.5 填充

对明文消息进行扩展的签名填充标准。填充格式为：

Text Only
00 | 01 | FF ... FF | 00 | ASN.1 | HASH

三、ElGamal 数字签名

ElGamal 的签名方案与加密方案有较大区别。

密钥生成

  1. 选取足够大的素数 \(p\)（十进制位数不低于 160 位），使得在 \(\mathbb{Z}_p\) 上求解离散对数问题困难。
  2. 选取 \(\mathbb{Z}_p^*\) 的生成元 \(g\)。

  3. 随机选取整数 \(d\)（\(0 \leq d \leq p - 2\)），计算 \(y \equiv g^d \bmod p\)。

  4. 公钥：\((p, g, y)\)

  5. 私钥：\(d\)

签名

选取随机数 \(k \in \mathbb{Z}_{p-1}\)，且 \(\gcd(k, p-1) = 1\)：

\[ r \equiv g^k \bmod p \]
\[ s \equiv (m - dr)k^{-1} \bmod (p-1) \]

签名结果为 \((r, s)\)。

验证

验证等式：

\[ g^m \equiv y^r \cdot r^s \bmod p \]

正确性推导：

\[ y^r \cdot r^s \equiv g^{dr} \cdot g^{ks} \equiv g^{dr + ks} \pmod p \]

由 \(s \equiv (m - dr)k^{-1} \bmod (p-1)\) 得 \(ks \equiv m - dr \bmod (p-1)\)，即 \(ks + dr = a(p-1) + m\)。

由费马定理 \(g^{p-1} \equiv 1 \bmod p\)：

\[ g^{ks + dr} \equiv g^{a(p-1) + m} \equiv (g^{p-1})^a \cdot g^m \equiv g^m \bmod p \]

攻击方法

完全破译攻击

条件 1：\(p\) 太小或无大素因子

若 \(p\) 太小可使用大步小步算法分解，若无大素因子可使用 Pohlig–Hellman 算法计算离散对数，从而求出私钥。

条件 2：随机数 \(k\) 复用

若签名者复用了随机数 \(k\)，攻击者可计算私钥。假设两个签名使用了相同的 \(k\)：

\[ r \equiv g^k \bmod p \]
\[ s_1 \equiv (m_1 - dr)k^{-1} \bmod (p-1) \]
\[ s_2 \equiv (m_2 - dr)k^{-1} \bmod (p-1) \]

两式相减：

\[ k(s_1 - s_2) \equiv m_1 - m_2 \bmod (p-1) \]

解出 \(k\) 后，可求私钥：

\[ d \equiv \frac{m - ks}{r} \bmod (p-1) \]

通用伪造签名

条件：消息 \(m\) 未取哈希，或未指定消息格式。

原理：已知 Alice 的公钥 \((p, g, y)\)，伪造签名：

  1. 选择整数 \(i, j\)，其中 \(\gcd(j, p-1) = 1\)。
  2. 计算 \(r \equiv g^i y^j \bmod p\)，\(s \equiv -rj^{-1} \bmod (p-1)\)。
  3. 计算消息 \(m \equiv si \bmod (p-1)\)。

则 \((r, s)\) 是消息 \(m\) 的有效签名。但攻击者无法伪造指定格式的消息，且消息进行哈希操作后此攻击不再可行。

已知签名伪造

若攻击者知道 \((r, s)\) 是消息 \(M\) 的合法签名，可伪造其他消息签名。

  1. 选择整数 \(h, i, j \in [0, p-2]\) 且满足 \(\gcd(hr - js, \varphi(p)) = 1\)。
  2. 计算： $$ r' = r^h \alpha^i y_A^{\,j} \bmod p $$ $$ s' = sr \cdot (hr - js)^{-1} \bmod \varphi(p) $$ $$ m' = r' \cdot (hm + is) \cdot (hr - js)^{-1} \bmod \varphi(p) $$

则 \((r', s')\) 是 \(m'\) 的有效签名。

抵抗措施：验证签名时检查 \(r < p\)。

四、DSA (Digital Signature Algorithm)

DSA 是 ElGamal 签名算法的变体，实际中更常用。

密钥生成

  1. 选择合适的哈希函数 \(H\)（一般为 SHA1 或更高强度）。
  2. 选择密钥长度 \(L\) 和 \(N\)（决定签名安全程度），例如 \((1024, 160)\)、\((2048, 256)\)。
  3. 选择 \(N\) 位的素数 \(q\)。
  4. 选择 \(L\) 位的素数 \(p\)，使得 \(p - 1\) 是 \(q\) 的倍数。
  5. 选择 \(g\)，使 \(\text{ord}(g) = q\)（在模 \(p\) 下）。计算方式：\(g = h^{(p-1)/q} \bmod p\)，其中 \(1 < h < p - 1\)。

  6. 选择私钥 \(x\)（\(0 < x < q\)），计算 \(y \equiv g^x \bmod p\)。

  7. 公钥：\((p, q, g, y)\)

  8. 私钥：\(x\)

签名

  1. 选择随机数 \(k\)（\(0 < k < q\)）作为临时密钥。
  2. 计算 \(r \equiv (g^k \bmod p) \bmod q\)。
  3. 计算 \(s \equiv (H(m) + xr) k^{-1} \bmod q\)。

签名结果为 \((r, s)\)。与 ElGamal 的重要区别是使用了哈希函数处理消息。

验证

  1. \(w = s^{-1} \bmod q\)
  2. \(u_1 = H(m)w \bmod q\)
  3. \(u_2 = rw \bmod q\)
  4. \(v = (g^{u_1} y^{u_2} \bmod p) \bmod q\)

若 \(v = r\)，则校验成功。

攻击方法

已知 \(k\)

若已知临时密钥 \(k\)，可直接计算私钥：

\[ x \equiv r^{-1}(ks - H(m)) \bmod q \]

\(k\) 共享攻击

若两次签名共享了 \(k\)，则 \(r\) 相同：

\[ s_1 \equiv (H(m_1) + xr) k^{-1} \bmod q \]
\[ s_2 \equiv (H(m_2) + xr) k^{-1} \bmod q \]

两式相减：

\[ k(s_1 - s_2) \equiv H(m_1) - H(m_2) \bmod q \]

解出 \(k\) 后即可求出私钥 \(x\)。