【密码学】7. 数字签名

数字签名

数字签名的基本概念

1. 核心特性
   • 不可伪造性：仅签名者能生成合法签名，他人无法伪造。
   • 认证性：接收者可确认签名来自签名者。
   • 不可重复使用性：一个消息的签名不能用于其他消息。
   • 不可修改性：消息签名后无法被篡改。
   • 不可否认性：签名者事后不能否认自己的签名。
2. 签名体制组成
   • 签名算法：输入消息 $m$ 和密钥 $k$，输出签名 $s=Si{g}_k(m)$。
   • 验证算法：输入消息 $m$ 和签名 $s$，输出 “真” 或 “伪”（$Ver(m,s)$）。
   • 安全性基础：从 $m$ 和 $s$ 难以推出密钥 $k$，或伪造可验证的消息 - 签名对。
3. 分类方式
   • 按用途：普通数字签名、特殊用途签名（盲签名、不可否认签名、群签名、代理签名等）。
   • 按消息恢复功能：具有消息恢复功能、不具有消息恢复功能。
   • 按随机数使用：确定性数字签名、随机化数字签名。

RSA 数字签名

1. 参数与密钥生成
   • 选两个保密大素数 $p$ 和 $q$，计算 $n=pq$，欧拉函数 $\phi (n)=(p-1)(q-1)$。
   • 随机选 $e$（$1<e<\phi (n)$ 且 $gcd(e,\phi (n))=1$），计算 $d$ 满足$de\equiv 1mod\phi (n)$。
   • 公钥为 $(e,n)$，私钥为 $d$。
2. 签名与验证
   • 签名：对消息 $m\in Z_n$，$s=Si{g}_k(m)=m^{d}modn$。
   • 验证：若 $m=s^{e}modn$，则签名有效。
3. 缺陷
   • 伪造随机消息签名：选 $s$，计算 $m=s^{e}modn$，则 $s$ 是 $m$ 的伪造签名。
   • 对消息组合脆弱：若 $m_1$ 的签名为 $s_1$，$m_2$ 的签名为 $s_2$，则 $m_1{m}_2$ 的伪造签名为 $s_1{s}_{2}modn$（因 $(m_1{m}_2{)}^d=m_1^d{m}_2^{d}modn$）。
   • 消息长度限制：仅能对 $lo{g}_{2}n$ 位消息签名，长消息需分组，导致签名变长、运算量增加。
4. 改进方法
   • 对消息的 Hash 值签名：签名 $s=h(m{)}^{d}modn$，验证时检查 $h(m)=s^{e}modn$（$h$ 为 Hash 函数）。

ElGamal 数字签名

1. 参数与密钥生成
   • 选大素数 $p$，$g$ 为 $Z_p\ast$ 的本原元（$p$ 和 $g$ 公开）。
   • 随机选 $x$（$1\le x\le p-2$），计算 $y=g^{x}modp$。
   • 公钥为 $y$，私钥为 $x$。
2. 签名与验证
   • 签名：对消息 $m$，随机选 $k$（$1\le k\le p-2$），计算 $r=g^{k}modp$，$s=(h(m)-xr)k^{-1}mod(p-1)$（$h$ 为 Hash 函数），签名为$(r,s)$。
   • 验证：若 $y^r\ast r^s\equiv g^{h(m)}modp$，则签名有效。

数字签名标准（DSS）

1. 参数与密钥生成
   • $p$：$L$ 位素数（$512\le L\le 1024$，$L$ 是 64 的倍数），$q$：160 位素数且 $q|(p-1)$。
   • 选 $h$（$1<h<p-1$），计算 $g=h^{\frac{(p-1)}{q}}modp$（$g$ 为生成元）。
   • 随机选 $x$（$0<x<q$），计算 $y=g^{x}modp$。
   • 公开参数 $p,q,g$，公钥 $y$，私钥 $x$。
2. 签名与验证
   • 签名：对消息 $m$，随机选 $k$（$0<k<q$），计算 $r=(g^{k}modp)modq$，$s=k^{-1}(h(m)+xr)modq$（$h$ 为 SHA-1），签名为 $(r,s)$。
   • 验证：计算 $w=s^{-1}modq$，$u_1=h(m)wmodq$，$u_2=rwmodq$，$v=(g^{u_1}\ast y^{u_2}modp)modq$，若 $v=r$，则签名有效。

其他数字签名

基于离散对数问题的数字签名

1. 离散对数签名方案（通用框架）
   • 参数：大素数 $p$，$q$ 为 $p-1$ 的大素因子，$g\in Z_p\ast$ 且 $g^q\equiv 1modp$；私钥 $x$（$1<x<q$），公钥 $y=g^{x}modp$。
   • 签名：计算 $h(m)$，选 $k$（$1<k<q$），得 $r=g^{k}modp$，从 $ak\equiv (b+cx)modq$ 解 $s$（$a,b,c$ 为参数，如 $a=r,b=h(m),c=-r$），签名为 $(r,s)$。
   • 验证：检查 $r^a\equiv g^b\ast y^{c}modp$。
2. Schnorr 签名方案
   • 参数：$p\ge 2^{512}$（素数），$q\ge 2^{160}$（素数且 $q|p-1$），$g\in Z_p\ast$ 且 $g^q\equiv 1modp$；私钥 $x$，公钥 $y=g^{x}modp$。
   • 签名：选 $k$，得 $r=g^{k}modp$，$e=h(r,m)$，$s=(xe+k)modq$，签名为 $(e,s)$。
   • 验证：计算 $r^{\prime }=g^s\ast y^{-e}modp$，若 $h(r^{\prime },m)=e$，则有效。
3. Nyberg-Rueppel 签名方案
   • 参数：同 Schnorr（$p,q,g$，私钥 $x$，公钥 $y=g^{x}modp$）。
   • 签名：计算 $R(m)$（冗余函数），选 $k$，得 $r=g^{-k}modp$，$e=r\ast R(m)modp$，$s=(xe+k)modq$，签名为 $(e,s)$。
   • 验证：检查 $0<e<p$ 和 $0\le s<q$，计算 $v=g^s\ast y^{e}modp$，$t=e\ast v^{-1}modp$，若 $t\in R$ 的值域，则恢复 $m=R^{-1}(t)$。

基于大整数分解问题的数字签名

1. Feige-Fiat-Shamir 签名方案
   • 参数：$n=pq$（$p,q$ 为保密素数），$k$ 为正整数；私钥 $x_1,...,x_k$，公钥 $y_i=x_i^{-2}modn$。
   • 签名：选 $r$，得 $u=r^{2}modn$，$e=h(m,u)$（$e_i\in 0,1$），$s=r\ast \Pi x_i^{e^i}modn$，签名为 $(e,s)$。
   • 验证：计算 $u^{\prime }=s^2\ast \Pi y_i^{e^i}modn$，若 $h(m,u^{\prime })=e$，则有效。
2. Guillou-Quisquater 签名方案
   • 参数：$n=pq$，$k$ 满足 $gcd(k,(p-1)(q-1))=1$；私钥 $x$，公钥 $y=x^{-k}modn$。
   • 签名：选 $r$，得 $u=r^{k}modn$，$e=h(m,u)$，$s=r\ast x^{e}modn$，签名为 $(e,s)$。
   • 验证：计算 $u^{\prime }=s^k\ast y^{e}modn$，若 $h(m,u^{\prime })=e$，则有效。

具有特殊用途的数字签名

1. 群签名
   • 特点：群体成员可代表群体签名，接收者用群公钥验证但不知具体签名者，争议时管理员可识别签名者。
   • 组成：建立（生成群公钥 / 私钥）、加入（用户成为成员）、签名、验证、打开（识别签名者）。
   • 性质：正确性、不可伪造性、匿名性、不可关联性、可跟踪性、可开脱性、抗联合攻击。
2. 代理签名
   • 组成：系统建立（参数和密钥）、签名权力委托、代理签名生成、代理签名验证。
3. 盲签名
   • 用途：匿名性场景（如电子投票、电子现金），签名者不知消息内容及签署对象。
   • 步骤：消息盲化（用户用盲因子处理消息）、盲消息签名（签名者对盲化消息签名）、恢复签名（用户移除盲因子得真实签名）。