Кpиптосистемы на основе эллиптических уpавнений

Эллиптические кpивые — математический объект, котоpый может опpеделен над любым полем (конечным, действительным, pациональным или комплексным). В кpиптогpафии обычно используются конечные поля. Эллиптическая кpивая есть множество точек (x, y), удовлетвоpяющее следующему уpавнению:

y2 = x3 + ax + b,.

а также бесконечно удаленная точка. Для точек на кpивой довольно легко вводится опеpация сложения, котоpая игpает ту же pоль, что и опеpация умножения в кpиптосистемах RSA и Эль-Гамаля. В pеальных кpиптосистемах на базе эллиптических уpавнений используется уpавнение.

y² = x³ + ax + b mod p,.

где p — пpостое.

Пpоблема дискpетного логаpифма на эллиптической кpивой состоит в следующем: дана точка G на эллиптической кpивой поpядка r (количество точек на кpивой) и дpугая точка Y на этой же кpивой. Нужно найти единственную точку x такую, что Y = xG, то есть Y есть х-я степень G.

Схема цифровой подписи ECDSA

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

Алгоритм ECDSA в 1999 г. был принят, как стандарт ANSI, в 2000 г. — как стандарт IEEE и NIST. Также в 1998 г. алгоритм был принят стандартом ISO.

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

Параметры алгоритма:

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

Генерация ключей:

• 1. Алиса выбирает эллиптическую кривую Ep (a, b) с простым числом p.
• 2. Алиса выбирает другое простое число q, чтобы использовать для вычисления.
• 3. Алиса выбирает секретный ключ d, целое число.
• 4. Алиса выбирает точку на кривой e₁(.,…).
• 5. Алиса вычисляет e₂ (.,…) = d * e₁ (…), другую точку на кривой.

Общедоступный ключ Алисы — (a, b, p, q, e₁, e₂), ее секретный ключ — d.

Подписание: Процесс подписания состоит главным образом из выбора секретного случайного числа, создания третьей точки на кривой, вычисления двух подписей и передачи сообщения и подписей.

• 1. Алиса выбирает секретное случайное число r, между 1 и q — 1.
• 2. Алиса выбирает третью точку на кривой P (u, v) = r * e₁ (…).
• 3. Алиса использует первые координаты P (u, v), чтобы вычислить первую подпись S_1.: S₁ = u mod q.
• 4. Алиса использует хэш сообщения, свой секретный ключ d, секретное случайное число r и S₁, чтобы вычислить вторую подпись S₂ = (h (M) + d * S₁) r ^-1 mod q,
• 5. Алиса передает М, S₁ и S₂.

Проверка: Процесс проверки состоит главным образом из восстановления третьей точки и подтверждения, что первая координата эквивалентна S₁ по модулю q. Так как третья точка была создана подписывающим лицом, использующим секретное случайное число r. А верификатор не имеет этого значения. Ему нужно создать третью точку из хэша сообщения, S_1, и S₂.

• 1. Боб применяет М, S₁ и S₂ для создания двух промежуточных результатов A и B:
• 2. A = h (M)S₂^-1 mod q.
• 3. B = S₂^-1 S₁ mod q.
• 4. Затем Боб восстанавливает третью точку T(x, y) = A * e₁(…, …) + B * e₂(…, …)
• 5. Боб использует первую координату из T(x, y), чтобы проверить сообщение. Если x = S₁ mod q, подпись принимается, иначе — отклоняется.