Гостевая статья Цифровые подписи, ECDSA и EdDSA

Ссылка скрыта от гостей

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

• Аутентификация сообщения - доказательство того, что определенный известный отправитель (владелец секретного ключа) создал и подписал сообщение.
• Целостность сообщения - доказательство того, что сообщение не было изменено после подписания.
• Безотказность - подписавшая сторона не может отрицать подписание документа после того, как подпись однажды создана.

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

Цифровые подписи не могут идентифицировать, кто является лицом, созданой подписи. Это может быть решено в сочетании с цифровым сертификатом, который связывает владельца открытого ключа с личностью (человеком, организацией, веб-сайтом или другим). С помощью

Ссылка скрыта от гостей

сообщения связываются с открытыми ключами, а не с цифровыми удостоверениями.

Подписывать сообщения и проверять подписи: как это работает?

Схемы цифровой подписи обычно используют криптосистему с открытым ключом (например, RSA или ECC) и используют пары открытый / закрытый ключи. Сообщение подписывается закрытым ключом, а подпись проверяется соответствующим открытым ключом:

Сообщения подписываются отправителем с использованием закрытого ключа (ключа подписи). Обычно входное сообщение хэшируется, а затем подпись рассчитывается по алгоритму подписи. Большинство алгоритмов подписи выполняют некоторые вычисления с помощью хэша сообщения + ключ подписи таким образом, что результат не может быть вычислен без ключа подписи. Результатом подписания сообщения является цифровая подпись (одно или несколько целых чисел):

signMsg(msg, privKey) 🡒 signature

Подписи сообщений проверяются соответствующим открытым ключом (ключом проверки). Обычно подписанное сообщение хэшируется, и некоторые вычисления выполняются алгоритмом подписи с использованием хеша сообщения + открытый ключ. Результатом подписания является логическое значение (действительная или недействительная подпись):

verifyMsgSignature(msg, signature, pubKey) 🡒 valid / invalid

Подпись сообщения математически гарантирует, что определенное сообщение было подписано определенным (секретным) закрытым ключом, который соответствует определенному (не секретному) открытому ключу. После того, как сообщение подписано, сообщение и подпись не могут быть изменены, и, таким образом, аутентификация и целостность сообщения гарантируются. Любой, кто знает открытый ключ подписавшего сообщения, может проверить подпись. После подписания автор не может отказаться от акта подписания (это известно как отказ от авторства).

Большинство схем подписи работают так, как показано на следующей диаграмме:

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

При проверке подписи сообщение для проверки хэшируется (либо отдельно, либо вместе с открытым ключом), и выполняются некоторые вычисления между хешем сообщения, цифровой подписью и открытым ключом, и, наконец, сравнение решает, действительна ли подпись или нет ,

Цифровые подписи отличаются от КАС(кодов аутентификации сообщений), поскольку MAC создаются и проверяются одним и тем же секретным ключом с использованием симметричного алгоритма, а цифровые подписи создаются ключом подписи и проверяются другим ключом проверки, соответствующим подписи, ключ с использованием асимметричного алгоритма. И подписи, и коды КAС обеспечивают аутентификацию и целостность сообщений.

Схемы и алгоритмы цифровой подписи
Большинство криптосистем с открытым ключом, таких как RSA и ECC, предоставляют безопасные схемы цифровой подписи (алгоритмы подписи). Примерами хорошо известных схем цифровой подписи являются: DSA, ECDSA, EdDSA, подписи RSA, подписи Эль-Гамаля и подписи Шнорра.

Вышеупомянутые схемы подписи основаны на сложности DLP (проблема дискретного логарифма) и ECDLP (проблема дискретного логарифма эллиптической кривой) и являются квантово-разрушаемыми (достаточно мощные квантовые компьютеры могут вычислить ключ подписи на основе подписи сообщения). Квантово-безопасные подписи (такие как SPHINCS, BLISS и XMSS) не используются массово из-за большой длины ключа, длинных подписей и более низкой производительности по сравнению с ECDSA и EdDSA.

Наиболее популярные схемы цифровой подписи (по состоянию на ноябрь 2018 г.): подписи RSA, ECDSA и EdDSA. Давайте дадим некоторые подробности о них, а также некоторые примеры кода.

Подписи RSA
Криптосистема с открытым ключом RSA предоставляет криптографически безопасную схему цифровой подписи (sign + verify), основанную на математике модульных возведения в степень и дискретных логарифмах и сложности задачи целочисленной факторизации (ЗЦФ). Процесс подписи / проверки RSA работает следующим образом:

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

Подписи RSA являются детерминированными (одно и то же сообщение + один и тот же закрытый ключ создают одну и ту же подпись). Недетерминированный вариант RSA-подписей легко создать, добавив во входное сообщение несколько случайных байтов перед подписанием.

Подписи RSA широко используются в современной криптографии, например, для подписания цифровых сертификатов для защиты веб-сайтов. Например (по состоянию на ноябрь 2018 г.) официальный веб-сайт Microsoft использует Sha256RSA для своего цифрового сертификата. Тем не менее, в последнее десятилетие наблюдается тенденция перехода от RSA и DSA к подписям на основе эллиптических кривых (например, ECDSA и EdDSA). Современные криптографы и разработчики предпочитают подписи ECC за их более короткую длину ключа, более короткую подпись, более высокий уровень безопасности (при той же длине ключа) и лучшую производительность.

DSA (алгоритм цифровой подписи)
DSA (алгоритм цифровой подписи) - это криптографически безопасный стандарт для цифровых подписей (подписывание сообщений и проверка подписи), основанный на математике модульных возведений в степень и дискретных логарифмов и сложности проблемы дискретного логарифма (DLP). Это альтернатива RSA и используется вместо RSA из-за ограничений патентов с RSA (до сентября 2000 года). DSA является вариантом схемы подписи Эль-Гамаля. Процесс подписи / проверки DSA работает следующим образом:

• Алгоритм подписи DSA вычисляет хеш сообщения, затем генерирует случайное целое число k и вычисляет подпись (пара целых чисел {r, s}), где r вычисляется из k, а s вычисляется с использованием хеша сообщения + показатель частного ключа + случайное число k. Из-за случайности подпись недетерминирована.
• Алгоритм проверки подписи DSA включает вычисления, основанные на хэше сообщения + показатель открытого ключа + подпись {r, s}.

Случайное значение k (генерируемое при вычислении подписи) открывает потенциальную уязвимость: если два разных сообщения подписаны с использованием одного и того же значения k и одного и того же закрытого ключа, то злоумышленник может вычислить закрытый ключ подписавшего напрямую (см. tintinweb/ecdsa-private-key-recovery).

Вариант детерминированного DSA определен в

Ссылка скрыта от гостей

, который вычисляет случайное число k как HMAC из личного ключа, хэша сообщения и нескольких других параметров. Детерминированный DSA считается более безопасным.

В современной криптографии подписи на основе эллиптических кривых (например, ECDSA и EdDSA) предпочтительнее DSA из-за более короткой длины ключа, более короткой длины подписи, более высокого уровня безопасности (для той же длины ключа) и лучшей производительности.

ECDSA (алгоритм цифровой подписи эллиптической кривой)

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

ECDSA - это адаптация классического алгоритма DSA, который основан на схеме подпись Эль-Гамаля. Точнее, алгоритм ECDSA представляет собой вариант подпись Эль-Гамаля с некоторыми изменениями и оптимизациями для обработки представления элементов группы (точек эллиптической кривой). Как и любой другой криптоалгоритм эллиптической кривой, ECDSA использует эллиптическую кривую (например, secp256k1), закрытый ключ (случайное целое число в пределах длины ключа кривой - для подписи сообщений) и открытый ключ (точка EC, вычисляемая из закрытого ключа путем умножения его на точка генератора кривой - для проверки подписей). Процесс подписи / проверки ECDSA работает следующим образом:

• Алгоритм подписания ECDSA вычисляет хэш сообщения, затем генерирует случайное целое число k и вычисляет подпись (пара целых чисел {r, s}), где r вычисляется из k, а s вычисляется с использованием хеша сообщения + закрытый ключ + случайное число k . Из-за случайности подпись недетерминирована.
• Алгоритм проверки подписи ECDSA включает вычисления, основанные на хэше сообщения + открытый ключ + подпись {r, s}.

Случайное значение k (генерируемое при вычислении подписи) открывает потенциальную уязвимость: если два разных сообщения подписаны с использованием одного и того же значения k и одного и того же закрытого ключа, то злоумышленник может вычислить закрытый ключ подписавшего напрямую (см. tintinweb/ecdsa-private-key-recovery).

Вариант детерминированного ECDSA определен в

Ссылка скрыта от гостей

, который вычисляет случайное число k как HMAC из закрытого ключа + хеш сообщения + несколько других параметров. Детерминированный ECDSA считается более безопасным.

Подписи ECDSA являются наиболее широко используемым алгоритмом подписи, который используется миллионами каждый день (по состоянию на ноябрь 2018 года). Например, цифровые сертификаты на веб-сайтах Amazon подписываются схемой подписи Sha256ECDSA

EdDSA (алгоритм цифровой подписи Эдвардса)
EdDSA (алгоритм цифровой подписи кривой Эдвардса) - это быстрый алгоритм цифровой подписи, использующий эллиптические кривые в форме Эдвардса (например,

Ссылка скрыта от гостей

и

Ссылка скрыта от гостей

), детерминированный вариант схемы подписи Шнорра, разработанный командой известного криптографа. Даниэль Бернштейн.

EdDSA является более простым, чем ECDSA, более безопасным, чем ECDSA, и предназначен для работы быстрее, чем ECDSA (для кривых с сопоставимой длиной ключа). Как и ECDSA, схема подписей EdDSA основывается на сложности задачи ECDLP (проблема дискретного логарифма с эллиптической кривой) в плане надежности.

Алгоритм подписи EdDSA работает с эллиптическими кривыми Эдвардса, такими как Curve25519 и Curve448, которые высоко оптимизированы для производительности и безопасности. Показано, что подписи Ed25519 обычно быстрее, чем традиционные подписи ECDSA по кривым с сопоставимой длиной ключа. Тем не менее, конкурс производительности является спорным. Процесс подписи / проверки EdDSA работает следующим образом:

• Алгоритм подписи EdDSA генерирует детерминированное (не случайное) целое число r (вычисляется путем хеширования сообщения и хэша секретного ключа), а затем вычисляет подпись {Rs, s}, где Rs вычисляется из r, а s вычисляется из хеш (сообщение + открытый ключ, полученный из частного + число r) + закрытый ключ. Подпись является детерминированной (одно и то же сообщение, подписанное одним и тем же ключом, всегда дает одну и ту же подпись).
• Алгоритм проверки подписи EdDSA включает вычисления эллиптической кривой на основе сообщения (хешированного вместе с открытым ключом и точкой EC Rs из подписи) + открытый ключ + число s из подписи {Rs, s}.

По своей сути подписи EdDSA являются детерминированными (что повышает их безопасность). Недетерминированный вариант EdDSA-подписей легко создать, добавив во входное сообщение несколько случайных байтов перед подписанием.

Краткое сравнение между подписей EdDSA Ed25519 и ECDSA secp256k приведено ниже:

Современные разработчики часто используют подписи Ed25519 вместо 256-битных кривых ECDSA, потому что схема подписи EdDSA-Ed25519 использует ключи, которые умещаются в 32 байта (64 шестнадцатеричных цифры), подписи умещаются в 64 байта (128 шестнадцатеричных цифр), подпись и проверка быстрее и безопасность считается лучше.
Публичные цепочки блоков (например, Биткойн и Эфириум) часто используют подписи ECDSA на основе secp2561, поскольку открытый ключ подписчика (и его адрес цепочки блоков) можно легко восстановить из подписи (вместе с подписанным сообщением), добавив в подпись всего 1 дополнительный бит ,
В общем случае, считается, что подписи EdDSA рекомендуется ECDSA, но это весьма спорно и зависит от случая использования, на кривых, участвующих и многих других параметров.
Другие схемы подписи и алгоритмы
Большинство алгоритмов подписи основаны на общих схемах подписи, таких как подписи Эль-Гамаля и подписи Шнорра.

• Подпись RSA получена из схемы шифрования RSA.
• DSA и ECDSA основаны на схеме подписи ElGamal.
• EdDSA является производной от схемы подписи Шнорра.

Другие схемы подписи включают в себя:

• Ссылка скрыта от гостей
  : схема цифровой подписи с эллиптической кривой (основанная на сложности проблемы ECDLP), слегка упрощенный вариант ECDSA, известный как немецкая версия ECDSA.
• Ссылка скрыта от гостей
  : схема цифровой подписи с эллиптической кривой (основанная на сложности проблемы ECDLP), сложный вариант ECDSA, известный как корейская версия ECDSA. ECKDSA подписывает данное сообщение с помощью закрытого ключа EC вместе с хешем цифрового сертификата подписавшего. Это добавляет идентичность к цифровой подписи, в дополнение к аутентификации сообщения, целостности и невозможности отказа.
• Ссылка скрыта от гостей
  : схема цифровой подписи с эллиптической кривой (основанная на сложности задачи ECDLP), известная как китайский алгоритм цифровой подписи, разработанный Китайской академией наук.
• Ссылка скрыта от гостей
  : схема цифровой подписи с эллиптической кривой (основанная на сложности задачи ECDLP), известная как российский алгоритм цифровой подписи, один из российских стандартных алгоритмов криптографии (называемых алгоритмами ГОСТ).

После краткого обзора самых популярных алгоритмов цифровой подписи давайте познакомимся с техническими подробностями о алгоритмах подписи RSA, ECDSA и EdDSA с примерами кода.

Ссылка скрыта от гостей