第6章：数字签名

数字签名的基本概念

背景

  • 在政治、军事、外交、商业以及日常事务中，签名用于认证、核准、生效。在电子世界里，需要数字签名来替代手写签名，实现对数字信息的签名。

特性

  1. 不可伪造性：只有签名者能生成合法签名。
  2. 认证性：接收者可以确认签名来自签名者。
  3. 不可重复使用性：一个消息的签名不能用于其他消息。
  4. 不可修改性：签名后的消息不能被修改。
  5. 不可否认性：签名者不能否认自己的签名。

数字签名方案组成

  • 包含签名算法和验证算法。
  • 签名算法输入签名者的私钥和消息，输出消息的数字签名。
  • 验证算法输入签名者的公钥、消息和签名，输出真或伪。

数字签名方案分类

  1. 按用途：普通数字签名、盲签名、不可否认签名、群签名、代理签名等。
  2. 按消息恢复功能：具有消息恢复功能和不具有消息恢复功能。
  3. 按随机数使用：确定性数字签名和随机化数字签名。
RSA数字签名

RSA算法描述

  1. 密钥生成

    • 选择两个大素数 $ p $ 和 $ q $。
    • 计算 $ n = pq $ 和欧拉函数 $ \phi(n) = (p-1)(q-1) $。
    • 选择整数 $ e $，满足 $ 1 < e < \phi(n) $ 且 $ \gcd(e, \phi(n)) = 1 $。
    • 计算 $ d $，使得 $ ed \equiv 1 \mod \phi(n) $。
    • 公钥为 $ (e, n) $，私钥为 $ d $。

  2. 签名

    • 对于消息 $ m $，签名为 $ s \equiv m^d \mod n $。

  3. 验证

    • 对于消息签名对 $ (m, s) $，如果 $ m \equiv s^e \mod n $，则 $ s $ 是 $ m $ 的有效签名。

RSA数字签名的缺陷

  • 伪造签名：任何人可以伪造随机消息 $ m $ 的签名 $ s $，方法是先选取 $ s $，再用公钥 $ (e, n) $ 计算 $ m \equiv s^e \mod n $。
  • 签名同态性：若已知 $ m_1 $ 和 $ m_2 $ 的签名分别为 $ s_1 $ 和 $ s_2 $，则 $ m_1m_2 $ 的签名为 $ s_1s_2 $。
  • 签名消息长度限制：每次只能对 $ \log_2 n $ 位长的消息进行签名。

引入Hash以解决上述缺陷

  • 签名前先对消息进行Hash变换，对变换后的消息签名。签名为 $ s \equiv h(m)^d \mod n $。验证时，先计算 $ h(m) $，再检查 $ h(m) \equiv s^e \mod n $ 是否成立。
其他数字签名方案

ElGamal签名方案

  1. 参数与密钥生成

    • 选择大素数 $ p $ 和本原元 $ g $。
    • 随机选择整数 $ x $，计算 $ y \equiv g^x \mod p $。
    • 公钥为 $ y $，私钥为 $ x $。

  2. 签名

    • 对于消息 $ m $，随机选择整数 $ k $，计算 $ r \equiv g^k \mod p $， $ s \equiv (h(m) - xr)k^{-1} \mod (p-1) $。
    • 签名为 $ (r, s) $。

  3. 验证

    • 对于签名对 $ (m, (r, s)) $，验证 $ y^r r^s \equiv g^{h(m)} \mod p $ 是否成立。

Schnorr签名方案

  • 基于离散对数问题，生成签名时选择随机数使得签名不可预测。

Neburg–Rueppel签名方案

  • 类似于ElGamal签名，基于离散对数问题的随机化数字签名方案。

基于身份的签名方案

  • Shamir签名方案：基于身份的签名，利用身份信息生成签名。
  • Cha-Cheon签名方案：改进的基于身份的签名方案，增强了安全性。

特殊用途的签名方案

  • 代理签名：允许原始签名者委托代理签名者代签。
  • 多重签名：多个签名者对同一消息共同签名。
  • 盲签名：签名者对盲化后的消息签名，不知道消息内容。
  • 环签名：一组签名者中的任何一个可以代表群体签名，无法识别具体签名者。
数字签名标准（DSS）

DSS算法

  • 1991年NIST提出，基于ElGamal和Schnorr签名方案，安全性基于离散对数问题。
  • 只可用于签名，不可用于加密。

参数与密钥生成

  • 选择素数 $ p $ 和 $ q $，其中 $ q $ 是 $ p-1 $ 的因子。
  • 选择生成元 $ g $，随机选取私钥 $ x $，计算公钥 $ y \equiv g^x \mod p $。

签名

  • 对消息 $ m $，随机选择整数 $ k $，计算 $ r \equiv (g^k \mod p) \mod q $， $ s \equiv 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 = r $ 是否成立。