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

article/2025/3/18 17:28:09

前言:之前在做密码学题的时候了解了一下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为正整数)

可以看出,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 =(n)
所以7*d+120*k=1,这个方程可以由扩展欧几里得算法(辗转相除法)来得出结果:
六、120 = 7 * 17 + 117 = 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。

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

	1230186684530117755130494958384962720772853569595334792197322452151726400507263657518745202199786469389956474942774063845925192557326303453731548268507917026122142913461670429214311602221240479274737794080665351419597459856902143413

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

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

参考博客
RSA算法基础详解
RSA算法原理(二)
RSA超详细讲解


http://chatgpt.dhexx.cn/article/EOX27B3O.shtml

相关文章

如何利用好大数据挖掘潜在用户?

就目前而言&#xff0c;现在的大数据技术为绝大部分的业务提供了许多功能&#xff0c;同时还提高了效率和收入。当然除了这些以外&#xff0c;大数据分析还为公司的潜在客户和现有客户提供了许多好处。这些优点让很多公司对于大数据技术十分向往&#xff0c;那么怎么能够利用好…

激发客户潜在需求

企业不光要看到客户的显现需求&#xff0c;更要挖掘客户的潜在需求&#xff0c;因为客户的潜在需求是可以转化为显现需求的&#xff0c;满足客户的潜在需求可以为企业带来更多经济效益。 前言 潜在需求是指消费者虽然有明确意识的欲望&#xff0c;但由于种种原因还没有明确的显…

HubSpot入站营销:吸引潜在客户的7大技巧!

入站营销是当今数字化时代的重要策略之一。它不仅可以帮助企业吸引潜在客户、建立品牌知名度&#xff0c;还能促进客户参与并提高客户满意度。今天运营坛将带领大家深入探讨HubSpot入站营销的理论和实践&#xff0c;包括如何开始入站营销、入站营销的框架以及关键技巧。 一、什…

Python决策树、随机森林、朴素贝叶斯、KNN(K-最近邻居)分类分析银行拉新活动挖掘潜在贷款客户

最近我们被客户要求撰写关于银行拉新活动的研究报告&#xff0c;包括一些图形和统计输出。 项目背景&#xff1a;银行的主要盈利业务靠的是贷款&#xff0c;这些客户中的大多数是存款大小不等的责任客户&#xff08;存款人&#xff09;。银行拥有不断增长的客户。该银行希望增…

潜在客户需要单独管理吗?

通常销售型企业会将客户类型区分为&#xff1a;潜在客户、意向客户和购买客户等状态。那么&#xff0c;潜在客户需要单独拿出来进行管理吗&#xff1f;。 企业从展会、网站、广告及其它市场活动收集来的潜在客户是客户挖掘、获得、细分的主要目标受众&#xff0c;这些线索客户的…

python数据分析与挖掘实战---航空公司客户价值分析

航空公司客户价值分析 一、 背景与挖掘目标 **** 客户关系管理是企业的核心问题&#xff0c;关键在于客户的分类&#xff1a;区别无价值客户&#xff0c;高价值客户&#xff0c;针对不同客户群体有的放矢投放具体服务方案&#xff0c;实现企业利润最大化的目标。 各大航空公…

银行电话精准营销的探索性分析并基于XGboost进行潜在客户预测建模

问题背景&#xff1a; 随着利率市场化改革推进&#xff0c;银行业整体面临息差收窄的压力&#xff0c;不少银行将中间业务收入作为新的利润增长点。其中&#xff0c;以招商银行为代表的一批大型股份制银行&#xff0c;更是将大财富管理模式做到了极致&#xff0c;中间收入占比的…

如何和产品潜在的客户沟通

老于笔记01.10 一个人幸运的前提其实是他有能力改变自己。 正文 和产品潜在的客户沟通很有必要&#xff0c;有时候还需要对他们提供必要指导&#xff0c;这样有助于挖掘他们需求&#xff0c;将他们变成真正的消费者。 1 C端产品的第一批用户很可能来自推消以外的其他渠道&#…

salesforce-使用Web-to-Lead引入网站的潜在客户

salesforce的web-to-lead功能可以将网站的流量转化为潜在客户&#xff0c;只需要用户填写我们在salesforce后台设定好的表单&#xff0c;即可实现将用户填写的信息导流到salesforce后台&#xff0c;从而统一管理网站的潜在客户。 我个人比较习惯在英文环境下操作&#xff0c;我…

链脉刘松华:如何用AI名片发掘更多潜在客户

本文来自链脉联合创始人:刘松华 乐尚七色光美术教育创始人 懂孩子家庭教育讲师 润阳父母大学家庭教育讲师 润阳演讲大学演说训练讲师 链脉名片联合创始人 新营销能量讲师 链脉创富讲师 销售行业需要不断的签单成交就需要不断有潜在客户的加入,所以潜在客户的获取关乎到…

Python爬虫爬取知乎用户信息+寻找潜在客户

【Python应用】寻找社交网络中的目标用户 日后的更新&#xff1a;由于是很久以前的课程设计项目&#xff0c;完整的源码已经不见了&#xff0c;关键的网页数据获取和解析的部分代码我在文章中已经贴出来了&#xff0c;但写的也不够好&#xff0c;如果想参考爬取知乎的同学&…

用户画像实战:基于Kmeas的电商潜在客户识别

电商潜在客户识别 前言 1、任务描述 此数据集仅用于学习客户细分概念&#xff0c;也称为市场篮子分析。我将以最简单的形式使用无监督的ML技术&#xff08;KMeans聚类算法&#xff09;来演示这一点。 通过超市商场会员卡信息&#xff0c;我们可以得到一些关于客户的基本数据…

数据分析,把握商机 关键词采集工具助你挖掘潜在客户

数据分析&#xff0c;是指对大量的数据进行收集、处理、分析和解析的过程&#xff0c;从而发现其中隐含的规律、趋势和价值信息。而在商业领域&#xff0c;数据分析则是一种能力&#xff0c;可以帮助企业更好地了解市场、客户和竞争对手&#xff0c;把握商机&#xff0c;提高效…

营销自动化如何帮助你挖掘潜在客户?

点击上方“AI公园”&#xff0c;关注公众号&#xff0c;选择加“星标“或“置顶” 作者&#xff1a;Xen Chia 编译&#xff1a;ronghuaiyang 导读 看看如何使用营销自动化工具来得到潜在客户。 你如何争取潜在客户&#xff1f; 如果你的答案将是“购买潜在客户”&#xff0c;那…

Python实现预测信用卡潜在客户

一、数据集 有一家名为Happy Customer Bank (快乐客户银行) 的银行&#xff0c;是一家中型私人银行&#xff0c;经营各类银行产品&#xff0c;如储蓄账户、往来账户、投资产品、信贷产品等。 该银行还向现有客户交叉销售产品&#xff0c;为此他们使用不同类型的通信方式&…

数据挖掘(二)预测潜在贷款发放客户

注&#xff1a;参考多篇csdn及b站文章所得 一、实验背景 某机构想要预测哪些客户可能会产生贷款违约行为&#xff61;他们搜集了历史客户行为的部分数据以及目标客户的信息,希望通过历史数据对目标客户进行预测哪些客户会是潜在的违约客户,从而缩小目标范围,实现低风险贷款发…

淘宝客服话术《挖掘每一个潜在客户》

在这个电商行业的时代&#xff0c;作为一名淘宝客服人员&#xff0c;与店铺之间的关系是密不可言的&#xff0c;客服相当于店铺的门面&#xff0c;也是和客户第一接触者&#xff0c;重要性可想而知。 随着客服岗位的泛滥&#xff0c;客服之间的能力也是参差不齐的&#xff0c;想…

依据数据简单分析,发掘潜在客户

大数据概论作业(一) 信息技术的不断发展让人们离不开科技,我们每天使用各类电子产品所产生的信息数据不计其数,而这些数据的合理利用将会使我们的生活更加的便捷,所以,大数据俨然已成为现在前沿科技。的研究热点,大数据来源于我们生活的方方面面,也必将影响着我们…

生成微信小程序码、URL Scheme和URL Link

通用第一步,获取access_token,需要服务端去获取并缓存 (APPID和APPSECRET在微信小程序后台查看获取) https://api.weixin.qq.com/cgi-bin/token?grant_typeclient_credential&appidAPPID&secretAPPSECRET 1.获取小程序码(通过该接口生成的小程序码&#xff0c;永久有…

如何生成小程序太阳码

近期在小程序管理后台发现了生成太阳码的工具&#xff0c;以此来记录下。 登录微信公众平台&#xff08;https://mp.weixin.qq.com/&#xff09; 菜单栏工具->生成小程序码 输入页面路径->点击确定->右击保存太阳码 注意&#xff1a; 生成的页面路径必须是已发布的&am…