RSA加密

这几天在重点研究ZIOS的加密部分，之所以这次重点要做加密，主要原因是之前的mini-HID甚至jubeat的P4IO都被抄过了。不过先前的就算了，当初也没想着要防。

花了一些时间研究了RSA加密的数学逻辑和程序算法，发现挺有趣又不难理解，做一些总结和分享。

RSA加密有两把"钥匙"，一个是“公钥”，一个是“私钥”。

有趣的点是，用公钥锁上之后，是用私钥打开。所以打开的那把钥匙是不会暴露给别人的，自然就更难被他人破解和复制。

从某种意义上来讲，就是一种乱序密码表。例如这个密码的范围是1、2、3、4、5，用1来表示3，用2来表示5等等……总共5种不重复的组合。由于不知道密钥，就等同于不知道密码表，那么假设看到的密文是1，也没办法确定实际要表达的意思是12345种的哪一个了。

如果这个时候做一个超~超~超~超~超~大型密码表，数据长度可能绕地球5圈都绕不完的那种，那么从密文破解到明文的难度就非常大了。

可是那么大的密码表要怎么实现……毕竟电脑可能都存不下来那么庞大的数据量。这里就是RSA加密最精髓的地方了。

RSA加密用的是余数的方式，因为余数的范围是确定的，就像7的余数一定是0-6，这样就确定了整个表的大小，也确定了明文的范围一定要在余数的范围内。

然后用了两个算法，确定余数之间的唯一对应关系，就实现了超大型密码表。

具体的数学算法：

先随便选2个质数，假设是7和11。

先得出两个数相乘的数N = 7 x 11 = 77

然后将两个质数各-1，得出最小公倍数M。6和10的最小公倍数是30。

然后再取一个和M互质的数E，并且不能为1，也不能大于M，这里E有多个解，我们假设取13好了。

下一步就要确定一个数D，这里要求D不能为1也不能大于M，而且E x D 的结果除以M的余数为1.

这里如果用穷举，可以试一下M有余1的数有哪些：

31，61，91........咦！91÷13=7，是个整数。所以这里D=7。

所以这里可以获得最终结果：

公钥E,N：E=13,N=77

私钥D,N：D=7,N=77

接下来进行加密：

密文 = ( 明文的E次方 ) 求N的余

根据之前的分析，明文是不能大于N的，这里随便假设我们想要传递的明文是 20

那么密文就是  (20^13)mod77 = 69

然后获取到加密的数据是69，这时候要解密成正确的明文：

明文 = ( 密文的D次方 ) 求N的余

试算一下：(69^7)mod77 = 20

这样就完成了密码表上的对应。

但这里存在一个问题，如果密码表超级大，求次方的时候电脑算的过来么？

确实是算不过来，但这里因为目的是求余，所以有个很有趣的特性：

假设14÷13余1，那么(2x14)÷13就余2，(3x14)÷13就余3....

所以14的平方÷13的余，就是1x14再求余，所以答案是1。

就可以总结出 n的平方求m的余 =  （（n先求m的余）乘 n）再求m的余

利用这点，就可以让电脑不用存那么大的次方数再求余了。

所以RSA算法实现起来并不复杂诶