Elliptic Curve Digital Signature Algorithm

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

Особливості

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Посилання

• Neal Koblitz and Alfred Menezes (1995) [Архівовано 8 серпня 2017 у Wayback Machine.]. — Another Look at Generic Groups.

• Digital Signature Standard; includes info on ECDSA [Архівовано 27 грудня 2016 у Wayback Machine.]

Див. також

Еліптична криптографія

EdDSA

Примітки

1. 08.08.2002. Цифровая подпись. Эллиптические кривые - MorePC.Ru. www.morepc.ru. Архів оригіналу за 31 грудня 2012. Процитовано 14 квітня 2018.
2. http://www.psu.edu/. Архів оригіналу за 27 лютого 2012. {{cite web}}: Зовнішнє посилання в |title= (довідка)