криптография — дискретный логарифм грубой силы: может кто-нибудь объяснить мне различия во времени выполнения между C ++ и C ++ с NTL?
Это больше вопрос времени выполнения и / или сложности времени, чем проблемы криптографии, поэтому, пожалуйста, продолжайте читать:
в университете мы должны реализовать алгоритм дискретного логарифма методом грубой силы, чтобы найти секреты в обмене 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,581 с):
p = 20084173
g = 2
t = 7709318
secret: = 557254
p = 20084173
g = 2
t = 6676335
secret: = 8949383
-> time: 7.581s
Ну, я думал, что это действительно долго, поэтому я проверил это без NTL и нормальных длинных в C ++ -> представьте, что все ZZ заменены на длинные (0,124 с):
p = 20084173
g = 2
t = 7709318
Secret: = 557254
p = 20084173
g = 2
t = 6676335
Secret: = 8949383
-> time: 0.124s
Может кто-нибудь объяснить мне, почему NTL намного медленнее? Пожалуйста, имейте в виду, что я не эксперт в этой области и просто пытаюсь понять основы криптографии и как реализовать их в простых примерах.
Спасибо!
Решение
В общем. NTL — это мощная и хорошо написанная библиотека для длинно-целочисленной и другой криптографической арифметики, но она явно не может сравниться с эффективностью встроенных типов для небольших чисел.
Обратите внимание, что при использовании длинного типа все операции переводятся в инструкции с одним процессором. Это так быстро, как может, но ограничено 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.
Другие решения