在RSA中，CPU如何处理这个巨大的模数（8192位）？

#1 楼

它（或更确切地说，是运行它的软件）将使用任意精度（“ bignum”）算法。这种工作方式基本上与您（可能）在学校学习纸上算术的方式相同。

在学校教给我们人类的算术是10进位算术-也就是说，我们将数字表示为由十个不同的数字组成的字符串，从“ 0”到“ 9”，其中每个数字单独代表一个小于10的不同小数字，并且在另一个数字的左边放置一个数字，其值乘以10。 br />
假设您在上小学时并未完全入睡，您可能还记得必须记住一个数字的加法和乘法表：1 +1 = 2，7 + 7 = 14，6×4 = 24，依此类推。这些是基数为10的算术的基本“原子”运算，一旦您知道如何进行操作，就可以将它们组合起来以计算出具有更大数字的东西。当然，所有基本操作都被完美地记住了；如果说，忘记7×6是什么，但仍要记住6×6 = 36，则可以再从中算出六个数字，最后得出42。如果您忘记了例如7 + 7的含义，那么您可以指望一下达到14。事实证明，对于我们人类来说，要记住那些基本的一位数运算-即与人类一起实现它们等同于查找表-每次运算都比从第一原理中求出运算要快得多。对于计算机，折衷可能会有所不同。）

例如，取决于如何教授数学在您的学校，您可能还记得在纸上写下这样的一个附加问题：

Exercise: 12345 + 67890 = ______

             <-- carries
    12345    <-- first number
  + 67890    <-- second number
  -------
             <-- result

并进行求解从右到左按数字igit。在这里，您将从5 + 0 = 5（无进位）开始：

       0     <-- carries
    12345    <-- first number
  + 67890    <-- second number
  -------
        5    <-- result

，然后继续进行4 + 9 = 13（即写下3，携带1）：

      10     <-- carries
    12345    <-- first number
  + 67890    <-- second number
  -------
       35    <-- result

然后1 + 3 + 8 = 4 + 8 = 12（即写下2，携带1），依此类推，直到：

    1110     <-- carries
    12345    <-- first number
  + 67890    <-- second number
  -------
    80235    <-- result

对于其他基本算术运算，例如减法，乘法甚至是长除法（也可用于模数归约），他们也学到了类似的纸笔算法。要意识到的重要一点是，所有这些计算方法都是基于操纵数字字符串的规则，以及对单个数字的简单算术运算。只要您可以执行基本的一位数运算，并且知道将它们组合在一起的算法，就可以在纸上使用所需（或需要）的数字进行算术运算。

因此那么，计算机是如何做到的呢？当然，他们可以使用与我们完全相同的十进制算术规则，但是效率很低。典型的CPU已经具有快速电路，可通过一条机器代码指令将任意两个32或64位（甚至可能更大）的数字相加或相乘，因此将32或64位算术视为基本构造更为有意义。因此，bignum算术的典型计算机实现有效地使用了32或64位整数的“数字”，并将较大的数字表示为这些较小整数的字符串。所使用的算法与我们用于铅笔和纸计算的算法非常相似，不同之处在于，计算机不是以10为基数，而是更可能使用以232或264为基数。

，让我们计算两个随机的128位数字的总和（为方便起见，用十六进制表示）：

Exercise: 3d96d3e9d019665051ecf94e4c0c697b +
          a80314053a779df7464ea2feebf771be = ______

现代CPU也许能够直接计算出该数字，但是让我们假设我们只有32位CPU。幸运的是，我们可以将数字分解为32位块，并使用之前使用的相同加法算法：

                                         <-- carries
    3d96d3e9 d0196650 51ecf94e 4c0c697b  <-- first number
  + a8031405 3a779df7 464ea2fe ebf771be  <-- second number
  -------------------------------------
                                         <-- result

所以首先，我们需要计算4c0c697b + ebf771be，我们的CPU会很容易地告诉我们13803db39（即32位结果3803db39，加上进位1）：

                             1           <-- carries
    3d96d3e9 d0196650 51ecf94e 4c0c697b  <-- first number
  + a8031405 3a779df7 464ea2fe ebf771be  <-- second number
  -------------------------------------
                               3803db39  <-- result

接下来我们问我们的CPU可以计算51ecf94e + 464ea2fe，并且由于进位而将结果加1，从而得出983b9c4d（下一个位置没有进位）：

                    0        1           <-- carries
    3d96d3e9 d0196650 51ecf94e 4c0c697b  <-- first number
  + a8031405 3a779df7 464ea2fe ebf771be  <-- second number
  -------------------------------------
                      983b9c4d 3803db39  <-- result

我们可以然后以相同的方式进行剩余的两个32位加法运算，得到d0196650 + 3a779df7 = 10a910447（即0a910447并带有1）和3d96d3e9 + a8031405 + 1 = e599e7ef：

  0        1        0        1           <-- carries
    3d96d3e9 d0196650 51ecf94e 4c0c697b  <-- first number
  + a8031405 3a779df7 464ea2fe ebf771be  <-- second number
  -------------------------------------
    e599e7ef 0a910447 983b9c4d 3803db39  <-- result

！

我在这个简单的示例中使用了加法运算，但是类似的算法也可以用于其他算术运算，包括取幂和模块化归约（通常将它们合并为一个模块化的求幂算法，因为它的功能更多）高效地将它们组合在一起，而不是先求幂然后再减小）。

还请注意，用于加密的算术算法raphy往往有些专门化，因为在加密中，确保算法花费相同的时间（并且消耗大致相同的功率等）来避免定时攻击和其他类型的旁信道攻击通常很重要。）不管要加（或乘或乘幂等）的数字是什么。

#2 楼

当然，处理器不能直接处理如此大量的数据。这是通过GMP之类的库完成的。有关此类库的列表，请参见Wikipedia；有关基础思想的信息，请参见Gerhard和von zur Gathen等优秀教科书。免费提供的《应用密码学手册》也谈到了这一点，特别是在第14章中。

#3 楼

正如其他人指出的那样，您通常使用某种任意精度的整数库。我感到有必要指出，但是，与加法相比，将乘法扩展到大整数绝对是不平凡的。通过加法，您可以从一个单词到下一个单词有一点进位，并且在典型的处理器上，您甚至有一条专用于执行加法运算的指令，该加法考虑了进位位，因此从最低有效位开始变成一个简单的循环以获得结果最重要。

通过乘法，事情并不是那么简单。让我们考虑一下与@Ilmari所使用的示例相同的示例，它具有128位数字和32位CPU（但是，显然，乘而不是加数字）。 -不重要的。此外，结果的位0仅取决于两个输入中每个输入的位0。结果的位1仅取决于两个输入的位1和位0的进位（依此类推）。使用乘法，您不会得到分段的“整洁”效果。

这种情况并非并非没有希望。目前，让我们考虑在32位计算机上将两个64位操作数相乘。我们可以将操作数分为两部分，一个由低32位组成，另一个由高32位组成。然后我们应用分配属性：

（A + B）（C + D）= AC + BC + AD + BD

因为每个输入只有32个有效位，我们可以在32位进程上执行每个单独的乘法，而不会出现任何问题。这使我们可以将4个中间值相加-因此现在有了@Ilmari已经概述的（相对）简单的情况。

#4 楼

当其他答案从更简单的问题“计算机如何处理大量计算”解决该问题时，特定的问题是计算机如何处理较大的模数，答案是存在专门用于处理较大的模数计算的算法和技术。 />维基百科提供了一个简短的术语和算法列表，在执行此操作时应该考虑一下这些术语和算法：

由于模块化算术具有如此广泛的应用范围，因此重要的是要知道解决一个算法很难一致性系统。线性一致系统可以在多项式时间内以高斯消去的形式求解，有关详细信息，请参见线性一致定理。还存在诸如Montgomery约简之类的算法，以使简单的算术运算（例如乘法和乘幂模n）能够有效地大量执行。
某些运算，例如找到离散对数或二次同余，似乎是就像整数分解一样困难（甚至可以证明），因此是密码算法和加密的起点。这些问题可能是NP中间问题。
求解非线性模块化算术方程组是NP完全的。

模块化算术没有得到广泛的讲授，因此有许多发现当他们在离散数学中寻求针对特定类型问题的更简单解决方案时，它就为自己服务。

#5 楼

要记住的一个重要方面，我在其他答案中没有看到，是二进制模8192非常容易，因为8192只是2^13。

如果将模数设为“正常”以10为底的数字，您会称其简单。 %100。您只需截断最后2位数字之前的所有内容。

在二进制中，1237659%100=59或以二进制形式%8192也是如此。您只需输入您的电话号码，例如10000000000000，而仅使用最后13位数字，然后得到1001100001000010111000100010001001。

编辑：

对不起。发布此答案后，我再次通读了您的问题，并意识到它是％8192bit或〜1 * 10 ^ 2466。尽管我的“答案”仍然是正确的，但它没有任何明显的影响。