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

Record my learning process of CTF.

CTF

字数统计: 2.1k阅读时长: 8 min

 2019/08/07   Share

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

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

对称加密：

加密和解密用的是同一密钥，也是最简单、最快速的加密方式，通常使用的密匙相对较小，容易被破解，如果密钥过大，安全性确实可以得到保证，但同样加密和解密的效率将会很低。
因为双方都需要密钥进行加密解密，如果有一方的密钥泄露出去，整个安全性将不复存在，所以这也是对称加密的缺点。

在这里插入图片描述

非对称加密：

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

在这里插入图片描述
下面就来学习属于非对称加密中的RSA算法

RSA概述：

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

RSA算法涉及的数学知识

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

一、互质关系

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

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

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

任意两个质数构成互质关系，比如7和61。

一个数是质数，另一个数只要不是前者的倍数，两者就构成互质关系，比如3和10。

如果两个数之中，较大的那个数是质数，则两者构成互质关系，比如97和57。

1和任意一个自然数是都是互质关系，比如1和99。

p是大于1的整数，则p和p-1构成互质关系，比如57和56。

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可以分解成两个互质的整数之积

1	n = p1 × p2

则

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

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

举个列子：

1
2
3

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)等于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为正整数）

可以看出，a的 φ(n)-1 次方，就是a对模数n的模反元素
在这里插入图片描述

五、模运算

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

举个例子：

1	10 mod 4=2、8 mod 3=2

六、同余

给定一个正整数m，如果两个整数a和b满足a-b能被m整除，即(a-b) mod m=0，
那么就称整数a与b对模m同余，记作a≡b (mod m)，同时可成立a mod m=b

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

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

七、欧几里德算法

欧几里德算法是用来求两个正整数最大公约数的算法
计算公式gcd(a,b) = gcd(b,a mod b)

计算方法：

用较大数除以较小数，再用出现的余数（第一余数）去除除数，再用出现的余数（第二余数）去除第一余数，如此反复，直到最后余数是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，密文为C，则加密公式为：
在这里插入图片描述
假设明文为13，则

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

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

密文为C，明文为M，则解密公式为：
在这里插入图片描述

1 2	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。

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

12301866845301177551304949
　　58384962720772853569595334
　　79219732245215172640050726
　　36575187452021997864693899
　　56474942774063845925192557
　　32630345373154826850791702
　　61221429134616704292143116
　　02221240479274737794080665
　　351419597459856902143413

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

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

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

Next Post

文件包含漏洞——DVWA练习
Previous Post

实验吧——SQL注入 Write up(一)

CATALOG

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

2. RSA算法涉及的数学知识

2.0.1. 一、互质关系
2.0.2. 二、欧拉函数
2.0.3. 三、欧拉定理
2.0.4. 四、模反元素
2.0.5. 五、模运算
2.0.6. 六、同余
2.0.7. 七、欧几里德算法

3. RSA算法

3.0.1. （一）、生成密钥过程：
3.0.2. （二）、加密解密过程
3.0.3. (三)、RSA安全性

