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 日
© 允许规范转载
END
本文作者：
 文章标题：RSA加密算法,针对考试,必拿分
 本文地址：https://blog.zaunekko.com/archives/24/
 版权说明：若无注明，本文皆ZaunEkko原创，转载请保留文章出处。
如果觉得我的文章对你有用，请随意赞赏