УДК 004.056.55

Анализ алгоритмов криптографической защиты данных на основе эллиптических кривых

Коржов А.В., Чернышова А.В.

Донецкий национальный технический университет

кафедра программной инженерии им. Л.П. Фельдмана

E-mail: mr.demonsmert@mail.ru

Аннотация:

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

Annotation:

Korzhov A.V., Chernyshova A.V. Analysis of cryptographic data protection algorithms based on elliptic curves. The article discusses in detail the various cryptographic data protection algorithms that use elliptical cryptography.

Ключевые слова: криптография, протокол, эллиптическая кривая, ECDHE, ECDSA, преимущество, недостаток.

Keywords: cryptography, protocol, elliptic curve, ECDHE, ECDSA, advantage, disadvantage.

Введение

В современном мире вопросами безопасной передачи информации занимается криптография. Данная наука ставит перед собой вопросы о защите данных пользователей в Интернете, с помощью различных криптографических алгоритмов защиты передаваемой информации по сети. В настоящее время существуют различные протоколы для передачи данных по сети Интернет, однако особое место занимают протоколы, которые применяют криптографию на основе эллиптических кривых. Примерами таких протоколов могут послужить: SSL/TLS, Signal Protocol, SSH (Secure Shell), Bitcoin, FIDO (Fast Identity Online), IPSec, WireGuard [1].

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

Современные протоколы, такие как SSL/TLS, Signal Protocol, SSH (Secure Shell), Bitcoin, FIDO (Fast Identity Online), IPSec, WireGuard, применяют различные алгоритмы криптографии, которые основаны на эллиптических кривых. Каждый из алгоритмов, применяемый в данных протоколах, имеет свои преимущества и недостатки. Проведя подробный анализ данных алгоритмов, можно будет сделать вывод о наиболее сильных сторонах эллиптических алгоритмов, а также составить требования к авторскому алгоритму для протокола передачи данных с криптографией на эллиптических кривых.

Современные алгоритмы эллиптической криптографии

Проведя анализ современных протоколов передачи данных, среди которых SSH (Secure Shell), Bitcoin, FIDO (Fast Identity Online), IPSec, WireGuard, можно выделить несколько современных алгоритмов эллиптической криптографии, которые применяются наиболее широко: ECDHE, ECDSA, X3DH, Double Ratchet, Curve25519 [1].

ECDHE (Elliptic Curve Diffie-Hellman Ephemeral) — криптографический алгоритм, реализующий механизм согласования сеансовых ключей на основе эллиптических кривых. Его ключевая функция заключается в обеспечении безопасного обмена временными (эфемерными) ключами между клиентом и сервером, что гарантирует свойство совершенной прямой секретности (PFS). В протоколах SSL/TLS ECDHE применяется для создания уникального сессионного ключа, предотвращающего компрометацию прошлых или будущих сессий даже при утечке долгосрочных ключей.

ECDSA (Elliptic Curve Digital Signature Algorithm) — стандартизированный алгоритм цифровой подписи, основанный на математике эллиптических кривых. Предназначен для формирования и верификации электронных подписей, обеспечивающих аутентификацию сторон и защиту целостности данных. В рамках TLS/SSL ECDSA используется для подписи сертификатов, аутентификации участников соединения и подтверждения легитимности ключевых параметров на этапе handshake.

X3DH — алгоритм, основной целью которого является безопасный обмен ключами и данными. Данный алгоритм был разработан специально для Signal Protocol и, в первую очередь, отвечает за генерацию сессионных ключей и их последующую подпись. Особенностью данного алгоритма являются то, что он расширяет классический алгоритм Диффи-Хеллмана за счёт тройного ключевого согласования.

Double Ratchet — криптографический алгоритм, разработанный для безопасного и конфиденциального обмена сообщениями в режиме реального времени. Данный алгоритм был также создал для Signal Protocol и является комбинацией алгоритма ECDHE и алгоритмов симметричного шифрования. Данный алгоритм способен обеспечивать: автоматическое обновление ключей шифрования для каждого сообщения, сохранять работоспособность при частичной компрометации.

Curve25519 — современный, безопасный алгоритм на эллиптических кривых, который позволяет создавать ключи и проводить обмен ими с высокой производительностью. Данный алгоритм обеспечивает высокую безопасность данных и превосходную производительность. Также, стоит отметить, что данный алгоритм стал частью политики безопасности ECC-curve25519-ChaCha20Poly1305 [2].

Приведённые выше алгоритмы являются алгоритмами эллиптической криптографии, однако стоит отметить, что среди них выделяются два основных и самых распространённых на данный момент времени алгоритма — ECDHE и ECDSA. Данные алгоритмы являются “стандартом” эллиптической криптографии. Остальные алгоритмы, такие как X3DH, Double Ratchet и Curve25519 являются алгоритмами, которые созданы на основе алгоритмов ECDHE и ECDSA. Так, например, алгоритм X3DH взял за основу алгоритм ECDSA и немного дополнил его тройным ключевым согласованием, в то время как алгоритм Double Ratchet полностью взял алгоритм ECDHE и совместил его с симметричным шифрованием. Curve25519, в свою очередь, разработан на основе ECDHE, однако содержит особую эллиптическую кривую настроек для обеспечения высокой производительности и безопасности.

Далее мы поговорим более подробно об алгоритмах ECDHE и ECDSA, выделим их преимущества и недостатки.

Основы эллиптических алгоритмов

Эллиптические алгоритмы включают в свою основу несколько важных этапов, благодаря которым они могут обеспечить высокую безопасность и достаточно высокую производительность. В своей основе, эллиптические алгоритмы содержат: эллиптическую кривую, базовую точку G, закрытый ключ d, открытый ключ Q. Далее рассмотрим каждый из данных элементов более подробно.

Главным элементом алгоритма эллиптической криптографии является эллиптическая кривая, которая определяется уравнением Вейерштарсса. Данное уравнение представлено в общем виде над конечными полями ниже:

\[ y^{2} = x^{3} + ax + b \tag{1} \]

В уравнение (1) можно выделить следующие переменные:

- x, y — координаты точек на эллиптической кривой;

- a, b — параметры, которые определяют конкретную эллиптическую кривую.

Важно отметить, что все вычисления производятся над конечным полем (Fp).

В качестве примера эллиптической кривой можно привести кривую, которая применяется в алгоритме Curve25519 и носит аналогичное название. Данная кривая представлена ниже:

\[ y^{2} = x^{3} + 486662x^{2} + x \tag{2} \]

Следующим важным элементом эллиптического алгоритма является базовая точка G. Данная точка принадлежит эллиптической кривой и служит для генерации публичных ключей. Для генерации используется также закрытый ключ d, который представлен случайным числом в диапазоне [1, n-1], при том, что число n соответствует порядку эллиптической кривой. Далее, происходит генерация открытого ключа Q, при помощи формулы (3). В данной формуле операция “×” соответствует операции сложения точки G с самой собой d раз.

\[ Q = d \times G \tag{3} \]

Алгоритм ECDHE

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

Общий секрет сторон формируется на основе их публичных ключей. Например, если сторона 1 и сторона 2 сгенерировали свои открытые ключи по формуле, представленной на рисунке 3, то данные стороны должны вычислить общий секрет (секретное значение) по формуле (4).

\[ S = d_1 * Q_2 = d_2 * Q_1 = d_1 d_2 \times G \tag{4} \]

Сложность вычисления общего секрета сторон составляет основу безопасности эллиптического алгоритма ECDHE и известна как задача дискретного логарифма на эллиптических кривых [4].

Далее будет рассмотрен общий механизм работы алгоритма ECDHE.

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

2) Второй этап включает в себя процесс генерации ключей. Каждая сторона должна произвести процесс генерации закрытого ключа d, а также произвести генерацию открытого ключа Q.

3) Далее стороны должны произвести обмен публичными ключами. На данном этапе участники должны произвести обмен между собой открытыми ключами, чтобы в последующем высчитать общий секрет.

4) Четвёртым этапом является вычисление общего секрета. Обе стороны должны вычислить общий секрет S при помощи своего закрытого ключа и полученного открытого ключа.

5) Последний этап — производство сессионных ключей. На данном этапе общий секрет S проходит процесс преобразования в ключ симметричного шифрования через любую функцию хеширования.

В таблице 1 приведём основные преимущества и недостатки алгоритма ECDHE, которые выделяются в современных реализациях.

Таблица 1 - Преимущества и недостатки алгоритма ECDHE
Преимущества Недостатки

Обеспечивается прямая секретность.

Крайне уязвим при плохой реализации (например, при слабом генераторе случайных ключей).

Высокий уровень защиты при меньших ключах.

Сложная оптимизация на ограниченных устройствах (микроконтроллерах).

Производительнее традиционных алгоритмов (RSA, DSA и др.).

Может потребоваться поддержка нестандартных кривых для определённых устройств и приложений.

Меньшая вычислительная нагрузка на CPU и память.

Генерация ключей требуется для каждой отдельной сессии.

Короткие ключи с высоким уровнем безопасности (256-битный ECDHE ключ, в сравнении с 3072-битным RSA ключом).

В долгосрочной перспективе уязвим к полному квантовому взлому (совершенные квантовые атаки).

Временные (эфемерные) ключи.

Требуется корректное и полное согласование параметров кривой и генератора.

Устойчив к базовым квантовым атакам.

Высокое сочетание с различными алгоритмами аутентификации.

Помимо преимуществ и недостатков, требуется выделить основные уязвимости алгоритма ECDHE. Среди основных уязвимостей выделяются уязвимости к следующим атакам:

- атака по времени (Timing Attacks);

- Side-Channel атаки;

- инвалидация кривой (Invalid Curve Attack).

Атака по времени (Timing Attacks) — некорректная реализация операций над точками эллиптической кривой (например, скалярного умножения) может позволить злоумышленнику определить закрытый ключ через анализ времени выполнения операций.

Side-Channel атаки — утечки данных через электромагнитное излучение, потребление энергии или кэш-память могут раскрыть секретные параметры, которые помогут злоумышленнику получить необходимую информацию.

Инвалидация кривой (Invalid Curve Attack) — если реализация не проверяет принадлежность публичного ключа оппонента к заданной кривой, злоумышленник может подменить точку, что приведёт к компрометации секрета.

На практике алгоритм ECDHE встроен в криптографические библиотеки. Так, например, на рисунке 1 представим реализацию алгоритма ECDHE с применением языка программирования Python и библиотеки cryptography.

Реализация ECDHE на языке программирования Python

Рис. 1 Реализация ECDHE на языке программирования Python

Алгоритм ECDSA

Алгоритм ECDSA представляет собой алгоритм цифровой подписи, основанный на криптографии эллиптических кривых (ECC). Он обеспечивает аутентификацию, целостность данных и неотрекаемость, используя меньшую длину ключей по сравнению с классическими алгоритмами (например, RSA). ECDSA стандартизирован в NIST FIPS 186-5 [5] и широко применяется в TLS, блокчейне (Bitcoin) и IoT-устройствах.

Математические основы данного алгоритма включают в себя все основные элементы: эллиптическую кривую, базовую точку, закрытый ключ и открытый ключ. Однако, в отличии от ECDHE, алгоритм ECDSA не предполагает генерацию общего секрета для обоих сторон.

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

Генерация цифровой подписи.

1. Вычисление хэша сообщения. Хэш вычисляется по формуле (5), при этом хэш должен быть преобразован в целое число.

\[ h = Hash(m) \tag{5} \]

2. Генерация случайного числа k. Данное число должно быть сгенерировано в диапазоне [1, n-1], после чего будет применяться для генерации точки R.

3. Вычисление точки R. Данная точка должна быть вычислена с помощью формулы (6).

\[ R = k \times G \tag{6} \]

4. Вычисление параметра r. Вычисление данного параметра производится по формуле (7).

\[ r = x_R * mod(n) \tag{7} \]

В формуле (7) xR является координатой X точки R, которую мы вычислили на предыдущем шаге. В случае, если параметр r = 0, требуется повторить действия начиная с шага 2.

5. Вычисление параметра s. Данный параметр вычисляется по формуле (8), которая представлена ниже.

\[ s = k^{-1} (h + d \times r) mod (n) \tag{8} \]

В тех случаях, когда s = 0, требуется также повторить все действия, начиная с шага 2 алгоритма генерации подписи.

6. Получение пары для подписи. В конце работы алгоритма мы получаем пару (r, s), которая является нашей цифровой подписью.

Проверка подлинности цифровой подписи.

1. Проверка пары (r, s). Для начала проверки цифровой подписи, требуется убедиться, что параметры r и s находятся в диапазоне [1, n-1].

2. Следующим шагом является вычисление хэша h. Данный хэш вычисляется согласно формуле, представленной ранее формулой (5).

3. Вычисление значений u1 и u2. Данные значения вычисляются согласно формулам (9) и (10).

\[ u_1 = h * s^{-1} mod (n) \tag{9} \]
\[ u_2 = r * s^{-1} mod (n) \tag{10} \]

4. Вычисление точки P. Данная точка вычисляется с применением значений u1 и u2, которые были получены на предыдущем шаге. Формула (11) демонстрирует, как происходит вычисление точки P.

\[ P = u_1 \times G + u_2 \times Q \tag{11} \]

5. Проверка параметра r. Если проверка, которая представлена формулой (12), выполняется, тогда можно говорить о том, что цифровая подпись корректна и данные не были видоизменены. В ином случае — данные были повреждены.

\[ r = x_p mod(n) \tag{12} \]

В таблице 2 приведём основные преимущества и недостатки алгоритма ECDSA.

Таблица 2 — Преимущества и недостатки алгоритма ECDSA
Преимущества Недостатки

Высокая защита при короткой длине ключа.

Уязвим при неправильной реализации, особенно при повторном использовании параметра k.

Высокая скорость генерации и проверки цифровой подписи в сравнении с другими алгоритмами.

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

Минимальная нагрузка на вычислительные ресурсы.

Короткие подписи могут быть менее совместимы со старыми системами или ПО, ожидающими длинные поля.

Отлично подходит для встраиваемых устройств, IoT, мобильных телефонов.

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

Высокая защита от различных атак при корректной реализации.

При повторе параметра k ключ становится вычислить возможно.

Уязвимости данного алгоритма можно выделить следующие:

- атаки, связанные с некорректной генерацией параметров (зачастую параметра k);

- Side-Channel атаки; атаки по времени (Timing Attacks);

- инвалидация кривой (Invalid Curve Attack);

- атаки на хэш-функции;

атаки на математические свойства кривых;

квантовые атаки; социальные атаки.

Некоторые из атак мы рассмотрели при описании алгоритма ECDHE, поэтому поговорим о новых атаках.

Атаки, связанные с некорректной генерацией параметров — данный вид атак предполагает повторное использование параметра k при создании подписи. В случае, если один и тот же параметр k используется для подписи разных сообщений, то злоумышленник способен вычислить закрытый ключ d. Примером такой атаки может служить уязвимость, которая была обнаружена в PlayStation 3, где параметр k был статически генерируемым.

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

Атаки на математические свойства кривых — данные атаки включают в себя две разновидности. Первая разновидность — атака на кривые с малым порядком подгруппы. В данном случае предполагается, что порядок подгруппы n содержит малые простые делители и злоумышленник может восстановить значение d прибегнув к алгоритму Полига-Хеллмана, а также к китайской теореме об остатках. Вторая разновидность — атака сдвига битов. Предполагается, что злоумышленник будет эксплуатировать утечки информации, если алгоритм применяет дополнительные алгоритмы скалярного умножения, который в свою очередь не имеют защиты от side-channel атак.

Квантовые атаки — данные атаки предполагают применение квантовых алгоритмов на квантовых компьютерах, чтобы вычислить необходимые параметры для взлома алгоритма. Так, например, предполагается что алгоритм Шора способен за полиномиальное время вычислить закрытый ключ d по открытому ключу Q.

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

На практике, алгоритм ECDSA встроен в криптографические библиотеки. Так, например, на рисунке 2 представим реализацию алгоритма ECDSA с применением языка программирования Python и библиотеки cryptography.

Реализация ECDSA на языке программирования Python

Рис. 2 Реализация ECDSA на языке программирования Python

В свою очередь, на рисунке 3 представим реализацию алгоритма ECDSA с применением языка программирования C++ при использовании библиотеки OpenSSL.

Реализация ECDSA на языке программирования C++

Рис. 3 Реализация ECDSA на языке программирования C++

Выводы

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

Для каждого алгоритма был проведён анализ метода его работы, а также были выявлены основные преимущества и недостатки алгоритмов и проанализированы основные уязвимости для данных алгоритмов. Помимо данного анализ, для каждого из эллиптических алгоритмов (ECDHE и ECDSA) была приведена простая реализация данных алгоритмов с применением языка программирования Python и применением библиотеки cryptography.

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

Литература

1. Чернышова, А. В. Анализ эффективности протоколов передачи данных, использующих криптографические алгоритмы на эллиптических кривых / А. В. Чернышова, А. В. Коржов // Программная инженерия: методы и технологии разработки информационно-вычислительных систем (ПИИВС-2024) : Сборник материалов и докладов V Международной научно-практической конференции, Донецк, 27–28 ноября 2024 года. – Донецк: Донецкий национальный технический университет, 2024. – С. 100-110. – EDN VWDIKY.

2. Касаткин, И. А. Обзор системы безопасности стандарта промышленной связи Open Platform Communications Unified Architecture / И. А. Касаткин // Информационные технологии в науке, промышленности и образовании: Сборник трудов Всероссийской научно-технической конференции, Ижевск, 23–24 мая 2024 года. – Ижевск: Ижевский государственный технический университет им. М.Т. Калашникова, 2024. – С. 376-380. – EDN BDYMLS.

3. Bernstein D. J. Curve25519: New Diffie-Hellman Speed Records [Электронный ресурс] // Proceedings of PKC 2006. – 2006. – С. 207–228. – URL: https://cr.yp.to/ecdh/curve25519-20060209.pdf (дата обращения: 04.04.2025).

4. Алгоритм шифрования данных с использованием эллиптических кривых / В. К. Байдицкая, Г. Ю. Березовский, Е. М. Гунченко, О. В. Лелонд // Лучшая научно-исследовательская работа 2016: сборник статей победителей II Международного научно-практического конкурса. – Пенза: "Наука и Просвещение" (ИП Гуляев Г.Ю.), 2016. – С. 20-26. – EDN WEHRNB.

5. National Institute of Standards and Technology (NIST). Digital Signature Standard (DSS) [Электронный ресурс] // FIPS PUB 186-5. – 2023. – URL: https://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.186-5.pdf (дата обращения: 04.04.2025).

6. Великий, А. О. Алгоритмы хеширования / А. О. Великий, А. Н. Гамова // Информатика, управляющие системы, математическое и компьютерное моделирование (ИУСМКМ-2024) : XV Международная научно-техническая конференция в рамках X Международного Научного форума Донецкой Народной Республики, Донецк, 29–30 мая 2024 года. – Донецк: Донецкий национальный технический университет, 2024. – С. 16-24. – EDN QXXIPY.