Rsa加密原理与简单实现

article/2025/3/18 17:37:35

源码:https://gitee.com/Cheney822/programmes/blob/master/rsa.py

1背景

1.1 数据加密

指的是根据一定规则,将数据处理成不规则的数据,使得人们除非有了关键的钥匙以及得知这个规则,难于得知无规则数据的真实含义。这个一定规则 就是加密算法,这个钥匙就是密钥。

数据加密分为对称密钥加密以及非对称密钥加密:

  • 对称密钥加密: 双方共同持有这个密钥,发送方用这个密钥按照指定的算法将数据加密,再发出去;接收方用这个密钥将接收到的数据解密,以得到真实的数据含义。由于双方都持有这个密钥,而且内容相同,所以叫对称密钥
  • 非对称密钥加密:这种加密方式的密钥是一对,发送方用其中的一把钥匙将数据加密,再发出去;接收方用这对密钥的另一把钥匙将数据解密,以得到真实的数据含义。发送方持有密钥中的一把钥匙,接收方持有另外一把。接收方持有的钥匙叫 私钥, 而接收方持有的这把钥匙叫公钥 。两把钥匙不一样,所以叫做非对称密钥加密,也叫做公开密钥算法。

1.2 非对称密钥加密

RSA公开密钥密码体制是一种使用不同的加密密钥与解密密钥,“由已知加密密钥推导出解密密钥在计算上是不可行的”密码体制 。
在公开密钥密码体制中,加密密钥(即公开密钥)PK是公开信息,而解密密钥(即秘密密钥)SK是需要保密的。加密算法E和解密算法D也都是公开的。虽然解密密钥SK是由公开密钥PK决定的,但却不能根据PK计算出SK 。
正是基于这种理论,1978年出现了著名的RSA算法,它通常是先生成一对RSA密钥,其中之一是保密密钥,由用户保存;另一个为公开密钥,可对外公开,甚至可在网络服务器中注册。为提高保密强度,RSA密钥至少为500位长,一般

推荐使用1024位。这就使加密的计算量很大。为减少计算量,在传送信息时,常采用传统加密方法与公开密钥加密方法相结合的方式,即信息采用改进的DES或IDEA对话密钥加密,然后使用RSA密钥加密对话密钥和信息摘要。对方收到信息后,用不同的密钥解密并可核对信息摘要。
RSA是被研究得最广泛的公钥算法,从提出到现在已近三十年,经历了各种攻击的考验,逐渐为人们接受,普遍认为是目前最优秀的公钥方案之一。

RSA公开密钥密码体制的原理是:根据数论,寻求两个大素数比较简单,而将它们的乘积进行因式分解却极其困难,因此可以将乘积公开作为加密密钥.

2概要设计

2.1 函数

程序涉及到的函数及功能如下:

image-20220406001245868

2.2 接口

程序文件对外开放的方法有三个,分别是加解密和获取密钥。

  • 首先是获取密钥newkeys函数,该函数获取一个参数nbits用来指定密钥的位数。函数返回两个list,每个list内有两个元素,分别为[N, e], [N, d]。
  • 然后是加密函数,该函数接受两个参数,分别为:待加密的明文和公钥。待加密的信息为Bytes类型,公钥为[int, int]类型,返回值为一个list,其中的每一项分别对应bytes的每一位。
  • 最后是解密函数,该函数与加密函数类似。不同之处在于其接受的密文是list类型(对应加密的返回值),返回的是bytes类型(对应用户输入系统的数据类型)
    加解密过程中数据的变化如下图所示:
image-20220406001339131

以上对外的接口内部会调用内部函数(以__开头),外部在使用时不建议直接调用。

2.3 流程

RSA算法的具体描述如下:

(1)任意选取两个不同的大素数p和q计算乘积
img

(2)任意选取一个大整数e,满足
img |

整数e用做加密钥(注意:e的选取是很容易的,例如,所有大于p和q的素数都可用)

(3)确定的解密钥d,满足

img

img

是一个任意的整数;所以,若知道e和 img,则很容易计算出d ;

(4)公开整数n和e,秘密保存d ;

(5)将明文m(m<n是一个整数)加密成密文c,加密算法为
img |

(6)将密文c解密为明文m,解密算法为:

img

然而只根据n和e(注意:不是p和q)要计算出d是不可能的。因此,任何人都可对明文进行加密,但只有授权用户(知道d)才可对密文解密

3详细设计

生成密钥

  • 第一步,随机选择两个不相等的质数p和q。
  • 第二步,计算p和q的乘积n。
  • 第三步,计算n的欧拉函数φ(n)。φ(n) = (p-1)(q-1)
  • 第四步,随机选择一个整数e,条件是1< e < φ(n),且e与φ(n) 互质。
  • 第五步,计算e对于φ(n)的模反元素d。所谓"模反元素"就是指有一个整数d,可以使得ed被φ(n)除的余数为1。
  • 第六步,将n和e封装成公钥,n和d封装成私钥。
img

3优化的判断素数方法

主要优化的规则

  • 1.大于3的素数一定在6的倍数前一个或后一个(如素数37在36的后面)
  • 2.要判断n是否为素数,只需要让n从2开始,依次除到根号n即可
  • 3.在进行“让n从2开始,依次除到根号n”过程中,若n除以2的余数不为0,可以直接跳过[2, sqrt(n)]里面的所有偶数

复杂度分析

1.最基础的算法:也就是让n从2开始判断,一直到n-1
若遇到的数是素数时,此时需要进行n-2次判断
当遇到的不是素数时,要进行a(2<a<n-2)次判断
也就是说时间复杂度为n

2.改进后的算法:
根据规则二,判断素数只要从[2,sqrt(n)]即可,此时复杂度为sqrt(n)
根据规则3,无论如何都可以不判断2之后的偶数(当n大于2,当n除尽2时,n不为素数,之后不需要判断,如果n除不尽2时,之后的偶数不要判断)
假设n可以除尽2和不可以除尽2概率相等,那此时复杂度为sqrt(n)/4
根据规则一,只有1/3的数要进行判断,此时复杂度为sqrt(n)/12
也就是说时间复杂度为sqrt(n)/12

快速幂取模运算

输入x,n,p,如何计算xn mod p?

暴力的做法就是直接将n个x乘起来,最终mod p。理论上来说,这样做显然是可以的,但是很明显,这样做的话,程序要循环n次,也就是说它的时间复杂度是O(n),如果n非常大,算法的效率就特别低,为此引入列快速幂运算。

快速幂的本质就是:底数不断取2次幂,指数不断除2次幂,直到指数除到为1,计算完毕。原先的n次幂运算,它的时间复杂度为O(n),而如果是快速幂运算,时间复杂度就被降到了O(log2n)。

但是,这个过程中,如果指数的奇数的话,就没有办法除2次幂。对于整数的除,都是整除。例如求2的5次方,经过一次快速幂,它并不会变成4的2.5次方,而是4的2次方,因为4整除2等于2。跟实际还是差了一个4的0.5次方,也就是“原底数”。

每一次到奇数幂时,就会有这些原底数被漏乘,最终形成一群因为是奇数幂而漏乘的“底数群”。因此,我们需要对奇数次幂的情况进行特判,存储这些没乘上的底数群,最终return的时候将它们都乘上。

由上,引入一个每一次处理奇数次幂时,未被底数乘上的待乘底数群。这个底数群的初始值为1,当为奇数次幂时,这个未乘的底数群就以乘以目前的底数的形式进行更新。最后,这个未乘的底数群乘幂为1时不包含奇数幂时遗漏的底数的不完全结果,就是快速幂的最终结果。

然后再加入取模操作即可。

扩展欧几里得算法

​ 欧几里得算法是求最大公约数的算法, 也就是辗转相除法。记 gcd(a,b) 为a和b的最大公约数,欧几里得算法的基本原理是gcd(a,b)==gcd(b,a%b),(b!=0) 和 gcd(a,0)==a 。

应用在RSA加密算法求逆元中:

​ 首先我们知道,再求两个数的最大公约数的时候可以用欧几里得算法。在欧几里得算法中,通过辗转相除,当余数为0的时候最后的除数就是两个数的最大公约数。

​ 而在其扩展算法中,我们已知两个数的最大公约数,我们已知 ax = 1(mod p),展开就是 ax mod p = 1,首先我们先求 p = x1 * a + p1,然后p = a,a = p1,迭代下去

​ 知道pi = 1(i表示出了i次)为之,然后就可以得出 1 = p - xi * a,此时的a和p已经不是我们初始的a和p了,我们需要往前推,推到 1= yp + x*a 为止,此时得出的x就是a的逆元。

​ 如果逆元x为负数,或者比p大,要对其就行取余操作。

4运行测试

4.1获取密钥

img

4.2加密

img

4.3解密

img

4.4完整操作

img

结果:img


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

相关文章

RSA加密原理简述

RSA加密原理简述 RSA简介&#xff1a;前置技能&#xff08;数论知识&#xff09;RSA加密原理 RSA简介&#xff1a; RSA加密算法使用不同的加密密钥与解密密钥&#xff0c;且由已知加密密钥推导出解密密钥在计算上是不可行的&#xff0c;以此来保障安全。 RSA算法通常是先生成一…

RSA加密基本原理

工作中遇到RSA加密的内容&#xff0c;特意学习了一下&#xff0c;作为自己的笔记吧。&#xff08;公钥和私钥得到不在本次文章范围内&#xff0c;此处只有基本原理&#xff09;方便自己更好的理解。 笔记来源于bilibili的视频&#xff0c;地址如下&#xff1a; https://www.bil…

非对称加密算法--RSA加密原理详解

密码学是在编码与破译的斗争实践中逐步发展起来的,并随着先进科学技术的应用&#xff0c;已成为一门综合性的尖端技术科学。 密码学发展史 在说RSA加密算法之前&#xff0c; 先说下密码学的发展史。其实密码学的诞生&#xff0c;就是为了运用在战场&#xff0c;在公元前&#…

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

前言&#xff1a;之前在做密码学题的时候了解了一下RSA&#xff0c;但总感觉那时总结的过少&#xff0c;而且也理解的不到位&#xff0c;这次就再来详细的了解一下&#xff0c;并通过做题来巩固一下。 一、对称加密与非对称加密 对称加密&#xff1a; 加密和解密用的是同一密…

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

就目前而言&#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;他们搜集了历史客户行为的部分数据以及目标客户的信息,希望通过历史数据对目标客户进行预测哪些客户会是潜在的违约客户,从而缩小目标范围,实现低风险贷款发…