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

数学、物理等理工
回复
peng
Site Admin
帖子: 197
注册时间: 周五 11月 01, 2019 9:06 am

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

帖子 peng »

前言:之前在做密码学题的时候了解了一下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可以分解成两个互质的整数之积
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)等于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整除,只取所得的余数作为结果,就叫做模运算。

举个例子:
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,则
M^e ≡ c (mod n)
13^7 = 117 (mod 143)
二、通过私钥进行解密(n,d)

密文为C,明文为M,则解密公式为:
在这里插入图片描述
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的原理以及涉及的数学原理,接下来就通过做题来进行巩固。

https://bealright.github.io/2019/08/07/ ... %E7%90%86/

回复