密码学 5：公钥密码

RSA 算法 #

密钥生成 #

选择两个大素数 $p$ 和 $q$。计算 $n=pq$，$\phi(n)=(p-1)(q-1)$。

随机选择 $e$，使得 $1<e<\phi(n)$，且 $\gcd(e, \phi(n))=1$。计算 $e$ 模 $\phi(n)$ 的乘法逆 $d$。

$(n, e)$ 为公钥，$d$ 为私钥。

加解密过程 #

对于加密，要求消息 $m$ 满足 $m<n$，密文 $C=m^e\ \mathrm{mod}\ n$。

对于解密，$m=C^d\ \mathrm{mod}\ n$。

正确性验证：

• 如果 $\gcd(m, n)=1$，上述结论是显然的（欧拉定理）。

• 如果 $\gcd(m, n)\ne 1$，因为 $n$ 只有两个非 1 因子 $p$ 和 $q$，不失一般性地设 $\gcd(m, q)=1$，记 $m=xp$，有 $1\leqslant x<q$。由欧拉定理有 $m^{k\phi(q)}\equiv 1\ (\mathrm{mod}\ q)$，即 $(m^{k\phi(q)})^{\phi(p)}=m^{k\phi(n)}\equiv 1\ (\mathrm{mod}\ q)$，故存在 $r\in\mathbf{Z}$，使得 $m^{k\phi(n)+1}=1+rq$，左右同乘 $m=xp$，有

  $$ m^{k\phi(n)+1}=m+mrq=m+xprq=m+rxn $$

  即 $m^{k\phi(n)+1}\equiv m\ (\mathrm{mod}\ n)$。

共模攻击 #

如果 RSA 中使用共模 $n$ 生成多个密钥，设两个用户使用共模各自生成了公钥 $e_1$ 和 $e_2$，且 $\gcd(e_1, e_2)=1$。现在，他们对同一条明文消息 $m$ 进行加密，得到 $C_1$ 和 $C_2$。通过 $e_1$ 和 $e_2$，可以使用扩展的欧几里得算法得到 $r$ 和 $s$ 使得

设 $r$ 是负数。则

明文泄露。

CCA #

RSA 无法抵御 CCA。假设敌手获取到明文 $m_1$ 的密文 $C_1$，他可以选择一段明文 $m$，然后构造 $C_2=C_1\cdot m^e\ \mathrm{mod}\ n$，令私钥持有者解密 $C_2$，得到（无意义的）明文 $m_2$，则

所以持有私钥的人真的会这么听话地帮你解密吗 密码学中最大的不确定因素是人。

Rabin 算法 #

密钥生成 #

选择两个大素数 $p$ 和 $q$，形式为 $4k+3$。计算 $n=pq$，$n$ 为公钥，$p$ 和 $q$ 为私钥。

加解密过程 #

对于明文消息 $m$，其密文 $C=m^2\ \mathrm{mod}\ n$。解密过程即求 $x^2\equiv C\ (\mathrm{mod}\ n)$ 的 $x$，即 $x^2\equiv C\ (\mathrm{mod}\ p)$ 或者 $x^2\equiv C\ (\mathrm{mod}\ q)$ 的四个解之一。

DH 密钥交换协议 #

离散对数困难问题 #

对于 $b=a^i\ \mathrm{mod}\ N$，在已知 $a$、$b$ 和 $N$ 的条件下求 $i$ 是困难的。即，求解离散对数问题 $\mathrm{dlog}_{a, N}b$ 是困难的。

交换步骤 #

首先选择随机素数 $p$，随机选择它的一个本原根 $g$，双方公开决定它们。

随后，双方各自生成一个私有参数 $x, y\in Z_p$，然后公开 $h_x=g^x$ 和 $h_y=g^y$。由离散对数难问题的性质，敌手此时不能计算得到 $x$ 和 $y$ 本身。

双方分别公开 $h_x$ 和 $h_y$，然后，各自均可计算出 $g^{xy}$。至此，双方完成密钥交换。

ElGamal 加密算法 #

密钥的产生 #

选择一素数 $p$ 和小于它的随机数 $sk$，$g$ 是 $p$ 的本原根，计算 $pk=g^{sk}\ \mathrm{mod}\ p$。$sk$ 作为私钥，$pk$ 作为公钥。

加密 #

对于明文消息 $m\in{1,\cdots,p-1}$，随机选择整数 $k\in{2,\cdots,p-2}$，计算

• 一次性密钥 $C_1=g^k\ \mathrm{mod}\ p$
• 密文 $C_2=pk^k\cdot m\ \mathrm{mod}\ p$。

将 $C_1$ 和 $C_2$ 传输出去。

解密 #

记 $K=pk^{k}$，有 $C_2=K\cdot m\ \mathrm{mod}\ p$，即 $m=C_2\cdot K^{-1}\ \mathrm{mod}\ p$。

而 $K=pk^k={g^{sk}}^k={g^k}^{sk}=C_1^{sk}$

所以 $m=(C_1^{sk})^{-1}\cdot C_2\ \mathrm{mod}\ p$。

椭圆曲线加密算法 #

椭圆曲线的定义 #

「椭圆曲线」是一个二元方程的解的集合。在 ECC 中，使用下面形式的二元方程：

同时定义「无穷远点」或者称为「零点」。记这些点的集合为 $E(a, b)$。当 $4a^3+27b^2\neq 0$ 时，可以基于 $E(a, b)$ 定义一个二元运算，使其成为一个交换群。将这个运算记为加法 $+$。

加法运算的规则 #

定义加法运算：如果椭圆曲线上的 3 个点位于同一直线，那么它们的和为 $O$。

• $O$ 是加法的单位元，即对于任意点 $P$ 有 $P+O=P$。
• 对于点 $P(x_P, y_P)$，它的逆元是 $-P=(x_P, -y_P)$。
• 对于点 $P$ 和 $Q$，当它们的 $x$ 坐标不同时，将它们相连得到一条直线，此直线与椭圆曲线本身相交的点关于 $x$ 轴的对称点是它们的和。当它们的 $x$ 坐标相同时，它们连线与 $x$ 轴的交点是它们的和。

将其代数化定义，当 $P$ 和 $Q$ 不重叠时，它们连线的斜率 $k=\dfrac{y_Q-y_P}{x_Q-x_P}$，它们的和 $R(x_R, y_R)$ 满足

而当 $P$ 和 $Q$ 重叠时，它们的连线就是那一点的切线，斜率 $k=\dfrac{3x_P^2+a}{2y_P}$，有

有限域上的椭圆曲线 #

上面讨论的椭圆曲线的点都在实数域上，这显然是难以计算的。因此，定义有限域 $Z_p$ 上的椭圆曲线。在 $Z_p$ 上定义

其中 $(x, y)\in Z_p$，$a, b\in Z_p$ 且 $4a^3+27b^2\not\equiv 0\ (\mathrm{mod}\ p)$。该方程所有在 $Z_p$ 上的解和无穷远点构成了一个 $Z_p$ 上的椭圆曲线，记作 $E_p(a, b)$。$E_p(a, b)$ 中的点的个数约等于 $Z_p$ 元素的个数即 $p$。

椭圆曲线上的离散对数困难问题和 DH 密钥交换 #

记乘法是多次加法，即 $k\times P$ 为 $k$ 个 $P$ 相加。则，考虑 $Q=k\times P$，其中 $Q, P\in E_p(a, b)$，$k<p$。已知 $k$ 和 $P$ 求 $Q$ 是容易的，但是已知 $Q$ 和 $P$ 求 $k$ 是困难的。

基于此，选择大素数 $p$ 和 $a, b$ 构造 $E_p(a, b)$，记 $E_p(a, b)$ 的元素个数为 $n$。选择本原点 $G$，满足 $n\times G=O$。用户 A 和 B 各自选择一个小于 $n$ 的整数 $n_A$ 和 $n_B$，各自产生公钥 $pk_A=n_A\times G$，$pk_B=n_B\times G$，然后公开交换。双方可以计算出相同的密钥 $n_A\times pk_B=n_B\times pk_A$。

椭圆曲线上的 ElGamal 加密 #

选择 $E_p(a, b)$ 上的生成元 $G$，选择小于 $n$ 的整数 $x$ 为私钥，$Q = x\times G$ 为公钥。将消息 $m$ 编码为此曲线上的点 $P_m$。

加密：随机选择 $n<k$，计算

• 一次性密钥 $C_1=k\times G$；
• 密文 $C_2=P_m+kQ$。

将 $C_1$ 和 $C_2$ 传输出去。解密只需要计算 $C_2-x\times C_1$，有