算法思想

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

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

密钥生成算法

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

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

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

加解密算法

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

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

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

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

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

证明

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