公钥加密

公开密钥加密（public-key cryptography），也称为非对称加密（asymmetric cryptography）。在这种方法中，需要一对密钥，一个是私钥，另一个是公钥。这两个密钥是数学相关，用某用户密钥加密后所得的信息，只能用该用户的解密密钥才能解密。如果知道了其中一个，并不能计算出另外一个。因此如果公开了一对密钥中的一个，并不会危害到另外一个的秘密性质。称公开的密钥为公钥；不公开的密钥为私钥。

最早公开的公钥加密算法，也同时是至今依然最常用的就是 RSA。

事实上有三类算法和公钥加密相关，一个是前面说到的密钥交换算法，二个就是 RSA 这种加密算法，三个是数字签名算法。

为什么一直使用 RSA 来加密，还一定要使用前面提到的 AES 之类的对称密钥加密？是因为 RSA 比 AES 之类的对称密钥加密，要慢上几百上千倍。

RSA

首先随机选择两个大质数 $p$ 和 $q$，然后把他们相乘，得到 $N$，这个是可以公开的。然后再选择一个加密指数 $e$，这个通常是 3 或者 65537，这个指数是公开的。然后 $(N, e)$ 组合就是公钥。使用公钥将明文 M 加密成密文 C 过程如下：

$$C \equiv M^e ; (\bmod N)$$

对于解密的过程，你需要一个解密指数 $d$。利用 $p$ 和 $q$ 很容易计算出 $d$。这个过程涉及到一定的数学理论。解密过程如下：

$$M \equiv C^d ; (\bmod N)$$

RSA 的安全性建立在 $d$ 很难被逆向计算出来。

对于 RSA 的攻击，从理论上而言，由于尚未发现多项式时间里能够分解质因数的方法，所以还是安全的。但是量子计算机的出现，增加了从量子算法上破解 RSA 的可能。目前常见的破解方式还是实现上。比如 Python 的一个叫 Salt 的库，由于使用加密指数 $e$ 为 1，就导致了 $C = M$ 的情况。

目前通过暴力的方式破解 RSA 达到了 768 位，大大威胁了 1024 bit 密钥的安全性。所以目前推荐密钥至少要有 2048 位。