ECDSA

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

ECDSA (Elliptic Curve Digital Signature Algorithm) — алгоритм с открытым ключом для создания цифровой подписи, аналогичный, по своему строению, DSA, но определённый, в отличие от него, не над полем целых чисел, а в группе точек эллиптической кривой.

Особенности[править | править исходный текст]

Стойкость алгоритма шифрования основывается на проблеме дискретного логарифма в группе точек эллиптической кривой. В отличие от проблемы простого дискретного логарифма и проблемы факторизации целого числа, не существует субэкспонециального алгоритма для проблемы дискретного логарифма в группе точек эллиптической кривой. По этой причине «сила на один бит ключа» существенно выше в алгоритме, который использует эллиптические кривые.[1]

Д. Брауном (Daniel R. L. Brown) было доказано, что алгоритм ECDSA не является более безопасным, чем DSA. Им было сформулировано ограничение безопасности для ECDSA, которое привело к следующему заключению:

«Если группа эллиптической кривой может быть смоделирована основной группой и ее хэш-функция удовлетворяет определенному обоснованному предположению, то ECDSA устойчива к chosen-message атаке с существующей фальсификацией.»[2]

Алгоритм ECDSA в 1999 г. был принят, как стандарт ANSI, в 2000 г. — как стандарт IEEE и NIST. Также в 1998 г. алгоритм был принят стандартом ISO. Несмотря на то, что стандарты ЭЦП созданы совсем недавно и находятся на этапе совершенствования, одним наиболее перспективных из них на сегодняшний день является ANSI X9.62 ECDSA от 1999 — DSA для эллиптических кривых.

Выбор параметров[править | править исходный текст]

Для подписывания сообщений необходима пара ключей — открытый и закрытый. При этом закрытый ключ должен быть известен только тому, кто подписывает сообщения, а открытый — любому желающему проверить подлинность сообщения. Также общедоступными являются параметры самого алгоритма.

Параметры алгоритма[править | править исходный текст]

  1. Выбор хэш-функции H(x). Для использования алгоритма необходимо, чтобы подписываемое сообщение являлось числом. Хеш-функция должна преобразовать любое сообщение в последовательность битов, которые можно потом преобразовать в число.
  2. Выбор большого простого числа q — порядок одной из циклических подгрупп группы точек эллиптической кривой.
    Замечание: Если размерность этого числа в битах меньше размерности в битах значений хэш-функции H(x) то используются только левые биты значения хэш-функции.
  3. Простым числом p обозначается характеристика поля координат F_p.

Генерирование ключей ECDSA[править | править исходный текст]

Для простоты будем рассматривать эллиптические кривые над полем F_p, где F_p — конечное простое поле. Причем, если необходимо, конструкцию можно легко адаптировать для эллиптических кривых над другим полем.

Пусть E — эллиптическая кривая, определенная над F_p, и P — точка простого порядка q кривой E(F_p). Кривая E и точка P являются системными параметрами. Число p — простое. Каждый пользователь — условно назовём его Алиса — конструирует свой ключ посредством следующих действий:

  1. Выбирает случайное или псевдослучайное целое число x из интервала [1,q-1].
  2. Вычисляет произведение (кратное) Q = x·P.

Открытым ключом пользователя Алисы A является точка Q, а закрытым — x.

Вместо использования E и P в качестве глобальных системных параметров, можно фиксировать только поле F_p для всех пользователей и позволить каждому пользователю выбирать свою собственную эллиптическую кривую  E и точку P\in E(F_p). В этом случае определенное уравнение кривой E, координаты точки P, а также порядок q этой точки P должны быть включены в открытый ключ пользователя. Если поле F_p фиксировано, то аппаратная и программная составляющие могут быть построены так, чтобы оптимизировать вычисления в том поле. В то же время имеется огромное количество вариантов выбора эллиптической кривой над полем F_p.

Вычисление цифровой подписи[править | править исходный текст]

Для того, чтобы подписать какое-либо сообщение, для которого подсчитано значение h хэш-функции H, пользователь A должен сделать следующее:

  1. Выбрать случайное целое число k \in [1, q-1].
  2. Вычислить k\cdot P = (x_1, y_1) и положить в r = x_1\mod q, где r получается из целого числа x_1 между 0 и (p - 1) приведением по модулю q.
    Замечание: если r = 0, то уравнение подписи s = k^{-1}(h + x\cdot r)\mod q не зависит от секретного ключа x, и следовательно, (r,s) не подходит в качестве цифровой подписи. Значит, в случае r = 0 необходимо вернуться к шагу 1.
  3. Вычислить k^{-1}\pmod q и положить s = k^{-1}(h + x\cdot r)\mod q, где h — значение хеш-функции подписываемого сообщения.
    Замечание: если s = 0, то значение s^{-1}\pmod q, нужное для проверки, не существует. Значит, в случае s = 0 необходимо вернуться к шагу 1.

Подписью для сообщения является пара целых чисел (r, s).

Проверка цифровой подписи[править | править исходный текст]

Для того, чтобы проверить подпись пользователя Алисы (r, s) на сообщение, пользователь Борис B должен сделать следующее:

  1. Получить подтвержденную копию открытого ключа Q пользователя А;
  2. Проверить, что числа r и s являются целыми числами из интервала [1, q-1], и вычислить значение хеш-функции h от сообщения;
  3. Вычислить u_1 = s^{-1}h \mod q и u_2 = s^{-1}r \mod q;
  4. Вычислить u_1\cdot P + u_2\cdot Q = (x_0, y_0), и относительно x_0, как целого числа между 0 и (p - 1), положить v = x_0 \mod q;
  5. Принять подпись, если и только если v = r.

Заметим, что, если пользователь Алиса вычислила свою подпись правильно, то u_1P + u_2Q = (u_1 + xu_2)P = (s^{-1}\cdot h\mod q + x\cdot s^{-1}\cdot r\mod q)\cdot P = k\cdot P , так как k = s^{-1}(h + xr)\pmod q , и поэтому v = r.

Для подтверждения публичного ключа Q нужно проделать следующее (O здесь обозначает бесконечно удалённую точку):

  1. Проверить, что Q не равно O и координаты верны;
  2. Проверить, что Q лежит на кривой;
  3. Проверить, что qQ = O;

ECDSA согласно стандарту ANSI X9.62[править | править исходный текст]

Для практического применения алгоритма ECDSA налагают ограничения на поля, в которых определены эллиптические кривые. Более того для избежания некоторых известных атак, ограничения накладываются и на уравнения, задающие эллиптические кривые, и на порядок базовых точек. Для простоты в данном разделе будем рассматривать только конечные F_p.

Требования к эллиптической кривой[править | править исходный текст]

Для того, чтобы избежать известных атак, основанных на проблеме дискретного логарифма в группе точек эллиптической кривой, необходимо, чтобы число точек эллиптической кривой E делилось на достаточно большое простое число n . Стандарт ANSI X9.62 требует n > 2^{160}. Уравнение эллиптической кривой строится специфическим образом, используя случайные/псевдослучайные коэффициенты.

Главными параметрами при построении эллиптической кривой являются:

  1. размерность поля p, где p явлется простым числом;
  2. два элемента поля F_p — a и b, определенные уравнением эллиптической кривой E, где E имеет вид:
    y^2 = x^3 + ax + b,
    где a, b \in F_p, и 4a^3 + 27b^2 \not\equiv 0 \pmod p.
  3. два элемента поля F_p — x_G и y_G, которые определяют конечную точку G = (x_G, y_G) — генератор группы E(F_p)
  4. порядок q точки G, где q > 2^{160} и q > 4 \sqrt{p}
  5. сомножитель h = #E(F_p)/q, где обозначение #E(F_p) означает порядок группы точек эллиптической кривой E(F_p).

Генерация главных параметров[править | править исходный текст]

Один из способом генерирования криптографически надежных параметров заключается в следующем:

  1. Выбираем коэффициенты a и b специфическим образом используя в вычислениях случайные/псевдослучайные числа. Пусть E — эллиптическая кривая — y^2 = x^3 + ax + b;
  2. Вычисляем N = \#E(F_p);
  3. Проверяем, что N имеет делитель, который является большим простым числом q (q > 2^{160} и q > 4 \sqrt{p}). Если нет, то нужно вернуться на шаг 1.
  4. Проверяем, что q не делит {p^k - 1} для каждого k, 1 \le k \le 100. Если нет, то нужно вернуться на шаг 1;
  5. Проверяем, что q \ne p. Если нет, то нужно вернуть на шаг 1;
  6. Берем случайную точку G' \in E(F_q) и положить G = (N/q)G'. Повторяем до тех пор пока G \ne O.

В 1985 г. Скооф (Schoof) представил алгоритм, работающий за полимиальное время, для подсчета \#E(F_p), число точек эллиптической кривой определенная над полем F_p (p — нечетное простое число). Алгоритм Скоофа является достаточно не эффективным на практике для значений p, которые действительно представляют интерес, то есть p > 2^{160}. В последние несколько лет было проделано много работы по улучшению и ускорению алгоритма Скоофа, сейчас он называется SEA (Schoof-Elkies-Atkin) алгоритм. С такими улучшениями криптографически пригодные эллиптические кривые, определенные над полями, чьи порядки более, чем 2^{200}, могут быть сгенерированы за несколько часов на рабочих станциях.

Преимущества ECDSA перед DSA[править | править исходный текст]

ECDSA является очень привлекательным алгоритмом для реализации ЭЦП. Самым важным преимуществом ECDSA является возможность его работы на значительно меньших полях F_p. Как, в общем, с криптографией эллиптической кривой, предполагается, что битовый размер открытого ключа, который будет необходим для ECDSA, равен двойному размеру секретного ключа в битах. Для сравнения, при уровне безопасности в 80 бит (то есть атакующему необходимо примерно 2^{80} версий подписи для нахождения секретного ключа), размер открытого ключа DSA равен, по крайней мере, 1024 бит, когда как открытого ключа ECDSA — 160 бит. С другой стороны размер подписи одинаков и для DSA, и для ECDSA: 4t бит, где t — уровень безопасности, измеренный в битах, то есть — примерно 320 бит для уровня безопасности в 80 бит.

Практическая реализация[править | править исходный текст]

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

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

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