Выбор эффективного метода подбора эллиптической кривой для реализации на ней криптографической системы | Статья в журнале «Молодой ученый»

Авторы: ,

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

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

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

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

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

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


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

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

Похожие статьи

Эллиптические кривые в алгоритме Диффи - Хеллмана над...

Основные термины (генерируются автоматически): кривой, дискретный логарифм, целое число, операция сложения, образ операцией, пользователь

Ключевые слова. эллиптические кривые, Криптосистема Диффи–Хеллмана, абелева группа, суперсингулярная кривая.

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

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

2. Бессалов А.В., Телиженко А.Б. Криптосистемы на эллиптических кривых : Учеб. пособие.

Особенности оценки качества и оптимизации алгоритмов...

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

Разработка эффективной реализации алгоритмов выполнения...

Ключевая слова: криптосистема на точках эллиптической кривой, система остаточных классов, модульное сложение, приближенный

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

Оценка стойкости криптосистемы Эль-Гамаля

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

Пост-квантовый алгоритм электронно-цифровой подписи на...

Например, алгоритм ЭЦП ECDSA использует проблему вычисления дискретного логарифма в группе точек эллиптической кривой, а

Будем использовать в качестве односторонней ЭЦП алгоритм Винтерница.

Способ хранения закрытого ключа криптосистемы цифровой подписи.

Анализ псевдослучайных последовательностей на эллиптической...

Эллиптическая кривая широко используется для построения криптосистем [].

Критерий 1. Двучлен будет образующим элементом в , только если - образующий элемент в .

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

Обзор видов атак по побочным каналам на криптографические...

На данный момент Лаборатория RSA рекомендует использовать для обычных задач ключи размером 1024 бита, а для особо важных — 2048 бит.

Оптимальным вариантом может стать криптосистема на эллиптических кривых (ЭК).

Эллиптические кривые в алгоритме Диффи - Хеллмана над...

Основные термины (генерируются автоматически): кривой, дискретный логарифм, целое число, операция сложения, образ операцией, пользователь

Ключевые слова. эллиптические кривые, Криптосистема Диффи–Хеллмана, абелева группа, суперсингулярная кривая.

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

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

2. Бессалов А.В., Телиженко А.Б. Криптосистемы на эллиптических кривых : Учеб. пособие.

Особенности оценки качества и оптимизации алгоритмов...

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

Разработка эффективной реализации алгоритмов выполнения...

Ключевая слова: криптосистема на точках эллиптической кривой, система остаточных классов, модульное сложение, приближенный

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

Оценка стойкости криптосистемы Эль-Гамаля

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

Пост-квантовый алгоритм электронно-цифровой подписи на...

Например, алгоритм ЭЦП ECDSA использует проблему вычисления дискретного логарифма в группе точек эллиптической кривой, а

Будем использовать в качестве односторонней ЭЦП алгоритм Винтерница.

Способ хранения закрытого ключа криптосистемы цифровой подписи.

Анализ псевдослучайных последовательностей на эллиптической...

Эллиптическая кривая широко используется для построения криптосистем [].

Критерий 1. Двучлен будет образующим элементом в , только если - образующий элемент в .

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

Обзор видов атак по побочным каналам на криптографические...

На данный момент Лаборатория RSA рекомендует использовать для обычных задач ключи размером 1024 бита, а для особо важных — 2048 бит.

Оптимальным вариантом может стать криптосистема на эллиптических кривых (ЭК).

Обсуждение

Социальные комментарии Cackle

Похожие статьи

Эллиптические кривые в алгоритме Диффи - Хеллмана над...

Основные термины (генерируются автоматически): кривой, дискретный логарифм, целое число, операция сложения, образ операцией, пользователь

Ключевые слова. эллиптические кривые, Криптосистема Диффи–Хеллмана, абелева группа, суперсингулярная кривая.

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

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

2. Бессалов А.В., Телиженко А.Б. Криптосистемы на эллиптических кривых : Учеб. пособие.

Особенности оценки качества и оптимизации алгоритмов...

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

Разработка эффективной реализации алгоритмов выполнения...

Ключевая слова: криптосистема на точках эллиптической кривой, система остаточных классов, модульное сложение, приближенный

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

Оценка стойкости криптосистемы Эль-Гамаля

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

Пост-квантовый алгоритм электронно-цифровой подписи на...

Например, алгоритм ЭЦП ECDSA использует проблему вычисления дискретного логарифма в группе точек эллиптической кривой, а

Будем использовать в качестве односторонней ЭЦП алгоритм Винтерница.

Способ хранения закрытого ключа криптосистемы цифровой подписи.

Анализ псевдослучайных последовательностей на эллиптической...

Эллиптическая кривая широко используется для построения криптосистем [].

Критерий 1. Двучлен будет образующим элементом в , только если - образующий элемент в .

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

Обзор видов атак по побочным каналам на криптографические...

На данный момент Лаборатория RSA рекомендует использовать для обычных задач ключи размером 1024 бита, а для особо важных — 2048 бит.

Оптимальным вариантом может стать криптосистема на эллиптических кривых (ЭК).

Эллиптические кривые в алгоритме Диффи - Хеллмана над...

Основные термины (генерируются автоматически): кривой, дискретный логарифм, целое число, операция сложения, образ операцией, пользователь

Ключевые слова. эллиптические кривые, Криптосистема Диффи–Хеллмана, абелева группа, суперсингулярная кривая.

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

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

2. Бессалов А.В., Телиженко А.Б. Криптосистемы на эллиптических кривых : Учеб. пособие.

Особенности оценки качества и оптимизации алгоритмов...

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

Разработка эффективной реализации алгоритмов выполнения...

Ключевая слова: криптосистема на точках эллиптической кривой, система остаточных классов, модульное сложение, приближенный

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

Оценка стойкости криптосистемы Эль-Гамаля

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

Пост-квантовый алгоритм электронно-цифровой подписи на...

Например, алгоритм ЭЦП ECDSA использует проблему вычисления дискретного логарифма в группе точек эллиптической кривой, а

Будем использовать в качестве односторонней ЭЦП алгоритм Винтерница.

Способ хранения закрытого ключа криптосистемы цифровой подписи.

Анализ псевдослучайных последовательностей на эллиптической...

Эллиптическая кривая широко используется для построения криптосистем [].

Критерий 1. Двучлен будет образующим элементом в , только если - образующий элемент в .

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

Обзор видов атак по побочным каналам на криптографические...

На данный момент Лаборатория RSA рекомендует использовать для обычных задач ключи размером 1024 бита, а для особо важных — 2048 бит.

Оптимальным вариантом может стать криптосистема на эллиптических кривых (ЭК).

Задать вопрос