前言
RSA算法是现今使用最广泛的公钥密码算法，也是号称地球上最安全的加密算法。本文主要参考了参考资料中的文章，加上自己的理解，算是总结了。
历史
对称加密算法
1976年以前，所有的加密方法都是同一种模式：
（1）甲方选择某一种加密规则，对信息进行加密；
（2）乙方使用同一种规则，对信息进行解密。
简单点说：由于加密和解密使用同样规则（简称"密钥"）
这种加密模式有一个最大缺点：甲方必须把加密规则告诉乙方，否则无法解密。保存和传递密钥，就都成了最头疼的问题。
非对称加密算法
1976年，两位美国计算机学家Whitfield Diffie 和 Martin Hellman，提出了一种崭新构思，可以在不直接传递密钥的情况下，完成解密。
（1）乙方生成两把密钥（公钥和私钥）。公钥是公开的，任何人都可以获得，私钥则是保密的。
（2）甲方获取乙方的公钥，然后用它对信息加密。
（3）乙方得到加密后的信息，用私钥解密。
如果公钥加密的信息只有私钥解得开，那么只要私钥不泄漏，通信就是安全的。
RSA加密算法简史
1977年，三位数学家Rivest、Shamir 和 Adleman 设计了一种算法，可以实现非对称加密。这种算法用他们三个人的名字命名。从那时直到现在，RSA算法一直是最广为使用的 非对称加密算法。
必备数学知识
RSA加密算法中，只用到质数、互质数、指数运算、模运算等几个简单的数学知识。所以，我们也需要了解这几个概念。
1. 质数
质数又称素数，指在一个大于1的自然数中，除了1和此整数自身外，不能被其他自然数整除的数。这个概念，我们在上初中，甚至小学的时候都学过了，这里就不再过多解释了。
1. 互质数
百度百科上的解释是：公因数只有1的两个数，叫做互质数。；维基百科上的解释是：互质，又称互素。若N个整数的最大公因子是1，则称这N个整数互质。
常见的互质数判断方法主要有以下几种：
- 两个不同的质数一定是互质数。例如，2与7、13与19。
- 一个质数，另一个不为它的倍数，这两个数为互质数。例如，3与10、5与 26。
- 相邻的两个自然数是互质数。如 15与 16。
- 相邻的两个奇数是互质数。如 49与 51。
- 较大数是质数的两个数是互质数。如97与88。
- 小数是质数，大数不是小数的倍数的两个数是互质数。例如 7和 16。
- 2和任何奇数是互质数。例如2和87。
- 1不是质数也不是合数，它和任何一个自然数在一起都是互质数。如1和9908。
- 辗转相除法。
3.指数运算
指数运算又称乘方计算，计算结果称为幂。nm指将n自乘m次。把nm看作乘方的结果，叫做”n的m次幂”或”n的m次方”。其中，n称为“底数”，m称为“指数”。
4.模运算
模运算即求余运算。“模”是“Mod”的音译。和模运算紧密相关的一个概念是“同余”。数学上，当两个整数除以同一个正整数，若得相同余数，则二整数同余。
两个整数a，b，若它们除以正整数m所得的余数相等，则称a，b对于模m同余，记作: a ≡ b (mod m)；读作：a同余于b模m，或者，a与b关于模m同余。例如：26 ≡ 14 (mod 12)。
5.欧拉函数
任意给定正整数n，计算在小于等于n的正整数之中，有多少个与n构成互质关系？计算这个值的方法就叫做欧拉函数，以φ(n)表示.
例如，在1到8之中，与8形成互质关系的是1、3、5、7，所以φ(n)=4
在RSA算法中，我们需要知道欧拉函数对以下定理成立
如果n可以分解成两个互质的整数之积，即n=p×q，则有：φ(n)=φ(pq)=φ(p)φ(q);
即积的欧拉函数等于各个因子的欧拉函数之积。比如，φ(56)=φ(8×7)=φ(8)×φ(7)=4×6=24。
算法基础
公钥与密钥的产生
假设Alice想要通过一个不可靠的媒体接收Bob的一条私人讯息。她可以用以下的方式来产生一个公钥和一个私钥：
加密消息
假设Bob想给Alice送一个消息m，他知道Alice产生的N和e。他使用起先与Alice约好的格式将m转换为一个小于N的整数n，比如他可以将每一个字转换为这个字的Unicode码，然后将这些数字连在一起组成一个数字。假如他的信息非常长的话，他可以将这个信息分为几段，然后将每一段转换为n。用下面这个公式他可以将n加密为c：
ne ≡ c (mod N)
计算c并不复杂。Bob算出c后就可以将它传递给Alice。
解密消息
Alice得到Bob的消息c后就可以利用她的密钥d来解码。她可以用以下这个公式来将c转换为n：
cd ≡ n (mod N)
得到n后，她可以将原来的信息m重新复原。
解码的原理是：
cd ≡ n e·d(mod N)
以及ed ≡ 1 (mod p-1)和ed ≡ 1 (mod q-1)。由费马小定理可证明（因为p和q是质数）
n e·d ≡ n (mod p) 和 n e·d ≡ n (mod q)
这说明（因为p和q是不同的质数，所以p和q互质）
n e·d ≡ n (mod pq)
RSA加密算法的缺点
虽然RSA加密算法作为目前最优秀的公钥方案之一，在发表三十多年的时间里，经历了各种攻击的考验，逐渐为人们接受。但是，也不是说RSA没有任何缺点。由于没有从理论上证明破译RSA的难度与大数分解难度的等价性。所以，RSA的重大缺陷是无法从理论上把握它的保密性能如何。在实践上，加密和解密花费时间长、速度慢，只适合对少量数据进行加密。
参考资料：
1、http://www.ruanyifeng.com/blog/2013/06/rsa_algorithm_part_one.html
2、http://www.ruanyifeng.com/blog/2013/07/rsa_algorithm_part_two.html
3、http://en.wikipedia.org/wiki/RSA_(cryptosystem)
4、http://blog.sciencenet.cn/home.php?mod=space&uid=287179&do=blog&id=391134
5、https://segmentfault.com/a/1190000004461428
6、http://blog.csdn.net/aitangyong/article/details/53861894
