[!info] related notes

• 物联网网络安全复习题目
• 密码学
• 安全MOC

RSA算法计算实例

1. 题目描述

已知条件：

• 两个素数 $p = 13$, $q = 17$
• 公钥指数 $e = 7$
• 明文 $m = 20$

求解任务：

1. 计算模数 $n$ 及欧拉函数 $\phi(n)$。
2. 验证 $e$ 与 $\phi(n)$ 互素。
3. 计算私钥 $d$。
4. 计算明文 $m=20$ 的密文 $c$（加密）。
5. 计算密文 $c$ 的明文 $m$（解密）。

2. 解题过程

(1) 计算 n 和 phi(n)

根据 RSA 密钥生成原理：

• 模数 $n$：

  $$

n = p \times q = 13 \times 17 = 221

$$

• 欧拉函数 $\phi(n)$：

$$

\phi(n) = (p-1)(q-1) = 12 \times 16 = 192

$$

(2) 验证 e 与 phi(n) 互素

使用辗转相除法计算 $gcd(e, \phi(n))$：

1. $192 = 27 \times 7 + 3$
2. $7 = 2 \times 3 + 1$
3. $3 = 3 \times 1 + 0$

结论：余数为 1，故 $gcd(7, 192) = 1$，满足互素条件。

(3) 求解私钥 d

我们需要求解 $d$，使得 $e \times d \equiv 1 \pmod{\phi(n)}$，即 $7d \equiv 1 \pmod{192}$。

利用扩展欧几里得算法逆推：

1. 由 (2) 中步骤可得：$1 = 7 - 2 \times 3$
2. 将 $3 = 192 - 27 \times 7$ 代入上式：

$$

1 = 7 - 2 \times (192 - 27 \times 7)

$$

$$

1 = 7 - 2 \times 192 + 54 \times 7

$$

$$

1 = 55 \times 7 - 2 \times 192

$$ 3. 整理得 $55 \times 7 \equiv 1 \pmod{192}$。

结论：私钥 $d = 55$。

(4) 加密过程

• 公式：$c = m^e \pmod n$
• 计算：

$$

c = 20^7 \pmod{221}

$$

使用模重复平方法（快速幂）：

• $20^1 \equiv 20$
• $20^2 = 400 \equiv 179 \pmod{221}$
• $20^4 = 179^2 = 32041 \equiv 217 \equiv -4 \pmod{221}$
• $20^7 = 20^4 \times 20^2 \times 20^1 \equiv (-4) \times 179 \times 20 \pmod{221}$
• $\dots \equiv -14320 \pmod{221}$
• $-14320 \pmod{221} = 45$

结果：密文 $c = 45$。

(5) 解密过程

• 公式：$m = c^d \pmod n$
• 计算：

$$

m = 45^{55} \pmod{221}

$$ (计算过程略，可通过将 55 拆解为二进制 $32+16+4+2+1$ 进行模重复平方计算)

结果：解密得到明文 $m = 20$。

---

相关链接：

• RSA算法
• [[非对称密码学基础]]

📖 相关资源

• cryptography - 密码学基础
• security-moc - 安全 MOC
• iot-network-security-review - 物联网网络安全复习