КЛАССИФИКАЦИЯ ЭЛЛИПТИЧЕСКИХ КРИВЫХ ИСПОЛЬЗУЕМЫХ В КРИПТОГРАФИИ

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

Эллиптической кривой является набор точек описываемый уравнением Вейерштрассе:

Существует несколько видов эллиптических кривых:

• гладкие эллиптические кривые;
• сингулярные эллиптические кривые;
• суперсингулярные эллиптические кривые.

Гладкие эллиптические кривые отличаются от сингулярных тем что для гладких выполняется следующее неравенство:

Для сингулярных же оно не выполняется.

Суперсингулярные кривые проявляют себя при работе с бинарным конечным полем Галуа.

При использовании кривых над ними приходятся проводить арифметические операции. Основной операцией является сложение двух точек кривой. Сложение точек представлено на рисунке 1.

 Рисунок 1. Сложение точек

Для того чтобы сложить две точки P и Q необходимо провести между ними прямую, пересекающую кривую в третьей точке R, а затем отразить эту точку относительно горизонтальной оси координат. Получившаяся точку и будет являться суммой точек P+Q.

Все эллиптические кривые относятся к кривым над вещественными числами. Для того чтобы не возникало проблем с округлением чисел в криптографии используют кривые над бинарным конечным полем Галуа. Это позволяет определять связь между исходным текстом и зашифрованными данными.

Одним из наиболее важных параметров кривой в криптографии является количество точек над конечным полем(порядок эллиптической кривой).

По теореме Хассе - количество точек кривой, определенной над полем Zq с q элементами тогда справедливо равенство:

А т.к. используется конечное поле Галуа, которое состоит из элементов, можно сказать, что порядок кривой  равен , где .

Суперсингулярной эллиптической кривой является та кривая у которой t без остатка делится на характеристику поля(2).

Точки эллиптической кривой над конечным полем являются группой, для этой группы определена операция сложения. Поэтому можно представить умножение числа k на точку G как G+G+..+G с k слагаемыми.

Допустим, имеется сообщение M представленное в виде целого числа. Его можно зашифровать, используя выражение C=M*G.Возникает вопрос, насколько сложно восстановить M зная параметры кривой E(a,b), шифротекст С и точку G.

Эта задача называется задачей дискретного логарифмирования на эллиптической кривой и не имеет быстрого решения. Наиболее быстрые методы решения данной задачи имеют сложность , где q - количество точек эллиптической кривой над полем. При этом для решения задачи дискретного логарифмирования в конечных полях есть алгоритмы имеющею сложность , где c и d - некоторые константы, а p - размер поля.

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

В итоге все эллиптические кривые можно классифицировать по наличию методов решения задачи дискретного логарифма:

• Безопасные для использования в системах шифрования
• С риском взлома при использовании в системах шифрования

К первым относятся гладкие эллиптические кривые, для которых не существует общего метода решения задачи дискретного логарифма.

Ко вторым относятся сингулярные и суперсингулярные кривые за счет своих специфичных свойств, из-за которых задача решения дискретного логарифма на эллиптической кривой сводится к задаче решения дискретного логарифма в конечном поле.

Плюсы и минусы использования эллиптических кривых

Основные плюсы:

1.Меньшая длинна ключа по сравнению с «классическими» алгоритмами шифрования.

2.Более высокая скорость работы алгоритмов шифрования основанных на эллиптических кривых.

3.Из-за меньшей длинны ключа и более высокой скорости работы алгоритма алгоритмы основанные на эллиптических кривых можно использовать на устройствах с ограниченными вычислительными ресурсами.

Основные минусы:

1.Эллиптическая криптография – это очень сложно для понимания.

2.Основа криптографии на эллиптических кривых вытекает из отсутствия алгоритма решения задачи дискретного логарифмирования на эллиптических кривых, если такой алгоритм появится то произойдет крах всей криптографии на основе эллиптических кривых.

Список литературы:

1.Алгоритмические основы эллиптической криптографии / А.А. Болотов, СБ. Гашков, А.Б. Фролов и др. -М.: МЭИ, 2000. - 100 с.

2.Пылин, В.В. Оценка стойкости эллиптической кривой / В .В.Пылин // Информационные технологии в профессиональной деятельности и научной работе: сборник материалов Всероссийской научно- практической конференции с международным участием. - Йошкар-Ола: Марийский государственный технический университет, 2007. -С.118- 120.

3.Ростовцев, А.Г. Подпись и шифрование на эллиптической кривой: анализ безопасности и безопасная реализация / А.Г. Ростовцев, Е.Б. Маховенко// Проблемы информационной безопасности. Компьютерные системы. - 2003. - №1. - С. 64-73.