Discrete logarithm brute force: Can someone explain me the runtime differences between C++ and C++ with NTL?

Question

This is more a runtime and/or time-complexity question than a cryptography problem, so please continue reading:

in university we have to implement a brute-force discrete logarithm algorithm to find the secrets in a diffie hellman exchange and I started to implement it with C++ and the NTL library so I wouldn't have to worry about datatypes and large primes.

My example numbers are the following with a 25 bit prime and we want to find the discrete logarithm:

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

I implemented the following in C++ with 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;
}

output (7.581s):

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

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

-> time: 7.581s

Well, I thought that's really long, so I tested it without NTL and normal long's in C++ -> imagine all ZZ replaced by long (0.124s):

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

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

-> time: 0.124s

Can someone please explain me why the NTL is that much slower? Please keep in mind that I am no expert in this field and just trying to figure out cryptography basics and how to implement those in easy examples.

Thank you!

Answer 1

In general. NTL is a powerful and well-written library for long-integer and other crypto-related arithmetic, but it obviously cannot beat the efficiency of builtin types for small numbers. Notice that when using long type, all the operations translate to single cpu instructions. It is as fast as it can get but is limited to 32/64 bits.

On the other hand, ZZ is a full-blown class that needs to manage its memory and is able to operate on arbitrary-length integers. This comes at a price.

Possible optimizations. Having said that, you can try and optimize things a bit taking into account the fact that ZZ is a class, so it may make sense to e.g. avoid creation of unnecessary temporary objects.

For example, consider the line

x = x * g;

it calls operator* on two objects and assigns the new value to x again. Looking at the implementation of it, we see:

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

so a new temporary object is created and returned. I think it would be more efficient to call

x *= g

since the implementation of operator*= avoids the temporary creation

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

Using ZZ_p. Another thing to consider is that you are essentially doing arithmetic in Z_p (i.e. in Z modulo p), so probably you would like to use class ZZ_p that performs the reduction automatically when necessary.

Using NTL with GMP If you care about the performance of (long) arithmetic a good idea is to build NTL so that it uses GMP for the underlying long arithmetic. This gives somehow better performance than plain NTL.