Перегляд вихідного коду сторінки Еліптична криптографія

'''Еліптична криптографія'''&nbsp;— розділ [[Криптографія|криптографії]], який вивчає [[Асиметричні алгоритми шифрування|асиметричні криптосистеми]], засновані на [[Еліптична крива|еліптичних кривих]] над [[Поле Галуа|скінченними полями]]. Головна перевага еліптичної криптографії полягає в тому, що на сьогодні існування [[Клас складності PSPACE|субекспоненціальних]] [[алгоритм]]ів вирішення завдань [[Дискретний логарифм|дискретного логарифмування]] не є відомим.
Використання еліптичних кривих для створення криптосистем було незалежно запропоновано {{не перекладено|Ніл Коблиц|Нілом Коблицем||Neal Koblitz}} та {{не перекладено | Міллер Віктор |Віктором Міллером||Victor S. Miller}} у [[1985]] році.<ref>{{книга | автор = Jeffrey Hoffstein, Jill Pipher, Joseph H. Silverman | частина = | назва = An introduction to mathematical cryptography | оригінал = | посилання = http://books.google.ru/books?id=XLY9AnfDhsYC&lpg=PA301 | відповідальний = | видання = | місце = | видавництво = Springer | рік = | тому = | сторінка = 301 | сторінок = 523 | серія = | isbn = | тираж =}}</ref>

== Вступ ==
Асиметрична криптографія заснована на складності вирішення деяких математичних задач. Ранні криптосистеми з відкритим ключем, такі як алгоритм [[RSA]], криптостійкі завдяки тому, що складно розкласти велике число на [[прості множники]]. При використанні алгоритмів на [[Еліптична крива|еліптичних кривих]] припускається, що не існує субекспоненційних [[алгоритм]]ів для вирішення завдання [[Дискретний логарифм|дискретного логарифмування]] в групах їх точок. При цьому [[порядок групи]] точок еліптичної кривої визначає складність завдання. Вважається, що для досягнення такого ж [[Рівень криптостійкості|рівня криптостійкості]] як і в RSA, потрібні групи менших порядків, що зменшує витрати на зберігання та передачу інформації. Наприклад, на конференції RSA 2005 [[Агентство національної безпеки]] оголосила про створення «Suite B», у якому використовуються виключно алгоритми еліптичної криптографії, причому для захисту інформації класифікованої до «Top Secret» використовуються всього лише 384-бітові ключі.

== Еліптичні криві над скінченними полями ==
{{main | Еліптична крива}}

Еліптичною кривою називається множина точок <math> (x, y) </math>, що задовольняють рівняння:
: <math> y^2 + a_1xy + a_3y = x^3 + a_2x^2 + a_4x + a_6 </math>
Це рівняння може розглядатися над довільними полями і, зокрема, над [[Поле Галуа|скінченними полями]], що викликає особливу зацікавленість для криптографії.

У криптографії еліптичні криві розглядаються над двома типами скінченних полів: простими полями непарної [[Характеристика (алгебра)|характеристики]] (<math>\mathbb{Z}_p</math>, де <math>p > 3</math>&nbsp;— просте число) і полями характеристики 2 (<math>GF(2^m)</math>).

== Еліптичні криві над полями непарної характеристики ==
Над полем <math> \mathbb {Z}_p </math> характеристики <math> p> 3 </math> рівнянню еліптичної кривої ''E'' можна надати вигляд:
: <math> E: \quad y^2 = x^3 + Ax + B \pmod p, </math>
де <math> A, B \in \mathbb {Z}_p </math>&nbsp;— константи, що задовольняють <math> 4A^3 + 27B^2 \not \equiv 0 \pmod p </math>.

Групою точок еліптичної кривої ''E'' над полем <math> \mathbb {Z}_p </math> називається множина пар <math> (x, y) </math>, що лежать на ''E'', об'єднаних з нульовим елементом <math>\mathcal{O}</math>:
: <math>E(\mathbb{Z}_p) = \mathcal{O} \cup \left\{ (x, y) \in \mathbb{Z}_p \times \mathbb{Z}_p | y^2 \equiv x^3 + Ax + B \pmod p \right\}. </math>

Слід зазначити, що в <math> \mathbb {Z} _p </math> у кожного ненульового елемента є або два квадратні корені, або нема жодного, тому точки еліптичної кривої розбиваються на пари виду <math> (x, y) </math> і <math> (x, -y) </math>.

=== Приклад ===
Розглянемо еліптичну криву <math>y^2 = x^3 + 3x + 2 </math> над полем <math> \mathbb {Z}_5 </math>. На цій кривій, зокрема, лежить точка <math> (1,1) </math>, оскільки <math>1^2 \equiv 1^3 + 3 \cdot 1 + 2 \pmod 5 </math>.

== Теорема Гассе ==

[[Теорема Гассе про еліптичні криві]] стверджує, що кількість точок на еліптичній кривій близька до розміру скінченного поля:
: <math> (\sqrt p - 1)^2 \leqslant | E (\mathbb {Z}_p) | \leqslant (\sqrt p + 1)^2, </math>

звідки:
: <math> \left| | E (\mathbb {Z} _p) | -p \right| < 2\sqrt p + 1.</math>

== Еліптичні криві над полями характеристики 2 ==
Над полем характеристики 2 розглядають два види еліптичних кривих:
* Суперсингулярна крива
*: <math>y^2 + ay = x^3 + bx + c</math>
* Несуперсингулярна крива
*: <math>y^2 + axy = x^3 + bx^2 + c</math>

Особлива зручність суперсингулярних еліптичних кривих полягає в тому, що для них легко обчислити порядок, тоді як обчислення порядку несуперсингулярних кривих викликає труднощі. Суперсингулярні криві зручні для створення саморобної ЕСС-криптосистеми. Для їх використання можна обійтися без трудомісткої процедури обчислення порядку.

== Проєктивні координати ==
Для обчислення суми пари точок на еліптичній кривій потрібно не тільки кілька операцій додавання і множення в <math> \mathbb {F}_q </math>, а й операція [[Обернений елемент|обернення]], тобто для заданого <math> x \in \mathbb{F}_q </math> знаходження такого <math> y \in \mathbb {F}_q </math>, що <math> xy = 1 </math>, яка на один-два порядки повільніша, ніж множення. На щастя, точки на еліптичній кривій можуть бути представлені в різних [[система координат|системах координат]], які не вимагають використання обернення при додаванні точок:
* У [[проєктивна площина|проєктивній]] системі координат кожна точка <math> (x, y) </math> задається трьома координатами <math> (X, Y, Z) </math>, які задовольняють співвідношенням:
*: <math> x = \frac{X}{Z} </math>, <math> y = \frac{Y}{Z} </math>.
* У системі координат [[Карл Густав Якоб Якобі|Якобі]] точка також задається трьома координатами <math> (X, Y, Z) </math> зі співвідношеннями: <math> x = \frac{X}{Z^2} </math>, <math> y = \frac{Y}{Z^3} </math>.
* У системі координат Лопес-Дахаб ({{lang-zh|洛佩斯 · 達哈卜}}, {{lang-la|Lopez-Dahab}}) Виконується співвідношення: <math> x = \frac{X}{Z} </math>, <math> y = \frac{Y}{Z^2} </math>.
* У модифікованій системі координат Якобі використовуються 4 координати <math> (X, Y, Z, aZ^4) </math> з тими ж співвідношеннями.
* У системі координат Чуднівського-Якобі використовується 5 координат <math> (X, Y, Z, Z^2, Z^3) </math>.

Важливо зазначити, що можуть існувати різні найменування&nbsp;— наприклад, [[IEEE P1363|IEEE P1363-2000]] називає проєктивними координатами те, що зазвичай називають координатами Якобі.

== Реалізація шифрування ==
Конкретні реалізації алгоритмів шифрування на еліптичній кривій описані нижче. Тут ми розглянемо загальні принципи еліптичної криптографії.

=== Набір параметрів ===
Для використання еліптичної криптографії всі учасники повинні узгодити всі параметри, що визначають еліптичну криву, тобто набір параметрів криптографічного протоколу. Еліптична крива визначається константами <math> a </math> і <math> b </math> з рівняння (2). [[Абелева група|Абелева]] підгрупа точок є [[циклічна група|циклічною]] і задається однією [[Породжувальна множина групи|породжує]] точкою '' G ''. При цьому кофактор <math> h = \frac{|E|}{n} </math>, де '' n ''&nbsp;— [[Порядок елемента|порядок]] точки '' G '', повинен бути невеликим (<math> h \le 4 </math>, бажано навіть <math> h = 1 </math>).

Отже, для поля характеристики 2 характерний набір параметрів: <math> (m, f, a, b, G, n, h) </math>, а для скінченного поля <math> \mathbb {Z}_p </math>, де <math> p> 3 </math>, набір параметрів: <math> (p, a, b, G, n, h) </math>.

Існує кілька рекомендованих наборів параметрів:
* NIST<ref>{{Cite web |url=http://csrc.nist.gov/groups/ST/toolkit/documents/dss/NISTReCur.pdf |title=Recommended Elliptic Curves for Government Use |accessdate=18 грудня 2015 |archive-date=5 червня 2011 |archive-url=https://web.archive.org/web/20110605101110/http://csrc.nist.gov/groups/ST/toolkit/documents/dss/NISTReCur.pdf }}</ref>
* SECG<ref>{{Cite web |url=http://www.secg.org/download/aid-386/sec2_final.pdf |title=SEC 2: Recommended Elliptic Curve Domain Parameters |accessdate=31 травня 2005 |archiveurl=https://web.archive.org/web/20050531214022/http://www.secg.org/download/aid-386/sec2_final.pdf |archivedate=31 травня 2005 |deadurl=no }}</ref>

Для створення власного набору параметрів необхідно:
# Вибрати набір параметрів.
# Знайти еліптичну криву, що задовольняє цьому набору параметрів.

Для знаходження кривої для заданого набору параметрів використовуються два методи:
* Вибрати випадкову криву, потім скористатися алгоритмом підрахунку точок.<ref>[http://www-math.mit.edu/~musiker/schoof.pdf Schoof's algorithm]{{Недоступне посилання|date=квітень 2019 |bot=InternetArchiveBot }}</ref><ref>{{Cite web |url=http://www.esat.kuleuven.be/cosic/eurocrypt2000/pdf/fre-sea.pdf |title=Schoof-Elkies-Atkin algorithm |accessdate=26 липня 2011 |archiveurl=https://web.archive.org/web/20110726052703/http://www.esat.kuleuven.be/cosic/eurocrypt2000/pdf/fre-sea.pdf |archivedate=26 липня 2011 |deadurl=yes }}</ref>
* Вибрати точки, після чого побудувати криву за цими точкам, використовуючи техніку множення.

Існує декілька класів [[Криптографічна стійкість|криптографічно «слабких»]] кривих, яких слід уникати:
* Криві над <math> \mathbb{F}_{2^m} </math>, де <math> m </math>&nbsp;— не просте число. Шифрування на цих кривих піддається [[Атака Вейля|атакам Вейля]].
* Криві з <math> | E (\mathbb{F}_q) | = Q </math> вразливі до атаки відображенням точки даної кривої на аддитивну групу поля <math> \mathbb{F}_q </math>.

=== Швидка редукція (NIST-криві) ===
Розподіл по модулю '' p '' (необхідний для операцій додавання і множення) може виконуватися швидше, якщо як '' p '' вибрати просте число близьке до ступеня числа 2.
Зокрема, в ролі '' p '' може виступати просте [[число Мерсенна]]. Наприклад, хорошим вибором є <math> p = 2 ^ {251} - 1 </math> або <math> p = 2 ^ {256} - 2 ^ {32} - 2 ^ 9 - 2 ^ 8 - 2 ^ 7 - 2 ^ 6 - 2 ^ 4 - 1 </math>. [[Національний інститут стандартів і технології]] (NIST) рекомендує використовувати такі прості числа подібні до p.

Порівняно з [[Редукція Барретта|алгоритмом Барретта]], може бути на порядок швидшим.<ref>{{cite journal |first=M. |last=Brown |first2=D. |last2=Hankerson |first3=J. |last3=Lopez |first4=A. |last4=Menezes |title=Software Implementation of the NIST Elliptic Curves Over Prime Fields |journal=Topics in Cryptology&nbsp;– CT-RSA 2001 |series=Lecture Notes in Computer Science |year=2001 |volume=2020 |pages=250–265 |doi=10.1007/3-540-45353-9_19 |isbn=978-3-540-41898-6 }}</ref> Вища швидкість цього методу є більш практичною ніж теоретичною, і полягає в тому, що операції з числами близькими до ступенів двійки ефективніше виконуються комп'ютерами [[Бітові операції|бітовими операціями]].

Ще одною перевагою кривих, рекомендованих NIST, є вибір значення <math> a = -3 </math>,&nbsp;— це прискорює операцію додавання в координатах Якобі.

=== Еліптичні криві, рекомендовані NIST ===
NIST рекомендує 15 еліптичних кривих, багато з яких були отримані Jerry Solinas (NSA) на базі напрацювань {{нп3 |Ніл Коблиц|Ніла Коблица|| Neal Koblitz}}<ref>{{книга | автор = Neal Koblitz | заголовок = Random Curves: Journeys of a Mathematician|посилання=http://books.google.ru/books?id=p2QalcsaNtIC&pg=PA312&|видавництво=Springer|рік=2009 | сторінки = 312-313 | сторінок = 402 | isbn = 9783540740780 | qoute = "In 1991 I proposed using certain curves … This idea was developed and improved upon by Jerry Solinas of NSA. The very first paper ever presented publicly ..by an NSA nenber was Jerry's analysis "}}</ref>. Зокрема, [[Федеральні стандарти обробки інформації|FIPS]] 186-3<ref>[http://csrc.nist.gov/publications/fips/fips186-3/fips_186-3 .pdf FIPS 186-3]{{Недоступне посилання|date=липень 2019 |bot=InternetArchiveBot }} // NIST, 2009; застарів в 2013 році з виходом FIPS 186-4</ref> рекомендує 10 скінченних полів. Деякі з них:
* Поля <math> \mathbb {F} _p </math>, де просте '' p '' має довжину 192, 224, 256, 384 або 521<ref>Може здатися, що в цій послідовності допущено помилку. Однак, остання величина саме 521, а не 512 бітів.</ref> [[біт]].
* Поля <math> \mathbb {F} _ {2 ^ m} </math>, де ''m'' = 163, 233, 283, 409 або 571.

Причому для кожного скінченного поля рекомендують одну еліптичну криву. Ці скінченні поля та еліптичні криві вибрані, як часто помилково вважають, завдяки високому рівню безпеки. За заявами NIST їх вибір був обґрунтований ефективністю програмної реалізації.<ref>[[Даніель Джуліус Бернштайн|Daniel J. Bernstein]], Tanja Lange, [http://www.hyperelliptic.org/tanja/vortraege/20130531.pdf Security dangers of the NIST curves ] {{Webarchive|url=https://web.archive.org/web/20151220022548/https://www.hyperelliptic.org/tanja/vortraege/20130531.pdf |date=20 грудня 2015 }} // 2013.09.16: «Why did NIST choose these curves? * Most people we have asked: security * Actual NIST design document: eficiency» ([http://cr.yp.to/talks/2013.05.31/slides -dan + tanja-20130531-4x3.pdf]{{Недоступне посилання|date=липень 2019 |bot=InternetArchiveBot }})</ref> Є сумніви в безпеці принаймні декількох з них.<ref>{{cite web | url = http: //safecurves.cr.yp.to/index.html | title = SafeCurves: choosing safe curves for elliptic-curve cryptography. | author = Daniel J. Bernstein and Tanja Lange | date = 2013.11.18 | publisher = safecurves.cr.yp.to | lang = en | accessdate = 2013 -12-20 }}{{Недоступне посилання|date=липень 2019 |bot=InternetArchiveBot }}</ref><ref>{{cite news | url = http: //www.computerra.ru/82902/elliptic-crypto/ | title = Сноуден і еліптичне крипто: Bitcoin і TOR поза підозрою, але що з іншими проєктами? | author = Євген Золотов | date = 16 вересня 2013 | publisher = Компьютерра | accessdate = 2013-12-20 | archive-date = 21 січня 2018 | archive-url = https://web.archive.org/web/20180121053948/http://www.computerra.ru/82902/elliptic-crypto/ }}</ref><ref>Dr Michael Scott, [http://www.certivox.com/blog/bid/344797/Backdoors-in-NIST-elliptic-curves Backdoors in NIST elliptic curves]{{Недоступне посилання}}, Oct 24, 2013: «The curves themselves were suggested by Jerry Solinas who worked at the NSA.»</ref>

=== Розмір ключа ===
Найшвидшим алгоритмам, що виконують завдання [[Дискретний логарифм|дискретного логарифмування]] на еліптичних кривих, як от [[алгоритм Шенкса]] і [[ρ-метод Полларда дискретного логарифмування|ρ-метод Полларда]], необхідно <math> O ( \sqrt {n}) </math> операцій. Тому розмір поля повинен як мінімум в два рази перевищувати розмір ключа. Наприклад, для 128-бітного ключа рекомендується використовувати еліптичну криву над полем <math> \mathbb {F} _p </math>, де ''p'' має довжину 256 бітів.

Найскладніші публічно зламані схеми на еліптичних кривих містили 112-бітний ключ для скінченного простого поля і 109-бітний ключ для скінченного поля характеристики 2.

У липні [[2009]] року, кластер з більше двохсот [[PlayStation 3|Sony Playstation 3]] за 3,5 місяці знайшов 109-бітний ключ. У квітні [[2004]] з використанням 2600 комп'ютерів протягом 17 місяців знайдено ключ над полем характеристики 2.

== Застосування ==
Більшість криптосистем сучасної криптографії природним чином можна «перекласти» на еліптичні криві. Головна ідея полягає в тому, що відомий алгоритм, який використовується для конкретних скінченних груп переписується для використання груп раціональних точок еліптичних кривих:
* [[Elliptic Curve Digital Signature Algorithm|ECDSA]] алгоритм, що ґрунтується на [[Електронний цифровий підпис|ЕЦП]].
* [[Протокол Діффі — Геллмана на еліптичних кривих|ECDH]] алгоритм заснований на [[Протокол Діффі — Геллмана|алгоритмі Діффі&nbsp;— Геллмана]].
* [[ECIES]] ({{lang-en|Elliptic Curve Integrated Encryption Scheme}})&nbsp;— також ґрунтується на еліптичних кривих.
* [[ECMQV]] алгоритм, що ґрунтується на [[MQV]], протоколі розподілу ключів Менезеса-Кью-Венстоуна.
* [[Факторизація Ленстри за допомогою еліптичних кривих]]
* [[Dual EC DRBG]]

Необхідно відзначити, що безпека таких систем цифрового підпису спирається не тільки на криптостійкість алгоритмів шифрування, але й на криптостійкість використаних [[криптографічна геш-функція|криптографічних геш-функцій]] і [[Генерація випадкових чисел|генераторів випадкових чисел]].

З огляду 2013 найчастіше використовуються криві: nistp256, nistp384, nistp521, secp256k1, secp384r1, secp521r1<ref>Bos et al, [http://cryptome.org/2013/11/ecc-practice.pdf Elliptic Curve Cryptography in Practice ] {{Webarchive|url=https://web.archive.org/web/20160207133548/http://cryptome.org/2013/11/ecc-practice.pdf |date=7 лютого 2016 }} // MSR-TR-2013-119, November +2013</ref>

== Примітки ==
{{reflist|2}}

== Посилання ==
* {{Книга | автор = Болотов А.А., Гашков С.Б., Фролов А.Б., Часовських А.А. | назва = Алгоритмічні основи еліптичної криптографії | місце = Москва | видавництво = МЕІ | рік = 2000 | сторінок = 100 | посилання = http://new.math.msu.su/department/dm/dmmc/PUBL1/elcr_ps.zip | archivedate = 4 березня 2016 | archiveurl = https://web.archive.org/web/20160304200513/http://new.math.msu.su/department/dm/dmmc/PUBL1/elcr_ps.zip }}
* {{Книга | автор = Болотов А.А., Гашков С.Б., Фролов А.Б., Часовських А.А. | назва = Елементарне введення в еліптичну криптографію | місце = Москва | видавництво = КомКнига | рік = 2006 | сторінок = 280}}

{{Крипто навігація}}
{{Алгебричні криві}}
{{ВП-портали|Програмування|Інформаційні технології|Математика}}
{{вичитати}}


{{Crypto-stub}}

[[Категорія:Криптографія]]
[[Категорія:Криптографія з відкритим ключем]]
[[Категорія:Стандарти криптографії]]
[[Категорія:Електронний підпис]]
[[Категорія:Еліптичні криві]]