密码学 - 数字签名公式整理

RSA 签名方案
- 密钥生成:
  - 选择两个大素数 $ p $ 和 $ q $
  - 计算 $ n = pq $
  - 计算 $ \phi(n) = (p-1)(q-1) $
  - 选择一个整数 $ e $（满足 $ 1 < e < \phi(n) $ 且 $ \gcd(e, \phi(n)) = 1 $）
  - 计算私钥 $ d $（满足 $ ed \equiv 1 \pmod{\phi(n)} $）
  - 公钥为 $ (e, n) $，私钥为 $ (d, n) $
- 签名:
  - 对消息 $ m $ 进行哈希得到消息摘要 $ H(m) $
  - 计算签名 $ s = H(m)^d \mod n $
- 验证:
  - 对签名 $ s $ 进行验证计算 $ H(m) $ 的哈希值： $ v = s^e \mod n $
  - 若 $ v \equiv H(m) \mod n $，则验证通过

ElGamal签名方案
- 密钥生成:
  - 选定大素数 $ p $ 和生成元 $ g $
  - 选择私钥 $ x $（随机数），计算公钥 $ y = g^x \mod p $
- 签名:
  - 选择一个随机数 $ k $（满足 $ 1 < k < p-1 $ 且 $ \gcd(k, p-1) = 1 $）
  - 计算 $ r = g^k \mod p $
  - 计算 $ s = k^{-1}(H(m) - xr) \mod (p-1) $
  - 签名为 $ (r, s) $
- 验证:
  - 计算 $ v_1 = y^r r^s \mod p $
  - 计算 $ v_2 = g^{H(m)} \mod p $
  - 若 $ v_1 \equiv v_2 \mod p $，则验证通过
DSA（数字签名算法）
- 密钥生成:
  - 选定大素数 $ p $ 和生成元 $ g $
  - 选定一个160位素数 $ q $（满足 $ q | (p-1) $）
  - 选择私钥 $ x $（随机数），计算公钥 $ y = g^x \mod p $
- 签名:
  - 选择一个随机数 $ k $（满足 $ 1 < k < q $ 且 $ \gcd(k, q) = 1 $）
  - 计算 $ r = (g^k \mod p) \mod q $
  - 计算 $ s = k^{-1}(H(m) + xr) \mod q $
  - 签名为 $ (r, s) $
- 验证:
  - 计算 $ w = s^{-1} \mod q $
  - 计算 $ u_1 = H(m)w \mod q $
  - 计算 $ u_2 = rw \mod q $
  - 计算 $ v = ((g^{u_1} y^{u_2}) \mod p) \mod q $
  - 若 $ v \equiv r \mod q $，则验证通过

ECDSA（椭圆曲线数字签名算法）
- 密钥生成:
  - 选定椭圆曲线参数 $ E $ 和基点 $ G $
  - 选择私钥 $ d $（随机数），计算公钥 $ Q = dG $
- 签名:
  - 选择一个随机数 $ k $（满足 $ 1 < k < n $，$ n $ 是基点 $ G $ 的阶）
  - 计算 $ R = kG $，取 $ r = R_x \mod n $（其中 $ R_x $ 是点 $ R $ 的 x 坐标）
  - 计算 $ s = k^{-1}(H(m) + dr) \mod n $
  - 签名为 $ (r, s) $
- 验证:
  - 验证 $ r, s $ 是否在有效范围内（$ 1 \leq r, s < n $）
  - 计算 $ w = s^{-1} \mod n $
  - 计算 $ u_1 = H(m)w \mod n $
  - 计算 $ u_2 = rw \mod n $
  - 计算 $ P = u_1G + u_2Q $
  - 取 $ v = P_x \mod n $（其中 $ P_x $ 是点 $ P $ 的 x 坐标）
  - 若 $ v \equiv r \mod n $，则验证通过