RSA加密算法

加密算法

谈到加密算法，我们不得不谈一下密码学中加密算法的两个分支：对称加密和非对称加密。

对称加密算法（以单表替代密码为例）

我们假设Felix要向你们之间的某位读者发送一段信息 $m$ ，为方便起见，我们假设这段信息是"THANKYOUFORFOLLOWINGME"。现在，为了使这段信息不被外人所知，需要对其加密。我们假设加密方式为：所有用后一位字母替代，那么上述的这段信息就被加密为：“UIBOLZPVGPSGPMMPXJOHNF”，这是不可读的。当读者接收到这段信息时，只需要将加密后的信息往前倒退一位，便可以得到原始信息。我们把原始信息称为明文，加密后的信息称为密文，加密方式（在上例中体现为字母的替代）称为加密算法，解密方式（在上例中体现为字母的替代）称为解密算法，加密时移动的位数1称为加密密钥，解密时移动的位数1称为解密密钥。

上面这种加密方式一般被称为单表替代密码，上述的例子又是其中十分特殊的一种，称为凯撒密码。我们观察可以知道，加密密钥和解密密钥是相同的，我们把具有这种性质的加密算法称为对称加密算法。

对称加密算法是有好处的：其计算量小，加密简单，用于加密和解密的密钥相同，算法只需要选取可逆映射即可。但对称加密也存在一些问题：双方在通信前需要互相商定密钥，并且在通信过程中，任何一方的密钥泄露都将使得所有通信被破解；其次，任何两者之间的通信都需要选取不同的密钥，这在通信网复杂的情况下，每个通信节点都需要储存数量庞大的密钥，给用户带来负担。

当然，密钥泄露的问题不是不可解决的。我们可以在每一次通信都使用不同的密钥，这样，密文在理论上是牢不可破的。但是这又会带来问题，我们如何获得这么庞大数量的密钥呢？我们又如何储存呢？密钥的分发在这种情况下变成了棘手的问题。所以，一次一密的加密方式在实际应用中是不广泛的。

非对称加密

随即而来进入我们脑海的一种加密方式就是非对称加密，即加密密钥和解密密钥不相同的加密方式。我们一般称前者为公钥，后者为私钥，因为前者是公开给所有人的，后者是密文接收方自己保存的。我们知道，由于加密和解密是逆运算，我们是有可能通过暴力破解求出加密方式的逆运算的。所以，为了保证安全性，非对称加密的算法一般都十分复杂，运算量相比于对称加密算法繁琐得多，因此，非对称加密牺牲了加密效率，换来了更高的安全性。下面我们来讨论一下非对称加密中的典型加密方式，即RSA加密。

RSA加密算法

基于的数学运算原理——模运算

首先我们来思考一个问题，有什么方式使得攻击者知道加密方式的情况下很难求算出其逆运算？有一种运算符合类似的性质：其正向运算十分简单，但逆运算极其复杂，它是模运算（Mod）。模运算就是我们一般说的求余。其正向运算是很简单的，例如

3^3\ \textrm{mod}\ 7=6,

完成这个运算只需要一个简单的除法即可，但是设想，如果给出的形式是方程，即

3^x\ \textrm{mod}\ 7=6,

求解满足上述方程的x的值，其运算是比较复杂的，因为我们不知道其商的值，也就不能快速利用乘法求算 $x$ ，一般我们会使用枚举法求算其解。但是如果方程是

3^x\ \textrm{mod}\ 7156464845153468615315646=6,

这时候，枚举法也变得十分困难了，这个方程已经是计算上不可解的了。因此，模运算也被称为单向运算。RSA就是利用了模运算的这点性质。

加密算法和解密算法确定

知道了我们要使用模运算作为加密和解密算法，那么我们不妨假设明文信息是 $m$ （message），密文信息是 $c$ （cipher），公钥为 $e$ ，私钥为 $d$ ，于是我们可以得到

\begin{cases} m^e\ \textrm{mod}\ N=c,\\ c^d\ \textrm{mod}\ N=m. \end{cases}

消去密文 $c$ ，上式可化为

(m^e\ \textrm{mod}\ N)^d\ \textrm{mod}\ N=m,

可以证明上式等价于

m^{ed}\ \textrm{mod}\ N=m.

这个结论先放在这里，我们后续会使用到它。

欧拉函数和欧拉定理

为了充分理解RSA密码的数学原理，我们需要先提到欧拉函数和欧拉定理。

欧拉函数

首先介绍一下欧拉函数：假设给定一个正整数 $n$ ，欧拉函数 $\varphi(n)$ 的值是不超过 $n$ 的与其互质的正整数的数目，例如不超过6的与6互质的正整数有1和5，那么我们就说， $\varphi(6)=2$ 。一般求解欧拉函数的值时，我们经常采用素因数分解的方式，让我们来看一个例子：求解 $\varphi(100)$ 的值。我们对其质因数分解，得到

100=2^2\cdot 5^2。

那么其与其互质的整数数量为

\varphi(100)=100\times(1-\dfrac{1}{2})\times(1-\dfrac{1}{5})=40.

对于任意正整数 $x$ ，假设其各个质因数为 $p_i$ ，那么其欧拉函数的值为

\varphi(x)=x\prod^n_{i=1}(1-\dfrac{1}{p_i}).

显然，这样计算一个正整数的欧拉函数是很复杂的。但如果上式中的 $x$ 是质数呢？问题就变得非常简单，因为这时 $P_i=\{x\}$ 。于是我们可以知道，质数 $p$ 的欧拉函数为

\varphi(p)=p-1.

同样的，如果对于两个互质的正整数 $p,q$ ，其乘积的欧拉函数就等于欧拉函数的乘积，即

\varphi(p\times q)=\varphi(p)\times \varphi(q).

这为我们求解欧拉函数提供了一个很好的解决方式。

欧拉定理

欧拉定理是数论中的重要定理，我们这里只做介绍，不作证明。欧拉定理说的是，对于互质的两正整数 $m$ 和 $n$ ，满足以下关系恒成立：

m^{\varphi(n)}\equiv1\ (\textrm{mod}\ n),

我们对上式两边同时取 $k$ 次幂，得到

m^{k\varphi(n)}\equiv1\ (\textrm{mod}\ n),

两边同时乘上 $m$ ，有

m^{k\varphi(n)+1}\equiv m\ (\textrm{mod}\ n),

改写得到

m^{k\varphi(n)+1}\ \textrm{mod}\ n= m.

这是我们需要的欧拉定理的形式。

密钥的生成

读者是否还记得我们在确定算法的时候找到了公钥和私钥的关系式？即

m^{ed}\ \textrm{mod}\ N=m.

与我们得到的欧拉定理的形式

m^{k\varphi(n)+1}\ \textrm{mod}\ n=m.

相比，我们发现，这时我们只需要使得

ed=k\varphi(N)+1，

即对于任何一个公钥 $e$ ，我们私钥 $d$ 的生成方式为计算 $d$ 使得

ed\ \textrm{mod}\ \varphi(N)=1.

这时我们可以利用到一条数学定理：如果两正整数互质（这里表现为 $d$ 与 $\varphi(N)$ 互质），那么一定存在 $d$ 满足上述关系，即 $ed-1$ 被 $\varphi(N)$ 整除，我们称这样的 $d$ 为模反元素。

所以，我们只要保证公钥 $e$ 和求得的 $\varphi(N)$ 互质，那么私钥 $d$ 的存在性是不言而喻的。那么现在问题的关键就是：如何确定 $\varphi(N)$ 和 $e$ 的值。

我们任意选取足够大的两个质数 $p$ 和 $q$ ，这是我们产生 $\varphi(N)$ 的来源。我们令 $N=p\cdot q$ ，这样的 $N$ 通常是非常大的，理论上计算 $\varphi(N)$ 需要对其进行质因数分解，然而对不知道 $p$ 和 $q$ 的人来说，这几乎是不可能的事情，因为 $N$ 的质因数分解被证明是计算上不可行的了。但作为密钥的分发方，我们却很容易解出，因为我们选取的是两个质数，利用欧拉函数的性质，我们很容易知道

\varphi(N)=\varphi(p\cdot q)=\varphi(p)\cdot\varphi(q)=(p-1)(q-1).

有了这个解，我们只需要任意取一个和 $\varphi(N)$ 互质的数就行了。由此，我们将 $(e,N)$ 作为公钥发送出去，待我们计算出 $d$ 后，保留 $(d,N)$ 作为私钥即可。销毁 $p$ 和 $q$ ，这样这组公钥私钥几乎是无法被破解的了。

加密流程总结

至此，我们已经知道了加密基于的数学原理和方法，这里我们来一些总结。

步骤	内容	生成
1	选取两个不相等的足够大的质数	$p$ 和 $q$
2	计算它们的乘积 $N=p\times q$	$N$
3	利用 $N$ 的因数计算其欧拉函数 $\varphi(N)=(p-1)\times(q-1)$	$\varphi(N)$
4	选取任一与 $\varphi(N)$ 互质的整数 $e$	公钥成员 $e$
5	计算模反元素 $d$ ： $ed\ \textrm{mod}\ \varphi(N)=1$	私钥成员 $d$
6	公布公钥 $(e,N)$	公钥 $(e,N)$
7	保存私钥 $(d,N)$	私钥 $(d,N)$
8	销毁 $p$ 和 $q$	无

这就是RSA加密算法的原理和流程。

关于关键的 $p$ 和 $q$

我们知道，如果两个数很接近，那么它们的差值一定很小。如果我们选取的 $p$ 和 $q$ 相差不大，那么RSA在这种情况下是很容易被攻破的。我们可以假设 $p>q$ 并且

p=a+b,\quad q=a-b,

那么大数 $N$ 就可以被表示为

N=p\times q=(a+b)(a-b)=a^2-b^2.

由于 $b$ 很小，所以 $a$ 和 $\sqrt{N}$ 的值非常接近，于是我们可以轻易倒推出用于产生密钥的 $p$ 和 $q$ 的值。这种情况下，RSA的安全性很低。但好在幸运的是，应用中不会产生这样的错误，所以RSA依然是很可靠的加密方式。

后记

从对于RSA彻底的分析来看，密码学在本质上是数学的实际应用。笔者在理解RSA密码加密的学习过程中，其实更多的时候都在了解其基于的数学原理，而并非大多数人所认为的加密过程。站在一个高度看RSA密码，其实其可靠性是由于人类对质因数分解掌握的不完全所保证的，因为知道公钥 $(e,N)$ ，从理论上是可以破解私钥的，只是实际不可行罢了。当然，我们也不能因此质疑RSA密码的可靠性，因为密码学对密码是否可用的标准一直只有两条：破解密码耗费的资源大于信息本身，或者破解密码需要的时间远大于信息的时效性，而并没有将牢不可破作为其中的标准。