信息传输背后的巨人,原来如此亲切……

封面

互联网之所以如此发展壮大,离不开一个重要的算法 —— RSA 加密算法

如今,几乎所有的信息传输,都基于这个加密算法,从 Https 到 SSH,成为了互联网环境中的空气,无处不在,且重要无比。那么 RSA 算法是如何实现的呢?为什么它会承载起整个互联网的安全?

加密基石

在加密领域,有一块很重要的基石,就是我们在中学学习的质数,或者素数

还记的它的定义吗?就是除了 $1$ 和 它本身外,不能被任何正整数整除的数。比如 $2,3,5,7,11$ 等等。

有多少个质数呢?这个问题欧几里得在他的《几何原本》重已经得到证明,答案是有无穷多个。

对于质数来说,还有很多有趣的定理,其中一些就是 RSA 加密的基础。

欧拉函数

有这样的一个问题:

如果有个任意一个正整数 $n$ ,那么小于 $n$ 的正整数中有多少个与 $n$ 互质呢?

计算这个问题的过程就叫 欧拉函数,数学中用 $\phi(n)$ 表示。比如正整数 $8$ ,从 $1$ 到 $8$ 中,有 $1,3,5,7$ 与 $8$ 互质,所以 $\phi(8) = 4$

$\phi$ 是希腊字母表中第 21 个字母的小写形式,有些字体也可是写成:$φ$。大写为 $\Phi$,音标 /fi/,类似 连读的发音,在此特指 欧拉函数

如何求解欧拉函数呢?

最简单的方法就是写个循环,从 $1$ 开始,找与 $n$ 互质的数,不过这种方式效率太差,有没有更高效的算法呢?

数学家已经找到了更好的方法。

首先 任意一个大于 $1$ 的正整数,都可以表示为一系列质数的乘积,即 算术基本定理。 例如 $8 = 2\times2\times2 = 2^3$,$1323 = 3^3 \times 7^2$,等等

然后,如果两个整数互质,它们的乘积,那么这个乘积值的欧拉函数值等于两个质数各自欧拉函数值的乘积,也就是:

如果 $n = p \times q$ 那么: \(\phi(n) = \phi(p)\times\phi(q)\tag 1\)

推理过程,需要用到 孙子定理,有兴趣的读者可以研究一下,这里就不做展开了。

还有,对于一个质数 $q$,它的欧拉函数值是多少呢?很容易根据质数的定义得到结果,因为质数无法被除了 $1$ 和 本身以外的任何整数整除,那么小于它的正整数中,就有 $q-1$ 个数与 $q$ 互质。

有了这个概念,就能得到一个重要的推论:

如果 $p$ 和 $q$ 都是质数,那么它们的乘积 $n$ 的 欧拉函数值就为: \(\phi(n)=(p-1)\times(q-1)\tag 2\)

先记住这个推论。

欧拉定理

前面的欧拉函数,实际上是为了欧拉定理服务的,什么是欧拉定理呢?

欧拉定理实际上是在说明一个同余(具有共同的余数)问题的,具体定理如下:

如果 $n$ 和 $a$ 为正整数,且 $n$ 和 $a$ 互质(即 $n$ 和 $a$ 的最大公约数为 $1$),那么:

\[a^{\phi(n)}\equiv 1(mod\ n)\tag 3\]

如何理解呢,就是互质的两个数,如果对另一个数做求余运算,那么,对另一个数的欧拉函数值次方求余,余数必然是 $1$。

欧拉定理的证明 比较复杂,有兴趣的读者可以自行研究。

这样需要引出一个重要的概念 —— 模反元素

简单说,一个数 $a$ 对数 $n$ 的模反元素 $b$ 就是要满足:

\[a\times b\equiv 1(mod\ n)\]

即 $a\times b$ 除以 $n$ 余数为 $1$。

欧拉定理的出现,让一些关于余数的求解问题变地及其简单,例如,$7$ 和 $10$ 互质,那么就有:

\[7^{\phi(10)}\equiv 1(mod\ 10)\]

而 $\phi(10) = 4$,所以就有:

\[7^{4k} \equiv1(mod\ 10)\]

现在问 $7^{220}$ 的余数是多少?是不是心算就能知道答案呢?

欧拉定理有一个特殊的情况:

如果正整数 $a$ 和 质数 $p$ 互质,因为 $\phi(p) = p-1$,所以这种情况下,欧拉定理可以写成:

\[a^{p-1}\equiv1(mod\ p)\tag 4\]

是不是已经被这些公式搞晕了,其实这些公式是相互支撑的,主要是为了得到最后的这个公式(公式 4),因为它是 RSA 的理论基础。

RSA 加密算法

有了前面的一些理论铺垫,再去看 RSA 算法的时候,理解起来就更清晰了。

RSA 加密算法,主要是创建一对密钥,一个是公钥一个是私钥。

如果需要给某个人发送加密消息时,可以用那个人公布的公钥对消息进行加密。等那个人收到消息后,可以用他的私钥进行解密,很神奇吧,不过其中的秘密就在上节的定理中。

创建密钥

我先来看看 RSA 计算密钥对的过程。

  1. 随机选取两个不相等的质数 $p$ 和 $q$,比如选取 $59$ 和 $43$
  2. 计算 $p$ 和 $q$ 的乘积 $n$,即 $59\times43=2537$
  3. 计算 $n$ 的欧拉函数 $\phi(n)$,根据公式 2,就有 $\phi(n)=(p-1)\times(q-1)$。即 $\phi(2537)=(59-1)\times(43-1)=2436$
  4. 随机选择一个整数 $e$,条件是:$1<e<\phi(n)$ 且 $e$ 与 $\phi(n)$ 互质。我们在 $1$ 到 $2436$ 直接选择 $13$ 作为 $e$
  5. 计算 $e$ 对 $\phi(n)$ 的模反元素 $d$。根据前面模反元素的定义,可以得到,$d$ 必须使得 $e\times d\equiv 1 (mod\ n)$。如何获得 $d$ 呢?我们做下分解:
    1. $e\times d\equiv 1 (mod\ n)$ 等价于 $e\times d -1 = k\times \phi(n)$
    2. 那么求解 $d$ 就相当于求解二元一次方程:$ex + \phi(n)y=1$
    3. 已知 $e$ 为 $13$ 和 $\phi(n)$ 为 $2436$ 扩展欧几里得算法 可以得到解为:$(937, -5)$。扩展欧几里得算法代码如下:

      1
      2
      3
      4
      5
      6
      7
      def extendedEuclidean(a, b):
        if (b == 0):
          return 1, 0
        else:
          m,n = extendedEuclidean(b, a % b)
          quotient = a//b
          return n, m - (n * quotient)
      
      • 这是一个递归算法,当 $b$ 等于 $0$ 时,$x$ 就为 $1$,$y$ 就为 $0$
      • 否则将 $b$ 和 除以 $a$ 的余数作为新参数,继续
      • 直到将 $b$ 分解为 $0$,逐层返回,最终就很求解到 $x$ 和 $y$
      • 需要注意的是 $x$ 和 $y$ 并非唯一,这个方法只能返回其中一个解
  6. 将 $n$ 和 $e$ 封装为公钥,将 $n$ 和 $d$ 封装为私钥。即公钥为 $(2537, 13)$,私钥为 $(2537, 937)$

实际应用中,公钥和私钥对一定的规范表达,例如 ASN.1,这里为了简便,不做相应的格式化了。

加密和解密

有了密钥,如何对一个信息进行加密呢?

如果用 $m$ 表示信息,$c$ 表示加密后的结果,那么他们必将满足以下公式:

\[m^e\equiv c(mod\ n)\tag 5\]

实际上就是 $c$ 是求模运算的余数。

例如我们要发送的原文信息是 65,来看看加密后的结果是什么:

\[65^{13}\ mod\ 2537 = 1722\]
1
2
>>> 65**13%2537
1722

计算可知 $c=1722$,这样就完成了加密。

下面看看如何解密:

如果公式 5 成了,那么下面的公式也必然成立:

\[c^d\equiv m(mod\ n)\]

即 $c$ 的 $d$ 次方,与 $n$ 求模,余数就是 $m$。

我们来计算一下:

\[1722^{937}\ mod\ 2537 = 65\]
1
2
>>> 1722**937%2527
65

这样我们就实现了加密和解密的过程。

这里有个问题,如果对字符串或者图片等信息,如何加密呢?

其实只需要获得这些信息的二进制编码就好了,只要保证 $m < n$ 就可以了。

RSA 的可靠性

我们了解了 RSA 加密过程后,就能体会到,为了保险,私钥对$(n, d)$ 是需要严格保密的,要不然就失去了加密的效果。

其中最重要的是 $d$,因为 $n$ 和 $e$ 是公开的。

那么,$d$ 就不能被反向的计算出来吗?

其实真的可以,无非就是多试几次就可以了,那 RSA 为啥还指的信赖呢?

这主要取决于被破解的成本高不高。截至目前,1024 位(比特位)一下的整数 RSA 加密可以被破解,所以需要设置更高位数的整数,比如 2048 甚至更高位数的整数。

其中导致破解成本的是:(目前)没有一个有效的算法可以快速地实现因数分解,这个就成了 RSA 加密算法的护城河。

总结

RSA 已经深入到了我们生活的角角落落,就像互联网中的空气一样,对我们很重要,习以为常,甚至感受不到它的存在。

但是我们还是有必要了解一下 RSA 算法的本质,虽然有很多数学公式和理论不好理解,但通过研究和学习,能感受到先驱者们的伟大和我们人类的巨大智慧。

在此向 RSA 算法的三位数学家:Rivest、Shamir 和 Adleman 致敬。

三位数学家

比心!

Python Geek Tech wechat
欢迎订阅 Python 技术,这里分享关于 Python 的一切。