Умножение точек.

Для успешного применения в криптографии необходимо уметь достаточно быстро вычислять при известных и . Наиболее эффективный метод вычисления основан на представлении числа в двоичной системе счисления (подобный метод мы использовали при вычислении в кольце ).

Разложим число по степеням двойки: . Последовательно вычисляем для – степеней двойки: В результате мы найдем , выполнив не более операций суммирования:

В общем для вычисления требуется выполнить не более операций сложения на

Пример.Вычислим на кривой , если

Запишем в виде разложения по степеням двойки: Последовательно находим:

Поэтому

Если выбрать случайные числа и на отрезке и составить два списка:

то если удается найти и такие, что , то число является решением задачи дискретного логарифмирования . Из теории вероятностей известно (см. [2]), что если взять , то вероятность найти и , удовлетворяющие соотношению , близка к единице.

Наиболее быстрый из известных в настоящее время алгоритмов решает задачу ECDLP примерно за шагов.

Большинство криптосистем современной криптографии естественным образом «перекладывается» на эллиптические кривые. Сложность криптосистемы, получаемых в результате такой «модификации», базируется на сложности решения задачи дискретного логарифмирования. Основное преимущество эллиптической криптографии заключается в том, что, как уже говорилось выше, на сегодняшний день неизвестны эффективные алгоритмы для решения задачи дискретного логарифмирования в группах точек эллиптических кривых. Кроме того, считается, в эллиптических криптосистемах можно использовать ключи меньших длин, чем в классических системах с открытым ключом, для обеспечения эквивалентной защиты.