最近参与的项目偶尔接触到了RSA加密相关的东西，由于之前不了解是怎么回事，这次特意学习了一下。
在网上找了很多资料，但是大部分都比较晦涩难懂，说得很抽象。在综合了几篇文章后加入了自己的理解总结如下：
首先加密的方式分为两种：即对称加密与非对称加密。对称加密的话加密与解密的方式相同，而非对称加密的情况下加密与解密的方式不同。对称加密存在的安全问题在于一旦加密与解密一方遭到破解，则会立刻泄密，然而非对称加密则不存在这个问题。而在非对称加密算法种当前应用最广泛的应该就是RSA了。RSA加密中有一套公钥和一套私钥，公钥用于加密而私钥用于解密。公钥大家都可以看到，但是私钥只有自己知道。而RSA的难破解之处在于一种数学特性，即让两个大质数相乘求解很容易，而通过积来反推是哪两个质数相乘得到的却很困难。
在说明RSA加密原理之前还有两个预备知识：
1.同余定理
如果a除以n余数为b，那么可以称为a在模为n的情况下同余b，即：
a ≡ b (mod n)
如果另外一个数c除以n也余b的话也可以写成
c ≡ b (mod n)
那么a和c在同余运算中可以看做为同一个类别，即
a ≡ c
通过同余的特性我们还可以继续推导出几个公式（模相同的情况下）：
1.如果a ≡ b, b ≡ c，则a ≡ c
2.如果a ≡ b, c ≡ d, 则a + c ≡ b + d
3.如果a ≡ b, c ≡ d，则ac ≡ bd
4.如果a ≡ b，c为一个正整数，则a ^ c ≡ b ^ c
2.欧拉定理
对于任意一个正整数a，必有
a ^ φ(n) ≡ 1 (mod n)
其中φ(n)是欧拉方程，返回的结果是小于n的所有与n互质的数的个数
有了这两个预备知识就可以往下说明了
假设p与q都为质数（实际运用中可能会达到1000位到2000位）
设p * q = N
那么在N为两个质数的乘积的情况下，φ(N)可以写为：
φ(N) = (p - 1) * (q - 1)
假设φ(N) = k
这时候寻找一个自然数e：
使得 1 < e < φ(N) 并且 e与φ(N)互质
再寻找一个自然数d：
使得 d * e ≡ 1 (mod k)
那么就可以写成：
d * e = k * t + 1
最终推导出这个公式，也正是RSA的精髓：
d * e = t * φ(N) + 1
其中d(decrypt)就是我们的私钥，而e(encrypt)就是我们的私钥
=>公钥: (e, N)
=>私钥: (d, N)
假设明文为m，密文为M，mod一直为N，则必有：
m ^ e ≡ M
M ^ d ≡ m
也就是明文的e次方除以N的余数为密文，而密文的d次方除以N的余数必为之前的明文
以下为证明：
m ^ ed ≡ m ^ (1 + t * φ(N)) ≡ m * ((m ^ t) ^ φ(N))
由欧拉定理可知：
(m ^ t) ^ φ(N) ≡ 1
m ^ t可以看做欧拉定理中的a，这样一来就可以根据同余的性质推导出：
m ^ ed ≡ m
(m ^ e) ^ d ≡ M ^ d ≡ m
举个例子的话：
取p = 31, q = 37
那么N = 31 * 37 = 1174
⌽(N) = (31 - 1) * (37 - 1) = 1080
这个时候随便取e = 13，那么再取个d = 997
比如说明文m = 521
那么经过计算
m ^ e % N = M = 955
M ^ d % N = 521
其实这么一看秘钥d并不是唯一的，实际上只要是d + n(p - 1)(q - 1)，n为任意自然数的话都可以作为秘钥来解码，但是问题在于破解RSA的前提是必须要知道p和q是多少，因此现阶段来看RSA可以说还是很安全的
