关于RSA算法本身，就提及一下，它是属于非对称密码体制.
基本的加密方式就如下图所示：
c为加密后的密文，m为加密前的明文
其中一般会给出公开密钥n、e的值，这样根据规则，便可以实现加密过程。而题目往往需要进行解密，那么就需要先求解出p、q，随后再求解出私钥d。但有时候题目还是友善的，会把p、q值告诉你，看你运气啦！
那么接下来，主要分成的两个部分内容：
一、求解p、q
首先，我们的题目往往是简单的，即易于破解的！
可以通过寻找最接近n值的一个数（a）平方，然后与 n 做差，如果差值刚好是某一个数（b）的平方数，那么根据平方差公式，可获两个数（a+b）以及（a-b），如果碰巧两个都是素数的话，好耶，问题解决！
若不行，那么继续选择（a+k）的情况，其中 k =1，2，3...再根据上述步骤进行分析就得，总会出来的，毕竟考试考得是方法。
详细的内容部分如下图所示啦：
** 二、在步骤一的基础上，求解密钥d**
这里需要求解的公式就是：
其中 的值我们很容易就能获得
我们直接来看个例子
例子中，最终求得的d值为1019.
这里我个人认为是分成三个部分来看的，不理解算法本身的话，那就学会观察！
左上角运用是是欧几里得法（即辗转相除），如3200/79=40...60；79/60=1...19等等，可以发现就是不断地在让除数变成被除数，让余数变成除数，如此循环，知道余数为0.
而右上角的呢，实际上是在将左上角的等式进行转换，以此表示出每一个余数
好了，有了上述两个铺垫，那么就可以看最下面的式子了。
首先原本需要求解的问题中，mod 取余运算后等于1，那么我们就反过来，往回推！
1=19-36 其中 3 我们可以用 3=60-193 表示，所以原式变成了 1=19-（60-19*3）
补充插曲：等式里面还有3，但不需要再一次代入了，根本原因等会儿说，从反面角度来说，继续代入只会无限死循环。同时，原式中的19 也可以直接代入，只不过也可以集中到接下来的一步在整体代入。
原式中 1=19-（60-193），接下来就处理19了，19=79-601，所以原式就等于
1=（79-601）-（60-（79-601）*3）
同理，再代入60，所以原式就等于
1=（79-（3220-7940）1） -（（3220-7940）-（79-3220-7940）*3）
然后展开就能够获得
1=（-25）3220+101979
转变一下式子，也就是说*101979/3220=25...1 **由此就得到了私钥d！
好了，复盘一下，其实前面两步的铺垫，在我看来就是在寻找除数与商之间的乘积关系，而最后一步，借助的是逆向的思维方式，它在尽力的使1=19-3*6 这个式子不断回推，回推到寻找得到3220与79之间的关系，也就是说，回代的目的就是在构建3200与79的式子。而之前所提及为什么不需要无限回代3，就是因为3只是个中转站，只要和3220、79能够构建起关系就可以了。
总结下来就是，寻找关系（分解），回推，重新构建关系！
希望能够帮到各位欸，纯粹的算法分析就不放在考试向的内容里啦！祝大家考试顺利，反正当时自己看懂了就很开森~
版权归原作者 Flying_fish7 所有， 如有侵权，请联系我们删除。