计算机技术学习札记

密码学 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\)。

正确性验证：

\[\begin{aligned} C^d\ \mathrm{mod}\ n &=(m^e)^d\ \mathrm{mod}\ n=m^{ed}\ \mathrm{mod}\ n\\ &=m^{k\phi(n)+1}\ \mathrm{mod}\ n=m\ \mathrm{mod}\ n=m \end{aligned}\]

  • 如果 \(\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\) 使得

\[re_1+se_2=1\]

设 \(r\) 是负数。则

\[m\equiv c_1^rc_2^s=(c_1^{-1})^rc_2^s\ (\mathrm{mod}\ n)\]

明文泄露。

CCA

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

\[m_1=\dfrac{m_2}{m}\ \mathrm{mod}\ n\]

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

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 中，使用下面形式的二元方程：

\[y^2=x^3+ax+b\]

同时定义「无穷远点」或者称为「零点」。记这些点的集合为 \(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)\) 满足

\[\begin{aligned} x_R&=k^2-x_P-x_Q\\ y_R &=k(x_P-x_R)-y_P \end{aligned}\]

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

\[\begin{aligned} x_R&=k^2-2x_P \\ y_R &= k(x_P-x_R)-y_P \end{aligned}\]

有限域上的椭圆曲线

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

\[y^2\equiv x^3+ax+b\ (\mathrm{mod}\ 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\)，有

\[\begin{aligned} C_2-x\times C_1&=P_m+k\times x\times G-x \times k\times G=P_m \end{aligned}\]