c++ - Visual C++ BigInt 和 SecureRandom？是否有带有 modPow 的 BigInt 库？

Question

我必须将一些加密代码从我不太熟悉的 java (visual c++) 移植到 visual c++。我在 http://sourceforge.net/projects/cpp-bigint/ 找到了一个图书馆我可以用于大整数。

但是它没有等效于 javas SecureRandom 类。我确实在 c++ 中找到了一个名为 beecrypt 的项目，但无法使其与 Visual Studio 2008 一起使用。

有人对这些类型的库有任何经验吗？我也看到了 gmp，但找不到可以立即与 visual studio 一起使用的。

在我走错路之前有什么建议吗？

谢谢!

----更新--------

我似乎有一个使用上面的 cpp-bigint 的小数字的概念证明。库中没有 modPow 函数。现在我创建了一个 for 循环，例如:

for(RossiBigInt i("0",DEC_DIGIT); i< r; i++)

{ x = x * g; x = x % p;

这给了我 x = g^r mod p 但它很慢。有谁知道其他具有 modPow 函数的 BitInteger 库或知道我计算这个的更快方法吗？

谢谢!

Answer 1

可以使用“平方和乘法”算法有效地评估 modPow 函数。在 Java 中它看起来像这样(如果 Java 的 BigInteger 还没有它的话):

/* Compute x^n mod m. */
static BigInteger modPow(BigInteger x, BigInteger n, BigInteger m)
{
    if (n.signum() < 0)
        throw new IllegalArgumentException("bwah, negative exponent");
    BigInteger r = BigInteger.ONE;
    for (int i = n.bitLength() - 1; i >= 0; i --) {
        if (n.testBit(i))
            r = r.multiply(x).mod(m);
        if (i > 0)
            r = r.multiply(r).mod(m);
    }
    return r;
}

由此，循环迭代的次数等于指数的长度(以位为单位)，因此计算时间是可以接受的。

每次迭代您仍然会得到一到两个模约简，因此这不会是有史以来最快的求幂算法(模约简比乘法要昂贵得多)。典型的 modPow() 实现使用蒙哥马利归约，这是一个巧妙的技巧，它在最后将所有模块化归约合并为一个类似的操作。

如果您有时间，实现您自己的模幂运算将非常具有教学意义；您将从阅读“应用密码学手册”的第 14 章开始，该手册可从 this site 免费下载。 .然而，在这个对预算的世俗考虑常常限制创造力和空闲时间的严酷世界中，您可能会对已经实现的库感到满意。众所周知，GMP 非常好，但在 Windows 上使用起来有些困难。 NTL 你可能会好运.