首页

这次来深入到 RSA 算法的细节中去。因为咱们每天说非对称加密，说公钥私钥，但是公钥和私钥到底是怎么产生的，加密和解密过程到底是怎么样的，不看看具体算法实现还真是感觉心里没底。RSA 算法是非对称加密算法鼻祖，至今仍然是最为广泛使用的算法之一，所以我们就来拆解一下 RSA 算法本身。

宏观思路

学东西最怕的就是没有大思路，直接深入细节。所以开始之前，我们先宏观上讨论一下 RSA 算法到底是用来干嘛的？总体的实现思路又是怎样的呢？

说到最底层，RSA 算法的作用其实非常简单，就是生成公钥和私钥的。公钥用于加密信息，私钥用来解密。整个过程的大思路是先上锁，后开锁。Alice 自己先买一把锁，然后把锁头发送给 Bob ，注意 Bob 给信息上锁的时候，肯定是不需要钥匙的，上了锁的信息发送给 Alice 之后，Alice 就可以用钥匙打开锁，拿到信息。锁和开锁明显是两个不同的过程，没有必要让钥匙参与到上锁过程中，这个就是非对称加密的的思路源头了。上锁的时候，Bob 只需要公钥，而 Alice 开锁的时候才需要私钥。所以公钥就是加密 Key ，私钥就是解密 Key 。解密是加密的逆向过程，所以实现加密和解密的第一步就是找到一个函数，函数的正向运算很容易，但是逆向运算很难。对应 RSA 的情况，也就是把公钥和信息作为参数进行运算，得到密文，这个过程要很容易，而逆向运算，由密文和公钥想要获得信息，是很难做到的。

当然，这个函数还必须有另外一个特点。就是逆向操作虽然默认很难做到的，但是如果拥有了特定的提示信息，操作就变得非常容易了。这里的提示信息，显然就是私钥。

总之，找到这样一个正向容易运算，反向默认很难，但是如果有了私钥就很容易运算的函数，就是实现 RSA 算法的核心思路。

具体实现

下面我们就来看看 RSA 算法具体的实现方式。

先来补充一个数学知识：取模运算。取模运算跟取余运算很类似，基本就是算余数。例如 3 mod 2 的结果就是1，mod 就是取模的意思。

RSA 使用的单向函数是这样的，拿出要加密的信息 m ，我们知道任何的计算机信息都能转换成二进制数，所以当然也能转换成十进制的一个整数。这里 m 是一个整数，接下来随机选择一个 e ，来作为 m 的指数。注意，这里的指数 e 的选择范围是有一定限制的，但是是随机任意选择的。接下来，进行 m 的 e 次方运算，然后对也是随机选取的另一个整数 N 进行取模运算，最后得到的结果就是密文，用 c 表示 。举个例子，m 等于7 ，e 选择为2 ，N 选择23，这样，最后的密文 c 就等于49对23取模，结果是6。也就是说7经过加密，最后密文是6。这个运算有个特点，给定 m 和 e 以及 N 的值，很容易算出 c ，但是给定 c 和 e 以及 N 很难算出 m 来。这就是我们需要的单向函数。

于是，我们的锁就有了，也就是 ”e 次方然后对 N 取模“。那么，开这把锁的钥匙是什么呢？简单来说，就是让逆向运算过程变得简单的信息。

逆向运算，就是从密文得到信息。经过数学推导，其实是可以得到这样的逆向运算过程，一定存在一个整数 d ，使得 c 的 d 次方对 N 取模，是可以得到 m 的。最终， e 和 N 按照一定规范组合到一起，就是公钥，而 d 和 N 组合到一起就是私钥。而如何给定 e ，算出合适的 d ，其实是要引入另一个单向函数了，这就是整数分解问题了。

总之，RSA 算法的单向函数找到了，于是加密用的锁也就找到了。但是其实这个函数本身不是 RSA 算法最复杂的地方，最复杂的内容在于如何由 e 算出 d 。

安全性取决与整数分解问题

如何运算出 d 的过程我们暂时不展开。粗略来讲，从 e 运算出 d 的过程，涉及到 N 的整数分解问题。整个 RSA 算法的安全性就取决于整数分解这个基本数学问题。

来解释一下整数分解问题。整数分解就是把一个数分解成多个素数的乘积。素数就是那些只能被1和自己整除的整数，这个小时候咱们学过的。例如 45 可以分解成 3x3x5 ，任何数分解的结果都是唯一的。而 RSA 算法中的整数分解有一定的特殊性。被分解的数需要是两个，而不是多个素数的乘积。虽然由两个素数相乘获得结果非常简单，但是反过来，分解过程是很难的。很难的意思就是如果数足够大，即使用计算机也需要成千上万年才能算出来的问题，或者可以说很难就等于”实际中不能实现“。而这一点就是 RSA 算法的安全基石。如果有一天，有数学家找出整数分解的有效运算方法，那么 RSA 算法也就不能用了。

实际生成公钥和私钥的过程是，我们选出 p1 和 p2 两个大素数，让 N = p1 * p2 。随机选择一个指数 e ，这样公钥就有了。而在知道 p1 和 p2 的前提下，从公钥算出私钥，也就是算出 d ，是非常容易的。而外人，因为不知道 p1 和 p2 ，而只知道 N ，所以不可能从 e 算出 d ，也就是不可能用公钥算出私钥。

总之只要整数分解问题无解，那么 RSA 就是安全的。

总结

这就是 RSA 算法的工作原理了。宏观上的思路就是，要找到一个包含取模运算的单向函数，保证信息加密容易，而反向解密很难。另外，还要找到第二个单向函数，也就是整数分解问题的函数，保证在知道分解结果的条件下，从公钥算出私钥是容易的，而如果不知道，就不可能算出私钥。真正的 RSA 算法，是这两个单向函数的综合使用。但是对于如何进行解密，公钥和私钥生成的细节，我们没有展开，因为这涉及到更多的数学推导，后续文章中 Peter 再给大家介绍。

参考：