RSA 算法的加密方法(对大数的)解析 之一
本帖最后由 tfrist 于 2020-12-29 01:43 编辑我同时也上传了一份word版的到我的百度盘。有兴趣的去下载:
--------------------------------------------------------------------------
链接: https://pan.baidu.com/s/1o3TN0mV9kkMvr-Xz9k_cfQ
提取码: dac4
--------------------------------------------------------------------------
第二篇已经发出 RSA 算法的加密方法(对大数的)解析 之二 谢谢捧场。 请务必看我此篇的基础再去看第二篇。
0 受众群
读此文需要有一定的知识作为基础，比如有一定的算法知识，有C的基础 (能看懂就好)，能读懂ASM（看懂即可），懂什么是平方 、指数，什么是取余。懂原子弹爆炸模型--- 哦这个是可选的.哈哈. 当然也要有逻辑能力！
1开篇
本文不探讨RSA的公私钥体系，如何生成公钥私钥等。 如果需要了解这方面的内容可以访问百度百科https://baike.baidu.com/item/RSA%E7%AE%97%E6%B3%95/263310?fr=aladdin去学习。而本文只是通过一个实例分析探讨在实际软件应用中RSA是如何用公钥来进行加密的。
2 RSA加解密算法解析
讲解之前先对RSA的加密算法说明一下。RSA公钥是由 N和e组成，私钥是由N和d组成。加密过程是 “明文”做e次方运算然后对其运算结果取N的模，结果就是加密的数据。解密过程是对”密文”做d次方运算然后对齐结果取N的模，结果就是明文。如下图所示：
知道了算法，我们要去实现它就可以按照算法描述的一步一步的去做乘方(类似于方法power())然后取余数就可以了。但是实际软件的运算时不是这样的。因为数据量太大了。下面我举个例子来说明一下: 比如2是我要加密的数据”明文”。当它运行多次乘方后，它的结果是非常大的，数据量是几何级增长的。如下几个实例。
2^2=4,
2^10=1024,
2^30=1073741824,
2^67=147573952589676412928,
2^1024=????1024次方后结果会是300多位，这里我就不具体列出了。
可见指数越高产生的数据量也越大。当然实际运算的时候指数e或者d可不止几十，几百， 那可是成千上万啊。此外要加密数据也不会是2这么小的数，可以是非常大的。这样的话数据量是非常非常恐怖的 就是把你的当前所有的内存都用光了也可能都撑不下一次运算的结果。想想原子弹爆炸的图形。数据量就是这样增长起来的。
3算法优化
那怎么办呢，如何实现这个算法的呢？我们是幸运的，数学家们给我们提供了简便优化的方法来处理大数的指数运算。本文主要关注的也是这方面，优化后的算法是怎样的？计算机软件中是如何实现的？任何一个数的多次方取余都可以简化成这个数的平方取余然后余数再平方再取余一次类推每次平方后原指数除以2直到结果变成1，多次之后就能计算完成了。任何大数的平方（实际应用中相对的大数，你硬说一个大数占满16G的内存我也无话可说。呵呵）计算机就可以处理了（内存方面和CPU方面），这样就大大的简化了数据量和复杂度，并且效率还提高了计算次数小于或者等于原来硬算的次数的一半儿。
举个例子: 随便举例子
26的8次方然后取71的模等于45.
26^8%71=45这是硬算的结果，优化后算法变成如下，在一个循环里面运算，条件就是当剩余指数不为0循环:
第一次计算， 26*26%71=37，之后指数除以2，8/2=4. 剩余指数变成4.
第二次计算上一次的余数的平方然后取余， 37*37%71=20，剩余指数继续除以2, 4/2=2.
第三次继续执行平方取余, 结果就是20*20%71 =45, 剩余指数继续变为 2/2=1.
当每次运算前，先检测剩余指数除以2是否有余数(也就是余1时)，如果没有就是被2整除，那就是重复以上的算法，如果有余数时， 我们需要额外计算一次，当前平方取余后结果同原始数对71取余的结果（当e的值是奇数时，否则这个数就是1）相乘再取余。这里有点绕或者我能力有限不能完美的解释。哪位有更好的解释请告知我。没关系后面有C代码的实例，跑一下就明白了。
那么继续接上面第三次运算后，可以成为第四次也是最后一次，当前的剩余指数是1，除以2后余数为1. 也就是1%2=1.此时的运算变为：
45*1(初始值是1,之前没有改变过)%71=45.之后剩余指数1除以2去整数，则1/2=0.剩余指数为0，循环终止。则最终的运算结果就是最后计算后的45.跟我们之前硬算8次之后的结果相同。
以下是一个我自己实现的样例代码: 它能加密的最大数就是unsignedint的范围内.
unsignedlong intVerify_RSA_Encrypt(unsignedint Ori_data,unsigned inte, unsignedint N)
{
unsignedlong intremainder = 1;//结果余数初始值是1
while(e)
{
if(e % 2 == 1) //当e是奇数时运算，通常运算会发生在第一次和最后一次
remainder = (remainder * Ori_data)% N;
Ori_data= (Ori_data * Ori_data)% N; //正常的平方运算再取余
e/= 2;//剩余指数除以2
}
returnremainder;}
再一个例子： 之前例子中e是一个偶数的，这次运算一个e为奇数的。
如： 14^11%40=24这是硬算的结果. 以下我会引用上面C代码中变量来说明.
第一次， e%2==1, 则计算后remainder=1*14%40=14.继续 14*14%40=36. e/2=5.
第二次， e%2==1, 则计算后remainder=14*36%40=24继续 36*36%40=16, e/2=2.
第三次， e%2!=1, 跳过计算remainder，继续平方取余16*16%40=16, e/2=1.
第四次， e%2==1, 则计算后remainder=24*16%40=24,继续 16*16%40=16, e/2=0.
第五次， e的值为0退出循环.则返回remainder的值24. 而24就是优化算法后的运算结果。
在下一篇中我会列举一个真是大数RSA加密过程。期待中ing......
第二篇已经发出 RSA 算法的加密方法分析 之二 谢谢捧场。 JingZi 发表于 2020-12-16 15:55
老哥，对RSA数字签名有涉猎吗
没问题。早几年前就研究过。我记得大致原理应该是这样的，发布者用他的私钥使用RSA加密算法对一段数据进行加密。这就是签名过程。 验证方用发布者的公钥使用RSA算法对这段数据进行解密，然后比对发布者的明文，如果相同说明这段数据是经过发布者签名的，是有效的。大致就是这样吧 应该还有一些细节我不记得了。 Hmily 发表于 2020-12-8 15:13
千万不要从word里直接复制粘贴到论坛，如果粘贴也最好切换到“纯文本”格式下粘贴，然后进行润色，贴图参看 ...
谢谢提醒。 我还真就是从word里面贴过了的。好看了一下这个链接里面的教学。学到了。 发下一篇的时候我会按这个操作！ 感谢！ 请问谁知道多插入的图片怎么删除掉？ 吓我一跳，我还以为是你整出了RSA解密算法。 本帖最后由 tfrist 于 2020-12-16 01:38 编辑
wql15813 发表于 2020-12-8 12:55
吓我一跳，我还以为是你整出了RSA解密算法。
破解RSA算法肯定没有。 不过不久的将来通过量子计算机暴力破解RSA是秒秒钟的事情！ 加密呀，我记着哈希算法。 玟篠 发表于 2020-12-8 13:11
加密呀，我记着哈希算法。
那你写一篇hash的啊！大家多交流啊！ 感谢！！！很有启发~~~~~~~谢谢楼主 千万不要从word里直接复制粘贴到论坛，如果粘贴也最好切换到“纯文本”格式下粘贴，然后进行润色，贴图参看这个https://www.52pojie.cn/misc.php?mod=faq&action=faq&id=29&messageid=36 RSA算法的软件现在很多，先替换一下，在对应解密文件，
谢谢楼主分享！！！！