Методы факторизации натуральных чисел. Ишмухаметов Ш.Т. - 94 стр.

Глава 3. Эллиптические кривые                                         95

хотя обеспечивает большой практический прирост скорости сходимости
алгоритма.
         Если сравнивать метод эллиптических кривых с другими методами
факторизации, то метод Ленстры относится к классу субэкспоненциальных
методов факторизации, а, значит, работает быстрее любого метода,
упомянутого во второй главе.
         Если сравнивать его с методом квадратичного решета QS и методом
решета числового поля NFS, то все зависит от размера наименьшего делителя
числа n. Если число n выбрано по методу RSA как произведение двух
простых чисел примерно одинаковой длины, то метод ЕК имеет ту же оценку,
что и метод квадратичного решета, но уступает методу решета числового
поля.
         Однако если   n   имеет размерность, превышающую рекордные
показателя для методов QS и NFS, (напомним, что последнее рекордное
разложение чисел RSA с использованием NFS относится к числу длины 768
бит), то единственная надежда найти делитель n может выполнена только
с помощью метода эллиптических кривых.


3.4. Криптографические протоколы на эллиптических
         кривых
          Рассмотрим    наиболее   известные   варианты    использования
эллиптических кривых в криптографии.

Протокол Диффи-Хелмана

Протокол Диффи-Хельмана используется для генерации двумя удаленными
абонентами общего секретного ключа в условиях незащищенного канала
связи.
         Сначала выбирается простое число р ≈ 2160 и параметры a и b
эллиптической кривой. Этим задается множество точек ЭК Ep (a, b). Затем
на Ep (a, b) выбирается генерирующая точка G = (x1 , y1 ). При выборе G
важно, чтобы наименьшее значение n, при котором nG = 0, оказалось