Русская Википедия:ECDSA
ECDSA (Elliptic Curve Digital Signature Algorithm) — алгоритм с открытым ключом, использующийся для построения и проверки электронной цифровой подписи при помощи криптографии на эллиптических кривых.
Алгоритм достаточно популярен в области электронных цифровых подписей из-за сложности задачи, на которой основано вычисление закрытого ключа из открытого. ECDSA принят различными организациями в качестве стандарта. Алгоритм состоит из четырёх частей: генерация основных параметров, генерация ключевой пары, создание и проверка цифровой подписи. В общем случае, считается достаточно безопасным (для соответствующих уровней криптостойкостей), а также имеет реализации в множестве криптографических библиотек.
История
Эллиптические кривые, в качестве математического понятия, изучаются уже достаточно давно. Например, ещё у древнегреческого математика Диофанта в III веке нашей эры в труде «Арифметика» были задачи, которые сводились к нахождению рациональных точек на эллиптической кривойШаблон:Sfn. Однако, их применение для реальных задач, в частности, для области криптографии, было неизвестно до конца XX века. В 1985 году Виктор Миллер и Нил Коблиц предложили использование эллиптических кривых для криптографииШаблон:Sfn.
В 1991 году Национальным институтом стандартов и технологий (NIST) был разработан DSA, построенный на идее использования проблемы дискретного логарифма. Вскоре после этого, NIST запросил публичные комментарии по поводу своего предложения о схемах цифровой подписи. Воодушевившись данной идеей, Скотт Ванстоун в статье «Responses to NIST’s proposal» предложил аналог алгоритму цифровой подписи, использующий криптографию на эллиптических кривых (ECDSA)Шаблон:Sfn.
В период с 1998-2000 гг. ECDSA был принят различными организациями, как стандарт (ISO 14888-3, ANSI X9.62, IEEE 1363—2000, FIPS 186-2)Шаблон:Sfn.
Применение
Область применения ECDSA ограничивается областью применения электронной цифровой подписи. Другими словами, в тех местах, где может потребоваться проверка целостности и авторства сообщения. Например, использование в криптовалютных транзакциях (в биткойне и эфириуме) для обеспечения того, чтобы средства могли быть потрачены только их законными владельцамиШаблон:Sfn.
Основные параметры эллиптической кривой
Основными параметрами (англ. domain parameters) <math display="inline">D = (q, FR, a, b, G, n, h)</math> эллиптической кривой над конечным полем <math>\mathbb{F}_q</math> называется совокупность следующих величинШаблон:Sfn:
- Порядок конечного поля <math>q</math> (например, простое конечное поле <math>\mathbb{F}_p</math> при <math display="inline">q = p</math>, где <math display="inline">p > 3</math> и является простым числом).
- <math display="inline">FR</math> (Field Representation) — индикатор, использующийся для представления элементов, принадлежащих полю <math>\mathbb{F}_q</math>.
- Два элемента поля <math>a, b \in \mathbb{F}_q</math>, задающие коэффициенты уравнения эллиптической кривой <math>E</math> над полем <math>\mathbb{F}_q</math> (например, <math>y^2 = x^3 + ax + b</math> при <math>q = p > 3</math>).
- Базовая точка <math display="inline">G = (x_G, y_G) \in E(\mathbb{F}_q)</math>, имеющая простой порядок <math>n</math>.
- Целое число <math display="inline">h</math>, являющееся кофактором <math display="inline">h = \#E(\mathbb{F}_q)/n</math>, где <math display="inline">\#E(\mathbb{F}_q)
</math> — порядок кривой, численно совпадающий с числом точек в <math display="inline">E(\mathbb{F}_q) </math>. Параметры должны быть выбраны таким образом, чтобы эллиптическая кривая, определённая над конечным полем <math>\mathbb{F}_q</math> была устойчива ко всем известным атакам, применимым к ECDLP. Помимо этого, могут быть и другие ограничения, связанные с соображениями безопасности или реализации. Как правило, основные параметры являются общими для группы сущностей, однако в некоторых приложениях (реализациях), они могут быть специфичными для каждого конкретного пользователяШаблон:Sfn
ECDSA по стандарту ANSI X9.62
Для практического применения ECDSA налагают ограничения на поляШаблон:Sfn, в которых определены эллиптические кривые. Для простоты, рассмотрим случай реализации алгоритмов, когда <math>\mathbb{F}_q</math> — простое конечное поле, (для других полей — аналогично), тогда наше эллиптическое уравнение принимает вид <math display="inline">y^2 = x^3 + ax +b</math>.
Алгоритм генерации основных параметров
Для того, чтобы избежать известных атак, основанных на проблеме дискретного логарифма в группе точек эллиптической кривой, необходимо, чтобы число точек эллиптической кривой <math>E</math> делилось на достаточно большое простое число <math>n </math>. Стандарт ANSI X9.62 требует <math>n > 2^{160}</math>. Предлагается следующий алгоритмШаблон:Sfn: Шаблон:Рамка Ввод: Порядок поля <math>q</math>, индикатор представления поля <math>FR</math> для <math display="inline">\mathbb{F}_q</math>, <math>L</math> - уровень безопасности: <math display="inline">160 \leqslant L \leqslant [\log_2q]</math> и <math display="inline">2^L \geqslant 4 \sqrt q</math>.
Вывод: Основные параметры эллиптической кривой <math display="inline">D = (q, FR, a, b, G, n, h)</math>. Шаблон:Конец рамки Шаблон:Рамка Шаг 1. Выберите верифицировано случайным образом элементы <math display="inline">a, b \in \mathbb{F}_q</math>, удовлетворяющие условию <math>4a^3 + 27b^2 \not\equiv 0 \bmod q</math>.
Шаг 2. <math display="inline">N := \#E(\mathbb{F}_q)</math>, порядок кривой можно вычислить при помощи алгоритма SEA.
Шаг 3. Проверьте, что <math display="inline">N \bmod n = 0</math> при большом простом числе <math>n \geqslant 2^L</math>. Если нет, тогда перейдите к шагу 1.
Шаг 4. Проверьте, что <math>q^k - 1 \bmod n = 0</math> <math>\forall k \in [1, 20] </math>. Если нет, тогда перейдите к шагу 1.
Шаг 5. Проверьте, что <math>n \neq q</math>. Если нет, тогда перейдите к шагу 1.
Шаг 6. <math>h := N / n</math>.
Шаг 7. Выберите произвольную точку <math display="inline">G^' \in E(\mathbb{F}_q)</math> и задайте <math display="inline">G := hG^'</math>. Повторяйте, пока <math display="inline">G \neq \mathcal{O}</math>, где <math>\mathcal{O}</math> - бесконечно удалённая точка
Шаг 8. Верните <math display="inline">(q, FR, a, b, G, n, h)</math> Шаблон:Конец рамки Алгоритмы верификации случайным образом дают гарантию того, что эллиптическая кривая над конечным полем была сгенерирована абсолютно случайноШаблон:Sfn.
Алгоритм генерации ключевой пары
Будем рассматривать обмен сообщениями между Алисой и Бобом. Предварительно используя алгоритм генерации основных параметров, Алиса получает свои основные параметры эллиптической кривой. Используя следующую последовательность действий, Алиса сгенерирует себе открытый и закрытый ключШаблон:Sfn. Шаблон:Рамка Ввод: Основные параметры эллиптической кривой <math display="inline">D</math>.
Вывод: Открытый ключ - <math>Q</math>, закрытый ключ - <math>d</math>. Шаблон:Конец рамки Шаблон:Рамка Шаг 1. Выберите случайное или псевдослучайное целое число <math>d \in [1, n-1]</math>.
Шаг 2. Вычислите координаты точки на эллиптической кривой <math>Q = dG</math>.
Шаг 3. Верните <math>(Q, d)</math>. Шаблон:Конец рамки Шаблон:Выпадающий список
Алгоритм генерации цифровой подписи
Алиса, обладающая основными параметрами кривой <math>D</math> и закрытым ключом <math>d</math> хочет подписать сообщение <math>m</math>, для этого она должна сгенерировать подпись <math>(r,s)</math>Шаблон:Sfn.
В дальнейшем <math>\mathcal{H}</math> обозначает криптографическую хэш-функцию, выходное значение которой имеют битовую длину не более <math>n</math> (если это условие не выполняется, то выходное значение <math>\mathcal{H}</math> может быть усечено). Предполагается, что мы работаем со выходом функции, уже преобразованным в целое число. Шаблон:Рамка Ввод: Основные параметры эллиптической кривой <math display="inline">D</math>, закрытый ключ <math>d</math>, сообщение <math>m</math>.
Вывод: Подпись <math>(r,s)</math>. Шаблон:Конец рамки Шаблон:Рамка Шаг 1. Выберите случайное или псевдослучайное целое число <math>k \in [1, n-1]</math>.
Шаг 2. Вычислите координаты точки <math>kG = (x_1, y_1)</math>.
Шаг 3. Вычислите <math>r = x_1 \bmod n</math>. Если <math>r = 0</math>, тогда перейдите к шагу 1.
Шаг 4. Вычислите <math>e = \mathcal{H}(m)</math>.
Шаг 5. Вычислите <math>s = k^{-1}(e + dr) \bmod n</math>. Если <math>s = 0</math>, тогда перейдите к шагу 1.
Шаг 6. Верните <math>(r,s)</math>. Шаблон:Конец рамки
Алгоритм проверки цифровой подписи
Чтобы проверить подпись Алисы <math>(r, s)</math> сообщения <math>m</math>, Боб получает аутентичную копию её основных параметров кривой <math>D</math> и связанный с ними открытый ключ <math>Q</math>Шаблон:Sfn:. Шаблон:Рамка Ввод: Основные параметры эллиптической кривой <math display="inline">D</math>, открытый ключ <math>Q</math>, сообщение <math>m</math>, подпись <math>(r,s)</math>.
Вывод: Решение о принятии или отклонении подписи. Шаблон:Конец рамки Шаблон:Рамка Шаг 1. Проверьте, что <math>r, s</math> - целые числа, принадлежащие <math>[1,n -1]</math>. Если какая-либо проверка не удалась, то вернуть "Отклонить".
Шаг 2. Вычислите <math>e = \mathcal{H}(m)</math>.
Шаг 3. Вычислите <math>w = s^{-1} \bmod n</math>.
Шаг 4. Вычислите <math>u_1 = ew \bmod n</math> и <math>u_2 = rw \bmod n</math>.
Шаг 5. Вычислите координаты точки <math>X = (x_2, y_2) = u_1G +u_2Q</math>.
Шаг 6. Если <math>X = \mathcal{O}</math>, то вернуть "Отклонить". Иначе вычислить <math>v = x_2 \bmod n</math>.
Шаг 7. Если <math>v = r</math>, то вернуть "Принять", иначе "Отклонить" Шаблон:Конец рамки Шаблон:Выпадающий список
Пример работы ECDSA
В данном примереШаблон:Sfn, будут описываться только значащие вычислительные шаги в алгоритмах, считая, что все проверки могут быть сделаны без текстового описания.
1. Используя алгоритм генерации основных параметров, получим следующие значения: <math>p = 114973</math>, эллиптическая кривая <math>E: y^2 = x^3 - 3x + 69424</math>, и базовая точка <math>G = (11570,42257)</math> с порядком <math>n = 114467</math>.
2. Сгенерируем пару ключей, в соответствие с алгоритмом генерации ключевой пары: Шаблон:Рамка Шаг 1. Выбираем <math>d = 86109 \in [1, 114466]</math>.
Шаг 2. Вычисляем координаты точки <math>Q = dG = (6345,28549)</math>. Шаблон:Конец рамки 3. Алгоритмом генерации цифровой подписи, подпишем сообщение, заданное в виде текста <math display="inline">m = worldof</math> с значением хэш-функции <math>e = \mathcal{H}(m) = 1789679805</math>. Шаблон:Рамка Шаг 1. Выбираем <math>k = 84430 \in [1, 114466]</math>.
Шаг 2. Вычисляем координаты точки <math>kG = (x_1, y_1) = (31167, 10585)</math>.
Шаг 3. Вычисляем <math display="inline">r = x_1 \bmod n = 31167 \bmod 114973 = 31167</math>.
Шаг 4. Вычисляем <math display="inline">s = k^{-1}(e + dr) \bmod n = 84430^{-1} (1789679805 + 86109 \cdot 31167) \bmod 114973 = 82722</math>. Шаблон:Конец рамки 4. Проверим достоверность подписи <math>(r, s)</math> для сообщения <math>m</math> с помощью алгоритма проверки цифровой подписи. Шаблон:Рамка Шаг 1. Вычисляем <math>w = s^{-1} \bmod n = 82722^{-1} \bmod 114973 = 83035</math>.
Шаг 2. Вычисляем <math>u_1 = ew \bmod n = 1789679805 \cdot 83035 \bmod 114973 = 71001</math> и <math>u_2 = rw \bmod n = 31167 \cdot 83035 \bmod 114973 = 81909</math>.
Шаг 3. Вычисляем координаты точки <math>X = u_1G + u_2Q = (66931,53304) + (88970,41780) = (31167,31627)</math>.
Шаг 4. Вычислим <math>v = x_2 \bmod n = 31167 \bmod 114973 = 31167</math>.
Шаг 5. Проверяем <math>v = r = 31167</math>. Принимаем подпись. Шаблон:Конец рамки
Безопасность
ECDSA по сравнению c DSA
Д. Брауном (Daniel R. L. Brown) было доказано, что алгоритм ECDSA не является более безопасным, чем DSA. Им было сформулировано ограничение безопасности для ECDSA, которое привело к следующему заключению: «Если группа эллиптической кривой может быть смоделирована основной группой и её хеш-функция удовлетворяет определённому обоснованному предположению, то ECDSA устойчива к атаке на основе подобранного открытого текста с существующей фальсификацией»Шаблон:Sfn.
Математические преимущества
Стойкость алгоритма шифрования основывается на проблеме дискретного логарифма в группе точек эллиптической кривой. В отличие от проблемы простого дискретного логарифма и проблемы факторизации целого числа, не существует субэкспоненциального алгоритма для проблемы дискретного логарифма в группе точек эллиптической кривой. По этой причине «сила на один бит ключа» существенно выше в алгоритме, который использует эллиптические кривыеШаблон:Sfn.
Это означает, что в криптографии на эллиптических кривых можно использовать значительно меньшие параметры, чем в других системах с открытыми ключами, таких как RSA и DSA, но с эквивалентным уровнем безопасности. К примеру, битовый размер ключей: 160-битный ключ будет равносилен ключам с 1024-битным модулем в RSA и DSA при сопоставимом уровне безопасности (против известных атак). Преимущества, полученные от меньших размеров параметров (в частности, ключей), включают скорость выполнения алгоритма, эффективное использование энергии, пропускной полосы, памятиШаблон:Sfn. Они особенно важны для приложений на устройствах с ограниченными возможностями, таких как смарт-картыШаблон:Sfn.
Опасения по поводу разработанных алгоритмов
Явной проблемой является отсутствие доверия к некоторым уже разработанным ранее алгоритмамШаблон:Sfn. Например, NIST Special Publication 800-90, содержащая детерминированный генератор случайных битов на эллиптических кривых Dual_EC_DRBG. В самом стандарте содержится набор констант кривой, появление которых в представленном виде не объяснено, Шумоу и Фергюсон показали, что данные постоянные связаны с некоторым случайным набором чисел, работающим как бэкдор, возможно, для целей АНБ, но этому нет никаких достоверных подтвержденийШаблон:Sfn.
Практическая реализация
ECDSA реализован в таких криптографических библиотеках, как OpenSSL, Cryptlib, Crypto++, реализации протоколов GnuTLS, интерфейсе программирования приложений CryptoAPI. Существует и множество других программных реализаций алгоритма электронной цифровой подписи на эллиптических кривых, большинство из которых, в основном, сосредоточено на одном приложении, например, быстрой реализации для одного конкретного конечного поляШаблон:Sfn.
Примечания
Литература
Ссылки
Шаблон:Криптосистемы с открытым ключом Шаблон:Добротная статья
