数字签名算法¶
数字签名方案¶
- 公钥签名方案：
- 利用私钥生成签名
- 利用公钥验证签名
- 只有私钥的拥有者才能生成签名，所以能够用于证明谁生成的消息
- 任何知道公钥的人可以验证消息（他们要确认公钥拥有者的身份，这是公钥的密钥分配问题）
- 通常不对整个消息签名，因为这将会使交换信息长度增加一倍
- 使用消息的 hash 值
- 数字签名可以 提供消息的不可否认性
RSA 签名方案¶
- RSA 加密解密是可交换的
- 可以用于数字签名方案
RSA 密钥生成¶
- 选择两个大素数 \(p\) 和 \(q\)
- 计算 \(n = p \cdot q\)
- 计算 \(\phi(n) = (p - 1)(q - 1)\)
- 选择公钥指数 \(e\)，满足 \(1 < e < \phi(n)\) 且 \(\gcd(e, \phi(n)) = 1\)
- 计算私钥指数 \(d\)，满足 \(d \cdot e \equiv 1 \bmod \phi(n)\)
- 公钥是 \((e, n)\)
- 私钥是 \((d, p, q)\)
RSA 签名生成与验证¶
-
给定 RSA 方案 \(\{K=(e, n), K^{-1}=(d, p, q)\}\)
-
要签名消息 \(M\)：计算：
\[ \begin{cases} h = H(M) \\ S = h^{d} (\bmod n) \\ \end{cases} \Rightarrow (M, S) \] -
要验证签名, 计算：
\[ \begin{cases} h = H(M) \\ h' = S^{e}(\bmod n) \\ \end{cases} \Rightarrow h^{\prime} = h? \]
-
RSA 签名方案的使用¶
- 使用 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\)
- 假设 A 发送消息给 B
- 看起来，一个消息可用 RSA 先加密再签名而不改变大小
- 但是，加密使用的是消息接收者的模，签名是消息发送者的模，后者可能比前者小
- 如果先加密再签名，可能会导致加密后的消息大于签名模，无法使用 RSA 进行签名（RSA 要求 \(0 < M < n\)）
- 交换两者顺序，先签名再加密可以避免这个问题
- 签名常使用 HASH 函数值
- 用 \(h=H(M)\) 代替消息 \(M\) 进行签名
ElGamal 签名方案¶
- ElGamal 加密算法是不可交换的
- 存在一个相关的签名算法
- 安全性是 基于计算离散对数的困难性
ElGamal 密钥生成¶
- 选择共享的素数 \(p\) 和公开的生成元 \(g\)
- 每个用户选择一个随机数作为私钥 \(x\)
- 计算各自的公开密钥：\(y = g^x \bmod p\)
- 公钥是 \((y, g, p)\)
- 私钥是 \((x)\)
ElGamal 签名生成与验证¶
- 签名消息 \(M\)：
- 选择随机数 \(k\)，满足 \(\gcd(k, p - 1) = 1\)
- \(k\) 应该被销毁或保密，不能重复使用
- 计算 \(K = g^{k} \bmod p\)
- 用 Euclidean (inverse) 扩展算法求 \(S\)：
- \(M = x \cdot K + k \cdot S \bmod (p - 1)\) ;
- 即求 \(S = k^{-1}(M - x \cdot K) \bmod (p - 1)\)
- 发送 \((M, K, S)\)，其中 \((K, S)\) 是对 \(M\) 的签名
- 选择随机数 \(k\)，满足 \(\gcd(k, p - 1) = 1\)
- 验证 \((K, S)\) 是对 \(M\) 的签名:
- \(y^{K} \cdot K^{S} \equiv g^{M} \bmod p\)
- 同 ElGamal 加密方案，签名信息也是消息的 2 倍
- 通常对消息的 HASH 值进行签名
ElGamal 签名方案举例¶
- 密钥生成：
- 取 \(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} \]
DSA (Digital Signature Algorithm)¶
- DSA 是数字签名算法，DSS 是数字签名标准
- DSA 是 ElGamal 及 Schnorr algorithms 的变形
- 生成 320 bit 签名
- 安全性是 基于计算离散对数的困难性
- 被广泛接受
DSA 密钥生成¶
- 首先选取公开参数 \((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} (\bmod p) > 1\)
- 选取大素数 \(p\)
- 每个用户选取私钥并计算他们的公钥:
- 选取 \(x < q\)
- 计算 \(y = g^{x} \bmod p\)
- 公钥是 \((y, p, q, g)\)
- 私钥是 \((x)\)
DSA 签名生成与验证¶
-
签名消息 \(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? \]
DSA 安全性¶
- 基于离散对数
- 最初建议使用一个共同的 modulus p
- 现在建议不同的工作组使用不同的 \((p, q, g)\)
- Gus Simmons 发现存在潜信道，能够泄露私钥
带密钥的 HASH¶
- 以上的签名方法都是公钥技术
- 计算与数据量较大
-
需要私钥的认证方案
- 好的方法是使用快速的 hash 函数：
-
密钥与消息同时参加运算：
\[ KeyedHash = \mathbf{Hash}(Key \parallel Message) \] -
存在一些弱点
- 随后建议：
\[ KeyedHash = \mathbf{Hash} (Key_1 \parallel \mathbf{Hash} (Key_2 \parallel Message)) \]
HMAC¶
- HMAC 是使用带密钥的 HASH 函数的结果
- 成为 internet 标准（RFC2104）
-
结构:
\[ HMAC_K = \mathbf{Hash}((K^+ \oplus opad) \parallel \mathbf{Hash}((K^+ \oplus \text{ipad}) \parallel M)) \]- \(K^+\)：经过填充的密钥
- \(opad, ipad\)：特殊的填充值
- \(opad=01011010\) 重复 \(b/8\) 次
- \(ipad=00110110\) 重复 \(b/8\) 次
- 安全性是基于原来的 HASH 函数的安全性
- 任何 MD5, SHA-1, RIPEMD-160 都可以这样使用