RSA算法加解密过程全解析

$$若a,m均为正整数,且gcd(a,m)=1,则a^{\phi (m)}\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d}m)$$

$gcd(a,m)$表示求数a和m的最大公因数，如果最大公因数为1，这两个数互质。

其中$\phi (m)$是一个重要的数论函数：欧拉函数。$\phi (m)$表示小于等于m的正整数中与m互质的数的数目。显然，若m为素数，则$\phi (m)=m-1$。

如果A和B满足$A\mathrm{m}\mathrm{o}\mathrm{d}n=B\mathrm{m}\mathrm{o}\mathrm{d}n$，我们称之为A与B有同余关系，同余关系常常又表示成：$A\equiv B(\mathrm{m}\mathrm{o}\mathrm{d}n)$。同余关系是一种等价关系。

模的含义可以换算为普通乘式：
$$A\mathrm{m}\mathrm{o}\mathrm{d}B=C\to A=kB+C$$
基本的模加法和模乘法、模幂运算规则如下：
$$\begin{gathered} (A+B)\mathrm{m}\mathrm{o}\mathrm{d}C=(A\mathrm{m}\mathrm{o}\mathrm{d}C+B\mathrm{m}\mathrm{o}\mathrm{d}C)\mathrm{m}\mathrm{o}\mathrm{d}C \\ (A\ast B)\mathrm{m}\mathrm{o}\mathrm{d}C=((A\mathrm{m}\mathrm{o}\mathrm{d}C)\ast (B\mathrm{m}\mathrm{o}\mathrm{d}C))\mathrm{m}\mathrm{o}\mathrm{d}C \\ (A^B)\mathrm{m}\mathrm{o}\mathrm{d}C=(A\mathrm{m}\mathrm{o}\mathrm{d}C{)}^B\mathrm{m}\mathrm{o}\mathrm{d}C \end{gathered}$$

了解了模幂的规则，其实我们很快就能发现函数$f(a,x)=a^x\mathrm{m}\mathrm{o}\mathrm{d}m$很有趣，因为存在$f(f(a,e),d)=f(a,ed)$，即$(a^e\mathrm{m}\mathrm{o}\mathrm{d}m{)}^d\mathrm{m}\mathrm{o}\mathrm{d}m=a^{ed}\mathrm{m}\mathrm{o}\mathrm{d}m$成立，而$a^{ed}\mathrm{m}\mathrm{o}\mathrm{d}m$与$a^{\phi (m)}\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d}m)$之间的相似度又不禁令我们遐想联翩。实际上，欧拉定理再变通一下，我们就能得

到$a^{\phi (m)+1}\mathrm{m}\mathrm{o}\mathrm{d}m=a$，**其中$a<m$。**那么，要是$ed=\phi (m)+1$的话，不就有$a^{ed}\mathrm{m}\mathrm{o}\mathrm{d}m=a^{\phi (m)+1}\mathrm{m}\mathrm{o}\mathrm{d}m=a$了吗？！那么，我们现在这样来描述我们的加解密函数$f_1$和$f_2$，令$f_1=f_2=a^x\mathrm{m}\mathrm{o}\mathrm{d}m$，其中a为明文，选择一个$m$，计算$\phi (m)$，公钥和私钥的策略是，然后选择一个$e$并根据$ed=\phi (m)+1$计算$d$。

经过上面的简单思考，我们来解决一些随之而来的问题。

首先，我们为了得到$a^{\phi (m)+1}\mathrm{m}\mathrm{o}\mathrm{d}m=a$，实际上弱化了欧拉定理，要求底数$a<m$。不过这并不是什么大问题，底数a代表的明文如果实在太长，我们把它分割一下，让它小于m就行了。

其次，欧拉定理还要求底数a和模m互质（$gcd(a,m)=1$），这是一个比较严苛的要求。幸运的是，即使明文a与m不互质，我们也可以证明我们的加密、解密函数仍然有效，稍后将给出证明。

另外，在实现上仍有诸多疑问：一个数的幂的结果增长得特别快，计算$a^{ed}$是否很容易超出编程语言中整型变量的范围呢？如何根据$n$确定$\phi (n)$？

我们先来解决计算$a^{ed}\mathrm{m}\mathrm{o}\mathrm{d}n$的问题。

例如，要求计算$2^{256}\mathrm{m}\mathrm{o}\mathrm{d}7$。显然，先计算出$2^{256}$不是什么明智的选择。根据模算术的基本规则，我们可以得到：
2 256 m o d    7 = ( 2 128 m o d    7 ∗ 2 128 m o d    7 ) m o d    7 2^{256}\mod 7=(2^{128}\mod 7*2^{128}\mod7)\mod7 2256mod7=(2