algorithm - 由于数量众多，无法理解 RSA 实现

我试图了解非对称加密算法的工作原理。我发现最常用的算法是 RSA，所以我检查了它的工作原理。我实际上并没有完全理解整个东西，但我知道它涉及使用天文数字的乘法和模运算。

我读到 RSA 使用 4096 或 8192 位密钥长度。这意味着相乘后的值和指数值的组合最多应该是 4096 位，对吧？让我们假设一个 1000 位的整数适合这个密钥长度。为此，我们假设 2 500 位数字相乘。

这是我无法理解的。一个 500 位的数字应该是 2000 位长，对吧？现代计算机的长度为 64 位。高性能服务器可以是 128 甚至 256 位长。但是 2000 位？我从未听说过有任何计算机能够或具有能够处理它的 ALU。

那么乘法、取模和其他运算是如何对如此庞大的数字进行的呢？或者 RSA 被设计成实际上不会进行这么大的计算（因为我对它的理解不够清楚）？还是在普通计算机中无法做到这一点，并且我们使用的密钥是预先计算好的？

还是我应该接受密码学很难并离开它？

标签： algorithmrsa

如果你回想在学校学习乘法和加法，大数是通过解决大数的组成数字上的简单问题来计算的。这篇 wiki 文章概述了小学乘法算法。它还展示了如何在代码中实现该算法。因此，您的问题的简单答案是该算法的一个奇特版本用于执行处理大数所需的数学运算。

由于计算机一次可以处理 64、128 或更多位，因此执行数学运算是一次对多个数字执行，而不是一次执行一个数字。

对于像 RSA 这样的算法，速度很受重视，数学可能会针对特定的密钥长度进行多次硬编码。NIST 哈希函数竞赛等竞赛非常重视性能，甚至考虑在硬件中实现数学的难度。

更一般地说，长数学由GMP、Boost Multiprecision Library等库执行。