2

我必须将一些加密代码从我不太熟悉的 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 库，或者知道我计算它的更快方法吗？

谢谢！

4

2 回答 2

2

可以使用“平方和乘法”算法有效地评估 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 章开始，可从该站点免费下载。然而，在这个对预算的平凡考虑经常限制创造力和空闲时间的严酷世界中，您可能会对已经实施的库感到满意。众所周知，GMP 非常好，但在 Windows 上使用起来有些困难。使用NTL可能会有更好的运气。

于 2010-03-04T22:48:09.197 回答
0

要在 Windows 上生成随机数据，您还可以使用 CryptoAPI，特别是CryptGenRandom方法。

于 2010-03-04T05:52:48.823 回答