C++ 处理非常大的整数

Question

我使用 RSA 算法进行加密/解密，为了解密文件，您必须处理一些相当大的值。 更具体地说，像

P = C^d % n
  = 62^65 % 133

Now that 这样的事情实际上是唯一需要进行的计算。 我尝试过使用 Matt McCutchen 的 BigInteger 库，但在链接过程中遇到了很多编译器错误，例如：

encryption.o(.text+0x187):encryption.cpp: undefined reference to `BigInteger::BigInteger(int)'

encryption.o(.text+0x302):encryption.cpp: undefined reference to `operator<<(std::ostream&, BigInteger const&)'

encryption.o(.text$_ZNK10BigIntegermlERKS_[BigInteger::operator*(BigInteger const&) const]+0x63):encryption.cpp: undefined reference to `BigInteger::multiply(BigInteger const&, BigInteger const&)'

所以我想知道处理 RSA 算法产生的真正大整数的最佳方法是什么。

我听说有一种可能是将变量声明为双长整型，所以...

long long decryptedCharacter;

但我不确定可以存储多大的整数。

---

例如，我尝试使用 dev C++ 编译并运行以下程序：

#include iostream

#include "bigint\BigIntegerLibrary.hh"

using namespace std;

int main()
{
    BigInteger a = 65536;
    cout << (a * a * a * a * a * a * a * a);
    return 0;
}

然后我收到这些错误。

Derek，我认为通过包含 BigIntegerLibrary.hh 文件，编译器将遍历并编译它将使用的所有必需文件。

我应该如何尝试编译上面的程序以解决链接错误？

Answer 1

确保 RSA 实施安全的因素不仅仅是大数字。 简单的 RSA 实现往往会通过侧通道泄漏私人信息，尤其是计时（简单来说：计算时间取决于处理的数据，这允许攻击者恢复部分（可能是全部）私钥位）。 好的 RSA 实现可以实施对策。

此外，除了模幂之外，还存在整个填充业务，这在概念上并不困难，但是，与所有 I/O 和解析代码一样，存在出现细微错误的空间。 最容易编写的代码是其他人已经编写过的代码。

另一点是，一旦您的 RSA 代码启动并运行，您可能会开始设想扩展和其他情况，例如“如果我想要使用的私钥不在 RAM 中而是在智能卡中怎么办？”。 一些现有的 RSA 实现实际上是可以处理该问题的 API。 在 Microsoft 世界中，您需要查找 CryptoAPI，它集成在 Windows 中。 您可能还想查看 NSS，这是 Firefox 浏览器的内容用于 SSL。

总而言之：您可以从大整数构建一个符合 RSA 的实现，但这比通常看起来更难正确完成，所以我的建议是使用现有的 RSA 实现。

Answer 2

Openssl 还有一个可以使用的 Bignum 类型。 我用过它并且效果很好。 如果您愿意，可以轻松用 C++ 或 Objective-C 等 oo 语言包装。

https://www.openssl.org/docs/crypto/bn.html

另外，如果您不知道，要找到 x^y % z 形式的方程的答案，请查找称为模幂的算法。 大多数 crypto 或 bignum 库都有专门用于此计算的函数。

Answer 3

long int 通常为 64 位，可能不足以处理那么大的整数。 您可能需要某种 bigint 库。

另请参阅 Stack Overflow 上的此问题

Answer 4

查看您的编译器文档。 有些编译器定义了类型，例如 __int64，可以提供它们的大小。 也许您已经有其中一些可用。

Answer 5

只是要注意： __int64 和 long long 是非标准扩展。 不保证所有 C++ 编译器都支持其中任何一种。 C++是基于C89的（98年就出来了，所以不能基于C99）

（C从C99开始就支持‘long long’）

顺便说一句，我不认为64位整数可以解决这个问题。

Answer 6

我使用 LibTomCrypt 库来满足我的加密需求，取得了很大的成功。 它快速、精简且便携。 它可以为您执行 RSA，或者根据您的需要仅处理数学运算。

Answer 7

事实上，您在使用某些大整数库时遇到问题并不意味着这是一个糟糕的方法。

使用 long long 绝对是一个不好的方法。

正如其他人所说，已经使用 biginteger 库可能是一个好方法，但是您必须发布有关如何使用提到的库的更多详细信息，以便我们能够帮助您解决这些错误。

Answer 8

我在编写 RSA 实现时使用了 GMP。

Answer 9

Tomek，听起来您没有正确链接到 BigInteger 代码。 我认为你应该解决这个问题而不是寻找新的库。 我查看了源代码，BigInteger::BigInteger(int) 是最明确定义的。 粗略一看，其他人也是如此。

您收到的链接错误意味着您要么忽略编译 BigInteger 源，要么在链接时忽略包含生成的目标文件。 请注意，BigInteger 源使用“cc”扩展名而不是“cpp”，因此请确保您也正在编译这些文件。

Answer 10

我建议使用 gmp，它可以处理任意长的整数并且具有良好的 C++ 绑定。

据我所知，当前硬件/软件的 long long 是 64 位，因此 unsigned 可以处理高达 (2**64)-1 == 18446744073709551615 的数字，这比您必须使用 RSA 处理的数字小很多。

Answer 11

要查看 long long 的大小，请尝试以下操作：

#include <stdio.h>

int main(void) {
    printf("%d\n", sizeof(long long));

    return 0;
}

在我的机器上，它返回 8，这意味着 8 个字节可以存储 2^64 个值。

Answer 12

我会尝试 GMP 库 - 它很强大，经过充分测试，并且通常用于此类代码。

Answer 13

对于 RSA，您需要一个 bignum 库。 这些数字太大，无法放入 64 位 long 中。 我曾经有一位大学同事，他接到了实施 RSA 的任务，其中包括构建他自己的 bignum 库。

碰巧的是，Python 有一个 bignum 库。 编写 bignum 处理程序足够小，适合计算机科学作业，但仍然有足够的陷阱使其成为一项不平凡的任务。 他的解决方案是使用 Python 库生成测试数据来验证他的 bignum 库。

您应该能够获得其他 bignum 库。

或者，尝试用 Python 实现原型，看看它是否足够快。

Answer 14

如果您没有将 RSA 作为学校作业或其他内容来实现，那么我建议您查看 crypto++ 库 http:// www.cryptopp.com

加密技术的实现非常容易糟糕。

Answer 15

这是我的方法，它结合了使用平方+模幂的快速求幂，这减少了所需的空间。

long long mod_exp (long long n, long long e, long long mod)
{
  if(e == 1)
  {
       return (n % mod);
  }
  else
  {
      if((e % 2) == 1)
      {
          long long temp = mod_exp(n, (e-1)/2, mod);
          return ((n * temp * temp) % mod);
      }
      else
      {
          long long temp = mod_exp(n, e/2, mod);
          return ((temp*temp) % mod); 
      }
  }
}