В криптографии используется алгоритм цифровой подписи с эллиптической кривой (ECDSA ) предлагает вариант алгоритма цифровой подписи (DSA), который использует криптографию эллиптической кривой.
Содержание
- 1 Размер ключа и подписи
- 2 Генерация подписи алгоритм
- 3 Алгоритм проверки подписи
- 3.1 Корректность алгоритма
- 4 Восстановление открытого ключа
- 4.1 Корректность алгоритма восстановления
- 5 Безопасность
- 6 Реализации
- 7 Пример использования
- 8 См. Также
- 9 Ссылки
- 10 Дополнительная литература
- 11 Внешние ссылки
Размер ключа и подписи
Как и в случае криптографии с эллиптической кривой в целом, бит размер открытого ключа , который считается необходимым для ECDSA, примерно вдвое превышает размер уровня безопасности в битах. Например, при уровне безопасности 80 бит (это означает, что злоумышленнику требуется не более операций, чтобы найти закрытый ключ) размер Открытый ключ ECDSA будет иметь 160 бит, тогда как размер открытого ключа DSA составляет не менее 1024 бит. С другой стороны, размер подписи одинаков для DSA и ECDSA: примерно бит, где - это уровень безопасности, измеряемый в битах, то есть около 320 бит для уровня безопасности 80 бит.
Алгоритм генерации подписи
Предположим, Алиса хочет отправить подписанное сообщение Бобу. Первоначально они должны согласовать параметры кривой . В дополнение к полю и уравнению кривой нам понадобится , базовая точка простого порядка на кривой; - порядок умножения точки .
Параметр | |
---|
CURVE | поле эллиптической кривой и используемое уравнение |
G | базовая точка эллиптической кривой, точка на кривой, которая генерирует подгруппу большого простого порядка n |
n | целочисленный порядок G, означает, что , где - идентификационный элемент. |
| закрытый ключ (выбирается случайным образом) |
| открытый ключ (вычисляется по эллиптической кривой) |
m | сообщение для отправки |
Порядок базовой точки должен быть простым . В самом деле, мы предполагаем, что каждый ненулевой элемент кольца обратим, так что должно быть полем. Это означает, что должен быть простым (см. личность Безу ).
Алиса создает пару ключей, состоящую из целого числа закрытого ключа , случайно выбранного в интервале ; и точка кривой открытого ключа . Мы используем для обозначения умножения точки эллиптической кривой на скаляр.
Чтобы Алиса подписывала сообщение , она выполняет следующие действия:
- Вычислить . (Здесь HASH - это криптографическая хеш-функция, например SHA-2, с преобразованием вывода в целое число.)
- Пусть быть крайними левыми битами , где - длина в битах группового порядка . (Обратите внимание, что может быть больше, чем , но не больше.)
- Выберите a криптографически безопасное случайное целое из .
- Вычислить точку кривой .
- Рассчитать . Если , вернитесь к шагу 3.
- Вычислите . Если , вернитесь к шагу 3.
- Подпись - это пара . (И также является действительной подписью.)
. Согласно стандартным примечаниям, не только требуется, чтобы был секретным, но также важно выбрать другое для разных подписей, в противном случае уравнение на этапе 6 может быть решено для , закрытого ключа: с учетом двух подписей и , используя то же самое неизвестное для разных известных сообщений и , злоумышленник может вычислить и , а поскольку (все операции в этом абзаце выполняются по модулю ) атрибут Акер может найти . Поскольку , злоумышленник теперь может вычислить закрытый ключ. .
Эта ошибка реализации использовалась, например, для извлечения ключа подписи, используемого для PlayStation 3 игровая консоль.
Другой способ утечки закрытых ключей в подписи ECDSA - это когда генерируется неисправным генератор случайных чисел. Такой сбой при генерации случайных чисел привел к потере средств пользователями Android Bitcoin Wallet в августе 2013 года.
Чтобы гарантировать, что уникален для каждого сообщения можно полностью обойти генерацию случайных чисел и сгенерировать детерминированные подписи путем получения как из сообщения, так и из закрытого ключа.
Алгоритм проверки подписи
Чтобы Боб мог аутентифицировать подпись Алисы, он должен иметь копию ее точки кривой открытого ключа . Боб может проверить, что является допустимой точкой кривой следующим образом:
- Убедитесь, что не совпадает с элементом идентичности , и его координаты в противном случае действительны
- Убедитесь, что лежит на кривой
- Убедитесь, что
После этого Боб выполняет следующие шаги :
- Убедитесь, что и являются целыми числами в . В противном случае подпись недействительна.
- Вычислить , где HASH - та же функция, что и при генерации подписи.
- Пусть будет крайние левые биты .
- Вычислить и .
- Вычислить точку кривой . Если , то подпись недействительна.
- Подпись действительно, если , в противном случае недопустимо.
Обратите внимание, что эффективная реализация вычислил бы обратный только один раз. Кроме того, используя трюк Шамира, можно получить сумму двух скалярных умножений можно вычислить быстрее, чем два скалярных умножения, выполненных независимо.
Правильность алгоритма
Не сразу очевидно, почему проверка даже работает правильно. Чтобы понять, почему, обозначим как точку кривой, вычисленную на шаге 5 проверки,
Из определения открытого ключа как ,
Потому что Скалярное умножение на эллиптической кривой распределяется по сложению,
Расширяя определение и из шага проверки 4,
Сбор общий термин ,
Расширение определения из шага подписи 6,
Поскольку обратное к обратному элементу является исходным элементом, а произведение обратного элемента и элемента является тождеством, мы остаемся с
Из определения , это этап проверки 6.
Это показывает только то, что правильно подписанное сообщение будет правильно проверено; многие другие свойства необходимы для безопасного алгоритма подписи.
Восстановление открытого ключа
Имеется сообщение и подпись Алисы в этом сообщении, Боб может (потенциально) восстановить открытый ключ Алисы:
- Убедитесь, что и - целые числа в . В противном случае подпись недействительна.
- Вычислить точку кривой где - одно из , , и т. д. (при условии, что не слишком велик для элемента поля) и - такое значение, которое удовлетворяет уравнению кривой. Обратите внимание, что может быть несколько точек кривой, удовлетворяющих этим условиям, и каждое различное значение приводит к отдельному восстановленному ключу.
- Вычислить , где HASH - та же функция, которая используется при генерации подписи.
- Пусть быть крайние левые биты .
- Calculate и .
- Вычислить точку кривой .
- подпись действительна, если , соответствует открытому ключу Алисы.
- Подпись недействительна, если все возможные очков пробовали, но не найдено ни одного Открытый ключ Алисы.
Обратите внимание, что недействительная подпись или подпись из другого сообщения приведет к восстановлению неверного открытого ключа. Алгоритм восстановления может использоваться для проверки действительности подписи только в том случае, если заранее известен открытый ключ подписывающей стороны (или его хэш).
Правильность алгоритма восстановления
Начните с определения из шага восстановления 6,
Из определения из шага 4 подписания,
Поскольку скалярное умножение эллиптической кривой распределяется по сложению,
Расширяя определение и из шага восстановления 5,
Расширение определение из шага подписи 6,
Поскольку произведение обратный элемент, и элемент является тождественным, у нас остается
Первый и второй члены компенсируют друг друга,
Из определения , это Открытый ключ Алисы.
Это показывает, что правильно подписанное сообщение восстановит правильный открытый ключ при условии, что дополнительная информация была предоставлена для однозначного вычисления точки кривой из значения подписи .
Security
В декабре 2010 года группа, называющая себя fail0verflow, объявила о восстановлении Закрытый ключ ECDSA, используемый Sony для подписи программного обеспечения для игровой консоли PlayStation 3. Однако эта атака сработала только потому, что Sony неправильно реализовала алгоритм, потому что был статическим, а не случайным. Как указано в разделе Алгоритм генерации подписи выше, это делает разрешимым, а весь алгоритм бесполезным.
29 марта 2011 года два исследователя опубликовали статью IACR, демонстрирующую, что можно получить закрытый ключ TLS сервера, используя OpenSSL, который аутентифицируется с помощью Elliptic Curves DSA через двоичный файл. поле через синхронизирующую атаку. Уязвимость была исправлена в OpenSSL 1.0.0e.
В августе 2013 года было обнаружено, что ошибки в некоторых реализациях Java класса SecureRandom иногда приводили к конфликтам в . Это позволило хакерам восстанавливать закрытые ключи, давая им такой же контроль над транзакциями биткойнов, как и у законных владельцев ключей, используя тот же эксплойт, который использовался для раскрытия ключа подписи PS3 в некоторых реализациях приложений Android, использующих Java. и полагаться на ECDSA для аутентификации транзакций.
Эту проблему можно предотвратить с помощью непредсказуемой генерации , например, детерминированной процедуры, описанной в RFC 6979.
Проблемы
В отношении ECDSA существуют проблемы двух видов:
- Политические проблемы: надежность кривых, созданных NIST, подвергается сомнению после того, как выяснилось, что NSA охотно вставляет бэкдоры в программное обеспечение, компоненты оборудования и опубликованные стандарты; известные криптографы выразили сомнения относительно того, как были построены кривые NIST, и добровольное заражение уже было доказано в прошлом.. Тем не менее, доказательства того, что названные кривые NIST используют редкую слабость, пока отсутствуют.
- Технические проблемы: сложность правильной реализации стандарта, его медлительность и недостатки конструкции, которые снижают безопасность в недостаточно защищенных реализациях Dual_EC_DRBG генератора случайных чисел.
Обе эти проблемы резюмированы в libssh curve25519 Введение.
Реализации
Ниже приведен список криптографических библиотек, которые обеспечивают поддержку ECDSA:
Пример использования
Wikipedia.org использует ECDSA в наборе шифров TLS для аутентификации в веб-браузеры, что показано в следующей сокращенной расшифровке.
$ date среда, 4 марта 10:24:52 EST 2020 $ openssl s_client -connect wikipedia.org:443 # в приведенных ниже выводах для краткости указаны УДАЛЕНИЯ CONNECTED (00000003) depth = 2 O = Digital Signature Trust Co., CN = DST Корневой CA X3 verify return: 1 depth = 1 C = US, O = Let's Encrypt, CN = Let's Encrypt Authority X3 verify return: 1 depth = 0 CN = *.wikipedia.org verify return: 1 --- Цепочка сертификатов 0 с : / CN = *. Wikipedia.org i: / C = US / O = Let's Encrypt / CN = Let's Encrypt Authority X3 1 с: / C = US / O = Let's Encrypt / CN = Let's Encrypt Authority X3 i: / O = Digital Signature Trust Co./CN=DST Корневой CA X3 --- Сертификат сервера ----- НАЧАЛО СЕРТИФИКАТА ----- MIIHOTCCBiGgAwIBAgISA4srJU6bpT7xpINN6bbGO2 / mMA0GCSqGSIb3DQEBCwUA... много строк DELETEDKzpJTJDWXWUA... КОНЕЦ СЕРТИФИКАТА ----- subject = / CN = *. Wikipedia.org Issueer = / C = US / O = Let's Encrypt / CN = Let's Encrypt Authority X3 --- Не отправлены имена CA сертификатов клиента Дайджест подписи однорангового узла: SHA256 Server Временный ключ: ECDH, P-256, 256 бит --- рукопожатие SSL прочитало 3353 байта s и записано 431 байт --- Новый, TLSv1 / SSLv3, Cipher - ECDHE-ECDSA-AES256-GCM-SHA384 Открытый ключ сервера - 256 бит Поддерживается безопасное повторное согласование Сжатие: НЕТ Расширение: НЕТ Нет согласованного ALPN SSL-сеанс: Протокол: TLSv1.2 Cipher: ECDHE-ECDSA-AES256-GCM-SHA384 ID сеанса:... DELETED... Session-ID-ctx: Master-Key:... DELETED... Key-Arg: Нет Идентификатор PSK: Нет Подсказка идентификатора PSK: Нет Имя пользователя SRP: Нет Время начала: 1583335210 Тайм-аут: 300 (сек) Проверить код возврата: 0 (ок) --- ВЫПОЛНЕНО
См. Также
Ссылки
Дополнительная литература
- Аккредитованный комитет по стандартам X9, Американский национальный стандарт X9.62-2005, Криптография с открытым ключом для индустрии финансовых услуг, Алгоритм цифровой подписи с эллиптической кривой (ECDSA)), 16 ноября 2005 г.
- Certicom Research, Стандарты эффективной криптографии, SEC 1: Elliptic Curve Cryptography, Version 2.0, 21 мая 2009 г.
- Лопес, Дж. И Дахаб, Р. Ан Оверви ew of Elliptic Curve Cryptography, Technical Report IC-00-10, State University of Campinas, 2000.
- Дэниэл Дж. Бернштейн, алгоритм возведения в степень Пиппенгера, 2002.
- Дэниел Р.Л. Браун, Общие группы, сопротивление столкновениям и ECDSA, Дизайн, коды и криптография, 35, 119–152, 2005. Версия ePrint
- Ян Ф. Блейк, Гадил Серусси и Найджел Смарт, редакторы, Advances in Elliptic Curve Cryptography, London Mathematical Society Lecture Note Series 317, Cambridge University Press, 2005.
- Hankerson, D.; Vanstone, S. ; Менезес А. (2004). Руководство по криптографии с эллиптическими кривыми. Springer Professional Computing. Нью-Йорк: Спрингер. doi : 10.1007 / b97644. ISBN 0-387-95273-X.
Внешние ссылки