RSA加密解密原理

article/2025/3/18 17:32:49

引言
        CTF密码学类题目中,RSA加密可谓是很重要且常见的加密类型,今天就总结下 RSA加密的原理及解密方法。


文章目录

      • RSA算法简介:
        • 1、什么是非对称加密算法:
        • 2、RSA 加密原理:
        • 3、RSA加密算法过程详解:
          • 1、找出质数 :
          • 2、计算公共模数:
          • 3、计算欧拉函数 φ(n):
          • 4、计算公钥 e:
          • 5、计算私钥 d:
          • 6、加密生成密文:
          • 7、解密生成明文:
        • 4、示例:
        • 5、例题:
          • 1、easy_RSA:
          • 2、i春秋 RSA :

RSA算法简介:

  • RSA加密算法是一种 非对称加密 算法,RSA算法相比别的算法思路非常清晰,但是想要破解的难度非常大。

  • RSA算法基于一个非常简单的数论事实:两个素数相乘得到一个大数很容易,但是由一个大数分解为两个素数相乘却非常难。

1、什么是非对称加密算法:

  • 对称加密 算法使用同一个密钥进行加密解密的方式不同,非对称加密 算法是使用不同密钥进行加密和解密的算法,也称为公私钥加密。

非对称加密算法实现机密信息交换的基本过程:

  • 甲方生成 一对密钥 并将其中的一把作为 公钥 向其它方公开,得到该公钥的乙方使用该密钥对机密信息进行加密后再发送给甲方,甲方再用自己保存的另一把 私钥 对加密后的信息进行解密。

图解:
在这里插入图片描述

2、RSA 加密原理:

了解了非对称加密算法的原理,我们再来说说 RSA 加密算法的基本流程。

如图:在这里插入图片描述

3、RSA加密算法过程详解:

先来了解一下什么是 互质数:

  • 两个或多个整数的公因数只有1的非0自然数,则两个非0自然数叫做互质数。例如 2 和 3,公因数只有1,所以为互质数。
1、找出质数 :

随机找两个质数 p 和 q ,p 与 q 越大,越安全。

2、计算公共模数:
 n = p * q 

假设 p = 65 ,q = 71。计算他们的乘积 n = p * q = 4615 ,转化为二进制为 1001000000111,即该加密算法即为 13 位。位数越长,算法则越难被破解。实际应用中,RSA密钥一般是1024位,重要场合则为2048位。

3、计算欧拉函数 φ(n):
φ(n) = φ(p*q) = (p-1)(q-1)

φ(n) 表示:在小于等于 n 的正整数之中,与 n 构成互质关系的数的个数。

例:

在 1 到 8 之中,与 8 形成互质关系的是1、3、5、7,所以 φ(n) = 4。

计算公式(即欧拉函数)为

前提:P 与 Q 均为质数

φ(n) = φ(P*Q)= (P-1)(Q-1) 

设:

P = 65 ,Q = 71

φ(n) = 64 * 70 = 4480 

即有4480 个数与 n(4615)互质。

4、计算公钥 e:
1 < e < φ(n)

要求:

  • e 的取值必须是整数
  • e 和 φ(n) 必须是互质数
5、计算私钥 d:

计算公式:

e * d % m = 1  其中(φ(n) = m)

即找一个整数 d,使得 (e * d ) % m = 1,等价于 e * d - 1 = y * m ( y 为整数)

得到 d ,实质就是对下面二元一次方程求解:

e * x - m * y = 1 e,m为已知量,求 x,y。

这个方程可以用 扩展欧几里得算法 求解,此处就不详细介绍了,可以看这个了解下: 扩展欧几里得算法

得到:

  • 公钥=(e,n)

  • 私钥=(d,n)

对外,只暴露公钥。

6、加密生成密文:

C = M e M^e Me mod n

C:密文 M:明文

7、解密生成明文:

M = C d C^d Cd mod n

C:密文 M:明文


下面举一个完整的例子

4、示例:

1、找出质数 p 、q :

p = 3  
q = 11

2、计算公共模数 n:

n = p * q = 3 * 11 = 33
n = 33

3、计算欧拉函数 φ(n):

φ(n) = (p-1)(q-1) = 2 * 10 = 20
φ(n) = 20

4、计算公钥 e:

1 < e < φ(n)
1 < e < 20

e 的取值范围为: { 3, 7, 9, 11, 13, 17, 19 }

为了方便测试,我们取最小的值 e =3,3 和 φ(n) = 20 互为质数,满足条件。

5、计算私钥 d:

e * d % φ(n) = 1
3 * d % 20 = 1   

计算出 d = 7

6、公钥加密:

公式:C = M e M^e Me mod n

随便拿一个数字,这里方便演示 取 M = 2

C = 2 3 2^3 23 % 33 = 8

" M = 2 " 经过RSA加密后变成了 " C = 8 "

7、私钥解密:

M = C d C^d Cd mod n

C = 8
d = 7
n = 33

计算:

M = 8 7 8^7 87 % 33

解得: M = 2


🆗,简单了解 RSA的基本原理之后,来看几个CTF中的RSA例题。

5、例题:

1、easy_RSA:

在这里插入图片描述
打开附件:
在这里插入图片描述
这题很简单,就是求参数d 的值,那么如何计算d 呢?也就是如何求 e * x - m * y =1 式子中的 x ?

步骤:

1、先计算欧拉函数:
在这里插入图片描述
得到 φ(n) = 2135733082216268400

2、求 d:

根据加密原理,解密的方法就是:把欧拉函数的值 +1,再除以17 * n(这里 n 先取1)
在这里插入图片描述
得到 d = 125631357777427553,尝试提交flag: cyberpeace{125631357777427553} 正确,看来 n 的值确实为 1 。( ̄▽ ̄)"

提供一个求私钥脚本:

#!/usr/bin/env python3
# -*- coding:utf-8 -*-
import gmpy2p = 473398607161
q = 4511491
e = 17m = (p-1)*(q-1)
d = int(gmpy2.invert(e,m)) //invert: 求逆元,返回值是一个 mpz 对象
print('私钥为:',d)

运行结果(我的python出了点小问题):
在这里插入图片描述
得到 d = 125631357777427553

2、i春秋 RSA :

在这里插入图片描述
打开附件:
在这里插入图片描述
可以看到题目给出了 n,e,c 三个值 ,求明文的值。

首先先对 n 进行因式分解,使用在线网站:大数分解网站

得到 p ,q :

在这里插入图片描述

p = 310935513029228809998830208036655366162721470228774287453148308675193510132489142448801010943658159980501154153084396100667001391643762749806500051502679498536716532334917842894939889468693960937309663256592497965458780801192062835123429808
544757340971089756707788360038227894054989413747980167536893779923551227744017809301855984582408943622461942486239113822841696775958645014753081946441406022729616992302829930205076689399802050792392219242304302303180769915076199603301447453
07022538024878444458717587446601559546292026245318907293584609320115374632235270795633933755350928537598242214216674496409625928797450473
q = 310935513029228809998830208036655366162721470228774287453148308675193510132489142448801010943658159980501154153084396100667001391643762749806500051502679498536716532334917842894939889468693960937309663256592497965458780801192062835123429808
544757340971089756707788360038227894054989413747980167536893779923551227744017809301855984582408943622461942486239113822841696775958645014753081946441406022729616992302829930205076689399802050792392219242304302303180769915076199603301447453
07022538024878444458717587446601559546292026245318907293584609320115374632235270795633933755350928537598242214216674496409625928997877221

2、相关参数都已得到,就可以编写脚本求明文信息了:

#!/usr/bin/env python
# coding:utf-8
import gmpy2   p = gmpy2.mpz(31093551302922880999883020803665536616272147022877428745314830867519351013248914244880101094365815998050115415308439610066700139164376274980650005150267949853671653233491784289493988946869396093730966325659249796545878080119206283512342980854475734097108975670778836003822789405498941374798016753689377992355122774401780930185598458240894362246194248623911382284169677595864501475308194644140602272961699230282993020507668939980205079239221924230430230318076991507619960330144745307022538024878444458717587446601559546292026245318907293584609320115374632235270795633933755350928537598242214216674496409625928997877221)
q = gmpy2.mpz(31093551302922880999883020803665536616272147022877428745314830867519351013248914244880101094365815998050115415308439610066700139164376274980650005150267949853671653233491784289493988946869396093730966325659249796545878080119206283512342980854475734097108975670778836003822789405498941374798016753689377992355122774401780930185598458240894362246194248623911382284169677595864501475308194644140602272961699230282993020507668939980205079239221924230430230318076991507619960330144745307022538024878444458717587446601559546292026245318907293584609320115374632235270795633933755350928537598242214216674496409625928797450473)
e = gmpy2.mpz(65537)#计算私钥d
m = (p - 1) * (q - 1)
d = gmpy2.invert(e, m)
print "private key:",d#求密文M
c = gmpy2.mpz(168502910088858295634315070244377409556567637139736308082186369003227771936407321783557795624279162162305200436446903976385948677897665466290852769877562167487142385308027341639816401055081820497002018908896202860342391029082581621987305533097386652183849657065952062433988387640990383623264405525144003500286531262674315900537001845043225363148359766771033899680111076181672797077410584747509581932045540801777738548872747597899965366950827505529432483779821158152928899947837196391555666165486441878183288008753561108995715961920472927844877569855940505148843530998878113722830427807926679324241141182238903567682042410145345551889442158895157875798990903715105782682083886461661307063583447696168828687126956147955886493383805513557604179029050981678755054945607866353195793654108403939242723861651919152369923904002966873994811826391080318146260416978499377182540684409790357257490816203138499369634490897553227763563553981246891677613446390134477832143175248992161641698011195968792105201847976082322786623390242470226740685822218140263182024226228692159380557661591633072091945077334191987860262448385123599459647228562137369178069072804498049463136233856337817385977990145571042231795332995523988174895432819872832170029690848)
print "明文:"
M  =  pow(c,d,p*q)
print '10进制: '+str(M)
flag = str(hex(M))[2:]# 从第3位为往后截取
print '16进制: '+flag
print 'ASCII码: '+flag.decode('hex')

注释:

  • gmpy2.mpz(x): 初始化一个大整数x
  • pow( x, y, z): 计算 x y x^y xy mod z

得到 flag:
在这里插入图片描述
🆗,关与RSA的总结暂时就到这里了,以后发现好用的方法或解题技巧会接着更新。╰( ̄ω ̄o)


http://chatgpt.dhexx.cn/article/5W53oppI.shtml

相关文章

# RSA加密原理和一些知识笔记

RSA加密原理和一些知识笔记 原文地址&#xff1a; 01&#xff1a;RSA 加密和原理 .pem .csr .crt .der .p12文件的区别 base64 (https://www.cnblogs.com/zyzmlc/p/12875277.html) 写得不错&#xff0c;这应该是他的学习笔记&#xff0c;我做了一些错误修正 复习&#xff1a;…

Rsa加密原理与简单实现

源码&#xff1a;https://gitee.com/Cheney822/programmes/blob/master/rsa.py 1背景 1.1 数据加密 指的是根据一定规则&#xff0c;将数据处理成不规则的数据&#xff0c;使得人们除非有了关键的钥匙以及得知这个规则&#xff0c;难于得知无规则数据的真实含义。这个一定规则…

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;那…