视频

应满足的条件

1. 签名与文件不可分割。

对消息进行某种变换完成签名；使签名是待签名文件的函数。

2. 签名者时候不可否认自己的签名。

签名使用发方独有的秘密信息完成，只对应唯一的公开验证信息。

3. 接收者能验证签名，而其他人都无法伪造签名。

签名与唯一的公开信息对应，能够验证；签名与发方独有秘密信息相关，无法伪造。

4. 双方对于签名真伪发生争执时，有可信第三方能解决双方争执。

签名对应的验证密钥由可信第三方确认并发布。靠法律解决争执。

数字签名方法

1. 可交换公钥加密算法

必须是满足 $D_{k_d} (E_{k_e} (x)) = E_{k_e} (D_{k_d} (x)) = x$ 的公钥密码算法。

就是将私钥 $k_d$ 作为签名密钥，公钥 $k_e$ 作为签名识别密钥。

2. 专用数字签名算法

RSA 数字签名算法

记用户 A 的参数为 $(N_A, e_A, d_A)$，用户 B 的参数为 $(N_B, e_B, d_B)$，$E$ 为加密 $D$ 为脱密。显然每方的 $N$ 都要不相同。

以 A 发送给 B 为例，签名

$$c = m^{d_A} \mod N_A$$

验证

$$m = c^{e_A} \mod N_A$$

发送时，将 $(m, c)$ 作为一个整体。

这个算法也可以实现带签名的保密通信，但是要使逆变换唯一，需要保证模数的顺序。

当 $N_A < N_B$ 时，先签名，后加密。即用户 A 先用自己私钥 $d_A$ 对消息 $m$ 签名，得到 $y = m_{d_A} \mod N_A$，再用对方公钥 $e_B$ 对签名信息 $y$ 加密得到 $c = y^{e_B} \mod N_B$，最后把签名和加密完成的信息 $c$ 发送给对方 B。

反之亦然。哪个模数小就先进行哪一方的操作。

若后签名，攻击方可以通过公开信息解出中间信息重新签名，扰乱通信。针对这种情况，采用两个模数，保证所有用户签名模数均小于其他用户加密模数，即可保证一定先签名后加密，无法进行重签名攻击。

缺陷

1. 任何人都可以利用 A 的签名密钥 $k_e$，给定任意 $y$，任何人都可以计算出 $x = y^{k_e} mod N$，从而伪造对消息 $x$ 的签名 $y$（对 $x$ 签名是 $y^{k_e \times k_d}$，而公私钥相乘为 $1$，正好就是 $y$）。

2. 如果 A 对两份文件 $x_1, x_2$ 签名分别为 $y_1, y_2$，故任何第三方知道 $x_1, x_2, y_1, y_2$ 都可以伪造 $x_1 x_2 mod N$ 的签名 $y_1 y_2 mod N$。

但是伪造出签名的源文件攻击者都无法控制。

3. 长文件签名时非常慢。ECB 加密模式容易遭受替换攻击。

所以一般对文件摘要签名。

DSA 数字签名算法

基于有限域离散对数问题。

参数选取

1. 大素数 $p: 2^{L - 1} < p < 2^L, L$ 至少为 512 bit 且为 64 的倍数，推荐 1024 bit。

2. 选取素数 $q$: ($q$ 是 $p - 1$ 的一个 160 bit 的素数因子)。

3. 选取整数 $g = h^{(p - 1)/q} \mod p$，($g > 1$, $1 < h < p - 1$)

4. 随机选取整数 $x, (0 < x < q)$

5. 计算 $y = g^x \mod p$

公开参数 $p, q, g, y$，保密 $x$

签名

设用户 A 对消息 $m$ 签名，则：

1. A 秘密选取一个小于 $q$ 的随机数 $k$

2. A 计算

   $$\left\{ \begin{array}{l} r = (g^k \mod p) \mod q \\ s = k^{-1} (H(m) + x r) mod q \end{array} \right.$$

验证

3. B 计算 $$\left\{ \begin{array}{l} w = s^{-1} \mod q \\ u_1 = H(m) w \mod q \\ u_2 = r w \mod q \end{array} \right.$$ $$v = ((g^{u_1} \times y^{u_2}) \mod p) \mod q$$

如果 $v = r$，则 B 确认 $(r,s)$ 是 A 对 m 的签名，否则无效。

为什么？

因为

$$\begin{array}{l} s = k^{-1} (H(m) + x r) mod q \\ ks = (H(m) + x r) mod q \end{array}$$

从而

$$\begin{array}{l} \quad ((g^{u_1} y^{u_2}) \mod p) \mod q \\ = ((g^{u_1} y^{x u_2}) \mod p) \mod q \\ = ((g^{H(m) w} y^{x r w}) \mod p) \mod q \\ = ((g^{k s w}) \mod p) \mod q \\ = ((g^k) \mod p) \mod q \\ = r \end{array}$$

ECDSA 密钥数字签名算法

实际还是把有限域上的运算转换成椭圆曲线群上运算。

参数选取

1. 构造有限域 $F$。

2. 生成域 $F$ 上的椭圆曲线 $E$。

3. 取椭圆曲线中的一个点 $P$，要求 $P$ 有大素数阶 $q$。

4. 选取一个整数 $d$，计算 $Q = d P$

公开 $F, E, P, Q$，保密 $d$

签名

1. A 秘密选取一个小于 $q$ 的随机数 $k$

2. A 计算

   $$\begin{array}{l} k P = (u, v) \\ r = u \mod q \\ s = k^{-1} (H(m) + r d) \mod q \end{array}$$

则其签名为 (r,s)

验证

和 DSA 完全一样没有任何区别

3. B 计算 $$\left\{ \begin{array}{l} w = s^{-1} \mod q \\ u_1 = H(m) w \mod q \\ u_2 = r w \mod q \end{array} \right.$$ $$v = ((g^{u_1} \times y^{u_2}) \mod p) \mod q$$

$(u, v) = u_1 P + u_2 Y$，则 B 确认 $(r, s)$ 是 A 对 m 的签名，否则无效。

群签名

就是第三方产生许多密钥对，每个成员有一些私钥，验证时团体共用一张公钥表。

盲签名

A 只让 B 签名而 B 不知道文件内容。常用于电子货币、电子选举等。

签名

假设 B 的公钥 $e$，私钥 $d$，模 $n$。

A 选用盲因子 $k$。计算

$$t = M k^e \mod n$$

然后把 $t$ 发送给 B 签名

$$S(t) = t^d = (M k^e)^d mod n$$

A 取得签名再计算出脱盲的签名

$$S = \frac{t^d}{k} \mod n = \frac{M^d k}{k} \mod n = M^d \mod n$$