Исследование вопросов применения эллиптических кривых Эдвардса в микропроцессорных криптографических системах
Автор: Лисовский Леонид Дмитриевич
Научный руководитель: Зуйкова Татьяна Николаевна
Рубрика: 4. Информатика
Опубликовано в
LXXXII международная научная конференция «Исследования молодых ученых» (Казань, май 2024)
Дата публикации: 19.05.2024
Статья просмотрена: 107 раз
Библиографическое описание:
Лисовский, Л. Д. Исследование вопросов применения эллиптических кривых Эдвардса в микропроцессорных криптографических системах / Л. Д. Лисовский. — Текст : непосредственный // Исследования молодых ученых : материалы LXXXII Междунар. науч. конф. (г. Казань, май 2024 г.). — Казань : Молодой ученый, 2024. — С. 79-84. — URL: https://moluch.ru/conf/stud/archive/516/18542/ (дата обращения: 17.10.2024).
При реализации криптографических алгоритмов в микропроцессорных криптосистемах актуальной задачей является совершенствование методов криптозащиты информации с применением инновационных решений. Целью работы является формирование новых подходов к практической реализации микропроцессорных криптографических систем на основе математического аппарата эллиптических кривых Эдвардса. Разработанное программное обеспечение позволило осуществить генерацию циклических подгрупп точек эллиптических кривых и провести сравнительный анализ эллиптических кривых в канонической форме Вейерштрасса и кривых Эдвардса. В настоящей работе подтверждена целесообразность замены в криптографических алгоритмах эллиптических кривых в канонической форме Вейерштрасса кривыми Эдвардса.
Ключевые слова: эллиптическая криптография, эллиптическая кривая, форма Вейерштрасса, кривые Эдвардса, конечные поля, группа точек, циклическая подгруппа, ко-фактор.
В инфокоммуникационных приложениях широко применяются криптографические методы защиты передаваемой, хранимой и обрабатываемой информации. Одним из перспективных направлений для поиска решений повышения криптостойкости асимметричных криптографических алгоритмов является применение математического аппарата эллиптических кривых. [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]
Теоретические основы эллиптических кривых подробно изложены в монографии [4]. При реализации базовых криптографических операций в группе точек эллиптической кривой над простым полем GF(p) используют пару операций: сложение и вычитание. [3] Целочисленные решения уравнения эллиптической кривой над простым полем образуют конечную группу множества точек с координатами ( x, y ).
Для сравнительного анализа эллиптических кривых в канонической форме Вейерштрасса и кривых Эдвардса разработано программное обеспечение, осуществляющее генерацию циклических подгрупп групп точек эллиптических кривых над простыми полями Галуа.
Генерация циклических подгрупп выполнена по следующему алгоритму:
1) инициализация параметров эллиптической кривой;
2) последовательный выбор точек эллиптической кривой с целочисленными координатами ( x, y );
3) сложение с выбранной точкой ( x, y );
4) если результат не совпадает с нейтральным элементом e группы точек, то возврат к шагу 3;
5) точка (x, y) — искомая порождающая точка циклической подгруппы, возврат к шагу 2.
В результате исследования созданы программы, производящие подсчет порядков циклических подгрупп для эллиптических кривых в канонической форме Вейерштрасса и кривых Эдвардса.
Результаты вычислительных экспериментов, проведенных с применением разработанных программ, представлены в таблице 1 для эллиптических кривых в форме Вейерштрасса с параметрами a, b и в таблице 2 для эллиптических кривых Эдвардса с параметром d над простыми полями GF(p) .
Таблица 1
Результаты экспериментов с эллиптическими кривыми в форме Вейерштрасса
p |
a |
b |
Порядок группы точек |
Кол-во базовых точек с ко-фактором 1 |
Кол-во базовых точек с ко-фактором от 1 до 4 |
Кол-во базовых точек с ко-фактором более 4 |
3 |
0 |
1 |
3 |
2 |
1 |
0 |
5 |
1 |
-1 |
9 |
6 |
2 |
1 |
7 |
3 |
4 |
10 |
4 |
4 |
2 |
11 |
1 |
3 |
18 |
6 |
8 |
4 |
13 |
2 |
3 |
18 |
6 |
8 |
4 |
17 |
2 |
3 |
22 |
10 |
10 |
2 |
19 |
2 |
1 |
27 |
18 |
6 |
3 |
Каждый элемент в группе точек эллиптической кривой, являясь порождающей точкой, может порождать циклическую подгруппу, количество элементов которой называется порядком подгруппы. Количество элементов группы точек называется порядком группы. Эффективность циклической подгруппы оценивается ко-фактором, определяемым как отношение порядка группы к порядку циклической подгруппы. Ко-фактор не должен превышать значения 4, при котором порождающая точка формирует циклическую подгруппу, содержащую четвертую часть всех точек группы. При значении ко-фактора 1 порождаемая циклическая подгруппа содержит все точки группы. Для криптографических инфокоммуникационных приложений используются циклические подгруппы с ко-фактором не более 4 [3].
Таблица 2
Результаты экспериментов с эллиптическими кривыми Эдвардса
p |
d |
Порядок группы точек |
Кол-во базовых точек с ко-фактором 1 |
Кол-во базовых точек с ко-фактором от 1 до 4 |
Кол-во базовых точек с ко-фактором более 4 |
4 |
-4 |
8 |
0 |
7 |
1 |
5 |
-5 |
16 |
0 |
12 |
4 |
7 |
-7 |
48 |
16 |
20 |
12 |
11 |
-11 |
120 |
32 |
40 |
48 |
13 |
-13 |
144 |
0 |
0 |
144 |
17 |
-17 |
256 |
0 |
0 |
256 |
19 |
-19 |
360 |
96 |
104 |
160 |
Количество целочисленных решений уравнения эллиптической кривой Эдвардса значительно превышает количество целочисленных решений канонического уравнения в форме Вейерштрасса над простыми полями GF(p) , что позволяет при меньшем значении p обеспечить требуемый диапазон значений обрабатываемых данных алгоритмами эллиптической криптографии.
Сравнительный анализ полученных данных подтверждает целесообразность замены в криптографических алгоритмах эллиптических кривых в канонической форме Вейерштрасса кривыми Эдвардса.
Литература:
- Анализ возможностей математического аппарата с целью применения в криптографических инфокоммуникационных приложениях // К. А. Нечаев, Т. Н. Зуйкова. XIV Молодежный научный форум. Сборник трудов, том 1. М.: МТУСИ, 2023. С. 300–307. — URL: https://drive.google.com/drive/folders/16qXsSUXWdSh5BaTaRNLGxH-V2u35wqay (дата обращения: 15.05.2024).
- Эллиптические кривые для нового стандарта электронной подписи [Электронный ресурс] // С. В. Смышляев. — ООО «КРИПТО-ПРО». — URL: https://www.cryptopro.ru/blog/2014/01/21/ellipticheskie-krivye-dlya-novogo-standarta-elektronnoi-podpisi (дата обращения: 15.05.2024).
- Математика криптографии и теория шифрования / А. Бехроуз. ИНТУИТ. URL: https://intuit.ru/studies/courses/552/408/info (дата обращения: 15.15.2024).
- Бессалов А. В. Эллиптические кривые в форме Эдвардса и криптография: Монография. — 2017.
Ключевые слова
эллиптическая кривая, эллиптическая криптография, конечные поля, форма Вейерштрасса, кривые Эдвардса, группа точек, циклическая подгруппа, ко-факторПохожие статьи
Робастная устойчивость системы с одним входом и одним выходом в классе катастроф «гиперболическая омбилика»
В статье предлагается новый подход к построению систем управления для объектов с неопределенными параметрами в форме трехпараметрических структурно-устойчивых отображений из теории катастроф, позволяющей синтезировать высокоэффективные системы управл...
Модифицированное уравнение Беллмана для эргодических марковских цепей с доходами
Управляемые марковские цепи с одним эргодическим классом и, возможно, с невозвратными состояниями изучаются с помощью операторов сжатия. Строится модифицированное уравнение Беллмана, позволяющее найти оптимальные стратегии не только на конечном, но и...
Анализ влияния вычислительной погрешности в явных методах Рунге — Кутты
Статья посвящена нахождению приемов и способов улучшения и оптимизации известных методов интегрирования систем обыкновенных дифференциальных уравнений (СОДУ). Задача уменьшения вычислительной погрешности при меньших затратах является наиболее актуаль...
Разработка эффективной реализации алгоритмов выполнения арифметических операций с точками эллиптической кривой на базе приближенного метода в СОК
В статье исследуются методы выполнения арифметических операций с точками эллиптической кривой. Предложен метод модульного сложения чисел в системе остаточных классов с использованием приближенного метода, позволяющий без использования операции сравне...
Применение ИКТ в геометрических и физических приложениях определённого интеграла
Выбор темы связан с информатизацией процесса обучения. Роль математического аппарата в решении задач по естественным дисциплинам нельзя переоценить. Без математической грамотности невозможно успешное освоение методов решения по физике, химии, биологи...
Алгоритм решения прикладных задач для обыкновенных дифференциальных уравнений четвертого порядка с методом дифференциальной прогонки
Метод дифференциальной прогонки развивается для решения широкого класса краевых задач дифференциальных уравнений четвертого порядка с переменными коэффициентами. В ряде прикладных задач показывается эффективность предлагаемого метода как способа алго...
Применение итерационного алгоритма Шульца в рекуррентных алгоритмах параметрической идентификации
В данной статье рассмотрен процесс исследования и реализации рекуррентных алгоритмов параметрической идентификации (на примере алгоритма Левенберга-Маркварда) в программной среде Unity Pro XL с использованием средств промышленной автоматики, в том чи...
Разработка эффективных методов реализации псевдослучайных последовательностей в системе остаточных классов
В статье исследуется вопрос генерации псевдослучайных чисел в системе остаточных классов. Для повышения производительности и уменьшения издержек, связных с реализацией проблемных операций в системе остаточных классов, используется приближенный метод....
О корнях кубического уравнения
Известно, что решение некоторых теоретических и практических задач, а также моделирование некоторых физических процессов требует определение границ отрезков (интервалов) в которых находятся корни кубического уравнения с действительными коэффициентами...
Похожие статьи
Робастная устойчивость системы с одним входом и одним выходом в классе катастроф «гиперболическая омбилика»
В статье предлагается новый подход к построению систем управления для объектов с неопределенными параметрами в форме трехпараметрических структурно-устойчивых отображений из теории катастроф, позволяющей синтезировать высокоэффективные системы управл...
Модифицированное уравнение Беллмана для эргодических марковских цепей с доходами
Управляемые марковские цепи с одним эргодическим классом и, возможно, с невозвратными состояниями изучаются с помощью операторов сжатия. Строится модифицированное уравнение Беллмана, позволяющее найти оптимальные стратегии не только на конечном, но и...
Анализ влияния вычислительной погрешности в явных методах Рунге — Кутты
Статья посвящена нахождению приемов и способов улучшения и оптимизации известных методов интегрирования систем обыкновенных дифференциальных уравнений (СОДУ). Задача уменьшения вычислительной погрешности при меньших затратах является наиболее актуаль...
Разработка эффективной реализации алгоритмов выполнения арифметических операций с точками эллиптической кривой на базе приближенного метода в СОК
В статье исследуются методы выполнения арифметических операций с точками эллиптической кривой. Предложен метод модульного сложения чисел в системе остаточных классов с использованием приближенного метода, позволяющий без использования операции сравне...
Применение ИКТ в геометрических и физических приложениях определённого интеграла
Выбор темы связан с информатизацией процесса обучения. Роль математического аппарата в решении задач по естественным дисциплинам нельзя переоценить. Без математической грамотности невозможно успешное освоение методов решения по физике, химии, биологи...
Алгоритм решения прикладных задач для обыкновенных дифференциальных уравнений четвертого порядка с методом дифференциальной прогонки
Метод дифференциальной прогонки развивается для решения широкого класса краевых задач дифференциальных уравнений четвертого порядка с переменными коэффициентами. В ряде прикладных задач показывается эффективность предлагаемого метода как способа алго...
Применение итерационного алгоритма Шульца в рекуррентных алгоритмах параметрической идентификации
В данной статье рассмотрен процесс исследования и реализации рекуррентных алгоритмов параметрической идентификации (на примере алгоритма Левенберга-Маркварда) в программной среде Unity Pro XL с использованием средств промышленной автоматики, в том чи...
Разработка эффективных методов реализации псевдослучайных последовательностей в системе остаточных классов
В статье исследуется вопрос генерации псевдослучайных чисел в системе остаточных классов. Для повышения производительности и уменьшения издержек, связных с реализацией проблемных операций в системе остаточных классов, используется приближенный метод....
О корнях кубического уравнения
Известно, что решение некоторых теоретических и практических задач, а также моделирование некоторых физических процессов требует определение границ отрезков (интервалов) в которых находятся корни кубического уравнения с действительными коэффициентами...