ECDSA (ECDSA)
ECDSA (Elliptic Curve Digital Signature Algorithm) — алгоритм с открытым ключом, использующийся для построения и проверки электронной цифровой подписи при помощи криптографии на эллиптических кривых.
Алгоритм достаточно популярен в области электронных цифровых подписей из-за сложности задачи, на которой основано вычисление закрытого ключа из открытого. ECDSA принят различными организациями в качестве стандарта. Алгоритм состоит из четырёх частей: генерация основных параметров, генерация ключевой пары, создание и проверка цифровой подписи. В общем случае, считается достаточно безопасным (для соответствующих уровней криптостойкостей), а также имеет реализации во множестве криптографических библиотек.
История
[править | править код]Эллиптические кривые в качестве математического понятия изучаются уже достаточно давно. Например, ещё у древнегреческого математика Диофанта в III веке нашей эры в труде «Арифметика» были задачи, которые сводились к нахождению рациональных точек на эллиптической кривой[1]. Однако, их применение для реальных задач, в частности, для области криптографии, было неизвестно до конца XX века. В 1985 году Виктор Миллер и Нил Коблиц предложили использование эллиптических кривых для криптографии[2].
В 1991 году Национальным институтом стандартов и технологий (NIST) был разработан DSA, построенный на идее использования проблемы дискретного логарифма. Вскоре после этого NIST запросил публичные комментарии по поводу своего предложения о схемах цифровой подписи. Воодушевившись данной идеей, Скотт Ванстоун в статье «Responses to NIST’s proposal» предложил аналог алгоритму цифровой подписи, использующий криптографию на эллиптических кривых (ECDSA)[2].
В период с 1998-2000 гг. ECDSA был принят различными организациями как стандарт (ISO 14888-3, ANSI X9.62, IEEE 1363—2000, FIPS 186-2)[3].
Применение
[править | править код]Область применения ECDSA ограничивается областью применения электронной цифровой подписи. Другими словами, в тех местах, где может потребоваться проверка целостности и авторства сообщения. Например, использование в криптовалютных транзакциях (в биткойне и эфириуме) для обеспечения того, чтобы средства могли быть потрачены только своими законными владельцами[4].
Основные параметры эллиптической кривой
[править | править код]Основными параметрами (англ. domain parameters) эллиптической кривой над конечным полем называется совокупность следующих величин[5]:
- Порядок конечного поля (например, простое конечное поле при , где и является простым числом).
- (Field Representation) — индикатор, использующийся для представления элементов, принадлежащих полю .
- Два элемента поля , задающие коэффициенты уравнения эллиптической кривой над полем (например, при ).
- Базовая точка , имеющая простой порядок .
- Целое число , являющееся кофактором , где — порядок кривой, численно совпадающий с числом точек в .
Параметры должны быть выбраны таким образом, чтобы эллиптическая кривая, определённая над конечным полем , была устойчива ко всем известным атакам, применимым к ECDLP. Помимо этого могут быть и другие ограничения, связанные с соображениями безопасности или реализации. Как правило, основные параметры являются общими для группы сущностей, однако в некоторых приложениях (реализациях), они могут быть специфичными для каждого конкретного пользователя[6]
ECDSA по стандарту ANSI X9.62
[править | править код]Для практического применения ECDSA налагают ограничения на поля[7], в которых определены эллиптические кривые. Для простоты рассмотрим случай реализации алгоритмов, когда — простое конечное поле (для других полей — аналогично), тогда наше эллиптическое уравнение принимает вид .
Алгоритм генерации основных параметров
[править | править код]Для того, чтобы избежать известных атак, основанных на проблеме дискретного логарифма в группе точек эллиптической кривой, необходимо, чтобы число точек эллиптической кривой делилось на достаточно большое простое число . Стандарт ANSI X9.62 требует . Предлагается следующий алгоритм[8]:
Ввод: Порядок поля , индикатор представления поля для , - уровень безопасности: и . Вывод: Основные параметры эллиптической кривой . |
Шаг 1. Выберите верифицировано случайным образом элементы , удовлетворяющие условию . Шаг 2. , порядок кривой можно вычислить при помощи алгоритма SEA. Шаг 3. Проверьте, что при большом простом числе . Если нет, тогда перейдите к шагу 1. Шаг 4. Проверьте, что . Если нет, тогда перейдите к шагу 1. Шаг 5. Проверьте, что . Если нет, тогда перейдите к шагу 1. Шаг 6. . Шаг 7. Выберите произвольную точку и задайте . Повторяйте, пока , где - бесконечно удалённая точка Шаг 8. Верните |
Алгоритмы верификации случайным образом дают гарантию того, что эллиптическая кривая над конечным полем была сгенерирована абсолютно случайно[9].
Алгоритм генерации ключевой пары
[править | править код]Будем рассматривать обмен сообщениями между Алисой и Бобом. Предварительно используя алгоритм генерации основных параметров, Алиса получает свои основные параметры эллиптической кривой. Используя следующую последовательность действий, Алиса сгенерирует себе открытый и закрытый ключ[10].
Ввод: Основные параметры эллиптической кривой . Вывод: Открытый ключ - , закрытый ключ - . |
Шаг 1. Выберите случайное или псевдослучайное целое число . Шаг 2. Вычислите координаты точки на эллиптической кривой . Шаг 3. Верните . |
Целью проверки открытого ключа является подтверждение того, что открытый ключ обладает определенными арифметическими свойствами. Успешное выполнение данного алгоритма демонстрирует, что соответствующий закрытый ключ математически существует, но не гарантирует, что кто-то не вычислил данный закрытый ключ или что заявленный владелец действительно обладает им[11].
Ввод: Основные параметры эллиптической кривой , открытый ключ - . Вывод: Решение о принятии или отклонении достоверности открытого ключа . |
Шаг 1. Проверьте, что . Шаг 2. Проверьте, что являются правильно представленными элементами в , т.е. целыми числами, принадлежащими . Шаг 3. Проверьте, что удовлетворяет уравнению эллиптической кривой, определяемому элементами поля . Шаг 4. Проверьте, что . Шаг 5. Если какая-либо проверка не прошла, то вернуть "Отклонить", иначе "Принять". |
Алгоритм генерации цифровой подписи
[править | править код]Алиса, обладающая основными параметрами кривой и закрытым ключом , хочет подписать сообщение , для этого она должна сгенерировать подпись [12].
В дальнейшем обозначает криптографическую хэш-функцию, выходное значение которой имеют битовую длину не более (если это условие не выполняется, то выходное значение может быть усечено). Предполагается, что мы работаем с выходом функции, уже преобразованным в целое число.
Ввод: Основные параметры эллиптической кривой , закрытый ключ , сообщение . Вывод: Подпись . |
Шаг 1. Выберите случайное или псевдослучайное целое число . Шаг 2. Вычислите координаты точки . Шаг 3. Вычислите . Если , тогда перейдите к шагу 1. Шаг 4. Вычислите . Шаг 5. Вычислите . Если , тогда перейдите к шагу 1. Шаг 6. Верните . |
Алгоритм проверки цифровой подписи
[править | править код]Чтобы проверить подпись Алисы сообщения , Боб получает аутентичную копию её основных параметров кривой и связанный с ними открытый ключ [13]:.
Ввод: Основные параметры эллиптической кривой , открытый ключ , сообщение , подпись . Вывод: Решение о принятии или отклонении подписи. |
Шаг 1. Проверьте, что - целые числа, принадлежащие . Если какая-либо проверка не удалась, то вернуть "Отклонить". Шаг 2. Вычислите . Шаг 3. Вычислите . Шаг 4. Вычислите и . Шаг 5. Вычислите координаты точки . Шаг 6. Если , то вернуть "Отклонить". Иначе вычислить . Шаг 7. Если , то вернуть "Принять", иначе "Отклонить" |
Пусть подпись для сообщения действительно была сгенерирована Алисой, в таком случае, . Перестановка дает следующее[14]:
Таким образом, получаем , поэтому , что и требовалось доказать.
Пример работы ECDSA
[править | править код]В данном примере[15] будут описываться только значащие вычислительные шаги в алгоритмах, считая, что все проверки могут быть сделаны без текстового описания.
1. Используя алгоритм генерации основных параметров, получим следующие значения: , эллиптическая кривая , и базовая точка с порядком .
2. Сгенерируем пару ключей в соответствии с алгоритмом генерации ключевой пары:
Шаг 1. Выбираем . Шаг 2. Вычисляем координаты точки . |
3. Алгоритмом генерации цифровой подписи подпишем сообщение, заданное в виде текста со значением хэш-функции .
Шаг 1. Выбираем . Шаг 2. Вычисляем координаты точки . Шаг 3. Вычисляем . Шаг 4. Вычисляем . |
4. Проверим достоверность подписи для сообщения с помощью алгоритма проверки цифровой подписи.
Шаг 1. Вычисляем . Шаг 2. Вычисляем и . Шаг 3. Вычисляем координаты точки . Шаг 4. Вычислим . Шаг 5. Проверяем . Принимаем подпись. |
Безопасность
[править | править код]ECDSA по сравнению c DSA
[править | править код]Д. Брауном (Daniel R. L. Brown) было доказано, что алгоритм ECDSA не является более безопасным, чем DSA. Им было сформулировано ограничение безопасности для ECDSA, которое привело к следующему заключению: «Если группа эллиптической кривой может быть смоделирована основной группой и её хеш-функция удовлетворяет определённому обоснованному предположению, то ECDSA устойчива к атаке на основе подобранного открытого текста с существующей фальсификацией»[16].
Математические преимущества
[править | править код]Стойкость алгоритма шифрования основывается на проблеме дискретного логарифма в группе точек эллиптической кривой. В отличие от проблемы простого дискретного логарифма и проблемы факторизации целого числа, не существует субэкспоненциального алгоритма для проблемы дискретного логарифма в группе точек эллиптической кривой. По этой причине «сила на один бит ключа» существенно выше в алгоритме, который использует эллиптические кривые[17].
Это означает, что в криптографии на эллиптических кривых можно использовать значительно меньшие параметры, чем в других системах с открытыми ключами, таких как RSA и DSA, но с эквивалентным уровнем безопасности. К примеру, битовый размер ключей: 160-битный ключ будет равносилен ключам с 1024-битным модулем в RSA и DSA при сопоставимом уровне безопасности (против известных атак). Преимущества, полученные от меньших размеров параметров (в частности, ключей), включают скорость выполнения алгоритма, эффективное использование энергии, пропускной полосы, памяти[18]. Они особенно важны для приложений на устройствах с ограниченными возможностями, таких как смарт-карты[19].
Опасения по поводу разработанных алгоритмов
[править | править код]Явной проблемой является отсутствие доверия к некоторым уже разработанным ранее алгоритмам[20]. Например, NIST Special Publication 800-90, содержащая детерминированный генератор случайных битов на эллиптических кривых Dual_EC_DRBG. В самом стандарте содержится набор констант кривой, появление которых в представленном виде не объяснено, Шумоу и Фергюсон показали, что данные постоянные связаны с некоторым случайным набором чисел, работающим как бэкдор, возможно, для целей АНБ, но этому нет никаких достоверных подтверждений[21].
Практическая реализация
[править | править код]ECDSA реализован в таких криптографических библиотеках, как OpenSSL, Cryptlib, Crypto++, реализации протоколов GnuTLS, интерфейсе программирования приложений CryptoAPI. Существует и множество других программных реализаций алгоритма электронной цифровой подписи на эллиптических кривых, большинство из которых в основном сосредоточено на одном приложении, например, быстрой реализации для одного конкретного конечного поля[22].
Примечания
[править | править код]- ↑ Diophantus Arithmetic, с. 221.
- ↑ 1 2 Liao H. Z., Shen Y. Y, с. 109—110.
- ↑ Liao H. Z., Shen Y. Y, с. 110.
- ↑ Mayer H.
- ↑ Lopez J., Dahab R, с. 12.
- ↑ Hankerson et al, с. 172.
- ↑ Hankerson et al, с. 173-174.
- ↑ Hankerson et al, Алгоритм генерации основных параметров, с. 174.
- ↑ Hankerson et al, с. 175-178.
- ↑ Hankerson et al, Алгоритм генерации ключевой пары, с. 180.
- ↑ Hankerson et al, Алгоритм проверки открытого ключа, с. 181.
- ↑ Liao H. Z., Shen Y. Y, Алгоритм генерации цифровой подписи, с. 116-117.
- ↑ Liao H. Z., Shen Y. Y, Алгоритм проверки цифровой подписи, с. 117.
- ↑ Liao H. Z., Shen Y. Y, Доказательство работы алгоритма проверки цифровой подписи, с. 117.
- ↑ Liao H. Z., Shen Y. Y, с. 118—119.
- ↑ Brown D.
- ↑ Коржев В.
- ↑ Hankerson et al, Предисловие, с. xix.
- ↑ Lopez J., Dahab R, Аннотация.
- ↑ Schneier B. The NSA Is Breaking Most Encryption on the Internet.
- ↑ Schneier B. The Strange Story of Dual_EC_DRBG.
- ↑ Lopez J., Dahab R.
Литература
[править | править код]- Liao H. Z., Shen Y. Y. On the Elliptic Curve Digital Signature Algorithm . «Tunghai Science» (2006). Дата обращения: 28 сентября 2022. Архивировано 28 сентября 2022 года.
- Hankerson D., Menezes A. J., Vanstone S. Guide to elliptic curve cryptography . «Springer Science & Business Media» (2006). Дата обращения: 16 ноября 2022.
- Lopez J., Dahab R. An overview of elliptic curve cryptography . «Institute of Computing. State University of Campinas» (2000). Дата обращения: 16 ноября 2022.
- Коржев В. Цифровая подпись. Эллиптические кривые . «Открытые системы» (8 августа 2002). Дата обращения: 16 ноября 2008. Архивировано 31 декабря 2012 года.
- Mayer H. ECDSA security in bitcoin and ethereum: a research survey . «CoinFaabrik» (28 июня 2016). Дата обращения: 28 сентября 2022. Архивировано 20 января 2022 года.
- Brown D. Generic groups, collision resistance, and ECDSA . «Codes and Cryptography» (26 февраля 2002). Дата обращения: 27 ноября 2008. Архивировано 27 февраля 2012 года.
Ссылки
[править | править код]- Schneier B. The NSA Is Breaking Most Encryption on the Internet (5 сентября 2013).
- Schneier B. The Strange Story of Dual_EC_DRBG (5 сентября 2013).
- Neal Koblitz and Alfred Menezes (1995). — Another Look at Generic Groups. Дата обращения: 27 ноября 2008. Архивировано 27 февраля 2012 года.
- Александрийский Д. Издательство «Наукa», Главная редакция физико-математической литературы (1974). — Арифметика и книга о многоугольных числах. Дата обращения: 2 декабря 2022.
Эта статья входит в число добротных статей русскоязычного раздела Википедии. |