RSA加解密(非对称加密)

前置知识：

因数与模除

对于a x b = c(a，b为质数)，已知a和b求c非常容易，但是已知c求a和b却只能用试除法，所以当数c非常庞大的时候，a和b的值将会因耗时太长而不可求

也就是说上述的过程乘法容易，倒推却非常难，同样的顺易逆难也展现在模除中：

a mod b = c，在a足够大时，已知 c 和 b ，得到a的希望十分渺茫

二者相结合，就是RSA加密难以被破解的精髓

欧拉函数 α(n) ：

小于或等于n的正整数中与n互质的数的数目

易知，如果n为质数，则 α(n)=n−1

那么，对于质数a，b，若a x b = c， 则 α(c)=α(a)×α(b)=(a−1)×(b−1)

RSA加密过程：

1.发送方->公钥数字G与N，接收方->私钥S与N

加密：

2.发送方按照一定格式将明文变为十进制数字num

3.通过计算得到密文 M=num^G%N

解密：

4.接收方拿到M，计算 M^S%N 得到明文num

eg：

公钥(7,55) 密钥(23,55) 明文： 9 4 6

加密：

9^7 % 55 = 4

4^7%55=49

6^7%55=41

得到密文： 4 49 41

解密：

4^23 % 55 = 9

49^23 % 55 = 4

41^23 % 55 = 6

得到明文：9 4 6

看到这里或许你会发问了，前置中的欧拉函数和因数的知识好像都没有用到诶，不过我既然写出来了，就一定会用到，除非公钥G和私钥S的数字是凭空出现的，刚好让num^G^S % n = num

公钥密钥制作：

1.选取两个质数p和q，得到n = p x q

2.通过欧拉函数得到 t=α(n)=(p−1)×(q−1)

3.任意选取一个 大于0小于t 且 不能整除t的数G作为公钥

4.通过公式 (G×S)%t=1 得到私钥

分析：

在整个加解密过程中，对于第三方已知的只有公钥（S，N）以及密文M，如果不是歪打正着，就不可能完成明文=密文^? % N的解密

破解：

万法均为暴力破解，除非偷得到密钥........

如果有神仙突破天花板了当我没说

Notice:

已知p，q，公钥or私钥x 求 私钥or公钥y：

y = ((p-1)*(q-1) + 1) / x

拿原理就容易得到，欧拉函数加一再除以已知密钥