如何在C语言中处理大量数字

Question

我正在使用C语言编写RSA加密算法。我并不打算将其用于任何生产环境，主要是为了扩大我对加密的理解。

如何处理RSA生成的巨大数字？即使使用像103这样相对较小的私钥进行解密，我仍然面临处理类似以下内容的问题：

67^103 mod 143 = (1.21816096336830017301951805581 x 10^188) mod 143

存储这样大小的数字的最佳方法是什么？是否有使用标准库的方法？

- mstagg

---

你可以自己实现所有的大数运算，但使用现有的多精度库（如GMP）会更容易。 - Artjom B.

那会起作用。但要小心溢出。你必须实现乘法，然后是除法（用于取模）。但说真的，最好使用GMP。 - Karoly Horvath

@mstagg RSA涉及大整数，在您的示例中显示了一个实数。这是一个使用大整数库的案例，或者编写一个这样的库既有教育意义又不会太过繁琐。 - Weather Vane

@Weather Vane 不同意这里的 67^103 mod 143 需要使用大型 int 库。输入都小于等于8位，这里的一切都可以通过快速简单的整数运算来解决。 - chux - Reinstate Monica

是的，OP在等式右侧的写法似乎表明他还没有学会高效的模指数运算。使用这种高效的ModExp，可以使用原语完成此操作。但是，对于更大的模数，他将需要一个bigint库，无论是自制的还是第三方的。我同意关于GMP的看法。它非常快速。例如，有3种主要方法可用于乘法。学校风格的长乘法最慢。使用FFT进行乘法对于非常大的数字来说是最快的。比大多数人自己编码的速度快得多。 - WDS

Answer 1

错误的方法。不需要先计算67^103，而是应该在循环中逐位计算指数。

每次循环计算一个比特位的模值。

uint32_t powmod(uint32_t base, uint32_t expo, uint32_t mod) {

  // % mod need only for the cases expo==0, mod<=1
  uint32_t y = 1u % mod;

  while (expo) {
    if (expo & 1u) {
      y = ((uint64_t) base * y) % mod;
    }
    expo >>= 1u;
    base = ((uint64_t) base * base) % mod;
  }

  return y;
}

int main(void) {
  printf("%lu",(unsigned long)  powmod(67, 103, 143));
}

输出

89

- chux - Reinstate Monica

---

“处理RSA生成的大量数字的诀窍”是不要按照通常的方式进行数学运算-使用像上面那样的快捷方式。 - chux - Reinstate Monica

哦，是的，甚至以前做过这个幂运算练习，通过处理每一位幂：没有仔细阅读 Q，+1。 - Weather Vane

@Weather Vane 是的 - RSA 的整个目的就是利用计算技巧（如果有密钥），来解决一个数学黑盒问题，否则通过暴力计算是不可行的。 - chux - Reinstate Monica