0x01 简介

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

0x02 数学储备

●同余运算

●欧拉函数

●欧拉定理

●费马小定理

●欧拉函数：

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

●费马小定理：

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

0x03 算法概况

●数据处理：

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

2、我们引入欧拉函数

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

（欧拉定理）

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

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

4、计算d，满足

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

●加解密过程：

→加密：

→解密：

→原理解释：

让我们分析解密过程：

接着根据欧拉-费马定理

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

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

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

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