Elliptic Curve Digital Signature Algorithm

3 хв читання
20 мовами

ECDSA (Elliptic Curve Digital Signature Algorithm) - алгоритм з відкритим ключем для створення цифрового підпису, аналогічний за своєю будовою DSA, але визначений, на відміну від нього, не над кільцем цілих чисел, а в групі точок еліптичної кривої.

Особливості

Стійкість алгоритму шифрування ґрунтується на задачі дискретного логарифма в групі точок еліптичної кривої. На відміну від задачі простого дискретного логарифма і задачі факторизації цілого числа, не існує субекспоненціального алгоритму для задачі дискретного логарифма в групі точок еліптичної кривої. З цієї причини «сила на один біт ключа» істотно вище в алгоритмі, який використовує еліптичні криві.

Д. Брауном (Daniel R. L. Brown) було доведено, що алгоритм ECDSA не є більш безпечним, ніж DSA. Ним було сформульовано обмеження безпеки для ECDSA, яке призвело до наступного висновку:

«Якщо група еліптичної кривої може бути змодельована основною групою і її хеш-функція задовільняє певні обґрунтовані припущення, то ECDSA стійка до атаки на основі підібраного відкритого тексту з існуючої фальсифікацією.»

Алгоритм ECDSA в 1999 р був прийнятий як стандарт ANSI, в 2000 р - як стандарт IEEE і NIST. Також в 1998 р алгоритм був прийнятий стандартом ISO. Незважаючи на те, що стандарти ЕЦП створені зовсім недавно і знаходяться на етапі вдосконалення, одним з найбільш перспективних з них на сьогоднішній день є ANSI X9.62 ECDSA від 1999 - DSA для еліптичних кривих.

Вибір параметрів

Для підписування повідомлень необхідна пара ключів - відкритий і закритий. При цьому закритий ключ повинен бути відомий тільки тому, хто підписує повідомлення, а відкритий - будь-кому хто бажає перевірити справжність повідомлення. Також загальнодоступними є параметри самого алгоритму.

Параметри алгоритму

Вибір хеш-функції $H(x)$ . Для використання алгоритму необхідно, щоб повідомлення, яке підписується, було числом. Хеш-функція повинна перетворити будь-яке повідомлення в послідовність бітів, які можна потім перетворити в число.
Вибір великого простого числа $q$ - порядок однієї з циклічних підгруп групи точок еліптичної кривої. Зауваження: Якщо розмірність цього числа в бітах менше розмірності в бітах значень хеш-функції $H(x)$ то використовуються тільки ліві біти значення хеш-функції.
Простим числом $p$ позначається характеристика поля координат $F_{p}$ .

Генерування ключів ECDSA

Для простоти будемо розглядати еліптичні криві над полем $F_{p}$ , де $F_{p}$ - скінченне просте поле. Причому, якщо необхідно, конструкцію можна легко адаптувати для еліптичних кривих над іншим полем.

Нехай $E$ - еліптична крива, визначена над $F_{p}$ , і $P$ - точка простого порядку $q$ кривої $E$ ( $F_{p}$ ). Крива $E$ і точка $P$ є системними параметрами. Число $p$ - просте. Кожен користувач - умовно назвемо його Аліса - конструює свій ключ за допомогою наступних дій:

Вибирає випадкове або псевдовипадкове ціле число $x$ з інтервалу $[1,q-1]$ .
Обчислює (кратне) $Q=xP$ .

Відкритим ключем користувача Аліси $A$ є точка $Q$ , а закритим - $x$ .

Замість використання $E$ і $P$ в якості глобальних системних параметрів, можна фіксувати тільки поле $F_{p}$ для всіх користувачів і дозволити кожному користувачеві вибирати свою власну еліптичну криву $E$ і точку $P$ $\in$ $E(F_{p})$ . В цьому випадку певне рівняння кривої $E$ , координати точки $P$ , а також порядок $q$ цієї точки $P$ повинні бути включені у відкритий ключ користувача. Якщо поле $F_{p}$ фіксоване, то апаратна і програмна складові можуть бути побудовані так, щоб оптимізувати обчислення в тому полі. У той же час є величезна кількість варіантів вибору еліптичної кривої над полем $F_{p}$ .

Переваги ECDSA перед DSA

ECDSA є дуже привабливим алгоритмом для реалізації цифрового підпису. Найважливішою перевагою ECDSA є можливість його роботи на значно менших полях $F_{p}$ . Як, загалом, з криптографією еліптичної кривої, передбачається, що бітовий розмір відкритого ключа, який буде необхідний для ECDSA, дорівнює подвійному розміру секретного ключа в бітах. Для порівняння, при рівні безпеки в 80 біт (тобто атакуючому необхідно приблизно $2^{80}$ версій підписів для знаходження секретного ключа), розмір відкритого ключа DSA дорівнює, принаймні, 1024 біт, тоді як відкритого ключа ECDSA - 160 біт. З іншого боку розмір підпису однаковий і для DSA, і для ECDSA: $4t$ біт, де $t$ — рівень безпеки, який вимірюється в бітах, тобто - приблизно 320 біт для рівня безпеки в 80 біт.

Практична реалізація

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