密码学101：RSA算法解析

这是关于加密技术的一系列文章的一部分。如果这是你看到的第一篇文章，我强烈建议你从 系列的开头 开始阅读。

RSA 加密是目前使用最广泛的加密算法之一——它仅依赖于 模 n 的整数加法群。这是一个很好的例子，展示了在没有椭圆曲线或其他更复杂构造的情况下，可以做到多少。

这一段专注于解释 RSA 算法的工作原理和细微差别。

潜在问题

许多加密机制的工作原理是，除非你知道某个 秘密密钥，否则执行某种操作是非常困难的。在 加密 中，这正是这个概念：未加密的信息在不知道该秘密密钥的情况下是 不可解读 的。

那么，这是如何实现的呢？通过构建一个问题，除非你有一些额外的 秘密信息，否则这个问题是 非常难以解决 的。RSA 就基于这样的问题：将大数字分解为其素因子。即：给定一个（大）数字 n，将其表示为：

其中 p 和 q 是大素数。如果你知道 p 和 q，计算 n 是极其简单的——如果你知道 n 和 q，计算 p 也是如此。

多大算是足够大？

当然，如果问题容易解决，那这一切都是 毫无意义 的。例如，如果 n = 7×11 = 77，那么因式分解几乎在瞬间就完成了。然而，随着素数的增大，因式分解所需的时间也越来越长。

建议的素因子 p 和 q 的大小在 1024 到 2048 位之间。作为参考，这是一 个 1024 位素数的样子：

170154366828665079503315635359566390626153860097410117673698414542663355444709893966571750073322692712277666971313348160841835991041384679700511912064982526249529596585220499141442747333138443745082395711957231040341599508490720584345044145678716964326909852653412051765274781142172235546768485104821112642811

是的，它很大。

估计找到一个 2048 位长的大数的素因子需要多长时间是很困难的。主要是因为实际上并没有进行过这样的尝试！

但仍然有人推测，即使有强大的硬件，这也需要从 数百年 到 数千年。除非量子计算技术变得可用——这是另一个故事。

准备工作

我们如何使用前面的问题来加密数据？这样做将需要一些定义。特别是，我们需要了解 欧拉函数 及其性质。

欧拉函数

对于任何自然数 n，该函数（表示为 φ(n)) 计算有多少...