RSA算法原理

前言

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个整数互质。
常见的互质数判断方法主要有以下几种：

1. 两个不同的质数一定是互质数。例如，2与7、13与19。
2. 一个质数，另一个不为它的倍数，这两个数为互质数。例如，3与10、5与 26。
3. 相邻的两个自然数是互质数。如 15与 16。
4. 相邻的两个奇数是互质数。如 49与 51。
5. 较大数是质数的两个数是互质数。如97与88。
6. 小数是质数，大数不是小数的倍数的两个数是互质数。例如 7和 16。
7. 2和任何奇数是互质数。例如2和87。
8. 1不是质数也不是合数，它和任何一个自然数在一起都是互质数。如1和9908。
9. 辗转相除法。

3.指数运算

指数运算又称乘方计算，计算结果称为幂。n^m指将n自乘m次。把n^m看作乘方的结果，叫做”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的一条私人讯息。她可以用以下的方式来产生一个公钥和一个私钥：

1. 随意选择两个大的质数p和q，p不等于q，计算N=pq。
2. 根据欧拉函数，求得r = (p-1)(q-1)
3. 选择一个小于 r 的整数* e*，求得 e 关于模 r 的模反元素，命名为d。（模反元素存在，当且仅当e与r互质）
4. 将* p 和 q 的记录销毁。
   (N,e)是公钥，(N,d)*是私钥。Alice将她的公钥(N,e)传给Bob，而将她的私钥(N,d)藏起来。

加密消息

假设Bob想给Alice送一个消息m，他知道Alice产生的N和e。他使用起先与Alice约好的格式将m转换为一个小于N的整数n，比如他可以将每一个字转换为这个字的Unicode码，然后将这些数字连在一起组成一个数字。假如他的信息非常长的话，他可以将这个信息分为几段，然后将每一段转换为n。用下面这个公式他可以将n加密为c：

n^e ≡ c (mod N)

计算c并不复杂。Bob算出c后就可以将它传递给Alice。

解密消息

Alice得到Bob的消息c后就可以利用她的密钥d来解码。她可以用以下这个公式来将c转换为n：

c^d ≡ n (mod N)

得到n后，她可以将原来的信息m重新复原。
解码的原理是：

c^d ≡ 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