Авторы: ,

Рубрика: Информатика

Опубликовано в Молодой учёный №3 (137) январь 2017 г.

Дата публикации: 19.01.2017

Статья просмотрена: 139 раз

Библиографическое описание:

Тырыгина Г. А., Хайбуллин Р. Р. Выбор эффективного метода подбора эллиптической кривой для реализации на ней криптографической системы // Молодой ученый. — 2017. — №3. — С. 53-56. — URL https://moluch.ru/archive/137/37310/ (дата обращения: 19.04.2018).



Ключевые слова: криптографические методы защиты информации, электронно-цифровая подпись, эллиптическая криптография, эллиптические кривые, конечные поля, порядок эллиптической кривой, точки эллиптической кривой, арифметические операции над точками эллиптической кривой

Введение

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

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

Стоит отметить, что существует вероятность того, что в будущем решение такой задачи может быть получено за полиномиальное время.

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

Целью научного исследования является поиск оптимальной эллиптической кривой, для реализации на ней эллиптической криптосистемы.

Объект исследования — эллиптические криптосистемы.

Предмет исследования — эллиптическая кривая над полем вычетов большого простого числа для построения на ней модели эллиптической криптосистемы.

Задачи, выполняемые в ходе исследования:

1.Определить основные особенности в вопросах подбора эллиптических кривых.

2.Определиться с методикой подбора эллиптических кривых.

2.Подобрать эллиптическую кривую для построения на ней, в будущем, модели криптосистемы.

Криптосистема, построенная на эллиптической кривой

Логичным является утверждение, что эллиптическая криптосистема должна строится на эллиптической кривой. А их существует великое множество. Общий вид эллиптических кривых следующий (1):

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

Важно, чтобы эллиптическая кривая, на которой будет строиться криптосистема, не оказалась сингулярной, суперсингулярной или аномальной, так как в противном случае, использование таких кривых в криптосистеме приведет к тому, что она окажется не крипто-стойкой. Это связано с тем, что особые свойства таких кривых позволяют свести задачу дискретного логарифма на эллиптической кривой, к задаче дискретного логарифма в конечном поле. И в отличие от кривых, не являющихся сингулярными и аномальными, для такого класса кривых, стандартные ключи размером 20–40 байт будут уязвимы к атакам, что позволит злоумышленникам заполучить ключ за небольшое количество времени.

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

Согласно вышесказанному, следующим вопросом, берущимся во внимание, при поиске эллиптической кривой, является вопрос о количестве точек этой кривой, или же по-другому, вопрос о ее порядке.

Задача поиска эллиптической кривой с определенным количеством точек является достаточно нетривиальной.

Существует несколько способов решения такой задачи. Рассмотрим некоторые из них:

‒ метод комплексного умножения;

‒ алгоритм Шуфа.

Метод комплексного умножения хоть и позволяет достаточно эффективно искать эллиптические кривые с необходимым количеством точек, все же, в отличие от алгоритма Шуфа, не является универсальным.

В свою очередь, алгоритм Шуфа имеет достаточно большую вычислительную сложность (2), и, к тому же, заключает в себе довольно сложный математический аппарат.

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

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

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

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

Литература:

  1. Анин, Б. Р. О шифровании и дешифровании / Б. Р. Анин // Конфидент. — 1997. — № 1. — С. 71–79.
  2. Аснис, И. Л. Краткий обзор криптосистем с открытым ключом / И. Л. Аснис, С. В. Федоренко, К. Б. Шабунов // Защита информации. — 1994. — № 2. — С. 35–43.
  3. Биркгоф, Г. Современная прикладная алгебра: Пер. с англ./ Г. Биркгоф, Т. Барти. — М. Мир, 1976. — 400 с.
  4. Болотов А. Е. Элементарное введение в эллиптическую криптографию: Протоколы криптографии на эллиптических кривых / А. Е. Болотов, С. Б. Гашков, А. Б. Фролов — М.: КомКнига, 2006. — 280 с.
  5. Гайкович, В. Компьютерная безопасность: заметки о текущем состоянии дел / В. Гайкович // Банковские технологии. — 1997.- Июнь. — С.56–58.
  6. Галатенко, В. А. Основы информационной безопасности: учебное пособие / В. А. Галатенко; под ред. академика РАН В. Б. Бетелина, — 4-е изд. — М.: Интернет-Университет Информационных технолгий; БИНОМ. Лаборатория знаний, 2008. — 205 с.
  7. Гольев Ю. И., Ларин Д. А., Тришин А. Е., Шанкин Г. П. Криптография: страницы истории тайных операций. М.: Гелиос АРВ, 2008, 288с.
  8. Куприянов А. И., Сахаров А. В., Шевцов В. А. Основы защиты информации. Академия, 2008.-256 с.
  9. Оценка безопасности информационных технологий / А. П. Трубачев, И. А. Семичев, В. Н. Шакунов и др. — М.: СИП РИА, 2001. — 388 с.
  10. Романец Ю. В., Тимофеев П. А., Шаньгин В. Ф., «Защита информации в компьютерных системах и сетях / Под ред. В. Ф. Шаньгина. — 2-е изд., перераб. И доп. — М.: радио и связь, 2001 г.
  11. Ростовцев А. Г. Теоретическая криптография / А. Г. Ростовцев, Е. Б. Маховенко — Санкт-Петербург.: НПО «Профессионал», 2004. — 479 с.
  12. Рябко Б. Я. Криптографические методы защиты информации: Учебное пособие для вузов / Б. Я. Рябко, А. Н. Фионов — М.: Горячая линия — Телеком, 2011. — 229 с.
  13. Фостер Джеймс С. Создание защищенных от вторжения прикладных программ. ДМК пресс, 2009. -784с.
  14. Ященко, В. В. Введение в криптографию / Под общей ред. В. В. Ященко. — СПб.: Питер, 2001. — 288 с.
Основные термины (генерируются автоматически): эллиптической кривой, эллиптических кривых, подбора эллиптической кривой, модулю большого числа, подбора эллиптических кривых, точками эллиптической кривой, эллиптической криптосистемы, порядок эллиптической кривой, точки эллиптической кривой, оптимальной эллиптической кривой, выбора эллиптической кривой, поиске эллиптической кривой, поиска эллиптической кривой, количеством точек, метода подбора эллиптической, модели эллиптической криптосистемы, способа подбора эллиптической, эллиптических кривых следующий, использование эллиптических кривых, качестве критерия эффективности.

Ключевые слова

криптографические методы защиты информации, электронно-цифровая подпись, эллиптическая криптография, эллиптические кривые, конечные поля, порядок эллиптической кривой, точки эллиптической кривой, арифметические операции над точками эллиптической кривой

Обсуждение

Социальные комментарии Cackle
Задать вопрос