密码学——RSA加密算法原理

前言：之前在做密码学题的时候了解了一下RSA，但总感觉那时总结的过少，而且也理解的不到位，这次就再来详细的了解一下，并通过做题来巩固一下。

一、对称加密与非对称加密

对称加密：

非对称加密：

相较于对称加密，非对称加密使用两个密匙，即公开密钥和私钥密钥。
非对称加密很有趣，公钥是任何人都可以请求得到的，但私钥只有一个人持有，而且用公钥加密的密文只能通过私钥来解开，解密者无需像对称加密一样接收加密者的密钥，而是自己保存一个密钥，这样就不在网上传送密匙，不会被拦截，会更加安全，但是相对于对称加密，非对称加密加密和解密的效率会低一些

下面就来学习属于非对称加密中的RSA算法

RSA概述：

1977年，三位数学家Rivest、Shamir 和 Adleman 设计出RSA算法，可以实现非对称加密。而在此之前，使用的都是对称加密。

RSA算法涉及的数学知识

了解RSA之前，需要了解一些数学知识

一、互质关系

两个正整数，除1以外，没有其他公因子，那么这两个数就是互质关系。

例如：30与7就是互质关系，但是30不是质数，这就是说明不是质数也能构成互质关系

由互质关系能得出以下结论：

1. 任意两个质数构成互质关系，比如7和61。
2. 一个数是质数，另一个数只要不是前者的倍数，两者就构成互质关系，比如3和10。
3. 如果两个数之中，较大的那个数是质数，则两者构成互质关系，比如97和57。
4. 1和任意一个自然数是都是互质关系，比如1和99。
5. p是大于1的整数，则p和p-1构成互质关系，比如57和56。
6. p是大于1的奇数，则p和p-2构成互质关系，比如17和15。

二、欧拉函数

在数论，对正整数n，欧拉函数是小于n的正整数中与n互质的数的数目，以φ(n)表示

其实欧拉函数就是用来计算这样一个问题

任意给定正整数n，在小于等于n的正整数之中，有多少个与n构成互质关系？

举个列子：

在1—10中，与10互质的有1、3、7、9，即φ(n)=4

通过欧拉函数又衍生出几种情况：

第一种情况： 如果n=1，则 φ(1) = 1 。因为1与任何数（包括自身）都构成互质关系。
第二种情况： 如果n是质数，则φ(n)=n-1 。因为质数与小于它的每一个数，都构成互质关系。比如7与1、2、3、4、5、6都构成互质关系。

其中对RSA最重要的一种情况就是：

如果n可以分解成两个互质的整数之积

n = p1 × p2 

则

φ(n) = φ(p1p2) = φ(p1)φ(p2) 

通过这个公式可以看出积的欧拉函数等于各个因子的欧拉函数之积

举个列子：

n=21 n=3*7 φ(n) = φ(p1p2) = φ(3)φ(7)=2*6=12 

三、欧拉定理

欧拉定理表明，若n,a为正整数，且n,a互质，则以下公式成立：

换句话就是a的φ(n)次方被n除的余数为1或者是a的φ(n)次方减去1，可以被n整除。

举个列子：

例如：2和5互质，φ(5)=4，则2的4次方(16)减1,15恰好被n(5)整除 

欧拉定理还有一个特殊情况：

如果正整数a与质数p互质，因为质数p的φ§等于p-1，则欧拉定理可以写成：

四、模反元素

如果两个正整数a和n互质，那么一定可以找到整数b，使得 ab-1 被n整除，或者说ab被n除的余数是1。这时，b就叫做a的“模反元素”。

举个列子：

a=3,n=4 (3*b-1)%4=0 故b=7或b=3 显然模反元素不止一个，即如果b是a的模反元素，则 b+kn 都是a的模反元素（k为正整数） 

让m去被n整除，只取所得的余数作为结果，就叫做模运算。

举个例子：

10 mod 4=2、8 mod 3=2 

六、同余

而且同余与模运算是不同的

a≡b (mod m)仅可推出b=a mod m 

七、欧几里德算法

计算方法：

用较大数除以较小数，再用出现的余数（第一余数）去除除数，再用出现的余数（第二余数）去除第一余数，如此反复，直到最后余数是0为止

计算流程图为：

需要的数学知识已经了解完了，接下来就来学习RSA

RSA算法

（一）、生成密钥过程：

一、随机选择两个不相等的质数p和q

二、计算p和q的乘积n

三、计算n的欧拉函数φ(n)

四、随机选择一个整数e，条件是1< e < φ(n)，且e与φ(n) 互质

五、计算e对于φ(n)的模反元素d

六、将n和e封装成公钥，n和d封装成私钥

下面就通过一个列子来执行一遍

一、选取两个不相等的质数p=11 q=13 二、n=p*q=143 三、φ(n)=(p-1)(q-1)=10*12=120 四、从1<e<60, 随机选取一个e,这里选取7 五、根据欧拉定理 e*d ≡ 1 (mod φ(n))，该公式又可转化为e*d - 1 = kφ(n) 所以7*d+120*k=1,这个方程可以由扩展欧几里得算法（辗转相除法）来得出结果： 六、120 = 7 * 17 + 1 17 = 17 * 1 //余数放前面 1 = 120 * 1 + 7 * (-17) 1 = 120 * 1 + 7 *(-17) 故d = -17 k = 1 在RSA中d必须是正整数，所以将它翻转 d=120 + （-17）=103 故公钥为（n,e）=(143,7) 私钥为（n,d）=(143,103) 

（二）、加密解密过程

求出公钥和私钥，就可以对信息进行加密和解密

一、通过公钥进行加密（n,e）

M^e ≡ c (mod n) 13^7 = 117 (mod 143) 

二、通过私钥进行解密（n,d）

C^d ≡ M (mod n) 117^103 = 13 (mod 143) 

换句通俗的话说C的d次方除以n的余数为M

(三)、RSA安全性

在已知n和e的情况下即（公钥），能否推导出d？

 （1）ed≡1 (mod φ(n))。只有知道e和φ(n)，才能算出d。 　　（2）φ(n)=(p-1)(q-1)。只有知道p和q，才能算出φ(n)。 　　（3）n=pq。只有将n因数分解，才能算出p和q。 

但现实生活中，不可能跟我们举例子一样那么小，而且大整数的因数分解，是一件非常困难的事情，例如：

 4949 　　5334 　　0726 　　0899 　　0557 　　1702 　　3116 　　0665 　　13 

没法对这个整数进行因数分解，过于大了，而且目前激活成功教程的只有暴力激活成功教程，所以RSA才号称是地球上最安全的算法。

总结：这次总结更加详细的了解了RSA的原理以及涉及的数学原理，接下来就通过做题来进行巩固。

参考博客：
RSA算法基础详解
RSA算法原理（二）
RSA超详细讲解