5.5.7 公共密钥方法

虽然约定加密方法可以有效地用现代计算机实施, 并且对于双向通信仅需要单个密钥, 但仍然有几点值得注意:

(1)加密的安全性仅靠保持下一个密钥的秘密性.

(2) 在进行任何通信前, 密钥必须用足够安全的信道交换; 非人工通信是违规的.

(3) 此外, 绝不可能对第三方证实特定的消息已被特定发件人发送.

5.5.7.1 迪菲-赫尔曼密钥交换

用公开密钥加密的概念是迪菲 (Diffie) 和赫尔曼 (Hellman) 于 1976 年提出的. 每个参与者拥有两个密钥: 公布在一般容易接受的寄存器中的公共密钥, 以及只有参与者知道并且绝对保持机密的私人密钥. 具有这些性质的方法称为不对称密码 (参见第 517 页 5.5.2).

第 $i$ 个参与者的公开密钥 $K P_{i}$ 控制加密步骤 $E_{i}$ ,他的私人密钥 $K S_{i}$ 控制解密步骤 $D_{i}$ . 下列条件必须满足:

(1) $D_{i} \circ E_{i}$ 组成恒等映射.

(2) $E_{i}$ 和 $D_{i}$ 的有效实施方法是知道的.

(3) 私人密钥 $K S_{i}$ 不能由公开密钥 $K P_{i}$ 在可预见到的未来时日推出.

(4) $E_{i} \circ D_{i}$ 也产生恒等映射.

那么加密算法能够作为使用公开密钥的电子签名方法. 电子签名方法可使发信人查出对信息的伪证签名.

如果 $A$ 要向 $B$ 发送加密消息 $m$ ,那么 $A$ 从寄存器中取回 $B$ 的公开密钥 $K P_{B}$ , 应用加密算法 $E_{B}$ ,并计算 $E_{B} (m) = c . A$ 通过公开网络将密文 $c$ 发送给 $B, B$ 将应用他的解密函数 $D_{B}$ 中的私人密钥 $K S_{B}$ 恢复信息的明文: $D_{B} (c) = D_{B} (E_{B} (m)) = m$ . 为了预防信息被破坏, A 可以通过下列方式应用借助公开密钥的电子签名方法将他发送给 $B$ 的消息电子签名: $A$ 用他的私人密码加密信息 $m : D_{A} (m) = d . A$ 对 $d$ 附加他的签名 “A” 并且应用 $B$ 的公开密钥对总体加密: $E_{B} (D_{A} (m), “A”) =$ $E_{B} (d, “A”) = e$ . 于是签名且加密的文件由 A 发送给 B.

参与者 $B$ 应用他的私人密钥将消息解密,并且得到 $D_{B} (e) = D_{B} (E_{B} (d, "A")) =$ ( $d$ ,“A”). 依据这个文件 $B$ 可以证实 $A$ 是发送者,并且现在可以应用 $A$ 的公共密钥解密 $d : E_{A} (d) = E_{A} (D_{A} (m)) = m$ .

5.5.7.2 迪菲-赫尔曼单向函数

应用公开密钥的方法的加密算法必须确立具有 “陷门” 的单向函数. 在此所谓陷门是某个必须保持秘密的特殊的附加信息. 一个单射函数 $f : X \to Y$ 称为具有陷门的单向函数, 如果下列条件成立:

(1) 存在 $f$ 和 $f^{- 1}$ 的有效计算方法;

(2)在不知道保密的附加信息时不能从 $f$ 算出 $f^{- 1}$ .

在没有保密的附加信息时不可能产生从 $f$ 得到 $f^{- 1}$ 的有效方法.

5.5.7.3 RSA 码和 RSA 方法

1. RSA 码

Rivest, Shamir 和 Adleman 发展了一种基于欧拉-费马定理的保密信息的加密方法 (参见第 510 页 5.4.4, 2.). 这个方法称为RSA 算法 (用他们的姓氏的第一个字母命名), 可以使解密所需要的密钥部分公开而不危害消息的机密性. 有鉴于此, 在本书中也使用术语公开密钥码.

为了应用 RSA 算法,接受者 $B$ 选取两个非常大的素数 $p$ 和 $q$ ,算出 $m = p q$ , 并且选取数 $r$ 使与 $φ (m) = (p - 1) (q - 1)$ 互素,而且 $1 < r < φ (m)$ . B 公布数 $m$ 和 $r$ ,因为它们对于解密是必须的.

为从发送者 $A$ 向接受者 $B$ 传送一个保密信息,首先必须将消息文本转换为数字串,并且将数字串分裂成 $N$ 个相同长度的 (小于 100 个十进数位) 的区组. 现在 A 算出 $m$ 除以 $N^{r}$ 的余数 $R$ :

\begin{matrix} (5.276a) & N^{r} \equiv R (\mod m) . \end{matrix}

发送者 $A$ 对于由原文本得到的 $N$ 个区组中的每一个计算出数 $R$ ,并且将它发送给 B. 如果接受者有线性同余式 $r s \equiv 1 (\mod φ (m))$ 的解,那么他就能将消息 $R$ 解密. 数 $N$ 是 $m$ 除以 $R^{s}$ 的余数:

\begin{matrix} (5.276b) & R^{s} \equiv {(N^{r})}^{s} \equiv N^{1 + k φ (m)} \equiv N \cdot {(N^{φ (m)})}^{k} \equiv N (m) . \end{matrix}

这里应用了欧拉-费马定理 (参见第 510 页 5.4.4,2.) 以及 $N^{φ (m)} \equiv 1 (m)$ . 最后, B 将数字串转换成文本.

$◼$ 接受者 $B$ 希望得到从 $A$ 发送来的机密信息,选取素数 $p = 29$ 及 $q = 37$ (实际上这对于实用目的太小了),算出 $m = 29 \cdot 37 = 1037$ (以及 $φ (1037) = φ (29) \cdot φ (37) =$ $1008)$ ,并且取 $r = 5$ (它满足要求 $gcd (1008, 5) = 1$ ). B 将值 $m = 1037$ 和 $r = 5$ 传递给 A.

A 想将机密消息 $N = 8$ 发送给 B. A 通过计算 $N^{r} = 8^{5} \equiv 578 (1073)$ 将 $N$ 加密为 $R = 578$ ,并且确实将值 $R = 578$ 发送给 B. B 解同余式 $5 \cdot s \equiv (1008)$ ,得到解 $s = 605$ ,于是确定 $R^{s} = 578^{605} \equiv 8 = N (1073)$ .

注 RSA 码的安全性与非法窃听者分解 $m$ 所需要的时间有关. 依据当代计算机的速度, RSA 算法的使用者应该选取素数 $p$ 和 $q$ 至少具有 100 个十进制数位,迫使窃密者要花费大约 74 年实施解密. 但对于合法的使用者确定与 $φ (p q) =$ $(p - 1) (q - 1)$ 互素的 $r$ ,其付出两相比较是小的.

2. RSA 方法

RSA 方法是最普及的非对称加密方法.

(1) 假设 设 $p$ 和 $q$ 是两个素数,并且 $p q \approx 10^{2048}$ ,以及 $n = p q . p$ 和 $q$ 的十进制数位相差应该是一个小的数; 还有, $p$ 和 $q$ 相差不太大. 此外,数 $p - 1$ 和 $q - 1$ 应当含相当大的素因子,同时 $p - 1$ 和 $q - 1$ 的最大公因子应当相当小. 设 $e > 1$ 与 $(p - 1) (q - 1)$ 互素,并且令 $d$ 满足 $d \cdot e \equiv 1 (\mod (p - 1) (q - 1))$ . 现在将 $n$ 和 $e$ 作为公共密钥,而将 $d$ 作为私人密钥.

(2) 加密算法

\begin{matrix} (5.277a) & E : {0, 1, \dots, n - 1} \to {0, 1, \dots, n - 1}, E (x) := x^{e} (\mod n) . \end{matrix}

(3) 解密算法

\begin{matrix} (5.277b) & D : {0, 1, \dots, n - 1} \to {0, 1, \dots, n - 1}, D (x) := x^{d} (\mod n) . \end{matrix}

于是对于信息 $m$ 有 $D (E (m)) = E (D (m)) = m$ .

当 $n > 10^{200}$ 时这个加密方法中的函数成为一个侯选的具有陷门的单向函数 (参见第 522 页 5.5.7.2). 要求的附加信息是怎样分解 $n$ 的知识. 没有这种知识就不可能解同余式 $d \cdot e \equiv 1 (\mod (p - 1) (q - 1))$ . 只要上面的条件被满足, RSA 方法实用中将被看作是安全的. 与其他方法相比较, 它的缺点是密钥相对较大, 并且 RSA 比 DES 慢 1000 倍.

5.5.7 公共密钥方法 ​

5.5.7.1 迪菲-赫尔曼密钥交换 ​

5.5.7.2 迪菲-赫尔曼单向函数 ​

5.5.7.3 RSA 码和 RSA 方法 ​

1. RSA 码 ​