RSA加密算法,针对考试,必拿分

博主： ZaunEkko
发布时间：2021 年 06 月 05 日
4942次浏览
5 条评论
1991字数
分类：考试

# RSA加密算法,针对考试,必拿分

来了,为了解决最近的考试,我整理一个网络安全必考的知识点,如果你学过数论,应该很容易知道是RSA加密算法是什么原理,但这里不深究,仅方便考试,不多说,进入正题,本篇会写的很干,原理不赘述,只讲如何做就行~~

## 例题

e = 31,n = 3599,d = ?

## 1.确定p,q,e,n,d的关系,求φ(N)~~

首先,致命一击的题目一般会给我们e,n,让我们求d,只给我们两个,就已经够了,因为p,q是隐含的,n = p*q~~

本题为例,3599=(60+1)(60-1)可知p=61,q=59~~

φ(N)=(p-1)(q-1)=58*60=3480

## 2.列出ed - kφ(N) = 1的式子,求解

1. ed - kφ(N) = 1
2. 设x = d, y = -k
3. 则ex+yφ(N) = 1 ,即 31x + 3480y = 1
4. 辗转相除法(欧几里得算法)求最大公约数,**分解到余数为1**
   
   3480 = 31x112 + 8  (3480/31算出商和余数) 再这里我们用下面这个式子表示
   
   8 = 3480 + 31x (-112) 记为③
   
   下一步被除数31 = 8 x3 +7再用下式表示
   
   7 = 31 + 8 x(-3)记为②
   
   下一步被除数8 = 7x1 + 1记为① 此时,我们发现余数为1,停止~~
   
   草纸上为清楚表示,将4步骤化为如下的写法~~
   
   3480 = 31 x 112 + 8			|			8 = 3480 + 31 x (-112)       ③
   
   31 = 8 x 3 + 7						|            7 = 31 + 8 x (-3)  				②
   
   8 = 7 x 1 + 1							|			1 = 8 + 7 x(-1)					①
5. 回代
   
   ②代入①得到一个式子//也就是把7替换成②右边的表达式
   
   1 = 8 + [31 + 8 x (-3)]x(-1) = 31 x (-1) + 8 x 4
   
   ③代入得到的式子//也就是把8替换为③右边的表达式
   
   1 = 31 x (-1) + 8 x 4 = 31 x(-1) + [3480 + 31 x (-112)] x 4 =3480 x 4 + 31 x (-449)
6. 得到x,y,d
   
   我们得到1 = 3480 x 4 + 31 x (-449) 和第3步得到的式子惊人的发现居然对上了,这就是数学的奇妙(也不奇妙,还不快去学数论||ヽ(*￣▽￣*)ノミ|Ю)
   
   1 = 3480 x 4 + 31 x (-449) ,31 x + 3480y = 1 ,则x = -449, y = 4, d = x = -449
   
   又因为d是正整数,d = d + 3480 = 3480 + (-449) = 3031

至此完毕~~

## 3.草纸上或者卷纸上的步骤

那么你自己不看上面的过程自己来练一练吧~~

问:e = 31, n =  3599,求d?

---

n = 3599 = 59x 61

φ(N) = 58 x 60 = 3480

ed - kφ(N) = 1

设x = d ,y = -k

则31x + 3480y = 1

3480 = 31 x 112 + 8		| 8 = 3480 + 31 x (-112) 	③

31 = 8 x 3 + 7					| 7 = 31 + 8 x (-3)	②

8 = 7 x 1 + 1						| 1 = 8 + 7 x (-1)	①

∴②代入①

1 = 8 + [31 + 8 x(-3)] x (-1)

= 31 x (-1) + 8 x 4

③代入

1 = 31 x (-1) + [3480 + 31 x (-112)] x 4

=3480 x 4 + 31 x (-449)

∴ d = x = -449 , y = 4

∵d为正整数

∴d = d + 3480 = 3480 + (-449) = 3031

原理没有深入赘述,如果按照本篇所指引的方法答题,在这里看懂了,再练习一道题,那么就必定拿下了,加油ヾ(◍°∇°◍)ﾉﾞ~~

最后修改：2021 年 06 月 04 日 04 : 40 PM

END

本文作者： ZaunEkko
文章标题：RSA加密算法,针对考试,必拿分
本文地址：https://www.zaunekko.com/archives/24/
版权说明：若无注明，本文皆ZaunEkko原创，转载请保留文章出处。

如果觉得我的文章对你有用，请随意赞赏

5 条评论

在下YB Google Chrome 91.0.4472.77 Windows 10
June 4th, 2021 at 04:46 pm

这个太厉害了，请问博主我可以发到我们专业群里给大家分享嘛

回复
1. ZaunEkko Google Chrome 91.0.4472.77 Windows 10
  June 4th, 2021 at 04:46 pm
  
  @在下YB
  
  不懂就问,我们⌇●﹏●⌇不是一个学校的嘛?
  
  回复
  1. 在下YB Google Chrome 91.0.4472.77 Windows 10
    June 4th, 2021 at 04:48 pm
    
    @ZaunEkko
    
    哇博主居然秒回，什么神仙博主啊，爱了爱了
    
    回复
    
    ZaunEkko Google Chrome 91.0.4472.77 Windows 10
    June 4th, 2021 at 04:49 pm
    
    @在下YB
    
    全站qq,微信推送以及smtp服务哦,也就是说,你评论我可以在qq上或者微信上看到哦,并且,我回复你的时候也会给你发一个邮件哦~~OωO
    
    回复
    
    捏麻麻滴 QQ浏览器 10.8.4552.400 Windows 10
    November 26th, 2021 at 06:44 pm
    
    @ZaunEkko
    
    欸，厉害了这
    
    回复

发表评论取消回复

评论 *

私密评论

名称 *

🎲

邮箱 *

地址

书签网
这张图片很不错
笒鬼鬼
你的文章大图版怎么是这样的，怎么修改的可以分享下？css
笒鬼鬼
站点名称：笒鬼鬼站点链接：https://www.cengui...
笒鬼鬼
站点名称：笒鬼鬼站点链接：https://www.cengui...
TheJan
handsome模板添加服务器状态栏，接口文件，能否发我一下呀？

今日已经过去小时

这周已经过去天

本月已经过去天

今年已经过去个月

RSA加密算法,针对考试,必拿分

ZaunEkko • 2021 年 06 月 05 日

# RSA加密算法,针对考试,必拿分

## 例题

e = 31,n = 3599,d = ?

## 1.确定p,q,e,n,d的关系,求φ(N)~~

首先,致命一击的题目一般会给我们e,n,让我们求d,只给我们两个,就已经够了,因为p,q是隐含的,n = p*q~~

本题为例,3599=(60+1)(60-1)可知p=61,q=59~~

φ(N)=(p-1)(q-1)=58*60=3480

## 2.列出ed - kφ(N) = 1的式子,求解

至此完毕~~

## 3.草纸上或者卷纸上的步骤

那么你自己不看上面的过程自己来练一练吧~~

问:e = 31, n =  3599,求d?

---

n = 3599 = 59x 61

φ(N) = 58 x 60 = 3480

ed - kφ(N) = 1

设x = d ,y = -k

则31x + 3480y = 1

3480 = 31 x 112 + 8		| 8 = 3480 + 31 x (-112) 	③

31 = 8 x 3 + 7					| 7 = 31 + 8 x (-3)	②

8 = 7 x 1 + 1						| 1 = 8 + 7 x (-1)	①

∴②代入①

1 = 8 + [31 + 8 x(-3)] x (-1)

= 31 x (-1) + 8 x 4

③代入

1 = 31 x (-1) + [3480 + 31 x (-112)] x 4

=3480 x 4 + 31 x (-449)

∴ d = x = -449 , y = 4

∵d为正整数

∴d = d + 3480 = 3480 + (-449) = 3031

原理没有深入赘述,如果按照本篇所指引的方法答题,在这里看懂了,再练习一道题,那么就必定拿下了,加油ヾ(◍°∇°◍)ﾉﾞ~~

RSA加密算法,针对考试,必拿分

5 条评论

发表评论取消回复

个人博客同步

VSCode配置MSVC+VSCode使用easyx库,2021.5.13日配置~~

KMP算法以及优化(代码分析以及求解next数组和nextval数组)

最小生成树,Prim算法与Kruskal算法,408方向,思路与实现分析

云服务器Apache+MySQL(远程连接)+PHP等环境安装

C++PRIMER第二章前半部分答案

VSCode配置MSVC+VSCode使用easyx库,2021.5.13日配置~~

网络工程实验安排

C++PRIMER第五版练习题答案第一章

最小生成树,Prim算法与Kruskal算法,408方向,思路与实现分析

RSA加密算法,针对考试,必拿分

5 条评论

发表评论 取消回复

RSA加密算法,针对考试,必拿分

发表评论取消回复