Crypto101 阅读笔记(4)

公钥加密

公开密钥加密(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 位。