Исследование вопросов применения эллиптических кривых Эдвардса в микропроцессорных криптографических системах

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

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

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

В настоящее время в РФ национальный стандарт формирования цифровой электронной подписи ГОСТ 34.10–2018 основан на эллиптических кривых в канонической форме Вейерштрасса [2]. Однако эллиптические кривые Эдвардса обладают рядом преимуществ и позволяют более эффективно использовать вычислительные ресурсы микропроцессорных криптосистем.

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

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

В основе математического аппарата эллиптических кривых над простыми полями лежат модулярная математика и алгебраическая структура группы. В модулярной математике применяется оператор по модулю mod , представляющий собой процесс деления целого числа a на целое число n , где результатом является не частное, а целочисленный остаток r : amod n=r.

Результатом (a mod n) является положительное целое число, меньшее, чем n . Таким образом множество Zn наименьших вычетов по модулю n , содержащее все целые числа от 0 до ( n –1), образует конечное поле по модулю nGF(n) . Множество Zp наименьших вычетов по модулю простого числа p , образует конечное простое поле по модулю pGF(p) .

Алгебраическая структура группа G множества S , обозначаемая G = , с оператором (•) позволяет использовать одну пару взаимно обратных операций. Непустое подмножество группы G является подгруппой Н , и при этом H является группой относительно оператора (•) в группе G . Циклическая подгруппа — это такая подгруппа группы, которая может быть порождена путем многократного применения операции возведения в степень к элементу группы. Генератор g циклической подгруппы порядка n порождает все n элементов этой подгруппы. Одна и та же циклическая подгруппа может иметь несколько генераторов.

Порядок конечной группы, обозначаемый | G |, — это количество элементов в группе G . Теорема Лагранжа соотносит порядок группы G с порядком ее подгруппы H . Если порядки соответственно равны | G | и | H |, то по теореме Лагранжа | H | является делителем | G |. Одно из применений теоремы Лагранжа заключается в том, что порядки потенциальных подгрупп могут быть определены, основываясь на порядке группы G , если известны его делители. [3]

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

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

1) инициализация параметров эллиптической кривой;

2) последовательный выбор точек эллиптической кривой с целочисленными координатами ( x, y );

3) сложение с выбранной точкой ( x, y );

4) если результат не совпадает с нейтральным элементом e группы точек, то возврат к шагу 3;

5) точка (x, y) — искомая порождающая точка циклической подгруппы, возврат к шагу 2.

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

Результаты вычислительных экспериментов, проведенных с применением разработанных программ, представлены в таблице 1 для эллиптических кривых в форме Вейерштрасса с параметрами a, b и в таблице 2 для эллиптических кривых Эдвардса с параметром d над простыми полями GF(p) .

Таблица 1

Каждый элемент в группе точек эллиптической кривой, являясь порождающей точкой, может порождать циклическую подгруппу, количество элементов которой называется порядком подгруппы. Количество элементов группы точек называется порядком группы. Эффективность циклической подгруппы оценивается ко-фактором, определяемым как отношение порядка группы к порядку циклической подгруппы. Ко-фактор не должен превышать значения 4, при котором порождающая точка формирует циклическую подгруппу, содержащую четвертую часть всех точек группы. При значении ко-фактора 1 порождаемая циклическая подгруппа содержит все точки группы. Для криптографических инфокоммуникационных приложений используются циклические подгруппы с ко-фактором не более 4 [3].

Таблица 2

Результаты экспериментов с эллиптическими кривыми Эдвардса

Количество целочисленных решений уравнения эллиптической кривой Эдвардса значительно превышает количество целочисленных решений канонического уравнения в форме Вейерштрасса над простыми полями GF(p) , что позволяет при меньшем значении p обеспечить требуемый диапазон значений обрабатываемых данных алгоритмами эллиптической криптографии.

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

Литература:

1. Анализ возможностей математического аппарата с целью применения в криптографических инфокоммуникационных приложениях // К. А. Нечаев, Т. Н. Зуйкова. XIV Молодежный научный форум. Сборник трудов, том 1. М.: МТУСИ, 2023. С. 300–307. — URL: https://drive.google.com/drive/folders/16qXsSUXWdSh5BaTaRNLGxH-V2u35wqay (дата обращения: 15.05.2024).
2. Эллиптические кривые для нового стандарта электронной подписи [Электронный ресурс] // С. В. Смышляев. — ООО «КРИПТО-ПРО». — URL: https://www.cryptopro.ru/blog/2014/01/21/ellipticheskie-krivye-dlya-novogo-standarta-elektronnoi-podpisi (дата обращения: 15.05.2024).
3. Математика криптографии и теория шифрования / А. Бехроуз. ИНТУИТ. URL: https://intuit.ru/studies/courses/552/408/info (дата обращения: 15.15.2024).
4. Бессалов А. В. Эллиптические кривые в форме Эдвардса и криптография: Монография. — 2017.