Эта статья входит в число добротных статей

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. Верните .

Алгоритм генерации цифровой подписи[править | править код]

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

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

Ввод: Основные параметры эллиптической кривой , закрытый ключ , сообщение .

Вывод: Подпись .

Шаг 1. Выберите случайное или псевдослучайное целое число .

Шаг 2. Вычислите координаты точки .

Шаг 3. Вычислите . Если , тогда перейдите к шагу 1.

Шаг 4. Вычислите .

Шаг 5. Вычислите . Если , тогда перейдите к шагу 1.

Шаг 6. Верните .

Алгоритм проверки цифровой подписи[править | править код]

Чтобы проверить подпись Алисы сообщения , Боб получает аутентичную копию её основных параметров кривой и связанный с ними открытый ключ [13]:.

Ввод: Основные параметры эллиптической кривой , открытый ключ , сообщение , подпись .

Вывод: Решение о принятии или отклонении подписи.

Шаг 1. Проверьте, что - целые числа, принадлежащие . Если какая-либо проверка не удалась, то вернуть "Отклонить".

Шаг 2. Вычислите .

Шаг 3. Вычислите .

Шаг 4. Вычислите и .

Шаг 5. Вычислите координаты точки .

Шаг 6. Если , то вернуть "Отклонить". Иначе вычислить .

Шаг 7. Если , то вернуть "Принять", иначе "Отклонить"

Пример работы 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].

Примечания[править | править код]

  1. Diophantus Arithmetic, с. 221.
  2. 1 2 Liao H. Z., Shen Y. Y, с. 109—110.
  3. Liao H. Z., Shen Y. Y, с. 110.
  4. Mayer H.
  5. Lopez J., Dahab R, с. 12.
  6. Hankerson et al, с. 172.
  7. Hankerson et al, с. 173-174.
  8. Hankerson et al, Алгоритм генерации основных параметров, с. 174.
  9. Hankerson et al, с. 175-178.
  10. Hankerson et al, Алгоритм генерации ключевой пары, с. 180.
  11. Hankerson et al, Алгоритм проверки открытого ключа, с. 181.
  12. Liao H. Z., Shen Y. Y, Алгоритм генерации цифровой подписи, с. 116-117.
  13. Liao H. Z., Shen Y. Y, Алгоритм проверки цифровой подписи, с. 117.
  14. Liao H. Z., Shen Y. Y, Доказательство работы алгоритма проверки цифровой подписи, с. 117.
  15. Liao H. Z., Shen Y. Y, с. 118—119.
  16. Brown D.
  17. Коржев В.
  18. Hankerson et al, Предисловие, с. xix.
  19. Lopez J., Dahab R, Аннотация.
  20. Schneier B. The NSA Is Breaking Most Encryption on the Internet.
  21. Schneier B. The Strange Story of Dual_EC_DRBG.
  22. Lopez J., Dahab R.

Литература[править | править код]

Ссылки[править | править код]