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. Вибір хеш-функції . Для використання алгоритму необхідно, щоб повідомлення, яке підписується, було числом. Хеш-функція повинна перетворити будь-яке повідомлення в послідовність бітів, які можна потім перетворити в число.
  2. Вибір великого простого числа - порядок однієї з циклічних підгруп групи точок еліптичної кривої. Зауваження: Якщо розмірність цього числа в бітах менше розмірності в бітах значень хеш-функції то використовуються тільки ліві біти значення хеш-функції.
  3. Простим числом позначається характеристика поля координат .

Генерування ключів ECDSA[ред. | ред. код]

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

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

  1. Вибирає випадкове або псевдовипадкове ціле число з інтервалу .
  2. Обчислює (кратне) .

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

Замість використання і в якості глобальних системних параметрів, можна фіксувати тільки поле для всіх користувачів і дозволити кожному користувачеві вибирати свою власну еліптичну криву і точку . В цьому випадку певне рівняння кривої , координати точки , а також порядок цієї точки повинні бути включені у відкритий ключ користувача. Якщо поле фіксоване, то апаратна і програмна складові можуть бути побудовані так, щоб оптимізувати обчислення в тому полі. У той же час є величезна кількість варіантів вибору еліптичної кривої над полем .

Переваги ECDSA перед DSA[ред. | ред. код]

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

Практична реалізація[ред. | ред. код]

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

Посилання[ред. | ред. код]

Див. також[ред. | ред. код]

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

EdDSA

Примітки[ред. | ред. код]

  1. 08.08.2002. Цифровая подпись. Эллиптические кривые - MorePC.Ru. www.morepc.ru. Процитовано 2018-04-14. 
  2. http://www.psu.edu/.