RSA算法

1. 历史

1977年，三位数学家RonRivest、Adi Shamir 和 Leonard Adleman 设计了一种算法，可以实现非对称加密。这种算法用他们三个人的名字命名，叫做RSA算法。

2. 密钥生成

随机选择两个不相等的质数 $p$ 和 $q$
计算 $n = q p, ϕ (n) = (p - 1) (q - 1)$
选择一个整数 $e$ ,满足 $1 < e < ϕ (n), gcd (e, ϕ (n)) = 1$
计算 $e$ 的模反元素 $d$ ，满足 $e d \equiv 1 (\mod ϕ (n))$
公钥为 $(e, n)$ ，密钥为 $(d, n)$

3. 加密和解密

加密明文 $M, M < n$ ,

C = E (M) = M^{e} (\mod n)

解密密文 $C$ ,

M = D (C) = C^{d} (\mod n)

4. 举例

爱丽丝选择了 $p = 61, q = 53$ , 计算

\begin{aligned} n & = p q = 61 \times 53 = 3233 \\ ϕ (n) & = (p - 1) (q - 1) = 360 \times 52 = 3120 \end{aligned}

爱丽丝选择 $e = 17$ ，解同余方程

17 \times d \equiv 1 (\mod 3120)

使用扩展欧几里得算法解方程

17 d + 3120 y = 1

得到 $d = 2753$

公钥为 $(17, 3233)$ , 密钥为 $(2753, 3233)$
鲍勃使用公钥加密明文'A'=65

E (65) = 65^{17} (\mod 3233) = 2790

爱丽丝用私钥解密

D (2790) = 2790^{2753} (\mod 3233) = 65

5. 证明

根据加密规则 $M^{e} \equiv C (\mod n), C$ 可以写成 $C = M^{e} - k n$ 下面证明下面的公式成立

C^{d} \equiv M (\mod n)

将C代入要我们要证明的那个解密规则：

(M^{e} - k n)^{d} \equiv M (\mod n)

它等同于求证

M^{e d} \equiv M (\mod n)

由于

e d \equiv 1 (\mod ϕ (n))

所以

e d = h ϕ (n) + 1

将ed代入得到：

M^{h ϕ (n) + 1} \equiv M (\mod n)

接下来，分成两种情况证明上面这个式子。

5.1 $M$ 与 $n$ 互质

根据欧拉定理，此时

M^{ϕ (n)} \equiv 1 (\mod n)

得到

{(M^{ϕ (n)})}^{h} \times M \equiv M (\mod n)

原式得到证明。

5.2 $M$ 与 $n$ 不是互质关系

此时，由于 $n$ 等于质数 $p$ 和 $q$ 的乘积，所以 $M$ 必然等于 $k p$ 或 $k q$ 。以 $M = k p$ 为例，考虑到这时 $k$ 与 $q$ 必然互质，则根据欧拉定理，下面的式子成立：

{(k p)}^{q - 1} \equiv 1 (\mod q)

进一步得到

((k p)^{q - 1})^{h (p - 1)} \times k p \equiv k p (\mod q)

即

(k p)^{e d} \equiv k p (\mod q)

将它改写成下面的等式

(k p)^{e d} = t q + k p

这时 $t$ 必然能被 $p$ 整除，即 $t = t^{'} p$

(k p)^{e d} = t^{'} p q + k p

因为 $m = k p, n = p q$ ，所以

M^{e d} \equiv M (\mod n)

原式得到证明。

6. 密钥对的个数

对于选定的 $n = p q$ ，能够产生的密钥对 ${e, d, n}$ 有多少个？

由于 $e d \equiv 1 (\mod ϕ (n))$ ，所以 $gcd (e, ϕ (n)) = 1$ ，而且 $1 < e < ϕ (n)$ ，所以 $e$ 的个数是和 $ϕ (n)$ 互质的数的个数，也就是 $e$ 有 $ϕ (ϕ (n))$ 个对于 $d$ ，由于 $e d \equiv 1 (\mod ϕ (n))$ ，当 $e$ 确定时，方程 $e x \equiv 1 (\mod ϕ (n))$ 在 $1 < x < ϕ (n)$ 有且只有一个解，所以密钥对 ${e, d, n}$ 的个数为 $ϕ (ϕ (n))$ 个

比如 $p = 13, q = 17$ ，那么 $ϕ (n) = 12 \times 16 = 2^{6} \times 3$ , $ϕ (ϕ (n)) = ϕ (2^{6}) \times ϕ (3) = 2^{5} \times 2 = 64$ 所以一共有64对密钥

7. 交换律

当通信的双方使用模数相等的RSA算法时，RSA算法满足交换律，也就是说Alice使用的密钥为 ${e_{1}, d_{1}, n}$ , Bob使用的密钥对为 ${e_{2}, d_{2}, n}$ ，满足

e_{1} d_{1} \equiv e_{2} d_{2} \equiv 1 (\mod ϕ (n))

那么

E_{B} (E_{A} (M)) = E_{A} (E_{B} (M))