密码学题解 - 椭圆曲线 ElGamal 密码体制

在椭圆曲线上的ElGamal密码体制中，设椭圆曲线为$E_{11}(1, 6)$，生成元p=(2, 7)，接收者的私钥x=4。（1）求接收者的公钥Q。（2）发送者欲发送消息Pm=(7, 9)，选择随机数k=2，求密文c。（3）给出接收者从密文c恢复消息Pm的过程。

在椭圆曲线上的ElGamal密码体制中，求解和解密的过程如下：

已知条件

• 椭圆曲线 $E_{11}(1, 6)$
• 生成元 $p = (2, 7)$
• 接收者的私钥 $x = 4$

（1）求接收者的公钥 $Q$

接收者的公钥 $Q$ 通过计算 $Q = x \cdot p$ 获得，即将生成元 $p$ 乘以私钥 $x$。

首先，回顾一下椭圆曲线上的点加法运算。对于两个点 $P = (x_1, y_1)$ 和 $Q = (x_2, y_2)$ 在模 $n$ 的椭圆曲线上，点加法的公式为：

• 当 $P \neq Q$ 时： $$\lambda = \frac{y_2 - y_1}{x_2 - x_1} \mod n$$ $$x_3 = \lambda^2 - x_1 - x_2 \mod n$$ $$y_3 = \lambda(x_1 - x_3) - y_1 \mod n$$
• 当 $P = Q$ 时（点倍加）： $$\lambda = \frac{3x_1^2 + a}{2y_1} \mod n$$ $$x_3 = \lambda^2 - 2x_1 \mod n$$ $$y_3 = \lambda(x_1 - x_3) - y_1 \mod n$$

对于给定的椭圆曲线 $E_{11}(1, 6)$，生成元 $p = (2, 7)$，私钥 $x = 4$，我们要计算 $Q = x \cdot p$：

1. 计算 $2p$：

   $$\lambda = \frac{3x_1^2 + a}{2y_1} \mod 11 = \frac{3 \cdot 2^2 + 1}{2 \cdot 7} \mod 11 = \frac{3 \cdot 4 + 1}{14} \mod 11 = \frac{13}{14} \mod 11 = 13 \cdot 14^{-1} \mod 11$$

   计算 14 的逆元：

   $$14 \equiv 3 \mod 11 \implies 3 \cdot 4 \equiv 1 \mod 11 \implies 14^{-1} \equiv 4 \mod 11$$

   所以：

   $$\lambda = 13 \cdot 4 \mod 11 = 52 \mod 11 = 8$$

   计算 $x_3$ 和 $y_3$：

   $$x_3 = \lambda^2 - 2x_1 \mod 11 = 8^2 - 2 \cdot 2 \mod 11 = 64 - 4 \mod 11 = 60 \mod 11 = 5$$ $$y_3 = \lambda(x_1 - x_3) - y_1 \mod 11 = 8(2 - 5) - 7 \mod 11 = 8(-3) - 7 \mod 11 = -24 - 7 \mod 11 = -31 \mod 11 = 2$$

   所以 $2p = (5, 2)$。

2. 计算 $4p = 2(2p) = 2(5, 2)$：

   $$\lambda = \frac{3x_1^2 + a}{2y_1} \mod 11 = \frac{3 \cdot 5^2 + 1}{2 \cdot 2} \mod 11 = \frac{3 \cdot 25 + 1}{4} \mod 11 = \frac{76}{4} \mod 11 = 76 \cdot 4^{-1} \mod 11$$

   计算 4 的逆元：

   $$4 \cdot 3 \equiv 1 \mod 11 \implies 4^{-1} \equiv 3 \mod 11$$

   所以：

   $$\lambda = 76 \cdot 3 \mod 11 = 228 \mod 11 = 8$$

   计算 $x_3$ 和 $y_3$：

   $$x_3 = \lambda^2 - 2x_1 \mod 11 = 8^2 - 2 \cdot 5 \mod 11 = 64 - 10 \mod 11 = 54 \mod 11 = 10$$ $$y_3 = \lambda(x_1 - x_3) - y_1 \mod 11 = 8(5 - 10) - 2 \mod 11 = 8(-5) - 2 \mod 11 = -40 - 2 \mod 11 = -42 \mod 11 = 2$$

   所以 $4p = (10, 2)$。

因此，接收者的公钥 $Q = (10, 2)$。

（2）求发送者发送消息 $P_m = (7, 9)$ 的密文 $c$

选择随机数 $k = 2$，计算密文 $c = (C_1, C_2)$：

1. 计算 $C_1 = k \cdot p$：

   $$2 \cdot p = (5, 2)$$

   所以 $C_1 = (5, 2)$。

2. 计算 $C_2 = P_m + k \cdot Q$：

   $$k \cdot Q = 2 \cdot (10, 2)$$

   计算 $2Q$：

   $$\lambda = \frac{3x_1^2 + a}{2y_1} \mod 11 = \frac{3 \cdot 10^2 + 1}{2 \cdot 2} \mod 11 = \frac{3 \cdot 100 + 1}{4} \mod 11 = \frac{301}{4} \mod 11$$ $$301 \mod 11 = 4 \quad (4 \mod 11 = 4, \ 4^{-1} = 3)$$ $$\lambda = 4 \cdot 3 \mod 11 = 12 \mod 11 = 1$$ $$x_3 = \lambda^2 - 2x_1 \mod 11 = 1^2 - 2 \cdot 10 \mod 11 = 1 - 20 \mod 11 = -19 \mod 11=3$$ $$y_3 = \lambda(x_1 - x_3) - y_1 \mod 11 = (10 - 3) - 2 \mod 11 = 10 - 5 \mod 11 = 5$$

   所以 $2Q = (3, 5)$。

   计算 $P_m + 2Q$：

   $$P_m = (7, 9), \quad 2Q = (3, 5)$$ $$\lambda = \frac{5 - 9}{3 - 7} \mod 11 = \frac{-4}{-4} \mod 11 = 1$$ $$x_3 = \lambda^2 - x_1 - x_2 \mod 11 = 1^2 - 7 - 3 \mod 11 = 1 - 10 \mod 11 = -9 \mod 11 = 2$$ $$y_3 = \lambda(x_1 - x_3) - y_1 \mod 11 = 1(7 - 2) - 9 \mod 11 = 5 - 9 \mod 11 = -4 \mod 11 = 7$$

   所以 $C_2 = (2, 7)$。

因此，密文 $c = (C_1, C_2) = ((5, 2), (2, 7))$。

（3）接收者从密文 $c$ 恢复消息 $P_m$ 的过程

接收者使用私钥 $x = 4$ 从密文 $c = ((5, 2), (2, 7))$ 恢复消息 $P_m$：

1. 计算 $x \cdot C_1$：

   $$x \cdot C_1 = 4 \cdot (5, 2)$$

   计算 $4 \cdot (5, 2)$：

   $$2 \cdot (5, 2) = (10, 2)$$

   再计算 $2 \cdot (10, 2)$：

   $$2 \cdot (10, 2) = (3, 5)$$

   所以 $x \cdot C_1 = (3, 5)$。

2. 计算 $-x \cdot C_1$，即 $(3, 6)$：

   $$C_2 - x \cdot C_1 = (2, 7) + (3, 6)$$

计算 $C_2 - x \cdot C_1$：

$$C_2 = (2, 7), - x \cdot C_1 = (3, 6)$$ $$\lambda = \frac{6 - 7}{3 - 2} \mod 11 = \frac{-1}{1} \mod 11 = 10$$ $$x_3 = \lambda^2 - x_1 - x_2 \mod 11 = 10^2 - 2 - 3 \mod 11 = 100 - 5 \mod 11 = 95 \mod 11 = 7$$ $$y_3 = \lambda(x_1 - x_3) - y_1 \mod 11 = 10(2 - 7) - 7 \mod 11 = -50 - 7 \mod 11 = -57 \mod 11 = 9$$

所以 $C_2 - x \cdot C_1 = (7, 9)$。

因此，接收者恢复的消息 $P_m = (7, 9)$。