密码学题目 - ElGamal密码体制加密

在ElGamal密码体制中，设素数p=71，生成元g=7。（1）如果接收者B的公钥为yB=3，发送者A随机选择整数k=2，求明文m=30所对应的密文。（2）如果发送者A选择另一个随机整数k，使得明文m=30加密后的密文为c=(59, c2)，求c2。

ElGamal密码体制

已知条件：

• 素数 $p = 71$
• 生成元 $g = 7$
• 接收者B的公钥 $y_B = 3$
• 明文 $m = 30$

（1）随机整数 $k = 2$

计算密文 $c = (C_1, C_2)$：

1. 计算 $C_1$：

   $$C_1 = g^k \mod p = 7^2 \mod 71$$

   计算 $7^2$：

   $$7^2 = 49$$

   所以：

   $$C_1 = 49 \mod 71 = 49$$

2. 计算 $C_2$：

   $$C_2 = m \cdot (y_B)^k \mod p = 30 \cdot 3^2 \mod 71$$

   计算 $3^2$：

   $$3^2 = 9$$

   所以：

   $$C_2 = 30 \cdot 9 \mod 71 = 270 \mod 71$$

   计算 $270 \mod 71$：

   $$270 = 3 \cdot 71 + 57 \implies 270 \mod 71 = 57$$

因此，密文 $c = (C_1, C_2) = (49, 57)$。

（2）选择另一个随机整数 $k$，使密文为 $c = (59, C_2)$

假设发送者选择的随机整数 $k$ 使得 $C_1 = 59$。我们需要求解此情况下的 $C_2$。

1. 确定 $k$： $$C_1 = g^k \mod p = 59$$ 我们需要找到满足 $7^k \equiv 59 \mod 71$ 的 $k$。

通过计算可以找到 $k$：

$$7^1 = 7$$ $$7^2 = 49$$ $$7^3 = 343 \equiv 59 \mod 71$$

所以 $k = 3$。

1. 计算 $C_2$： $$C_2 = m \cdot (y_B)^k \mod p = 30 \cdot 3^3 \mod 71$$ 计算 $3^3$： $$3^3 = 27$$ 所以： $$C_2 = 30 \cdot 27 \mod 71 = 810 \mod 71$$ 计算 $810 \mod 71$： $$810 = 11 \cdot 71 + 29 \implies 810 \mod 71 = 29$$

因此，当 $k = 3$ 时，密文 $c = (59, 29)$。

总结

• 当随机数 $k = 2$ 时，明文 $m = 30$ 的密文为 $c = (49, 57)$。
• 当随机数 $k = 3$ 时，明文 $m = 30$ 的密文为 $c = (59, 29)$。

在RSA密码体制中，已知素数p=3，q=11，公钥e=7，计算私钥d并给出对明文m=5的加密和解密过程。

RSA密码体制

已知条件：

• 素数$p = 3$
• 素数$q = 11$
• 公钥$e = 7$
• 明文$m = 5$

1. 计算$n$ 和$\phi(n)$

1. 计算$n$：

   $$n = p \times q = 3 \times 11 = 33$$

2. 计算$\phi(n)$：

   $$\phi(n) = (p-1) \times (q-1) = (3-1) \times (11-1) = 2 \times 10 = 20$$

2. 计算私钥$d$

私钥$d$ 是$e$ 在模$\phi(n)$ 下的乘法逆元，即满足：

$$e \times d \equiv 1 \pmod{\phi(n)}$$

即：

$$7 \times d \equiv 1 \pmod{20}$$

我们需要找到$d$ 使这个等式成立。可以使用扩展欧几里得算法来计算：

扩展欧几里得算法求解：

$$7d \equiv 1 \pmod{20}$$

步骤如下：

$$20 = 2 \times 7 + 6$$ $$7 = 1 \times 6 + 1$$

从中我们可以逆向求得：

$$1 = 7 - 1 \times 6$$ $$6 = 20 - 2 \times 7$$

代入得：

$$1 = 7 - 1 \times (20 - 2 \times 7) = 7 - 20 + 2 \times 7 = 3 \times 7 - 20$$

因此$d = 3$，因为：

$$7 \times 3 \equiv 1 \pmod{20}$$

所以私钥$d = 3$。

3. 对明文$m = 5$ 进行加密和解密

1. 加密：

   • 使用公钥$(e, n)$
   • 密文$c$： $$c \equiv m^e \mod n = 5^7 \mod 33$$

   计算$5^7 \mod 33$：

   $$5^2 = 25$$ $$5^4 = 25^2 = 625 \equiv 31 \mod 33$$ $$5^6 = 5^4 \times 5^2 = 31 \times 25 = 775 \equiv 16 \mod 33$$ $$5^7 = 5^6 \times 5 = 16 \times 5 = 80 \equiv 14 \mod 33$$

所以密文$c = 14$。

1. 解密：

   • 使用私钥$(d, n)$
   • 明文$m$： $$m \equiv c^d \mod n = 14^3 \mod 33$$

   计算$14^3 \mod 33$：

   $$14^2 = 196\equiv 31 \mod 33$$ $$14^3 = 31 \times 14 = 434 \equiv 5 \mod 33$$

所以解密后的明文$m = 5$。

总结

• 私钥$d = 3$
• 明文$m = 5$ 加密后的密文$c = 14$
• 密文$c = 14$ 解密后的明文$m = 5$