数字签名算法¶

数字签名方案¶

使用 RSA 加密、认证:
- 假设 A 发送消息给 B
  - 用发送者的私钥签名：\(S = M^{d_A} \bmod n_A\)
  - 用接收者的公钥加密：\(C = S^{e_B} \bmod n_B\)
- 接收者 B 解密:
  - \(S = C^{d_B} \bmod n_B\)
  - 验证签名：\(M = S^{e_A} \bmod n_A\)
看起来，一个消息可用 RSA 先加密再签名而不改变大小
- 但是，加密使用的是消息接收者的模，签名是消息发送者的模，后者可能比前者小
- 如果先加密再签名，可能会导致加密后的消息大于签名模，无法使用 RSA 进行签名（RSA 要求 \(0 < M < n\)）
- 交换两者顺序，先签名再加密可以避免这个问题
签名常使用 HASH 函数值
- 用 \(h=H(M)\) 代替消息 \(M\) 进行签名

密钥生成：
- 取 \(p = 11, g = 2\)
- 选择私钥 \((x = 8)\)
- 计算公钥：
  - \(y = g^x \bmod p = 2^8 \bmod 11 = 3\)
  - 公钥是 \((y = 3, g = 2, p = 11)\)
对 \(M = 5\) 签名：
- 选择随机数 \(k = 9\)
- 确定 \(\gcd(9, 10) = 1\)
- 计算：\(K = g^{k} \bmod p = 2^9 \bmod 11 = 6\)
- 求解：
  
  \[ 5 = 8 \times 6 + 9 \cdot S \bmod 10; \]
  - 因为 \(9^{-1} \equiv 9 \bmod 10\)
  - 所以 \(S = k^{-1}(M - x \cdot K) \bmod (p - 1) = 9 \times (5 - 8 \times 6) \bmod 10 = 3\)
- 签名是 \((K = 6, S = 3)\)
要验证签名，确认：

\[ \begin{aligned} &y^{K} \cdot K^{S} \bmod p = 3 ^ {6} \cdot 6 ^ {3} \bmod 11 = 10 \\ &g^{M} \bmod p = 2 ^ {5} \bmod 11 = 10 \\ \end{aligned} \]

首先选取公开参数 \((p, q, g)\)：
- 选取大素数 \(p\)
  - 512 ～ 1024 bit（64 倍数）
- 选取素数 \(q\)
  - 160 bit
  - \(q\) 是 \(p - 1\) 的因子
- 选择 \(g = h^{(p - 1) / q}\)
  - 满足对任何 \(h < p - 1, h^{(p - 1) / q} \pmod p > 1\)
每个用户选取私钥并计算他们的公钥:
- 选取 \(x < q\)
- 计算 \(y = g^{x} \bmod p\)
- 公钥是 \((y, p, q, g)\)
- 私钥是 \((x)\)

签名消息 \(M\)
- 生成随机签名密钥 \(k\)，满足 \(k < q\)
- 计算
  
  \[ \begin{aligned} &K = (g^{k} \bmod p) \bmod q \\ &S = k^{-1} \cdot (\mathrm{HASH}(M) + x \cdot K) \pmod{q} \end{aligned} \]
发送签名 \((K, S)\) 及消息 \(M\)
验证签名, 计算:

\[ \begin{cases} w = S^{-1} \pmod{q} \\ u1 = (\mathrm{HASH}(M)\cdot w) \pmod{q} \\ u2 = K\cdot w \pmod{q} \\ v = g^{u1}\cdot y^{u2} \pmod{p}\pmod{q} \\ \end{cases}\quad \Rightarrow v = K? \]

以上的签名方法都是公钥技术
- 计算与数据量较大
需要私钥的认证方案
- 好的方法是使用快速的 hash 函数：
- 密钥与消息同时参加运算：
  
  \[ KeyedHash = \mathbf{Hash}(Key \parallel Message) \]
- 存在一些弱点
随后建议：

\[ KeyedHash = \mathbf{Hash} (Key_1 \parallel \mathbf{Hash} (Key_2 \parallel Message)) \]