RSA算法•真正的小学二年级数学题

🐢：本篇数学内容极多，请勿在睡前阅读。

因数，质数和离经叛道

让我们从轻松的部分开始：2×3=6，在这个式子中2和3就是6的因数。1×6=6，恭喜你，你发现了一个重要定理，一个数字可能有好几组因数。

那数字13呢，咦，似乎只有1×13这一组因数，所以，我们把形如13这样的数字叫做质数。

现在，我们来尝试一点不一样的，除法。6÷2=3，很正常，9÷4＝2…1，事情开始不一样了。在这里，剩下的这个1叫做余数。

最后，我们需要知道互质数，很简单，也就是两个公共的因数只有1的数字，就像13和40。

一个例子

如果你搞明白了以上内容，RSA算法对你也不是一个难事。

现在需要一个例子。为了方便起见，我们以（7，33）这个数对作为🍄的公钥，（3，33）为私钥。也就是说（7，33）对于任何人都是公开的。（统一称呼，我们把7，3，33用字母D，E，N代替）

🐢仍然想要发送114514，为了让大家能够跟着计算，我们一位一分隔，得到了六个数字。

加密并不麻烦，对着六个数进行幂运算，即F(x) = x^D ，结果为1，1，16384，78125，1，16384。

然后把它们分别除以N求余，得到1，1，16，14，1，16。这就是我们的密文。

🍄收到后会进行解密，这也不难，遵循同样的过程，只不过在这里F(x) = x^E 。结果等于1，1，4，5，1，4！好耶，一次RSA加密完成了。

难吗？不难，可以很难！

要想搞懂为什么破解RSA算法要用上量子计算机，我们首先要亲手生成一对密钥。注意，在这篇文章中，我们不会涉及实现这一切的详细证明。（🐢：确实太复杂）

首先，让我们选择两个质数，一个叫p，一个叫q，相乘得到的就是N，例如，p＝11，q＝5。

然后，我们要用到欧拉公式∅(x)，这个公式表示了小于等于N的数中与N互质数字的个数。可能有点绕，但我们只需要知道对于两个质数的乘积，∅(pq)＝(p-1)(q-1)，在这个例子中，它等于40，我们把它设为T。

现在，我们可以选择公钥D了，它被定义为大于1小于T的随意一个数字。不过，D不能是T的因数。我们选择7。

最后解开这样的一个式子就可以得到E，(D×E)modT＝1。

现在，你就得到了我们刚才所用的密钥对。很简单对吧，破解似乎也不难，只要对N分解因数就好了。那么让我们试试吧！

在这里，我们把N设置为这个数字。

没错，这就是RSA算法中实际使用的一个N，你要是把他分解出来了，请一定告诉我。（🐢：20万美元💵，我来了！）

结束，也是开始

到这为止，关于非对称加密的讲解终于结束了。现在，无论你发送一条微信，甚至访问一个网页，都悄无声息的发生了这套过程。这就是现代密码学的贡献。

在下一期，我们将把视角前移几百年，讲一讲古典密码学的杰作——恩格玛机。