密码学题目 - RSA签名方案

在RSA签名方案中，设p=7，q=17，公钥e=5，消息m的Hash值为19，试计算私钥d并给出对消息的签名和验证过程。

求私钥 $d$ 的计算过程

已知参数：

• $$p = 7$$
• $$q = 17$$
• $$n = p \times q = 7 \times 17 = 119$$
• $$\phi(n) = (p - 1) \times (q - 1) = 6 \times 16 = 96$$
• 公钥 $e = 5$

我们需要找到私钥 $d$，满足：

$$d \equiv e^{-1} \mod 96$$

即：

$$5 \times d \equiv 1 \pmod{96}$$

5×d 与 1 在模 96 下是同余的

使用扩展欧几里得算法求解逆元

扩展欧几里得算法步骤：

1. 使用欧几里得算法找到 $e$ 和 $\phi(n)$ 的最大公约数：

   $$96 = 5 \times 19 + 1$$

   这里我们得到了 $1 = 96 - 5 \times 19$。

2. 改写成扩展欧几里得算法形式：

   $$1 = 96 - 5 \times 19$$

   即：

   $$1 = 96 \times 1 - 5 \times 19$$

   从而：

   $$1 \equiv -5 \times 19 \pmod{96}$$

   因此： $d = -19$。

3. 将负数转为正数形式：

   $$d = 96 - 19 = 77$$

因此，私钥 $d$ 为：

$$d = 77$$

签名和验证过程

对消息的签名

消息 $m$ 的 Hash 值 $h(m) = 19$。

签名 $s$ 为：

$$s \equiv h(m)^d \mod n$$ $$s \equiv 19^{77} \mod 119$$

计算 $19^{77} \mod 119$

用模重复平方方法计算 $19^{77} \mod 119$：

19^1 ≡ 19 (mod 119)
19^2 ≡ 19 * 19 ≡ 361 ≡ 4 (mod 119)
19^4 ≡ 4^2 ≡ 16 (mod 119)
19^8 ≡ 16^2 ≡ 256 ≡ 18 (mod 119)
19^16 ≡ 18^2 ≡ 324 ≡ 86 (mod 119)
19^32 ≡ 86^2 ≡ 7396 ≡ 18 (mod 119)
19^64 ≡ 18^2 ≡ 324 ≡ 86 (mod 119)
19^77 ≡ 19^64 * 19^8 * 19^4 * 19 ≡ 86 * 18 * 16 * 19 ≡ 470592 ≡ 66 (mod 119)

所以签名 $s = 66$。

签名验证

验证签名过程：

$$s^e \mod n$$ $$66^5 \mod 119$$

用模重复平方方法计算 $66^5 \mod 119$：

66^1 ≡ 66 (mod 119)
66^2 ≡ 66 * 66 ≡ 4356 ≡ 72 (mod 119)
66^4 ≡ 72^2 ≡ 5184 ≡ 67 (mod 119)
66^5 ≡ 66^4 * 66 ≡ 67 * 66 ≡ 4422 ≡ 19 (mod 119)

因此：

$$s^e \equiv 19 \mod 119$$

验证通过，计算结果为19，等于消息的 Hash 值 $h(m)$。

总结

• 私钥 $d$：77
• 签名 $s$：66
• 验证：$66^5 \equiv 19 \mod 119$，验证通过。