引入
一直到上个世纪的70年代，人们都还在使用对称加密算法，也就是说信息的收发方会通过事先商定好的密钥，对数据进行加密和解密。
然而这种加密方式有诸多缺陷，随着网络规模的不断增大，每多一个用户就需要保存许多额外的密钥，密钥的管理也将逐渐成为所有人的负担。
更加致命的是，密钥必须通过见面协商，而没有办法直接通过网络进行交换。因为密钥的传输过程需要进行加密，而没有密钥则不能进行加密。
那有没有一种可能性，我们用不同的密钥对数据进行加密和解密。其中对数据加密的密钥是对所有人公开的，而对数据解密的密钥却仅为接收者持有呢？
RSA简介
RSA公钥加密算法是1977年由Ron Rivest、Adi Shamirh和Len Adleman在美国麻省理工学院发现的。RSA取名来自开发他们三者的名字。
RSA是目前最有影响力的公钥加密算法，它能够抵抗到目前为止已知的所有密码攻击，已被ISO推荐为公钥数据加密标准。RSA算法基于一个十分简单的数论事实：将两个大素数相乘十分容易，但那时想要对其乘积进行因式分解却极其困难，因此可以将乘积公开作为加密密钥。
正是基于这种理论，1978年出现了著名的RSA算法，它通常是先生成一对RSA密钥，其中之一是保密密钥，由用户保存；另一个为公开密钥，可对外公开，甚至可在网络服务器中注册。为提高保密强度，RSA密钥至少为500位长，一般推荐使用1024位。这就使加密的计算量很大。为减少计算量，在传送信息时，常采用传统加密方法与公开密钥加密方法相结合的方式，即信息采用改进的DES或IDEA对话密钥加密，然后使用RSA密钥加密对话密钥和信息摘要。对方收到信息后，用不同的密钥解密并可核对信息摘要。
RSA算法是第一个能同时用于加密和数字签名的算法，也易于理解和操作。RSA是被研究得最广泛的公钥算法，从提出到现今的三十多年里，经历了各种攻击的考验，逐渐为人们接受，普遍认为是目前最优秀的公钥方案之一。
RSA原理
算法原理
RSA公开密钥密码体制的原理是：根据数论，寻求两个大素数比较简单，而将它们的乘积进行因式分解却极其困难，因此可以将乘积公开作为加密密钥。
算法描述
RSA算法的具体描述如下：
任意选取两个不同的大素数p和q计算乘积n = pq，φ(n) = (p-1)(q-1)
任意选取一个大整数e，满足gcd(e, φ(n)) = 1，整数e用做加密钥（注意：e的选取是很容易的，例如，所有大于p和q的素数都可用）
确定的解密钥d，满足(de) mod φ(n) = 1，即de = kφ(n) + 1, k >= 1是一个任意的整数；所以，若知道e和φ(n)，则很容易计算出d
公开整数n和e，秘密保存d
将明文m（m<n是一个整数）加密成密文c，加密算法为：c = E(m) = mᵉ mod n
将密文c解密为明文m，解密算法为：m = D(c) = cᵈ mod n
然而只根据n和e（注意：不是p和q）要计算出d是不可能的。因此，任何人都可对明文进行加密，但只有授权用户（知道d）才可对密文解密。
安全性
RSA的安全性依赖于大数分解，但是否等同于大数分解一直未能得到理论上的证明，也并没有从理论上证明破译。RSA的难度与大数分解难度等价。因为没有证明破解RSA就一定需要做大数分解。假设存在一种无须分解大数的算法，那它肯定可以修改成为大数分解算法，即RSA的重大缺陷是无法从理论上把握它的保密性能如何，而且密码学界多数人士倾向于因子分解不是NPC问题。
目前，RSA的一些变种算法已被证明等价于大数分解。不管怎样，分解n是最显然的攻击方法。现在，人们已能分解140多个十进制位的大素数。因此，模数n必须选大些，视具体适用情况而定。
RSA算法的保密强度随其密钥的长度增加而增强。但是，密钥越长，其加解密所耗用的时间也越长。因此，要根据所保护信息的敏感程度与攻击者破解所要花费的代价值不值得以及系统所要求的反应时间来综合考虑，尤其对于商业信息领域更是如此。
运算速度
由于进行的都是大数计算，使得RSA最快的情况也比DES慢上好几倍，无论是软件还是硬件实现。速度一直是RSA的缺陷。一般来说只用于少量数据加密。RSA的速度比对应同样安全级别的对称密码算法要慢1000倍左右。
算法攻击
迄今为止，对RSA的攻击已经很多，但都没有对它构成真正的威胁。在这里，我们讨论一些典型的攻击方法：
RSA的选择密码攻击
RSA在选择密码攻击面前显得很脆弱。一般攻击者是将某一信息进行下伪装，让拥有私钥的实体签名；然后，经过计算就可得到它所想要的信息。实际上，攻击利用的都是同一个弱点，即存在这样一个事实：乘幂保留了输入的乘法结构。前面已经提到，这个固有的问题来自于公钥密码系统的最基本的特征，即每个人都能使用公钥加密信息。从算法上无法解决这一问题，改进措施有两条：是采用好的公钥协议保证工作过程中实体不对其他实体任意产生的信息解密，不对自己一无所知的信息签名；二是决不对陌生人送来的随机文档签名，或签名时首先对文档作Hash处理，或同时使用不同的签名算法。
RSA的小指数攻击
当公钥e取较小的值，虽然会使加密变得易于实现，速度有所提高，但这样做也是不安全的。最简单的办法就是e和d都取较大的值。
因为密钥的产生受素数产生技术的限制，所以也有它的局限性。
（1）密钥的产生受素数产生技术的限制，因而难以做到一次一密；
（2）分组长度太大，为保证安全性，n至少也要600比特以上，使运算代价很高，尤其是速度较慢，比对称密码算法慢几个数量级；随着大整数素因数分解算法的改进和计算机计算能力的提高，对n的长度在不断增加，不利于实现数据格式的标准化。
RSA详细解析
单向函数：模运算
在公钥加密算法中，由于公钥是对所有人公开的信息，我们需要保证数据被“公钥”加密之后，不能够被轻易地反推出来。
那什么样的算法单向计算容易，而逆向反推却非常难呢？（这种关系被称为限门单向函数）
其中一个答案是模运算。模运算又被叫作求余运算，像计算机中伪随机数、散列（hash）算法都是它的典型应用。
试想一下这个例子：3³ mod 7
要计算3的3次方对7取余数很容易，答案是6。
3ⁿ mod 7 = 6
但已知答案是6的情况下，我们又应当如何去寻找这里的n值呢？由于求余运算并不可逆，我们只能一个数一个数地代进去尝试，从0开始直到得到答案3。
但如果这里出现的是很大很大的数字，再去一一尝试就很不现实了：3ⁿ mod 98859834576182328468765894361723649832 = 6
这也是为什么模运算被称作是单向函数，因为对于大数来说，对模运算求逆是根本不现实的。而公钥加密正是利用了模运算的这个特性。
模运算加密原理
假设我们将原始数据表示成一个数m（message）
然后我们对它求e次幂，这里的e（encrypt）可以看作是我们加密时用的密钥
然后我们将结果除以N并取余数，最后得到密文c（cipher）
并且根据之前我们讲到的正向计算出这里的密文c很简单，但反向推出这里的原始数据却很难
解密的过程与之非常类似，我们需要对密文c求d次幂，这里的d（decrypt）代表另外一个用于解密的密钥，最后得到的结果是解密后的原始数据m
为了接下来理解的方便，我们将两个公式做一些变换
再变换一下
合并为一个更为简洁的形式：m的e*d次幂除以N取余数，将会得到原始数据m本身。
可以发现，如何选取这里的e和d便成了公钥加密中最关键的问题
为此我们就不得不提到欧拉在1763年的一个重要发现————欧拉定理（Euler’s Theorem）
欧拉定理
欧拉定理表示，对于任何一个与n互质的正整数m，取它φ(n)次方并除以n取余数，结果都永远等于1。
这里的φ(n)是欧拉函数，它代表在小于或等于n的正整数中，有多少个与n互质的数
这样说可能有些抽象，我们来看一个例子：φ(6)
我们会发现在小于等于6的正整数中，只有1、5和数字6除了1以外并不存在其它的公约数，所以φ(6)=2
在了解φ函数之后，我们回到欧拉定理，尝试对公式进行一些简单的变换，首先我们可以在等式两端同时取k次幂
k在这里代表任意的正整数
接着我们可以在两端同时乘以m
化简后式子如下：
最后我们将模运算写在等式的左边，如果我们将这个公式和之前讲到的加密解密公式对应起来
我们会发现这里公式的指数部分是相同的，于是我们可以将d与e的关系表示成这种形式
也就是说我们可以通过选取这里的k、n、e，来计算出解密的密钥d
这个公式看起来非常简单，但其实这里φ(n)的计算并没有想象中的那么容易，而φ(n)的计算也恰恰正是公钥加密中最关键的部分
实际上，要计算出φ(n)的唯一办法是对这个数n做质因数分解，而大数的质因数分解本身是非常困难的事情
截至目前为止，用最前沿的分布式算法，花了大约2700个“CPU年”，才成功分解了一个829位的数字。因此对于大数来说，φ(n)的求解可以看作是计算上不可行的（computational infeasible）
但是，如果n本身就是一个质数，情况就有所不同了，比如对于质数7来说，小于等于7并与7互质的数有1~6，除了7本身，因此φ(7)=6
同理对于质数13来说，与13互质的数除了13本身其它全部都是，因此φ(13)=12
其实对于任何的质数p，我们可以推广到φ(p)等于这个质数p减去1：
除此之外，φ函数还有一个重要的特性，对于任意两个互质的整数p和q，φ(p*q)可以直接拆分为φ(p)和φ(q)它们单独的乘积（欧拉函数是积性函数）
例如，我们可以选取两个质数17和23，因此我们可以轻易求得φ(391)=352
RSA加密解密
我们代入之前推导出的公式，然后选取一个较小的数e=3，这里我们需要保证它与φ(n)互质
于是在k=5的情况下，求得用于解密的密钥d等于587
在求出了私钥d以后，我们将不再需要这里的p和q了，算法会将e和n公布，作为加密时用的公钥（public key），而d将保存下来作为解密时用的私钥（private key），其他人由于不知道p和q这两个关键的质因数，没有办法计算出这里的φ(n)，因而无从破译这里的私钥d
公钥加密正是利用了这个信息不对等，让加密者能够快速构造出一个φ(n)，而其他人却无法在有限的时间内求解它
接着我们用求得的e、d、n来模拟一段信息的加密解密过程，我们要加密的字符是“a”，它所对应的ascII编码是97，于是97的三次方除以391并取余数等于79，79是我们加密后的密文，为了解密，我们计算79的587次方除以391取余数，得到原始数据97，因此成功还原了字符“a”
RSA的应用
RSA是当今应用最为广泛的公钥加密算法，像数字签名、数字证书、SSH、HTTPS的加密连接，全部是它的典型应用
在实际使用中，由于公钥加密的计算量大、速度慢，通常它会和对称加密算法一同使用
公钥加密算法常被用作最初连接的建立，而真正数据传输的过程会交由对称加密算法来处理
参考与鸣谢
https://www.bilibili.com/video/BV14y4y1272w
https://baike.baidu.com/item/RSA%E7%AE%97%E6%B3%95/263310