理解RSA算法原理

介绍

        RSA算法，就是我们常说的公钥算法，这个算法在很多地方都能看到它的应用。管理代码仓库时，我们不想每次都使用密码，可以使用SSH，把公钥传到github/gitee，私钥保存到本地，下次就可以直接拉推代码了；访问网站时，我们要认定一个网站的合法身份，需要询问它的合法证书，而支撑证书的实现原理也少不了公钥算法。

        本文的目的，是换一个角度去理解这个RSA算法，从设计者的角度去理解它，才能真正了解它的由来和原理。

角度转变

        一想到RSA算法，我们先来看百科和《密码学》上如何来教我们认识这个算法的。

        这段文字，其实把RSA算法说得很清楚，但是如果此时有人问你“RSA的原理是啥？”，你如何回答这个问题？ 我曾经看了这段文字无数遍，仍然还是觉得无法回答这个问题，因为这段文字其实是在教我们如何使用这个算法，本质上是站在用户的角度来认识这个算法的，并没有从设计者的角度来教我们认识它。下面我们尝试换个角度来看看。

从对称到非对称

        有人说，加密解密是天才疯子之间的一个对抗游戏，他们的一方想尽办法要把一段信息加密成谁也破解不了的密文，另一方则想尽办法把加密的密文破解出来。

        最开始，对称密钥算法就像我们家里面门上安装的锁，当我们试图锁门时，只要有一把钥匙就行了，而当我们想要打开这扇门，也同样需要这把钥匙。抽象成算法就是，一个变换的规则，比如较为古老的凯撒密码，当别人给你发一段文字"To Bejing"，密钥是"所有字母向后移动一个位置",根据这个密钥可以得到加密的结果"Up Cfjkjoh"，当你收到这段文字后，你只需要把密钥反向作用一下(类似于锁门反向扭转)，密文就会被解密出来。但是这个问题就在于，任何人知道了这个密钥都能解密出来，当你要和一个远在千里之外的人加密通信，你还得提前通信沟通密钥，一旦你的密钥被劫持，那所有的加密动作都失去了意义。这就是常说的对称加密。

        来到非对称加密时代，我们希望别人就算知道我们怎么加密的，也不知道我们怎么解密，也就是说加密和解密是两把钥匙，而不是像开门那样反向扭转就行了。同时，更高的期望带来更高的要求，要做到这样，需要更加巧妙的设计。RSA算法也就是在这样的需求下诞生。

        RSA到底是什么，我们前面已经见识过了，在此不再赘述，现在假设我们就是设计者，如何从头来设计一个算法实现这样一个目的。

1. 最基本的要求

        首先，我们有一段明文M，我们希望有两个密钥,，得到如下的一个结果：

                 加密：我们用加密M,得到了密文E

                 解密：我们用解密E,又得到了明文M

       这个其实就是我们对加解密算法最原始的一个理解和要求，用一把钥匙对门进行上锁，然后用另外一把钥匙把门打开，这就是非对称加密。把这两个步骤合并一下，就得到如下表达式

  2. 提出问题: 如何巧妙设计这两个密钥，让它达到我们的要求?

        让我们来看看，RSA算法是怎么干的，它利用了数论的知识，使用了取模的方式，并巧妙地选取密钥，目的就是为了解决我们基于步骤1提出的问题。

        它选取了两个密钥，一个叫做e，一个叫做d，我们先不去考虑e和d的由来，假设这个e和d是我们想象的，最终我们希望这两个密钥能够实现这样一个效果。

         本质就是用e对M进行加密，然后用d对加密结果进行解密，这样一圈下来，我们又得到了最初的明文M。只是此处的加解密我们要特殊提出来描述一下：那就是求指数再取模。

3.深入RSA：它怎么保证如上等式成立？

        在上面两步，我们从原始需求出发，并“假想”了一个等式，这个等式恰好满足了我们的需求，可是，是否存在这样的e,d,n让我们这个等式成立，如果要让这个等式成立，他们需要满足什么条件和关系呢?这个时候，数论知识帮助我们解决了这个问题。

• 一点魔法

        我们先来说一个数论知识，这个知识是数学家推理得到的一个结论，这个结论就是：

        如果p,q是素数，且有n=pq和z=(p-1)(q-1)，那么如下等式成立

       这个地方，x和y是任意的，你可以带入任何有效值，但是n和z的关系是密切的，n是p和q的乘积，z是(p-1)和(q-1)的乘积，就这样的一个关系，使得如上等式成立。而这个等式，是RSA算法的关键，正是因为有了这个等式，RSA算法才有了根基。

•  回到RSA

        我们回到第二步，把它做一个变形，实际上我们需要得到的是这样的表达式：

        很明显，如果要得到上面这个等式，我们希望通过某种方式，把ed变成1，我们可以选取一个z得到这样一个表达式：

        构造这个表达式，是为了利用上面数论的知识（把M看作x,ed看作y），可以把n分解成p,q的乘积，选取z=(p-1)(q-1)，这个等式就成立(依据如上的数学结论)。

        再进一步，我们还需要ed和z之间满足一个关系，这个关系就是:

        这个关系一旦满足，就可以变换成,也就是如下等式成立

•  关于ed和z的关系

        e和d就是我们的加解密密钥，在选取e的时候，我们只需要从[1,n)中选一个数字，满足和z互质，e确定了之后，再找一个d，满足ed对z取模余1，这样一对密钥就构成了。至于为什么这么选择，能够让明文被加密后再被解密出来，上面两步即可说明。

4.综述

        理解RSA算法，首先理解设计它的初衷，RSA算法难以理解之处就在于它为了让如下等式成立：

巧妙地构造了加/解密地方式(求指数取模)，并且定义了一个规则，这个规则决定我们如何来选取密钥，按照这个规则选取的密钥，可以通过数论知识得以证明，加密密钥和解密密钥的两次作用可以通过数学规律抵消掉，让密文恢复明文。要理解RSA，关键在于理解选取密钥时的规则，以及为什么就得按照这个规则来选（换一个规则行不行？），按照这个规则来选是利用了什么数学知识使得等式很巧妙地就满足了。