RSA加密算法原理（二）

在RSA加密算法原理（一）一文中我科普了一些简单的数论基础知识，接下来可以细说RSA的数学原理啦~

先以一个例子简单讲一下RSA算法的流程，假设A要向B发消息，那么B会按以下流程生成一对密钥：

生成一对密钥（公私钥）

选择两个不相等的素数 $p$ 和 $q$，例如 $p=31,q=37$
计算 $n=p\times q=31\times37=1147$
计算 $\phi(n)$，这里有一个比较直观的看法：由于 $n$ 是两个素数 $p,q$ 的乘积，那么小于 $n$ 的正整数中，与 $n$ 不互素的应该有

$\begin{aligned}&kq,k= 1,2,...,p-1\\&kp,k= 1,2,...,q-1\end{aligned}$

且$p、q$均为素数可以保证这些数两两不同，因此

$\begin{aligned}\phi(n)&=n-1-(p-1)-(q-1)\\&=n-p-q+1\\&=(p-1)(q-1)\\&=30\times36=1080\end{aligned}$

在 $(1, \phi(n))$ 之间随机选择一个正整数 $e$，使得 $e ⊥ \phi(n)$，这里我们随便选一个 $e=67$
接下来，我们要找 $e$ 在 $\mathbb{Z}_{\phi(n)}$ 群中的乘法逆元正整数 $d$，回顾RSA加密算法原理（一）中所写，$d$ 要满足：$ed\equiv 1 \pmod{\phi(n)}$。由于 $e$ 与 $\phi(n)$ 互素，这样的 $d$ 一定是存在的，这里我们找出一个 $d=403$，可自行代入验证看看对不对。
现在，我们称二元组 $(n,e)$ 是本次加密的公钥，称 $d$ 是本次加密的私钥。因此本例中公钥是 $(1147, 67)$，私钥是 $403$。

得到公私钥后，B将公钥发送给A，A将自己的信息按以下流程加密：

加密过程

假设A发送的信息转换为数字以后为$m$，且需要保证$m<n$，这里假设$m=1024$
计算得到密文

$\begin{aligned}c&=m^e \pmod{n}\\&=1024^{67} \pmod{1147}\\&=280\end{aligned}$

B得到的密文为280，他将其发送给A。

解密过程

现在A拿到了密文$c=280$，同时A手中还握有私钥$d=403$，另外A当然知道$n$的值，因此A可以按以下方法进行解密（$m<n$也可以从解密过程看出来）：

$\begin{aligned}m&=c^d \pmod{n}\\&=280^{403} \pmod{1147}\\&=1024\end{aligned}$

还真的得到了明文，但这是巧合吗？当然不是，且看：

解密过程证明

首先我们有 $m^e\equiv c\pmod{n}$，这意味着 $c=kn+m^e$，那么 $c^d=(kn+m^e)^d\equiv m^{ed}\pmod{n}$。这是由于二项式展开项中，只有 $kn^0\times m^{ed}$ 不能被 $n$ 整除，其余所有项都含有 $n$ 的幂。

接下来我们只要证明:

$m^{ed}\equiv m\pmod{n}$

注意到 $ed=k\phi(n)+1$，代入之后我们需要证明的变成了:

$m^{k\phi(n)+1}\equiv m\pmod{n}$

接下来分为两类讨论：

$m,n$ 互素，此时由欧拉定理，$m^{\phi(n)}\equiv 1\pmod{n}$，因此 $m^{\phi(n)}=tn+1$，故 $\begin{aligned}m^{k\phi(n)+1}&=m(tn+1)^k\\ &\equiv m\times (tn)^0\times 1^k\\&=m\pmod{n}\end{aligned}$
$m,n$不互素，此时必定有 $m=kp$ 或 $m=kq$，WLOG，我们只考虑 $m=kp$ 情形，此时必有 $m \bot q$，因此

$m^{\phi(q)}=(kp)^{q-1}\equiv 1\pmod{q}$

与前面证明类似，可以得到

$[(kp)^{q-1}]^{h(p-1)}\times (kp)=(kp)^{h(p-1)(q-1)+1}\equiv kp\pmod{q}$

回过头来，我们有 $ed\equiv 1\pmod{\phi(n)}$，即 $ed=h(p-1)(q-1)+1$，此时我们让前面式子里的 $h$ 取为这里的 $h$，然后将 $ed$ 代入，就有

$(kp)^{ed}\equiv kp\pmod{q}$

那么 $(kp)^{ed}=kp+tq$，左侧为 $p$ 的倍数，那么右侧的 $t$ 必然也是 $p$ 的倍数，设为 $t=rp$，于是 $(kp)^{ed}=kp+rpq$，这也即 $m^{ed}=m+rn$，显然有：

$m^{ed}\equiv m\pmod{n}$

故对所有的情形均证明了该解密过程确实可以得到明文。

接下来我们来讨论该算法是否安全。

在获取公钥(n,e)的情况下如何才能破解密文？

以下列举一种想破解密文的常规思路。

要想破解密文，首先得得到密钥 $d$
$d$ 是 $e$ 在 $\phi(n)$ 乘群中的逆元，要想得到 $d$，就要得到 $\phi(n)$
$\phi(n)=(p-1)(q-1)$，要想得到$\phi(n)$，似乎要先得到 $p,q$
$p,q$ 是 $n$ 的素因子，要想得到 $p,q$，必须分解 $n$

由此我们发现，在获取公钥的情况下，常规思路破解密文的难度等同于对$n$进行素因子分解。我们当然可以轻松算出 $1147=31\times 37$，但当 $n$ 是一个上千二进制位的数的时候，分解它目前而言是一件不太可能的事。以下内容来自维基百科。

对极大整数做因数分解的难度决定了 RSA 算法的可靠性。换言之，对一极大整数做因数分解愈困难，RSA 算法愈可靠。假如有人找到一种快速因数分解的算法，那么 RSA 的可靠性就会极度下降。但找到这样的算法的可能性是非常小的。今天只有短的 RSA 密钥才可能被暴力破解。到 2008 年为止，世界上还没有任何可靠的攻击 RSA 算法的方式。只要密钥长度足够长，用 RSA 加密的信息实际上是不能被解破的。

维基百科: RSA加密演算法

在重要场合进行使用时，一般会取 $n$ 为上千二进制位的长整数，$e$ 一般取65537。