我正在使用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算法产生的真正大整数的最佳方法。

我听说可能是将变量声明为double long，所以...

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文件，编译器可以检查并编译将使用的所有必需文件。

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

解决方案

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

另请参阅堆栈溢出问题

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

#include <stdio.h>

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

    return 0;
}

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

查看编译器文档。某些编译器具有定义的类型，例如__int64，可以为我们提供它们的大小。也许我们有一些可用的。

请注意：__int64和long long是非标准扩展名。不能保证所有C ++编译器都支持。 C ++基于C89(它于98年问世，因此不能基于C99)

(自C99以来，C支持" long long")

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

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

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

当前硬件/软件中的afaik long longs是64位，因此unsigned可以处理的数字最大为(2 ** 64)-1 == 18446744073709551615，这比我们必须处理RSA的数字小很多。

对于RSA，我们需要一个bignum库。这些数字太大，无法容纳64位长的数字。我曾经在大学里有一位同事，他被派去实施RSA，包括建立自己的bignum库。

碰巧的是，Python有一个bignum库。编写bignum处理程序的大小足以适应计算机科学的任务，但仍然有很多难题，使其成为一项艰巨的任务。他的解决方案是使用Python库生成测试数据以验证他的bignum库。

我们应该能够获得其他bignum库。

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

实际上，使用某些biginteger库存在问题并不意味着这是一种不好的方法。

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

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

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

我们得到的链接错误暗示我们或者在编译时忽略了BigInteger源，或者在链接时忽略了包含生成的目标文件。请注意，BigInteger源使用" cc"扩展名而不是" cpp"，因此请确保我们也正在编译这些文件。

元答案：

如果我们将库用于bigint运算，请问自己为什么不对整个RSA实现使用库。

例如，http://www.gnu.org/software/gnu-crypto/包含RSA实现。它具有与GMP相同的许可证。

但是，它们与http://mattmccutchen.net/bigint/的许可证不同，在我看来，这已经被放置在美国的公共领域中。

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

糟糕地实现加密东西是如此容易。

使用LibTomCrypt库满足我的加密需求，我取得了很多成功。快速，轻巧和便携式。它可以为我们执行RSA，或者根据需要处理数学。

Openssl还具有可以使用的Bignum类型。我已经用过了，效果很好。如果需要，可以很容易地包装到C ++或者Objective-C之类的oo语言中。

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

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

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

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

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

确保RSA实施安全的不仅仅是数量庞大。一个简单的RSA实现往往会通过侧通道(尤其是定时)泄漏私有信息(简单地说：计算时间取决于处理后的数据，这使攻击者可以恢复某些(可能是全部)私有密钥位)。良好的RSA实施可实施对策。

此外，除了模块化的求幂运算之外，还有整个填充业务，这在概念上并不难，但是，由于所有I / O和解析代码，都有一些细微的bug的余地。最容易编写的代码是已经由其他人编写的代码。

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

综上所述：我们可以从大整数中构建RSA兼容的实现，但这比通常看起来要困难得多，因此我的建议是使用现有的RSA实现。