密码学知识点讲解之RSA(一) – 作者:云影安全团队

0x01 简介

RSA是1977年由罗纳德·李维斯特(Ron Rivest)、阿迪·萨莫尔(Adi Shamir)和伦纳德·阿德曼(Leonard Adleman),RSA是他们三人姓氏开头字母拼在一起组成的。

1606565618_5fc23ef2089f03a2fc267.png!small?1606565618365

0x02 数学储备

●同余运算

●欧拉函数

●欧拉定理

●费马小定理

●欧拉函数:

在数论中,对于正整数n,欧拉函数是小于或等于n的正整数中与n互质的数的数目(因此φ(1)=1)

1606565626_5fc23efa713eb356b3d9f.png!small?1606565626818

●费马小定理:

如果p是一个质数,而整数a不是p的倍数,则有a^{p-1}≡1(mod p)

1606565633_5fc23f0133b4ff40e6495.png!small?1606565633485

0x03 算法概况

●数据处理:

1、任意选择两个不同的较大质数p与q,并计算n = p x q。

2、我们引入欧拉函数

1606565641_5fc23f09da6ffbbc63cf9.png!small?1606565642183

表示对正整数n来说,小于或等于n的正整数中与n互质的数的数目。那么显然

1606565649_5fc23f111a8fb01b461bc.png!small?1606565649462

(欧拉定理)

3、再次任意选择一个实数e,满足

1606565656_5fc23f1840b6f327ca8c1.png!small?1606565656494

(gcd(x,y)指x和y的最大公因数)

4、计算d,满足

1606565662_5fc23f1eecf4fcbe4a34f.png!small?1606565663256

在以上过程中,(e,n)被称为公钥,(d,n)被称为私钥,公钥被用来加密,而私钥被用来解密。公钥(e,n)会被公开,而私钥(d,n)会被自己保存。也就是说,每个人都可以利用公钥对文件进行加密,而只有拥有私钥的人才可以将加密的文件进行还原解密。

●加解密过程:

→加密:

1606565670_5fc23f265a2a83e47710d.png!small?1606565670646

→解密:

1606565680_5fc23f30892ca5c8c279a.png!small?1606565680836

→原理解释:

让我们分析解密过程:

1606565687_5fc23f37095176cd9b145.png!small?1606565687291

接着根据欧拉-费马定理

1606565695_5fc23f3f411643dbdf9f3.png!small?1606565695574

这样一来就得到原来的明文m啦

本次的RSA讲解只是为大家介绍RSA运作的原理及过程,之后的文章就会为大家分析CTF比赛中RSA的相关攻击方式,请您持续关注。

致力于网络安全CTF入门培训与青少年网络安全人才培养
关注微信公众号:云影安全

接收我们的最新文章及消息~

图片[12]-密码学知识点讲解之RSA(一) – 作者:云影安全团队-安全小百科

来源:freebuf.com 2020-11-28 20:13:05 by: 云影安全团队

© 版权声明
THE END
喜欢就支持一下吧
点赞0
分享
评论 抢沙发

请登录后发表评论