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 для еліптичних кривих.
Вибір параметрів
Для підписування повідомлень необхідна пара ключів - відкритий і закритий. При цьому закритий ключ повинен бути відомий тільки тому, хто підписує повідомлення, а відкритий - будь-кому хто бажає перевірити справжність повідомлення. Також загальнодоступними є параметри самого алгоритму.
Параметри алгоритму
- Вибір хеш-функції
. Для використання алгоритму необхідно, щоб повідомлення, яке підписується, було числом. Хеш-функція повинна перетворити будь-яке повідомлення в послідовність бітів, які можна потім перетворити в число.
- Вибір великого простого числа
- порядок однієї з циклічних підгруп групи точок еліптичної кривої. Зауваження: Якщо розмірність цього числа в бітах менше розмірності в бітах значень хеш-функції
то використовуються тільки ліві біти значення хеш-функції.
- Простим числом
позначається характеристика поля координат
.
Генерування ключів ECDSA
Для простоти будемо розглядати еліптичні криві над полем , де
- кінцеве просте поле. Причому, якщо необхідно, конструкцію можна легко адаптувати для еліптичних кривих над іншим полем.
Нехай - еліптична крива, визначена над
, і
- точка простого порядку
кривої
(
). Крива
і точка
є системними параметрами. Число
- просте. Кожен користувач - умовно назвемо його Аліса - конструює свій ключ за допомогою наступних дій:
- Вибирає випадкове або псевдовипадкове ціле число
з інтервалу
.
- Обчислює (кратне)
.
Відкритим ключем користувача Аліси є точка
, а закритим -
.
Замість використання і
в якості глобальних системних параметрів, можна фіксувати тільки поле
для всіх користувачів і дозволити кожному користувачеві вибирати свою власну еліптичну криву
і точку
. В цьому випадку певне рівняння кривої
, координати точки
, а також порядок
цієї точки
повинні бути включені у відкритий ключ користувача. Якщо поле
фіксоване, то апаратна і програмна складові можуть бути побудовані так, щоб оптимізувати обчислення в тому полі. У той же час є величезна кількість варіантів вибору еліптичної кривої над полем
.
Переваги ECDSA перед DSA
ECDSA є дуже привабливим алгоритмом для реалізації цифрового підпису. Найважливішою перевагою ECDSA є можливість його роботи на значно менших полях . Як, загалом, з криптографією еліптичної кривої, передбачається, що бітовий розмір відкритого ключа, який буде необхідний для ECDSA, дорівнює подвійному розміру секретного ключа в бітах. Для порівняння, при рівні безпеки в 80 біт (тобто атакуючому необхідно приблизно
версій підписів для знаходження секретного ключа), розмір відкритого ключа DSA дорівнює, принаймні, 1024 біт, тоді як відкритого ключа ECDSA - 160 біт. З іншого боку розмір підпису однаковий і для DSA, і для ECDSA:
біт, де
— рівень безпеки, який вимірюється в бітах, тобто - приблизно 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.]
Див. також
Примітки
- . www.morepc.ru. Архів оригіналу за 31 грудня 2012. Процитовано 14 квітня 2018.
- http://www.psu.edu/. Архів оригіналу за 27 лютого 2012.
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
ECDSA Elliptic Curve Digital Signature Algorithm algoritm z vidkritim klyuchem dlya stvorennya cifrovogo pidpisu analogichnij za svoyeyu budovoyu DSA ale viznachenij na vidminu vid nogo ne nad kilcem cilih chisel a v grupi tochok eliptichnoyi krivoyi OsoblivostiStijkist algoritmu shifruvannya gruntuyetsya na zadachi diskretnogo logarifma v grupi tochok eliptichnoyi krivoyi Na vidminu vid zadachi prostogo diskretnogo logarifma i zadachi faktorizaciyi cilogo chisla ne isnuye subeksponencialnogo algoritmu dlya zadachi diskretnogo logarifma v grupi tochok eliptichnoyi krivoyi Z ciyeyi prichini sila na odin bit klyucha istotno vishe v algoritmi yakij vikoristovuye eliptichni krivi D Braunom Daniel R L Brown bulo dovedeno sho algoritm ECDSA ne ye bilsh bezpechnim nizh DSA Nim bulo sformulovano obmezhennya bezpeki dlya ECDSA yake prizvelo do nastupnogo visnovku Yaksho grupa eliptichnoyi krivoyi mozhe buti zmodelovana osnovnoyu grupoyu i yiyi hesh funkciya zadovilnyaye pevni obgruntovani pripushennya to ECDSA stijka do ataki na osnovi pidibranogo vidkritogo tekstu z isnuyuchoyi falsifikaciyeyu Algoritm ECDSA v 1999 r buv prijnyatij yak standart ANSI v 2000 r yak standart IEEE i NIST Takozh v 1998 r algoritm buv prijnyatij standartom ISO Nezvazhayuchi na te sho standarti ECP stvoreni zovsim nedavno i znahodyatsya na etapi vdoskonalennya odnim z najbilsh perspektivnih z nih na sogodnishnij den ye ANSI X9 62 ECDSA vid 1999 DSA dlya eliptichnih krivih Vibir parametrivDlya pidpisuvannya povidomlen neobhidna para klyuchiv vidkritij i zakritij Pri comu zakritij klyuch povinen buti vidomij tilki tomu hto pidpisuye povidomlennya a vidkritij bud komu hto bazhaye pereviriti spravzhnist povidomlennya Takozh zagalnodostupnimi ye parametri samogo algoritmu Parametri algoritmu Vibir hesh funkciyi H x displaystyle H x Dlya vikoristannya algoritmu neobhidno shob povidomlennya yake pidpisuyetsya bulo chislom Hesh funkciya povinna peretvoriti bud yake povidomlennya v poslidovnist bitiv yaki mozhna potim peretvoriti v chislo Vibir velikogo prostogo chisla q displaystyle q poryadok odniyeyi z ciklichnih pidgrup grupi tochok eliptichnoyi krivoyi Zauvazhennya Yaksho rozmirnist cogo chisla v bitah menshe rozmirnosti v bitah znachen hesh funkciyi H x displaystyle H x to vikoristovuyutsya tilki livi biti znachennya hesh funkciyi Prostim chislom p displaystyle p poznachayetsya harakteristika polya koordinat Fp displaystyle F p Generuvannya klyuchiv ECDSA Dlya prostoti budemo rozglyadati eliptichni krivi nad polem Fp displaystyle F p de Fp displaystyle F p kinceve proste pole Prichomu yaksho neobhidno konstrukciyu mozhna legko adaptuvati dlya eliptichnih krivih nad inshim polem Nehaj E displaystyle E eliptichna kriva viznachena nadFp displaystyle F p i P displaystyle P tochka prostogo poryadku q displaystyle q krivoyi E displaystyle E Fp displaystyle F p Kriva E displaystyle E i tochka P displaystyle P ye sistemnimi parametrami Chislo p displaystyle p proste Kozhen koristuvach umovno nazvemo jogo Alisa konstruyuye svij klyuch za dopomogoyu nastupnih dij Vibiraye vipadkove abo psevdovipadkove cile chislo x displaystyle x z intervalu 1 q 1 displaystyle 1 q 1 Obchislyuye kratne Q xP displaystyle Q xP Vidkritim klyuchem koristuvacha Alisi A displaystyle A ye tochka Q displaystyle Q a zakritim x displaystyle x Zamist vikoristannya E displaystyle E i P displaystyle P v yakosti globalnih sistemnih parametriv mozhna fiksuvati tilki pole Fp displaystyle F p dlya vsih koristuvachiv i dozvoliti kozhnomu koristuvachevi vibirati svoyu vlasnu eliptichnu krivu E displaystyle E i tochku P displaystyle P displaystyle in E Fp displaystyle E F p V comu vipadku pevne rivnyannya krivoyi E displaystyle E koordinati tochki P displaystyle P a takozh poryadok q displaystyle q ciyeyi tochki P displaystyle P povinni buti vklyucheni u vidkritij klyuch koristuvacha Yaksho pole Fp displaystyle F p fiksovane to aparatna i programna skladovi mozhut buti pobudovani tak shob optimizuvati obchislennya v tomu poli U toj zhe chas ye velichezna kilkist variantiv viboru eliptichnoyi krivoyi nad polem Fp displaystyle F p Perevagi ECDSA pered DSAECDSA ye duzhe privablivim algoritmom dlya realizaciyi cifrovogo pidpisu Najvazhlivishoyu perevagoyu ECDSA ye mozhlivist jogo roboti na znachno menshih polyah Fp displaystyle F p Yak zagalom z kriptografiyeyu eliptichnoyi krivoyi peredbachayetsya sho bitovij rozmir vidkritogo klyucha yakij bude neobhidnij dlya ECDSA dorivnyuye podvijnomu rozmiru sekretnogo klyucha v bitah Dlya porivnyannya pri rivni bezpeki v 80 bit tobto atakuyuchomu neobhidno priblizno 280 displaystyle 2 80 versij pidpisiv dlya znahodzhennya sekretnogo klyucha rozmir vidkritogo klyucha DSA dorivnyuye prinajmni 1024 bit todi yak vidkritogo klyucha ECDSA 160 bit Z inshogo boku rozmir pidpisu odnakovij i dlya DSA i dlya ECDSA 4t displaystyle 4t bit de t displaystyle t riven bezpeki yakij vimiryuyetsya v bitah tobto priblizno 320 bit dlya rivnya bezpeki v 80 bit Praktichna realizaciyaNa sogodnishnij den realizaciya elektronnih cifrovih pidpisiv zdijsnyuyutsya programnim chinom Dlya stvorennya podibnih produktiv vikoristovuyut specialni programni paketi sho dozvolyayut stvoryuvati kriptografichni dodatki z vikoristannyam riznih zovnishnih pristroyiv bezpeki PosilannyaNeal Koblitz and Alfred Menezes 1995 8 serpnya 2017 u Wayback Machine Another Look at Generic Groups Digital Signature Standard includes info on ECDSA 27 grudnya 2016 u Wayback Machine Div takozhEliptichna kriptografiyaPrimitki www morepc ru Arhiv originalu za 31 grudnya 2012 Procitovano 14 kvitnya 2018 http www psu edu Arhiv originalu za 27 lyutogo 2012