互联网之所以如此发展壮大,离不开一个重要的算法 —— 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 计算密钥对的过程。
- 随机选取两个不相等的质数 $p$ 和 $q$,比如选取 $59$ 和 $43$
- 计算 $p$ 和 $q$ 的乘积 $n$,即 $59\times43=2537$
- 计算 $n$ 的欧拉函数 $\phi(n)$,根据公式 2,就有 $\phi(n)=(p-1)\times(q-1)$。即 $\phi(2537)=(59-1)\times(43-1)=2436$
- 随机选择一个整数 $e$,条件是:$1<e<\phi(n)$ 且 $e$ 与 $\phi(n)$ 互质。我们在 $1$ 到 $2436$ 直接选择 $13$ 作为 $e$
- 计算 $e$ 对 $\phi(n)$ 的模反元素 $d$。根据前面模反元素的定义,可以得到,$d$ 必须使得 $e\times d\equiv 1 (mod\ n)$。如何获得 $d$ 呢?我们做下分解:
- $e\times d\equiv 1 (mod\ n)$ 等价于 $e\times d -1 = k\times \phi(n)$
- 那么求解 $d$ 就相当于求解二元一次方程:$ex + \phi(n)y=1$
-
已知 $e$ 为 $13$ 和 $\phi(n)$ 为 $2436$ 扩展欧几里得算法 可以得到解为:$(937, -5)$。扩展欧几里得算法代码如下:
1
2
3
4
5
6
7def 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$ 并非唯一,这个方法只能返回其中一个解
- 将 $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 |
|
计算可知 $c=1722$,这样就完成了加密。
下面看看如何解密:
如果公式 5 成了,那么下面的公式也必然成立:
\[c^d\equiv m(mod\ n)\]即 $c$ 的 $d$ 次方,与 $n$ 求模,余数就是 $m$。
我们来计算一下:
\[1722^{937}\ mod\ 2537 = 65\]1 |
|
这样我们就实现了加密和解密的过程。
这里有个问题,如果对字符串或者图片等信息,如何加密呢?
其实只需要获得这些信息的二进制编码就好了,只要保证 $m < n$ 就可以了。
RSA 的可靠性
我们了解了 RSA 加密过程后,就能体会到,为了保险,私钥对$(n, d)$ 是需要严格保密的,要不然就失去了加密的效果。
其中最重要的是 $d$,因为 $n$ 和 $e$ 是公开的。
那么,$d$ 就不能被反向的计算出来吗?
其实真的可以,无非就是多试几次就可以了,那 RSA 为啥还指的信赖呢?
这主要取决于被破解的成本高不高。截至目前,1024 位(比特位)一下的整数 RSA 加密可以被破解,所以需要设置更高位数的整数,比如 2048 甚至更高位数的整数。
其中导致破解成本的是:(目前)没有一个有效的算法可以快速地实现因数分解,这个就成了 RSA 加密算法的护城河。
总结
RSA 已经深入到了我们生活的角角落落,就像互联网中的空气一样,对我们很重要,习以为常,甚至感受不到它的存在。
但是我们还是有必要了解一下 RSA 算法的本质,虽然有很多数学公式和理论不好理解,但通过研究和学习,能感受到先驱者们的伟大和我们人类的巨大智慧。
在此向 RSA 算法的三位数学家:Rivest、Shamir 和 Adleman 致敬。
比心!