RSA加密解密过程

在每次写CTF题时RSA加密都是我和老火鸡的噩梦，笑死有教程都根本看不懂。而叔叔最近给我推送了一个视频讲的很是通俗，看了一遍就给我懂完了。这里指记录简单的加密解密过程，详细教程请去观看视频。博客中的数据也为视频中所用的

加密解密过程简介

这个加密算法是一个非对称加密算法。用户这边拥有公钥而服务器这边拥有一个私钥。假设公钥中有两个数字（7，33），私钥有（3，33），而33是公钥与私钥所公有的数字。

我们要加密的数据转化为十进制编码假设为3，1，15。

第一步：我们要将我们要加密的三个数字进行7次方运算（也就是公钥中第一个数）。

1
2
3

3  ^ 7 = 2187
1  ^ 7 = 1
15 ^ 7 = 170859375

第二步：我们对刚求得出来的数字除以公钥中第二个数字也就是33来取余。

1
2
3

2187      % 33 = 9
1         % 33 = 1
170859375 % 33 = 27

而得到的这几个数字9，1，27就是3，1，15的密文了，就直接可以发送给对方。

对方接收到密文对其解密的步骤和加密的步骤也是一样的，首先将密文进行私钥中第一个数字的次方运算。

1
2
3

9  ^ 3 = 729
1  ^ 3 = 1
27 ^ 3 = 19683

然后使用私钥的第二个数字33取余。

1
2
3

729   % 33 = 3
1     % 33 = 1
19683 % 33 = 15

我们将得出来的数字与最先加密前的数据进行对比发现是一样的。这就是加密解密的基本流程。我们用公钥加密后的数据私钥可以解密，而私钥加密的数据公钥也一样可以解密。将其变换为公式就是：

1
2
3

设：公钥为（E，N），私钥为（D，N）。
明文^E%N=密文
密文^D%N=明文

公钥私钥制作过程

1. 选取两个质数分别用p和q来表示。（这里假设p=3，q=11。）
2. 将质数相乘，乘机用N来表示。这里的N也就是之前公钥私钥中公用的那个数字。（N=p*q=3*11=33）
3. 使用欧拉函数：将两个质数p和q分别减去1再相乘。得出的数用T来表示。（T=(p-1)*(q-1)=2*10=20）
4. 选出公钥E，而公钥需要符合一下三个条件：（这里设E=3）
   • 公钥必须为质数；
   • 公钥要大于1且小于T（1<公钥<T）；
   • 公钥不能是T的因子。
5. 计算私钥D，公式为（D*E）%T=1。（D=7）

经过以上算法我们就可以得出公钥为（3，33），私钥为（7，33）。

私钥安全问题

私钥使我们不能公开，我们从他计算的公式中可以看出私钥与E也就是公钥和T有关。而公钥我们必要要去公开，所以我们私钥的安全性会受到T的影响。而T是又p和q两个质数得出的，所以我们最开始选的质数p和q就是私钥的关键了。如果p、q值设置的比较大那么T和N都会变的非常大了。这样就会让私钥D的反推工作变的非常困难了。