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的式子,求解
- ed - kφ(N) = 1
- 设x = d, y = -k
- 则ex+yφ(N) = 1 ,即 31x + 3480y = 1
辗转相除法(欧几里得算法)求最大公约数,分解到余数为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) ①
回代
②代入①得到一个式子//也就是把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)
得到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
原理没有深入赘述,如果按照本篇所指引的方法答题,在这里看懂了,再练习一道题,那么就必定拿下了,加油ヾ(◍°∇°◍)ﾉﾞ~~
5 条评论
这个太厉害了，请问博主我可以发到我们专业群里给大家分享嘛
不懂就问,我们⌇●﹏●⌇不是一个学校的嘛?
哇博主居然秒回，什么神仙博主啊，爱了爱了
全站qq,微信推送以及smtp服务哦,也就是说,你评论我可以在qq上或者微信上看到哦,并且,我回复你的时候也会给你发一个邮件哦~~OωO
欸，厉害了这