RSA核心思想
郝伟 2020/07/23

算法思想

RSA算法核心的思想只有两部分：

• Alice随机生成两个数作为解密，一个被称为公钥发布给所有人，另一个作为私钥只有自己持有；
• 任何人可以使用公钥对数据加密，只有Alice可以使用私钥解密获得原数据。

这样，Bob就可以使用公钥对要传输的数据加密再发给Alice，即便Bob加密后的数据泄露也不怕，因为别人没有密钥，无法解开。

主要特性

所以RSA算法的神奇之处有两点：

• 数据只能使用公钥加密，必需使用私钥才能解开
  这种加密方式称之为非对称加密，即加密和解密的密钥是不相同的。对应的有对称加密，即加密和解密的解密是一样的。对称加密容易实现，比如我们可以在加密时，对数据加上1，解密时再减去1，此时1就是密钥（当然这样安全性很弱，只是演示）。非对称加密相对困难，比如2002年计算机领域的最高奖图灵奖就发给了RSA算法，2015年发给了另一种非对称加密算法ECDH。
• 只要密钥长度足够，目前无法破解
  如果加解密的强度不够，易被暴力破解，那么实际的应用性也不够强。RSA算法的好处在于，可以通过增加密钥长度来提高其安全性。密钥本质上就是数，所以所谓增加密钥长度，就是使用更大的数来表示，这样在暴力破解时，运算量可以极大地提高。比如，来自Wikipedia的数据显示，在 Intel Dual-Core i7-4500U 1.80GHz 处理器上，破解128位要2秒，192位要16秒，256位35分钟，260位1小时。即便有些算法能够加速破解过程，但是仍然需要大量的时间，比如一款名为 YAFU 的软件使用相同的硬件破解320位需要5720秒。目前，已知的被破解的RSA密钥长度在2016年是768位，2018年达到795位，随时破解算法和计算机能力的提升，这个数字在未来还会继续提高。但是无法如何，这个过程进展是越来越缓慢的，目前推荐的密钥长度是1024位，而在一些安全极高的场合，已经是2048位了。

算法原理

RSA的核心思想是基于欧拉定理：$a^{φ(n)} \equiv 1 \ (\mathrm{mod} \ n)$，其中 $a,n$ 都是大于1的自然数且两者互质，$\varphi{(n)}$ 是求[1, n) 区间上与 $n$ 互质的个数，如 $\varphi{(8)}=4$，因为在 [1, 8) 区间上，1，3，5，7都与8互质。对欧拉定义举例说明，如取 $a=3,n=8$，那么 $3^{φ(8)} \equiv 1 \ (\mathrm{mod} \ 8)$，即 $3^4=81$，$81$ 对 $8$ 取余等于 $1$，满足公式。欧拉定理的详细说明可参见此链接：点击我。

前文已经说过，RSA分为两步，分别有密钥生成算法和加解密算法，我们先从密钥生成算法说起。

密钥生成算法

密钥的本质就是数，所以公私钥分别是两个数。基于RSA算法，这两个数都是正整数。那么这两个数是如何计算来的都是基于欧拉函数，即$\varphi{(n)}$，下面我们就说一下详细计算过程。

1. 取两个质数 $p$ 和 $q$，如 $p=61, q=53$；
2. 计算 $n = qp$，如 $n = 61*53=3233$；
3. 根据欧拉函数计算 $\varphi{(n)}=\varphi{(qp)}=\varphi{(p)}*\varphi{(q)}=(p-1)*(q-1)=60*52=3120$；
4. 计算公钥因子 $e$ 满足 $1<e< \varphi{(n)}$ 且与 $\varphi{(n)}$ 互质，如 $e = 17$；
5. 计算私钥因子 $d$ 满足 $ed=k(\varphi{(n)}-1)$，其中 $k$ 为正整数，比如可如 $k = 1, d=413$。

经过以上的计算，我们最终完成了密钥生成计算，其中公钥为 $(n,e)$ 密钥为 $(n,d)$，如公钥为 (3233,17)，私钥为 (3233,413)。

加解密算法

设明文为 $M$，密文为 $m$，那么计算公式分别如下：

• 加密：$m = M^e \ \mathrm{mod} \ n$ …… ①
• 密钥：$M = m^d \ \mathrm{mod} \ n$ …… ②

这个过程是不是很简洁，举例说明，假设 $M=65$，那么

• 加密：$m = 65^{17} \ \mathrm{mod} \ 3233=2790$
• 解密：$M = 2790^{413} \ \mathrm{mod} \ 3233=65$

可见，原文65在使用公钥(3233,17)加密后，得到2790，然后再使用私钥(3233,413)解密后，又得到了原文。为什么可以相等呢，我们可以简单证明。

证明

联合①②式可得：
$$m = (m^d \ \mathrm{mod} \ n)^e \ \mathrm{mod} \ n= m^{ed} \ \mathrm{mod} \ n=m^{\varphi(n)+1} \ \mathrm{mod} \ n$$根据余数性质三，可得：$$m^{\varphi(n)+1} \ \mathrm{mod} \ n=(m \ \mathrm{mod} \ n)*(m^{\varphi(n)} \ \mathrm{mod} \ n) \ \mathrm{mod} \ n$$根据欧拉定理易知，中间一项为1，所以$$m^{\varphi(n)+1} \ \mathrm{mod} \ n=m \ \mathrm{mod} \ n$$又因为 $m<n$，所以$$m^{\varphi(n)+1} \ \mathrm{mod} \ n=m$$即加密后的数据最终等于$m$，证毕。