C++ 处理非常大的整数
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/124332/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
C++ handling very large integers
提问by
I am using the RSA Algorithm for encryption/decryption, and in order to decrypt the files you have to deal with some pretty big values. More specifically, things like
我使用 RSA 算法进行加密/解密，为了解密文件，您必须处理一些相当大的值。更具体地说，像
P = C^d % n
= 62^65 % 133
Now that is really the only calculations that ill be doing. I have tried using Matt McCutchen's BigInteger Library, but I am getting a lot of compiler errors during linking, such as:
现在这确实是唯一不合适的计算。我曾尝试使用 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&)'
So I was wondering what would be the best way to go about handling the really big integers that come out of the RSA Algorithm.
所以我想知道处理来自 RSA 算法的真正大整数的最佳方法是什么。
I heard that a possibility would be to declare your variables as a double long, so...
我听说有可能将您的变量声明为双长，所以......
long long decryptedCharacter;
but I'm not sure exactly how big of an integer that can store.
但我不确定可以存储的整数到底有多大。
Well for example, I try to compile and run the following program using dev C++:
例如，我尝试使用 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;
}
then I get those errors.
然后我得到这些错误。
Derek, I thought that by including the BigIntegerLibrary.hhfile, that the compiler would go through and compile all the necessary files that it will use.
Derek，我认为通过包含该BigIntegerLibrary.hh文件，编译器将遍历并编译它将使用的所有必要文件。
How should I try and compile the program above in order to resolve the linking errors?
我应该如何尝试编译上面的程序以解决链接错误？
回答by Derek Park
Tomek, it sounds like you aren't linking to the BigInteger code correctly. I think you should resolve this problem rather than looking for a new library. I took a look at the source, and BigInteger::BigInteger(int)is most definitely defined. A brief glance indicates that the others are as well.
Tomek，听起来您没有正确链接到 BigInteger 代码。我认为你应该解决这个问题而不是寻找一个新的图书馆。我查看了源代码，并且BigInteger::BigInteger(int)非常明确地定义了。简短的一瞥表明其他人也是如此。
The link errors you're getting imply that you are either neglecting to compile the BigInteger source, or neglecting to include the resulting object files when you link. Please note that the BigInteger source uses the "cc" extension rather than "cpp", so make sure you are compiling these files as well.
您收到的链接错误意味着您要么忽略了编译 BigInteger 源代码，要么在链接时忽略了包含生成的目标文件。请注意，BigInteger 源使用“cc”扩展名而不是“cpp”，因此请确保您也在编译这些文件。
回答by TFKyle
I'd suggest using gmp, it can handle arbitrarily long ints and has decent C++ bindings.
我建议使用gmp，它可以处理任意长的整数并且具有不错的 C++ 绑定。
afaik on current hardware/sofware long longs are 64bit, so unsigned can handle numbers up to (2**64)-1 == 18446744073709551615 which is quite a bit smaller than numbers you'd have to deal with with RSA.
当前硬件/软件上的 afaik 长整数是 64 位，因此 unsigned 可以处理高达 (2**64)-1 == 18446744073709551615 的数字，这比您必须处理 RSA 的数字小得多。
回答by ConcernedOfTunbridgeWells
For RSA you need a bignum library. The numbers are way too big to fit into a 64-bit long long. I once had a colleague at university who got an assignment to implement RSA including building his own bignum library.
对于 RSA，您需要一个 bignum 库。这些数字太大而无法放入 64 位 long long。我曾经有一位大学同事，他接到了一项实施 RSA 的任务，包括构建他自己的 bignum 库。
As it happens, Python has a bignum library. Writing bignum handlers is small enough to fit into a computer science assignment, but still has enough gotchas to make it a non-trivial task. His solution was to use the Python library to generate test data to validate his bignum library.
碰巧的是，Python 有一个 bignum 库。编写 bignum 处理程序足够小以适应计算机科学作业，但仍然有足够的陷阱使其成为一项重要的任务。他的解决方案是使用 Python 库生成测试数据来验证他的 bignum 库。
You should be able to get other bignum libraries.
您应该能够获得其他 bignum 库。
Alternatively, try implementing a prototype in Python and see if it's fast enough.
或者，尝试在 Python 中实现一个原型，看看它是否足够快。
回答by tfinniga
If you're not implementing RSA as a school assignment or something, then I'd suggest looking at the crypto++ library http://www.cryptopp.com
如果您没有将 RSA 实施为学校作业或其他内容，那么我建议您查看 crypto++ 库http://www.cryptopp.com
It's just so easy to implement crypto stuff badly.
糟糕地实施加密货币太容易了。
回答by Jeremy Ruten
To see the size of a long long try this:
要查看 long long 的大小，请尝试以下操作：
#include <stdio.h>
int main(void) {
printf("%d\n", sizeof(long long));
return 0;
}
On my machine it returns 8 which means 8 bytes which can store 2^64 values.
在我的机器上，它返回 8，这意味着 8 个字节可以存储 2^64 个值。
回答by Vlad
Here is my approach, it combines fast exponentation using squaring + modular exponentation which reduces the space required.
这是我的方法，它结合了使用平方 + 模幂的快速幂运算，从而减少了所需的空间。
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);
}
}
}
回答by Thomas Pornin
There is more to secure RSA implementation than just big numbers. A simple RSA implementation tends to leak private information through side channels, especially timing (in simple words: computation time depends on the processed data, which allows an attacker to recover some, possibly all, of the private key bits). Good RSA implementations implement countermeasures.
保护 RSA 实施的不仅仅是大数字。一个简单的 RSA 实现往往会通过侧信道泄漏私人信息，尤其是时间（简单来说：计算时间取决于处理的数据，这允许攻击者恢复部分，可能是全部的私钥位）。好的 RSA 实现会实施对策。
Also, beyond the modular exponentiation, there is the whole padding business, which is not conceptually hard, but, as all I/O and parsing code, has room for subtle bugs. The easiest code to write is the code which has already been written by somebody else.
此外，除了模幂之外，还有整个填充业务，这在概念上并不难，但是，作为所有 I/O 和解析代码，存在细微错误的空间。最容易编写的代码是其他人已经编写的代码。
Another point is that once you have your RSA code up and running, you may begin to envision extensions and other situations, e.g. "what if the private key I want to use is not in RAM but in a smartcard ?". Some existing RSA implementations are actually API which can handle that. In the Microsoft world, you want to lookup CryptoAPI, which is integrated in Windows. You may also want to look at NSS, which is what the Firefox browser uses for SSL.
另一点是，一旦您的 RSA 代码启动并运行，您可能会开始设想扩展和其他情况，例如“如果我想要使用的私钥不在 RAM 中，而是在智能卡中怎么办？”。一些现有的 RSA 实现实际上是可以处理的 API。在 Microsoft 世界中，您想查找CryptoAPI，它集成在 Windows 中。您可能还想查看NSS，它是 Firefox 浏览器用于 SSL 的内容。
To sum up: you canbuild up a RSA-compliant implementation from big integers, but this is more difficult to do correctly than what it usually seems, so my advice is to use an existing RSA implementation.
总而言之：您可以从大整数构建符合 RSA 的实现，但这比通常看起来更难正确执行，因此我的建议是使用现有的 RSA 实现。
回答by robottobor
Openssl also has a Bignumtype you can use. I've used it and it works well. Easy to wrap in an oo language like C++ or objective-C, if you want.
Openssl 还有一个Bignum类型你可以使用。我已经使用过它并且效果很好。如果需要，可以轻松地使用 C++ 或 Objective-C 之类的 oo 语言进行包装。
https://www.openssl.org/docs/crypto/bn.html
https://www.openssl.org/docs/crypto/bn.html
Also, in case you didn't know, to find the answer to the equation of this form x^y % z, look up an algorithm called modular exponentiation. Most crypto or bignum libraries will have a function specifically for this computation.
此外，如果您不知道，要找到 x^y % z 形式的方程的答案，请查找称为模幂运算的算法。大多数加密或 bignum 库都有专门用于此计算的函数。
回答by Greg Hewgill
回答by Scott Langham
Check out your compiler documentation. Some compilers have types defined such as __int64 that give you their size. Maybe you've got some of them available.
查看您的编译器文档。一些编译器定义了诸如 __int64 之类的类型，这些类型为您提供了它们的大小。也许你有一些可用的。
