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$ 不互素的应该有

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

  • 在 $(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$
  • 计算得到密文

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

解密过程

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

还真的得到了明文,但这是巧合吗?当然不是,且看:

解密过程证明

首先我们有 $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$ 的幂。

接下来我们只要证明:

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

接下来分为两类讨论:

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

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

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

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

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

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

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

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

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

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

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

维基百科: RSA加密演算法

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