0

这更像是一个运行时和/或时间复杂性问题，而不是密码学问题，所以请继续阅读：

在大学里，我们必须实现一个蛮力离散对数算法来在一个 diffie hellman 交换中找到秘密，我开始用 C++ 和 NTL 库来实现它，所以我不必担心数据类型和大素数。

我的示例数字如下，带有 25 位素数，我们想要找到离散对数：

p = 20084173;  /* the prime */
g = 2;         /* the generator */
a = 7709318;   /* the logarithm of a */
b = 6676335;   /* the logarithm of b */

我在C++ 中使用 NTL实现了以下内容：

int main() {

    ZZ p, g, a, b;

    // 25 Bit
    p = 20084173;
    g = 2;
    a = 7709318;
    b = 6676335;

    exhaustiveSearch(p, g, a);
    exhaustiveSearch(p, g, b);

    return 0;
}

ZZ exhaustiveSearch(ZZ p, ZZ g, ZZ t) {
    ZZ i, x;
    i = 0;
    x = 1;
    while ((x = (x % p)) != t) {
        i++;
        x = x * g;
    }
    cout << endl << endl << "p = " << p << endl << "g = " << g << endl << "t = " << t << endl << "secret: = " << i << endl;
    return i;
}

输出（7.581s）：

p = 20084173
g = 2
t = 7709318
secret: = 557254

p = 20084173
g = 2
t = 6676335
secret: = 8949383

-> time: 7.581s

好吧，我认为这真的很长，所以我在没有 NTL 和 C++ 中的普通 long 的情况下对其进行了测试 -> 想象所有 ZZ 都被 long (0.124s) 取代：

p = 20084173
g = 2
t = 7709318
Secret: = 557254

p = 20084173
g = 2
t = 6676335
Secret: = 8949383

-> time: 0.124s

有人可以解释一下为什么 NTL 慢得多吗？请记住，我不是该领域的专家，我只是想弄清楚密码学基础知识以及如何在简单的示例中实现这些基础知识。

谢谢！

4

1 回答 1

1

一般来说。NTL 是一个功能强大且编写良好的库，用于长整数和其他与密码相关的算术，但它显然无法击败小数的内置类型的效率。请注意，当使用 long 类型时，所有操作都转换为单个 cpu 指令。它尽可能快，但仅限于 32/64 位。

另一方面，ZZ 是一个成熟的类，需要管理其内存并且能够对任意长度的整数进行操作。这是有代价的。

可能的优化。话虽如此，考虑到 ZZ 是一个类这一事实，您可以尝试对事物进行一些优化，因此避免创建不必要的临时对象可能是有意义的。

例如，考虑这条线

x = x * g;

它调用operator*两个对象并再次将新值分配给 x。查看它的实现，我们看到：

inline ZZ operator*(const ZZ& a, const ZZ& b)
      { ZZ x; mul(x, a, b); NTL_OPT_RETURN(ZZ, x); }

因此创建并返回了一个新的临时对象。我认为打电话会更有效率

x *= g

由于实施operator*=避免了临时创建

inline ZZ& operator*=(ZZ& x, const ZZ& a)
  { mul(x, x, a); return x; }

使用 ZZ_p。要考虑的另一件事是，您实际上是在 Z_p 中进行算术运算（即以 Z 为模 p），因此您可能希望使用 ZZ_p 类在必要时自动执行归约。

将 NTL 与 GMP 结合使用 如果您关心（长）算术的性能，一个好主意是构建 NTL，以便它将 GMP 用于底层长算术。这提供了比普通 NTL 更好的性能。

于 2014-06-06T13:34:55.687 回答