从欧拉函数、欧拉定理到RSA加解密

古希腊哲学家苏格拉底曾言：“我唯一知道的就是我一无所知。”；
中国儒家学派创始人孔子曰：“知之为知之，不知为不知，是知也。”；
德国著名数学家希尔伯特则满怀信心地说道：“我们必须知道，我们必将知道。”
。我觉得希尔伯特和苏格拉底、孔子的说法并不矛盾，因为只有当你知道自己不知道时，才会去探寻，才会说"我们必须知道，我们必将知道"。

欧拉在发现欧拉函数、欧拉定理时，肯定不知道他发现的这些东西会成为当代计算机密码学中非对称秘钥RSA的基石。英国著名数学家哈代（华罗庚的导师）也不知道，甚至他认为这些定理大都是无用的。他甚至在《一个数学家的辩白》中自豪地宣称:

“真正"的数学家所研究的"真正"的数学，如费马、欧拉、高斯和阿贝尔所研究的数学，几乎是完全"无用"的。…
我从未做过任何一件"有用的事”。我的新发现未曾，且将来也不大可能为世界增加哪怕是最限度的舒适感，不论是直接的还是间接的，也不管是善意的还足恶意的，都做不到这一点。我也曾培训过其他数学家，但这些人与我是同样类型的数学家，他们所做的工作也同我做的工作一样没有用处。若是以实用的标准来作评判的话，我的数学生命的价值是零;从数学之外看来，我的价值无论如何也是微不足道的。我只有一种机会免被判断为完全微不足道，那就是人们可能判定我已做出了一些有创造价值的工作。
我不否认，我已做了一些创造性的工作，问题是它们的价值怎样。

显然哈代错了。欧拉函数、欧拉定理已成为当代计算机密码学中非对称秘钥RSA的基石。我们现在浏览网页、购物等等的安全性大都依赖非对称密码方案。而
RSA密码方案(有时也称为Rivest-Shamir-Adleman算法)是目前使用最广泛的一种非对称密码方案，当然椭圆曲线和离散对数方案也逐渐普及。

RSA算法是 Ronald Rivest, Adi Shamir 和Leonard Adleman 在1977
年提出的。RSA应用非常广泛，在实际中常用于：

1. 加密小片段的数据，比如用于密钥传输.

2. 数字签名，比如数字证书。

需要注意的是，RSA比对称加密(例如AES)要慢很多。这主要是因为RSA执行中涉及到大量计算。因此，RSA并不是为了取代对称密码。RSA的一个主要用途就是安全地交换对称密码的密钥（即密钥传输)。实际上，RSA通常与类似AES的对称密码一起使用，其中真正用来加密大量数据的是对称密码。

RSA的安全性主要是建立在整数因式分解问题上：两个大素数相乘在计算上是非常简单的(人们使用笔和纸就能完成)，但是对其乘积结果进行因式分解却是非常困难的。欧拉函数和欧拉定理在RSA中发挥着至关重要的作用。下面我们将先将讲述欧拉函数、欧拉定理，最后再介绍RSA。

欧拉函数

欧拉函数考虑的是互素个数问题。

欧拉函数：当 m 为大于1的整数时，用$\phi (m)$ 表示$1,2,\dots ,m$
中与m 互素的正整数个数，则
$$\phi (m)=m(1-\frac{1}{p_1})(1-\frac{1}{p_2})\dots (1-\frac{1}{p_k})(1)$$
其中 $p_1,p_2,\dots ,p_k$ 为 m 的所有互异的素因数。

重新看这个问题的时候，我想到了一个更简单的证明方法。欧拉函数(1)
式可以化为
$$\phi (m)=\frac{m}{p_1{p}_2\dots p_k}(p_1-1)(p_2-1)\dots (p_k-1).(2)$$
这个式子可以理解为有 $\frac{m}{p_1{p}_2\dots p_k}$ 个区间，区间的大小为
$p_1{p}_2\dots p_k$ 。只要证明每个区间都有 $(p_1-1)(p_2-2)\dots (p_k-1)$
个数和 m 互素即可。

引理1 如果 $m=p_1{p}_2\dots p_k$ ，则
$$\phi (m)=(p_1-1)(p_2-1)\dots (p_k-1).(3)$$

不妨设 $p_1<p_2<\cdots <p_k$ ，当k=1时显然成立， 因为当 p
为素数时$\phi (p)=p-1$。

当 k=2 时，$\phi (p_1{p}_2)$ 可以这样计算，我们从 $\phi (p_1)$
个数中任意取一个数，不妨记为 a ，$(a,p_1)=1$ ，然后通过 a
生成下面这些数
$$a+0p_1,a+p_1,a+2p_1,\dots ,a+(p_2-1)p_1(4)$$
由于
$(p_1,p_2)=1$ ，根据"互素时剩余类的性质"，可知
$0,p_1,2p_{}$