c++ - C++ 处理非常大的整数

Question

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

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

现在，这确实是唯一不合适的计算。我曾尝试使用 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文件，编译器将遍历并编译它将使用的所有必要文件。

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

score 13 · Accepted Answer

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

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

score 12 · Accepted Answer

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

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

score 3 · Accepted Answer

如果您没有将 RSA 用作学校作业或其他东西，那么我建议您查看 crypto++ 库http://www.cryptopp.com

糟糕地实施加密货币非常容易。

score 3 · Accepted Answer

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

#include <stdio.h>

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

    return 0;
}

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

score 3 · Accepted Answer

对于 RSA，您需要一个 bignum 库。这些数字太大了，无法容纳 64 位长。我曾经有一个大学同事，他得到了一个实施 RSA 的任务，包括建立他自己的 bignum 库。

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

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

或者，尝试在 Python 中实现一个原型，看看它是否足够快。

score 3 · Accepted Answer

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

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); 
      }
  }
}

score 3 · Accepted Answer

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

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

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

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

score 2 · Accepted Answer

Openssl 也有一个可以使用的Bignum类型。我已经使用它并且效果很好。如果需要，可以很容易地用 C++ 或 Objective-C 等 oo 语言进行封装。

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

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

score 2 · Accepted Answer

我会试用GMP库——它很健壮，经过良好测试，并且通常用于这种类型的代码。

score 1 · Accepted Answer

我在使用LibTomCrypt库来满足我的加密需求方面取得了很大的成功。它快速、精简且便携。它可以为你做你的 RSA，或者如果你想只处理数学。

score 1 · Accepted Answer

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

另请参阅Stack Overflow 上的这个问题

score 1 · Accepted Answer

查看您的编译器文档。一些编译器定义了诸如 __int64 之类的类型，这些类型为您提供了它们的大小。也许你有一些可用的。

score 1 · Accepted Answer

请注意：__int64 和 long long 是非标准扩展。不能保证所有 C++ 编译器都支持这两者。C++是基于C89的（98年出来的，所以不能基于C99）

（从 C99 开始，C 就支持 'long long'）

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

score 0 · Accepted Answer

事实上，您在使用某些 biginteger 库时遇到问题并不意味着这是一种不好的方法。

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

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

score 0 · Accepted Answer

0

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

于 2009-05-18T19:26:45.103 回答

c++ - C++ 处理非常大的整数

15 回答 15

Related

Reference