RSA加解密示例
示例1¶
1. 密钥生成步骤¶
- 选择素数：令 \(p = 3, q = 11\)。
- 计算模数：\(n = p \times q = 33\)。
- 计算欧拉函数：\(\phi(n) = (3-1) \times (11-1) = 2 \times 10 = 20\)。
- 选择公钥指数 \(e\)：我们需要一个与 20 互质的数，选 \(e = 3\)。
- 计算私钥指数 \(d\)：需满足 \(3d \equiv 1 \pmod{20}\)。
- 通过试算：\(3 \times 7 = 21\)，而 \(21 \div 20\) 余 \(1\)。
- 所以 \(d = 7\)。
结果：
- 公钥：\((n=33, e=3)\)
- 私钥：\((n=33, d=7)\)
2. 加密演示¶
假设我们要发送的消息明文 \(M = 5\)：
计算 \(125 \div 33 = 3\) 余 \(26\)，所以 密文 \(C = 26\)。
3. 解密演示¶
接收方收到密文 \(26\)，使用私钥 \(d=7\) 进行还原：
为了计算方便，我们可以拆解幂运算：
- \(26^1 \equiv 26 \equiv -7 \pmod{33}\)
- \(26^2 \equiv (-7)^2 = 49 \equiv 16 \pmod{33}\)
- \(26^4 \equiv 16^2 = 256 \equiv 25 \pmod{33}\)
- \(26^7 = 26^4 \times 26^2 \times 26^1 \equiv 25 \times 16 \times (-7) \pmod{33}\)
- 计算得出结果为 \(5\)。
明文还原成功！
示例2¶
取： $$ p=61,\quad q=53 $$ 则： $$ n = 61 \cdot 53 = 3233 $$ 计算： $$ \lambda(n)=\operatorname{lcm}(60,52)=780 $$ 选： $$ e=17 $$ 求逆得到： $$ d=413 $$ 公钥： \((n=3233, e=17)\) 私钥： \(d=413\)
加密 \(m=65\)： $$ c = 65^{17} \bmod 3233 = 2790 $$ 解密： $$ m = 2790^{413} \bmod 3233 = 65 $$
基于中国剩余定理（CRT）的加速¶
为提升解密效率，实际私钥通常还包含：
$$
d_p = d \bmod (p-1),\quad
d_q = d \bmod (q-1),\quad
q^{-1} \bmod p
$$
先分别计算：
$$
m_1 = c^{d_p} \bmod p,\quad
m_2 = c^{d_q} \bmod q
$$
再用中国剩余定理合成得到最终 \(m\)。
该方法可使解密速度提升约 4 倍。
RSA数字签名¶
签名¶
Alice 对消息 \(M\)：
-
计算哈希： $$ h = \text{hash}(M) $$
-
生成签名： $$ s = h^d \bmod n $$
-
发送 \((M, s)\) 给 Bob。
验证¶
Bob 计算： $$ h = \text{hash}(M) $$ 并检查： $$ s^e \stackrel{?}{\equiv} h \pmod n $$ 若成立，则：
- 消息确实来自 Alice；
- 消息未被篡改。
数学依据： $$ s^e = (hd)e = h^{de} \equiv h \pmod n $$
为什么必须先做哈希？¶
若直接签名原始消息 \(m\)，则存在可乘法伪造的漏洞：
- 可伪造 \((m_1 m_2, s_1 s_2)\)；
- 可对 \(m=1\) 伪造签名 \(s=1\)。
因此**现代 RSA 签名必须先哈希，再签名**（如 RSA-PSS）。