ZaunEkko - 考试
type: channel
link: https://blog.zaunekko.com/tag/%E8%80%83%E8%AF%95/
items: RSA加密算法,针对考试,必拿分

RSA加密算法,针对考试,必拿分
type: item
date: 2021-06-04T16:33:00+08:00
description: 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=34802.列出ed - kφ(N) = 1的式子,求解ed - kφ(N) = 1设x = d, y = -k则ex+yφ(N) = 1 ,即 31x + 3480y = 1辗转相除法(欧几里得算法)求最大公约数,分解到余数为13480 = 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 = 3480ed - kφ(N) = 1设x = d ,y = -k则31x + 3480y = 13480 = 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原理没有深入赘述,如果按照本篇所指引的方法答题,在这里看懂了,再练习一道题,那么就必定拿下了,加油ヾ(◍°∇°◍)ﾉﾞ~~​