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文件,编译器会经历并编译它将使用的所有必要文件.

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

Answer 1

元回答:

如果您正在使用bigint算法的库,那么问问自己为什么不使用库来实现整个RSA.

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

但是,他们没有与http://mattmccutchen.net/bigint/相同的许可证,这在我看来已经被置于美国的公共领域.

Answer 2

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

您所暗示的链接错误意味着您要么忽略编译BigInteger源,要么忽略在链接时包含生成的对象文件.请注意,BigInteger源使用"cc"扩展名而不是"cpp",因此请确保您也在编译这些文件.

Answer 3

我建议使用gmp,它可以处理任意长的int并具有不错的C++绑定.

当前硬件/软件上的afaik长多为64位,因此无符号可以处理最多(2**64)-1 == 18446744073709551615的数字,这比你必须处理RSA的数字要小得多.

Answer 4

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

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