这段时间在Xman学习，前几天讲了密码学就想复习一下RSA，然后发现之前理解的全忘了。找了好久才找到篇好的讲解，趁还没忘赶紧记一下
RSA
RSA是一种非对称加密算法，说到非对称加密首先就要说一下对称加密。简单的像异或，到有些复杂的AES,DES这些都是对称加密算法。加密方与解密方都拥有同样的密钥，通过这个密钥进行加密解密
对称加密有着一个巨大的缺点，就是如何将密钥安全地递交给解密方。为了解决这个问题，非对称加密算法便应运而生了
最早的出现的非对称加密算法是Diffie-Hellman密钥交换算法，通过某种数学关系生成公钥与私钥。加密方使用公钥加密，解密方使用私钥解密
在进行数据传输时，解密方会先将公钥传给加密方，加密方用公钥加密密文，再将数据传给解密方，如何解密方再利用私钥解密，就能够获得加密方发送过来的信息
同时由于私钥是极难以通过公钥推导得到的，即使在传输过程中公钥泄露了，也依旧能够保证密文的安全性
RSA算法便是基于这样想法，而在这里要讨论的就是究竟是通过什么样的数学关系获得公钥和私钥，为什么不同的密钥却可以解出原来的信息
为了讨论这个，先要知道一点数论知识
互质关系
互质关系很简单，真正的小学生都知道的关系。两个数之间除了1以外没有其他公因数，则这两个数互质
通过互质的定义，我们可以推出以下几个关系
- 任意两个质数互质
这个很好理解，毕竟质数除自身外只有1个因数，因此两个质数间也就只有1这个公因数 - 一个数是质数，另一个数只要不是前者的倍数，两者就构成互质关系
这个另一个数为质数时，同1理。为合数时既然不为质数的倍数，那自然也就只有1为公因数 - 如果两个数之中，较大的那个数是质数，则两者构成互质关系
既然较大的是质数，就说明较小的那个数的倍数不会是质数，那依旧只会有1为公因数 - 1和任意一个自然数是都是互质关系
定义易证 - p是大于1的整数，则p和p-1构成互质关系
在p和p-1中，必定分别数奇数与偶数。而假设k为奇数，k=pq，p与q都必定是奇数。当p>1，q>1时，k-p≤k-3<k-1<k<k+1<k+3≤k+p，k-1和k+1都不会是p的倍数，因此k-1与k+1中都不会与k有1之外的的公因数 - p是大于1的奇数，则p和p-2构成互质关系
同5理k-p≤k-3<k-2<k<k+2<k+3≤k+p，得证
欧拉函数
欧拉函数是用于计算对于任意一个自然数，比该自然数小且与该自然数互质的数的个数，记作φ(n)
欧拉函数有以下这几种情况
- n = 1
自然φ(n)=1 - n为质数
既然n为质数，那n自然与小于自身的所有自然数互质，因此φ(n)=n-1 - n = m^k(m为质数，k为自然数)
由于m为质数，因此不与n互质的数必定有因数m。由于n=m^k=m*m^(k-1),所以一共就有m^(k-1)个数不与n互质，因此φ(n)=m^k-m^(k-1)=m^k(1-1/m) - n = pq(p,q为互质数)
由于p，q互质，那么p与q就不会有除1之外相同的公因数。
剩下的不会证，没学数论真的理解不动orz - n=(p1^k1)(p2^k2)(p3^k3)…(pn^kn)(均为质数)
由于所有质数本身就是质数，而所有合数通过分解最终都会分解成质数的乘积，因此这个情况实际上是针对除了1以外所有正整数
由n=pq的情况，我们可以易得，φ(n)=φ(p1^k1)φ(p2^k2)φ(p3^k3)…φ(pn^kn)
然后再由n=m^k的情况，的得到φ(n)=(p1^k1)(p2^k2)(p3^k3)…(pn^kn)(1-1/p1)(1-1/p2)(1-1/p3)…(1-1/pn)=n(1-1/p1)(1-1/p2)(1-1/p3)…(1-1/p4)
欧拉定理
当正整数a与n互质时，有这么一个定理
a^φ(n) ≡ 1(mod n)
也就是a的φ(n)除n的余数为1
同时有着这么一个特殊情况，当n为质数时，则
a^φ(n-1) ≡ 1(mod n)
这也是所谓的费马小定理
模反元素
先上一个式子
ab ≡ 1(mod n)
一眼看下去，这个式子和上面的欧拉定理很像
只要稍加推导就能得到
ab = a^φ(n)b = a^(φ(n)-1)
而此处的这个b，就是a的模反元素
密钥的生成
写了这么多数论的东西，终于可以开始写RSA了
首先生成密钥需要两个不相等的质数p和q，由于都为质数，p和q互质
接着通过获得n=pq，再计算φ(n)。由于pq互质，且又为质数，因此φ(n)=φ(p)φ(q)=(p-1)(q-1)
然后选一个整数e(1<e<φ(n),且e与φ(n)互质)，继而通过计算获得e对于φ(n)的模反元素d
此时就获得了n,e,d，这里的(n,e)就会作为公钥，(n,d)作为私钥
RSA的可靠性
我们知道RSA通过将密钥分成公钥和私钥，攻击者就算截取了数据，也只能得到公钥无法解密。那么公钥是否能够推得私钥？
看密钥的生成过程，我们得知ed≡1(mod φ(n)),只有知道e和φ(n)，才有可能解得私钥d。而φ(n)=(p-1)(q-1)，n=pq。也就是说，只要能将n因式分解，就能够破解得到私钥
因此，RSA的可靠性取决于p和q的大小，越大越难以分解，到达一定长度就可以认为是无法破解的
加密与解密
知道公钥与私钥的来源，接下来就是加密与解密的方式
加密是使用公钥去进行加密，但要注意的是，m必须为整数同时还要小于n。因此通常情况下会将字符串用unicode编码后再进行加密
加密如下式
m^e ≡ c(mod n)
c就是加密后的密文
然后解密就是
c^d ≡ m(mod n)
通过这条式子就能够获得原文m
解密证明
单纯看上面的式子，要直接看得出加密过程是正确的还是比较难的，这里证明一下
先从加解密的式子开始
m^e ≡ c(mod n)c^d ≡ m(mod n)
处理一下加密式
c = m^e - kn
代入解密式
(m^e-kn)^d ≡ m(mod n)
由于(m^e-kn)^d进行展开后，除了m^ed以外，其他的部分都是n的倍数，(mod n)直接为0，于是上式可以简化成
m^ed ≡ m(mod n)
从密钥的生成可知
ed ≡ 1(mod φ(n))
可得
ed = hφ(n)+1
再代入简化后的式子
m^(hφ(n)+1) ≡ m(mod n)
接下来就要进行分类讨论了
- 当m与n互质时
由于m与n互质，m^k与n互质
然后再由由欧拉定理得到
m^hφ(n) ≡ 1(mod n)
同乘m得
m^(hφ(n)+1) ≡ m(mod n)
原式得证
- 当m与n不互质
由于m，n不互质，且n为质数p与q的乘积，因此m必有p或q其中一个因子。因此设m=kp，由于m<n，因此k<p。而p又是质数，因此k与p互质，m与p也互质。因此(kp)^x与q互质，由此可得下式
[(kp)^h(q-1)]^(p-1) ≡ 1(mod q)
进而
(kp)^(h(q-1)(p-1)+1) ≡ kp(mod q)
由于ed = kφ(n)+1 = h(q-1)(p-1)+1，可得
(kp)^ed ≡ kp(mod q)
式子右边变换一下
(kp)^ed = tq+kp
左边可以看作nkp，即p的倍数，因此右边也是p的倍数。由于q≠p，因此t为p的倍数，于是设t=dp，则
(kp)^ed = dqp+kp
由于m=kp，n=pq，因此
m^ed ≡ dn+m
也就是
m^(hφ(n)+1) ≡ m(mod n)
证明完成