RSA非对称加密算法
今天让我来谈谈RSA非对称加密算法的具体实现和原理。其实绝大多数的博客上都谈了很多RSA算法的应用，主要是数字签名和SSL相关的。但其实很少有人深入原理去探讨阐述，最多就说明一下因为大质数分解很难所以可以认为RSA是安全的。花了一整天时间弄懂RSA后，我终于明白为什么很少有博客深入原理探讨了，因为这太特么烦了，需要的前置数学知识还挺多，大部分都是码农所不了解的。
RSA算法历史
以下内容来自维基。感觉麻省好贱，这么好的东西居然要藏着掖着。
RSA是1977年由罗纳德·李维斯特（Ron Rivest）、阿迪·萨莫尔（Adi Shamir）和伦纳德·阿德曼（Leonard Adleman）一起提出的。当时他们三人都在麻省理工学院工作。RSA就是他们三人姓氏开头字母拼在一起组成的。 1973年，在英国政府通讯总部工作的数学家克利福德·柯克斯（Clifford Cocks）在一个内部文件中提出了一个相同的算法，但他的发现被列入机密，一直到1997年才被发表。 对极大整数做因数分解的难度决定了RSA算法的可靠性。换言之，对一极大整数做因数分解愈困难，RSA算法愈可靠。假如有人找到一种快速因数分解的算法的话，那么用RSA加密的信息的可靠性就肯定会极度下降。但找到这样的算法的可能性是非常小的。今天只有短的RSA钥匙才可能被强力方式解破。到目前为止，世界上还没有任何可靠的攻击RSA算法的方式。只要其钥匙的长度足够长，用RSA加密的信息实际上是不能被解破的。 1983年麻省理工学院在美国为RSA算法申请了专利。这个专利2000年9月21日失效。由于该算法在申请专利前就已经被发表了，在世界上大多数其它地区这个专利权不被承认。
前置知识
totient function
这里引入一个totient function（怎么这么像厕所函数）\(\phi (n)\)
这又特么叫欧拉函数（所以欧拉函数在这个世界上到底有多少个啊？）。根据wolfram上的定义，它定义了与正整数\(n\)互质且\(\leq n\)的正整数个数。而显然1与所有的正整数互质。举个栗子来说\(\phi (24)=8\)，因为与24互质的有1、5、7、11、13、17、19、23
Congruence
另引入一个Congruence同余的概念，见wolfram
如果两个数字\(b\)和\(c\)有如下特性：\(b-c\)可以被\(m\)整除，那么就可以说\(b\)和\(c\)模\(m\)同余（\(b\) and \(c\) are said to be "congruent modulo \(m\)."），记为
\[b \equiv c(mod \ m)\]
关于Congruence，有一个性质接下来会使用到
\[a \equiv b(mod \ m) \ AND \ c \equiv d(mod \ m) \Rightarrow ac \equiv bd(mod \ m)\]
简单证明一下，根据Congruence的性质，可以有
\[a - k_1m = b - k_2m \\ c - k_3m = d - k_4m\]
其中\(k_1,k_2,k_3,k_4\)均为整数
则二者相乘得
\[(a - k_1m)(c- k_3m)=(b-k_2m)(d-k_4m) \\ ac - m(...)=bd-m(...)\]
得证。
Euler's theorem
在数论中，欧拉定理，也称费马-欧拉定理（又特么是欧拉），见wiki，描述如下：
若\(n\)和\(a\)为正整数，且\(n\)、\(a\)互素，则有
\[a^{\phi(n)} \equiv 1 (mod \ n)\]
它实际上是费马小定理的推广。
不过这个定理的证明看得我云里雾里。尝试理（chao）解（xie）一下：
首先，我们需要“所有与\(n\)互质的同余类构成一个乘法群”这个性质。哦在这停顿，解释一下同余类和群的概念。
同余类
如同任何同余关系，对于模\(n\)同余是一种等价关系，整数\(a\)的等价类是一个集合\(\{...,a-2n,a-n,a,a+n,a+2n,...\}\)，标记为\(\overline{a_n}\)。由对于模\(n\)同余的所有整数组成的这个集合称为同余类
群
群是一个集合\(G\)，连同一个运算"\(·\)"，它结合任何两个元素\(a\)和\(b\)而形成另一个元素，记为\(a·b\)，且满足如下性质：
- 封闭性:对于所有\(G\)中\(a\), \(b\)，运算\(a·b\)的结果也在\(G\)中
- 结合性:对于所有\(G\)中的\(a\), \(b\)和\(c\)，等式 \((a·b)·c = a· (b·c)\)成立
- 单位元:存在\(G\)中的一个元素\(e\)，使得对于所有\(G\)中的元素\(a\)，等式\(e·a = a·e = a\)成立
- 逆元: 对于每个\(G\)中的\(a\)，存在\(G\)中的一个元素\(b\)使得\(a·b = b·a = e\)，这里的\(e\)是单位元
也就是说，设\(\{ \overline{a_1}, \overline{a_2},...,\overline{a_{\phi(n)}} \}\)是比\(n\)小的正整数中所有与\(n\)互质的数对应的同余类组成的集合（这个集合也称为模\(n\)的简化剩余系）。这些同余类构成一个群，称为整数模\(n\)触发群。所以当对这些数进行变换\(\overline{a_i} \rightarrow \overline{a \cdot a_i} = \overline{a} \cdot \overline{a_i}\)时（\(a\)是和\(n\)互质的一个数，从而也属于某个同余类），变换所得的同余类集合仍然是原来的\(\overline{a_1}, \overline{a_2},...,\overline{a_{\phi(n)}}\)。即，集合\(\{ \overline{a_1}, \overline{a_2},...,\overline{a_{\phi(n)}} \}\)和\(\{ \overline{aa_1}, \overline{aa_2},...,\overline{aa_{\phi(n)}} \}\)相同。
因此，\(a^{\phi(n)}a_1a_2\cdots a_{\phi(n)} \equiv (aa_1)(aa_2) \cdots (aa_{\phi(n)}) \equiv a_1a_2 \cdots a_{\phi(n)} \ (mod \ n)\)
从而\(a^{\phi(n)} \equiv 1 \ (mod \ n)\)
（好吧我承认我毛都没看懂）
RSA算法步骤
Step 1
首先需要选择两个足够大的质数\(p\)和\(q\)，并将它们的乘积记为\(n\)
\[n \equiv pq \\ (e,\phi(n))=1\]
其中\((e,\phi(n))\)指最大公约数，因此\((e,\phi(n))=1\)指的是\(e\)和\(\phi(n)\)互质
然后定义私钥\(d\)和公钥\(e\)使得
\[d \ e \equiv 1(mod \ \phi(n))\]
根据totient function的性质，可以有
\[\phi(n)=(p-1)(q-1)\]
因此公钥即为\((e,n)\)，私钥即为\((d,n)\)
Step 2
设需要加密的信息为数字\(M\)，那么加密方使用公钥\(e\)和\(n\)进行加密
\[E=M^e(mod \ n)\]
解密使用私钥\(d\)解密，注意这里使用了欧拉定理
\[E^d \equiv (M^e)^d (mod \ n)\equiv M^{ed} (mod \ n)\equiv M^{N \phi(n)+1} (mod \ n) \\ \equiv [M \cdot {(M^{\phi(n)})}^N](mod \ n) \equiv [M \cdot 1(mod \ n)](mod \ n) \equiv M(mod \ n) \]
Step 3
可以注意到，如果需要破解得到消息，则可以通过得到\(d\)。最直接的方法就是对\(n\)进行因式分解。显然这很困难。不过，这里有一些比较坑爹的事实：
- 至今为止还没有人找到一个多项式时间的算法来分解一个大的整数的因子，同时也还没有人能够证明这种算法不存在
- 至今为止也没有人能够证明对\(n\)进行因数分解是唯一的从\(E\)导出\(M\)的方法，但今天还没有找到比它更简单的方法。（至少没有公开的方法。）
也就是说，虽然RSA真的很屌，但它还是没有被证明确实是unfuckable的。这不禁让我想起一个又一个被日穿的摘要算法。。。
Step 4
实际上在真正的RSA算法实现中，因为码农和数学家之间的巨大鸿沟（欧拉大爷们求你不要再吊打我的智商了），有特别多的坑。关于这一点，已经有人在吐槽这帮傻比码农了，见知乎专栏。
除开知乎专栏外，wolfram也提到了一些需要注意的地方：
\(p\)和\(q\)的挑选必须小心，保证\(p \pm 1\)和\(q \pm 1\)能被大质数整除，否则容易被Pollard p-1 factorization method和Williams p+1 factorization method因式分解出\(n\)导致被日。同时\(\phi(\phi(pq))\)也必须够大且能够被大质数整除（wolfram没说为啥）
wolfram上还提到了需要注意的地方，然而我并没有看懂（所以就不贴了），涉及到群环域的知识。
总结
扒完RSA后，我的感想就是：大规模应用一个理论上尚未证明完备的东西，而且在应用上也花式掉链子，人类真是一种贼胆大的生物。