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

                                                                       80

5. Эллиптические кривые и их приложения в
    криптографии
      Хотя эллиптические кривые (Elliptic Curves) исследовались на
протяжении более сотни лет, интерес к ним проявляли исключительно узкие
специалисты в области теории чисел. Так было примерно до 1985 г., пока
одновременно и независимо Н. Коблиц (N. Coblitz) и В. Миллер (V. Miller)
не предложили использовать эллиптические кривые для построения
криптосистем с открытым ключом.
      После этого интерес к эллиптических кривых стал расти в
геометрической прогрессии. Были найдены приложения инструмента
ЭК в разных областях криптографии таких, как теория кодирования,
генерация псевдослучайных последовательностей, алгоритмическая теория
чисел для построения тестов на простоту и, наконец, для создания одного из
самых красивых методов факторизации целых чисел (Х. Ленстра [24]).
      Метод    факторизации     Ленстры    можно     рассматривать    как
модификацию (p − 1)–метода Полларда (см.разд 3.2). Он является самым
быстрым среди всех методов, упомянутых ранее. Как и (p − 1)–метод
Полларда, сложность этого метода определяется величиной не самого числа
n, а величиной его наименьшего делителя, поэтому, даже если число n
очень велико и недоступно другим алгоритмам, оно может быть проверено
с помощью метода факторизации эллиптических МФЭК. Подобно (p − 1)–
методу Полларда (см.разд. 3.2), МФЭК состоит из двух стадий. Первая
стадия алгоритма была разработана самим Ленстрой и имеет единственный
вариант. Вторая стадия имеет несколько вариаций. Одна из них, основанная
на парадоксе близнецов, была предложена Брентом. [9].
      В этой главе мы рассмотрим основные свойства эллиптических кривых
и их приложения в теории чисел и криптографии. Среди литературы на
русском языке, относящейся к теме эллиптический кривых отметим, в
первую очередь, книгу Н. Коблица «Курс теории чисел и криптографии»
[49] и две книги А. Болотова, С. Гашкова, А. Фролова и А. Часовских
под названием «Элементарное введение в эллиптическую криптографию»